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:

  1. Swapping two rows.
  2. Multiplying a row by a non-zero scalar.
  3. Adding a multiple of one row to another row.

Key Insight: Applying these operations to the augmented matrix [A|b] does not change the solution x of the system. The goal is to use these operations to introduce zeros below the main diagonal of the A portion of the matrix.

How It Works

The algorithm proceeds in two main phases:

  1. Forward Elimination: The goal is to convert the matrix A into an upper triangular matrix U. 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-1 columns.
  2. Backward Substitution: After forward elimination, the augmented matrix is in the form [U|b'], where U is upper triangular. The system Ux = 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_n and x_{n-1}. Since x_n is now known, x_{n-1} can be solved for.
    • This process continues backward until all components of x are found.

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 L has all its entries above the main diagonal equal to zero (L[i,j] = 0 for i < j).
  • An upper triangular matrix U has all its entries below the main diagonal equal to zero (U[i,j] = 0 for i > 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:

  1. Substitute A=LU into Ax=b to get LUx = b.
  2. Define an intermediate vector y = Ux.
  3. First, solve Ly = b for y. This is called forward substitution.
  4. Then, solve Ux = y for x. 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:

  1. At step k of the elimination (for column k), search for the element with the largest absolute value in the current column at or below the diagonal (A[i,k] for i >= k).
  2. Let this largest element be at row p.
  3. Swap row k with row p.
  4. 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) + c where T is the iteration matrix and c is a vector, both derived from A and b. The method converges if and only if the spectral radius (the largest absolute eigenvalue) of T is 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 A is 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 all i.

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)

  1. Decompose the matrix A into its diagonal (D), strictly lower triangular (-L*), and strictly upper triangular (-U*) parts: A = D - L* - U*.
  2. The system Ax=b becomes (D - L* - U*)x = b.
  3. Isolate the term with the diagonal matrix: Dx = (L* + U*)x + b.
  4. This naturally suggests an iterative formula by using the old x on the right to compute the new x on the left: Dx^(k+1) = (L* + U*)x^(k) + b
  5. 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 values x_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.
Solving Systems of Linear Equations (Ax=b) - CS323: Numerical Analysis and Computing - diagram 1
Solving Systems of Linear Equations (Ax=b) - CS323: Numerical Analysis and Computing - diagram 1

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 section

All sections of CS323: Numerical Analysis and Computing · Browse more course pages