What is forward and back substitution in Gaussian elimination?

Overview

Gaussian elimination is a method in which an augmented matrix is subjected to row operations until the component corresponding to the coefficient matrix is reduced to triangular form.

After we have obtained our triangular matrix, there are two different approaches we can use to solve a system of linear equations:

1. Forward substitution
2. Back substitution

$$\begin{bmatrix} a_{11} & 0 & 0 &....& 0\\ a_{21} & a_{22} & 0 &....& 0\\ a_{31} & a_{32} & a_{33} &....& 0\\ ... & ... & ... &...& 0\\ a_{n1} & a_{n2} & ... &a_{n,n1}& a_{n,n} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ .\\ x_n \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ .\\ b_n \end{bmatrix}$$

Forward substitution

The procedure of solving a system of linear algebraic equations (SLAE) with a lower triangular coefficient matrix is known as forward substitution. Solving an SLAE with a triangular matrix form is a variant of the generic substitution approach.

Equation

$$Lx=y$$

• $L$ represents the factor of the matrix of the lower triangle.
• $x$ represents the variable of matrix.
• $y$ is the result vector.

The matrix form of a lower triangle:

$$\begin{bmatrix} x & 0 & 0 \\ 2x & y & 0 \\ 3x & 2y & 3z \end{bmatrix}$$

Visualization of forward substitution

The visualization shows how forward substitution works. The method transforms the matrix into a lower triangular form and then starts solving an equation from top to bottom.

• The diagram above shows how forward substitution works. In this process, we make a lower triangle and start from the top.
• As we can see at the top, only $x$ exists, and other values are zero, so it is easy to find a value of $x$ and use it for the next step.
• In the second step, we find the value of $y$ by using the value of $x$, which came from the first step.
• Similarly, in the third step, we use $x$ and $y$ values and find the value of $z$.

Back substitution

The procedure of solving an SLAE with an upper triangular coefficient matrix is known as back substitution.

Equation

$$Ux=y$$

• $U$ represents the factor of matrix of upper triangle.
• $x$ represents the variable of matrix.
• $y$ is the result vector.

The matrix form of an upper triangle:

$$\begin{bmatrix} 3x & 2y & 3z \\ 0 & y & 2z \\ 0 & 0 & z \end{bmatrix}$$

Visualization of backward substitution

It shows how the backward substitution works. The method transforms the matrix into an upper triangular form and then starts solving an equation from bottom to top.

• The lower diagram shows how back substitution works. In this process we make an upper triangle and start from the bottom.
• As we can see at the bottom, only $z$ exists and other values are zero, so it is easy to find a value of $z$ and use it for next step.
• In the second step, we find the value of $y$ using the value of $z$, which came from previous step.
• Similarly, in the third step, we use $y$ and $z$ to find the value of $x$.