Update the unknowns in row order, immediately using newly computed components. The component equations areThus and . Using only old values in all three row equations would instead describe the Jacobi method, not the Gauss-Seidel method.
From zero, the first update is . For the next update, the first component is , the second is , and the third is . Therefore .
For the spectral error bound for a diagonalizable fixed-point iteration, the exact solution is a fixed point: . Subtracting it from the iteration gives the error recurrence , with . Multiplying by and using givesIterating proves , including because . This argument does not assume is orthogonal; it simply expresses the error in an eigenbasis.
Write and let . The stated Euclidean norm givesTaking nonnegative square roots proves . At this is equality. This is a contraction bound in the transformed coordinates; an arbitrary nonorthogonal does not give the same unit-constant bound for the original error norm.
The iteration matrix has eigenvalues : expanding its characteristic polynomial down the first column leaves the triangular two-by-two block with diagonal entries . The distinct eigenvalues ensure diagonalizability. Thus its spectral radius is .
The previous bound gives , so the Gauss-Seidel iteration converges for every initial guess under the stated diagonalization. Its limit is the exact solution . Since , a fixed matrix also sends this transformed error to zero; its operator norm can account for any amplification in the original coordinates.
Articles by others on the same topic
There are currently no matching articles.