From a scalar tangent to a linear solve
Suppose and we seek . A small residual in one component is not enough: every equation must hold simultaneously. Near a current estimate , linearization suggests
where is the Jacobian matrix of partial derivatives.
Definition 6.3.1
(Newton step)
When is invertible, the Newton step is the solution of the linear system
In implementation one solves the linear system rather than explicitly forming . A direct solve normally costs less and has better backward-error behavior than explicitly forming the inverse. Neither approach removes sensitivity to an ill-conditioned Jacobian, so a computed step can still be inaccurate. A singular Jacobian may make the equation have no solution or many solutions, so (1) is not automatically defined.
Worked example 6.3.2
(A circle and a line)
Take
The two solutions are , with matching signs. If an iterate lies on the line, with , the second row of (1) forces equal step components. The first row then gives
Starting from gives and , close to . This is a genuine vector Newton calculation whose symmetry reduces it to one dimension. Whenever the first Newton step exists, its second row places the next iterate exactly on the line, even if the start was off it. A different initial point may converge to the other root. For and , the exact error identity makes the quadratic behavior near visible.
What quadratic convergence actually assumes
Use the Euclidean norm and its induced matrix norm. Write for the closed ball of radius .
Definition 6.3.3
(Lipschitz Jacobian)
The Jacobian is Lipschitz on with constant if
Two facts are needed: the Jacobian stays invertible near the root, and its inverse stays bounded there.
Lemma 6.3.4
(Jacobians near the root stay invertible)
Let be Lipschitz with constant on , let be invertible, and put . If , then for every the matrix is invertible and .
Proof
(Neumann series for the perturbed Jacobian)
Put , and . Then . For the series converges to , so is invertible with . Since , the matrix is invertible and , whose norm is at most .
Theorem 6.3.5
(Local quadratic convergence)
Suppose is continuously differentiable on an open set containing a closed ball , , and is Lipschitz there with constant . If is invertible and , choose
For every , each exact Newton step is defined, all iterates stay in the ball, and
Thus at least quadratically in the sense of the first bound. The theorem assumes exact linear solves. Separately, if is constant on the ball (), one exact step reaches the root; the displayed radius formula is then not used. The chosen positive- radius is sufficient, not asserted sharp. Inexact linear solves or rounding add perturbations, so (2) need not hold unchanged.
Proof
(Integral remainder and induction)
Let and . By the lemma, is invertible with . The segment from to is in the ball. The fundamental theorem of calculus along it gives
If , subtract and factor out :
Lipschitz continuity bounds the integrand by . Using the lemma,
Since , this is at most . Induction keeps the iterates in the ball and gives convergence; the first inequality proves (2). If , the integral formula is exactly , so .
Proof X-ray
What gives the explicit quadratic bound?
Invertibility of supplies the constant ; the Lipschitz constant is used twice, once in the lemma to keep close to and once in the integral remainder. The key move is to write as an integral of the Jacobian along the segment to the root. In the Newton step has canceled the first-order term exactly, so only the variation of times remains, which supplies the second power of the error. The proof closes because turns the quadratic bound into a halving, so the next iterate is again in the ball. Without invertibility of the constant does not exist, and for the error only halves. The theorem is local: it does not identify an unknown root or prove that an arbitrary initial guess enters this ball.
Worked example 6.3.6
(Checking the bound on a scalar equation)
For we have , root , and , so and . The start has error . Newton's step is , giving , , . The errors are about , , . The ratios are about , , , all at most , in agreement with (2), and tending to . The number of correct digits roughly doubles at each step.
Failures that the theorem does not rule out
Counterexample mode
A singular starting Jacobian
For the circle-and-line example, at the Jacobian has a zero first row while the first component of is . The Newton linear system is inconsistent. The roots themselves have invertible Jacobians, but that does not make a step from every starting point possible.
Worked example 6.3.7
(A singular root gives only linear convergence)
Even when every step is defined, convergence can be slow at a multiple root. For the system , the Jacobian is and a nonzero and any give . From the iterates are . The root has singular Jacobian and the -error decreases only by a factor of two, so the hypothesis that is invertible cannot be dropped from the theorem.
For practical systems, stopping based solely on a step or a residual is a decision requiring scale and conditioning information. Damping or line search may help avoid bad steps, but neither is an unconditional global convergence guarantee for arbitrary systems.
Common mistake
(Stopping because the residual is small)
A small residual need not mean a small error without a suitable inverse or conditioning bound: has residual at even though the root is one unit away.
Common mistake
(Reading the local theorem as a global guarantee)
The theorem concerns starts inside and needs a root and a Lipschitz Jacobian already in hand. It does not show that an arbitrary initial guess converges, or that a root exists; the circle-and-line example already has a start from which no first step exists.
Practice with solutions
Exercise 6.3.8
(Compute the Jacobian of at and solve its Newton system.)
Foundation
Solution(3)
- 1
Evaluate and at
- 2
Solve the Newton system
With the first row gives , so .
Because: The second row says , so the two components are equal.
- 3
Form the next iterate
. As a check, , a much smaller residual than .
Quick check
(For , why is convergence to not quadratic for an initial ?)
Compute two iterates.
Solution · Answer
and is zero after the first step. The ratio stays , whereas a quadratic bound would make that ratio tend to zero. The Jacobian at the root is singular.
Quick check
(In the theorem suppose and . Give one permitted positive radius when .)
Compare with .
Solution · Answer
Here , so is permitted, as is any smaller positive radius.
Quick check
(Why is alone insufficient for a universal bound on the distance to a root across all systems?)
Try .
Solution · Answer
For the family , the residual at tends to zero as while its distance to the root remains one.
Quick check
(Does the local theorem prove convergence from every starting point? Identify one hypothesis it needs near the root.)
Look at the list of hypotheses.
Solution · Answer
No. One hypothesis is that is invertible; the theorem also requires a Lipschitz bound on and a sufficiently close start. It gives no conclusion for an arbitrary start outside the ball.