************************************************************** Clase 17: Condicionamiento ************************************************************** **Bibliografía de la Clase:** * Numerical Linear Algebra.L.N. Trefethen. Part III: Lecture 12 ``Conditioning and Condition Numbers`` .. topic:: Condicionamiento Es la sensibilidad o perturbación de un **problema** matemático que puede verse como una función `f: X \to Y`, donde `f(x)` es una instancia del problema. .. topic:: Estabilidad Se refiere a la sensibilidad o perturbación de un **algoritmo** para resolver un problema. Un problema se dice **bien condicionado** si pequeñas perturbaciones de `x` conllevan a pequeños cambios en `f(x)`, de lo contrario se dice **mal condicionado**. Números de condición #################### Para cuantificar el tamaño de una perturbación pequeña en `x` denominada `\delta x` de un problema se utilizan los números de condición. Se define `\delta f = f(x+\delta x) - f(x)` como el efecto de `\delta x` en la función `f`. Existen dos números de condición: * **Número de condición absoluto** teniendo en cuenta que `\delta x` y `\delta f` son infinitesimales: `\hat{\kappa}=\sup_{\delta x}\frac{\| \delta f \|}{\| \delta x \|}` Si la función `f` es diferenciable, podemos evaluar `\hat{\kappa}` obteniendo las derivadas parciales de `f`, en este caso puede definirse `\delta f \approx J(x) \delta x` y `\hat{\kappa}= \| J(x) \|` donde la norma es inducida sobre `X` y `Y`. * **Número de condición relativo** se usa cuando interesan los cambios relativos. `\kappa = \sup_{\delta x} \big( \frac{\| \delta f \|}{\| f(x) \|} \big/ \frac{\| \delta x \|}{\| x \|} \big)` `\kappa = \frac{\| J(x) \| \| x \| }{\| f(x)\||}` Debido a que los computadores introducen errores relativos, `\kappa` es más usado en la práctica que `\hat{\kappa}`. .. note:: El Jacobiano es una matriz que contiene todas las derivadas parciales de primer orden de una función `f`. `J(x)=\begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \dots & \frac{\partial f_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1} & \cdots & \frac{\partial f_n}{\partial x_n} \end{bmatrix}` **Ejemplos** Encuentre el número de condición relativo para los siguientes problemas: * `f(x)=x^2 - 2x +1` * `f(x) = x_1- x_2` donde `x=[x_1,x_2]^T`. * Búsqueda de raíces para los polinomios de Wilkinson * Cálculo de valores propios en matrices no simétricas Número de condición de una matriz ################################# Se le denomina `\kappa(A)` al número de condición de la matriz A, donde: .. math:: \kappa(A)=\| A \| \| A^{-1} \|, donde `\| \cdot \|` es una norma matricial. Si `\kappa(A)` es grande (ej: `\kappa(A)>10^6`) se dice que `A` es una matriz **mal condicionada**. Se dirá que `A` está **bien condicionada** en el caso contrario. Condicionamiento de la multiplicación matriz-vector ################################################### El problema es entonces `f: x \to Ax` y la perturbacion `\delta x`. La perturbación de `f` sería entonces .. math:: \delta f = A(x+\delta x) - Ax \\ \delta f = A \delta x Con esta información, podemos encontrar el número de condición relativo del problema `f`: .. math:: \kappa = \sup_{\delta x} \big( \frac{\| \delta f \|}{\| f(x) \|} \big/ \frac{\| \delta x \|}{\| x \|} \big)\\ \kappa = \sup_{\delta x} \big( \frac{\| A \delta x \|}{\| Ax \|} \big/ \frac{\| \delta x \|}{\| x \|} \big) pero sabemos que `\|A \| = \sup_{\delta x} \frac{\| A \delta x \|}{\| \delta x \|}` que es la definición de la norma inducida de una matriz. Entonces se tiene que: .. math:: \kappa = \|A \| \frac{\| x \|}{\| Ax \|} Caso especial: A es invertible ============================== El número de condición relativo `\kappa` se simplifica cuando `A` es invertible ya que se cumple que: .. math:: x= A^{-1} A x\\ \| x \| \leq \| A^{-1} \| \| A x \| de esta manera podemos reescribir `\kappa` como: .. math:: \kappa = \|A \| \frac{\| x \|}{\| Ax \|} \\ \kappa \leq \| A \| \| A^{-1} \| \\ \kappa = \alpha \| A \| \| A^{-1} \| \\ donde `x` puede elegirse convenientemente de manera que `\alpha` sea igual a `1`. .. math:: \alpha = \frac{\| x \|}{\| A^{-1} \| \| Ax \|} finalmente decirmos que `\kappa=\| A \| \| A^{-1} \|`. .. note:: El caso de matrices cuadradas de `m \times m \quad`, `\|A\|_2 = \sigma_1` y `\|A^{-1}\|_2 = \frac{1}{\sigma_m}`. Por lo tanto `\kappa = \frac{\sigma_1}{\sigma_m}`. Si `A` no es invertible el procedimiento es análogo, pero ahora usando la pseudoinversa: .. math:: \kappa=\| A \| \| A^{\dagger} \| .. topic:: Perturbación en `b` Ahora el problema es el cálculo de `x` dado `b`, es decir: `f: b \to A^{-1} b` donde su número de condición cuando perturbamos `b` (no `x` como en el caso anterior) se obtiene de manera análoga y es también `\kappa=\| A \| \| A^{-1} \|`. Condicionamiento de un sistema de ecuaciones ############################################ En el caso anterior analizamos el efecto de perturbar `x` o `b` separadamente. Ahora se analizará el efecto de perturbar `A` en `x` manteniendo `b` fijo: .. math:: (A + \delta A) (x + \delta x) = b \\ Ax + A \delta x + x \delta A + \delta A \delta x = b, \\ considerando que `\delta A \delta x \approx 0` se tiene: .. math:: b + A \delta x + x \delta A = b \\ A \delta x + x \delta A = 0 \\ \delta x = -A^{-1} \delta A x \\ \| \delta x \| \leq \| A^{-1} \| \| \delta A \| \| x\| \\ Entonces el cálculo del número de condición relativo es: .. math:: \kappa = \sup_{\delta x} \big( \frac{\| \delta x \|}{\| x \|} \big/ \frac{\| \delta A \|}{\| A \|} \big) \\ \kappa = \sup_{\delta x} \big( \frac{\| A^{-1} \| \| \delta A \| \| x\| }{\| x \|} \big/ \frac{\| \delta A \|}{\| A \|} \big) \\ \kappa = \| A \| \| A^{-1} \| **Ejercicio propuesto** 1. Sea `A \in M(202 \times 202,\mathbb{R})` con `\|A\| _{2}=100` y `\|A\| _{F}=101`. Determine una cota mínima para el número de condición `\kappa(A)` definido en `\| . \| _{2}`. 2. Dada la matriz `A=\begin{bmatrix} 1 & \beta \\ \alpha & 1 \end{bmatrix}` determine los números de condición relativos `\kappa_\alpha` y `\kappa_\beta` para el cálculo de los valores propios de `A`..