2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – CivilSigma Aug 15 '15 at 4:24
  • $\begingroup$ @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. $\endgroup$ – Erick Wong Aug 19 '15 at 18:07
  • $\begingroup$ @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? $\endgroup$ – CivilSigma Aug 19 '15 at 18:34
  • $\begingroup$ @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]$. $\endgroup$ – Erick Wong Aug 19 '15 at 19:37
3
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for a very nice explanation. $\endgroup$ – srijan Aug 16 '15 at 3:53
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Is it not necessary to check monotonicity of $x_n$ in the interval $(6/5, 2)$? Please clear my doubt. $\endgroup$ – srijan Aug 16 '15 at 3:49
  • $\begingroup$ 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... $\endgroup$ – Empty Aug 16 '15 at 15:50
  • $\begingroup$ @S.Panja-1729 Since $|g'(1.2)| = \tfrac53 > 1$, the fixed point at $1.2$ is repelling. $\endgroup$ – Erick Wong Aug 20 '15 at 2:53
0
$\begingroup$

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]$

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

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.