Finding Square Roots Using Newton’s Method
Let A > 0 be a positive real number. We want to show that there is a real number x with x^2 = A. We already know that for many real numbers, such as A = 2, there is no rational number x with this property. Formally, let f(x) : = x^2 − A. We want to solve the equation f(x) = 0.
Newton gave a useful general recipe for solving equations ofthe form f(x) = 0. Say we have some approximation x(k) to a solution. He showed how to get a better approximation x(k+1). It works most of the time if your approximation is close enough to the solution.
Here’s the procedure. Go to the point ( x(k), f( x(k) ) ) and find the tangent line. Its equation is
The next approximation,x(k+1), is where this tangent line crosses the x axis.
Applied to compute square roots, so f(x) : = x^2 − A, this gives
From this, by simple algebra we find that
Pick some x(0) so that x(0)^2 > A. then equation (2) above shows that subsequent approxi-mationsx(1),x(2), . . . , are monotone decreasing. Equation (2) then shows thatthe sequencex(1) ≥ x(2) ≥ x(3)≥. . ., is monotone decreasing and non-negative. By the monotone conver-gence property, it thus converges to some limitx.
I claim thatx2=A. Rewrite (2) as
and let k -> ∞, since x(k+1)−x(k)→0 and x(k) is bounded, this is obvious.
We now know that A^(1/2) exists as a real number. then it is simple to use (1) to verify that
Equation (3) measures the error x(k+1)−A^(1/2). It shows that the error at the next step is the square of the error in the previous step. Thus, if the error at some step is roughly 10^(-6) (so 6 decimal places), then at the next step the error is roughly 10^(−12)(so 12 decimal places).
Example:To 20 decimal places,7^(1/2) = 2.6457513110645905905. Let’s see what Newton’smethod gives with the initial approximation x(0)= 3:
x1= 2.6666666666666666666
x2= 2.6458333333333333333
x3= 2.6457513123359580052
x4= 2.6457513110645905908
Remarkable accuracy.
Example 2:
Find the root of the equation x^2−4x−7=0 , near x=5 to the nearest thousandth.
We have our x0=5. In order to use Newton's method, we also need to know the derivative of f. In this case, f(x) = x^2 - 4x - 7, and f′(x)=2x−4.
Using Newton's method, we get the following sequence of approximations:
We can stop now, because the thousandth and ten-thousandth digits of x2 and x3 are the same. If we were to continue, they would remain the same because we have gotten sufficiently close to the root:
Our final answer is therefore 5.317.
References: