Linear Systems and Solution Methods: Study Notes for College Algebra

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. Equations:

  • $x + y = 20$ (total volume constraint)

  • $0.10x + 0.30y = 4.8$ (dissolved substance constraint)

  The solution is the intersection point of the two lines represented by these equations.

Geometric Interpretation of Linear Equations

Each linear equation in two variables ($ax + by = c$) represents a straight line. The solution to a system is the intersection point(s) of these lines.

• One solution: Lines intersect at a single point.

• No solution: Lines are parallel and distinct.

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

Determinants and Uniqueness of Solutions

The determinant of a square matrix indicates whether a system has a unique solution.

• If $\det(A) \neq 0$, the system has a unique solution.

• If $\det(A) = 0$, the system has either no solution or infinitely many solutions.

2x2 Determinant:

$\det\left(\begin{bmatrix} a & b \\ c & d \end{bmatrix}\right) = ad - bc$

3x3 Determinant (by elimination): Reduce to upper triangular form and multiply the diagonal entries.

Matrix Notation

Systems of equations can be written compactly as $Ax = b$, where $A$ is the coefficient matrix, $x$ is the vector of unknowns, and $b$ is the vector of constants.

Conditioning and Sensitivity

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

• Condition number: $\kappa(A) = \|A\|\|A^{-1}\|$ (measures sensitivity)

• Residual: $r = b - Ax_{\text{approx}}$ (measures how well an approximate solution satisfies the equations)

Elimination and Triangular Systems

Elimination Method

Elimination transforms the system into an equivalent upper triangular system, which can be solved by back substitution.

• Permitted operations: swap equations, multiply by nonzero constants, add multiples of one equation to another.

Augmented Matrix

The augmented matrix records the coefficients and constants, making elimination systematic:

$\begin{bmatrix} 1 & 1 & | & 5 \\ 2 & -1 & | & 1 \end{bmatrix}$

Back and Forward Substitution

• Back substitution: Used for upper triangular systems, solve from bottom to top.

• Forward substitution: Used for lower triangular systems, solve from top to bottom.

General formula for back substitution:

$x_i = \frac{1}{u_{ii}} \left( y_i - \sum_{j=i+1}^n u_{ij} x_j \right)$

General formula for forward substitution:

$y_i = \frac{1}{\ell_{ii}} \left( b_i - \sum_{j=1}^{i-1} \ell_{ij} y_j \right)$

Gaussian Elimination, Pivoting, and Factorisations

Gaussian Elimination

Gaussian elimination systematically applies elimination to reduce a matrix to upper triangular form.

• Partial pivoting: Swap rows to ensure the largest available pivot is used, improving numerical stability.

PLU Factorisation

With pivoting, the factorisation $PA = LU$ is used, where $P$ is a permutation matrix, $L$ is lower triangular, and $U$ is upper triangular.

• To solve $Ax = b$:

  • Solve $Ly = Pb$ (forward substitution)

  • Solve $Ux = y$ (back substitution)

Crout and Cholesky Factorisations

• Crout: $A = LU$ with $U$ having ones on the diagonal.

• Cholesky: For symmetric positive-definite matrices, $A = LL^T$.

Tridiagonal Systems and the Thomas Algorithm

For tridiagonal matrices, the Thomas algorithm efficiently solves the system in $O(n)$ operations by exploiting the structure.

Iterative Methods

Jacobi and Gauss–Seidel Methods

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

• Gauss–Seidel: Uses the most recently updated values as soon as they are available.

Jacobi update formula:

$x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j \neq i} a_{ij} x_j^{(k)} \right)$

Gauss–Seidel update formula:

$x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j < i} a_{ij} x_j^{(k+1)} - \sum_{j > i} a_{ij} x_j^{(k)} \right)$

Convergence and Stopping Criteria

• Residual test: $\|b - Ax^{(k+1)}\|_\infty < \varepsilon$

• Iterate-change test: $\|x^{(k+1)} - x^{(k)}\|_\infty < \varepsilon$

• Strict diagonal dominance: $|a_{ii}| > \sum_{j \neq i} |a_{ij}|$ for all $i$ (sufficient for convergence)

Matrix Splitting and Spectral Radius

Iterative methods can be written as $x^{(k+1)} = T x^{(k)} + c$, where $T$ is the iteration matrix. The method converges if the spectral radius $\rho(T) < 1$.

Successive Over-Relaxation (SOR)

SOR modifies Gauss–Seidel by introducing a relaxation parameter $\omega$:

$x_i^{(k+1)} = (1 - \omega)x_i^{(k)} + \omega \tilde{x}_i^{(k+1)}$

• $0 < \omega < 1$: under-relaxation

• $\omega = 1$: Gauss–Seidel

• $1 < \omega < 2$: over-relaxation

Choosing and Checking a Method

• Small dense systems: Gaussian elimination with partial pivoting.

• Symmetric positive-definite: Cholesky factorisation.

• Tridiagonal: Thomas algorithm.

• Large sparse: Iterative methods (Jacobi, Gauss–Seidel, SOR).

Always check the residual to verify the accuracy of the computed solution, especially in sensitive or ill-conditioned systems.

Summary Table: Methods for Solving Linear Systems

Method	When to Use	Key Features
Gaussian Elimination	Small to medium dense systems	Direct, uses elimination and back substitution
PLU Factorisation	Multiple right-hand sides	Stores elimination for reuse
Cholesky	Symmetric positive-definite matrices	Efficient, stores one triangular factor
Thomas Algorithm	Tridiagonal matrices	Linear time, exploits structure
Jacobi	Large sparse systems	Simple, simultaneous updates
Gauss–Seidel	Large sparse systems	Sequential updates, faster convergence
SOR	Large sparse systems	Adjustable relaxation, can accelerate convergence

Additional info: These notes expand on the provided material with definitions, formulas, and structured explanations suitable for College Algebra students. The content covers core topics in linear systems, elimination, determinants, conditioning, and iterative methods, all of which are foundational in College Algebra and related courses.