Solving nonlinear systems — Newton's method in n dimensions: Question bank

Definition Notation used on this page

$F : R^{n} \to R^{n}$ is our system, written component-by-component as $F = (f_{1}, \dots, f_{n})$ : each $f_{i} (x_{1}, \dots, x_{n})$ is one scalar equation, and a root $x^{*}$ makes all of them vanish at once, $F (x^{*}) = 0$ .
$J (x)$ is the Jacobian matrix evaluated at $x$ , with entries $J_{ij} = \partial f_{i} / \partial x_{j}$ ; row $i$ is the gradient $\nabla f_{i}$ of the $i$ -th component function.
$Δ x_{k}$ is the Newton step at iterate $x_{k}$ , solving $J (x_{k}) Δ x_{k} = - F (x_{k})$ . Every quantity is evaluated at the current iterate $x_{k}$ — the arguments matter, so we keep them.
$e_{k} := x_{k} - x^{*}$ is the error vector at step $k$ — how far the current guess sits from the true root.
$∥ \cdot ∥$ is any fixed vector norm (e.g. Euclidean length); every statement below holds for any consistent choice — just use the same one throughout.
$t_{k} \in (0, 1]$ is a step-length (damping) factor: instead of a full step we may move only part-way, $x_{k + 1} = x_{k} + t_{k} Δ x_{k}$ .
The quadratic-convergence bound is $∥ e_{k + 1} ∥ \leq C ∥ e_{k} ∥^{2}$ , where $C$ is concretely $C = \frac{1}{2} ∥ J (x^{*})^{- 1} ∥ \cdot L$ , with $L$ a Lipschitz constant of $J$ near $x^{*}$ (how fast the Jacobian changes) and $∥ J (x^{*})^{- 1} ∥$ measuring how far $J$ is from singular. It holds only near the root, where $J (x^{*})$ is nonsingular so that inverse exists.

Two pictures to keep in mind

The traps below all trace back to two behaviours. Look at both figures before answering.

Figure — Solving nonlinear systems — Newton's method in n dimensions

Overshoot. On the left the linear model at $x_{k}$ (the tangent ramp) is a good guide and the full step lands near the root. On the right the same full step overshoots because the true curve bends away — the damping factor $t_{k}$ shrinks the step back into the trustworthy zone.

Basins of attraction. Which root Newton reaches depends on the start in a wildly sensitive, fractal way — so "converges to the nearest root" is simply false.

True or false — justify

The Newton step direction

Δ x_{k}

always points "downhill" for the residual

∥ F ∥

False on two counts. First, Newton guarantees descent of the squared residual

ϕ = \frac{1}{2} ∥ F ∥^{2}

, not

∥ F ∥

itself. Its gradient is

\nabla ϕ = J^{⊤} F

, so the directional derivative along the Newton step is

\nabla ϕ^{⊤} Δ x_{k} = (J^{⊤} F)^{⊤} (- J^{- 1} F) = - F^{⊤} F = - ∥ F ∥^{2} < 0

— genuinely downhill, but only when

J

is nonsingular so

Δ x_{k} = - J^{- 1} F

exists. Second, even then a full step can overshoot (see s01), which is why damped Newton scales it by

t_{k}

F

is linear, Newton converges in exactly one iteration from any start.

True. Then

F (x) = A x - b

for a fixed matrix

A

and constant vector

b

, so

J (x) = A

is constant, the linear model is

F

, and the first solve lands exactly on the root

x^{*} = A^{- 1} b

Quadratic convergence means the error is squared every step no matter where you start.

False. The bound

∥ e_{k + 1} ∥ \leq C ∥ e_{k} ∥^{2}

(with

e_{k} = x_{k} - x^{*}

and

C = \frac{1}{2} ∥ J (x^{*})^{- 1} ∥ L

) is local — it only kicks in once

x_{k}

is close enough that

C ∥ e_{k} ∥ < 1

; far away Newton may crawl, cycle, or diverge.

A stopping test on

∥Δ x_{k} ∥

alone is sufficient.

False. Near a nearly-singular

J (x_{k})

a tiny step can occur while

∥ F (x_{k}) ∥

is still large; you must also check the residual

∥ F (x_{k}) ∥

is small.

Newton's method requires

F

to be differentiable.

True. The whole method is built on the first-order Taylor model

F (x_{k} + h) \approx F (x_{k}) + J (x_{k}) h

; without a Jacobian there is no linear model to solve.

J (x^{*})

is singular, Newton simply fails and produces nothing.

False. It usually still converges, just slower — the rate drops from quadratic to linear (like scalar Newton at a double root where

f^{'} = 0

The Newton iteration is a special case of Fixed-point iteration.

True. It is the fixed-point map

g (x) = x - J (x)^{- 1} F (x)

; its fast convergence comes from that map's derivative vanishing at

x^{*}

Doubling

n

(unknowns) leaves the per-step cost roughly unchanged.

False. The dominant cost is the linear solve,

O (n^{3} /3)

via LU decomposition, so doubling

n

multiplies work by about

8

Newton always converges to the root nearest the starting point.

False. There is no such guarantee — Newton's "basins of attraction" are famously fractal (see s02), so a start can jump to a far-away root or diverge entirely.

Spot the error

"To update, compute

J^{- 1}

then set

x_{k + 1} = x_{k} - J (x_{k})^{- 1} F (x_{k})

Forming

J^{- 1}

explicitly is the error. Solve

J (x_{k}) Δ x_{k} = - F (x_{k})

by one LU factorization — about

3 \times

cheaper and far more stable than inverting.

"The Jacobian's rows are the gradients

\nabla f_{j}

of column

j

Mixed up. Row

i

\nabla f_{i}

(the

i

-th component function's partials); entry

J_{ij} = \partial f_{i} / \partial x_{j}

runs equation $i$ across all variables $j$ .

"Since Newton converges quadratically, one iteration suffices for any tolerance."

No — quadratic means the number of correct digits doubles per step, so you still need several steps to build up those digits (e.g.

2 \to 4 \to 8 \to 16

"We set

F (x_{k}) + J (x_{k}) h = F (x_{k + 1})

and solve."

The right-hand side must be

0

, not

F (x_{k + 1})

. We demand the linear model hit zero, giving

J (x_{k}) h = - F (x_{k})

"Broyden's method is just Newton with a better convergence rate."

Backwards. Broyden approximates

J

to skip refactorizing, trading Newton's quadratic rate for a cheaper superlinear one — faster per step, but more steps.

"A large residual

∥ F (x_{k}) ∥

means

x_{k}

is far from the root."

Not necessarily. If

J (x_{k})

is ill-conditioned, a small residual can hide a large error

∥ e_{k} ∥

and vice-versa; residual and error are only loosely linked.

Why questions

Why do we truncate Taylor after the linear term rather than keeping the quadratic term?

Keeping only the linear term makes the model a solvable linear system

J (x_{k}) h = - F (x_{k})

; keeping the quadratic term would leave us with another nonlinear system to solve — no progress.

Why does discarding the

O (∥ h ∥^{2})

remainder give quadratic convergence?

Because that discarded remainder is the leftover error, and it scales like

∥ h ∥^{2} \approx ∥ e_{k} ∥^{2}

(where

e_{k} = x_{k} - x^{*}

), so the next error is proportional to the square of the current one — that proportionality factor is the constant

C = \frac{1}{2} ∥ J (x^{*})^{- 1} ∥ L

Why must

J (x^{*})

be nonsingular for fast convergence?

A singular

J

has no unique step (the linear model is flat in some direction), so the update direction blows up or is undefined — and the bound's factor

∥ J (x^{*})^{- 1} ∥

would be infinite. This mirrors scalar Newton stalling where

f^{'} = 0

Why prefer solving the linear system over inverting

J

, even though the formula shows

J^{- 1}

Solving needs one factorization plus back-substitution (

\approx n^{3} /3

flops); inverting costs

\sim 3 \times

that and amplifies rounding error — the

J^{- 1}

in the formula is notation, not an instruction.

Why is Newton called only locally convergent?

The linear model is trustworthy only near

x_{k}

; far from the root the neglected higher-order terms dominate, so the guarantee holds only inside a neighbourhood of

x^{*}

(exactly the overshoot risk shown in s01).

Why does damped Newton help when the full step overshoots?

A line-search step-length

t_{k} \in (0, 1]

shrinks the step until the squared residual

\frac{1}{2} ∥ F ∥^{2}

actually decreases — which the Newton direction always allows since its directional derivative is

- ∥ F ∥^{2} < 0

— keeping you inside the region where the linear model is still a decent guide.

Why can Newton solve a linear

F

in one step but a nonlinear one cannot?

For linear

F

the model has zero discarded remainder, so the first solve is exact; for nonlinear

F

the remainder is nonzero, so each step only approximates and must repeat.

Edge cases

What happens if you start exactly at the root,

x_{0} = x^{*}

Then

F (x_{0}) = 0

, so

Δ x_{0} = 0

and you stay put — the method recognises it is already done.

What if

J (x_{k})

is singular mid-iteration (not at the root)?

The solve

J (x_{k}) Δ x_{k} = - F (x_{k})

has no unique solution; the method breaks down and needs a fix (perturb

x_{k}

, add regularisation, or switch to a globalised variant).

What if two roots sit very close together?

Their basins interleave finely (an extreme version of s02), so the same

x_{0}

can flip between roots under tiny perturbations, and convergence may slow because

J

is small between them.

What if

F

has no real root at all?

Newton cannot converge to a root that doesn't exist; iterates typically diverge, wander, or cycle — a residual

∥ F ∥

that never approaches zero is the tell.

What if

n = 1

Everything collapses to scalar Newton's method (1-D):

J (x_{k})

becomes the single number

f^{'} (x_{k})

and the solve becomes the division

x_{k + 1} = x_{k} - f (x_{k}) / f^{'} (x_{k})

What if the root is a whole curve of solutions (infinitely many roots)?

Then

J

is singular along that set (some direction leaves

F

unchanged), so quadratic convergence is lost and Newton may drift along the solution manifold rather than pin a point.

Recall One-line self-test

The single sentence that guards against most traps here ::: "The linear model $J (x_{k}) Δ x_{k} = - F (x_{k})$ is exact only for linear $F$ and trustworthy only near $x_{k}$ — everything Newton does (and fails to do) follows from that."