Jacobi Method with error

Preparing for my Numerical Analysis exam,

If the Jacobi's method is used to solve the linear system, $Ax=b$, where $$A=\begin{pmatrix}5 & -2 & 3\\-3 & 9 & 1\\2&-1&-7\end{pmatrix}$$

will the method be convergent?

This part I think I can do. Since there is no $b$ vector as in $Ax = b$, we cannot iterate toward a solution. Instead we reason that $A$ will converge using the Jacobi method as it is diagonally dominant.

Then it says, Determine the matrix G in the error equation $e_{n+1} = Ge_n$, and test the convergence criterion using either $||\cdot||_\infty$ or $||\cdot||_1$ norm.

I know that the norms are the max of the column and row sums, but I don't understand the "find the matrix G in the error equation" part of the question.

• If you do the calculations, writing $x_i = x+e_i$, you should find that the error $e_{i+1}$ depends in a nice way on the previous error $e_i$ (and in fact, it may well satisfy a linear transformation). Commented Mar 3, 2014 at 18:17
• @tabstop forgive me, but I truthfully don't understand what you mean. Given that there is no solution vector, we cannot iterate toward convergence / divergence, but knowing that $A$ is diagonally dominant, means that it's guaranteed to converge. Commented Mar 3, 2014 at 18:26
• If you don't have a solution vector, then you don't have a problem; so we can take it as read that $b$ exists, even if we don't know what it is. Its value is irrelevant to the problem. Commented Mar 3, 2014 at 20:18

If we write $$x_{k+1}=D^{-1}(b-Rx_k)$$ where $D$ is the diagonal bit and $R$ is everything else, and we write $x_k=x+e_k$ where $e_k$ is the error in the $k$'th iterate, then $$x+e_{k+1} = D^{-1}b-D^{-1}R(x+e_k)$$ and multiplying through by $D$ we have $$Dx + De_{k+1} = b-Rx-Re_k$$ but since $x$ is a solution, $Dx+Rx=b$; consequently $$De_{k+1} = -Re_k$$ regardless of the value of $b$. Presumably you can figure out from here how to get $e_{k+1}$ by itself.

In methods like Jacobi and Gauss-Seidel, you create a fixed point iteration of the form $$f(x_k) = x_{k+1} = Tx_k + c$$. For it to work, you require that at your solution $$x^{*}$$ the iteration returns $$x^{*}=f(x^*)=Tx^{*} + c$$ . We can express the equation $$Ax=b$$ as

$$Ax = (L + D + U)x = b$$ $$Dx = -(L+U)x + b$$ $$x = -D^{-1}(L+U)x + D^{-1}b$$

If we turn this into an iteration we already have the form we wanted above and we know that at the solution the iteration will return the solution, since that is how we got it in the first place.

This is actually the Jacobi iteration, where the iteration matrix $$T=-D^{-1}(L+U)$$.

The question now is whether this iteration will converge and for which $$x_0$$. To answer this question we define the error at step $$k$$ and then substitute with the equations we derived above.

$$x_{k} - x^{*} = e_{k} = Tx_{k} + c - Tx^{*} - c = T(x_{k} - x^{*}) = Te_{k} = T^{k}e_{0}$$

So the error at each step is transformed by $$T$$ and is amplified or increased linearly by it. We want the error to decrease, so we need to derive a condition that guarantees that the error will disappear, which we can do using matrix norms and two associated inequalities $$|Ax| \leq ||A||\; |x|$$ and $$||AB|| \leq ||A||\;||B||$$:

$$|T^ke_0| \leq ||T^k||\;|e_0| \leq ||T||^k\;|e_0| \implies e_0 \rightarrow 0$$ as $$k \rightarrow \infty$$ iff $$||T||<1$$ for some norm of T and any $$x_0$$.

So the $$G$$ in your case is the $$T$$ in my explanation and it is the iteration matrix that ends up remapping the error you make at each step of the iteration we have derived above.