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$$

  • $\begingroup$ @copper.hat thanks for the edit, could you help me with my questions? $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – jh123 Oct 20 '18 at 21:55
  • $\begingroup$ But how do I test for gauss seidal? Is it the same thing? $\endgroup$ – jh123 Oct 20 '18 at 21:56
  • $\begingroup$ Strict diagonal dominance works for both. $\endgroup$ – copper.hat Oct 20 '18 at 21:57
  • $\begingroup$ Okay so they both converge then? $\endgroup$ – jh123 Oct 20 '18 at 21:57
  • 1
    $\begingroup$ Glad to be able to help! $\endgroup$ – copper.hat Oct 20 '18 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.