3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you familiar with the fixed-point iteration $x_{k+1} = g(x_k)$ (seeking to identify $r$ such that $g(r)=r$) and its convergence properties? $\endgroup$ – Dominique Feb 24 '13 at 16:59
  • $\begingroup$ Newton's method converges to multiple roots only linearly. $\endgroup$ – vonbrand Feb 24 '13 at 17:03
  • $\begingroup$ @vonbrand This isn't Newton's method. There is a factor $k$ in there. $\endgroup$ – Dominique Feb 24 '13 at 17:04
7
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you very much. And I'm interested.. Do we know that $f^{(k+1)}(r) \neq 0$? $\endgroup$ – Anne Feb 24 '13 at 18:26
  • $\begingroup$ @Anne No we don't. $\endgroup$ – Dominique Feb 24 '13 at 18:43
  • $\begingroup$ 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? $\endgroup$ – Anne Feb 24 '13 at 18:50
  • $\begingroup$ @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)$. $\endgroup$ – Dominique Feb 24 '13 at 22:19
  • $\begingroup$ 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? $\endgroup$ – Anne Feb 24 '13 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.