Читать книгу Fundamentals of Numerical Mathematics for Physicists and Engineers - Alvaro Meseguer - Страница 18

One of the drawbacks of Newton's method is that we must supply the derivative of the function at every iteration. As mentioned before, the derivative can be approximated using (1.10) so there is no need for providing a supplementary function for the evaluation . Either in the exact or approximate version of Newton's method, we need two function evaluations per iteration. There are situations where two or more evaluations per iteration may be computationally expensive, such as in the case of extending Newton's method to solve systems of nonlinear equations, as we will address in Part II. Now, let us assume that we have to provide a Newton‐like iteration without explicitly appealing to the derivative of and with just one evaluation of per iteration.

Assume that we have identified an interval such that . The key point is to provide an estimation of the slope of the function at the th iterate and substitute Newton's iteration by

(1.17)

Provided that does not oscillate very much within , a reasonable estimation of is the slope provided by the mean value theorem. In this case, the expression (1.17) leads to what is usually termed as the chord method:

Chord Iteration:

(1.18)

The chord method can be improved by updating at every iteration with a new quantity obtained from the values of the th iterates and their images obtained at the previous stages and :

(1.19)

so that (1.17) now leads to the secant method:

Secant Iteration:

(1.20)

It is common practice to start the indexing at by taking the initial values and , so that the first iterate is the same as the one obtained with the chord method. It should be clear that both chord and secant methods involve just the new evaluation per iteration, the remaining terms being previously computed (and stored) in the past.

Starting from Newton's code as a reference, the reader may easily program chord and secant algorithms and compare their efficiency with Newton's method when solving the test cubic equation starting from the same initial interval , as was done with Newton's and bisection methods. Figure 1.2b shows the resulting convergence history of the two methods. From the two sets of data of Figure 1.2b we may conclude that while the chord method seems to converge linearly, the secant methods converges superlinearly with an approximate order . It can be formally proved that the exact convergence order of the chord method is , whereas for the secant method the order is the golden ratio (see exercises at the end of the chapter).