Numerical Analysis Home

Newton-Raphson Method


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.

Last edited