## Posts tagged ‘Newton method’

### Rational approximations of √2

Introducing undergraduates to rational approximations of √2 can be an opportunity to insidiously tell them about many parts of mathematics they certainly don’t want to hear about. In a less pessimistic way, I would say this is a nice way to illustrate the use of several theories in abstract mathematics.

First, you may want to tell them it is not a rational number, which could be easy, unless they never heard about factoring integers.

Then, you could use classical sequences from high school classes: it is easy to check that iterating $u_{n+1} = \frac{u_n+2}{u_n+1}$ converges to ±√2, and setting $U_n = \frac{u_n-\sqrt 2}{u_n+\sqrt 2}$ they will even be able to give an explicit formula with a geometric sequence. There is of course a well-known algorithm which speeds up considerably the computation : Newton’s method. This can be illustrated geometrically by drawing the graph of a function having √2 as a root (for example $x \mapsto x^2-2$):

1. take a rough approximation, such as x=1
2. imagine the function is affine (replacing the graph by its tangent)
3. use the approximation of the function to calculate an approximation of the solution
4. use this newly found rough solution to iterate from step 1

This method requires iterating $v_{n+1} = \frac 1 2 (v_n + 2/v_n)$, and converges considerably faster. Both methods yield sequences of rational numbers converging to √2, so should be considered as methods to obtain fractional numbers giving good approximations of √2. (more…)