Solution of Algebraic and Transcendental Equations
Bisection method
If \(f(x)\) is continuous on \([a,b]\) and \(f(a)\), \(f(b)\) have opposite signs, at least one root lies between \(a\)
and \(b\). Let \(f(a)<0<f(b)\) and take the first approximation \(x_0=\frac{a+b}{2}\).
If \(f(x_0)=0\), \(x_0\) is a root. Otherwise the root lies in \((x_0,b)\) or \((a,x_0)\) according as \(f(x_0)\) is
negative or positive. Call this interval \([a_1,b_1]\); its length is \(\abs{b-a}/2\). Bisect it at \(x_1\) and
repeat until the interval containing the root is as small as desired, say \(\varepsilon\). After \(n\) steps the
interval \([a_n,b_n]\) has length \(\abs{b-a}/2^n\), so we need
\[
\frac{\abs{b-a}}{2^n}\le\varepsilon,
\]
i.e.
\[
n\ge\frac{\log_\ee(\abs{b-a}/\varepsilon)}{\log_\ee2}.
\]
This is the number of iterations needed for accuracy \(\varepsilon\). For example, \(\abs{b-a}=1\) and
\(\varepsilon=0.001\) give \(n\ge10\).
The computational steps are:
Choose two real numbers \(a\) and \(b\) such that \(f(a)f(b)<0\).
Set \(x_r=(a+b)/2\).
enumerate[(a)]
If \(f(a)f(x_r)<0\), the root lies in the interval \((a,x_r)\). Then set \(b=x_r\) and go to step 2 above.
If \(f(a)f(x_r)>0\), the root lies in the interval \((x_r,b)\). Then set \(a=x_r\) and go to step 2.
If \(f(a)f(x_r)=0\), then \(x_r\) is a root of the equation \(f(x)=0\) and the computation may be terminated.
enumerate
In practice condition (c) is never met exactly, so a stopping criterion is needed. A convenient one is the
percentage error
\[
\varepsilon_r=\abs{\frac{x_r'-x_r}{x_r'}}\times100\%,
\]
where \(x_r'\) is the new value of \(x_r\). Stop when \(\varepsilon_r\) falls below a prescribed tolerance
\(\varepsilon_p\), or after a preset maximum number of iterations.
Example 10.1 Find a real root of the equation \(f(x)=x^3-x-1=0\).
Solution. Since \(f(1)<0\) and \(f(2)>0\), a root lies in \((1,2)\); take \(x_0=3/2\). Then
\(f(x_0)=\frac{27}8-\frac32-1=\frac78>0\), so the root lies in \((1,1.5)\) and
\[
x_1=\frac{1+1.5}2=1.25.
\]
Now \(f(x_1)=-19/64<0\), so the root lies in \((1.25,1.5)\) and
\[
x_2=\frac{1.25+1.5}2=1.375.
\]
Repeating, the successive approximations are
\[
x_3=1.3125,\qquad x_4=1.34375,\qquad x_5=1.328125,\ \text{etc.}
\]
Example 10.2 Find a real root of the equation \(x^3-2x-5=0\).
Solution. Let \(f(x)=x^3-2x-5\). Since \(f(2)=-1\) and \(f(3)=16\), a root lies in \((2,3)\); take
\[
x_1=\frac{2+3}2=2.5.
\]
Since \(f(2.5)=5.6250>0\), the root lies in \((2,2.5)\):
\[
x_2=\frac{2+2.5}2=2.25.
\]
\(f(2.25)=1.890625>0\), so the root lies in \((2,2.25)\):
\[
x_3=\frac{2+2.25}2=2.125.
\]
\(f(2.125)=0.3457>0\), so the root lies in \((2,2.125)\):
\[
x_4=\frac{2+2.125}2=2.0625.
\]
Continuing,
\begin{gather*}
x_5=2.09375,\quad x_6=2.10938,\quad x_7=2.10156,\quad x_8=2.09766,\\
x_9=2.09570,\quad x_{10}=2.09473,\quad x_{11}=2.09424,\ \dots
\end{gather*}
We find \(x_{11}-x_{10}=-0.0005\) and
\[
\abs{\frac{x_{11}-x_{10}}{x_{11}}}\times100=\frac{0.0005}{2.09424}\times100=0.02\%.
\]
Hence a root is \(x\simeq2.094\)–\(2.095\); continuing the bisection (or using the Newton–Raphson method below)
gives \(x=2.09455\), i.e. \(2.095\) correct to three decimal places.
Iteration method
To find a root of \(f(x)=0\), rewrite the equation as
\[
x=\phi(x).
\]
If \(x_0\) is an approximate root, the first approximation is
\[
x_1=\phi(x_0).
\]
Successive substitutions give the approximations
\[
x_2=\phi(x_1),\quad x_3=\phi(x_2),\ \dots,\quad x_n=\phi(x_{n-1}).
\]
The sequence need not converge, but if it converges to \(\xi\), then \(\xi\) is a root of \(x=\phi(x)\). Indeed, let
\[
x_{n+1}=\phi(x_n)
\]
As \(n\to\infty\), \(x_{n+1}\to\xi\) and, for continuous \(\phi\), \(\phi(x_n)\to\phi(\xi)\); hence \(\xi=\phi(\xi)\).
Convergence. Since \(x_1=\phi(x_0)\), the mean-value theorem gives
\[
\xi-x_1=\phi(\xi)-\phi(x_0)=(\xi-x_0)\,\phi'(\xi_0),\qquad x_0<\xi_0<\xi.
\]
Similarly, we obtain
\begin{align*}
\xi-x_2&=(\xi-x_1)\,\phi'(\xi_1), & x_1&<\xi_1<\xi,\\
\xi-x_3&=(\xi-x_2)\,\phi'(\xi_2), & x_2&<\xi_2<\xi,\\
&\ \,\vdots & &\ \,\vdots\\
\xi-x_{n+1}&=(\xi-x_n)\,\phi'(\xi_n), & x_n&<\xi_n<\xi.
\end{align*}
If we assume \(\abs{\phi'(\xi_i)}\le k\) (for all \(i\)), then
\[
\left.\begin{aligned}
\abs{\xi-x_1}&\le k\abs{\xi-x_0}\\
\abs{\xi-x_2}&\le k\abs{\xi-x_1}\\
\abs{\xi-x_3}&\le k\abs{\xi-x_2}\\
&\ \,\vdots\\
\abs{\xi-x_{n+1}}&\le k\abs{\xi-x_n}
\end{aligned}\ \right\}
\]
Multiplying these inequalities,
\[
\abs{\xi-x_{n+1}}\le k^{n+1}\abs{\xi-x_0}.
\]
If \(k<1\), the right-hand side tends to zero and \(x_0,x_1,x_2,\dots\) converges to \(\xi\). Thus \(\phi\) must satisfy
in a neighbourhood of the root; then any \(x_0\) chosen in an interval (within that neighbourhood) containing \(\xi\) leads to \(\xi\).
