Numerical Methods

## Iterative methods

The equation $F(x)=0$ can be transformed into the form,

$$$\label{gl2} x=f(x).$$$

This can be used to seek the zeros of $F(x)$ by iteration.

$\begin{eqnarray}\label{gladd} x_{0} & & \mbox{ Starting value} \nonumber\\ x_{1} & = & f(x_{0}) \nonumber\\ x_{2} & = & f(x_{1}) \nonumber\\ & . & \nonumber\\ & . & \nonumber\\ x_{t+1} & = & f(x_{t}) \qquad (t=0,1,2,\ldots) \end{eqnarray}$

If the method converges, this iteration can lead arbitrarily close to the exact solution of the problem (within roundoff error),

$\lim_{t \to \infty} x_{t} \to x_{exact}$

There is no guarantee that this method will converge. The convergence depends strongly from the way in which $F(x)=0$ is reformulated into $x=f(x)$. One formulation is $f(x)=F(x)+x$ however other formulations can sometimes be found that converge better.

Consider the function $F(x)=x^{3}-x-5$ in the vicinity of $x=2$. Three reformulations of this equation into a form $x=f(x)$ are,

$a)\quad x=x^{3}-5 \qquad b) \quad x=\frac{5}{x^{2}-1} \qquad c) \quad x=\sqrt[3]{x+5}$

Iterating the first two forms results in a diverging series while $c)$ converges quickly to a root of $x^{3}-x-5=0$. A condition for convergence is $\left|\frac{df}{dx}\right| < 1$ at the root.

Code that iterates these equations is given below.


f(x)

x