• metodo di aberth
• metodo qr
• polinomi di matrici
• polinomi palindromici

Metodi numerici per problemi palindromici agli autovalori.

Il lavoro di tesi parte dallo studio dei problemi agli autovalori della forma

P(lambda)x=0, (1)

con P(lambda) polinomio di matrici, ovvero polinomio avente per coefficienti matrici in C^(nxn).

Siamo interessati allo studio di tali problemi nel caso particolare in cui il polinomio P(lambda) abbia un certo tipo di simmetria nella struttura, ovvero P(lambda) palindromico con primo coefficiente uguale all'ultimo, secondo coefficiente uguale al penultimo, e così via.

Tale tipo di simmetria si riflette sullo spettro di P(lambda) in quanto gli autovalori si presentano in coppie del tipo (lambda, 1/lambda).
In questa tesi studiamo due differenti approcci numerici per la risoluzione di tale problema, in entrambi i casi siamo comunque interessati a procedimenti che determino le coppie di autovalori, ovvero l'esatta corrispondenza di un autovalore col suo inverso.

Un possibile metodo di risoluzione è quello di passare alla linearizzazione, cioè trovare un fascio di matrici L(lambda) = lambda X + Y di dimensioni maggiori avente gli stessi autovalori del problema di partenza. In [2] viene descritto un procedimento che conserva la simmetria del polinomio P(lambda) anche nel problema linearizzato, che quindi si presenterà nella forma

Ax = A^T x.

In [4] viene proposto un algoritmo di tipo QR per la risoluzione di tale problema, che viene discusso e analizzato all'interno della tesi. Analogamente al caso del QR classico vengono trattate anche le connesse strategie di deflazione e shift, nonchè di bulge chasing per l'applicazione del metodo a matrici in forma skew Hessenberg.

Un'altra possibilità è quella di risolvere direttamente il problema (1) senza ricorrere alla linearizzazione. In questa tesi viene proposto e descritto un algoritmo di questo tipo, basato sul metodo iterativo di Aberth [1].

Viene inoltre proposto un algoritmo di riduzione dell'ordine del problema di partenza, in modo da rimuovere tutte le coppie di autovalori del tipo (0,infinito) mantenendo al contempo la simmetria strutturale del polinomio.

Vengono infine forniti i risultati numerici di vari test al calcolatore, con particolare interesse nel confronto tra i diversi metodi per determinare quale tra questi risulti migliore in termini di velocità e precisione.



Riferimenti bibliografici

[1] O. Aberth. Iteration methods for nding all zeros of a polynomial simultaneously.
Mathematics of Computation, Vol. 27, No. 122, pp. 339-344, April 1973.

[2] D.S. Mackey, N. Mackey, C. Mehl and V. Mehrmann. Structured polynomial eingen-
value problems: Good vibrations from good linearizations. SIAM Journal on Matrix
Analysis and Applications, Vol. 28, No. 4, pp. 1029-1051, 2006.

[3] D.S. Mackey, N. Mackey, C. Mehl and V. Mehrmann. Numerical methods for palin-
dromic eigenvalue problems: Computing the anti-triangular Schur form. Numerical
Linear Algebra with Applications, Vol. 16, Issue 1, pp. 63-86, January 2009.

[4] C. Schroder. A QR-like algorithm for the palindromic eigenvalue problem. DFG
Research Center Matheon, Preprint 388, Germany, May 2007.