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.

SOR converges exactly for positive-definite A and relaxation parameter in (0, 2)

Statement

Let $n \geq 1$ , $A \in M_{n} (C)$ be Hermitian with strictly positive diagonal, and let $ω \in R ∖ {0}$ . Write $A = D - L - L^{*}$ by Diagonal, lower, and upper parts in the stationary-iteration convention, and define

$M_{ω} = ω^{- 1} D - L, N_{ω} = (ω^{- 1} - 1) D + L^{*}, G_{ω} = M_{ω}^{- 1} N_{ω} .$

The SOR iteration is $x^{(k + 1)} = G_{ω} x^{(k)} + M_{ω}^{- 1} b$ . It converges to the unique solution of $A x = b$ for every $b, x^{(0)} \in C^{n}$ if and only if $A$ is positive definite (meaning $x^{*} A x > 0$ for every nonzero $x$ ) and $0 < ω < 2$ .

Facts & Assumptions

Given: $n \geq 1$ , a Hermitian matrix $A$ with positive diagonal, a real $ω \neq 0$ , and arbitrary $b, x^{(0)} \in C^{n}$ .

[A1]

$A = A^{*}$ , $a_{i i} > 0$ , and $ω \in R ∖ {0}$ .

[F1]

SOR uses $M_{ω} = ω^{- 1} D - L$ and $N_{ω} = (ω^{- 1} - 1) D + L^{*}$ (Finite-budget successive over-relaxation stationary iteration).

[L1]

The fixed diagonal/lower/upper convention gives $A = D - L - L^{*}$ for Hermitian $A$ (Diagonal, lower, and upper parts in the stationary-iteration convention).

[L2]

For an invertible matrix $M$ and $A = M - N$ , the stationary update is $x^{(k + 1)} = M^{- 1} N x^{(k)} + M^{- 1} b$ (Stationary iteration from a matrix splitting $A = M - N$ ).

[L3]

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

[L4]

Hermitian positive definite means $A = A^{*}$ and $x^{*} A x > 0$ for every nonzero $x$ (Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal).

[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).

[L6]

Determinants are multiplicative for same-sized square matrices over a commutative ring (For same-sized finite square matrices over a commutative ring, $\det (A B) = \det (A) \det (B)$ ).

[L7]

The determinant of a triangular matrix is the product of its diagonal entries (The determinant of a triangular matrix is the product of its diagonal entries).

[L8]

When the characteristic polynomial splits as $\prod_{i} (t - λ_{i})$ , the determinant is $\prod_{i} λ_{i}$ (If $χ_{T} (x) = \prod_{i < n} (x - λ_{i})$ in $F [x]$ , then $\det (T) = \prod_{i < n} λ_{i}$ : determinant is the product of the eigenvalues counted with algebraic multiplicity).

[L9]

Every complex polynomial splits over $C$ (The complex numbers are algebraically closed).

Proof

1.1A1F1L1L2L5L6L7algebra

By [A1] and [F1], $M_{ω}$ is lower triangular with diagonal $a_{i i} / ω \neq 0$ , hence invertible by [L5]. Also $A = M_{ω} - N_{ω}$ by [L1], so [L2] applies with iteration matrix $G_{ω}$ . The matrix $N_{ω}$ is upper triangular with diagonal entries $(ω^{- 1} - 1) a_{i i}$ . Thus [L6]–[L7] give $\det (M_{ω}) = ω^{- n} \prod_{i} a_{i i}$ and $\det (N_{ω}) = (ω^{- 1} - 1)^{n} \prod_{i} a_{i i}$ . From $M_{ω} G_{ω} = N_{ω}$ and multiplicativity, $\det (G_{ω}) = \det (N_{ω}) / \det (M_{ω}) = (1 - ω)^{n}$ .

1.2A1F1L1L2L4algebra

For sufficiency, suppose $A$ is positive definite and $0 < ω < 2$ . Then $Q : = M_{ω} + M_{ω}^{*} - A = (2 / ω - 1) D$ is positive definite. For an eigenpair $G_{ω} v = λ v$ with $v \neq 0$ , one has $λ \neq 1$ since $A v = (1 - λ) M_{ω} v$ and $A$ is invertible. Put $a = v^{*} A v > 0$ . Then $v^{*} M_{ω} v = a / (1 - λ)$ , so $v^{*} Q v = a (2 Re \frac{1}{1 - λ} - 1) = a \frac{1 - ∣ λ ∣^{2}}{∣ 1 - λ ∣^{2}} > 0$ . Therefore $∣ λ ∣ < 1$ for every eigenvalue and $ρ (G_{ω}) < 1$ .

2.1L3L8L9step 1.1algebra

If SOR converges for every right-hand side and start, [L3] gives $ρ (G_{ω}) < 1$ . By [L8]–[L9], $∣ \det (G_{ω}) ∣ = \prod_{j = 1}^{n} ∣ λ_{j} ∣ \leq ρ (G_{ω})^{n} < 1$ . Step 1.1 therefore gives $∣ 1 - ω ∣ < 1$ , which for real $ω$ is equivalent to $0 < ω < 2$ .

2.2A1F1L1L2L3step 1.1algebra

Assume now that SOR converges for every right-hand side and start. Then $ρ (G_{ω}) < 1$ by [L3], so $1$ is not an eigenvalue of $G_{ω}$ and $I - G_{ω}$ is invertible. By [L2], $A = M_{ω} (I - G_{ω})$ is invertible. For $b = 0$ , its unique solution is $x_{*} = 0$ . For arbitrary nonzero $e^{(0)} : = x^{(0)}$ , set $e^{(k)} : = x^{(k)} - x_{*} = x^{(k)}$ and $δ_{k} = e^{(k + 1)} - e^{(k)}$ . The homogeneous SOR recurrence gives $M_{ω} e^{(k + 1)} = N_{ω} e^{(k)}$ , hence $A e^{(k)} + M_{ω} δ_{k} = 0$ . Expanding the Hermitian quadratic form gives $(e^{(k)})^{*} A e^{(k)} - (e^{(k + 1)})^{*} A e^{(k + 1)} = δ_{k}^{*} (M_{ω} + M_{ω}^{*} - A) δ_{k} = (2 / ω - 1) δ_{k}^{*} D δ_{k}$ . The last equality follows from [L1] and [F1].

3.1A1L3L4step 2.1step 2.2algebra

By step 2.1, $c : = 2 / ω - 1 > 0$ . Summing the identity in step 2.2 from $k = 0$ to $N - 1$ and taking $N \to \infty$ (the error tends to $0$ by the assumed convergence) gives $(e^{(0)})^{*} A e^{(0)} = c \sum_{k = 0}^{\infty} δ_{k}^{*} D δ_{k}$ . Moreover $δ_{0} \neq 0$ : otherwise step 2.2 implies $A e^{(0)} = 0$ , contrary to invertibility of $A$ . Since $D$ has positive diagonal, the first summand is strictly positive and all others are nonnegative. Thus $(e^{(0)})^{*} A e^{(0)} > 0$ for every nonzero $e^{(0)}$ , so [L4] gives that $A$ is positive definite.

4.1L3step 2.1step 3.1step 1.2∎

By [L3], $ρ (G_{ω}) < 1$ implies convergence to the unique solution for every right-hand side and every initial vector. Steps 2.1 and 3.1 prove the reverse implication.

Remarks

The conclusion is exact-arithmetic asymptotic convergence; it is not a one-step error decrease or a finite-precision accuracy guarantee. No optimal- $ω$ formula is asserted.

Depends on

Used by

SOR on a positive-definite system with relaxation parameter in (0, 2) Example

Dependency tree · two levels

41 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.4 (standard reference, not scraped)
Rutgers University MATH 574, Lecture Notes, §3 Matrix iterative methods (standard reference, not scraped)
David Bindel, Matrix Computations (CS 6210), Cornell University, Fall 2012, Lecture 31 (standard reference, not scraped)