# Intuition for convergence iterative formula

A convergence iterative formula , $g(x)$ , holding that $|g'(z)|<1$ .

In a case which the equation is given and I have to evaluate iterative formula in order to find its fixed point .

For example , given - $$\displaystyle x^2-5=0$$ it could be many iterative formula for that like - $$\displaystyle G_1(x) = \frac{5}{x}$$ $$\displaystyle G_2(x) = x+5-x^2$$ $$\displaystyle G_3(x) = \frac{x+5}{x+1}$$ but only $G_3(x)$ converges to fixed point ($2.230769$) .

How could I know whether I aiming to a convergence iterative formula ?

• – Mhenni Benghorbal Apr 2 '13 at 13:10
• How did you get $G_3(x).$? – Mhenni Benghorbal Apr 2 '13 at 13:36
• $x^2+x=x+5$ and so on ... – URL87 Apr 2 '13 at 13:44
• Note that, the condition $|f'(x)|<1$ is sufficient. – Mhenni Benghorbal Apr 2 '13 at 13:59

If $|G'(z)|\geq 1$ for $z$ near your solution, then letting $z_0$ be your first estimate, and letting $z_{n+1}=G(z_n)$. Assume the limit, $\lim_{n\to\infty} z_n = z_\infty$, exists, and hence that $z_\infty = G(z_\infty)$.

Find $\varepsilon$ so that $|G'(c)|\geq 1$ when $|c-z_\infty|<\varepsilon$.

Then there is an $N$ such that if $n\geq N$ $|z_n-z_\infty|<\varepsilon$.

But we see by the mean value theorem that:

$$|z_{N+1}-z_\infty| = |G(z_N)-G(z_\infty)|=|G(c)|\cdot |z_N-z_\infty|\geq |z_N-z_\infty|$$

More generally, $|z_{N+k}-z_\infty|\geq |z_N-z_\infty|$ for all $k$.

This basically means that we stop getting closer to $z_\infty$ once $|G'(c)|\geq 1$. The only way this series can converge is if $z_n=z_\infty$ for some $z_n$ - that is, if it "jumps" to the exact solution.

This argument doesn't ensure that we get convergence when $G'(c)<1$, but it does show why you need it for convergence.

On the other hand if $|G'(z_\infty)|<1$ and $G'$ is continuous, then there is some $z_0$ that can be used to start the process with this $G$.

Basically, you find that if $|G'(z)|<1-\epsilon$ for $|z-z_\infty|<\delta$ then $G'$ is a contraction. around $z_\infty$.

That might seem like cheating, since we haven't found $z_\infty$. But we often have an estimate. For example, in your case of $G_3(x)=\frac{x+5}{x+1}$, we know $2<z_\infty<3$ and we know that $G_3'(x) = \frac{-4}{(1+x)^2}$. Showing that $G_3'(z_\infty)$ is between $\frac{-4}{9}$ and $\frac{-4}{16}$.

• I ask about how to evaluate a "good" $G$ , not which $z_0$ start with him . – URL87 Apr 2 '13 at 13:35
• I literally said nothing about a good $z_0$. The point of the argument above is about conditions on $G'$ – Thomas Andrews Apr 2 '13 at 16:10