Newton's Function Confusion

Question

"Suppose that $r$ is a double root of $f(x) = 0$, that is $f(x)=f'(x)=0$, $f''(x) \neq 0$, and suppose that $f$ and all derivatives up to and including the second are continuous in some neighborhood of $r$. Show that $\epsilon_{n+1} \approx \frac{1}{2}\epsilon_{n}$ for Newton's method and therby conclude that the rate of convergence is $\textit{linear}$ near a double root. (If the root has multiplicity $m$, then $\epsilon_{n+1} \approx \left [ \frac{(m-1)}{m}\right ]\epsilon_n $)".

I'm a good amount of confused on this problem. So I know that $\epsilon_n = -\frac{f(x_n)}{f'(x_n)}$ (our error) and that a function with a double root can be written as $f(x) = (x-r)^2g(x)$ where $r$ is our double root.

I just don't really know how to do this / start this. If I calculate $\epsilon_n$, I get $-\frac{(x-r)^2g(x)}{2(x-r)g(x) + (x-r)^2g'(x)}$, but what use is that? I think I need a decent push forward in the right direction. Help?

Maybe, the $x$'s in my $\epsilon_n$ calculation are supposed to be $x_n$'s? Since we know that as $x_n \to r$, $(x_n - r) \to 0$. Then we could do something with that? That would just make it $0$ though which doesn't help us.

Answer 1

Write $f(x) = (x-r)^2g(x)$ for $x\neq r$ as you did. Note that this does not define $g$ at $r$, so it certainly isn't differentiable there… I'll start by extending $g$ at $r$ by continuity. Write Taylor's second order formula with Lagrange remainder for $f$ at $r$: \begin{align} f(r+h) &= f(r) + hf'(r) + \frac{h^2}2 f''(r+\theta_h) \\ &= \frac{h^2}2 f''(r+\theta_h) \end{align} for some $\theta_h\in[0,h]$. On the other hand, $f(r+h) = h^2 g(r+h)$, so that we get $g(r+h) = \frac12 f''(r+\theta_h)$. When $h$ tends to $0$, so does $\theta_h$, and so $f''(r+\theta_h)\to f''(r)$ because $f''$ is continuous. Hence $g(r+h)\to\frac12 f''(r)$, so I define $g$ at $r$ by setting $$g(r) = \frac12 f''(r).$$

Now consider the function $\phi(x) = (x-r)\sqrt{g(x)}$, and let's show that it is differentiable at $r$: $$ \frac{\phi(r+h)-\phi(r)}h = \frac{h\sqrt{g(r+h)}}h = \sqrt{g(r+h)} $$ which tends to $\sqrt{\frac12 f''(r)}$ when $h\to0$. Therefore $\phi$ is differentiable at $r$ and $\phi'(r) = \sqrt{\frac12 f''(r)}$.

Now write Taylor's formula at the first order for $\phi$ betweenn $r$ and $x_n$: $$ \phi(r) = \phi(x_n) + (r-x_n)\phi'(x_n) + (r-x_n)\varepsilon(r-x_n) $$ for some function $\varepsilon$ that tends to $0$ at $0$. Remembering that $\phi(r)=0$ and switching things around a bit you find that $$ e_n - \frac{\phi(x_n)}{\phi'(x_n)} = e_n\varepsilon(e_n). $$ Considering that $\phi(x)^2=f(x)$, differentiating gives $2\phi'(x)\phi(x) = f'(x)$, and dividing the first equation by the second gives $f(x)/f'(x) = \phi(x)/2\phi'(x)$. Combining this with the previous equation gives $$ e_n - \frac{f(x_n)}{f'(x_n)} - \frac{\phi(x_n)}{2\phi'(x_n)} = e_n\varepsilon(e_n). $$ Replacing $e_n - f(x_n)/f'(x_n)$ by $e_{n+1}$ we find $$ e_{n+1} = e_n\varepsilon(e_n) + \frac{\phi(x_n)}{2\phi'(x_n)}. $$ Now $\phi(x_n) = e_n \sqrt{g(x_n)}$, and $\phi'(x_n) \to \phi'(r) = \sqrt{\frac12 f''(r)}=\sqrt{g(r)}$, so finally we have $$ e_{n+1} = e_n \left(\varepsilon(e_n) + \frac12 \frac{\sqrt{g(x_n)}}{\phi'(x_n)} \right), $$ where $\varepsilon(e_n)\to0$ and $\sqrt{g(x_n)}/\phi'(x_n)\to1$, which answers the question.

Answer 2

$$ -\frac{(x-r)^2g(x)}{2(x-r)g(x) + (x-r)^2g'(x)} = (x-r)\frac{-g(x)}{2g(x) + (x-r)g'(x)} $$ If you take $|x-r| \le \frac C{|g'(x)|}$ (which you can do because $g$ is continuous, hence this works in some neighborhood of your point $r$ at which you use Newton) or if $g'(x) = 0$, then this bound is roughly linear.

Hope that helps,

Answer 3

This solution was shown to me by a friend. I understand now!

The solution is as follows:

Let us state the statement of Newton's Method: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

We know that (our initial guess) is $x_{n} = r + \epsilon$ where $r$ is our double-root and $epsilon$ is our $\textit{very}$ small error. Then our error is $\epsilon = r - x_n$.

Our statement for linear convergence is $|e_{n+1}| \leq |e_n|C$ where $C\in \left[ 0, 1\right )$

We can then write $\underbrace{r - x_{n+1}}_{e_{n+1}} = \underbrace{r - x_n}_{e_n} + \frac{f(x_n)}{f'(x_n)}$ to get $e_{n+1} = e_n + \frac{f(x_n)}{f'(x_n)}$.

From the Taylor Series around $r$, we can write a function with the double root $r$ as $f(x) = (x-r)^2g(x)$ where $g(x)$ is defined in: $(x-r)^2\left [ \underbrace{\frac{f''(r)}{2!} + \frac{f'''(r)(x-r)}{3!} + \dots}_{g(x)} \right ]$ since $f(r) = 0$ and $f'(r) = 0$.

We then calculate $\frac{f(x_n)}{f'(x_n)} = \frac{(x_n - r)^2g(x_n)}{2(x_n - r)g(x_n) + (x_n -r)^2g'(x_n)} = \frac{(x_n - r)}{2 + \frac{g'(x)}{g(x)}}$.

We can then make the appropriate substitutions $\frac{-e_n}{2 - e_n\frac{g'(x)}{g(x)}}$

$\lim_{n \to \infty} \frac{g'(x)}{g(x)} = \frac{g'(r)}{g(r)} = K$ where $K$ is a constant.

Then $e_{n+1} = e_n - \frac{e_n}{2 - e_nK} = e_n\frac{(1-e_nK)}{2-e_nK}$.

When we look at $n$ as it approaches infinity, then $\frac{(1-e_nK)}{2-e_nK} \to \frac{1}{2}$. This leaves us with the conclusion that $e_{n+1} \approx \frac{1}{2}e_n$