Proving iterative methods to calculate a linear system of equations converge.

36 Views Asked by At

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?