lineariteration

Linear iteration refers to an iterative method for solving systems of linear equations in which each new estimate is obtained by applying a linear function to the current estimate. In the standard stationary framework for Ax = b, the update is written as x^{k+1} = G x^k + c, where G is the iteration matrix and c is a constant vector derived from b. This form arises when a matrix decomposition A = M − N is used and the update becomes x^{k+1} = M^{-1} N x^k + M^{-1} b, so that G = M^{-1} N and c = M^{-1} b.

Convergence of a linear iteration to the solution x* of Ax = b typically requires the fixed-point equation x* = G x* + c to hold and, more importantly, a spectral radius condition: rho(G) < 1. When this holds, the error e^k = x^k − x* evolves as e^{k+1} = G e^k, so the error decreases geometrically. The rate is governed by the magnitude of the eigenvalues of G, and asymptotically the error shrinks like O(rho(G)^k). Sufficient conditions for rho(G) < 1 include certain diagonal dominance or positivity properties of A, depending on the chosen splitting A = M − N.

Common stationary linear iterations include Jacobi, Gauss-Seidel, and their variants. Jacobi uses the split A = D − (L + U) giving G_J = −D^{-1}(L + U); Gauss-Seidel uses A = (D + L) − U with G_GS = −(D + L)^{-1} U. Successive Over-Relaxation (SOR) adds a relaxation parameter ω to enhance convergence when appropriately chosen.

Linear iterations are simple and inexpensive per step but can be slow if G has eigenvalues near the unit circle. They are contrasted with non-stationary or Krylov methods, which do not fix G across iterations. They are widely used for large sparse systems, often with preconditioning to improve convergence. The term linear iteration emphasizes the linear dependence of the next estimate on the current one.