Alvaro Meseguer - Fundamentals of Numerical Mathematics for Physicists and Engineers

Convergence (Practical): A sequence is said to be converged to the desired tolerance after iterations if , .

The criterion above only refers to the convergence of a sequence, and not necessarily to the convergence to a root. After an iterative method has apparently converged to some stagnated value , it is always advisable to check the magnitude of in order to confirm if the method has succeeded. The code below is a simple implementation of the bisection method using the tolerance criterion previously described:

% Code 1: Bisection method for solving f(x) = 0 in [a,b] % Input: 1. [a,b]: interval (it assumes that f(a)f(b) < 0) % 2. tol: tolerance so that abs(x_k+1 - x_k) < tol % 3. itmax: maximum number of iterations allowed % 4. fun: function's name % Output: 1. xk: resulting sequence % 2. res: resulting residuals % 3. it: number of required iterations function [xk,res,it] = bisection(a,b,tol,itmax,fun) ak = a; bk = b; xk = []; res = []; it = 0; tolk = abs(bk-ak)/2 ; while it < itmax & tolk > tol ck = (ak + bk)/2; xk = [xk ck]; if it > 0; tolk = abs(xk(end)-xk(end-1)); end fa = feval(fun,ak); fc = feval(fun,ck); res = [res abs(fc)]; if fc*fa < 0; bk = ck; else ak = ck; end it = it + 1 ; end

In the previous code, the iterations stop either when the number of iterations reaches itmaxor when tol, i.e. the condition for practical convergence. This condition therefore provides what is usually known as a stopping criterion for root‐finding methods such as the bisection and other algorithms. However, two words of caution deserve to be mentioned at this point. First, we are implicitly assuming that since seems to be a Cauchy Sequence 6 (that is, decreases with increasing ), its convergence is guaranteed. While a convergent sequence must necessarily be of Cauchy type, the reverse statement is, in general, not true (although here it will be assumed to be). Second, the quantity has disappeared from the convergence criteria. In other words, once for some and beyond, we only know that the sequence has converged (in the practical sense) to some value , that henceforth will play the role of the numerical root within the prescribed tolerance.

Finally, the bisection code also provides the vector rescontaining the sequence of absolute quantities , usually called the residuals . Since this quantity should approach zero when converges to a root, the reader may wonder why should not be used as a measure for stopping the iterations. The reason is that the residual is not always a reliable measure (although it is often used in practice to decide convergence). We will address this question later in this chapter, when we introduce the concept of condition number of a root .

Newton's method , also known as Newton–Raphson method , 7 is probably the most important root‐finding algorithm of numerical mathematics. Its formulation naturally leads to a wide variety of other root‐finding algorithms and is easily adaptable to solving systems of nonlinear equations. 8 To formulate this method we will assume that is differentiable and that the root is close to some initial guess . To get a better estimation of the root we assume that, close to , the function can be approximated by its tangent line at the point plotted in gray below. In other words, we locally approximate by its first order Taylor expansion at :

(1.6)