Newton method with high multiplicity: rigorous proof

290 Views Asked by At

I am looking for a rigorous yet reasonably short proof of the following statement: let $f\in \mathcal{C}^{m}([a,b])$, and let $\alpha \in (a,b)$ such that $$ 0 = f(\alpha) = f'(\alpha) = f''(\alpha) = \dots = f^{(m-1)}(\alpha), \quad f^{(m)}(\alpha) \neq 0. $$ Then the Newton method $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$ converges locally to $\alpha$ linearly with rate $1-\frac{1}{m}$.

The usual way I see this proof is: one writes $f(x) = (x-\alpha)^m g(x)$, where $g(\alpha) \neq 0$, plugs this expression into the iteration function $\Phi(x) = x - \frac{f(x)}{f'(x)}$, and shows that $\lim_{x\to\alpha} \Phi'(x) = 1 - \frac{1}{m}$. Then standard results for fixed-point iterations $x_{k+1} = \Phi(x_k)$ (with a $\mathcal{C}^1$ iteration function $\Phi$) can be used to conclude.

However, on a closer look, I believe this proof has two issues:

  1. One needs to use the first and second derivative of $g$ when computing $\Phi'(x)$, so we are silently assuming that $g$ is differentiable in $x=\alpha$.

  2. One should also prove that $\Phi'(\alpha)$ actually exists and coincides with the limit, since nothing guarantees that $\Phi$ is a $\mathcal{C}^1$ function.

I do not see a quick way to fill these holes. Do you know of a way to avoid these two issues? Bonus points if it is a short and natural one, since ideally I'd like to show it in a course for engineering majors.

1

There are 1 best solutions below

4
On BEST ANSWER

Let $f\in \mathcal{C}^{m}([a,b])$ with $m\ge 2$, and let $\alpha \in (a,b)$ such that $$ 0 = f(\alpha) = f'(\alpha) = f''(\alpha) = \dots = f^{(m-1)}(\alpha), \quad f^{(m)}(\alpha) \neq 0. $$

Repeated application of L'Hôpital's rule gives $$ \begin{align} \lim_{x \to \alpha} \frac{f(x)}{(x-\alpha)^m} &= \lim_{x \to \alpha} \frac{f'(x)}{m(x-\alpha)^{m-1}} \\ &= \lim_{x \to \alpha} \frac{f''(x)}{m(m-1)(x-\alpha)^{m-2}} \\ &= \cdots \\ & = \lim_{x \to \alpha} \frac{f^{(m)}(x)}{m!} = \frac{f^{(m)}(\alpha)}{m!} \tag{$*$} \end{align} $$ because the $f^{(m)}$ is continuous at $x=\alpha$, so that the limit in the last line exist. What we need in the following is that the first three limits exist and are equal.

The function $$ \Phi(x) = \begin{cases} x - f(x)/f'(x) & \text{ if } x \ne \alpha \, ,\\ \alpha & \text{ if } x = \alpha \, , \end{cases} $$ is defined in some neighborhood of $x=\alpha$, and continuously differentiable except possibly at $x=\alpha$.

First we show that $\Phi$ is differentiable at $x = \alpha$ with $\Phi'(\alpha) = 1-1/m$: For $x \ne \alpha$ is $$ \frac{\Phi(x)-\Phi(\alpha)}{x-\alpha} = 1 - \frac{f(x)}{(x-\alpha)f'(x)} \\ = 1 - \frac{f(x)}{(x-\alpha)^m} \cdot \left( \frac{f'(x)}{(x-\alpha)^{m-1}}\right)^{-1} $$ and that converges to $1-\frac 1m$ by $(*)$.

Then we show that $\Phi'$ is continuous at $x=\alpha$: For $x \ne \alpha$ is $$ \Phi'(x) = \frac{f(x)f''(x)}{f'(x)^2} = \frac{f(x)}{(x-\alpha)^m} \cdot \frac{f''(x)}{(x-\alpha)^{m-2}} \cdot\left( \frac{f'(x)}{(x-\alpha)^{m-1}}\right)^{-2} $$ and that converges to $m(m-1) \cdot \frac 1{m^2} = \Phi'(\alpha) $, again by using $(*)$.