Nonlinear equations: the problem and iterative methods

The problem

Many problems in science and engineering end in a nonlinear equation: finding a simple root $\alpha$ of

There are three routes. The analytic one only works for specific families of equations. The graphical one (plot $f$ and look where it crosses the axis) locates the root but gives no precision: for $f(x)=\cos^2 x-x$ one sees the root is near $0.65$, and nothing more. The third route is iterative methods, which from one or several initial estimates generate a sequence $\{x_0,x_1,x_2,\dots\}$ converging to $\alpha$ to any desired accuracy.

Most memoryless methods are written as a fixed-point iteration $x_{k+1}=\phi(x_k)$. The central example is the Newton-Raphson method, with $\phi(x)=x-\frac{f(x)}{f'(x)}$.

Classification of iterative methods

• Without memory / with memory: the former use only the current iterate, $x_{k+1}=\phi(x_k)$; the latter also use previous iterates, $x_{k+1}=\phi(x_k,x_{k-1},\dots,x_{k-m})$, and need several initial estimates. The secant is the classic method with memory.
• One-point / multipoint: multipoint methods evaluate the function at intermediate points within the same iteration (predictor-corrector structure), like Traub's method or the high-order methods.
• With derivatives / derivative-free: when $f'$ is unknown or expensive, it is replaced by divided differences, as the secant and Steffensen methods do.

Stopping criteria and tolerance

An iterative method needs to know when to stop. The usual conditions, alone or combined, are:

• The last two iterates are very close: $|x_{k+1}-x_k|<\varepsilon$.
• The residual is very small: $|f(x_{k+1})|<\varepsilon$.
• A maximum number of iterations has been reached without converging (protects against infinite loops when the method diverges).

The value $\varepsilon$ is the tolerance. With double-precision arithmetic it makes no sense to request tolerances below machine precision; convergence studies with extreme tolerances (like $10^{-100}$ in the comparison exercise) use extended-precision arithmetic.