Trusted answers to developer questions

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.

**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:

- Forward substitution
- 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}$

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.

$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}$

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$.

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

$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}$

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$.

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

Related Courses