From the free course CS323: Numerical Analysis and Computing on Lykke
Solving Systems of Linear Equations (Ax=b)
Key concepts: Direct Methods · Iterative Methods · LU Factorization · Gaussian Elimination · Pivoting Strategies · Jacobi Method · Gauss-Seidel Method · Least Squares & Normal Equations · Computational Cost
This section explores the primary methods for solving systems of linear equations, a cornerstone of numerical computing. It contrasts direct methods like LU factorization with iterative methods such as Jacobi and Gauss-Seidel, analyzing their computational costs and stability. The section also covers the practical importance of pivoting and introduces least squares for solving overdetermined systems.
Solving Systems of Linear Equations (Ax=b)
The problem of solving a system of linear equations is one of the most fundamental and ubiquitous tasks in computational science. Represented in matrix form as Ax = b, where A is a known n x n matrix of coefficients, b is a known n x 1 column vector of constants, and x is the n x 1 column vector of unknown variables, this equation appears in fields as diverse as structural engineering, circuit analysis, machine learning, and economic modeling.
At its core, solving Ax = b means finding the vector x that, when transformed by the matrix A, yields the vector b. Geometrically, it's equivalent to finding the unique linear combination of the columns of A that produces b. The methods for finding this solution fall into two broad categories: direct methods, which compute the solution in a fixed number of steps, and iterative methods, which refine an initial guess until a desired level of accuracy is reached. The choice between these approaches depends critically on the size, structure, and properties of the matrix A.
This article provides a deep dive into the theory, implementation, and practical considerations of the most important algorithms for solving Ax=b.
Direct Methods: Finite-Step Solutions
Direct methods are algorithms that find the exact solution to Ax=b in a finite and predetermined number of computational steps, assuming perfect arithmetic without any round-off errors. For a system of n equations, the number of operations is a fixed function of n. The foundational algorithm for this class of methods is Gaussian Elimination, which is more formally and efficiently implemented in modern software as LU Factorization.
Gaussian Elimination
What It Is
Gaussian Elimination is the classical algorithm for solving linear systems. It systematically transforms a system of equations into an equivalent upper triangular system, which can then be easily solved using a process called back substitution. The transformation is achieved by applying a sequence of elementary row operations:
- Swapping two rows.
- Multiplying a row by a non-zero scalar.
- Adding a multiple of one row to another row.
Key Insight: Applying these operations to the augmented matrix
[A|b]does not change the solutionxof the system. The goal is to use these operations to introduce zeros below the main diagonal of theAportion of the matrix.
How It Works
The algorithm proceeds in two main phases:
-
Forward Elimination: The goal is to convert the matrix
Ainto an upper triangular matrixU. This is done column by column.- For the first column, use the first row (the pivot row) to create zeros in all entries below the first element (
A[1,1]). This is done by subtracting a suitable multiple of the first row from each subsequent row. - For the second column, use the second row to create zeros in all entries below the second diagonal element (
A[2,2]). - This process continues for
n-1columns.
- For the first column, use the first row (the pivot row) to create zeros in all entries below the first element (
-
Backward Substitution: After forward elimination, the augmented matrix is in the form
[U|b'], whereUis upper triangular. The systemUx = b'can be solved easily, starting from the last equation.- The last equation involves only
x_n, so it can be solved directly:x_n = b'_n / U[n,n]. - The second-to-last equation involves
x_nandx_{n-1}. Sincex_nis now known,x_{n-1}can be solved for. - This process continues backward until all components of
xare found.
- The last equation involves only
Concrete Example
Consider the system:
2x₁ + x₂ - x₃ = 8
-3x₁ - x₂ + 2x₃ = -11
-2x₁ + x₂ + 2x₃ = -3
The augmented matrix is:
[ 2 1 -1 | 8 ]
[-3 -1 2 | -11]
[-2 1 2 | -3 ]
Step 1: Forward Elimination
- Target: Zeros in the first column below the diagonal.
R₂ → R₂ - (-3/2) * R₁R₃ → R₃ - (-2/2) * R₁The matrix becomes:
[ 2 1 -1 | 8 ]
[ 0 1/2 1/2 | 1 ]
[ 0 2 1 | 5 ]
- Target: Zero in the second column below the diagonal.
R₃ → R₃ - (2 / (1/2)) * R₂ = R₃ - 4 * R₂The matrix becomes:
[ 2 1 -1 | 8 ]
[ 0 1/2 1/2 | 1 ]
[ 0 0 -1 | 1 ]
The system is now upper triangular.
Step 2: Backward Substitution The new system of equations is:
2x₁ + x₂ - x₃ = 8
1/2x₂ + 1/2x₃ = 1
-x₃ = 1
- From the last equation:
x₃ = -1. - Substitute into the second equation:
1/2x₂ + 1/2(-1) = 1⇒1/2x₂ = 3/2⇒x₂ = 3. - Substitute into the first equation:
2x₁ + (3) - (-1) = 8⇒2x₁ + 4 = 8⇒2x₁ = 4⇒x₁ = 2.
The solution is x = [2, 3, -1]ᵀ.
Common Pitfalls
The naive algorithm fails if a diagonal element (a pivot) used for elimination is zero. Even worse, if a pivot is very small relative to other entries, the algorithm becomes numerically unstable due to floating-point errors. This happens because we divide by the pivot, and division by a small number amplifies any existing round-off error. This critical issue motivates the need for pivoting strategies.
LU Factorization: A Formalization of Elimination
What It Is
LU Factorization (or LU Decomposition) is the matrix representation of Gaussian Elimination. It decomposes a square matrix A into the product of a lower triangular matrix L and an upper triangular matrix U.
A = LU
Definition:
- A lower triangular matrix
Lhas all its entries above the main diagonal equal to zero (L[i,j] = 0fori < j). - An upper triangular matrix
Uhas all its entries below the main diagonal equal to zero (U[i,j] = 0fori > j).
By convention, the diagonal elements of L are set to 1 (this is called a Doolittle decomposition). The matrix U is the same upper triangular matrix obtained from Gaussian Elimination. The matrix L stores the multipliers used during the elimination process.
Why It Matters
LU factorization decouples the elimination process (which depends only on A) from the vector b. The decomposition A = LU needs to be computed only once. Then, to solve Ax=b for any given b, we solve two much simpler triangular systems:
- Substitute
A=LUintoAx=bto getLUx = b. - Define an intermediate vector
y = Ux. - First, solve
Ly = bfory. This is called forward substitution. - Then, solve
Ux = yforx. This is called backward substitution.
This is extremely efficient when solving a system with the same coefficient matrix A but many different right-hand side vectors b. The expensive O(n³) decomposition is done once, and each subsequent solve only requires two O(n²) substitutions.
How It Works
The U matrix is the result of the forward elimination phase of Gaussian Elimination. The L matrix is constructed from the multipliers used. Specifically, if we subtract m_{ij} times row j from row i to create a zero at position (i,j), then the entry L[i,j] is exactly m_{ij}.
Let's implement Doolittle's algorithm, which computes L and U directly.
import numpy as np
def lu_factorization(A):
"""
Performs LU factorization of a square matrix A using Doolittle's algorithm.
A = LU, where L is lower triangular with unit diagonal, and U is upper triangular.
Args:
A (np.ndarray): A square n x n matrix.
Returns:
(np.ndarray, np.ndarray): A tuple containing the L and U matrices.
"""
n = A.shape[0]
if A.shape[1] != n:
raise ValueError("Input matrix must be square.")
L = np.zeros((n, n))
U = np.zeros((n, n))
for k in range(n):
# Set diagonal of L to 1
L[k, k] = 1.0
# Calculate U for the current row k
# U[k, j] = A[k, j] - sum(L[k, i] * U[i, j] for i in 0..k-1)
for j in range(k, n):
sum_lu = sum(L[k, i] * U[i, j] for i in range(k))
U[k, j] = A[k, j] - sum_lu
# Calculate L for the current column k
# L[i, k] = (A[i, k] - sum(L[i, j] * U[j, k] for j in 0..k-1)) / U[k, k]
for i in range(k + 1, n):
if U[k, k] == 0:
# This indicates the matrix is singular or requires pivoting.
# A robust implementation would handle this with pivoting.
raise np.linalg.LinAlgError("Zero pivot encountered. Pivoting is required.")
sum_lu = sum(L[i, j] * U[j, k] for j in range(k))
L[i, k] = (A[i, k] - sum_lu) / U[k, k]
return L, U
# Example from the Gaussian Elimination section
A = np.array([[2., 1., -1.],
[-3., -1., 2.],
[-2., 1., 2.]])
L, U = lu_factorization(A)
print("Matrix A:\n", A)
print("\nLower Triangular L:\n", L)
print("\nUpper Triangular U:\n", U)
print("\nVerification (L @ U):\n", L @ U)
Pivoting Strategies: Ensuring Numerical Stability
What It Is
As noted, Gaussian Elimination and LU Factorization can fail or become numerically unstable if a pivot element A[k,k] is zero or very small. Pivoting is a strategy of reordering the rows (and/or columns) of the matrix during factorization to ensure that the pivot element is as large as possible.
Why It Matters
Using a large pivot element minimizes the magnitude of the multipliers m_{ij}. This prevents the subtraction of nearly equal numbers and reduces the propagation of round-off errors, making the algorithm dramatically more stable and reliable in floating-point arithmetic. For all practical purposes, direct solvers are always implemented with pivoting.
How It Works
The most common strategy is Partial Pivoting:
- At step
kof the elimination (for columnk), search for the element with the largest absolute value in the current column at or below the diagonal (A[i,k]fori >= k). - Let this largest element be at row
p. - Swap row
kwith rowp. - Proceed with the elimination step as usual, using the new, larger pivot element
A[k,k].
This process of row-swapping can be represented by a permutation matrix P. A permutation matrix is an identity matrix with its rows reordered. Applying pivoting to A is equivalent to performing the factorization on a row-permuted version of A. The resulting factorization is:
PA = LU
To solve Ax=b, we first apply the same permutations to b by computing Pb, and then solve the system LUx = Pb.
Mathematical Representation of Pivoting
Without pivoting, the decomposition is A = LU. With partial pivoting, we introduce a permutation matrix P that encodes all the row swaps performed during the factorization.
// Without Pivoting:
A = \begin{pmatrix} 2 & 1 & -1 \\ -3 & -1 & 2 \\ -2 & 1 & 2 \end{pmatrix}
= \begin{pmatrix} 1 & 0 & 0 \\ -1.5 & 1 & 0 \\ -1 & 4 & 1 \end{pmatrix}
\begin{pmatrix} 2 & 1 & -1 \\ 0 & 0.5 & 0.5 \\ 0 & 0 & -1 \end{pmatrix}
= L \cdot U
// With Partial Pivoting:
// At step 1, the largest element in column 1 is -3 (row 2). Swap R1 and R2.
// This corresponds to a permutation matrix P1.
P_1 = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}
A' = P_1 A = \begin{pmatrix} -3 & -1 & 2 \\ 2 & 1 & -1 \\ -2 & 1 & 2 \end{pmatrix}
// Now we factor A'. The process continues, potentially with more swaps.
// The final result is PA = LU, where P is the product of all permutation matrices.
// For our example, the final P would be:
P = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}
// The factorization becomes PA = LU, which is numerically stable.
Iterative Methods: Refining an Initial Guess
For very large and sparse systems (where most entries in A are zero), direct methods like LU factorization become computationally prohibitive. The O(n³) complexity is too high, and a more subtle problem called fill-in occurs: the L and U factors of a sparse matrix can be much denser than the original matrix A, leading to excessive memory usage.
Iterative methods provide an alternative. They start with an initial guess for the solution, x^(0), and iteratively generate a sequence of approximations x^(1), x^(2), ... that (ideally) converge to the true solution.
General Form: Most simple iterative methods can be expressed as a fixed-point iteration:
x^(k+1) = T * x^(k) + cwhereTis the iteration matrix andcis a vector, both derived fromAandb. The method converges if and only if the spectral radius (the largest absolute eigenvalue) ofTis less than 1.
A sufficient (but not necessary) condition for convergence of many methods is that the matrix A is strictly diagonally dominant.
Definition: Strictly Diagonally Dominant A matrix
Ais strictly diagonally dominant if, for every row, the absolute value of the diagonal element is greater than the sum of the absolute values of all other elements in that row.|A[i,i]| > Σ_{j≠i} |A[i,j]|for alli.
The Jacobi Method
What It Is
The Jacobi method is the simplest iterative scheme. To compute the i-th component of the new approximation x_i^(k+1), it uses only the components from the previous approximation x^(k). All components of the new vector are computed simultaneously (or in parallel) before updating.
How It Works (Derivation)
- Decompose the matrix
Ainto its diagonal (D), strictly lower triangular (-L*), and strictly upper triangular (-U*) parts:A = D - L* - U*. - The system
Ax=bbecomes(D - L* - U*)x = b. - Isolate the term with the diagonal matrix:
Dx = (L* + U*)x + b. - This naturally suggests an iterative formula by using the old
xon the right to compute the newxon the left:Dx^(k+1) = (L* + U*)x^(k) + b - Solving for
x^(k+1)gives the Jacobi iteration:x^(k+1) = D⁻¹(L* + U*)x^(k) + D⁻¹b
In component form, the update rule for each x_i is:
x_i^(k+1) = (1 / A[i,i]) * (b_i - Σ_{j≠i} A[i,j] * x_j^(k))
Concrete Example
Consider the diagonally dominant system:
4x₁ - x₂ - x₃ = 1
-x₁ + 4x₂ - x₃ = 4
-x₁ - x₂ + 4x₃ = -7
Let the initial guess be x^(0) = [0, 0, 0]ᵀ.
Iteration 1:
x₁^(1) = (1/4) * (1 - (-1*0) - (-1*0)) = 0.25
x₂^(1) = (1/4) * (4 - (-1*0) - (-1*0)) = 1.0
x₃^(1) = (1/4) * (-7 - (-1*0) - (-1*0)) = -1.75
So, x^(1) = [0.25, 1.0, -1.75]ᵀ.
Iteration 2:
x₁^(2) = (1/4) * (1 - (-1*1.0) - (-1*-1.75)) = (1/4) * (1 + 1.0 - 1.75) = 0.0625
x₂^(2) = (1/4) * (4 - (-1*0.25) - (-1*-1.75)) = (1/4) * (4 + 0.25 - 1.75) = 0.625
x₃^(2) = (1/4) * (-7 - (-1*0.25) - (-1*1.0)) = (1/4) * (-7 + 0.25 + 1.0) = -1.4375
So, x^(2) = [0.0625, 0.625, -1.4375]ᵀ.
This process continues until ||x^(k+1) - x^(k)|| is below a specified tolerance. The true solution is x = [0, 1, -1.5]ᵀ.
Variations and Extensions
- Gauss-Seidel Method: A simple but often significant improvement over Jacobi. When computing
x_i^(k+1), it immediately uses the already updated valuesx_1^(k+1), ..., x_{i-1}^(k+1)in the same iteration. This typically leads to faster convergence. - Successive Over-Relaxation (SOR): An extension of Gauss-Seidel that introduces a relaxation parameter
ωto potentially accelerate convergence further. - Conjugate Gradient Method: A more advanced and powerful iterative method suitable for symmetric positive-definite matrices. It often converges much faster than Jacobi or Gauss-Seidel.
Real-World Usage with a Library
In practice, you would rarely implement these methods from scratch. Scientific computing libraries provide robust, optimized implementations. Here is how you might solve a large, sparse system using SciPy.
# First, ensure you have the necessary libraries installed
pip install numpy scipy
import numpy as np
from scipy.sparse import diags
from scipy.sparse.linalg import spsolve, cg
# --- 1. Direct Solver for a Dense Matrix ---
# Create a small, dense, well-conditioned matrix
A_dense = np.array([[4., -1., -1.], [-1., 4., -1.], [-1., -1., 4.]])
b_dense = np.array([1., 4., -7.])
# Use a direct solver (typically LU-based) from NumPy
print("--- Direct Method (NumPy) ---")
x_direct = np.linalg.solve(A_dense, b_dense)
print(f"Solution: {x_direct}")
print(f"Residual norm: {np.linalg.norm(A_dense @ x_direct - b_dense):.2e}\n")
# --- 2. Iterative Solver for a Large, Sparse Matrix ---
# Create a large, sparse, diagonally dominant matrix
# This represents a 1D finite difference discretization of a PDE
n = 10000
diagonals = [[-1] * (n - 1), [4] * n, [-1] * (n - 1)]
A_sparse = diags(diagonals, [-1, 0, 1], format='csr') # Compressed Sparse Row format
b_sparse = np.random.rand(n)
# Using a direct sparse solver (might be slow/memory intensive for huge n)
# from scipy.sparse.linalg import spsolve
# x_sparse_direct = spsolve(A_sparse, b_sparse)
# Use an iterative solver: Conjugate Gradient (cg)
print("--- Iterative Method (SciPy Conjugate Gradient) ---")
# The 'cg' function returns the solution and an info code (0 for success)
x_iterative, info = cg(A_sparse, b_sparse, tol=1e-8)
if info == 0:
print(f"Solution for first 5 elements: {x_iterative[:5]}")
residual_norm = np.linalg.norm(A_sparse @ x_iterative - b_sparse)
print(f"Residual norm: {residual_norm:.2e}")
else:
print(f"Conjugate Gradient failed to converge. Info code: {info}")
Comparison: Direct vs. Iterative Methods
The choice between direct and iterative methods is a fundamental decision in numerical linear algebra, driven by the characteristics of the problem at hand.
| Feature | Direct Methods (e.g., LU Factorization with Pivoting) | Iterative Methods (e.g., Jacobi, Conjugate Gradient) |
|---|---|---|
| Solution Quality | Computes an "exact" solution (up to machine precision). | Computes an approximate solution to a specified tolerance. |
| Computational Cost | Predictable, typically O(n³) for dense matrices. |
Depends on the matrix, desired accuracy, and method. Often O(k * nnz) where k is iterations and nnz is non-zero elements. |
| Memory Usage | Can be high for large matrices due to fill-in. | Very low for sparse matrices; only the non-zero elements of A and a few vectors need to be stored. |
| Applicability | General purpose. Excellent for dense, small to medium-sized, or ill-conditioned systems. | Best for large, sparse, and well-conditioned (often diagonally dominant) systems. |
| Robustness | Very robust and reliable when implemented with pivoting. | Convergence is not guaranteed and can be slow. Performance is highly sensitive to matrix properties. Preconditioning is often required. |
| Implementation | More complex to implement correctly from scratch. | Simpler methods (like Jacobi) are easy to implement. Advanced methods are complex. |
Source Materials
Study CS323: Numerical Analysis and Computing on Lykke
This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.
Add the free extensionSign in to open every sectionAll sections of CS323: Numerical Analysis and Computing · Browse more course pages