[alogo] Newton's iterative procedure

Theorem Let the function F(x) be defined in the closed interval D = [a,b], where it satisfies:
(i) F is differentiable at least up to order 3,
(ii) F has a simple root z in (a,b) i.e. F(z)=0, and F'(z) is different from zero.
Then there is an r>0 such that for every start-value x0 in the interval (z-r, z+r) the sequence defined through
xn+1 = xn - F(xn)/F'(xn)
converges to z.
The convergence is at least of order two.
We say that the convergence is of order k (integer), when the limit of |xn+1-z|/|xn-z|k exists and is a constant L>=0.

[0_0] [0_1] [0_2] [0_3]
[1_0] [1_1] [1_2] [1_3]
[2_0] [2_1] [2_2] [2_3]

The picture above illustrates Newton's method in the case of a quadratic function. xn+1 is the intersection point of the tangent at xn with the x-axis. The expression F(xn)/F'(xn) is called subtangent and gives the (signed) length xn-xn+1. In this particular case the sequence starting at an arbitrary x0 different from x*=-b/(2*a), which defines the min/max of the function, converges to the function's root lying on the same x-half-axis (defined by x*) with x0. Thus, the sequence converges in a much wider set than the one guaranteed by the theorem.

This method can be applied to obtain quickly the square root of a number. In fact taking F(x) = x2 - a as the basic function, the corresponding expression x - F(x)/F'(x) is 0.5*(x+(a/x)). The sequence with x0 = a (assumed to be positive) and xn+1 = 0.5*(xn+(a/xn)) converges rapidly to the square root of a.
More general, the sequence with x0 = a and xn+1 =((m-1)*xn+(a/(xnm-1)))/m converges rapidly to the m-th root of a (assumed to be positive).

See Also

Iterative.html
NewtonIterative2.html

References

Gisela-Jordan Engeln und Fritz Reutter Numerische Mathematik fuer Ingenieure Mannheim B.I.-Wissenschaftsverlag 1978, p. 43

Return to Gallery

Produced with EucliDraw©