Рекуррентные последовательности примеры решения

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

Производящие функции наиболее часто применяются при решении рекуррентных соотношений. Рекуррентные соотношения, в свою очередь, часто возникают в дискретной математике и комбинаторике, поэтому метод производящих функций для решения рекуррентных соотношений изучают именно в рамках этих дисциплин. Самые простыепримеры решения рекуррентных соотношений приводятся в этой лекции. Более сложные примеры — в последующих лекция.

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

Общая схема

Пусть последовательность (a0, a1, a2, …) удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для an (при n≥0) в замкнутом виде (если это возможно). Производящие функции позволяют делать эту работу почти механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.

Задано линейное однородное рекуррентное соотношение порядка 2 с постоянными коэффициентами:

Порядок соотношения — это его «глубина», то есть количество предшествующих элементов, требуемых для вычисления элемента с номером n. В данном случае порядок равен 2, так как для вычисления an требуется знать an-1 и an-2.

Попытаемся для начала «угадать» ответ:

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

Будем искать производящую функцию последовательности в виде

с этой целью умножим верхнюю строчку в записи рекуррентного соотношения на z0, следующую — на z1 и последнюю — на zn:

Теперь сложим все уравнения для всех значений n:

Левая часть уравнения в точности равна G(z), а в правой части есть суммы, очень похожие на функцию G(z), но не равные ей. Эти суммы нужно любым законным способом (используя правила работы с алгебраическими выражениями) привести к виду G(z). Начнём с первой:

Равенство (1) получатся вынесением z в первой степени за знак суммы, это необходимо, чтобы уровнять степень переменной z и индекс переменной a внутри суммы. Действие (2) — изменение индекса суммирования, которое позволяет избавиться от n-1. Равенство (3) получается, если прибавить и снова отнять значение a0, чтобы получить полную сумму от n=0 до ∞. Равенство (4) справедливо в силу того, что a0=0.

Аналогичные манипуляции со второй суммой дают нам выражение

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

откуда получаем производящую функцию последовательности в замкнутом виде —

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

Это можно сделать разными способами, но самый простой из них — разбить всю дробь на простые дроби и применить формулу для разложения 1/(1-z). Итак, разложим знаменатель функции на множители:

Теперь разобьём дробь на сумму простых дробей:

Вспомним разложение для простейшей рациональной функции:

Из этого разложения следует, что (см. также таблицу производящих функций)

Таким образом,

С другой стороны, мы искали G(z) в виде

поэтому, в силу равенства рядов, an=3n-2n (для n≥0). Теперь скажите: как проверить правильность полученного ответа?

Алгоритм

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

  1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен k):
  2. Домножить каждую строчку на z в соответствующей степени и просуммировать строчки для всех n≥0.
  3. В полученном уравнении привести все суммы ∑ к замкнутому виду. Получить уравнение для производящей функции.
  4. Выразить G(z) в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням z.

Числа Фибоначчи

Это классический пример, который приводят почти везде, где речь идет о решении рекуррентных соотношений. Рассмотрим рекуррентное соотношение для чисел Фибоначчи:

Это хорошо известная последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

Эти числа очень быстро растут, например, f10=55, f20=6765, f30=832040, f100=354224848179261915075.

Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:

Складываем все строчки:

Третий шаг алгоритма требует привести все суммы к замкнутому виду:

откуда получаем замкнутое выражение для производящей функции:

Осталось «всего лишь» разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:

Таким образом (проверьте),

Как теперь поступить с этими выражениями? Ведь пока нам известно разложение только одной рациональной функции:

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на z1:

Аналогично (но с делением на z2) поступим со второй дробью:

Таким образом,

и, следовательно,

Данное выражение можно «причесать», если обратить внимание на то, что 1/z1=-z2, 1/z2=-z1 и z1-z2=√5 (корень из 5):

Если записывать формулу в терминах хорошо известного «золотого сечения»

то, обозначив , получим

Если «золотое сечение» не использовать, то лучше всего формула выглядит в следующем виде:

чего достаточно трудно было ожидать, глядя на красивое исходное рекуррентное соотношение.

Обязательно проверьте формулу хотя бы для n=0, 1, 2. Как изменится производящая функция и конечная формула, если положить f0=f1=1?

Более сложное соотношение

Рассмотрим довольно произвольное рекуррентное соотношение:

Рассчитаем несколько первых элементов:

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

Пока непонятно, что делать с последней суммой. Как её «замкнуть»? На самом деле, очень просто, если вспомнить про производную (подробнее см. лекцию «Преобразование производящих функций: полиномиальный множитель и делитель»):

поэтому

Обратите внимание, что мы вынесли производную за знак бесконечной суммы, не проверив, имеем ли мы на это право. Можно показать, что все сделано законно, но мы не будем этим заниматься сейчас. Последняя сумма может быть свёрнута:

Подставив свёрнутое выражение обратно, имеем,

Таким образом, наше последнее уравнение примет вид

Это уравнение для производящей функции. Из него выражаем G(z):

Довольно страшное выражение, которое нам предстоит разложить в ряд, на самом деле только кажется таким. Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:

Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее (см. также «Расширенные биномиальные коэффициенты»):

Теперь соберём ответ:

Значит,

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

↑ наверх ↑

вернуться к содержанию


Вывод формулы n-ного члена для рекуррентной последовательности на примере задачи из квеста Амнезия

Пеленгский фермер Бух’ерик разводит хрякоплюхов. Эти животные размножаются так быстро, что их поголовье ежедневно возрастает в 3 раза. Но, начиная со второго дня, на ферму повадилась нападать стая страшных зверей долбогрызов, каждый вечер пожирающих вдвое больше хрякоплюхов, чем их было в предыдущий день.

Линейная рекуррентная последовательность

Сколько хрякоплюхов будет у фермера на 7-й вечер, если вначале их было 10?

Вы спросили у гаальца, что он думает по поводу этой задачки. После некоторого размышления тот ответил:
— В начале было 10 хрякоплюхов. В первый день они размножились, и к началу второго дня их стало 30. Во второй день они опять размножились (их стало 90), но вечером пришли долбогрызы и съели вдвое больше хрякоплюхов, чем было вчера (в первый день), т.е. 20 штук. Итого, в начале третьего дня получаем 70 хрякоплюхов. Мне кажется, что, продолжая решать таким образом, можно вычислить число хрякоплюхов в любой день.

Это задача из игры «Космические Рейнджеры 2», квест Амнезия.
Попробуем вывести формулу для количества хрякоплюхов на n-ный день, и посчитать для примера количество хрякоплюхов на 32-й день.

Читать дальше →

Читать полностью

математика, космические рейнджеры

Вычисление суммы. Рекуррентные формулы.

⇐ Предыдущая123Следующая ⇒

Условие задачи: Для x, изменяющегося в интервале от x0 до xk с шагом h, вычислить значения бесконечной суммы y(x) с точностью e=0.00001.

e = 0.000001: n = 1

For x = xh To xk Step dx

y = 0: i = 0: u = 1

 

While Abs(u) > e : y = y + u : u = (x) ^ 2 / (i + 1) * u : i = i + 1

Wend : n = n + 1

Next x

 

Вычисление чисел Фибоначчи.

Sub Fib1()

ActiveCell.FormulaR1C1 = "1"

Range("A2").Select

ActiveCell.FormulaR1C1 = "2"

Range("A3").Select

ActiveCell.FormulaR1C1 = "=R[-2]C+R[-1]C"

Range("A3").Select

Selection.AutoFill Destination:=Range("A3:A20"), Type:=xlFillDefault: Range("A3:A20").Select

 

18. Нахождение «сигнальной» матрицы В = sign(A).

Sub matAB()

Dim a(3, 3) As Integer : Dim b(3, 3) As Integer

Dim i, j As Integer : Dim s1, s2 As String

For i = 1 To 3 : For j = 1 To 3

If a(i, j) > 0 Then: b(i, j) = 1: Else

If a(i, j) = 0 Then: b(i, j) = 0: Else: b(i, j) = -1: End If

End If: Range(s1).Cells = b(i, j): Next: Next: End Sub

 

19. Решение уравнений вида f(x) = 0. Метод Ньютона.

При x=а f’(x)*f ’’(x)<0 – функция убывающая и f’(x)*f ’’(x)>0-функция возрастающая.

Расчетная формула Ньютона имеет вид:

Вычисления ведутся до тех пор, пока |xn-xn-1|<E

While Abs(f(x)) > 0.01

i = i + 1

x = x — f(x) / f1(x)

Wend

End Sub

 

20.

Рекуррентные соотношения.

Решение уравнений вида f(x) = 0. Метод деления отрезка пополам.

Алгоритм:

1. Ввести данные (а, b, е)

2. Если нужная точность достигнута (|b-a|<2е), переходим у пункту6

3. Взять середину очередного отрезка c=(a+b)/2

4. Если значение функции в точках а и с одного знака (f(а)*f (с)>0), то в качестве следующего отрезка взять другую половину а=с, иначе b=c.

5. Перейти к пункту 2

6. Напечатать ответ (a+b)/2

x = Del(a, b, eps)

Function Del(a As Double, b As Double, e As Double) As Double

Dim x As Double, n As Integer

If fun(a) * fun(b) <= 0 Then

n = 0: While (b — a) > e: n = n + 1 : x = (a + b) / 2

If fun(a) * fun(x) <= 0 Then

b = x: Else: a = x: End If

Range("B5").Cells = n : Del = (a + b) * 0.5

Wend: Else: MsgBox ("a,b=?")

Exit Function : End If : End Function

 

21. Решение уравнений вида f(x) = 0. Метод хорд.

Xn+1= Xn-(f(Xn)(b- Xn))/(f(b)-f(Xn))

Xn+1= Xn-(f(Xn)(Xn-а))/(f(Xn)-f(a))

| Xn+1- Xn|<Ɛ

x = Hor(a0, b0, eps)

Function Hor(a As Double, b As Double, e As Double) As Double: Dim x As Double, x0 As Double, n As Integer: If fun(a) * fun(b) <= 0 Then

n = 0: x0 = a: x = b: While Abs(x0 — x) > e

n = n + 1: x0 = x: x = b — fun(b) * (b — a) / (fun(b) — fun(a)): If fun(a) * fun(x) <= 0 Then: b = x : Else : a = x: End If : Hor = x: Wend : Else MsgBox ("a,b=?"): Exit Function : End If : End Function

 

22. Решение систем линейных уравнений итерационнымиметодами. Метод простой итерации.

Нормой вектора B и матрицы А называют соответственно следующие числа: ;

количество итераций m: m≥

|x(m)— x(m-1)| ≤

Xn+1= Xn-(f(Xn)(b- Xn))/(f(b)-f(Xn))

Xn+1= Xn-(f(Xn)(Xn-а))/(f(Xn)-f(a))

|Xn+1Xn|<Е

Алгоритм:

1) Преобразуем исходную систему к виду x=αx+β.

2) Находим норму матрицы.

3) Если |α| < 1, то переходим к пункту 4.

4) Задается начальное приближение и ε

5) Рассчитывается количество итераций i.

6) Вычисляется очередная итерация xi+1=n(xi)

7) Если |x(m)— x(m-1)| ≤ , то процесс закончен, иначе переход к пункту 6.

x = Hor(a0, b0, eps)

Call Iter(eps, x, n)

For i = 1 To 4

x(i) = 0: Next i: n = 0

Do : n = n + 1: l = False

For i = 1 To 4 : x0(i) = x(i) : Next i

For i = 1 To 4 : x(i) = b(i) / a(i, i)

For j = 1 To i – 1 : x(i) = x(i) — a(i, j) / a(i, i) * x0(j) : Next j

For j = i + 1 To 4 : x(i) = x(i) — a(i, j) / a(i, i) * x0(j) : Next j

If Abs(x(i) — x0(i)) > e Then : l = True

End If : Next i : Loop Until Not l : End Sub

 


⇐ Предыдущая123Следующая ⇒


Дата добавления: 2017-03-12; просмотров: 212 | Нарушение авторских прав


Поиск на сайте:


Добавить комментарий

Закрыть меню