# Compute two steps of the Jacobi and Gauss-Seidel methods starting with $(0,0)^T$

Compute two steps of the Jacobi and Gauss-Seidel methods starting with $$(0,0)^T$$ for the system $$\begin{bmatrix}4&1\\1&2\\\end{bmatrix} \begin{bmatrix}x\\y\\\end{bmatrix} = \begin{bmatrix}-1\\1\\\end{bmatrix}$$ Do you expect the iteration to converge and if so, why?

Below I have details of the first question, are they correct? this is my first time using these two methods. Secondly, I am not sure what to say about the convergence of these methods, looking for some help with this answer, thanks!

to begin with solve for $$x$$ and $$y$$ $$x = \frac{1}{4}(-1-y)$$ $$y = \frac{1}{2}(1-x)$$ Using Jacobi method: first approximation using $$x=y=0$$ $$x_1 = \frac{1}{4}(-1-0)=-0.25$$ $$y_1 = \frac{1}{2}(1-0)= 0.5$$ Second iteration using $$x_1 = -0.25, y_1 = 0.5$$ $$x_2 = \frac{1}{4}(-1-0.5) = -0.375$$ $$y_2 = \frac{1}{2}(1-(-0.25)) = 0.625$$

Using Gauss-Seidel method: first computation is identical to above calculation. That is using $$(0,0)$$ as the initial approximation, you obtain the following new value for $$x_1$$ $$x_1 = -\frac{1}{4} = -0.25$$ Now that we have a new value for $$x_1$$ we use it to compute a new value for $$y_1$$. That is, $$y_1 = \frac{1}{2}(1-(-0.25)) = 0.625$$ second computation use $$y_1 = 0.625$$ $$x_2 = \frac{1}{4}(-1-0.625) = -0.40625$$ use $$x_2 = -0.40625$$ to solve $$y_2$$ $$y_2 = \frac{1}{2}(1-(-0.40625)) = 0.703125$$

• @copper.hat thanks for the edit, could you help me with my questions? – jh123 Oct 20 '18 at 21:35

Your computations look good.

The Jacobi iteration is given by $$x_{k+1} = D^{-1}(b-Rx_k)$$, so to check convergence we look at the spectral radius (largest modulus of an eigenvalue) of $$D^{-1}R$$. If it is less than one it converges, otherwise it may not converge.

A sufficient condition that implies $$\rho(D^{-1}R) < 1$$ is strict diagonal dominance, so if $$a_{kk} > \sum_{i \neq k} a_{ki}$$ for all rows then $$\rho(D^{-1}R) < 1$$. It is straightforward to check that this holds in this case.

The same sort of analysis applies to Gauss Seidel, the iteration is $$x_{k+1} = L^{-1}(b-Ux_k)$$ and we look at the spectral radius of $$L^{-1}U$$. It turns out that strict diagonal dominance is a sufficient condition for this as well.

• Okay so for the jacobi I look at the matrix a and see that a11=4 which is greater then a12 and a22= 2 is greater then a21 so it converges – jh123 Oct 20 '18 at 21:55
• But how do I test for gauss seidal? Is it the same thing? – jh123 Oct 20 '18 at 21:56
• Strict diagonal dominance works for both. – copper.hat Oct 20 '18 at 21:57
• Okay so they both converge then? – jh123 Oct 20 '18 at 21:57
• Glad to be able to help! – copper.hat Oct 20 '18 at 22:06