1
$\begingroup$

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

1 Answers 1

4

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?

  • 0
    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.2011-12-22
  • 0
    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.2011-12-22