Secant Method

3 Key excerpts on "Secant Method"

• 

  eBook - ePub

  Numerical Analysis

  An Introduction

  • Timo Heister, Leo G. Rebholz, Fei Xue(Authors)
  • 2019(Publication Date)
  • De Gruyter

    (Publisher)

  −1 . This defines the following algorithm:

  Algorithm 46 (Secant Method).

  Given: f , tol, x 0 , x 1

  while( |

  xk

  +1 −

  xk

  | > tol):

  x

  k + 1

  =

  x k

  −

  f

  (

  x k

  )

  f

  (

  x k

  )

  − f

  (

  x

  k − 1

  )

  x k

  −

  x

  k − 1

  .

  Hence we may think of the Secant Method as Newton’s method, but with the derivative term f '(

  xk

  ) replaced by the backward difference

  f

  (

  x k

  )

  − f

  (

  x

  k − 1

  )

  x k

  −

  x

  k − 1

  .

  It is tedious (but not hard) to prove that the Secant Method converges superlinearly, with rate

  p =

  1 +

  5

  2

  ≈ 1.618.

  5.6Comparing bisection, Newton, Secant Method

  We now compare the bisection, Newton, and Secant Methods in the following table.

  (1 )

  The Secant Method can be extended to higher dimensions, but the approximation of the derivative requires more work. There are several similar methods known as “Quasi-Newton” or “Jacobian-free Newton” methods.

  (2 )

  The user needs to supply the derivative to the algorithm, which can be problematic, for example, if it is difficult to compute by hand or not accessible.

  (3 )

  To achieve the given convergence rate there are more technical requirements on f

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Fundamentals of Numerical Mathematics for Physicists and Engineers

  • Alvaro Meseguer(Author)
  • 2020(Publication Date)
  • Wiley

    (Publisher)

  The ordinates corresponding to the Secant Method (triangles) have been shifted downwards three units to avoid overlap between the two sets of data and help visualize. (b) Newton's method iterates for the solution of. Figure 1.4 a shows the result of applying Newton's and Secant Methods to find the double ill‐conditioned root of the equation studied in Section 1.6. Newton's iteration is started from, whereas the secant has been initialized from the interval that contains the root. The reader may check that in this case Newton's and Secant Methods lose their quadratic and golden ratio orders, respectively, both exhibiting linear convergence, as shown in Figure 1.4 a. Double or ill‐conditioned roots appear in physics more frequently than one may expect, particularly in problems where the transcendental equation to be solved is the result of imposing some kind of critical or threshold condition (we refer the reader to Practical 1.2, for example). In general, root‐finding methods converge to the desired solution only if the initial guess is really close to the sought root, i.e. most of the methods are just locally convergent. In practice, a root‐finding algorithm starting from an initial guess moderately far away from the root could easily lead to a sequence that may wander from one point to another of the real axis, eventually diverging to infinity or converging to a solution (not necessarily the sought one). Figure 1.4 b illustrates this phenomenon by showing the result of computing the roots of the function using Newton's method starting from different initial guesses. The first two roots of are located at and (black bullets in Figure 1.4 b). In this example, we initialize Newton's method from two initial guesses reasonably close (but not too close) to. To guide the eye, we have indicated the history of each of the two sequences by encircled numbering of their ordinates

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Introduction to Numerical Analysis and Scientific Computing

  • Nabil Nassif, Dolly Khuwayri Fayyad(Authors)
  • 2016(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  st was needed to meet the termination condition.
• Let f (x ) = x 4 − x 3 − x − 1. Search for the root of f in the interval [0, 3] with ϵ = 0.5 × 10 − 4 (5 significant figures rounded). The results of the bisection iterates are given in Table 2.3 .
Table 2.4 illustrates the convergence of the sequence of intervals {(
an
,
bn
)|n = 1, 2, 10}, generated by the bisection method for the function
f ( x ) = ln ( 1 + x ) −
1
1 + x
, as proved in Theorem 2.1. Computations are carried out up to 3 significant figures. To conclude, the bisection is a multistep method that, although conceptually clear and simple, has significant drawbacks since, as theory and practice indicate, it is a slowly convergent method. However it globally converges to the searched solution and can be used as a starter to more efficient locally convergent methods, notably both the Newton’s and Secant Methods.

2.4 Newton’s Method

Newton’s (or Newton-Raphson’s ) method is one of the most powerful numerical methods for solving non-linear equations. It is also referred to as the tangent method , as it consists in constructing a sequence of numbers {

rn

|

rn

∈ (a , b )∀n ≥ 1}, obtained by intersecting tangents to the curve y = f (x ) at the sequence of points {(r

n − 1

, f (r

n − 1

))|n ≥ 1} with the x-Axis. Constructing such tangents and such sequences requires additional assumptions to 2.2 − 2.5 as derived hereafter.

To start, let r 0 ∈ (a , b ) in which the root is located, and let M 0 = (r 0 , f (r 0 )) be the point on the curve

{ ( C ) | y = f ( x ) , a ≤ x ≤ b } .

Let also (𝒯0 ) be the tangent to (𝒞) at M 0 with equation given by:

y =

f '

(

r 0

) ( x −

r 0

) + f (

r 0

)

The intersection of (𝒯0 ) with the x-Axis is obtained for y = 0 and is given by:

r 1

=

r 0

−

f (

r 0

)

f ’ (

r 0

)

(2.19)

To insure that r

1 ∈ (

a , b ) , r 0 should be chosen “close enough” to r . Specifically, since f (r ) = 0, 2.19