minimos cuadrados

Problemas de
M´nimos Cuadrados
ı
• Ajuste de curvas.
´
• Sistemas rectangulares: Solucion en el sentido de m´nimos cuadrados. Ecuaciones
ı
normales.
´
´
• Ortogonalizacion: Gram-Schmidt. Factorizacion QR.
´
• Problemas de cuadrados m´nimos no lineales: Reduccion a problemas lineales.
ı

521230

-1-

´
DIM – Universidad de Concepcion

Considere un sistema rectangular deecuaciones

Ax = b
donde A

∈ Rm×n , con n < m, es una matriz rectangular de m filas y n columnas y

b ∈ Rm .
´
Este problema, en general, no tiene solucion: sistema sobredeterminado.

´
Una alternativa es buscar una solucion en el sentido generalizado siguiente:
Hallar x

∈ Rn tal que b − Ax

´
Definicion. El vector x que minimiza

b − Ax

ı
2 sea m´nima.

´
ı
2 es lasolucion en el sentido de m´nimos

cuadrados del sistema rectangular.

Ojo! En general:

Ax = b.

521230

-2-

´
DIM – Universidad de Concepcion

Ejemplo. Ajuste de polinomios.
Dado un conjunto de puntos

(x1 , y1 ), . . . , (xm , ym ),
nos proponemos encontrar el polinomio

p(x) = c0 + c1 x + . . . + cn−1 xn−1 ,
con n

´ ´
< m que este mas cerca de estos puntos en el sentidoque
m

|p(xi ) − yi |2 ,
i=1

sea m´nima.
ı

521230

-3-

´
DIM – Universidad de Concepcion

Esta suma de cuadrados es el cuadrado de la norma del residuo del sistema rectangular:



1


1


1

.
.
.
1

521230



n−1

x1

n−1 
x2  

n−1
x3  






x1

...

x2

 
...
  y2 
 
c1   
 y 
...
.  = 3.
 .   . 
.  . 
. 
 . 
. 
 . 
cn−1
n−1
. . . xm
ym

x3
.
.
.

xm

-4-

c0



y1

´
DIM – Universidad de Concepcion

∈ Rm×n (m ≥ n) y b ∈ Rm . Un vector x ∈ Rn minimiza la norma del
´
= b − Ax 2 si y solo si el residuo r es ortogonal a la imagen de A; esto es

Teorema. Sean A
residuo

r

2

si

At r = 0,
t

donde A es la matriz transpuestade A.

521230

-5-

´
DIM – Universidad de Concepcion

Consecuencia:

x debe satisfacer

At r = 0

⇐⇒

At (b − Ax) = 0

⇐⇒

At Ax = At b.

Estas ultimas ecuaciones reciben el nombre de ecuaciones normales.
´

´
Observacion: En el caso en que m

= n y que la matriz A sea una matriz no singular,

´
´
entonces las ecuaciones normales entregan como solucion lasolucion del sistema lineal

Ax = b.

521230

-6-

´
DIM – Universidad de Concepcion

´ ´
´
Las ecuaciones normales tienen solucion unica si y solo si todas las columnas de A son l.i.;
es decir, si rango(A)

= n.

´
En este caso, ademas, la matriz A

t

´
A es simetrica y definida positiva, de donde, las

´ ´
´
ecuaciones normales tienen solucion unica y se pueden utilizar losmetodos estudiados para
´
estas matrices, en particular, el metodo de Cholesky.

521230

-7-

´
DIM – Universidad de Concepcion

Para resolver las ecuaciones normales se puede proceder del siguiente modo:
1. Calcular la matriz A

t

A y el vector At b.

´
2. Obtener la matriz L de la factorizacion de Cholesky:
3. Resolver el sistema triangular inferior Ly
4. Resolver elsistema triangular superior L

521230

-8-

t

At A = LLt .

= At b.
x = y.

´
DIM – Universidad de Concepcion

Inconveniente: El condicionamiento de la matriz A

t

A es en general malo, lo que genera

gran sensibilidad respecto a errores de redondeo.
Por ejemplo, si A es cuadrada, entonces cond2 (A

t

A) = cond2 (A)2 .

´
´
Solucion: factorizacion QR. Ortogonalizarlas columnas de A mediante, por ejemplo,
Gram-Schmidt.
Para esto, escribamos:



donde ai

521230





A = a 1







a2





m×n
. . . an  ∈ R





∈ Rm , i = 1, 2, . . . , n, son las columnas de la matriz A.
-9-

´
DIM – Universidad de Concepcion

La idea es construir una matriz







Q =  q1







q2...