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

From Table 1.1, it is clear that the Newton–Raphson algorithm converges much faster than the bisection method. In numerical mathematics it is crucial to have a reliable measure of how fast (or slow) a method converges to the desired solution. Some readers may think that we are taking an alarming position since the bisection and Newton Matlab codes provide the solution almost instantaneously, the difference in speed between both methods in terms of computational time being unnoticeable. However, we will see in Part II that the efficiency of the method becomes much more relevant when solving systems of nonlinear equations.

A rigorous way of measuring quantitatively the performance of an iterative method is given by the concept of order of convergence:

Order of Convergence: A root‐finding method providing a sequence with has order of convergence if

(1.11)

for some positive bounded constant , usually termed as the asymptotic error constant. In particular, if , then must be smaller than unity for the criterion to be applicable.

If (and accordingly ) then the sequence is said to converge linearly. If , it is said that the sequence converges superlinearly. In particular, for and , the sequence is said to have quadratic or cubic convergence, respectively. However, the value of of a given sequence does not need to be an integer and in general will depend not only on the method used but also on the particular root sought, as we will see later. This implies that in practical situations, we will have to rely on the actual numerical sequence in order to estimate . Notice that the limit (1.11) can be rewritten in terms of the absolute errors:

(1.12)

which means that for large enough ,

(1.13)

Expression (1.13) is less formal but certainly provides more insight. For example, in the linear case (1.13) implies that , since for . In other words, the sequence must be monotonically decreasing in order to have linear convergence. According to Table 1.1, , and therefore the bisection method does not qualify to have linear convergence in the sense of (1.11)¹⁰

We can numerically estimate the actual order of convergence by taking the logarithm of both sides of (1.13) and setting the quantities , , and , so that the expression now reads

(1.14)

According to (1.14), the set of points should follow a linear law with slope . However, expression (1.13) must be conceived just as a local law, i.e. sufficiently close to the converged root. Typically, unless the iteration is started really close to the root, the first iterates of the sequence must be discarded from the analysis. On the other hand, since , the quotient appearing in (1.12) is affected by numerical cancelation and therefore the last few iterates must also be ruled out from the numerical evaluations.

Figure 1.2a shows the convergence of Newton's method based on the actual sequence obtained in Table 1.1 for the solution of , where the points seem to align parallel to a straight line of slope (dashed gray line), as an indication of quadratic convergence in this particular case. Sometimes, the slope of the numerical data can be clearly identified by simple eye inspection (particularly for or ), although linear regression may also be used if data are more scattered or if the value of is not an easily identifiable integer.

Figure 1.2 (a) Analysis of the order of convergence of the Newton's method: the points seem to align with a straight line of slope (dashed line). (b) Same analysis for chord (gray squares) and secant methods (gray circles), showing linear and golden ratio orders, respectively.

We can rigorously prove the quadratic convergence of Newton's method by evaluating the limit (1.11) for

(1.15)

Before calculating the limit above, first notice that Newton's iteration can be expressed in terms of the errors . Since we may write

and therefore

Since when , we may define as a continuous variable that approaches zero so that we can rewrite the previous limit as

where we have used L'Hôpital's rule to solve the indeterminate form . Therefore we conclude that Newton's method has quadratic convergence with asymptotic error constant

(1.16)