Рекурсивная функция и сходимость

[Alik]

Помогите пожалуйста понять как доказывается сходимость рекурсивных функций высокого порядка. Речь идет о реккурентно-зависимой системе линейных уравнений, а сходимость рассматривается как постоянные значения переменных достигаемые на бесконечности. Переменные: $x_1,...,x_5, в то время как $a_1,...,a_4 просто коэффициенты

\[ \begin{gathered} \left[ {\begin{array}{*{20}c} 1 & 0 & 0 & 0 & {a_1 } \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & {a_3 } \\ 0 & 0 & 0 & 1 & {a_4 } \\ 1 & 0 & 1 & 1 & 0 \\ \end{array} } \right] \times \left[ {\begin{array}{*{20}c} {x_1^{i + 1} } \\ {x_2^{i + 1} } \\ {x_3^{i + 1} } \\ {x_4^{i + 1} } \\ {x_5^{i + 1} } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {x_1^i } \\ {x_2^i } \\ {x_3^i } \\ {x_4^i } \\ 1 \\ \end{array} } \right] \\ \left[ {\begin{array}{*{20}c} 1 & 0 & 0 & 0 & { - a_1 } \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & {a_3 } \\ 0 & 0 & 0 & 1 & {a_4 } \\ 1 & 0 & { - 1} & { - 1} & 0 \\ \end{array} } \right] \times \left[ {\begin{array}{*{20}c} {x_1^{i + 2} } \\ {x_2^{i + 2} } \\ {x_3^{i + 2} } \\ {x_4^{i + 2} } \\ {x_5^{i + 2} } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {x_1^{i + 1} } \\ {x_2^{i + 1} } \\ {x_3^{i + 1} } \\ {x_4^{i + 1} } \\ 0 \\ \end{array} } \right] \\ \left[ {\begin{array}{*{20}c} 1 & 0 & 0 & 0 & {a_1 } \\ 0 & 1 & 0 & 0 & {a_2 } \\ 0 & 0 & 1 & 0 & { - a_3 } \\ 0 & 0 & 0 & 1 & {a_4 } \\ 1 & 1 & { - 1} & 1 & 0 \\ \end{array} } \right] \times \left[ {\begin{array}{*{20}c} {x_1^{i + 3} } \\ {x_2^{i + 3} } \\ {x_3^{i + 3} } \\ {x_4^{i + 3} } \\ {x_5^{i + 3} } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {x_1^{i + 2} } \\ {x_2^{i + 2} } \\ {x_3^{i + 2} } \\ {x_4^{i + 2} } \\ 1 \\ \end{array} } \right] \\ \left[ {\begin{array}{*{20}c} 1 & 0 & 0 & 0 & { - a_1 } \\ 0 & 1 & 0 & 0 & {a_2 } \\ 0 & 0 & 1 & 0 & { - a_3 } \\ 0 & 0 & 0 & 1 & {a_4 } \\ 1 & { - 1} & 1 & { - 1} & 0 \\ \end{array} } \right] \times \left[ {\begin{array}{*{20}c} {x_1^{i + 4} } \\ {x_2^{i + 4} } \\ {x_3^{i + 4} } \\ {x_4^{i + 4} } \\ {x_5^{i + 4} } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {x_1^{i + 3} } \\ {x_2^{i + 3} } \\ {x_3^{i + 3} } \\ {x_4^{i + 3} } \\ 0 \\ \end{array} } \right] \\ \left[ {\begin{array}{*{20}c} 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & { - a_2 } \\ 0 & 0 & 1 & 0 & { - a_3 } \\ 0 & 0 & 0 & 1 & {a_4 } \\ 0 & 1 & 1 & { - 1} & 0 \\ \end{array} } \right] \times \left[ {\begin{array}{*{20}c} {x_1^{i + 5} } \\ {x_2^{i + 5} } \\ {x_3^{i + 5} } \\ {x_4^{i + 5} } \\ {x_5^{i + 5} } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {x_1^{i + 4} } \\ {x_2^{i + 4} } \\ {x_3^{i + 4} } \\ {x_4^{i + 4} } \\ 0 \\ \end{array} } \right] \\ {\text{and so forth with period = 5}} \\ \left[ {\begin{array}{*{20}c} 1 & 0 & 0 & 0 & {a_1 } \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & {a_3 } \\ 0 & 0 & 0 & 1 & {a_4 } \\ 1 & 0 & 1 & 1 & 0 \\ \end{array} } \right] \times \left[ {\begin{array}{*{20}c} {x_1^{i + 6} } \\ {x_2^{i + 6} } \\ {x_3^{i + 6} } \\ {x_4^{i + 6} } \\ {x_5^{i + 6} } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {x_1^{i + 5} } \\ {x_2^{i + 5} } \\ {x_3^{i + 5} } \\ {x_4^{i + 5} } \\ 1 \\ \end{array} } \right] \\ \end{gathered} \]

[maxal]

Во-первых, первое и второе соотношения противоречат друг другу, если во втором сделать замену $i'=i+1$. Это бы имело смысл, если бы, например, было сказано, что $i=5m$ (т.е. кратно 5) - так ли это?

Во-вторых, можно перемножить все этим матрицы и получить "однородную" зависимость вида $M\cdot x^{i+5} = x^i$, которую гораздо проще исследовать. А исследрование надо начинать с приведения $M$ к жордановой форме - с ее помощью можно получить явное выражение для компонентов любого $x^{i+5k},$ $k=1,2,3,\dots$.

[Alik]

Не очень понимаю в чем состоит противоречие, если матрицы коэффициентов для каждого случая разные по определению. К жордановой форме нужно приводить каждую матрицу или уже их произведение? Почему будет работать трюк с "использованием" только первого и последнего членов рекурсии?
Написанная для этого случая в MATLAB программа показывает, что факт сходимости не зависит от выбора коэффициентов $a_1,...,a_4, при этом $x_5 стремится к нулю.

[maxal]

Alik писал(а):

Не очень понимаю в чем состоит противоречие, если матрицы коэффициентов для каждого случая разные по определению.

Непонятно, чем здесь случаи различаются. Например, сдвигом индексов случай 3 можно привести к случаю 1 (и там и там единица в нижней компоненте правой части), но матрицы при этом у них разные...

Alik писал(а):

К жордановой форме нужно приводить каждую матрицу или уже их произведение?

Можно, конечно, каждую матрицу приводить к жордановой форме, но "возни" тогда будет больше. Проще свернуть все эти случаи в единое рекуррентное соотношение и исследовать уже только его.

Alik писал(а):

Почему будет работать трюк с "использованием" только первого и последнего членов рекурсии?

Компоненты "последнего" члена являются обычными функциями от первого члена и индекса (ну и элементов матрицы), а как искать предел функций - хорошо известно.

[Alik]

Для начала попробую сделать reduced row echelon form (rref) всех матриц, только вот не знаю как задать в MATLAB коэффициенты $a_1, ..., a_4 в символьном виде

[TOTAL]

Почти все системы вырожденные, как решаете?

[Alik]

А вырожденность систем не связана с вычислением рекурсии -
задаем начальные значения переменных $x_1,...,x_5 ноль, коэффициенты $a_1,...,a_4 скажем $10^6.
Через несколько сот итераций:

\[ \left[ \begin{gathered} x_1 \hfill \\ x_2 \hfill \\ x_3 \hfill \\ x_4 \hfill \\ x_5 \hfill \\ \end{gathered} \right] = \left[ \begin{gathered} {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2} \hfill \\ {1 \mathord{\left/ {\vphantom {1 4}} \right. \kern-\nulldelimiterspace} 4} \hfill \\ {1 \mathord{\left/ {\vphantom {1 8}} \right. \kern-\nulldelimiterspace} 8} \hfill \\ {3 \mathord{\left/ {\vphantom {3 8}} \right. \kern-\nulldelimiterspace} 8} \hfill \\ {}_{}0 \hfill \\ \end{gathered} \right] \]

Думать, что $x_5 как был нулем, так и остался - ошибочно, он достигает максимального значения на первой итерации, а потом уменьшается. Снова подчеркну, что сходимость переменных к указанным величинам не зависит от выбора коэффициентов $a_1,...,a_4, от них зависит только темп сходимости.

[TOTAL]

Alik писал(а):

А вырожденность систем не связана с вычислением рекурсии

Как решаете вырожденные системы? Что принимаете за решение?

[Alik]

Системы вида $A_{i+1}{X_{i+1}=X_i решаю в лоб $X_{i+1}={A_{i+1}^{-1}}X_i , запускаеся цикл, критерий - приемлимое время расчетов (минут 5-10). По завершению строятся графики и наблюдаются указанные результаты.

[TOTAL]

Alik писал(а):

Системы вида $A_{i+1}{X_{i+1}=X_i решаю в лоб $X_{i+1}={A_{i+1}^{-1}}X_i

A_{i+1}^{-1} не существует.

[Alik]

Цитата:

A_{i+1}^{-1} не существует.

ОК, тогда придется пожаловаться на изобретателей LaTEX и сказать, что символ "\" в нем не отображается, а то что я делаю это для системы AX=B пишу в MATLAB X=A\B, чему же это эквивалентно по вашему мнению? Второй вариант проверенный мною - это X=(A^(-1))*B

[TOTAL]

Alik писал(а):

Цитата:

A_{i+1}^{-1} не существует.

ОК, тогда придется пожаловаться на изобретателей LaTEX и сказать, что символ "" в нем не отображается, а то что я делаю это для системы AX=B пишу в MATLAB X=A\B, чему же она эквивалентна по вашему мнению? Второй вариант проверенный мною - это X=(A^(-1))*B

Добавлено спустя 51 секунду:

Alik писал(а):

Цитата:

A_{i+1}^{-1} не существует.

ОК, тогда придется пожаловаться на изобретателей LaTEX и сказать, что символ "" в нем не отображается, а то что я делаю это для системы AX=B пишу в MATLAB X=A\B, чему же это эквивалентно по вашему мнению? Второй вариант проверенный мною - это X=(A^(-1))*B

Вы в курсе, что определитель матрицы с нулевой строкой равен нулю и что обратная к такой матрице не существует?

[ewert]

Alik писал(а):

ОК, тогда придется пожаловаться на изобретателей LaTEX и сказать, что символ "" в нем не отображается, а то что я делаю это для системы AX=B пишу в MATLAB X=A\B, чему же это эквивалентно по вашему мнению?

"" в LaТеХе традиционно пишется как "\backslash", а вот если Вы подсунете Матлабу ту конструкцию с вырожденной матрицей -- обидится Матлаб, ей-богу, обидится.

[Alik]

Вы правы, решабельность системы в таком виде не проверял, поскольку функция организована так, что нулевые строки просто удаляются, а все остальное по поводу $X=A\backslash{B} правда. Вообще эти матрицы могут быть и вырожденными и прямоугольными, существуют ли обратные матрицы в этом случае?

[Бодигрим]

Цитата:

поскольку функция организована так, что нулевые строки просто удаляются

Произведение вырожденных матриц не может быть невырожденной матрицей. Наличие нулевых строк является достаточным, но не необходимым условием вырожденности.

Цитата:

Вообще эти матрицы могут быть и вырожденными и прямоугольными, существуют ли обратные матрицы в этом случае?

Нет, в стандартном смысле ($AA^{-1}=E=A^{-1}A$) для для них обратной матрицы не существует. Но можно определенным образом ввести понятие псевдообратной матрицы. См. Гантмахер Ф.Р. — Теория матриц.