Solving systems of linear equations by Gaussian elimination

Solving systems of linear equations with determinants can be used for systems of two or three equations. For systems with more than three equations it is better to use the Gaussian elimination.

Gaussian Elimination is based on exclusion of unknowns. First we should use elementary row operations to reduce the matrix to row echelon form and then use the back substitution to solve each of the equations.

Consider the system of equations:



where x_i are the unknowns, i = 1, 2, ..., n; n < 200. If the number of equations is more than 200, it is necessary to use iterative methods.

a_i,j are the elements of the augmented matrix of coefficients.

Gaussian elimination to reduce a system to triangular

Express x₁ from the first equation
(2) x₁ = (a_1,n+1 - a_1,2x₂ - ... - a_1nx_n)/a₁₁

If a_1,1=0 and there is a non-zero element in the first column, we should swap rows. Then substitute (2) into all equations of the system (1), except the first equation. Thus, the unknown x ₁ will be eliminated from all the equations of the system, except the first equation.

The elements of the augmented matrix can be calculated by the formulas:

a_1j⁽¹⁾ = a_1j/a₁₁

a_ij⁽¹⁾ = a_ij - a_i1a_1j⁽¹⁾, i = 2,3,...,n; j = 1, 2, ..., n+1

After eliminating x₁ from all the equations, all elements of the first column of the transformed matrix will be zero, except a₁₁⁽¹⁾ = 1.

Repeat this procedure for x₂ - express it from the second equation and eliminate it from the rest of equations, etc.

Doing this we will put the system into triangular form where all the elements below the main diagonal are zeros.


To eliminate x_k.



Next, we do a backward elimination to solve the linear system and find the unknowns x_k from x_n to x₁. This procedure is called a backward elimination.

To minimize the error of division by the diagonal element in (3), it is recommended to rearrange the equations to put the element with the largest absolute value on the diagonal. This modification is called Gaussian elimination with partial pivoting.

To estimate the error of numerical solution of the system with discrepancies, the numerical solutions x_k , k = 1, 2, ..., n must be substituted into the system. Then we should calculate the difference between the right and left parts of the equations.



For small values of errors, r _k will be zero.