Chapter 28, Problem 1P

Program Plan Intro

To find the LU decomposition of Matrix A given as:

  

Explanation of Solution

LU Decomposition of A: The LU Decomposition of A means to decompose a matrix A into a product of lower triangular matrix and upper triangular matrix.

In Decomposition of A the input is lower triangular matrix and output is upper triangular matrix obtain by applying following row operation on A.

  

Here,

  

and

  

And lower triangular matrix is given by

  

Consider a matrix,

  

Initially calculate the value of all entries other than 0 and 1 of equation (1).

Apply the row operation to the matrix A to find the upper triangular matrix U

Calculate the value of

  (2)

Calculate the value of ,

  (3)

Calculate the value of

  (4)

Calculate the value of

  (5)

Apply row transformation to find upper triangular matrix.

  

Similarly calculate the value of,

  …… (6)

Calculate the value of,

  …… (7)

  …… (8)

Apply row transformation to find upper triangular matrix.

  

Calculate the value of,

  (9)

Calculate the value of,

  (10)

Apply row transformation to find upper triangular matrix.

The upper triangular matrix is-

  

The lower triangular matrix is-

  

Hence, the LU decomposition of A is-

  

Program Plan Intro

To solve the equation by using forward and backward substitution.

Explanation of Solution

Consider an expression-

  

  

To solve this, the following steps are followed-

Express in the decomposition form-

  

Let for any vector, the equation to be solved is. This is done by following steps:

• LUP Decomposition

• Forward Substitution

Let

  

After solving, the following value of is obtained-

  

• Backward Substitution

  

  

Solving for

  

Program Plan Intro

To find the inverse of A.

Explanation of Solution

Inverse of a matrix is a matrix such that where is an identity matrix.

  

To solve this, the following steps are followed-

• Forward Substitution

Let

  

After solving, the following value of is obtained-

  

Similarly, other columns can also be obtained in the following way-

  

Inverse of the matrix can be formed by using the five results which comprises the columns of the inverse matrix.

  

• Backward Substitution

Now find from

Solving for

  

Program Plan Intro

To show how, for any symmetric positive-definite, tridiagonal matrix and any n-vector to solve the equation

Explanation of Solution

Inverse of a matrix is a matrix such that where is an identity matrix.

  

To solve this, the following steps are followed-

• Forward Substitution

Let

  

After solving, the following value of is obtained-

  

Similarly, other columns can also be obtained in the following way-

  

Inverse of the matrix can be formed by using the five results which comprises the columns of the inverse matrix.

  

• Backward Substitution

Now find from

Solving for

  

Program Plan Intro

To show that, for any non-singular, tridiagonal matrix.

Explanation of Solution

Forward and Backward substitution take the same amount of operations as in the previous case. The only different case is the decomposition step. In this case, the decomposition is done into unit lower triangular and upper triangular matrix, and. The pivoting is done by the swapping rows such that the highest element of a column comes to the diagonal place. The decomposition looks like the following:

  

Here, loses the tri-diagonal property of matrixbut it is still a banded matrix. The essence to solve this is similar to the tri-diagonal case. The time complexity now depends on the width of the band or the distance between the farthest diagonals of the resultant matrix. Matrix becomes wider than the upper triangle of the initial matrix. The final complexity becomes

Hence the time complexity of LUP decomposition algorithm will be