# 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 $$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 $$x_1$$ requires one FLoating Point Operation per Second (FLOPS) – only one division. Computing $$x_2$$ will require 3 FLOPS – 1 multiplication, 1 division and 1 subtraction, $$x_3$$ will require 5 FLOPS – 2 multiplications, 1 division and two subtractions. Thus the computation of $$x_{mm}$$ will require $$(2n-1)$$ FLOPS.

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

## Backward substitution:

Consider a set of equations in a matrix form $$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 $$m^2$$ FLOPS.