Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Physics LibreTexts

5.1: The Basic Algorithm

( \newcommand{\kernel}{\mathrm{null}\,}\)

The best way to understand how Gaussian elimination works is to work through a concrete example. Consider the following N=3 problem:

[123322262][x0x1x2]=[344].

The Gaussian elimination algorithm consists of two distinct phases: row reduction and back-substitution.

5.1.1 Row Reduction

In the row reduction phase of the algorithm, we manipulate the matrix equation so that the matrix becomes upper triangular (i.e., all the entries below the diagonal are zero). To achieve this, we note that we can subtract one row from another row, without altering the solution. In fact, we can subtract any multiple of a row.

We will eliminate (zero out) the elements below the diagonal in a specific order: from top to bottom along each column, then from left to right for successive columns. For our 3×3 example, the elements that we intend to eliminate, and the order in which we will eliminate them, are indicated by the colored numbers 0, 1, and 2 in the following figure:

clipboard_ee51b6655ea8f5114a5fdf27ae6c5a4fd.png
Figure 5.1.1

The first matrix element we want to eliminate is at (1,0) (orange circle). To eliminate it, we subtract, from this row, a multiple of row 0. We will use a factor of 3/1=3:

(3x0+2x1+2x2)(3/1)(1x0+2x1+3x2)=4(3/1)3

The factor of 3 we used is determined as follows: we divide the matrix element at (1,0) (which is the one we intend to eliminate) by the element at (0,0) (which is the one along the diagonal in the same column). As a result, the term proportional to x0 disappears, and we obtain the following modified linear equations, which possess the same solution:

clipboard_ea9ac17b2d6a51a7ab06a9dfded14addf.png
Figure 5.1.2

(Note that we have changed the entry in the vector on the right-hand side as well, not just the matrix on the left-hand side!) Next, we eliminate the element at (2,0) (green circle). To do this, we subtract, from this row, a multiple of row 0. The factor to use is 2/1=2, which is the element at (2,0) divided by the (0,0) (diagonal) element:

(2x0+6x1+2x2)(2/1)(1x0+2x1+3x2)=4(2/1)3

The result is

clipboard_e2f868d69e640f2417ce294c0831f5479.png
Figure 5.1.3

Next, we eliminate the (2,1) element (blue circle). This element lies in column 1, so we eliminate it by subtracting a multiple of row 1. The factor to use is 2/(4)=0.5, which is the (2,1) element divided by the (1,1) (diagonal) element:

(0x0+2x14x2)(2/(4))(0x04x17x2)=5(2/(4))(2)

The result is

clipboard_e2b08908b35369e1242c4b67cc2443259.png
Figure 5.1.4

We have now completed the row reduction phase, since the matrix on the left-hand side is upper-triangular (i.e., all the entries below the diagonal have been set to zero).

5.1.2 Back-Substitution

In the back-substitution phase, we read off the solution from the bottom-most row to the top-most row. First, we examine the bottom row:

clipboard_e88050c7d67e5377372205efdc8d491ca.png
Figure 5.1.5

Thanks to row reduction, all the matrix elements on this row are zero except for the last one. Hence, we can read off the solution

x2=(4.5)/(7.5)=0.6.

Next, we look at the row above:

clipboard_e1a889d08902264079ef840ac8e9c2cfd.png
Figure 5.1.6

This is an equation involving x1 and x2. But from the previous back-substitution step, we know x2. Hence, we can solve for

x1=[5(7)(0.6)]/(4)=0.2.

Finally, we look at the row above:

clipboard_e88e368fb3f4b56d5b06e6434386c14d4.png
Figure 5.1.7

This involves all three variables x0, x1, and x2. But we already know x1 and x2, so we can read off the solution for x0. The final result is

[x0x1x2]=[0.80.20.6].

5.1.3 Runtime

Let's summarize the components of the Gaussian elimination algorithm, and analyze how many steps each part takes:

Row reduction
Step forwards through the rows. For each row n, N steps
Perform pivoting (to be discussed below). Nn+1N steps
Step forwards through the rows larger than n. For each such row m, NnN steps
Subtract (Amn/Ann) times row n from the row m (where A is the current matrix). This eliminates the matrix element at (m,n). O(N) arithmetic operations
Back-substitution
Step backwards through the rows. For each row n, N steps
Substitute in the solutions xm for m>n (which are already found). Hence, find xn. NnO(N) arithmetic operations

(The "pivoting" procedure hasn't been discussed yet; we'll do that in a later section.)

We conclude that the runtime of the row reduction phase scales as O(N3), and the runtime of the back-substitution phase scales as O(N2). The algorithm's overall runtime therefore scales as O(N3).


This page titled 5.1: The Basic Algorithm is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Y. D. Chong via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?