Как понизить ранг (глубину) рекуррентного соотношения?

[svv]

Бывают случаи, когда данным методом понизить порядок «не совсем получается». Возьмём соотношение $a_{n+2}+a_n=0$. В операторной форме $(S^2+1)(a_n)=0$, причём разложить оператор на множители можно лишь с использованием комплексных чисел:
$(S+i)(S-i)(a_n)=0$
Общее решение $a_n=A(-i)^n+Bi^n$
При вычёркивании операторного множителя $(S-i)$ наш метод даёт
$a_{n}+ia_{n-1}=2Bi^{n}$
Пусть коэффициент $B$ известен. Подставляя его, формально получаем соотношение первого порядка. И если последовательность $(a_n)$ может быть комплексной (почему нет?), тогда нет проблем.

Если же $(a_n)$ обязана быть вещественной, то, разделяя вещественную и мнимую часть, найдём
$a_n+ia_{n-1}=2(\operatorname{Re}B\cos\frac{\pi n}{2}-\operatorname{Im}B\sin\frac{\pi n}{2})+2i(\operatorname{Im}B\cos\frac{\pi n}{2}+\operatorname{Re}B\sin\frac{\pi n}{2})$
Вещественная часть и мнимая часть равны нулю по отдельности, и наше рекуррентное соотношение распадается на два эквивалентных выражения для общего члена:
$\begin{array}{rll}a_n&=&2(\operatorname{Re}B\cos\frac{\pi n}{2}-\operatorname{Im}B\sin\frac{\pi n}{2})\\ a_{n-1}&=&2(\operatorname{Re}B\sin\frac{\pi n}{2}+\operatorname{Im}B\cos\frac{\pi n}{2})\end{array}$
т.е. вместо понижения порядка нечаянно получили решение.

Дело в том, что при требовании вещественности $(a_n)$ произвольные коэффициенты $A$ и $B$ в общем решении не совсем произвольны связаны: $A=\overline{B}$, поэтому, зная один, знаем и другой, что определяет последовательность однозначно.

[maximkarimov]

Уважаемый svv, не могли бы Вы привести в качестве примера рекуррентное соотношение глубины 1 для чисел Фибоначчи? Для полной и окончательной ясности в моей (а может и не только!) голове.
Заранее благодарю.

[mihaild]

А на вид свободного члена есть ограничение? Если нет, то ситуация лучше не стала. Берем произвольную последовательность $a_n$, произвольный вектор коэффициентов $x_1, \ldots, x_k$ и получаем рекуррентное соотношение глубины $k$: $a_n = x_1 a_{n - 1} + \ldots + x_k a_{n - k} + c_n$ (где естественно $c_n = a_n - x_1 a_{n - 1} - \ldots - x_k a_{n - k}$).

[Dmitriy40]

maximkarimov в сообщении #1481553 писал(а):

Уважаемый svv, не могли бы Вы привести в качестве примера рекуррентное соотношение глубины 1 для чисел Фибоначчи? Для полной и окончательной ясности в моей (а может и не только!) голове.

Да легко: как известно отношение соседних чисел Фибоначчи стремится к золотому сечению, так что желаемое соотношение будет просто геометрической прогрессией с коэффициентом $\sqrt{5}/2+0.5$ и округлением до ближайшего целого числа. Будут проблемы с "запуском", переходом от 0 к 1, потом ещё раз к 1 и лишь потом к 2, но можно априори заявить что начало $\{0, 1, 1\}$ и лишь потом действует рекуррентное соотношение.

[kotenok gav]

Попробую применить теорию svv и получить ответ.
$F_{n+2}-F_{n+1}-F_n=0$
$(S^2-S-1)F_n=0$
$(S-\varphi)(S-\varphi+1)F_n=0$
Общее решение - $F_n=\frac{\varphi^n-(1-\varphi)^n}{2\varphi-1}$. Применяем оператор $S-\varphi$:
$(S-\varphi)F_n=\frac{(\varphi-S)(1-\varphi)^n}{2\varphi-1}=\frac{(\varphi-(1-\varphi))(1-\varphi)^n}{2\varphi-1}=(1-\varphi)^n$.
Получаем соотношение $F_{n+1}=\varphi F_n+(1-\varphi)^n$.

[nnosipov]

Да уж, проблема ... Пишем от балды какие-нибудь коэффициенты при $F_{n+1}$ и $F_n$, затем вычисляем эту линейную комбинацию и выдаем за правую часть.

Без разумных ограничений на вид рекуррентного соотношения задача смысла не имеет.

[svv]

kotenok gav, спасибо, всё точно.

[maximkarimov]

Cпасибо огромное всем участникам, в особенности svv, kotenok gav и mihaild!

[maxal]

maximkarimov в сообщении #1481086 писал(а):

Там описывается получение явной формулы методом производящих функций. Его применение к рекуррентному соотношению A глубиной 4, которое я привел выше в качестве примера, и к рекуррентному соотношению B глубиной 2, которое я не привел, дает одну и ту же формулу.

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

Самое подробное изложение этих вопросов на русском я видел в учебнике:
Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра, Том 2, 2003.
Глава XXV. Линейные рекуррентные последовательности.

Процитирую её оглавление:

Цитата:

Глава XXV. Линейные рекуррентные последовательности 292
§ 1. Основные определения. Семейство ЛРП с данным характеристическим многочленом и его базисы 293
§ 2. Умножение последовательности на многочлен. Генератор ЛРП 297
§ 3. Минимальный многочлен и аннулятор ЛРП 301
§ 4. Соотношения между семействами ЛРП с различными характеристическими многочленами 305
§ 5. Биномиальный базис пространства ЛРП над полем 307
§ б. Представление ЛРП над конечным полем с помощью функции "след" 312
§ 7. Периодические последовательности 319
§ 8. Периодические многочлены. Периодичность ЛРП над конечным кольцом 323
§ 9. Вычисление периода и длины подхода ЛРП над конечным полем 327
§ 10. ЛРП максимального периода над конечным полем 330
§ 11. Цикловой тип семейства ЛРП с реверсивным характеристическим многочленом над конечным кольцом 333
§ 12. ЛРП над кольцами вычетов 340
§ 13. Распределение элементов на циклах линейных рекуррент 352

[maximkarimov]

maxal в сообщении #1483573 писал(а):

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

Поскольку ранее было показано, что можно получить рекуррентную формулу любого порядка, который будет меньше порядка исходного ЛОРУ, не могли бы Вы пояснить что подразумевается под рекуррентной формулой "минимального" порядка? А еще лучше - показать получение минимального многочлена и рекуррентную формулу соответствующего порядка для ЛОРУ, которое было указано в качестве примера (первое сообщение темы). Спасибо.

[maxal]

maximkarimov в сообщении #1483881 писал(а):

Поскольку ранее было показано, что можно получить рекуррентную формулу любого порядка, который будет меньше порядка исходного ЛОРУ, не могли бы Вы пояснить что подразумевается под рекуррентной формулой "минимального" порядка?

Можно, но такая формула не будет линейной, вообще говоря. Так можно вообще от рекуррентности избавиться и получить явную формулу $n$-го члена как функцию от $n$, как, например, формула Бине для чисел Фибоначчи.
Моё же утверждение относится к линейным рекуррентным формулам (с не зависящими от $n$ коэффициентами).

maximkarimov в сообщении #1483881 писал(а):

А еще лучше - показать получение минимального многочлена и рекуррентную формулу соответствующего порядка для ЛОРУ, которое было указано в качестве примера (первое сообщение темы).

Ничего не получится, пока вы строго не определите последовательность $a_n$ -- одной лишь рекуррентной формулы не достаточно, нужны ещё значения начальных членов.

[maximkarimov]

Например, пусть будет $a=[1, 2, 6, 23]$.

[maxal]

maximkarimov в сообщении #1483927 писал(а):

Например, пусть будет $a=[1, 2, 6, 23]$.

С такими начальными значениями порядок ЛРП понизить нельзя. Для содержательного примера буду считать, что начальные значения [1, 2, 6, 22].

Итак, из

maximkarimov в сообщении #1481017 писал(а):

$a(n)=8a(n-1) - 21a(n-2) +22a(n-3) -8a(n-4)$

мы получаем характеристический многочлен

$$f(x) = \sum_{k=0}^4 c_i x^i = 8 - 22x + 21x^2 - 8x^3 + x^4.$$

На самом деле, для наших целей даже производящая функция не нужна, а нужен лишь генератор:

$$g(x) = \sum_{k=0}^3 x^{3-k} \sum_{i=0}^k a_{k-i} c_{4-i} = x^3 - 6x^2 + 11x - 6.$$

Минимальный многочлен вычисляется по формуле:

$$\frac{f(x)}{\gcd(f(x),g(x))} = x^2 - 5x + 4,$$

что даёт линейное рекуррентное соотношение минимального порядка для той же последовательности:

$$a(n) = 5a(n-1) - 4a(n-2).$$

P.S. А если же нужна производящая функция, то она получается как

$$\frac{g(x^{-1})}{xf(x^{-1})} = \frac{1-3x}{1-5x+4x^2}.$$

[maximkarimov]

1. Я правильно понимаю, что подразумевается возможность получения только линейного и однородного рекуррентного соотношения минимального порядка?
2. Как формулируются условия на начальные члены ЛОРУ, которые необходимы для понижения его порядка?

[maxal]

maximkarimov в сообщении #1483940 писал(а):

1. Я правильно понимаю, что подразумевается возможность получения только линейного и однородного рекуррентного соотношения минимального порядка?
2. Как формулируются условия на начальные члены ЛОРУ, которые необходимы для понижения его порядка?

1 - да.
2 - генератор и характеристический многочлен не должны быть взаимно просты.