Alvaro Meseguer - Fundamentals of Numerical Mathematics for Physicists and Engineers

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) 10

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.1for 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.