Using a 3by3 matrix explain why for a diagonally dominant tr

Using a 3-by-3 matrix, explain why for a diagonally dominant tri-diagonal matrix, the Gaussian elimination procedure will not break down.

Solution

Tri-diagonal matrix contains non-zero elements on the diagonal and also on first diagonal below and above the main diagonal.

Diagonally dominant matrix means diagonal elements are non-zero and a strictly diagonally dominant matrix is non-singular.

Gaussian elimination procedure tries to solve systems of equations by performing row reductions and getting zeros in non-diagonal entries in the matrix. Gaussian elimination breaks down if the matrix is singular, i.e. if after row-reduction step, a zero comes in the diagonal element. This causes breakdown during the back-substitution step. Hence, a singular matrix causes Gaussian elimination procedure to break down.

In case of diagonally dominant tri-diagonal matrix, it is non-singular and hence Gaussian elimination does not break down. The illustration of this is done below using 3-by-3 matrix,

Consider a 3-by-3 matrix

A = [a b c

d e f

g h i]

Suppose we are solving the equation, A x = B

B is a vector of 3-by-1,

B = [m

n

o]

x is also a 3-by-1 vector,

x = [x1

x2

x3]

To solve for x, A matrix has to be row-reduced into a upper-triangular matrix

After row-reduction, matrix A(row-reduced) might look something like this

A(row-reduced) = [a\' b\' c\'

0 e\' f\'

0 0 i\']

B(row-reduced) = [m\'

n\'

o\']

During back -substitution,

x3 = o\'/i\'

Using above calculated x3, x2 can be found

x2 = (n\' - f\' * x3)/e\'

Using above calculated x2, x1 can be found

x1 = (m\' - c\' * x3 - b\' * x2)/a\'

During the above back-substitution step, if the matrix is not diagonally dominant, i.e. if any of the diagonal elements turns out to be zero, then it results in divide-by-zero case.

Hence, Gaussian elimination breaks down, if the matrix is singular.

So, a digonally dominant tri-diagonal matrix, which implies non-singular property will not make Gaussian elimination break down.