|
|
Основы метода конечных разностей
Как по заданной последовательности {fn} D¢n = fn+1 – fn , D¢¢n = D¢n+1 – D¢n , … , D(m+1)n = D(m)n+1 – D(m)n , … Легко получить следующие формулы: D¢¢n = D¢n+1 – D¢n = (fn+2 – fn+1) – (fn+1 – fn) = fn+2 – 2×fn+1 + fn , D¢¢¢n = D¢¢n+1 – D¢¢n = (fn+3 –2×fn+2+fn+1) – (fn+2 –2×fn+1+fn) = fn+3 –3×fn+2+3×fn+1 –fn , D(m)n = Пример: Рассмотрим последовательность квадратов f(n) = n2 (n Î N0).Вычислим последовательные разности: D¢n = f(n+1) – f(n) = 2×n+1. Таким образом, f(n+1) = f(n) + 2×n+1 – рекуррентное соотношение первого порядка. Если вычислить вторые разности D¢¢n = D¢n+1 – D¢n = (2×(n+1)+1) – (2×n+1) = = 2, то получим f(n+2) – 2×f(n+1) + f(n) = 2, т.е. f(n+2) = 2×f(n+1) – f(n) + 2 – рекуррентное соотношение второго порядка. За счёт повышения порядка соотношения упрощается добавка в правой части: вместо 2×n + 1 получили 2. Вычислим D¢¢¢n = D¢¢n+1 – D¢¢n = 2 – 2 = 0. Таким образом, получаем рекуррентное соотношение третьего порядка: f(n+3) = 3×f(n+2) – f(n+1) + f(n). Оказывается, метод последовательных разностей позволяет задать рекуррентным соотношением любую последовательность натуральных степеней {nk} Этот метод можно применять и к другим видам последовательностей. Например, если f(n) = log5 f(n+1) = log5 f(n) + 2×n + 1 Û f(n+1) = f(n)×52×n+1. Если выбрать рекуррентное соотношение u(n+2) = 2×u(n+1) – u(n) + 2, то получим log5 f(n+2) = 2×log5 f(n+1) – log5 f(n) + 2 Û f(n+2) = 25× 5. Числа Фибоначчи. Рассмотрим следующую задачу. Пара кроликов раз в месяц приносит приплод из двух крольчат (самки и самца), которые через два месяца после рождения тоже приносят приплод. Сколько кроликов появится через год, если в начале была одна пара и в течение года кролики не умирают и их воспроизводство не прекращается ? Пусть f(n) – количество пар кроликов через n месяцев. Ясно, что по условию f(0) = 1, f(1) = 2. Пусть уже прошёл n – 1 месяц и известны числа f(0), f(1), … , f(n – 1). Через месяц размножатся все пары кроме последних f(n – 1) – f(n – 2) пар, т.е. появится f(n – 1) – (f(n – 1) – f(n – 2)) = f(n – 2) новых пар, и всего станет f(n – 1) + f(n – 2) пар кроликов. Таким образом, Полученная последовательность 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, … называется последовательностью чисел Фибоначчи. Она является рекуррентной последовательностью порядка 2. Рассмотренные примеры показывают, что рекуррентные последовательности встречаются в самых разных математических задачах. В примерах 1, 2, 3 были найдены общие решения рекуррентных соотношений в смысле следующего определения: последовательность j(c0 , … , ck–1 , n), зависящая от k независимых параметров c0 , … , ck–1 Î С ,называется общим решением рекуррентного соотношения f(n+k) = F(n, f(n+k–1), f(n+k–2), … , f(n)) (n Î N0) порядка k , если одновременно выполнены два условия: (ОР1):при любых значениях c0 , … , ck–1 Î С j(c0 , … , ck–1 , n) является решением рассматриваемого рекуррентного соотношения, т.е. верны равенства j(c0 , … , ck–1 , n+k) = F(n, j(c0 , … , ck–1 , n+k–1), … , j(c0 , … , ck–1 , n)). (ОР2):для любого решения a(n) рассматриваемого соотношения найдутся значения параметров c0 , … , ck–1 Î С , что a(n) = j(c0 , … , ck–1 , n) для любого n Î N0 . В рассмотренных примерах j(с, n) = с×n! – общее решение рекуррентного соотношения f(n + 1) = (n + 1)×f(n) , j(a, n) = a×qn – общее решение рекуррентного соотношения f(n + 1) = q×f(n), j(a, d) = a + d×n – общее решение рекуррентного соотношения f(n + 2) = 2×f(n + 1) – f(n). Последовательность чисел Фибоначчи, являясь решением рекуррентного соотношения второго порядка f(n+1) = f(n) + f(n – 1), удовлетворяет начальным условиям f(0) = 1, f(1) = 2. Основная задача теории рекуррентных соотношений может быть сформулирована как задача нахождения общих решений рекуррентных соотношений. При этом выше было показано, что по первым k значениям последовательности-решения однозначно восстанавливаются остальные её члены. Поэтому важен не процесс вычисления решения, а отыскание явной формулы, задающей n-й член общего решения. Наиболее изучены линейные рекуррентные соотношения с постоянными коэффициентами, т.е. соотношения вида f(n + k) = a1×f(n + k – 1) + … + ak×f(n) + b(n), где a1 , … , ak – заданные постоянные комплексные числа – коэффициенты соотношения, ak ¹ 0, а b(n) – заданная последовательность – свободный член соотношения. Если b(n) = 0 при любом n Î N0 , то линейное рекуррентное соотношение называется однородным, в противном случае – неоднородным. Примеры: В рассмотренных выше примерах линейными с постоянными коэффициентами были соотношения f(n+1) = q×f(n), f(n+2) = 2×f(n+1) – f(n), f(n+1) = f(n) + 2×n+1, f(n+2) = f(n) + f(n–1). Все, кроме третьего, являются однородными. Теорема (о линейной структуре решений линейного рекуррентного соотношения). (1) Если {un} (2) Общее решение линейного рекуррентного соотношения с постоянными коэффициентами является суммой общего решения соответствующего линейного однородного соотношения и некоторого частного решения исходного неоднородного рекуррентного соотношения. Доказательство. (1) проверяется непосредственно: если un+k = a1×un+k–1 + … + ak×un , vn+k = a1×vn+k–1 + … + ak×vn , то (un+k ± vn+k) = (a1×un+k–1 + … + ak×un ) ± (a1×vn+k–1 + … + ak×vn ) = = a1×(un+k–1 ± vn+k–1 ) + … + ak×(un ± vn ), т.е. {un ± vn} Аналогично, (a×un+k ) = a×(a1×un+k–1 + … + ak×un ) = = a1×(a×un+k–1 ) + … + ak×(a×un ), т.е. {a×un } (2) Пусть y(c0 , … , ck–1 , n) = y(с, n), где для краткости введено обозначение c = (c0 , … , ck–1) – общее решение линейного однородного рекуррентного соотношения f(n+k) = a1×f(n+k–1)+…+ak×f(n), а v(n) – произвольное частное решение неоднородного соотношения f(n+k) = a1×f(n+k–1)+…+ak×f(n) + b(n). Вначале покажем, что j(c , n) = y(c , n)+v(n) будет решением рассматриваемого неоднородного соотношения. Тогда j(с, n+k) = y(с , n+k) + v(n+k) = = (a1×y( c, n+k–1)+…+ak×y(c, n)) + (a1×v(n+k–1)+…+ak×v(n)+b(n)) = = a1×(y( c, n+k–1)+v(n+k–1)) + … + ak×(y(c, n) + v(n)) + b(n)= = a1×j(c, n+k–1)+…+ak×j(c, n) + b(n), что и требовалось. Таким образом, j(с, n) = j(c0 , … , ck–1 , n) – решение неоднородного соотношения. Докажем теперь, что j(c0 , … , ck–1 , n) – общее решение этого неоднородного рекуррентного соотношения. Для этого нужно понять, что любое решение получается при некоторых значениях параметров c0 , … , ck–1 . Пусть w(n) – любое решение исходного неоднородного соотношения. Тогда w(n) – v(n) будет решением однородного соотношения: (w(n+k) – v(n+k)) = = (a1×w(n+k–1) + … + ak×w(n) + b(n)) – (a1×v(n+k–1) + … + ak×v(n) + b(n)) = = a1×(w(n+k–1) – v(n+k–1)) + … + ak×(w(n) – v(n)). Поскольку y(с, n) – общее решение однородного соотношения, то найдётся такой набор c0 = a0 , … , ck–1 = ak–1 , что w(n)–v(n) = y(a1 , … , ak , n) , поэтому w(n) = y(a1 , … , ak , n)+v(n) = j(a1 , … , ak , n), что и требовалось. Теорема доказана. Эта теорема сводит задачу нахождения общего решения линейного неоднородного рекуррентного соотношения порядка k c постоянными коэффициентами к нахождению общего решения соответствующего линейного однородного рекуррентного соотношения и поиску частного решения исходного неоднородного соотношения.
Не нашли, что искали? Воспользуйтесь поиском по сайту: ©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|
построить рекуррентное соотношение k-го порядка, которому она удовлетворяет ? В некоторых случаях можно применить следующий приём, связанный с рассмотрением конечных разностей последовательности {fn} 
.
с фиксированным показателем k Î N.
, то можно рассмотреть вспомогательную более простую последовательность u(n) = log5 f(n) = n2 найти для неё с помощью метода конечных разностей рекуррентное соотношение, например, соотношение u(n+1) = u(n) + 2×n + 1 и вернуться обратно к последовательности f(n):
.
.