¿Por qué el Operador de la Norma tan duro para calcular?

Question

Recientemente tomé un mejor vistazo al operador de la norma definida en una matriz de $\mathbf A \in \Bbb{K}^{n\times n}$ como sigue:

$$ \|\mathbf Un\|_p=\sup\{\|\mathbf Ax\|_p \mid x\in\Bbb{K}^n\tierra\|x\|=1\} $$

La primera vez que veía esto pensé "ok, vamos a calcular para un par de ejemplo de las matrices". Empecé con $n = 3$$p = 2$, sólo el comienzo "simple". Vamos $$ \mathbf A = \left[\begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33}\end{de la matriz}\right]\quad a_{ij}\in\Bbb{K}^n $$ Ahora si vamos a minimizar $\|\mathbf Ax\|_2$ ($ = \|\mathbf Ax\|$), podríamos hacerlo fácil en nosotros mismos y sólo minimizar $\|\mathbf Ax\|^2$ así que como para no preocuparse de que molesto radical. Tenemos $$ \begin{align} \|\mathbf Ax\|^2 & = (a_{11}x_1 + a_{12}x_2 + a_{13}x_3)^2 + (a_{21}x_1 + a_{22}x_2 + a_{23}x_3)^2 + (a_{31}x_1 + a_{32}x_2 + a_{33}x_3)^2 \\ & = Ax_1^2 + Bx_2^2 + Cx_3^2 + Dx_1x_2 + Ex_1x_3 + Fx_2x_3 \end{align} $$ donde $$ \begin{align} A & = a_{11}^2+a_{21}^2+a_{31}^2 \\ B & = a_{12}^2+a_{22}^2+a_{32}^2 \\ C & = a_{13}^2+a_{23}^2+a_{33}^2 \\ D & = 2(a_{11}a_{12} + a_{21}a_{22} + a_{31}a_{33}) \\ E & = 2(a_{11}a_{13} + a_{21}a_{23} + a_{31}a_{33}) \\ F & = 2(a_{12}a_{13} + a_{22}a_{23} + a_{32}a_{33}) \end{align} $$ Ahora vamos a definir $$ G(x_1,\ x_2,\ x_3) = Ax_1^2+Bx_2^2+Cx_3^2+Dx_1x_2+Ex_1x_3+Fx_2x_3 $$ Así que, si queremos minimizar $||\mathbf Ax||^2$, estamos bien vamos a tener que minimizar $$ N(x_1,\ x_2,\ x_3) = \frac{G(x_1,\ x_2,\ x_3)}{x_1^2+x_2^2+x_3^2} $$ o simplemente minimizar $G$ con la restricción $g(x_1,\ x_2,\ x_3) = x_1^2 + x_2^2 + x_3^2 = 1$. El último parecía más fácil para mí, así que me dio un tiro, el uso de multiplicadores de Lagrange.

Como de costumbre, me define $$ \mathcal{L}(x_1,\ x_2,\ x_3,\ \lambda) = G(x_1,\ x_2,\ x_3)-\lambda g(x_1,\ x_2,\ x_3) $$ la configuración es degradado a cero da $$ \nabla \mathcal L = 0 \implica \begin{cases} 2(A - \lambda)x_1 + Dx_2 + Ex_3 & = 0 \\ Dx_1 + 2(B - \lambda)x_2 + Fx_3 & = 0 \\ Ex_1 + Fx_2 + 2(C - \lambda)x_3 & = 0 \\ x_1^2 + x_2^2 + x_3^2 - 1 & = 0 \end{casos} $$ Ahora esto es donde realmente empecé a atascarse. Traté de resolver las tres primeras ecuaciones para $x_1,\ x_2,$ $x_3$ pero no acabar con cualquier cosa que podría utilizar. He intentado solucionar $x_1$ en términos de$x_2,\ x_3,$$\lambda$, $x_2$ en términos de$x_3$$\lambda$, y, a continuación, subbing que todos en la tercera ecuación, pero terminó con $x_3 = 0$ o $$ 4\lambda^3 - 4\lambda^2(a+B+C) + \lambda(4AB+4AC+4AC-D2+E^2+B^2)-4ABC-AF^2-^2+CD^2+DEF = 0 $$ que, aunque técnicamente es solucionable por $\lambda$ a través de la ecuación cúbica, sería increíblemente desordenado.

Ahora, probablemente creado mi propio obstáculo para este problema, porque no quería pensar sobre el sistema de ecuaciones de manera lógica y sólo quería bash. A pesar de mi enfoque, parece que el operador de la norma es una cosa muy difícil de calcular, y que sólo se analizó el caso en que $n = 3$$p = 2$. ¿Y el caso general? Lo que si $n = 75$$p = 9/4$? Cómo en el mundo podría calcular, entonces?

Las preguntas son retóricas, sin embargo, y mi pregunta es la siguiente:

Por qué definir una norma ordinaria para matrices que es tan difícil de calcular en general?

Veo que el operador de la norma en todas partes, y parece que la norma estándar para una gran cantidad de teoremas (a menos que me equivoco y ||A|| a significa que cualquier norma de la matriz). Entonces, ¿por qué habríamos de definir una norma estándar en una manera que es muy difícil de calcular? ¿Cuál es el punto? Es fácil trabajar en teoremas? Me sale que es intuitivamente tiene sentido como una norma, pero que no puede ser fácil para trabajar, sobre todo en comparación a cosas como la norma de Frobenius.

Entonces, ¿por qué nos preocupamos de esta definición?

Answer 1

En primer lugar, como otros han mencionado, el operador de la norma tiene muchas buenas propiedades que la hacen conveniente para el uso en pruebas (básicamente el hecho de que, por definición, satisface $\| Ax \| \le \| A \| \|x \|$). Usted podría, por ejemplo, terminar con los factores del operador de la norma en varios límites; incluso si usted no puede calcular el operador de la norma, si usted puede superior o límite inferior, según proceda, a continuación, usted todavía puede extraer información de estos límites. Para ver realmente el operador de la norma en la acción que usted puede intentar aprender algunos análisis funcional; lo que realmente empieza a ser útil en el infinito-dimensional de configuración.

Segundo, he aquí cómo calcular el operador de la norma (edit: al $p=2$). Permítanme asumir que $A$ es real por la sencillez, aunque no importa mucho. Desea maximizar $\langle Ax, Ax \rangle$ $x$ rangos de todos los vectores unitarios. Esto es equivalente a la maximización de la

$$\langle A^T A x, x \rangle.$$

Ahora, a diferencia de $A$, la matriz $A^T A$ es simétrica, y por tanto, por el teorema espectral tiene una base ortonormales de vectores propios. Estos son el derecho vectores singulares $r_i$ $A$ , y los correspondientes valores propios son las plazas $\sigma_i^2$ de los valores singulares de a $A$ (hasta la aparición de algunos ceros, que no importa para este cálculo). Si escribimos $x$ en esta base como

$$x = \sum x_i r_i$$

tenemos que

$$\langle Ax, Ax \rangle = \sum \sigma_i^2 x_i^2$$

donde $\langle x, x \rangle = \sum x_i^2 = 1$. Esto es mucho más fácil problema de optimización! De ello se desprende que $\langle Ax, Ax \rangle$ se maximiza cuando se $x$ es igual a un derecho singular vector correspondiente a la de mayor valor singular $\sigma_1$, y que su valor máximo es $\sigma_1^2$. Por lo tanto $\sigma_1$ es el operador de la norma de $A$. Tenga en cuenta que si $A$ es normal que coincide con el valor absoluto de la mayor autovalor (en valor absoluto) de $A$.

El mayor valor singular se puede calcular de diversas maneras. Ver el artículo de Wikipedia sobre la descomposición de valor singular para más detalles.

Answer 2

El punto es: en matemática pura, que en su mayoría no se preocupan en realidad el cálculo de cosas ;)

Por supuesto, esto es (en parte) de una broma, pero la respuesta es que esta norma tiene un montón de buenas propiedades (ver análisis funcional), y te permite demostrar teoremas que va a hacer otros cálculos mucho más fácil. El problema es: si desea definir las cosas por lo que realmente funcionan para los teoremas (satisfacer algunas buenas universal de la propiedad, etc), que son a menudo muy difícil (si no imposible) para calcular en la práctica. Pero después de todo, la informática no es todo lo que usted quiera, si teoremas se las arreglan para hacer todo mucho más claro.

Answer 3

Un operador de la norma es mejor que una norma, es un álgebra de norma (no se si es el término correcto, en francés). El punto es que la norma satisface: $$\forall A,B,\|AB\|\leqslant\|A\|\times\|B\|.$$

Answer 4

Depende de la norma que usted toma, para empezar. Algunos matriz normas son difíciles de calcular, otros no lo son. En tu ejemplo, para $p=2$, la norma de la matriz $A\in \mathbb{K}^{n\times n}$ es la raíz cuadrada del máximo autovalor de a $A^* A$. Este cálculo no es demasiado difícil, incluso de grandes dimensiones, ya que este es un Hermitian, resp. simétrica autovalores del problema.

Del mismo modo, para $p=1$ $p=\infty$ la matriz norma ha expresiones simples, como la columna suma, resp. fila de la suma de la norma.

La razón técnica por el operador de las normas grande ha sido señalado en las respuestas anteriores. Submultiplicativity es muy útil para muchos tipos de estimaciones. Por ejemplo, se puede conseguir que la $\|A\| \geq r(A)$ donde $r(A)$ es el radio espectral de $\|A\|$. Y en la parte superior de que la famosa fórmula Gelfand $$ r(A) = \lim_{k\to \infty} \|A^k\|^{1/k} = \inf_{k\geq 1} \|A^k\|^{1/k},$$ que incluso tiene para delimitada lineal de operadores en espacios de Banach.

Answer 5

El operador de la norma de una matriz cuadrada $A$ es la raíz cuadrada de la magnitud de la mayor autovalor de a $A^T A$. Para ver esto, en primer lugar tenga en cuenta que $$\|A^T A\| = \sup\limits_{\|x\|=1} \| A^T A x \| = \sup\limits_{\|x\|=1} \sup\limits_{\|y\|=1} \langle A^T A x , y \rangle = \sup\limits_{\|x\|=1} \sup\limits_{\|y\|=1} \langle Ax , Ay \rangle$$ $$= \sup\limits_{\|x\|=1} \|Ax\|^2.$$ Por lo tanto $\|A^T A\| = \|A\|^2$. Ahora, con el hecho de que una matriz simétrica tiene un orthornomal base de vectores propios, no es difícil mostrar que para una matriz simétrica $S$, $\|S\|$ es el (valor absoluto) de la mayor autovalor de a $S$. Desde $A^T A$ es simétrica, esto completa la prueba.