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:

Quote:

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

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

$\displaystyle \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 !

Re: determine the order of convergence of steffensen's method

Quote:

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 $\displaystyle f\in C^1(\mathbb{R})$ (I think a locally bounded derivative would be enough).

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

$\displaystyle \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 $\displaystyle |F'(r)|$ while the second blows up so the limit doesn't exist. If $\displaystyle q=1$ in the above, calculting $\displaystyle F'(r)$ we arrive at the conclusion that the limit in this case is $\displaystyle |F'(r)|=2$.

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

$\displaystyle \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 $\displaystyle q=1$ is the only value for which the limit isn't zero or infinite.

Re: determine the order of convergence of steffensen's method

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

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

I guess I could maybe try computing $\displaystyle F''(r)$ and using Taylor's series, but to compute $\displaystyle 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 ... ?

Re: determine the order of convergence of steffensen's method

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