# How can I efficiently calculate the inverse of this symmetric near-tridiagonal matrix?

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.

• Depending on condition Woodbury identity or an iterative solver – user251257 Aug 31 '16 at 17:52
• @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"? – Arturo don Juan Aug 31 '16 at 17:54
• 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. – user251257 Aug 31 '16 at 17:59
• 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? – user251257 Aug 31 '16 at 18:25
• @user251257 Yes, that is what I need. I'll edit this question. – Arturo don Juan Aug 31 '16 at 18:31

## 3 Answers

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.

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

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.