# Solving a Triangular Matrix using Forward & Backward Substitution

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

## More on Estimation Theory:

## Recommended Books on Estimation Theory: