Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm studying numerical analysis and I read in Wikipedia that "If the root being sought has multiplicity greater than one, the convergence rate is merely linear".

The article in Wikipedia also mentions that "if the multiplicity $m$ of the root is known, one can use the following modified algorithm that preserves the quadratic convergence rate: $$x_{n+1} = x_n -m \bigl[f(x_n)/f'(x_n)\bigr].$$

I tried proving this and I couldn't do it (I only managed to prove that convergence rate is at least linear). Any ideas on how can this be proven ?

share|improve this question
    
    
Yes, thats what I wrote before the edit...anyways I fixed it... thanks for the edit –  Belgi Dec 21 '11 at 10:06
    
Oh, I'm sorry, my goof. –  David Mitra Dec 21 '11 at 10:07

2 Answers 2

up vote 8 down vote accepted

Hum, I am not going to write full details... write $f(x) = (x-a)^m g(x)$ with $g(a)\ne 0$.

Then $$\phi(x) = x - m {f(x) \over f'(x)} = x - { (x-a) g(x) \over g(x) + {1\over m} (x-a) g'(x)} $$

Set $x_{n+1} = \phi(x_n)$ and $y_n = x_n - a$. Then readily $$y_{n+1} = y_n \left( 1 - {1 \over 1 + {1\over m} y_n {g'(a+y_n)\over g(a+y_n)}}\right).$$

A first order approximation gives $$y_{n+1} \simeq y_n^2 {1\over m} {g'(a+y_n)\over g(a+y_n)},$$ hence the quadratic convergence (here I leave you some gory details).

Note that without the $m$ the same computations leads to $$y_{n+1} \simeq y_n \left( {m-1\over m} + {1\over m} y_n {g'(a+y_n)\over g(a+y_n)} \right) \simeq {m-1\over m} y_n,$$ so you will get a linear rate of convergence.

share|improve this answer

Suppose that $x$ is a m-multiple root. then you can have $f(x_k)=(x_k-x)^mf^{(m)}(x)/m!+O((x_k-x)^{m+1})$, derivate it $f'(x_k)=m(x_k-x)^{m-1}f^{(m)}(x)/m!+O((x_k-x)^m)$

$$x_{k+1}-x=x_k-f(x_k)/f'(x_k)-x$$ $$=x_k-x-(x_k-x)/m+O((x_k-x)^2)$$ you see this is linear convergence. But if you change here $x_{k+1}=x_k-m[f(x_k)/f'(x_k)]$

then you can get this result $x_k-x-m(x_k-x)/m+O((x_k-x)^2)=O((x_k-x)^2)$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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