漸化式: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))
    となり、厳密解に収束する。

トップ   差分 バックアップ リロード   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-05-08 (土) 16:39:00 (3451d)