MATH 3511 SPRING 2023 HOMEWORK 2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH 3511 SPRING 2023 HOMEWORK 2
(DUE IN CLASS FEBRUARY 10)
Instructions: For written questions, write your answers on your own papers. For pro- gramming questions, submit your codes using MATLAB Grader. Hand in your homework (written part) on Friday, February 10 before class.
For the first two problems, we want to examine two important theorems we discussed in class.
Theorem 1. If A is symmetric positive definite, then the Gauss-Seidel method converges (Jacobi might not converge) .
Theorem 2. If A is strictly diagonally dominant by rows, then the Jacobi and Gauss-Seidel methods converge .
1. (Positive definite matrix) Consider the matrix,
A = \
( 1 1 0.2)
a. Show that A is positive definite.
b. Compute the spectral radius of the iteration matrix of the Jacobi and the Gauss- Seidel methods. Show that forward Gauss-Seidel converges for Ax = b for any b and initial guess while Jacobi diverges.
Remark. Use eig in MATLAB when you calculate the eigenvalues .
2. (Diagonally dominant matrix) Consider the matrix,
A = \ 
(a 0 1)
a. Determine the range of a such that A is strictly diagonally dominant by rows.
b. Compute the spectral radius of the iteration matrix of the Jacobi and the Gauss- Seidel methods. Show that they indeed converge with the values of a in part [a.].
Remark. Calculate the eigenvalues by hand for this problem.
3. (Richardson) Recall that Richardson’s iteration is of the form xk+1 = xk+ γ(b − Axk),
where γ is a positive number. This is a special case of the classical iterative methods we discussed in class with B = γI . Answer the following questions,
a. What is the iteration matrix of Richardson’s iteration?
b. Suppose A has an eigenvalue λ, can you find an eigenvalue of the iteration matrix in terms of λ?
c. If A has a negative eigenvalue, does Richardson’s iteration converge? Why?
d. If A only has positive eigenvalues, what choice of γ guarantees the convergence of Richardson’s iteration? Here we assume the smallest eigenvalue of A is λmin and the largest eigenvalue of A is λmax .
0 λmin λmax
Hint: For part [b.], if A has an eigenvalue λ, then it means Av = λv where v is the associated eigenvector. What can you say about (I − γA)v? For part [d.], what choice of γ guarantees ρ(I − γA) < 1?
4. (Implementation) Implement the Richardson’s iteration and solve the following problem. Submit your codes through MATLAB Grader. Consider Ax = b where
\ 2 −1 0 
\
0(1)
−1 . . . . . .
a. Can you find a γ that makes Richardson’s iteration convergent?
b. According to part [d.] of problem 4, what should be the range of γ for convergence to hold? You can compute this using MATLAB.
Additional Problems (do not submit):
1. Prove that if A is SPD, then all the eigenvaules of A are positive. In other words, prove if xtAx > 0 for all x 
0 implies all the eigenvaules of A are positive.
2. Prove that if all the eigenvaules of A are positive, then A is SPD.
3. Prove that if A is SPD, then all its diagonal entries are positive.
4. Compute problem 4 using Jacobi and Gauss-Seidel and compare the results to Richardson. Using the same stopping criterion, which one is the fastest? Explain your reasoning.
2023-02-11