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 35 by A-1, i.e.
| $$\mathbf{\left({A}^{-1}A\right)x={A}^{-1}b}$$ |
or simply
| $$\mathbf{x={A}^{-1}b}$$ | (36) |
since A-1A is by definition the multiplicative identity.
The solution algorithm suggested by Equation 36 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 35 are modified as the system is forced into triangular form. This requires repetition of the entire procedure if you want to solve Equation 35 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 35 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}$$ | (37) |
Substituting Equation 37 into Equation 35 yields
| $$\mathbf{\left(LU\right)x=b}$$ | (38) |
Associating the factors in Equation 38 yields
| $$\mathbf{L\left(Ux\right)=b}$$ | (39) |
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 39 suggests an algorithm for solving Equation 35. Define a vector y such that
| $$\mathbf{y=Ux}$$ | (40) |
Substituting Equation 40 into Equation 39 yields
| $$\mathbf{Ly=b}$$ | (41) |
Since b is known and L is lower triangular, Equation 41 can be solved for y by forward substitution. Once y is known, Equation 40 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 41 for y by forward substitution.
Solve Equation 40 for x by back substitution.