Problem 6 (20 pts). Suppose we have a matrix M E Rnxn decomposed into blocks:

1- [ B]₁

CD

M =

where A E Rkxk is nonsingular.

a) Verify that the following "block LU decomposition" formula holds:

I

A

- [CA- ] [4

M =

B

0 D-CA-¹B

The matrix D-CA-¹B is called the Schur complement of A and is the matrix we get after

X1

eliminating the first block of unknowns x1 in the system

via the formula

x₁ = A-¹(b₁ - Bx2); plugging this formula into the second block row of the equation yields:

b₂ = Cx₁ + Dx2 = CA-¹(b₁- Bx2) + Dx2 (D-CA-¹B)x2 = b2 - CA-¹b₁.

-1

b) Describe how you can construct the full LU decomposition of M by computing an LU

decomposition of A, evaluating and factorizing D-CA-¹B, and finally manipulating the

result using efficient operations (and never explicitly constructing A-¹)!