Invertibility de la incertidumbre de la matriz

Question

Dado que partimos de unos $n\times n$ matriz cuadrada $A_0$ que es no singular. Añadimos algo de perturbación, $\Delta A$, por lo que nuestra nueva matriz es $A = A_0 + \Delta A$. La pregunta es si podemos garantizar invertibility de nuestro nuevo $A$ matriz de si $|\Delta A_{ij}|<\rho$. Nos podemos referir a esta $\rho$ como el radio de invertibility o el radio de la no singularidad.

No parece ser un documento que habla sobre este problema exacto, el aditivo caso: http://www.eecs.berkeley.edu/~elghaoui/Pubs/InvErr_LAA02. Se dice que el $\rho$ es el menor valor singular de a $A$.

Mi pregunta es, si queremos generar algo random $A$ matriz invertible, podemos experimentalmente convergen en $\rho$ a través de numerosos ensayos? Supongo que esto es más de una pregunta acerca de los posibles algoritmos de álgebra lineal.

Answer 1

En realidad, si $A=A_0+\Delta A$ donde $A_0$ es invertible, entonces para todos los $\Delta A$ tal que $\|\Delta A\|_*<\rho$ $\rho=1/\|A_0^{-1}\|_*$ la matriz $A$ es invertible así. Esto es válido para cualquier sub-multiplicativa de la matriz de norma $\|\cdot\|_*$ consistente con algunos (pero más o menos arbitrarias) vector de norma $\|\cdot\|$, $\|Ax\|\leq\|A\|_*\|x\|$. Tenga en cuenta que $\|\cdot\|_*$ no necesariamente tiene que ser el operador de la norma inducida por el vector de norma $\|\cdot\|$. Es decir, todas las matrices $A$ en una bola abierta centrada en $A_0$ con el radio de $\rho$ es invertible. La forma de la bola depende de la elección de la norma $\|\cdot\|_*$.

De hecho, para la 2-norma, que es, $\|\cdot\|_*=\|\cdot\|_2$, $\rho=1/\|A_0^{-1}\|_2=\sigma_{\min}(A_0)$.

Desde el conjunto de invertir matrices es densa, no es probable que una generados al azar de la matriz va a ser singular. Sin embargo, uno simplemente puede calcular o estimar el $\rho$ de las $A_0$ y la norma elegida usando $\rho=\|A_0^{-1}\|_*$. Ya que para cualquier $x\neq 0$, $\|A_0^{-1}\|_*\leq\|A_0^{-1}x\|/\|x\|=\|y\|/\|A_0y\|$ con $y=A_0^{-1}x$, se puede estimar $\|A_0^{-1}\|_*$ por un procedimiento que intenta maximizar el cociente $\|y\|/\|A_0y\|$ sobre todos los distinto de cero $y$.

De nuevo, para la 2-norma, esto podría conducir a una especie de iteración inversa aplicada a $A_0^TA_0$.

---

La prueba de la primera instrucción: Vamos a $A_0$ ser invertible y deje $\|\cdot\|_*$ ser un sub-multiplicativa de la matriz de la norma en consonancia con algunos de vectores de norma $\|\cdot\|$. Suponga que $A=A_0+\Delta A$ es singular. Existe un vector distinto de cero $x$ tal que $0=Ax=A_0x+\Delta A x$, $x=-A_0^{-1}\Delta A x$. Por lo tanto $\|x\|=\|A_0^{-1}Ax\|\leq\|A_0^{-1}\|_*\|A\|_*\|x\|$ y, por tanto, dividiendo por $\|x\|\neq 0$ da $\|A\|_*\geq 1/\|A_0^{-1}\|_*=\rho$. Desde $A_0+\Delta A$ ser singular implica que $\|\Delta A\|\geq\rho$, mediante la inversión de la implicación, conseguimos que los si $\|\Delta A\|<\rho$ $A=A_0+\Delta A$ es nonsingular.

Answer 2

Desde el determinante es un polinomio (en la matriz de entradas), es un mapa continuo, por lo que su inversa mapas abiertos los conjuntos de bloques abiertos (dada una norma de matrices, pero todos ellos son equivalentes, ya que estamos en dimensión finita). Desde $\Bbb R - \{0\}$ es abierto, por lo que es el conjunto de invertir matrices (que simplemente es $\det^{-1}(\Bbb R - \{ 0 \})$). Por lo tanto, dado un no-singulares de la matriz A, se puede encontrar una "bola" de matrices en torno a Una que contiene sólo nonsingular matrices. Así que la respuesta a tu primera pregunta, sí, se puede :-)

Respecto a la segunda cuestión, aviso primero que $\rho$ depende de su matriz norma. Tomemos $||A||=\max |a_{i\,j}|$. A continuación, $\rho$ no es ciertamente mayor que (el valor absoluto de) el menor autovalor de a $A$, ya que el $\det(A - \lambda_{min}I) = 0$.

He intentado esto: calcular SVD de a$A$$A = U D V^T$. A continuación, calcular $B=U(D-tI)V^T$ donde $t$ es el menor valor singular de a $A$.

Por lo tanto, $B$ es singular por su diseño (su menor valor singular es $0$). Y valores singulares de a $A-B$ son todos iguales a $t$, ya que el $A-B=U(tI)V^T$.

Así que tienes un $\Delta A = B-A$, de tal manera que $A+\Delta A$ es singular, y el espectro de la norma de $\Delta A$ es el mínimo valor singular de a $A$.