#freeze
*漸化式：Recurrence relation [#eb78a13d]
In mathematics, a recurrence relation is an equation that recursively defines a sequence: each term of the sequence is defined as a function of the preceding terms.

A difference equation is a specific type of recurrence relation.

*漸化式の例：フィボナッチ数列 [#y81e9681]
-Example: Fibonacci numbers
 Fn+2 = Fn+1 + fn with initial values F0=0,F1=0.
We obtain the sequence of Fibonacci numbers which begins:
 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
-一般解の導出
The Fibonacci recursion
 Fn+2 - Fn+1 - Fn =0
is similar to the defining equation of the golden ratio in the form
 x^2 - X -1 = 0 
which is also known as the generating polynomial of the recursion.
By definition α,β is a root of the equation
 α = (1+√5)/2,　β=(1-√5)/2.
Any root of the equation above satisfies x^2 - X -1 = 0 and multiplying by  x^n　shows:
 x^(n+2)-x^(n+1)-x^n = 0
Both α^n and β^n are geometric series (for n = 1, 2, 3, ...) that satisfy the Fibonacci recursion. 
Linear combinations of series α^n and β^n, with coefficients a and b, can be defined by
 Fc(n)=a・α^n + b・β^n　for any real a and b.
All thus-defined series satisfy the Fibonacci recursion
 Fc(n+2)=a・α^(n+2) + b・β^(n+2)
        =a・(α^(n+1)+α^n) + b・(β^(n+1)+β^n)
        =a・α^(n+1)+ b・β^(n+1) + a・α^n+b・β^n
        =Fc(n+1) + Fc(n).
Requiring that Fc(0)=0,Fc(1)=1 yields 
 Fc(0)=a・α^0 + b・β^0 = a + b =0
 Fc(1)=a・α^1 + b・β^1 = a・α + b・β =0
Then　a=1/√5　and　b=-1/√5.
The solution of the Fibonacci recursion is
 Fn=(α^n - β^n)/√5　=｛(1+√5)/2｝^n　＋　｛(1+√5)/2｝^n
 α = (1+√5)/2,　β=(1-√5)/2.
-''このことから　特性方程式の解の線形結合で、一般解が求められることが理解できる。''
*線形差分方程式の特性関数を用いた一般解法 [#edd965a3]
An order  linear homogeneous recurrence relation with constant coefficients is an equation of the form:
 Fn = a1・Fn-1 + a2・Fn-2 + a3・Fn-3 + ・・・・+am・Fn-m
The characteristic polynomial is 
 p(x)=x^m-a1・xm-1 + a2・xm-2 + a3・xm-3 + ・・・・+am=0.

-For order 1 no theory is needed; the recurrence
 Fn=r・Fn-1　with initial condition F0=k.
Note that the characteristic polynomial is simply x-r=0.
The most general solution is 
 Fn=k・r^n　.
-Consider, for example, a recurrence relation of the form
 Fn=a1・Fn-1 + a2・Fn-2
The characteristic polynomial is
 p(x)=x^2-a1・x - a2=0
Solve for x to obtain the two roots λ1, λ2.
If these roots are distinct, we have the general solution
 Fn = A・λ1^n + B・λ2^n
while if they are identical (when a1^2 + 4a・2 = 0), we have
 Fn = A+ B・n・λ2^n
This is the most general solution, the two constants A and B can be chosen freely to produce a solution. If "initial conditions"  have been given then we can solve (uniquely) for A and B.

-m次元の線形漸化式は、特性方程式のm個の解と初期条件を使って、n番目のFnを解のn乗線形結合で表わされることが理解できる。
-このことは、線形差分方程式の解が明示的に求められることを意味する。言い換えれば、積分計算をしなくても解析解を示せることを意味する。

*微分方程式の差分による解法：オイラー法の例 [#w9b119ba]
When solving an ordinary differential equation numerically, one typically encounters a recurrence relation. For example, when solving the initial value problem
 y'(t)=f(t,y(t)) , y0=y(t0)
with Euler's method and a step size h, one calculates the values
 y0=y(t0), y1=y(t0+h),y2=y(t0+2h),・・・・・・・・
by the recurrence
 yn+1 = yn + h・f(tn,yn)
Systems of linear first order differential equations can be discretized exactly analytically using the methods shown in the discretization article.
#ref(http://upload.wikimedia.org/wikipedia/commons/thumb/a/ae/Euler_method.png/220px-Euler_method.png)

-y'(t)=f(t,y(t))=r・y(t)の場合

--厳密解は、y(t)=e^rt
積分区間[t0,tf]をn分割すると、h=(tf-t0)/nである。
 yn=y(to+nh)=yo・e^(rnh)　=y0・e^(r(tf-t0))　・・・・・厳密解
--オイラー法では
  yn+1 = yn + h・f(tn,yn)= yn + hr・yn=(1+hr)・yn
これを繰り返すので
 yn = y0・(1+hr)^n　　　　・・・・・オイラー法の近似解
刻み幅hを十分小さくするとyn= y0・(1+hr)^n　は、指数eの定義より
 Lim　y0・(1+r(tf-t0)/n)^n　=　y0・e^(r(tf-t0))
となり、厳密解に収束する。
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS