Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

gaussian
calculation
forward
backward
substitution

What is forward and back substitution in Gaussian elimination?

Isra Javaid

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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

[a1100....0a21a220....0a31a32a33....0............0an1an2...an,n1an,n][x1x2x3.xn]=[b1b2b3.bn]\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=yLx=y

  • LL represents the factor of the matrix of the lower triangle.
  • xx represents the variable of matrix.
  • yy is the result vector.

The matrix form of a lower triangle:

[x002xy03x2y3z]\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 xx exists, and other values are zero, so it is easy to find a value of xx and use it for the next step.
  • In the second step, we find the value of yy by using the value of xx, which came from the first step.
  • Similarly, in the third step, we use xx and yy values and find the value of zz.

Back substitution

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

Equation

Ux=yUx=y

  • UU represents the factor of matrix of upper triangle.
  • xx represents the variable of matrix.
  • yy is the result vector.

The matrix form of an upper triangle:

[3x2y3z0y2z00z]\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 zz exists and other values are zero, so it is easy to find a value of zz and use it for next step.
  • In the second step, we find the value of yy using the value of zz, which came from previous step.
  • Similarly, in the third step, we use yy and zz to find the value of xx.

RELATED TAGS

gaussian
calculation
forward
backward
substitution

CONTRIBUTOR

Isra Javaid
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring