Post on 16-Feb-2016
description
Recordatorio Ajuste exponencial Descomposición QR
Ajuste mínimo cuadrático de curvas
Métodos Numéricos
Prof. Juan Alfredo GómezConferencia 21
1 / 26
Recordatorio Ajuste exponencial Descomposición QR
Conferencia 21
1 RecordatorioMotivaciónAjuste linealAjuste polinomial
2 Ajuste exponencial
3 Descomposición QR
2 / 26
Recordatorio Ajuste exponencial Descomposición QR
Puntos de una función sujetos a perturbaciones
3 / 26
Recordatorio Ajuste exponencial Descomposición QR
Polinomio de interpolación de Lagrange
4 / 26
Recordatorio Ajuste exponencial Descomposición QR
Función linal con perturbaciones aleatorias
5 / 26
Recordatorio Ajuste exponencial Descomposición QR
Comparación de ambas metodologías
6 / 26
Recordatorio Ajuste exponencial Descomposición QR
Problema de mínimos cuadrados
De�nición en el caso de una recta
Dada una colección de datos {(xi , yi )}mi=1 encontrar los coe�cientes de larecta y = a0 + a1x que mejor aproxima esos datos de acuerdo a la normacuadrática:
min→ E2(a0, a1) =m∑i=1
[yi − (a0 + a1xi )]2
De las condiciones de optimalidad
2∑m
i=1(yi − (a0 + a1xi )(−1) = 0
2∑m
i=1(yi − (a0 + a1xi )(−xi ) = 0
obtenemos la ecuación normal ∑m
i=11
∑m
i=1xi∑m
i=1xi
∑m
i=1x2i
a0
a1
=
∑m
i=1yi∑m
i=1xiyi
7 / 26
Recordatorio Ajuste exponencial Descomposición QR
Problema de mínimos cuadrados
De�nición en el caso de una polinomios
Dada una colección de datos {(xi , yi )}mi=1 encontrar los coe�cientes de unafunción polinomial
Pn(x) = a0 + a1x + · · ·+ anxn
con grado n < m − 1 que mejor aproxima los datos de acuerdo a la normacuadrática:
min→ E2 =m∑i=1
[yi − Pn(xi )]2 =
m∑i=1
yi − 2
m∑i=1
Pn(xi )yi +m∑i=1
(Pn(xi ))2
Condiciones de optimalidad de primer orden:
0 =∂E2
∂aj= −2
∑m
i=1yix
ji + 2
∑n
k=0ak
∑m
i=1xj+ki , j = 0, . . . , n
8 / 26
Recordatorio Ajuste exponencial Descomposición QR
Ecuaciones Normales
Reescribiendo las condiciones de optimalidad
−2∑m
i=1yix
ji + 2
∑n
k=0ak
∑m
i=1xj+ki = 0, j = 0, . . . , n
obtenemos las Ecuaciones normales
∑m
i=1x0i
∑m
i=1x1i · · ·
∑m
i=1xni∑m
i=1x1i
∑m
i=1x2i · · ·
∑m
i=1xn+1
i
.
.
....
. . ....∑m
i=1xni
∑m
i=1xn+1
i · · ·∑m
i=1x2ni
a0
a1
.
.
.
an
=
∑m
i=1yix
0
i∑m
i=1yix
1
i
.
.
.∑m
i=1yix
ni
Observación
Las ecuaciones normales en el caso de ajuste polinomial tienen soluciónúnica siempre que los xi sean distintos.
9 / 26
Recordatorio Ajuste exponencial Descomposición QR
Aspectos generales
Motivación
En ciertos casos es apropiado asumir que los datos tienen una dependenciaexponencial del tipo y = beax o del tipo y = bxa.
El problema de mínimos cuadrados asociado
Se minimizan en cada caso las funciones
E =∑m
i=1[yi − beaxi ]2; E =
∑m
i=1[yi − bxai ]
2
Ecuaciones normales no lineales!
2∑m
i=1(yi − beaxi )(−eaxi ) = 0
2∑m
i=1(yi − beaxi )(−bxieaxi ) = 0
y en el otro caso:
2∑m
i=1(yi − bxai )(−xai ) = 0
2∑m
i=1(yi − bxai )(−b(ln xi )xai ) = 0
10 / 26
Recordatorio Ajuste exponencial Descomposición QR
Mínimos cuadrados logarítmicos
Idea alternativa
Si los datos son exponenciales, aplicar un ajuste de mínimos cuadradoslineal considerando el logaritmo de las ecuaciones aproximantes, o sea:
y = beax ! ln y = ln b + ax
y = bxa ! ln y = ln b + a ln x
Ecuaciones Normales (caso y = beax)
ln b =(∑m
i=1 x2i )(∑m
i=1 ln yi )−(∑m
i=1 xi (ln yi ))(∑m
i=1 xi )m(
∑mi=1
x2i )−(
∑mi=1
xi )2
a =m(
∑mi=1 xi (ln yi ))−(
∑mi=1 xi )(
∑mi=1 ln yi )
m(∑m
i=1x2i )−(
∑mi=1
xi )2
11 / 26
Recordatorio Ajuste exponencial Descomposición QR
Mínimos cuadrados logarítmicos
Idea alternativa
Si los datos son exponenciales, aplicar un ajuste de mínimos cuadradoslineal considerando el logaritmo de las ecuaciones aproximantes, o sea:
y = beax ! ln y = ln b + ax
y = bxa ! ln y = ln b + a ln x
Ecuaciones Normales (caso y = bxa)
ln b =(∑m
i=1(ln xi )2)(
∑mi=1 ln yi )−(
∑mi=1(ln xi )(ln yi ))(
∑mi=1 ln xi )
m(∑m
i=1(ln xi )
2)−(∑m
i=1ln xi )
2
a =m(
∑mi=1(ln xi )(ln yi ))−(
∑mi=1 ln xi )(
∑mi=1 ln yi )
m(∑m
i=1(ln xi )
2)−(∑m
i=1ln xi )
2
12 / 26
Recordatorio Ajuste exponencial Descomposición QR
Ejemplo de ajuste exponencial (caso y = beax)
Cálculos asociados
xi yi x2i ln yi xi ln yi r(xi ) = 3.071e0.5056xi
1.00 5.10 1.0000 1.629 1.629 5.0921.25 5.79 1.5625 1.756 2.195 5.7781.50 6.53 2.2500 1.876 2.815 6.5561.75 7.45 3.0625 2.008 3.514 7.4392.00 8.46 4.0000 2.135 4.271 8.4427.50 11.8750 9.405 14.424
a =m(
∑mi=1 xi (ln yi ))−(
∑mi=1 xi )(
∑mi=1 ln yi )
m(∑m
i=1x2i )−(
∑mi=1
xi )2 = 5(14.424)−7.5(9.405)
5(11.875)−(7.5)2= 0.5056
ln b =(∑m
i=1 x2i )(∑m
i=1 ln yi )−(∑m
i=1 xi (ln yi ))(∑m
i=1 xi )m(
∑mi=1
x2i )−(
∑mi=1
xi )2
ln b = 11.875(9.405)−14.424(7.5)5(11.875)−(7.5)2
= 1.122 =⇒ b = e1.122 = 3.071
13 / 26
Recordatorio Ajuste exponencial Descomposición QR
Ejemplo de ajuste exponencial
14 / 26
Recordatorio Ajuste exponencial Descomposición QR
Caso no Lineal
En general el problema a resolver
El problema consiste en encontrar el mínimo de la suma de los cuadradosde m funciones no lineales; es decir
Minimizar g(x) =1
2
m∑i=1
r2i (x) =1
2‖r(x)‖22
Donde ri (x) representa el error en la predicción que hace el modelo de laobservación i ,
ri (x) = yi − f (x , ti ), i = 1, . . . ,m
15 / 26
Recordatorio Ajuste exponencial Descomposición QR
Observaciones
Un sistema de ecuaciones lineales Ax = b, con A ∈ Mm×n, n < m, quetiene más ecuaciones que incógnitas, se dice que es superdeterminado osobredeterminado.
Los sistemas superdeterminados aparecen en problemas que utilizan datosexperimentales para aproximar una solución, debido a que es habitual tomarmás datos empíricos de los necesarios, para luego ajustarlos a una soluciónque no veri�can de modo exacto.
De�nición
Sea el sistema de ecuaciones lineales Ax = b, superdeterminado. Entonces,se dice que α ∈ Rn es una solución en mínimos cuadrados del sistemaAx = b, si se veri�ca
‖Aα− b‖22 = Mín{‖Ax − b‖22 : x ∈ R}
Además
16 / 26
Recordatorio Ajuste exponencial Descomposición QR
Continuación De�nición
1 Si Aα− b = 0, el sistema de ecuaciones Ax = b es compatible.
2 Si Aα− b 6= 0, el sistema Ax = b es incompatible y la norma‖Aα− b‖2 es llamada a veces error de la solución en mínimoscuadrados
Observación
Si resolvemos el problema de mínimos cuadrados tenemos que buscar elmínimo de
f (x) = (Ax − b)t(Ax − b) =⇒ f ′(x) = (AtA)x − Atb = 0
Obtenemos un sistema de ecuaciones llamados ecuaciones normales
AtAx = Atb
17 / 26
Recordatorio Ajuste exponencial Descomposición QR
Descomposición QR
Teorema
Sea V un espacio vectorial con producto interno y B = {v1, . . . , vn} unabase de V . Entonces existe B′ = {y1, . . . , yn} tal que B es una baseortonormal de V y [v1, . . . , vk ] = [y1, . . . , yk ], ∀k = 1, . . . , n.
Observaciones
Es claro que basta encontrar {u1, . . . , un} base ortogonal de V talque [v1, . . . , vk ] = [y1, . . . , yk ], ∀k = 1, . . . , n ya que basta de�nir
luego yi =ui
‖ui‖.
Para encontrar estos ui ortogonales se puede seguir el siguienteesquema:
u1 = v1; u2 = v2 − ut1v2
ut1u1u1
ui = vi −i−1∑k=1
ci,kuk , donde ci,j =v ti uj
utj uj
18 / 26
Recordatorio Ajuste exponencial Descomposición QR
Observaciones
El esquema anterior se conoce como el método de Gram-Schmidt.
Se puede construir la siguiente matriz:
B =
‖u1‖ c21‖u1‖ c31‖u1‖ · · · cm1‖u1‖
0 ‖u2‖ c32‖u2‖ · · · cm2‖u2‖0 0 ‖u3‖ · · · cm3‖u3‖...
......
. . ....
0 0 0 · · · ‖um‖
donde B es una matriz triangular superior con diagonal positiva.
Teorema
Sea A ∈ Mn×m(R) de rango m, entonces existe una matriz Q ∈Mn×m(R) que veri�ca QtQ = In×n y una matriz triangular superiorR ∈Mn×m(R) tal que A = QR
19 / 26
Recordatorio Ajuste exponencial Descomposición QR
Ejemplo
Hallar la descomposición QR de la matriz A =
1 0 10 2 11 1 0
Desarrollo
Sea B = {v1, v2, v3} = {(1, 0, 1), (0, 2, 1), (1, 1, 0)} las columnas de A.Aplicaremos el método de Gram-Schmidt a la base B. Entonces
u1 = v1 = (1, 0, 1)
u2 = v2 − v t2u1ut1u1
u1 =(− 1
2 , 2,12
)u3 = v3 − v t3u2
ut2u2u2 − v t3u1
ut1u1u1 =
(− 2
3 ,13 ,−
23
)normalizando se obtiene:
y1 =u1
‖u1‖=
1√2(1, 0, 1) y2 =
u2
‖u2‖=
√2
3
(−1
2, 2,
1
2
)
y3 =u3
‖u3‖=
1
1
(−2
3,1
3,−2
3
)20 / 26
Recordatorio Ajuste exponencial Descomposición QR
Vectores ortonormales
y1 =1√2(1, 0, 1) y2 =
√2
3
(−1
2, 2,
1
2
)y3 =
u3
‖u3‖=
1
1
(−2
3,1
3,−2
3
)Finalmente
Q =
1/√2 − 1
3√2
2/3
0 2√2/3 1/3
1/√2 1/3
√2 −2/3
R =
√2 1/√2 1/
√2
0 3/√2 1/
√2
0 0 1
21 / 26
Recordatorio Ajuste exponencial Descomposición QR
Observación
Si A posee columnas l.i. y A = QR.
AtAx = Atb ⇐⇒ RtQtQRx = RtRx = RtQtb ⇐⇒ Rx = Qtb
La ultima equivalencia debido a que Rt es invertible por serlo R.
Resolver la ecuación Rx = Qtb, lo cual tiene dos ventajas, una esque R es triangular y la otra es que, en general, el error que secomete al resolver de esta manera mediante una computadora digitales menor que el que se comete empleando la ecuación normalAtAx = Atb.
22 / 26
Recordatorio Ajuste exponencial Descomposición QR
Ejemplo
Encuentre la solución del sistema de ecuaciones superdeterminado1 1 01 0 11 1 11 2 1
x
y
z
=
1024
Desarrollo
Primero calculemos el sistema normal AtA = Atb, 4 4 34 6 33 3 3
x
y
z
=
71116
23 / 26
Recordatorio Ajuste exponencial Descomposición QR
Calculando su descomposición QR tenemos que
Q =(
0, 62469 −0, 49975 0, 60, 62469 0, 78086 00, 46852 −0, 37481 −0, 8
)R =
(−6, 40312 −7, 65251 −5, 15373
0 −1, 56173 0, 281110 0 0, 6
)Reduzcamos el sistema a la forma Rx = Qtb 6, 40312 7, 65251 5, 15373
0 1, 56173 0, 281110 0 −0, 6
x
y
z
=
14.05562.8424−0.6
�nalmente al hacer la sustitución hacia atrás obtenemos que
x = −1, y = 2, z = 1, y el residuo es r(x) = Ax − b = 0
Con lo cual el sistema tiene solución.
24 / 26
Recordatorio Ajuste exponencial Descomposición QR
Ejercicios
Considere la siguiente tabla de valores:
xi −2 −1 0 1 2
f (xi ) 0.0338 0.4119 3.013 0.4240 0.0249
Realice ajuste los datos a la función m1(x) = a + bx2.
Realice un ajuste de datos a la función m2(x) = aebx2y compare con el inciso
anterior. ¾Cuál presenta menor error cuadrático?
La intensidad de la luz disminuye en razón inversamente proporcional al cuadrado de ladistancia x desde la fuente al detector. En la experiencia de laboratorio, se coloca unsensor (light sensor de PASCO) a una distancia x de la fuente de luz que va cambiando.Se Obtiene la siguiente tabla:
Distancia x a0.20 0.25 0.30 0.35 0.40 0.45 0.50
la fuente de luz (cm)Intensidad I (lux) 171 106 73 52 39 30.5 24.5
Queremos ajustar m pares de datos (xi , yi ) a la función m(x) = a + bx2
con a, b
contantes a determinar.
25 / 26
Recordatorio Ajuste exponencial Descomposición QR
Ejercicios
Considere las siguientes matrices
A =
1 2 00 1 01 −2 22 0 −1
, b =
−1−132
1 Determine el sistema normal asociado a Ax = b.
2 Obtenga la descomposición QR de A del sistema normal asociado.
3 Encuentre la solución del sistema(si es que existe) usando ladescomposición hallada en el inciso anterior.
26 / 26