Gaussian Elimination

Example

Suppose the goal is to find and describe the solution(s), if any, of the following system of linear equations:

$\begin{alignat}{7} 2x &&\; + \;&& y &&\; - \;&& z &&\; = \;&& 8 & \qquad (L_1) \\ -3x &&\; - \;&& y &&\; + \;&& 2z &&\; = \;&& -11 & \qquad (L_2) \\ -2x &&\; + \;&& y &&\; +\;&& 2z &&\; = \;&& -3 & \qquad (L_3) \end{alignat}$

The algorithm is as follows: eliminate x from all equations below, and then eliminate y from all equations below . This will put the system into triangular form. Then, using back-substitution, each unknown can be solved for.

In the example, x is eliminated from by adding to . x is then eliminated from by adding to . Formally:

The result is:

$\begin{alignat}{7} 2x &&\; + && y &&\; - &&\; z &&\; = \;&& 8 & \\ && && \frac{1}{2}y &&\; + &&\; \frac{1}{2}z &&\; = \;&& 1 & \\ && && 2y &&\; + &&\; z &&\; = \;&& 5 & \end{alignat}$

Now y is eliminated from by adding to :

The result is:

$\begin{alignat}{7} 2x &&\; + && y \;&& - &&\; z \;&& = \;&& 8 & \\ && && \frac{1}{2}y \;&& + &&\; \frac{1}{2}z \;&& = \;&& 1 & \\ && && && &&\; -z \;&&\; = \;&& 1 & \end{alignat}$

This result is a system of linear equations in triangular form, and so the first part of the algorithm is complete.

The last part, back-substitution, consists of solving for the knowns in reverse order. It can thus be seen that

Then, can be substituted into, which can then be solved to obtain

Next, z and y can be substituted into, which can be solved to obtain

The system is solved.

Some systems cannot be reduced to triangular form, yet still have at least one valid solution: for example, if y had not occurred in and after the first step above, the algorithm would have been unable to reduce the system to triangular form. However, it would still have reduced the system to echelon form. In this case, the system does not have a unique solution, as it contains at least one free variable. The solution set can then be expressed parametrically (that is, in terms of the free variables, so that if values for the free variables are chosen, a solution will be generated).

In practice, one does not usually deal with the systems in terms of equations but instead makes use of the augmented matrix (which is also suitable for computer manipulations). For example:

Therefore, the Gaussian Elimination algorithm applied to the augmented matrix begins with:

$\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array} \right]$

which, at the end of the first part (Gaussian elimination, zeros only under the leading 1) of the algorithm, looks like this:

$\left[ \begin{array}{ccc|c} 1 & \frac{1}{3} & \frac{-2}{3} & \frac{11}{3} \\ 0 & 1 & \frac{2}{5} & \frac{13}{5} \\ 0 & 0 & 1 & -1 \end{array} \right]$

That is, it is in row echelon form.

At the end of the algorithm, if the Gauss–Jordan elimination (zeros under and above the leading 1) is applied:

$\left[ \begin{array}{ccc|c} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1 \end{array} \right]$

That is, it is in reduced row echelon form, or row canonical form.

Read more about this topic: Gaussian Elimination

Famous quotes containing the word example:

“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)

Gaussian Elimination - Example

Famous quotes containing the word example: