3
$\begingroup$

The Jacobi method is an iterative method for approaching the solution of the linear system $Ax=b$, with $A\in\mathbb{C}^{n\times n}$, where we write $A=K-L$, with $K=\mathrm{diag}(a_{11},\ldots,a_{nn})$, and where we use the fixed point iteration $$\alpha_{j+1}=K^{-1}L\alpha_j+K^{-1}b,$$ so that we have for a $j\in\mathbb{N}$: $$\alpha-\alpha_{j+1}=K^{-1}L(\alpha-\alpha_{j}).$$

Now my syllabus provides a proof for convergence for the case that $A$ is diagonally-row dominant, but I and our teacher both couldn't see a way to rewrite the proof to a proof for the diagonally-column dominant case. The proof for the diagonally-row dominant is given using the $\|\cdot\|_{\infty}$ norm, and I found on the internet that the diagonally-column dominant case can be proved using the $\|\cdot\|_{1}$ norm. The proof strategy would be to show that $$\|\alpha-\alpha_{j+1}\|\leq \rho^j\|\alpha-\alpha_1\|,$$ for some matrix norm $\|\cdot\|$ and a $0\leq\rho<1$, from which convergence would follow immediately.

Does anyone have an idea how to continue? Using the $\|\cdot\|_{1}$ norm as suggested by the internet we want to have something like $$\|\alpha-\alpha_{j+1}\|_1\leq\|(K^{-1}L)^j\|_1\cdot\|\alpha-\alpha_1\|_1,$$ and somehow conclude $\|K^{-1}L\|_1$ should be bounded by $1$. I know about the characterization $$r:=\max_{i\in\{1,\ldots,n\}}\Bigg\{|a_{ii}|^{-1}\sum_{\substack{i&=1\\ i&\neq j}}|a_{ji}|\Bigg\}.$$

I'd like to proof this without Gershgorin's theorem, since this is not covered in my course. It is fine if the case follows from the diagonally-row dominant case.

$\endgroup$
4
$\begingroup$

The Jacobi iteration is an example of a stationary iteration $$ x_{n+1} = G x_n + f.$$ By induction we obtain $$ x_n = \sum_{j=0}^n G^j f.$$ In particular, we have $x_n \rightarrow (I-G)^{-1}f$ when, say, $\|G\|_\infty<1$ or $\|G\|_1 < 1$.

Now, Jacobi's method is often introduced with row diagonal dominance in mind. Therefore, the linear system $Ax=b$ is rewritten at $Dx = (D-A)x+b$ where $D$ is the main diagonal. This gives rise to the stationary iteration corresponding to $G = D^{-1}(D-A)$ and $f = D^{-1}b$. If $A$ is strictly diagonally dominant by rows, then $\|G\|_\infty < 1$ is immediate. However, another construction is possible. The introduction of a new variable $y = Dx$ yields the equivalent linear system $y = (D-A)D^{-1} y + b$ and the stationary iteration $$y_{n+1} = (D-A) D^{-1} y_n + b.$$ When $A$ is strictly diagonally dominant by columns, the driving matrix $G = (D-A)D^{-1}$ satisfies $\|G\|_1 < 1$. In this case $y_n \rightarrow y$ which solves $y = (D-A)D^{-1} y + b$. Now, what about Jacobi's method? With the definition $z_n := D^{-1}y_n$ we have $z_{n+1} = D^{-1}(D-A)z_n + D^{-1}b$, i.e., Jacobi's method. The sequence $z_n$ is convergent because the sequence $y_n$ is convergent and $z_n \rightarrow z$ where $z$ solves the equation $z=D^{-1}(D-A)z+D^{-1}b$, i.e., $z = x = A^{-1}b$.

$\endgroup$
  • $\begingroup$ Thank you for your detailed answer everything is clwar to me now. You're approach is clearer than the one in my syllabus. I also found out I had a misunderstanding about the definition of the imduced matrix norms, which made solving this problem impossible $\endgroup$ – Václav Mordvinov Jun 9 '18 at 12:45
  • $\begingroup$ I was also confused but this is a truly a great answer! Thanks :) +1 $\endgroup$ – rae306 Jun 9 '18 at 18:04
  • $\begingroup$ @VáclavMordvinov Thank you for your kind words. Until today I had never thought to establish the convergence without using Gershgorin's theorem. I was happy to learn that it was not necessary. Later, when you have the time, then you should study Gershgorin's theorem. It is a classical result with a short proof and some good extensions. $\endgroup$ – Carl Christian Jun 9 '18 at 22:16
  • $\begingroup$ @rae306 Thank you! Writing clearly is important to me so I appreciate the feedback. $\endgroup$ – Carl Christian Jun 9 '18 at 22:17
  • $\begingroup$ @CarlChristian I just read the theorem, proof and one extension on Wikipedia, and it is a nice result with a really easy proof indeed! $\endgroup$ – Václav Mordvinov Jun 10 '18 at 7:21

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.