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
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:
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
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.
