Как по рекуррентному соотношению найти сумму

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

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

, где

Сначала запишем формулы для слагаемых
с номерами nиn— 1.

Вычислим отношение .

Таким образом, мы получили, что

Отсюда можно легко получить рекуррентное
соотношение для вычисления очередного
слагаемого.

В этой формуле s_n– очередное
слагаемое,s_n-1– предыдущее
слагаемое,x– точка, в которой
вычисляется сумма ряда,n– номер
очередного слагаемого.

Используя
полученную рекуррентную формулу, найдем
сумму ряда в некоторой заранее заданной
точке xс определенной точностью
ε. Так же как и предыдущем случае,
исходными данными будут значениеxи необходимая точность вычислений ε.
Для ввода исходных данных будем
использовать функциюInputBox.
Результатом программы является значение
накопленной суммы. Но для проверки
правильности вычислений мы будем еще
выводить значение левой части выражения,
номер и значение последнего слагаемого,
вошедшего в сумму. Для вывода результатов
будем использовать окно списка с именемlstA.

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

Рассмотрим
особенности программной реализации
этого алгоритма. Для решения задачи нам
потребуются следующие переменные: x– точка, в которой вычисляется сумма
ряда,eps– требуемая точность вычислений,summa– искомая сумма ряда,slag– очередное слагаемое. Все эти переменные
имеют рациональный тип данных. Для
повышения точности наших вычислений
будем использовать типDouble.

Dim x, summa, slag, eps As Double

Так как рекуррентная формула зависит
от номера очередного слагаемого, то для
его хранения заведем переменную n.

Dim n As Integer

Очищаем окно списка.

lstA.Items.Clear()

Вводим исходные данные.

x = Val(InputBox(«Введите
точку»))

eps = Val(InputBox(«Введите
точность»))

Задаем начальные значения переменных.
Номер первого слагаемого равен единице.

n = 1

По формуле ряда определяем первое
слагаемое.

slag = x

Итоговую сумму полагаем равной первому
слагаемому.

summa = slag

Организуем основной цикл.

Do

На каждом шаге мы вычисляем очередное
слагаемое. При этом его номер будет на
единицу больше, чем на предыдущем шаге.

n += 1

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

slag = -slag * x ^ 2 / ((2 * n
— 2) * (2 * n — 1))

И добавляем его к итоговой сумме.

summa += slag

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

Loop Until Math.Abs(slag) <=
eps

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

lstA.Items.Add(«summa=»
+ Str(summa))

lstA.Items.Add(«sin(x)=»
+ Str(Math.Sin(x)))

lstA.Items.Add(«n=» +
Str(n))

lstA.Items.Add(«Последнее
слагаемое =» + Str(slag))

Полный
текст программы представлен в приложении
18. Пример работы программы приведен на
рис. 32. Исходные данные для этого случая:
x = 1,eps = 1e-4
= 10^-4.

Рис. 32.Пример работы программы
вычисления суммы ряда с использованием
рекуррентного соотношения

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

Как решать рекуррентные соотношения?

Для решения рекуррентных соотношений применяют один из двух основных способов:

• Метод производящих функций
• Метод характеристического уравнения

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

Метод производящих функций

1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$)
   $$a_{0} = …, \ a_{1} = …, \ a_{k-1} = …, \ … \ a_{n} = …, ngeqslant k$$
2. Домножить каждую строчку на $z$ в соответствующей степени $z^{k} cdot a_{k}$ и сложить все выражения для $n ge 0$. В левой части получится сумма $displaystylesum_{n=0}^{infty} a_nz^n$ — это производящая функция, назовем ее $G(z)$. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее $G(z)$.
3. Решить полученное уравнение относительно $G(z)$.
4. Разложить $G(z)$ в степенной ряд, тогда коэффициент при $z_n$ будет искомым выражением для $a_n$.

Метод характеристических функций

Этот метод практически полностью аналогичен методу решения линейных неоднородных дифференциальных уравнений с постоянными коэффициентами, кратко алгоритм выглядит так:

1. Записать соответствующее однородное рекуррентное уравнение (РУ):
   $$
   p_{n+k} a_{n+k} + p_{n+k-1}a_{n+k-1} + … + p_n a_n =f to \ to p_{n+k} a_{n+k} + p_{n+k-1}a_{n+k-1} + … + p_n a_n =0.
   $$
2. Выписать для него характеристическое уравнение и найти его корни $lambda_i$
   $$
   p_{n+k} lambda^{k} + p_{n+k-1}lambda^{k-1} + … + p_{n-1}lambda + p_n =0.
   $$
3. Выписать согласно полученным корням $lambda_1, …,lambda_k$ общее решение однородного рекуррентного соотношения (подробнее теорию см. по ссылке [1] ниже).
   $$
   C_1 lambda_1^n +…+C_k lambda_k^n , mbox { для случая различных простых корней},
   $$
   $$
   C_1 lambda_1^n + C_2 nlambda_1^n +…+C_m n^m lambda_1^n+…+C_k lambda_k^n mbox { для случая корня }, lambda_1 , { кратности }, m.
   $$

4. Подобрать частное решение неоднородного рекуррентного соотношения по виду правой части (особенно удобно для правых частей вида $mu^n*P(n)$, $P(n)$ — многочлен от $n$).
5. Представить общее решение неоднородного РУ как сумму общего решения соответствующего однородного РУ и частного решения неоднородного РУ.
6. Подставить начальные условия $a_0, a_1, …, a_{k-1}$ и получить значения констант $C_1, …, C_k$.

Решение для последовательности чисел Фибоначчи

Последовательность чисел Фибоначи — это последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , … $$

Числа Фибоначчи растут быстро: $f_{10}=55$, $f_{20}=6765$, а $f_{100}=354224848179261915075$.

Общая формула данной рекуррентной последовательности имеет вид6

$$begin{array}{rcl}
f_0&{}={}&0,\
f_1&{}={}&1,\
f_n&{}={}&f_{n-1}+f_{n-2}, quad ngeq2.\
end{array}
$$

Способ 1. Производящяя функция

Начинаем с второго шага алгоритма, домножаем на $z^n$:

$$begin{array}{rcl}
1cdot f_0 &= &0cdot 1,\
zcdot f_1 &= &1cdot z,\
zcdot f_n & = &(f_{n-1}+f_{n-2})cdot z^n, quad ngeq2.\
end{array}
$$

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

$$f_0 + f_1 z + sum_{n=2}^{infty}f_nz^n =
z + sum_{n=2}^{infty}f_{n-1}z^n+sum_{n=2}^{infty}f_{n-2}z^n.
$$

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

$$begin{array}{rcl}
G(z) &=& z + zsum_{n=2}^{infty}f_{n-1}z^{n-1}+z^2 sum_{n=2}^{infty}f_{n-2}z^{n-2},\
G(z) &=& z + zsum_{n=1}^{infty}f_{n}z^{n}+z^2 sum_{n=0}^{infty}f_{n}z^{n},\
G(z) &=& z + z(G(z)-f_0)+z^2 G(z),\
G(z) &=& z + zG(z)+z^2G(z),\
end{array}
$$

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

$$ G(z) = frac{z}{1-z-z^2}. $$

Теперь разложим ее в степенной ряд. Для этого сначала разложим знаменатель на множители. Найдем корни уравнения:

$$1-z-z^2 = 0,\
z_1=-frac{1-sqrt{5}}{2}, z_2=-frac{1+sqrt{5}}{2}.$$

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

$$G(z) = frac{z}{1-z-z^2}=frac{-z}{(z_1-z)(z_2-z)}
= frac{z_1/(z_1-z_2)}{z_1-z} + frac{z_2/(z_2-z_1)}{z_2-z}.
$$

Чтобы разложить данные дроби в ряды, используем известное разложение для дроби:

$$frac{1}{1-z} = sum_{n=0}^{infty}z^n = 1 + z + z^2 + z^3 + cdots.$$

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

$$ frac{z_1/(z_1-z_2)}{z_1-z} = frac{1}{z_1-z_2} frac{1}{1-frac{z}{z_1}} =
frac1{z_1-z_2}sum_{n=0}^{infty}frac{z^n}{z_1^n}.
$$

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

$$frac{z_2/(z_2-z_1)}{z_2-z} = frac{1}{z_2-z_1}frac{1}{1-frac{z}{z_2}} =
frac{1}{z_2-z_1}sum_{n=0}^{infty}frac{z^n}{z_2^n}.
$$

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

$$G(z)=sum_{n=0}^{infty} f_nz^n =sum_{n=0}^{infty}biggl (frac{1}{z_1-z_2} frac{1}{z_1^n} + frac{1}{z_2-z_1}frac{1}{z_2^n} biggr)z^n,
$$

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

$$f_n = frac1{z_1-z_2}frac{1}{z_1^n} + frac1{z_2-z_1}frac{1}{z_2^n}.
$$

Преобразуем данное выражение, используя то, что

$$1/z_1=-z_2, quad 1/z_2 = -z_1, quad z_1-z_2=sqrt{5} $$

$$f_n=frac{1}{sqrt{5}}left( biggl( frac{1+sqrt{5}}{2} biggr)^n — biggl( frac{1-sqrt{5}}{2} biggr)^n right).
$$

И окончательно,

$$ f_n = frac1{2^nsqrt{5}} bigl( (1+sqrt{5})^n — (1-sqrt{5})^n bigr). $$

Способ 2. Характеристическое уравнение

Запишем характеристический многочлен для $f_n=f_{n-1}+f_{n-2}$, и найдем его корни:

$$
x^2=x+1,\
D=1+4=5, \
x_{1,2}=frac{1pm sqrt{5}}{2}.
$$

Тогда общее решение однородного рекуррентного уравнения имеет вид:

$$
f_n=C_1 biggl(frac{1- sqrt{5}}{2} biggr)^n+C_2 biggl(frac{1+ sqrt{5}}{2} biggr)^n.
$$

Осталось найти значения произвольных постоянных $C_1, C_2$ из начальных условий $f_0=0, f_1=1$.

$$
f_0=C_1 +C_2 =0,\
f_1=C_1 bigl(frac{1- sqrt{5}}{2} bigr)+C_2 bigl(frac{1+ sqrt{5}}{2} bigr)=1.
$$

Решая систему, найдем

$$
C_1 =-1/sqrt{5},\
C_2 = 1/sqrt{5}.
$$

Итоговое выражение для последовательности чисел Фибоначчи:

$$
f_n= -frac{1}{sqrt{5}} bigl(frac{1- sqrt{5}}{2} bigr)^n +frac{1}{sqrt{5}} bigl(frac{1+ sqrt{5}}{2} bigr)^n = \
=frac1{2^nsqrt{5}} bigl( (1+sqrt{5})^n — (1-sqrt{5})^n bigr).
$$

Результаты обоих методов совпали, решение вторым методом оказалось проще и короче.

Примеры решений

Задача 1. Решить рекуррентное соотношение $f(n+2)=-6f(n+1)+7f(n)+n-3$ с начальными условиями $f(0)=2$ и $f(1)=4$, сделать проверку

Задача 2. Решить рекуррентное соотношение $f(n+2)=-2f(n+1)+3f(n)-3^n$ с начальными условиями $f(0)=1$, $f(1)=3$ и сделать проверку

Задача 3. 1. Решить рекуррентное соотношение $f(n+2) =-5f(n+1) -4f(n) + 3n^2$
с начальными условиями $f(0) = 2$, $f(1) = 3$.
2. Проверить, удовлетворяет ли найденное решение начальным условиям и обращает ли оно рекуррентное соотношение в справедливое тождество.

Задача 4. Найти последовательность ${a_n}$, удовлетворяющую рекуррентному соотношению $a_{n+2} + 4 a_{n+1} + 3 a_{n} = 0$ и начальным условиям $a_1=2$, $a_2=4$.

Полезные ссылки

• Рекуррентные последовательности, ЛОРУ, ЛНРУ Краткое изложений лекций по ДМ для 1 курса МГУ
• Решение рекуррентных соотношений Краткая теория и примеры, метод производящих функций
• Разностное уравнение и рекуррентная последовательность Более продвинутый материал
• Примеры: примитивно-рекурсивные функции
• Примеры: разностные уравнения

Определения

Определение:

Рекуррентная формула (англ. recurrence relation) — формула вида , выражающая каждый следующий член последовательности через предыдущих членов и номер члена последовательности , вместе с заданными первыми p членами, где — порядок рекуррентного соотношения.

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

член может быть записан следующим образом:

Для этого можно использовать метод производящих функций (англ. generating function method).

Метод производящих функций

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

1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен ):

2. Домножить каждую строчку на в соответствующей степени () и сложить все выражения, многоточие надо рассматривать как множество из выражений, где . В левой части получится сумма — это производящая функция, назовем ее . Правую часть преобразовать так, чтобы она превратилась в выражение, включающее .
3. Решить полученное уравнение, получив для выражение в замкнутом виде.
4. Разложить в степенной ряд, коэффициент при будет искомым выражением для .

Примеры

пример

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

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

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

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

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

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

Левая часть уравнения в точности равна , а в правой части есть суммы, очень похожие на функцию , но не равные ей. Эти суммы нужно привести к виду . Начнём с первой:

Равенство получатся вынесением в первой степени за знак суммы, это необходимо, чтобы уровнять степень переменной и индекс переменной a внутри суммы. Действие — изменение индекса суммирования, которое позволяет избавиться от . Равенство получается, если прибавить и снова отнять значение , чтобы получить полную сумму от до . Равенство справедливо в силу того, что .

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

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

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

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

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

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

Из этого разложения следует, что

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

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

поэтому, в силу равенства рядов, (для ).

пример: числа Фибоначчи

Рассмотрим рекуррентное соотношение для чисел Фибоначчи:

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

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

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

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

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

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

Нам известно разложение следующей рациональной функции:

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

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

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

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

Данное выражение можно упростить, если обратить внимание на то, что , и . Подставим и в предыдущее выражение:

пример

Найдём производящую функцию для последовательности квадратов чисел Фибоначчи: $1, 1, 4, 9, 25, ldots, f_k^2,ldots$.

По определению последовательности Фибоначчи выполняется:

Возведя в квадрат и сложив, получим:

Обозначим рассматриваемую последовательность , а её члены , тогда:

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

Приведём суммы к замкнутому виду:

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

пример

Рассмотрим следующее рекуррентное соотношение:

Следующие действия аналогичны тем, которые мы делали для чисел Фибоначчи:

Вспомним, что

поэтому

Последняя сумма может быть свёрнута:

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

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

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

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:

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

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

Значит,

См. также

• Производящая функция
• Арифметические действия с формальными степенными рядами

Источники информации

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

Рассмотрим последовательность элементов , первые элементов которой известны.

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

Определение. Рекуррентным соотношением между элементами последовательности называется формула вида ,.

Например, рекуррентное соотношение , , задает Последовательность чисел Фибоначчи: 1, 1, 2, 3, 5, 8,…

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

Рассмотрим последовательность элементов . — известные начальные значения последовательности элементов, удовлетворяющих линейному неоднородному рекуррентному соотношению (1):

, (1)

— известные действительные числа.

Тогда (2) – линейное однородное рекуррентное соотношение, соответствующее (1):

. (2)

Определение. Характеристическим Уравнением, соответствующим (2), называется уравнение вида

. (3)

Корни уравнения (3) называются характеристическими числами рекуррентного соотношения (1).

Теорема 13.1. (О структуре общего решения линейного неоднородного рекуррентного соотношения (1)). Пусть общее решение линейного однородного рекуррентного соотношения (2), — Любое частное решение линейного неоднородного рекуррентного соотношения (1). Тогда — общее решение линейного неоднородного рекуррентного соотношения (1).

Теорема 13.2. (О структуре общего решения линейного однородного рекуррентного соотношения (2)). Если — действительный корень характеристического уравнения (3) кратности , то общее решение линейного однородного рекуррентного соотношения (2) вычисляется по формуле , где — многочлен степени по переменной N, . Коэффициенты определяются из начальных значений рекуррентного соотношения.

Общее решение рекуррентного соотношения (2) при и действительных корнях уравнения (3) и имеет вид

при ,

при =.

Пример. Выведем формулу Бине для вычисления последовательности чисел Фибоначчи.

Решение. ,

— линейное однородное рекуррентное соотношение с постоянными коэффициентами , начальные значения , .

Составим характеристическое уравнение и найдем характеристические числа и . Характеристическое уравнение имеет два различных корня кратности 1, значит, . Тогда общее решение , где и произвольные постоянные (, ). Используем заданные значения , составим систему из двух уравнений с двумя неизвестными:

Решением системы является пара чисел и . Таким образом, .□

Полученная формула называется формулой Бине и применяется для вычисления значений последовательности Фибоначчи только по их номеру, независимо от предыдущих членов последовательности.

Замечание. Часто рассматривается последовательность .

Например, для последовательности чисел Фибоначчи 0, 1, 1, 2, 3, 5, … рекуррентное соотношение записывается в виде , .

Задачи и упражнения.

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

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

13.3. Составьте рекуррентное соотношение последовательности квадратов натуральных чисел.

14. Понятие производящей функции.

Рассмотрим последовательность чисел

. (1)

Рассмотрим также последовательность функций действительной или комплексной переменной

. (2)

Формально составим функциональный ряд, используя элементы (1) и (2):

. (3)

Будем считать ряд (3) сходящимся абсолютно на Или в некоторой области комплексной плоскости. Функция Является суммой ряда (3).

Определение. Сумма ряда (3) называется Производящей функцией для заданной последовательности чисел (1) по заданной последовательности функций (2).

Чаще других используются степенные функции Или . Поэтому ряд (3), как правило, является степенным.

Например. Положим в формуле бинома Ньютона . Тогда

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

Пример. Составить производящую функцию последовательности чисел Фибоначчи , , .

Решение. Используем последовательность функций действительной переменной Умножим рекуррентное соотношение на и просуммируем по :

. (4)

По допущению все ряды абсолютно сходятся на R.

.

Подставив суммы в (4), получим , тогда .□

Задачи и упражнения.

14.1. Докажите, что функция является производящей для последовательности числе, общий член которой имеет вид .

14.2. Найдите производящую функцию для последовательности чисел .

14.3. Найдите общий член последовательности, для которой функция является производящей.

14.4. Найдите общий член последовательности, для которой функция является производящей.

< Предыдущая