*
Depa amen o de In o má ica
Uni e sidad de Jaime I de Cas ellón
12071 Cas ellón, España
Tel.:
+
34-964-345771; Fax:
+
34-964-345848
E-mail: [email p o ec ed].
**
Depa amen o de Sis emas In o má icos
y
Compu ación
Uni e sidad Poli écnica de Valencia
46071 Valencia, España
Tel.:
+
34-963-877000; Fax:
+
34-963-877358
E-mail: [email p o ec ed].
RESUMEN
El p oblema lineal-cuad á ico de con ol óp imo apa ece en el análisis y diseño de sis emas
dinámicos lineales. La solución de es e p oblema en el modelo de espacio de es ados puede
ob ene se esol iendo una ecuación ma icial cuad á ica: la ecuación algeb aica de Ricca i. En
es e abajo se p esen an di e sos algo i mos pa a esol e ecuaciones ma iciales de Ricca i
median e los cua o mé odos más iables: el mé odo de Kew on, el mé odo de Schu , la unción
signo ma icial y la unción disco ma icial. Los esul ados expe imen ales compa an es os
mé odos desde el pun o de is a de la p ecisión numé ica y de la e iciencia.
Pdabm
cla e:
Ecuación algeb aica de Ricca i, con ol óp imo, con ol ealimen ado, álgeb a ma icial,
algo i mos po bloques.
NUMERICAL METHODS FOR THE SOLUTION OF THE LINEAR-QUADRATIC
OPTIMAL CONTROL PROBLEM
SUMMARY
The linea -qaud a ic op imal con ol p oblem a ises in he analysis and design o dynamic
linea sys ems. The solu ion o his p oblems can be compu ed in he s a e-space model by
sol ing a quad a ic ma ix equa ion: he algeb aic Ricca i ma ix equa ion. In his pape we
Recibido: No iemb e 1995
QCni e si a Poli kcnica de Ca alunya (España)
ISSN
0213-1315
383
Re is a In e nacional de Mé odos Numé icos pa a Cálculo y Diseño en Ingenie ía. Vol.
14,3,
383-402(1998)
p esen nume ical algo i hms o sol ing Ricca i ma ix equa ions by means o ou o he mos
eliable nume ic me hods: New on's me hod, he Schu me hod, he ma ix sign unc ion and
he ma ix disk unc ion. The expe imen al esul s compa e hese me hods bo h om he poin
o iew
o
e iciency and accu acy.
Key
wolds:
Algeb aic Ricca i equa ions, op imal con ol, eedback con ol, ma ix algeb a, block-
pa i ioned algo i hms.
En los úl imos años el análisis y diseño de sis emas dinámicos lineales (SDL) y,
en gene al, los p oblemas de con ol se han con e ido en un á ea de c ecien e in e és
in es igado . Así, la ecuación algeb aica de Ricca i (EAR) es en la ac ualidad un
mé odo es ánda numé icamen e iable pa a esol e el p oblema lineal-cuad á ico de
con ol óp imo1. Además, el desa ollo de las úl imas gene aciones de compu ado as de
al as p cs aciones ha pe mi ido la esolución de p oblemas de con ol de g an dimensión.
En es e sen ido, en es e abajo se p esen a un es udio expe imen al de di e sos ié odos
iu ié icos pa a la esolucón de EAR con ma ices coe icien e densas.
Conside emos el SDL con inuo e in a ian e en el iempo de inido po
donde
A
E
JRnXn
es la ma iz de es ados,
B
E
IRnXm
la ma iz de en adas (o con oles)
y
C
E
IRpXn
la ma iz de salidas, x( ), u( ) y y( ) los ec o es de es ados, en adas
y
salidas espec i amen e, de dimensiones ap opiadas.
La dimensión
n
del ec o de es ados x( ) en gene al sa is ace
n
>>
m,
~
>>
p
y
es habi ualmen e meno que unos pocos miles, en el caso de p oblemas de con ol
densos".
Las ecuaciones en
(1)
se conocen como el modelo de espacio de es ados del sis ema.
El es ado del sis ema xo en el ins an e inicial o (sin pé dida de gene alidad o
=
O)
y
la
secuencia de en adas u( ),
=
o,
. .
.
,
de inen la secuencia de salidas y( ), o,
. . .
,
.
En un en o no eal se u iliza el ec o de en adas pa a sa is ace cie os
eqiii i nie i os en el compo amien o dinámico del sis ema. Además, simul áneamen e
es deseable minimiza la can idad de es ue zo eque ido. Es e doble obje i o se puede
o mula como un p oblema de minimización sob e u( ) del uncional cuad á ieo
donde Q
E
IRnXn
es una ma iz de pesos de es ados, simé ica semide inida posi i a
(Q"'
1
O),
Q
=
GTG
una ac o ización de ango comple o de
Q
y
R
E
IR nX n
una
ma iz de pesos de con oles, simé ica de inida posi i a
(R
=
R~
>
0) e e .
1.
En
algunos casos, po ejemplo en el p oblema de egulación de las salidas,
Q
y
C
es án
elacionadas po Q
=
CTC.
MÉTODOS NUMÉRICOS PARA LA
RESOLUCION
385
En el p oblema lineal-cuad á ico de con ol óp imo se desea calcula un con ol
ealimen ado po el es ado u( )
=
Fx( ),
F
E
IRmXn, al que minimiza el uncional
cuad á ico
J
en
(2)
y
la ma iz de es ados del sis ema en lazo ce ado
es es able, es o es, los alo es p opios de (A
+
BF)
ienen pa e eal nega i a. Bajo
cie as condiciones, especi icadas en el siguien e eo ema, es e p oblema iene una única
soluciÓnl7.
Dejinición
1
El SDL i( )
=
Ax( )
+
Bu( ) (o el pa (A,
B))
es es abilizable, si exis e un
con ol ealimen ado po el es ado al que el co espondien e sis ema en lazo ce ado
es es able17.
De inición
2
El SDL i( )
=
Ax( ), y( )
=
Cx( ) (o el pa (A, C)) es de ec able, si el sis ema
dual asociado x( )
=
ATz( )
+
CTu( ) es es abilizablei7.
Teo ema
3
Si el pa (A, B) es es abilizable
y
el pa (A, C) es de ec able, en onces exis e un
único con ol óp imo
que minimiza
J,
donde X
E
IRnXn es la única solución simé ica, semide inida posi i a
de la ecuación algeb aica de Ricca i en iempo con inuo
Además, bajo es as condiciones el sis ema en lazo ce ado
es es able.
El eo ema an e io in oduce un mé odo pa a esol e el p oblema lineal-
cuad á ico de con ol óp imo basado en la ecuación algeb aica de Ricca i (5), pues o
que una ez se conoce X, el con ol ealimen ado u( ) se ob iene ácilmen e de
(4).
La
EAR es una de las ap oximaciones numé icas más iables pa a esol e es e p oblema
de con ol
y
puede aplica se asimismo en SDL en iempo con inuo gene alizados
donde
E
E
IRnXn
puede se singula 17
y
SDL en iempo disc e o gene alizados
El p oblema lineal-cuad á ico de con ol óp imo apa ece en p oblemas de con ol
óp imo
H2,
con ol obus o
y
op imización
H,,
es abilización de SDL, il ado óp imo
y
cálculo de descomposiciones de Kalman, e c.17 EAR de g an dimensión apa ecen po
ejemplo en el con ol de g andes es uc u as dinámicaslg. En gene al, en p oblemas
de mayo dimensión ( a ios miles de a iables de es ados), las ma ices coe icien e que
in e ienen son dispe sas. Es e ipo de p oblemas p esen an el incon enien e de que,
aunque las ma ices coe icien e son dispe sas, la solución
X
es densa. Así pues, ninguno
de los mé odos es udiados en las en las siguien es secciones esul a ap opiado pa a es e
ipo de p oblemas. En ealidad, únicamen e se conocen ap oximaciones heu ís icas pa a
la esolución de p oblemas dispe sosz3.
En es e abajo se p esen an algo i mos de al as p es aciones pa a esol e EAR de
amaño mode ado, donde in e ienen ma ices coe icien e densas, median e cua o de
los mé odos con mayo iablidad numé ica: el mé odo de New on, el mé odo de Schu ,
la unción signo ma icial
y
la unción disco ma icial. Los algo i mos desa ollados
u ilizan in ensi amen e las lib e ías compu acionales BLAS
y
LAPACKZ. La lib e ía
BLAS dispone de una se ie de núcleos compu acionales básicos, que habi ualmen e son
desa ollados y a inados po el p opio ab ican e del compu ado . La lib e ía LAPACK
con iene di e sas u inas del álgeb a ma icial
y
ealiza un empleo e icien e de los
ecu sos co npu acionales median e la u ilización de écnicas o ien adas po bloques
y
u inas del BLAS.
En las implemen aciones se ha u ilizado un nodo compu acional de un
mul ip ocesado con memo ia compa ida, el Silicon G aphics Powe Challenge. Es c
nodo compu acional es el SGI MIPS RS8000.
El abajo es á es uc u ado del siguien e modo. En la sección siguien e se desc iben
los p incipales mé odos numé icos pa a la esolución de EAR en el modelo de espacio
de es ados. Pos e io men e se p esen an los esul ados expe imen ales ob enidos en
es a a qui ec u a. Finalmen e, en la úl ima sección se comen an las conclusiones del
abajo.
Mé odos numé icos
pa a
la
EAR
Exis en cua o ipos de mé odos pa a esol e la EAR en el modelo de espacio
de es ados: el mé odo de New on, los mé odos basados en los ec o es de Schu , los
mé odos basados en la unción signo ma icial
y
los mé odos basados en la unción disco
ma icial15.
El mé odo de New on es un algo i mo numé icamen e es able, pe o el cos e de es e
mé odo i e a i o es bas an e al o
y
su con e gencia puede se len aL3. Es e mé odo
abaja di ec amen e con las ma ices coe icien e del p oblema
y
en cada i e ación se
calcula una nue a ap oximación a la solución de la EAR.
MÉTODOS NUMÉRICOS PARA LA RESOLUCIÓN
387
Po o a pa e, los es an es es ipos de mé odos abajan sob e la ma iz 2n
x
2n
x=
[-&
A
-BR-lBTl
-aT
(9)
asociada a la EAR. Es a ma iz es hamil oniana, pues o que
JH
=
(JH)~,
-In
On
j=[On
"1
(10)
donde
In
es la ma iz iden idad de o den n. Es os mé odos calculan una base del
subespacio in a ian e es able de
1-1
y, a pa i de és a, ob ienen la solución de la EAR.
El
mé odo
de
New on
El mé odo de New on (o i e ación de Kleinmann) ue in oducido en13 como un
mé odo i e a i o pa a esol e la EAR. Es e mé odo equie e una ap oximación inicial
a la solución del p oblema y su con e gencia puede esul a len a si es a ap oximación
es á lejana a la solución exac a del p oblema. Sin emba go, és e es un mé odo cuya
es abilidad numé ica ha sido p obada. En consecuencia, y debido a su al o cos e
compu acional, es e mé odo es á conside ado como un algo i mo e icien e pa a e ina
las soluciones ob enidas median e algún o o mé odo.
El mé odo de New on se calcula una secuencia de ma ices que, bajo cie as
condiciones, con e ge a la única solución semide inida posi i a de la EAR. Es e
algo i mo se ob iene del siguien e eo ema13:
Twm na
4
Sea Xk, k
=
0,1,2,.
. .
,
la única solución semide inida posi i a de la ecuación
ma icial lineal de Lyapuno en iempo con inuo
ATX~
+x~A~
+Q+
FFRF~
=O
(11)
donde
1
T
Fk
=
-R-
B
Xk-1, k
=
1,2,.
. .
Al, =A+BFk, k=0,1,
...
(12)
y
con
Fo
calculada al que A
+
BFo
es es able. En onces
1. O<X<XkS1-<Xk-<
...<
XO, k=0,1,
...
2. limk,, Xk
=
X
3.
La con e gencia de la secuencia de ma ices es asin ó icamen e cuad á ica, es o es,
3c' al que I(Xk+l
-
X(I
5
clJIXk
-
X1I2,
Vk
=
O,
1,.
. .
Pues o que el pa de ma ices (AB) es es abilizable ( e las condiciones pa a la
exis encia
y
unicidad de la solución eque ida de la EAR), es posible encon a una

ma iz de ealimen ación
Fo
al que
A
+
BFo
es es able. Po ejemplo, el algo i mo de
Bass pe mi e encon a es e con ol de ealimen ación de es ados3. Así, si la i e ación
se inicia en es a ap oximación, la secuencia siemp e con e ge a la solución eque ida
de la EAR. Además, si la ecuación ma icial lineal de Lyapuno ll se esuel e median e
algún mé odo numé icamen e e~ able~?~', en onces se puede p oba que el mé odo de
Sew o i es asimismo numé icamen e es ablez0.
La siguien e implemen ación del mé odo de New on o ece una al a iabilidad en
p esencia de e o es de edondeo6.
Algo i mo
1
1. Calcula una ma iz de ealimen ación inicial
Fo
al que
A
+
BFo
es es able
2. Calcula la solución simé ica inicial
Xo
esol iendo la ecuación ma icial lineal de
L yapuno
3.
Pa a
k
=
0,1, 2,.
.
.
has a con e gencia o
k
>
max i e
b)
Calcula la solución
xl,
de la ecuación ma icial lineal de Lyapuno
Fin pa a
La con e gencia de es a i e ación puede mejo a se median e el uso de las écnicas
de búsqueda lineal6. Básicamen e, la siguien e solución
Xk+l
se calcula como
donde
O
<
k
5
2 se escoge en cada i e ación de modo que se minimiza
( )
=
(1
-
)2
.
aza(~2)
+
2(1
-
) 2 aza(RkTk)
+
4
.
aza(~i)
TI,
=
XksXk
(16)
Es a búsqueda lineal exac a puede educi conside ablemen e el núme o de
i e aciones del mé odo de New on. El siguien e eo ema mues a las p opiedades del
mé odo de New on modi icado median e la búsqueda lineal6:
MÉTODOS NUMÉRICOS PARA LA RESOLUCIÓ?;
389
Teo ema
5
Conside emos el pa (AB) con olable Xo
=
X:
al que A
-
SXo es es able
y
O
<
k
5
2,
k
2
O,
en onces las soluciones ap oximadas Xk,
k
>
O
p oducidas median e
el mé odo de New on con búsqueda lineal sa is acen
1.
A
-
SXk es es able
4.
li nk,, Xk
=
X
y
la con e gencia es asin ó icamen e cuad á ica
Los esul ados numé icos en la sección siguien e mues an la e iciencia del empleo
de búsquedas lineales (Figu a 1). Además, el cos e compu acional po i e ación de es e
mé odo puede educi se explo ando la es uc u a simé ica de algunas de las ma ices
que in e ienen
(S,
Rk
y
Xk).
El
mé odo de
Schu
El desa ollo del mé odo de Schu pa a la esolución de la EAR ue una ex ensión
na u al de los mé odos basados en el uso de ec o es p opios14. El mé odo de Schu e i a
las di icul ades numé icas asociadas al cálculo de los ec o es p opios abajando sob e
los ec o es de Schu , que pueden se calculados median e un mé odo numé icamen e
es able, el algo i mo i e a i o
QRIO.
Los mé odos basados en los ec o es de Schu calculan una base del subespacio
in a ian e es able de
3
y
en onces la solución de la EAR se ob iene a pa i de
un
sis ema algeb aico lineal.
El mé odo de Schu pa a esol e la EAR14 es el siguien e:
Algo i mo
2
1.
Calcula una ans o mación de semejanza, de inida po una ma iz o ogo ial
Ul
al que educe la ma iz hamil oniana asociada con la EAR a la o ma eal de Schu
( o ma iangula supe io po bloques, con bloques diagonales de dimensión
1
x
1
ó2x2)
2. Calcula una ans o mación de semejanza de inida po una ma iz o ogonal
U2,
que desplaza los alo es p opios de
T
con pa e eal nega i a al bloque supe io
izquie do de
T
3.
Si V
=
U1U2, en onces la solución de la
EAR
se calcula esol iendo el sis ema
lineal XVli
=
Vzl, donde V es á pa icionada en bloques de dimensión
n
x
n
del
siguien e modo
Exis en di e sas modi icaciones de las dos p ime as e apas del mé odo de Schu
que in en an explo a la es uc u a hamil oniana del p oblema, como el algo i mo
QR hamil onianos. Sin emba go, es e algo i mo p esen a el incon enien e de que no
se conoce ningún mé odo pa a educi una ma iz hamil oniana gene al a la o ma
Hessenbe g-hamil oniana median e ans o maciones simplé icas o ogonales. Es a
ed~icción únicamen e puede ealiza se si la ma iz
S
o la ma iz
Q
(o ambas) son
de ango uno.
Un mé odo simila , el algo i mo
SR,
que es á ambién basado en el uso de
ans o maciones simplé icas,
y
en consecuencia p ese a la es uc u a del p oblema,
se desc ibe en la e .7. Sin emba go, algunas de las ans o maciones in oducidas en
es e mé odo no son o ogonales,
y
po an o es posible in oduci g andes e o es de
edondeo en la solución.
La unción signo ma icial
Conside emos la descomposición canónica de Jo dan1° de la ma ix N de inida como
donde
x
es una ma iz de ec o es p opios
y
ec o es p incipales de N,
D
=
diag(di, d2,.
.
.
,
dm) una ma iz diagonal que con iene los alo es p opios de N
y
N
una ma iz nilpo en e
(3:
Nk
=
Ozn). La unción signo ma icial de N se de ine como
donde la unción signo escala es á de inida po
si Re(a)
>
O
signo(a)
=
si Re(a)
<
O
inde inida si Re(a)
=
O
y
Re(a) es la pa e eal de a.
A
pa i de signo (N) se puede p oba z4 que la solución de la EAR asociadada se
ob iene esol iendo el sis ema lineal de ango comple o sob ede e minado
I emcaones
pa a
la incaón signo ma icaal
Enz4 se demues a que, aplicando el mé odo de New on-Raphson a la ecuación
ma icial no lineal N2
=
12n,
se ob iene la siguien e i e ación pa a la unción signo
ma icial
1
W~+~=~(W~+W<~), wo=X (24)
y la secuencia Wk
,
k
=
0,1,2,
.
. .
,
con e ge cuad á icamen e a signo N.
Una écnica de acele acióng esul a en el siguien e esquema i e a i o clásico
Es a écnica es ácilmen e u ilizable, mejo a la con e gencia y equie e un cos e
compu acional adicional de o den meno .
Exis en o os esquemas i e a i os di e en es que pueden esul a más e icien es
sob e compu ado as de al as p es aciones debido al ipo de ope aciones que los
componen. Un nue o esquema i e a i o acional18 esul a en una i e ación " ica!' en
p oduc os ma iciales. El esquema i e a i o acional ob enido es el siguien e:
donde
El mayo cos e po i e ación de es e esquema puede compensa se en algunos
p oblemas po su mayo con e gencia, que depende del pa áme o
m.
Una ap oximación di e en e esul a en o a i e ación " ica" en p oduc os
ma iciales. Si
Iw?
-
12,1
<
1,
en onces el esquema i e a i o de New on-Schul~'~,
comenzando en W
,
con e ge a signo (W )
Pues o que Wo
=
3C
es hamil oniana, puede ácilmen e p oba se que las ma ices
de la secuencia Wk,
k
=
1,2,.
. .
calculadas median e (25) y (26) son ambién
hamil onianas. En consecuencia, Zk
=
Jw~,
k
=
0,1,2,
. . .
(J
de inida en (10)) de ine
una secuencia de ma ices simé icas inde inidas y el esquema i e a i o simé ico
con e ge a
J
signo (N). Así, es e esquema i e a i o únicamen e equie e la in e sión
de ma ices simé icas y p esen a po an o un meno cos e compu acional. La misma
idea puede aplica se al esquema i e a i o acional (26).
Bi
-
60
-
-
20-
n
n
Figu a
2.
Tiempo de CPU
(S)
de la unción signo ma icial pa a la esolución de la
EAR asociada a los p oblemas CVAV (izquie da)
y
MC (de echa) en el
Silicon G aphics Powe Challenge
educe a la mi ad el cos e del esquema i e a i o clásico. Es o es debido a la u ilización
en el esquema i e a i o simé ico de núcleos compu acionales menos e icien es.
Es a misma si uación se epi e en e el esquema i e a i o acional dgec s
y
el esquema i e a i o simé ico acional dhac s , aunque ambos algo i mos ob ienen
iempos de ejecución supe io es a los an e io es. Po úl imo, como mues a el p oblema
MC, el esquema i e a i o mix o puede esul a más e icien e en algunos casos.
La unción disco ma icial
En el es udio expe imen al se han desa ollado di e sas implemen aciones del
mé odo basado en la unción disco ma icial, que co esponde al algo i mo 3. Es as
a ian es di ie en en el ipo de descomposición o ogonall0 que se u iliza pa a esol e
el sis ema lineal sob ede e minado en la e apa
3.
Expe imen almen e se ha p oba,do
que las di e encias exis en es son de o den meno
y
en consecuencia se ha escogido una
a ian e del algo i mo 3, que emplea la ac o ización
QR
con pi o amien o de columnas
en la e ce a e apa.
-
dgec gs:
Compa ación global
En p ime luga , en es e es udio compa a i o se analizan las a ian es más e icien es
de cada uno de los cua o mé odos:
-
dgec nz: Mé odo de New on con búsqueda lineal exac a
-
dgec sc: Mé odo de Schu
-
dhac sd: Función signo ma icial median e el esquema i e a i o simé ico

MÉTODOS NGMÉRICOS PARA LA RESOLUCIÓN
399
-
dgec gs: Función disco ma icial
La Figu a
3
mues a el compo amien o del iempo de ejecución de los di e en es
algo i mos desa ollados cuando a ía el amaño del p oblema.
8W~~~~~7..
450-
-+-
dgec n
7W
-
-+-
dgec nz
1
400-
-
x
-
dgec sc
6W
-
-
x
-
dgec sc
350
-
+
dhac sd
500
-
+
dhac sd
3W-
--'--
dgec gs
4W
-
--'--
dgec gs
C
3W-
200
-
50
1W
150 200 250 300 350 400 450
SW
5% M
100
150 2W 250 300 350 400 450 500 550
n
n
Figu a 3. Tiempo de CPU
(S)
pa a la esolución de la EAR asociada
a
los p oblemas
CVAV (izquie da)
y
MC (de echa) en el Silicon G aphics Powe Challenge
En ambas igu as el iempo de CPU pa a esol e los p oblemas de mayo amaño
median e la unción disco ma icial se ob u o ex apolando los esul ados disponibles.
La igu a an e io mues a que el algo i mo más e icien e es el basado en el cálculo
de la unción signo ma icial dhac sd seguido del mé odo de Schu dgec sc. Es os
dos algo i mos p esen an además un cos e conside ablemen e meno que los algo i mos
basados en el mé odo de New on
y
la unción disco ma icial.
La unción signo ma icial equie e ope aciones ma iciales que esul an al amen e
e icien es sob e las a qui ec u as ac uales. Además, p esen a un bajo cos e po i e ación
y
una ápida con e gencia.
El mé odo de Schu p esen a un cos e compu acional eó ico compa able a la
unción signo ma icial. En cambio, el ipo de ope aciones ma iciales que equie e
(algo i mo i e a i o
QR)
no esul an an e icien es sob e los compu ado es ac uales.
El mé odo de New on p esen a un al o cos e po i e ación y aunque las écnicas de
búsqueda lineal educen el cos e global del algo i mo, és e oda ía esul a no ablemen e
más al o que en la unción signo ma icial o el mé odo de Schu .
Po úl imo, la unción disco ma icial p esen a asimismo un al o cos e po i e ación
y
equie e además un ele ado núme o de i e aciones, pues o que no se conoce ningún
mé odo de acele ación de la con e gencia pa a es e mé odo.
A
con inuación se desc iben los esul ados ob enidos u ilizando el mé odo de
New on como un algo i mo de e inamien o i e a i o pa a a ina las soluciones
calcualdas median e los es an es mé odos.
La Tabla
11
mues a el esiduo ela i o ( e (39)) de los mé odos globales
cons uidos median e el mé odo de Schu , la unción signo ma icial o la unción disco
ma icial
y
e inados median e el mé odo de New on. Además, se p esen a el núme o de
i e aciones de e inamien o necesa ias pa a ob ene una p ecisión simila a la ob enida
di ec amen e median e el mé odo de New on.
Tabla
11.
E o ela i o
y
núme o de i e aciones del mé odo de Kew on
(en e pa én esis)
La abla an e io mues a que el mé odo de Schu , la unción signo ma icial
y
la unción disco ma icial, e inados median e el mé odo de New on, pe mi en ob ene
soluciones pa a las EAR es udiadas de p ecisión compa able a la ob enida median c el
mé odo de New on. Además, en es os p oblemas únicamen e es necesa io una i e ación
de e inado pa a ob ene al p ecisión.
CONCLUSIONES
En es e abjao se han p esen ado di e sos algo i mos pa a la esolución
del p oblema lineal-cuad á ico de con ol óp imo pa a sis emas dinámicos lineales
o mulados en el modelo de espacio de es ados.
Los mé odos analizados (mé odo de New on, mé odo de Schu
y
unciones
signo
y
disco ma icial) es án basados en la esolución de la ecuación algeb aica de
Ricca i. Es os mé odos es án conside ados como numé icamen e iables, pues e i an
las di icul ades numé icas de los algo i mos basados en el modelo polinomial.
El análisis de los mé odos incluye un amplio es udio expe imen al de las di e en es
a ian es de cada uno de los algo i mos desa ollados. Es e análisis ealiza una
compa ación de los algo i mos, an o desde el pun o de is a de las p es aciones como
de la p ecisión de los esul ados.
METODOS
NUMÉRICOS
PARA
LA
RESOLUCIÓN
401
El mé odo más e icien e es la unción signo ma icial, pues une a la e iciencia de
las ope aciones ma iciales que emplea, un escaso cos e po i e ación y una ápida
con e gencia. Además, en e los di e en es esquemas i e a i os, la u ilización del
esquema i e a i o simé ico consigue educi el cos e de es e mé odo.
El mé odo de Schu p esen a un cos e compu acional lige amen e supe io , pe o
iene la en aja, en e a la unción signo ma icial, de e i a di icul ades numé icas si
la ma iz hamil oniana es casi singula .
F en e a los an e io es algo i mos, el mé odo de New on p esen a como en aja
p incipal su es abilidad numé ica, aunque su cos e po i e ación esul a muy al o. El
ejemplo de écnicas basadas en búsquedas lineales consigue acele a la con e gencia de
es e mé odo. En cambio, en es e caso no se ob iene bene icio alguno al explo a la
es uc u a hamil oniana del p oblema.
Po úl imo, la unción disco ma icial equie e un al o cos e po i e ación que
de e mina sus peo es p es aciones. Sin emba go, es e mé odo puede ene in e és en
a qui ec u as pa alelas po el ipo de ope aciones que equie e.
REFERENCIAS
1. B.D.O. Ande son y J.B. Moo e, "Lznea Op zmal Con ol", P en ice-Hall, Englewood Cli s,
USA, (1971).
2. E. Ande son e al., LAPACK, Use 's Guide, SIAM, (1992).
3. E.S. A ms ong, "An Ex ension o Bass's Algo i hm o S abilizing Linea Con inuous
Sys ems", IEEE l' ans. on Au oma zc Con ol, Vol. 20, pp. 153-154, (1975).
4. Z. Bai, J. Demmel y M. Gu, "In e se F ee Pa allel Spec al Di ide and Conque Algo i hms
o Nonsymme ic Eigenp oblems", Compu e Science Di ision Repo , UCB//CSD-94-
793, Gni e si y o Cali o nia a Be keley, (1994).
5. R. Ba els y G.W. S ewa , "Algo i hm 432. The Solu ion o he Ma ix Equa ion
AX
-
XB
=
C",
Comm. o he ACM, Vol. 15, pp. 820-826, (1972).
6. P. Benne , "Con ibu ions o he Nume ical Solu ion o Algeb aic Ricca i Equa ions", Tesis
Doc o al, Facul y o Ma hema ics, TU Chemni z-Zwickau, (1997).
7. A. Bunse-Ge s ne
y
V. Meh mann, A Symplec ic QR-like Algo i hm o he Solu ion o
he Real Algeb aic Ricca i Equa ion", IEEE T ans. on Au oma zc Conk ol, Vol.
31,
pp.
1104-1113, (1986).
8. R. Bye s, "A Hamil onian QR Algo i hm", SIAM
J.
Sczen z ic
&
S a zs zcal Compu zng,
Vol.
7,
pp. 212-229, (1985).
9.
R.
Bye s, "Sol ing he Algeb aic Ricca i Equa ion wi h he Ma ix Sign Func ion", Lzn.
Algeb a
&
I s Appl, Vol. 85, pp. 267-279, (1987).
10. G.H. Golub y C.F. Van Loan, "Ma zx Compu a zons", The John Hopkins Uni e si y P ess,
Bal imo e, USA, (1989).
11. S.J. Hamma ling, "Nume ical Solu ion o he S able, Non-Nega i e De ini e Lyapuno
Equa ion, IMA
J.
Nume zcal Analyszs, Vol. 2, pp. 303-323, (1982).
12. C. Kenney y A.J. Laub, "Ra ional I e a i e Sle hods o he Ma ix Sign Func ion", SIAM
J.
Ma zx Analyszs
&
Appl., Vol. 12, pp. 273-291, (1991).
13. D.L. Kleinmann, "On an I e a i e Technique o Ricca i Equa ion Compu a ions", IEEE
T ans. Au oma zc Con ol, Vol.
13,
pp. 114-115, (1968).
14. A.J. Laub, "A Schu Me hod o Sol ing Algeb aic Ricca i Equa ions, IEEE T ans.
Au oma zc Con ol, Vol. 24, pp. 913-921, (1979).
15. A.J. Laub, In a ian Subspace Me hods o he Nume ical Solu ion o Ricca i Equa ions",
En The Ricca i Equa ion", S. Bi an i, A.J. Laub y J.C. Willems (Eds.), Chap e 7,
Sp inge -Ve lag, Be lin, (1991).
16. A.N. Malyshe , "Pa allel Algo i hm o Sol ing Some Spec al P oblems o Lineal
Algeb a", Linea Algeb a
&
I s Appl, Vol. 188-189, pp. 489-520, (1993).
17. V. Meh mann,
"
The Au onomous Linea Quad a ic Con ol P oblem"
,
Sp inge -Ve lag,
Be li i, (1991).
18. P. Pandey, C. Kenney y A.J. Laub, "A Pa allel Algo i hm o he Ma ix Sign F'unc ion",
In .
J.
High Speed Compu ing, Vol. 2, pp. 181-191, (1990).
19.
P.M.
Papadopoulos e al., "Op imal Con ol S udy o he Space S a ion Sola Dynamic
Powe Mo iule", P oceedings o he 30 h Con e en,ce on Decision and Con ol, B igh on,
UK,
(1991).
20. P.H. Pe kon, N.D. Ch is o y M.M. Kons an ino , "Compu a ional Me hods o Linea
Con ol Sys ems", P en ice-Hall In e na ional L d., UK, (1991).
21. E.S. Quin ana y V. He nández, "Pa allel Algo i hms o Sol ing he Algeb aic Ricca i
Equa ion ia he Ma ix Sign F'unc ion", P oceedings o he 3 d IFAC Wo lcshop on
Algo i hms and A chi ec u es o Real-Time Con ol AARTC'95, pp. 533-542, Os ende,
(1995).
22. E.S. Quin ana,
"
Algo i mos pa alelos pa a esol e ecuaciones ma iciales de Ricca i en
p oblemas de con ol", Tesis Doc o al, Dep . de Sis emas In o má icos
y
Compu ación,
Uni e sidad Poli écnica de Valencia, (1996).
23. S. Rich e y A. Sco edwa d Hodel, "Homo opy Me hods o he Solu ion o Gene al
Modi ied Algeb aic Ricca i Equa ions", Con e ence on Decision, and Con ol, Honolulu,
(1990).
24. J. Robe s, "Linea Model Reduc ion and Solu ion o he Algeb aic Ricca i Equa ion by
he Use o he Sign Func ion", In .
J.
o Con ol, Vol. 32, pp. 677-687, (1980).
25.
X.
Sun y E.S. Quin ana, "Spec al Di ision Me hods o Block Gene alized Schu
Decomposi ions", Compu e Science Dep ., Duke Lni e si y, Technical Repo CS-1996-13,
(1996).