0

Given the $n\times n$ matrix $$B=\begin{bmatrix} \frac{1}{2}&\frac{1}{2^2}&\frac{1}{2^3}&\cdots &\frac{1}{2^n}\\ a &0&0 &\cdots&0 \\ 0 &a&0&\cdots &0\\ \vdots&\ddots &\ddots&\ddots&\vdots\\ 0&\cdots&\cdots&a&0\end{bmatrix}$$ I want to prove the Gauss-Seidel or Jacobi method used to solve linear system of equations $Ax=b$ converge (in this case, for any vector $b$). I know the Jacobi iteration matrix is $D^{-1}(L+U)$ where $$D=\begin{bmatrix}1/2&0&\cdots&0 \\ 0&0&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&0&0\end{bmatrix}$$ $$L=\begin{bmatrix}0&0&\cdots&\cdots&0 \\ a&0&\cdots&\cdots&0\\ 0&a&0&\cdots&0\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&0&a&0\end{bmatrix}$$ $$U=\begin{bmatrix} 0&\frac{1}{2^2}&\frac{1}{2^3}&\cdots &\frac{1}{2^n}\\ 0 &0&0 &\cdots&0 \\ 0 &0&0&\cdots &0\\ \vdots&\ddots &\ddots&\ddots&\vdots\\ 0&\cdots&\cdots&0&0\end{bmatrix}$$ are all $n\times n$ matrices. To converge, the Jacobi iteration matrix must have a spectral radius of $|\rho|<1$. The problem is that $D$ is not invertible, so I can't calculate this matrix. The same happens with the Gauss-Seidel iteration matrix: $(D+L)^{-1}U$. What can I do to avoid that problem?

mathie12
  • 191
  • Is the upper-right entry $\frac{1}{2n}$ or $\frac{1}{2^n}$? – zipirovich Jun 18 '18 at 01:35
  • It's $\frac{1}{2^n}$ thank you for pointing it out. – mathie12 Jun 18 '18 at 01:36
  • I think you should work with the pseudoinverse of $D$, which for a diagonal matrix is just "take the reciprocal of the nonzero diagonal elements, leave the zeros be". You can probably also work with the pseudoinverse of $D+L$ in Gauss-Seidel, but that will take a little more effort to calculate. – Ian Jun 18 '18 at 01:37
  • Just keep in mind that you really just want to find a mapping $F$ such that if $x=F(x)$ then $Ax=b$. The real problem with my suggestion for Jacobi is that $x=F(x)$ is equivalent to $(Ax)_1=b_1$. – Ian Jun 18 '18 at 02:13
  • What about permuting the matrix such that there are elements on the diagonal? Just move every row up and the top to the bottom. Issue is that then the matrix is certainly not diagonal dominant (see last row), but it might be possible to show that the spectral radius of the iteration matrix is less than one. – Dan Doe Apr 22 '22 at 06:57

0 Answers0