Download Sesión especial 1 Álgebra lineal y análisis matricial: avances

Sesión especial 1
Álgebra lineal y análisis matricial: avances
recientes en teoría y computación
Resúmenes de las conferencias
Congreso Bienal
de la
Real Sociedad Matemática Española
Zaragoza, 30 de enero - 3 de febrero de 2017
Versión actualizada el 20 de enero de 2017
Congreso Bienal de la Real Sociedad Matemática Española (Zaragoza, 2017)
3
Sesión especial 1
Álgebra lineal y análisis matricial: avances
recientes en teoría y computación
Programa
Jueves, 2 de febrero
17:00 - 17:30 José Mas (Universitat Politècnica de València), Precondicionadores para resolver problemas de
mínimos cuadrados mediante métodos iterativos.
17:30 - 18:00 José-Javier Martínez (Universidad de Alcalá), Matrices de Jacobi totalmente positivas y cálculo
preciso de raíces de polinomios ortogonales.
18:00 - 18:30 Ion Zaballa (Universidad del País Vasco / Euskal Herriko Unibertsitatea), Un procedimiento
para reducir matrices polinomiales a formas simples de forma estable.
18:30 - 19:00 Miguel V. Carriegos (Universidad de León), Matrices sobre anillos conmutativos y sistemas
lineales.
19:00 - 19:30 M.a Isabel García Planas (Universitat Politècnica de Catalunya), Controlabilidad de sistemas
líder-seguidores.
Viernes, 3 de febrero
9:00 - 9:30 Rafael Cantó Colomina (Universitat Politècnica de València), Aplicaciones de un teorema de
Brauer.
9:30 - 10:00 Laureano González Vega (Universidad de Cantabria), Subresultantes para polinomios «à la
Lagrange».
10:00 - 10:30 Pedro Alonso (Universidad de Oviedo), Matrices casi estrictamente signo regulares: caracterizaciones, factorizaciones y análisis de error regresivo.
10:30 - 11:00 Carlos Beltrán Álvarez (Universidad de Cantabria), La complejidad teórica del cálculo aproximado de valores y vectores propios.
11:30 - 12:00 Juan Manuel Peña (Universidad de Zaragoza), Cálculos precisos con subclases de matrices
totalmente positivas.
12:00 - 12:30 Josep Ferrer (Universitat Politècnica de Catalunya), Diagrama de bifurcación de sistemas dinámicos lineales bimodales conteniendo una silla.
—– • —–
Precondicionadores para resolver problemas
de mínimos cuadrados mediante métodos iterativos
José Mas
Instituto de Matemática Multidisciplinar, Universitat Politècnica de València
[email protected]
Financiado en parte por el Ministerio de Economía y Competitividad a través de la Red de Excelencia ALAMA
MTM2015-68805-REDT.
4
S1. Álgebra lineal y análisis matricial: avances recientes en teoría y computación
Resumen
Si el número de ecuaciones y/o incógnitas es muy grande y la matriz es vacía, se puede obtener la solución de mínimos
cuadrados de un sistema de ecuaciones lineales con más ecuaciones que incógnitas, o recíprocamente con más incógnitas
que ecuaciones, utilizando métodos iterativos, entre ellos variantes adaptadas del método del gradiente conjugado aplicado
a las ecuaciones normales, como el algoritmo CGLS (ver [1]).
Para acelerar la convergencia del método se pueden utilizar precondicionadores, entre ellos factorizaciones incompletas
de Cholesky, pero como las ecuaciones normales suelen ser mucho más densas que la matriz original es conveniente adaptar
los algoritmos para obtener precondicionadores vacíos que se puedan calcular sin problemas de estabilidad y que sean
eficientes al ser aplicados al sistema resultante.
Presentamos un algoritmo que permite obtener una factorización incompleta de Cholesky con estas características
(ver [2]) así como nuevas ideas que combinan este algoritmo o algoritmos similares con otros que buscan representar
ciertos bloques de la matriz que producirían un llenado excesivo mediante aproximaciones de rango bajo (o de menor
rango) obtenidas con técnicas de muestreo, ver por ejemplo [3].
Referencias
[1] Å. Björck, Numerical methods for least squares problems, SIAM, Philadelphia (1996).
[2] R. Bru, J. Marín, J. Mas y M. Tůma, Preconditioned iterative methods for solving linear least squares
problems, SIAM J. Sci. Comput. 36 (4) (2014), A2002–A2022.
[3] V. Rokhlin y M. Tygert, A fast randomized algorithm for overdetermined linear least-squares regression,
Proc. Natl. Acad. Sci. USA 105 (36) (2008), 13212–13217.
—– • —–
Matrices de Jacobi totalmente positivas
y cálculo preciso de raíces de polinomios ortogonales
José-Javier Martínez
Departamento de Física y Matemáticas, Universidad de Alcalá
[email protected]
Trabajo en colaboración con Ana Marco. Financiado en parte por el Ministerio de Economía y Competitividad a través de la Red
de Excelencia ALAMA MTM2015-68805-REDT.
Resumen
Como W. Gautschi recordaba en [2], la integración respecto a una cierta medida dλ sobre la recta real es ciertamente
un tema pertenenciente al análisis y, siguiendo a Gauss, para calcular de manera aproximada las integrales definidas uno
llega a los polinomios ortogonales relativos a dicha medida dλ. La relación con el álgebra lineal reside en el hecho de que
los ceros de esos polinomios ortogonales son precisamente los valores propios de las correspondientes matrices de Jacobi.
Una completa presentación de este tema puede verse en el ya clásico libro de W. Gautschi [3], centrado en los métodos
constructivos (incluyendo códigos en Matlab) relacionados con los polinomios ortogonales.
Un aspecto nuevo en este contexto es observar que una matriz de Jacobi, además de ser tridiagonal y simétrica, puede
poseer alguna propiedad adicional relevante. Desde el punto de vista del cálculo preciso de los ceros de los polinomios
ortogonales una propiedad importante (que se verifica para algunas familias de polinomios ortogonales) es la positividad
total [1].
El objetivo de este trabajo es mostrar cómo la positividad total de las matrices de Jacobi de ciertas familias de
polinomios ortogonales ayuda a calcular de manera más precisa, haciendo uso de algoritmos desarrollados por P. Koev
[4], los ceros de dichos polinomios.
Referencias
[1] A. Barreras y J. M. Peña, Characterizations of Jacobi sign regular matrices, Linear Algebra Appl. 436 (2012),
381–388.
[2] W. Gautschi, The interplay between classical analysis and (numerical) linear algebra - A tribute to Gene H.
Golub, Electron. Trans. Numer. Anal. 13 (2002), 119–147.
Congreso Bienal de la Real Sociedad Matemática Española (Zaragoza, 2017)
5
[3] W. Gautschi, Orthogonal Polynomials. Computation and Approximation, Oxford University Press, Oxford,
2004.
[4] P. Koev, Accurate eigenvalues and SVDs of totally nonnegative matrices, SIAM J. Matrix Anal. Appl. 27
(2005), 1–23.
—– • —–
Un procedimiento para reducir matrices polinomiales
a formas simples de forma estable
Ion Zaballa
Departamento de Matemática Aplicada y EIO, Universidad del País Vasco (UPV/EHU)
[email protected]
En colaboración con Y. Nakatsukasa, L. Taslaman, F. Tisseur. Financiado en parte por el Ministerio de Economía y
Competitividad a través de la Red de Excelencia ALAMA MTM2015-68805-REDT.
Resumen
La matrices cuadradas se pueden reducir a formas simples por medio de transformaciones de semejanza. Es decir,
a matrices en forma diagonal (cuando la matriz es no defectuosa), triangular (forma de Schur) o Hessenberg. Si en vez
de semejanza se permite el uso de transformaciones de equivalencia estricta, reducciones similares son posibles para
haces de matrices. En ambos casos, matrices o haces, hay algoritmos diseñados para obtener las correspondientes formas
reducidas. Para matrices polinomiales, sin embargo, la equivalencia estricta no posibilita, en general, la reducción de
la matriz original a otra con el mismo grado y una de las formas mencionadas más arriba. En este trabajo se propone
un procedimiento práctico para reducir las matrices polinomiales con coeficiente principal no singular a formas simples
(diagonal, triangular o Hessenberg) con la misma estructura de valores propios que las originales cuando ello sea posible.
—– • —–
Matrices sobre anillos conmutativos y sistemas lineales
Miguel V. Carriegos
Departamento de Matemáticas, Universidad de León
[email protected]
Financiado en parte por el Ministerio de Economía y Competitividad a través de la Red de Excelencia ALAMA
MTM2015-68805-REDT.
Resumen
Presentamos algunos resultados sobre pares de matrices o sistemas lineales de la forma (A, B) ∈ Rn×n × Rn×m
donde las matrices tienen elementos en un anillo conmutativo R. Se presentan los invariantes de los sistemas lineales y se
prueba que, bajo la hipótesis de invariantes proyectivos, dos sistemas lineales son equivalentes si y solo si sus invariantes
son isomorfos [3]. Como consecuencia del resultado anterior se tiene una enumeración de clases de equivalencia de
sistemas sobre un anillo conmutativo arbitrario. Además se tiene una vía para estudiar el problema de forma algebraica
enumerando las clases de isomorfía de módulos proyectivos finitamente generados. También proporcionamos cálculos
concretos en algunas clases interesantes de anillos conmutativos: anillos proyectivamente triviales, anillos regulares de
von Neumann y dominios de Dedekind, así como anillos producto [4].
Para concluir, se muestra cómo algunos números combinatorios relacionados con la teoría de particiones surgen de
manera natural de este estudio [2].
Referencias
[1] I. Baragaña, V. Fernández e I. Zaballa, Hermite indices and the action of the feedback group, Linear Algebra
Appl. 401 (2005), 401–427.
[2] N. Benyahia Tani y S. Bouroubi, Enumeration of the partitions of an integer into parts of a specified number
of different sizes and especially two sizes, J. Integer Seq. 14 (2011), 11.3.6.
6
S1. Álgebra lineal y análisis matricial: avances recientes en teoría y computación
[3] M. V. Carriegos, Enumeration of classes of linear systems via equations and via partitions in an ordered
abelian monoid, Linear Algebra Appl. 438 (2013), 1132–1148.
[4] M. V. Carriegos y N. DeCastro-García, Partitions of elements in a monoid and its applications to systems
theory, Linear Algebra Appl. 494 (2016), 161–170.
[5] M. V. Carriegos y A. L. Muñoz-Castañeda, On the K-theory of feedback actions on linear control systems,
Linear Algebra Appl. 440 (2014), 233–242.
—– • —–
Controlabilidad de sistemas líder-seguidores
M.a Isabel García-Planasa y Sonia Tarragonab
a
Dept. de Matemàtiques, Universitat Politècnica de Catalunya
b
Dept. de Matemáticas, Universidad de León
a
[email protected], b [email protected]
Financiado en parte por el Ministerio de Economía y Competitividad a través de la Red de Excelencia ALAMA
MTM2015-68805-REDT.
Resumen
Durante los últimos años, los sistemas multiagentes dinámicos han sido ampliamente estudiados y esto es debido a que
los multiagentes aparecen en diferentes áreas como por ejemplo en el problema de consenso de las redes de comunicación,
o de control de formación de robots móviles. Mayoritariamente, el problema de consenso ha sido estudiado desde el
punto de vista de la estabilidad. Sin embargo, recientemente se ha visto impulsado el tratamiento de los problemas de
controlabilidad. El estudio de la capacidad de control está motivado por el hecho de que la arquitectura de la red de
comunicación de sistemas multiagente en ingeniería es generalmente ajustable. Por lo tanto, es significativo analizar cómo
mejorar la controlabilidad de un sistema multiagente. En este trabajo consideramos sistemas multiagente que consisten
en k + 1 agentes con la dinámica ẋi = Ai xi + bi ui , i = 0, 1, . . . , k en que el primer agente toma el papel de líder y por
tanto su movimiento es independiente del movimiento de los otros agentes, y gobierna el movimiento de los seguidores.
Referencias
[1] M. I. García-Planas, Obtaining consensus of multi-agent linear dynamic systems, Advances in Applied and
Pure Mathematics, 91–95, WSEAS Press, 2014.
[2] A. Jadbabaie, J. Lin y A. S. Morse, Coordination of groups of mobile autonomous agents using nearest
neighbor rules, IEEE Trans. Automat. Control 48, (2007), 943–948.
[3] W. Ni y D. Cheng, Leader-following consensus of multi-agent systems under fixed switching topologies,
Systems Control Lett. 59, (2010), 209–217.
[4] R. O. Saber y R. M. Murray, Consensus problems in networks of agents with switching topology and timedelays, IEEE Trans. Automat. Control 49 (9) (2004), 1520–1533.
—– • —–
Aplicaciones de un teorema de Brauer
Rafael Cantó Colomina
Departamento de Matemática Aplicada, Instituto Universitario de Matemática Multidisciplinar, Universitat Politècnica
de València
[email protected]
Trabajo en colaboración con Rafael Bru ([email protected]) y Ana M. Urbano ([email protected]). La investigación ha sido
financiada parcialmente por el Ministerio de Economía y Competitividad a través del proyecto MTM2013-43678-P y a través de la
Red de Excelencia ALAMA MTM2015-68805-REDT.
Congreso Bienal de la Real Sociedad Matemática Española (Zaragoza, 2017)
7
Resumen
Dada una matriz cuadrada A, en un teorema de Brauer [1] se demuestra cómo modificar un valor propio simple de
A mediante una perturbación de rango uno sin cambiar el resto de sus valores propios. Diferentes resultados se pueden
considerar como aplicaciones del citado teorema como el estudio de la estabilidad de los sistemas lineales de control,
incluyendo el caso de los sistemas no controlables. Así como las técnicas de deflación de Wielandt y de Hotelling. En
1955, Perfect publicó una extensión del resultado de Brauer, el teorema de Rado, que muestra cómo modificar en solo
una etapa, r valores propios de A sin cambiar ninguno de los n − r valores propios restantes. Como consecuencia de este
resultado son los métodos de deflación por bloques y el problema de asignación de polos para sistemas lineales de control
invariantes de múltiple entrada y múltiple salida.
A continuación se obtienen relaciones entre las estructuras de Jordan de A y de la matriz actualizada mediante una
perturbación de rango uno, A + vi q ∗ , siendo vi un vector propio de A asociado al valor propio λi y q un vector arbitrario.
Se caracterizan las cadenas de Jordan de la matriz A + vi q ∗ a partir de las cadenas de Jordan de A.
Por último se introduce un procedimiento para reducir el número de condición si de un valor propio simple λi de
A. Con este proceso se obtiene una matriz actualizada, A + vi q ∗ , que es semejante a la matriz A y con el número de
condición del valor propio λi igual a 1, mientras que el resto de números de condición asociados a los valores propios
de A + vi q ∗ son menores o iguales que los correspondientes números de condición asociados a los valores propios de la
matriz inicial A.
Referencias
[1] A. Brauer, Limits for the characteristic roots of matrices IV: applications to stochastic matrices, Duke Math.
J. 19 (1952), 75–91.
—– • —–
Subresultantes para polinomios «à la Lagrange»
Laureano González-Vega
Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria
[email protected]
Parcialmente subvencionado por el Ministerio de Economía y Competitividad y por el European Regional Development Fund
(ERDF) mediante el proyecto MTM2014-54141-P y a través de la Red de Excelencia ALAMA MTM2015-68805-REDT.
Resumen
Las subresultantes permiten calcular el máximo común divisor de dos polinomios mediante la manipulación, libre de
fracciones, de las matrices de Sylvester. Existen fórmulas que muestran la relación que existe entre las subresultantes
de dos polinomios y sus raíces que se remontan a J. J. Sylvester ([3]). En [1] se introducen una serie de fórmulas que
presentan a las subresultantes de dos polinomios en función de la evaluación de estos en un conjunto cualquiera de
nodos pero que implican un número exponencial de sumandos. Mostraremos cómo evitar este problema y usar estas
fórmulas para calcular subresultantes de polinomios fáciles de evaluar y difíciles de desarrollar (esto es, presentados «à
la Lagrange»). Esta situación aparece en el contexto del álgebra polinomial por valores: así presentaremos, tal y como se
indica en [2, 4], cómo las matrices en estas fórmulas permiten transformar problemas de intersección en diseño geométrico
asistido por ordenador a cuestiones de álgebra lineal numérica (cálculo de la SVD y de valores propios generalizados).
Referencias
[1] F. Apery, J. P. Jouanolou, Élimination. Le cas d’une variable, Collection Methodes, Hermann, 2006.
[2] R. M. Corless, G. M. Diaz-Toca, M. Fioravanti, L. Gonzalez-Vega, I. F. Rua y A. Shakoori, Computing the
topology of a real algebraic plane curve whose defining equations are available only «by values», Comput.
Aided Geom. Design 30 (2013), 675–706.
[3] C. D’Andrea, H. Hong, T. Krick y A. Szanto, Sylvester’s double sums: The general case, J. Symbolic Comput.
44 (2009), 1164–1175.
[4] G. M. Diaz-Toca, M. Fioravanti, L. Gonzalez-Vega y A. Shakoori, Using implicit equations of parametric
curves and surfaces without computing them: polynomial algebra by values, Comput. Aided Geom. Design
30 (2013), 116–139.
8
S1. Álgebra lineal y análisis matricial: avances recientes en teoría y computación
—– • —–
Matrices casi estrictamente signo regulares: caracterizaciones,
factorizaciones y análisis de error regresivo
Pedro Alonso,a Juan Manuel Peñab y María Luisa Serranoa
a
b
Departamento de Matemáticas, Universidad de Oviedo
Departamento de Matemática Aplicada, Universidad de Zaragoza
[email protected], [email protected], [email protected]
Financiado en parte por el Ministerio de Economía y Competitividad a través de la Red de Excelencia ALAMA
MTM2015-68805-REDT.
Resumen
Las matrices signo regulares (SR, en inglés), matrices donde todos sus menores de orden k, para cada k = 1, . . . , n,
tienen el mismo signo o son cero, surgen de forma natural en muchas aplicaciones de las matemáticas, la estadística, la
economía o el diseño geométrico asistido por ordenador, entre otras (ver [1] y [4]). Si todos los menores de la matriz A
son no negativos, entonces se dice que A es totalmente positiva (TP). Una subclase de las matrices TP, con importantes
aplicaciones, la forman las matrices casi estrictamente totalmente positivas (ASTP), matrices TP donde los menores son
positivos si y solo si todos sus elementos diagonales son no nulos.
Una matriz SR es casi estrictamente signo regular (ASSR) si todos sus menores no triviales de orden k, para cada k =
1, . . . , n, tienen el mismo signo estricto. Este tipo de matrices forman una subclase de las matrices SR cuya intersección
con las matrices no singulares TP es el conjunto de las matrices no singulares ASTP.
En [2] los autores presentan una caracterización algorítmica de las matrices ASSR a través de la eliminación de
Neville (NE), un método alternativo a la eliminación gaussiana que se ha mostrado especialmente eficiente cuando se
trabaja con matrices SR y sus subclases. Cuando una matriz ASSR tiene todos sus menores no positivos, se denomina
casi estrictamente totalmente negativa (ASTN), y tal característica simplifica notablemente su caracterización.
En este trabajo se presentan algunas interesantes propiedades relacionadas con las matrices ASSR, incluyendo su
caracterización por medio de su factorización QR (ver [3]). Finalmente, también se analizan algunos resultados sobre el
error cuando la NE con estrategia de pivotaje dos-determinantal se aplica a este tipo de matrices.
Referencias
[1] T. Ando, Total positive matrices, Linear Algebra Appl. 90 (1987), 165–219.
[2] P. Alonso, J. M. Peña y M. L. Serrano, On the characterization of almost strictly sign regular matrices, J.
Comput. Appl. Math. 275 (2015), 480–488.
[3] P. Alonso, J. M. Peña y M. L. Serrano, QR decomposition of almost strictly sign regular matrices, J. Comput.
Appl. Math. (en prensa), http://dx.doi.org/10.1016/j.cam.2015.10.030.
[4] S. M. Fallat y Ch. R. Johnson, Totally nonnegative matrices, Princeton University Press, 2011.
—– • —–
La complejidad teórica del cálculo aproximado
de valores y vectores propios
Carlos Beltrán Álvarez
Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria
[email protected]
Trabajo conjunto con Diego Armentano, Peter Bürgisser, Felipe Cucker y Michael Shub. Financiado en parte por el Ministerio de
Economía y Competitividad a través de la Red de Excelencia ALAMA MTM2015-68805-REDT.
Resumen
El cálculo (aproximado) de valores y vectores propios es un problema clásico en álgebra lineal numérica. A (casi)
todos los efectos prácticos, este problema puede considerarse resuelto con el uso de algoritmos iterativos tales como QR
Congreso Bienal de la Real Sociedad Matemática Española (Zaragoza, 2017)
9
iterado con sus diversas estrategias de shift, la iteración de Rayleigh, o métodos del tipo divide y vencerás. Sin embargo,
ninguno de estos métodos puede responder, con lo que conocemos hoy en día, a una pregunta hecha por James Demmel en
1977 en el contexto de la comprensión de la complejidad del cálculo de los valores y vectores propios: ¿es posible calcular
estos pares con precisión prefijada para una matriz de tamaño n con un número de operaciones que sea polinomial en
n? La frase de Demmel [1, p. 139] es:
So the problem of devising an algorithm [for the eigenvalue problem] that is numerically stable and globally
(and quickly!) convergent remains open.
En esta charla presentaré un algoritmo que, sin tratar de competir en un contexto práctico con los excelentes métodos
existentes, responde afirmativamente a esta pregunta. La charla incluirá conceptos básicos, ejemplos y dejará al oyente
con algunos problemas muy sencillos de enunciar, pero aún sin resolver, relacionados con los valores propios de una
matriz.
Referencias
[1] J. Demmel, Applied numerical linear algebra, SIAM, 1977.
[2] D. Armentano, C. Beltrán, P. Bürgisser, F. Cucker y M. Shub, A stable, polynomial-time algorithm for the
eigenpair problem, por aparecer.
—– • —–
Cálculos precisos con subclases de matrices totalmente positivas
Juan Manuel Peña
Departamento de Matemática Aplicada / IUMA, Universidad de Zaragoza
[email protected]
Financiado en parte por el Ministerio de Economía y Competitividad a través de la Red de Excelencia ALAMA
MTM2015-68805-REDT.
Resumen
Una matriz se llama totalmente positiva si todos sus menores son no negativos. Estas matrices tienen importantes
aplicaciones en muchos campos, como puede verse en [1] y [2]. Dada una matriz totalmente positiva no singular, si
conocemos su descomposición bidiagonal con alta precisión relativa, entonces podemos realizar cálculos algebraicos con
alta precisión relativa, tales como hallar la inversa, los valores singulares o los valores propios. Sin embargo, hasta ahora la
descomposición bidiagonal con alta precisión relativa solo se ha podido conseguir para unas pocas subclases de matrices
totalmente positivas, como recordamos en esta presentación.
Referencias
[1] T. Ando, Total positive matrices, Linear Algebra Appl. 90 (1987), 165–219.
[2] S. M. Fallat y Ch. R. Johnson, Totally nonnegative matrices, Princeton University Press, 2011.
—– • —–
Diagrama de bifurcación de sistemas dinámicos lineales bimodales
conteniendo una silla
Josep Ferrer
Departamento de Matemáticas, Universitat Politècnica de Catalunya
[email protected]
En colaboración con Marta Peña y Antoni Susin. Financiado en parte por el Ministerio de Economía y Competitividad a través
de la Red de Excelencia ALAMA MTM2015-68805-REDT.
10
S1. Álgebra lineal y análisis matricial: avances recientes en teoría y computación
Abstract
We continue the study of the structural stability and the bifurcations of planar bimodal linear dynamical systems
(BLDS), that is, systems consisting of two linear dynamics acting on each side of a straight line, assuming continuity
along the separating line. Here we complete this study when one of these subsystems is a saddle, the unique planar BLDS
where tangency/saddle (and saddle/tangency) singularities may appear. So, this is a 3-dimensional bifurcation diagram,
depending on the trace of the saddle, and the trace and the determinant of the other subsystem. In particular one
3-codimensional bifurcation appears, as well as several 1-codimensional and 2-codimensional bifurcations. We describe
the qualitative changes of the dynamical behaviour at each kind of them.