Inversa de matriz dispersa no es generalmente escasa

Question

Tengo una pregunta con respecto a la inversa de matrices cuadrado escasos (o puede restringirse a real simétricos matrices definidas positivas).

Me encontré con varias veces las páginas web que indica que la inversa de la matriz sparse no es generalmente escasa y mi experiencia también lo dijo. Una excepción puede ser matrices diagonales.

¿Cómo puede verificarse la clase tesis de afirmaciones?

Answer 1

Primero de todo, que yo sepa no existe una definición precisa de una matriz dispersa. La palabra dispersas se utiliza para una serie de $(A_n)_{n\in\mathbb{N}}$ $n\times n$ matrices cuya fracción de la no-cero entradas converge a cero.

Considerar la serie de matrices de $A_n$ entradas $1$ en la diagonal y en la posición por encima de la diagonal, y cero entradas de otra manera, que es $$A_n = \begin{pmatrix} 1 & 1 & 0 & \cdots & 0 \\ 0 & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & 0 \\ \vdots & & \ddots & \ddots & 1 \\ 0 & \cdots & \cdots & 0 & 1 \end{pmatrix}$$

El número de no-cero entradas de $A_n$$n + (n-1) = 2n - 1$, por lo que la fracción no-cero entradas es $\frac{2n - 1}{n^2}$. Desde $\lim_{n\to \infty} \frac{2n-1}{n^2} = 0$, la serie $A_n$ es escasa.

Es sencillo comprobar que todas las matrices $A_n$ son invertible con la inversa de la $A_n^{-1} = (b_{ij})$ donde $$b_{ij} = \begin{cases} 0 & \text{ if }i>j\text{,}\\ 1 & \text{ if }i \leq j\text{ and }j-i\text{ even,}\\ -1 & \text{if }i \leq j\text{ and }j-i\text{ odd,} \end{casos}$$ que es $$ A_n^{-1} = \begin{pmatrix} 1 & -1 & 1 & \cdots & \pm 1 \\ 0 & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & 1 \\ \vdots & & \ddots & \ddots & -1 \\ 0 & \cdots & \cdots & 0 & 1 \end{pmatrix}$$ La fracción no-cero entradas de $A_n^{-1}$ es $$\frac{(n^2 + n)/2}{n^2} \desbordado{n\to \infty}{\rightarrow} 1/2, $$ así que la serie $A_n^{-1}$ no es escasa.

Answer 2

Un buen ejemplo es una matriz de la flecha, como\begin{equation} A = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \ \end{bmatrix}. \end{Equation} puede comprobar que $A^{-1}$ es denso. Los factores de LU de $A$ no están muy escasos.

Sin embargo, es posible encontrar una factorización «escasos LU» $A$:\begin{equation} A = PLUQ^T, \end{ecuación } donde $P$ y $Q$ matrices de la permutación y $L$ y $U$ son escasos. Puede observar esto en Matlab usando la función de lu.