EXERCISE 1

Solve the linear system Ax = b, x, b e Rn and A e Rn Xn symmetric positive definite using conjugate gradient method.

(a) Implement the linear preconditioned Conjugate Gradient method.

(b) Let n = 100. We construct the ground truth x*  (using Matlab’s code) as

xtrue  =  zeros(n,1);

xtrue(floor(n/4):floor(n/3))  =  1;

xtrue(floor(n/3)+1:floor(n/2))  =  -2;

xtrue(floor(n/2)+1:floor(3/4*n))  =  0.5;

and for each matrix below the matching right hand b = Ax*  to satisfy the linear system. Solve the linear system Ax = b for the following matrices A

· A1  =  diag(1:n);

· A2  =  diag([ones(n-1,  1)  100]);

·  1d negative Laplacian:

A3  =  -diag(ones(n-1,  1),  -1)  -  diag(ones(n-1,  1),  1)  +  diag(2*ones(n,  1));

Choose the initial point x0 = (0, . . . , 0)T  and stopping tolerance tol  =  1e-12.

(c) For each of the matrices Ai, i = 1, 2, 3 evaluate the convergence a posteriori.  In practice, the true solution is seldom available, so a common practice is to consider the residual norm instead.

What are the empirical convergence rates, how did you obtain them?  Do they agree with the theoretical predictions?  What are the theoretical predictions for each of the matrices? Paraphrase the relevant theoretical results.

(d)  Solve the linear system for the matrices A1 and A3 in (b) using the following preconditioners:

·  Cholesky (see  chol())

· Incomplete Cholesky (see  ichol()).

·  Diagonal M = diagA3 , (see  diag()).