5.6: Ejercicios

Ejercicio 5.1

Supongamos que la\(m \times n\) matriz compleja\(A\) se perturbe a la matriz\(A + E\).

a) Demostrar que

\[\left|\sigma_{\max }(A+E)-\sigma_{\max }(A)\right| \leq \sigma_{\max }\tag{E}\]

También encontramos una\(E\) que dé como resultado que la desigualdad se logre con igualdad.

(Pista: Para mostrar la desigualdad, escribe\((A + E) = A + E\) y\(A = (A + E) - E\), toma la 2-norma en ambos lados de cada ecuación, y usa la desigualdad triangular.)

Resulta que el resultado en (a) realmente se aplica a todos los valores singulares de\(A\) y\(A + E\), no solo al más grande. La parte (b) a continuación es una versión del resultado para el valor singular más pequeño.

(b) Supongamos que A tiene un rango de columna inferior al completo, es decir, tiene rango\(< n\), pero\(A + E\) tiene rango de columna completa. Mostrar (siguiendo un procedimiento similar a la parte (a) - pero mirando en\(min \|(A+E)x\|_{2}\) lugar de la norma de\(A + E\), etc.) que

\[\sigma_{\min }(A+E) \leq \sigma_{\max }\tag{E}\]

De nuevo encontramos una\(E\) que dé como resultado que la desigualdad se logre con igualdad.

[El resultado en (b), y algunas extensiones del mismo, dan lugar al siguiente procedimiento sonoro (y ampliamente utilizado) para estimar el rango de alguna matriz subyacente\(A\), dada solo la matriz\(A + E\) y el conocimiento de\(\|E\|_{2}\): Calcular la SVD de\(A + E\), luego declarar el “rango numérico” de \(A\)ser el número de valores singulares de\(A + E\) que son mayores que el umbral\(\|E\|_{2}\). La información dada es consistente con tener una\(A\) de este rango.]

(c) Verifica los resultados anteriores usando tus propios ejemplos en MATLAB. También podría resultarle interesante verificar numéricamente que para grandes\(m, n\), la norma de la matriz\(E = s * randn(m, n)\) -que es una matriz cuyas entradas son independientes, de media cero, gaussiana, con desviación estándar\(s\) - está cerca de\(s *(\sqrt{m}+\sqrt{n})\). Entonces, si\(A\) es perturbado por tal matriz, entonces un valor razonable para usar como umbral al determinar el rango numérico de\(A\) es este número.

Ejercicio 5.2

Dejar\(A\) y\(E\) ser\(m \times n\) matrices. Demostrar que

\[\min _{\operatorname{rank} E \leq r}\|A-E\|_{2}=\sigma_{r+1}\tag{A}\]

Para probar esto, observe que la restricción de rango on\(E\) puede interpretarse de la siguiente manera: Si\(v_{1},. . . v_{r+1}\) son vectores linealmente independientes, entonces existe un vector distinto de cero\(z\), expresado como una combinación lineal de tales vectores, que pertenece al espacio nulo de\(E\). Proceder de la siguiente manera:

1. Seleccione los\(v_{i}\)'s de la SVD de A.
2. Seleccione un elemento candidato\(z\) con\(\|z\|_{2} = 1\).
3. \(\|(A - E)z\|_{2} \geq \sigma_{r+1}\)Demuéstralo. Esto implica que\(\|(A - E)\|_{2} \geq \sigma_{r+1}\).
4. Construir una\(E\) que logre el límite anterior.

Ejercicio 5.3

Consideremos el sistema real, cuadrado de ecuaciones\(Ax = (U \Sigma V^{T})x = y\), donde\(U\) y\(V\) son matrices ortogonales, con

\ [\ Sigma=\ left (\ begin {array} {cc}
1 & 0\\
0 & 10^ {-6}
\ end {array}\ right),\ quad y=U\ left (\ begin {array} {c}
1\\
10^ {-6}
\ end {array}\ right)\ nonumber\]

Todas las normas en este problema se toman como 2 normas.

a) ¿Cuál es la norma de la solución exacta\(x\)?

b) Supongamos que\(y\) está perturbado a\(y + \delta y\), y que correspondientemente la solución cambia de\(x\) en (a) a\(x + \delta x\). Encuentra una perturbación\(\delta y\), con\(\|\delta y\|= 10^{-6}\), tal que

\[\frac{\|\delta x\|}{\|x\|} \approx \kappa(A) \frac{\|\delta y\|}{\|y\|}\nonumber\]

donde\(\kappa (A)\) esta el numero de condicion de\(A\).

(c) Supongamos que en lugar de\(y\) perturbarnos nos perturbaremos\(A\)\(A + \delta A\), cambiándolo a, con la solución cambiando correspondientemente de\(x\) a\(x + \delta x\) (para algunos\(\delta x\) que es diferente a en la parte (b)). Encuentra una perturbación\(\delta A\), con\(\|\delta A\|= 10^{-7}\), tal que

\[\frac{\|\delta x\|}{\|x\|} \approx \kappa(A) \frac{\|\delta A\|}{\|A\|}\nonumber\]

Ejercicio 5.4 Matrices Definitivas Positivas

Una matriz\(A\) es positiva semidefinida si es\(x^{\prime}Ax \geq 0\) para todos\(x \neq 0\). Decimos que\(Y\) es la raíz cuadrada de una matriz semi-definida positiva hermitiana si\(Y^{\prime}Y = A\). Demostrar que\(Y\) siempre existe y se puede construir a partir de la SVD de\(A\).

Ejercicio 5.5

Dejar\(A\) y\(B\) tener dimensiones compatibles. Demuestre que si

\ [$\ |A x\ |_ {2}\ leq\ |B x\ |_ {2} $
para todos los $x$\ nonumber\]

entonces existe una matriz\(Y\) con\(\|Y\|_{2} \leq 1\) tal que

\[A=YB\nonumber\]

Asumir\(B\) tiene rango completo a la simplicidad.

Ejercicio 5.6

(a) Supongamos

\ [\ left\ |\ left (\ begin {array} {cc}
X\\
A
\ end {array}\ right)\ right\ |\ leq\ gamma\ nonumber\]

Demostrar que existe una matriz\(Y\) con\(\|Y\|_{2} \leq 1\) tal que

\[X=Y\left(\gamma^{2} I-A^{\prime} A\right)^{\frac{1}{2}}\nonumber\]

(b) Supongamos

\ [\ left\ |\ left (\ begin {array} {cc}
X & A\\ end {array}\ right)\ right\ |\ leq\ gamma\ nonumber\]

Demostrar que existe una matriz\(Z\) con\(\|Z\| \leq 1\) tal que\(X = (\gamma^{2}I - AA^{*})^{\frac{1}{2}}Z\)

Ejercicio 5.7 Dilatación Matricial

Los problemas anteriores nos pueden ayudar a probar el siguiente resultado importante:

\ [\ gamma_ {0} :=\ min _ {X}\ izquierda\ |\ izquierda (\ begin {array} {cc}
X & B\\
C & A
\ end {array}\ right)\ right\ |=\ max\ left\ {\ |\ left (\ begin {array} {cc}
C &\ izquierda.a)\ |,\ |\ left (\ begin {array} {c}
B\\
A
\ final {matriz}\ derecha)\ |\ derecha\}
\ end {array}\ right. \ derecho. \ nonumber\]

Esto se conoce como el teorema de dilatación matricial. Observe que el lado izquierdo siempre es mayor o igual que el lado derecho independientemente de la elección de\(X\). A continuación, esbozamos los pasos necesarios para demostrar que este límite inferior es apretado. Las dilataciones matriciales juegan un papel importante en la teoría de sistemas particularmente en los problemas de reducción de modelos.

1. Dejar que\(\gamma_{1}\) se defina como

\ [\ gamma_ {1} =\ max\ left\ {\ left\ |\ left (\ begin {array} {ll}
C & A
\ end {array}\ right)\ right\ |,\ left\ |\ left (\ begin {array} {l}
B\\
A
\ end {array}\ right)\ right\ |\ right\}\ nonumber\]

Demostrar que:

\[\gamma_{0} \geq \gamma_{1}\nonumber\]

2. Utilice el ejercicio anterior para demostrar que existen dos matrices\(Y\) y\(Z\) con normas menores o iguales a una tal que

\[B=Y\left(\gamma_{1}^{2} I-A^{*} A\right)^{\frac{1}{2}}, \quad C=\left(\gamma_{1}^{2} I-A A^{*}\right)^{\frac{1}{2}} Z\nonumber\]

3. Definir una solución candidata a ser\(\tilde{X}=-Y A^{*} Z\). Mostrar por sustitución directa que

\ [\ begin {aligned}
\ left.\ |\ begin {array} {cc}
\ tilde {X} & B\\
C & A
\ end {array}\ right)\ | &=\ left\ |\ left (\ begin {array} {cc}
-Y A^ {*} Z & Y\ left (\ gamma_ {1} ^ {2} I-A^ {*} A\ derecha) ^ {\ frac {1} {2}}\
C=\ izquierda (\ gamma_ { 1} ^ {2} I-A A ^ {*}\ derecha) ^ {\ frac {1} {2}} Z & A
\ end {array}\ derecha)\ derecha\ |\
&=\ izquierda\ |\ izquierda (\ begin {array} {cc}
Y & 0\\
0 & I
\ end {array}\ derecha)\ left (\ begin {array} * {cc}
-A^ {} &\ left (\ gamma_ {1} ^ {2} I-A^ {*} A\ derecha) ^ {\ frac {1} {2}}\
C=\ izquierda (\ gamma_ {1} ^ {2} I-A A ^ {*}\ derecha) ^ {\ frac {1} {2}} & A
\ end {array}\ derecha)\ left (\ begin {array} {cc}
Z & 0\\
0 & I
\ end {array}\ right)\ derecha\ |
\ final {alineado}\ nonumber\]

4. Demostrar que

\ [\ left\ |\ left (\ begin {array} {cc}
\ tilde {X} & B\\
C & A
\ end {array}\ right)\ right\ |\ leq\ gamma_ {1}\ nonumber\]

Esto implica aquello\(\gamma_{0} \leq \gamma_{1}\) que prueba la aseveración.

Ejercicio 5.8

Demostrar o desmentir (a través de un contraejemplo) las siguientes desigualdades de valores singulares.

1. \(\sigma_{\min }(A+B) \leq \sigma_{\min }(A)+\sigma_{\min }(B)\)para cualquier\(A\) y\(B\).
2. \(\sigma_{\min }(A+E) \leq \sigma_{\max }(E)\)siempre que\(A\) no tenga rango de columna, y\(E\) es cualquier matriz.
3. \(\sigma_{\max }(A) <1\), luego\[\sigma_{m a x}(I-A)^{-1} \leq \frac{1}{1-\sigma_{\max }(A)}\nonumber\]
4. \(\sigma_{i }(I + A) \leq \sigma_{i}(A)+1\).