el problema de m´ınimos cuadrados

Capıtulo 8

El Problema de MınimosCuadrados

8.1. El problema de mınimos cuadrados

El problema del ajuste de datos; es decir, descubrir una funcion matematica quepueda explicar de la mejor forma posible el comportamiento de algun mecanismo ogrupo de seres u objetos que puede ser medido, y del cual conocemos algunos datos(con sus posibles errores de medicion), es un problema clasico y ha supuesto un retopara la comunidad matematica desde su planteamiento por Gauss y Legendre hacia1800.

En lenguaje de algebra lineal consiste en encontrar la solucion de un sistema linealAx “ b siendo A P Cmˆn con m ě n. En A y b se recogen todos los datos delexperimento que se quieren ajustar. Enseguida veremos algunos ejemplos.

Sabemos que el sistema tiene solucion si y solo si b P ImA, condicion que difıcilmentese cumple si m es mucho mayor que n. Si m ą n diremos que el sistema Ax “ b esta

171

172 El Problema de Mınimos Cuadrados

sobredeterminado; y si no existe ningun x P Cnˆ1 tal que Ax “ b lo que se puedeintentar es buscar un x de forma que el vector

r “ Ax´ b P Cm,

que se llama residuo o vector residual, sea lo “mas pequeno” posible. Lo grandeo pequeno que sea r lo mediremos mediante una norma. El problema de mınimoscuadrados consiste en encontrar x P Cnˆ1 para que el vector residuo tenga la menornorma euclıdea posible. Su formulacion precisa serıa la siguiente:

Problema de mınimos cuadrados: Sea F “ R o C. Dada una matriz A P Fmˆny un vector b P Fm,(m ě n) encontrar x P Cnˆ1 para que }Ax´ b}2 sea mınimo.

La eleccion de la norma euclıdea se puede justificar desde varios puntos de vista:historico, geometrico, estadıstico, . . . ; pero sobre todo porque es la norma habitual,conduce a los algoritmos mas sencillos y ası como todas las normas son funcionescontinuas de los vectores, la norma euclıdea es, ademas, diferenciable. Como, poranadidura, la funcion }Ax ´ b}2 alcanza su maximo absoluto en un maximo local,este maximo puede calcularse igualando a cero las derivadas parciales de dicha fun-cion. Este proceso conduce a lo que se llaman las ecuaciones normales del problemade mınimos cuadrados. Estas ecuaciones nos las encontraremos mas adelante proce-dentes de un contexto completamente diferente.

Ejemplo 8.1 El ejemplo mas tıpico de ajuste de datos por mınimos cuadrados esel calculo del polinomio de interpolacion: dados m puntos del plano pxi, yiq,i “ 1, . . . ,m, de forma que xi ‰ xj para i ‰ j, se trata de encontrar un polinomiode grado a lo mas m ´ 1, ppxq “ a0 ` a1x ` ¨ ¨ ¨ ` am´1x

m´1, que pase por los npuntos.

Se trata, entonces, de encontrar los coeficientes a0, a1,. . . , am´1, para que

ppxiq “ yi, i “ 1, . . . ,m.

Esto equivale a resolver el sistema lineal

a0 ` a1xi ` ¨ ¨ ¨ ` am´1xm´1i “ yi, i “ 1, . . . ,m (8.1)

8.1 El problema de mınimos cuadrados 173

cuya matriz de coeficientes es

A “ “xj´1i

‰ “

»———–

1 x1 x21 ¨ ¨ ¨ xm´1

1

1 x2 x22 ¨ ¨ ¨ xm´1

2...

......

. . ....

1 xm x2m ¨ ¨ ¨ xm´1

m

fiffiffiffifl

Esta es una matriz de Vandermonde cuyo determinante es

detA “ź

iăjpxi ´ xjq.

Por consiguiente A es invertible y el sistema (8.1) tiene una unica solucion. En laFigura 8.1 se muestra la grafica del polinomio de interpolacion que pasa por los11 puntos pi, 0q con i “ ´5,´4, . . . ,´1, 0, 1, . . . , 4, 5. Se trata de un polinomio degrado 10. A su derecha se ha escrito el codigo de MATLAB que obtiene los co-eficientes del polinomio de interpolacion: c “ Azb y que da la grafica: plot(t,

polyval(p,t),a,b,’r*’,’markersize’,10);. El comando polyval(p,t) devuel-ve un vector: el valor del polinomio p en las componentes del vector t. Notese eluso de las sentencias fliplr y flipud para obtener la matriz de los coeficientesdel sistema y los coeficientes del polinomio de interpolacion en la forma apropia-da. La sentencia zeroaxes hace que los ejes cartesianos se dibujen en la forma quese acostumbra a utilizar en la pizarra: dos lıneas perpendiculares que se cortan enp0, 0q.

−6 −4 −2 2 4 6

−3

−2

−1

1

2

3

4

5 Figura 8.1:a=-5:5;

A=fliplr(vander(a));

b=[0 0 0 1 1 1 0 0 0 0 0]’;

c=Azb;p=flipud(c);

t=linspace(-5.05,5.05);

plot(t, polyval(p,t),a,b,’r*’,...;

’markersize’,10);

zeroaxes

Indudablemente el polinomio de interpolacion se ajusta perfectamente a los datos,pero a menudo estos proceden de experimentos y lo que se pretende es buscar una


curva que interprete los datos obtenidos. Como las mediciones se realizan en momen-tos puntuales, tal grafica deberıa reflejar, salvo que se tengan motivos para pensarlo contrario, una comportamiento suave entre dos datos consecutivos, y no la fluc-tuacion que muestra el polinomio de interpolacion de nuestro ejemplo. Quiza unpolinomio de menor grado pueda mostrar un mejor comportamiento. Tal polinomiono pasara por algunos de los puntos. Pero la medicion de todo proceso real conllevaerrores que podrıan explicar tal fenomeno.

Ejemplo 8.2 (Ajuste por mınimos cuadrados) Con los mismos datos del ejem-plo anterior calcular el polinomio de grado 7 que mejor se ajusta a los datos en elsentido de los mınimos cuadrados.

Siguiendo los mismos pasos que en el ejemplo anterior lo que buscamos es un poli-nomio de grado a lo mas n´ 1 ď m´ 1

ppxq “ a0 ` a1x` ¨ ¨ ¨ ` an´1xn´1

tal que }ppxq ´ y}2 sea mınimo. Aquı, ppxq es el vector cuya i-esima componente esppxiq y el vector y es el que tiene por i-esima componente yi.

Ahora bien, si

A “

»———–

1 x1 x21 ¨ ¨ ¨ xn´1

1

1 x2 x22 ¨ ¨ ¨ xn´1

2...

......

. . ....

1 xm x2m ¨ ¨ ¨ xn´1

m

fiffiffiffifl

es la matriz de Vandermonde truncada y c “ pa0, a1, . . . , an´1q es el vector de loscoeficientes de p tenemos que ppxq “ Ac. Ası que se trata de hallar un vector c enel que se alcance

mınxPCn }Ax´ y}2.

En la Figura 8.2 se presenta la grafica producida por MATLAB del polinomio degrado 7 que mejor se ajusta a los datos pai, biq en el sentido de los mınimos cuadrados.El problema de mınimos cuadrados correspondiente se calcula en el interior de lasentencia ployfit. El resto del codigo de MATLAB que se muestra es el mismo queen el apartado anterior.

Una observacion final antes de abordar la solucion del problema de mınimos cua-drados y los algoritmos correspondientes. Una variante del problema de encontrar

8.2 La solucion del problema de mınimos cuadrados 175

−6 −4 −2 2 4 6

−3

−2

−1

1

2

3

4

5 Figura 8.2:a=-5:5

A=fliplr(vander(a))

b=[0 0 0 1 1 1 0 0 0 0 0]’;

p=polyfit(a,b,7);

t=linspace(-5.3,5.3);

plot(t, polyval(p,t),a,b,’r*’,...

’markersize’,10);

axis([-6 6 -3 5]);

zeroaxes

el polinomio de grado a lo mas n´ 1 que mejor se ajusta a una nube de m puntos,pxi, yiq, distribuıdos en el plano es el de encontrar la funcion

φpxq “ c1φ1pxq ` c2φ2pxq ` ¨ ¨ ¨ ` cnφnpxq,

que mejor se ajusta a una de tales nubes de puntos. Aquı φ1, φ2,. . . , φn son funcionesdadas, o de las que uno sospecha que una combinacion lineal de ellas puede ajustarsebien a los datos. En este caso el problema se reduce a calcular el vector c donde sealcanza el mınimo:

mınxPC }Ax´ y}2,

siendo A P Fmˆn la matriz cuyo elemento en la posicion pi, jq es φjpxiq y siendo y elvector cuyas componetes son y1, . . . , ym.

8.2. La solucion del problema de mınimos cuadra-

dos

En esta seccion demostramos el resultado que nos da la solucion del problema demınimos cuadrados. Geometricamente la situacion es muy simple (vease la Figura8.3): el vector de ImA cuya distancia a b es mınima es la proyeccion ortogonal de bsobre ImA. Y la distancia mınima es la norma del residuo. Esto es lo que nos diceel siguiente Teorema.


b Im A

Ax0

r=Ax0−b

Figura 8.3: La solucion del problema de mınimos cuadrados

Teorema 8.3 Sean A P Fmˆn, F “ R o C, y b P Fmˆ1, m ě n. Sea PA la proyeccionortogonal sobre ImA. Entonces, Ax0 cumple

}Ax0 ´ b}2 “ mınxPFn }Ax´ b}2

si y solo si se cumple cualquiera de las siguientes condiciones que son equivalentes:

(i) Ax0 “ PAb.

(ii) b´ Ax0 P pImAqK.

(iii) A˚Ax0 “ A˚b.

Ademas, la solucion x0 es unica si y solo si rangA “ n.

En la demostracion se usa el teorema de Pitagoras: Si x, y P Cn son ortogonalesentonces }x` y}22 “ }x}22 ` }y}22. En efecto, }x` y}22 “ px` yq˚px` yq “ x˚x` y˚ `x˚y`y˚x “ x˚x`y˚y “ }x}22`}y}22, donde hemos usado que x˚y “ y˚x “ 0 porquex e y son ortogonales.

Demostracion.- Todo se basa en la demostracion de la idea geometrica expuestamas arriba:

mınxPCn }Ax´ b}2 “ }PAb´ b}2.

Vemaos que esto es ası. En efecto

}Ax´ b}22 “ }Ax´ PAb` PAb´ b}22 “ }Ax´ PAb}22 ` }PAb´ b}22

8.3 Algoritmos para calcular la solucion del problema de mınimos cuadrados 177

porque Ax´PAb P ImA y PAb´ b “ ´pI ´PAqb P pImAqK y aplicando el Teoremade Pitagoras. Por lo tanto, para todo x P Cn

}Ax´ b}2 ě }PAb´ b}2.Pero como PAb P ImA, existe x1 P Cn tal queAx1 “ PAb; i.e., }Ax1´b}2 “ }PAb´b}2.Por lo tanto mın

xPCn }Ax´ b}2 “ }PAb´ b}2, tal y como deseabamos mostrar.

Ahora, si Ax0 es el vector que hace mınima la distancia de Ax a b entonces

}PAb´ b}22 “ mınxPCn }Ax´ b}

22 “ }Ax0 ´ b}22 “ }Ax0 ´ PAb}22 ` }PAb´ b}22.

De aquı deducimos que }Ax0 ´ PAb}2 “ 0; es decir, Ax0 “ PAb.

Solo queda demostrar la equivalencia entre las tres condiciones. Por una parte

PAb “ Ax0 ñ b´ Ax0 “ b´ PAb “ pI ´ PAqb P pImAqK.Y si b´Ax0 P pImAqK entonces PApb´Ax0q “ 0 de modo que PAb “ PAAx0. Perocomo Ax0 P ImA tenemos que PAAx0 “ Ax0. Esto demuestra la equivalencia entrelas condiciones (i) y (ii).

Finalmente, como pImAqK “ KerA˚ tenemos que b ´ Ax0 P pImAqK si y solo siA˚pb´ Ax0q “ 0; i. e., A˚Ax0 “ A˚b.

Falta demostrar que la solucion del problema de mınimos cuadrados es unica si ysolo si rangA “ n. Ahora bien, rangA “ n si y solo si A˚A es invertible. Una formade ver esto es, por ejemplo, la siguiente: rangA “ n si y solo si σnpAq ‰ 0. Comolos valores singulares de A son las raıces cuadradas positivas de los valores propiosde A˚A, σn ‰ 0 si y solo si todos los valores propios de A˚A son distintos de cero;i.e. detpA˚Aq ‰ 0. Pero A˚A es invertible si y solo si el sistema A˚Ax “ A˚b tienesolucion unica.

8.3. Algoritmos para calcular la solucion del pro-

blema de mınimos cuadrados

El Teorema 8.3 nos da las claves para calcular un vector x0 que solucione el problemade mınimos cuadrados. En primer lugar, el sistema A˚Ax “ A˚b recibe el nombre de


ecuaciones normales del problema de mınimos cuadrados. Es el sistema que apareceal calcular el mınimo local de la funcion

fpxq “ }Ax´ b}2.Es decir, el sistema

BfBxi pxq “ 0, i “ 1, . . . , n

da lugar al sistema A˚Ax “ A˚b. Como la funcion f es convexa, alcanza su mınimoabsoluto en un mınimo local.

Para resolver el sistema A˚Ax “ A˚b numericamente, tendremos en cuenta la es-tructura especial de la matriz A˚A: es hermıtica (simetrica en el caso real). Ademases definida positiva porque x˚A˚Ax “ }Ax}2 ą 0 para x ‰ 0. Ahora bien todamatriz hermıtica definida positiva admite una factorizacion de Cholesky (variantede la factorizacion LU cuando la matriz es simetrica o hermıtica). En MATLABel comando chol(A) devuelve la factorizacion de Cholesky de A si esta es hermıti-ca definida positiva. Recordemos que una factorizacion de Cholesky de una matrizhermıtica definida positiva, A, es una factorizacion de la forma

A “ LL˚

siendo L una matriz triangular inferior. Esta factorizacion es especialmente apro-piada para resolver sistemas lineales mediante sustitucion hacia adelante y haciaatras.

Teniendo en cuenta todo esto podemos dar un primer algoritmo para la resoluciondel problema de mınimos cuadrados.

Algoritmo mınimos cuadrados via ecuaciones normales

Dada A P Fmˆn y dado b P Fm

1. Formense las matrices A˚A y A˚b.

2. Calculese la factorizacion de Cholesky de A˚A “ LL˚, (chol(A))

3. Resuelvase Ly “ A˚b (z o sustitucion hacia adelante)

4. Resuelvase L˚x “ y.(z o sustitucion hacia atras)


Cuando A es hermıtica definida positiva pero mal condicionada, el algoritmo deCholesky puede dar resultados muy inexactos. Por lo tanto, el algoritmo anteriorno es adecuado para resolver el problema de mınimos cuadrados. Una posibilidadserıa usar la factorizacion QR de A˚A para conseguir la factorizacion de Choleskyde A˚A en vez del algoritmo de Cholesky. En efecto, si A “ QR es la factorizacionQR reducida de A, entonces

A˚A “ R˚Q˚QR “ R˚R “ LL˚,

donde hemos utilizado que Q˚Q “ In, por tener Q columnas ortonormales, y hemospuesto L “ R˚. Esto nos muestra que si A es de rango completo, la factorizacion deCholesky de A˚A es unica. Esta alternativa, sin embargo, carece de sentido porquela ventaja del algoritmo de Choleski es que su coste es „ 1

n3 mientras que el de lafactorizacion QR es „ 2n2m ´ 2

3n3 ya que no se necesita el calculo de Q. Para m

grande en comparacion con n, usar la factorizacion de Cholesky es ventajoso cuandola matriz esta bien condicionada. Cuando no lo esta hay otras formas de resolverel problema de mınimos cuadrados que veremos a continuacion. En la primera deellas se trata de usar la factorizacion QR y resolver un sistema triangular superior.La idea es usar la segunda forma de obtener la solucion del problema de mınimoscuadrados que hemos visto en el Teorema 8.3: x0 es solucion del problema de mınimoscuadrados mın

xPFn }Ax´ b}2 si y s olo si Ax0 “ PAb.

Para calcular x0 debemos conseguir PA, que es la proyeccion ortogonal sobre ImA.Recordemos que PA “ QQ˚, donde Q es una matriz cuyas columnas son una baseortonormal de ImA. Recordemos que si A “ QR es una factorizacion QR reducidade A entonces las columnas de Q froman una base ortonormal de ImA y, por con-siguiente, QQ˚ es la proyeccion ortogonal sobre ImA. Ası pues, sustituyende A porQR y PA por QQ˚ ene Ax0 “ PAb obtenemos QRx0 “ QQ˚b. Como las columnasde Q son ortonornales Q˚Q “ In y la solucion del problema de mınimos cuadradoses x0 “ R´1pQ˚bq. El siguiente algoritmo implementa estas operaciones.

Algoritmo mınimos cuadrados via factorizacion QR


1. Hallese la factorizacion QR, reducida, de A

2. Calculese Q˚b.

3. Resuelvase Rx “ Q˚b (z o sustitucion hacia atras)


Estos dos algoritmos pueden presentar problemas si la matriz A es singular o muyproxima a serlo; i.e., κpAq es extremadamente grande. Si la situacion es esta, tenemosuna alternativa: los valores singulares.

8.3.1. El problema de mınimos cuadrados y la inversa Moore-Penrose

La inversa generalizada de Moore-Penrose se puede definir como la matriz que solu-ciona el problema de mınimos cuadrados. Es decir, de la misma que la solucion delsistema Ax “ b es x “ A´1b siempre que A sea invertible, la solucion del problemade mınimos cuadrados es x0 “ A:b. Veremos que esto es, en efecto ası, y que este he-cho nos proporciona un algoritmo alternativo para resolver el problema de mınimoscuadrados.

Recordemos que x0 es solucion del problema se mınimos cuadrados si y solo si essolucion del sistema Ax “ PAb, siendo PA la proyeccion ortogonal sobre ImA. Re-cordemos tambien que si r “ rangA y A “ UΣV ˚ es una descomposicion completade A en valores singulares, entonces las r primeras columnas de U son una base or-tonormal de ImA. (Proposicion 3.10). Sea Ur la submatriz de U formada por sus rprimeras columnas. Como son una base ortonormal de ImA, la matriz UrUr es laproyeccion ortogonal sobre ImA. Es decir, PA “ UrUr . Ası pues, si ponemos

Σ “„

Σr 00 0

entonces el sistema Ax “ PAb es equivalente a

Ur“Σr 0

‰V ˚x “ UrU

˚r b.

Y este sistema es equivalente a“Σr 0

‰V ˚x “ Ur b dado que Ur Ur “ Ir. Pongamos

c “ Ur b y y “ V ˚x. Entonces,

Ax “ PAbô“Σr 0

‰y “ c.

Si Σr “ Diagpσ1, . . . , σrq, la solucion general de este sistema es

y “ “c1{σ1 c2{σ2 ¨ ¨ ¨ cr{σr yr`1 ¨ ¨ ¨ yn

‰T

con yr`1,. . . , yn, numeros arbitrarios. Si el rango de A es completo, n, la solucion delsistema queda completamente determinada; cosa que ya habıamos demostrado. Pero


si rangA ă n entonces hay infinitas soluciones del problema de mınimos cuadrados.Entre ellas, se suele escoger la solucion de norma mınima. Y esta es la que se consiguehaciendo yr`1 “ ¨ ¨ ¨ “ yn “ 0. Finalmente, como y “ V ˚x, tenemos que x “ V y.Ademas, }x}2 “ }V y}2 “ }y}2. En definitiva, el vector x0 de norma mınima quesoluciona el problema de mınimos cuadrados es:

x0 “ V y0 “ V

»—————————–

c1{σ1

c2{σ2...

cr{σr0...0

fiffiffiffiffiffiffiffiffiffifl

“ Vr

»———–

c1{σ1

c2{σ2...

cr{σr

fiffiffiffifl ,

donde Vr es la submatriz de V formada por sus r primeras columnas.

Ahora vamos a “volver hacia atras” a fin de recuperar la solucion del problemaen terminos de los datos originales: A y b. Recordemos, antes de nada, que conlas notaciones introducidas A “ UrΣrVr es una descomposicion reducida de A envalores singulares. En consecuencia

A: “ VrΣ´1r U˚r

es la inversa generalizada o Moore-Penrose de A.

Ahora bien,

x0 “ Vr

»———–

c1{σ1

c2{σ2...

cr{σr

fiffiffiffifl “ VrΣ

´1r c “ VrΣ

´1r U˚r b,

porque c “ Ur b. Ası pues, el vector de norma mınima que soluciona el problema demınimos cuadrados es

x0 “ VrΣ´1r U˚r b “ A:b

tal y como habıamos anunciado.

Este proceso, ademas, nos proporciona un algoritmo para calcular la solucion delproblema de mınimos cuadrados en el caso mas general.


Algoritmo mınimos cuadrados via valores singulares


1. Calcular la descomposicion reducida de A en valores singulares:A “ UΣV ˚, U P Fmˆr, V P Fnˆr y Σ “ Diagpσ1, . . . , σrq.

2. Calcular c “ U˚b.

3. Calcular x “ V Σ´1c. Este es el vector de menor norma que solu-ciona el problema de mınimos cuadrados.

8.4. El condicionamiento del problema de mıni-

mos cuadrados

El condicionamiento del problema de mınimos cuadrados es un tema importante por-que tiene implicaciones no triviales en el estudio de la estabilidad de los algoritmospara este problema. Como es habitual analizaremos en detalle el condicionamien-to del problema y estudiaremos la estabilidad de los algoritmos mediante ejemplossignificativos.

Recordemos que el problema de mınimos cuadrados consiste en lo siguiente (supon-dremos en lo sucesivo que la matriz del sistema tiene rango completo):

Dada A P Fmˆn de rango completo y m ě n, y dado b P Fm,calcular x P Fn para que }Ax´ b}2 sea mınima.

(8.2)

Ya sabemos que, en este caso, la solucion del problema es unica y viene dada por

x “ A:b

donde A: P Fnˆn es la pseudoinversa o inversa generalizada de Moore-Penrose de A(ver 3.6). Ademas, si y “ Ax es el vector en ImA mas proximo a b entonces

y “ Pb,

8.4 El condicionamiento del problema de mınimos cuadrados 183

siendo P la proyeccion ortogonal sobre ImA.

Nuestro objetivo es estudiar el condicionamiento del Problema (8.2) respecto a per-turbacione en A y en b. Es decir, los datos del problema son la matriz A y el vectorb. La solucion es el vector de coeficientes x o el correspondiente vector y “ Ax. Asıpues

Datos: A, b. Soluciones: x, y.

Tenemos ası, en realidad, cuatro posibles cuestiones de condicionamiento: Errorrelativo en x o y respecto a pequenas perturbaciones en los datos b o A.

El objetivo en esta seccion es dar un resultado fundamental sobre el condicionamien-to del problema de mınimos cuadrados. Para entender el enunciado y como apoyoa la demostracion necesitamos introducir algunos conceptos y un par de resultadosauxiliares. En primer lugar debemos recordar que para una matriz A P Fmˆn derango completo n el numero de condicion es

κ2pAq “ }A}2}A:}2 “ σ1

σn.

Im A

b

y=Ax=Pbθ

r=Ax−b

Figura 8.4: El problema de mınimos cuadrados.

En segundo lugar, necesitamos el conceto de angulo entre dos vectores de Fm. Lodefinimos, como es habitual, a partir de la desigualdad de Cauchy-Schwartz: si x, y PFm entonces

|x˚y| ď }x}2}y}2,


de modo que

´1 ď x˚y}x}2}y}2 ď 1.

Se define, entonces el angulo, θ, de x, y como

θ “ arc cosx˚y

}x}2}y}2 .

Equivalentemente

cos θ “ x˚y}x}2}y}2 .

En nuestro caso, para calcular el angulo de b e y debemos hacer el producto escalarb˚y “ b˚Pb. Teniendo en cuenta que P es una proyeccion (P 2 “ P ) ortogonalpP ˚ “ P ) resulta que

b˚y “ b˚Pb “ b˚PPb “ b˚P ˚Pb “ }Pb}22 “ }y}22.Ası pues

cos θ “ }y}2}b}2 .

Para el seno usamos la identidad sen2 θ “ 1´ cos2 θ:

sen2 θ “ 1´ }y}22

}b}22“ }b}

22 ´ }y}22}b}22

.

Ahora bien, b “ y ` b ´ y siendo y y b ´ y ortogonales (y P ImA y b ´ y “b´ Pb “ pIm ´ P qb P pImAqK). Por consiguiente, usando el Teorema de Pitagoras,}b}22 “ }y}22 ` }b´ y}22 y

sen θ “ }b´ y}2}b}2Todas estos resultados generalizan los habituales en R2 (Figura 8.4)

En tercer lugar, para cualquier norma inducida }Ax} ď }A} }x}. Necesitaremos unamedidad de lo lejos o cerca que esta }y} “ }Ax} de su maximo valor posible:

η “ }A}2 }x}2}y}2 “ }A}2 }x}2}Ax}2 .

Estos parametros tienen el siguiente rango de variacion:

1 ď κpAq ă 8 0 ď θ ď π{2 1 ď η ď κpAq


Todas estas acotaciones son claras excepto, quiza, la ultima que viene de la siguienteobservacion:

}x}2 “ }A´1Ax}2 ď }A´1}2}Ax}2,de modo que

η ď }A}2}A´1}2}Ax}2}Ax}2 “ κ2pAq.

El resultado previo que necesitamos es el siguiente

Lema 8.4 Para A P Fmˆn de rango completo n se tiene:

}pA˚Aq´1A˚}2 “ 1

σn. (8.3)

}pA˚Aq´1}2 “ 1

σ2n

(8.4)

siendo σ1 ě ¨ ¨ ¨ ě σn los valores singulares de A.

Demostracion.- La propiedad (8.4) es una consecuencia inmediata de que los valo-res singulares de A son las raıces cuadradas positivas de los valores propios de A˚A,y de que 1{σ2

n es el mayor valor singular de pA˚Aq´1 (ver Porposiciones 3.12 y 3.16).

Para probar la propiedad (8.3) se usa el Teorema SVD para ver que los valoressingulares de pA˚Aq´1A˚ y los de A: coinciden.

Podemos ahora plantear y demostrar el resultado principal

Teorema 8.5 Sean b P Fm y A P Fmˆn con b ‰ 0 y rangA “ n ď m. Para elproblema de mınimos cuadrados (8.2) se cumplen las siguientes propiedades, todorespecto de la norma `2:

(i) El numero de condicion del problema de calcular y “ Ax P Fn respecto de b es

1

cos θ. (8.5)


(ii) El numero de condicion del problema de calcular x P Fn respecto de b es

κ2pAqη cos θ

. (8.6)

(iii) Sea x la solucion del problema de mınimos cuadrados relativo a minimizar

}pA` δAqx´ b}2. Si y “ pA` δAqx y ε “ }δA}2}A}2 ă σnσ1

entonces

}y ´ y}2}y}2 ď ε

κ2pAqcos θ

Òpε2q. (8.7)

(iv) En las mismas condiciones del apartado anterior

}x´ x}2}x}2 ď ε

ˆκ2pAq ` κ2pAq2 tan θ

η

˙Òpε2q. (8.8)

(v) Sea x es la solucion del problema de mınimos cuadrados relativo a minimizar}pA` δAqx´ pb` δbq}2. Si sen θ ‰ 1 y

ε “ max

"}δA}2}A}2 ,

}δb}2}b}2

*ă σnσ1

siendo σ1 ě ¨ ¨ ¨ ě σn los valores singulares de A, entonces

}x´ x}2}x}2 ď ε

"κ2pAq

ˆ1

η cos θ` 1

˙` κ2pAq2 tan θ

η

*Òpε2q. (8.9)

En el caso especial en que m “ n, el problema de mınimos cuadrados se reduce alde la resolucion de un sistema de ecuaciones lineales. En tal caso θ “ 0 y las cotasde (8.6) y (8.8) se reducen a κ2pAq{η y κ2pAq recuperando los resultados vistos enla Leccion 4.

Demostracion.- Demostraremos las propiedades (i) y (v). La propiedad (ii) sedemuestra de manera muy similar a la propirdad (i), la propiedad (iv) es una casoparticular de la (v) y la propiedad (iii) requiere una demostracion independientepero parecida a la (iv).

(i) La relacion entre b e y esy “ Pb


siendo P la proyecccion ortogonal sobre ImA. Vimos en la Seccion 4.3 del Capıtulo4 que el numero de condicion del problema de multiplicar Ax para A dada y xvariable:

f : Fn Ñ Fmx ; b “ Ax

es

κ “ }f 1pxq}}fpxq}{}x} “

}A} }x}}Ax} , (8.10)

En nuestro caso se trata del numero de condicion del problema y “ Pb respecto deb para P dado. Entonces

κpbq “ }P }2}b}2}y}2Como P es una proyeccion ortogonal P “ QQ˚ para alguna matriz Q P Fnˆm con

columnas ortonormales. Sea U “”Q rQ

ıuna matriz unitaria. Entonces

U˚PU “„Q˚rQ˚QQ˚

”Q rQ

ı“„In 00 0

Por lo tanto, los valores singulares de P son todos iguales a 1 y en particular

}P }2 “ σ1pP q “ 1

Finalmente, recordemos que cos θ “ }y}2}b}2 . En conclusion:

κpbq “ }P }2}b}2}y}2 “ 1

cos θ,

tal y como se deseaba demostrar.

(v) En primer lugar definimos E “ 1

εδA y f “ 1

εδb. Por hipotesis,

}δA}2}A}2 ă σn

σ1

y como }A}2 “ σ1, tenemos que }δA}2 ă σn. Por el Teorema 3.18 resulta querangpA ` δAq “ n y consecuentemente rangpA ` tEq “ n para todo t P r0, εs. Sesigue entonces que el sistema

pA` tEq˚pA` tEqxptq “ pA` tEq˚pb` tfq (8.11)


tiene una unica solucion para cada t P r0, εs. Invertir una matriz es una funciondiferenciable en los elementos de la matriz. Por lo tanto x es una funcion diferenciablede t en r0, εs. Por la definicion de diferencial

xpεq “ xp0q ` εx1p0q `Opε2q.

Como xpεq “ x, xp0q “ x, b ‰ 0 y sen θ ‰ 1, tenemos que x ‰ 0 y

}x´ x}2}x}2 “ ε

}x1p0q}2}x}2 `Opε2q. (8.12)

Necesitamos una estimacion de }x1p0q}2. Para ello calculamos x1p0q en (8.11). Pri-mero derivamos

E˚pA`tEqxptq`pA`tEq˚Exptq`pA`tEq˚pA`tEqx1ptq “ E˚ppb`tfq`pA`tEq˚f,

y sustituımos t “ 0 recordando que xp0q “ x:

E˚Ax` A˚Ex` A˚Ax1p0q “ A˚f ` E˚b.

Ası

x1p0q “ pA˚Aq´1A˚pf ´ Exq ` pA˚Aq´1E˚pb´ Axq.Tomando normas:

}x1p0q}2 ď }pA˚Aq´1A˚}2p}f}2 ` }E}2}x}2q ` }pA˚Aq´1}2}E˚}2}b´ Ax}2.

Por una parte, }E}2 “ 1

ε}δA}2 ď }A}2. Y de la misma forma }f}2 ď }b}2. Tambien

}A˚}2 “ }A}2, ası que

}x1p0q}2 ď }pA˚Aq´1A˚}2p}A}2}x}2 ` }b}2q ` }pA˚Aq´1}2}A}2}b´ Ax}2 ďď }pA˚Aq´1A˚}2}A}2

ˆ }b}2}A}2 ` }x}2

˙` }pA˚Aq´1}2}A}22

}b´ Ax}2}A}2 .

Por otra parte, por el Lema 8.4, }pA˚Aq´1A˚}2}A}2 “ κ2pAq y }pA˚Aq´1}2}A}22 “κ2pAq2. Entonces

}x1p0q}2}x}2 ď κ2pAq

ˆ }b}2{}Ax}2}A}2}x}2{}Ax}2 ` 1

˙` κ2pAq2 }b´ Ax}2{}Ax}2}A}2}x}2{}Ax}2 .

8.5 Estabilidad de los algoritmos para el problema de mınimos cuadrados 189

Ahora bien, η “ }A}2}x}2}Ax}2 , cos θ “ }Ax}2}b}2 y tan θ “ }b´ Ax}2}Ax}2 . En consecuencia

}x1p0q}2}x}2 ď κ2pAq

ˆ1

η cos θ` 1

˙` κ2pAq2 tan θ

η

sustituyendo en (8.12)

}x´ x}2}x}2 ď ε

"κ2pAq

ˆ1

η cos θ` 1

˙` κ2pAq2 tan θ

η

*`Opε2q,

tal y como se querıa demostrar.

8.5. Estabilidad de los algoritmos para el proble-

ma de mınimos cuadrados

Un estudio experimental de la estabilidad de los algoritmos para la resolucion delproblema de mınimos cuadrados lineal es el objetivo de una de las practicas obli-gatorias con MATLAB que habra de realizarse en este curso. En ella se planteaun problema de mınimos cuadrados cuya solucion debe ser calculada con los tresalgoritmos vistos en la Seccion 8.3. A su vez, para los algoritmos basados en la fac-torizacion QR, se utilizaran los tres algoritmos vistos en las Lecciones 6 y 7; es decir,los algoritmos clasico y modificado de Gram-Schmidt y el algoritmo de Householder.

A traves de dicho experimento se comprobara que los algoritmos basados en la reso-lucion de las ecuaciones normales y el factorizacion de Cholesky ası como los basadosen la factorizacion QR obtenida con los algoritmos de Gram-Schmidt pueden darresultados con mucho error si la matriz del sistema esta mal condicionada. Por lotanto, estos algoritmos son inestables. No obstante, hay resultados (ver [11, Sec20.4]) que muestran que para matrices bien condicionadas el algoritmo basado en laresolucion de las ecuaciones normales es estable hacia atras y para valores de m mu-cho mayores que n, el coste operacional sensiblemente menor que el metodo basadoen la factorizacion QR mediante reflexiones de Householder. En tales situaciones,el metodo basado en la resolucion de las ecuaciones normales serıa el preferido. Porotra parte, a pesar de que el metodo basado en la factorizacion QR mediante elalgoritmo modificado de Gram-Schmidt es inestable cuando se implementa de lamanera indicada en la Seccion 8.3, hay una forma de hacerlo que lo hace estable


hacia atras (ver [11, Sec 20.3]). Finalmente, los algoritmos basados en la factoriza-cion QR mediante reflexiones de Householder y valores singulares son estables haciaatras para sistemas en los que A es una matriz de rango completo. A continuacionse enuncian el teorema que hace explıto este resultado.

Teorema 8.6 Supongamos que el problema de mınimos cuadrados con una matrizA de rango completo se resuelve mediante el algoritmo QR por reflexiones de Hou-seholder o mediante la descomposicion en valores singulares en un ordenador quecumple los axiomas (5.2) y (5.4) de la Leccion 5. Este algoritmo es estable haciaatras: para cada A P Fmˆn (m ě n y rangA “ n) existe una perturbacion δA talque

}δA}}A} “ OpεMq

y la solucion px producida por el algoritmo satisface

}pA` δAqpx´ b}2 “ mınxPFn }pA` δAqx´ b}2.

Para terminar, conviene mencionar que si la matriz A no es de rango completo,sabemos que la solucion no esta determinada de forma unica y el unico algoritmocompletamente estable es el basado en la descomposicion de A en valores singulares.

el problema de m´ınimos cuadrados

Documents