Precondicionamiento de sistemas de ecuaciones de matrices variables en la modelización de campos de viento
Abstract
Programa de Doctorado: Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Full text
Ins i u o Uni e si a io de Sis emas
In eligen es y Aplicaciones Numé icas en
Ingenie ía
Tesis Doc o al
PRECONDICIONAMIENTO DE
SISTEMAS DE ECUACIONES DE
MATRICES VARIABLES EN LA
MODELIZACIÓN DE CAMPOS DE
VIENTO
Héc o Sa mien o Almeida
Las Palmas de G an Cana ia, Ab il de 2010
UNIVERSIDAD DE LAS PALMAS
DE GRAN CANARIA
A mis nie os, Tom´as y Sa a
Ag adecimien os
A An onio Su´a ez Sa mien o y Gus a o Mon e o Ga c´ıa, di ec o es de es a e-
sis, sin cuyo alien o, aseso amien o y u ela no hubie a sido posible la ealizaci´on
de es e abajo.
A Edua do Rod ´ıguez Ba e a que, pacien emen e, me ha ayudado a esol e
los imp e is os y dudas in o m´a icas que ue on su giendo du an e el desa ollo
del ema.
A Ma ´ıa Dolo es Ga c´ıa Le´on y Elizabe h Fl´o ez V´azquez, po su ines imable
colabo aci´on, g acias a las cuales, las ideas y expe imen os necesa ios pa a el de-
sa ollo y p esen aci´on de es a esis, se han hecho ealidad.
A odos los compa˜ne os del Depa amen o de Ma em´a icas que de una o ma
u o a me han animado y ayudado, en odo momen o, a la e minaci´on de es a
esis.
A mi amilia, en especial, po su amable paciencia du an e los la gos iempos
de ausencia que ha supues o pa a ellos mi dedicaci´on a es e ema.
A odos, muchas g acias.
Resumen
En la o mulaci´on ma em´a ica de los modelos de campos de ien o su gen g an-
des sis emas de ecuaciones lineales, ca ac e izados po ene ma ices a iables,
al depende es as de un cie o pa ´ame o, , al que: Ax=bdonde Aes una
ma iz sim´e ica del ipo A=M+ N, siendo M y N dos ma ices, ipo spa se,
di e en es, Sim´e icas De inidas Posi i as (SDP) y el pa ´ame o ≥0.
Los m´e odos basados en los subespacios de K ylo cons i uyen la mejo al e -
na i a pa a la esoluci´on de los sis emas de ecuaciones spa se. En el caso pa icula
de sis emas cuya ma iz es SDP, el m´e odo del G adien e Conjugado, es el que
p esen a los mejo es esul ados
En es a esis se a a de ex ende el uso del algo i mo del G adien e Conjugado
P econdicionado a los sis emas de ecuaciones de ma ices a iables, es udiando los
P econdicionado es m´as adecuados pa a mejo a su con e gencia.
El p esen e abajo es ´a es uc u ado en es pa es.En una p ime a pa e se
desc iben los dis in os ipos de modelizaciones de campos de ien o y el p oceso
de gene aci´on de sus sis emas de ecuaciones lineales de ma ices a iables. En
la segunda pa e se p esen a el es ado del a e de los m´e odos i e a i os pa a la
esoluci´on de sis emas lineales basados en los subespacios de K ylo , analizando
la in luencia de su P econdicionamien o y Reo denaci´on. Y en la e ce a pa e, se
adap a la cons ucci´on de P econdicionado es al caso de los sis emas de ecuaciones
de ma ices a iables. Se ilus a su e icacia median e nume osos expe imen os
num´e icos y se des aca la impo ancia de las ´ecnicas p esen adas en la aplicaci´on
de Algo i mos Gen´e icos, pa a la selecci´on de los pa ´ame os ´op imos del modelo
de ien o.
Finalmen e, se ex aen las conclusiones opo unas y se exponen las posibles
l´ıneas u u as.
´
Indice gene al
1. INTRODUCCI´
ON 1
1.1. ANTECEDENTES.......................... 1
1.2. OBJETIVOS ............................. 3
1.3. METODOLOG´
IA........................... 4
2. CAMPOS DE VIENTO 8
2.1. PRELIMINARES........................... 8
2.2. MODELOS DE CAMPOS DE VIENTO . . . . . . . . . . . . . . 10
2.3. BREVES NOCIONES DE C´
ALCULO VARIACIONAL . . . . . . 13
2.3.1. FUNCIONAL: SU DEFINICI´
ON .............. 13
2.3.2. C´
ALCULO VARIACIONAL . . . . . . . . . . . . . . . . . 14
2.3.3. ECUACIONES DE EULER . . . . . . . . . . . . . . . . . 14
2.3.4. PROBLEMAS VARIACIONALES CON LIGADURAS . . 16
2.4. MODELO DE MASA CONSISTENTE . . . . . . . . . . . . . . . 17
2.5. CONSTRUCCI´
ON DEL CAMPO INICIAL . . . . . . . . . . . . 21
2.5.1. INTERPOLACI´
ON HORIZONTAL . . . . . . . . . . . . . 21
2.5.2. EXTRAPOLACI´
ON VERTICAL . . . . . . . . . . . . . . 22
3. DISCRETIZACI´
ON MEDIANTE ELEMENTOS FINITOS 30
3.1. GENERALIDADES ......................... 30
3.2. MALLAS ADAPTATIVAS . . . . . . . . . . . . . . . . . . . . . 31
3.3. GENERACI´
ON DE MATRICES VARIABLES . . . . . . . . . . . 37
4. ESTIMACI´
ON DE PAR´
AMETROS 39
4.1. CONSIDERACIONES PREVIAS . . . . . . . . . . . . . . . . . . 39
4.2. ALGORITMOS GENETICOS . . . . . . . . . . . . . . . . . . . . 42
´
Indice gene al i
5. M´
ETODOS ITERATIVOS BASADOS EN SUBESPACIOS DE
KRYLOV 47
5.1. PRELIMINARES........................... 47
5.2. SUBESPACIOS DE KRYLOV . . . . . . . . . . . . . . . . . . . . 48
5.3. M´
ETODO DEL GRADIENTE . . . . . . . . . . . . . . . . . . . 50
5.4. M´
ETODO DEL GRADIENTE CONJUGADO . . . . . . . . . . . 53
5.5. OTROS M´
ETODOS DE KRYLOV . . . . . . . . . . . . . . . . . 58
5.5.1. M´
ETODOS DE ORTOGONALIZACI´
ON ......... 59
5.5.2. M´
ETODOS DE BIORTOGONALIZACI´
ON........ 60
5.5.3. M´
ETODOS BASADOS EN LA ECUACI´
ON NORMAL . 64
6. PRECONDICIONAMIENTO 66
6.1. CONSIDERACIONES PREVIAS . . . . . . . . . . . . . . . . . . 66
6.2. CONDICIONAMIENTO DE UN SISTEMA . . . . . . . . . . . . 67
6.3. T´
ECNICAS DE PRECONDICIONAMIENTO . . . . . . . . . . . 69
6.4. M´
ETODO DEL GRADIENTE CONJUGADO PRECONDICIO-
NADO................................. 72
6.5. PRECONDICIONADORES EXPL´
ICITOS E IMPL´
ICITOS . . . 75
6.6. PRECONDICIONADORES EXPL´
ICITOS............. 76
6.6.1. PRECONDICIONADOR AINV . . . . . . . . . . . . . . . 76
6.6.2. PRECONDICIONADOR SAINV . . . . . . . . . . . . . . 79
6.7. PRECONDICIONADORES IMPL´
ICITOS............. 81
6.7.1. POR COMPARACI´
ON CON EL M´
ETODO DE RICHARD-
SON.............................. 81
6.7.2. POR FACTORIZACIONES INCOMPLETAS . . . . . . . 84
7. REORDENACI´
ON 89
7.1. PRELIMINARES........................... 89
7.2. ALGORITMO DE CUTHILL-McKEE INVERSO (RCM) . . . . . 91
7.3. ALGORITMO DEL M´
INIMO VECINO (MN) . . . . . . . . . . . 91
7.4. ALGORITMO DE GEORGE . . . . . . . . . . . . . . . . . . . . 92
7.5. ALGORITMO MULTICOLORING (MC) . . . . . . . . . . . . . 93
´
Indice gene al
8. PRECONDICIONAMIENTO DE SISTEMAS DE MATRIZ VA-
RIABLE 95
8.1. PROPUESTA DE ESTRATEGIA . . . . . . . . . . . . . . . . . . 95
8.2. ADAPTACI´
ON DEL PRECONDICIONADOR SAINV . . . . . . 97
8.3. ADAPTACI´
ON DE LA FACTORIZACI´
ON DE CHOLESKY . . 99
9. EXPERIMENTOS NUM´
ERICOS 102
9.1. APLICACIONES TEST . . . . . . . . . . . . . . . . . . . . . . . 102
9.1.1. PRELIMINARES . . . . . . . . . . . . . . . . . . . . . . . 102
9.1.2. EJEMPLO1 ......................... 104
9.1.3. EJEMPLO2 ......................... 107
9.1.4. EJEMPLO3 ......................... 110
9.2. ELECCI´
ON DEL PAR´
AMETRO ´
OPTIMO ............ 116
9.2.1. PRELIMINARES . . . . . . . . . . . . . . . . . . . . . . . 116
9.2.2. EJEMPLO4 ......................... 118
9.2.3. EJEMPLO5 ......................... 119
9.2.4. AN´
ALISIS DE RESULTADOS . . . . . . . . . . . . . . . 120
10.CONCLUSIONES Y LINEAS FUTURAS 122
10.1.CONCLUSIONES .......................... 122
10.2. LINEAS FUTUTRAS . . . . . . . . . . . . . . . . . . . . . . . . 125
BIBLIOGRAF´
IA ............................. 127
METODOLOG´
IA 4
p econdicionado es, an o expl´ıci os como impl´ıci os.
Expone las ´ecnicas de eo denaci´on y su e ec o en la esoluci´on de sis emas
p econdicionados.
Implemen a los p econdicionado es SAINV y los ob enidos como conse-
cuencia de la ac o izaci´on incomple a de Cholesky, pa a su aplicaci´on a los
sis emas de ecuaciones lineales de ma ices a iables.
Realiza un es udio compa a i o del e ec o que p oducen los p econdiciona-
do es, an e io men e ci ados, sob e la con e gencia del algo i mo del G a-
dien e Conjugado, al aplica los a los sis emas de ecuaciones lineales de ma-
ices a iables, ob enidos en la modelizaci´on p ´ac ica de di e sos campos
de ien o de la isla de G an Cana ia.
Comp oba la in luencia de la eo denaci´on en la soluci´on de a ios de esos
sis emas lineales de coe icien es a iables, ob enidos en la modelizaciones
p ´ac icas mencionadas.
Realiza , asimismo, un es udio compa a i o de la con e gencia del algo i -
mo del G adien e Conjugado, con la u ilizaci´on de los p econdicionado es
p opues os, en la selecci´on, median e Algo i mos Gen´e icos, de los alo es
pa am´e icos ´op imos, pa a di e en es campos de ien o.
1.3. METODOLOG´
IA
El p esen e abajo se inicia con la In oducci´on, Cap´ı ulo 1, donde se p e-
sen an los an eceden es, los obje i os p opues os en el desa ollo de es as esis, y
la me odolog´ıa seguida a lo la go de la misma.
El con enido b´asico, se es uc u a en es g andes bloques. Un p ime bloque,
que aba ca desde el cap´ı ulo 2 has a el cap´ı ulo 4, en el que se expone la p oble-
m´a ica de la modelizaci´on de los campos de ien o, su disc e izaci´on po MEF y
loa p ocesos de es imaci´on de los pa ´ame os que in e ienen en su o mulaci´on.
Un segundo bloque, que a del cap´ı ulo 5 al 7, en el que se da una isi´on gene-
al del es ado del a e de los m´e odos i e a i os, pa a la esoluci´on de g andes
METODOLOG´
IA 5
sis emas de ecuaciones lineales, basados en los subespacios de K ylo , as´ı como
de las ´ecnicas de p econdicionamien o y eo denaci´on de dichos sis emas. Y un
e ce bloque, cons i uido po el cap´ı ulo 8, donde se a a de hace una nue-
a apo aci´on, ex endiendo las ´ecnicas de p econdicionamien o a los sis emas de
ecuaciones lineales de ma ices a iables. Po ´ul imo, en el cap´ı ulo 9, se p esen an
los esul ados de di e sos expe imen os num´e icos, donde se aplican los p econdi-
cionado es p opues os a los sis emas de ma ices a iables, se u ilizan di e en es
eo denaciones y se comp ueba su in luencia sob e la con e gencia del algo i mo
del G adien e Conjugado.
El p ime bloque, dedicado a la modelizaci´on de campos de ien o es ´a cons i-
uido po :
El Cap´ı ulo 2, donde se exponen el es ado del a e de la modelizaci´on de
los campos de ien o, as´ı como, unas b e es nociones de C´alculo Va iacional,
dada su aplicaci´on en la o mulaci´on ma em´a ica de los modelos en cues i´on.
Se p es a especial a enci´on al Modelo de Masa Consis en e, po conside a se,
ac ualmen e, como el m´as e icien e, llegando a es ablece la ecuaci´on di e-
encial el´ıp ica que lo de ine. Asimismo, se analiza la cons ucci´on del campo
inicial, po su ascendencia en la consecuci´on de un esul ado inal co ec o.
El Cap´ı ulo 3, en el que se a on a la disc e izaci´on, po el M´e odo de Ele-
men os Fini os, de la ecuaci´on el´ıp ica, mencionada an e io men e, co es-
pondien e a los Modelos de Masa Consis en e. Se expone la p oblem´a ica de
la gene aci´on de mallas adap a i as, pa a consegui disc e iza con m´as e i-
cacia, sob e odo en los e enos de o og a ´ıa compleja. Llegando inalmen e
a la gene aci´on del sis ema de ecuaciones lineales del modelo ma em´a ico,
que esul a se de ma iz Sim´e ica De inida Posi i a (SDP), de coe icien es
a iables, dependien es de un pa ´ame o, denominado pa ´ame o de es abi-
lidad del modelo.
El Cap´ı ulo 4, dedicado al an´alisis y alo aci´on, no solo, de los pa ´ame os
que in e ienen an la cons ucci´on del campo inicial, sino ambi´en, del pa ´a-
me o de es abilidad, po su g an p o agonismo en el sis ema de ecuaciones
METODOLOG´
IA 6
lineales ob enido.
El segundo bloque, co espondien e a los m´e odos del C´alculo Num´e ico pa a la
esoluci´on de g andes sis emas de ecuaciones lineales, es ´a o mado po :
El Cap´ı ulo 5, en el que se exponen los undamen os de los m´e odos i e a i-
os basados en los subespacios de K ylo , po conside a se los m´as adecuados
pa a la esoluci´on de g andes sis emas lineales. P es ando especial a enci´on
al algo i mo del G adien e Conjugado, po a a se del m´e odo m´as e icaz
pa a esol e los sis emas de ma ices SDP, que, como se ha indicado, es el
ipo de sis ema que se ob iene en la modelizaci´on de campos de ien o de
Masa Consis en e.
El Cap´ı ulo 6, dedicado po en e o al P econdicionamien o de sis emas,
po se una he amien a que mejo a sensiblemen e la con e gencia de los
m´e odos de K ylo . Adem´as de expone el es ado del a e de es a ´ecnica,
se es ablece el algo i mo del G adien e Conjugado P econdicionado, pues
es el m´e odo que se u iliza ´a m´as adelan e pa a a on a los expe imen os
num´e icos y, ambi´en, se desc iben los p econdicionado es expl´ıci os AINV
y SAINV, as´ı como, los impl´ıci os, an o los ob enidos po compa aci´on con
el m´e odo de Richa dson, como los que se undamen an en ac o izaciones
incomple as de la ma iz inicial del sis ema.
El Cap´ı ulo 7, en el que se es udian los m´e odos m´as p ´ac icos de Reo -
denaci´on de sis emas, como son: el algo i mo de Cu hill-McKee In e so, el
del M´ınimo Vecino y el Mul icolo ing, que basados en la eo ´ıa de g a os,
p opo cionan ma ices con ancho de banda o pe il meno , lo que incide
no ablemen e en una mayo simpli icaci´on, a la ho a de cons ui un p econ-
dicionado m´as e icaz.
El e ce bloque, donde se hace la apo aci´on no edosa de es a esis, es ´a cons i-
uido po :
El Cap´ı ulo 8, en el que, a pa i del conocimien o de los p incipales p e-
condicionado es aplicables a los sis emas de ma ices SDP, como son los
SAINV y los basados en la ac o izaci´on incomple a de Cholesky (ICHOL),
METODOLOG´
IA 7
se implemen a su adap aci´on a los sis emas de ecuaciones lineales de ma-
ices a iables, que, como ya se ha indicado, son los que se ob ienen en la
modelizaci´on ma em´a ica de los campos de ien o.
Los esul ados de los expe imen os num´e icos, ealizados pa a con on a las p o-
pues as apo adas en es a esis, se ecogen en
El Cap´ı ulo 9, que a su ez se dis ibuye en dos secciones.
Una, dedicada a las aplicaciones es , donde se han u ilizado ambos ipos
de p econdicionado es, SAINV e ICHOL, sob e sis emas de ecuaciones de
ma ices a iables ob enidos en es modelos de campos de ien o dis in-
os, conseguidos con es disc e izaciones di e en es, sob e una egi´on de la
isla de G an Cana ia, comp obando en la p ´ac ica, la e icacia de los dis in-
os p econdicionado es, as´ı como, la in luencia de las di e en es ´ecnicas de
Reo denaci´on.
O a, o ien ada a la op imizaci´on del pa ´ame o de es abilidad, donde se
han aplicado los p econdicionado es ipo ICHOL, dado que, con los esul-
ados ob enidos en los expe imen os an e io es, han demos ado se los m´as
e icaces pa a es os modelos. Se han u ilizado sob e los sis emas de ecuacio-
nes de ma ices a iables co espondien es a la modelizaci´on de dos campos
de ien o di e en es, usando siemp e el algo i mo del G adien e Conjugado
P econdicionado. En cada uno de es os ejemplos se ecogen los iempos de
compu aci´on, pa a dos gamas dis in as de alo es del pa ´ame o, pues es os
esul ados in lui ´an no ablemen e a la ho a de selecciona el p econdiciona-
do m´as adecuado pa a usa en la selecci´on del alo ´op imo del pa ´ame o,
median e Algo i mos Gen´e icos, dado la epe i i idad del p oceso.
Las conclusiones ob enidas y las u u as lineas de in es igaci´on, con las que inaliza
es e abajo, se ecogen en el Cap´ı ulo 10.
Cap´ı ulo 2
CAMPOS DE VIENTO
2.1. PRELIMINARES
El ien o no es o a cosa que el ai e en mo imien o, en endiendo po ai e la
masa de gases que cons i uyen nues a a m´os e a e es e.
Hace unos cua o mil seiscien os millones de a˜nos el Sis ema Sola se condens´o
a pa i de una nube de gas y pol o in e es ela , la Nebulosa Sola . Las a m´os e as
de la Tie a, Venus y Ma e se o ma on a pa i de ma e ia ol´a il que escap´o de
cada plane a. La p imi i a a m´os e a de la Tie a es aba compues a po di´oxido
de ca bono (CO2), ni ´ogeno (N2) y apo de agua (H2O), con azas de hid ´o-
geno (H2), una mezcla muy simila a la emi ida hoy en d´ıa po los olcanes. La
apa ici´on del ox´ıgeno (O2) como componen e de la a m´os e a ue el esul ado de
su p oducci´on po la ac i idad o osin ´e ica. Se es ima que el ni el ac ual de O2
se alcanz´o hace ap oximadamen e cua ocien os millones de a˜nos y se man iene
g acias a un balance en e su p oducci´on po o os´ın esis y su desapa ici´on po
la espi aci´on de los se es i os y g adual descenso del ca bono o g´anico. La a -
m´os e a ac ual es ´a compues a p incipalmen e po los gases N2(78 %), O2(21 %),
A (1 %) y una p opo ci´on muy a iable de apo de agua, que puede alcanza
has a un 3 %.
Desde la m´as emo a an ig¨
uedad, el homb e se di´o cuen a que el ien o pod´ıa
se ap o echado como uen e de ene g´ıa, as´ı los egipcios na egaban ya a ela en
el a˜no 4500 a.C. M´as a de el ap o echamien o de la ene g´ıa e´olica con inu´o con
la apa ici´on de los molinos, se ienen da os de ellos desde el siglo II a.C. Los
PRELIMINARES 9
m´as an iguos e an de eje e ical, pe o hacia el siglo VIII apa ecie on en Eu opa,
p oceden es del Es e, los g andes molinos de eje ho izon al con cua o aspas. A
pa i de los siglos XII y XIII se gene aliza el uso de los molinos de ien o pa a
la molienda de g anos y pa a la ele aci´on de agua, ac i idades que se man ienen
has a bien en ado el siglo XIX. La llegada de la e oluci´on indus ial, con la
u ilizaci´on masi a del apo , la elec icidad y los combus ibles ´osiles como uen e
de ene g´ıa, in e umpe su desa ollo. Sin emba go, en la segunda mi ad del siglo
XIX, apa ece el popula molino ame icano mul ipala, u ilizado pa a el bombeo de
agua, p ac icamen e en odo el mundo, y cuyas ca ac e ´ıs icas hab ´ıan de sen a
las bases pa a el dise˜no de los mode nos ae ogene ado es. Du an e el siglo XX, la
supe icie del plane a se ha ido cub iendo paula inamen e de m´as y m´as pa ques
e´olicos, que an su giendo como al e na i a iable de las cen ales ´e micas. La
sociedad ha ido adqui iendo conciencia de los p oblemas medio ambien ales y
alo a cada ez m´as el uso de las ene g´ıas eno ables. Es a c ecien e inquie ud
social ha adqui ido una g an impo ancia desde el pun o de is a pol´ı ico (no hay
o maci´on pol´ı ica que se sus aiga a los p oblemas ecol´ogicos y no los incluya en su
p og ama elec o al) y econ´omico (las emp esas in ie en cada d´ıa m´as en es udios
de impac o ambien al y en publicidad pa a ala dea de sus alo es ecol´ogicos, sean
eales o no), lo que ha p oducido en los ´ul imos a˜nos un c ecimien o no able de la
p oducci´on de ene g´ıa el´ec ica de o igen e´olico.
La Con e encia de Mad id, ma zo de 1994, conside ´o iable que las ene g´ıas
eno ables con ibuye an con un 15 % a la demanda o al de ene g´ıa p ima ia en
la CE, an es de 2010. Espa˜na ocupa un luga des acado en el pano ama e´olico
comuni a io, con el quin o pues o po po encia e´olica ins alada, de ´as de Di-
nama ca, Alemania, Reino Unido y Holanda. Las emp esas del sec o necesi an
he amien as cada ez m´as so is icadas que les pe mi a hace en e a las demandas
de un me cado cada ez m´as compe i i o y exigen e.
Po o a pa e el desa ollo indus ial ha a´ıdo como consecuencia el e ido
masi o a la a m´os e a de sus ancias con aminan es. Es cada ez m´as e iden e que
la con aminaci´on a mos ´e ica iene g a es epe cusiones que p o ocan la al e a-
ci´on de las condiciones medioambien ales del plane a. Las consecuencias de es a
con aminaci´on an desde la llu ia ´acida, has a el aumen o de los as o nos espi-
MODELOS DE CAMPOS DE VIENTO 10
a o ios y al´e gicos de la poblaci´on, pasando po el p eocupan e e ec o in e nade o
de g a es consecuencias a la go plazo.
2.2. MODELOS DE CAMPOS DE VIENTO
Los modelos de campos de ien o son he amien as que pe mi en a on a di-
e sos p oblemas elacionados con el impac o del ien o en nues o en o no, ales
como, el es udio de sus e ec os sob e una de e minada es uc u a (especialmen e
puen es y edi icios de g an al u a), la dispe si´on de con aminan es en la a m´os-
e a, la p opagaci´on de incendios o el es udio del emplazamien o y endimien o
de pa ques e´olicos. Conc e amen e en es e ´ul imo segmen o, con los modelos de
campo de ien o se pueden a on a di e sos p oblemas su gidos en el seno de las
emp esas dedicadas a la explo aci´on de es e ipo de pa ques, ales como la e alua-
ci´on de la po encia p oducida po un ae ogene ado , en unci´on de su si uaci´on,
y su compa aci´on con las cu as suminis adas po el ab ican e; el es udio de la
ubicaci´on ´op ima de la ed de es aciones de medida p e ia a la ins alaci´on del
pa que y la dis ibuci´on m´as e icaz de los aeo gene ado es.
Los modelos de campos de ien o son, pues, he amien as cada ez m´as impo -
an es pa a a on a con e icacia una amplia gama de p oblemas de in e ´es social,
pol´ı ico y econ´omico, y cada ez se exige m´as de ellos.
Inicialmen e los modelos me eo ol´ogicos se di iden en dos g andes g upos: los
Modelos F´ısicos y los Modelos Ma em´a icos. Los p ime os usan ´uneles de ien o
sob e ep oducciones a peque˜na escala del e eno en es udio. En los Modelos Ma-
em´a icos, que se ´an los obje os de es a esis, se emplean ´ecnicas algeb aicas y de
c´alculo pa a esol e ecuaciones me e eol´ogicas. A su ez los Modelos Ma em´a icos
se di iden en Anal´ı icos y Num´e icos; los p ime os, po la g an complejidad de las
ecuaciones que desc iben la a m´os e a, hacen muy di ´ıcil la esoluci´on exac a en
dominios i egula es, mien as que los segundos o ecen mejo es pe spec i as. Po
ello el obje i o de es a esis a a se a a de apo a he amien as de C´alculo
Num´e ico que pe mi an la modelizaci´on ma em´a ica de campos de ien o con la
mayo e icacia posible.
Seg´un la ex ensi´on del dominio a es udia , los Modelos de Vien o se pueden
MODELOS DE CAMPOS DE VIENTO 11
clasi ica en Modelos de Mac oescala, cuando el ´a ea de es udio aba ca desde un
con inen e has a el globo e ´aqueo comple o. Modelos de Mesoescala, cuando se
e ie en a ex ensiones que an desde unos pocos kil´ome os has a al ededo de
cien, y de Mic oescala, pa a egiones locales que ienen como m´aximo al ededo
de un kil´ome o.
Los Modelos Ma em´a icos de Campos de Vien o ambi´en se pueden clasi ica
en Modelos de P on´os ico o Din´amicos y Modelos de Diagn´os ico o Cinem´a icos.
Los Modelos de P on´os ico se basan en la soluci´on de ecuaciones hid odin´a-
micas y e modin´amicas que depende del iempo (llamadas ambi´en ecuaciones
p imi i as po que de i an di ec amen e de los p incipios de conse aci´on) modi-
icadas pa a su aplicaci´on a la a m´os e a. Sin emba go la soluci´on del conjun o
comple o de ecuaciones sigue siendo una a ea cos osa. Adem´as, cuan o m´as ela-
bo ado es el modelo, m´as iables deben se los da os de en ada pa a ap o echa
las en ajas o ecidas, y con ecuencia es os da os no suelen es a disponibles.
Au o es como Lalas e al. [58] incluyen en los Modelos Din´amicos algunos
c´odigos que in oducen ap oximaciones a las ecuaciones p imi i as, a la ez que
desp ecian su dependencia del iempo. Es os c´odigos, denominados JH, se basan
en una p opues a ealizada po Jackson y Hun [51] y son ampliamen e u ilizados.
Como ejemplo podemos ci a el modelo empleado po T oen y Pe e senen [110]
en la con ecci´on del A las Eu opeo de Vien o.
Los Modelos de Diagn´os ico deben su nomb e a que no se u ilizan pa a eali-
za p e isiones a a ´es de la in eg aci´on de las elaciones conse a i as. Eliminan
di ec amen e de sus ecuaciones la dependencia del iempo y po es a az´on se les
llama ambi´en Cinem´a icos. Es os modelos gene an un campo de ien o que sa is-
ace algunas es icciones ´ısicas. Si la ´unica es icci´on que se les impone es que
cumplan la ecuaci´on de con inuidad, lo que supone la conse aci´on de la masa, el
modelo se denomina de Masa Consis en e. Los Modelos de Diagn´os ico no equie-
en muchos da os de en ada y son ´aciles de usa , po lo que esul an a ac i os
desde el pun o de is a p ´ac ico. Au o es como Pennel [81] han comp obado que
en algunos casos los Modelos de Masa Consis en e mejo ados, ales como NOABL
y COMPLEX, supe a on los esul ados de Modelos Din´amicos m´as complicados y
cos osos. Sin emba go hay que ene en cuen a que los Modelos de Diagn´os ico no
MODELOS DE CAMPOS DE VIENTO 12
conside an los e ec os ´e micos ni los debidos a cambios de g adien es de p esi´on.
Po ello, lujos ales como las b isa ma inas, ien os en pendien e y o os ales
como los de sepa aci´on a a o del ien o, no pueden simula se con es a modelos,
a no se que se inco po en en los da os de ien o inicial, a pa i de obse aciones
ealizadas en luga es ap opiados a al e ec o [54, 76].
Los Modelos de Diagn´os ico es ´an dise˜nados espec´ı icamen e pa a p edeci los
e ec os de la o og a ´ıa sob e el lujo medio de ien o conside ado de mane a es a-
ciona ia, es o es, lujos p omediados en in e alos de iempo en e 10 minu os y 1
ho a.
NOABL [82] es un modelo me eo ol´ogico que p opo ciona una ep esen aci´on
p ecisa del e eno g acias a una ans o maci´on de la coo denada e ical en la que
la coo denada m´as baja es con o me a la supe icie del e eno. Pos e io men e,
di e sos au o es [55, 56, 108] ealiza on algunas modi icaciones en la inicializaci´on
del mismo, con el in de que el modelo conside a a el e ec o de la ugosidad del
e eno sob e el pe il del ien o, de o ma que el modelo dispusie a de pe iles
m´as ealis as que los del c´odigo o iginal y u ie a en cuen a el cambio debido a
la ue za de Co iolis en la di ecci´on del ien o, en la capa l´ımi e a mos ´e ica. Los
c´odigos esul an es ue on bau izados como NOABL* [58] y EOLOS [108], aun-
que ac ualmen e es m´as conocido po AIOLOS, po su e e encia a la e imolog´ıa
g iega. M´as a de se in oduje on modi icaciones que desc iben con m´as p ecisi´on
los pe iles de ien o en di e en es condiciones de es abilidad. Es e nue o c´odigo
[86] se llam´o WINDS(Wind- ield In e pola ion by Non Di e gen Squemes). Am-
bos modelos, AIOLOS y WINDS, usan da os de es aciones si uadas en ie a y,
opcionalmen e, da os obse ados an o de pe iles e icales como de ien o geos-
´o ico. Tambi´en u ilizan coo denadas con o mes al e eno. Ambos se basan en la
minimizaci´on de los cuad ados de las di e encias en e las elocidades de un ien o
inicial, ob enido po in e polaci´on de los da os obse ados, y el ien o a ajus a ,
suje o a la es icci´on de que el campo de ien o ajus ado ha de ene di e gencia
nula [99].
Adem´as de los ya ci ados, exis e oda una gama de Modelos de Diagn´os ico
que la comunidad cien ´ı ica ha enido u ilizando en p oblemas elacionados con la
me eo olog´ıa y/o con la con aminaci´on a mos ´e ica. Den o de los m´as conocidos
MODELO DE MASA CONSISTENTE 19
U ilizando el g upo de ecuaciones (2.3), que hemos is o an e io men e pa a las
Ecuaciones de Eule , esul a que:
F0
p1= Φ; F0
q1= 0; F0
1= 0
F0
p2= 0; F0
q2= Φ; F0
2= 0
F0
p3= 0; F0
q3= 0; F0
3= Φ
Y sus i uyendo y de i ando con enien emen e end emos:
2(u−uo)α2
1−∂Φ
∂x = 0
2( − 0)α2
1−∂Φ
∂y = 0
2(ω−ω0)α2
2−∂Φ
∂z = 0
u=1
2α2
1
∂Φ
∂x +u0
=1
2α2
1
∂Φ
∂y + 0
ω=1
2α2
2
∂Φ
∂z +ω0
Que pueden esumi se como:
~u =~ 0+T~
∇Φ (2.10)
Exp esi´on en la que T= (Th, Th, T ), se puede conside a como un enso diagonal
de ansmisi´on, al que:
T=diagh1
2α2
1
,1
2α2
1
,1
2α2
2i(2.11)
cons an e pa a un dominio dado, Ω.
As´ı el campo soluci´on, ~u, se ob end ´a a pa i del campo inicial, ~ 0, y de los
alo es de Φ, pa a cuyo c´alculo se ecu e a la ecuaci´on de condici´on
~
∇·~u = 0,o sea,∂u
∂x +∂
∂y +∂ω
∂z = 0
esul ando la ecuaci´on di e encial siguien e:
1
2α2
1
∂2Φ
∂x2+∂u0
∂x +1
2α2
1
∂2Φ
∂y2+∂ 0
∂y +1
2α2
2
∂2Φ
∂z2+∂ω0
∂z = 0.
Teniendo en cuen a que los pa ´ame os α1yα2, se suelen conside a cons an es en
odo el dominio Ω, la ecuaci´on an e io se puede simpli ica mul iplicando odos
los ´e minos po 2 α2
1y llamando a
α2
1
α2
2
=T
Th
=α2=. (2.12)
se ob iene
∂2Φ
∂x2+∂2Φ
∂y2+∂2Φ
∂z2=−1
Th∂u0
∂x +∂ 0
∂y +∂ω0
∂z (2.13)
MODELO DE MASA CONSISTENTE 20
ecuaci´on el´ıp ica en Φ, donde ecibe el nomb e de pa ´ame o de es abilidad del
modelo.
Teniendo en cuen a las exp esiones (2.6) y (2.10), es a ecuaci´on di e encial, en
de i adas pa ciales, es a ´a suje a a una condici´on ipo Neuman en las on e as
impe meables ( e eno y on e a supe io ); ya que
~n ·T~
∇Φ = −~n ·~ 0en Γb(2.14)
que se comple a con la condici´on de Di ichle , nula en las on e as pe meables
( on e as e icales del dominio):
Φ = 0 en Γa(2.15)
Obs´e ese que en la on e a supe io , al se el campo inicial ~ 0ho izon al, la
condici´on (2.14) se ans o ma en
~n ·T~
∇Φ = 0 (2.16)
Po an o, desde el pun o de is a ma em´a ico, la pa e esencial de la cons uc-
ci´on de un modelo de ien o de Masa Consis en e, se con ie e en la esoluci´on
de la ecuaci´on di e encial en de i adas pa ciales (??), con las condiciones de con-
o no (2.14) y (2.15).
Obs´e ese que el pa ´ame o de es abilidad del modelo, , a a es a p esen e
en la soluci´on del p oblema, de ah´ı que los modelos de Masa Consis en e sean
c i icados po su al a dependencia de pa ´ame os. La elecci´on ace ada de sus
alo es es de g an impo ancia pa a la iabilidad de los esul ados. Teniendo en
cuen a (2.11) y (2.12):
=T
Th
(2.17)
esul ando en onces que pa a 1, p edomina el ajus e del lujo en la di ecci´on
e ical, es deci , el ai e iende a sob epasa las ba e as del e eno, m´as que a
pasa ho izon almen e al ededo de ellas. Mien as que pa a 1, el ajus e del
lujo ocu e p ime amen e en el plano ho izon al, po an o el ai e pasa ´a al ededo
de las ba e as del e eno m´as que sob e ellas. En pa icula , → ∞ signi ica
ajus e e ical pu o, mien as que →0 signi ica ajus e ho izon al pu o [7].
CONSTRUCCI ´
ON DEL CAMPO INICIAL 21
2.5. CONSTRUCCI´
ON DEL CAMPO INICIAL
Pa a la cons ucci´on del campo inicial pa imos de los alo es de la elocidad
del ien o y de su di ecci´on ob enidos en las es aciones de medida. Los da os de
ien o se oman de es aciones ubicadas en el dominio de es udio. Cada es aci´on
de medida p opo ciona la elocidad (en m/s) y di ecci´on del ien o a una al u-
a zssob e el ni el del e eno ( ´ıpicamen e 10 me os). La di ecci´on del ien o
iene dada en g ados sexagesimales medidos en sen ido ho a io y omando como
e e encia la di ecci´on no e. As´ı el no e se co esponde a 0 g ados, el su a 180
g ados, el es e a 90 g ados y el oes e a 270 g ados. A e ec os de c´alculo en el mo-
delo, es necesa io ob ene el ´angulo medido en sen ido an iho a io, omando como
e e encia el semieje posi i o ho izon al. Po o o lado, como las es aciones miden
el ien o en in e alos disc e os de iempo, en gene al es necesa io in e pola las
medidas pa a calcula el ien o en un ins an e conc e o.
El campo inicial ~ 0se cons uye en dos e apas:
2.5.1. INTERPOLACI´
ON HORIZONTAL
En p ime luga , se calcula median e in e polaci´on ho izon al el alo de ~ 0en
los pun os del dominio si uados a la misma al u a zs(sob e el e eno) que las
es aciones de medida.
La ´ecnica m´as com´un de in e polaci´on se o mula en ´e minos de la in e sa de
la dis ancia al cuad ado en e el pun o y la es aci´on de medida [116]. Sin emba go,
o os au o es usan simplemen e la al i ud de los pun os de medida [79]. Aqu´ı se
p opone una ´o mula que iene en cuen a ambas conside aciones,
~ 0(ze) = β
N
P
n=1
~ n
d2
n
N
P
n=1
1
d2
n
+ (1 −β)
N
P
n=1
~ n
|∆hn|
N
P
n=1
1
|∆hn|
(2.18)
El alo de ~ nco esponde a la elocidad obse ada en la es aci´on n,Nes el
n´ume o de es aciones u ilizadas en la in e polaci´on, dnes la dis ancia ho izon al
desde la es aci´on nal pun o donde es amos calculando la elocidad del ien o,
CONSTRUCCI ´
ON DEL CAMPO INICIAL 22
|∆hn|es la di e encia de al u a en e la es aci´on ny el pun o en es udio, y βes
un pa ´ame o de peso que oma alo es en e 0 y 1. Cuando β→1 aumen a la
impo ancia de la dis ancia ho izon al desde cada pun o a las es aciones de me-
dida. Es a ap oximaci´on se emplea en p oblemas con una o og a ´ıa egula o en
an´alisis bidimensionales. De mane a an´aloga, si β→0 es en onces la di e encia de
al u a en e cada pun o y las es aciones de medida la que esul a de e minan e, en
de imen o de la dis ancia ho izon al. Es a segunda ap oximaci´on es la que se usa
cuando la o og a ´ıa del e eno es i egula . En la p ´ac ica, las egiones geog ´a icas
es udiadas suelen combina zonas de o og a ´ıa i egula con o as de o og a ´ıa mas
egula , po lo que oma un alo in e medio pa a βsuele se lo m´as ap opiado.
2.5.2. EXTRAPOLACI´
ON VERTICAL
Con la in o maci´on ob enida en el paso an e io se ealiza una ex apolaci´on
e ical pa a de ini el campo de elocidades en la o alidad del dominio.
El ien o se desa olla, en p ime luga , como consecuencia de di e encias es-
paciales en la p esi´on a mos ´e ica. Es as di e encias de p esi´on no malmen e son
causadas po una di e en e abso ci´on de la adiaci´on sola . En un plano ho izon al,
el ien o luye de las zonas de al a p esi´on a zonas de baja p esi´on y e icalmen e
de zonas de baja p esi´on a zonas de al a p esi´on. La elocidad del ien o es p o-
po cional al cambio de p esi´on po unidad de dis ancia o g adien e de p esi´on. Las
zonas con p esiones simila es se ep esen an en los mapas me eo ol´ogicos unidas
median e l´ıneas imagina ias denominadas isoba as. Cuan o m´as jun as es ´an unas
isoba as, mayo se ´a la ue za del ien o.
Un segundo ac o que a ec a el mo imien o del ai e es la ue za de Co iolis,
debida a la o aci´on e es e. El pa ´ame o = 2Θ sen φlse denomina pa ´ame o
de Co iolis, siendo Θ = 7,292 ×10−5s−1la elocidad de o aci´on de la Tie a y
φlla la i ud. Se conside a posi i a en el hemis e io no e, nula en el ecuado y
nega i a en el hemis e io su .
En e ce luga puede apa ece una acele aci´on cen ´ıpe a, cuando el ien o
gi a en o no a un cen o. Po ´ul imo, apa ece la icci´on debida al desplazamien o
del ai e. Los ien os in luenciados po el g adien e de p esi´on y la ue za de Co iolis
CONSTRUCCI ´
ON DEL CAMPO INICIAL 23
se denominan ien os geos ´o icos.
Es a i icaci´on a mos ´e ica:
En es e modelo se conside a una di isi´on de la capa m´as baja de la a m´os e a
en dis in as subcapas, en las que la ex apolaci´on e ical de las elocidades de
ien o se ealiza de o ma di e en e, como puede obse a se en la igu a 2.1.
~ 0(z) = ~ ∗
klog z
z0−Φm
Zs
Z0
Zsl
hm
Zpbl
Capa de Mezcla
Vien o Geos ´o ico
~ 0(z) = ρ(z)~ 0(zsl) + [1 −ρ(z)]~ g
Figu a 2.1: Pe il e ical de ien o de inido sob e cada capa de la es a i icaci´on a -
mos ´e ica.
As´ı, la capa l´ımi e plane a ia es ´a si uada a una al i ud zpbl sob e el ni el del
e eno, y es la capa de la a m´os e a, si uada po debajo de la a m´os e a lib e, que
es ´a a ec ada di ec amen e po la icci´on de la supe icie de la ie a (conocida
ambi´en como capa l´ımi e a mos ´e ica). La al i ud de la capa l´ımi e plane a ia
zpbl sob e el e eno se ha omado al que la di ecci´on e in ensidad del ien o es
cons an e a pa i de esa al u a [101]:
zpbl =γ|~ ∗|
(2.19)
siendo γun pa ´ame o comp endido en e 0,15 y 0,45 que depende de la es abilidad
de la a m´os e a y ~ ∗la elocidad de icci´on que se ´a de inida m´as adelan e a pa i
CONSTRUCCI ´
ON DEL CAMPO INICIAL 24
de los alo es ob enidos en la in e polaci´on ho izon al.
La capa de mezcla, ambi´en llamada capa l´ımi e con ec i a, es la capa l´ımi-
e a mos ´e ica suje a a en´omenos con ec i os causados po el calo supe icial.
El ai e es ´a bien mezclado, es deci , el ien o y el po encial de empe a u a son
p ´ac icamen e cons an es con la al u a. La al i ud de la capa de mezcla hmse con-
side a ´a igual a zpbl pa a condiciones neu as e ines ables. En condiciones es ables
se ap oxima po
hm=γ0s|~ ∗|L
(2.20)
donde usualmen e se oma el pa ´ame o γ0= 0,4 [117] y Les la longi ud de
Monin-Obuko , que se calcula a a ´es de la ´o mula de Liu [85],
1
L=azb
0(2.21)
con ayb, de inidas po la clase de es abilidad de Pasquill (Ve Tabla 2.1):
Clase de es abilidad de Pasquill a b
A (Ex emadamen e Ines able) -0.08750 -0.1029
B (Mode adamen e Ines able) -0.03849 -0.1714
C (Lige amen e Ines able) -0.00807 -0.3049
D (Neu a) 0.00000 0.0000
E (Lige amen e Es able) 0.00807 -0.3049
F (Mode adamen e Es able) 0.03849 -0.1714
Tabla 2.1: Coe icien es aybpa a el c´alculo de la longi ud de Monin Obuko seg´un la
clase de es abilidad de Pasquill.
La capa supe icial, localizada a una al u a zsl sob e la supe icie, es la capa
baja, den o de la capa l´ımi e plane a ia, inmedia amen e adyacen e a la capa de
la supe icie de la ie a, en la que la ue za de a as e de icci´on es dominan e.
Conocido el alo de la al u a de la capa de mezcla hm, la al i ud de la capa
supe icial se suele ija en [117]
zsl =hm
10 (2.22)
CONSTRUCCI ´
ON DEL CAMPO INICIAL 25
Es abilidad a mos ´e ica:
El concep o de es abilidad a mos ´e ica es ´a elacionado an o con la u bulen-
cia a mos ´e ica como con el g adien e e ical de empe a u a y las si uaciones de
in e si´on ´e mica. La es abilidad a mos ´e ica nos p opo ciona una medida cuali-
a i a de las a iaciones de la densidad del ai e, debidas a los cambios de p esi´on
y empe a u a y que in luyen en de e minados mo imien os a mos ´e icos.
Las condiciones a mos ´e icas pueden clasi ica se como:
Es able: Si una masa de ai e sube se encon a ´a odeada de ai e m´as calien e
y, po an o, menos denso que ella, lo que la ha ´a baja ; y si baja, se encon a ´a
odeada de ai e m´as ´ıo (m´as denso), y ende ´a a subi . Es a endencia que iene
el ai e de pe manece en la misma capa es lo que se denomina es abilidad de la
es a i icaci´on a mos ´e ica.
Ines able: En condiciones ines ables la empe a u a po encial disminuye con
la al u a, inc emen ´andose los mo imien os e icales, es deci si el ai e sube se
encon a ´a odeado de ai e m´as ´ıo y denso que ´el, y ende ´a a segui subiendo;
y si baja se encon a ´a con ai e m´as calien e y lige o, y ende ´a a segui bajando.
Neu a: Si un olumen de ai e (despu´es de un desplazamien o e ical en una
capa a mos ´e ica sin mezcla con el ai e ci cundan e) expe imen a una ue za ne a
e ical nula, los mo imien os ascensionales no se e ´an pe u bados po el g a-
dien e ´e mico, en onces la capa a mos ´e ica se asume neu almen e es a i icada.
Bajo ales condiciones, dicho olumen ni iende a ol e a su posici´on o iginal
(es a i icaci´on es able) ni acele a alej´andose de ella (es a i icaci´on ines able).
La es abilidad a mos ´e ica puede se ca ac e izada median e la abla de inida
po Pasquill.(Ve Tabla 2.2 )
Pe il e ical de elocidades de ien o:
Como se mues a en la Figu a 2.1, se conside a un pe il loga ´ı mico-lineal [57]
en la capa l´ımi e plane a ia, que iene en cuen a la in e polaci´on ho izon al [70],
CONSTRUCCI ´
ON DEL CAMPO INICIAL 26
Clase de es abilidad de Pasquill
Insolaci´on Noche
Velocidad del Cubie o
ien o en la ´o ≥4/8≤3/8
supe icie (m/s) Fue e Mode ada Lige a nubes nubes
<2 A A-B B - -
2-3 A-B B C E F
3-5 B B-C C D E
5-6 C C-D D D D
>6 C D D D D
Pa a A-B, oma la media de los alo es de A y B, e c.
Tabla 2.2: Clases de es abilidad de Pasquill seg´un la elocidad del ien o en la supe icie
y la insolaci´on. Insolaci´on ue e co esponde al mediod´ıa soleado de mi ad
de e ano en Ingla e a; insolaci´on lige a a condiciones simila es en mi ad
del in ie no. La noche se e ie e al pe iodo que a desde una ho a an es de
pone se el sol has a una ho a despu´es de sali . La clase neu a D debe ´ıa
se usada ambi´en, a pesa de la elocidad del ien o, pa a cielos cubie os
du an e el d´ıa o la noche, y pa a cualquie condici´on del cielo du an e las
ho as p eceden e y siguien e de la noche de inida an e io men e.
el e ec o de la ugosidad en la in ensidad y di ecci´on del ien o, y la es abilidad
del ai e (neu a, es able o ines able) seg´un la clasi icaci´on de Pasquill. En la capa
supe icial se cons uye un pe il loga ´ı mico de elocidades de ien o de inido po ,
~ 0(z) = ~ ∗
klog z
z0−Φmz0< z ≤zsl (2.23)
donde ~ 0es la elocidad del ien o, k≃0,4 es la cons an e de on Ka man y
zes la al u a sob e el e eno del pun o es udiado. El ´e mino ~ ∗ ep esen a la
elocidad de icci´on. En el lujo u bulen o a mos ´e ico las ue zas que se oponen
al mo imien o es ´an ca ac e izadas po la acci´on que eje cen las ugosidades o
aspe ezas p opias de la o og a ´ıa del e eno. La elocidad de icci´on se ob iene
en cada pun o a pa i de las medidas in e poladas a la al u a de las es aciones
CONSTRUCCI ´
ON DEL CAMPO INICIAL 27
(in e polaci´on ho izon al),
~ ∗=k ~ 0(ze)
ln ze
z0−Φm(ze)(2.24)
Asimismo, z0co esponde a la longi ud de ugosidad de la zona. El concep o de
longi ud de ugosidad iene a de ini una al u a po encima del e eno di e en e
de z= 0, donde, en eo ´ıa de la capa supe icial, la elocidad del ien o es ce o.
El alo de z0depende de las ca ac e ´ıs icas del e eno. Una o ma de es ima la
es median e alo es es ´anda pa a di e en es ipos de e eno [64]; e igu a 2.2.
O os au o es la de inen como z0=e
30 , donde ees la al u a media de los obs ´aculos
exis en es en la zona de es udio.
Po ´ul imo, Φm, es una unci´on que depende de la es abilidad del ai e [117]:
Φm= 0 (neu a)
Φm=−5z
L(es able)
Φm= log "θ2
m+ 1
2θm+ 1
22#−2 a c an θm+π
2(ines able)
donde
θm= (1 −16 z
L)1/4(2.25)
El ien o geos ´o ico es una buena ap oximaci´on al ien o eal con lujo uni-
o me en la al a a m´os e a (a m´os e a lib e), donde la icci´on y acele aciones no
son impo an es. La o ma gene al de la exp esi´on usada pa a calcula el ien o
geos ´o ico es la bien conocida ley de esis encia geos ´o ica (geos ophic d ag low)
[85]
|~
Vg|=|~ ∗|
kslog |~ ∗|
z0−A2
+B2(2.26)
Los alo es de los coe icien es A y B ienden a se ∼1,8 y ∼1,5 espec i amen e,
que son los alo es acep ables pa a condiciones neu as de es abilidad a mos ´e ica.
El ien o en la supe icie se supone que gi a un ´angulo φgcon espec o a ~
Vg,
dado po la elaci´on
φg= sin−1 −B|~ ∗|
k|~
Vg|!(2.27)
En nues o modelo, desde zsl has a zpbl se ealiza una in e polaci´on lineal en
ρ(z) con el ien o geos ´o ico ~ g
~ 0(z) = ρ(z)~ 0(zsl) + [1 −ρ(z)]~ gcon zsl < z ≤zpbl (2.28)
CONSTRUCCI ´
ON DEL CAMPO INICIAL 28
Z (m)
0
~
~
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
2
3
4
5
7
8
9
6
10
10
−5
−4
−3
−2
−1
2
6
5
4
3
7
8
9
1
2
3
4
5
Cen os de ciudades con edi icios muy al os
Cen os de g andes poblaciones, ciudades
Cen os de pequeñas poblaciones
Al ededo es de poblaciones
Bosques
A eas esca padas o mon añosas
Region de ni el medio de bosque
Muchos a boles, se os, pocos edi icios
Muchos se os
Pocos a boles, e ano Tie as de cul i o Hie ba al a( 60 cms)
campos cul i ados
Ae opue os
Llanu as de hie bas medianas
A boles aislados
Pocos a boles, in ie no
Hie ba sin co a
Hie ba co ada ( 3 cm)
Supe icie na u al ne ada ( ie as de cul i o)
Desie o (llanu a)
Planicie cubie a de nie e
Te eno ondulado
Ma abie o en calma
Hielo, planicie (llanu a) enlodada.
G andes ex ensiones de agua
Vien o ma aden o en
zonas cos e as
Figu a 2.2: Longi ud de ugosidad: alo es ap oximados de z0pa a dis in os ipos de
e eno de inidos po McRae (1982)
MALLAS ADAPTATIVAS 34
Despu´es de es os an eceden es nos p oponemos desc ibi a con inuaci´on el p o-
ceso de c eaci´on de una malla de e aed os que espe e la opog a ´ıa de una egi´on
ec angula con una p ecisi´on de e minada, disponiendo ´unicamen e de la in o -
maci´on digi alizada del e eno. Es e p oblema posee cie a di icul ad debido a la
ue e i egula idad de la supe icie del e eno. Po o a pa e, deseamos que la
malla es ´e adap ada, es deci , que exis a una densidad de nodos mayo donde sea
necesa io pa a de ini las ca ac e ´ıs icas geom´e icas de nues o dominio. La malla
gene ada pod ´a u iliza se como malla base pa a la simulaci´on num´e ica de p o-
cesos na u ales en el dominio; po ejemplo, ajus e de campos de ien o [116, 70],
p opagaci´on de uego [68], con aminaci´on a mos ´e ica [115], e c. Es os en´ome-
nos ienen su mayo e ec o en las zonas p ´oximas al e eno, de ah´ı que ambi´en
sea deseable que la densidad de nodos aumen e al ace ca nos a ´es e. Sob e es-
a malla base, adap ada a las ca ac e ´ıs icas geom´e icas del dominio, se pod ´an
aplica pos e io men e algo i mos de e inamien o y des e inamien o de e aed os
pa a mejo a la soluci´on num´e ica del p oblema [61, 62, 45, 44]. Es os algo i mos
end ´an un especial in e ´es en los p oblemas e olu i os.
Nues o dominio es ´a limi ado en su pa e in e io po el e eno y en su pa e
supe io po un plano ho izon al si uado a una al u a en la que las magni udes
obje o del es udio puedan se conside adas es ables. Las pa edes la e ales es ´an
o madas po cua o planos e icales, pa alelos dos a dos. Las ideas b´asicas pa-
a la cons ucci´on de la malla inicial combinan, po un lado, la u ilizaci´on de
un algo i mo de e inamien o y des e inamien o pa a dominios bidimensionales y,
po o o lado, un algo i mo de gene aci´on de mallas de e aed os basado en la
iangulaci´on de Delaunay.
Es bien conocido que pa a cons ui una iangulaci´on de Delaunay es nece-
sa io de ini una nube de pun os en el dominio y su on e a. Es os nodos se ´an
p ecisamen e los ´e ices de los e aed os que con o man la malla. La gene aci´on
de pun os en nues o dominio se ealiza ´a sob e di e en es capas, eales o ic icias,
de inidas desde el e eno has a la on e a supe io del dominio. En conc e o, se
cons uye una iangulaci´on con una dis ibuci´on uni o me de pun os en el plano
supe io del dominio. Es a malla bidimensional puede se ob enida a pa i de la
MALLAS ADAPTATIVAS 35
ealizaci´on de un cie o n´ume o de e inamien os globales sob e una malla simple
o, po ejemplo, puede ambi´en cons ui se ealizando una iangulaci´on de De-
launay sob e la dis ibuci´on uni o me de pun os es ablecida. Conside a emos la
malla ob enida como el ni el m´as bajo de la secuencia que de ine la dis ibuci´on
de los pun os en el es o de las capas. Sob e es a malla egula aplicamos a con-
inuaci´on el algo i mo de e inamien o y des e inamien o, [26, 83], pa a de ini la
dis ibuci´on de los nodos de la capa co espondien e a la supe icie del e eno. Pa-
a ello, en p ime luga se cons uye una unci´on que in e pola las co as ob enidas
a pa i de una digi alizaci´on de la opog a ´ıa de la zona ec angula es udiada.
En segundo luga , ealizamos una se ie de e inamien os globales sob e la malla
uni o me has a consegui una malla egula capaz de cap a la a iaci´on opog ´a-
ica del e eno. El m´aximo g ado de disc e izaci´on iene de inido po el ni el de
de alle de la digi alizaci´on. Pos e io men e, se ealiza ´a un des e inamien o sob e
es os ´ul imos ni eles de malla u ilizando como pa ´ame o de des e inamien o el
m´aximo e o de co as pe mi ido en e la supe icie eal del e eno y la supe icie
de inida median e la in e polaci´on a ozos ob enida con la malla bidimensional
esul an e.
Una ez que se ha de inido la dis ibuci´on de nodos sob e el e eno y sob e
el plano supe io del dominio, comenzamos a dis ibui los nodos si uados en e
ambas capas. Es a dis ibuci´on se puede ealiza median e di e en es es a egias,
en las que in e iene una unci´on de espaciado e ical . La ca ac e ´ıs ica unda-
men al de es a unci´on es que el g ado de disc e izaci´on ob enido sob e la e ical
debe disminui con la al u a, o a lo sumo man ene se cons an e.
Es a nube de pun os se ´a u ilizada po nues o mallado idimensional basado
en la iangulaci´on de Delaunay. Pa a e i a posibles p oblemas de con o midad
con la supe icie del e eno, se p opone cons ui la malla de e aed os con la
ayuda de un pa alelep´ıpedo auxilia . Sob e su ca a in e io se si ´uan odos los
nodos dis ibuidos sob e el e eno, p oyec ados sob e un plano ho izon al si uado
a la al u a de inida po la co a m´ınima de la egi´on de es udio, y sob e su ca a
supe io se si ´uan los pun os dis ibuidos en el plano supe io del dominio a su
al u a eal. Es o conlle a una ans o maci´on de coo denadas, a endiendo a la
unci´on de espaciado sob e cada e ical, pa a si ua el es o de pun os en el
MALLAS ADAPTATIVAS 36
pa alelep´ıpedo auxilia . Es os de alles nos asegu a ´an que la dis ancia m´axima
en e dos pun os consecu i os sob e la misma e ical del dominio eal se ´a siemp e
igual o in e io que la co espondien e dis ancia es ablecida en el pa alelep´ıpedo
auxilia .
Se de ine la nube de pun os en el dominio eal y se analiza la ans o maci´on
en e el dominio eal y el pa alelep´ıpedo auxilia en el que se cons uye la malla
median e una e si´on del m´e odo de iangulaci´on de Delaunay [24]. P oponemos
cua o es a egias di e en es pa a de e mina el n´ume o de pun os gene ados so-
b e la e ical de cada nodo de la malla bidimensional adap ada a la supe icie
del e eno, y analizamos las ca ac e ´ıs icas undamen ales de cada una de ellas.
Las dos p ime as es a egias gene an pun os sob e capas de inidas en e el e eno
y la on e a supe io del dominio. En es os dos casos, el n´ume o de capas ea-
les que se desea c ea se ´a in oducido como da o. En la p ime a es a egia el
g ado de concen aci´on de las capas hacia el e eno se impone, mien as que en
la segunda se ob iene au om´a icamen e en unci´on del ama˜no de los elemen os
exis en es en la malla bidimensional adap ada a la supe icie del e eno. En las
dos ´ul imas es a egias las capas gene adas se ´an i uales, es deci , no se de ine
un n´ume o conc e o de supe icies in e io es al dominio sob e las que se si ´uan los
pun os. Po ello, di emos que en es as dos ´ul imas es a egias el n´ume o de capas
es a iable, y se ´a calculado au om´a icamen e en unci´on de los ama˜nos de los
elemen os exis en es en la malla bidimensional que de ine el e eno, o, ambi´en,
en la co espondien e a la on e a supe io del dominio. En conc e o, la e ce a
es a egia concen a ´a los pun os hacia el e eno en unci´on del ama˜no de los
elemen os de inidos sob e ´el. En cambio, la ´ul ima es a egia de e mina au om´a-
icamen e, pa a cada nodo del e eno, una unci´on de espaciado e ical con el
obje o de espe a las dis ancias desde el p ime pun o gene ado has a el e eno,
y desde el ´ul imo pun o gene ado has a la on e a supe io , en unci´on de los
ama˜nos de los elemen os exis en es sob e ambas supe icies.
Una ez que se ha cons uido la iangulaci´on de Delaunay de la nube de pun-
os en el pa alelep´ıpedo, p ocedemos a si ua los pun os en sus posiciones eales
man eniendo la opolog´ıa de la malla. Hay que ene en cuen a que es e p oceso
de comp esi´on de la malla puede da luga a c uces de e aed os que hab ´a que
GENERACI ´
ON DE MATRICES VARIABLES 37
deshace pos e io men e. Asimismo, se ´a aconsejable aplica una e apa de sua i-
zado pa a mejo a la calidad de los elemen os de la malla esul an e.
3.3. GENERACI´
ON DE MATRICES VARIA-
BLES
Pa a la disc e izaci´on median e elemen os ini os de la o mulaci´on cl´asica del
p oblema el´ıp ico que apa ece en los modelos de Campos de Vien o de Masa
Consis en e, dada po la exp esi´on (13), con las condiciones de con o no (14)
y (15) se ha u ilizado una malla de e aed os, gene ada median e las ´ecnicas
adap a i as ya desc i as.
Es o conduce a un conjun o de ma ices elemen ales de dimensi´on 4 ×4 aso-
ciadas al elemen o Ωe, siendo ˆ
ψila unci´on de o ma co espondien e a su i-´esimo
nodo, i= 1,2,3,4, de inidos en el elemen o de e e encia ˆ
Ωey|J|el jacobiano de
la ans o maci´on de Ωeaˆ
Ωe,
{Ae}ij =Zˆ
Ωe{(∂ˆ
ψi
∂ξ
∂ξ
∂x +∂ˆ
ψi
∂η
∂η
∂x +∂ˆ
ψi
∂ϕ
∂ϕ
∂x )(∂ˆ
ψj
∂ξ
∂ξ
∂x +∂ˆ
ψj
∂η
∂η
∂x +∂ˆ
ψj
∂ϕ
∂ϕ
∂x )+
+(∂ˆ
ψi
∂ξ
∂ξ
∂y +∂ˆ
ψi
∂η
∂η
∂y +∂ˆ
ψi
∂ϕ
∂ϕ
∂y )(∂ˆ
ψj
∂ξ
∂ξ
∂y +∂ˆ
ψj
∂η
∂η
∂y +∂ˆ
ψj
∂ϕ
∂ϕ
∂y )+ (3.1)
+(∂ˆ
ψi
∂ξ
∂ξ
∂z +∂ˆ
ψi
∂η
∂η
∂z +∂ˆ
ψi
∂ϕ
∂ϕ
∂z )(∂ˆ
ψj
∂ξ
∂ξ
∂z +∂ˆ
ψj
∂η
∂η
∂z +∂ˆ
ψj
∂ϕ
∂ϕ
∂z )}·|J|dξ dη dϕ
y de ec o es elemen ales de 4 ×1,
{be}i=Zˆ
Ωe−1
Th{u0(∂ˆ
ψi
∂ξ
∂ξ
∂x +∂ˆ
ψi
∂η
∂η
∂x +∂ˆ
ψi
∂ϕ
∂ϕ
∂x )+
+ 0(∂ˆ
ψi
∂ξ
∂ξ
∂y +∂ˆ
ψi
∂η
∂η
∂y +∂ˆ
ψi
∂ϕ
∂ϕ
∂y )+ (3.2)
+w0(∂ˆ
ψi
∂ξ
∂ξ
∂z +∂ˆ
ψi
∂η
∂η
∂z +∂ˆ
ψi
∂ϕ
∂ϕ
∂z )}·|J|dξ dη dϕ
N´o ese que la ma iz elemen al puede esc ibi se como
{Ae}ij ={Me}ij +{Ne}ij (3.3)
GENERACI ´
ON DE MATRICES VARIABLES 38
El ensamblaje de ales ma ices elemen ales conduce a un sis ema lineal de la
o ma:
Ax=b(3.4)
donde Aes una ma iz sim´e ica a iable del ipo
A=M+ N (3.5)
siendo M y N dos ma ices, ipo ”spa se”, di e en es, Sim´e icas De inidas Posi i-
as,(SDP), cons an es pa a un ni el de disc e izaci´on dado y el llamado pa ´a-
me o de es abilidad del modelo, ya mencionado; debiendo esol e se el sis ema
pa a cada alo di e en e de .
P ecisamen e el obje i o p incipal de es a esis consis e en plan ea p opues as
que hagan posible soluciona po m´e odos i e a i os, no demasiado cos osos, es e
ipo de sis emas de ecuaciones lineales de ma ices a iables.
Cap´ı ulo 4
ESTIMACI´
ON DE
PAR´
AMETROS
4.1. CONSIDERACIONES PREVIAS
La e iciencia de los modelos de masa consis en e pa a ajus e de campos de
ien o depende en g an medida de cie os pa ´ame os que apa ecen en las dis-
in as e apas del p oceso, especialmen e de algunos de los que in e ienen en la
cons ucci´on del campo de ien o inicial y de los m´odulos de p ecisi´on de Gauss.
En gene al, los alo es de es os pa ´ame os se oman usando una se ie de eglas
emp´ı icas. Se puede plan ea su es imaci´on de mane a au om´a ica, al que las
elocidades obse adas en las es aciones de medida sean egene adas de la o ma
m´as exac a posible po el modelo, dando luga po an o a un p oblema in e so.
Exis en di e sos m´e odos de esoluci´on de p oblemas in e sos elacionados con la
es imaci´on de pa ´ame os. De en e ellos, se han elegido los algo i mos gen´e icos,
po se una he amien a obus a y lexible, que puede se compe i i a ya que los
c´alculos pueden pa aleliza se.
Pa a el c´alculo au om´a ico de cie os pa ´ame os del modelo de ien o se plan-
ea el siguien e p oblema in e so: de las Nes aciones de medida disponibles se
oman N como e e encia; el es o, se u ilizan pa a el c´alculo del ien o. El ien o
as´ı ob enido se compa a con el medido en las N es aciones de e e encia. Pa a la
es imaci´on de los pa ´ame os del modelo se p ocede a minimiza la di e encia en e
los esul ados ob enidos y las medidas obse adas en las es aciones de e e encia.
CONSIDERACIONES PREVIAS 40
Es a ´ecnica supone una mejo a sus ancial sob e la p opues a de Ba na d [8] pa a
la es imaci´on de uno solo de los pa ´ame os po un p ocedimien o de ensayo y
e o . E. Rod ´ıguez, en su Tesis: Modelizaci´on y simulaci´on num´e ica de campos
de ien o median e elemen os ini os adap a i os en 3-D, [89], p opone ex ende lo
a un o al de cua o de los pa ´ame os que in e ienen en el modelo y au oma iza
su c´alculo; de al o ma que la unci´on a minimiza sea:
F(α, β, γ, γ0) = 1
N
N
X
n=1
|~ n−~ (xn, yn, zn)|
|~ n|
donde ~ (xn, yn, zn) es la elocidad del ien o ob enida po el modelo en la posici´on
de la es aci´on n, y N es el n´ume o de es aciones de e e encia, 1 ≤N ≤N, siendo
Nel n´ume o o al de es aciones de medida disponibles.
En p ime luga se conside a el pa ´ame o de es abilidad
α=α1
α2
= T
Th
=√
ya es ablecido como ´o mula 2.12, que se de i a del uncional 2.8, y cuyo m´ınimo
no a ´ıa si se di ide po α2
2. Hay que se˜nala que pa a α >> 1 p edomina el ajus e
de ien o en la di ecci´on e ical, mien as que pa a α << 1 el ajus e iene luga
p edominan emen e sob e el plano ho izon al. Po lo an o la elecci´on de α, ´o ,
de e mina que el ien o ienda a odea los obs ´aculos o a sob epasa los. Di e sos
expe imen os num´e icos han hecho pa en e que el compo amien o de los modelos
de masa consis en e depende sensiblemen e de la elecci´on de los alo es de , po lo
que se p es a pa icula a enci´on a es e p oblema. Di e sos au o es han es udiado
c´omo pa ame iza la es abilidad debido a que la di icul ad en la de e minaci´on
de los alo es de αhan limi ado el uso de modelos de masa consis en e en e enos
de o og a ´ıa compleja. En [103, 54, 14], los au o es p oponen oma α= 10−2, o
sea, p opo cional a la magni ud de w/u. O os, como Ross [91] y Moussiopoulos
[76], elacionan αcon el n´ume o de F oude, mien as que Geai, [38], Lalas, [58],
y Tomb ou, [108], p oponen que el pa ´ame o α a ´ıe en la di ecci´on e ical.
Finalmen e, Ba na d e al., [8], p oponen un p ocedimien o pa a ob ene αen cada
simulaci´on del campo de ien o. La idea es usa N elocidades de ien o obse adas
pa a ob ene el campo de ien o y usa las es an es N como e e encia. En onces
se ealiza ´ıan di e sas simulaciones con dis in os alo es de , lo que supond ´ıa
CONSIDERACIONES PREVIAS 41
esol e la ecuaci´on (3.4)
Ax=b
a ias eces, con i mando la idea de que es muy in e esan e pode esol e es e
ipo de ecuaciones, de ma ices a iables, de la o ma m´as e icien e posible.
El alo que m´as ace que el ien o es imado al obse ado en las es aciones de
e e encia es el que se oma como alo del pa ´ame o de es abilidad.
Es e m´e odo p opo ciona alo es de que s´olo son ´alidos pa a cada caso pa i-
cula y, po an o, no p opo ciona alo es ´alidos a p io i pa a o as simulaciones.
E. Rod iguez, en su Tesis, [89], es udia una e si´on del m´e odo p opues o po Ba -
na d e al., [8], u ilizando algo i mos gen´e icos como he amien a de op imizaci´on
que pe mi e una selecci´on au om´a ica de .
El segundo pa ´ame o a es ima es el coe icien e de peso β(0 ≤β≤1) de
la ecuaci´on 2.18, co espondien e a la in e polaci´on ho izon al de las medidas de
ien o obse adas. Cuando β→1 adquie e m´as impo ancia la dis ancia ho i-
zon al de cada pun o a las es aciones de medida, mien as que pa a β→0 se da
m´as peso a la dis ancia e ical en e cada pun o y las es aciones [70]. En gene al,
pa a e enos complejos se u iliza la segunda ap oximaci´on [79]. En o og a ´ıas m´as
llanas o en an´alisis ho izon ales en 2-D, se u iliza la p ime a. En aplicaciones m´as
ealis as exis i ´an zonas con o og a ´ıa compleja y zonas de o og a ´ıa m´as egula ,
lo que sugie e el uso de alo es in e medios de β.
El siguien e pa ´ame o obje o de es imaci´on es γ, que apa ece en la ecua-
ci´on 2.19 y es ´a elacionado con la capa l´ımi e plane a ia en la es a i icaci´on
a mos ´e ica. Exis en di e en es au o es que p oponen dis in os angos pa a es e
pa ´ame o. Pano sky y Du on, [80], p oponen el in e alo [0.15, 0.25]. Sin emba -
go, en [85] se u iliza di ec amen e el alo γ= 0,3 en el c´odigo de su p og ama
WINDS, mien as que pa a Baas, [7], γha de es a den o del in e alo [0.3, 0.4].
En nues as simulaciones el espacio de b´usqueda de γincluye odas es as posibi-
lidades.
Finalmen e, ambi´en esul a de in e ´es ob ene es imaciones de los alo es del
pa ´ame o γ0, que in e iene en el c´alculo de la al u a de la capa de mezcla en el
caso de condiciones a mos ´e icas es ables, ´ease la ´o mula (2.20). Ga a p opone
di ec amen e γ0= 0,4. Tambi´en en el c´odigo de WINDS el alo de γ0es ´a en
ALGORITMOS GENETICOS 42
o no a 0,4. As´ı, hemos de inido el espacio de b´usqueda pa a el alo de γ0en el
en o no de 0,4.
Desde el pun o de is a de es a esis, donde nos plan eamos el p econdiciona-
mien o de los sis emas de ecuaciones a iables de los modelos de campos de ien o
(3.4):
Ax=b
con iene acla a que los pa ´ame os β,γyγ0solo in e ienen en la in e polaci´on
del ien o inicial y po an o sus alo es a ec an, ´unicamen e, al c´alculo del ec o
del segundo miemb o b, mien as que el pa ´ame o de es abilidad α, ´o , a ec a
al c´alculo del ien o esul an e, ya que con ´el cambia la es uc u a de la ma iz
Apues o que iene exp esada como (3.5)
A=M+ N
A la ho a de ecu i al p econdicionamien o del sis ema pa a mejo a su e-
soluci´on po m´e odos i e a i os los alo es asignados al pa ´ame o (α) ienen un
g an p o agonismo, de ah´ı que se le dedique especial a enci´on a su es imaci´on ´op i-
ma. Pa a ello se p opone la u ilizaci´on de Algo i mos Gen´e icos, como he amien a
obus a, pa a su selecci´on.
En el Cap´ı ulo 9.2 se p esen an los esul ados de nume osos expe imen os
num´e icos, con los que se comp ueba el compo amien o de los dis in os p econ-
dicionado es p opues os, pa a una amplia gama de alo es de α()
4.2. ALGORITMOS GENETICOS
Los algo i mos gen´e icos (en los sucesi o AG) son he amien as de op imiza-
ci´on basadas en el mecanismo de e oluci´on na u al. P oducen in en os sucesi os
que ienen una p obabilidad cada ez mayo de alcanza el ´op imo global. Los as-
pec os m´as impo an es de los AG son la cons ucci´on de una poblaci´on inicial, la
e aluaci´on de cada indi iduo a a ´es de la unci´on de ap i ud o unci´on obje i o,
la selecci´on de los pad es de la siguien e gene aci´on, el c uce de esos pad es pa a
c ea los hijos y la mu aci´on, que inc emen a la di e sidad.
En la igu a 4.1 puede e se una ep esen aci´on esquem´a ica del uncionamien o
de los AG. Se pa e de una poblaci´on inicial a la que se some e a p ueba a a ´es
SUBESPACIOS DE KRYLOV 48
En los m´e odos i e a i os , a pa i de un ec o inicial, x0, se gene a una
secuencia de ec o es (xi), que con e ge a la soluci´on buscada. A pesa de la
con e gencia ela i amen e len a, el ca ´ac e spa se de Ahace posible e ec ua un
ele ado n´ume o de i e aciones sin un abajo excesi o. Po o a pa e, los e o es
de edondeo, impo an es en los m´e odos di ec os, in luyen, po lo gene al, en la
elocidad de con e gencia, pe o no en la ap oximaci´on inal.
Adem´as de los m´e odos cl´asicos de es e ipo, (Jacobi, Gauss-Seidel, SOR y
SSOR) que se ajus an a es as p ecisiones, se han desa ollado o os que p esen an
mayo es en ajas espec o a los mismos, sob e odo en es os sis emas spa se. En e
ellos han adqui ido ´ul imamen e especial ele ancia los algo i mos basados en los
Subespacios de K ylo [94]. La ´apida e oluci´on expe imen ada po los sis emas
in o m´a icos ha con ibuido a acili a su implemen aci´on [41].
5.2. SUBESPACIOS DE KRYLOV
En los m´e odos i e a i os, los sucesi os alo es de la soluci´on ap oximada en
la esoluci´on de A x =b, ienen dados po la elaci´on de ecu encia
xi+1 =xi+B−1(b−A xi) (5.1)
´o bien
B xi+1 =C xi+b, siendo C =B−A(5.2)
Di e en es elecciones pa a las ma ices ByC, en unci´on de la ma iz A, conducen
a los m´e odos cl´asicos de elajaci´on (Jacobi, Gauss-Seidel, SOR).
Pe o es as exp esiones ambi´en se pueden esc ibi en unci´on del ec o esiduo,
i=b−A xi
con lo cual
xi+1 =xi+B−1 1
De es a o ma, eligiendo una ap oximaci´on inicial, x0, los alo es de las sucesi as
i e aciones se pod ´ıan calcula po las espec i as exp esiones:
x1=x0+B−1 0
SUBESPACIOS DE KRYLOV 49
x2=x1+B−1 1=x0+B−1 0+B−1(b−A x1) =
=x0+B−1 0+B−1(b−A xo−A B−1 0) = x0+B−1 0+B−1( 0−A B−1 0) =
=x0+ 2B−1 0−B−1A B−1 0
x3=x2+B−1 2
x4=x3+B−1 3
.........................
.........................
xi=xi−1+B−1 i−1
En el caso de que B=Iqueda ´ıa:
x1=x0+ 0
x2=x0+ 2 0−A 0
x3=x2+ 2=x0+ 2 0−A 0+ (b−A x2) =
=x0+ 2 0−A 0+ (b−A x0+ 2 A 0−A2 0) =
=x0+ 2 0−A 0+ ( 0+ 2 A 0−A2 0) =
=x0+ 3 0+A 0−A2 0
x4=x3+ 3
.........................
.........................
xi=xi−1+ i−1
Es deci , la i-´esima i e aci´on de la soluci´on ap oximada se puede exp esa como
la suma de la ap oximaci´on inicial y una combinaci´on lineal de i ec o es:
xi=x0+C.L.{ 0, A 0, A2 0, ......, Ai−1 0}
Po an o
xi=x0+ [ 0, A 0, A2 0, ......, Ai−1 0] (5.3)
El subespacio Ki(A; 0), de base [ 0, A 0, A2 0, ......, Ai−1 0], es llamado subes-
pacio de K ylo de dimensi´on i, co espondien e a la ma iz Ay esiduo inicial
M´
ETODO DEL GRADIENTE 50
0
5.3. M´
ETODO DEL GRADIENTE
En los sis emas de ecuaciones lineales A x =b, cuya ma iz de coe icien es
es Sim´e ica y De inida Posi i a (SDP), el m´e odo del G adien e ´o del M´aximo
Descenso es una buena he amien a pa a su esoluci´on.
Sea A∈ <n×nuna ma iz SDP y b∈ <n. Se conside a como soluci´on ´op ima
x∈ <ndel sis ema A x =b, aquella que minimiza la unci´on de e o :
E(x) = A e(x), e(x)∈ < /E(x) : <n→ < (5.4)
siendo e(x), el e o de una soluci´on, = x−¯x, ∈ <n, en la que ¯xes la soluci´on
exac a del sis ema y (x), el esiduo, = b−A x =A¯x−A x =A(¯x−x).
Minimiza E(x) = A(x−¯x), x−¯x=A x−A¯x, x−¯x=A x, x−2A¯x, x+
A¯x, ¯x, implica, pues o que A¯x, ¯xes cons an e, ob ene el m´ınimo pa a la
unci´on A x, x−2A¯x, x= 2J(x), siendo
J(x) = 1
2A x, x−b, x/J(x) : <n→ < (5.5)
No cabe duda que encon a una soluci´on x, lo m´as ce cana posible a ¯xpasa
po minimiza J(x).
La condici´on necesa ia pa a que una unci´on de a ias a iables, di e enciable,
alcance un alo m´ınimo en x, es que su g adien e sea ce o:
g ad J(x) = J0(x) = 1
2A x, x0
−b, x0
=1
2{[(A x)0]Tx+(x0)TA x}−(x0)Tb=
=1
2(ATx+A x)−b=1
2(AT+A)x−b= 0
Si adem´as Aes sim´e ica:
J0(x) = A x −b(5.6)
La na u aleza del pun o c ´ı ico depende ´a del signo de
J00 (x) = A
Si Aes de inida posi i a, no cabe duda que la soluci´on del g adien e nulo se co-
esponde ´a con un m´ınimo del e o , y, en es e caso, con la soluci´on exac a.
La en aja de u iliza J(x), es que el p oblema de op imiza x∈ <nes eem-
plazado po un p oblema unidimensional que se puede desc ibi como sigue:
M´
ETODO DEL GRADIENTE 51
I. E alua Jcon una ap oximaci´on inicial x0.
II. De e mina una di ecci´on a pa i de x0que p oduzca una descenso en J.
III. Calcula cuan o debemos mo e nos en esa di ecci´on pa a ob ene una mejo
soluci´on x1.
IV. Vol e al paso I, eemplazando x0po x1.
P oceso de i e aci´on, que esc ibi emos como:
xi+1 =xi+αipi(5.7)
donde pies un ec o di ecci´on y αi, un escala , que de e mina emos minimizando
J(xi) a lo la go de pi:
J(xi+αipi) = minαJ(xi+α pi)
con xi, pi∈ <n ijos:
(α) = J(xi+α pi) = 1
2(xi+α pi)TA(xi+α pi)−bT(xi+α pi) =
=1
2α2pT
iA pi+αpT
i(A xi−b) + 1
2xT
i(A xi−2b)
El pun o c ´ı ico de la unci´on pa ab´olica (α) se puede de e mina haciendo
0(α) = 0:
0(α) = αpT
iA pi+pT
i(A xi−b) = 0
y eniendo en cuen a que 00 (α) = pT
iA pi, siendo Auna ma iz de inida posi i a,
se co esponde ´a con un m´ınimo, po lo cual
αi=αop (xipi) = pT
i(b−A xi)
pT
iA pi
= i, pi
A pi, pi(5.8)
El conocimien o del ac o αinos pe mi e ambi´en es ablece , con acilidad,
una o mulaci´on i e a i a pa a el ec o esiduo:
As´ı, pa iendo de la exp esi´on 5.7, podemos ans o ma la con las ope aciones
siguien es:
A xi+1 =A xi+αiA pi
b−A xi+1 =b−A xi−αiA pi
i+1 = i−αiA pi(5.9)
M´
ETODO DEL GRADIENTE 52
Fo mulaci´on que nos a a pe mi i demos a que cualquie ec o esiduo e-
sul a siemp e o ogonal a la di ecci´on de descenso an e io . En e ec o, ecu iendo
al p oduc o escala de ambos ec o es, end emos:
i+1, pi= i, pi−αiA pi, pi=
= i, pi− i, pi
A pi, piA pi, pi= 0
esul ado nulo que con i ma su o ogonalidad.
Sabemos que el g adien e de una unci´on, en un pun o, de ine la di ecci´on
de la de i ada di eccional m´axima y adem´as iene el sen ido en que aumen a la
unci´on; po an o, pa ece l´ogico, que pa a minimiza la unci´on J(x) omemos
como di ecci´on de descenso, pi, la del ec o g adien e, pe o en sen ido con a io,
o sea
pi=−∇J(xi) = −J0(xi)
y que seg´un 5.6, se con e i ´a en
pi=b−A xi= i
po lo que la ´o mula de i e aci´on se con e i ´a en:
xi+1 =xi+αi i(5.10)
y la o mulaci´on i e a i a pa a el ec o esiduo se ans o ma ´a en:
i+1 =b−A xi+1 =b−A(xi+αi i) = i−αiA i(5.11)
dando luga al algo i mo siguien e [94]:
ALGORITMO DEL GRADIENTE
Valo inicial: x0
0=b−A x0
pa a i= 0,1,2, .... has a la con e gencia, hace :
αi= i, i
A i, i
xi+1 =xi+αi i
i+1 = i−αiA i
M´
ETODO DEL GRADIENTE CONJUGADO 53
5.4. M´
ETODO DEL GRADIENTE CONJUGA-
DO
Hemos is o en el m´e odo an e io , que la condici´on
J(x)≤J(x+α p),∀α∈ <
supone consegui el alo ´op imo de xen la di ecci´on p, lo que implica que cada
nue o ec o esiduo es o ogonal a la di ecci´on de descenso an e io y, a su ez,
dicha di ecci´on de descenso iene dada po un ec o opues o al g adien e de J(x),
que coincide con el ec o esiduo, con lo que esul a ´a:
i+1⊥piy pi≡ i⇒ i+1⊥ i
La di icul ad del M´e odo del G adien e eside en que es a elaci´on de o ogonalidad
no es ansi i a, es deci si bien i+1⊥ iy i+2⊥ i+1, es o no supone que i+2⊥ i
y, po consiguien e, con las sucesi as i e aciones se aya pe diendo la condici´on de
op imizaci´on de x.
Pa a man ene es a condici´on, se debe abaja con unas di ecciones de des-
censo, que a di e encia del M´e odo del G adien e, conse en los equisi os de o -
ogonalidad con espec o a odas las di ecciones an e io es y que po an o odas
las di ecciones sean conjugadas.
Seg´un hemos is o an e io men e, si x0es un alo ´op imo de xen la di ecci´on
p esul a que:
x0=x+α p ⇒ 0⊥p
Hallemos aho a un nue o alo x00 en una nue a di ecci´on q:
x00 =x0+α q
el nue o esiduo se ´a
00 =b−Ax00 =b−A(x0+α q) = b−Ax0−α A q = 0−α A q
pa a que el nue o alo 00 siga siendo ´op imo espec o a la di ecci´on de pdebe ´a
cumpli se que 00 ⊥p, es deci :
0−α A q, p= 0
M´
ETODO DEL GRADIENTE CONJUGADO 54
o sea
0, p−αA q, p= 0
como
0⊥p⇒ 0, p= 0 ⇒A q, p= 0
y, po an o, se dice que los ec o es pyq, que cumplen dicha condici´on, son A
conjugados; como adem´as la ma iz Aes sim´e ica y de inida posi i a, podemos
a i ma que pyqson A-o ogonales.
En lo sucesi o usa emos di ecciones de descenso p0, p1, p2, ......pique sean A-
o ogonales dos a dos, es deci , al que:
pT
i·A pj= 0,∀i6=j
.
Adem´as, eniendo en cuen a que la ma iz Aes sim´e ica y de inida posi i a,
podemos comp oba que el conjun o de los ec o es p0, p1, p2, ......pi,A-o ogonales,
esul an se linealmen e independien es.
En e ec o, si exis e una colecci´on de coe icien es escala es αk, al que:
α0p0+α1p1+α2p2+...... +αipi= 0
se cumpli ´a ambi´en que:
α0A p0+α1A p1+α2A p2+...... +αiA pi= 0
que mul iplicando escala men e po p0, se con ie e en
α0pT
0A p0+α1pT
0A p1+α2pT
0A p2+...... +αipT
0A pi= 0
como po hip´o esis odos los pT
i·A pj,∀i6=j, son nulos, esul a ´a que α0pT
0A p0=
0 y al se Ade inida posi i a implica ´a que:
α0= 0
De o ma simila se puede demos a pa a cualquie
αk/ k = 1,2, .....i ⇒ ∀k∈ {0,1,2, ....i}, αk= 0
y po an o odos los ec o es A-o ogonales se ´an linealmen e independien es.
M´
ETODO DEL GRADIENTE CONJUGADO 55
El M´e odo del G adien e Conjugado [50, 52, 1, 84] iene a se una a ian e del
M´e odo del G adien e, en el que las sucesi as di ecciones de descenso se gene an
como e siones conjugadas de los g adien es que se an ob eniendo seg´un p og esa
el m´e odo. Cada nue a di ecci´on,pi+1, se ob iene en el plano o mado po las
di ecciones o ogonales i+1 ypisiguiendo la exp esi´on
pi+1 = i+1 +βipi(5.12)
de e min´andose el escala βide al o ma que pi+1 ypisean A-o ogonales, es
deci :
pT
i+1 A pi= 0
po an o
( i+1 +βipi)TA pi= ( T
i+1 +βipT
i)A pi= 0
esul ando
βi=− T
i+1 A pi
pT
iA pi
=−A pi, i+1
A pi, pi(5.13)
lo que nos a a ga an iza que los esiduos sucesi os sean o ogonales, o sea que
i+1, i= 0
.
En e ec o:
i+1 = i−αiA pi
po an o
i+1, i= i−αiA pi, i= i, i−αiA pi, i=
= i, i−αiA pi, pi−βi−1pi−1= i, i−αiA pi, pi+αiβi−1A pi, pi−1
pe o eniendo en cuen a que piypi−1son A-o ogonales, y el alo de αi, esul a ´a
que
M´
ETODO DEL GRADIENTE CONJUGADO 56
i+1, i= i, i− i, pi
= i, i− i, i+βi−1pi−1
= i, i− i, i−βi−1 i, pi−1
= 0
Como consecuencia de odo lo an e io , se puede a i ma que es e M´e odo del
G adien e Conjugado iene dos p opiedades esenciales:
A) Cada di ecci´on de descenso es A-o ogonal a odas las di ecciones an e io es,
con lo cual no se pie de la condici´on de ´op imo de cada nue o ec o , x, hallado:
Pa iendo de cada p oduc o A pi+1, pi= 0, se puede comp oba ´acilmen e que
A pi+1, pk= 0, pa a 0≤k≤i.
B) P escindiendo de los e o es de edondeo, el M´e odo con e ge a lo sumo en
ni e aciones [112], siendo nel o den de la ma iz cuad ada A:
En e ec o, omando como base que i+1, pi= 0, se puede demos a con acilidad
que
i+1, pk= 0, pa a 0≤k≤i.
o sea, que cada ec o esiduo es o ogonal a odas las di ecciones de descenso
an e io es.
Aho a bien, pa a k < n −1, puede ocu i que k= 0, con lo cual b−A xk=
0, hab ´ıamos encon ado ya la soluci´on co ec a y el M´e odo con e ge ´ıa en k
i e aciones.
Pe o mien as k6= 0, hab ´a un esiduo no nulo, cada ez m´as peque˜no. As´ı
llega ´ıamos has a n, que se ´ıa o ogonal a p0, p1, p2, ......pn−1, que son n ec o es
linealmen e independien es y A-o ogonales , con lo cual n end ´ıa que se nulo
y po an o b−A xn= 0, con lo que hab ´ıamos llegado a la soluci´on exac a, y po
an o a la ´ul ima y n-sima i e aci´on.
P ecisamen e los n ec o es, p0, p1, p2, ......pn−1, linealmen e independien es,
de inen un subespacio de ndimensiones, A-o ogonales, que esul a se un Subes-
pacio de K ylo , co espondien e a la ma iz A=<n×n, de ec o inicial p0, que
se hace co esponde con el esiduo inicial 0.
M´
ETODO DEL GRADIENTE CONJUGADO 57
Hay que se˜nala , sin emba go, que en la p ´ac ica, la apa ici´on de e o es de
edondeo, hace que las di ecciones de descenso no sean exac amen e A-o ogonales
y, po an o, que el G adien e Conjugado se compo e como un m´e odo i e a i o
cualesquie a [4].
El esquema p incipal del algo i mo del G adien e Conjugado consis e en ob e-
ne
xi+1 =xi+αipi
sabiendo, po la exp esi´on (5.8), que
αi= i, pi
A pi, pi
es el escala ´op imo, que minimiza la unci´on e o ,
y omando cada di ecci´on de descenso, seg´un (5.12), como
pi+1 = i+1 +βipi
siendo
βi=−A pi, i+1
A pi, pi
que nos pe mi e man ene la o ogonalidad en e odas las di ecciones ´op imas,
pi.
Teniendo, adem´as, en cuen a la exp esi´on (5.9), de i e aci´on de los esiduos:
i+1 = i−αiA pi
Las condiciones de o ogonalidad del p oceso, en e ec o es esiduo y di ec-
ciones de descenso, nos an a pe mi i exp esa αiyβide o ma m´as sencilla, de
al mane a que hagan es e algo i mo m´as e icien e:
As´ı
αi= T
ipi
pT
iA pi
= T
i( i+βi−1pi−1)
pT
iA pi
= T
i i+βi−1 T
ipi−1
pT
iA pi
= T
i i
pT
iA pi
= i, i
A pi, pi
OTROS M´
ETODOS DE KRYLOV 64
p oblema de m´ınimos cuad ados que plan ean es os m´e odos; es deci , haciendo
una ac o izaci´on LU, en luga de la ac o izaci´on QR adicional [36].
5.5.3. M´
ETODOS BASADOS EN LA ECUACI´
ON NOR-
MAL
La esoluci´on del sis ema de ecuaciones A x =b, donde la ma iz Aes no sim´e-
ica, es equi alen e a esol e el sis ema ATA x =ATbde ma iz ATA, sim´e ica
de inida posi i a, al que se puede aplica el algo i mo del G adien e Conjugado.
La ecuaci´on
ATA x =ATb
ecibe el nomb e de Ecuaci´on No mal.
Al igual que el CG, los m´e odos desa ollados a pa i de la Ecuaci´on No mal
cumplen las dos condiciones undamen ales de minimizaci´on de la no ma esidual
y op imizaci´on del cos e compu acional, si emba go p esen an el incon enien e
de que el condicionamien o del nue o sis ema es el cuad ado del sis ema inicial:
K(ATA) = K(A)2, lo cual, pa a sis emas mal condicionados, puede esul a de-
sas oso y adem´as en cada i e aci´on apa ecen dos p oduc os ma iz po ec o
co espondien es a las ma ices AyATaumen ando el cos e compu acional. Re-
sul an as´ı m´e odos como:
El M´e odo CGN(M´e odo del G adien e Conjugado pa a la Ecuaci´on No -
mal). Es e m´e odo cons uye una sucesi´on de ec o es:
xk=x0+hAT 0,(ATA)AT 0,(ATA)2AT 0, ....., (ATA)k−1AT 0i
con esiduo m´ınimo en cada paso, sin e ec ua el c´alculo expl´ıci o del p oduc o
ATA.
El M´e odo LSQR(Leas -Squa e QR). P opues o po Paige y Saunde s, en
1982 [78]. Es e m´e odo in en a co egi el posible empeo amien o del n´ume o de
condici´on de los sis emas al aplica el m´e odo de la Ecuaci´on No mal.
OTROS M´
ETODOS DE KRYLOV 65
La idea b´asica del LSQR es halla la soluci´on del sis ema sim´e ico:
I A
AT−λ2I
x
=
b
0
minimizando,
A
λI
x−
b
0
2
donde λes un n´ume o eal a bi a io.
Cap´ı ulo 6
PRECONDICIONAMIENTO
6.1. CONSIDERACIONES PREVIAS
Aunque los m´e odos i e a i os basados en los subespacios de K ylo es ´an,
e´o icamen e, bien undamen ados, casi odos ellos adolecen de len i ud en la con-
e gencia, p incipalmen e aquellos que se usan pa a esol e p oblemas que su gen
de emas como din´amica de luidos o simulaciones de mecanismos elec ´onicos.
P econdiciona un sis ema es un paso cla e pa a el ´exi o de los m´e odos de K ylo
que se usan en es as aplicaciones [74].
Es ampliamen e econocido que la al a de obus ez es una de las debilidades
de los m´e odos i e a i os, es e incon enien e ha impedido la amplia acep aci´on de
es os m´e odos en aplicaciones indus iales, a pesa de su in ´ınseco a ac i o pa a
esol e g andes sis emas de ecuaciones lineales. Tan o la e icacia, como la obus ez
de las ´ecnicas i e a i as pueden mejo a se con el uso de los p econdicionado es.
P econdiciona es simplemen e un medio de ans o ma un sis ema lineal o iginal
en o o que enga la misma soluci´on, pe o que sea m´as ´acil de esol e po m´e odos
i e a i os. En gene al la iabilidad de es os m´e odos dependen mucho m´as de la
calidad del p econdicionado , que del m´e odo de K ylo elegido.
Encon a un buen p econdicionado pa a esol e un sis ema lineal spa se es ´a
conside ado, con ecuencia, como una combinaci´on de a e y ciencia [94]. algunos
m´e odos de p econdicionamien o uncionan so p esi amen e bien, a pesa de sus
escasas expec a i as e´o icas.
N´o ese que en p incipio no hay i ualmen e l´ımi es pa a elegi opciones que
CONDICIONAMIENTO DE UN SISTEMA 67
pe mi an ob ene buenos p econdicionado es. Po ejemplo, los p econdicionado-
es pueden de i a se del conocimien o de los p oblemas ´ısicos de los que su ge
el sis ema lineal o pueden cons ui se a pa i de la ma iz de coe icien es del
sis ema o iginal. En l´ıneas gene ales un p econdicionado es cualquie o ma ex-
pl´ıci a o impl´ıci a de modi icaci´on de un sis ema lineal o iginal que lo haga m´as
´acil de esol e po un m´e odo i e a i o dado. El sis ema esul an e debe pode se
esol e po un m´e odo basado en los subespacios de K ylo y deben eque i se
menos pasos pa a su con e gencia, que si se aplica a el mismo m´e odo al sis ema
o iginal (Aunque es o no pueda ga an iza se e´o icamen e, sino con i ma se con
la expe iencia).
En de ini i a, pa a esol e cie os p oblemas es indispensable la implemen a-
ci´on de un p econdicionado adecuado pa a asegu a la con e gencia del m´e odo
de K ylo elegido.
En es a secci´on in oduci emos ideas gene ales sob e p econdicionamien o de
sis emas y elaciona emos algunos de los p econdicionado es m´as u ilizados pa a
esol e sis emas de ma iz sim´e ica de inida posi i a, que son los que su gen en
los modelos de campos de ien o.
6.2. CONDICIONAMIENTO DE UN SISTEMA
Decimos que un sis ema de ecuaciones, A x =b, es ´a bien o mal condicionado,
cuando peque˜nas a iaciones en sus coe icien es, o en sus ´e minos independien es,
p oducen una peque˜na ´o g an a iaci´on en la soluci´on del mismo. Con obje o de
da una medida del buen o mal condicionamien o de un sis ema se in oduce la
noci´on de n´ume o de condici´on ( ela i o a una no ma ma icial dada) [15, 32].
Limi ´andonos al caso m´as sencillo, si se p oduce una pe u baci´on, ∆b, en el
ec o columna de los ´e minos independien es, amos a analiza la pe u baci´on,
∆x, que se p oduci ´a en la soluci´on exac a, x, del sis ema. Empleando una no -
ma ma icial a bi a ia y una no ma ec o ial cualquie a, compa ible con ella, se
end ´a:
A x =b
A(x+ ∆x) = b+ ∆b
⇒A∆x= ∆b
CONDICIONAMIENTO DE UN SISTEMA 68
∆x=A−1∆b
b=A x
⇒
k∆xk≤k A−1k k ∆bk
kbk≤k Ak k xk
⇒
k∆xk k bk≤k Ak k A−1k k ∆bk k xk ⇒
⇒k∆xk
kxk≤k Ak k A−1kk∆bk
kbk
Al ac o kAk k A−1k=K(A), se le denomina n´ume o de condicionamien o del
sis ema, ela i o a la no ma ma icial k·k; ob eni´endose as´ı la siguien e elaci´on
del e o ela i o de la soluci´on, en unci´on del e o ela i o en los ´e minos in-
dependien es:
k∆xk
kxk≤K(A)k∆bk
kbk(6.1)
E iden emen e, cuan o meno sea el alo num´e ico, K(A), meno se ´a la a iaci´on
de la soluci´on an e las posibles luc uaciones en los alo es de los elemen os de b.
Dicho n´ume o se ´a siemp e mayo o igual que la unidad:
1≤k Ik=kA·A−1k≤k Ak k A−1k=K(A) (6.2)
Cuan o m´as p ´oximo a la unidad sea K(A), mejo condicionado es a ´a el sis ema:
l´ım
K(A)→1k∆xk/kxk
k∆bk/kbk= 1
Con iene esal a que el n´ume o de condici´on, K(A), del sis ema A x =b, es una
can idad in ´ınseca a su ma iz de coe icien es, A. En o as palab as, el condicio-
namien o del sis ema es independien e del ec o b, de ´e minos independien es.
De o ma simila , si denominamos ∆Aa las a iaciones in oducidas en los
coe icien es de la ma iz, no cabe duda que el sis ema se ans o ma ´a en
(A+ ∆A)(x+ ∆x) = b
A pa i del cual, como en el caso an e io , se puede comp oba ´acilmen e que:
k∆xk
kx+ ∆xk≤k Ak k A−1kk∆Ak
kAk
lo que nos indica que el e o ela i o de la nue a soluci´on es ambi´en unci´on del
e o ela i o p oducido po las a iaciones de la ma iz de coe icien es y, ambos,
es ´an elacionados po el mismo n´ume o K(A), ya de inido an e io men e.
T´
ECNICAS DE PRECONDICIONAMIENTO 69
Po an o, cuan o m´as ce cano a 1 es ´e el n´ume o de condicionamien o, K(A),
an o meno se ´a la a iaci´on de la soluci´on del sis ema, an e las posibles luc ua-
ciones en los alo es, an o de los elemen os de A, como de by po an o se di ´a
que el sis ema es ´a mejo condicionado.
Usando la no ma espec al k · k2, K(A) = µM
µm≥1, donde µMyµmson,
espec i amen e, los alo es singula es m´aximo y m´ınimo de la ma iz del sis-
ema, alo es que se pueden calcula po µi=pλi(AAT), siendo λi(AAT) los
co espondien es alo es p opios de AAT.
Cuando Aes sim´e ica,µi(A)≡λi(A), y el n´ume o de condicionamien o se ´ıa
K(A) = λM
λm≥1
Con es a de inici´on, dado que la bondad del condicionamien o de una ma iz
iene dada, en p incipio, po la p oximidad de K(A) a la unidad, en el caso que los
alo es singula es ex emos coincidie an, el n´ume o de condicionamien o adqui i ´ıa
es e alo ´op imo.
6.3. T´
ECNICAS DE PRECONDICIONAMIEN-
TO
En nume osas ocasiones, la ma iz y el ec o segundo miemb o del sis ema se
calculan de o ma ap oximada, pudiendo exis i cie as di e encias con los alo es
num´e icos que e lejen exac amen e el p oblema. En es os casos, un mal condicio-
namien o del sis ema a ec a ´ıa nega i amen e a la con e gencia.
Se hace necesa io as´ı, mejo a es e condicionamien o u ilizando adecuadas ´ec-
nicas de p econdicionamien o. T´ecnicas que, en gene al, consis en en ans o ma
el sis ema en o o de id´en ica soluci´on, pe o con meno K(A).
Pa a ello mul iplica emos la exp esi´on A x =bpo una ma iz M, llamada
ma iz de p econdicionamien o:
M A x =M b
al que
K(M A)< K(A).
T´
ECNICAS DE PRECONDICIONAMIENTO 70
El meno alo de K(M A) co esponde ´ıa a M=A−1, pues o que queda ´ıa
K(A−1A) = 1, que es, ob iamen e, el caso ideal y el sis ema con e ge ´ıa en una
sola i e aci´on, pe o el cos e compu acional del c´alculo de A−1equi ald ´ıa a esol e
el sis ema po un m´e odo di ec o.
Es a ci cuns ancia sugie e pa a Muna ma iz lo m´as p ´oxima posible a A−1,
sin que su de e minaci´on suponga un ele ado cos e. Gene almen e, se op a po
conside a como ma iz de p econdicionamien o a M−1, y ob ene Mcomo ap o-
ximaci´on de A, esc ibiendo,
M−1A x =M−1b
Los o denado es, con m´ul iples p ocesado es en pa alelo, o ecen una g an e -
sa ilidad [92]. G o e y Simon [47] p oponen ob ene Mcomo ap oximaci´on de
A−1, minimizando una no ma que educe el c´alculo a npeque˜nos p oblemas inde-
pendien es de m´ınimos cuad ados. Asimismo, en [102] y [77] se plan ea e ec ua
es a ap oximaci´on po una exp esi´on polin´omica P(A). El campo de posibles p e-
condicionado es aplicables en o denado es que no engan es as ca ac e ´ıs icas es
ambi´en muy amplio.
Po o o lado, en los algo i mos p econdicionados de los dis in os m´e odos
igu a ´an p oduc os de ma iz in e sa po ec o , que no deben exigi excesi o
abajo adicional, po ello, la ma iz Mdebe se ´acilmen e in e ible. Po ejemplo
una ma iz diagonal, o una ma iz ac o izada adecuadamen e pa a e ec ua esos
p oduc os po p ocesos de emon e, sin necesidad de calcula M−1.
Dependiendo de la o ma de plan ea el p oduc o de la in e sa de la ma iz de
p econdicionamien o po la ma iz del sis ema, y ap o echando la descomposici´on
en ac o es de aquella, se dis inguen los siguien es casos:
-a) P econdicionamien o po la izquie da:
M−1A x =M−1b
M−1A=˜
A
M−1b=˜
b
˜
A x =˜
b
-b) P econdicionamien o po la de echa:
A M−1M x =b
A M−1=˜
A
M x = ˜x
˜
A˜x=b
-c) P econdicionamien o po ambos lados:
T´
ECNICAS DE PRECONDICIONAMIENTO 71
Exp esando M ac o izada como M=M1M2,
M−1
1AM−1
2M2x=M−1
1b
M−1
1AM−1
2=˜
A
M2x= ˜x
M−1
1b=˜
b
˜
A˜x=˜
b
Las ca ac e ´ıs icas de cada p oblema y, en de ini i a, de la ma iz A, del p e-
condicionado u ilizado Me, incluso, de la ole ancia exigida pa a el c i e io de
pa ada adop ado, hacen m´as e icien e una o ma u o a de p econdicionamien o,
sin que pueda es ablece se a p io i bases de elecci´on que nos inclinen po una de
ellas.
El p econdicionamien o de un sis ema iene po inalidad mejo a la con e gen-
cia del m´e odo aplicado espec o a la con e gencia del sis ema sin p econdiciona .
En la esoluci´on de sis emas sim´e icos, la az´on de con e gencia del G adien e
Conjugado
kx−xikA≤2 pK(A)−1
pK(A)+1!i
kx−x0kA
depende del n´ume o de condicionamien o K(A), unci´on de los au o alo es mayo
y meno de la ma iz del sis ema. Sin emba go, en la p ´ac ica, despu´es de cie -
o n´ume o de i e aciones la con e gencia se hace supe lineal, como si el n´ume o
de condicionamien o inicial uese sus i uido po o o meno , de al o ma que la
az´on de con e gencia depende, adem´as, de la dis ibuci´on o al de los alo es
p opios de A. Las ´ecnicas de p econdicionamien o, ienen po obje o ans o ma
el sis ema o iginal A x =b, en o o, con o a nue a ma iz ˜
A, con unos nue os
au o alo es que conduzcan a una con e gencia m´as ´apida, bien disminuyendo el
n´ume o de condicionamien o K(A), bien mejo ando la dis ibuci´on de los au o a-
lo es m´as peque˜nos del espec o [48, 113]. Las dis in as i e aciones xi, del sis ema
p econdicionado e i ica ´an:
kx−xik˜
A≤2
qK(˜
A)−1
qK(˜
A)+1
i
kx−x0k˜
A
con
xi∈x0+Ki(˜
A; ˜ 0).
En los sis emas no sim´e icos, es complicado p oba que el sis ema p econdi-
cionado esul an e posee un espec o de au o alo es que mejo e la con e gencia
M´
ETODO DEL GRADIENTE CONJUGADO PRECONDICIONADO 72
espec o al sis ema o iginal. Pe o, po analog´ıa, y, a´un sin demos aciones ma-
em´a icas que lo con i men, se pod ´ıa espe a un compo amien o simila . Es a
conclusi´on, co obo ada num´e icamen e en odas las aplicaciones, pe mi e a a
´ecnicas de p econdicionamien o en los m´e odos ipo doble-g adien e, al igual que
se u iliza en el G adien e Conjugado, con las sal edades co espondien es que
con emplen la no sime ´ıa del sis ema.
6.4. M´
ETODO DEL GRADIENTE CONJUGA-
DO PRECONDICIONADO
Dado que en la Modelizaci´on de los Campos de Vien o el ipo de ma ices
que apa ecen en sus Sis emas de Ecuaciones, son Sim´e icas De inidas Posi i as
(SDP), el mejo m´e odo i e a i o pa a esol e las es el del G adien e Conjugado
(GC), cuyo algo i mo ya ha sido expues o an e io men e (Secci´on 4.4). Teniendo
en cuen a, adem´as, que median e un P econdicionamien o adecuado se consigue
mejo a la con e gencia del p oceso i e a i o, es po ello que adop amos, como
m´e odo m´as adecuado pa a la esoluci´on de los Sis emas de Ecuaciones o iginados
en los Modelos de Campos de Vien o, el del G adien e Conjugado P econdicio-
nado (GCP) [74]. De hecho, odos los ejemplos ealizados, cuyos esul ados se
ecogen en el apa ado de Expe imen os Num´e icos, han sido a on ados con es e
p ocedimien o, po conside a lo el m´as id´oneo, dado que el ipo de ma ices sob e
las que se aplica son SDP.
En los casos de P econdicionamien o expues os an e io men e, an o po la
izquie da, como po la de echa, aunque la ma iz o iginal del sis ema, A, sea
Sim´e ica De inida Posi i a, las nue as ma ices p econdicionadas, ˜
A, an o
˜
A=M−1A
como
˜
A=A M−1
en gene al, no ienen po que con inua siendo Sim´e icas, de ah´ı la necesidad
de in oduci es a egias que al P econdiciona con in´uen conse ando la Sime-
´ıa, pa a que el m´e odo del G adien e Conjugado no pie da, sino que mejo e, su
PRECONDICIONADORES EXPL´
ICITOS 79
N´o ese la simpli icaci´on que supone que, pa a el c´alculo de los p oduc os in-
e nos, s´olo se equie e el uso de las ilas de A, lo cual hace el p ocedimien o
bas an e a ac i o, pues o que no es necesa io almacena expl´ıci amen e la ma iz
Acomple a.
Una ez calculados ZyD, la soluci´on del sis ema A x =b, puede compu a se
como
x∗=A−1b=Z D−1ZTb=
n
X
i=1 zT
ib
pizi
Aunque Asea una ma iz spa se, el cos e de es a algo i mo, aplicado al como
se ha desc i o, lo hace in iable, ya que Z iende a se una ma iz densa. Pa a
e i a es e e ec o ill-in, con o me se an ob eniendo los ec o es zi, se e ec ´ua la
simpli icaci´on de desp ecia aquellas en adas in e io es en alo absolu o a una
cie a ole ancia p e ijada 0 ≤δ≤1.
Llamando ˜
Za la ma iz iangula ob enida:
A−1≈˜
Z˜
D−1˜
ZT
que se ´ıa la incomple a ac o izada de A.
6.6.2. PRECONDICIONADOR SAINV
Aunque no es ecuen e, el algo i mo AINV puede conduci (pa a ma ices
A,SDP) a alo es de pi(en adas de la diagonal p incipal) nulos o nega i os.
En el p ime caso, en cuan o se ob u ie a un pice o, no pod ´ıa p osegui el
p oceso,pues o que los pison denominado es en las ´o mulas de ecu encia que
se u ilizan en el algo i mo AINV pa a calcula las zj
i, y, si lo que ocu e, es la
apa ici´on de un pi<0,como A−1≈Z D−1ZT, da ´ıa luga a una ap oximada
in e sa que ya no es De inida Posi i a
E iden emen e, es o no ocu e en el caso e´o ico de calcula exac amen e los
alo es de zi, ya que siendo A, Sim´e ica De inida Posi i a, la exp esi´on (6.9)
esul a ´a
pi=zT
iA zi>0.
PRECONDICIONADORES EXPL´
ICITOS 80
La az´on de es e b eakdown es la siguien e:
Los pi o es pi, en adas de la diagonal p incipal, D, se ob ienen, seg´un el algo i mo
AINV, po la elaci´on
pi=p(i−1)
i=aT
iz(i−1)
i=
i−1
X
l=1
ailzl−1
li +aii (1 ≤i≤n),
si hacemos ce o algunas de las en adas de los ec o es zi, algunos de los p o-
duc os ailzli desapa ece ´ıan y, en el caso gene al de A, SDP, es os sumandos que
se eliminan pueden esul a posi i os con lo que ealmen e es amos haciendo, al
p escindi de ellos, es disminui el alo e´o icamen e posi i o de los pi, pudiendo
llega a hace se nulos o nega i os.
Llamando ˜zia los ec o es modi icados (al elimina las en adas in e io es a δ),
pa a algunas ma ices puede ocu i que el c´alculo de los co espondien es pi o es
sea:
˜pi=aT
i˜zi˜zT
iA˜zi
con lo cual se a pe diendo la o ogonalidad de los ec o es ˜zi, aumen ando as´ı las
p obabilidades del b eakdown.
Pa a obus ece el p oceso, [12], el algo i mo SAINV p opone que los ˜pise
compu en usando la exp esi´on
˜pi= ˜zT
iA˜zi,
p ocedimien o algo m´as cos oso que el del AINV, pe o m´as segu o y que ga an iza
la no up u a del mismo.
As´ı el c´alculo de los ˜pise puede exp esa como
˜pi= ˜ T
i˜zidonde ˜ T
i= ˜zT
iA.
La di e encia de cos e depende ´a de cuan o m´as denso esul e el ec o ˜ ien
compa aci´on con aT
i. Los expe imen os ealizados demues an que el esul ado del
nue o p ocedimien o da luga a un p econdicionado de m´as al a calidad y cos e
muy pa ecido al an e io , con lo cual compensa de ini i amen e el uso de una
ap oximaci´on algo m´as cos osa.
Po odo ello, el nue o algo i mo de la ac o izaci´on in e sa es abilizada (SAINV)
puede esc ibi se de la siguien e o ma:
PRECONDICIONADORES IMPL´
ICITOS 81
ALGORITMO SAINV
(1) Hace z(0)
i=ei(1 ≤i≤n)
(2) Pa a i= 1,2, ..., n hace
i=A zi−1
i
(3) pa a j=i, i + 1, ..., n hace
p(i−1)
j= T
iz(i−1)
j
in.
si i=ni a (4)
pa a j=i+ 1, ..., n hace
z(i)
j=z(i−1)
j− p(i−1)
j
p(i−1)
i!z(i−1)
i
in.
in.
(4) Hace zi=z(i−1)
iypi=p(i−1)
i,pa a 1 ≤i≤n.
Vol e a Z= [z1, z2, ...., zn] y D=diag(p1, p2, ..., pn)
Ob iamen e los algo i mos AINV y SAINV [30] son ma em´a icamen e equi a-
len es; sin emba go, con el es abilizado se consigue una ap oximada in e sa m´as
iable. Aplic´andolo a cualquie ma iz SDP se ob iene un p oceso sin up u as.
6.7. PRECONDICIONADORES IMPL´
ICITOS
6.7.1. POR COMPARACI´
ON CON EL M´
ETODO DE RI-
CHARDSON
El m´e odo de Richa dson, m´e odo i e a i o muy simple, de elaci´on de ecu-
encia
xi+1 =xi+α(b−A xi)
PRECONDICIONADORES IMPL´
ICITOS 82
con α > 0, pe mi e, po compa aci´on con o os m´e odos i e a i os, de ini cie a
ma ices u ilizables como p econdicionado es.
Pa a ello, con as a emos la ´o mula de ecu encia pa a la soluci´on que e-
sul a de aplica el m´e odo Richa dson al sis ema p econdicionado po una ma iz
gen´e ica M, con la ´o mula co espondien e que se ob iene aplicando los m´e odos,
e´o icamen e supe io es, de Jacobi, SOR y SSOR al sis ema sin p econdiciona .
-P econdicionado de Jacobi ´o Diagonal
Aplicando el m´e odo de Richa dson al sis ema p econdicionado
M−1A x =M−1b
queda, pa a el c´alculo de los sucesi os alo es de la soluci´on:
xi+1 =xi+α(M−1b−M−1A xi)
y, mul iplicando po la ma iz de p econdicionamien o, esul a:
M xi+1 =M xi+α(b−A xi).(6.10)
Po o o lado, conside ando la descomposici´on de la ma iz Ade la o ma
A=D−E−F, (siendo Dla ma iz diagonal o mada po los elemen os de la
diagonal p incipal de AyE,Fma ices iangula es), y u ilizando el m´e odo de
Jacobi pa a la esoluci´on del sis ema A x =b, esul a,
xi+1 =D−1(E+F)xi+D−1b
mul iplicando po la ma iz diagonal, y ope ando:
D xi+1 =D xi+ (b−A xi).(6.11)
Compa ando las exp esiones de ecu encia inales de ambos m´e odos, (6.10)
y (6.11), se obse a que el m´e odo de Jacobi aplicado al sis ema sin p econdiciona ,
equi ale al de Richa dson, con α= 1, menos obus o y m´as simple, cuando se
aplica al sis ema p econdicionado con la ma iz diagonal D=diag(A).
Resul a as´ı un p econdicionado elemen al, que se conoce como p econdicio-
nado Diagonal, ´acil de implemen a y con ma iz in e sa que se de e mina con
PRECONDICIONADORES IMPL´
ICITOS 83
muy bajo cos e compu acional.
-P econdicionado SOR
Aplicando el m´e odo SOR al sis ema A x =b, y con la misma descomposici´on
an e io A=D−E−F, queda pa a la ´o mula de ecu encia de la soluci´on:
xi+1 = (D−w E)−1[(1 −w)D+w F]xi+w(D−w E)−1b,
donde wes el llamado pa ´ame o de elajaci´on y, ope ando con enien emen e
esul a:
(D−w E)xi+1 = (D−w E)xi+w(b−A xi).(6.12)
Compa ando de nue o con el m´e odo de Richa dson aplicado al sis ema p econ-
dicionado, (6.10), de ini ´ıamos, en es a ocasi´on, la ma iz de p econdicionamien o
como:
M= (D−w E).
-P econdicionado SSOR
Aplicando aho a el m´e odo SSOR al sis ema sin p econdiciona , se ob iene
pa a la soluci´on:
xi+1 =D
w−F−11−w
wD+ED
w−E−11−w
wD+Fxi+
+D
w−F−12−w
wDD
w−E−1
b
ope ando, pa a exp esa es a elaci´on de o ma que se pueda compa a con la (6.10),
queda
1
w(2 −w)(D−wE)D−1(D−wF)xi+1 =1
w(2 −w)(D−wE)D−1(D−wF)xi+(b−A xi)
(6.13)
con lo que esul a como ma iz de p econdicionamien o
1
w(2 −w)(D−wE)D−1(D−wF).
En el caso de aplica es e p econdicionado a sis emas sim´e icos, ya que en
es os casos, (D−wF) = (D−wE)T, se puede exp esa como un p oduc o de dos
PRECONDICIONADORES IMPL´
ICITOS 84
ma ices iangula es anspues as,
M="(D−wE)D−1/2
pw(2 −w)#"(D−wE)D−1/2
pw(2 −w)#T
Pa a sis emas no sim´e icos, se puede esc ibi como p oduc o de dos ma ices
iangula es, in e io y supe io , espec i amen e
M= (I−wED−1)D−wF
w(2 −w)
6.7.2. POR FACTORIZACIONES INCOMPLETAS
La p opiedad que en p incipio, debe e i ica una ma iz de p econdicionamien-
o M, de se una ap oximaci´on, m´as o menos ce cana, de la ma iz de coe icien es
del sis ema, sugie e que un p ocedimien o pa a ob ene la sea el descompone Ade
la o ma A≈A1A2, de al mane a, que no suponga un excesi o es ue zo compu-
acional, y adop a pa a la misma
M=A1A2
Adem´as de o as ac o izaciones posibles des aca emos dos de ellas: la basada en
la ac o izaci´on en dos ma ices iangula es LU, usualmen e u ilizada en la eso-
luci´on de sis emas po m´e odos di ec os, y la ac o izaci´on incomple a de Cholesky
.
-P econdicionado ILU(0)
Resul a de descompone Aen dos ma ices iangula es, in e io y supe io ,
espec i amen e, LyU,
A≈LU =M
cuyos elemen os, mij, sean ales que:
mij = 0 si aij = 0
(A−LU)ij = 0 si aij 6= 0
PRECONDICIONADORES IMPL´
ICITOS 85
es deci , que los elemen os nulos de la ma iz del sis ema, con in´uen siendo nulos
en las posiciones espec i as de las ma ices iangula es.
Si no ealiz´a amos es a simpli icaci´on, el cos e compu acional se inc emen a ´ıa
y equi ald ´ıa a esol e el sis ema po un m´e odo di ec o.
-P econdicionado ILU(n)
Pa a las ma ices idiagonales o pen adiagonales que esul an de la disc e-
izaci´on de p oblemas con ecuaciones en de i adas pa ciales el´ıp icas, se pueden
p ac ica o os ni eles de ac o izaci´on, consis en es en ellena alguna diagonal
de las ma ices ac o es de la descomposici´on, que en ILU(0) se ´ıan nulas. La
ap oximaci´on se ´ıa mayo a cos a de inc emen a el abajo compu acional de la
descomposici´on.
-Fac o izaci´on incomple a de Cholesky
Es ´a especialmen e indicado pa a ac o iza ma ices Sim´e icas De inidas Po-
si i as, (SDP).Su obje i o consis e en descompone Aen es ma ices, una ma iz
cen al diagonal y dos ma ices la e ales: una iangula in e io y su anspues a.
Sea A= (aij) una ma iz n×n, SDP. En o den a ealiza su ac o izaci´on
podemos conside a la o mada po
A= (aij) =
a11 T
1
1A2
o sea, compues a po : su p ime elemen o, a11; una ma iz columna, (n−1)×1, 1,
o mada po los elem os de su p ime a columna menos el p ime o; su anspues a,
la ma iz ila, 1 ×(n−1), T
1y la ma iz A2, (n−1) ×(n−1), SDP, esul ado de
elimina la p ime a ila y la p ime a columna de la ma iz inicial A.
A pa i de es a es uc u a, como p ime paso de su ac o izaci´on, ´acilmen e
puede descompone se en un p oduc o de es ma ices, de la siguien e o ma:
A= (aij) =
a11 T
1
1A2
=
a11 0
1I
a−1
11 0
0C2
a11 T
1
0I
=L1Z1LT
1
Siendo Ila ma iz unidad y C2una ma iz (n−1) ×(n−1), SDP, ob enida a
pa i de A2, al que:
C2=A2−1
a11
1 T
1= (aij)(2),∀i, j ≥2
PRECONDICIONADORES IMPL´
ICITOS 86
en la que, po an o, su p ime elemen o se ´a:
(a22)(2) =a22 −a2
12
a11
.
Es a nue a ma iz C2, as´ı ob enida, a su ez puede es uc u a se de la misma
o ma que se hizo con la ma iz inicial A:
C2= (aij)(2) =
a(2)
22 T
2
2A3
Siendo 2una ma iz columna (n−2)×1 y A3una ma iz SDP, (n−2)×(n−2).En
o den a e i a el e ec o ill-in, que apa ece ´a al calcula los elemen os (ai2)(2), pa a
i≥3, co espondien es a la ma iz columna 2y su anspues a, ealiza emos una
ap oximaci´on, omando en su luga una nue a ma iz columna, l2, que enga las
mismas en adas que 2, pe o man eniendo nulas aquellas que lo son en la ma iz
inicial A, y as´ı esul a ´a:
C2= (aij)(2) =
a(2)
22 T
2
2A3
≈
a(2)
22 lT
2
l2A3
nue a ma iz, igual de spa se que la inicial, que ol emos a ac o iza de la misma
o ma an e io , en una ma iz cen al y dos iangula es a ambos lados:
C2= (aij)(2) ≈
a(2)
22 lT
2
l2A3
=
a(2)
22 0
l2I
a(2)−1
22 0
0C3
a(2)
22 lT
2
0I
siendo aho a
C3= (aij)(3) =A3−1
a(2)
22
l2lT
2
una ma iz SDP, (n−3) ×(n−3),∀i, j ≥3.
En dicha ma iz su p ime a en ada aho a se ´a:
a(3)
33 =a(2)
33 −a(2)2
23
a(2)
22
.
Con las ac o izaciones ealizadas has a aho a, eniendo en cuen a que 1=l1,
la ma iz inicial Ase pod ´a descompone de la siguien e o ma:
A≈
a11 0
l1I
1 0 0
0a(2)
22 0
0l2I
a−1
11 0 0
0a(2)−1
22 0
0 0 C3
1 0 0
0a(2)
22 lT
2
0 0 I
a11 lT
1
0I
=
PRECONDICIONADORES IMPL´
ICITOS 87
=L1L2Z2LT
2LT
1
p oduc o de una ma iz cen al y dos ma ices iangula es a cada lado.
Con inuando con la ac o izaci´on de C3, de o ma simila a la an e io , puede
descompone se la ma iz inicial como:
A≈
a11 0
l1I
1 0 0
0a(2)
22 0
0l2I
1 0 0 0
0 1 0 0
0 0 a(3)
33 0
0 0 l3I
a−1
11 0 0 0
0a(2)
22
−10 0
0 0 a(3)
33
−10
0 0 0 C4
1 0 0 0
0 1 0 0
0 0 a(3)
33 lT
3
0 0 0 I
1 0 0
0a(2)
22 lT
2
0 0 I
a11 lT
1
0I
=L1L2L3Z3(L1L2L3)T
Y p ocediendo de la misma o ma, al llega a la n-sima ac o izaci´on esul a ´a:
A≈L1L2L3.....LnZn(L1L2L3.....Ln)T=L D LT
al que
L=
a11 000··· 0
a12 a(2)
22 0 0 ··· 0
a13 a(2)
23 a(3)
33 0··· 0
a14 a(2)
24 a(3)
33 a(4)
44 ··· 0
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
a1na(2)
2na(3)
3na(4)
44 ···a(n)
nn
y
PRECONDICIONADORES IMPL´
ICITOS 88
D=
a−1
11 000··· 0
0a(2)
22
−10 0 ··· 0
0 0 a(3)
33
−10··· 0
0 0 0 a(4)
44
−1··· 0
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
0 0 0 0 ···a(n)
nn
−1
Con lo cual queda ´a la ma iz Aap oximadamen e igual a un p oduc o de dos
ma ices iangula es la e ales, LyLT, y una ma iz cen al diagonal.
Los p econdicionado es impl´ıci os m´as usuales son el DIAGONAL y el ILU(0).
El DIAGONAL, es con mucho, el que menos es ue zo compu acional exige. Se
calcula di ec amen e omando los elemen os de la diagonal p incipal de Ay los
p oduc os ma iz in e sa po ec o se e ec ´uan, asimismo, de o ma inmedia a.
Sin emba go su aplicaci´on se e educida, pues o que en muchos sis emas mal con-
dicionados, ep esen a i os de p oblemas ´ısicos con capas l´ımi es, singula idades
o condiciones de con o no especiales, no mejo an sus ancialmen e la con e gencia.
Los p econdicionado es ILU(0), exigen m´as es ue zo compu acional inicial pa-
a su cons ucci´on y los p oduc os de ma iz in e sa po ec o se ealizan po
p ocesos de emon e, pe o su aplicaci´on da luga a buenos esul ados en sis emas
que con el p econdicionado DIAGONAL no con e gen.
ALGORITMO MULTICOLORING (MC) 94
En gene al el n´ume o de colo es necesa ios no excede ´a al del m´aximo g ado
de cada nodo +1.
Una ez asignados los colo es a odos los nodos del g a o asociado a la ma iz,
se eo dena ´es a eag upando odos los ´e ices, es deci , odos los elemen os de
la diagonal p incipal, del mismo colo ; as´ı se consigue una nue a es uc u a de la
ma iz eo denada po bloques, en la que los bloques diagonales se ´an p ecisamen e
ma ices diagonales y el n´ume o de bloques coincidi ´a con el n´ume o de colo es.
El es o de las en adas con igu a an dos ma ices iangula es spa se si uadas a
ambos lados de los bloques diagonales.
Si bien la ´ecnica del mul icolo ing esul a muy ba a a, al u iliza los p e-
condicionado es ILU(0) puede ocu i , seg´un Saad, que el n´ume o de i e aciones,
necesa ias pa a alcanza la con e gencia, p obablemen e esul e mucho m´as al o
p econdicionando la ma iz con el eo denamien o mul icolo , que p econdicionan-
do la ma iz o iginal di ec amen e.
Cap´ı ulo 8
PRECONDICIONAMIENTO DE
SISTEMAS DE ECUACIONES
LINEALES DE MATRIZ
VARIABLE
8.1. PROPUESTA DE ESTRATEGIA
El obje i o p incipal de es a esis consis e en ex ende las ´ecnicas de P econ-
dicionamien o, as´ı como las de Reo denaci´on, a los sis emas de ecuaciones lineales
de ma ices a iables [105, 96], que su gen de la modelizaci´on de campos de ien o
[75], que como ya se ha is o an e io men e, son del ipo:
Aεxε=bε
donde ε ep esen a el pa ´ame o de es abilidad del modelo y
Aε=M+ε N
siendo MyNma ices cons an es pa a un ni el de disc e izaci´on dado y, adem´as,
Sim´e icas De inidas Posi i as (SDP), po lo que, pa a su esoluci´on, u iliza emos
siemp e el algo i mo del G adien e Conjugado P econdicionado.
Pa a p econdiciona es os sis emas se pod ´ıa ecu i , en p incipio, a dos es-
a egias ex emas:
PROPUESTA DE ESTRATEGIA 96
a) Po un lado, se pod ´ıa cons ui un ´unico p econdicionado pa a un cie o
alo de ε,εo, y lo aplica ´ıamos pa a la esoluci´on de los dis in os sis emas que
su gen pa a cada alo de , lo que conduci ´a a con e gencias cada ez m´as len as
a medida que los alo es de εse ayan alejando del alo inicial.
b) Po o o lado, y´endonos al ex emo opues o, usa ´ıamos un p econdicionado
di e en e pa a cada sis ema, o sea pa a cada alo de ε, lo que esul a ´ıa muy
cos oso.
En es a esis se p opone una soluci´on in e media, que consis e en cons ui
un p econdicionado , que pueda se ac ualizado ´acilmen e pa a cada alo de ε,
y cuya aplicaci´on al algo i mo del G adien e Conjugado de luga a elocidades
de con e gencia comp endidas en e las conseguidas al aplica las es a egias ex-
emas mencionadas. Con lo que en de ini i a se consegui ´a mejo a el g ado de
e icacia del algo i mo a u iliza en la esoluci´on del sis ema.
Es e ipo de soluci´on in e media ya ha sido p opues o po Benzi [11] y Meu an
[65], independien emen e, usando cada uno de ellos un modelo de P econdiciona-
do di e en e que, a un bajo cos e compu acional, se adap an ´acilmen e pa a cada
alo del pa ´ame o, ε; es a egia que conduce a consegui un g ado de con e gen-
cia, con el algo i mo del G adien e Conjugado P econdicionado, in e medio en e
las con e gencias alcanzables usando las dos opciones ex emas.
Benzi desa olla su es udio u ilizando un P econdicionado Expl´ıci o, median e
la cons ucci´on de In e sas Ap oximadas, usando el algo i mo SAINV, pa a el caso
especial de ma ices a iables, Aε, del ipo
Aε=M+ε I
siendo Ila ma iz uni a ia.
Sin emba go Meu an lo hace pa a la ma iz
Aε=M+ε D
siendo D una ma iz diagonal y conside ando un P econdicionado Impl´ıci o, a
pa i de una Fac o izaci´on Incomple a de Cholesky de la ma iz M.
ADAPTACI ´
ON DEL PRECONDICIONADOR SAINV 97
8.2. ADAPTACI´
ON DEL PRECONDICIONA-
DOR SAINV
En es e es udio, p oponemos segui un camino pa alelo al p opues o po Benzi
[97] pa a el caso especial de ma ices a iables del ipo:
Aε=M+ε I
siendo Muna ma iz SDP e Ila ma iz uni a ia; pe o ex endi´endolo al caso m´as
gen´e ico de
Aε=M+ε N
Con el algo i mo SAINV, ya expues o en el Cap´ı ulo 6, (6.6.2), se puede cons-
ui una in e sa ap oximada ac o izada de una ma iz A, SDP, a pa i de la
ob enci´on po cong uencia de una o ma diagonal de la misma:
ZTA Z =D=diag(d1, d2, ....., dn)
median e la ma iz iangula supe io Z= [z1, z2, ....., zn] conseguida po un
p oceso de A-conjugaci´on de G and-Schmid , a pa i del conjun o de ec o es
uni a ios linealmen e independien es {e1, e2, ....., en} ∈ <n, donde
dj=zT
jA zj>0,1≤j≤n.
Si ealizamos el p oceso de c´alculo de los ec o es zide o ma incomple a, des-
ca ando, en cada caso, las en adas espec i as meno es de una cie a ole ancia
escogida, δ, al que: 0 < δ < 1, se ob iene una ma iz spa se ap oximada de Z,
que denominamos ˜
Z, con la que se pod ´a cons ui la ma iz ap oximada in e sa
de A:
A−1≈˜
Z˜
D−1˜
ZT.
Pues bien, aplicando dicho algo i mo, se puede ob ene una ap oximada in e sa
de M:
M−1≈˜
Z˜
D−1˜
ZT=P−1
y, a pa i de ah´ı, se conside a un p econdicionado pa a Aε=M+ε N de la
o ma:
P−1
ε=˜
Z(˜
D+ε E)−1˜
ZT
ADAPTACI ´
ON DEL PRECONDICIONADOR SAINV 98
donde Ese ´ıa una ma iz gen´e ica, sim´e ica, a de e mina , ´acilmen e compu-
able, que haga a ( ˜
D+ε E) Sim´e ica De inida Posi i a y al que los p oduc os
P−1
εpo ec o , que igu an en el G adien e Conjugado, no supongan un cos e
ele ado.
A e ec os de de ini Ey, dando po supues o que la in e sa exac a de Mse ´ıa
M−1=Z D−1ZT, se es ablece la di e encia
Pε−Aε=Z−T(D+ε E)Z−1−(M+ε N) = ε(Z−TEZ−1−N).
Si se oma a E=ZTNZ, esul a ´ıa: Pε−Aε= 0, con lo cual se consegui ´ıa el
p econdicionado ideal
P−1
ε=A−1
ε.
E iden emen e, es o no es iable, dado que no se dispone de la ma iz Z, sino de
su ap oximaci´on ˜
Z, pe o ello sugie e como mejo exp esi´on pa a la ma iz E:
E=˜
ZTN˜
Z
y as´ı, de es a o ma, Ecumpli ´ıa con las condiciones necesa ias mencionadas
an e io men e.
En luga de inicia el p oceso con la ob enci´on de la ap oximada in e sa de
M, que se co esponde con la ap oximada in e sa de Aε=M+ε N, pa a ε= 0,
se puede ob ene inicialmen e una ap oximada in e sa de Aε0=M+ε0N. Y as´ı
las sucesi as ma ices, pa a los dis in os alo es de εse esc ibi ´ıan:
Aε=M+ε N =Aε0−ε0N+ε N =Aε0+ ∆ε N
donde ∆ε=ε−ε0.
Dado que εes siemp e posi i o, la ma iz Aε, ob iamen e, es de inida posi i a,
aunque ∆εsea nega i o.
De odo ello esul a que la ap oximada in e sa se ´ıa:
A−1
ε0≈˜
Z˜
D−1˜
ZT=P−1
ε0
y el p econdicionado pa a la ma iz a iable:
P−1
ε=˜
Z(˜
D+ ∆ε E)−1˜
ZT
ADAPTACI ´
ON DE LA FACTORIZACI ´
ON DE CHOLESKY 99
siendo po supues o E=˜
ZTN˜
Z, al igual que an es y con las mismas p es aciones.
Una opci´on pa a cons ui E, con los equisi os p e is os, es oma una ap o-
ximaci´on de ˜
Zque nomb a emos como ˜
Zk, que se ob iene ex ayendo solamen e
su diagonal p incipal, si k= 1, y adem´as sus k−1 diagonales supe io es, si k > 1,
y conside ando pa a Nla ap oximaci´on Nh, ex ayendo su diagonal p incipal, si
h= 1, y las h−1 diagonales secunda ias pa a h > 1. Con lo cual denomina emos
Eh,k =˜
ZT
kNh˜
Zk
En la p ´ac ica, a e ec os de no inc emen a el cos e po i e aci´on del G adien e
Conjugado, esul a ´u il conside a las pa ejas h= 1 y k= 2 ´o h= 2 y k= 1,
que dan luga , espec i amen e, a las ma ices E1,2´o E2,1, idiagonales. Incluso
se puede consegui una mayo simpli icaci´on conside ando h=k= 1, esul ando
as´ı la ma iz E1,1, diagonal.
8.3. ADAPTACI´
ON DE LA FACTORIZACI´
ON
DE CHOLESKY
Aqu´ı op amos po gene aliza la ac o izaci´on incomple a de Cholesky, p o-
pues a po Meu an [98] pa a el caso de ma ices Aε=M+εD, siendo Duna
ma iz diagonal, al caso m´as gene al de las ma ices Aε=M+ε N, siendo MyN
dos ma ices sim´e icas de inidas posi i as n×n. As´ı pod emos esc ibi Aεcomo
sigue:
Aε= (mij) + ε(nij) =
m11 +εn11 ( 1M+ε 1N)T
1M+ε 1NM2+εN2
donde 1M, 1N ep esen an ma ices columnas ((n−1,1) y M2, N2ma ices de
o den n−1.
Fac o izando Aε,
Aε=
m11 +εn11 0
l1M+εl1NI
(m11 +εn11)−10
0C2
m11 +εn11 (l1M+εl1N)T
0 I
con lo que nos queda,
Aε=L1Z1LT
1(8.1)
ADAPTACI ´
ON DE LA FACTORIZACI ´
ON DE CHOLESKY 100
siendo l1M= 1Myl1N= 1N.
Iden i icando, ´e mino a ´e mino, se ob iene pa a la ma iz C2:
C2=M2+εN2−1
m11 +εn11
(l1M+εl1N) (l1M+εl1N)T(8.2)
Si, a e ec os de cons ui el p econdicionado , omamos como p ime a ap oxima-
ci´on s´olo los elemen os de la diagonal de N, se ´ıa l1N= 0, quedando
C2=εD2+M2−1
m11 +εn11
l1MlT
1M
y la ap oximaci´on de o den ce o,
C2=εD2+M2−1
m11
l1MlT
1M
con lo cual, las en adas de C2se ob end ´ıan ´acilmen e, a˜nadiendo εD2a la ma iz
que esul a en la ac o izaci´on de M.
O a ap oximaci´on consis e en conside a , en (8.2), odas las en adas de N2
y desp ecia los p oduc os εl1N, quedando C2, de o ma simila ,
C2=εN2+M2−1
m11
l1MlT
1M
Con inuando con es a ap oximaci´on,
C2=εN2+
m(2)
22 T
2M
2MM3
=
m(2)
22 +εn22 ( 2M+εl2N)T
2M+εl2NM3+εN3
Haciendo ce os en 2Mlas co espondien es en adas nulas de M, pa a e i a el
e ec o ill-in, ob enemos l2M.
Fac o izando C2:
C2≈
m(2)
22 +εn22 0
l2M+εl2NI
m(2)
22 +εn22−10
0C3
m(2)
22 +εn22 (l2M+εl2N)T
0 I
donde,
C3=M3+εN3−1
m(2)
22 +εn22
(l2M+εl2N) (l2M+εl2N)T.
U ilizando las mismas simpli icaciones an e io es, se consigue
C3=M3+εN3−1
m(2)
22
l2MlT
2M=
m33 +εn33 ( 3M+εl3N)T
3M+εl3NM4+εN4
ADAPTACI ´
ON DE LA FACTORIZACI ´
ON DE CHOLESKY 101
esul ando as´ı, pa a C3, la misma ley de o maci´on que se ob u o pa a C2.
Con es os c i e ios de o maci´on de las ma ices Ci, la ac o izaci´on ap oxi-
mada de Aε,queda:
Aε≈L1Z1LT
1=L1L2Z2LT
2LT
1= (L1L2···Ln)Zn(L1L2···Ln)T(8.3)
siendo Znla ma iz diagonal
(m11 +εn11)−1.
m(2)
22 +εn22−1.
m(3)
33 +εn33−1.
. . . . .
.m(n)
nn +εnnn−1
Las en adas diagonales de la ma iz iangula in e io (L1L2···Ln) se ´an m(i)
ii +
εnii. Y las espec i as columnas in e io es a los elemen os diagonales end ´an
de inidas po ma ices ljM +εljN de o den (n−j)×1.
APLICACIONES TEST 108
εICHOL(Aε0) ICHOLDICHOLNFull-ICHOL
0noI e .
(s)
-
-
-
-
-
-
184
6.21
10−6noI e .
(s)
184
5.96
184
5.99
184
6.00
184
6.21
10−5noI e .
(s)
184
5.96
184
5.99
184
6.00
184
6.23
10−4noI e .
(s)
184
5.98
184
5.99
184
6.01
184
6.21
10−3noI e .
(s)
181
5.89
181
5.90
181
5.91
181
6.12
10−2noI e .
(s)
170
5.55
170
5.56
170
5.56
169
5.73
10−1noI e .
(s)
148
4.81
135
4.43
131
4.29
126
4.35
1noI e .
(s)
232
7.50
149
4.88
105
3.46
78
2.79
10 noI e .
(s)
454
14.66
303
9.84
145
4.74
76
2.73
102noI e .
(s)
995
32.09
675
22.03
261
8.46
>5000
–
103noI e .
(s)
1452
46.58
965
31.29
354
11.50
>5000
–
104noI e .
(s)
1583
50.73
1049
33.98
384
12.45
>5000
–
105noI e .
(s)
1604
51.40
1059
34.25
388
12.57
>5000
–
106noI e .
(s)
1605
51.43
1060
34.29
388
12.58
>5000
–
Tabla 9.4: Ejemplo 2, 43.954 ecuaciones:N´ume o de i e aciones y iempo de compu-
aci´on (en s.) del G adien e Conjugado con di e en es P econdicionado es
po Fac o izaci´on Incomple a de Cholesky
APLICACIONES TEST 109
Obse ando los esul ados de la Tabla 9.4, con los P econdicionado es po
Fac o izaci´on Incomple a, podemos conclui que pa a peque˜nos alo es de εno es
necesa io adap a la ac o izaci´on inicial pues o que con ella se consigue alcanza
la con e gencia a muy bajo cos e. Sin emba go, con alo es al os de ε, el ICHOLN
iene el mejo compo amien o. Con iene ene en cuen a que pa a los alo es de
εcomp endidos en e 1 y 10 la e-compu a izaci´on de la ac o izaci´on incomple a
esul a m´as aconsejable.
APLICACIONES TEST 110
9.1.4. EJEMPLO 3
En las Tablas 9.5 y 9.7 se p esen an los esul ados conseguidos pa a el sis e-
ma de 98.999 ecuaciones, ob enido con o o e inamien o pos e io , u ilizando los
mismos ipos de P econdicionado es.
En es a caso, an o con los P econdicionado es SAINV como ICHOL, en odas
sus a ian es, la con e gencia ue ex emadamen e len a (m´as de 5000 i e aciones)
pa a alo es de ε≥104, po lo que a pa i de ε= 103ya no se ecogen los
esul ados en ambas ablas.
εFull-SAINV SAINV11 SAINV12 SAINV21 SAINV(Aε0)
0I e .
(seg.)
278
3541.68
-
-
-
-
-
-
-
-
10−6I e .
(seg.)
278
3540.47
278
25.83
278
26.70
278
30.21
278
19.04
10−5I e .
(seg.)
278
3541.55
278
25.78
278
26.71
278
30.24
279
19.05
10−4I e .
(seg.)
280
3566.12
279
25.81
278
26.73
279
30.30
279
19.08
10−3I e .
(seg.)
277
3540.38
278
25.82
276
26.61
278
30.17
276
18.37
10−2I e .
(seg.)
258
3538.34
257
24.32
258
25.31
257
28.48
256
17.39
10−1I e .
(seg.)
214
3543.85
227
22.34
229
23.21
224
25.79
307
20.82
100I e .
(seg.)
193
3524.28
283
26.14
291
27.64
275
30.00
653
44.06
101I e .
(seg.)
257
3591.23
591
47.11
589
48.93
581
54.65
1724
116.03
102I e .
(seg.)
548
3724.73
1724
124.27
1670
126.10
1659
127.71
>5000
–
103I e .
(seg.)
1290
3785.34
4234
297.10
4002
304.06
4128
305.60
>5000
–
Tabla 9.5: Ejemplo 3, 98.999 ecuaciones: N´ume o de i e aciones y iempo de compu-
aci´on (en segundos) del G adien e Conjugado pa a los dis in os P econdi-
cionado es SAINV
Una ez m´as se comp ueba que pa a alo es peque˜nos de εbas a con un
p econdicionado ´unico, el SAINV(Aε0); es especialmen e no o io que es e ipo de
p econdicionado empieza a alla a pa i de ε= 102.
Sin emba go pa a alo es de ε≥1 el SAINV11 p esen a los mejo es esul ados.
APLICACIONES TEST 111
εO den
Inicial
MN
(69,43s)
RCM
(0,70s)
MC
(0,45s)
0I e .
(s)
278
3541.68
264
3092.93
273
2757.27
263
4626.74
10−6I e .
(s)
278
25.83
265
16.35
274
16.25
263
20.13
10−5I e .
(s)
278
25.78
264
16.29
274
16.22
263
20.15
10−4I e .
(s)
279
25.81
264
16.27
273
16.18
263
20.15
10−3I e .
(s)
278
25,82
262
16.16
272
16.11
260
19.93
10−2I e .
(s)
257
24.32
236
14.61
247
14.66
240
28.40
10−1I e .
(s)
227
22.34
208
12.89
212
12.58
219
16.81
1I e .
(s)
283
26.14
261
16.15
265
15.71
270
20.69
10 I e .
(s)
591
47.11
520
32.04
549
32.32
553
42.24
102I e .
(s)
1724
124.27
1512
92.96
1589
92.23
1623
123.67
103I e .
(s)
4234
297,10
3701
227.79
3756
220.51
3924
294.04
Tabla 9.6: Ejemplo 3, 98.999 ecuaciones: N´ume o de i e aciones y iempo de compu-
aci´on (en segundos) del G adien e Conjugado con el P econdicionado
SAINV11 pa a di e en es Reo denaciones
Dado que con el p econdicionado SAINV11 se consigui´o un mejo compo a-
mien o, ue elegido pa a aplica lo ambi´en sob e los Sis emas Reo denados [28, 106]
u ilizando los Algo i mos ci ados en el Cap´ı ulo 7: M´ınimo Vecino (MN), Cu hill-
McKee In e so (RCM) y Mul icolo ing (MC). Los esul ados se ecogen en la
Tabla 9.6
APLICACIONES TEST 112
Como puede obse a se, eo denando con los Algo i mos MN y RCM, mejo a la
con e gencia del G adien e Conjugado P econdicionado. Sin emba go el Algo i mo
MC no es an e icien e, como ya e a de p e e , de acue do con los comen a ios
expues os en el apa ado 6.5 sob e su al a de e icacia.
(a) O den Inicial (b) M´ınimo Vecino
(c) Cu hill-McKee In e so (d) Mul icolo ing
Figu a 9.1: Pa ones de ‘spa sidad’ de las ma ices, con su o den inicial y una ez
eo denadas
APLICACIONES TEST 113
En la igu a 9.1 se mues an los pa ones de spa sidad de la ma iz inicial
del sis ema y de sus eo denaciones, seg´un los Algo i mos indicados. La imagen
co espondien e a la ma iz con el eo denamien o Cu hill-McKee In e so es la que
m´as se asemeja a una ma iz diagonal y en e ec o es la eo denaci´on que p oduce
mejo es esul ados. Sin emba go la simple obse aci´on del pa ´on ob enido con el
eo danamien o Mul icolo ing ya nos an icipa que los esul ados a consegui no
an a se mucho mejo es que los del G adien e Conjugado P econdicionado apli-
cado di ec amen e sob e la ma iz con su o den inicial, sob e odo pa a alo es
ele ados de ε.
En la Tabla 9.7 se puede comp oba como en es e ejemplo, pa a 98.999 ecuacio-
nes, se ob ienen esul ados simila es a los conseguidos con los p econdicionado es
ICHOL en los sis emas de 43.954 ecuaciones: en gene al, pa a peque˜nos alo es de
εno es necesa io adap a la ac o izaci´on inicial pues o que con ella se consigue
alcanza la con e gencia a muy bajo cos e. Sin emba go, con alo es al os de ε, el
ICHOLN iene el mejo compo amien o. Teniendo en cuen a que pa a los alo es
de εcomp endidos en e 1 y 10 la e-compu a izaci´on de la ac o izaci´on incom-
ple a esul a m´as e ec i a.
De o ma simila a como se hizo con los p econdicionado es SAINV, aqu´ı se ha
elegido el p econdicionado ICHOLN, po su mejo compo amien o, pa a aplica lo
sob e los sis emas eo denados y comp oba as´ı la e icacia de la Reo denaci´on en
los Sis emas de Ecuaciones Va iables. Los esul ados se ecogen en la Tabla 9.8.
En es e caso, pa a alo es de εcomp endidos en e 0 y 10, se ha conseguido
mejo a el cos e de las i e aciones con la eo denaci´on del M´ınimo Vecino y a
pa i de alo es de ε≥102los mejo es esul ados se han conseguido con el
eo denamien o de Cu hill-McKee In e so. Pe o eniendo en cuen a que el iempo
de implan aci´on del MN(69,43s.) es muy supe io al del RCM(0,7s.), en de ini i a,
la esoluci´on se aba a a mucho m´as con el Cu hill-McKee In e so.
Po lo que espec a al Mul icolo ing, pa a ning´un alos de ε, se ha conseguido
mejo a la e icacia conseguida con el ICHOLNaplicado di ec amen e a la ma iz
APLICACIONES TEST 114
εICHOL(Aε0) ICHOLDICHOLNFull-ICHOL
0noI e .
(s)
-
-
-
-
-
-
201
16.81
10−6noI e .
(s)
201
16.14
201
16.16
201
16.19
201
16.82
10−5noI e .
(s)
201
16.15
201
16.16
201
16.19
201
16.83
10−4noI e .
(s)
201
16.15
201
16.16
201
16.19
201
16.83
10−3noI e .
(s)
201
16.14
201
16.16
200
16.11
200
16.76
10−2noI e .
(s)
188
15.22
191
15.35
189
15.24
189
15.87
10−1noI e .
(s)
225
18.08
157
12.65
155
12.52
151
12.85
1noI e .
(s)
483
38.63
211
16.94
148
11.97
132
11.33
10 noI e .
(s)
1350
107.71
540
43.14
259
20.91
236
19.64
102noI e .
(s)
3973
317.16
1466
116.86
593
47.62
>5000
–
103noI e .
(s)
>5000
–
3468
277.11
1269
101.60
>5000
–
Tabla 9.7: Ejemplo 3: 98.999 ecuaciones. N´ume o de i e aciones y cos e compu acio-
nal (en s.) del G adien e Conjugado con di e en es P econdicionado es po
Fac o izaci´on Incomple a de Cholesky
inicial, lo cual e ela la ine icacia de la eodenaci´on MC con los p econdicionado es
ICHOL, con i m´andose as´ı la opini´on de Youse Saad en su ob a I e a i e Me hods
[94], donde comen a que sob e odo con los p econdicionado es ILU(0), puede ocu-
i una p´e dida de e icacia, pues o que el n´ume o de i e aciones pa a alcanza
la con e gencia puede aumen a , esul ando m´as al o que si se p econdiciona a
di ec amen e la ma iz o iginal.
APLICACIONES TEST 115
εIni ial
O de ing
MN
(69.43 s)
RCM
(0.70 s)
MC
(0.45 s)
0noI e .
(s)
201
16.81
158
12.86
175
13.84
223
24.01
10−6noI e .
(s)
201
16,19
159
12.53
175
13.46
223
22.51
10−5noI e .
(s)
201
16.19
159
12.54
175
13.45
222
22.41
10−4noI e .
(s)
201
16.19
158
12.47
176
13.53
223
22.51
10−3noI e .
(s)
200
16.11
157
12.37
174
13.38
220
22.21
10−2noI e .
(s)
189
15.24
143
11.31
160
12.30
207
20.90
10−1noI e .
(s)
155
12.52
116
9.19
131
10.12
170
17.21
1noI e .
(s)
148
11.97
123
9.73
129
9.97
160
16.20
10 noI e .
(s)
259
20,91
227
17.88
240
18.38
277
27.91
102noI e .
(s)
593
47.62
533
41.61
536
40.73
632
63.43
103noI e .
(s)
1269
101.60
1212
94.45
1177
89.23
1395
139.79
Tabla 9.8: Ejemplo 3, 98.999 ecuaciones: N´ume o de i e aciones y iempo de compu-
aci´on (en segundos) del G adien e Conjugado con el P econdicionado
ICHOLNpa a di e en es Reo denaciones
ELECCI ´
ON DEL PAR ´
AMETRO ´
OPTIMO 116
9.2. ELECCI´
ON DEL PAR´
AMETRO ´
OPTIMO
9.2.1. PRELIMINARES
Como ya se indicaba en el Cap´ı ulo 4, ESTIMACI´
ON DE PAR´
AMETROS, el
ajus e e icien e de un modelo de campo de ien o depende, en g an medida, de
la adecuada alo aci´on de los pa ´ame os que apa ecen en las dis in as e apas del
p oceso, especialmen e de aquel que in e iene de o ma b´asica en la o mulaci´on
del sis ema
(M+ε N)xε=bε
pues o que a ec a de o ma di ec a al c´alculo del ien o esul an e.
Dicho pa ´ame o, ε, de es abilidad del modelo, es ´a es echamen e elacionado
con los m´odulos de p ecisi´on de Gauss, a a ´es de las elaciones (2.12) y (2.17):
ε=α2=T
Th
=α2
1
α2
2
E. Rod ´ıguez en su Tesis Modelizaci´on y simulaci´on num´e ica de campos de ien o
median e elemen os ini os adap a i os en 3D [89], p opone la u ilizaci´on de Al-
go i mos Gen´e icos, como m´e odos de op imizaci´on basados en un mecanismo de
e oluci´on na u al, pa a ealiza la selecci´on au om´a ica del pa ´ame o ε(α), pues
se a a de una he amien a obus a, lexible, compe i i a y cuyos c´alculos pueden
pa aleliza se. Ve Cap´ı ulo 4(4.2).
Uno de los aspec os m´as impo an es de los Algo i mos Gen´e icos es la cons-
ucci´on de una poblaci´on inicial y la pos e io e aluaci´on, de cada indi iduo de la
misma, de acue do con los esul ados de su aplicaci´on a una unci´on obje i o. En
el caso de la modelizaci´on de campos de ien o se adop a como unci´on obje i o
la minimizaci´on de las di e encias en e el ien o esul an e, calculado median e
la esoluci´on del sis ema lineal Aεxε=bε, y el obse ado, en las es aciones de
e e encia. Ello lle a como consecuencia que pa a cada indi iduo de la poblaci´on
inicial hay que esol e dicho sis ema.
Luego, a eno de los esul ados conseguidos, se p ocede ´a a c ea una nue a
poblaci´on, median e ope ado es de Selecci´on, C uce y Mu aci´on, que nue amen e
hay que some e la a la e aluaci´on de la unci´on obje i o, lo cual supone ol e
a esol e el sis ema an as eces como alo es seleccionados. A pa i de es os
ELECCI ´
ON DEL PAR ´
AMETRO ´
OPTIMO 117
alo es se uel e a gene a o a nue a poblaci´on, con los mismos c i e ios, que se
uel e a e alua , y as´ı sucesi amen e, has a consegui un indi iduo que cumpla
con el c i e io de pa ada, que se ´a el alo ´op imo del pa ´ame o a conside a pa a
ese Modelo.
Ello implica que en el p oceso de selecci´on hay que esol e el sis ema Aεxε=
bε, an as eces como posibles alo es de ε(α) a es ima , mul iplicado po el n´u-
me o de i e aciones a ealiza , en cada paso sucesi o del Algo i mo Gen´e ico; po
lo que se hace necesa io dispone de m´e odos e icaces que pe mi an la implemen-
aci´on ´apida de un p econdicionado pa a cada alo del pa ´ame o. De ah´ı la
impo ancia de conoce el cos e compu acional que supone el u iliza dis in os
ipos de p econdicionado es.
Como conclusi´on de los es s ealizados an e io men e se es ableci´o, que los p e-
condicionado es basados en la Fac o izaci´on Incomple a de Cholesky, pa ecen se
la he amien a m´as e icaz pa a mejo a la con e gencia del m´e odo del G adien e
Conjugado, en la esoluci´on de los Sis emas Lineales de Ecuaciones Va iables, po
an o es os han sido los ipos de p econdicionado es elegidos pa a comp oba su
compo amien o a la ho a de e alua una poblaci´on inicial de pa ´ame os, ε(α),
de ca a a la elecci´on de su alo ´op imo median e Algo i mos Gen´e icos [29].
En es e apa ado p esen amos los esul ados ob enidos al esol e los Sis e-
mas Lineales de Ecuaciones Va iables, co espondien es a la modelizaci´on de dos
campos de ien o di e en es, usando siemp e el m´e odo del G adien e Conjugado
P econdicionado, el m´as e icaz cuando hay ma ices Sim´e icas De inidas Posi-
i as, como es el caso, y u ilizando los p econdicionado es basados en la Fac o-
izaci´on Incomple a de Cholesky, ya es udiados an e io men e, en sus a ian es
ICHOL(Aε0), ICHOLD,ICHOLNyFull −ICHOL.
Todos los expe imen os han sido ealizados en un equipo XENON P ecisi´on
530 con Fo an de Doble P ecisi´on. Los p ocesos de i e aci´on siemp e se han
iniciado a pa i de un ec o nulo y inalizados si
i
0
2≤10−10 o si el n´ume o
de i e aciones se hac´ıa supe io a 10.000.
CONCLUSIONES 123
Posi i as, SDP, se jus i ica el conside a como mejo m´e odo i e a i o pa a su e-
soluci´on, po su p obada e icacia, el G adien e Conjugado P econdicionado, GCP,
lo que conduce a ene que a on a , como no edoso, el P econdicionamien o de
Ma ices Va iables.
Dado que pa a cada alo del pa ´ame o, ε, se o igina una ma iz di e en e,
el P econdicionamien o de las mismas debe consegui se de o ma ´apida y e icaz,
pa a una amplia gama de alo es de su pa ´ame o.
Se p opone como es a egia, pa a consegui lo, la cons ucci´on de un ´unico
P econdicionado , ´acilmen e adap able a cada alo di e en e del pa ´ame o, o
sea un P econdicionado Va iable . Es o se plan ea a a ´es de dos modelos de
P econdionamien o di e en es: uno Expl´ıci o, cons uyendo In e sas Ap oxima-
das (SAINV), y o o Impl´ıci o, undamen ado en la Fac o izaci´on Incomple a de
Cholesky (ICHOL).
La amplia gama de expe imen os num´e icos ealizados, con ambos ipos de
P econdicionado es, nos pe mi e ob ene las siguien es conclusiones:
Po lo que al P econdicionamien o SAINV se e ie e, puede a i ma se que pa-
a peque˜nos alo es del pa ´ame o, ε, no pa ece en able la cons ucci´on de un
P econdicionado Va iable, bas a ´ıa con dispone de un ´unico P econdicionado ,
elabo ado a pa i de un alo inicial de ε, al que se ha denominado SAINV(Aε0).
Sin emba go, pa a alo es de ε≥1, los llamados SAINV11, SAINV12 SAINV21 p e-
sen an no ables en ajas sob e el an e io y ob iamen e esul an m´as econ´omicos
que el hecho de cons ui un P econdicionado di e en e pa a cada alo dis in o
del pa ´ame o (nomb ado como Full-SAINV). Con iene des aca que, en e odos
ellos, el que p opo ciona los mejo es esul ados es el SAINV11.
En lo que espec a a los P econdicionado es ICHOL, ocu e algo simila . En
gene al, pa a peque˜nos alo es de ε, bas a ´ıa con cons ui un ´unico P econdiciona-
do , pa a un de e minado alo inicial del pa ´ame o, el denominado ICHOL(Aε0);
pe o, pa a alo es al os de ε, el ICHOLDy el ICHOLN ienen el mejo compo a-
mien o. En especial el ICHOLNp esen a los mejo es esul ados de odos a pa i
de alo es de ε≥102, pa a los que ni el cons ui un P econdicionado di e en e
pa a cada ε(α) (Full-ICHOL), da ´ıa esul ado, pues o que as´ı no se alcanza la con-
e gencia. Es o se debe a que, pa a alo es al os de ε, al ealiza la ac o izaci´on
CONCLUSIONES 124
incomple a de la ma iz Aε, se pie de su posi i idad, con lo cual la aplicaci´on del
G adien e Conjugado esul a ines able. Sin emba go es o no ocu e con los nue os
ICHOL, el D y el N.
En los al ededo es del alo uni a io del pa ´ame o, los expe imen os ealizados
no pe mi en ob ene una conclusi´on de ini i a ace ca de cual se ´ıa la mejo es a-
egia. P obablemen e la e-compu a izaci´on pa a cada alo de εsea la elecci´on
m´as iable.
Los P econdicionado es basados en al algo i mo SAINV no son an e icien es
como los que se undamen an en la Fac o izaci´on Incomple a de Cholesky, di e-
encia que se acen ´ua, a a o de es os ´ul imos, a medida que c ece el n´ume o de
ecuaciones del Sis ema. Po ello, puede conclui se que, de odos los expe imen-
ados, el P econdicionado denominado ICHOLNes el que conduce a los mejo es
esul ados.
Teniendo en cuen a lo an e io , ambi´en puede a i ma se, que el P econdicio-
nado ICHOLNcons i uye la mejo opci´on, a la ho a de op a po selecciona , de
o ma au om´a ica, el alo ´op imo de un pa ´ame o, pa a un Campo de Vien o
de e minado, pues o que, hace posible u iliza pa a ello la po en e he amien a
de los Algo i mos Gen´e icos, al pe mi i a on a con apidez la g an can idad
de eces que se debe esol e el Sis ema, pa a una amplia gama de alo es del
pa ´ame o ε.
Po lo que espec a a la in luencia de la Reo denaci´on, p e ia al P econdicio-
namien o, podemos conclui que, pa a g andes sis emas de ecuaciones, un o den
adecuado mejo a la e icacia del m´e odo del G adien e Conjugado P econdiciona-
do, ya que con ello se p oducen P econdicionado es con mejo es cualidades que
pe mi en educi el n´ume o de pasos pa a alcanza la con e gencia. Po an o,
con una adecuada Reo denaci´on puede mejo a se la e icacia de los P econdiciona-
mien os an o con In e sas Ap oximadas, como con Fac o izaciones Incomple as
de Cholesky.
Analizando conjun amen e, no s´olo el nue o cos e de las i e aciones una ez
Reo denado el Sis ema, sino a˜nadiendo ambi´en los iempos eque idos pa a su
implan aci´on, se comp ueba que el algo i mo de Reo denaci´on m´as e ec i o es el
Cu hill-McKee In e so y en pa icula asociado con la Fac o izaci´on Incomple a
LINEAS FUTUTRAS 125
de Cholesky.
Sin emba go el algo i mo Mul icolo ing no apo a ninguna mejo a a la ejecu-
ci´on de los m´e odos i e a i os p econdicionados.
Queda pues pa en e, a modo de esumen, que el uso de los P econdicionado es
basados en la Fac o izaci´on Incomple a de Cholesky es una he amien a e icaz pa a
mejo a la con e gencia del algo i mo del G adien e Conjugado P econdicionado,
en el caso de los Sis emas Lineales de Ecuaciones Va iables, con ma ices Sim´e-
icas De inidas Posi i as; en especial el que se ha denominado como ICHOLN,
debido a su in e io cos e compu acional. Al menos hay una amplia gama de alo-
es de εpa a los cuales con dichos P econdicionado es se consiguen con e gencias
m´as ´apidas, que con el uso de los P econdicionado es ob enidos expl´ıci amen e
con la Ap oximada In e sa (SAINV) y, po supues o, mejo ando los esul ados que
se puedan consegui con un e-compu a izaci´on comple a pa a cada alo dis in o
del pa ´ame o.
10.2. LINEAS FUTUTRAS
Con es e abajo se ab en a ias l´ıneas u u as que admi en se es udiadas en
p o undidad:
En p ime luga , se ´ıa in e esan e comp oba el compo amien o del algo i mo
del G adien e Conjugado P econdicionado u ilizando ambi´en P econdicionado es
Va iables, ipos SAINV e ICHOL, simila es a los aqu´ı p opues os, pe o aplic´an-
dolos sob e Sis emas Lineales de Ma ices Va iables Sim´e icas o iginados en la
esoluci´on de o os ipos de p oblemas di e en es a la Modelizaci´on de Campos de
Vien o.
As´ı como, ambi´en se ´ıa de in e ´es, es udia los esul ados a consegui con dicho
algo i mo al aplica lo a Ma ices Va iables Sim´e icas en gene al, pe o u ilizando
P econdicionado es Va iables dis in os de los SAINV e ICHOL aqu´ı desc i os.
LINEAS FUTUTRAS 126
O as posibles l´ıneas de in e ´es, se ´ıan las que su jan al a on a el es udio de la
e icacia de nue os P econdicionado es Va iables, dis in os a los SAINV e ICHOL,
ap opiados pa a Ma ices Va iables No Sim´e icas, que se o iginen al abo da
modelizaciones di e en es a las de los Campos de Vien o y ene que ecu i a
algo i mos dis in os al G adien e Conjugado, pe o basados en los Subespacios de
K ylo , como pueden se o os m´e odos de o ogonalizaci´on, como el GMRES
o m´e odos de bio ogonalizaci´on, como el Bi-CGSTAB y los QMR, TFQMR y
QMRGCSTAB.
Finalmen e, debe se˜nala se, que incluso se ´a in e esan e amplia los es udios
indicados u ilizando o as T´ecnicas de Reo denaci´on, no solo basadas exclusi a-
men e en la posici´on de los elemen os de la ma iz, sino ambi´en, que u iesen en
cuen a la in luencia de los alo es num´e icos de dichos elemen os.
Bibliog a ´ıa
[1] L. Adams. m-S ep p econdi ioned conjuga e g adien me hods. SIAM J.
Sci. S a . Compu . 6,2, 453–463 (1985).
[2] P. Almeida. “Resoluci´on di ec a de sis emas spa se po g a os.” Tesis
Doc o al, Uni e sidad de Las Palmas de G an Cana ia (1989).
[3] W.E. A noldi. The P inciple o Minimized I e a ion in he Solu ion o
he Ma ix Eingen alue P oblem. Qua . Appl. Ma h. 9, 17–29 (1951).
[4] S.F. Ashby, T.A. Man eu el y P.E. Saylo . A axonomy o con-
juga e g adien me hods. SIAM J. Nume . Anal. 27, 1542–1568 (1990).
[5] O. Axelsson. A Res a ed Ve sion o a Gene alized P econdi ioned Con-
juga e G adien Me hod. Comunica ions in Applied Nume ical Me hods 4,
521–530 (1988).
[6] O. Axelsson. “I e a i e Solu ion Me hods.” Camb idge Uni e si y P ess
(1996).
[7] A.F. de Baas. “Modelling o A mosphe ic Flow Fields.”, cap´ı ulo Scaling
Pa ame e s and hei Es ima ion, p´aginas 87–102. Wo ld Sci. Singapo e
(1996).
[8] J.C. Ba na d, H.L. Wegley y T.R. Hies e . Imp o ing he pe o -
mance o mass consis en nume ical models using op imiza ion. J. Clima e.
Appl. Me eo ol. 26, 675–686 (1987).
[9] R. Ba e , M. Be y, T.F. Chan, J. Demmel, J. Dona o, J. Don-
ga a, V. Eijkhou , R. Pozo, C. Romine y H.A. Van de Vo s .
Bibliog a ´ıa 128
“Templa es o he solu ion o linea sys ems: Building Blokcs o I e a i e
Me hods.” SIAM, Philadelphia (1994).
[10] M. Benzi. P econdi ioning Techniques o La ge Linea Sys ems: A Su ey.
Jou nal o Compu a ional Physics 182, 418–477 (2002).
[11] M. Benzi y D. Be accini. App oxima e in e se p econdi ioning o
shi ed linea sys ems. BIT Num. Ma h. 43, 231–244 (2003).
[12] M. Benzi, J.K. Cullum y M. Tuma. Robus app oxima e in e se p e-
condi ioning o he conjuga e g adien ma hod. SIAM J. Sci. Compu . 22,
1318–1332 (2000).
[13] R. Boubel, D. Fox, D. Tu ne y A. S e n. “Fundamen als o Ai
Pollu ion”. Academic P ess, San Diego (1994).
[14] J.A. Businge y S.P.S. A ya. Heigh s o he mixed laye in he s ably
s a i ied plane a y bounda y laye . Ad . Geophys 18A, 73–92 (1974).
[15] T.F. Chan, E. Gallopoulos, V. Simonsini, T. Sze o y C.H. Tong.
A Quasi-Minimal esidual a ian o he BI-CGSTAB algo i hm o nonsym-
me ic sys ems. SIAM J. Sci. Compu . 15,2, 338–347 (1994).
[16] C. Conde y G. Win e . “M´e odos y algo i mos b´asicos de ´algeb a nu-
m´e ica.” Edi o ial Re e ´e, Ba celona (1990).
[17] E. H. Cu hill y J.M. Mckee. Reducing he Bandwid h o Spa se Sym-
me ic Ma ices. En “P oc. 24 h Na ional Con e ence o he Associa ion
o Compu ing Machine y”, p´aginas 157–172. B ondon P ess, New Je sey,
U.S.A. (1969).
[18] C.G. Da is, SS. Bunke y J.P. Mu schlecne . A mosphe ic T ans-
po Models o Complex Te ain. J. Clima e. Appl. Me eo ol. 23(2), 235–
238 (1984).
[19] M. Dike son. A mass-consis en a mos e ic lux model o egions wi h
complex e ain. J. Appl. Me eo . 17, 241–253 (1978).
Bibliog a ´ıa 129
[20] Q.V. Dinh, V. Man el, J. Pe iaux y B. S ou sle . “Con ibu ion o
p oblems T4 and T6 ini elemen GMRES and conjuga e g adien sol e s.”
In o me T´ecnico. Dassaul A ia ion. (1993).
[21] S. Douglas y R. Kessle . “Use ’s guide o he Diagnos ic Wind Model
(Ve sion 1.0)”. Sys em Applica ions, Inc., San Ra ael. Cali o nia (2009).
[22] L.C. Du o. The E ec o O de ing on P econdi ioned GMRES Algo-
i hm. In . Jou . Num, Me h. Eng. 36, 457–497 (1993).
[23] L. Elsgol z. “Ecuaciones Di e enciales y C´alculo Va iacional”. Edi o ial
MIR. Mosc´u (1969).
[24] J.M. Escoba y R. Mon eneg o. Se e al aspec s o h ee-dimensional
Delaunay iangula ion. Ad ances in Enginee ing So wa e 1/2(27), 27–39
(1996).
[25] J.M. Escoba , E. Rod ´
ıguez, R. Mon eneg o, G. Mon e o y
J.M. Gonz´
alez-Yus e. Simul aneous un angling and smoo hing o e-
ahed al meshes. Compu . Me hods Appl. Mech. Eng g. 192, 2775–2787
(2003).
[26] L. Fe agu , R. Mon eneg o y A. Plaza. E icien e ine-
men /de e inemen algo i hm o nes ed meshes o sol e e olu ion p oblems.
Comm. Num. Me h. Eng. 10, 403–412 (1994).
[27] R. Fle che . Conjuga e G adien Me hods o Inde i e Sys ems. Lec u es
No es in Ma h. 506, 73–89 (1976).
[28] E. Fl´
o ez, M.D. Ga cia, A. Su´
a ez y H. Sa mien o. The E ec o
O de ing on he Con e gence o he Conjuga e G adien Me hod o Sol ing
P econdi ioned Shi ed Linea Sys ems. En B.H.V. Topping, G. Mon-
e o y R. Mon eneg o, edi o es,“P oceeding o The Fi h In e na ional
Con e ence on Enginee ing Compu a ional Techonology. Las Palmas de G.
C.”, p´aginas 191–192. Ci il-Comp P ess, S i lingshi e, U.K. (2006).
Bibliog a ´ıa 130
[29] E. Fl´
o ez, H. Sa mien o, M.D. Ga cia, A. Su´
a ez y G. Mon e-
o. Incomple e ac o isa ion o p econdi ioning shi ed linea sys ems a i-
sing om a pa ame e es ima ion p oblem in wind modelling. En B.H.V.
Topping, edi o , “P oceedings o he Six h In . Con e ence on Enginee ing
Compu a ional Techonology. A enas”. Ci il-Comp P ess, S i lingshi e, U.K.
(2008).
[30] E. Fl´
o ez V´
azquez. “Cons ucci´on de in e sas ap oximadas ipo ”spa -
se”basada en la p oyecci´on o ogonal de F obenius pa a el p econdiciona-
mien o de sis emas de ecuaciones no sim´e icos.” Tesis Doc o al, Uni e sidad
de Las Palmas de G. C. (2003).
[31] R.W. F eund. A anspose- ee quasi-minimal esidual algo i hm o non-
He mi ian linea sys ems. SIAM J. Sci. Compu . 14, 470–482 (1993).
[32] R.W. F eund y N.M. Nach igal. Qm : a quasi-minimal esidual me -
hod o non-He mi ian linea sys ems. Nume ische Ma h. 60, 315–339
(1991).
[33] R.W. F eund y N.M. Nach igal. An implemen a ion o he QMR
me hod based on coupled wo- e m ecu ences. SIAM J. Sci. Comp. 15,2,
313–337 (1994).
[34] M. Gal´
an. “A ances en el M´e odo de Residuo M´ınimo Gene alizado (algo-
i mo GMRES), su Desa ollo en ANSI-C con Algo i mos de Pa alelizaci´on
y Vec o izaci´on, y sus Aplicaciones al M´e odo de los Elemen os Fini os.”
Tesis Doc o al, Uni e sidad de Las Palmas de G an Cana ia (1994).
[35] M. Gal´
an, G. Mon e o y G. Win e . A di ec sol e o he leas
squa e p oblem a ising om GMRES(k). Com. Num. Me h. Eng. 10, 743–
749 (1994).
[36] M.D. Ga c´
ıa, E. Fl´
o ez, A. Su´
a ez, L. Gonz´
alez y G. Mon e o.
New implemen a ion o QMR- ype algo i hms. Compu e s and S uc u es
83, 2414–2422 (2005).
Bibliog a ´ıa 131
[37] M.D. Ga c´
ıa Le´
on. “Es a egias pa a la esoluci´on de g andes sis emas de
ecuaciones lineales. M´e odos de Cuasi-M´ınimo Residuo Modi icados.” Tesis
Doc o al, Uni e sidad de Las Palmas de G. C. (2003).
[38] P. Geai. “Me hode d’in e pola ion e de econs i u ion idimensionelle
d’un champ de en : le code d’analyse obje i e MINERVE”. In o meT´ecnico.
Elec ici `e de F ance (1985).
[39] P. Geai. “Recons i u ion idimensionnelle d’un champ de en dans un
domaine a’ opog aphie complexe a pa i de meseu es in si u.” In o meT´ec-
nico. DER/HE/34-87.05, EDF, Cha ou. F ance (1987).
[40] I.M. Gel and y S.V. Fomin. “Calculus o Va ia ions”. P en ice-Hall,
INC (1963).
[41] A. Geo ge. Compu e Implemen a ion o he Fini e Elemen Me hod.
Repo S an CS p´aginas 71–208 (1971).
[42] A. Geo ge y J.W. Liu. The E olu ion o he Minimum Deg ee O de ing
Algo i hms. SIAM Re . 31, 1–19 (1989).
[43] G.H. Golub y G.A. Meu an . “R´esolu ion num´e ique des g ands sys-
`emes lin´eai es.” Edi ions Ey olles, Pa ´ıs. (1983).
[44] J.M. Gonz´
alez-Yus e. “Un Algo i mo de Re inamien o/De e inamien o
Local pa Mallas de Te aed os.” Tesis Doc o al, Uni e sidad de Las Palmas
de G an Cana ia (2004).
[45] J.M. Gonz´
alez-Yus e, R. Mon eneg o, J. Escoba , G. Mon e o
y E. Rod ´
ıguez. Local e inemen o 3-D iangula ions using objec -
o ien ed me hods. Ad . in Eng. So w. (2003).
[46] A. G eenbaum. “I e a i e Me hods o Sol ing Linea Sys ems”. SIAM,
Philadelphia (1997).
[47] M. G o e y H. Simon. “Pa allel P econdi ioning and App oxima e In-
e ses on he Connec ion Machine.” In o me T´ecnico. NASA Con ac No.
NAS2-12961 (1986).