AS/4602/WKC/5
DEPARTMENT OF MATHEMATICS
MATH4602 Scientific Computing
Mimi Project
Due Date: 23 April 2024 (5:00 pm)
In this MATLAB coding assignment, we focus on solving the following structured linear system of equations:
Ax = b
where A is an n2 × n2 matrix taking the following form.
Here In is the n × n identity matrix and
It is a block-Toeplitz matrix with Toeplitz blocks. We first consider solving the linear system by using an iterative method, the Gauss-Seidel method.
(a) (i) Show that A is a symmetric positive definite matrix for d ≥ 2. Therefore Gauss- Seidel method converges when applied to solving the linear system Ax = b.
(ii) Let the right-hand side vector b = Ae where
e = [1 1 ... 1]T
and the true solution of Ax = b is e. Write a MATLAB program to implement the Gauss-Seidel method for solving Ax = b with the initial guess x0 = 0 and the stopping criterion is as follows:
||xn - e|| 2 < 10-6
where xn is the approximate solution obtained in the nth iteration.
(iii) What is the computational cost in each iteration of the Gauss-Seidel method?
(iv) Report the number of iterations for convergence for the following pairs of (n,d), n = 10, 20, 30, 40 and d = 2, 3, 4, 5. Discuss your observations.
(b) We then consider solving the same linear system of equations by using the Block Jacobi method. The idea is to consider the splitting of the matrix A as the sum of the diagonal block bimatrix
and the bi-diagonal block matrix (A - D).
(i) Write a MATLAB program to implement the Block Jacobi method for solving Ax = b with the initial guess x0 = 0 and the same stopping criterion
||xn - e|| 2 < 10-6
where xn is the approximate solution obtained in the nth iteration.
(ii) What is the computational cost in each iteration of the block Jacobi method?
(iii) Report the number of iterations for convergence for the following pairs of (n,d), n = 10, 20, 30, 40 and d = 2, 3, 4, 5. Discuss your observations.
(c) We then consider solving the same linear system of equations by using the Block Gauss-Seidel method. The idea is to consider the splitting of the matrix A as the sum of the lower triangular blocks
and the upper triangular blocks (A - L).
(i) Write a MATLAB program to implement the block Gauss-Seidel method for solving Ax = b with the initial guess x0 = 0 and the same stopping criterion
||xn - e|| 2 < 10-6
where xn is the approximate solution obtained in the nth iteration.
(ii) What is the computational cost in each iteration of the block Gauss-Seidel method? (iii) Report the number of iterations for convergence for the following pairs of (n,d), n = 10, 20, 30, 40 and d = 2, 3, 4, 5. Discuss your observations.