1

How can I find the approximate value of $\sqrt{2}$ by using the fixed point iteration? I have tried

$x-\sqrt{2}=0$,

$x^2=2$,

$x^2-2+x=x$,

$g(x)=x^2-2+x$,

$g\prime(x)=2x+1$

And i choose $x_0=-\frac{1}{2}$.

But i cant find the approximate value correctly. Where am i wrong?

Raio
  • 1,537

3 Answers3

2

A nice one is $g(x)=x$ where $g(x)=\frac{x}{2}+\frac{1}{x}$.

Remark: The problem with $g(x)=x^2-2+x$ is precisely the derivative. As you computed, we have $g'(x)=2x+1$, and therefore near the root the derivative has absolute value (quite a bit) bigger than $1$. This means that even though $\sqrt{2}$ is a fixed point of $g$, it is a fixed point that repels. If at a certain stage we are close to $\sqrt{2}$, at the next stage we are quite a bit further away.

The really nice thing about the $g(x)$ of the answer is that $g'(\sqrt{2})=0$. This means that the nearer we are to $\sqrt{2}$, the faster we approach $\sqrt{2}$.

There are plenty of possibilities other than the one suggested. But do make sure your choice has derivative with absolute value $\lt 1$ for $x$ near $\sqrt{2}$. And whatever your choice is, one should start with $x_0$ that is not too far from $\sqrt{2}$. A "good" fixed point iteration may not converge, or may converge to the wrong thing, if $x_0$ is far from the root we are looking for.

André Nicolas
  • 507,029
  • 1
    This is the obvious choice. Here's a strange one ;-) $$f(x)=\frac{x(x^2+6)}{3x^2+2}$$ – WimC Sep 08 '14 at 19:14
  • @WimC, I just saw your comment after posting an answer (which took me a while to compose) elaborating on alternatives. – Barry Cipra Sep 08 '14 at 20:15
  • @AndreNicolas: By mistake I downvoted your answer thinking you were talking about the $f(x)=\sqrt{2}-x$ function the OP has at the title. I flagged it now so that the moderator reverses my downvote. My apologies for the mistake. –  Sep 08 '14 at 20:55
  • @ioannisgalidakis: No problem! I did not even see the title, was using the conventional general $f$. – André Nicolas Sep 08 '14 at 21:02
  • @BarryCipra My function has a small extra trick up its sleeve that you may not have noticed. Give it a spin. – WimC Sep 08 '14 at 21:03
  • @WimC, I think I know what trick you've got in mind. I'll counter with $(3x^5-20x^3+60x)/32$. – Barry Cipra Sep 08 '14 at 21:08
  • @WimC: The $\frac{x(x^2+6)}{3x^2+2}$ is nice, three, when there is stability, is better than two. – André Nicolas Sep 08 '14 at 21:22
  • @WimC and André, for the sake of the OP (and other readers), we should probably stop being cryptic. You get good convergence if the derivative is $0$ at the fixed point. You get better convergence if the second derivative is also $0$, which is easy to verify in my example. But in WimC's case, the third derivative is $0$ at $\sqrt2$ as well. – Barry Cipra Sep 08 '14 at 21:51
  • Just so I have it written down somewhere, $(280x-140x^3+42x^5-5x^7)/128$ has $\sqrt2$ as a fixed point and its first three derivatives equal to $0$ there. – Barry Cipra Sep 08 '14 at 22:23
  • And for arbitrary precision binary arithmetic, with efficient polynomial evaluation, the cost per iteration is on the low side. – André Nicolas Sep 08 '14 at 22:27
1

In general, you can produce a function $g(x)$ with $\sqrt2$ as a fixed point by letting

$$g(x)=x+(x^2-2)h(x)$$

with pretty much any function $h(x)$. However, as André Nicolas pointed out, if you want $\sqrt2$ to be an attracting fixed point for $g$, which is what you need if you want to approximate $\sqrt2$ by iterating the function $g$, then you need $|g'(\sqrt2)|\lt1$. Moreover, as André pointed out, you're really best off if $g'(\sqrt2)=0$. Since

$$g'(x)=1+2xh(x)+(x^2-2)h'(x)$$

we have

$$g'(\sqrt2)=1+2\sqrt2h(\sqrt2)$$

It's convenient at this point to take $h$ to have the form $h(x)=cxk(x^2)$, because then we have

$$g'(\sqrt2)=1+4ck(2)$$

in which case we can get $g'(\sqrt2)=0$ by letting $c=-1/(4k(2))$ and all we need is to choose a function $k(x)$ such that $k(2)\not=0$. The simplest such function is $k(x)\equiv1$, which gives $c=-1/4$ and thus

$$g(x)=x-{1\over4}x(x^2-2)={6x-x^3\over4}$$

Alternatively, $k(x)=1/x$ leads to $h(x)=-1/(2x)$ which gives

$$g(x)=x-{1\over2x}(x^2-2)={x\over2}+{1\over x}$$

as in André's answer. But as I said, you can really let $k$ be anything you like (as long as $k(2)\not=0$) and get a function $g$ that has $\sqrt2$ as an attracting fixed point.

Finally, as André also pointed out, whatever $g$ you use, you need to start close enough to $\sqrt2$ so that you're within the "basin of attraction" of the fixed point. I'll leave that for someone else to discuss in detail, but merely note that $x_0=1$ works as a starting point for either $(6x-x^3)/4$ or $x/2+1/x$ as the function to be iterated.

Barry Cipra
  • 79,832
0

You cannot use fixed point iteration to approximate $\sqrt{2}$ using this map (Meaning the map the OP has at the title: $f(x)=\sqrt{2}-x$).

The fixed point of the map is found by setting:

$$f(x)=x\implies x_0=\frac{\sqrt{2}}{2}$$

But this map satisfies:

$$|f'(x)|_{x=x_0}=1$$

consequently the fixed point ($x_0$) is $\mathbf{neutral}$, so in particular i's not an attractor, which means your iteration in an open interval $(x_0-\epsilon,x_0+\epsilon)$ around $x_0$ will fail.

So you need to look at a different map, like those pointed out by Nicolas and Cipra.