Iterative methods replace exact factorization by a sequence of approximate solutions, which is essential for large sparse systems.
Stationary iteration
Definition. A stationary linear iteration has the form \(x_{k+1}=Gx_k+c\). It converges for every initial point exactly when the spectral radius \(\rho(G)\lt1\).
Jacobi and Gauss-Seidel
Proposition. Splitting \(A=D-L-U\) gives Jacobi and Gauss-Seidel iterations by solving with different easy parts of \(A\). Their convergence depends on matrix structure such as diagonal dominance or positive definiteness.
Residual correction
Definition. Most iterative methods can be read as repeatedly correcting the residual \(r_k=b-Ax_k\). A good correction approximately solves \(Ae_k=r_k\) without solving the full system exactly.
Conjugate gradient
Theorem. For symmetric positive definite \(A\), conjugate gradient minimizes the \(A\)-norm of the error over \(x_0+\mathcal K_k(A,r_0)\). Its convergence depends on the distribution of eigenvalues, especially the effective condition number.
Stopping rules
Remark. A small residual is not the same as a small error unless conditioning is controlled. Practical stopping rules combine relative residuals, preconditioned residuals, iteration budgets, and the accuracy required by the outer problem.
Stationary iterations
Split \(A=M-N\) with easily invertible \(M\). The iteration \[ x_{k+1}=M^{-1}Nx_k+M^{-1}b \] has error \[ e_{k+1}=Ge_k,\qquad G=M^{-1}N. \]
Theorem. A stationary iteration converges for every initial vector if and only if \[ \rho(G)<1. \]
Proof. Convergence for every initial error is equivalent to \(G^k\to0\). If \(G^k\to0\), every eigenvalue satisfies \(\lambda^k\to0\), so \(\rho(G)<1\). Conversely, put \(G\) in Jordan form. Every block contributes a polynomial in \(k\) times \(|\lambda|^k\), which tends to zero when all \(|\lambda|<1\).
Jacobi and Gauss--Seidel
With \(A=D-L-U\), Jacobi uses \(M=D\), while Gauss--Seidel uses \(M=D-L\). Strict row diagonal dominance guarantees convergence of both. For symmetric positive definite \(A\), Gauss--Seidel converges; Jacobi needs additional spectral conditions.
Proposition (diagonal dominance). If \[ |a_{ii}|>\sum_{j\ne i}|a_{ij}| \quad\text{for every }i, \] then the Jacobi iteration matrix has \(\|G_J\|_\infty<1\).
Proof. Row \(i\) of \(G_J\) has off-diagonal entries \(-a_{ij}/a_{ii}\), so its absolute row sum is strictly below one.
Richardson iteration
For symmetric positive definite \(A\), \[ x_{k+1}=x_k+\omega(b-Ax_k) \] converges when \(0<\omega<2/\lambda_{\max}\). The optimal fixed step is \[ \omega_*=\frac{2}{\lambda_{\min}+\lambda_{\max}}, \] with contraction factor \[ \frac{\kappa_2(A)-1}{\kappa_2(A)+1}. \] This is gradient descent on \(\tfrac12x^\top Ax-b^\top x\); poor conditioning makes contours elongated and slows convergence.
Residuals and stopping
The residual satisfies \(r_k=Ae_k\), so \[ \frac{\|e_k\|}{\|x\|} \le\kappa(A)\frac{\|r_k\|}{\|b\|}. \] A residual tolerance should therefore account for conditioning and data error. Iteration beyond the noise floor can waste work or amplify model error. For preconditioned systems, monitor a norm tied to the original residual, not only the transformed recurrence.
Asynchronous iterations
For contractions in a monotone norm, coordinates may be updated with bounded delays and fair scheduling while retaining convergence. This supports parallel relaxation. Without contraction or with unbounded stale data, asynchronous updates can diverge even if synchronous iteration converges.