Backward Substitution in MATLAB

Backward Substitution

Consider a Upper Triangular matrix U of dimension n, U x = b

$$\begin{bmatrix} u_{1,1}&u_{1,2}&\dots&u_{1,n}\\ 0&u_{2,2}&\dots&u_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\dots&u_{n,n} \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2}\\ \vdots\\ x_{n} \end{bmatrix} = \begin{bmatrix} b_{1}\\ b_{2}\\ \vdots\\ b_{n} \end{bmatrix}$$

Solving Procedure:

1. $$x_{n} = \frac{b_{n}}{u_{n,n}}$$
2. Moving to ${n-1}^{th}$ row, there are two coefficients related to $x_{n}$(already known) and $x_{n-1}$ (unkown). $$u_{n-1,n-1}x_{n-1}+u_{n-1,n}x_{n}=b_{n-1}$$
3. Solving for unknown $x_{n}$, we have $$x_{n-1} = \frac{b_{n-1}-u_{n-1,n}x_{n}}{u_{n-1,n-1}}$$
4. Generalizing for $i^{th}$ row, $$x_{i} = \frac{1}{u_{i,i}}\left( b_{i}-\sum_{j=i+1}^{n}u_{i,j}x_{j} \right)$$

A MATLAB function to solve upper triangular system is provided. This process is also known as 'backward substitution'

function X = backwardsubstitution(U,B)
% Input U = Upper triangular matrix
%       B = Right hand vector (force vector)
% Output X = solution vector (output vector)
n = size(U,1);          % n = rank of matrix U
for i = n:-1:1          % loops to move from last row to first row
    sum = 0;
    for j = i+1:n
        sum = sum + U(i,j)*X(j)/U(i,i);
    end
    X(i) = B(i)/U(i,i) - sum;
end


A = [5 2 4; 0 3 2; 0 0 1];
B = [10; -2; -2];
x = backwardsubstitution(A,B)

x =

    3.3333    0.6667   -2.0000

Published with MATLAB® R2020b