Inverse matrix to a bi-diagonal matrix

Question

I need to find an inverse matrix to a bi-diagonal matrix $A$. I know that I can use "inv(A)" but it isn't a good point. Is there any algorithm that can count it easily?

Answer 1

As Surb mentioned, one extremely rarely needs to actually form $A^{-1}$, so you should consider carefully whether you actually need this inverse. Assuming that you still conclude that you want to form $A^{-1}$ (or need a formula for some theoretical analysis), an exact inversion formula for a bidiagonal matrix with a nonzero diagonal can be produced.

Consider the matrix

$$ A = \begin{bmatrix} a_1 & b_1 \\ & a_2 & b_2 \\ & & \ddots & \ddots \\ & & &a_n \end{bmatrix}. $$

Suppose the diagonal entries of $A$ are nonzero and write this as

$$ A = \operatorname{diag}(a_1,a_2,\ldots,a_n) \underbrace{\begin{bmatrix} 1 & b_1/a_1 \\ & 1 & b_2/a_2 \\ & & \ddots & \ddots \\ & & &1 \end{bmatrix}}_{=C}. $$

Define $c_i = - b_i/a_i$. Then

$$ C = \begin{bmatrix} 1 & -c_1 \\ & 1 & -c_2 & \\ & & \ddots & \ddots \\ & & & 1\end{bmatrix}. $$

One can check that

$$ C^{-1} = \begin{bmatrix} 1 & c_1 & c_1c_2 & \cdots & c_1\cdots c_{n-1} \\ 0 & 1 & c_2 & \cdots & c_2\cdots c_{n-1} \\ 0 & 0 & 1 & \cdots & c_3\cdots c_{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \end{bmatrix}. $$

$A^{-1}$ is then given by $A^{-1} = C^{-1}\operatorname{diag}(1/a_{1},\ldots,1/a_n)$. Evaluating the products that appear in $C$ in a clever order gives an optimal $O(n^2)$ way of evaluating and storing the dense matrix and an $O(n)$ algorithm for evaluating any entry of $A^{-1}$ for $A$ an $n\times n$ matrix. This formula is numerically stable only if the diagonal entries of $A$ are not small relative to the off-diagonal entries of $A$. If this is not the case, you need to be very careful to get an accurate answer and a well-established library like MATLAB's inv is probably the safest best.

If you need a representation of the inverse, note that $A^{-1}$ is a semiseparable matrix which means a structured representation of $A^{-1}$ can be stored in only $O(n)$ space.