Problem 1. Write an algorithm to solve Ly = b and Ux = y, where L is lower triangular but each diagonal element is not necessary 1, and U is upper triangular with every diagonal element equal to 1.

For computing y, j goes from 1 to n, for computing x, j goes from n to 1.

Problem 2. Suppose that A = BTB where B is a m x m matrix with linearly independent columns. Show that A is positive definite.

Theorem 3.6 (p. 91):

Let A be a real symmetric matrix of order n. Then A is positive definite if and only if (e) There exists a nonsingular matrix C such that A = CCT

Let B=CT. Since C is nonsingular, CT, and therefore B, is also nonsingular.

If A = BTB, then A= CCT and is therefore positive definite, and also symmetric.

 

Problem 3. Prove that if a matrix is Column diagonally dominant then no pivoting is necessary for row elimination. [Hint: Prove first that the lower right corner of the partly processed matrix is diagonally dominant]

Given:

 

After one step of Gaussian elimination,

If the matrix, excluding the first row and column is still diagonally dominant, then no pivoting is necessary for a column diagonally dominant matrix.

If the lower right corner is still diagonally dominant, then for all i>1,

All columns are essentially equivalent, so if the second column is diagonally dominant, they all are.

Since I am working backward, steps are valid if the make an equivalent or weaker inequality, so this is ok.

The original matrix was diagonally dominant

Which is another statement of the original matrix being column diagonally dominant. So column diagonally dominant matrices do not require pivoting in Gaussian elimination.

 

Problem 4. Show that the Sherman-Morrison formula (Woodbury formula) is satisfied.

(A + UBV)-1 =A-1 - A-1U (Im + BVA-1U)-1 BVA-1

where A is an n x n nonsingular matrix, B is a m x m matrix, U is an n x m matrix, V is an m x n matrix, and Im is the identity of order m.

(AB + AC)-1 = (B + C)-1 A-1

(BA + CA)-1 = A-1 (B + C)-1

(Im + BVA-1U) BVA-1 = U(B-1 + VA-1U)-1 VA-1

=(V-1B-1 + A-1U)-1 A-1

=(AV-1B-1 + U)-1

=B (AV-1 + UB)-1

=BV(A + UBV)-1

(A + UBV)-1 =A-1 - A-1U (Im + BVA-1U)-1 BVA-1

(A + UBV)-1 =A-1 - A-1UBV (A + UBV)-1

(A + UBV)-1+ A-1UBV (A + UBV)-1 = A-1

A(A + UBV)-1+ UBV (A + UBV)-1 = I

(A + UBV)(A + UBV)-1 = I

 

Problem 5. Consider an n x n tridiagonal matrix with constant superdiagonal and with constant subdiagonal. That is, there exist two constants u and l such that ai,j+1 = u and aj+1,i = l for i= 1, 2, ..., n-1. A tridiagonal matrix with this structure can be stored using an array D that contains the diagonal elements and two variables L and U that contain l and u, respectively. Write an algorithm to factor the tridiagonal matrix stored in L, D, and U, and an algorithm to solve the factored system.