как решать линейные рекурентные уравнения ?

Сообщение №5953 от erdes 06 декабря 2002 г. 21:27
Тема: как решать линейные рекурентные уравнения ?

вот например
f(n+1)=An*f(n)+...+Ak*f(n-k)

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


Отклики на это сообщение:

> вот например
> f(n+1)=An*f(n)+...+Ak*f(n-k)

> есть же наверное общий метод?
> подскажите, пожалуйста
> или ссылочку дайте

А. А. Самарский, Е. С. Николаев, Методы решения сеточных уравнений.


(*) a(k)*f(n+k)+...+a(0)*f(n)=0, n=0,1,.. - линейное однородное разностное уравнение k-ого порядка.

1. В общем случае для его решения необходимо найти всех корни x(1),..,x(k) (действительные и комплексные) характеристического многочлена:
P(x)=a(k)*x^k+...+a(0)=0.
Общее решение дает сумма собственных функций (соответствующих корням характеристического многочлена) с произвольными коэффициентами.
Например, если все корни различные и действительные, то общее решение есть:
c(1)*x(1)^n+...+c(k)*x(k)^n.

2. В некоторых случаях (в том числе при непостоянных коэффициентах a(i)) также помогает метод производящих функций.
Вводится функция F(z)=sum_0^+oo f(n)*z^n (или F(z)=sum_0^+oo f(n)*z^n/n! и т.п.). Складывая (*) по всем n>=0 приходят к уравнению относительно F(z), разрешают его и полученное F(z) раскладывают обратно по степеням. Коэффициент при n-ом члене и есть f(n).

В Рунете информации на эту тему вроде немного.
Однако если в любом ихнем поисковике ввести "linear difference equations"
или "recurrence" - ссылками засыпит.
В частности есть очень неплохая электронная книга о производящих функциях: Herbert S. Wilf. GeneratingFunctionology (точной ссылки, к сожалению, не помню, но найти ее не составит труда).
На худой конец идею о производящих функциях можно уловить в Грехем Р., Кнут Д., Паташник О. Конкретная математика. М., 1998.
Из русскоязычной литературы:
1. Деч Г. Руководство к практическому применению преобразования Лапласа и Z-преобразования. М., 1971.
2. Миролюбов А.А., Солдатов М.А. Линейные неоднородные разностные уранения. М., 1986.
3. Гельфонд А.О. Исчисление конечных разностей. М., 1952.
4. Лихтарников Л.М. Элементарное введение в функциональные уравнения. СПб., 1997.


> вот например
> f(n+1)=An*f(n)+...+Ak*f(n-k)

> есть же наверное общий метод?
> подскажите, пожалуйста
> или ссылочку дайте

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

"Важный раздел К. р. и. посвящен решению разностных уравнений вида

F [x,(f (x),...,Dnf (x)] = 0 (1)

задаче, во многом сходной с решением дифференциальных уравнений n-го порядка. Обычно уравнение (1) записывают в виде

Ф [х, f (x), f (x1),..., f (xn)] = 0,

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

f (x+n) + a1f (x+n-1) +... + anf (x) = 0,

где a1,..., an - постоянные числа. Чтобы решить такое уравнение, находят корни l1, l2,... ln его характеристического уравнения

ln + a1ln-1+...+an = 0.

Тогда общее решение данного уравнения представится в виде

f (x) = С1l1х + C2l2x +... + Cnlnx,

где C1, C2,..., Cn - произвольные постоянные (здесь предполагается, что среди чисел l1, l2,..., ln нет равных).

Лит.: Березин И. С., Жидков Н. П., Методы вычислений, 3 изд., т. 1-2, М., 1966; Гельфонд А. О., Исчисление конечных разностей, 3 изд., М., 1967."



я услышал то, что хотел услышать
отличный форум


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100