algoriritmo matematicos para sistemas de ecuacions
TRANSCRIPT
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
1/49
Algoritmos matemáticos para:sistemas de ecuaciones lineales
inversión de matrices y mínimoscuadrados
Jose Aguilar
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
2/49
Inversión de matricesDefinición (Inversa de una matriz): Sea A una matriz nxn. Una matriz C de nxnes una inversa de A si CA=AC=I.
Para la matriz no es difícil verificar que la matriz
satisface que
−
−=
21
94 A
=
41
92C
=
−
−
10
01
21
94
41
92
Se dice entonces que la matriz C es una inversa de la matriz A. Esto se define
enseguida:
eorema: Sea A una matriz nxn con inversa C tal que CA=AC=I. Si D es otramatriz nxn tal que AD=I , entonces C=D.
Demostración: !omo la multi"licación de matrices es asociativa# se tiene que
C ( AD)$(CA)D# de donde# como AD=I % CA=I # se tiene que
C ( AD)$CI=C % (CA)D=ID=D# "or tanto# C=D.
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
3/49
Se denotar& la inversa de una matriz A# cuando exista# como A-1. Entonces A
A-1 = A-1 A = I. 'ótese que no se dee ex"resar A-1 como 1/A.
Definición: Una matriz cuadrada que tiene inversa se llama invertile. Una
matriz cuadrada que no tiene inversa se llama singular.
eorema: La matriz
= ba
A
Inversión de matrices
es invertible si ad - bc ≠0 , en cuyo caso la inversa está dada por la fórmula
eorema: Sean A y B matrices invertibles nxn. Entonces
a! AB es invertible
b! " AB !#1 $ B-1 A-1
−−
−
−
−=
−
−
−=
−
bcad
a
bcad
cbcad
b
bcad
d
ac
bd
bcad A
11
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
4/49
inversión de matrices
Propiedades de la inversión de matrices
La matriz inversa, si existe, es única
A-1·A = A·A-1= I
(At ) –1 = (A-1 ) t
(A·B) -1 = B -1·A-1
(A-1 ) -1 = A
(kA) -1 = (1/k) · A-1
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
5/49
inversión de matrices
Observación:
Podemos encontrar matrices que cumplen A·B = I , pero que B·A ≠ I , en talcaso, podemos decir que A es la inversa de B "por la izquierda" o que B es la
inversa de A "por la derecha".
Por el método de Gauss-JordanUsando determinantesDirectamente
Hay varios métodos para calcular la matriz inversa de una matrizdada:
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
6/49
inversión de matrices
Dada la matriz buscamos una matriz que cumpla A·A-1 = I, es decir
Cálculo Directo de la Matriz Inversa
La matriz que se ha calculado realmente sería la inversa por la "derecha", pero es fácilcomprobar que también cumple A-1 · A = I, con lo cual es realmente la inversa de A.
Para ello planteamos el sistema de ecuaciones:
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
7/49
!&lculo de las inversas:Sea A$*aij +una matriz nxn. Para ,allar A
-1 si es que existe# se dee encontrar
una matriz X $* x ij + nxn tal que AX=I # esto es# tal que
=
100
010
001
21
22221
11211
21
22221
11211
⋯
⋮⋱⋮⋮
⋯
⋯
⋯
⋮⋱⋮⋮
⋯
⋯
⋯
⋮⋱⋮⋮
⋯
⋯
nnnn
n
n
nnnn
n
n
x x x
x x x
x x x
aaa
aaa
aaa
Inversión de matrices
Esto es un sistema de ecuaciones con n vectores de incógnitas# % entonces es
"osile a"licar el -todo de /auss01ordan "ara encontrar la inversa de A. 2a
idea es transformar# "or medio de o"eraciones elementales "or filas# lamatriz aumentada del sistema (A,I) a un sistema (I, A-1 )
A-1 (A,I) ⇔⇔⇔⇔ (A-1 A, A-1 I) ⇔⇔⇔⇔ (I, A-1 )
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
8/49
Sistema de ecuaciones lineales
a11x1+a12x2+...+a1nxn=b1
.
.
.
an1x1+an2x2+...+annxn=bn
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
9/49
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
10/49
Métodos directos e iterativosMétodos directos e iterativos
DIRECTOSDIRECTOS
• Ax =b
ITERATIVOSITERATIVOS
• x = Cx + d
• x = A-1 b
• Tamaño pequeño
• x(k+1) = Cx(k) + d• Tamaño grande
x=A-1b
Limx->∞
=Cx+d
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
11/49
Sistema de ecuaciones lineales
2x1+3x2=2
x1+x2=3
x2=2/3-(2/3)x1
x2=3-x1
3-x1=2/3-(2/3)x1 3-2/3 =x1-(2/3)x1
2.333=0.333x1 x1=7
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
12/49
Método de JacobiMétodo de Jacobi
A L D U
x D (b (L U)x )(k 1) 1 (k)
= + +
= − ++ −
- U=triang. sup; L=triang. Inf.
- D=diag(A);
La ecuación A x = b se transforma en (D - L - U ) x = b x = (L + U ) x + b
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
13/49
5lgoritmo -todo de 1acoi5lgoritmo -todo de 1acoi
función 1acoi (5#)
66 x( es una a"roximación inicial a la solución66
7$8
Mientras no convergencia
y=0
para 3$9 hasta n
si 3≠i entonces
%$%aij x j*
xi*+1= (bi-y)/aii
K=K+1
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
14/49
Método de Gauss-SeidelMétodo de Gauss-Seidel
x (b a x a x a x )/a
1
(k+1)
1
k+1
12 2
(k)
13 3
(k)
1n n
(k)
11
k+1 k k
= − − −
⋯
x (b
x (b
a x a x a x )/a
a x a x a x )/a
2 2
3
(k+1)
3
n
(k+1)
n
21 1 23 3 2n n 22
31 1
(k+1)
32 2
(k+1)
3n n
(k)
33
n1 1
(k+1)
n2 2
(k+1)
n,n 1 n 1
(k+1)
nn
= −
= −
= −
− −
− −
− −
− −
⋮
⋯
⋯
⋮ ⋮ ⋱ ⋮
⋯
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
15/49
Modelo matricialModelo matricial
A L D U
(L D)x b Uxx (L D) (b Ux )
(k 1) (k)
(k 1) 1 (k)
= + +
+ = −= + −
+
+ −
- D = diag(A)
- U=triang. Sup; L=triang inf
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
16/49
Algoritmo Método de Gauss-SeidelAlgoritmo Método de Gauss-Seidel
función /aussi (5# x# )
66 x( es una a"roximación inicial a la solución66para ;$9 hasta convergencia
para $ as a ny=0
para 3$9 hasta n
si 3≠i entonces
%$%aij x j
xi= (bi-y)/aii
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
17/49
APROXIMACIÓN ! M"NIMO#
C$ARAO#
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
18/49
-odelado de datos• El modelado de datos se "uede ex"resar de la
siguiente forma:
• Dadas:
– Una colección finita de datos
– Una forma funcional
•
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
19/49
Para comprender datos experimentales, deseamosdeterminar una recta o una curva que “encaje” o “se ajuste”más (o describa mejor) estos datos
Imaginemos la siguiente tabla con los pasados de un cursoen semestres pasados.
Curso 1 2 3 4 5 6
E3em"lo
Si quisiéramos trazar una recta que acerque a los puntos en latabla hay muchas opciones. Sin embargo, hay una que se ajustamejor a estos datos, bajo cierto criterio.
Caso anterior es y = 0.13333 + 0.05 x
Porcentajede pasados
0.70 0.75 0.80 0.80 0.85 0.80
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
20/49
La relación entre dos variables métricas puede serrepresentada mediante la línea de mejor ajuste a los datos.Esta recta se le denomina rectarecta dede regresión,regresión, ypuede sernegativa o positiva, la primera con tendencia decreciente y la
segunda creciente.
GRÁFI!" $E $I"%ER"I&' ( RE)* $E REGRE"I&'
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
21/49
%ara el c+lculo de la recta de regresión se aplica el método demínimos cuadrados entre dos variables.
Esta línea es la ue -ace mínima la suma de los cuadrados delos residuos.
GRÁFI!" $E $I"%ER"I&' ( RE)* $E REGRE"I&'
.
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
22/49
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
23/49
!riterio de los minimos cuadrados• =ormulacion del a3uste "or -inimos
cuadrados:
( ) ( )21
, N
k J a b k ε
== ∑
donde N es el numero de datos entrada-salida dado
y f xε = −
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
24/49
Llamemos a “u” perturbación o error, siendo la diferencia que hay entre el
valor observado de la variable exógena (y) y el valor estimado que
obtendremos a través de la recta de regresión .
La metodología para la obtención de la recta será hacer MÍNIMA la suma delos CUADRADOS de las erturbaciones. Por ué se elevan al cuadrado?
ˆ i y
ii
bxa y +=∧
2 2ˆ( )i i iu y y= − 2 2
1 1
ˆ( )n n
i i i
i i
u y y= =
= −∑ ∑
( ) 22 2
, 1 1 1
ˆ( )minn n n
i i i i iq p i i i
x pu q y y y= = =
= − = − +
∑ ∑ ∑ a b
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
25/49
Un "rolema de o"timizacion• 5"roximaciones com"utacionales:
– 5lgoritmos numricos generales "ara la minimización deuna función
,allar raíces? algoritmos que a"rovec,an la forma de la función
– 5lgoritmos con una a"roximación asada en la inteligenciaartificial: algoritmos genticos
• Solución analítica: mínimos cuadrados lineal
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
26/49
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
27/49
E3em"lo: una entrada# una salida
8
10
12
14
16
Y
0
2
4
6
0 1 2 3 4 5 6 7 8 9 10
X
¿Como podemos modelar el proceso que genera estos datos?
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
28/49
E3em"lo: dos entradas# una salida
0 2 3,1 ,5 ,6
2 4 6
T Z
=
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
29/49
-odelos lineales vs . 'o lineales• Es com4n asumir que f (u) "ertenece a una
familia de funciones que com"arten la mismaestructura % difieren "or los valores tomados
.
( ), y f u θ =
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
30/49
El modelo lineal• Un modelo lineal asume que la función es
lineal res"ecto a los parámetros θ
( ) ( ) ( ) ( )1 1 2 2, q q f u f u f u f uθ θ θ θ = + + +⋯
Aquí, la linealidad se refiera a “conrespecto a los parametros”
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
31/49
-odelos no0lineales• En los modelos no0lineales la función es no0
lineal res"ecto a los paramtros θ
( ) ( ), exp f u uθ θ = −
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
32/49
Estimación de -ínimos !uadrados
2inealDada una colección finita de observaciones
Z N
= {u (0), y (0), u (1), y (1), ..., u (N ), y (N )}
UY
ˆt tProceso
Modelo
Regresor lineal
y g u=
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
33/49
• El mtodo de regresión de mínimos cuadradosconsiste en encontrar la curva o función que me3or se
a3uste a una serie de "untos (@i#Ai)# otenidosgeneralmente a "artir de un ex"erimento.
Mínimos Cuadrados
entre la función % los datos oservados.
• El caso o e3em"lo m&s sencillo es el a3uste de una
función lineal a la serie de "untos.
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
34/49
Re%resión &inea&Se asume que la relación entrada0salida "uede ser
descrita "or una estructura de re%resor &inea&
f (u,θ ) es denominada la funcion de ajuste . Las f i (u ) sondenominadas las funciones base
( ) ( ) ( ) ( )1 1 2 2, q q f u f u f u f uθ θ θ θ ε = + + + +⋯
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
35/49
5lgunas funciones ase• =unciones "olinomiales
• =unciones ase /ausianas
( ) j j
f u u=
• =unciones ase Sigmoidales
• =ourier Bavelets
( ) ( )2exp 2 j
j
u f u
σ
−
= −
1( )
1 exp( ) j
f ua
=+ −
R ióR ió 'i &'i & BXAY ++
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
36/49
Re%resiónRe%resión 'inea&'inea&
La gráfica muestra elajuste de la nube depuntos a una línea recta
e BX AY ++=
Como los datos X, Y,
objetivo es entoncesencontrar los mejoresvalores para los
coeficientes A, B, talque e 0.
e representa las diferencias entre elmodelo lineal y las observaciones
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
37/49
2os errores cometidos• Dados unos datos % el modelo
lineal# deseamos calcular los
Cme3ores "ar&metros.
• ueremos minimizar oserrores.
error
Error en la a"roximación
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
38/49
Error en la a"roximación
Y
(e i = Yi – A - B*Xi)
El objetivo es minimizarel error cometido con laaproximación
X
Xi
Éste se representa comola distancia entre el valorreal y el aproximado
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
39/49
2os residuos• El a3uste de minimos cuadrados ,alla el vector
de "arametros - tal que se minimiza
1 N
( ) ( ) ( )( )ˆ ,k y k f u k ε θ = −
1k N ε ==
residuos = errores
! it i l 3 3 t
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
40/49
!riterio "ara el me3or a3uste
• !omo se tiene una serie de n "untos (@i# Ai)(i$9#F#n)# la acumulación de los errores ser&:
−−=
nn
BX Y e
• Para que los valores de error "ositivos % negativos
no se cancelen entre sí# stos se deen elevar alcuadrado
== ii 11
! l ió d
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
41/49
!ancelación de erroresF
• Para este e3em"lo dedos "untos# los errores
e9 % eG se cancelan.
• 2a suma de los errores $
Y
X1 X22
11
2 )(∑∑==
−−=n
i
ii
n
i
i BX AY e
Regresión LinealRegresión Lineal
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
42/49
∑∑ == −−==n
i
ii
n
i
i BX AY eS 1
2
1
2 )(
Regresión LinealRegresión Lineal
• Sea:
• !omo el o3etivo es encontrar 5 % ># tal que Ssea mínimo# "ara esto se deriva S
"arcialmente con res"ecto a 5 % >
res"ectivamente % se igualan a cero
#istema de ecuaciones para encontrar A y (
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
43/49
#istema de ecuaciones para encontrar A y (
• 2as derivadas "arciales de S con res"ecto a 5 %
a > se ,acen cero# así:
∂S
∑ =−−−=
∂
∂
=−−−=
∂
0))((2 X BX AY
B
S A
(2)
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
44/49
En resumen las fórmulas para calcular los coeficientes A y B de unafunción lineal de regresión con sólo dos tipos de variables X y Y son:
Regresión LinealRegresión Lineal -- FórmulasFórmulas
N
X BY A −=
∑ ∑∑ = ==
= ==
−
−−
=
N
i
N
i
ii N
i
i
i
ii
Y N
Y X N
X
X X
B1 1
1
2
1 1;1;
)(
Regresión LinealRegresión Lineal -- AlgoritmoAlgoritmo
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
45/49
Regresión LinealRegresión Lineal AlgoritmoAlgoritmo
Entrada: '4mero de datos n# datos )*+y,
sumx # sumy # sumxy # sumx% $ 8
i$8
Mientras iH$n09
sum%$sum%%(i)sumxG$sumxG(x(i)x(i))
sumx%$sumx%(x(i)%(i))
i$i9
enominador $sumxsum%0nsumxG
a$(sumxsum%0nsumx%)6Denominador
b$(sumxsumx%0sumxGsum%)6Denominador
Im"rimir a %
Regresión No LinealRegresión No Lineal
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
46/49
: AX Y Potencia B=
Regresión No LinealRegresión No Lineal
Hay ocasiones en las cuales la relación existente entre X y Y no es lineal, sinembargo ésta puede ser descrita por algún otro tipo de función. EJ:
2
2210
:
...:
)()(
)()();(:
:
CX BX AY Parabólica
X A X A X A AY Polinómica
A Log BX Y Log
A Log X BLogY X BLog AY a Logarítmic
AeY l Exponencia
N N
ee
++=
++++=
+=
+=+=
=
3. Regresión No Lineal3. Regresión No Lineal
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
47/49
• Relación no-lineal entre lasvariables X y Y.
3. Regresión No Lineal3. Regresión No Lineal
Y
• Posiblementeparabólica???
X
RegresiónRegresión nono--lineal:lineal: PotenciaPotencia:
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
48/49
RegresiónRegresión nono lineal:lineal: PotenciaPotencia:
B AX Y =
( )
X Log
X Log
N
Y Log X Log
Y Log X Log
B N
ii N
i
N
i
N
ii
N
ii
ii
2
12
1
11
)(
)(
)()(
)(*)(
∑
−∑
∑
∑
∑
−
=
=
=
==
;;
i 1=
∑
−
∑
= ==
N
X Log
B N
Y Log
A
N
i
i
N
i
i
11
)()(
exp
RegresiónRegresión nono--lineal:lineal: ExponencialExponencial:
-
8/19/2019 Algoriritmo matematicos para sistemas de ecuacions
49/49
RegresiónRegresión nono lineal:lineal: ExponencialExponencial:
BX AeY =
( )2
11
2
111
1
)(
1
)(
∑−∑
∑
∑−∑=
==
===
N
ii
N
ii
N
ii
N
ii
N
iii
X N
X
Y Log X N Y Log X B ;;
∑−
∑= ==
N
X B
N
Y Log A
N
ii
N
ii
11
)(exp