Numerical iteration method

Question

A function is given such that $ f(x)=0 $ and it can be written as $ x=g(x)$. Now, we have to determine the root of $f(x)$ (the value of x so that $ f(x)=0$). My textbook states that only when $|g’(a)|<1$ ( a is a random value of the function) , by using $x=a$ in interatio n method, the value of the root will be converging. In other words when $ |g’(a)|>1$, we can't determine the root because the value we get by using iterative method is diverging.

Is it true? For instance, $$f(x)=x^3-2x+3$$ $$g(x)=(2x-3)^\frac{1}{3}$$ By using $ x=1.6 $ in iteration method, the root is equal to $1.893$. But $g’(x)=1.949$ which isn't less than 1. I am wrong or the textbook is wrong?

Answer 1

What you claim the book says is certainly not true. The condition $|g'(a)|<1$ must hold not for a random number $a$, but for $a$ the root of the equation.

What the book probably explains is that if $|g'(x)|<1$ for all $x$, then you can pick at random the first point of the iteration, and the sequence of iterations will converge to the solution.

Answer 2

$g'(x)=\frac 23(2x-3)^{-2/3}$ and evaluated at $x=1.893$ gives $g'(1.893)=0.782757 \lt 1$

Answer 3

The most basic form of the theorem says that if $x_0$ is close enough to the root $x$ and $|g'(x)|<1$, then the fixed point iteration converges. This version doesn't say how close "close enough" is.

A slightly more precise version of the theorem says that if you have a neighborhood of $x$, call it $N$, such that for any $y \in N$ you have $|g'(y)|<1$, and $x_0 \in N$, then the fixed point iteration converges.

The condition $|g'(x)|<1$ is very nearly necessary. The only way for fixed point iteration to converge to $x$ without this condition is for one of the iterates of the sequence to be exactly equal to $x$, which almost never happens.

By contrast, the hypothesis of the second version of the theorem implies that in particular $|g'(x_0)|<1$. This condition is far from being necessary. For example, if $g(x)=\frac{x+1/x}{2}$, then the iteration converges for any $x_0 \neq 0$.