Matrices estructuradas y alta precisión relativa

Laburpena

Esta memoria se enmarca, dentro del Algebra Lineal Numérica, en el campo de estudio de métodos numéricos adaptados a clases de matrices con estructura especial, que es un campo que muestra una intensa y creciente actividad investigadora. Concretamente, considerará clases de matrices para las que se encontrarán métodos numéricos cuyo cálculo se podrá llevar a cabo con alta precisión relativa. Conseguir cálculos precisos es una propiedad muy deseable para cualquier método numérico. El ideal es conseguir alta precisión relativa (independientemente del condicionamiento del problema). Sin embargo, hasta ahora sólo se ha podido garantizar dicha alta precisión relativa en un número muy reducido de métodos numéricos para una lista muy reducida de problemas matemáticos. En particular, en métodos aplicados a matrices con una estructura especial. Hasta ahora, las principales clases de matrices para las que se han podido desarrollar métodos con alta precisión relativa han sido clases de matrices cuya estructura tiene alguna relación con la positividad o bien con la dominancia diagonal. Las matrices no negativas han aparecido con gran frecuencia en aplicaciones a los campos más diversos, como la Física, Química, Biología, Ingeniería, Economía y Ciencias Sociales. Además, el bien conocido resultado sobre la positividad de su valor propio dominante y vector propio asociado (Teorema de Perron-Frobenius) ha sido un instrumento clave en la modelización matemática de muchas situaciones reales. En general, las clases de matrices relacionadas con la positividad se han mostrado muy fructíferas en las aplicaciones. En particular, en los problemas de aproximación, representación aproximada de curvas y superficies y diseño geométrico asistido por ordenador es frecuente que aparezcan matrices con una estructura especial relacionada con la positividad. Por ejemplo, es muy frecuente que aparezcan matrices no negativas e incluso totalmente positivas (es decir, con todos sus menores no negativos). En los últimos años, se han visto las grandes ventajas que conlleva encontrar algoritmos adaptados a la estructura especial de estas matrices. Las matrices totalmente positivas están dentro de la clase más amplia de las matrices signo regulares, que es una de las clases de matrices a considerar en la tesis. Una matriz de orden n es signo regular si todos sus menores de orden k, para cada k=1,... ,n, tienen el mismo signo o son cero. El interés de las matrices signo regulares no singulares en muchas aplicaciones es debido a su caracterización como aplicaciones lineales que disminuyen la variación de signo. Se pueden encontrar muchas aplicaciones de estas transformaciones en [4], [15], y [19]. Uno de los logros de la memoria ha sido la caracterización de las matrices signo regulares no singulares Jacobi (o tridiagonales). En contraste con los abundantes resultados publicados sobre matrices totalmente positivas (véase, por ejemplo, los libros [10], [12], [15] y [21] o los surveys que aparecen en [2], [8], [9], [11] y [13]), son mucho más escasos los resultados publicados en el caso de las signo regulares. Una de las razones que podría explicar esta diferencia es el papel que ha jugado en los últimos años la eliminación de Neville (véase [14]) en la teoría de la Total Positividad. Este procedimiento de eliminación es muy conveniente cuando se trata con matrices totalmente positivas y también preserva su estructura. Además, los multiplicadores de la eliminación de Neville determinan la descomposición de matrices totalmente positivas no singulares en producto de bidiagonales y son parámetros naturales de las matrices totalmente positivas de cara a obtener algoritmos con alta precisión relativa. De hecho, en [16] se probó que si se conocen dichos multiplicadores y los pivotes diagonales (que determinan la descomposición bidiagonal de la matriz) con alta precisión relativa, entonces se pueden calcular sus inversas, valores propios o valores singulares con alta precisión relativa. Esta idea se ha aplicado a garantizar cálculos con alta precisión relativa en subclases de matrices totalmente positivas como las de Vandermonde [6], las de Bernstein-Vandemonde [17], las de Pascal [1] o matrices de colocación de bases racionales [5]. En esta memoria presentamos una clase de matrices, llamadas SBD, que incluyen a las totalmente positivas y a sus inversas. Veremos que para esta clase de matrices también podremos obtener algoritmos con alta precisión relativa para calcular sus inversas, valores propios o valores singulares a partir de la descomposición bidiagonal. Otra de las clases de matrices relacionada con algoritmos de alta precisión relativa es la clase de las M-matrices. Recordemos que las M-matrices (en el caso no singular) son matrices que tienen elementos diagonales positivos, elementos extradiagonales no positivos y cuya inversa es no negativa. Constituyen una clase de matrices que ha dado lugar a importantes aplicaciones en Análisis Numérico, en programación lineal, en sistemas dinámicos y en economía (véase [3]). Una descomposición reveladora del rango de una matriz A es una factorización A=XDY^T, donde D es diagonal no singular y X,Y son bien condicionadas. En [6] se probó que si se conoce una descomposición reveladora del rango con alta precisión relativa, también se pueden conocer los valores singulares con alta precisión relativa. Métodos para el cálculo de una descomposición reveladora del rango de M-matrices diagonal dominantes se han obtenido en [7] y [20], usando ambos eliminación gaussiana, pero [7] con la estrategia de pivotaje completo y [20] con la estrategia introducida en [18]. En el caso de estas matrices, los parámetros naturales que se suponen conocidos de antemano para poder garantizar alta precisión relativa son los elementos extradiagonales y las sumas de filas. Aquí veremos que un método que se puede implementar mejorando las propiedades de [7] y [20]. Además lo extendemos a una clase de Z-matrices (recordemos que una matriz cuadrada es una Z-matriz si sus elementos extradiagonales son no positivos) que llamamos cuasi-diagonal dominantes. En el Capítulo 1 introducimos conceptos y notaciones básicos así como resultados auxiliares. Muchas de las clases de matrices conocidas mencionadas en la memoria habrán sido presentadas en este capítulo, así como las descomposiciones matriciales usadas más importantes. También se introducirán los algoritmos de corte de esquinas, de gran importancia en diseño geométrico asistido por ordenador (CAGD) y para los que obtendremos una aplicación en el Capítulo 3. Finalmente, introducimos el concepto de alta precisión relativa y recordamos que podremos asegurar que un algoritmo cumplirá dicha propiedad si no usa restas (salvo en los datos iniciales). El Capítulo 2 está dedicado a las matrices signo regulares no singulares de Jacobi y a alguna extensión de las mismas. Por un lado, se caracterizan de diversas maneras y, por otro lado, se ve su relación con las matrices diagonal dominantes y otras clases de matrices. El Capítulo 3 se dedica a las matrices SBD, que son introducidas en el mismo, y a otras clases de matrices relacionadas. Realizamos un estudio sistemático de clases de matrices que admitan descomposiciones bidiagonales con objeto de tratar de adaptarles las técnicas que han permitidos la obtención de algoritmos con alta precisión relativa en el caso de matrices totalmente positivas. Para ello fue conveniente explorar condiciones de signo en las descomposiciones bidiagonales. Para las clases de matrices resultantes de nuestro estudio, las matrices SBD, se realizó también un análisis matricial clásico, estudiando los signos de sus menores o su comportamiento con respecto a los complementos de Schur o al producto de Hadamard, comparando dicho comportamiento con el de las matrices totalmente positivas, como se puede ver en este capítulo. Se prueba la estabilidad backward (o regresiva) que tiene la eliminación Gaussiana sin realizar pivotaje en las matrices SBD. Se extienden a clases de matrices más amplias desigualdades válidas para las matrices totalmente positivas y relacionadas con el mínimo valor propio, el complemento de Schur y el producto de Hadamard. También se presenta una aplicación a diseño asistido por ordenador. En el Capítulo 4 encontramos para la clase de las M-matrices no singulares diagonal dominantes una implementación de su factorización LDU (con una adecuada estrategia de pivotaje) que es más económica que las de [7] y [20]. Así, se podrá aplicar con ventaja en el cálculo de valores singulares con alta precisión relativa. También extendemos y adaptamos las técnicas que han permitido la obtención de algoritmos con alta precisión relativa para M-matrices no singulares diagonal dominantes a clases de matrices más generales u otras clases de matrices relacionadas. En particular, a las Z-matrices cuasi-diagonal dominantes. Finalmente, se presentarán otras clases de matrices relacionadas y se estudiarán algunas de sus propiedades. Terminamos la memoria con un apéndice que presenta una aplicación informática que puede resultar muy útil cuando se quieren comparar experimentos numéricos obtenidos con dos entornos distintos de cálculo matemático, como les ocurre a los experimentos numéricos presentados en esta memoria. Bibliografía [1] P. Alonso, J. Delgado, R. Gallego, and J.M. Peña, Conditioning and accurate computations with Pascal matrices, J. Comput. Appl. Math. 252 (2013), 21-26. [2] T. Ando, Totally positive matrices, Linear Algebra Appl. 90 (1987), 165-219. [3] A. Berman and R.J. Plemmons, Nonnegative matrices in the mathematical sciences, Classics in Applied Mathematics, 9, SIAM, Philadelphia, 1994. [4] L.D. Brown, I.M. Johnstone, and K.B. MacGibbon, Variation diminishing transformations: a direct approach to total positivity and its statistical applications, J. Amer. Statist. Assoc. 76 (1981), 824-832. [5] J. Delgado and J.M. Peña, Accurate computations with collocation matrices of rational bases, Appl. Math. Comput. 219 (2013), 4354-4364. [6] J. Demmel, M. Gu, S. Eisenstat, I. Slapnicar, K. Veselic, and Z. Drmac, Computing the singular value decomposition with high relative accuracy, Linear Algebra Appl. 299 (1999), 21-80. [7] J. Demmel and P. Koev, Accurate SVDs of weakly diagonally dominant M-matrices, Numer. Math. 98 (2004), 99-104. [8] J. Demmel and P. Koev, The accurate and efficient solution of a totally positive generalized Vandermonde linear system, SIAM J. Matrix Anal. Appl. 27 (2005), 142-152. [9] S.M. Fallat, Bidiagonal factorizations of totally nonnegative matrices, Amer. Math. Monthly 108 (2001), 697-712. [10] S.M. Fallat and C.R. Johnson, Totally Nonnegative Matrices, Princeton University Press, Princeton and Oxford, 2011. [11] S. Fomin and A. Zelevinsky, Total positivity: tests and parametrizations, Math. Intelligencer 22 (2000), 23-33. [12] F.P. Gantmacher and M.G. Krein, Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems, revised ed., AMS Chelsea, Providence, RI, 2002. [13] M. Gasca and C.A. Micchelli (eds.), Total positivity and its applications, Proceedings of the meeting held in Jaca, September 26-30, 1994. Mathematics and its Applications, 359. Kluwer Academic Publishers Group, Dordrecht, 1996. [14] M. Gasca and J.M. Peña, Total positivity and Neville elimination, Linear Algebra Appl. 165 (1992), 25-44. [15] S. Karlin, Total positivity, Vol. I, Stanford University Press, Stanford, 1968. [16] P. Koev, Accurate computations with totally nonnegative matrices, SIAM J. Matrix Anal. Appl. 29 (2007), 731-751. [17] A. Marco and J.J. Martínez, A fast and accurate algorithm for solving Bernstein-Vandermonde linear systems, Linear Algebra Appl. 422 (2007), 616-628. [18] J.M. Peña, Pivoting strategies leading to diagonal dominance by rows, Numer. Math. 81 (1998), 293-304. [19] J.M. Peña (ed.), Shape Preserving Representations in Computer Aided-Geometric Design, Nova Science Publishers, Commack (NY), 1999. [20] J.M. Peña, LDU decompositions with L and U well conditioned, Electron. Trans. Numer. Anal. 18 (2004), 198-208. [21] A. Pinkus, Totally positive matrices, Cambridge Tracts in Mathematics, Num. 181, Cambridge University Press, 2010.