ErrBnd Math. 128 B 28 Jan. 1997 Error Bounds Associated with Newton’s Iteration W. Kahan Math. Dept. Univ. of Calif. Berkeley CA 94720-3840 Suppose we seek a root z of the equation f(z) = o where f(x) is a continuously differentiable vector-valued function of the vector x in a normed space. Newton’s iteration replaces a guess x by x - f’(x)-1f(x) repeatedly in the hope of convergence to z . Is there some neighborhood around z within which iteration must converge to z ? And if convergence is assured, yet we cannot iterate forever; at some point we shall accept an approximate z0 despite f(z0) /= o . How close is z0 to z ? Claim 1: If f is twice differentiable about z , and if for ~~~~~~~~ some positive δ we find that || f’(x)-1f"(y) || < 2/δ as x and y range independently throughout a ball || x - z || < δ , then Newton’s iteration will converge to the root z from every starting point x in that ball. Moreover, convergence is at least quadratic. This claim merely reassures us that, under normal circumstances, Newton’s iteration will converge rapidly to a root z from any starting point close enough to z ; under normal circumstances f’(z)-1 does exist and f"(x) does stay bounded at all x near z , so a positive radius δ has to exist. Proof of Claim 1: According to Newton’s divided difference formula, f(z) = f(x) + f’(x)(z-x) + ∆|2f((z,x,x))(z-x)(z-x) where |∆2f is the second divided difference of f and, according to Hermite’s integral representation for divided differences, |∆2f((a,b,c)) = The uniformly weighted average of f"(y)/2 as y runs over the triangle whose vertices are a, b, c . If x lies in the ball ||x-z|| < δ , so does the degenerate triangle whose vertices are z, x, x , and therefore so does y , and therefore ||f’(x)-1f"(y)/2|| < 1/δ , and therefore ||f’(x)-1|∆2f((z,x,x))|| = || Average of f’(x)-1f"(y)/2 ...|| _< Average of ||f’(x)-1f"(y)/2|| ... < 1/δ . Newton’s iteration replaces x by New(x) = x - f’(x)-1f(x) ; by using Newton’s divided difference formula with f(z) = o we find New(x) - z = f’(x)-1|∆2f((z,x,x))(x-z)(x-z) , whence follows that ||New(x) - z||/δ _< ||f’(x)-1|∆2f((z,x,x))|| ||x-z||2/δ < (||x-z||/δ)2 . Therefore, starting the iteration xn+1 := New(xn) at any x0 in the ball leads to a sequence {xn} that stays in the ball and log(||xn+1-z||/δ) < 2 log(||xn-z||/δ) < ... < 2n+1 log(||x0-z||/δ) --> -∞ as n --> ∞ , as claimed. Who can wait until n --> ∞ ? Instead we shall accept some xn as good enough; call it z0 . How close is it to a desired root z ? 1ErrBnd Math. 128 B 28 Jan. 1997 Claim 2: If we can find some positive δ > || f’(x)-1f(z0) || ~~~~~~~~ throughout the ball || x - z0 || < δ , then at least one root z lies in that ball. Proof: Define a trajectory x = y(τ) by solving the initial value problem y(0) = z0 , d y(τ)/dτ = -f’(y(τ))-1f(y(τ)) for all τ _> 0 . Our first task is to discover for how large an interval 0 _< τ < T the trajectory stays inside the ball || y(τ) - z0 || < δ . We know that the trajectory exists inside the ball for some sufficiently small T > 0 ; let T be the largest value for which the trajectory stays inside the ball throughout 0 _< τ < T . Along the trajectory we find that d f(y(τ))/dτ = f’(y(τ)) dy(τ)/dτ = = f’(y(τ)) (-f’(y(τ))-1f(y(τ)) ) = -f(y(τ)) , whence follows that f(y(τ)) = e-τf(z0) . Therefore the length of the trajectory from τ = 0 up to τ = T is ∫oT || dy(τ)/dτ || dτ = ∫oT || f’(y(τ))-1f(y(τ)) || dτ = ∫oT || f’(y(τ))-1f(z0) || e-τ dτ < ∫oT δ e-τ dτ = (1 - e-T) δ < δ . If T were finite we would observe that || y(T) - z0 || could not exceed the length of the trajectory from τ = 0 to τ = T , so y(T) would have to lie strictly inside the ball, so T could not be the largest such value. Therefore the trajectory y(τ) lies in the ball for all τ _> 0 and has finite length less than the radius δ of the ball. Therefore a limit z exists inside the ball such that y(τ) --> z and f(y(τ)) = e-τf(z0) --> f(z) = o as τ --> ∞ . Thus is claim 2 proved. Comment 1 : The same conclusion could be drawn from a different hypothesis δ > ||f’(x)-1|| ||f(z0)|| . Besides being stronger (harder to satisfy), this hypothesis is affected by scaling; replacing f(x) by Lf(x) for any invertible linear operator L alters the stronger hypothesis but does not affect the root z , nor Newton’s iteration, nor the Claims proved above. And yet the stronger hypothesis is the one more often applied: Given a constant σ > ||f’(x)-1|| throughout a region known to be farther than δ from all roots other than z , we infer that ||z0-z|| < δ wherever ||f(z0)|| < δ/σ . Comment 2 : Claim 2 concerns "at least one root" instead of "just one root" because the ball may contain more than one root. For example, let x be a complex variable, so that ||x|| = |x| ; and let f(x) = 1 + exp(x) , so that z = _+ιπ . Choose δ = 2π and z0 = 3.13ι . Then f’(x)-1f(z0) = exp(-x)(1 + exp(3.13ι)) , so |f’(x)-1f(z0)| = 2 exp(-Re(x)) cos(1.565) .