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 ?

  • $\begingroup$ A related problem. $\endgroup$ – Mhenni Benghorbal Apr 2 '13 at 13:10
  • $\begingroup$ How did you get $G_3(x).$? $\endgroup$ – Mhenni Benghorbal Apr 2 '13 at 13:36
  • $\begingroup$ $x^2+x=x+5$ and so on ... $\endgroup$ – URL87 Apr 2 '13 at 13:44
  • $\begingroup$ Note that, the condition $|f'(x)|<1 $ is sufficient. $\endgroup$ – 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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.