## 漸化式：Recurrence relation †

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.

## 漸化式の例：フィボナッチ数列 †

• 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.```
• このことから　特性方程式の解の線形結合で、一般解が求められることが理解できる。

## 線形差分方程式の特性関数を用いた一般解法 †

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乗線形結合で表わされることが理解できる。
• このことは、線形差分方程式の解が明示的に求められることを意味する。言い換えれば、積分計算をしなくても解析解を示せることを意味する。

## 微分方程式の差分による解法：オイラー法の例 †

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.

• 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))`
となり、厳密解に収束する。

Last-modified: 2010-05-08 (土) 16:39:00 (3795d)