Let A be a n times n band matrix of the following form 2 1 0

Let A be a n times n band matrix of the following form. (2 1 0 0 0 ctdot 0 b_1 2 1 0 0 ctdot 0 c_1 b_2 2 1 0 ctdot vellip 0 c_2 dtdot dtdot dtdot dtdot vellip 0 0 dtdot dtdot dtdot dtdot 0 vellip vellip dtdot c_n minus 1 b_n minus2 2 1 0 0 ctdot 0 c_n minus 2 b_n minus1 2)Write an efficient algorithm (fully exploiting the sparsity pattern) which generates the upper-triangular result of applying Gaussian elimination to A. You may assume that pivoting is unnecessary. Let t_n be the total number of floating point arithmetic operations (additions, subtractions, multiplications, and divisions combined) performed when the algorithm in part (a) is executed; write a formula for t_n.

Solution

Since diagonal elements are = 2 divide all rows first by 2 to make diagonal elements as 1.

Step II: R2-b2/2 R1 = R2 and R3-c/2 R1 = R3 makes I column fully 0 except diagonal element 1.

Step III: Now in II column pivot diagonal element =1

Hence make other elements below II row in the column by suitable operations to make 1.

Step 4: Now in III column pivot diagonal element is 1. Make suitable row operations to make all elements in III column below diagonal to become 0

Continue this till last

Then the matrix would have become upper triangular.

-------------------------------------------------------------