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