# Rootfinding for nonlinear equations

Rootfinding for nonlinear equations

Here we want to solve an equation of the kind ${\displaystyle f(x)=0}$.

Suppose that there exist ${\displaystyle \alpha \in \mathbb {R} }$ such that ${\displaystyle f(\alpha )=0}$. Then we want to construct a sequence ${\displaystyle x_{k}}$, with ${\displaystyle k\in \mathbb {N} }$, such that

${\displaystyle \lim _{k\to \infty }x_{k}=\alpha }$

The number ${\displaystyle \alpha }$ is called root (of the function ${\displaystyle f}$).

## Convergence

If the sequence defined by the numerical method converges, we can ask what the rate of convergence is. With this aim, we define the order of convergence of a sequence :

Definition (Order of convergence). A sequence ${\displaystyle x_{k}}$ converges to ${\displaystyle \alpha }$ with order ${\displaystyle p\geq 1}$ if

${\displaystyle |x_{k+1}-\alpha |=C|x_{k}-\alpha |^{p},\quad \forall k>0,}$

${\displaystyle p}$ is the order of convergence of the numerical method that has generated the sequence ${\displaystyle x_{k}}$. The constant ${\displaystyle C}$ is called rate of convergence. If ${\displaystyle p=1}$ and ${\displaystyle C}$ is between 0 and 1, the convergence is said to be linear convergence.Under the linear convergence condition,if ${\displaystyle C=0}$, the sequence is said to converge superlinearly and if ${\displaystyle C=1}$, then the sequence is said to converge sublinearly.

The quantity

${\displaystyle e_{k+1}\equiv |x_{k+1}-\alpha |}$

represents the error at step ${\displaystyle k}$. In general, with a numerical method, we do a finite number of iterations and for this reason we seek only an approximation ${\displaystyle x_{k+1}}$ of the true root ${\displaystyle \alpha }$. In particular, we can define a tolerance ${\displaystyle \epsilon }$ such that if ${\displaystyle |x_{k+1}-\alpha |\leq \epsilon }$,we can stop the iteration and conclude that ${\displaystyle x_{k+1}}$ is the approximation of the true root.

### Example

Suppose that the sequence ${\displaystyle x_{k}}$ converges to ${\displaystyle \alpha }$ with order 2, where the constant ${\displaystyle C=1}$, and suppose that the initial error ${\displaystyle e_{0}=|x_{0}-\alpha |=10^{-1}}$. Consider a tolerance ${\displaystyle \epsilon =10^{-10}}$, then we can find the approximation of the true root by using the definition of convergence.Hence,

${\displaystyle e_{1}=|x_{1}-\alpha |=|x_{0}-\alpha |^{2}=10^{-2}}$

which is greater than the tolerance, so we should keep going until the error is less than the tolerance. We can get

${\displaystyle e_{2}=|x_{2}-\alpha |=|x_{1}-\alpha |^{2}=10^{-4}}$

which is also greater than the tolerance, thus we should do the iteration to calculate

${\displaystyle e_{3}=|x_{3}-\alpha |=|x_{2}-\alpha |^{2}=10^{-8}}$

which is still larger than the tolerance. Similarly,

${\displaystyle e_{4}=|x_{4}-\alpha |=|x_{3}-\alpha |^{2}=10^{-16}}$

which is less than the tolerance. Therefore, we can stop here and can conclude that ${\displaystyle x_{4}}$ is the approximation of the true root.

YangOu (talk) 02:44, 26 October 2012 (UTC)