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.

This is a question from D Kincaid & W Cheney, Numerical Analysis (3ed), Brooks-Cole 2002;

Find the condition on $\alpha$ to ensure that the iteration will converge linearly to a zero of $f$ if started near the zero.

This question is in the Newton's Method Section, I tried to get a solution using ideas from that section, but I am not sure,

Say $f(r)=0$ and and $x_{n}-r=e_{n}$ then using $x_{n+1}=x_{n}-\alpha f(x_{n})$. we get $e_{n+1}=e_{n}-\alpha f(x_{n})$.

Using Taylor's thm we have $0=f(r)=f(x_{n}-r)=f(x_{n})-e_{n}f'(\eta_{x})$ for some $\eta_{x}$ between $r$ and $x_{n}$.

Using this in above we get $e_{n+1}=e_{n}-\alpha f(x_{n})=e_{n}-\alpha e_{n} f'(\eta_{x}) \approx e_{n}(1-\alpha f'(r))$

To have linear convergence we need $(1-\alpha f'(r)\neq 0)$ and $|1-\alpha f(r)| <1$.

But this does not say anything about the convergence of the method.

Then I thought that I can convert this as a functional iteration problem finding fixed point of some function F, this fixed point is the zeros of $f$. That is say $F(x)=x-\alpha f(x)$. Under the condition $|F'(r)|=\lambda<1$ and then by continuity of $F'$ (assuming $f'$ is cont.) we can get the desired result with the same conditions, $1-\alpha f'(r)\neq 0$ and $|1-\alpha f'(r)|<1$

any help would be appreciated.

-last two lines corrected

share|improve this question
add comment

1 Answer

Your key equation is $e_{n+1}\approx e_{n}(1-\alpha f'(r))$. As you say, you need $|1-\alpha f'(r)| <1$ for the iteration to converge (note you lost a prime on $f$). This gives a condition on $\alpha$ based on the value of $f'$ near the root. Ideally, it would be $\frac1{f'(r)}$, right?

share|improve this answer
    
Thanks for correction and answer. if $\alpha = \frac{1}{f'(r)}$ then don't we have at least quadratic convergence ?, but still have linear convergence. So we can say that $|1-\alpha f'(r)|<1$ is enough for linear convergence. –  aranel Dec 22 '11 at 18:51
    
Exactly. The usual Newton's method has $\alpha = \frac{1}{f'(r)}$ and is quadratic, but any $\alpha$ near that will be linear, reducing it by the factor $1-\alpha f'(r)$ at each step. –  Ross Millikan Dec 22 '11 at 19:23
add comment

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.