# Solving a Triangular Matrix using Forward & Backward Substitution

(3 votes, average: 5.00 out of 5)

## Forward Substitution:

Consider a set of equations in a matrix form $latex Ax=b$, where A is a lower triangular matrix with non-zero diagonal elements. The equation is re-written in full matrix form as

It can be solved using the following algorithm

From the DSP implementation point of view, computation of $latex x_1$ requires one FLoating Point Operation per Second (FLOPS) – only one division. Computing $latex x_2$ will require 3 FLOPS – 1 multiplication, 1 division and 1 subtraction, $latex x_3$ will require 5 FLOPS – 2 multiplications, 1 division and two subtractions. Thus the computation of $latex x_{mm}$ will require $latex (2n-1)$ FLOPS.

Thus the overall FLOPS required for forward substitution is $latex 1+3+5+\cdots+(2m-1)$ $latex = m^2$ FLOPS

## Backward substitution:

Consider a set of equations in a matrix form $latex Ax=b$, where A is a upper triangular matrix with non-zero diagonal elements. The equation is re-written in full matrix form as

Solved using the following algorithm

This one also requires $latex m^2$ FLOPS.