Resolución de Sistemas Lineales
Métodos directos
Generalidades
Cbx
AC
bAx
bAx
)2
)1
estable) poco (caro, Algoritmo1
1
Sistemas fáciles de resolver
Matrices diagonalesMatrices triangulares inferioresMatrices triangulares superiores
Métodos Directos: Eliminación de Gauss
Triangularización
operaciones elementales
Sustitución hacia atrás
bxU
bxA
Fase de Reducción
1443
1332
1221
3:
:
2:
48140
10120
43210
43121
81423
33241
43452
43121
fffP
fffP
fffP
Reducción para EG
610057
57
10
21
21
23
1
45
554
59
00
57
57
10
21
21
23
1
2
812057
57
10
21
21
23
1
58120
775021
21
23
1
2
4
7212
5511421
21
23
1
27212
55114
1132
722
55114
132
33233
22133
1221
1
321
321
321
fffff
fffff
ffff
f
xxx
xxx
xxx
Eliminación de Gauss
)()1()1()()1()1(
)()1()()1(
)()(
)()()1(
1
)(
)(
)()()()1(
)1()()(
10
0
1
0
001
,...1,
nk
nnn
nk
nnn
nk
n
kkik
ki
ki
nk
kk
k
kkk
kik
ikkkjik
kij
kij
kkk
bLLxALL
bLxAL
bxA
bmbb
m
m
L
a
amnkjiamaa
ALA
Resolver todo por reducción
213
10672
13
12000
10030067
0010
213
0001
48140
10120
43210
43121
484
12
432
432
432
32
432
4321
x
xxx
xx
xxx
xxxx
Pivoteo
Permutar filas (equivale a premultiplicar A por una matriz P)
fila pivote p Dividir por números
pequeños también puede amplificar los errores numéricos
Guardar un vector de permutación
1
max
0
)(
)(
)()(
)(
kpk
kik
ik
kik
nik
kpk
kkk
a
am
aa
a
Ejemplo: necesidad de pivoteo en EG
3005
2004
0
997.1
6006
4001
0
5000
0
0
5092:500000
300520040
32001.0
60064001.00
300520040
32001.0
3
2
001.0
1000
623.4
712.3
1
3005
2004
0
1997.10
010
001
102000
011000
001
643.5072.12
623.4712.31
32001.0
23233
12
1
2
121221
fmff
VV
AMM
AM
M
fmffM
A
Conclusión
Se hubiera obtenido lo mismo partiendo de:
pivoteo!
~
612
541
32001.0~
yx
byA
bAx
A
Normalización (escalado)
ijnj
i
i
ad
ddiagD
DbDAx
bAx
1max
1
Método de Gauss-Jordan
2
13
106
72
13
12000
1003006
70010
2
130001
12000
763003
21010
53001
4:
2:
2:
2020900
76300
43210
129301
48140
10120
43210
43121
2443
2332
2111
x
fffP
fffP
fffP
Alternativas: EG – desc LU
yUx
bLy
Lyb
LybLL
ybLUx
bLUx
bAx
Resolver3)
Resolver2)
LUA Factorear1)
:Algoritmo
1
1
Factorización LU
iu
il
nnn
n
aaa
aaa
aaa
u
uu
uuu
lll
ll
l
ii
ii
1Crout
1Doolittle
:de Métodos
libertad de grados incógnitas
ecuaciones
00
00
00
2
2
333231
232221
131211
33
2322
131211
333231
2221
11
Ejemplo
2000
4200
6930
6422
12
3
3
2
2
1
0112
5
0012
30001
71111
17185
15363
6422
1000
2100
2310
3211
2321
0235
0033
0002
71111
17185
15363
6422
Algoritmo de factorización LU
jsuisl
ulula
u
uu
uu
uuu
llll
lll
ll
l
sjis
ji
ssjis
n
ssjisij
nn
knkk
n
n
nnnknkn
kkkk
00
000
0
0
0
0
00
),min(
11
222
11211
11
21
2221
11
kkik
k
sskis
k
sskisik
kk
kjkk
k
ssjks
k
ssjkskj
kk
kkkk
k
sskks
k
sskkskk
ji
ssjisij
ululula
uki
ululula
lkj
ululula
ula
1
11
1
11
1
11
),min(
1
0
0
Método de Factorización QR
A=QR Q: ortogonal R: triangular superior
Q-1 = QT
A x = b
QR x = b
Q y = b => y = QT b
R x = y ¿Cómo efectuar la descomposición QR?
Características de Q
Las columnas de Q forman un conjunto ortogonal de vectores
Un conjunto de vectores es ortogonal si y sólo si cada par u,v tal que uv verifica que (u,v) = 0
CM: Encontrar la solución de:
yQRx
yQRRxR
yQRQRxQR
yQRxQRQR
yAAxA
yAx
T
TTT
TTTT
TT
TT
)()()(
Calculo de inversas
1-
22
11
2121
1
AIIA
:práctican Disposició
nn
nn
eAx
eAx
eAx
eeexxxA
AXIAX
Sistemas lineales especiales
1000
7100
6510
4321
4000
0300
0020
0001
1764
0153
0012
0001
4000
21300
121020
4321
1764
0153
0012
0001
23993204
9362163
201662
4321
TLDLA
Factorización de Choleski
TT
M
T MMLDLDLDLA 2
1
2
1
Factorización de Choleski
Esto es posible siempre que A sea: Simétrica Definida positivaEs decir:
00
xAxx
AAT
T
Teorema: factorización de Choleski
0con inferior r triangulaMcon MMA Además,
0con Dy
diagonal laen unoscon inferior r triangulaes L donde LDLAen
pivoteosin EG usando afactorizadser puedeA Entonces
positiva. definiday simétrica Sea
T
T
ii
iiii
nxn
m
dd
A
Cálculo de los elementos de M
! 0 exige
0
00
000
cálculo deOrden
00
000
00
2122222
222
21222
11
111111
11
1212121112
11111121111
222
11211
21
2212
11
mammma
ma
mmma
ma
mmma
aamma
m
mm
mmm
mmm
mm
m
MMA
nnnn
nn
n
n
nnnn
T
Evaluación de determinantes
Teorema: sobre cómo afectan al determinante las operaciones elementales entre filas
Teorema
det(A))Adet(
A de cualquiera fila otra aA de fila una de múltiploun a
adicionar de resulta que matriz la es A Si a)
det(A)-)Adet(
A de filas dos
ar intercambi de resulta que matriz la es A Si b)
det(A)k)Adet(
k constante lapor A de fila una
r multiplica de resulta que matriz la es A Si a)
A Sea mxn
Ejemplo
165)det(
100
510
321
)55(3
5500
510
321
310
5100
510
321
32
162
510
321
3
162
510
963
162
963
510
)det(
162
963
510
1
233
133
A
fff
fff
A
A
Observar:
0
8411
5193
0000
4231
)det(
2
8411
5193
8462
4231
122
A
fff
A
Lectura obligatoria
Gerald págs 104-144