Clase 17: Condicionamiento¶

Bibliografía de la Clase:

Numerical Linear Algebra.L.N. Trefethen. Part III: Lecture 12 Conditioning and Condition Numbers

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.

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}$ .

Nota

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:

$\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

$\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$ :

$\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:

$\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:

$x= A^{-1} A x\\ \| x \| \leq \| A^{-1} \| \| A x \|$

de esta manera podemos reescribir $\kappa$ como:

$\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$ .

$\alpha = \frac{\| x \|}{\| A^{-1} \| \| Ax \|}$

finalmente decirmos que $\kappa=\| A \| \| A^{-1} \|$ .

Nota

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:

$\kappa=\| A \| \| A^{\dagger} \|$

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:

$(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:

$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:

$\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

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}$ .

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$ ..

Contenidos

Tema anterior

Próximo tema

Esta página

Clase 17: Condicionamiento¶

Números de condición¶

Número de condición de una matriz¶

Condicionamiento de la multiplicación matriz-vector¶

Caso especial: A es invertible¶

Condicionamiento de un sistema de ecuaciones¶

Navegación

Contenidos

Tema anterior

Próximo tema

Esta página

Búsqueda rápida

Clase 17: Condicionamiento¶

Números de condición¶

Número de condición de una matriz¶

Condicionamiento de la multiplicación matriz-vector¶

Caso especial: A es invertible¶

Condicionamiento de un sistema de ecuaciones¶

Navegación