logo

Secant Method 📂Numerical Analysis

Secant Method

Methods

20180903\_131323.png 20180903\_131333.png 20180903\_131343.png

Let f,f’,f’’f,f’,f’’ be continuous near α\alpha and suppose f(α)=0,f′(α)≠0f(\alpha) = 0, f '(\alpha) \ne 0.

For a sufficiently close initial value x0,x1x_{0} , x_{1} to α\alpha, the sequence {xn}\left\{ x_{n} \right\} defined by xn+1:=xn−f(xn)xn−xn−1f(xn)−f(xn−1) x_{n+1} := x_{n} - f ( x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }} converges to α\alpha with order 1+52\displaystyle {{1 + \sqrt{5} } \over {2}} when n→∞n \to \infty.

Explanation

The Golden Ratio

The order of convergence might seem quite familiar – it is precisely the golden ratio, 1+52=1.618⋯\displaystyle {{1 + \sqrt{5} } \over {2}} = 1.618 \cdots. During the proof involving three consecutive terms from the sequence definition, the Fibonacci sequence appears, which is an interesting phenomenon before mentioning the usefulness of the secant method. This order indicates that the secant method is faster than the bisection method, but slower than the Newton-Raphson method.

The reason for adopting this method despite the faster Newton-Raphson method is that finding the derivative can be excessively difficult at times. Moreover, when compared in terms of the amount of computation, the lower convergence order of the secant method entails more computations than the Newton-Raphson method. However, the secant method may be preferable in terms of the computation cost per operation. The choice of the method depends on the problem (though frankly, almost no method other than the Newton method is used).

Initial Value Problem

20180903\_131820.png

Similar to the Newton-Raphson method, if the initial value is incorrectly given, it may not converge if it is not sufficiently close to α\alpha.

Proof 1

  • H{a,b,c,⋯ }\mathscr{H} \left\{ a,b,c, \cdots \right\} represents the smallest interval including a,b,c,⋯a,b,c, \cdots.

Part 1. Difference Table

Let us define f[x0,x1]:=f(x1)−f(x0)x1−x0f[x0,x1,x2]:=f[x1,x2]−f[x0,x1]x2−x0 \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*} . These are called difference tables, and there exist ξ∈H{x0,x1}ζ∈H{x0,x1,x2} \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*} satisfying f’(ξ)=f[x0,x1]f ’ ( \xi ) = f [ x_{0} , x_{1} ] and 12f’’(ζ)=f[x0,x1,x2]\displaystyle {{1} \over {2}} f ’’ ( \zeta ) = f [ x_{0} , x_{1} , x_{2} ].

Part 2. α−xn+1=−(α−xn−1)(α−xn)f′′(ζn)2f’(ξn)\displaystyle \alpha - x_{n+1} = - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f ''( \zeta _{n} ) } \over { 2 f ’ ( \xi_{n} ) }}

Multiplying both sides of xn+1=xn−f(xn)xn−xn−1f(xn)−f(xn−1)x_{n+1} = x_{n} - f ( x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }} by −1-1 and adding α\alpha results in α−xn+1=α−xn+f(xn)xn−xn−1f(xn)−f(xn−1) \alpha - x_{n+1} = \alpha - x_{n} + f ( x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }} , and α−xn+1=α−xn+xnf(xn)−xn−1f(xn)f(xn)−f(xn−1)=xnf(xn)−xn−1f(xn)+αf(xn)−xnf(xn)−αf(xn−1)+xnf(xn−1)f(xn)−f(xn−1)=1f(xn)−f(xn−1)[−xn−1f(xn)+αf(xn)−αf(xn−1)+xnf(xn−1)]=1f(xn)−f(xn−1)[(α−xn−1)f(xn)−(α−xn)f(xn−1)]=−(α−xn−1)(α−xn)f(xn)−f(xn−1)[f(xn)xn−α−f(xn−1)]=−(α−xn−1)(α−xn)f(xn)−f(xn−1)[f(xn)−f(α)xn−α−f(xn−1)−f(α)xn−1−α]=−(α−xn−1)(α−xn)1f(xn)−f(xn−1)[f[xn,α]−f[xn−1,α]]=−(α−xn−1)(α−xn)xn−xn−1f(xn)−f(xn−1)[f[xn,α]−f[xn−1,α]xn−xn−1]=−(α−xn−1)(α−xn)f[xn−1,xn,α]f[xn−1,xn] \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*} . Arranging yields α−xn+1=−(α−xn−1)(α−xn)f[xn−1,xn,α]f[xn−1,xn] \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} ] }} , and by the properties of the difference table, the following is obtained: α−xn+1=−(α−xn−1)(α−xn)f′′(ζn)2f’(ξn) \alpha - x_{n+1} = - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f ''( \zeta _{n} ) } \over { 2 f ’ ( \xi_{n} ) }} .

Part 3. Convergence

Consider a sufficiently small I:=[α−δ,α+δ]I : = [ \alpha - \delta , \alpha + \delta ] in the vicinity of α\alpha that satisfies all given assumptions.

Defining M:=max⁡x∈I∣f′′(x)∣2min⁡x∈I∣f′(x)∣ M := {{ \max_{x \in I } | f '' (x) | } \over { 2 \min_{x \in I} | f '(x) | }} as follows, based on the results from Part 1, ∣α−xn+1∣≤∣α−xn∣∣α−xn−1∣M | \alpha - x_{n+1}| \le | \alpha - x_{n} | | \alpha - x_{n-1} | M Multiplying both sides by MM results in ∣α−xn+1∣M≤(∣α−xn∣M)⋅(∣α−xn−1∣M) | \alpha - x_{n+1}| M \le ( | \alpha - x_{n} | M ) \cdot ( | \alpha - x_{n-1} | M ) Assuming a sufficiently small II, setting ε:=max⁡{(∣α−xn∣M),(∣α−xn−1∣M)}<1 \varepsilon := \max \left\{ ( | \alpha - x_{n} | M ) , ( | \alpha - x_{n-1} | M ) \right\} < 1 yields ∣α−xn+1∣M≤ε2 | \alpha - x_{n+1}| M \le \varepsilon^2 ∣α−xn+3∣M≤(∣α−xn+2∣M)⋅(∣α−xn+1∣M)≤ε2⋅ε=ε3 | \alpha - x_{n+3}| M \le ( | \alpha - x_{n+2}| M ) \cdot ( | \alpha - x_{n+1}| M ) \le \varepsilon^2 \cdot \varepsilon = \varepsilon^3 ∣α−xn+4∣M≤(∣α−xn+3∣M)⋅(∣α−xn+2∣M)≤ε3⋅ε2=ε5 | \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 and in this manner, the inequality ∣α−xn+m+1∣M≤(∣α−xn+m∣M)⋅(∣α−xn+m−1∣M)≤εqm⋅εqm−1=εqm+1 | \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} } is obtained.

The General Term of the Fibonacci Sequence: Let’s say a sequence {Fn}\left\{ F_{n} \right\} is defined as Fn+1:=Fn+Fn−1F_{n+1} := F_{n} + F_{n-1}. If F0=F1=1F_{0} = F_{1} = 1 then for r0:=1+52\displaystyle r_{0} : = {{1 + \sqrt{5} } \over {2}} and r1:=1−52\displaystyle r_{1} : = {{1 - \sqrt{5} } \over {2}}, Fn=r0n+1−r1n+1r0−r1\displaystyle F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }} .

{qm}\left\{ q_{m} \right\} is none other than the Fibonacci sequence, for a sufficiently large mm, qm∼15(1.618)m+1 q_{m} \sim {{1} \over {\sqrt{5}}} ( 1.618 )^{m+1} Thus, ∣α−xn+m∣≤1Mεqm | \alpha - x_{n+m}| \le {{1} \over {M}} \varepsilon^{ q_{m} } and when n→∞n \to \infty, xn→αx_{n} \to \alpha, not only that but it can be seen that it converges with order 1+52∼1.618 {{1 + \sqrt{5} } \over {2}} \sim 1.618 .

■

Implementation

Below is code written in R.

The itmax option is the maximum number of iterations, which defaults to giving up on the calculation if a precision solution is not found even after 10001000 iterations.

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)

The result of executing the above code is as follows.

20180903\_125940.png

  1. Atkinson. (1989). An Introduction to Numerical Analysis(2nd Edition): p68~69. ↩︎