Newton, or the machine for building high-performing sequences --------------------------------------------
Newton proposed his algorithm around 1669 in De analysi per aequationes numero terminorum infinitas, and published it in 1671. The assumptions needed to apply the method are fairly limited: if f is continuous, twice differentiable and its first and second derivatives are continuous around the solution f(ξ)=0,f(\xi)=0, and if, moreover, the first derivative does not vanish at ξ\xi, then the sequence defined by
xn+1=xn−f(xn)/f′(xn)x_{n+1}=x_n-f(x_n)/f'(x_n)
converges to ξ\xi.
Since the derivative f '(x) measures the slope of the tangent to the graph of f at x, the basic idea is to replace an estimate of the solution xi with the intersection of the tangent at *xi* to the graph and the x-axis. This estimate is always closer to the solution! Newton's method has many advantages: its simplicity, its ease of implementation, its extremely fast convergence, and its numerical stability.
Newton's method: computational details ---------------------------------------
• Heron's method can be derived from Newton's method:
Define f(x)=x2−a.f(x)=x^2-a. We seek the solution of f (x) = 0; the solution is indeed a.\sqrt{a}.
Now, f′(x)=2xf'(x)=2x and
f(x)f′(x)=x2−a2x=x2−a2x.\frac{f(x)}{f'(x)}=\frac{x^2-a}{2x}=\frac{x}{2}-\frac{a}{2x}.
We therefore set
xn+1=xn−f(xn)f′(xn)=xn−xn2+a2xn=xn2+a2xn=12(xn−axn).x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{x_n}{2}+\frac{a}{2x_n}=\frac{x_n}{2}+\frac{a}{2x_n}=\frac{1}{2}(x_n-\frac{a}{x_n}).
And there you have it!
• We can dispense with division in Newton's method:
Set f(x)=1/x−af(x)=1/x-a. It follows that f′(x)=−1/x2f'(x)=-1/x^2. We deduce that
f(x)f′(x)=1x−a−1x2=−x2(1x−a)=−x2+ax2.\frac{f(x)}{f'(x)}=\frac{\frac{1}{x}-a }{-\frac{1}{x^2}}=-x^2(\frac{1}{x}-a)=-x^2+ax^2.
We are thus led to define
xn+1=xn−f(xn)f′(xn)=xn+xn−axn2=2xn−axn2.x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n+x_n-ax^2_n=2x_n-ax^2_n.
The division has disappeared!
Calculating roots by hand -------------------------------
Since the advent of calculators, square roots can be computed instantly. Before that, people used a method resembling long division, one that earlier generations still learned in school.
We start by grouping the digits of the radicand (the number whose square root we are seeking) in twos, starting from the right. In our example, we want to find the square root of 163. The first group is 63, the next is 1. We look for the largest integer whose square is less than or equal to the group on the left. That is 1, since 12 = 1 is indeed less than or equal to 1, and 22 = 4 > 1. So a = 1; we write it to the right of the vertical bar. Subtract *a2* from our group, giving 1 – 1 = 0. Bring down the next two-digit group.
We now look for the largest integer b such that [2a]b × b is less than 63 (where the number [2a]b is formed by appending b to 2a).
We find b = 2. Subtract [2a]b × b (here 44) from the previous remainder 63; we get 19. Place our b (equal to 2) to the right of the 1. There is no longer any two-digit group left to bring down, so to compute a decimal digit, we bring down a group of two zeros after 19. As with b, now look for the largest integer c such that [2ab]c × c is less than 1,900.
We find c = 7. Subtract 1,729 from 1,900, leaving 171.
Using the same method, find the second decimal digit d. It will be the largest integer such that [2abc]d × d is less than 17,100 (equal to the remainder 171 with a group of two zeros added). We find d = 6. We can go on like this for as long as needed: the decimal digits fall one after another, drop by drop. In the end, 12,76<163<12,7712,76 <\sqrt{163} < 12,77.
This manual process is lengthy and requires making no computational errors (the numbers involved quickly become gigantic), but it is remarkably effective!