2
$\begingroup$

I'm interested in calculating the inverse of the following matrix in order to solve a system of linear equations.

$$T=\begin{pmatrix} b & a & 0 & 0 & \cdots & a\\ a & b & a & 0 & \cdots & 0\\ 0 & a & b & a & \cdots & 0\\ 0 & 0 & a & b & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & a & b & a & 0\\ 0 & 0 & 0 & a & b & a\\ a & 0 & 0 & 0 & a & b \end{pmatrix}$$

This matrix is almost tridiagonal, except for entries in the top-right and bottom-left corners. I have seen how to calculate the inverse of tridiagonal matrix, but how would those corner-entries affect the inverse?

By the way, this matrix shows up in the Crank-Nicolson method applied to parabolic PDE's (diffusion equation particularly) with periodic boundary conditions.

$\endgroup$
5
  • $\begingroup$ Depending on condition Woodbury identity or an iterative solver $\endgroup$ – user251257 Aug 31 '16 at 17:52
  • $\begingroup$ @user251257 Could you elaborate on how I could use an iterative solver? And what do you mean "depending on condition"? Do you mean "depending on your computational tools"? $\endgroup$ – Arturo don Juan Aug 31 '16 at 17:54
  • $\begingroup$ the woodbury identity is not that stable. So a bad conditioned matrix (or the the tridiagonal part) makes the identity useless for numerical application. There is a large range of iterative solvers. For example, Jacobi method is pretty simple but usually slow. $\endgroup$ – user251257 Aug 31 '16 at 17:59
  • $\begingroup$ ah, sorry, i have made an error. Do you really need the inverse? Don't you just need to solve linear equations with that matrix? $\endgroup$ – user251257 Aug 31 '16 at 18:25
  • $\begingroup$ @user251257 Yes, that is what I need. I'll edit this question. $\endgroup$ – Arturo don Juan Aug 31 '16 at 18:31
1
$\begingroup$

I assume, that you want to solve $Ax = b$, and you are not iterested in the inverse $A^{-1}$ (which is dense).

You may perform the LQ factorization of $A$ (or QR of $A'$) using Givens rotations. In this case $n$ rotations are required. Then resulting $L$ matrix is lower triangular with two subdiagonals except the last row of $L$, which is dense and must be stored separately. The matrix $Q$ cannot be formed explicitly, since is dense. Required decomposition can be performed in $O(n^2)$ operations.

$\endgroup$
0
$\begingroup$

The Sherman-Morris formula can be used for this type of matrix https://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula

$\endgroup$
-1
$\begingroup$

This can be solved efficiently by using the Thomas algorithm. The Wikipedia page does a pretty good job on explaining it. For your case of periodic boundary, you may need to spend a little bit more time to look for a better explanation.

$\endgroup$

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.