How to prove sequence converges quadratically to a root of multiplicity

[i_a_n]

A function f has a root of multiplicity $m>1$ at the point $ x_*$ if $f(x_*)=f'(x_*)=...=f^{(m-1)}(x_*)=0$. Assume that the iteration$ x_{k+1}=x_k-mf(x_k)/f'(x_k)$ converges to $x_*$. If$ f^{(m)}(x_*)≠0$, prove that this sequence converges quadratically.(We may use the Taylor's series, but I cannot get the result we need to prove.
Expand expand $f(x_k)$ around $x_*$ until $m$-th order derivative term, which has the form
$(x_k - x_*)^m f^{(m)} (x_k) / m!$, and similarly for $ f ' (x_k)$ )

 

[MarkFL]

Re: how to prove sequence converges quadratically to a root of multiplicity

In an effort to let our helpers know where you are stuck, can you post your working so far and/or your thoughts on what you should try?

 

[I like Serena]

Re: how to prove sequence converges quadratically to a root of multiplicity

A function f has a root of multiplicity $m>1$ at the point $ x_*$ if $f(x_*)=f'(x_*)=...=f^{(m-1)}(x_*)=0$. Assume that the iteration$ x_{k+1}=x_k-mf(x_k)/f'(x_k)$ converges to $x_*$. If$ f^{(m)}(x_*)≠0$, prove that this sequence converges quadratically.(We may use the Taylor's series, but I cannot get the result we need to prove.
Expand expand $f(x_k)$ around $x_*$ until $m$-th order derivative term, which has the form
$(x_k - x_*)^m f^{(m)} (x_k) / m!$, and similarly for $ f ' (x_k)$ )

Hey!
This looks a lot like the other thread, where I posted http://www.mathhelpboards.com/f16/optimization-problem-Newtons-method-3447/#post15282.
Heck, you can even copy and paste it, and tweak it a little to be more generalized.
How far can you get?

 

[I like Serena]

Re: how to prove sequence converges quadratically to a root of multiplicity

Hmm, I thought you would be able to do this.
I guess I was wrong.
Ah well, it wouldn't be the first time I was wrong.

 

[blue_raver22]

To prove that the sequence converges quadratically, we need to show that the error term, which is the difference between the actual root and the approximated root, decreases quadratically with each iteration.

Let $x_*$ be the root of multiplicity $m$ and let $x_k$ be the $k$th iteration of the sequence. We can express the error term as $e_k = x_* - x_k$. Using Taylor's series expansion, we can write:

$f(x_*) = f(x_k) + (x_* - x_k)f'(x_k) + \frac{(x_* - x_k)^2}{2!}f''(x_k) + ... + \frac{(x_* - x_k)^m}{m!}f^{(m)}(x_k)$

Since $f(x_*) = 0$ (as $x_*$ is a root), we can simplify this expression to:

$0 = (x_* - x_k)f'(x_k) + \frac{(x_* - x_k)^2}{2!}f''(x_k) + ... + \frac{(x_* - x_k)^m}{m!}f^{(m)}(x_k)$

Dividing both sides by $f'(x_k)$ (since $f'(x_k) \neq 0$ for convergence), we get:

$0 = x_* - x_k + \frac{(x_* - x_k)^2}{2!}\frac{f''(x_k)}{f'(x_k)} + ... + \frac{(x_* - x_k)^m}{m!}\frac{f^{(m)}(x_k)}{f'(x_k)}$

Since $f^{(m)}(x_*) \neq 0$, we can rewrite the last term as:

$0 = x_* - x_k + \frac{(x_* - x_k)^2}{2!}\frac{f''(x_k)}{f'(x_k)} + ... + \frac{(x_* - x_k)^{m-1}}{(m-1)!}\frac{f^{(m-1)}(x_k)}{f'(x_k)}$

Substituting $f^{(m-1)}(x_k) = 0$ (as $x_*$ is a root of multiplicity $m$),