--- title: "Iterative Methods for Large Linear Systems" description: "Iterative methods build successive approximations to solutions of large sparse linear systems. Stationary iterations converge from every start when their iteration matrix has spectral radius below 1. " canonical: https://lightmysky.com/learn/mathematics/iterative-methods-for-large-linear-systems-mt_FKkxKYVGYJ source: https://lightmysky.com/learn/mathematics/iterative-methods-for-large-linear-systems-mt_FKkxKYVGYJ.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Iterative Methods for Large Linear Systems Iterative methods build successive approximations to solutions of large sparse linear systems. Stationary iterations converge from every start when their iteration matrix has spectral radius below 1. Suitable preconditioning can reduce the work needed. Subject: Mathematics · Area: Linear Algebra · Ages 23 to 24 Page: https://lightmysky.com/learn/mathematics/iterative-methods-for-large-linear-systems-mt_FKkxKYVGYJ ## Ready when they can - Run a splitting step, calculate a residual to check a guess, and state the iteration's convergence condition - Say why the conjugate gradient method needs a symmetric positive definite matrix - Explain what a preconditioner changes and why that helps ## Lesson: Solving big systems by approximation You have seen how LU factors can serve repeated solves. For a large sparse matrix, factorisation may require too much storage or work, but it can still be suitable. An iterative method builds successive guesses. Check a guess x with its residual r = b - Ax: multiply by A, then subtract from b. For an ill-conditioned matrix, a small residual need not mean a small solution error. A splitting writes A = B - C, where B is invertible and cheap to solve. Repeat B x_next = C x_old + b; the iteration matrix is T = B^-1 C. Jacobi takes B as the diagonal of A, so those diagonal entries must be nonzero. It computes every new coordinate from old values. Gauss-Seidel instead uses each fresh coordinate as soon as it is available. **Example.** For 5x + y = 11 and x + 4y = 9, Jacobi uses x_next = (11 - y_old)/5 and y_next = (9 - x_old)/4. From (0,0), the first guess is (2.2,2.25). The next guess is (1.75,1.7). Both second-step updates use the first guess: y_next uses x_old = 2.2, not the fresh x value 1.75. *(drawing: Each Jacobi pair is calculated from the entire previous pair.)* A stationary iteration fixes T and c: x_next = T x_old + c. If the solution x_star is a fixed point, subtract its equation: e = x - x_star obeys e_next = T e_old. An eigenvalue lambda satisfies T v = lambda v for nonzero v; lambda and v may be complex. The spectral radius rho(T) is the largest eigenvalue magnitude. Convergence to x_star from every start holds exactly when rho(T) < 1. Error need not decrease at each step. Starting at x_star stays there even if rho(T) >= 1. Strict row diagonal dominance means that, in each row, the absolute diagonal entry exceeds the sum of the absolute off-diagonal entries. It guarantees convergence of Jacobi and Gauss-Seidel from every start. It is sufficient, not necessary: without it, Jacobi may still converge. In the worked system, 5 > 1 and 4 > 1, so the guarantee applies. A real matrix is SPD (symmetric positive definite) if A = A^T and v^T A v > 0 for every nonzero v. For symmetric A, this is equivalent to all eigenvalues being positive. A diagonal matrix is symmetric; its diagonal entries are its eigenvalues. One nonzero v with v^T A v < 0 rules out positive definiteness; positive diagonal entries alone do not prove it. The span of vectors is the set of all their linear combinations. The conjugate gradient method is abbreviated CG. For symmetric A, f(x) = (1/2)x^T A x - b^T x has gradient Ax - b, the vector of first partial derivatives. SPD makes f strictly convex: strictly below each chord between its endpoints. Its unique minimum solves Ax = b. Standard CG needs both assumptions. From start x0, its kth iterate minimizes f over nested affine sets x0 + K_k in exact arithmetic. For k >= 1, K_k is the span of r0, Ar0, ..., A^(k-1)r0, where r0 = b - Ax0. CG need not be faster than another solver. Choose an invertible preconditioner M whose systems are cheap to solve. Left preconditioning gives M^-1 A x = M^-1 b. Transform both sides to preserve the exact solution. Apply M^-1 by solving with M, rather than forming an inverse. For M = diag(2,5) and b = (8,15), solve M c = b to get c = (4,3). A diagonal solve divides each component by its diagonal entry. For CG, use a symmetric positive definite M through preconditioned CG. Do not apply ordinary CG blindly to M^-1 A: it need not be symmetric in the usual inner product. A smaller ratio of largest to smallest preconditioned eigenvalue can improve the convergence bound; clustering can also help. Neither improvement nor a faster total solve is automatic. Solving with M also has a cost. **Recap.** Jacobi uses old values. Stationary convergence from every start needs rho(T) < 1. Standard CG needs SPD assumptions. Judge preconditioning by its effect and cost. *The lesson, practice questions and flashcards were written for this dataset.* ## Practice 14 questions on this page, each with its working shown. ## Needs first - [LU Factorisation, Pivoting and the Cost of a Solve](https://lightmysky.com/learn/mathematics/lu-factorisation-pivoting-and-the-cost-of-a-solve-mt_5Gg2v3Oxrr) - [Conditioning, Stability and Floating-Point Error](https://lightmysky.com/learn/mathematics/conditioning-stability-and-floating-point-error-mt_q8IoCElXIV) ## Optional connections - [Symmetric Matrices and the Spectral Theorem](https://lightmysky.com/learn/mathematics/symmetric-matrices-and-the-spectral-theorem-mt_sdQv4m7Nbk)