Metodo gauss seidel

1. 0.1MetododeGauss-Seidel
LosmetodosdeGaussyCholeskyhacenpartedelosmetodosdirectoso
nitos.Alcabodeunnumeronitodeoperaciones,enausenciadeerrores
deredondeo,seobtienex

soluciondelsistemaAx=b.
ElmetododeGauss-Seidelhacepartedelosmetodosllamadosindirectoso
iterativos.Enellossecomienzaconx
0
=(x
0
1
;x
0
2
;:::;x
0
n
),unaaproximacion
inicialdelasolucion.Apartirdex
0
seconstruyeunanuevaaproximacionde
lasolucion,x
1
=(x
1
1;x
1
2;:::;x
1
n).Apartirdex
1
seconstruyex
2
(aquelsu-
perndiceindicalaiteracionynoindicaunapotencia).Assucesivamentese
construyeunasucesiondevectoresfx
k
g,conelobjetivo,nosiempregaran-
tizado,deque
lim
k!1
x
k
=x

:
Generalmentelosmetodosindirectossonunabuenaopcioncuandolamatriz
esmuygrandeydispersaorala(sparse),esdecir,cuandoelnumerode
elementosnonulosespeque~nocomparadoconn
2
,numerototaldeelementos
deA.Enestoscasossedebeutilizarunaestructuradedatosadecuadaque
permitaalmacenarunicamenteloselementosnonulos.
EncadaiteraciondelmetododeGauss-Seidel,haynsubiteraciones.Enla
primerasubiteracionsemodicaunicamentex1.Lasdemascoordenadasx2,
x3,...,xnnosemodican.Elcalculodex1sehacedetalmaneraquese
satisfagalaprimeraecuacion.
x
1
1=
b1(a12x
0
2
+a13x
0
3
++a1nx
0
n
)
a11
;
x
1
i
=x
0
i
;i=2;:::;n:
Enlasegundasubiteracionsemodicaunicamentex2.Lasdemascoorde-
nadasx1,x3,...,xnnosemodican.Elcalculodex2sehacedetalmanera
quesesatisfagalasegundaecuacion.
x
2
2
=
b2(a21x
1
1
+a23x
1
3
++a2nx
1
n
)
a22
;
x
2
i=x
1
i;i=1;3;:::;n:
Assucesivamente,enlan-esimasubiteracionsemodicaunicamentexn.
Lasdemascoordenadasx1,x2,...,xn1nosemodican.Elcalculodexnse
1

2. hacedetalmaneraquesesatisfagalan-esimaecuacion.
x
n
n=
bn(an1x
n1
1
+an3x
n1
3
++annx
n1
n
)
ann
;
x
n
i
=x
n1
i
;i=1;2;:::;n1:
Ejemplo0.1.Resolver
2
6
6
4
10210
12023
21300
12320
3
7
7
5
2
6
6
4
x1
x2
x3
x4
3
7
7
5
=
2
6
6
4
26
15
53
47
3
7
7
5
partiendodex
0
=(1;2;3;4).
x
1
1
=
26(22+(1)3+04)
10
=2:5;
x
1
=(2:5;2;3;4):
x
2
2
=
15(12:5+(2)3+34)
20
=1:175;
x
2
=(2:5;1:175;3;4):
x
3
3
=
53(22:5+1(1:175)+04)
30
=1:9725;
x
3
=(2:5;1:175;1:9725;4):
x
4
4=
47(12:5+2(1:175)+31:9725)
20
=2:0466;
x
4
=(2:5;1:175;1:9725;2:0466):
Unavezquesehahechounaiteracioncompleta(nsubiteraciones),seutiliza
elultimoxobtenidocomoaproximacioninicialysevuelveaempezar;se
calculax1detalmaneraquesesatisfagalaprimeraecuacion,luegosecalcula
x2...Acontinuacionestanlasiteracionessiguientesparaelejemploanterior.
3.03231.17501.97252.0466
3.03231.01141.97252.0466
3.03231.01142.00252.0466
3.03231.01142.00251.9991
2

3. 3.00251.01142.00251.9991
3.00250.99972.00251.9991
3.00250.99972.00021.9991
3.00250.99972.00021.9998
3.00000.99972.00021.9998
3.00001.00002.00021.9998
3.00001.00002.00001.9998
3.00001.00002.00002.0000
3.00001.00002.00002.0000
3.00001.00002.00002.0000
3.00001.00002.00002.0000
3.00001.00002.00002.0000
Teoricamente,elmetododeGauss-Seidelpuedeserunprocesoinnito.En
lapracticaelprocesoseacabacuandodex
k
ax
k+n
loscambiossonmuy
peque~nos.Estoquieredecirqueelxactualescasilasolucionx

.
Comoelmetodonosiempreconverge,entoncesotradetenciondelproceso,
nodeseadaperoposible,estadeterminadacuandoelnumerodeiteraciones
realizadasesigualaunnumeromaximodeiteracionesprevisto.
Elsiguienteejemplonoesconvergente,nisiquieraempezandodeunaaprox-
imacioninicialmuycercanaalasolucion.Lasolucionexactaesx=(1;1;1).
Ejemplo0.2.Resolver
2
4
1210
1112
152
3
5
2
4
x1
x2
x3
3
5=
2
4
11
12
8
3
5
partiendodex
0
=(1:0001;1:0001;1:0001).
1.00121.00011.0001
1.00121.01341.0001
1.00121.01340.9660
0.68631.01340.9660
0.68632.51890.9660
0.68632.51899.9541
3

4. 83.50312.5189 9.9541
83.5031926.4428 9.9541
83.5031926.44282353.8586
AlgunoscriteriosgarantizanlaconvergenciadelmetododeGauss-Seidel.
Porsercondicionessucientesparalaconvergenciasoncriteriosdemasiado
fuertes,esdecir,lamatrizApuedenocumplirestosrequisitosysinembargo
elmetodopuedeserconvergente.Enlapractica,confrecuencia,esmuy
dispendiosopoderaplicarestoscriterios.
Unamatrizcuadradaesdediagonalestrictamentedominanteporlas
siencadalaelvalorabsolutodelelementodiagonalesmayorquelasuma
delosvaloresabsolutosdelosotroselementosdelala,
jaiij>
n
X
j=1;j6=i
jaijj;8i:
Teorema0.1.SiAesdediagonalestrictamentedominanteporlas,en-
tonceselmetododeGauss-Seidelconvergeparacualquierx
0
inicial.
Teorema0.2.SiAesdenidapositiva,entonceselmetododeGauss-Seidel
convergeparacualquierx
0
inicial.
TeoricamenteelmetododeGauss-Seidelsedeberadetenercuandokx
k

x

k<".Sinembargolacondicionanteriornecesitaconocerx

,queespre-
cisamenteloqueseestabuscando.Entonces,demanerapracticaelmetodo
deGSsedetienecuandokx
k
x
k+n
k<".
Dejandodeladolossuperndices,lasformulasdelmetododeGauss-Seidelse
puedenreescribirparafacilitarelalgoritmoyparamostrarquekx
k
x

ky
kx
k
x
k+n
kestanrelacionadas.
xi
bi
n
X
j=1;j6=i
aijxj
aii
;
xi
bi
n
X
j=1
aijxj+aiixi
aii
;
4

5. xi xi+
biAix
aii
:
Sean
ri=biAix;
i=
ri
aii

Elvalorriessimplementeelerror,residuoorestoquesecometeenlai-esima
ecuacionalutilizarelxactual.Siri=0,entonceslaecuacioni-esimase
satisfaceperfectamente.Elvalorieslamodicacionquesufrexienuna
iteracion.
Seanr=(r1;r2;:::;rn),=(1;2;:::;n).Entoncesx
k+n
=x
k
+.Ademas
x
k
essolucionsiysolamentesir=0,osea,siysolamente=0.Lo
anteriorjusticaqueelmetododeGSsedetengacuandokk".Lanorma
kkpuedeserlanormaeuclidianaomaxjijo
P
jij.
Sienelcriteriodeparadadelalgoritmosedeseaenfatizarsobreloserroreso
residuos,entoncessepuedecompararkkcon"=k(a11;:::;ann)k;porejemplo,
kk
"
maxjaiij

Elesquemadelalgoritmopararesolverunsistemadeecuacionesporel
metododeGauss-Seideles:
datos:A;b;x
0
;",maxit
x=x
0
parak=1;:::;maxit
nrmD 0
parai=1;:::;n
i=(biprodEsc(Ai;x))=aii
xi xi+i
nrmd nrmD+i
n-parai
sinrmD"entx

x,salir
n-parak
5

6. 0.2Solucionpormnimoscuadrados
ConsideremosahoraunsistemadeecuacionesAx=b,nonecesariamente
cuadrado,dondeAesunamatrizmncuyascolumnassonlinealmente
independientes.Estoimplicaquehaymaslasquecolumnas,mn,y
queademaselrangodeAesn.Esmuyprobablequeestesistemanotenga
solucion,esdecir,talveznoexistexquecumplaexactamentelasmigual-
dades.Sedeseaque
Ax=b;
Axb=0;
kAxbk=0;
kAxbk2=0;
kAxbk
2
2
=0:
EsPosiblequelodeseadonosecumpla,entoncessequierequeelincumplim-
iento(elerror)sealomaspeque~noposible.Sedeseaminimizaresacantidad,
minkAxbk
2
2
: (1)
ElvectorxqueminimicekAxbk
2
2
sellamasolucionpormnimoscuadrados.
Comoseveramasadelante,talxexisteyesunico(suponiendoquelas
columnasdeAsonlinealmenteindependientes).
Conelanimodehacermasclaraladeduccion,supongamosqueAesuna
matriz43.Seaf(x)=kAxbk
2
2
,
f(x)=(a11x1+a12x2+a13x3b1)
2
+(a21x1+a22x2+a23x3b2)
2
+
(a31x1+a32x2+a33x3b3)
2
+(a41x1+a42x2+a43x3b4)
2
:
0.2.1Ecuacionesnormales
Paraobtenerelmnimodefserequierequelastresderivadasparciales,
@f=@x1,@f=@x2y@f=@x3,seannulas.
@f
@x1
=2(a11x1+a12x2+a13x3b1)a11
+2(a21x1+a22x2+a23x3b2)a21
6

7. +2(a31x1+a32x2+a33x3b3)a31
+2(a41x1+a42x2+a43x3b4)a41:
Escribiendodemaneramatricial,
@f
@x1
=2(A1xb1)a11+2(A2xb2)a21+2(A3xb3)a31
+2(A4xb4)a41:
SiBesunamatrizyuunvectorcolumna,entonces(Bu)i=Biu.
@f
@x1
=2

((Ax)1b1)a11+((Ax)2b2)a21+((Ax)3b3)a31
+((Ax)4b4a41

;
=2
4
X
i=1
(Axb)iai1;
=2
4
X
i=1
(A1)i(Axb)i;
=2
4
X
i=1
(A
T
1)i(Axb)i;
=2A
T
1(Axb);
=2

A
T
(Axb)

1
Demanerasemejante
@f
@x2
=2

A
T
(Axb)

2
;
@f
@x3
=2

A
T
(Axb)

3
Igualandoacerolastresderivadasparcialesyquitandoel2setiene

A
T
(Axb)

1
=0;

A
T
(Axb)

2
=0;

A
T
(Axb)

3
=0
7

8. Esdecir,
A
T
(Axb)=0;
A
T
Ax=A
T
b: (2)
Lasecuaciones(2)sellamanecuacionesnormalesparalasolucion(oseu-
dosolucion)deunsistemadeecuacionespormnimoscuadrados.
LamatrizA
T
Aessimetricadetama~nonn.Engeneral,siAesunamatriz
mnderangor,entoncesA
T
Atambienesderangor(ver[Str86]).Como
sesupusoqueelrangodeAesn,entoncesA
T
Aesinvertible.Masaun,A
T
A
esdenidapositiva.
PorserA
T
Ainvertible,hayunaunicasolucionde(2),osea,hayunsolo
vectorxquehacequelasderivadasparcialesseannulas.Engeneral,las
derivadasparcialesnulassonsimplementeunacondicionnecesariaparaobtener
elmnimodeunafuncion(tambienloesparamaximosoparapuntosdesilla),
peroenestecaso,comoA
T
Aesdenidapositiva,fesconvexa,yentonces
anularlasderivadasparcialesseconvierteencondicionnecesariaysuciente
paraelmnimo.
Enresumen,silascolumnasdeAsonlinealmenteindependientes,entonces
lasolucionpormnimoscuadradosexisteyesunica.Paraobtenerlasolucion
pormnimoscuadradosseresuelvenlasecuacionesnormales.
ComoA
T
Aesdenidapositiva,(2)sepuederesolverporelmetodode
Cholesky.SimnyalhacerlafactorizaciondeCholeskyresultaque
A
T
Anoesdenidapositiva,entonceslascolumnasdeAsonlinealmente
dependientes.
SielsistemaAx=btienesolucionexacta,estacoincideconlasolucionpor
mnimoscuadrados.
Ejemplo0.3.Resolverpormnimoscuadrados:
2
6
6
4
210
123
221
542
3
7
7
5
2
4
x1
x2
x3
3
5=
2
6
6
4
3:1
8:9
3:1
0:1
3
7
7
5
:
Lasecuacionesnormalesdan:
2
4
342015
202512
151214
3
5
2
4
x1
x2
x3
3
5=
2
4
4:0
20:5
23:4
3
5
8

9. Lasolucionpormnimoscuadradoses:
x=(2:0252;1:0132;2:9728):
Elerror,Axb,es:
2
6
6
4
0:0628
0:0196
0:0039
0:0275
3
7
7
5
:3
Ejemplo0.4.Resolverpormnimoscuadrados:
2
6
6
4
213
120
226
546
3
7
7
5
2
4
x1
x2
x3
3
5=
2
6
6
4
3
9
3
0
3
7
7
5
:
Lasecuacionesnormalesdan:
2
4
342048
202515
481581
3
5
2
4
x1
x2
x3
3
5=
2
4
3
21
27
3
5
AltratarderesolverestesistemadeecuacionesporelmetododeCholesky;
nosepuedeobtenerlafactorizaciondeCholesky,luegoA
T
Anoesdenida
positiva,esdecir,lascolumnasdeAsonlinealmentedependientes.Sise
aplicaelmetododeGauss,seobtienequeA
T
Aessingularyseconcluyeque
lascolumnasdeAsonlinealmentedependientes.3
Ejemplo0.5.Resolverpormnimoscuadrados:
2
6
6
4
21
12
22
54
3
7
7
5

x1
x2

=
2
6
6
4
3
0
6
6
3
7
7
5
:
Lasecuacionesnormalesdan:

3420
2025

x1
x2

=

48
15

Lasolucionpormnimoscuadradoses:
x=(2;1):
9

10. Elerror,Axb,es:
2
6
6
4
0
0
0
0
3
7
7
5
:
Enestecaso,elsistemainicialtenasolucionexactaylasolucionpormnimos
cuadradoscoincideconella.3
Laimplementacionecientedelasolucionpormnimoscuadrados,vaecua-
cionesnormales,debetenerencuentaalgunosdetalles.Noesnecesario
construirtodalamatrizsimetricaA
T
A(n
2
elementos).Bastaconalmacenar
enunarreglodetama~non(n+1)=2lapartetriangularsuperiordeA
T
A.
Estealmacenamientopuedeserporlas,esdecir,primerolosnelementosde
laprimerala,enseguidalosn1elementosdelasegundalaapartirdel
elementodiagonal,despueslosn2delaterceralaapartirdelelemento
diagonalyassucesivamentehastaalmacenarunsoloelementodelalan.Si
sealmacenalapartetriangularsuperiordeA
T
Aporcolumnas,sealmacena
primerounelementodelaprimeracolumna,enseguidadoselementosdela
segundacolumnayassucesivamente.Cadaunadelasdosformastienesus
ventajasydesventajas.LasolucionporelmetododeCholeskydebetener
encuentaestetipodeestructuradealmacenamientodelainformacion.
Otrosmetodosecientespararesolversistemasdeecuacionespormnimos
cuadradosutilizanmatricesortogonalesdeGivensodeHouseholder.
10

11. functiona=interFilas(a,i,j)
t=a(i,:)
a(i,:)=a(j,:)
a(j,:)=t
endfunction
//----------------------------------------------------------
functionx=sistTriSup(a,b)
//soluciondeunsistematriangularsuperior
n=size(a,1)
x=zeros(n,1)
fori=n:-1:1
x(i)=(b(i)-a(i,i+1:n)*x(i+1:n))/a(i,i)
end
endfunction
//----------------------------------------------------------
function[x,y]=interc(x,y)
t=x
x=y
y=t
endfunction
//==========================================================
//==========================================================
//metododeGaussconpivoteoparcial
//nomuyeficiente
a0=[245-10;1234;-10854;-112-2]
b=[-144044-1]'
eps=1.0e-8;
n=size(a0,1)
a=[a0b]
fork=1:n-1
[vmax,pos]=max(abs(a(k:n,k)))
11

12. ifvmax<=eps
printf('Matrizsingularocasisingular.')
return
end
m=k-1+pos
ifm>k
a=interFilas(a,k,m)
end
fori=k+1:n
coef=a(i,k)/a(k,k)
a(i,:)=a(i,:)-coef*a(k,:)
end
end
ifabs(a(n,n))<=eps
printf('Matrizsingularocasisingular.')
return
end
x=sistTriSup(a(:,1:n),a(:,n+1))
//==========================================================
//==========================================================
//metododeCholesky
//resolverAx=b
//Asimetricaydefinidapositiva
//
//factorizaciondeCholeskyA=U'U,Utriangularsuperiorinevertible
//
//Ax=b
//U'Ux=b
//seay=Ux
//U'y=b
//resolverelsistemaanteriorparaobtenery
12

13. //reoslverUx=yparaobtenerx
a=[923;28-1;3-15]
b=[362423]'
n=size(a,1)
y=zeros(n,1);
x=zeros(n,1);
u=chol(a)
y(1)=b(1)/u(1,1)
fori=2:n
y(i)=(b(i)-u(1:i-1,i)'*y(1:i-1))/u(i,i)
end
x(n)=y(n)/u(n,n)
fori=n-1:-1:1
x(i)=(y(i)-u(i,i+1:n)*x(i+1:n))/u(i,i)
end
//==========================================================
//==========================================================
//metododeGauss-Seidel
a=[102-10;120-23;-21300;12320]
b=[26-155347]'
x0=[0000]'
n=size(a,1)
x=x0
maxit=10
fork=1:maxit
13

14. fori=1:n
res=b(i)-a(i,:)*x
x(i)=x(i)+res/a(i,i)
end
end
14