[Math] how to show the convergence of an algorithm

algorithmsconvergence-divergencenumerical methodsrecursive algorithms

I have two unknown variables x and y which are non linear equations to be solved.

\begin{eqnarray}
y=\frac {|\sin(2x+\theta)|}{\sin x\sqrt{A+2B\cos(2x+\theta)}} \nonumber \\
x=\arccos\bigg( -\frac{1}{2(Dr^{y/M}+1)} \bigg)
\end{eqnarray}

I have developed some iterative process algorithm to calculate the answer.

simulations show that the algorithm converges, but the problem is how do I prove this mathematically. What techniques need to be used?

Algorithm:

given $x(0)=2\pi/3$ and $\epsilon=10^{-6}$ and $A,B,D,r,M,\theta$ are constants

i=0

  1. compute $y$:
    \begin{equation}
    y(i)=\frac {|\sin(2x(i)+\theta)|}{\sin x(i)\sqrt{A+2B\cos(2x(i)+\theta)}} \nonumber
    \end{equation}

  2. update $x$:
    \begin{equation}
    x(i+1)=\arccos\bigg( -\frac{1}{2(Dr^{y(i)/M}+1)} \bigg) \nonumber
    \end{equation}

    i=i+1

repeat till $|x(i+1)-x(i) |<\epsilon$

Best Answer

This is a fixed point iteration, which, given an equation $x=f(x)$ you want to solve for $x$, seeks the solution by an iterative process $x_{k+1}=f(x_k)$ starting from some initial guess $x_0$.

A usual approach to determine if the fixed point iteration converges is to verify whether $f$ is Lipschitz continuous with the Lipschitz constant smaller than one.

Related Question