# Thread: determine the order of convergence of steffensen's method

1. ## determine the order of convergence of steffensen's method

Hey guys. This numerical analysis section is really throwing me. I don't quite know how to handle this order of convergence stuff. Here's just one example of a problem that's giving me trouble:

Let $F(x)=x-\frac{f(x)}{g(x)}$, where $g(x)=\frac{f(x+f(x))-f(x)}{f(x)}$ and $f$ is smooth.

Suppose a sequence $\{x_n\}$ satisfies $x_{n+1}=F(x_n)$ and converges to $r$, where $r$ is a simple zero of $f$. We define "order of convergence" to be the largest real number $q$ such that

$\lim_{n\to\infty}\frac{|x_{n+1}-r|}{|x_n-r|^q}$

exists and is nonzero. Determine the order of convergence.
Any help would be much appreciated !

2. ## Re: determine the order of convergence of steffensen's method

Originally Posted by hatsoff
Hey guys. This numerical analysis section is really throwing me. I don't quite know how to handle this order of convergence stuff. Here's just one example of a problem that's giving me trouble:

Any help would be much appreciated !
I'm going to assume $f\in C^1(\mathbb{R})$ (I think a locally bounded derivative would be enough).

Obviously your limit is $0$ when $q<0$. Since $g(r)=f'(r)\neq 0$ (I'm assuming this is your definition of simple zero) $F'(r)$ exists, $F(r)=r$ so if we put $q>1$ we get

$\frac{|F(x_n)-F(r)|}{|x_n-r|^q}=\frac{|F(x_n)-F(r)|}{|x_n-r|}|x_n-r|^{1-q}$

and the first term goes to $|F'(r)|$ while the second blows up so the limit doesn't exist. If $q=1$ in the above, calculting $F'(r)$ we arrive at the conclusion that the limit in this case is $|F'(r)|=2$.

Now if $0 we get, using the triangle inequality first, the fact that $f$ is locally Lipschitz continous and that $f(r)=0$

$\frac{|F(x_n)-r|}{|x_n-r|^{q}} \leq |x_n-r|^{1-q} + \frac{1}{|g(x_n)|} \frac{ |f(x_n)|}{|x_n-r|^q} \leq |x_n-r|^{1-q}\left(1+\frac{1}{|g(x_n)|}\right)\rightarrow0$

So in fact $q=1$ is the only value for which the limit isn't zero or infinite.

3. ## Re: determine the order of convergence of steffensen's method

Thanks, but I get $F'(r)=0$, not $|F'(r)|=2$.

Oh, and I forgot to say $f$ is smooth.

I guess I could maybe try computing $F''(r)$ and using Taylor's series, but to compute $F''(r)$ would take perhaps an hour or more---assuming I didn't make any elementary mistakes. Perhaps there is a more efficient method of solution ... ?

4. ## Re: determine the order of convergence of steffensen's method

Yes, I misread a sign, but the argument still works: The limit is then $0$ for $q\leq 1$ and infinity for $q>1$. Have you asked a professor for clarification? Maybe there's something we're missing.