Suppose \(f\) is a function with a unique root \(x^*\) in \([a,b]\). Assume \(f''\) is continuous in \([a,b]\). To find \(x^*\),
let \(x_0\) be a "good" initial approximation (i.e., \(|x^*-x_0|^2 \approx 0\)) where \(f'(x_0)\neq 0\). Using Taylor's Theorem
on \(f\) about \(x_0\), we get
\[f(x)=f(x_0)+\frac{f'(x_0)}{1!}(x-x_0)
+\frac{f''(\xi)}{2!}(x-x_0)^2,\]
for some number \(\xi\) (depends on \(x\)) between \(x_0\) and \(x\). Plugging \(x=x^*\), we get
\[\begin{align*}
& 0=f(x^*)=f(x_0)+\frac{f'(x_0)}{1!}(x^*-x_0)
+\frac{f''(\xi)}{2!}(x^*-x_0)^2\\
\implies & f(x_0)+\frac{f'(x_0)}{1!}(x^*-x_0)
=-\frac{f''(\xi)}{2!}(x^*-x_0)^2 \approx 0 \;\;(\text{since }|x^*-x_0|^2\approx 0)
\end{align*}\]
Now solving for \(x^*\), we get
\[x^*\approx x_0-\frac{f(x_0)}{f'(x_0)}.\]
So \(x_1=x_0-\frac{f(x_0)}{f'(x_0)}\) is an approximation to \(x^*\). Using \(x_1\), similarly we get
\(x_2=x_1-\frac{f(x_1)}{f'(x_1)}\). Continuing the process, we get a sequence \(\{x_n\}\) to approximate \(x^*\) where
\[\boxed{x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)},\; n=0,1,2,\ldots}\]
Observation.
\(x_{n+1}\) is the \(x\)-intercept of the tangent line to \(y=f(x)\) at \((x_n,f(x_n))\).
The equation of the tangent line to \(y=f(x)\) at \((x_n,f(x_n))\) is
\[y=f(x_n)+f'(x_n)(x-x_n).\]
For the \(x\)-intercept, \(y=0\). So
\[0=f(x_n)+f'(x_n)(x-x_n)\implies x=x_n-\frac{f(x_n)}{f'(x_n)}.\]
Thus \(x_{n+1}\) is the \(x\)-intercept of the tangent line to \(y=f(x)\) at \((x_n,f(x_n))\).
Remark. We will show later that \(\{x_n\}\) converges to \(x^*\) for a good choice of an initial approximation \(x_0\).
If \(x_0\) is far from \(x^*\), then \(\{x_n\}\) may not converge to \(x^*\). For example, \(f(x)=x^2-5\) has a unique root
\(x^*=\sqrt{5}\) in \([-2,3]\). But the Newton-Raphson Method constructs a sequence \(\{x_n\}\) using \(x_0=-2\)
that converges to \(-\sqrt{5}\neq x^*\).
Example.
Do four iterations by the Newton-Raphson Method to approximate the root \(x^*\) of \(f(x)=e^x-x-2\) on the interval \([0,2]\)
using \(x_0=1\).
Solution. \(f(x)=e^x-x-2 \implies f'(x)=e^x-1\) and \(f'(1)=e-1\neq 0\). Thus
\[x_{n+1}
=x_n-\frac{e^{x_n}-x_n-2}{e^{x_n}-1},\; n=0,1,2,\ldots\]
\[\begin{array}{|l|l|c|l|l|}
\hline n & x_n & f(x_n) & f'(x_n) & x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\\
\hline 0 & 1 & -0.2817 & 1.7182 & 1.1639 \\
\hline 1 & 1.1639 & 0.0384 & 2.2023 & 1.1464 \\
\hline 2 & 1.1464 & 0.0004 & 2.1468 & 1.1462 \\
\hline 3 & 1.1462 & 0.0000 & 2.1462 & 1.1462 \\
\hline
\end{array}\]
Since \(|x_4-x_3|<10^{-4}\), we can say that the root is \(x_4=1.1462\) roughly correct to four decimal places
(almost true as \(x^*=1.146193\)). Actually \(x_4\) is correct to 12 decimal places! Note that this sequence converges
to the root faster than that of other methods (why?).
Convergence: Suppose \(f\) is a function with a simple root \(x^*\) in \([a,b]\), i.e., \(f'(x^*)\neq 0\).
Assume \(f''\) is continuous in \([a,b]\). Then there is a \(\delta>0\) such that the sequence \(\{x_n\}\) constructed by
the Newton-Raphson Method converges to \(x^*\) for any choice of the initial approximation \(x_0\in (x^*-\delta,x^*+\delta)\).
Consider the following function \(g\) on \([a,b]\):
\[g(x)=x-\frac{f(x)}{f'(x)}\]
First note that \(x^*\) is a fixed point of \(g\) in \([a,b]\). Since \(f'(x^*)\neq 0\), by the continuity of \(f'\)
in \([a,b]\), there is a \(\delta_1>0\) such that \(f'(x)\neq 0\) for all \(x\in [x^*-\delta_1,x^*+\delta_1]\).
So \(g\) is continuous on \([x^*-\delta_1,x^*+\delta_1]\).
The convergence follows by that of the Fixed Point Iteration of \(g\) on \([x^*-\delta,x^*+\delta]\) if we can show that there
is a positive \(\delta<\delta_1\) such that
(i) \(x^*-\delta\leq g(x)\leq x^*+\delta\) for all \(x\in [x^*-\delta,x^*+\delta]\) and (ii) \(|g'(x)|<1\) for all
\(x\in(x^*-\delta,x^*+\delta)\). To prove (ii), note that
\[\begin{align*}
& g'(x)=1-\frac{f'(x)f'(x)-f(x)f''(x)}{(f'(x))^2}=\frac{f(x)f''(x)}{(f'(x))^2}\\
\implies & g'(x^*)=\frac{f(x^*)f''(x^*)}{(f'(x^*))^2}=0\;\; (\text{since }f(x^*)=0,\;f'(x^*)\neq 0)
\end{align*}\]
Since \(g'(x^*)=0\), by the continuity of \(g'\) in \([x^*-\delta,x^*+\delta]\), there is a positive \(\delta<\delta_1\)
such that \(|g'(x)|<1\) for all \(x\in (x^*-\delta,x^*+\delta)\). So we have (ii). To show (i), take
\(x\in [x^*-\delta,x^*+\delta]\). By the MVT on \(g\), we have \(g(x)-g(x^*)=g'(\xi)(x-x^*)\) for some \(\xi\) between \(x\)
and \(x^*\). Thus
\[|g(x)-x^*|=|g(x)-g(x^*)|=|g'(\xi)||x-x^*|<|x-x^*|.\]
Since \(x\in [x^*-\delta,x^*+\delta]\), i.e., \(|x-x^*|\leq \delta\), we have \(|g(x)-x^*|<|x-x^*|\leq \delta\), i.e.,
\(x^*-\delta\leq g(x)\leq x^*+\delta\). ◼
Note that if the root \(x^*\) of \(f\) is not simple, i.e., \(f'(x^*)=0\), then this proof does not work but still
\(\{x_n\}\) may converge to \(x^*\). For multiple root \(x^*\) of \(f\) we use a modified Newton-Raphson iteration formula.
The Secant Method: In the iteration formula by the Newton-Raphson Method
\[x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)},\; n=0,1,2,\ldots,\]
we need to calculate the derivative \(f'(x_n)\) which may be difficult sometimes. To avoid such calculations, the
Secant Method modifies the above formula by replacing \(f'(x_n)\) with its approximation. Note that
\[f'(x_n)=\lim_{x\to x_n}\frac{f(x)-f(x_n)}{x-x_n}.\]
If \(x_{n-1}\) is close to \(x_n\), then
\[f'(x_n)\approx\frac{f(x_{n-1})-f(x_n)}{x_{n-1}-x_n}
=\frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}.\]
Thus
\[x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\approx
x_n-\frac{f(x_n)}{\frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}}=x_n-\frac{(x_n-x_{n-1})f(x_n)}{f(x_n)-f(x_{n-1})}.\]
Thus the iteration formula by the Secant Method is
\[\boxed{x_{n+1}=x_n-\frac{(x_n-x_{n-1})f(x_n)}{f(x_n)-f(x_{n-1})},\; n=1,2,3,\ldots}\]
Note that geometrically \(x_{n+1}\) is the \(x\)-intercept of the secant line joining \((x_n,f(x_n))\) and
\((x_{n-1},f(x_{n-1}))\). Also note that the convergence of the sequence \(\{x_n\}\) by the Secant Method is slower
than that of the Newton-Raphson Method.
