Algorithms and Parallel Computing

20.5 MATRIX TRIANGULARIZATION ALGORITHM

This section shows the algorithm to convert a square matrix A to an upper triangular matrix U. Once we obtain a triangular matrix, we can use forward or back substitution to solve the system of equations.

Assume we are given the system of linear equations described by

(20.26)

The solution for this system will not change if we premultiply both sides by the Givens matrix G_pq:

(20.27)

Premultiplication with the Givens matrix transforms the linear system into an equivalent system

(20.28)

and the solution of the equivalent system is the same as the solution to the original system. This is due to the fact that premultiplication with the Given matrix performs two elementary row operations:

1. Multiply a row by a nonzero constant.

2. Add multiple of one row to another row.

Let us assume we have the following system of linear equations

(20.29)

To solve this system, we need to convert the system matrix to an upper triangular matrix. So we need to change element a_2,1 from 3 to 0. After multiplying by the Givens matrix G₂₁, element is given ...