Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Основной теоремой, описывающей производящие функции последовательностей, являющихся решениями линейных однородных рекуррентных соотношений с постоянными коэффициентами, является следующее утверждение.
Теорема 2.5 Пусть - последовательность с комплексными членами и - комплексные числа, причем . Тогда следующие три условия равносильны:
(2.7)
где
где
соответственно кратности - многочлен от n степени не выше
Доказательство.
Пусть последовательность является решением рекуррентного соотношения (2.7), т.е. для любого выполняется равенство
(2.8)
Положим
Тогда применяя линейную операцию и сдвиг начала получим
но в силу (2.8) для любого поэтому . Следовательно, .
Умножая обе части этого равенства на и группируя соответствующие члены получим
Очевидно, выражение
является многочленом от степени не выше .
Таким образом,
где Q многочлен от степени не выше
(2)(3) Сейчас мы будем рассматривать выражение не как формальный степенной ряд, а как рациональную функцию.
Разложим многочлен на линейные множители. (Так как поле комплексных чисел алгебраически замкнуто, а мы находимся в этом поле, то данное разложение всегда можно осуществить). Пусть
где
Так как Q то Q(x)= Следовательно,
Выразим рациональную функцию в виде суммы простых дробей
где - комплексные числа.
Разложим функцию в ряд Маклорена.
(2.9)
Очевидно, ряд Маклорена функции является суммой степенных рядов вида (2.9). Следовательно,
Согласно основному принципу теории производящих функций имеем
(Здесь мы опять рассматриваем выражение как формальный степенной ряд.)
Следовательно,
В силу леммы 2.3 выражение
является многочленом от n степени не выше . Таким образом,
где - различные корни уравнения
соответственно кратности - многочлен от степени не выше где i=1,…,s.
Для того, чтобы показать, что всякая последовательность вида
где - произвольные комплексные числа является решением рекуррентного соотношения (2.7) в силу леммы 2.2 достаточно показать, что последовательность , где - корень уравнения
кратности , является решением рекуррентного соотношения (2.7), т.е. показать, что
Положим
Тогда
Вынося за знак суммы и разлагая по формуле бинома Ньютона, получим
Меняя порядок суммирования, имеем
(2.10)
Пусть
Заметим, что Поскольку является корнем многочлена кратности (1), то согласно лемме 2.4
, т.е. L[nmn] = 0, так как .
Таким образом, последовательность является решением рекуррентного соотношения (2.7).
Теорема 2.5 показывает, что общее решение линейного однородного рекуррентного соотношения
(2.11)
где - произвольные комплексные числа имеет вид
где - произвольные комплексные числа, а - различные корни уравнения
(2.12)
соответственно кратности .
Уравнение (2.12) называется характеристическим уравнением рекуррентного соотношения (2.11).
Задание начальных значений
приводит к системе k линейных уравнений
из которой коэффициенты находятся однозначно. Пример.
1. Найти решение рекуррентного соотношения
,
удовлетворяющего начальным значениям
.
Характеристическое уравнение этого соотношения
имеет корни = 1 и = 3.
Следовательно, общее решение данного рекуррентного соотношения имеет вид
.
Используя начальные значения, составляем систему уравнений для нахождения
Ее решением являются .
Таким образом, требуемым решением данного рекуррентного соотношения является последовательность
2. Найдем формулу для -го члена последовательности Фибоначчи. Последовательность Фибоначчи является решением рекуррентного соотношения
(2.13)
и удовлетворяет начальным значениям и , т.е. является последовательностью
1,2,3,5,8,13,...
Однако более удобно добавить к этой последовательности вначале числа 0 и 1, т.е. рассмотреть последовательность
0,1,1,2,3,5,8,13,...
Ясно, что эта последовательность удовлетворяет тому же самому рекуррентному соотношению (2.13) и начальным значениям . На самом деле выбор начальных значений для последовательности Фибоначчи не важен; существенные свойства этой последовательности определяются соотношением (2.13) (иногда полагают ).
Характеристическое уравнение соотношения (2.13) имеет корни
Следовательно, общее решение данного рекуррентного соотношения имеет вид
Используя начальные значения, составляем систему уравнений для нахождения ,;
Отсюда находим, что и поэтому формула для -го члена последовательности Фибоначчи имеет вид
На первый взгляд кажется удивительным, что это выражение при всех натуральных значениях принимает целые значения.
Покажем как, используя теорему 2.5, можно вывести формулы для суммы квадратов, кубов и т.д. натуральных чисел.
Прежде всего, покажем, что последовательности
являются возвратными.
Если то Следовательно,
(2.14)
Увеличивая на единицу, получим
(2.15)
Вычитая почленно (2.14) из (2.15), получим
или
(2.16)
Увеличивая в (2.16) на единицу, будем иметь
(2.17)
Откуда (вычитая почленно (2.16) из (2.17))
или
Таким образом, последовательность является решением линейного однородного рекуррентного соотношения третьего порядка.
Подобным образом можно показать, что последовательность является решением рекуррентного соотношения
и вообще последовательность является решением рекуррентного соотношения
Теперь покажем, что если последовательность удовлетворяет рекуррентному соотношению
,
где - произвольные комплексные числа, то последовательность
удовлетворяет некоторому рекуррентному соотношению вида
и найдем коэффициенты
Как было показано ранее, если , то . Но в силу теоремы 2.5 где , а Р(х) – многочлен от х степени не выше k- 1.
Следовательно,
Найдем коэффициенты многочлена (1 — x)Q(x). Очевидно,
Тогда в силу теоремы 2.5 последовательность должна быть решением рекуррентного соотношения
(2.18)
Таким образом, последовательность является решением рекуррентного соотношения
(2.19)
и вообще последовательность является решением рекуррентного соотношения
Характеристическим уравнением соотношения (2.19) является уравнение
,
которое имеет один корень кратности 4. Следовательно, общее решение соотношения (2.18) имеет вид
С учетом начальных значений
имеем систему уравнений
Ее решением являются
Таким образом,
Аналогично можно показать, что
(2.20)
и вообще найти соответствующие формулы для ,
Так как то из (2.20) следует неожиданное, на первый взгляд, равенство
Рассмотрим линейное рекуррентное соотношение с постоянными коэффициентами
(2.21)
Согласно теореме 2.1 общее решение этого рекуррентного соотношения можно представить как сумму общего решения рекуррентного соотношения
и некоторого решения соотношения (2.21). При нахождении некоторого решения рекуррентного соотношения (2.21) оказывается полезной следующая теорема.
Теорема 2.6 Для любого линейного рекуррентного соотношения с постоянными коэффициентами
(2.22)
где - многочлен от степени и существует решение вида , где - многочлен от степени , если не является корнем характеристического уравнения
(2.23)
и вида , если -корень характеристического уравнения (2.23) кратности .
Доказательство. Рассмотрим два случая.
1) . В этом случае будем искать решение в виде , где
Рассматривая коэффициенты как неизвестные, покажем, что их можно определить так, чтобы выполнялось равенство:
, (2.24)
или ,
Применяя равенство (2.10), получим
(2.25)
где и
Приравнивая выражение (2.25) многочлену и приравнивая коэффициенты при одинаковых степенях , получим уравнений с неизвестными :
(2.26)
Так как определитель этой системы равен (т.к. ), то существуют такие , что выполняется (2.26) и, следовательно, также выполняется равенство (2.24), т.е. последовательность является решением рекурентного соотношения (2.22).
2) Пусть теперь является корнем характеристического уравнения кратности . В этом случае будем искать решение в виде
(2.27)
Очевидно, для того, чтобы (2.27) было решением рекуррентного соотношения (2.22), необходимо выполнения равенства
,
или равенства
(2.28)
Опять применяя (2.10) и помня, что согласно лемме 2.4
Имеем:
(2.29)
Подставляя выражение (2.29) в равенство (2.28) и приравнивая после этого коэффициенты при одинаковых степенях n в обоих частях равенства (2.28), опять получаем систему уравнений для определения
(2.30)
Определитель системы (2.30) равен
поэтому определяются однозначно, и мы получаем решение вида (2.27)
Пример.
1. Предположим, что в аквариуме находится шесть литров воды. Каждую неделю один литр испаряется, и в аквариум добавляют два литра воды, предварительно вылив один литр. Известно, что в одном литре воды находится 0,01 г. соли, а наличие в аквариуме 0,1 г. соли является критическим для его обитателей. При испарении соль остается. Спрашивается, может ли количество соли в аквариуме достичь критического уровня?
Обозначим через содержание соли в аквариуме в конце -й недели после взятия и добавления воды. Тогда
или
(2.31)
где .
Для того, чтобы применить теорему 2.6 считаем, что т.е. а . Так как число 1 не является корнем характеристического уравнения, то должно существовать решение в виде , где - многочлен от нулевой степени, т.е. в виде Подставляя в (2.31) имеем . Откуда .
Общим решением рекуррентного соотношения является последовательность . Следовательно, общее решение для (2.31) имеет вид . Из начального условия находим, что Таким образом,
.
Итак, мы видим, что
- содержание соли в аквариуме всегда меньше 0,1 г. ;
- с увеличением n величина все ближе к 0 и, следовательно, содержание соли становится все ближе к 0,1.
2. Найти наибольшее число частей, на которые делят плоскость n прямых. Обозначим это число через . Очевидно, для того чтобы было максимальным необходимо провести -ю прямую так, чтобы она пересекала все ранее проведенные прямые. Тогда на ней будет n точек пересечения, которые разбивают ее на части. Поскольку каждая из этих частей должна быть границей двух частей плоскости, одна из которых образована прямыми, а другая, новая, образована путем добавления -ой прямой, получаем новых частей плоскости. Это дает
.
Очевидно, . Общим решением рекуррентного соотношения является произвольная константа . Частное решение рекуррентного соотношения
(2.32)
будем искать в виде поскольку - корень характеристического уравнения . Подставляя в (2.32), имеем
Приравнивая коэффициенты при и свободные члены, получим .
Откуда Следовательно, общее решение рекуррентного соотношения (2.32) имеет вид Из начального условия находим, что Таким образом, требуемым решением является .
3. Найти наибольшее число частей, на которые произвольно расположенных плоскостей делят пространство.
Обозначим это число через , а через - соответствующую величину для плоскостей. Для того, чтобы было наибольшим каждая плоскость должна пересекать остальные. Любая плоскость пересекает плоскостей по прямым. Как было показано выше, наибольшее число частей на которые эти прямые могут разделить плоскость равно , каждая из которых является границей старой и новой частей пространства. Это дает дополнительно частей пространства. Поэтому
Очевидно, .
Решая это рекуррентное соотношение получим
2.3 Линейные рекуррентные соотношения с переменными коэффициентами
Гарантированного способа решения линейных рекуррентных соотношений с переменными коэффициентами не существует, однако имеется несколько приемов, которые могут помочь в решении подобных соотношений.
1. Если коэффициентами являются многочлены, то бывает полезно перейти к соотношению между производящими функциями. Например, рассмотрим следующее рекуррентное соотношение
Используя это соотношение, перейдем к соотношению между производящими функциями. Пусть и Тогда
(2.33)
но . Подставив в (2.33) получим
или
(2.34)
Решая это дифференциальное уравнение получим , но
Приравнивая коэффициенты при имеем
Вообще любое рекуррентное соотношение с коэффициентами, которые являются многочленами от , может быть сведено к дифференциальному уравнению вида (2.34).
2. Если рекуррентное соотношение является соотношением первого порядка
(2.35)
то умножая обе его части на множитель получим
или, обозначив через
Откуда
Складывая эти равенства, получим
т.е.
Таким образом, любое рекуррентное соотношение вида (2.35) можно свести к простой сумме.
Оба из перечисленных подхода к решению линейных рекуррентных соотношений с переменными коэффициентами имеют серьезные недостатки. Первый метод может привести к трудно поддающимся решению дифференциальным уравнениям. Второй может привести к непостижимой для нас сумме.
3. Задача о минимальном остове
Определение 3.1 Остовом связного графа называется его подграф, являющийся деревом, вершины которого совпадают с вершинами данного графа.
Задача о минимальном остове формулируются следующим образом: для произвольного связного графа и функции (приписывающей каждому ребру графа положительное действительное число, называемое его весом) найти его остов для которого сумма весов имела бы наименьшее возможное значение (сумма берется по всем ребрам остова ). (В дальнейшем такой остов будем называть минимальным.)
Нетрудно видеть, что задача о минимальном остове допускает, например, следующую интерпретацию. Требуется соединить несколько городов дорогами (причем не обязательно непосредственно каждую пару городов), так чтобы суммарная стоимость прокладки дорог была бы наименьшей, если известна стоимость прокладки дороги между каждой парой городов.
В самом деле, постоим граф, вершины которого соответствует городам, а ребра – дорогам, которые могут быть положены между городами. Припишем каждому ребру вес, который равен стоимости строительства соответствующей дороги. Составление проекта строительства дорог теперь можно вести к построению для данного графа его остова наименьшего веса. Это возможно в силу того, что, во-первых, ребра любого остова соединяют каждую вершину (город) графа с любой другой вершиной (городом) и, во-вторых, минимальный остов представляет собой совокупность дорого наименьшей общей стоимости.
Рассмотрим алгоритм решения задачи о минимальном остове, известный под названием алгоритм Краскала.
Перед началом работы алгоритм все ребра исходного графа считаются непомеченными и ни один из букетов не сформирован. (Букетом мы здесь называем множество, состоящее из некоторых вершин исходного графа.)
Если имеет место случай а), то вернуться к началу 3. Если имеет место случай b), то пометить выбранное ребро, включить его концевую вершину, не принадлежащую ранее ни одному букету, в тот же букет, которому принадлежит другая концевая вершина данного ребра и пре5йти к 4. Если имеет место случай с), пометить выбранное ребро, сформировать новый букет из концевых вершин данного ребра и перейти к 4. Если имеет место случай d), пометить выбранное ребро, оба букета, содержащие концевые вершины данного ребра, слить в один букет и прейти к 4.
Суть алгоритма Краскала состоит в просмотре ребер исходного графа в порядке не возрастания весов. Причем при этом осуществляется проверка того, не образует ли данное ребро в совокупности с ребрами, помеченными на предыдущих шагах (а именно помеченные ребра включаются в остов), цикл. Если ответ – отрицательный, то ребро метится.
Каким же образом осуществляется такая проверка? Ребра, помеченные в процессе их осмотра, образуют граф, имеющий одну или несколько компонент связности. Вершины, принадлежащие одной компоненте связности, объединяются в совокупность, которая в рамках рассматриваемого алгоритма называется букетом. Ребро образует цикл с ранее помеченными ребрами, если обе его концевые вершины принадлежат одному букету (одной компоненте связности).
Если алгоритм завершает работу в случае вхождения всех вершин графа в один букет, то, поскольку букеты состоят из концевых вершин помеченных ребер, помеченные ребра образуют остов исходного графа. Если алгоритм завершает работу в результате невозможности выбора очередного ребра, то исходный граф является несвязным, т.е. не имеет остова. Действительно, в этом случае по окончании работы алгоритма будут сформированы по крайней мере два различных букета, для которых не найдется ни одного ребра, соединяющего какую-либо вершину одного из них с какой-либо вершиной другого. Так как если бы такое ребро нашлось, то в процессе работы алгоритма оно было бы помечено, а соответствующие букеты слились бы в один. Таким образом, если исходный граф является связным (т.е. имеет остов), то алгоритм Краскала строит остов данного графа.
Покажем, что этот остов является минимальным. Прежде всего, заметим, что любые два остова графа имеют одинаковое число ребер. Предположим, что алгоритм Краскала строит остов связного графа который не является минимальным, т.е. существует остов графа отличный от такой, что
Так как и различны, но имеют одни и те же вершины и одинаковое число ребер, тог существует по крайней мере одно ребро, принадлежащее . Пусть - первое такое ребро из просмотренных алгоритмов Краскала (т.е. до ребра множества исостоят из одинаковых ребер). Поскольку дерево является наибольшим связным графом, не содержащим цикла, то граф полученный из графа S добавлением ребра ) содержит некоторый цикл , причем . Поскольку не содержит циклов, то цикл должен содержать по крайней мере одно ребро, скажем которое не содержится в . (Заметим, что ) Заменим в графе ребро на Полученный граф обозначим через . Покажем, что - остов графа . В самом деле, граф получается из связного графа удалением ребра , входящего в цикл C, поэтому, - связный граф. Кроме того, очевидно, (так как остов графа ), следовательно, граф является деревом. Поскольку, то остов графа G.
Покажем, что . предположим, что . Тогда ребро при построении остова должно быть просмотрено ранее ребра (поскольку ребра графа просматриваются алгоритмом Краскала в порядке не убывания их весов). Так как ребро не было включено в (т.е. не было помечено), то оно должно образовывать цикл с ребрами, просмотренными ранее и включенными в Но, поскольку до ребра (в данном упорядочении) множества и состоят из одних и тех же ребер, то содержит цикл, что противоречит тому, что дерево. Следовательно,
Так как граф отличается от графа S только ребром , то причем число общих ребер у и на одно больше чем у и . многократно повторяя аналогичную замену в графе некоторого его ребра, не входящего в , на ребро, которое входит в, можно преобразовать граф в граф , причем так, что сумма мер на каждом шаге не будет увеличиваться. Следовательно, Противоречие показывает, что алгоритм Краскала стрит минимальный остов связного графа .
Алгоритм Краскала обладает свойством, состоящим в том, что каждое ребро исходного графа просматривается не более одного раза. Однако алгоритм Краскала включает в себя упорядочение ребер исходного графа в порядке убывания их весов и слияние «букетов», поэтому его сложность зависит от сложности выполнения этих процедур. В настоящее время разработаны эффективные методы решения обоих этих задач (см., например, [15]). Мы не будем здесь рассматривать эти методы, отметим только, что сложность упорядочения ребер равна и решения второй задачи также можно добиться за операций (здесь – это число элементов в обоих сливаемых множествах) . Поэтому сложность алгоритма Краскала равна где – число ребер исходного графа.
Алгоритм типа алгоритм Краскала относятся к так называемым жадным алгоритмам. Основным свойством жадных алгоритмов является выбор на каждом шаге самого выгодного варианта без учета последствий, которые могут возникнуть в результате такой стратегии. В разделе 2 мы уже рассматривали подобный алгоритм, при решении задачи о покрытии, однако так мы отмечали, что жадный алгоритм является приближенным. Алгоритм Краскала же, как мы убедились, является точным. Почему жадный алгоритм правильно решает задачу о минимальном остове? Каковы свойства тех задач, которые могут быть решены точно жадным алгоритмом? Насколько широк класс подобных задач? Ниже будет дан ответ на эти вопросы.