resolución de sistema de ecuaciones...

Metodos Iterativos Normas de vectores y matrices

Resolucion de Sistema de EcuacionesLineales

Hermes Pantoja Carhuavilca

Facultad de Ingenierıa IndustrialUniversidad Nacional Mayor de San Marcos

Metodos ComputacionalesHermes Pantoja Carhuavilca 1 de 28


CONTENIDO

Metodos IterativosIntroduccionDefinicionMetodos IterativosMetodo de JacobiConvergenciaMetodo de Gauss Seidel

Normas de vectores y matricesCriterios de Parada

Hermes Pantoja Carhuavilca 2 de 28


INTRODUCCION

La ventaja frente a los metodos directos es que son menossensibles a los errores de redondeo y esto se aprecia en sistemasde orden elevado donde los errores de redondeo de losmetodos directos son considerables.

Metodos Iterativos Hermes Pantoja Carhuavilca 3 de 28


Definicion de Metodo IterativoUn metodo iterativo construye una sucesion de vectores x(k) talque

lımk→∞

x(k) = x

siendo x la solucion del sistema Ax = b.

Construccion de un metodo iterativoSe parte de una aproximacion inicial x(0) y luego se calcula

x(k+1) = F(x(k)) k = 0, 1, . . . ,

donde F se toma de forma lineal: F(x) = Tx + c.

x(k+1) = Tx(k) + c k = 0, 1, . . . ,

La matriz T se denomina matriz de iteracion.



DIFERENTES METODOS ITERATIVOS

I Metodo de JacobiI Metodo de Gauss-Seidel



METODO DE JACOBI

El metodo Jacobi es el metodo iterativo para resolver sistemasde ecuaciones lineales mas simple y se aplica solo a sistemascuadrados, es decir a sistemas con tantas incognitas comoecuaciones.



METODO DE JACOBI



FORMA MATRICIAL

Sea el sistema Ax = b, donde

A =

a11 a12 . . . a1na21 a22 . . . a2n...

.... . .

...an1 an2 . . . ann

trabajamos sobre la siguiente particion de A:

D =

a11 0 . . . 0

0 a22. . .

......

.... . . 0

0 . . . 0 ann

,L =

0 0 . . . 0−a21 0 . . . 0

......

. . ....

−an1 −an2 . . . 0



U =

0 −a12

... −a1n0 0 . . . −a2n...

.... . .

...0 0 . . . 0

De tal forma que:

A = D− L−U

x(k+1) = D−1(L + U)x(k) + D−1b

Tj = D−1(L + U),Matriz de Iteracion de Jacobic = D−1b



EJEMPLO

EjemploSea el sistema (

7 −6−8 9

)(x1x2

)=(

3−4

)

Aproximar la solucion utilizando el metodo de Jacobi. x01 = 0 y

x02 = 0



CONVERGENCIA

DefinicionA es de diagonal estrictamente dominante si para cada fila i se cumple:

|aii| >n∑

j=1;j6=i

|aij|

Una matriz se dice matriz diagonalmente dominante, si en cadauno de los renglones, el valor absoluto del elemento de ladiagonal principal es mayor que la suma de los valoresabsolutos de los elementos restantes del mismo renglon. Aveces la matriz de un sistema de ecuaciones no esdiagonalmente dominante pero cuando se cambian el orden delas ecuaciones y las incognitas el nuevo sistema puede tenermatriz de coeficientes diagonalmente dominante.



TeoremaSi A es una matriz diagonalmente estrictamente dominante, entoncesla iteracion de Jacobi converge para cualquier valor inicial

En ciertas ocasiones al aplicar Jacobi la matriz no esdiagonalmente dominante y por tanto no existira garantıa deconvergencia. Sin embargo, en algunos casos sera posiblereordenar las incognitas en otra manera de forma que la nuevamatriz de coeficientes sea diagonalmente dominante. Esto sepuede detectar revisando todos los posibles ordenamientos delas incognitas y ver como es la matriz resultante. Claro que estoconlleva un bueno numero de pruebas pues el numero posiblede ordenamientos en n variables es (n− 1)! pero cuando n esreducido es sencillo.



Definicion (Polinomio Caracterıstico)P(λ) = det(A− λI)

Definicion (Espectro)Se llama espectro ”ξ” de la matriz A al conjunto de soluciones de laecuacion P(λ) = 0

Definicion (Radio Espectral)Radio espectral de la matriz A: ρ(A) = Max{|λ|}, λ ∈ ξ



TeoremaLa sucesion x(k+1) = Tx(k) + c, para k ≥ 0 converge a la solucionunica x = Tx + c si y solo si ρ(T) < 1.

EjemploAnalizar la convergencia del siguiente sistema lineal

x1 + x2 = 3x1 − 3x2 = −3



El metodo de Gauss-Seidel es muy semejante al metodo deJacobi. Mientras que en el de Jacobi se utiliza el valor de lasincognitas para determinar una nueva aproximacion, en el deGauss-Seidel se va utilizando los valores de las incognitasrecien calculados en la misma iteracion, y no en la siguiente.



METODO DE GAUSS SEIDEL



EJEMPLO

EjemploSea el sistema (

7 −6−8 9

)(x1x2

)=(

3−4

)

Aproximar la solucion utilizando el metodo de Gauss Seidel.x0

1 = 0 y x02 = 0



FORMA MATRICIAL

A = D− L−U

x(k+1) = (D− L)−1Ux(k) + (D− L)−1b

Tgs = (D− L)−1U,Matriz de Iteracion de Gauss Seidelc = (D− L)−1b



TeoremaSi A es una matriz diagonalmente estrictamente dominante, entoncesla iteracion de Guass Seidel converge para cualquier valor inicial



NORMA VECTORIAL

Una norma vectorial en Rn es una funcion ||.||, de Rn en R conlas siguientes propiedades:

I ||x|| ≥ 0 para todo x ∈ Rn.

I ||x|| = 0 si y solo si x = (0, 0, ..., 0)t.I ||ax|| = |a|||x|| para todo a ∈ R y x ∈ Rn.I ||x + y|| ≤ ||x||+ ||y|| para todo x, y ∈ Rn.

Para nuestro proposito solo necesitaremos dos normasespecıficas de Rn

Normas de vectores y matrices Hermes Pantoja Carhuavilca 20 de 28


VECTOR EN Rn

El vector

x =

x1x2...

xn

Se denotara por: x = (x1, x2, . . . , xn)t



DEFINICIONES



EJEMPLO

Ejemplo

El vector x = (−1, 1,−2)t en R3 tiene normas||x||2 =

√(−1)2 + (1)2 + (−2)2 =

√6

||x||∞ = max{| − 1|, |1|, | − 2|} = 2



DEFINICIONES

Si x = (x1, x2, . . . , xn)t y y = (y1, y2, . . . , yn)t son vectores en Rn

las distancias l2 y l∞ entre x e y estan definidas por

||x− y||2 ={ n∑

i=1

|xi − yi|2}1

2

||x− y||∞ = max1≤i≤n|xi − yi|



NORMA MATRICIALUna norma matricial en Rn×n es una funcion ||.||, de Rn×n en Rcon las siguientes propiedades:

I ||A|| ≥ 0 para todo A ∈ Rn×n.

I ||A|| = 0 si y solo si A es 0.I ||αA|| = |α|||A|| para todo α ∈ R y A ∈ Rn×n.I ||A + B|| ≤ ||A||+ ||B|| para todo A,B ∈ Rn×n.I ||AB|| ≤ ||A||||B||

Teorema (Norma Matricial)Si A = (aij) es una matriz de n× n, entonces

||A||∞ = max1≤i≤n

n∑j=1

|aij|



TeoremaSi A es una matriz real de n× n entonces

I [ρ(At.A)]12 = ||A||2

I ρ(A) ≤ ||A|| para cualquier norma ||.||



CRITERIOS DE PARADA

Una vez fijada una toleracia ε, para cuando se cumpla uno ovarios de los siguientes criterios:

I ||x(k+1) − x(k)|| < ε

I||x(k+1) − x(k)||||x(k+1)||

< ε

I ||Ax(k) − b|| < ε



CONDICIONAMIENTO DE UN SISTEMA LINEALSabemos que el condicionamiento influye en la calidad de lasolucion de un problema cualquiera. En particular, en elproblema de hallar la solucion de un sistema lineal nosencontramos con que al comparar el valor exacto del terminoindependiente de un sistema con el calculado puede haberdiscrepancias. En concreto, definiendo el vector residual r en laforma

r = b− b

en donde b es el valor calculado.

TeoremaSi A es una matriz invertible, se verifica

1. ||x− x|| ≤ ||r||||A−1||

2.||x− x|||x||

≤ ||A|||A−1||| ||r||||b||


resolución de sistema de ecuaciones...

Documents