8. Interval Newton Methods
Society for Industrial and Applied Mathematics eBooks · 2009
In Chapter 6, we discussed iterative interval methods for solving equations in fixed-point form. Given an equation x=ƒ (x) , 8.1 we take an interval extension F of f (which is automatically inclusion isotonic if f is rational) and set up an iterative procedure of the form Xk+1 =F ( Xk ) ∩ Xk (k=0,1,2,…) . 8.2 If we start with an X0 such that F (X0) ⊆ X0, then (8.2) produces a nested sequence of intervals {Xk} convergent to an interval X* such that X* = F (X*) and X* ⊆ Xk for all k = 0, 1, 2, …. On a computer, the procedure can be halted when Xk+1 = Xk; using IA at a specific number of digits, this yields the narrowest interval possible (with that many digits) containing X*. The Krawczyk method, considered in Chapter 6 in the linear case, falls under the same general scheme as (8.2) and can be used to solve nonlinear systems of equations. More generally, interval Newton methods share properties with the Krawczyk method, can be implemented with iteration (8.2), and can be used to prove existence and uniqueness of a solution to a nonlinear system of equations in a given box, even though the interval Newton operator is not inclusion isotonic as is F in (8.2). We describe these methods below. 8.1 Newton's Method in One Dimension Our approach will be to initially develop Newton's method in its simplest form. Let f be a real-valued function of a real variable x, and suppose that f is continuously differentiable. By the mean value theorem, we can write ƒ (x) =ƒ (y) + ƒ′ (s) (x−y) 8.3 for some s between x and y. Now let [a, b] be an interval in which we seek a solution of the equation ƒ (x) =0. 8.4