A m × n system of linear equations where m = n and A is not singular, possesses a unique solution. A solution for the unknown vector x is obtained by premultiplying Equation 19 by A^{-1}, i.e.
$\mathbf{\left({A}^{-1}A\right)x={A}^{-1}b}$ |
or simply
$\mathbf{x={A}^{-1}b}$ | (20) |
since A^{-1}A is by definition the multiplicative identity.
The solution algorithm suggested by Equation 20 is
Invert matrix A.
Premultiply the vector b by A^{-1}.
This procedure is computationally inefficient and rarely used in practice. Most direct solutions to systems of linear equations are derived from a procedure known as Gaussian elimination, which is a formalization of the ad hoc techniques used to solve linear equations in high school algebra. The basic algorithm is
Transform the system of equations into a triangular form.
Solve the triangular set of equations through a series of variable substitutions.
A major drawback to this procedure is that both sides (A and b) of Equation 19 are modified as the system is forced into triangular form. This requires repetition of the entire procedure if you want to solve Equation 19 with a new b vector. A technique known as LU decomposition overcomes this problem by systematically capturing the intermediate states of A as the transformation to triangular form progresses. This effectively decouples the operations on A from those on b, permitting solutions to Equation 19 for many b vectors based on a single triangular factorization.
More specifically, LU decomposition produces a lower triangular matrix L and an upper triangular matrix U such that
$\mathbf{LU=A}$ | (21) |
Substituting Equation 21 into Equation 19 yields
$\mathbf{\left(LU\right)x=b}$ | (22) |
Associating the factors in Equation 22 yields
$\mathbf{L\left(Ux\right)=b}$ | (23) |
Recalling that efficient procedures exist for solving triangular systems (i.e. forward substitution for lower triangular systems and backward substitution for upper triangular systems), Equation 23 suggests an algorithm for solving Equation 19. Define a vector y such that
$\mathbf{y=Ux}$ | (24) |
Substituting Equation 24 into Equation 23 yields
$\mathbf{Ly=b}$ | (25) |
Since b is known and L is lower triangular, Equation 25 can be solved for y by forward substitution. Once y is known, Equation 24 can be solved for x by back substitution.
In summary, the preferred algorithm for solving for a nonsingular n × n system of linear equations is
Compute an LU decomposition of A.
Solve Equation 25 for y by forward substitution.
Solve Equation 24 for x by back substitution.