TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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.

Irreducibly weak row diagonal dominance with a strict row guarantees Jacobi and Gauss–Seidel convergence

Statement

Let $n \geq 1$ and $A = (a_{i j}) \in M_{n} (R)$ satisfy weak row diagonal dominance

$∣ a_{i i} ∣ \geq \sum_{j \neq i} ∣ a_{i j} ∣ (i = 1, \dots, n),$

with strict inequality in at least one row. Assume the directed off-diagonal graph, with edge $i \to j$ when $i \neq j$ and $a_{i j} \neq 0$ , is strongly connected (paths of length $0$ are allowed). Then the Jacobi and fixed-order Gauss–Seidel iterations defined by Finite-budget Jacobi stationary iteration and Finite-budget Gauss–Seidel stationary iteration converge in exact arithmetic to the unique solution of $A x = b$ for every $b, x^{(0)} \in R^{n}$ .

Facts & Assumptions

Given: $n \geq 1$ , a real matrix $A$ satisfying the displayed weak row inequalities, at least one strict row, and a strongly connected directed off-diagonal graph.

[A1]

Every row satisfies $∣ a_{i i} ∣ \geq \sum_{j \neq i} ∣ a_{i j} ∣$ , with at least one strict row; the off-diagonal graph has edges $i \to j$ exactly when $a_{i j} \neq 0$ and is strongly connected.

[L1]

$A = D - L - U$ , where $D$ is diagonal and $L, U$ are the negative strict lower and upper parts (Diagonal, lower, and upper parts in the stationary-iteration convention).

[F1]

Jacobi has iteration matrix $G_{J} = D^{- 1} (L + U)$ (Finite-budget Jacobi stationary iteration).

[F2]

Fixed-order Gauss–Seidel has iteration matrix $G_{G} = (D - L)^{- 1} U$ (Finite-budget Gauss–Seidel stationary iteration).

[L2]

For the comparison matrix $C \geq 0$ with row sums at most $1$ , strongly connected positive-entry graph, and a strict row, there is $v > 0$ with $C v < v$ (An irreducible row-substochastic matrix with a strict row has a weighted contraction).

[L3]

In a stationary split $A = M - N$ , the update has iteration matrix $G = M^{- 1} N$ (Stationary iteration from a matrix splitting $A = M - N$ ).

[L4]

A stationary iteration converges to the unique solution for every right-hand side and every start exactly when $ρ (G) < 1$ (A stationary splitting converges for every start if and only if its iteration matrix has spectral radius below $1$ ).

[L5]

A lower-triangular system with nonzero diagonal has a unique forward substitution solution (Forward and backward substitution are correct, unique, and quadratic in scalar operations).

Proof

1.1A1L5algebra

If $n > 1$ and $a_{i i} = 0$ , [A1] forces every off-diagonal entry in row $i$ to vanish, contradicting strong connectivity. If $n = 1$ , the strict-row hypothesis forces $∣ a_{11} ∣ > 0$ . Hence every diagonal entry is nonzero, and the Jacobi and lower-triangular Gauss–Seidel solves are defined by [L5].

2.1A1L1L2step 1.1algebra

Define $C_{i i} = 0$ and $C_{i j} = ∣ a_{i j} ∣ / ∣ a_{i i} ∣$ for $i \neq j$ . Its row sums are at most $1$ , one is strictly below $1$ , and its positive-entry graph is the graph in [A1]. By [L2], choose $v > 0$ with $C v < v$ , and set $q_{J} = \max_{i} (C v)_{i} / v_{i} < 1$ .

3.1F1step 2.1algebra

By [F1], $∣ G_{J} ∣ = C$ entrywise. For $∥ z ∥_{v} : = \max_{i} ∣ z_{i} ∣ / v_{i}$ , nonnegativity gives $∣ G_{J} z ∣ \leq C ∣ z ∣ \leq ∥ z ∥_{v} C v \leq q_{J} ∥ z ∥_{v} v$ . Thus every eigenvalue $λ$ of $G_{J}$ satisfies $∣ λ ∣ \leq q_{J} < 1$ , so $ρ (G_{J}) < 1$ .

3.2A1L1step 2.1algebra

Set $B_{L} = ∣ D ∣^{- 1} ∣ L ∣$ and $B_{U} = ∣ D ∣^{- 1} ∣ U ∣$ . Then $C = B_{L} + B_{U}$ , $B_{L}$ is strictly lower triangular, and $(I - B_{L})^{- 1} = \sum_{r = 0}^{n - 1} B_{L}^{r} \geq I$ . Thus $H : = (I - B_{L})^{- 1} B_{U} = \sum_{r = 0}^{n - 1} B_{L}^{r} B_{U} \geq 0$ . Since $(I - B_{L}) v - B_{U} v = (I - C) v > 0$ , multiplying by $(I - B_{L})^{- 1} \geq I$ gives $H v < v$ . Consequently $q_{G} : = \max_{i} (H v)_{i} / v_{i} < 1$ .

4.1F2L1step 3.2algebra

Because $D - L = D (I - D^{- 1} L)$ and $D^{- 1} L$ is strictly lower triangular, $(D - L)^{- 1} U = \sum_{r = 0}^{n - 1} (D^{- 1} L)^{r} D^{- 1} U$ . Entrywise absolute values obey $∣ X Y ∣ \leq ∣ X ∣ ∣ Y ∣$ , so $∣ G_{G} ∣ \leq H$ . The same weighted-vector estimate as in step 3.1 yields $∥ G_{G} z ∥_{v} \leq q_{G} ∥ z ∥_{v}$ ; hence $ρ (G_{G}) < 1$ .

5.1L3L4step 3.1step 4.1∎

By [L3]–[L4], the two spectral-radius bounds imply convergence to the unique solution of $A x = b$ for every right-hand side and every initial vector.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

14 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

Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., §4.2.3 (standard reference, not scraped)