tesis funciones matrices.pdf

Departamento de Sistemas Informticos y Computacin

Universidad Politcnica de Valencia

Tesis Doctoral

Computacin de Altas Prestaciones para el Clculo de Funciones de Matrices y su Aplicacin a la

Resolucin de Ecuaciones Diferenciales

presentado por:

J. Javier Ibez Gonzlez

Director:

Dr. D. Vicente Hernndez Garca

Valencia, 2006

Resumen

La presente memoria se enmarca dentro de la lnea de investigacin de Computacin de Altas Prestaciones para el Clculo de Funciones de Matrices y su Aplicacin a la Resolucin de Ecuaciones Diferenciales. Este campo de investigacin est teniendo un gran auge en los ltimos aos, ya que proporciona soluciones a cuestiones muy diversas como son la simulacin de fenmenos fsicos o la resolucin de problemas de control.

La tesis se centra, fundamentalmente, en el desarrollo de mtodos y la implementacin de algoritmos que calculan Funciones de Matrices, y su aplicacin a la resolucin de Ecuaciones Diferenciales Ordinarias (EDOs) y Ecuaciones Diferenciales Matriciales de Riccati (EDMRs).

El punto de partida del trabajo desarrollado ha sido el estudio del estado del arte de cada una de esas reas, proponindose nuevos mtodos y algoritmos que, de algn modo, mejoran los ya existentes.

Tambin se han explorado diversos campos de aplicacin de este tipo de aproximaciones. Uno de ellos, la propagacin de rayos luminosos en fibras de cristal fotnico y la posibilidad de controlar su comportamiento usando medios peridicos, est siendo una de las perspectivas ms prometedoras en la bsqueda de alternativas a la tecnologa de los semiconductores. En este sentido, la Computacin de Altas Prestaciones permite, mediante la simulacin, conocer el comportamiento de la luz en esos medios, dando soporte experimental a las cuestiones tericas que en la actualidad se estn investigando.

Para obtener un software de calidad, se ha utilizado un paradigma de ciclo de vida de tipo semiautomtico. Adems, se han realizado numerosas pruebas que han permitido determinar, por un parte, los parmetros ptimos de los algoritmos implementados y, por otra, analizar la precisin y eficiencia del cdigo implementado.

Resum

La present memria semmarca dins la lnia dinvestigaci de Computaci dAltes Prestacions per al Clcul de Funcions de Matrius i la seua Aplicaci a la Resoluci dEquacions Diferencials. Este camp dinvestigaci est tenint una gran expansi en els ltims anys, ja que proporciona solucions a qestions molt diverses com sn la simulaci de fenmens fsics o la resoluci de problemes de control.

La tesi se centra, fonamentalment, en el desenvolupament de mtodes i la implementaci de algoritmes que calculen Funcions de Matrius, i la seua aplicaci a la resoluci dEquacions Diferencials Ordinries (EDOs) i Equacions Diferencials Matricials de Riccati (EDMRs).

El punt de partida del treball realitzat ha sigut lestudi de lestat de lart de cada una deixes rees, proposant-se nous mtodes i algoritmes que, dalguna manera, milloren els ja existents.

Tamb shan explorat diversos camps daplicaci desta tipus daproximacions. Un dells, la propagaci de rajos lluminosos en fibres de cristall fotnic i la possibilitat de controlar el seu comportament usant medis peridics, est sent una de les perspectives ms prometedores en la busca dalternatives a la tecnologia dels semiconductors. En este sentit, la Computaci dAltes Prestacions permet, per mitj de la simulaci, conixer el comportament de la llum en eixos medis, donant suport experimental a les qestions teriques que en lactualitat sestan investigant.

Per a obtindre un software de qualitat, sha utilitzat un paradigma de cicle de vida de tipus semiautomtic. A ms, shan realitzat nombroses proves que han perms determinar, per una part, els parmetres ptims dels algoritmes implementats i, duna altra, analitzar la precisi i eficincia del codi implementat.

Abstract

The present memory is framed in the research field of High-Performance Computing of Matrix Functions and its Application to the Solution of Differential Equations. This research field is having an important growth in the last years, since it provides solutions to very diverse questions, such the simulation of physical phenomena or the treatment of control problems.

The thesis is focused, fundamentally, on the development of methods and the implementation of algorithms that compute Matrix Functions, and its application to the solution of Ordinary Differential Equations (ODEs) and Differential Matrix Riccati Equations (DMREs).

The starting point of the developed work has been the study of the state-of-the-art of each one of those areas, setting out new methods and algorithms that, in some way, improve the existing ones.

Diverse fields of application of this type of approaches have also been explored. One of them, the propagation of light beams in photonic crystal fibers and the possibility of controlling their behaviour using periodic means, is one of the most promising perspectives in the search of alternatives to the semiconductors technology. In this sense, the High-Performance Computing allows, by means of the simulation, to know the behaviour of the light in those means, giving experimental support to the theoretical questions that at the present time are the subject of research.

In order to obtain quality software, a semiautomatic life cycle has been used. In addition, numerous tests have been carried out, which have allowed, on the one hand, to the determine optimal values for the parameters of the implemented algorithms and, on the other hand, to analyze the precision and efficiency of the implemented code.

Agradecimientos

Al llegar al final de un largo viaje, uno contempla todo el camino recorrido, y recuerda cada una de las etapas por las que ha ido pasando; en especial, suele recordar como comenz y como ha llegado a esa meta final. Todo ese trayecto ha trascurrido por numerosas dificultades, pero gracias a la familia, amigos y compaeros de trabajo, ha llegado a buen trmino. Por todo ello quiero expresar mi ms profundo agradecimiento a todos aquellos, que de alguna manera, han contribuido a este feliz desenlace.

En primer lugar quiero agradecer especialmente toda la ayuda y apoyo que he recibido durante todo este tiempo a mi director de tesis Dr. Vicente Hernndez Garca. De l quiero destacar su profundo conocimiento de las materias desarrolladas en la tesis, su rigurosidad cientfica, su clara visin de los aspectos que pudieran ser novedosos y sobre todo por la paciencia y confianza que siempre ha depositado en m.

Agradezco tambin a mis compaeros de viaje Enrique Arias y Jess Peinado, por sus constantes apoyos y compartir con ellos tareas de investigacin; a mi compaero de despacho Juan Garayoa, por todo lo compartido en los muchos aos que nos conocemos y por la ayuda que siempre he tenido de l; a Pedro Lpez, por su constante apoyo y sabios consejos; a Pedro Ruiz, por el camino que hemos iniciado y el que nos queda por recorrer; a mis compaeros de la asignatura de CNU Victor Garca e Ignacio Blanquer, por toda la ayuda que en numerosas ocasiones me han brindado. Tampoco quiero olvidar a mis compaeros del grupo de investigacin Antonio Vidal, Vicente Vidal, Jos E. Romn, David Guerrero, Jos Miguel Alonso, Fernando Alvarruiz, Gabriel Garca, Germn Vidal, etc., por todos los consejos y ayudas que en muchas ocasiones he recibido de ellos. En general, quiero agradecer a todos los compaeros del Departamento de Sistemas Informticos y Computacin de la Universidad Politcnica de Valencia por la ayuda que en algn momento me hayan podido dar.

Quiero agradecer tambin toda la ayuda y colaboracin de Albert Ferrando, Pedro Fernndez de Crdoba y Mario Zacars, que me ha permitido conocer un rea de investigacin tan importante como la Fotnica en la que aplicar los algoritmos de clculo de Funciones de Matrices desarrollados en esta Tesis .

Muchas gracias, como no poda ser menos, a mis amigos Dolores, Javier, Neri, Amalia, Miguel, Rosa, Pablo, Jos, Laura, Vicente, Juan, Manoli, Abelardo, Gloria, etc., por esos momentos que hemos compartido juntos y que espero sigamos disfrutando.

Muchas gracias a mis padres Jacinto y Gloria por darme la vida, y todo el cario y afecto que, de manera desinteresada, siempre me han mostrado. Gracias tambin a mi hermana Gloria, por todas las cosas compartidas y por el mutuo afecto que nos tenemos. Agradezco tambin la comprensin y nimo que siempre me ha dado mi familia ms cercana Pepe, Emilia, Pepe, Eli, Miguel, Cristina, Carlos, Lourdes, Carol, Toni, Andrs, Ani, Maria Jess, Guillermo, Miguel ngel, Maria Jos, Marivi, Silvia, Bernab, etc., y mis sobrinos Isabel, Carlos, Patricia, Victor, Adrin, Javier, Maria Jess, Guillermo.

Por ltimo, gracias a Mari, amiga, esposa y compaera por todo el cario compartido desde nuestra adolescencia, y por todo el apoyo, paciencia y comprensin que siempre ha tenido conmigo, y a mis hijos Jorge y lvaro, por el cario que siempre recibo de ellos.

VII

NDICE GENERAL

Captulo 1 Introduccin......................................................................... 1 1.1 Resumen de Contenidos.................................................................................... 1 1.2 Objetivos y Aportaciones de la Tesis................................................................ 1 1.3 Metodologa...................................................................................................... 4 1.4 Estructura de la Tesis ....................................................................................... 7

Captulo 2 Estado del Arte .................................................................. 11 2.1 Resumen de Contenidos.................................................................................. 11 2.2 Funciones de Matrices ................................................................................... 11

2.2.1 Definiciones y Propiedades ................................................................................................11 2.2.2 Funciones de Matrices ms Usuales ...................................................................................14

2.2.2.1 Funcin Exponencial.................................................................................................14 2.2.2.2 Funcin Signo ...........................................................................................................15 2.2.2.3 Funcin Raz Cuadrada.............................................................................................16 2.2.2.4 Funcin Raz p-sima................................................................................................19 2.2.2.5 Funcin Logaritmo....................................................................................................21 2.2.2.6 Funciones Seno y Coseno .........................................................................................22

2.2.3 Mtodos Numricos para el Clculo de Funciones de Matrices .........................................23 2.2.3.1 Funcin Exponencial.................................................................................................23

2.2.3.1.1 Mtodos Basados en las Series de Taylor ............................................................23 2.2.3.1.2 Mtodos Basados en los Aproximantes de Pad ..................................................23 2.2.3.1.3 Mtodos Basados en Integracin Numrica .........................................................27 2.2.3.1.4 Mtodos Polinomiales ..........................................................................................29 2.2.3.1.5 Mtodos Basados en la Descomposicin de Matrices ..........................................32 2.2.3.1.6 Mtodos Basados en los Subespacios de Krylov..................................................36

2.2.3.2 Funcin Signo ...........................................................................................................37 2.2.3.3 Funcin Raz Cuadrada.............................................................................................39 2.2.3.4 Funcin Raz p-sima de una Matriz.........................................................................41 2.2.3.5 Funcin Logaritmo....................................................................................................43 2.2.3.6 Funcin Coseno.........................................................................................................45 2.2.3.7 Caso General .............................................................................................................46

2.2.4 Software de Funciones de Matrices ....................................................................................47 2.2.4.1 Expokit......................................................................................................................47 2.2.4.2 Proyecto Parallel Computation of Matrix Functions .............................................47 2.2.4.3 Proyecto Numerical Analysis of Matrix Functions ...............................................48

2.3 Ecuaciones Diferenciales Ordinarias (EDOs) ............................................... 48 2.3.1 Definiciones y Propiedades ................................................................................................48 2.3.2 Mtodos Numricos para la Resolucin de EDOs..............................................................49 2.3.3 Mtodos de un solo Paso ....................................................................................................49

2.3.3.1 Mtodos Basados en las Series de Taylor .................................................................49 2.3.3.2 Mtodos de Runge-Kutta ..........................................................................................50 2.3.3.3 Mtodos Multipaso Lineales .....................................................................................52

2.3.3.3.1 Mtodos de Adams...............................................................................................52 2.3.3.3.2 Mtodos BDF .......................................................................................................54

2.3.4 Linealizacin a Trozos de EDOs ........................................................................................55 2.3.5 Software para la Resolucin de EDOs................................................................................56

2.4 Ecuaciones Diferenciales Matriciales de Riccati (EDMRs) .......................... 58 2.4.1 Definiciones y Propiedades ................................................................................................58 2.4.2 Mtodos de Resolucin de EDMRs....................................................................................60

2.4.2.1 Integracin Directa....................................................................................................60 2.4.2.2 Mtodos de Linealizacin .........................................................................................60

VIII

2.4.2.2.1 Mtodo de Davison-Maki.....................................................................................61 2.4.2.2.2 Procedimiento Iterativo Matricial ASP (Automatic Synthesis Program) .............62

2.4.2.3 Mtodo BDF .............................................................................................................62 2.4.3 Mtodos de Resolucin de EDMRs Simtricas ..................................................................64

2.4.3.1 Mtodos de Linealizacin .........................................................................................64 2.4.3.1.1 Mtodo de la Exponencial no Negativa................................................................64 2.4.3.1.2 Mtodo de Schur ..................................................................................................65

2.4.3.2 Mtodo de Chandrasekhar.........................................................................................66 2.4.3.3 Algoritmo de Particionado Numrico (APN)............................................................68 2.4.3.4 Mtodo Basado en la Ecuacin Algebraica de Riccati (EAR) ..................................70 2.4.3.5 Mtodo de Leipnik ....................................................................................................71 2.4.3.6 Mtodo de la Raz Cuadrada .....................................................................................72 2.4.3.7 Mtodo de Rusnak ....................................................................................................73 2.4.3.8 Mtodos Conservativos y Mtodos Simplcticos .....................................................74 2.4.3.9 Mtodos BDF para EDMRs de gran Escala..............................................................76

2.4.4 Aplicaciones .......................................................................................................................78 2.4.4.1 Problemas del Control ptimo..................................................................................78 2.4.4.2 Problemas de Filtrado y Estimacin..........................................................................79 2.4.4.3 Sistemas de Parmetros Distribuidos ........................................................................80 2.4.4.4 Reduccin de Orden y Desacoplamiento ..................................................................81 2.4.4.5 Resolucin de Problemas de Contorno .....................................................................82

2.4.5 Software para la Resolucin de EDMRs ............................................................................83 2.5 Conclusiones................................................................................................... 84

Captulo 3 Clculo de Funciones de Matrices ................................... 87 3.1 Resumen de Contenidos.................................................................................. 87 3.2 Algoritmos Basados en los Aproximantes Diagonales de Pad..................... 90

3.2.1 Esquema General................................................................................................................90 3.2.2 Determinacin de los Polinomios de la Aproximacin Diagonal de Pad .........................92 3.2.3 Funciones Polinmicas y Racionales..................................................................................94 3.2.4 Clculo de Funciones de Matrices ......................................................................................96

3.2.4.1 Funcin Exponencial.................................................................................................97 3.2.4.2 Funcin Potencia Fraccionaria ..................................................................................99 3.2.4.3 Funcin Logaritmo..................................................................................................102 3.2.4.4 Funcin Coseno.......................................................................................................104 3.2.4.5 Funcin Seno ..........................................................................................................106

3.3 Algoritmos Basados Descomposicin Real de Schur de una matriz ............ 108 3.3.1 Esquema General..............................................................................................................108 3.3.2 Algoritmo Basado en la Reduccin a una Forma Diagonal por Bloques..........................109 3.3.3 Algoritmos Basados en la Resolucin de la Ecuacin Conmutante .................................112

3.3.3.1 Algoritmos Orientados a Columnas y a Diagonales................................................113 3.3.3.1.1 Algoritmo Orientado a Columnas ......................................................................117 3.3.3.1.2 Algoritmo Orientado a Diagonales.....................................................................118

3.3.3.2 Algoritmos Orientados a Bloques ...........................................................................119 3.3.3.3 Algoritmo con Agrupacin de Valores Propios Cercanos ......................................121

3.3.4 Algoritmo Basado en los Aproximantes Diagonales de Pad...........................................124 3.4 Conclusiones................................................................................................. 125

Captulo 4 Linealizacin a Trozos .................................................... 129 4.1 Resumen de Contenidos................................................................................ 129 4.2 Mtodos de Linealizacin a Trozos para EDOs........................................... 131

4.2.1 EDOs no Autnomas ........................................................................................................131 4.2.1.1 Mtodo Basado en los Aproximantes Diagonales de Pad .....................................135 4.2.1.2 Mtodo Basado en la Ecuacin Conmutante...........................................................142

IX

4.2.1.3 Mtodo Basado en los Subespacios de Krylov .......................................................145 4.2.2 EDOs Autnomas .............................................................................................................149

4.2.2.1 Mtodo Basado en los Aproximantes Diagonales de Pad .....................................151 4.2.2.2 Mtodo Basado en la Ecuacin Conmutante...........................................................153 4.2.2.3 Mtodo Basado en los Subespacios de Krylov .......................................................155

4.3 Mtodos de Linealizacin a Trozos de EDMRs ........................................... 158 4.3.1 Resolucin de EDMRs con Coeficientes Variables..........................................................158

4.3.1.1 Mtodo Basado en los Aproximantes Diagonales de Pad .....................................160 4.3.1.2 Mtodo Basado en la Ecuacin Conmutante...........................................................167 4.3.1.3 Mtodo Basado en los Subespacios de Krylov .......................................................172

4.3.2 Resolucin de EDMRs con Coeficientes Constantes .......................................................175 4.3.2.1 Mtodo Basado en los Aproximantes Diagonales de Pad .....................................177 4.3.2.2 Mtodo Basado en la Ecuacin Conmutante...........................................................181 4.3.2.3 Mtodo Basado en los Subespacios de Krylov .......................................................184

4.4 Conclusiones................................................................................................. 186

Captulo 5 Resultados Experimentales ............................................ 189 5.1 Resumen de Contenidos................................................................................ 189 5.2 Clculo de Funciones de Matrices ............................................................... 190

5.2.1 Funciones Polinmicas y Racionales................................................................................190 5.2.1.1 Resultados Funciones Polinmicas .........................................................................191 5.2.1.2 Resultados Funciones Racionales ...........................................................................194

5.2.2 Rutinas Basadas en los Aproximantes Diagonales de Pad..............................................200 5.2.3 Rutinas Basadas en la Descomposicin real de Schur de una matriz ...............................210

5.3 Propagacin de Ondas Monocromticas en Fibras de Cristal Fotnico .... 214 5.3.1 Algoritmo Basado en la Diagonalizacin de una Matriz ..................................................216 5.3.2 Algoritmo Basado en los Aproximantes Diagonales de Pad...........................................217 5.3.3 Algoritmo Basado en la Iteracin DB y en los Aproximantes Diagonales de Pad .........218 5.3.4 Resultados.........................................................................................................................218

5.4 Resolucin de EDOs..................................................................................... 220 5.4.1 EDOs Autnomas .............................................................................................................222 5.4.2 EDOs no autnomas .........................................................................................................237

5.5 Resolucin de EDMRs.................................................................................. 246 5.5.1 EDMRs con Coeficientes Constantes ...............................................................................249 5.5.2 EDMRs con Coeficientes Variables .................................................................................266

5.6 Conclusiones................................................................................................. 280

Captulo 6 Conclusiones y Lneas Futuras de Investigacin ......... 285 6.1 Resumen de Contenidos................................................................................ 285 6.2 Conclusiones Finales.................................................................................... 285

6.2.1 Funciones de Matrices ......................................................................................................285 6.2.2 Aplicacin de las Funciones de Matrices .........................................................................286 6.2.3 Resolucin de EDOs.........................................................................................................287 6.2.4 Resolucin de EDMRs .....................................................................................................288

6.3 Publicaciones en el Marco de la Tesis ......................................................... 290 6.4 Lneas Futuras de Investigacin .................................................................. 292

Apndice A. Conceptos Bsicos y Notaciones ................................. 295

Apndice B. MATLAB...................................................................... 307

X

Resolucin de EDOs.......................................................................................................................307 Funciones de Matrices ....................................................................................................................308

Apndice C. BLAS y LAPACK........................................................ 311 BLAS 312

Convenciones en el BLAS .........................................................................................................312 Estructura del BLAS ..................................................................................................................313

LAPACK ........................................................................................................................................315 Estructura del LAPACK ............................................................................................................315 Tratamiento de Errores en el LAPACK .....................................................................................316 Equilibrado y Condicionamiento en LAPACK..........................................................................319 Proyector Espectral y Separacin de Matrices ...........................................................................320 Otras Caractersticas del LAPACK............................................................................................322

Argumentos Matriciales ........................................................................................................322 Matrices de Trabajo...............................................................................................................322 Argumento Info .....................................................................................................................322 Determinacin del Tamao de Bloque ptimo .....................................................................322

Prestaciones del LAPACK.........................................................................................................323

Apndice D. SGI Altix 3700.............................................................. 325 Arquitectura ....................................................................................................................................325 Software..........................................................................................................................................325

Compiladores .............................................................................................................................326 Libreras .....................................................................................................................................326

Bibliografa .............................................................................................. 327

Captulo 1: Introduccin

1

Captulo 1 Introduccin

1.1 Resumen de Contenidos Esta memoria se enmarca dentro de la lnea de investigacin de Computacin de Altas Prestaciones para el Clculo de Funciones de Matrices y su aplicacin a la resolucin de problemas que aparecen en ingeniera y en otras reas de aplicacin. Entre los problemas tratados en esta tesis se encuentran la Resolucin de Ecuaciones Diferenciales Ordinarias (EDO), la Resolucin de Ecuaciones Diferenciales Matriciales de Riccati (EDMRs) y la Simulacin de la Propagacin de Ondas en Fibras de Cristal Fotnico. Para ello, se han diseado nuevos mtodos y algoritmos, escritos en MATLAB y FORTRAN, que resuelven los problemas citados. La implementacin de dichos algoritmos se ha realizado de manera eficiente y portable, desde un punto de vista computacional, al haber utilizado libreras optimizadas de BLAS (Basic Linear Algebra Subroutines) y LAPACK (Linear Algebra PACKage), hoy por hoy, los estndares ms ampliamente utilizados en el desarrollo de software numrico de Altas Prestaciones.

Este captulo est estructurado en cuatro secciones. En la segunda seccin se enumeran los objetivos que han servido de gua en el desarrollo de la tesis, describiendo adems las aportaciones ms relevantes de la misma.

La tercera seccin describe la metodologa utilizada en el desarrollo del software. Para obtener un software de calidad es necesario utilizar metodologas procedentes de la Ingeniera del Software. Para ello se han aplicado mtodos y tcnicas que proceden de dicha disciplina, adaptndolos convenientemente para el desarrollo de Software de Computacin Numrica de Altas Prestaciones.

La ltima seccin est dedicada a detallar el contenido de cada uno de los captulos que conforman esta tesis, describiendo brevemente el contenido de los mismos.

1.2 Objetivos y Aportaciones de la Tesis Los objetivos generales que se han pretendido alcanzar al desarrollar esta tesis han sido:

Estudiar las propiedades numricas de las Funciones de Matrices ms usuales y as desarrollar nuevos algoritmos para su clculo.

Resolver EDOs y EDMRs mediante tcnicas que involucran Funciones de Matrices, desarrollando nuevos mtodos y algoritmos.

Anlisis y resolucin de problemas reales en los que es necesario el clculo de Funciones de Matrices.

Desarrollar un software de computacin numrica de calidad, es decir, eficiente, de altas prestaciones, portable, robusto y correcto, para la resolucin de los problemas citados.

Todos estos objetivos se han alcanzado, como a continuacin se detalla.


2

La necesidad de calcular Funciones de Matrices aparece en una gran variedad de aplicaciones, constituyendo una herramienta bsica en el diseo de sistemas de control, problemas de conveccin difusin, estudio de fluidos, etc. En algunas de estas aplicaciones se requiere un tiempo de clculo muy elevado, al aparecer en la resolucin del problema matrices de gran dimensin, mientras que en otras es necesario realizar muchos clculos por unidad de tiempo para, por ejemplo, poder interactuar sobre un sistema fsico en tiempo real. En esta tesis se ha realizado un estudio completo de las funciones matriciales ms utilizadas, proponindose la utilizacin de metodologas generales para el clculo de las mismas. En la actualidad el paquete de software MATLAB tiene implementadas un amplio conjunto de Funciones de Matrices; sin embargo, nicamente se dispone de un reducido nmero de rutinas escritas en lenguajes de alto nivel que calculan algunas de las funciones matriciales ms usuales. Entre las contribuciones de esta tesis para el clculo de Funciones de Matrices se encuentran las siguientes:

Desarrollo de algoritmos, basados en metodologas generales, para el clculo de Funciones de Matrices: algoritmos basados en los aproximantes diagonales de Pad de una funcin y algoritmos basados en la descomposicin real de Schur de una matriz.

Se ha diseado nuevos algoritmos basados en los aproximantes diagonales de Pad que permiten el clculo eficiente de Funciones de Matrices como, por ejemplo, la potencia fraccionaria de una matriz (Algoritmo 3.7) o la funcin seno matricial (Algoritmo 3.10).

Se han diseado nuevos algoritmos que utilizan la descomposicin real de Schur de una matriz para calcular Funciones de Matrices. Entre estos algoritmos se encuentran el basado en la forma diagonal a bloques (Algoritmo 3.13 ), los basados en la Ecuacin Conmutante (Algoritmo 3.15, Algoritmo 3.16, Algoritmo 3.17, Algoritmo 3.18), el basado en la agrupacin en clusters de los valores propios cercanos de un matriz (Algoritmo 3.22) y el basado en los aproximantes diagonales de Pad (Algoritmo 3.23).

Diseo e implementacin de funciones/rutinas escritas en MATLAB y FORTRAN, para el clculo de Funciones de Matrices, basadas en las rutinas anteriores.

Estudio, diseo e implementacin de rutinas de altas prestaciones que permiten la simulacin de la propagacin de ondas en fibras de cristal fotnico.

Para la mayora de las EDOs no lineales se desconoce su solucin analtica y hay que utilizar tcnicas numricas para obtener soluciones aproximadas. Estas tcnicas se basan en la transformacin, mediante frmulas de diferenciacin o de integracin numrica, de un problema continuo en otro discreto, siendo hasta ahora los mtodos Runge-Kutta o BDF (Backward Differentiation Formulae) los ms ampliamente utilizados. En esta tesis se propone resolver EDOs mediante la tcnica de linealizacin a trozos. Esta tcnica consiste en dividir el intervalo considerado en subintervalos ms pequeos, de manera que en cada uno de ellos se realiza una aproximacin lineal de la funcin que define a la EDO. Entre las aportaciones realizadas en esta tesis para la resolucin de EDOs se encuentran las siguientes:

Demostracin del Teorema 4.1 que permite resolver EDOs mediante la tcnica de linealizacin a trozos de la funcin que define a la EDO, y en donde no se requiere que la matriz Jacobiana sea invertible.


3

Desarrollo de dos nuevos mtodos, basados en el teorema anterior, para la resolucin de EDOs:

Mtodo basado en el clculo de la exponencial de una matriz a bloques, asociada al problema, mediante aproximantes diagonales de Pad.

Mtodo basado en el clculo del producto de la exponencial de una matriz a bloques por un vector mediante una aproximacin basada en subespacios de Krylov.

Desarrollo de un mtodo para la resolucin de EDOs basado en la linealizacin a trozos y en la Ecuacin Conmutante. En esta aproximacin es necesario que la matriz Jacobiana sea invertible.

Para cada uno de los mtodos anteriores se han desarrollo algoritmos para la resolucin de EDOs no autnomas (Algoritmo 4.5, Algoritmo 4.7, Algoritmo 4.11) y para la resolucin de EDOs autnomas (Algoritmo 4.14, Algoritmo 4.16 y Algoritmo 4.18).

Implementacin de los algoritmos anteriores en MATLAB y FORTRAN, determinando los parmetros caractersticos de los diferentes mtodos y optimizando sus costes espacial y temporal.

Una de las ecuaciones diferenciales no lineales ms usadas en el mbito cientfico es la Ecuacin Diferencial Matricial de Riccati (EDMR). Esta ecuacin juega un papel fundamental en problemas de control ptimo y filtrado. Una de las tcnicas ampliamente utilizadas para resolver dicha ecuacin consiste en aplicar el mtodo BDF. Este mtodo est especialmente indicado para resolver EDMRs de tipo rgido. Otro de los mtodos que se pueden aplicar en la resolucin de EDMRs consiste en la vectorizacin de ecuaciones diferenciales matriciales, que permite convertir una EDMR en una EDO. En esta tesis se han desarrollado varios mtodos de resolucin de EDMRs que consisten en aplicar la linealizacin a trozos a la EDO anterior, utilizando tcnicas especiales para la resolucin eficiente de la misma. Entre las aportaciones relativas a la resolucin de EDMRs se encuentran las siguientes:

Desarrollo de una nueva metodolga para la resolucin de EDMRs basada en la tcnica de linealizacin a trozos. Esta metodologa consiste, bsicamente, en transformar la EDMR en una EDO de gran dimensin y aplicarle la linealizacin a trozos.

Desarrollo de tres mtodos basados en la linealizacin a trozos. Mtodo basado en los aproximantes diagonales de Pad. El primer mtodo

consiste en calcular la solucin aproximada de una EDMR en un instante determinado mediante el clculo de dos exponenciales de matrices definidas a bloques. De este modo, se pasa de un problema vectorial de gran dimensin a otro matricial de menor dimensin. Este mtodo est basado en dos teoremas desarrollados en el mbito de esta tesis, Teorema 4.3 y Teorema 4.5, que se aplican, respectivamente, a EDMRs con coeficientes variables y a EDMRs con coeficientes constantes.

Mtodo basado en la Ecuacin Conmutante. Para el segundo mtodo se han demostrado dos teoremas, uno para EDMRs con coeficientes variables (Teorema 4.4) y otro para EDMRs con coeficientes constantes (Teorema 4.6), que permiten transformar un problema vectorial de resolucin de una


4

EDO de gran dimensin en otro matricial, consistente en resolver ecuaciones matriciales de Sylvester.

Mtodo basado en los subespacios de Krylov. El tercer mtodo est basado en el clculo del producto de la exponencial de una matriz definida a bloques, obtenida en el proceso de vectorizacin, por un vector, utilizando para ello los subespacios de Krylov.

A partir de los mtodos anteriores se han desarrollado seis nuevos algoritmos (Algoritmo 4.21, Algoritmo 4.23, Algoritmo 4.26, Algoritmo 4.29, Algoritmo 4.31, Algoritmo 4.33) y sus correspondientes implementaciones.

A partir de las pruebas realizadas en el Captulo 5, se puede comprobar que el coste computacional de las implementaciones basadas en los mtodos de linealizacin a trozos resultan ser menores que las implementaciones basadas en el mtodo BDF ([Diec92]), siendo adems algo ms precisas. Adems, tienen un buen comportamiento cuando se aplican a EDMRs de tipo rgido.

Hay que destacar que actualmente no se dispone de funciones escritas en MATLAB que resuelvan EDMRs y, en el caso de rutinas escritas en FORTRAN, tan slo se dispone del paquete DRSOL (), pero nicamente para datos en simple precisin.

Debido al gran nmero de algoritmos desarrollados e implementados, ha sido necesario utilizar una notacin que permitiese conocer a partir del nombre de un algoritmo la finalidad del mismo y el mtodo empleado. La nomenclatura utilizada para los algoritmos es txxyyyzzz, donde t indica el tipo de dato utilizado, xx indica el tipo de matriz, yyy indica el problema que se resuelve y zzz el mtodo utilizado. Los valores de los tres primeros caracteres son:

t: tipo de dato utilizado. t=s, datos reales de simple precisin; t=d, datos reales de doble precisin; t=c, datos complejos de simple precisin; t=z, datos complejos de doble precisin.

xx: tipo de matriz. xx=ge, indica matrices generales; xx=ct, indica matrices casi triangulares superiores.

La misma nomenclatura ha sido utilizada para nombrar a las funciones de MATLAB y a las rutinas en FORTRAN, de manera que para cada algoritmo se tiene una funcin en MATLAB y una rutina en FORTRAN con el mismo nombre.

1.3 Metodologa As como las metodologas para el desarrollo del software de gestin estn muy avanzadas, el software cientfico adolece en la actualidad de herramientas que cubran todas las etapas para el desarrollo completo de una aplicacin. Las tcnicas ms empleadas para el desarrollo del software de gestin no se pueden aplicar debido, fundamentalmente, a la propia naturaleza de las aplicaciones del clculo cientfico que, en general, poseen muy pocas caractersticas en comn. En esta tesis se aboga por


5

utilizar un ciclo de vida semiautomtico consistente, bsicamente, en dos etapas que a continuacin se describen.

Para la primera etapa se utiliza MATLAB pues dispone de un lenguaje de programacin que permite expresar y desarrollar, de forma sencilla, algoritmos numricos, disponiendo adems de numerosas funciones del algebra matricial y de una potente herramienta de depuracin de cdigo que facilita el desarrollo de los mismos.

En la segunda etapa se utiliza un lenguaje de alto nivel (FORTRAN) junto con las libreras BLAS y LAPACK. Estas libreras implementan, por una parte, las operaciones ms comunes entre vectores y matrices y, por otra, disponen de numerosas rutinas que resuelven los problemas ms comunes que aparecen en el algebra matricial. Esto posibilita escribir los programas en FORTRAN (o C) de forma modular, centrando la atencin en los aspectos algortmicos y no en los detalles del propio lenguaje utilizado. Otra ventaja adicional es que la mayor parte de los sistemas informticos utilizados en computacin disponen de libreras optimizadas de BLAS y LAPACK, con el consiguiente rendimiento de los cdigos que utilizan a esas rutinas.

De este modo, la combinacin de estas herramientas posibilita la creacin de software numrico robusto y de altas prestaciones de forma sistemtica y sencilla. En la siguiente figura se muestra el ciclo de vida utilizado en el desarrollo del software numrico.

Figura 1.1: Ciclo de vida utilizado en el desarrollo del software.

En (1) se tiene claramente definido el problema que se quiere resolver. En (2) se realiza una descripcin matemtica del mtodo que se va a implementar, partiendo de un estudio terico de la viabilidad del mismo. En (3) se realiza un primer algoritmo, escrito en MATLAB, que implementa el mtodo desarrollado en (2). A travs de sucesivas pruebas se determinan, mediante (4), los valores ptimos de los parmetros caractersticos del mtodo aplicado. Una vez se ha realizado este ajuste, se tiene un primer algoritmo escrito en MATLAB. Como paso intermedio para la codificacin del algoritmo anterior en un lenguaje de alto nivel, se desarrolla un segundo algoritmo en (5) mediante la traduccin del primer algoritmo, de manera que las operaciones que aparecen en l corresponden a operaciones bsicas del BLAS y del LAPACK. En (6) se hace una codificacin en un lenguaje de alto nivel en el que se hace una traduccin del algoritmo desarrollado en (5) utilizando llamadas a BLAS o a LAPACK. La etapa (7) es necesaria, fundamentalmente, cuando se usan algoritmos orientados a bloques, en los que es necesario optimizar los accesos a memoria.

Formulacin del problema (1)

Algoritmo 1

MATLAB (3)

Ajuste de los parmetros del algoritmo 1 (4)

Descripcin matemtica del

mtodo (2)

Algoritmo 2

MATLAB (5)

Cdigo en lenguaje de alto nivel (6)

Ajuste de los parmetros del

cdigo (7)


6

En la siguiente figura se muestra un ejemplo en el que aparece la codificacin de un fragmento de un algoritmo segn la metodologa considerada.

Figura 1.2: Codificacin de un fragmento de un algoritmo en las etapas (3), (5) y (6).

Como se puede observar, el cdigo de la etapa (3) se desglosa en varias lneas de cdigo correspondiente al algoritmo de la etapa (5). El cdigo obtenido en (6) es una traduccin, lnea a lnea, del cdigo de la etapa (5).

Para las etapas (3) y (6) se ha dispuesto de un numeroso conjunto de pruebas que permiten validar el cdigo desarrollado. Estas bateras de pruebas provienen, en algunos casos, de problemas reales y, en otros, de pruebas especiales que permiten comprobar la bondad de los algoritmos desarrollados. Entre las bateras de pruebas utilizadas se encuentran las siguientes:

Clculo de Funciones de Matrices. The Matrix Computation Toolbox for MATLAB ([High02]). Contiene una

coleccin de funciones escritas en MATLAB para la generacin de matrices de prueba, el clculo de factorizaciones matriciales, la visualizacin de matrices, etc.

Adems del anterior paquete, se han diseado y utilizado, dentro del marco de la tesis, numerosas funciones/rutinas escritas en MATLAB y FORTRAN que

(3) G= A21+A22*X-X*A11-X*A12*X;

(5) G=A21; G=A22*X+G; G=-X*A11+G; W=X*A12; G=-W*X+G;

(6) C G=A21 CALL DCOPY(MN,WORK(NA21),1,WORK(NG),1) C G=A22*X+G CALL DGEMM('N','N',M,N,M,ONE,WORK(NA22),M,X,M, $ ONE,WORK(NG),M) C G=-X*A11+G CALL DGEMM('N','N',M,N,N,-ONE,X,M,WORK(NA11),N, $ ONE,WORK(NG),M) C W=X*A12; CALL DGEMM('N','N',M,M,N,ONE,X,M,WORK(NA12),N, $ ZERO,WORK(NWORK),M) C G=-W*X+G; CALL DGEMM('N','N',M,N,M,-ONE,WORK(NWORK),M,X,M, $ ONE,WORK(NG),M)


7

generan matrices especiales, idneas para el estudio de Funciones de Matrices como, por ejemplo, matrices casi triangulares superiores, matrices de Hessenberg, matrices con valores propios mltiples, etc.

Resolucin de EDOs. Test Set for Initial Value Problems Solvers ([LiSw98]). Contiene una

coleccin de problemas de valores iniciales para EDOs, Ecuaciones Diferenciales Implcitas (EDIs) y Ecuaciones Diferenciales Algebraicas (EDAs), escritos en FORTRAN y procedentes de problemas reales.

Resolucin de EDMRs. Time-Varying Riccati Differential Equations with Known Analytic Solutions

([Choi92]). Se trata de un artculo aparecido en la revista IEEE Transactions on Automatic Control, en el que se definen problemas de EDMRs con solucin analtica conocida, ideales para su utilizacin en pruebas.

Numerical Integration of the Differential Riccati Equation and Some Related Issues ([Diec92]). Contiene una recopilacin de varios problemas de EDMRs que provienen de problemas reales, adems de una de las aproximaciones del mtodo de resolucin BDF ms ampliamente utilizada.

1.4 Estructura de la Tesis El contenido de esta tesis se estructura en seis captulos. El primero corresponde al actual captulo, en el que se ha realizado una breve descripcin de los objetivos planteados en esta tesis, se han enumerado las aportaciones realizadas y se ha explicado la metodologa utilizada en el desarrollo e implementacin de los algoritmos desarrollados.

En el segundo captulo se realiza una descripcin del estado del arte correspondiente al clculo de Funciones de Matrices y a la resolucin de EDOs y EDMRs. En el caso de las Funciones de Matrices se describen algunas de las definiciones de funcin de una matriz, se enumeran sus propiedades ms importantes y se describen los mtodos ms usuales para su clculo. Para la resolucin de EDOs se detallan nicamente aquellos aspectos de inters que posteriormente se utilizarn en el desarrollo e implementacin de los nuevos mtodos basados en la linealizacin a trozos. Por ltimo, se realiza una descripcin detallada del estado del arte correspondiente a la resolucin de EDMRs, haciendo una breve exposicin de sus principales propiedades, describiendo los mtodos numricos ms destacados que se han ido utilizando a lo largo del tiempo y enumerando algunas de sus aplicaciones.

El tercer captulo est dedicado a describir los algoritmos desarrollados en esta tesis para el clculo de Funciones de Matrices. Para ello se han desarrollado dos metodologas generales: una basada en los aproximantes diagonales de Pad y otra que utiliza la reduccin a la forma real de Schur de una matriz. La primera metodologa consiste, bsicamente, en las siguientes etapas: 1.- minimizar la norma de la matriz considerada; 2.-determinar un polinomio de Taylor apropiado de la funcin; 3.- calcular, a partir del polinomio de Taylor, los polinomios de la aproximacin diagonal de Pad de la funcin; 4.- obtener la aproximacin diagonal de Pad de la funcin; y 5.- calcular la funcin de la matriz, teniendo en cuenta la reduccin de la norma realizada en la primera etapa. Una vez realizada esta descripcin se particulariza, dicho algoritmo general, al clculo de algunas Funciones de Matrices: exponencial, logartmica, potencia


8

fraccionaria, seno y coseno. La segunda metodologa utiliza la forma real de Schur de una matriz para calcular, a partir de ella, la funcin de la matriz original. Los algoritmos que utilizan esta metodologa suelen ser muy precisos y razonablemente eficientes. Entre estos algoritmos se encuentran los basados en la Ecuacin Conmutante sin agrupacin de valores propios (algoritmos orientados a columnas, a diagonales y a bloques), el algoritmo basado en la agrupacin de valores propios cercanos, el algoritmo basado en la diagonalizacin a bloques de una matriz y el basado en el clculo de Funciones de Matrices casi triangulares superiores mediante los aproximantes diagonales de Pad.

El cuarto captulo est dedicado a la resolucin de EDOs y EDMRs mediante la tcnica de linealizacin a trozos. En el caso de EDOs se demuestra el Teorema 4.1 y se presentan tres mtodos, basados en l, que permiten resolver eficientemente EDOs: Mtodo basado en los aproximantes diagonales de Pad, mtodo basado en la Ecuacin Conmutante y mtodo basado en los subespacios de Krylov.

Para la resolucin de EDMRS se ha desarrollado una metodologa consistente en transformar la EDMR en una EDO y aplicar a esta ecuacin diferencial la tcnica de linealizacin a trozos desarrollada para EDOs. Al aplicar la linealizacin a trozos, se obtiene una Ecuacin Diferencial Lineal (EDL) de gran dimensin en cada subintervalo, por lo que se hace necesaria la aplicacin de mtodos especiales para su resolucin. En este caso, en lugar de aplicar los mtodos desarrollados para EDOs, se han desarrollado tres nuevos mtodos: Mtodo basado en los aproximantes diagonales de Pad, mtodo basado en la Ecuacin Conmutante y mtodo basado en los subespacios de Krylov Todos los anteriores mtodos se han particularizado para resolver EDOs autnomas y EDMRs con coeficientes constantes de modo que se han reducido los costes computacionales y de almacenamiento.

En el quinto captulo se detallan y analizan todas las pruebas realizadas. En primer lugar se describen brevemente los componentes software y hardware que, de algn modo, se han utilizado en el desarrollo e implementacin de los algoritmos descritos en esta tesis. A continuacin se describen las pruebas realizadas para el clculo de Funciones de Matrices, comenzando con el clculo de funciones polinmicas y racionales, continuando con el clculo de funciones trascendentes mediante los aproximantes diagonales de Pad y mediante la descomposicin real de Schur de una matriz. Para cada prueba se determinan los valores ptimos de los parmetros caractersticos de cada implementacin. En tercer lugar se presenta un problema consistente en la simulacin de la propagacin de ondas monocromticas en fibras de cristal fotnico. El inters del estudio es analizar dicha propagacin sin hacer uso de experimentos reales con las consiguientes ventajas que esto supone. Para ello se analizan e implementan los mtodos numricos ms adecuados para su simulacin. A continuacin se describen las pruebas realizadas para la resolucin de EDOs, presentando el problema a resolver y sus orgenes. Para cada problema se comparan las funciones/rutinas implementadas, habiendo determinado previamente los valores ptimos de los parmetros caractersticos de cada funcin/rutina. Para esa comparacin, se han realizado diversas pruebas en las que se vara el incremento de tiempo utilizado en la linealizacin a trozos, el tiempo final y el tamao de problema. Del mismo modo, se realiza un estudio similar para la resolucin de EDMRs.

En el sexto captulo se exponen las conclusiones de todo el trabajo realizado, se enumeran las publicaciones realizadas en el marco de esta tesis y se perfilan las posibles lneas de investigacin futuras que se abren con la misma.


9

Al final de la tesis se han aadido cuatro apndices que a continuacin se detallan. En el primer apndice se describen las definiciones, propiedades y teoremas que, de algn modo, se han utilizado en esta tesis, as como la notacin empleada en la misma. En el segundo apndice se realiza una descripcin de MATLAB, como entorno de desarrollo y programacin de algoritmos. En el tercer apndice se describen BLAS y LAPACK, por ser las libreras utilizadas en el desarrollo eficiente y portable de software numrico de altas prestaciones. En el cuarto anexo se describen los componentes software y hardware que se han utilizado en el desarrollo e implementacin de los algoritmos descritos en esta tesis: la mquina SGI Altix 3700, el compilador FORTRAN de Intel y las libreras SGI SCL (Scientific Computing Software Library) que contienen el BLAS y el LAPACK.

Captulo 2: Estado del Arte

11

Captulo 2 Estado del Arte

2.1 Resumen de Contenidos En este captulo se hace una revisin de las propiedades y mtodos ms relevantes para el clculo de Funciones de Matrices, y la resolucin de Ecuaciones Diferenciales Ordinarias (EDOs) y Ecuaciones Diferencial Matriciales de Riccati (EDMRs).

Este captulo se ha estructurado en cinco secciones. La segunda seccin comienza con un estudio completo de las funciones matriciales ms utilizadas, indicando sus orgenes y aplicaciones, haciendo adems una breve descripcin de los mtodos que se han ido utilizando desde sus comienzos hasta nuestros das. Junto a la descripcin de estos mtodos se realiza un estudio comparativo de los mismos, para deducir cules son las mejores estrategias para el clculo de Funciones de Matrices. La finalidad de este estudio es encontrar metodologas generales que permitan calcular eficientemente Funciones de Matrices, sin dejar de lado cada caso particular (tipo de funcin y matriz).

En la tercera seccin se describen nicamente aquellos aspectos de inters en la resolucin de EDOs que, de alguna manera, se utilizan en los siguientes captulos, especialmente los relacionados con el desarrollo e implementacin de los nuevos mtodos basados en la linealizacin a trozos.

En la cuarta seccin se comienza con una breve descripcin de las principales propiedades de las EDMRs, detallando a continuacin los mtodos de resolucin de EDMRs ms conocidos, para finalizar con algunos ejemplos de aplicaciones de las mismas.

En la ltima seccin se exponen las conclusiones de este captulo.

2.2 Funciones de Matrices

2.2.1 Definiciones y Propiedades De una manera informal, dada una funcin compleja de variable compleja )(zf definida sobre el espectro de una matriz cuadrada A , la matriz )(Af se puede obtener sustituyendo la variable z por la matriz A en la expresin que define a )(zf . Desde un punto de vista formal, )(Af se puede definir utilizando diferentes aproximaciones. En [Rine78], Rinehart demostr la equivalencia entre ocho definiciones de funciones de matrices; quizs la ms elegante de ellas, aunque no la ms til desde el punto de vista computacional, es la que se presenta en primer lugar.

Definicin 2.1 ([GoVa96], captulo11). Sea A una matriz cuadrada definida en el conjunto de los nmeros complejos C y

)(zf una funcin analtica definida en un abierto CU que contiene al espectro de A . Si U es una curva rectificable que rodea al espectro de A , entonces la matriz

)(Af se puede definir como


12

= dzAIzzfi

Af 1))((21)( .

Segn esta definicin, el elemento ),( jk de la matriz )(Af viene dado por

( )

= dzeAIzezfi

f jTkkj

1)(21 ,

siendo ke y je , respectivamente, la k-sima y la j-sima columna de la matriz identidad I . Esta definicin proviene del teorema integral de Cauchy, por lo que se trata de una definicin independiente de la curva . Una de las definiciones ms utilizadas ([Gant90], [LaMi85]) es la basada en la forma cannica de Jordan de una matriz y en el polinomio de interpolacin de grado mnimo de una funcin.

Definicin 2.2 ([Gant90], captulo 5). Dada una funcin analtica )(zf definida en un abierto CU que contiene al espectro de nxnA C , se define la matriz )(Af como

)()( ApAf = , siendo )(zp el polinomio de grado mnimo que interpola a la funcin )(zf en el espectro de la matriz A ; es decir,

)()( )()( ij

ij fp = , 1,,1,0 = inj L , si ,,2,1 L= ,

con s el nmero de valores propios distintos de A y in la mayor de las dimensiones de los bloques de Jordan que contienen al valor propio i . A partir de estas definiciones se pueden demostrar propiedades que permiten calcular y definir, de otras formas, las funciones de matrices.

Propiedad 2.1

Dada nxnA C y )(zf funcin analtica definida en un abierto CU que contiene al espectro de A , entonces )(Af es solucin de la ecuacin

( 2.1 ) XAAX = , denominada ecuacin conmutante.

Propiedad 2.2

Sea nxnA C y )(zf funcin analtica definida en un abierto CU que contiene al espectro de A . Si 1= XBXA entonces

1)()( = XBXfAf .


13

Propiedad 2.3

Sea nxnA C y )(zf funcin analtica definida en un abierto CU que contiene al espectro de A . Si ),,,(diag 21 rAAAA L= , con ii xnni CA , ri ,,2,1 L= ,

==

r

ii nn

1

,

entonces

))(,),(),(diag()( 21 rAfAfAfAf L= . Corolario 2.1.

Sea nxnA C y )(zf una funcin analtica definida en un abierto CU que contiene al espectro de A . Si

*QSQA = es la descomposicin de Schur de A , entonces

*)()( QSQfAf = . Corolario 2.2.

Sea nxnA C y )(zf una funcin analtica definida en un abierto CU que contiene al espectro de A . Si

( 2.2 ) 1),,,diag(21

= XJJJXAr L

es la descomposicin cannica de Jordan de la matriz A , entonces

( 2.3 ) 1))(,),(),(diag()(21

= XJfJfJfXAfr L ,

siendo

( 2.4 ) ( ) iiii

ii

i

xnn

i

ii

i

in

i

in

i

i

in

i

in

ii

f

ff

nf

nf

f

nf

nff

f

Jf C

=

)(00!1

)()(0

)!2()(

)!3()(

)(0

)!1()(

)!2()(

!1)(

)(

)1(

)2()3(

)1()2()1(

LLOL

MMOOML

L

, ri ,,2,1 L= .

Otros autores definen las funciones de matrices a partir del concepto de funcin matricial primaria.

Definicin 2.3 ([HoJo91]).

Sea nxnA C y )(zf una funcin analtica definida en un abierto CU que contiene al espectro de A . Si ( 2.2 ) es la descomposicin cannica de Jordan de la matriz A , se define la funcin matricial primaria de la matriz A como la matriz )(Af obtenida a partir de las expresiones ( 2.3 ) y ( 2.4 ).


14

Una ltima aproximacin proviene de la definicin de una funcin como suma de una serie de potencias. El siguiente teorema muestra la manera de definir funciones de matrices a partir de sumas de series de potencias de matrices.

Teorema 2.1.

Dada una matriz nxnA C y )(zf una funcin analtica definida en un abierto CU que contiene al espectro de A , definida por

=

=0

)(k

kk zczf ,

entonces la serie de potencias

=0k

kk Ac ,

es convergente, cumplindose adems ([Rine78] que

=

=0

)(k

kk AcAf .

2.2.2 Funciones de Matrices ms Usuales

2.2.2.1 Funcin Exponencial Entre las diferentes funciones de matrices, la funcin exponencial tiene una especial importancia debido a su relacin con la resolucin de sistemas de ecuaciones diferenciales lineales ([Bell83], [MoVa78]) que aparecen en la resolucin de diversos modelos asociados a fenmenos fsicos, qumicos, biolgicos, econmicos, etc. ([Karl59], [Varg62]). Por ejemplo, la solucin de la Ecuacin Diferencial Lineal (EDL) ([Bell53])

)()()( tbtAxdt

tdx += , 0t

con 0)0( xx = , siendo nxnA y nb , viene dada por

+=t

stAAt dssbexetv0

)( )()0()( .

Una forma sencilla de definir la exponencial de una matriz consiste en considerar la serie de potencias

=

=0 !

1k

kz zk

e ,

y definir la exponencial de la matriz A como

=

=0 !

1k

kA Ak

e .

Esta serie resulta ser convergente para cualquier matriz cuadrada A .


15

2.2.2.2 Funcin Signo La funcin signo matricial, junto a la exponencial de una matriz, resulta ser una de las funciones matriciales que durante ms tiempo y con mayor profundidad se ha investigado. Una de las primeras referencias acerca de la funcin signo matricial se encuentra en el trabajo realizado por Zolotarjov en el ao 1877, en el que se caracterizaban las mejores aproximaciones racionales de la funcin signo escalar mediante el uso de funciones del tipo seno elptico. Si embargo, el verdadero auge de esta funcin se encuentra en el trabajo desarrollado por Roberts. En 1971 Roberts realiz un informe tcnico ([Robe71]) en el que se defina esta funcin y se describan sencillos algoritmos para el clculo de la misma. En este trabajo tambin se desarroll el escalado y la estimacin del nmero de condicin asociados a la funcin signo matricial. Este informe tcnico no fue muy conocido por la comunidad cientfica hasta su publicacin como artculo, en el ao 1980, en la revista International Journal of Control [Robe80].

En 1971 Abramov ([Abra71]) tambin utiliz un mtodo basado en el clculo de la funcin signo matricial para revolver ciertos problemas de contorno asociados a la resolucin de EDOs.

Fruto del trabajo pionero de Roberts ha sido el desarrollo de numerosos campos de investigacin relacionados con la funcin signo matricial:

Aproximacin y condicionamiento de las funciones de matrices. Aplicaciones en control como, por ejemplo, la resolucin de la Ecuacin

Algebraica Matricial de Lyapunov (EAML) y la resolucin de la Ecuacin Algebraica Matricial de Riccati (EAMR).

Teora de sistemas y clculo matricial, aplicndose, por ejemplo, en el clculo de subespacios invariantes.

Descomposiciones que aparecen en el clculo de valores propios de una matriz. Clculo de la raz cuadrada de una matriz. Clculo de la funcin sector de una matriz.

A continuacin se define la funcin signo matricial tal como aparece en [Robe80]. La funcin signo escalar se define como

+=

0)Re( si10)Re( si1

)(signzz

z .

Si nxnA C no tiene valores propios imaginarios puros, entonces existe la funcin signo matricial de A y se puede definir a partir de la descomposicin cannica de Jordan de A , como a continuacin se detalla. Si

1),,,diag(21

= XJJJXAr L

es la descomposicin cannica de Jordan de la matriz A , entonces la funcin signo matricial de A se define como

1))sign(,),sign(,)diag(sign()(sign21

= XJJJXAr L .

Al cumplirse que


16

( ) 0)(sign == iz

zdzd

,

y teniendo en cuenta ( 2.4), entonces

( )

=

)(sign0000)(sign00

00)(sign0000)(sign

sign

i

i

i

i

iJ

L

MMOMMLL

, ri ,,2,1 L= .

Es fcil comprobar que la funcin signo matricial cumple las siguientes propiedades.

Propiedad 2.4.

Si nxnA C , entonces nIA =2)](sign[ . Propiedad 2.5.

Si nxnA C , entonces )(sign)(sign)(sign AccA = . Propiedad 2.6.

Los valores propios de la matriz )(sign A , nxnA C , son 1 . 2.2.2.3 Funcin Raz Cuadrada

Uno de los mtodos ms usuales para calcular funciones de matrices consiste en realizar un escalado previo de la matriz, pues permite reducir su norma y as se pueden aplicar tcnicas generales para el clculo de funciones de matrices como, por ejemplo, las aproximaciones de tipo polinmico (aproximaciones de Taylor) o las aproximaciones de tipo racional (aproximantes de Pad). Por ejemplo, el escalado utilizado en el clculo de la funcin logartmica, se puede realizar utilizando la identidad

j

AA j 2/1log2log = , L,2,1=j , en la que aparecen races cuadradas de matrices.

Para definir la raz cuadrada de una matriz es necesario que sea consistente con la definicin correspondiente al caso escalar. Dada una matriz nxnA C , una solucin

nxnX C de la ecuacin matricial cuadrtica AX =2 ,

se llama raz cuadrada de A . Por ejemplo, fcilmente se puede comprobar que la matriz

=0010

A

no tiene races cuadradas, sin embargo, la matriz


17

=0001

A

admite como races cuadradas a las matrices

=0001

1X ,

=0001

2X .

Segn esto, puede no existir la raz cuadrada de A , o existir una o ms races de ella. El siguiente teorema caracteriza las races cuadradas de una matriz cuadrada compleja y determina cules de ellas corresponden a funciones de matrices en el sentido de la Definicin 2.2.

Lema 2.1 ([Hig287]).

Si Ci es distinto de cero, entonces el bloque de Jordan

ii

i

xnn

i

i

i

i

J C

=

000100

000001

LL

MOOMMOL

,

tiene precisamente dos races cuadradas que son funciones de i

J en el sentido de la Definicin 2.2,

( 2.5 ) ( ) iiinin

inin

i

xnn

ij

ijij

i

ij

i

iji

i

ij

i

ijijij

j

f

ff

nf

nf

f

nf

nff

f

Jf C

=

)(000!1

)()(00

)!2()(

)!3()(

)(0

)!1()(

)!2()(

!1)(

)(

)1(

)2()3(

)1()2()1(

LL

MMOOML

L

, 2,1=j ,

donde =)(jf denota una de las dos ramas de la funcin raz cuadrada en el entorno de i .

Teorema 2.2 ([Hig287]).

Sea nxnA C una matriz no singular con la descomposicin de Jordan 11 ),,,diag(

21

== XJJJXXJXAr L ,

donde iii

xnnJ C , =

=r

ii nn

1, y s ( rs ) el nmero de valores propios distintos de A .

Se verifican entonces las siguientes propiedades:


18

1. A tiene precisamente s2 races cuadradas que son funciones de A en el sentido de la Definicin 2.2, dadas por

1))(,),(),(diag(2211

= XJfJfJfXFrrjjjj L ,

sj 2,,2,1 L= , correspondientes a todas las posibles elecciones de rjjj ,,, 21 L ( { }2,1ij ,

ri ,,2,1 L= ), sujetas a la restriccin de que lk jj = si lk = . 2. Si rs < , entonces A tiene races cuadradas que no son funciones de A en el

sentido de la Definicin 2.2. Estas races forman familias parametrizadas 11))(,),(),(diag()(

2211

= XUJfJfJfXUUFrrjjjj L ,

ri

s j 212 + , ri ,,2,1 L= , siendo U una matriz no singular arbitraria que conmuta con ),,,(diag

21 rJJJ L , y para cada j existen unos ndices k y l ,

dependientes de j , de manera que lk = y lk jj . Corolario 2.3 ([Hig287]).

Si Ck es distinto de cero, entonces las nicas races cuadradas de la matriz kJ del Lema 2.1 son las que aparecen en ( 2.5 ).

Corolario 2.4 ([Hig287]).

Si cada valor propio de nxnA C aparece en un solo bloque de Jordan de la forma cannica de Jordan de A , entonces A tiene precisamente r2 races cuadradas, todas ellas funciones de A en el sentido de la Definicin 2.2.

Corolario 2.5 ([Hig287]). Toda matriz hermtica y definida positiva tiene una nica raz cuadrada hermtica y definida positiva. A continuacin se detallan varios teoremas acerca de la existencia de races de matrices cuadradas reales.

Teorema 2.3 ([HoJo91], pgina 473).

Sea una matriz nxnA . Existe una matriz nxnB , raz cuadrada de A , si y solo si se cumplen las siguientes condiciones:

1. Dados los enteros nr =0 , )( kk Arangor = , para L,2,1,0=k , entonces la secuencia }{ 1+ kk rr para L,2,1,0=k , no contiene dos apariciones consecutivas del mismo entero par y si adems 10 rr es par, entonces 12 210 + rrr .

2. Si

ii

i

xnn

i

i

i

i

J C

=

000100

000001

LL

MOOMMOL


19

es un bloque de Jordan de A , con i un valor propio real negativo de A , entonces A tiene un nmero par de bloques de Jordan de igual tamao in incluido

iJ .

Teorema 2.4 ([High87]).

Sea nxnA una matriz no singular. Existe una matriz nxnB , raz cuadrada real de la matriz A , si y solo si cada bloque de Jordan de la matriz A correspondiente a un valor propio real negativo, aparece un nmero impar de veces.

La comprobacin de la existencia de races cuadradas de una matriz, a partir de los teoremas anteriores, es complicada de manejar, fundamentalmente porque es necesario conocer la descomposicin cannica de Jordan de la matriz considerada. El siguiente teorema, cuya demostracin est basada en la descomposicin real de Schur de una matriz, permite una comprobacin ms sencilla de la existencia de races cuadradas de matrices reales.

Teorema 2.5 ([High87]).

Sea nxnA una matriz no singular. Si A tiene un valor propio real negativo, entonces A no tiene races cuadradas que son funciones de A en el sentido de la Definicin 2.2. Si A no tiene valores propios reales negativos, entonces existen exactamente cr+2 races cuadradas reales que son funciones de A en el sentido de la Definicin 2.2, siendo r el nmero de valores propios reales de A y c el nmero de pares de valores propios complejos conjugados.

2.2.2.4 Funcin Raz p-sima

Dada una matriz nxnA C , se dice que la matriz nxnX C es una raz p-sima de la matriz A si cumple

AX p = . Entre las aplicaciones que requieren el clculo de las races p-simas de una matriz se encuentra el clculo de la funcin sector definida por

AAA pp /1)()sec( = ([KoBa95], [ShTs84]). Otra posible aplicacin aparece en el escalado de una matriz para el clculo del logaritmo de una matriz. En este caso, se determina un entero positivo p de manera que

pApA /1loglog = , con |||| /1 pA menor que un cierto valor ([ChHi01], [KeL289]).

Al igual que ocurre en el caso particular de races cuadradas, la raz p-sima de una matriz puede no existir o tener una o ms soluciones. Si A es no singular, entonces admite al menos una raz p-sima; en caso contrario, la matriz A admite races p-simas dependiendo de la estructura de los divisores elementales de A correspondientes a los valores propios nulos ([Gant90], seccin 8.7).


20

Definicin 2.4 ([Smit03]).

Sea nxnA C una matriz no singular con valores propios i , ni ,,1 L= , de manera que )arg( i , ni ,,1 L= . La raz p-sima principal de A , denotada por

nxnpA C/1 , se define como la matriz que satisface las dos condiciones siguientes: 1. AA pp =)( /1 . 2. Los argumentos de los valores propios de la matriz pA /1 se encuentran en el

intervalo [/,/] pp . El siguiente teorema, generalizacin del Teorema 2.2, permite caracterizar las races p-simas de una matriz cuadrada compleja a partir de su descomposicin de Jordan, y determina cules de ellas corresponden a funciones de matrices segn la Definicin 2.2.

Lema 2.2 ([Smit03]).

Si Ci es distinto de cero, entonces el bloque de Jordan

ii

i

xnn

i

i

i

i

J C

=

000100

000001

LL

MOOMMOL

,

tiene precisamente p races p-simas que son funciones de i

J , definidas como

( ) iiinin

inin

i

xnn

ij

ijij

i

ij

i

iji

i

ij

i

ijijij

j

f

ff

nf

nf

f

nf

nff

f

Jf C

=

)(000!1

)()(00

)!2()(

)!3()(

)(0

)!1()(

)!2()(

!1)(

)(

)1(

)2()3(

)1()2()1(

LL

MMOOML

L

, pj ,,2,1 L= ,

donde pjf =)( denota una de las p ramas de la funcin raz p-sima en el entorno de i .

Teorema 2.6 ([Smit03]).

Sea nxnA C una matriz no singular con la descomposicin de Jordan ( ) 1,,,diag

21

= XJJJXAr L ,

donde iii

xnnJ C , =

=r

ii nn

1, y s ( rs ) el nmero de valores propios distintos de A

Se verifican entonces las siguientes propiedades:


21

1. A tiene precisamente sp races de ndice p , dadas por 1))(,),(),(diag(

2211

= XJfJfJfXFrrjjjj L ,

spj ,,2,1 L= , correspondientes a todas las posibles elecciones de rjjj ,,, 21 L , { }pji ,,2,1 L ,

ri ,,2,1 L= , sujetas a la restriccin de que lk jj = si lk = . 2. Si rs < , entonces A tiene races p-simas que no son funciones de A . Estas

races forman familias parametrizadas 11))(,),(),(diag()(

2211

= XUJfJfJfXUUFrrjjjj L ,

ri

s pjp +1 , donde { }pji ,,2,1 L , ri ,,2,1 L= , siendo U una matriz no singular arbitraria que conmuta con ( )

rJJJ ,,,diag 21 L , y para cada j existen k y l ,

dependientes de j , de manera que lk = y lk jj . 2.2.2.5 Funcin Logaritmo

Los logaritmos de matrices aparecen en algunos campos de la ingeniera, como los relacionados con la teora de control. Por ejemplo, para un sistema fsico gobernado por la EDL

)()( tAxtx =& , 0)0( xx = , en la que nxnA es una matriz desconocida, es posible determinar esta matriz A a partir de n observaciones, nxxx ,,, 21 L , del vector de estados )(tx , producidas por n vectores de condiciones iniciales ([AlPr81], [SiSp76]). Puesto que la solucin de la ecuacin diferencial anterior es

0)( xetxAt= ,

particularizando esta expresin para 1=t y considerando como estados iniciales las columnas de la matriz identidad, se obtiene que

AeB = , y, por tanto, BA log= , siendo ],,,[ 21 nxxxB L= . El siguiente teorema caracteriza las condiciones de existencia del logaritmo de una matriz.

Teorema 2.7 ([HoJo91], pgina 475).

1. Si nxnA C es no singular, entonces existe al menos un matriz nxnX C que verifica Ae X = y es polinomial en A ; es decir, existe un polinomio )(zp de manera que )(ApX = .

2. Si nxnA C es singular, entonces no existe ninguna matriz nxnX C tal que Ae X = .

3. Si nxnA , entonces existe nxnX de manera que Ae X = si y solo si se cumplen las dos condiciones siguientes:


22

a. A es no singular. b. Si

ii

i

xnn

i

i

i

i

CJ

=

000100

000001

LL

MOOMMOL

,

es un bloque de Jordan de A , con i un valor propio real negativo de A , entonces A tiene un nmero par de bloques de Jordan de igual tamao in , incluido

iJ .

4. Si nxnA tiene algn valor propio real negativo, entonces ninguna solucin real de Ae X = puede ser polinomial en A o funcin matricial primaria de A . Como consecuencia de este teorema se tiene que si nxnA no tiene valores propios reales negativos, entonces tiene un logaritmo real; es decir, existe una matriz nxnL de manera que AeL = . Pueden existir diferentes matrices que proporcionen el logaritmo de una matriz, pero slo una de ellas tiene las partes imaginarias de sus valores propios en el intervalo [,] . Esta matriz se denomina logaritmo principal de A y se denota con Alog .

2.2.2.6 Funciones Seno y Coseno Las funciones matriciales trigonomtricas juegan un papel fundamental en los sistemas diferenciales lineales de segundo orden. Por ejemplo, el problema

022

=+ Axdt

xd , 0)0( xx = , '0)0(' xx = ,

con nxnA , tiene como solucin '0

10 )(sen)()cos()( xtAtAytAtx

+= . Problemas ms generales de este tipo, en los que aparece un trmino )(tf en la parte derecha de la ecuacin diferencial, proceden de la semidiscretizacin de la ecuacin de ondas y de los sistemas mecnicos sin amortiguamiento. En tales casos, las soluciones pueden expresarse en funcin de trminos que involucran senos y cosenos de matrices ([Serb79]).

Las definiciones ms usuales de la funciones seno y coseno de una matriz estn basadas en las series de Taylor

=

+

+= 012

)!12()1(sen

k

kk

kAA

y

=

=0

2

)!2()1(cos

k

kk

kAA .


23

2.2.3 Mtodos Numricos para el Clculo de Funciones de Matrices

2.2.3.1 Funcin Exponencial

2.2.3.1.1 Mtodos Basados en las Series de Taylor

Sea )(zf una funcin analtica definida sobre el espectro de nxnA C k

kk zczf

==

0)( .

Segn el Teorema 2.1, la matriz )(Af se puede hallar mediante la expresin

=

=0

)(k

kk AcAf .

El valor aproximado de )(Af se puede obtener truncando adecuadamente la serie anterior. Para ello se calculan los trminos de la serie hasta que se encuentra un nmero natural L , de manera que la representacin en coma flotante de la matriz LS sea igual a la representacin en coma flotante de 1+LS ; es decir, )()( 1+= LL SflSfl , siendo

=

=L

k

kkL AcS

0.

El valor aproximado de )(Af ser, por lo tanto, )( LSfl .

Este mtodo puede producir un resultado inexacto debido, fundamentalmente, a los errores de redondeo causados cuando se desprecian los trminos de la serie a partir de un cierto orden, y al problema de la cancelacin de dgitos significativos que se produce cuando se suman y restan nmeros del mismo orden de magnitud. Adems, a medida que A es mayor o la dispersin de los valores propios de la matriz A aumenta, se tiene que los errores de redondeo y los costes computacionales aumentan.

Se han diseado diversos algoritmos basados en las aproximaciones de Taylor ([PChK91], [GoVa96]), que intentan evitar esos problemas, haciendo uso de la identidad

( )mmAA ee /= . El mtodo de escalado y potenciacin consiste en seleccionar un valor m como potencia de 2, jm 2= , de manera que mAe / pueda calcularse con precisin y eficiencia, y entonces calcular ( )mmAe / mediante potenciacin repetida.

2.2.3.1.2 Mtodos Basados en los Aproximantes de Pad

Los aproximantes de Pad de orden ),( qp de zezf =)( son funciones racionales definidas como

)(/)()( zDzNzR pqpqpq = , donde


24

kp

kpq zkpkqp

pkqpzN = +

+=0 )!(!)!(

!)!()(

y

.)()!(!)!(

!)!()(0

kq

kpq zkqkqp

qkqpzD =

++=

En particular, )(0 zRp coincide con el polinomio de Taylor de grado p de la funcin ze .

Los aproximantes de Pad permiten calcular aproximadamente la exponencial de una matriz nxnA C mediante la expresin

[ ] [ ])()()( 1 ANADARe pqpqpqA = . El problema es que nicamente proporcionan buenas aproximaciones en un entorno del origen, tal como revela la igualdad

dueuuADAqp

ARe uAqppqqp

q

pqA )1(

1

0

11 )1()()!(

)1()( ++ ++= ([GoVa96], captulo 11).

Una manera de evitar el problema anterior consiste en utilizar el mtodo de escalado y potenciacin, eligiendo para ello el menor entero positivo j de manera que

1/||||


25

son necesarios para calcular la aproximacin de Pad de orden qp + , )(ARpq . Sin embargo, la misma cantidad de flops son necesarios para calcular la aproximacin de orden qpq +>2 , )(ARqq . La conclusin es anloga para qp > . Existen otros motivos para la utilizacin de aproximantes diagonales de Pad. Por ejemplo, si todos los valores propios de A estn en el semiplano 0)Re( suelen tener errores de redondeo ms elevados debido a problemas de cancelacin, mientras que con qp < se suelen producir mayores errores de redondeo debido al mal condicionamiento del denominador )(ADpq .

Existen ciertas aplicaciones donde la determinacin de p y q se basan en el comportamiento de

).(lim tARpqt

Si todos los valores propios de A estn en el semiplano complejo izquierdo abierto, entonces

0lim =At

te ,

y tambin

0)(lim =

tARpqt , si .pq > Cuando pq < (incluyendo el caso 0=q ) resulta que los aproximantes de Pad estn acotados para valores de t elevados. Si qp = entonces los aproximantes estn acotados cuando t tiende a infinito.

En [MoVa78] se proponen los valores ptimos de q ( qp = ) y j en las aproximaciones de Pad y Taylor, en funcin de la norma de la matriz A . Esos valores estn representados en la tabla que se presenta a continuacin.

Tabla 2.1: Parmetros ptimos de escalado y potenciacin, en los aproximaciones de Pad y Taylor.

(p,q) =10-3 =10-6 =10-9 =10-12 =10-15 || A ||=10-2

(1,0) (3,0)

(2,0) (4,0)

(3,0) (4,2)

(4,0) (4,4)

(4,0) (5,4)

|| A ||=10-1(2,1) (5,1)

(3,1) (7,1)

(4,1) (6,3)

(5,1) (8,3)

(6,1) (7,5)

|| A ||=100 (2,5) (4,5)

(3,5) (6,5)

(4,5) (8,5)

(5,5) (7,7)

(6,5) (9,7)

|| A ||=101 (2,8) (4,8)

(3,8) (5,9)

(4,8) (7,9)

(5,8) (9,9)

(6,8) (10,10)

|| A ||=102 (2,11) (5,11)

(3,11) (7,11)

(4,11) (6,13)

(5,11) (8,13)

(6,11) (8,14)

|| A ||=103 (1,0) (3,0)

(2,0) (4,0)

(3,0) (4,2)

(4,0) (4,4)

(4,0) (5,4)


26

Dada un pareja de valores y |||| A , entonces el par de arriba muestra los valores ),( jq ptimos asociados a la aproximacin de Pad

( )[ ] jjqq AR 22/ , y el de abajo especifica la eleccin ms eficiente de ),( jk correspondiente a la aproximacin de Taylor

( )[ ] jjk AT 22/ . A continuacin se presenta un algoritmo ([GoVa96]) que calcula la exponencial de una matriz mediante aproximantes diagonales de Pad.

),( AdgeexpF = . Entradas: Matriz nxnA , tolerancia + . Salida: Matriz nxnEAeF = + de manera que |||||||| AE . 1 ))||||(logfloor1,0max( 2 += Aj 2 jAA 2/= 3 Calcular q de manera que sea el menor entero positivo tal que

+++=+

)!1()!(!!2),( )(3

qpqpqpqp qp

4 nID = ; nIN = ; nIX = ; 1=c 5 Para qk :1=

5.1 kkq

kqcc)12()1(

++=

5.2 AXX = ; cXNN += ; cXDD k)1(+= 6 Para jk :1=

6.1 2FF = Algoritmo 2.1: Calcula la exponencial de una matriz mediante aproximantes

diagonales de Pad.

El coste del algoritmo anterior es 3)3/1(2 njq ++ flops. En el captulo 11 de [GoVa96] se seala la necesidad de utilizar tcnicas especiales, basadas en el mtodo de Horner y variantes, que permiten reducir el coste computacional de este mtodo. Si, por ejemplo, 8=q y se define )(ADD qq= y

)(ANN qq= , entonces AVUANqq +=)( y AVUADqq =)( ,

donde 44

82

642

20 )( AAcAcIcAcIcU nn ++++= , y

4275

231 )( AAcIcAcIcV nn +++= ,


27

siendo ic , 80 i , los coeficientes del polinomio N . Recientemente, Higham ([High04]) ha realizado una revisin del clculo de exponenciales de matrices mediante aproximantes de Pad. En ese artculo Higham argumenta y justifica que la mejor eleccin del valor de los aproximantes de Pad es el de 13== qp , en lugar de los valores de 6 y 8 que otros autores anteriormente haban sealado. Adems, para reducir el coste computacional, Higham utiliza tcnicas de anidamiento para el clculo de las matrices U y V ([PaSt73]).

2.2.3.1.3 Mtodos Basados en Integracin Numrica

Como Ate y 0xeAt son soluciones de la EDL que tiene a la matriz A como matriz de

coeficientes, es natural considerar mtodos basados en la integracin numrica. Los algoritmos de este tipo pueden tener un control del tamao del paso automtico, variando automticamente el orden de la aproximacin. Los mtodos basados en frmulas de un solo paso, frmulas multipaso y frmulas multipaso implcito (apartado 2.3.2) presentan ciertas ventajas. Son fciles de utilizar para el clculo de Ate , sin embargo, requieren un alto coste computacional.

Puesto que la ecuacin de estados de un sistema dinmico lineal continuo es un caso particular de la EDO no lineal,

0)0( )),(),(,()(' xxtutxtftx == , su solucin puede hallarse mediante mtodos de integracin numrica para este tipo de ecuaciones.

Una desventaja de esta aproximacin es la gran cantidad de operaciones necesarias, pues no hacen uso de la naturaleza especial del problema. Sin embargo, la implementacin de un algoritmo que resuelva una EDO es necesaria en el caso de ecuaciones de estado o de problemas control con coeficientes variables. Los mtodos numricos para resolver la EDO

0)0( )),(,()(' xxtxtftx == , son discretos; es decir, son mtodos que calculan una secuencia de aproximaciones

)( kk txx = para un conjunto de puntos kkk ttt +=+1 , 1,,1,0 = nk L ,

en donde el tamao de paso kt puede variar. En general, la aproximacin 1+kx se calcula a partir de los valores previos 01 ,,, xxx kk L . Los errores en la solucin numrica de una EDO son el resultado del proceso de discretizacin (llamado error de truncamiento) y de los errores de redondeo. El error de discretizacin local es el error producido en un paso dado, considerando que son exactos los valores previos y que no hay errores de redondeo en los clculos. Este error se puede determinar de la siguiente forma. Sea la funcin )(tyk que satisface

kkkkk xtytytfty == )(,))(,()(' . Entonces el error local kd est dado por

)( 11 ++ = kkkk tyxd .


28

De esta forma el error local es la diferencia entre la aproximacin calculada y la solucin terica definida por la misma condicin inicial en el instante 1+kt .

El error de discretizacin global ke en el paso k es la diferencia entre la aproximacin calculada kx (sin tener en cuenta los errores de redondeo) y la solucin exacta )( ktx determinada por la condicin inicial 0x , es decir,

)( kkk txxe = . Claramente, el error global depende de todos los errores locales producidos en los pasos previos.

Prcticamente, todos los cdigos actuales que resuelven EDOs controlan el error local en cada instante, y no intentan controlar directamente el error global. Sin embargo, las propiedades de los errores de redondeo no son estudiadas en profundidad, en parte porque la exactitud requerida en el algoritmo de resolucin de la EDO es menor que la precisin de la mquina.

Mtodos de Propsito General Muchas libreras que resuelven problemas de valores iniciales en EDOs, permiten calcular Ate , para diferentes valores de t . El problema de utilizar estas libreras es que no se aprovecha la linealidad de la ecuacin asociada al problema del clculo de

Ate , y que los coeficientes que aparecen en ella son constantes.

Mtodos de Paso nico Dos tcnicas clsicas para la resolucin de ecuaciones diferenciales son los mtodos de Taylor y Runge-Kutta de cuarto orden. Si se considera un tamao de paso t constante, entonces para la aproximacin de Taylor de orden cuatro, se obtienen las ecuaciones

iii xtATxAttAIx )(!4

... 44

4

1 =

+++=+ ,

y para el mtodo de Runge-Kutta de orden cuatro

43211 61

31

31

61 kkkkxx ii ++++=+ ,

siendo

)2/( , 121 kxtAktAxk ii +== , ( )3423 ),2/( kxtAkkxtAk ii +=+= .

En este caso, se puede comprobar que los dos mtodos produciran idnticos resultados, si no fuese por los errores de redondeo. Como el tamao del paso es fijo, la matriz

)(4 tAT nicamente se calcula una vez. En tal caso, 1+ix se puede obtener a partir de ix con solo realizar un producto matriz-vector. El mtodo de Runge-Kutta requiere cuatro de estos productos por paso.

Considrese )(tx para un valor particular de t , por ejemplo 1=t .

tesis funciones matrices.pdf

Documents