sel métodos directoshermes22.yolasite.com/resources/seldirectos_2012ii_uni.pdf · luego,...
Post on 28-Dec-2019
1 Views
Preview:
TRANSCRIPT
SEL Métodos Directos
Mg. Hermes Pantoja Carhuavilca
Universidad Nacional de IngenieriaFacultad de Ingenieria Mecánica
Métodos Numérico
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Agenda
Métodos DirectosGeneralidades sobre Métodos DirectosEliminación GaussianaPivoteoFactorización LU
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos Directos3 Generalidades sobre
Métodos Directos
Eliminación Gaussiana
Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Generalidades sobre métodos directos
I Encuentra una solución en un número finito deoperaciones(en ausencia de errores de redondeo)transformando el sistema en un sistema equivalente quesea ”más fácil” de solucionar.
I Triangulares (Superior o Inferior), Diagonales, .
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
4 Eliminación Gaussiana
Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Eliminación Gaussiana
I Usando Operaciones Elementales por Renglones (OER),la matriz A es transformada en una matriz triangularsuperior (todos los elementos debajo de la diagonal soncero).
I Sustitución hacia atrás es usada para resolver unsistema triangular superior
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
5 Eliminación Gaussiana
Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Eliminación Gaussiana
Primer Paso de Eliminación
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
6 Eliminación Gaussiana
Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Eliminación Gaussiana
Segundo Paso de Eliminación
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
7 Eliminación Gaussiana
Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Eliminación Gaussiana
Sustitución Regresiva
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
8 Eliminación Gaussiana
Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Ejemplo
EjemploUtilizando Eliminación Gaussiana resolver:
3x1 + 2x2 + 4x3 = 1x1 + x2 + 2x3 = 2
4x1 + 3x2 − 2x3 = 3
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
9 Eliminación Gaussiana
Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Ejemplo
Método de Eliminación Gaussiana
• Sistema equivalente:
Solución:
08
3/53/21/3
14 2 3
3
32
321
x
xx
xxx
0
5
3
*x
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
10 Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Pivoteo
I Computadoras usan precisión aritmética finita.
I Pequeños errores son introducidos en cada operaciónaritmética, propagación de errores
I Cuando los elementos pivotales son muy pequeños, losmultiplicadores podrían ser muy grandes.
I La adición de números de magnitud diferente puedeconducir a la pérdida de significación.
I Para reducir el error, se realiza intercambio de filas paramaximizar la magnitud del elemento pivotal.
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
11 Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Pivoteo
Ejemplo (Sin Pivoteo)
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
12 Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Pivoteo
Ejemplo (Con Pivoteo)
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
13 Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Procedimiento con Pivoteo
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
14 Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Pivoteo por Filas
I Más comúnmente llamado procedimiento de pivoteoparcial.
I Busque la columna pivotal.
I Encuentre el mas grande elemento en magnitud.
I Luego intercambie esta fila con la fila pivotal.
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
15 Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Pivoteo por Filas
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
16 Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Ejemplo de Pivoteo por Filas
15
7
6
5
0
7
3
1-
4
5-
0
1
2
3-
1
2
0
0
0
3
| )1()1( bA
15
6
7
5
0
3
7
1-
4
0
5-
1
2
1
3-
2
0
0
0
3
| )1()1( bA
3
3||max4
32
22
apivote
ani
i
tenemos 2,k , Para
En la etapa k, escoger para pivote el elemento de mayormódulo entre aik, i=k,k+1,...,n;
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
17 Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Pivoteo Completo
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
18 Pivoteo
Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Ejemplo de Pivoteo Completo
Luego, intercambiamos las filas 2 y 3 y las columnas 2 y 4:
15
7
6
5
0
7
3
1-
4
5-
0
1
2
3-
1
2
0
0
0
3
| )1()1( bA
15
6
7
5
2
1
3-
2
4
0
5-
1
0
3
7
1-
0
0
0
3
| )1()1( bA
77||max4 34
2,
apivoanji
ij tenemos 2,ke Para
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
Pivoteo
19 Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Algoritmo de la factorización LU
Descomposición de una matriz como producto de dostriangularesSupongamos que la matriz de un sistema Ax = b se puededescomponer como A = LU, con L triángular inferior y Utriangular superior.
LUx = b,⇔ Ly = b, Ux = y
TeoremaUna matriz cuadrada A es factorizable LU si y solo si en elalgoritmo de Gauss para encontrar una matriz escalonadapor filas que sea equivalente por filas a la matriz A no esnecesario aplicar operaciones elementales ( de filas).
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
Pivoteo
20 Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Diferentes Formas de Factorización
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
Pivoteo
21 Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Forma de Crout
I Cálculo de la primera columna de L li1 = ai1
I Cálculo de la primera fila de U u1j =a1jl11
I Cálculo alternado de las columnas de L y filas de U
lij = aij −∑
aj−1k=1likukj j ≤ i , i = 1, 2, . . . , n
uij =aij −
∑ai−1
k=1likukjlii
i ≤ j , j = 2, 3, . . . , n
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
Pivoteo
22 Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Crout
Descomposición de Cholesky
Descomposición de Cholesky. Sea A una matriz siméticay definida positiva, existe una única matriz triangular inferiorL con lii > 0 tal que
A = LLT
Esto esa11 a12 . . . a1na21 a22 . . . a2n...
... . . . ...an1 an2 . . . ann
=
l11 0 0 0l21 l22 . . . 0...
... . . . ...ln1 ln2 . . . lnn
l11 l12 . . . l1n0 l22 . . . l2n...
... . . . ...0 0 . . . lnn
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
Pivoteo
24 Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Descomposición de Cholesky
Note queI
a11 = l211 ⇒ l11 =√a11
l11 es un número real positivo ya que a11 > 0 por que Aes definida positiva.
I
ai1 = li1l11 ⇒ li1 =ai1l11
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
Pivoteo
25 Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Descomposición de Cholesky
I Como
aij = li1lj1 + li2lj2 + . . . + lij ljj ; j = 1, 2, . . . , i − 1
luego
lij =aij −
∑aj−1
k=1lik ljkljj
; j = 1, 2, . . . , i − 1
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
Pivoteo
26 Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Descomposición de Cholesky
I Ademásaii = l2i1 + . . . + l2ii
lo que implica
lii =[aii −
i−1∑k=1
l2ik
] 12
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
Pivoteo
27 Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Descomposición de Cholesky-MatLab
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
Pivoteo
28 Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Ejemplo:
EjemploDada la matriz A
A =
6 15 5515 55 22555 225 979
Factorizar utilizando descomposición de Cholesky.Solución:A es simetrica y definida positiva, en efecto:det(6) > 0;
det(
6 1515 55
)= 105 > 0
det(A) = 3920 > 0
29
SEL MétodosDirectos
Mg. HermesPantoja C.
Métodos DirectosGeneralidades sobreMétodos Directos
Eliminación Gaussiana
Pivoteo
29 Factorización LU
Universidad Nacional deIngenieria
Facultad de IngenieriaMecánica
Continuación
top related