セカント法

メソッド

$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$ であり、数列の定義から3つの連続した項を使用して証明中にフィボナッチ数列が出現する。セカントメソッドの有用性を言及する前にかなり興味深い現象である。この次数は、セカント法がバイセクションメソッドよりも早いが、ニュートン・ラフソン法よりは遅いことを意味する。

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

初期値問題

ニュートン・ラフソン法と同様に、初期値が間違って与えられた場合、十分に $\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)

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