PROBLEMAS DE MÍNIMOS CUADRADOS

PROBLEMAS DE MÍNIMOS CUADRADOS

F. VADILLO

Los mínimos cuadrados es una herramienta muy utilizada desde su invención por Gauss y Legrende hacia el año 1800. En términos de algebra lineal se trata de resolver sistemas lineales Ax = b con más ecuaciones que incógnitas, donde el término resolver se entiende en el sentido de minimizar la norma euclídea de vector residuo r = Ax − b. Estas notas se dividen en dos partes, en la primera se estudia el problema de ajuste de curvas a conjuntos datos que es uno de los principales orígenes de los problemas de mínimos cuadrados. En la segunda parte se comentan los métodos numéricos más habituales para resolver los problemas de mínimos cuadrados.

Resumen.

Índice

1. Introducción 2. Ajustes de curvas por mínimos cuadrados 2.1. Rectas de regresión por mínimos cuadrados 2.2. Ajustes de otras curvas por mínimos cuadrados 2.3. Combinaciones lineales por mínimos cuadrados 3. Solución mínimo cuadrática de sistemas sobre-determinados 3.1. Reectores de Householder 3.2. La factorización QR de una matriz 3.3. Pseudoinversa de una matriz 3.4. Descomposición valores singulares de una matriz 4. Ejercicios Referencias

1 2 2 4 6 8 8 9 10 10 12 13

1.

Introducción

El término mínimos cuadrados describe el problema muy frecuente de resolver sistemas de ecuaciones lineales sobre-determinados, esto es, sistemas lineales con más ecuaciones que incógnitas. En tal caso, en lugar de resolver las ecuaciones de manera exacta, habitualmente no existe tal solución, se busca sólo minimizar la suma de los cuadrados de los residuos.

1

2

F. VADILLO

Se considera un sistema a1,1 . . . (1.1) . . . an,1

lineal de n ecuaciones lineales con m incógnitas · · · a1,m b1 x . .. . 1 . . . . . . . . = . , . .. . . . . . xm · · · an,m bn

que se supone es sobre-determinado, es decir, tiene más ecuaciones que incógnitas (n > m). En notación matricial es (1.2) El vector residuo (1.3)

Ax = b.

r = Ax − b,

quizá pueda hacerse pequeño con una adecuada elección de x, pero en general será distinto de cero. Se trata entonces de hacerlo tan pequeño como se pueda en algún sentido y lo que se denomina solución mínimo cuadrática minimiza la norma euclidea del residuo, es decir, el problema se plantea de la siguiente forma:

Dada la matriz A ∈ Rn×m con n > m y el vector b ∈ Rn , se quiere calcular el vector x ∈ Rm que minimize Ax − b 2 .

En Matlab el operador backslash calcula la solución mínimo cuadrática del sistema: x = A\y utilizando algoritmo de después se estudiaran. ˜

2.

Ajustes de curvas por mínimos cuadrados

2.1. Rectas de regresión por mínimos cuadrados. Una de las fuentes habituales de problemas de mínimos cuadrados son los problemas de ajustes de curvas. Em la ciencia y la ingeniería los experimentos producen un conjunto de datos (x1 , y1 ), ..., (xn , yn ), com las abscisas {xk } diferentes, y el problema que se plantea es determinar una función y = f (x) que relacione los datos, lo mejor posible em algún sentido. Evidentemente, el resultado dependerá del tipo de función que se elija, por ejemplo, em la regresión f (x) = ax + b es una recta, y para ajustar los parámetros libres se pueden minimizar uno de los siguientes tres valores: El error máximo:

E∞ (f ) = m´x{|f (xk ) − yk | : 1 ≤ k ≤ n}. a

El error medio:

E1 (f ) = 1 n

M

|f (xk ) − yk |.

k=1


3

El error medio cuadrático:

E2 (f ) = 1 n

n 1/2

(f (xk ) − yk )

k=1

2

.

Em el método de mínimos cuadrados el error que se minimiza es el error medio cuadrático. Por tanto, la recta de regresión ajusta los parámetros a y b para minimizar el valor

n

(2.1)

E(a, b) =

k=1

(axk + b − yk )2 ,

que son la solución del sistema lineal conocido como ecuaciones normales de

Gauss

n

n

n

x2 k

k=1

a+

k=1 n

xk xk

b =

k=1 n

xk yk , yk ,

k=1

a + nb =

k=1

cuya obtención se deja como ejercicio para el alumno.

Ejemplo 2.1. La población en los Estados Unidos de América durante el siglo

XX ha seguido la evolución indicada en la tabla adjunta, se pide hallar la recta de regresión y pronostican el número de habitante en al año 2010. año millones de habitantes 1900 75.995 1910 91.972 1920 105.711 1930 123.203 1940 131.669 1950 150.697 1960 179.323 1970 203.212 1980 226.505 1990 249.633 2000 281.422 El programa lsline.m de [8] resuelve directamente el sistema normal, y la recta de regresión que resulta es:

y = 2,0253x − 3783,9,

que para el año 2010 pronostica 286.912 millones de habitantes. En la gura 1 se ha representado los puntos y la recta de regresión. Em el ajuste potencial f (x) = axp donde p es una constante conocida, el único parámetro libre a debe minimizar

n

(2.2)

E(a) =

(axp − yk )2 , k

k=1

4

400

F. VADILLO

350

300

250

200

150

100

50

0 1900

1920

1940

1960

1980

2000

2020

Figura 1.

Recta de regresión .

e igualando a cero la derivada se obtiene que (2.3)

a=

n p k=1 xk yk n 2p . k=1 xk

2.2. Ajustes de otras curvas por mínimos cuadrados. Suponga que ahora se quieren ajustar los datos (x1 , y1 ), ..., (xn , yn ) por el método de mínimos cuadrados usando una curva exponencial

(2.4)

y = c · eax ,

n

donde a y c son ahora los parámetros a elegir. El valor que se debe minimizar es (2.5)

E(a, c) =

(c · eaxk − yk )2 .

k=1

Igualando a cero las dos derivadas parciales de E(a, c) se llega al sistema de las dos ecuaciones normales

n n

c

k=1

xk e2axk −

k=1 n

xk yk eaxk

n

= 0, = 0,

c

k=1

e

axk

−

k=1

yk eaxk

ecuaciones que mo son lineales para las incógnitas a y c com la dicultad que esto supone.


5

Otra forma de resolver el mismo problema es por el método de linealización de los datos. Se supone que los datos yk > 0 y se toman logaritmos em (??) para obtener ln y = ax + ln c. Después se hace el siguiente cambio de variable

u = x,

com lo que resulta la recta

v = ln y,

b = ln c,

v = au + b,

com los datos transformados (uk , vk ) = (xk , ln(yk )) para k = 1, ..., m. Problema lineal que ya se sabe resolver.

Ejemplo 2.2. En el ejemplo de la población americana, la aproximación exponencial que se obtiene es (2.6)

y = 1,9908 · 10−9 · e0,0129x ,

y la estimación en el año 2010 es de 329.9944 millones de habitantes.

400

350

300

250

200

150

100

50

0 1900

1920

1940

1960

1980

2000

2020

Figura 2.

Ajuste exponencial .

La técnica de linealización de los datos se utiliza para ajustar otros tipos de a curvas com un cambio de variable adecuado. Por ejemplo, si f (x) = x + b el cambio 1 que linealiza el problema es u = x y v = y . Em la siguiente tabla se muestran algunos cambios de variables para linealizar datos.

6

F. VADILLO

Función y = f (x)

Cambios de variables

1 u = x, v = y

y= y= y= y=

a x

+b

d x+c 1 ax+b x ax+b

u = xy, v = y u = x, v =

1 u = x, v = 1 y 1 y

y = a ln x + b y = c · eax y=

1 (ax+b)2

u = ln x, v = y u = x, v = ln y u = x, v =

1 √ y

y = c · x · edx y=

l 1+c·eax

y u = x, v = ln( x )

u = x, v = ln

l y

−1

2.3. Combinaciones lineales por mínimos cuadrados. El problema de las combinaciones lineales em mínimos cuadrados se formula de la siguiente manera: dados m puntos {(xk , yk )} y un conjunto de m funciones linealmente independientes {fj (x)}, lo habitual es que n > m y se trata de encontrar m coecientes {cj } tales que la función

m

(2.7)

f (x) =

j=1

cj fj (x),

minimice la suma de los cuadrados de los errores

n n

m j=1

2

(2.8)

E(c1 , ..., cm ) =

(f (xk ) − yk )2 =

k=1 k=1

cj fj (xk ) − yk .

∂E Para que la función E sea mínima, es necesarios que ∂ci = 0 para i = 1, ..., m, lo que equivale a que los coecientes cj seam la solución del sistema de ecuaciones normales de Gauss n m

(2.9)

k=1

j=1

cj fj (xk ) − yk fi (xk ) = 0,

i = 1, ..., m.

Intercambiando el orden de los sumatorios el sistema anterior se puede escribir de la forma

m n n

(2.10)

j=1 k=1

fi (xk )fj (xk ) cj =

k=1

fi (xk )yk ,

i = 1, ..., m.


7

Este sistema lineal de orden m × m se puede escribir em notación matricial de forma mas cómoda. Deniendo la matriz y los siguientes vectores f1 (x1 ) · · · fm (x1 ) y1 c1 . . . .. . . . . . . . , c = . , y = . , F = . . . . .. . . . . . . . cm f1 (xn ) · · · fm (xn )

yn el sistema de ecuaciones normales es (2.11)

F T F c = F T y,

donde F T indica la matriz transpuesta y la incógnita es el vector c, que es también la solución del sistema sobre-determinado (2.12)

F c = y,

que tiene más ecuaciones que incógnitas porque n > m.

Ejemplo 2.3. Siguiendo con el ejemplo de la población americana en el siglo XX,

se tratara de ajustar los datos a un polinomio de grados 3 (2.13)

y ≈ c3 x3 + c2 x2 + c1 x + c0 . c0 = −4,25822238574126, c2 = −0,00000496111699, c1 = 0,00802427140030, c3 = 0,00000000101028,

La solución del sistema normal es:

con la gráca de la gura 3 que pronostica 312.6913 millones de habitantes para el

400

350

300

250

200

150

100

50

0 1900

1920

1940

1960

1980

2000

2020

Figura 3.

Ajuste con un polinomio de tercer grado.

8

F. VADILLO

año 2010. El programa censusgui.m de [1] dibuja ajustes polinomiales de diferentes grados y calcula la estimación de población para el año 2010.

3.

Solución mínimo cuadrática de sistemas sobre-determinados

Volviendo al problema de los sistemas lineales sobre-determinados (1.2), una forma teórica de calcular su solución mínimo cuadrática es utiliza los sistemas normales del tipo (2.11), bastaría multiplicar los dos lados por la matriz AT para obtener el llamado sistema normal (3.1)

AT Ax = AT b.

donde AT A es una matriz m × m, es decir, que si hubiera miles de observaciones (n fuera grande) y unos pocos parámetros (m fuera pequeña), el sistema normal es pequeño por lo que resolverlo sería barato. El siguiente teorema conrma la conveniencia de resolver los sistemas normales:

problema de mínimos cuadrados si y sólo si es solución del sistema norma (3.1). Además, la solución es única si y sólo si A tiene rango m.

Sin embargo, habitualmente los sistemas normales están mal condicionados porque su número de condición es muy alto, de hecho, (3.2)

Teorema 3.1. Sean A ∈ Rn×m y b ∈ Rn dados. Un vector x es la solución del

κ(AT A) = κ(A)2 . 1 1 A = δ 0 , 0 δ

Por ejemplo, considerando la matriz

con δ pequeño pero no cero, sus dos columnas son linealmente independientes aunque casi paralelas. Sin embargo, la matriz del sistema normal es

AT A =

1 + δ2 1

1 1 + δ2

,

que para |δ| < 10−8 computando con aritmética de doble precisión es una matriz singular que no tiene inversa, y por lo tanto el sistema normal no tiene una solución. La conclusión de todo esto es que en la práctica los problemas de mínimos cuadrados no se pueden resolver calculando las soluciones de los sistemas normales asociados (3.1) con los algoritmos habituales.

3.1. Reectores de Householder. Los reectores de Householder son matrices de transformación que se utilizan en algunos de los algoritmos numéricos más importantes para aproximar autovalores y valores singulares de matrices. Formalmente, un reector de Householder es una matriz de la forma

(3.3)

H = I − 2uuT ,

donde el vector u ∈ Rn es unitario ( u 2 = uT u = 1) e I es la matriz identidad. A 2 continuación se listan algunas propiedades de estas matrices:


9

1. Los reectores de Householder son matrices simétricas: H T = H . 2. Los reectores de Householder son matrices ortogonales: H −1 = H T =⇒ H2 = I. 3. Hu = u − 2uuT u = −u. 4. Si v es un vector ortogonal al vector u, entonces Hv = v − 2uuT v = v. Geométricamente es fácil observar que el reector H a cada vector de Rn le lleva a su reexión respecto del hiperplano ortogonal al vector u que lo dene. La propiedad que se utiliza en el posterior algoritmo se recoge en el siguiente teorema:

Teorema 3.2. Para todo par de vectores x, y ∈ Rn con las misma norma euclídea,

el reector construido con el vector u =

x−y x−y

2

lleva un vector en el otro.

En la práctica, dado un vector x ∈ Rn , se utiliza un reector para llevar lo a otro vector con sólo una componente no nula, lo detalles de la implementación se pueden consultar en [7].

resolver sistemas sobre-determinados utiliza la factorización QR de la matriz A del sistema. La idea consiste en escribir A = Q · R donde Q es una matriz ortogonal y R es una matriz con todos ceros por debajo de la diagonal principal. Para construir dicha factorización se utiliza el teorema 3.2 aplicando una sucesión de reectores de Householder que van anulando todos los elementos de la matriz por debajo de la diagonal principal con el resultado nal (3.4)

3.2. La factorización QR de una matriz. Unos de los métodos clásicos para

Hm · · · H2 H1 A = R,

donde la matriz R de n × m tiene todo cero por debajo de la diagonal y las matrices Hi son todas ortogonales porque son reectores. La factorización que resulta es (3.5)

A = Q · R,

con Q = (Hm · · · H2 H1 )T .

Aplicando al término derecho del sistema sobre-determinado (1.2) las mismas transformaciones se tiene (3.6)

Rx = (Hm · · · H2 H1 )b,

que es un sistema triangular superior de m ecuaciones que se resuelve con una sustitución regresiva. El algoritmo de resolución es el siguiente: 1. Computa la factorización QR de la matriz A = QR. 2. Computa el vector Qb. 3. Resuelve el sistema triangular superior Rx = Qb. Los detalles para la implementación del algoritmo QR se pueden consultar en textos clásicos como [5], [6], [3], [2],[4] o [7]. El programa qrsteps.m de la referencia [1] muestra paso a paso como se construye la factorización QR de cualquier matriz.

10

F. VADILLO

3.3. Pseudoinversa de una matriz. El concepto de pseudoinversa de una matriz debido a Moore y Penrose generaliza y extiendo el clásico concepto de matriz inversa de una matriz cuadrada. Sea A una matriz n × m con n > m de rango m, su pseudoinversa es la matriz que aparece en las ecuaciones normales

(3.7)

A† = (AT A)−1 AT ,

que es una matriz m × n. Según esta denición, si la matriz B fuera cuadrada no singular (3.8)

B † = (B T B)−1 B T = B −1 (B T )−1 B T = B −1 .

La matriz pseudoinversa tiene propiedades, aunque no todas, que recuerda la matriz inversa ordinaria, por ejemplo (3.9) (3.10)

A† A = (AT A)−1 AT A = I, AA† = A(AT A)−1 AT .

que indica que es la inversa por la izquierda, pero no así por la derecha porque Otra propiedad importante de la pseudoinversa es que se trata de la mejor aproximación a la inversa por la derecha en el sentido de que minimiza el residuo con respecto a la norma de Frobenius. La norma de Frobenius de la matriz A se dene la siguiente forma: 1/2 (3.11) y lo que se demuestra es que (3.12)

A

F

=

i j

a2 i,j

,

A† = m´ AZ − I ın

Z

F.

En relación con el problema que se plantea: calcular la solución mínimo cuadrática del sistema lineal sobre-determinado (1.2), en vista del sistema normal (3.1) asociado, es evidente que conocida la pseudoinversa de la matriz A la solución se reduce a un simple producto matricial porque la solución mínimo cuadrática es (3.13)

x = (AT A)−1 AT b = A† b.

Los algoritmos para calcular pseudoinversas de matrices utilizan la descomposición valores singulares que resumimos muy brevemente a continuación.

3.4. Descomposición valores singulares de una matriz. Dada una matriz

(3.14)

A ∈ Rn×m con n ≥ m siempre tiene una descomposición en valores singular SVD (singular values decomposition) tal que A = U ΣV T , Σ = diag(σ1 , ..., σm ) ∈ Rn×m ,

donde U ∈ Rn×n y V ∈ Rm×m son matrices ortogonales. Los valores σ1 ≥ .... ≥ σm ≥ 0 son los valores singulares de la matriz A y las columnas de U y V son los vectores singulares por la

izquierda y por la derecha respectivamente de la matriz A. En el siguiente cuadro se recogen algunas propiedades interesantes de los valores singulares de una matriz cuyas demostraciones se pueden consultar en la página 33 de la referencia [5].


11

1. El rango de A es r, el numero de valores singulares no nulos. 2 2 2. A 2 = σ1 y A F = σ1 + · · · σr . 3. Los valores singulares de A no cero, son las raíces cuadradas los autovalores no nulos de AT A. n 4. Si A ∈ Rn×n entonces |det(A)| = i=1 σi . T 5. Si A = A sus valores singulares son los valores absolutos de los autovalores de A. En los que se reere a la pseudoinversa de la matriz, el resultado que interesa es el siguiente:

Teorema 3.3. Si en la descomposición valores singulares de la matriz A

Σ= D 0 0 0 , D = diag(σ1 , · · · , σr ), σ1 ≥ · · · ≥ σr > 0, D−1 0 0 0 ,

entonces

A† = V Σ+ U T ,

donde

Σ+ =

Los algoritmos que calculan la descomposición valores singulares de una matriz son muy técnicos y por ello superan el contenido de estas notas. En las referencia [3], [2], [5], o [7] se pueden consultar los detalles. En Matlab el comando pinv(A) computa la pseudoinversa de la matriz A con dichos algoritmos.

Ejemplo 3.4. Se considera el sistema Ax = b donde :

A= 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 , b= 16 17 18 19 20

,

donde la matriz A tiene rango 2 lo mismo que el rango de la matriz ampliada por lo que la solución no es única. Utilizando el backslash A\y la ejecución produce un warning y la solución que se obtiene es −7,5000 . 0 x= 7,8333 Por otra parte, calculando x = A† b la solución es −7,5556 z = 0,1111 . 7,7778

x

Las dos son soluciones pero la segunda tiene menor norma euclidea porque 2 = 10,8449 mientras que z 2 = 10,8440.

12

F. VADILLO

4.

Ejercicios

1. Deduzca las ecuaciones normales de Gauss para la recta de regresión. 2. El nivel del agua en el mar del Norte está principalmente determinado por el llamado índice de marea que tiene la forma

H(t) = h0 + a1 sin

πt 6

+ a2 cos

πt 6

,

con t medido en horas. Ajuste los valores de los parámetros si han tomado las siguientes mediciones

t H(t)

0 2 1.0 1.6

4 1.4

6 0.6

8 0.2

10 0.8

3. Para conocer la relación entre la velocidad de caída de un paracaidista y la fuerza de fricción hacia arriba, se han efectuado las siguientes mediciones

v f

1.0 5

2.0 15.3

3.0 29.3

4.0 46.4

5.0 66.3

donde v se mide en centímetros por segundo y rozamiento f en 106 dinas. Dibuje los puntos de la tabla y decida que aproximación mínimo cuadrática le conviene. 4. En 1601 el astrónomo alemán J.Kepler formulo su tercera ley del movimiento planetario: T = c · d3/2 donde d es la distancia de un planeta al sol medida en millones de kilómetros, T es el periodo orbital en días y c es una constante. Los datos observados para los cuatro planetas Mercurio, Venus, Tierra y Marte son:

di 58 108 155 228 Ti 88 225 365 687 Ajuste el valor de c para estos datos en el sentido de los mínimos cuadrados. 5. Deduzca las ecuaciones normales para ajustar por mínimos cuadrados el plano z = a + bx + cy a los datos {(xi , yi , zi )}n . i=1 6. Cuando una población P (t) no puede crecer más de un cierto valor límite L, la gráca de la función P (t) es una curva llamada curva logística de ecuación y = L/(1 + ceat ). Ajuste los valores de c y a para L = 1000 y la tabla t 0 1 2 3 4 P (t) 200 400 650 850 950

7. Estime el peso atómico del nitrógeno y el oxígeno utilizando los pesos moleculares de los siguientes óxidos

N O = 30,006 N2 O = 44,013 N O2 = 46,006 N2 O3 = 76,012 N2 O5 = 108,010 N2 O4 = 92,011

8. Demuestre el teorema 3.1. 9. Demuestre el teorema 3.2.


13

Referencias

1. C.B.Moler, Numerical computing with matlab, SIAM, 2004. 2. D.S.Walkins, Fundaments of matrix computions, John Wiley, 1991. 3. G.H.Golub and C.F.Van Loan, Matrix computations, The Johns Hopkins University Press, 1989. 4. K.E.Atkinson, An introduction to numerical analysis, Wiley, 1978. 5. L.N.Trefethen and D.Bau, Numerical linear algebra, SIAM, 1997. 6. N.J.Higham, Accuracy and stability of numerical algoritms, SIAM, 1996. 7. R.Bulirsch and J.Stoer, Introduction to numerical analysis, Springer, 1980. 8. J.F.Mathews y K.D.Fink, Métodos numéricos con matlab. tercera edición, Prentice Hall, 1999.

Dep. Matemática Aplicada y Estadística de la Universidad del Pais Vasco

Documents

PROBLEMAS DE MÍNIMOS CUADRADOS