セカント法

メソッド

$f,f’,f’’$が$\alpha$の近傍で連続であり、$f(\alpha) = 0, f '(\alpha) \ne 0$とする。

$\alpha$に十分近い初期値$x_{0} , x_{1}$に対して $$ x_{n+1} := x_{n} - f ( x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }} $$ と定義された数列$\left\{ x_{n} \right\}$は、$n \to \infty$のとき$\alpha$へ$\displaystyle {{1 + \sqrt{5} } \over {2}}$次で収束する。

説明

黄金比

収束次数にかなり見覚えがあるはずだ。まさに黄金比の$\displaystyle {{1 + \sqrt{5} } \over {2}} = 1.618 \cdots$であり、数列の定義で三つの連続した項を使うため、証明の中にフィボナッチ数列が登場する。セカント法の有用性に言及する以前に、かなり興味深い現象である。この次数は、セカント法がバイセクション法よりは速いが、ニュートン・ラプソン法よりは遅いことを意味する。

ニュートン・ラプソン法の方が速いにもかかわらず、あえてこのような方法を考案した理由は、導関数を求めることが過度に難しい場合があるからである。また、計算量で比較すると、収束次数が低いためニュートン・ラプソン法に比べて計算回数は多いが、一回一回の計算コストの面ではセカント法の方が良い場合がある。どの方法がより良いかは問題による。（しかし正直に言えば、ニュートン法以外はほとんど使わない。）

初期値問題

ニュートン・ラプソン法と同様に、初期値が悪く与えられた場合、$\alpha$に十分近くないために収束しないことがある。

証明¹

• $\mathscr{H} \left\{ a,b,c, \cdots \right\}$は$a,b,c, \cdots$を含む最小の区間を表す。

パート1. 差分商

$$ \begin{align*} f [ x_{0} , x_{1} ] :=& {{ f ( x_{1} ) - f ( x_{0} ) } \over { x_{1} - x_{0} }} \\ f [ x_{0} , x_{1} , x_{2} ] :=& {{ f [ x_{1} , x_{2} ] - f [ x_{0} , x_{1} ] } \over { x_{2} - x_{0} }} \end{align*} $$ を定義しよう。これらを差分商と呼び、$f ’ ( \xi ) = f [ x_{0} , x_{1} ]$と$\displaystyle {{1} \over {2}} f ’’ ( \zeta ) = f [ x_{0} , x_{1} , x_{2} ]$を満たす $$ \begin{align*} \xi \in& \mathscr{H} \left\{ x_{0} , x_{1} \right\} \\ \zeta \in& \mathscr{H} \left\{ x_{0} , x_{1} , x_{2} \right\} \end{align*} $$ が存在する。

パート2. $\displaystyle \alpha - x_{n+1} = - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f ''( \zeta _{n} ) } \over { 2 f ’ ( \xi_{n} ) }}$

$x_{n+1} = x_{n} - f ( x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }}$の両辺に$-1$を掛けて$\alpha$を加えると $$ \alpha - x_{n+1} = \alpha - x_{n} + f ( x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }} $$ であり、 $$ \begin{align*} \alpha - x_{n+1} =& \alpha - x_{n} + {{ x_{n} f ( x_{n} ) - x_{n-1} f ( x_{n} ) } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \\ =& {{ x_{n} f ( x_{n} ) - x_{n-1} f ( x_{n} ) + \alpha f(x_{n}) - x_{n} f(x_{n}) - \alpha f(x_{n-1}) + x_{n} f(x_{n-1}) } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \\ =& {{1 } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ - x_{n-1} f ( x_{n} ) + \alpha f(x_{n}) - \alpha f(x_{n-1}) + x_{n} f(x_{n-1} ) \right] \\ =& {{1 } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ ( \alpha - x_{n-1} ) f ( x_{n} ) - ( \alpha - x_{n} ) f(x_{n-1} ) \right] \\ =& - {{ ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ {{ f ( x_{n} ) } \over { x_{n} - \alpha }} - {{ f(x_{n-1}) }} \right] \\ =& - {{ ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ {{ f ( x_{n} ) - f(\alpha) } \over { x_{n} - \alpha }} - {{ f(x_{n-1} ) - f( \alpha) } \over { x_{n-1} - \alpha }} \right] \\ =& - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ 1 } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ f[ x_{n} , \alpha ] - f[ x_{n-1} , \alpha ] \right] \\ =& - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ {{ f[ x_{n} , \alpha ] - f[ x_{n-1} , \alpha ] } \over { x_{n} - x_{n-1} }} \right] \\ =& - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f [ x_{n-1} , x_{n} , \alpha ] } \over { f [ x_{n-1} , x_{n} ] }} \end{align*} $$ である。整理すると $$ \alpha - x_{n+1} = - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f [ x_{n-1} , x_{n} , \alpha ] } \over { f [ x_{n-1} , x_{n} ] }} $$ であり、差分商の性質により次を得る。 $$ \alpha - x_{n+1} = - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f ''( \zeta _{n} ) } \over { 2 f ’ ( \xi_{n} ) }} $$

パート3. 収束性

与えられた仮定をすべて満たす$\alpha$の近傍として、十分小さい$I : = [ \alpha - \delta , \alpha + \delta ]$を考えよう。

$$ M := {{ \max_{x \in I } | f '' (x) | } \over { 2 \min_{x \in I} | f '(x) | }} $$ と定義すると、パート1で得た結果により $$ | \alpha - x_{n+1}| \le | \alpha - x_{n} | | \alpha - x_{n-1} | M $$ 両辺に$M$を掛けると $$ | \alpha - x_{n+1}| M \le ( | \alpha - x_{n} | M ) \cdot ( | \alpha - x_{n-1} | M ) $$ 十分小さい$I$を想定したので $$ \varepsilon := \max \left\{ ( | \alpha - x_{n} | M ) , ( | \alpha - x_{n-1} | M ) \right\} < 1 $$ を取れば $$ | \alpha - x_{n+1}| M \le \varepsilon^2 $$ $$ | \alpha - x_{n+3}| M \le ( | \alpha - x_{n+2}| M ) \cdot ( | \alpha - x_{n+1}| M ) \le \varepsilon^2 \cdot \varepsilon = \varepsilon^3 $$ $$ | \alpha - x_{n+4}| M \le ( | \alpha - x_{n+3}| M ) \cdot ( | \alpha - x_{n+2}| M ) \le \varepsilon^3 \cdot \varepsilon^2 = \varepsilon^5 $$ 同様の方法で不等式 $$ | \alpha - x_{n+m+1}| M \le ( | \alpha - x_{n+m}| M ) \cdot ( | \alpha - x_{n+m-1}| M ) \le \varepsilon^{ q_{m} } \cdot \varepsilon^{ q_{m-1} } = \varepsilon^{ q_{m+1} } $$ を得る。

フィボナッチ数列の一般項: 数列$\left\{ F_{n} \right\}$が$F_{n+1} := F_{n} + F_{n-1}$のように定義されているとしよう。$F_{0} = F_{1} = 1$ならば、$\displaystyle r_{0} : = {{1 + \sqrt{5} } \over {2}}$と$\displaystyle r_{1} : = {{1 - \sqrt{5} } \over {2}}$に対して$\displaystyle F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }} $

$\left\{ q_{m} \right\}$はほかならぬフィボナッチ数列であり、十分大きい$m$に対して $$ q_{m} \sim {{1} \over {\sqrt{5}}} ( 1.618 )^{m+1} $$ である。したがって $$ | \alpha - x_{n+m}| \le {{1} \over {M}} \varepsilon^{ q_{m} } $$ であり、$n \to \infty$のとき$x_{n} \to \alpha$であるだけでなく、 $$ {{1 + \sqrt{5} } \over {2}} \sim 1.618 $$ 次で収束することが確認できる。

■

実装

以下はRで書かれたコードである。

itmaxオプションは最大反復回数であり、デフォルトでは$1000$回反復しても望むほど精密な解が得られなければ計算を諦める。

Secant<-function(f,x0,x1,itmax=10^3,tol=10^(-8))
{
  if(f(x0)==f(x1)){stop('Wrong Initial Values')}
  
  x2 = x1 - f(x1) \ast ( ( x1  - x0 ) / ( f(x1) - f(x0) ) )
  for(i in 1:itmax)
  {
    x0 = x1
    x1 = x2
    x2 = x1 - f(x1) \ast ( ( x1  - x0 ) / ( f(x1) - f(x0) ) )
    if(abs(x2-x1)<tol) {return(x2)}
  }
  
  stop('Maybe Wrong Initial Point')
}
 
f<-function(x) {x^3 + 8}
Secant(f,-7,7)
 
g<-function(x) {x^6 - x - 1}
Secant(g,0,3)
 
h<-function(x) {exp(x)-1}
Secant(h,-2,-1)

上記のコードを実行した結果は以下の通りである。