ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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 on a positive-definite system with relaxation parameter in (0, 2)

Example

Take

$A = (\begin{array}{cc} 2 & - 1 \\ - 1 & 2 \end{array}), b = 0, x^{(0)} = (\binom{1}{0}), ω = \frac{3}{2} .$

The matrix is positive definite and $ω \in (0, 2)$ . For the fixed order $1, 2$ , the SOR iteration matrix is

$G_{ω} = (\begin{array}{cc} - 1 / 2 & 3 / 4 \\ - 3 / 8 & 1 / 16 \end{array}),$

with eigenvalues $(- 7 \pm i \sqrt{207}) / 32$ , both of modulus $1 / 2$ . Thus the error converges to zero for every initial vector.

Facts & Assumptions

Given: The displayed matrix, right-hand side, initial vector, and relaxation parameter.

[F1]

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

[L1]

For Hermitian $A$ with positive diagonal, SOR converges for every start if and only if $A$ is positive definite and $0 < ω < 2$ (SOR converges exactly for positive-definite A and relaxation parameter in (0, 2)).

[L2]

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

Verification

1.1givenL2algebra

For $z = (z_{1}, z_{2})^{T}$ , $z^{*} A z = ∣ z_{1} ∣^{2} + ∣ z_{2} ∣^{2} + ∣ z_{1} - z_{2} ∣^{2}$ , so [L2] shows that $A$ is positive definite; its diagonal is positive and $0 < 3 / 2 < 2$ .

1.2F1algebra

Here $D = 2 I$ , $L_{21} = 1$ , and $U = L^{*}$ . By [F1], $M_{ω} = (\begin{array}{cc} 4 / 3 & 0 \\ - 1 & 4 / 3 \end{array})$ and $N_{ω} = (\begin{array}{cc} - 2 / 3 & 1 \\ 0 & - 2 / 3 \end{array})$ , hence $G_{ω} = M_{ω}^{- 1} N_{ω} = (\begin{array}{cc} - 1 / 2 & 3 / 4 \\ - 3 / 8 & 1 / 16 \end{array})$ . Its characteristic polynomial is $λ^{2} + (7 / 16) λ + 1 / 4$ , whose roots are $(- 7 \pm i \sqrt{207}) / 32$ and have modulus $1 / 2$ .

2.1L1step 1.1step 1.2∎

The hypotheses of [L1] hold by step 1.1, so SOR converges for every start; in particular the stated start converges to the solution $0$ .

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.1 and 4.2.4 (standard reference, not scraped)