Newton's method - does it always work for functions that are close to the identity function?

80 Views Asked by At

Since Newton's method for finding roots trivially works for the identity function $t \mapsto t$, I was wondering whether it also works for every continuously differentiable functions that is sufficiently close to the identity. To be more precise:

Is there $\varepsilon >0$ such that Newton's method (initialized at any $x \in \mathbb{R}$) works for every continuously differentiable function $f \colon \mathbb{R} \to \mathbb{R}$ satisfying $|f(t)-t|<\varepsilon$ and $|f'(t)-1|<\varepsilon$ for every $t \in \mathbb{R}$?

1

There are 1 best solutions below

1
On BEST ANSWER

I don't understand why I got downvoted, but anyways, it seems that my intuition was right, I managed to prove the following:

Let $f \colon \mathbb{R} \to \mathbb{R}$ be a continuously differentiable function such that $|f'(t)-1|<1/5$ for every $t \in \mathbb{R}$. Then Newton's method for $f$ starting at any point in $\mathbb{R}$ converges to a root of $f$.

Proof: Obviously, there is exactly one $z \in \mathbb{R}$ with $f(z)=0$. For every $x \in \mathbb{R}$, denote $$\widehat{x}:=x-\frac{f(x)}{f'(x)}.$$ We claim that $|z-\widehat{x}| \leq |x-z|/2$ for every $x \in \mathbb{R}$. Obviously, this is true for $x=z$. Assume $x<z$. By the mean value theorem, there is $\xi \in (x,z)$ such that $$f'(\xi)=\frac{f(z)-f(x)}{z-x}=\frac{-f(x)}{z-x}=\frac{(\widehat{x}-x)f'(x)}{z-x}.$$ Since $4/5<f'(\xi)<6/5$ and both $f'(x)$ and $(z-x)$ are positive numbers, we have the following estimate: $$\frac{4}{5f'(x)}(z-x)<\widehat{x}-x<\frac{6}{5f'(x)}(z-x).$$ Substracting $(z-x)$ we obtain $$\frac{4-5f'(x)}{5f'(x)}(z-x)<\widehat{x}-z<\frac{6-5f'(x)}{5f'(x)}(z-x).$$ Since $4/5<f'(x)<6/5$, this leads to $$\frac{4-5 \cdot (6/5)}{5 \cdot (4/5)}(z-x)<\widehat{x}-z<\frac{6-5 \cdot (4/5)}{5 \cdot (4/5)}(z-x),$$ hence $$(x-z)/2<\widehat{x}-z<2(z-x)/5<(z-x)/2,$$ which proves that $|z-\widehat{x}| \leq |x-z|/2$. A similar approach works if $x>z$.

Finally, starting with any $x=x_0 \in \mathbb{R}$ and letting $x_n:=\widehat{x_{n-1}}$ for each $n \in \mathbb{N}$, it follows that $$|z-x_n| \leq 2^{-n}|z-x|$$ for each $n \in \mathbb{N}$. Therefore, $\displaystyle \lim_{n \to \infty} x_n = z$.