Results 1 to 4 of 4

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

  1. #1
    Senior Member
    Joined
    Feb 2008
    Posts
    410

    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 $\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 !
    Last edited by hatsoff; Sep 27th 2011 at 08:59 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    From
    México
    Posts
    721

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

    Quote Originally Posted by hatsoff View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2008
    Posts
    410

    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 ... ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    From
    México
    Posts
    721

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. determine the convergence
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Mar 13th 2011, 01:52 PM
  2. Replies: 4
    Last Post: Dec 3rd 2010, 05:27 AM
  3. How to determine the convergence
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 6th 2010, 02:46 PM
  4. Determine the order of a Runge-Kutta method
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: Oct 19th 2009, 06:56 AM
  5. Determine the convergence.
    Posted in the Calculus Forum
    Replies: 5
    Last Post: Mar 14th 2008, 01:21 PM

Search Tags


/mathhelpforum @mathhelpforum