(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) (x_{i}) = 1/(1-x) for 0 < x < 1.

**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).