Solving Linear Equations using Gaussian Elimination

Gaussian Elimination (GE) is one of the most popular methods to solve an linear equation. GE algorithm is the only direct method which is of much interest to the researchers. This method considers that the co-efficient matrix is square. If the matrix $A$ is not square then it can be made square and symmetric as shown for the case of Cholesky decomposition. GE works on the principle of elementary row operation on matrix $G$ . Matrix $A$ and $y$ are augmented to form matrix $G$ which is defined as

(1)

After applying Gaussian Elimination, the matrix $G$ is modified to $H$ as

(2)

where $B$ is an upper triangular matrix with diagonal elements equal to 1 and column vector $y$ becomes $z$ after applying Gaussian Elimination. The estimate $\hat{x}$ is computed as

(3)

The procedure for making the matrix $G$ into a triangular matrix is important and critical in terms of hardware implementation. The basic equation for elementary row operation is

(4)

Here, $R_{1:}$ and $R_{2:}$ denotes first and 2nd row respectively. Here, two new parameters are defined which are $\alpha$ and $\beta$ . The parameter $\beta$ indicates the value by which a row is divided and $\alpha$ is multiplication factor. Gaussian Elimination technique is illustrated for a $3\times 3$ co-efficient matrix. Gaussian Elimination algorithm is accomplished in three steps here. In the first step, row 1 of matrix $G$ is divided by ${\beta}_{11} = A_{11}$ . The $\alpha$ values for first step are ${\alpha}_{21} = A_{12}$ and ${\alpha}_{31} = A_{13}$ . In the second step, row 2 is divided by ${\beta}_{22} = A^*_{22}$ . The $\alpha$ value for second step s ${\alpha}_{32} = A^*_{23}$ . In the last step, row 3 of modified $G$ is divided by ${\beta}_{33} = A^{**}_{33}$ .

The algorithm for GE is mentioned in Algorithm 1. Input to the algorithm is augmented matrix $G$ . $G_{i:}$ denotes the elements of $i^{th}$ row of matrix $G$ . GE algorithm is the only direct technique which can be adopted for hardware implementation. Gaussian Elimination has lesser computational complexity than many matrix based factorization techniques. Most hardware expensive operation involved with Gaussian Elimination is division operation. Divider consumes higher logic gates and thus multiple divider can not be used. This is why GE may not be suitable for higher order matrices.

MATLAB code for Gaussian Elimination (2544 downloads )

Related Posts