Newton's Function Confusion "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.
 A: 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.
A: $$
-\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,
A: 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$
