Jacobi Method with error

Question

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.

Answer 1

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.

Answer 2

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.