漸化式

漸化式：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))

  となり、厳密解に収束する。