Linear Systems and Direct Methods

What is a Linear System?

A linear system is a collection of linear equations that must be satisfied simultaneously. Each equation represents a constraint, and the solution is a set of values that satisfies all constraints at once.

• Example: Mixing solutions problem: Let x = litres of 10% solution, y = litres of 30% solution.

  • Constraint 1: x + y = 20

  • Constraint 2: 0.10x + 0.30y = 4.8

  The solution is the intersection point of the two equations.

• Geometric Interpretation: In two variables, each equation is a line; the solution is their intersection.

Types of Solutions for Linear Systems

A system of two equations in two unknowns can have:

• One solution: Lines intersect at a single point.

• No solution: Lines are parallel and distinct.

• Infinitely many solutions: Lines coincide (are the same).

Matrix Representation of Linear Systems

Systems can be written in matrix form as , where:

• A is the matrix of coefficients

• x is the vector of unknowns

• b is the vector of constants

Example:

Determinants and Uniqueness of Solutions

The determinant of a square matrix A, denoted , indicates whether a unique solution exists:

• If , there is a unique solution.

• If , there is either no solution or infinitely many solutions.

2x2 Determinant Formula:

Geometric Meaning: In 2D, is the area scaling factor; in 3D, it is the volume scaling factor. If the determinant is zero, the system is degenerate (no unique intersection).

Conditioning and Sensitivity

Some systems are more sensitive to small changes in data than others. If lines are nearly parallel, a small change in coefficients or constants can cause a large change in the solution.

• Condition Number: (in a chosen norm). Large indicates high sensitivity.

• Residual: measures how well an approximate solution satisfies the equations.

Elimination Methods

Gaussian Elimination

Gaussian elimination systematically eliminates variables to reduce the system to upper triangular form, which can then be solved by back substitution.

• Permitted operations: swap equations, multiply by nonzero constants, add multiples of equations.

• Augmented matrix notation records the system and operations efficiently.

Back and Forward Substitution

• Back substitution: Used for upper triangular systems. Solve from the last variable upward.

• Forward substitution: Used for lower triangular systems. Solve from the first variable downward.

Back Substitution Formula:

Forward Substitution Formula:

Partial Pivoting and PLU Factorization

Partial pivoting selects the largest available pivot in each column to improve numerical stability. The process can be recorded as , where:

• P is a permutation matrix (row swaps)

• L is lower triangular (multipliers)

• U is upper triangular (result of elimination)

To solve :

1. Solve (forward substitution)

2. Solve (back substitution)

Special Factorizations

• Crout Factorization: with having ones on the diagonal.

• Cholesky Factorization: For symmetric positive-definite matrices, .

Tridiagonal Systems and the Thomas Algorithm

A tridiagonal matrix has nonzero entries only on the main diagonal and the two adjacent diagonals. The Thomas algorithm is an efficient elimination method for such systems, requiring operations.

Thomas Algorithm Steps:

• Forward sweep: eliminate lower diagonal

• Back substitution: solve for variables

Iterative Methods

Jacobi and Gauss–Seidel Methods

Iterative methods generate a sequence of approximations to the solution, starting from an initial guess.

• Jacobi Method: Each new value uses only values from the previous iteration.

• Gauss–Seidel Method: Each new value uses the most recently updated values as soon as they are available.

Jacobi Update Formula:

Gauss–Seidel Update Formula:

Convergence and Stopping Criteria

• Residual:

• Stopping criteria: Stop when the change between iterations or the residual is below a tolerance, or after a maximum number of iterations.

• Strict diagonal dominance ( for all i) is a sufficient condition for convergence.

Matrix Splitting and Spectral Radius

Iterative methods can be written as , where is the iteration matrix. The method converges if the spectral radius .

Successive Over-Relaxation (SOR)

SOR modifies Gauss–Seidel by introducing a relaxation parameter :

• : under-relaxation

• : Gauss–Seidel

• : over-relaxation

SOR Update Formula: where is the Gauss–Seidel candidate.

Choosing and Checking a Method

• For small, dense systems: Gaussian elimination with partial pivoting.

• For symmetric positive-definite systems: Cholesky factorization.

• For tridiagonal systems: Thomas algorithm.

• For large, sparse systems: Iterative methods (Jacobi, Gauss–Seidel, SOR).

Always check the residual and consider the conditioning of the system to assess the reliability of the solution.