PadhaikoAll subjects

Solution of System of Linear Algebraic Equations

Numerical Methods (ENSH 252)

Open in the Padhaiko app

2.1 Direct methods

A system of linear algebraic equations in unknowns is written in matrix form as:

where is the coefficient matrix, is the unknown vector, and is the constant vector. Direct methods compute the exact solution (up to machine round-off error) in a finite, predetermined number of arithmetic operations through elementary row transformations or matrix factorization.

2.1.1 Gauss Jordan method

The Gauss–Jordan method extends elimination so that the augmented matrix is reduced directly to reduced row echelon form . Because both elements below and above each pivot are eliminated and each pivot row is scaled to have leading , the solution vector is read off directly without back substitution.

Definition

Gauss–Jordan Reduction Procedure

Given the augmented matrix :

  1. For each pivot column :
    • If needed, swap row with a lower row so the pivot (partial pivoting).
    • Normalize row by dividing every entry in row by so the pivot becomes :
  1. After processing all columns, the augmented matrix has the form , giving directly.

2.1.2 Gauss elimination method, pivoting strategies (Partial and complete)

The Gauss elimination method converts into an upper triangular matrix through forward elimination, and then recovers by back substitution.

Definition

Forward Elimination and Back Substitution

  1. Forward elimination (): For each row , compute the multiplier () and update:
  1. Back substitution: Once is upper triangular ( for ):

Naive Gauss elimination fails if a pivot , and suffers severe round-off error if is very small compared with other entries in its column (causing large multipliers ). Pivoting avoids division by zero and controls round-off error growth.

AspectPartial PivotingComplete Pivoting
Search Region (at stage )Current column from row down to : Entire remaining submatrix :
Permutations UsedRow exchanges only ()Both row exchanges () and column exchanges ()
Effect on Unknowns Order of variables is unchangedColumn swaps permute the components of ; must track variable order
Multiplier BoundGuarantees Guarantees with slightly stronger numerical stability
Practical UseStandard default in numerical linear algebraRarely needed except for badly conditioned matrices

2.1.3 Matrix inverse using Gauss Jordan and Gauss elimination methods

If is non-singular (), its inverse satisfies .

  1. Using Gauss–Jordan method: Form the augmented matrix . Apply Gauss–Jordan elementary row operations to reduce the left half to the identity matrix . The same sequence of row operations transforms on the right into :
  1. Using Gauss elimination method: Solve linear systems (), where is the -th column of and is the -th column of . In practice, form , run forward elimination once to obtain , and perform back substitution on each of the right-hand-side columns of to recover the columns of .

2.1.4 Factorization methods (Do-Little’s method and Crout’s method)

LU factorization (decomposition) expresses a square matrix (when no row interchanges are needed) as the product of a lower triangular matrix and an upper triangular matrix :

Solving then splits into two fast triangular solves:

  1. Forward substitution: Solve for .
  2. Back substitution: Solve for .

This is especially efficient when solving for multiple right-hand sides , because and are computed only once.

Because and together have unknown entries while provides equations, diagonal entries must be fixed to make the factorization unique.

AspectDoolittle's MethodCrout's Method
Diagonal NormalizationUnit lower triangular: ()Unit upper triangular: ()
3x3 Matrix Form
Computation OrderRow of (), then column of ()Column of (), then row of ()
Key Formulas,
,

2.2 Iterative methods

For large, sparse linear systems (such as those arising from finite-difference discretizations), direct methods fill in zero entries and require operations. Iterative methods start from an initial guess and generate a sequence that converges to the solution .

Assuming for every row , isolate from the -th equation :

2.2.1 Jacobi’s method

In Jacobi's method (method of simultaneous displacements), all components of the new approximation are computed exclusively from the previous iterate .

Definition

Jacobi Iteration Formula

Starting from , compute for :

Because every component depends only on , all updates in Jacobi's method can be evaluated in parallel, though storage is needed for both and .

2.2.2 Gauss-Seidal method

In the Gauss–Seidel method (method of successive displacements; often written Gauss-Seidal in university syllabi), each newly computed component is substituted immediately into the remaining equations of the same iteration.

Definition

Gauss–Seidel Iteration Formula

Starting from , compute sequentially for :

Theorem

Sufficient Condition for Convergence (Diagonal Dominance)

Both Jacobi's method and the Gauss–Seidel method are guaranteed to converge for any initial guess if the coefficient matrix is strictly diagonally dominant, i.e., for every row :


2.3 Determination of largest and smallest Eigen values and corresponding vectors using the power method

For an matrix , a non-zero vector and scalar satisfying

are called an eigenvector and eigenvalue of . Suppose has linearly independent eigenvectors and eigenvalues ordered as .

Largest Eigenvalue (Standard Power Method)

Definition

Power Method for the Dominant Eigenpair

Start with an arbitrary initial non-zero vector (commonly ). At each iteration :

  1. Multiply by :
  1. Extract the scaling factor as the component of with the largest absolute value (preserving its sign):
  1. Normalize to prevent overflow/underflow:

As , (the largest eigenvalue in magnitude) and (its corresponding eigenvector).

(Note: Alternatively, the Rayleigh quotient may be used to estimate at each step.)

Smallest Eigenvalue (Inverse Power Method)

If is invertible (), then implies:

Thus, the eigenvalues of are , with the exact same eigenvectors. The smallest eigenvalue in magnitude of corresponds to the largest eigenvalue in magnitude of .

Definition

Inverse Power Method for the Smallest Eigenvalue

  1. Compute (or LU-factorize once so each step solves ).
  2. Apply the power method to :

where is the largest-magnitude component of .

  1. Once converges to , the smallest eigenvalue in magnitude of is:

with corresponding eigenvector .


Worked Out Examples

Example 2.1

2.1

Solve the following system of linear equations using Gauss elimination with partial pivoting:

Forming the augmented matrix:

First stage of partial pivoting and elimination (column 1): The first pivot cannot be used. Comparing magnitudes in column (), the largest is in row . Swap :

Row already has in column . Eliminate column from row using multiplier ():

Second stage of partial pivoting and elimination (column 2): In column (rows and ), , so swap :

Back substitution: From the upper triangular system:

Answer:

The unique solution is .

Example 2.2

2.2

Factorize the matrix using Doolittle's LU method and hence solve :

Setting up with :

Computing the entries of and :

  • Row 1 of : .
  • Column 1 of :
  • Row 2 of :
  • Column 2 of :
  • Row 3 of :

Thus:

Forward substitution () and back substitution ():

From :

From :

Answer:

and the solution is .

Example 2.3

2.3

Determine the largest eigenvalue and the corresponding eigenvector of

using the power method for iterations, starting with initial vector .

First and second power iterations:

  • Iteration 1:

So , .

  • Iteration 2:

So , .

Third and fourth power iterations:

  • Iteration 3:

So , .

  • Iteration 4:

So , .

Answer:

After iterations of the power method, the largest eigenvalue is (exact ) and the corresponding normalized eigenvector is .


Exercises

Exercise — Solution of System of Linear Algebraic Equations

Question 1

Differentiate between direct and iterative methods for solving systems of linear algebraic equations. Explain partial pivoting versus complete pivoting, and state the sufficient condition for convergence of the Jacobi and Gauss–Seidel methods.

Comparing direct and iterative methods:

  • Direct methods (Gauss elimination, Gauss–Jordan, LU factorization) obtain the exact solution (ignoring machine round-off) in a fixed, finite number of arithmetic steps of order . They work for any non-singular matrix and are ideal for small to medium dense systems.
  • Iterative methods (Jacobi, Gauss–Seidel) start from an initial guess and refine it successively until consecutive iterates agree within a tolerance. They take (or for sparse matrices) per iteration, require less memory, and are preferred for large sparse systems, though they are not guaranteed to converge for every matrix.

Partial vs. complete pivoting and iterative convergence condition:

  • In partial pivoting, at elimination step the pivot is chosen as the largest-magnitude entry in column at or below row using row swaps only (leaving variable order intact).
  • In complete pivoting, the pivot is chosen as the largest-magnitude entry in the entire remaining submatrix using both row and column swaps (requiring variable reordering to be tracked).
  • Diagonal dominance condition: Jacobi and Gauss–Seidel methods are guaranteed to converge for any initial guess if is strictly diagonally dominant:
Answer:

Direct methods solve in finitely many steps () without an initial guess, whereas iterative methods refine an initial guess asymptotically and excel on large sparse systems. Partial pivoting swaps rows to place the largest column entry on the diagonal; complete pivoting swaps both rows and columns across the remaining submatrix. Strictly diagonally dominant matrices () guarantee convergence for both Jacobi and Gauss–Seidel methods.

Question 2

Find the inverse of the matrix

using the Gauss–Jordan method.

Forming and placing a in the pivot position: Swap to get a unit pivot immediately:

Eliminating column 1 below row 1: Apply and :

Reducing columns 2 and 3 to identity form: Swap to obtain pivot in column :

Eliminate column (), then scale :

Finally, eliminate column above the pivot ():

Answer:
Question 3

Solve the system

using Crout's LU factorization method.

Setting up Crout's decomposition ():

Finding and column by column / row by row:

  • Column 1 of : .
  • Row 1 of :
  • Column 2 of :
  • Row 2 of :
  • Column 3 of :

Solving and : From :

From :

Answer:

With and , the solution is .

Question 4

Solve the diagonally dominant linear system

using the Gauss–Seidel method for iterations starting from .

Verifying diagonal dominance and writing the update formulas: In all three rows, , , and , so convergence is guaranteed. Writing the Gauss–Seidel updates (using newly computed values immediately):

Performing three Gauss–Seidel iterations from :

  • First iteration ():
  • Second iteration ():
  • Third iteration ():
Answer:

After Gauss–Seidel iterations, , rapidly converging to the exact solution .

Question 5

Find the smallest eigenvalue and corresponding eigenvector of

by performing iterations of the inverse power method starting from .

Computing : Applying Gauss–Jordan reduction to yields:

Applying the power method to for iterations:

  • Iteration 1:

So , .

  • Iteration 2:

So , .

  • Iteration 3:

So , .

Taking the reciprocal for the smallest eigenvalue of :

(The exact smallest eigenvalue is with eigenvector .)

Answer:

After iterations of the inverse power method, the smallest eigenvalue is and the corresponding eigenvector is .

← Solution of Non-Linear EquationsInterpolation →