Número de condición por norma vs número de condición por componente
Estoy revisando mis notas de clase para una clase de álgebra lineal numérica y hay algunas cosas en el capítulo que cubren los números de condición que no entendí del todo.
Se introducen dos tipos de números de condición, el primero viene dado por
$\kappa_{1}({f(\boldsymbol{x})} ; \boldsymbol{x})=\frac{\|\boldsymbol{J}(\boldsymbol{x})\|}{\|\boldsymbol{f}(\boldsymbol{x})\| /\|\boldsymbol{x}\|}$
y el segundo es
$\kappa_{2}(f(\boldsymbol{x}) ; \boldsymbol{x}) =\frac{\left|\boldsymbol{J}^{\mathrm{T}}(\boldsymbol{x})\right||\boldsymbol{x}|}{|f(\boldsymbol{x})|}$ .
Mi primera pregunta es, ¿cuál es la diferencia entre los dos? Dice que podemos emplear el segundo número de condición cuando el primero proporciona un resultado "pesimista", pero esto me parece muy arbitrario.
Luego se deriva que el segundo número de condición puede estar acotado por el primero si se usa la norma infinita y la salida $f$se supone que es escalar. Para la derivación utilizaron la siguiente ecuación
$\kappa_{1, \infty}(f ; \boldsymbol{x})=\frac{\left\|\boldsymbol{J}^{\mathrm{T}}(\boldsymbol{x})\right\|_{\infty}\|\boldsymbol{x}\|_{\infty}}{|f(\boldsymbol{x})|}$.
Debido a que se usó la transposición de la matriz jacobiana y $J^T$ es un vector de fila que se puede escribir como $\left\|\boldsymbol{J}^{\mathrm{T}}(\boldsymbol{x})\right\|_{\infty}=\|\boldsymbol{J}(\boldsymbol{x})\|_{1}=\sum_{i=1}^{m}\left|[\boldsymbol{J}(\boldsymbol{x})]_{i}\right|$. No entendí por qué usamos la transposición de$J$. ¿Es posible hacer lo mismo con$x$ ¿O tenemos que llevar la norma del infinito ahí?
Respuestas
Sus definiciones de los dos números de condiciones parecen ser inconsistentes entre sí. Un ligero escollo es que diferentes autores definen el jacobiano de manera diferente. Algunos usan (A)$J_{ij} = \partial f_i / \partial x_j$ y otros usan (B) $J_{ij} = \partial f_j / \partial x_i$. Con la primera definición, tenemos que$f(x+\Delta x) = f(x) + J(x) \Delta x + O(\|\Delta x\|^2)$ y con el segundo obtenemos $f(x+\Delta x) = f(x) + J^\top(x) \Delta x + O(\|\Delta x\|^2)$. La primera definición parece usar la definición (A) del jacobiano y la segunda definición definitivamente requiere que uno use la definición (B) para el producto$|J^\top(x)||x|$estar bien definido. En el caso de que la norma$\|\cdot\|$ es invariante a la transposición $\|A\| = \|A^\top\|$no importa qué definición uses. Hay suficientes consistencias de notación entre diferentes autores que me resulta difícil eliminar la ambigüedad de lo que está sucediendo aquí. Revisé libros populares de álgebra lineal numérica (Golub y Van Loan, Trefethen y Bau, Demmel, Higham) y no pude encontrar ningún otro que usara explícitamente este conjunto particular de definiciones. Quizás si pudiera encontrar otra fuente con este conjunto de definiciones, yo (o alguien más) podría ayudar más.
Permítanme abordar ahora su pregunta principal. Supongamos que quiero resolver el sistema diagonal de ecuaciones lineales
\ begin {ecuación} \ underbrace {\ begin {bmatrix} a & 0 \\ 0 & b \ end {bmatrix}} _ {= A} \ begin {bmatrix} x \\ y \ end {bmatrix} = \ begin { bmatrix} 1 \\ 1 \ end {bmatrix}. \ end {ecuación}
Esto corresponde a la función $f(a,b) = (a^{-1},b^{-1})$ con jacobiano
$$ J(a,b) = -\begin{bmatrix} a^{-2} & 0 \\ 0 & b^{-2} \end{bmatrix} $$
que tiene norma $\|J(a,b)\| = \max(a^{-2},b^{-2})$ en el operador $\infty$-norma. Asumamos en el futuro que$a > b > 0$ entonces $\|J(a,b)\| = b^{-2}$. El primer número de condición es entonces
$$ \kappa_1(f(a,b);(a,b)) = \frac{\|J(a,b)\|}{\|f(a,b)\|/\|(a,b)\|} = \frac{b^{-2}}{b^{-1}/ a} = \frac{a}{b}. $$
Así que si $a\gg b$, este problema está muy mal condicionado. Ahora, veamos el número de condición por componentes
$$ \kappa_2(f(a,b);(a,b)) = \frac{\begin{bmatrix} a^{-2} & 0 \\ 0 & b^{-2} \end{bmatrix}\begin{bmatrix}a\\ b\end{bmatrix}}{\begin{bmatrix} a^{-1} \\ b^{-1}\end{bmatrix}} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}. $$
No he visto esta definición que ha dado usando la división de vectores por elementos, y creo que el número de condición por componentes canónicos sería una norma de este "número de condición por vector". (por ejemplo, utilizando el$\infty$-norma, $\kappa_2(f(a,b);(a,b)) = 1$.) Usando el número de condición de componente, ¡el problema parece perfectamente bien condicionado! ¿Que esta pasando aqui?
El número de condición estándar de vainilla mide aproximadamente cuánto esperamos el error relativo entre $f(x+\Delta x)$ y $f(x)$ para ser comparado con el error relativo entre $x$ y $x+\Delta x$. Específicamente,
$$ \mbox{relative error in $F$} \le \kappa \cdot (\mbox{relative error in $X$}) + \mbox{higher order terms}. $$
Si decimos $(a+\Delta a, b+\Delta b)$ tiene un error relativo, digamos, $10^{-6}$ en el $\infty$-norm comparado con el valor real $(a,b)$ esto significa que los errores $\Delta a$ y $\Delta b$ en cada componente son menos de $10^{-6}\|(a,b)\| = 10^{-6}a$. Tenga en cuenta que si$a$ Es mas que $10^6b$, entonces esto significa el error $\Delta b$ puede ser más grande que $b$¡sí mismo! Pero cuando realmente evaluamos$f$, $a^{-1}$ es mucho más pequeño que $b^{-1}$ pero $b$ ha sido perturbado por un gran error $\Delta b$ y así el error relativo en $f$ (dominado en gran medida por el error relativo de $b^{-1}$es muy alto. En efecto, si se considera el error relativo de las normas, el error relativo de los componentes pequeños de un vector puede ser muy grande y estos errores de los componentes grandes pueden amplificarse si$f$ depende de las pequeñas entradas de su entrada.
En muchos entornos prácticos, tenemos un vector de entrada para el cual cada componente tiene un pequeño error relativo. Por ejemplo, si los errores$\Delta a$ y $\Delta b$ son el resultado de aproximar números reales arbitrarios $a$ y $b$ por números de coma flotante, tenemos que $|\Delta a| \le \epsilon |a|$ y $|\Delta b| \le \epsilon |b|$ por una pequeña constante $\epsilon$. Por lo tanto, este escenario del peor de los casos en el último caso es imposible, pero no hay forma de probar que usar normas como, si solo asumimos,$\|(\Delta a, \Delta b)\| \le \epsilon \|(a,b)\|$, no hay forma de mostrar $\Delta b$ es pequeño en relación con $b$. Los números de condición de componentes hacen exactamente esto. Le permiten medir el condicionamiento de un problema en relación con pequeñas perturbaciones de componentes en la entrada, lo que permite un control mucho mejor sobre el error relativo en valores pequeños en el vector de entrada.
Al final del día, todavía tengo que decir la línea "podemos emplear el segundo número de condición cuando el primero proporciona un resultado 'pesimista'" porque no hay una heurística general para mostrar definitivamente cuándo el condicionamiento por componentes será o ganó No da un límite de error sustancialmente mejor. Sin embargo, espero que el ejemplo que he dado sea una ilustración reveladora de cómo el condicionamiento por normas puede dar límites de error engañosamente pesimistas para un problema y cómo el condicionamiento por componentes puede dar límites más realistas.
La expresión para $\kappa_2$ no tiene sentido a menos que $f(x)$es un escalar. Las expresiones dadas para$\kappa_1$ y $\kappa_2$ no son definiciones, sino teoremas.
En esta respuesta, definiré rigurosamente el número de condición relativa por norma y el número de condición relativa del componente. Esto debería aclarar sus diferencias.
Dejar $\Omega \subseteq \mathbb{R}^n$ ser un conjunto abierto, deja $f : \Omega \rightarrow \mathbb{R}^m$ y deja $x \in \Omega$. Si$x \not = 0$ y si $f(x) \not = 0$, luego el número de condición relativa normwise $\kappa_f^{nr}$se define como sigue. Primero definimos una función auxiliar \ begin {ecuación} \ kappa_f ^ {nr} (x, \ delta) = \ sup \ left \ {\ frac {\ | f (x) -f (y) \ |} {\ | f (x) \ |} \ grande / \ frac {\ | xy \ |} {\ | x \ |} \:: \: 0 <\ | xy \ | <\ delta \ | x \ | \derecho \}. \ end {ecuación} donde$\delta > 0$ es cualquier número tal que $$ \{ y \in \mathbb{R}^n \: : \: \|x\| < \delta \|x\|) \subseteq \Omega. $$ Está claro que la función $\delta \rightarrow \kappa_f^{nr}(x,\delta)$es no negativo y no decreciente. De ello se deduce que el límite$$ \underset{\delta \rightarrow 0_.}{\lim} \kappa_f^{nr}(x,\delta) $$existe. Esto nos permite definir el número de condición relativa normativo$\kappa_f^{nr}$ como sigue $$ \kappa_f^{nr}(x) = \underset{\delta \rightarrow 0_+}{\lim} \kappa_f^{nr}(x,\delta).$$
El número de condición relativa por norma impone un límite estricto al error relativo por norma que se puede lograr. Si$y \in \Omega$ satisface $\|x-y\| \leq \delta \|x\|$, luego $$ \frac{\|f(x)-f(y)\|}{\|f(x)\|} = \left(\frac{\|f(x)-f(y)\|}{\|f(x)\|} \big/ \frac{\|x-y\|}{\|x\|}\right) \frac{\|x-y\|}{\|x\|} \leq \kappa_f^{nr}(x,\delta) \frac{\|x-y\|}{\|x\|} $$ Además, si $\delta$ es suficientemente pequeño, entonces $$ \kappa_f^{nr}(x,\delta) \approx \kappa_f^{nr}(x) $$es una buena aproximación. De ello se deduce que no podemos esperar un error relativo normativo que sea menor que$$ \frac{\|f(x)-f(y)\|}{\|f(x)\|} \approx \kappa_f^{nr}(x,\delta) \frac{\|x-y\|}{\|x\|}. $$A partir de esta definición es posible probar el siguiente resultado. Si$f : \Omega \rightarrow \mathbb{R}^m$también es diferenciable en el punto$x \in \Omega$, luego $$ \kappa_f^{nr}(x) = \frac{\|Df(x)\|\|x\|}{\|f(x)\|} $$ dónde $Df(x) \in \mathbb{R}^{m \times n}$ es el jacobiano de $f$ en el punto $x$. Para ser claro, si$A = Df(x)$ es el jacobiano de $f$ a $x$, luego $a_{ij} = \frac{\partial f_i}{\partial x_j}(x)$.
Ahora, para definir el número de condición relativa por componentes, primero definimos el error relativo por componentes. Dejar$x \in \mathbb{R}^n$ denotar el valor objetivo y dejar $y \in \mathbb{R}^n$denotar la aproximación. Entonces, el error relativo por componentes viene dado por \ begin {ecuación} \ rho (x, y) = \ max \ left \ {\ frac {| x_j - y_j |} {| x_j |} \:: \: j = 1, 2, \ dotsc, n \ right \}, \ end {ecuación} donde ampliamos la definición habitual de fracciones para incluir \ begin {ecuación} \ frac {a} {b} = \ begin {cases} 0 & a = 0 \ wedge b = 0, \\ \ infty & a> 0 \ wedge b = 0. \ end {cases} \ end {ecuación} Ahora vamos$x \in \Omega$ ser un punto tal que $x_j \not = 0$ para todos $j$ y $f_i(x) \not = 0$ para todos $i$. Empezamos definiendo una función auxiliar$\kappa_f^{cr}$ dada por $$ \kappa_f^{cr}(x,\delta) = \sup \left\{ \frac{\rho(f(x),f(y))}{\rho(x,y)} \: : \: 0 < \rho(x,y) < \delta \right\}. $$ Está claro que $\delta \rightarrow \kappa_f^{cr}(x,\delta)$es una función no negativa y no decreciente. De ello se deduce que el límite$$ \underset{\delta \rightarrow 0_+}{\lim} \kappa_f^{cr}(x,\delta) $$existe y no es negativo. Esto nos permite definir el número de condición relativa por componentes de$f$ como sigue $$ \kappa_f^{cr}(x) = \underset{\delta \rightarrow 0_+}{\lim} \kappa_f^{cr}(x,\delta). $$El número de condición relativa por componentes impone un límite estricto a la precisión por componentes que se puede lograr. Si$y \in \Omega$ es tal que $0 < \rho(x,y) < \delta$, luego $$ \rho(f(x),f(y)) = \left(\frac{\rho(f(x),f(y))}{\rho(x,y)}\right) \rho(x,y)\leq \kappa_f^{cr}(x,\delta) \rho(x,y). $$ Además, si $\delta$ es suficientemente pequeño, entonces $$ \kappa_f^{cr}(x,\delta) \approx \kappa_f{cr}(x) $$es una buena aproximación. De ello se deduce que no podemos esperar un error relativo por componentes que sea menor que$$ \rho(f(x),f(y)) \approx \kappa_f^{cr}(x,\delta) \rho(x,y). $$De la definición es posible probar el siguiente resultado. Si$f$también es diferenciable en$x \in \Omega$, luego $$ \kappa_f^{cr}(x) = \left \|\frac{|Df(x)||x|}{|f(x)|} \right\|_\infty. $$Aquí es vital apreciar el hecho de que la división en el lado derecho es por componentes cuando$f$ es una función vectorial.
Está claro que los dos números de condición miden la sensibilidad de $f$a pequeños cambios en la entrada, pero se basan en diferentes definiciones de "pequeño". Si$f$ es también función escalar, es decir, si $m = 1$, entonces tenemos $$ \kappa_f^{cr}(x) = \left \|\frac{|Df(x)||x|}{|f(x)|} \right\|_\infty = \frac{\||Df(x)||x|\|_\infty}{|f(x)|} \leq \frac{\||Df(x)|\|_\infty\||x|\|_\infty}{\|f(x)\|_\infty} = \frac{\|Df(x)\|_\infty\|x\|_\infty}{\|f(x)\|_\infty} =\kappa_f^{nr}(x). $$En este caso, vemos que el número de condición relativa por norma es siempre mayor que el número de condición por componente. Sin embargo, creo que es un poco engañoso afirmar que el número de condición relativa por norma más es pesimista que el número de condición por componente, simplemente porque utilizan una definición diferente de "pequeño".
Se puede evitar mucha confusión indicando siempre claramente el dominio y el codominio de la función en cuestión. De hecho, una función es realmente un triple $(f,U,V)$ que consta de un dominio $U$, un co-dominio $V$ y una regla $f$ para asignar un elemento exacto en el dominio $U$ exactamente un elemento en el co-dominio $V$. Desafortunadamente, la notación establecida tiende a enfocarse solo en la regla $f$.
La definición del número de condición relativa por componentes utilizada aquí se extrae del artículo "Números de condición mixtos, por componentes y estructurados" de Gohberg y Koltracht, SIAM J. Matrix Anal. Appl., 14 (3), página (s) 688–704, 1993.