Homework Assignment #7

(due: May 27 in class)




Theory Part

Problem 1 (30%):
Show that the following linear system of equations converges for both, Gauss Jacobi and Gauss Seidel methods:

E1: 4*x1 - x2 -x4 = 0
E2: -x1 +4*x2 -x3 -x5 = 5
E3: -x2 +4*x3 -x6 = 0
E4: -x1 +4*x4 -x5 = 6
E5: -x2 -x4 +4*x5 -x6 = -2
E6: -x3 -x5 + 4*x6 = 6


Bonus Problem(20%):
Proof part ii) of Corollary 7.20.
i.e., proof that for ||T||<1, the following error bound holds for the sequence {x(k)}, defined by x(k) = Tx(k-1) + c:

||x(k) - x|| <= ||T||(k) / (1-||T||) * ||x(1) - x(0)||

Hints
i) Consider ||x(m) - x(k)|| for any m > k > 1. Show that this is less or equal then ||x(m) - x(m-1)|| + ||x(m-1) - x(m-2)|| + ... + ||x(k+1) - x(k)||
ii) Now use that ||x(k+1) - x(k)|| = ||Tx(k) - Tx(k-1)||
iii) Since ||T|| < 1, the series converges, i.e. x(m) --> x as m --> infinity.
iv) The geometrical series sum(i=0,infinity) (xi) = 1/(1-x) for 0 < x < 1.

Numerics Part

Problem 3 (70%):
a) Solve problem 1 above using the Gauss Jacobi Method.
b) Solve problem 1 above using the Gauss Seidel Method.
c) Solve problem 1 above using the SOR method with omega = 1.1, 1.2, 1.3, 1.4, 1.5

Use a tolerance of 0.001. Set the maximum number of iterations to 100 (you will need fewer !). Use the following stopping criteria:
|| x(k) - x(k-1) ||infinity / || x(k) ||infinity < tolerance.

d) Compare the efficiency of the algorithms in (a), (b), and (c) (i.e., compare the number of iterations)

What you should turn in:
The codes you used in (a), (b), and (c).
Your final results for x for (a), (b), and (c).
Your answer to (d).