Root finding methods

4.2. Root finding methods#

4.2.1. Fixed point iteration#

If we want to numerically solve \(f(x) = 0\), rearrange \(f(x)\) to get \(g(x) = x\). Then, choose an inital guess \(x_0\) and iterate:

(4.1)#\[\begin{equation} x_{n+1} = g(x_n) \end{equation}\]

until \(x_{n+1} = x_n\) to the desired precision (error tolerance).

Example: Using fixed point iteration

To solve

(4.2)#\[\begin{equation} e^{-x^2} - x = 0 \end{equation}\]

First rearrange

(4.3)#\[\begin{align} x = e^{-x^2} = g(x) \end{align}\]

Then, guess \(x_0 = 0\) and set up a table:

\(n\)

\(x_n\)

\(g(x_n)\)

0

0

1.000

1

1.000

0.368

2

0.368

0.873

…

…

…

51

0.653

0.6528

At each iteration, \(g(x_n)\) is used as the new \(x_n\) until at \(n = 5\), where \(x_n = 0.6530 \approx 0.6528 = g(x_n)\).

The choice of rearranging \(f(x)\) is not unique, and some choices may be better than others. For example, convergence is only guaranteed when \(|g'(x)| \le k < 1\) for all \(x\) in an interval around the solution. Experience will guide your choice of rearrangement.

Example: Rearranging functions

To solve

(4.4)#\[\begin{equation} e^x - x^3 = 0 \end{equation}\]

One possible rearrangement is

(4.5)#\[\begin{align} e^x &= x^3 \\ x &= \ln(x^3) = 3 \ln x = g(x) \end{align}\]

Note that this method may fail spectacularly! In that case, choosing a better initial guess or rearrangement may help. Additionally, you can try to improve the stability of the method by slowly “mixing” solutions:

(4.6)#\[\begin{align} x_{n+1}^* &= g(x_n) \\ x_{n+1} &= \alpha x_{n+1}^* + (1-\alpha) x_n \end{align}\]

where \(\alpha\) is a mixing parameter. Smaller values of \(\alpha\) mix more slowly, which can be more stable but also requires more iterations.

Contents