9.5.2 Interpolation  9.5 Roots of equations  9.5 Roots of equations

9.5.1 Newton's method

The first-order Taylor expansion of the equation f(x)=0 is

f(x₀)+(x-x₀)f'(x₀) = 0  (9.38)

 

An estimate of the root, x^*, can be found from values of the function and its derivative:

$$\hat x^*=x_0-{{f(x_0)}\over{f'(x_0)}}$$ (9.39)

 

The formula can then be used iteratively to obtain improving estimates of the root:

$$\hat x^*_{n+1} = \hat x^*_n - {{f(\hat x^*_n)}\over{f'(\hatx_n^*)}}$$ (9.40)

 

Figure 9.1 illustrates the basis for the method. Numerical versions of Newton's method are very convenient and simple to use. These usually use finite-difference formulas to evaluate the derivative.

 

Figure 9.1:  A step in Newton's method. From an estimate x_n^* of the root of the equation y=f(x)=0, construct an improved estimate of the root x_n+1^*by finding the intersection of the line y=0 and the line through the point (x, f(x)) with slope $f^\prime(x_{n}^*)$.

 

Sometimes it is better to find roots of the function f(x)/f'(x). This function will have roots at the same locations as f(x), as long as the first derivative is finite, but the convergence will be faster for the case of multiple roots. To illustrate the problem, consider the equation

f(x)=(x-5)³=0  (9.41)

 

When Newton's method is used, convergence is very slow because the first derivative (which is in the denominator of Eq. (9.5.1)) approaches zero at the root. Starting at 10, the series is: 10, 8.333, 7.222, 6.481, 5.988, 5.658, 5.439, 5.292, 5.195, 5.130, ..., and after 20 terms is 5.002. If instead f(x)/f'(x) is used in (9.44), the series reaches the correct answer exactly in one step.

As an example, consider the function (1) that describes the drop semi-major axis. A plot of this relationship, for a=0.3, is shown in Fig. 9.2.  The function is monotonic in the interval chosen, and well suited to solution by Newton's method. If the starting value is a₀=0.3, Newton's method leads to a value of a₀=0.26563 after 7 steps, and the steps change by less than 0.00001 after that step.

 

Figure 9.2:  Plot of Green's (1975) equation, (1), characterizing the drop semi-major axis a₀ in terms of the volume-equivalent radius a, for a=0.3 cm. The solution to the equation corresponds to a₀=0.2656, as shown.

The disadvantages of Newton's method are that high-order roots can cause convergence to be slow, and the sequence may take undesirable jumps between roots or take a very large step upon encountering an inflection point.

   
 9.5.2 Interpolation  9.5 Roots of equations  9.5 Roots of equations