Newton’s Method

Let’s recall how Newton’s method works. Suppose we’re looking for a root of the function f : ℝ^{n} → ℝ^{n}, and for convenience let’s assume f is differentiable everywhere. Make an initial guess a_{0}. Then we linearize the system: approximate the graph of f by an affine function (whose linear part equals the derivative of f). We get a kind of generalized “point-slope form”, as in

y − f(a_{0}) = [Df(a_{0})](x − a_{0}).

We want to solve this when y = 0. Let’s assume that [Df(a_{0})] is invertible, which it will be most of the time. Then the solution of the above equation is

x = a_{0} − [Df(a_{0}]^{−1}f(a_{0}).

This becomes our next guess a_{1}. Then we continue inductively, constructing the sequence {a_{0}, a_{1}, a_{2}, … }, which we hope will converge to a root of f. Notice that, if a_{i} is a root of f, then a_{i+1} = a_{i} − [Df(a_{i})]^{−1}0 = a_{i}, and the sequence stabilizes.

If our initial guess was good enough, and other conditions are right, then we will generate a sequence that converges to a root. Just how good the conditions have to be are described by Kantorovich’s Theorem, which you’ll discuss in class tomorrow.

Let’s do an example to settle this process in our heads.

Exercise 2.7.7. We have the system of equations

\{ \begin{matrix}cos x + y & = 1.1 \\ x + cos(x + y) & = 0.9 \end{matrix} .

We are told to apply Newton’s method starting at a_{0} = \binom{0}{0}. A solution of the system is a root of the function f : ℝ^{2} → ℝ^{2} defined by

f\binom{x}{y} = \binom{cos x + y − 1.1}{x + cos(x + y) − 0.9}.

This function is certainly C^{1}, so we compute the derivative at a point \binom{x}{y}:

[Df\binom{x}{y}] = [\begin{matrix}− sin x & 1 \\ 1 − sin(x + y) & − sin(x + y) \end{matrix}] .

We know how to invert any 2 × 2 matrix, so we could write a general expression for a_{i+1} in terms of a_{i}, but we’ll just do it at the given initial point a_{0}. Remembering that sin 0 = 0 and cos 0 = 1, we compute that

a_{1} = \binom{0}{0} − [\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}]^{−1} \binom{−0.1}{0.1} = − [\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}] \binom{−0.1}{0.1} = \binom{−0.1}{0.1}.

We are now told to continue the process for three more iterations. Unlike row reduction, Newton’s method is not an algorithm that you understand better through doing it by hand. Thus we can apply a computer program (I used a Maple worksheet I found online) to get the next few elements of the sequence:

a_{2} = \binom{−0.1}{0.104995834721974234},
a_{3} = \binom{−0.0999874644705826684}{0.104994583257243025},
a_{4} = \binom{−0.0999874644062369407}{0.104994583328997234}.

The actual solution (as given by Maple) is approximately

a = \binom{−0.0999874644062369406}{0.104994583328997234}.

Just another example that, when Newton’s method works, it works extremely well.

Complex square roots. This is an example to look at the behavior of Newton’s method, rather than to actually solve a difficult nonlinear system. We want to see where we can start in the complex plane to find square roots of, say, −1. That is, we have the equation z^{2} = −1, or z^{2} + 1 = 0, which we rewrite in terms of real variables as

f\binom{x}{y} = \binom{x^{2} − y^{2} + 1}{2xy} = \binom{0}{0}.

We already know the derivative matrix, from an earlier homework assignment:

[Df\binom{x}{y}] = [\begin{matrix}2x & −2y \\ 2y & 2x \end{matrix}] ,

and this is easy to invert:

[Df\binom{x}{y}]^{−1} = \frac{1}{2(x^{2} + y^{2})} [\begin{matrix}x & y \\ −y & x \end{matrix}] .

So the general expression for a_{i+1} in terms of a_{i} is

a_{i+1} = \binom{x_{i}}{y_{i}} − \frac{1}{2(x_{i}^{2} + y_{i}^{2})} [\begin{matrix}x_{i} & y_{i} \\ −y_{i} & x_{i} \end{matrix}] \binom{x_{i}^{2} − y_{i}^{2} + 1}{2x_{i}y_{i}} = \frac{1}{2(x_{i}^{2} + y_{i}^{2})}\binom{x_{i}(x_{i}^{2} + y_{i}^{2} − 1)}{y_{i}(x_{i}^{2} + y_{i}^{2} + 1)}.

With some study of this equation, you’ll observe three kinds of behavior:

• If you start with a point that has y > 0, you’ll stay in the upper half-plane, and eventually converge to the point i.

• If you start with a point that has y < 0, you’ll stay in the lower half-plane, and eventually converge to the point −i.

• If you start with a point that has y = 0 (i.e., a real number in ℂ), then you’ll stay on

the real axis, never converging to either i nor −i. This situation is generic for square roots in ℂ. The two square roots are opposites

of each other, and determine the perpendicular bisector of the segment between them. Points on either side of the perpendicular bisector converge to the root on that side, and points on the perpendicular bisector don’t converge. In fact, this is the situation for any quadratic polynomial in z. The situation for higher-power polynomials is quite different, and extremely complicated. The result is beautiful pictures (such as on the cover of the textbook), which are still fueling a lot of research.