Рекуррентное соотношение

[worm2]

Объясняю как маленькому школьнику на примере решения такой задачи:

Найти решение уравнения
x+y=1
при условии, что
y=2

Я понимаю, что у Вас никаких проблем с её решением не возникает. Но давайте опробуем на ней наш новый метод, а потом применим его к более сложной задаче.
Решаем так:
1) Находим общее решение уравнения
x+y=0
Это все пары (t, -t), где t - любое.
2) Находим одно, любое, частное решение уравнения
x+y=1
Ну... как же найти одно решение? Попробуем подобрать...
x=0, y=0. Не подходит. x=1, y=1. Не подходит. x=1, y=0. Ура! Получилось!
3) Общее решение уравнения
x+y=1 получается как сумма решений, полученных в п.1 и 2:
(t+1,-t), где t --- любое.
Как же так?! --- воскликнете Вы --- ведь если бы мы выбрали другое частное решение, например, x=0, y=1, у нас бы получилось другое общее решение: (t,1-t)! Не может же одна задача иметь 2 разных решения?
Конечно, не может! Дело в том, что пары (t+1,-t) и (t,1-t) задают одно и то же решение, просто записанное по-разному. Вы можете легко в этом убедиться, изобразив оба решения геометрически. Так что общее решение, оказывается, не зависит от того, какое конкретное частное мы берём. Не с пониманием ли этого факта у Вас трудности?
4) Теперь нам нужно получить решение уравнения, которое удовлетворяет условию y=2. Подставляем:
-t=2
t=-2.
x=t+1=-1.
y=-t=2.
В итоге получаем ответ:
(-1,2)

=====

В Вашей задаче сложности вызывает п. 2), не так ли?
V.V. и Henrylee подсказывают Вам, в каком виде нужно искать решение. У них большой опыт в решении подобных задач и они просто знают, что эта подсказка приведёт к успеху!
Но если Вам не очень понятно, давайте пойдём другим путём.
Давайте рассмотрим уравнение, которое Вы получили:

$3T_{n+2}-4T_{n+1}+T_n = -2$

Как найти какое-нибудь одно его решение?
Попробуем поискать его в виде $T_k = a$, т.е. константа (не зависящая от k). Подставляем... не получилось При любом a получается 0=2.
Ну давайте тогда поищем ответ в виде $T_k = ak+b$, где a и b --- какие-нибудь константы. Пробуйте!

[Sakura]

worm2, простите, я еще больше запуталась, где-то вы свой маленький пример не очень подробно описали.
Вот отсюда я перестала понимать:

3) Общее решение уравнения
x+y=1 получается как сумма решений, полученных в п.1 и 2:
(t+1,-t)

Почему? Откуда? Как? Ведь Вы привели абсолютно не относящиеся друг к другу уравнения в п.п. 1 и 2. А раз они независят друг от друга, то почему в п.2 Вы взяли именно это уравнение, а не x+y=5, например? Почему мы тогда должны скадывать решения совершенно не относящихся друг к другу уравнений?

GAA, давайте альфу заменим на g, потому что я не знаю как здесь писать буквы греческого алфавита и не смогу писать те же симвлы, что и Вы.
Вопрос: откуда получилось, что gn3^n - это решение? Как к этому пришли?

[GAA]

Sakura писал(а):

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

см. тему Первые шаги в наборе формул.

Sakura писал(а):

Вопрос: откуда получилось, что gn3^n - это решение? Как к этому пришли?

Давайте продолжим решение (на Ваш вопрос быстро не ответить).
Подставив решение с неопределенным коэффициентом в полное уравнение и, разделив обе его части на $3^n$, получим
$\alpha (n+2)3^2 - 4\alpha (n+1) 3 + 3 \alpha n = -6$. Группируем слагаемые по степеням $n$. Если вид частного решения выбран правильный, то коэффициент при $n^1$ будет равен нулю, и это у нас получается. Приравнивая коэффициенты при $n^0$ в левой и правой части находим уравнение для $\alpha$.

[worm2]

Sakura писал(а):

Почему? Откуда? Как? Ведь Вы привели абсолютно не относящиеся друг к другу уравнения в п.п. 1 и 2. А раз они независят друг от друга, то почему в п.2 Вы взяли именно это уравнение, а не x+y=5, например? Почему мы тогда должны скадывать решения совершенно не относящихся друг к другу уравнений?

Это следует из того, что уравнение линейное.

Уравнение f(x)=y, где x, y - произвольные числовые объекты (векторы, например), называется линейным, если линейна функция f, т.е.
f(a*x+b*y) = a*f(x) + b*f(y) для любых числовых объектов x, y и любых чисел a, b.

Пусть X --- множество всех решений линейного уравнения f(x)=y, т.е.
$x \in X \Leftrightarrow f(x) = y$
Пусть U --- множество всех решений линейного однородного уравнения f(x)=0, т.е.
$u \in U \Leftrightarrow f(u) = 0$
Пусть теперь z - любое решение неоднородного уравнения f(x) = y, т.е. f(z) = y, или, что то же самое, $z \in X$.
Покажем, что любое решение $x \in X$ можно получить складывая z с каким-то элементом U, т.е. множество $T=\{t: t-z \in U\}$ совпадает с множеством всех решений X.
1) Пусть $t \in T$. Тогда $t-z=u\in U$, т.е. f(t-z)=0. Но f линейна. Поэтому f(t-z) = f(t)-f(z)=f(t)-y = 0, откуда f(t)=y, т.е. $t \in X$.
2) Пусть $x \in X$. Тогда f(x-z)=f(x)-f(z)=y-y=0, откуда $x-z \in U$, а значит, по определению T, $x \in T$.

Осталось проверить, что наша функция f, которая в нашем случае зависит от 3-мерного вектора $(W_n, W_{n+1}, W_{n+2})$, а результатом которой является действительное число, является линейной. Оставляю это Вам в качестве упражнения.

Добавлено спустя 3 минуты 10 секунд:

Что-то я в этом посте слишком по-вузовски всё написал, точно не для младших школьников.
Но если Вы хотите досконально разобраться в этой теме, или если Вы собираетесь учиться в Вузе, то разбор этого рассуждения лишним не будет.

[Sakura]

GAA, а где Вы взяли неопределенный коэффициент?

Давайте вернемся на шаг назад, потому что я ничего дальше не поняла.

Вот мы написали общее решение a_n = C_13^n+C_21^n для однородного уравнения.

Далее мы ищем частное решение неоднородного уравнения b_n_+_2-4b_n_+_1+3b_n = -2 * 3^n^+^1. Так? А как его искать?

Добавлено спустя 7 минут 27 секунд:

worm2, дело в том, что на самостоятельный разбор дано решить рекуррентное соотношение, но я не могу найти материал, который подробно, а самое главное понятно бы объяснял что к чему. Везде все галопом по Европам без объяснений, а у меня на каждое действие из этого возникает сто тысяч почему. Естесвенно, Ваше объяснение
вызвало еще больше путаницы и давайте тоже с Вами вернемся на шаг назад. Почему Вы вторым шагом взяли х+у=1, а не х+у=5? можно ли брать х+у=5 (или 3 или 10 или 100000), если нельзя, то почему?

[GAA]

Sakura писал(а):

GAA, а где Вы взяли неопределенный коэффициент? Давайте вернемся на шаг назад, потому что я ничего дальше не поняла.

В данном случае мы имеем уравнение со специальной правой частью $B d^n$, где $B$ некоторая константа. Для этого случая, если мне не изменяет память, правило таково: частное решение ищется в виде $\alpha n^m d^n$, где $m$ — равно кратности совпадения корня характеристического уравнения с $d$.

[Sakura]

GAA, а d^n и \alpha тогда что такое? И если Вас не затруднит, то "кратность совпадения корня характеристического уравнения с d" - что это? Более просто это можно объяснить?

[GAA]

Sakura писал(а):

d^n тогда что такое?

В Вашем примере $B=-6$, а $d^n$ — это $3^n$.

Sakura писал(а):

"кратность совпадения корня характеристического уравнения с d" - что это? Более просто это можно объяснить?

Это — недопустимое студенческое выражение (но краткое и образное). Давайте я поясню на Вашем примере. Если бы у Вас не было бы корня характеристического уравнения $k^2 - 4k + 3 = 0$ равного $d$, то $m$ равнялось бы 0. Но у Вас один из корней этого уравнения равен 3, вот Вы и должны взять $m$ равным 1.

[worm2]

Sakura писал(а):

Почему Вы вторым шагом взяли х+у=1, а не х+у=5? можно ли брать х+у=5 (или 3 или 10 или 100000), если нельзя, то почему?

Потому что исходное уравнение, которое нам нужно решить:
x+y=1 (а не 3, 5 и т.п.)
Мы пытаемся на втором шаге метода найти ОДНО его ЧАСТНОЕ решение. Почему из него одного плюс ОБЩЕЕ решение ОДНОРОДНОГО уравнения вдруг у нас получится ОБЩЕЕ РЕШЕНИЕ нашего уравнения (которое требуется решить в задаче)?
Давайте докажем.
Пусть (f(t),g(t)) --- общее решение неоднородного уравнения x+y=1, т.е.:
1) Для любого t:
f(t)+g(t) = 1
2) Для любых x и y, являющихся решением уравнения x+y=1, существует такое t, что f(t)=x, g(t)=y.

Пусть (F(t),G(t)) ---общее решение однородного уравнения x+y=0.

Покажем, что (F(t)+1, G(t)) совпадает с общим решением (f(t), g(t)) неоднородного уравнения.

Доказательство.
1) Нам надо показать, что для любого t
F(t)+1+G(t)=1
Это очевидно, т.к. по определению F(t)+G(t)=0.
2) Нам надо доказать, что для любых x и y, являющихся решением уравнения x+y=1, существует такое t, что F(t)+1=x, G(t)=y.
Поскольку x+y=1, то (x-1)+y=0, т.е. получили однородное уравнение на (x-1) и y. Поскольку (F(t), G(t)) --- его общее решение, то найдётся такое t, что F(t)=x-1 [а значит, F(t)+1=x], G(t)=y.
Доказательство завершено.

[Sakura]

GAA, т.е. мы m берем равным второму корню? Или если у нас один из корней получился равным d, то m мы в любом случае берем равным 1, даже если бы корни были 3 и 2? Или если бы корни были 3 и 2, то m мы бы взяли равное 2?

Добавлено спустя 11 минут 9 секунд:

worm2, правильно ли я понимаю, что имея неоднородное уравнение (которое надо решить), находим частное решение неоднородного уравнения, затем находим общее решение однородного уравнения, затем складываем результаты и получаем общее решение неоднородного уравнения?

[worm2]

Именно так!

Сей трюк возможен благодаря тому, что уравнение линейное.
С уравнением вроде $x^2+y^2=5$ этот финт ушами не прошёл бы!

[GAA]

Sakura писал(а):

m берем равным второму корню?

Нет.

Sakura писал(а):

Или если у нас один из корней получился равным d, то m мы в любом случае берем равным 1, даже если бы корни были 3 и 2?

Да.

Sakura писал(а):

Или если бы корни были 3 и 2, то m мы бы взяли равное 2?

Нет.

1. Школьникам о рекуррентных соотношениях с постоянными коэффициентами можно посмотреть в книге
Маркушевич А.И. Возвратные последовательности. Студенты смотрят в §7 «Уравнения в конечных разностях», гл.II «Интерполяция и численное интегрирование» книги Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. — М.: Наука, 1987.
2. По иному (с ударением на производящие функции) излагают Феллер (в Введение в теорию вероятностей и ее приложения. Т.1) и Кнут в Грин Д., Кнут Д. Математические методы анализа алгоритмов, 1987 и Грэхем Р., Кнут Д., Паташник О. Конкретная математика.
Отредактированы (уточнены) ссылки

[Sakura]

GAA, спасибо за ссылки.

Вот теперь, когда мы нашли m и d, получаем, что частное решение неоднородного уравнения будет равно \alpha n^m d^n, причем m=1, а d=3, мы в наше первоначальное соотношение подставляем вместо W_n полученное частное решение?

Но тогда:

W_n_+_2 - 4W_n_+_1 + 3W_n = -2 * 3^n^+^1

получит вид:

\alpha (n+2) 3^n^+^2 - 4 \alpha (n+1) 3^n^+^1 + 3 \alpha n 3^n = -2 * 3^n^+^1

разделим правую и левую части на 3^n, получим:

\alpha (n+2) 3^2 - 4 \alpha (n+1) 3 + 3 \alpha n = -2 * 3,

раскрыв скобки, после приведения, членов с \alpha n не останется, а \alpha = -1

Это все так? А дальше что? Запишем частное решение неоднородного уравнения? Как оно будет выглядеть?

W_n = -n 3^n

Так? А что потом надо сделать? Или это уже общее решение неоднородного уравнения, которое нам и надо было найти?

Добавлено спустя 3 минуты 42 секунды:

worm2, в вашем примере х+у=1, уравнение действительно линейное, т.е. первого порядка, но ведь мое первоначально записанное рекуррентное соотношение второго порядка. Значит Ваш прием не подходит? Или как правильно надо рассуждать?

[GAA]

Sakura писал(а):

А что потом надо сделать? Или это уже общее решение неоднородного уравнения, которое нам и надо было найти?

Общим решением неоднородного уравнения будет $W_n= C_1 3^n + C_2 1^n -n3^n$ (на этом мы заканчиваем выполнение n.3 и надо перейти к пункту 4).
Добавлено

Sakura писал(а):

...мое первоначально записанное рекуррентное соотношение второго порядка. Значит Ваш прием не подходит?

Докажите, что Ваше рекуррентное соотношение линейное. Успехов!

[worm2]

Sakura писал(а):

worm2, в вашем примере х+у=1, уравнение действительно линейное, т.е. первого порядка, но ведь мое первоначально записанное рекуррентное соотношение второго порядка. Значит Ваш прием не подходит? Или как правильно надо рассуждать?

Надо рассуждать так:
${\bf w} = (W_n, W_{n+1}, W_{n+2})$ (3-мерный вектор, состоящий из 3 компонент). Чтобы не загромождать выкладки, переобозначим компоненты вектора через x, y, z: ${\bf w} = (x, y, z)$. Тогда
$f({\bf w}) = z-4y+3x$.
И нужно показать, что $f(a_1{\bf w_1}+a_2{\bf w_2}) = a_1f({\bf w_1}) + a_2f({\bf w_2})$, где $a_1$, $a_2$ --- числа, ${\bf w_1} = (x_1, y_1, z_1)$ и т.п., а под записью $a_1{\bf w_1}$ подразумевается умножение числа на вектор, ну и тут ещё сложение векторов есть.

Добавлено спустя 2 минуты 12 секунд:

Сравните, например, с нелинейным рекуррентным соотношением $x_{n+1}-x_n^2=-2$, для которого выписать явную формулу гораздо сложнее.