how to prove the convergence of fixed point iteration algorithm

1,496

Do you know which quadrant for $\arccos$?

Clearly the iterative function maps $[-\pi,\pi]$ into itself. So you should be able to establish the existence of the fixed point by Brouwer's fixed point theorem. Beyond that you need some proof of contraction. Your formula is a mess, so no idea how you will do it.

Share:
1,496

Related videos on Youtube

Harry
Author by

Harry

Optimization is everywhere. watch out!

Updated on August 01, 2022

Comments

  • Harry
    Harry over 1 year

    Please refer to the below algorithm:

    enter image description here

    Above two steps can be rewritten as, \begin{equation} x(k+1)=\arccos\bigg( -\frac{1}{2(Dr^{\frac {|\sin(2x(k)+\theta)|}{M\sin x(k)\sqrt{A+2B\cos(2x(k)+\theta)}}}+1)} \bigg) \nonumber \end{equation}

    \begin{equation} x_{k+1}=f(x_{k}) \end{equation}

    The work I did was above equations can be written as $x_{k+1}=f(x_{k})$ If,

    1) $f'(n) \neq 0$, then the sequence converges linearly to the fixed point $n$.

    2) $f'(n) = 0$, then the sequence converges at least quadratically to the fixed point $n$.

    But unfortunately first derivative is a messy equation and hard to prove

    so any idea to prove the convergence of the algorithm?

    • Harry
      Harry almost 10 years
      @user44197 $\pi/2 \leq x(i) \leq 3\pi/2$
    • Emanuele Paolini
      Emanuele Paolini almost 10 years
      The statements 1) and 2) are valid only if you already know that the sequence converges.
    • Hagen von Eitzen
      Hagen von Eitzen almost 10 years
      Even with computing $f'$, one would possibly need some restrictions on $A,B,\ldots$. I assume you have at least $D>0$, $|B|<\frac12A$ as precondiitons.
    • Harry
      Harry almost 10 years
      @HagenvonEitzen how do you say that
    • Harry
      Harry almost 10 years
      @EmanuelePaolini is that possible to show the solutions of $x$ or $y$ is in converging sequence?
    • hardmath
      hardmath almost 10 years
      The problem statement itself is confused. Variable $r$ is called an input, and is used in the formula for updating $x$, but $r$ is then referred to as the fixed point of something, presumably the iteration $x_{k+1} = f(x_k)$. Complaining that the "first derivative is a messy equation" must be seen in the light of not clearly defining $f(x)$.
    • Harry
      Harry almost 10 years
      @hardmath inputs are constants and given in the problem. $x$ and $y$ are the varaibles.
    • hardmath
      hardmath almost 10 years
      @Harry: What are we to make of "converges... to the fixed point $r$"?
    • Harry
      Harry almost 10 years
      @hardmath If we substitute the $y(i)$ value to second equation we can have $x(i+1)=f(x(i))$. That also indeed a messy equation
    • Harry
      Harry almost 10 years
      @hardmath please refers the question again. I did some modification, hope you can understand now. thanks
    • Harry
      Harry almost 10 years
      @hardmath now, is that clear to you?
    • hardmath
      hardmath almost 10 years
      @Harry: I've asked you about your claim that $r$ is "the fixed point" of your iteration, in addition to stating that $r$ is an input.
    • Harry
      Harry almost 10 years
      @hardmath Sorry for the confusion. I have changed it now.
  • Harry
    Harry almost 10 years
    $\pi/2 \leq x(i) \leq 3\pi/2$
  • Hagen von Eitzen
    Hagen von Eitzen almost 10 years
    @Harry In that case by the nature of arccos we have $\frac\pi2\le x(i)\le\pi$ for $i\ge 1$.
  • Harry
    Harry almost 10 years
    @HagenvonEitzen will that be helpful to prove the convergence?
  • Harry
    Harry almost 10 years
    @user44197 Brouwer's fixed point theorem can't apply in here