TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A stationary splitting converges for every start if and only if its iteration matrix has spectral radius below $1$

Statement

Let $A = M - N$ be a matrix splitting in $M_{n} (C)$ with stationary iteration

$x_{k + 1} = M^{- 1} N x_{k} + M^{- 1} b,$

and let $B : = M^{- 1} N$ be its iteration matrix. Then the following are equivalent:

For every right-hand side $b$ and every initial vector $x_{0}$ , the iterates converge to the unique solution of $A x = b$ .
The spectral radius $ρ (B)$ is strictly less than $1$ .

Facts & Assumptions

Given: A complex matrix splitting $A = M - N$ with invertible $M$ , its stationary iteration, and its iteration matrix $B = M^{- 1} N$ .

[F1]

The stationary iteration is $x_{k + 1} = B x_{k} + M^{- 1} b$ with $B = M^{- 1} N$ (Stationary iteration from a matrix splitting $A = M - N$ ).

[L1]

The field $C$ is algebraically closed (The complex numbers are algebraically closed).

[L2]

Over an algebraically closed field, every endomorphism has Jordan form (Every finite-dimensional endomorphism over an algebraically closed field has Jordan form).

[L3]

The spectrum is the root set of the characteristic polynomial (For every finite-dimensional space, $σ_{F} (T)$ is exactly the set of roots in $F$ of $χ_{T}$ ).

Proof

technique · direct

1.1

A vector $x$ is a fixed point of the stationary iteration if and only if it solves $A x = b$ : indeed, by [F1], $x = B x + M^{- 1} b ⟺ M x = N x + b ⟺ A x = b .$ Therefore, whenever $x_{*}$ solves $A x = b$ , the error $e_{k} : = x_{k} - x_{*}$ satisfies $e_{k + 1} = B x_{k} + M^{- 1} b - x_{*} = B (x_{k} - x_{*}) = B e_{k} .$

F1algebra

2.1

Assume $ρ (B) < 1$ . By [L1], [L2], and [L3], we may write $B = S J S^{- 1}$ with $J$ Jordan and every eigenvalue $λ$ of $B$ satisfying $∣ λ ∣ < 1$ . On a Jordan block $J_{λ} = λ I + N$ with nilpotent $N$ , one has $J_{λ}^{k} = \sum_{j = 0}^{s - 1} (\binom{k}{j}) λ^{k - j} N^{j} .$ Because $∣ λ ∣ < 1$ , each scalar factor $(\binom{k}{j}) λ^{k - j}$ tends to $0$ , so every Jordan block tends to $0$ . Hence $J^{k} \to 0$ and therefore $B^{k} \to 0$ . Since $1 \notin σ (B)$ , the matrix $I - B$ is invertible by [L3]. Define $x_{*} : = (I - B)^{- 1} M^{- 1} b .$ Then $(I - B) x_{*} = M^{- 1} b$ , so $x_{*} = B x_{*} + M^{- 1} b$ , and step 1.1 shows that $x_{*}$ solves $A x = b$ . For any initial vector $x_{0}$ , step 1.1 gives $e_{k} = B^{k} e_{0} \to 0$ , so the iterates converge to $x_{*}$ . If $y$ is another solution of $A x = b$ , then step 1.1 also gives $y = B y + M^{- 1} b$ , hence $y - x_{*} = B (y - x_{*}) .$ Iterating and using $B^{k} \to 0$ yields $y - x_{*} = B^{k} (y - x_{*}) \to 0$ , so $y = x_{*}$ . Thus the iterates converge to the unique solution of $A x = b$ for every $b$ and every $x_{0}$ .

L1L2L3step 1.1algebra

3.1

Conversely, assume the iteration converges for every $b$ and every $x_{0}$ . Taking $b = 0$ , statement 1 gives convergence to the unique solution of $A x = 0$ . By step 1.1 that unique solution is also the unique fixed point of $x \mapsto B x$ , so it is $0$ . Hence for every start $x_{0}$ one has $B^{k} x_{0} = x_{k} \to 0$ , which means $B^{k} \to 0$ . If $B v = λ v$ with $v \neq 0$ , then $λ^{k} v = B^{k} v \to 0,$ so $λ^{k} \to 0$ and therefore $∣ λ ∣ < 1$ . By [L3], every spectral value of $B$ is such an eigenvalue over $C$ , and thus $ρ (B) < 1$ .

L3step 1.1algebra∎

Depends on

Used by

Jacobi and Gauss-Seidel splittings can be compared by the spectral radii of their iteration matrices Example

Dependency tree · two levels

28 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Gilbert Strang, 18.086 Mathematical Methods for Engineers II, Section 6.2 Iterative Methods (standard reference, not scraped)

A stationary splitting converges for every start if and only if its iteration matrix has spectral radius below 11