6

I've got a problem with a modified Newton's method. We've got a function $f \in C^{(k+1)}$ and $r$ which is it's multiple root of multiciplity $k$. Also $f^{(k)}(r) \neq 0$ and $f'(x) \neq 0 $ in the neighbourhood of $r$.

The modified Newton's method is $$x_{n+1} = x_n - k\frac{f(x_n)}{f'(x_n)}$$ How to prove that $x_n$ converges to $r$ quadratically?

I found one method using a function $G(x) = (x-r) f'(x) - kf(x)$ but then it's said that $ G^{(k+1)}(r) \neq 0$ but it comes from the fact that $f^{(k+1)}(r) \neq 0$, but it doesn't necessarily have to be true, am I right? We know that $f^{(k)}(r) \neq 0$, but we have no information about the $k+1$st derivative. I would appreciate if somebody explained to me precisely, why it quadratically converges.

Anne
  • 1,557

1 Answers1

14

If $k=1$, you have a simple root, your iteration reduces to Newton's method and we know that in that case, Newton's method converges quadratically.

If $k > 1$, you have a multiple root and if $f$ has a root of multiplicity $k$ at $r$, it can be written in the form $f(x) = (x-r)^k h(x)$ where $h(r) \neq 0$.

Now your iteration is a fixed-point iteration of the form $x_{k+1} = g(x_k)$ where $g(x) := x - k f(x)/f'(x)$. Using the expression of $f$ above, you can check that $g(r) = r$, which is why $g$ is called a fixed-point function---it does not move $r$---and $r$ is called a fixed point of $g$. The thing with fixed-point iterations is that they converge (to a fixed point of $g$) provided $|g'(r)| < 1$ and you initialize them sufficiently close to $r$. If you denote $e_n := (x_n -r)$ the error at the $n$-th iteration, then, using a Taylor expansion, you get $$ e_{n+1} = x_{n+1} - r = g(x_n) - r \approx g(r) + g'(r) (x_n - r) - r = g'(r) e_n $$ because $g(r) = r$. So essentially, the error is reduced by a factor $|g'(r)|$ at each iteration when you're sufficiently close to $r$. If $g'(r) \neq 0$, this is called linear convergence. But what if $g'(r) = 0$? You just perform a second-order expansion instead of a first-order expansion and you get $$ e_{n+1} \approx g(r) + g'(r) e_n + \tfrac{1}{2} g''(r) e_n^2 -r = \tfrac{1}{2} g''(r) e_n^2, $$ and now the error is (roughly) squared at each iteration. This is called quadratic convergence. (If $g''(r)=0$, you go to third order, etc.)

Why am I explaining all this? If you want to show that your modified Newton iteration converges quadratically, you can try to show that $g(r)=r$ and $g'(r) = 0$.

It's exactly the case with your iteration and it's relatively easy if you write $f(x) = (x-r)^k h(x)$. Compute $f'(x)$, $f''(x)$, $g'(x)$, simplify, and then plug $x=r$. You'll see that $g'(r)=0$.

Dominique
  • 3,144
  • Thank you very much. And I'm interested.. Do we know that $f^{(k+1)}(r) \neq 0$? – Anne Feb 24 '13 at 18:26
  • @Anne No we don't. – Dominique Feb 24 '13 at 18:43
  • Ok. But I'm still wondering about the method I read about earlier, the one that I mentioned in my first posts. When we have the function $G(x)$ as above, we can't assume that $G^{(k+1)} (r) \neq 0$, right? Or am I thinking wrong? – Anne Feb 24 '13 at 18:50
  • @Anne I'm not sure what the method with $G$ really is besides the fact that $G(r)=0$. All you know if that $f(r) = f'(r) = \cdots = f^{(k-1)}(r) = 0$ and $f^{(k)}(r) \neq 0$. The fact that $r$ is a root of multiplicity $k$ doesn't say anything about $f^{(k+1)}(r)$. All I can say is that for any $m \geq 0$, $G^{(m)}(x) = (m-k) f^{(m)}(x) + (x-r) f^{(m+1)}(x)$, so that $G^{(k)}(r) = 0$ and $G^{(k+1)}(r) = f^{(k+1)}(r)$. – Dominique Feb 24 '13 at 22:19
  • Yes, that's what I thought. Thank you. And just to be sure- $g^{''}$ in the neighbourhood of $r$ is $< \infty$ because $g$ as a function: [1 - quotient of functions at least of class $C^k$] is of class $C^k$ and k is at least 2, right? – Anne Feb 24 '13 at 22:40
  • @Anne Yes and because of your assumption that $f'(x) \neq 0$ over a neighborhood of $r$. – Dominique Feb 24 '13 at 22:46
  • Of course. Thank you so much! – Anne Feb 24 '13 at 23:05
  • so youre essnetially saying newotn method is linear for simple roots? that is not true? – james black Feb 19 '18 at 05:41
  • @jamesblack Newton's method is locally quadratic for simple roots. – Dominique Feb 27 '18 at 14:58