0

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
  • 172,524
jh123
  • 1,400

1 Answers1

1

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.

copper.hat
  • 172,524