Inverse matrix to a bi-diagonal matrix 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?
 A: 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.
