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]
For strict diagonal dominance, put
Induct 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 function
Holding 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.
If is symmetric positive definite and tridiagonal, set . Then
is positive definite. Applying the Householder-John theorem to and proves that the Jacobi iteration converges.
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.
Divide the supplied scheme by and take
Then , and is invertible because it is lower triangular with positive diagonal . Symmetry gives , so
The Householder-John theorem therefore gives convergence.
For a direct spectral proof, let . Expansion verifies . If with , then
The 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.
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 gives
If , then
The 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.
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. Thus
The Householder-John theorem now applies and proves Jacobi convergence for every initial vector. This is precisely why the tridiagonal structure matters.
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 gives
hence . The usual spectral-radius convergence criterion now proves the stated conclusion.
For the given scheme take the matrix splitting
Since is real symmetric, , and since it is positive definite, every diagonal entry in is positive. Thus
is positive definite exactly for . The theorem applies, and the iteration matrix has spectral radius below one. The unique solution is its fixed point, so . Therefore
The scheme is successive over-relaxation; at it becomes the Gauss-Seidel method.
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 matrix
Tridiagonality gives
Since 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.
The Householder-John theorem states the following. Let
be a splitting in which is Hermitian positive definite. If
is 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 therefore
contradicting the positive definiteness of .
Now let with . Then , so
Put and . Since ,
Consequently,
It follows that . Thus , proving the theorem.
Write
where and are the strict lower and upper triangular parts. The Jacobi method is
with iteration matrix
Here is symmetric, so . Regard the iteration as the splitting
Let
Because is tridiagonal, changing alternating signs reverses the sign of every off-diagonal entry while preserving every diagonal entry. Therefore
Since and is positive definite, is positive definite. The Householder-John theorem now gives
The Jacobi iterates therefore converge to the unique solution for every starting vector, which is the jacobi convergence for a symmetric positive-definite tridiagonal matrix.
For a splitting , successive over-relaxation updates
It reduces to the Gauss-Seidel method at . If is symmetric positive definite, the Householder-John theorem applies to , , since is positive definite for .