Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can I use fixed point iteration to solve $x^2 = 3$ using $g(x) = x^2 + x - 3$ to find the numerical value of the solution $x = +\sqrt{3}$. What happens? Then I use $g(x) = (x + 3/x)/2$. For which values of $x_0$ is this guaranteed to converge to the solution $x = +\sqrt{3}$?

share|improve this question
    
Have you heard of Newton's method? –  Siméon Sep 17 '13 at 20:46
    
Yes and I don't think we should use Newton's method here as it is just a fixed point iteration problem. –  user87274 Sep 17 '13 at 20:50
add comment

1 Answer

up vote 0 down vote accepted

First question: . Let $g(x)=x^2+x-3$, and consider solving $g(x)=x$ by Fixed Point Iteration.

If we are lucky enough to choose as our first "guess" $x_0$ the value $x_0=\sqrt{3}$, there will be trivial convergence. There are other values of $x_0$ such that the $n$-th iterate $x_n$ just happens to be exactly $\sqrt{3}$ for some $n$. But we show that there cannot be approach to $\sqrt{3}$.

Note that $\sqrt{3}$ is between $1$ and $2$. Suppose that the $n$-th iterate $x_n$ is between $1$ and $2$, and not exactly equal to $\sqrt{3}$. By the Mean Value Theorem, $$\frac{|x_{n+1}-\sqrt{3}|}{|x_n-\sqrt{3}|}= \frac{|g(x_n)-\sqrt{3}|}{|x_n-\sqrt{3}|}=|f'(c)|$$ for some $c$ between $1$ and $2$. Since $g'(x)=2x+1$, we have $|g'(c)|\gt 3$ in the interval $(1,2)$.

This says that $x_{n+1}$ is at least $3$ times further from $\sqrt{3}$ than $x_n$ is.

Remark: The point $x=\sqrt{3}$ is a fixed point of $g(x)=x$, but because the absolute value of $g'(x)$ is "big" near $x=\sqrt{3}$, the point $x=\sqrt{3}$ is a repelling fixed point.

Second question: We will be brief, leaving a number of details to you. Obviously a negative $x_0$ is no good, for then $x_n$ is always negative. Let $$g(x)=\frac{x+\frac{3}{x}}{2}.$$ Then $$g'(x)=-\frac{3}{2x^2}.$$ If $x\gt \sqrt{3}$, then $|g'(x)|\lt \frac{1}{2}$.

It follows by a Mean Value Theorem argument that if $x_0\gt \sqrt{3}$, then the fixed point iteration will converge to $\sqrt{3}$.

But actually any positive number $x_0$ will do the job. For if $0\lt x_0\le \sqrt{3}$, then $x_1\gt \sqrt{3}$, so we get convergence.

The rate of convergence is fairly quick: when we are near $\sqrt{3}$, the error gets multiplied by a factor $\lt 1/2$ with each iteration.

share|improve this answer
    
What's a repelling fixed point? –  user87274 Sep 17 '13 at 22:36
    
It means that if you start close to the fixed point (but not at the fixed point) the next iteration leaves you further away. So the fixed point resists being approached. For the second problem, the fixed point is an attracting fixed point, if you get close then the next iteration leaves you (substantially) closer. Attracting is good, repelling is bad. Attracting is connected with absolute value of the derivative being less than $1$. There are nice pictures of the process in some books. –  André Nicolas Sep 17 '13 at 22:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.