# Exam question on fixed point iteration

I am solving the following exam problem.

Problem: An iterative scheme is given by $$x_{n+1}= \frac{1}{5}\left(16-\frac{12}{x_n} \right).$$ Such a scheme with suitable initial approximation $x_0$ will

(a) not converge (b) converge to $1.6$ (c) converge to $1.8$ (d) converge to $2$

My attempt. By defining $g(x) = 1/5(16-12/x )$, I found that fixed points of $g(x)$ are $2$ and $6/5$. Thus, given iterative scheme will converge either to $2$ or $6/5$.

Using fixed point theorem I need to find the interval [a, b] show that $g(x)\in [a, b]$ and is continuous and derivative of g(x) should exit on $(a, b)$. Further I have to check that $|g^{'}(x)| \leq r$, $r <1$.

First confusion: I want to know that how to find such interval $[a, b]$ satisfying these conditions?

Second confusion: Here we see that at fixed point $2$, $|g^{'}(2)| <1$. My confusion is then can we conclude that sequence $x_n$ will converge to $2$?

Thank you for your help.

• Fixed point iteration is guaranteed to converge on an interval [a,b] if $max(|g'(b)|,| g'(a) | ) < 1$. So if you are not given an interval [a,b], pick one that satisfies the above. – CivilSigma Aug 15 '15 at 4:24
• @CivilSigma How can convergence not depend on the derivative away from the endpoints? What if $g(x) = a + (x-b)^2$ near $x=b$ and $g(x) = b + (x-a)^2$ near $x=a$? Then fixed point iteration oscillates between $a$ and $b$ and never converges, but the derivative is zero at the endpoints. – Erick Wong Aug 19 '15 at 18:07
• @ErickWong Do you mean that the root is near $x=b$ for $g(x)=a + (x-b)^2$ , then we pick an interval, say , $[b-3, b+3]$ and iterate to find b. I don't get what you meant by defining two functions, do we seek the point of intersection as the root we want to find? – CivilSigma Aug 19 '15 at 18:34
• @CivilSigma I was defining just one function (in a small neighbourhood of $b$, $g(x)$ acts like one function, and in a small neighbourhood of $a$ it acts like the other function, and in between it could behave arbitrarily). My point is that such a function clearly satisfies $\max(|g'(b)|,|g'(a)|) < 1$ but fixed point iteration does not converge. I guess I should have written $b - (x-a)^2$ near $x=a$ so that the counterexample doesn't take values outside of $[a,b]$. – Erick Wong Aug 19 '15 at 19:37

The function $$g(x):={1\over5}\left(16-{12\over x}\right)$$ has the fixed points $2$ and ${5\over6}$. As $$g'(x)={12\over 5x^2}\tag{1}$$ we have $$\bigl|g'(2)\bigr|={3\over5}<1,\qquad \bigl|g'(5/6)\bigr|={5\over3}>1\ .$$ Therefore we try to prove that $2$ is an attractive fixed point. To this end we have to produce an open $x$-interval $J$ containing $2$, and an $r<1$ such that $\bigl|g'(x)\bigr|\leq r$ for all $x\in J$. Now from $(1)$ we obtain $$0<g'(x)\leq {12\over 5\cdot 1.6^2}={15\over16}<1\qquad(x\geq1.6 )\ .\tag{2}$$ This shows that we can take $J:=[1.6, \>\infty[\$ and $r={15\over16}$.

Claim: When $x_n\in J$ then $$|x_{n+1}-2|\leq{15\over16}\>|x_n-2|\ .$$ This implies that we can take any point $x_0\in J$ as starting point, and obtain $\lim_{n\to\infty}x_n=2$.

Proof: By the MVT there is a point $\xi$ between $2$ and $x_n$ such that $$|x_{n+1}-2|=\bigl|g(x_n)-g(2)\bigr|=\bigl|g'(\xi)\bigr|\>|x_n-2|\>\leq{15\over16}|x_n-2|\ ,$$ where we have made use of $(2)$, since $\xi\in J$.

Note that $g$ is a Moebius transformation with the two fixed points $2$ and ${5\over6}$. Introducing a new complex coordinate $z$ such that the two fixed points correpond to $z=0$ and $z=\infty$ "conjugates" $g$ into $$\hat g(z)={3\over5} z\qquad(z\in\bar{\mathbb C})\ .$$ From this we can conclude that any starting point $z_0\ne\infty$, resp. $x_0\ne{5\over6}$, will lead to the desired convergence.

• Thank you for a very nice explanation. – srijan Aug 16 '15 at 3:53

Think $\{x_n\}$ as a sequence.

$$x_{n+1}-x_n=-\frac{(x_n-2)(5x_n-6)}{5x_n}$$

When $x_n>2$ then clearly $x_{n+1}-x_n<0$ (check!), and when $x_n<6/5$ then also $x_{n+1}-x_n<0$ (check!). So the sequence $\{x_n\}$ is monotone decreasing , also it is bounded (check!). So it must be convergent. So your option (A) is incorrect.

Let, $\{x_n\}$ converges to $l$. Then,

$$l=\frac{1}{5}\left(16-\frac{12}{l}\right)$$From here, you will get either $l=2$ or $l=1.2$.

From your options , clearly (D) is correct.

## NOTE:

If 'converges to $2$' and 'converges to $1.2$' both options are given , then it is hard to detect that at which point it converges..In that case , it depends on the initial approximation $x_0$.

• Thanks for the answer. Is it not necessary to check monotonicity of $x_n$ in the interval $(6/5, 2)$? Please clear my doubt. – srijan Aug 16 '15 at 3:49
• Actually when $x_0>2$ then $\{x_n\}$ is strictly decreasing ..and when $x_0<6/5$ then $\{x_n\}$ is also strictly decreasing..You can easily show it...If NOt then tell me..I will improve the answer... – Empty Aug 16 '15 at 15:50
• @S.Panja-1729 Since $|g'(1.2)| = \tfrac53 > 1$, the fixed point at $1.2$ is repelling. – Erick Wong Aug 20 '15 at 2:53

If you calculate $g'(x)=\frac{12}{5x^2}$ so $$g'(x)<1 \qquad \iff x>\sqrt{\frac{12}{5}}$$ In particular if you take $[a,b]=[1,6 ; 3]$

Let $x_{n} =\dfrac 6 5 +\dfrac 4 {5y_{n}}$

Then the equation turns into $5y_{n+1}-3y_{n}-2=0 \Rightarrow y_{n}=c\cdot(\dfrac 3 5)^n +1 \Rightarrow \\$

$x_{n}=\dfrac 6 5 +\dfrac 4 {5c\cdot (\dfrac 3 5 )^n+5}$

Now obviously

$\lim_{n\rightarrow \infty }x_{n}=\lim_{n\rightarrow \infty }\dfrac 6 5 +\dfrac 4 {5c\cdot (\dfrac 3 5 )^n+5}=\dfrac 6 5+\dfrac 4 5=2$