A strictly diagonally dominant matrix or a real symmetric positive-definite matrix guarantees convergence of the Gauss-Seidel method from every initial vector. These are sufficient conditions.[ref]
Notes for Ma221 Lecture 21, Nov 10 2009. Math 221, Matrix Computations, Fall 2009; Theorem 1, strict row diagonal dominance, web lines 462–465; Theorem 3, positive-definite SOR and its ω = 1 specialization, web lines 490–493
For strict diagonal dominance, putInduct through a sweep. Old coordinates have absolute error at most ; previously updated coordinates have absolute error at most . The component update and the triangle inequality therefore bound the new error by . This proves , a maximum norm contraction.
For a symmetric positive-definite matrix, write . The Householder-John theorem applies to and , because is a positive-definite matrix. Hence the iteration matrix has spectral radius less than one, which gives the convergence criterion for a stationary iteration.
There is also a geometric reason fresh updates help: the Gauss-Seidel method is exact coordinate descent on the convex quadratic functionHolding the other coordinates fixed, minimizing in coordinate gives the corresponding row update. A change lowers by exactly . Each fresh coordinate is therefore the minimizer for the current vector, and a complete sweep lowers the quadratic form error unless every coordinate already solves its row. This explains the method's beauty without implying monotone decrease in every vector norm.
Jacobi convergence for a symmetric positive-definite tridiagonal matrix Created 2026-09-24 Updated 2026-09-29
If is symmetric positive definite and tridiagonal, set . Thenis positive definite. Applying the Householder-John theorem to and proves that the Jacobi iteration converges.
Past exam of the mathematics course of the University of Cambridge 2007 ii Paper 2 38C a Solution Created 2026-09-24 Updated 2026-10-14
One form of the Householder-John theorem is as follows. Suppose and , with invertible and positive definite. Then the stationary iteration converges for every initial vector exactly when is positive definite; its iteration matrix is and convergence means spectral radius below one.
For a known positive definite system, design a splitting with easy to solve, such as diagonal or triangular, and arrange . The theorem then guarantees convergence. For example has when exceeds the largest eigenvalue of . In the converse direction, the discrete energy identity explains the criterion: stable gives as a convergent sum of positive matrices, while positive force every iteration eigenvalue inside the unit disk.
Past exam of the mathematics course of the University of Cambridge 2007 ii Paper 2 38C b Solution Created 2026-09-24 Updated 2026-10-14
Divide the supplied scheme by and takeThen , and is invertible because it is lower triangular with positive diagonal . Symmetry gives , soThe Householder-John theorem therefore gives convergence.
For a direct spectral proof, let . Expansion verifies . If with , thenThe value is impossible since and is invertible. Both quadratic forms are positive, hence . The error obeys and tends to zero, proving convergence to the unique solution for every initial iterate. This is the successive-over-relaxation iteration, with no assertion of convergence at the excluded endpoints.
Past exam of the mathematics course of the University of Cambridge 2010 ii Paper 1 39A a Solution Created 2026-09-24 Updated 2026-10-14
The Householder-John theorem says that, for a splitting with Hermitian positive definite, positivity of implies is invertible and . Invertibility follows since for would give .
For clarity, the spectral-radius conclusion follows from a useful energy identity. Put . Direct multiplication givesIf , thenThe eigenvalue one is impossible because is invertible. Both quadratic forms are positive, so . The splitting iteration propagates its error by ; spectral radius less than one therefore gives convergence from every initial vector.
Past exam of the mathematics course of the University of Cambridge 2010 ii Paper 1 39A b Solution Created 2026-09-24 Updated 2026-10-14
Write , with diagonal and the strict triangular parts. The Jacobi method updates all coordinates using the preceding iterate:For a symmetric positive definite matrix, has positive diagonal entries. In its splitting take , . The theorem requires to be positive definite, which need not hold for every positive definite matrix.
For this tridiagonal matrix, let . Neighboring indices have opposite signs, so : the diagonal stays fixed and every nonzero off-diagonal entry changes sign. ThusThe Householder-John theorem now applies and proves Jacobi convergence for every initial vector. This is precisely why the tridiagonal structure matters.
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 1 39A Solution Created 2026-09-24 Updated 2026-10-05
The Householder-John theorem states that if is Hermitian positive definite and is also Hermitian positive definite, then is invertible and . The associated stationary iteration therefore converges from every starting vector. For designing a method, choose a splitting with easily solved and verify the positive-definiteness condition on ; it is a sufficient certificate and does not require computing every iteration-matrix eigenvalue.
For completeness, put . If for , then , a contradiction. If , then . The case contradicts invertibility of . Taking scalar products and using Hermitian symmetry giveshence . The usual spectral-radius convergence criterion now proves the stated conclusion.
For the given scheme take the matrix splittingSince is real symmetric, , and since it is positive definite, every diagonal entry in is positive. Thusis positive definite exactly for . The theorem applies, and the iteration matrix has spectral radius below one. The unique solution is its fixed point, so . ThereforeThe scheme is successive over-relaxation; at it becomes the Gauss-Seidel method.
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 1 40C c Solution Created 2026-09-24 Updated 2026-10-03
The Householder-John theorem states: if is Hermitian positive definite and is also Hermitian positive definite, then is invertible and
Now let be real symmetric positive definite and tridiagonal. For the Jacobi splitting, and . Positive definiteness of implies every diagonal entry is positive, so is positive definite. Introduce the alternating-sign diagonal matrixTridiagonality givesSince is orthogonal, is positive definite whenever is. Both hypotheses of the Householder-John theorem hold, and hence the Jacobi iteration matrix satisfies . Therefore the Jacobi convergence for a symmetric positive-definite tridiagonal matrix follows.
Past exam of the mathematics course of the University of Cambridge 2025 ii Paper 4 40D a Solution Created 2026-09-24 Updated 2026-09-25
The Householder-John theorem states the following. Letbe a splitting in which is Hermitian positive definite. Ifis also Hermitian positive definite, then is nonsingular and every eigenvalue of has modulus less than one. Hence the associated stationary iteration converges.
First, must be nonsingular. If for some nonzero , then , and thereforecontradicting the positive definiteness of .
Past exam of the mathematics course of the University of Cambridge 2025 ii Paper 4 40D b Solution Created 2026-09-24 Updated 2026-09-25
Writewhere and are the strict lower and upper triangular parts. The Jacobi method iswith iteration matrix
Here is symmetric, so . Regard the iteration as the splittingLetBecause is tridiagonal, changing alternating signs reverses the sign of every off-diagonal entry while preserving every diagonal entry. ThereforeSince and is positive definite, is positive definite. The Householder-John theorem now givesThe Jacobi iterates therefore converge to the unique solution for every starting vector, which is the jacobi convergence for a symmetric positive-definite tridiagonal matrix.
Successive over-relaxation 2026-10-05
For a splitting , successive over-relaxation updatesIt reduces to the Gauss-Seidel method at . If is symmetric positive definite, the Householder-John theorem applies to , , since is positive definite for .