Problem 1 (Nonexistent LU Factorization):

Prove that the matrix

0」

1

1

is nonsingular and that it does not possess a (naïve) LU factorization.

Calculate the LU factorization (with pivoting) of the matrix

For each step of the algorithm, clearly mark the current L and U factor and the pivot element.

State the final LU factorization and permutation matrix P .

Problem 3 (Factorizing Tridiagonal Matrices):

In this exercise, we consider special symmetric tridiagonal matrices of the form

Throughout the exercise, we assume that T is positive definite.

a)  Show that T can be factorized via T = LL⊤ where L is a lower bidiagonal matrix, i.e.,

with positive diagonal entries fi   > 0 for all i =  1, . . . , n.  Briefly explain how positive definiteness of T is used in the computation/derivation of the factorization.

Hint: Mimic the derivation of the Cholesky decomposition.

b) Write a MATLAB or Python program that computes the factorization T = LL⊤ for given input vectors d ∈ Rn  and a ∈ Rn−1 .  Your algorithm should return the diagonal vectors f ∈ Rn and b ∈ Rn−1 that define the matrix L. Pay attention to efficient memory allocation and usage. Compute or estimate the number of required flops of your approach!

Problem 4 (A Deblurring Problem):

The goal of this exercise is to investigate and solve linear systems of the form

Tk XTk  = B  (1)

where B ∈ Rn×n  and k ∈ N are given inputs and T ∈ Rn×n  is a symmetric and positive definite tridiagonal matrix. We seek to recover the matrix X ∈ Rn×n .

The problem (1) can be used to model the deblurring problem presented in one of the introductory lectures.  Specifically, the matrix X corresponds the sharp original (square) n × n image, B represents the blurry image we have observed, and the linear mapping X →f Tk XTk  models the blurring operation. In this exercise, we assume that T is fully given by

i.e., every entry on the main diagonal is 4(2)6(6)  and all entries on the other two diagonals are set to 46  with 6 = 0.1. Applying the matrix T multiple times on the original image X intensifies the

Figure 1: Left: Original image X . Middle: Blurred image B = T5 XT5 . Right: Blurred image B = T15 XT15 .

a) The eigenvalues of the matrix T can be represented explicitly via:

λi =  −  cos ( )    i = 1, . . . , n,    6 = 0.1.

(You don’t need to verify this result). Estimate the condition number cond ∥ · ∥2 (Tk) of Tk using the spectral norm ∥ · ∥2  as base norm. For which choices of k and n is the matrix Tk generally well- or ill-conditioned?