Указатель — Разделы — Обозначения — Автор — О проекте
Вспомогательная результат к разделу ☞ РАЗНОСТНОЕ УРАВНЕНИЕ И РЕКУРРЕНТНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ.
Страница — в разработке. Начало работ — 20.04.2016, окончание — ??.??.????.
Известны первые члены линейной рекуррентной последовательности:
Чему равен следующий?
Теорема. Пусть имеется последовательность . Если эта последовательность является решением линейного однородного разностного уравнения порядка
, то все главные миноры
бесконечной ганкелевой матрицы
начиная с порядка будут равны
.
В этом случае разностное уравнение должно иметь вид
При дополнительных условиях
это уравнение будет уравнением в точности -го порядка.
Доказательство. Если элементы последовательности удовлетворяют некоторому уравнению вида
при хотя бы одном коэффициенте из отличном от нуля, то справедливы равенства
Эти равенства составляют систему линейных однородных уравнений относительно коэффициентов. По предположению, система совместна и имеет нетривиальное решение. Но тогда (см. ☞ ЗДЕСЬ) ее определитель
должен быть равен нулю. Этот определитель совпадает с из условия теоремы. Равенство нулю
доказывается аналогично:
если последовательность удовлетворяет уравнению
то она удовлетворяет и уравнению
Далее, при равенстве нулю определителя матрицы системы уравнений
ее фундаментальная система решений будет состоять из единственного набора значений если . Этот набор решений может быть построен с помощью алгебраических дополнений к элементам последней строки матрицы:
Но это и означает, что разностное уравнение имеет то представление в виде определителя, что указано в теореме. ♦
Пример 1. Известны первые члены линейной рекуррентной последовательности:
Чему равен следующий?
Решение. Имеем:
Вычисляем главные миноры:
Больше главных миноров вычислить невозможно поскольку последовательность обрывается. Выдвинем в качестве рабочей гипотезы, что наша последовательность «разворачивается в бесконечность» как линейная рекуррентная последовательность порядка . Тогда, в соответствии с теоремой эта последовательность является решением разностного уравнения
Раскладываем определитель по последней строке:
По имеющейся у нас информации нельзя гарантировать абсолютную истинность полученного ответа: любую последовательность можно так «испортить» в одном-единственном элементе, чтобы после обращения в нуль любого подряд идущего набора главных миноров матрицы , очередной главный минор стал бы отличным от нуля. Так что ответ в задаче приходится формулировать так:
Ответ. Если автор задачи не задумал особенную подлость, то очередной элемент последовательности равен .
Справедлив и более общий результат, который основан на понятии ранга бесконечной матрицы. По аналогии с конечными матрицами, будем считать ранг бесконечной матрицы равным если все ее миноры порядка
равны нулю, и существует хотя бы один минор порядка
отличный от нуля.
Теорема. Бесконечная ганкелева матрица
имеет конечный ранг тогда и только тогда, когда существуют числа
такие, что
т.е. последовательность является линейной рекуррентной последовательностью порядка
.
Пример 2. Найти линейное разностное уравнение задающее последовательность
Решение. В отсутствие гипотезы о порядке линейного разностного уравнения, имеет смысл организовать процедуру вычисления кандидата последовательно, начиная с минимально возможного. Так, в рассмотренном примере мы могли бы выдвинуть сначала гипотезу о том, что этот порядок равен :
Это уравнение правильно определяет элемент последовательности по значению
. Но величина
определяется с ошибкой. Рассмотрим следующий по порядку определитель:
Элементы последовательности определяются из этого уравнения (и из данных значений
) правильно, но
определяется неверно.
Снова два значения и
определятся правильно, а
— нет.
Теперь и
находятся верно, но
— нет:
.
Этот вариант дает верные значения элементов последовательности для всех доступных значений .
Имеется ли закономерность в формировании последовательноcти этих уравнений?
Для ответа на этот вопрос выпишем их характеристические полиномы:
Теперь разделим каждый полином, начиная c , на предыдущий (с остатком):
Итак, с точностью до числового сомножителя, остаток от деления на
совпадает с
. Наблюдение имеет под собой теоретическое обоснование.
Для произвольной числовой последовательности определитель
является полиномом по ; он называется ганкелевым полиномом k-го порядка, порожденным последовательностью
.
Его каноническое представление имеет коэффициентами числовые определители
-го порядка:
Коэффициенты будем обозначать ; таким образом
Коэффициент может обращаться в нуль, так что степень ганкелевого полинома
-го порядка может оказаться меньше
.
Теорема [?]. Полиномы
удовлетворяют следующему тождеству:
Если то тождество может быть переписано в более симметричном виде:
Пусть мы хотим использовать это тождество для вычисления коэффициентов полинома на основании уже вычисленных коэффициентов полиномов
и
. Величины констант
и
, используемых в тождестве, нам известны — это коэффициенты полинома
. Но оставшиеся константы, именно
и
, нам пока неизвестны, поскольку они являются коэффициентами полинома
, который мы хотим найти. Как разорвать порочный круг? — Посмотрим на детерминантные представления этих коэффициентов:
Это — определители -го порядка, отличающиеся только в последних столбцах. Первые же
столбцов совпадают с первыми столбцами транспонированного определителя
:
Но выражение для , т.е. разложение определителя по последнему столбцу, считается нам известным:
Тогда оба определителя и
могут быть вычислены по формулам
и, тем самым, мы «замыкаем» рекурсивную формулу вычисления ганкелевого полинома -го порядка.
Формула из теоремы применима для рекурсивного вычисления . Однако она не работает в случае
. Именно эта ситуация встречается в примере 1 предыдущего пункта.
Теорема [?]. Пусть . Если
, то
и
В противном случае
и
[?]. Иохвидов И.С. Ганкелевы и теплицевы матрицы и формы. М. Наука. 1974.
[?]. Uteshev A.Yu., Baravy I. Solution of Interpolation Problems via the Hankel Polynomial Construction. 2016. arXiv:1603.08752