Math 551 Section 01 Summer 2023
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Math 551 Section 01
Summer 2023
Chapter 7 Homework due Wednesday,June 28th at 11:59 PM
Notes: Try to answer all the questions by demonstrating all the steps of your cal-culations. Please submit your homework on Gradescope. This homework assignment covers Sections 7.1-7.3. Answer all the questions by demonstrating all the steps of your calculations. The MATLAB scripts for questions 3-5 are posted on Blackboard.
1. (20 points) In class, we discussed iterative schemes based on a specific splitting of a n x n matrix A to solve the linear system Ax = b.
(a) (10 points) If A = M - N, then show that the following schemes are equivalent:
Mxk+1 = Nxk + b;
xk+1 = (I - M一1 A)xk + M一1 b, where I is the identity matrix; xk+1 = xk + M一1 rk , where rk = b - Axk .
(b) (10 points) A totally equivalent splitting of A that we discussed is of the form: A = L + U + D . Note that, L is strictly lower triangular, U strictly upper triangular and D diagonal. This way, the Jacobi method reads
xk+1 = RJ xk + D一1 b,
with RJ the Jacobi iteration matrix RJ = -D一1 (L + U). If A is strictly
diagonally dominant, show that the Jacobi iteration matrix satisfies llRJ ll& < 1.
Note that if this condition holds, then the Jacobi method converges for any
initial vector x0 .
Hints :
n
● An n x n matrix A is strictly diagonally dominant if laii l > laij l holds.
j=1 j i
● Note that if A is an n x n matrix, then llAll& = j(n)=1 laij l.
2. (25 points) Consider the linear system
x1 + x2 + 3x3 = 5,
3x1 + x2 + x3 = 6,
x1 + 3x2 + x3 = 3,
(a) (15 points) Rearrange the equations to form a strictly diagonally dominant sys- tem. Perform two iterations of the Jacobi and Gauss–Seidel Methods (using the component form) from starting vector x0 = [0, 0, 0]T .
(b) (10 points) Perform two iterations of SOR to the system. Use starting vector x0 = [0, 0, 0]T and ω = 1.5.
3. (35 points) The linear system Ax = b with
A = ┌1(4) 4(1)┐ , b = ┌ ┐5(5)
has the unique solution x = [1 1]T .
(a) (15 points) Determine by hand the RJ = -D一1 (L + U) and RGS = -(L + D)一1 U, that is, the Jacobi and Gauss-Seidel iteration matrices, respectively (of course you may use MATLAB to verify your answers).
(b) (10 points) Find the o-norm and spectral radius of RJ and RGS .
(c) (10 points) Use the MATLAB script _q dw4 m3 .h to perform 5 iterations of both Jacobi and Gauss-Seidel methods using x0 = [0 0]T . For each present your results in a table with the following format:
● column 1: k (iteration step)
● column 2: x k) (1st component of the computed solution vector at step k)
● column 3: xk) (2nd component of the computed solution vector at step k)
● column 4: lle(k)ll& (error norm at step k)
● column 5: lle(k)ll& /lle(k 一1) ll& (ratio of successive error norms at step k).
Which method is converging faster? Justify your answer.
4. (10 points) Employ the Successive Over-Relaxation (SOR) method to solve the linear system
2x1 - x2 = 5,
-x1 + 2x2 - x3 = -2,
-x2 + 2x3 = 2,
with ω = 1.3 and initial vector x0 = [0 0 0]T . Stop the iterations when llrk ll2 < tol llbll2 holds with tol = 10一10 . Use and modify the MATLAB script _q dw4 m4 .h. Provide MATLAB output which includes the solution.
5. (10 points) Assume that ω e [0.5, 1.8] and notice that the case with ω < 1 corresponds to the Successive Under-Relaxation and ω > 1 to SOR. Also, when ω = 1, this is the original Gauss-Seidel method. Use and modify the MATLAB script _q dw4 m5 .h. Plot the spectral radius of the iteration matrix:
RSOR = (ωL + D)一1 [(1 - ω) D - ωU] ,
for the matrix A given in Question 4. What is the optimal value of ω here, i.e., ωopt ? Note that the ωopt which corresponds to the value such that the spectral radius ρ(RSOR ) attains its minimum value. Verify your answer by running code developed in Question 4 for ω = ωopt . Include its output together with the plot of ρ(RSOR ) as a function of ω and the code producing it.
2023-06-26