4.3. Root finding methods#
4.3.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:
until \(x_{n+1} = x_n\) to the desired precision (error tolerance).
Example: Using fixed point iteration
To solve
First rearrange
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
One possible rearrangement is
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:
where \(\alpha\) is a mixing parameter. Smaller values of \(\alpha\) mix more slowly, which can be more stable but also requires more iterations.
4.3.2. Bisection search#
We can apply this concept to find roots using the following procedure, called bisection search:
Chose \(a_0\) and \(b_0\) so \(f(a)\) and \(f(b)\) have opposite signs.
Starting at \(n = 0\), evaluate \(f(x_n)\) at the midpoint \(x_n = (a_n + b_n)/2\).
If \(f(x_n) \approx 0\) a solution is found within desired precision. Otherwise, if \(f(a_n)\) and \(f(x_n)\) have the same sign, \(a_{n+1} = x_n\); else, \(b_{n+1} = x_n\)
Increase \(n\) and repeat from step 2.
Example: Using bisection search
To solve
Start with \(a_0 = 0\) and \(b_0 = 1\), then make a table to implement the procedure:
\(n\) |
\(a_n\) |
\(b_n\) |
\(x_n\) |
\(f(a_n)\) |
\(f(b_n)\) |
\(f(x_n)\) |
---|---|---|---|---|---|---|
0 |
0 |
1 |
0.5 |
1.0 |
-0.632 |
0.279 |
1 |
0.5 |
1 |
0.75 |
0.275 |
-0.632 |
-0.180 |
2 |
0.5 |
0.75 |
0.625 |
0.275 |
-0.1180 |
0.052 |
… |
… |
… |
… |
… |
… |
… |
9 |
0.625 |
0.654 |
0.653 |
0.001 |
-0.002 |
-0.0007 |
When \(n=0\), \(f(x_0)\) > 0 so \(a_1\) = \(x_0\). Then, when \(n=1\), \(f(x_1)\) < 0 so \(b_2\) = \(x_1\). We continue this procedure until convergence.
4.3.3. Newton-Raphson method#
Although we cannot immediately solve the nonlinear equation \(f(x) = 0\), we can first linearize it, then solve the linear problem.
Iterating this process gives the Newton-Raphson method of root finding
The algorithm for the Newton-Raphson method is:
Guess \(x_0\) and set \(n = 0\).
Compute \(f(x_n)\) and \(f'(x_n)\). If \(f(x_n)\) is “close” to zero, stop.
Update \(x_{n+1}\) using eq. (4.22) then return to step 2.
Note that this method can converge much more rapidly than the fixed-point or bisection methods. However, it will fail if \(f'(x_n) = 0\).
Example: Newton-Raphson method
Solve \(x^2 = 2\).
We can rewrite this as \(f(x) = x^2-2 = 0\). We will also evaluate the derivative \(f'(x) = 2x\). Let the initial guess be \(x_0 = 1\).
\(n\) |
\(x_n\) |
\(f(x_n)\) |
\(f'(x_n)\) |
---|---|---|---|
0 |
1.0 |
-1.0 |
2.0 |
1 |
1.5 |
0.25 |
3.0 |
2 |
1.417 |
\(6.94 \times 10^{-3}\) |
2.833 |
3 |
1.414 |
This is close to the known value of \(\sqrt{2}\)!
Example: Newton-Raphson method 2
Solve \(e^{-x^2} - x = 0\).
We define \(f(x) = e^{-x^2} - x\) and calculate \(f'(x) = -2x e^{-x^2} - 1\). We choose an initial guess \(x_0 = 0\).
\(n\) |
\(x_n\) |
\(f(x_n)\) |
\(f'(x_n)\) |
---|---|---|---|
0 |
0 |
1.0 |
-1.0 |
1 |
1.0 |
-0.6321 |
-1.736 |
2 |
0.6358 |
0.03164 |
-1.849 |
3 |
0.6529 |
Note the rapid convergence compared to the methods above!
4.3.4. Skill builder problems#
Solve all roots of
to 3 significant figures by:
Fixed-point iteration starting from \(x_0 = 0.5\).
Solution
Rearrange as
(4.24)#\[\begin{equation} x = \cos(x) = g(x) \end{equation}\]\(n\)
\(x_n\)
0
0.500
1
0.878
2
0.639
3
0.803
4
0.695
5
0.768
6
0.719
7
0.752
8
0.730
9
0.745
10
0.735
11
0.742
12
0.737
13
0.740
14
0.738
15
0.740
16
0.739
17
0.739
Hence, \(x \approx 0.739\).
Bisection search in \(0 \le x \le 1\).
Solution
\(n\)
\(a_n\)
\(b_n\)
\(x_n\)
\(f(a_n)\)
\(f(b_n)\)
\(f(x_n)\)
0
0
1.00
0.500
1.00
-0.460
0.378
1
0.500
1
0.750
0.378
-0.460
-0.0183
2
0.500
0.750
0.625
0.378
-0.0183
0.186
3
0.625
0.750
0.688
0.186
-0.0183
0.0853
4
0.688
0.750
0.719
0.0853
-0.0183
0.0339
5
0.719
0.750
0.734
0.0839
-0.0183
0.0079
6
0.734
0.750
0. 742
0.0079
-0.0183
-0.0052
7
0.734
0.742
0.738
0.0079
-0.0052
0.0013
8
0.738
0.742
0.740
0.0013
-0.0052
-0.0019
9
0.738
0.740
0.739
0.0013
-0.0019
-0.0003
10
0.738
0.739
0.739
0.0013
-0.0003
0.0005
Hence, \(x \approx 0.739\).
Newton-Raphson method, starting from \(x_0 = \pi/2\).
Solution
For
(4.25)#\[\begin{align} f(x) &= \cos x - x \\ f'(x) &= -\sin x - 1 \end{align}\]The Newton-Raphson update is:
(4.26)#\[\begin{equation} x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \end{equation}\]\(n\)
\(x_n\)
\(f(x_n)\)
\(f'(x_n)\)
0
1.571
-1.571
-2.0
1
0.7854
\(-7.829 \times 10^{-2}\)
-1.7071
2
0.7395
\(-7.549 \times 10^{-4}\)
-1.674
3
0.7391
\(-7.513 \times 10^{-8}\)
-1.674
4
0.7391
Hence, $x \approx 0.739.