Изменения

Перейти к: навигация, поиск

Решение рекуррентных соотношений

334 байта убрано, 22:13, 12 марта 2018
Нет описания правки
==Примеры==
====ЧИСЛА ФИБОНАЧЧИ====
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
 
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
<br>[[Файл:Img39.png]]<br>
 
Это хорошо известная последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:
<br>[[Файл:Img40.png]]<br>
Эти числа очень быстро растут, например, f10=55, f20=6765, f30=832040, f100=354224848179261915075.
 
Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:
<br>[[Файл:Img45.png]]<br>
откуда получаем замкнутое выражение для производящей функции:
<br>[[Файл:Img48.png]]<br>
Осталось «всего лишь» разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:
<br>[[Файл:Img49.png]]<br>
Таким образом (проверьте),
<br>[[Файл:Img50.png]]<br>
Как теперь поступить с этими выражениями? Ведь пока нам Нам известно разложение только одной следующей рациональной функции:
<br>[[Файл:Img31.png]]<br>
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на <math>z1</math>:
<br>[[Файл:Img52.png]]<br>
Аналогично (но с делением на <math>z2</math>) поступим со второй дробью:
<br>[[Файл:Img53.png]]<br>
Таким образом,
и, следовательно,
<br>[[Файл:Img55.png]]<br>
Данное выражение можно «причесать»упростить, если обратить внимание на то, что <math>1/z1=-z2</math>, <math>1/z2=-z1 </math> и <math>z1-z2=√5 (корень из 5)</math>:
<br>[[Файл:Img59.png]]<br>
 
====БОЛЕЕ СЛОЖНОЕ СООТНОШЕНИЕ====
302
правки

Навигация