Вычисление линейных рекуррентных соотношений

Последовательность называется линейной рекуррентной, если существуют такие коэффициенты , что для любого n справедливо равенство . Для задания линейной рекуррентной последовательности, кроме ее коэффициентов, необходимо знать первые k ее членов, которые называются начальными условиями. Рассмотрим задачу выражения n-го члена последовательности через его номер и начальные условия.

Обозначим через вектор столбец, состоящий из k компонент , через — матрицу размерами вида . По правилу перемножения матриц имеем: . Многократным применением полученной формулы выводим . Задача вычисления n-го члена последовательности свелась, тем самым, к вычислению матрицы .

Характеристический многочлен матрицы А равен . Разделим многочлен на с остатком. Пусть , где - остаток от деления. Подставив вместо λ матрицу А, получим . По теореме Гамильтона-Кэли каждая матрица является корнем своего характеристического уравнения, то есть , где — нулевая матрица. Таким образом, , и задача вычисления свелась к вычислению многочлена r(λ).

Разложим многочлен на линейные множители , где . Для каждого неотрицательного j строго меньшего справедливо равенство , где — j-ая производная характеристического многочлена. Продифференцировав j раз равенство и, подставив в него βi , получим . Этими условиями многочлен r(λ) степени k-1 определяется однозначно. В литературе задача вычисления многочлена по таким условиям носит название «интерполяционный многочлен Лагранжа-Сильвестра».

В качестве примера вычислим n-ый член линейной рекуррентной последовательности , где . Положим . Характеристический многочлен равен . Остаток от деления на удовлетворяет соотношениям и . Единственный многочлен первой степени, удовлетворяющий этим условиям, равен . Таким образом, и .

При получении верхней оценки трудоемкости алгоритма Евклида, потребуется вычислить n-ый член последовательности Фиббоначчи.

Алгоритм Евклида и его варианты

Ниже, для простоты изложения, будем считать, что ищется наибольший общий делитель положительных чисел а и b, причем а≥b. Наибольший делитель чисел а и b обозначим НОД(а,b). Числа а и b записаны в позиционной (сокращенной) системе счисления по основанию р, и длина числа а равна n.

В основе алгоритма Евклида лежит равенство НОД(а,b) = НОД(а-vb,b), справедливое при любом целом v. Выбирая в качестве v частное от деления а на b, получаем алгоритм Евклида.

Описание алгоритма Евклида выглядит следующим образом:

while b<>0 do

Begin

v:=а div b;

а:=а-vb;

с:=а; а:=b; b:=с;

end;

Наибольший общий делитель после работы алгоритма будет находиться в а.

Оценим число итераций алгоритма Евклида. Для этого введем множество , состоящее из пар чисел (а,b), удовлетворяющих условиям: 0<b а и наибольший общий делитель а и b алгоритмом Евклида находится за k итераций. Очевидно, . Индукцией по k покажем существование в множестве такой «наименьшей» пары , что для любой пары (а,b) из выполняются неравенства , . При k=0 и k=1 данное утверждение очевидно, , , , . Пусть утверждение справедливо при k-1. Покажем его справедливость для k. Заметим, что пара принадлежит . Действительно, за одну итерацию алгоритма Евклида мы перейдем к паре из . Пусть пара (а,b) принадлежит и v — частное от деления а на b. За одну итерацию алгоритма Евклида мы перейдем к паре (b,a-vb) из . По предположению индукции выполняется неравенство и . Далее, выводим . Таким образом, пара — «наименьшая» в , утверждение индукции доказано.

Из приведенных рассуждений вытекают рекуррентные формулы и с начальными условиями .

Выразим k–ый член рекуррентной последовательности . Учитывая неравенство , из последней формулы выводим . Таким образом, число итераций алгоритма Евклида для пары чисел a и b (a>b) не превосходит -1=O(n), где n — длина числа а.

Наиболее трудоемкая операция в процессе выполнения итерации алгоритма Евклида — деление чисел а и b. Если длины чисел а и b равны, то трудоемкость деления O(n). Если длина числа b меньше длины числа а, то на следующей итерации длина числа а строго уменьшится. Из этого замечания вытекает, что наихудший случай, когда длины чисел b и а примерно равны на протяжении всего алгоритма Евклида, и тогда общая трудоемкость алгоритма .

Ситуация принципиально не изменится, если в качестве v выбрать ближайшее целое число к дроби а/b. В этом случае линейная рекуррентная последовательность примет вид , при начальных условиях , . Откуда найдем . Число итераций алгоритма Евклида в этом случае не превосходит 1+ =O(n). Далее, как и ранее, выводим общую трудоемкость алгоритма Евклида .

Тем самым доказана

Теорема. Трудоемкость алгоритма Евклида — .

В некоторых приложениях, кроме отыскания наибольшего общего делителя чисел а и b требуется найти целые u и w, удовлетворяющие равенству аu+bw=НОД(а,b). Для нахождения чисел u и w используется расширенный алгоритм Евклида. Любая итерация алгоритма Евклида может быть представлена как произведение вектора (а,b) на матрицу . Матрица имеет целочисленные элементы. Пусть Т — накопленное произведение этих матриц, то есть Т= , где — частное получаемое на i-ой итерации алгоритма Евклида. По построению Т, имеем (а,b)Т = (НОД(а,b),0). Таким образом, в первом столбце матрицы Т расположены искомые числа u и w.

Отметим, что трудоемкость расширенного алгоритма Евклида равна .