Home

Linear algebra is one of the corner stones of modern computational mathematics. Almost all numerical schemes such as the finite element method and finite difference method are in fact techniques that transform, assemble, reduce, rearrange, and/or approximate the differential, integral, or other types of equations to systems of linear algebraic equations.

A system of linear algebraic equations can be expressed as

or

Solving a system with a coefficient matrix is equivalent to finding the intersection point(s) of all m surfaces (lines) in an n dimensional space. If all m surfaces happen to pass through a single point then the solution is unique. If the intersected part is a line or a surface, there are an infinite number of solutions, usually expressed by a particular solution added to a linear combination of typically vectors. Otherwise, the solution does not exist.

The core of solving a system of linear algebraic equations is decomposing the coefficient matrix. Through the decomposition process, the coupled equations are decoupled and the solution can be obtained with much less effort. A better decomposition method will perform faster and introduce less errors. Common numerical methods used to solve linear algebraic equations are briefly discussed in this section:

• Gaussian Elimination

• LU Decomposition

• SV Decomposition

• QR Decomposition

Gaussian elimination executes a series of row operations to eliminate coefficients in order to form the triangular matrix .

The solution can thereafter be obtained.

The LU decomposition rewrites the coefficient matrix to two triangular matrices, i.e., , where is the lower triangular matrix and is the upper triangular matrix. Expressing the LU matrices explicitly, they look like

Thus, the system of linear algebraic equations can be decomposed to two systems of linear algebraic equations which can be solved directly.

The Singular Value Decomposition (SVD) rewrites the coefficient matrix to three matrices including two orthogonal matrices and , and a diagonal matrix , i.e., . Here,

The coefficient matrices of the system can then be moved to the right hand side of the equal sign.

The QR decomposition rewrites the coefficient matrix to two special matrices, i.e., . Here is an upper triangular matrix, is an orthogonal matrix, that is

The system can then be solved in the form of