Let $f :[a,b]\to\mathbb{R}$ be any function which is twice differentiable in $(a,b)$ with only one root $\alpha$ in $(a,b)$. Let $f'(x)$ and $f''(x)$ denote the first and second order derivatives of $f(x)$ with respect to $x$. If $\alpha$ is a simple root and is computed by the Newton-Raphson method, then the method converges if
$$|f(x)f''(x)|<|f'(x)|^2.$$
How to show this argument?
$\endgroup$3 Answers
$\begingroup$Let me try my best to answer your question. First, I am going to lay down some math FACTs / THMs / DEFs before I start the proof. I attached Wikipedia links to each FACT / THM / DEF. After this, I will complete the proof.
FACTs / THMs / DEFs:
FACT 1: The real numbers is a complete metric space under the usual absolute value. The definition of complete metric space is defined here: .
THM 1: The Banach Fixed Point Theorem. The theorem can be found here:
DEF 1: A Contraction Mapping. The definition can be found here:
PROOF:
Step 1:
Let$$T:X\rightarrow X$$$$x_{n+1}=T(x_n)=x_n-\frac{f(x_n)}{f'(x_n)}.$$
Our primary goal is to find conditions on $f$ such that the Banach-Fixed-Point THM (THM 1) is true. If THM 1 is true, $\forall x_0 \in X, \exists x^* \in X : \lim_{n\rightarrow\infty}x_n=x^*$ i.o.w. the NR-Method is guaranteed to converge.
Step 2:
First, THM 1 requires that $T$ be a contraction mapping (DEF 1). For this to be true we need restrict the domain $X$ to focus on only one fixed point. If we do not do this, $T$ is not technically a contraction mapping due to a contradiction (See THM 1's Wiki proof last line). Second, we need $X$ to be a complete metric space. This is true by FACT 1: $X\subset \mathbb{R}$ where the metric is $|\cdot|$.
With $X$ satisfying the conditions discussed above, lets assume $T$ is a contraction mapping. Then$$\exists q \in [0,1) : \forall x_2, x_1 \in X, |T(x_2)-T(x_1)| \leq q|x_2-x_1|.$$
Step 3:
Reducing this and taking the limit $x_2-x_1\rightarrow 0$ we find$$|T'(x)|=\lim_{x_2-x_1\rightarrow 0}\left|\frac{T(x_2)-T(x_1)}{x_2-x_1}\right|<\lim_{x_2-x_1\rightarrow 0}1 = 1, \forall x \in X$$$$|T'(x)| < 1, \forall x \in X.$$
Step 4:
Of course $T$ must be differentiable, but we will see that is equivalent to saying $f(x)$ is twice differentiable. Using standard differentiation one can show$$T'(x) = \frac{f(x)f''(x)}{f'(x)^2}, \forall x \in X.$$Finally, we have$$|f(x)f''(x)| < |f'(x)^2|, \forall x \in X.$$I.o.w. we have shown$|f(x)f''(x)| < |f'(x)^2|, \forall x \in X$ $\implies$ $T$ is a contraction mapping on $X$ $\implies$ $\forall x_0 \in X, \exists x^* \in X : \lim_{n\rightarrow\infty}x_n=x^*$ $\implies$ NR-Method converges.
I'll offer only a sketch proof. We can show the error terms $\varepsilon_n:=\alpha-x_n$ satisfy $\varepsilon_{n+1}=-\frac{f^{\prime\prime}(\xi_n)}{f^\prime(\xi_n)}\varepsilon_n^2$ for some $\xi_n$ between $x_n$ and $\alpha$. We're assured of convergence if $$\left|\frac{f^\prime(\xi_n)}{f^{\prime\prime}(\xi_n)}\right|>|\varepsilon_n|.$$But the given inequality may be rearranged, viz.$$\left|\frac{f^\prime(\xi_n)}{f^{\prime\prime}(\xi_n)}\right|>\left|\frac{f(\xi_n)}{f^\prime(\xi_n)}\right|\approx|\xi_n-\alpha|\sim|\epsilon_n|.$$
$\endgroup$ 2 $\begingroup$Look at $$g(x)=x-\frac{f(x)}{f'(x)}.$$ Then $$g'(x)=\frac{f(x)f''(x)}{f'(x)^2}$$ and by assumption $|g^\prime(x)|<1$. Now apply the fixed-point formulation of your choice.
$\endgroup$ 4
