Numerical solutions of equations

Every one knows that the solution to x² - 2 = 0, x > 0 is $x = \sqrt{2}$, but in some sense this is useless, as we generally want to know decimal approximations of numbers, as we have been trained from childhood to think of numbers as decimals. How then can we go about solving this problem in such as way as to produce a good decimal approximation of the solution? One way is bisection. We will discuss another way, called Newton's Method, which relies on the observation that it is always possible to solve an equation of the form -B = m(x-A) for x in terms B, A, and m using only addition, subtraction, multiplication and division. Therefore, if A, B and m are rational numbers, so is x.

To solve the problem at hand, put $f:(0,\infty)\rightarrow(0,\infty)$, f(x) = x² - 2 and observe that since f is continuous and f(1) < 0 < f(2) that f(x) = 0 has a solution somewhere between 1 and 2. We find an equation for the tangent line to y = f(x) at (2,2): y - 2 = 4(x-2). We do so because we believe that for $x\in [1,2]$ the tangent line lies near the graph of y = f(x).

We then find the x-intercept of the tangent line by solving 0-2 = 4(x-2) for x, which yields x = 3/2, the same value as bisection. Now we repeat the process replacing the point (2,2) with $(3/2,f(3/2)) \equiv (3/2,1/4)$. An equation of the tangent line to y = f(x) at (3/2,1/4) is y - (1/4) = 3(x-(3/2)). The x-intercept of this line is $x= 17/12 \approx 1.41666666$,while bisection gives x = 1.25. We may repeat this process as often as we like, although after a short while, the values it yields will not appear any different when represented as decimals and rounded to 8 places. In fact, here is what is happening. Suppose we have arrived after N repetitions at a value X_N. We construct the tangent line at $(X_N,f(X_N))\equiv (X_N,X_N^2-2)$. An equation for this tangent line is y - (X_N²-2) = 2X_N(x-X_N). To find the x-intercept, set y=0 and solve -(X_N² -2) = 2(X_N)(x-X_N) for x to get

$$x = X_N - \frac{X_N^2 - 2}{2X_N} = \frac{X_N^2 + 2}{2X_N}$$

and call this new x-intercept X_N+1. Now it is simple to compute the result of repeated apply our rule.

$$\begin{array} {ccccccccc} {\rm Trials} & 1 & 2 & 3 & 4 & 5 &... ...5& 1.41666667 &1.41421568 & 1.41421356 & 1.41421356 \end{array}$$

Note that $(1.41421365)^2 - 2 \approx 2\times 10^{-9}$ while $(1.40625)^2 - 2 \approx -2\times 10^{-2}$.

There was nothing special about solving x² -2 = 0, x > 0 in this way except that every tangent line had a non-zero slope and all tangent lines were on the same side of the graph. If either of these conditions fail to exist, the method may fail by giving an equation where there is no x to solve for, or by not giving a sequence of approximations which get close to the true solution of the equation. Assuming that these problems do not plague us we can, by following the procedure above, get

$$X_{NEW} = X_{OLD} - \frac{f(X_{OLD})}{f'(X_{OLD})}$$

for a general procedure.