From one equation to several
The unit on bracketing and Newton's method solves one equation by replacing with its tangent line. Many problems have several unknowns and as many equations, for instance the intersection of two curves. The same idea applies: replace the map by its best linear approximation at the current point, and solve the resulting linear system. The new computational ingredient is the solution of a linear system at every step, so this unit also uses the units on elimination and factorization. We prove a local quadratic convergence theorem and show how the hypotheses can fail.
Definitions
Definition 2.5.1
(Jacobian and Newton step)
Let be continuously differentiable on an open set , with components . Its Jacobian is the matrix with entries . A root is a point with . The linear approximation of at is . Newton's method sets this approximation to zero:
The step is defined exactly when is nonsingular; one never forms explicitly, but solves the system, for example by LU factorization with pivoting. For this is the familiar . Throughout, is a vector norm and the induced matrix norm.
Local quadratic convergence
Lemma 2.5.2
(Inverse of a perturbed invertible matrix)
Let be invertible and . Then is invertible and
Proof
(Factor out the unperturbed matrix)
Put , so . The series converges in norm, and telescoping shows that its sum is , with norm at most . Since , the product is the inverse of , and its norm is at most .
Theorem 2.5.3
(Local quadratic convergence of Newton’s method)
Let be continuously differentiable, , and nonsingular, with . Suppose that on a ball the Jacobian is Lipschitz: . Let . If , then every is nonsingular, all iterates stay in the ball, and
In particular , with quadratic convergence.
Proof
(Linearization error against a uniform inverse bound)
Let and . First, , so with . By the Neumann-series (perturbation) lemma is invertible and . Now, with the Newton update,
By the fundamental theorem of calculus along the segment, , so the bracket equals . Its norm is at most . Therefore . Since , we have and so . The argument applies at every step, and the errors tend to .
Proof X-ray
One radius doing two jobs
The proof rests on writing the new error as applied to a linearization error. The bracket is what the tangent model gets wrong, and the Lipschitz condition makes it quadratic, . The ball is convex, so the segment from to stays where that condition holds. Nonsingularity of is used only through , and the lemma converts it into the uniform bound near the root.
The radius does two jobs. It makes , so the lemma applies, and it makes , so the new error is at most half the old one. The second job keeps in the ball, which is what lets the same estimate be applied at the next step: the induction closes. If is singular, is undefined and no such radius exists; the singular-Jacobian example below shows the quadratic rate is then genuinely lost.
Two consequences are important. Quadratic convergence means the number of correct digits roughly doubles per step once the iterate is close. And the theorem is local: it says nothing about arbitrary starting points.
Worked examples
Worked example 2.5.4
(A circle and a hyperbola)
Solve , which has the root . Here with determinant . Start at .
Step 1. and with determinant . Solve : , i.e. . So .
Step 2. , , and the solve gives .
The sup-norm errors are and, for the next iterate, about : once the iterate is close, the number of correct digits roughly doubles per step, consistent with the theorem.
Worked example 2.5.5
(A singular Jacobian at the root)
For the only root is , where is singular. The Newton step for the first component is , and for the second component it is exact in one step. Thus the first coordinate is only halved at each iteration: convergence is linear, not quadratic. The same loss occurs for a multiple root of a single equation.
Worked example 2.5.6
(The scalar case as a check)
For and , , and the step is . From : , , so . Then , and , which differs from by about . The errors again show the doubling of correct digits.
Common mistakes and subtle points
- Convergence is local and may be to a different root. The circle-and-hyperbola system has four roots, , , and , and which one is reached depends on the start.
- The theorem needs a nonsingular Jacobian at the root and a Lipschitz Jacobian. Without these, convergence may be linear or fail.
- Cost. Each step needs , and a factorization, about operations for a dense system.
Common mistake
(Assuming the Newton step always exists)
For the circle and hyperbola, vanishes on the lines . At the Jacobian is , which is singular, so the equation with has no solution and no Newton step is defined. An implementation must detect a singular or nearly singular factorization rather than divide by a tiny pivot.
Common mistake
(Reading a small residual as a small error)
For the only root is and . At the residual has norm while the error has norm one. A small implies a small error only when is moderate.
Common mistake
(Inverting the Jacobian instead of solving)
The step needs only the solution of . An LU factorization with pivoting costs about operations for a dense matrix, while forming costs roughly three times as much and typically adds rounding error without benefit.
Counterexample mode
Newton’s method is not globally convergent
A tempting reading of the theorem is that Newton's method converges from any start once the root is simple. Take and , whose only root is , with . From , the iteration gives , , : the iterates diverge. The theorem is not contradicted. Here and has maximum at , so convergence is guaranteed only for . Global convergence needs a safeguard such as a line search or a bracket.
Exercises
Quick check
(Apply two Newton steps to from and compare with the root .)
The first equation is linear, so each step keeps .
Solution · Answer
. At : , . Solve and : so , , and . At : and . Solve and : , , . So . The sup-norm error to falls from to to .
Quick check
(For and , find and explain why convergence is linear.)
The two components are independent.
Solution · Answer
The components decouple. gives for the first coordinate, and the second coordinate is for (exact after one step, since ). So for . The error halves each step, which is linear convergence with ratio ; the Jacobian is singular at the root, so the theorem does not apply.
Quick check
(For with nonsingular, show that Newton's method reaches the solution in one step from any .)
The Jacobian of is .
Solution · Answer
Here and . The step solves , so and , the exact solution.
Quick check
(For , estimate the number of operations for one Newton step with a dense Jacobian solved by LU factorization, taking .)
Substitute .
Solution · Answer
operations, plus lower-order terms for evaluating and and for the triangular solves ().