Metodo delle sezioni finite

Per quanto visto nell’Osservazione 6.3, `e possibile associare al polinomio di Laurent (6.19) la matrice tridiagonale biinfinita di Toeplitz a blocchi

T =        . .. ... 0 . .. A0 A1 A−1 A0 . .. 0 . .. ...        .

Per quanto visto nella Proposizione 6.4, siamo interessati al calcolo della diagonale principale di T−1_{: per far ci`o usiamo le sezioni finite di T . Con}

il termine k−esima sezione finita di T , indicheremo la matrice seguente, costituita da k × k blocchi (ciascuno dei quali `e una matrice quadrata di dimensione n): Tk=       A0 A1 0 A−1 A0 . .. . .. ... A1 0 A−1 A0       . (6.27)

Osserviamo che, poich´e il polinomio di Laurent A(z) `e palindromo, la ma- trice Tk pu`o anche essere riscritta in una forma pi`u compatta, usando il

prodotto di Kronecker: si ha dunque

Tk= Ik⊗ A0+ Vk⊗ A1, (6.28)

dove Vk `e una matrice tridiagonale di dimensione k cos`ı definita

Vk=       0 1 0 1 0 . .. . .. ... 1 0 1 0      .

Spieghiamo ora come sia possibile usare le sezioni finite di T per il calcolo della diagonale principale di T−1, con riferimento al caso in cui A(z) sia uno dei polinomi (6.4)-(6.7).

78 CAPITOLO 6. UN APPROCCIO GENERALE `

E ben noto che, quando si vuole trovare la j−esima colonna dell’inversa di una data matrice A ∈ Mn(C), si pu`o procedere risolvendo il sistema

Ax = ej, dove ej `e la j−esima colonna di In. Analogamente, nel caso in

cui A sia una matrice costituita da k × k blocchi (ciascuno di dimensione n) il sistema da risolvere sar`a AX = ej⊗ In, dove ej stavolta `e la j−esima

colonna di Ik e X = (X1, ..., Xk)T con Xi∈ Mn(C), per i = 1, ..., k (come `e

lecito aspettarsi perch´e la notazione sia consistente).

Pertanto, nel nostro caso, risolvendo il sistema TkX(k) = ej ⊗ In ed

isolando X_j(k)_{, il j−esimo blocco di X}(k)_{, si trova il j−esimo blocco della} j−esima colonna di Tk−1, cio`e il j−esimo blocco della diagonale principale

di T_k−1. Si pu`o dimostrare che lim

k→∞X (2k+1) k+1 = Z0,

dove Z0 `e la matrice che costituisce i blocchi sulla diagonale principale di

T−1. Per farlo, riscriviamo X_k+1(2k+1) alla luce della (6.28).

Innanzitutto osserviamo che Vk pu`o essere portata in forma diagonale

mediante la matrice ortogonale Hk, il cui (ij)−esimo elemento `e dato da

r 2 k + 1sin µ ijπ k + 1 ¶ . Vale cio`e la relazione HT

kVkHk = Dk, dove Dk `e una matrice diagonale

avente elementi 2 cos(iπ/(k + 1)), per i = 1, ..., k. Ne consegue che Tk `e

simile ad una matrice diagonale a blocchi e

Dk= (HkT ⊗ In)Tk(Hk⊗ In) = Ik⊗ A0+ Dk⊗ A1,

dove, per l’ultima uguaglianza, sono state usate le propriet`a del prodotto di Kronecker e l’ortogonalit`a di Hk.

Siamo ora giunti a poter scrivere la seguente espressione: X_k+1(2k+1) = (eT_{k+1⊗ I}n)T_2k+1−1 (ek+1⊗ In)

= (eT_{k+1⊗ I}n)(H2k+1T ⊗ In) eD2k+1−1 (H2k+1⊗ In)(ek+1⊗ In)

= (eT_k+1H_2k+1T _{⊗ I}n) eD−1_2k+1(H2k+1ek+1⊗ In).

Poich´e H2k+1ek+1 non `e altro che la (k + 1)−esima colonna di H2k+1, il cui

i−esimo elemento, per i = 1, . . ., (2k + 1), `e dato dall’espressione r 1 k + 1sin µ i(k + 1)π 2(k + 1) ¶ = r 1 k + 1sin µ iπ 2 ¶ ,

6.3. ALTRI METODI DI SOLUZIONE 79 si ottiene X_k+1(2k+1) = 2k+1_X i=1 (k + 1)−1sin2 µ iπ 2 ¶ µ 2A1cos µ iπ 2(k + 1) ¶ + A0 ¶−1 = = 1 k + 1 2k+1_X i=1, i≡1(mod2) µ 2A1cos µ iπ 2(k + 1) ¶ + A0 ¶−1 = = 1 k + 1 k X i=0 µ 2A1cos µ (2i + 1)π 2(k + 1) ¶ + A0 ¶−1 . (6.29) `

E facile riconoscere nella formula (6.29), che presenta anche analogie con la (6.26), il metodo di Gauss-Chebyshev per il calcolo dell’integrale

1 π Z 1 −1 (2A1s + A0)−1 √ 1 − s2 ds. (6.30)

In accordo con quanto affermato nell’Osservazione 5.7, se A(z) `e il polinomio (6.4), si ha dunque che

lim

k→∞X (2k+1)

k+1 = A1/2,

per le note propriet`a di convergenza del metodo di Gauss-Chebyshev. Per le altre tre funzioni notevoli, un ragionamento analogo potrebbe sembrare ostacolato dal fatto che gli integrali (2.5), (4.5) e (5.7), possono essere scritti in forma pi`u generica, usando la stessa notazione di (6.30), nel modo seguente: 1 π Z 1 −1 (−2A1s + A0)−1 √ 1 − s2 ds.

Come si nota, la formula sopra differisce dalla (6.30) per un segno, ci`o per`o non ci dissuade dall’affermare che la (6.29) costituisce l’applicazione del metodo di Gauss-Chebyshev anche per quest’ultima espressione.

Infatti, per le propriet`a dei nodi di tale metodo di integrazione numerica, baster`a semplicemente riordinare gli indici di sommazione nella (6.29) per ottenere quanto voluto: in particolare, baster`a scambiare l’indice i−esimo con quello (n − i)−esimo.

Analogamente a quanto visto per la radice quadrata, la convergenza del metodo delle sezioni finite al segno, al fattore polare unitario o alla media di matrici segue quindi dalla convergenza del metodo di Gauss-Chebyshev applicato all’integrale (2.5), (4.5) o (5.7).

Bibliografia

[1] W.N. Anderson, T.D. Morley, G. Trapp. Characterization of parallel subtraction. Proc. Natl. Acad. Sci. USA 76, 3599-3601, 1979.

[2] T. Ando, C.-K. Li, R. Mathias. Geometric means. Linear Algebra Appl., 385:305-334, 2004.

[3] T. Ando. Concavity of certain maps on positive definite matrices and applications to Hadamard products. Linear Algebra Appl., 26:203-241, 1979.

[4] L. Autonne. Sur les groupes lin´eaires, r´eels et orthogonaux. Bulletin de la Soci´et´e Math´ematique de France, 30:121-134, 1902.

[5] Z. Bai, J. Demmel. Using the matrix sign function to compute invariant subspaces. SIAM J. Matrix Anal. Appl., 19(1):205-225, 1998.

[6] P.G Batchelor, M. Moakher, D. Atkinson, F. Calamante, A. Connelly. A rigorous framework for diffusion tensor calculus. Magnetic Resonance in Medicine, 53:221-225, 2005.

[7] R. Bevilacqua, D. Bini, M. Capovani, O. Menchi. Metodi numerici, Zanichelli Editore, Bologna, 1992.

[8] R. Bhatia, J. Holbrook. Riemannian geometry and matrix geometric means. Linear Algebra Appl., 413:594-618, 2006.

[9] D.A. Bini, L. Gemignani, B. Meini. Computations with infinite Toeplitz matrices and polynomials. Linear Algebra Appl., 343-344:21-61, 2002. [10] D.A. Bini, G. Latouche, B. Meini. Numerical Methods for Structured

Markov Chains, Oxford Univerity Press, New York, NY, USA, 2005. [11] B.L. Buzbee, G.H. Golub, C.W. Nielson. On direct methods for solving

Poisson’s equation. SIAM J. Numer. Anal., 7:627-656, 1970.

[12] A. Cayley. A memoir on the theory of matrices. Philos. Trans. Roy. Soc. London, 148:17-37, 1858.

82 BIBLIOGRAFIA [13] S.H. Cheng, N.J. Higham, C.S. Kenney, A.J. Laub. Approximating the logarithm of a matrix to specified accuracy. SIAM J. Matrix Anal. Appl., 22(4):1112-1125, 2001.

[14] E.D. Denman, A.N. Beavers. The matrix sign function and computations in systems. Appl. Math. Comput., 2:63-94, 1976.

[15] J. van den Eshof, A. Frommer, Th. Lippert, K. Schilling, H.A. van der Vorst. Numerical Methods for the QCD Overlap Operator:I. Sign-Function and Error Bounds. Computer Physics Communications, 146:203-224, 2002.

[16] K. Fan, A.J. Hoffman. Some metric inequalities in the space of matrices. Proc. Amer. Math. Soc., 6:111-116, 1955.

[17] M. Fiedler, V. Pt´ak. A New Positive Definite Geometric Mean of Two Positive Definite Matrices. Linear Algebra Appl., 251:1-20, 1997. [18] P. Henrici. Applied Computational Complex Analysis, John Wiley &

Sons, USA, 1974.

[19] N.J. Higham. Computing Real Square Roots of a Real Matrix. Linear Algebra Appl., 88-89:405-430, 1987.

[20] N.J. Higham. Computing the Polar Decomposition – with Applications. SIAM J. Sci. Statist. Comput., 7(4):1160-1174, 1986.

[21] N.J. Higham. Newton’s methods for the matrix square root. Math. Comp., 46(174):537-549, 1986.

[22] N.J. Higham. Stable iterations for the matrix square root. Numer. Algorithms, 15(2):227-242, 1997.

[23] N.J. Higham. The matrix sign decomposition and its relation with polar decomposition. Linear Algebra Appl., 212-213:3-20, 1994.

[24] N.J. Higham. Functions of Matrices: Theory and Computation. Society for Industrial and Applies Mathematics, Philadelphia, PA, USA, 2008. [25] N.J. Higham, P. Papadimitriou. A new parallel algorithm for compu- ting the singular value decomposition. Proceedings of the Fifth SIAM Conference on Applied Linear Algebra, John G. Lewis, editor, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1994, pp. 80-84.

[26] R.A. Horn, C.R. Johnson. Matrix Analysis. Cambridge University Press, 1985.

BIBLIOGRAFIA 83 [27] R.A. Horn, C.R. Johnson. Topics in Matrix Analysis. Cambridge

University Press, 1991.

[28] B. Iannazzo. A note on computing the matrix square root. Calcolo, 40:273-283, 2003.

[29] B. Iannazzo, B. Meini. Computing the matrix geometric mean: an unifying framework. In preparation, 2009.

[30] C.S. Kenney, A.J. Laub. Rational iterative methods for the matrix sign function. SIAM J. Matrix Anal. Appl., 12(2):273-291, 1991.

[31] C.S. Kenney, A.J. Laub. The matrix sign function. IEEE Trans. Automat. Control, 40(8):1330-1348, 1995.

[32] H. Kosaki. Geometric mean of several positive operators. 1984. [33] P. Laasonen. On the iterative solution of the matrix equation

AX2_{− I = 0. M.T.A.C., 12:109-116, 1958.}

[34] J.D. Lawson, Y. Lim. Solving symmetric matrix word equations via symmetric space machinery. Linear Algebra Appl., 414:560-569, 2006. [35] J.D. Lawson, Y. Lim. The Geometric Mean, Matrices, Metrics, and

More. Amer. Math. Monthly, 108:797-812, 2001.

[36] B. Meini. The matrix square root from a new functional perspective: theorical results and computational issues. SIAM J. Matrix Anal. Appl., 26(2):362-376, 2004.

[37] M. Moakher. A differential geometric approach to the geometric mean of symmetric positive-definite matrices. SIAM J. Matrix Anal. Appl., 26(3):735-747, 2005.

[38] M. Moakher. On the averaging of symmetric positive-definite tensors. J. Elasticity, 82:273-296, 2006.

[39] P. Pandey, C.S. Kenney, A.J. Laub. A parallel algorithm for the matrix sign function. Int. J. High Speed Computing, 2(2):181-191, 1990. [40] B.N. Parlett. A recurrence among the elements of triangular matrices.

Linear Algebra Appl., 14:117-121, 1976.

[41] D. Petz, R. Temesi. Means of positive numbers and matrices. SIAM J. Matrix Anal. Appl., 27(3):712-720, 2005.

[42] W. Pusz, S.L. Woronowicz. Functional calculus for sesquilinear forms and the purification map. Reports Math. Phys., 8:159-170, 1975.

84 BIBLIOGRAFIA [43] J.D. Roberts. Linear model reduction and solution of the algebraic Riccati equation by use of the sign function. Internat. J. Control, 32(4):677-687, 1980.

[44] K. Shoemake, T. Duff. Matrix animation and polar decomposition. Pro- ceedings of the Conference on Graphics Interface ’92 : 258-264, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1992.

[45] E.D. Sontag. Mathematical Control Theory: Deterministic Finite Di- mensional Systems. Second Edition. Springer, New York, NY, USA, 1998.

[46] G.P. Tolstov. Fourier Series. Dover Publications, New York, NY, USA, 1962.

[47] G.E. Trapp. Hermitian semidefinite matrix means and related matrix inequatilies – an introduction. Linear and Multilinear Algebra, 16:113- 123, 1984.

[48] J.F. Traub, H. Wozniakowski. Convergence and Complexity of New- ton Iteration for Operator Equation. J. Ass. Computing Machinery, 26(2):250-258, 1979.

Ringraziamenti (bis) ...ovvero “grazie, e ancora grazie” `

E pi`u facile dirsi medico che saper guarire, dirsi pittore che dipingere, dir- si genio che creare. `E pi`u facile ridere delle cose che capirle, aggirare le difficolt`a che sormontarle, citare l’errore di un uomo che comprenderne la

complessa natura (G. Prezzolini)

Guarda pi`u avanti, guarda pi`u in alto, guarda pi`u lontano e troverai una

strada (Lord R. Baden-Powell)

Considero valore tutte le ferite (E. De Luca) Un pensiero vada a quanti hanno intersecato la loro vita con la mia in questi anni pisani, con un misto di riconoscenza, gioia e malinconia:

agli amici/colleghi/compagni di (s)ventura del dip, perch´e, in accordo col detto “mal comune, mezzo gaudio”, `e stato bello crescere condividendo gioie e dolori, i momenti di svago e spensieratezza cos`ı come quelli di fatica e scoramento (non faccio nomi, ma chi si riconosce in questa categoria vi `e automaticamente incluso);

alle coinquiline, passate e presenti, perch´e (specialmente da un po’ di tempo a questa parte) penso di essere stata insopportabile;

alle Zie e alle altre compagne di calcetto, perch´e ho “ringhiato” scari- cando le tensioni e mi sono sentita Totti le poche volte che ho segnato (ma erano tutte reti di fattura davvero pregevole):... sono soddisfazioni!

Includo tra i protagonisti degli anni pisani, ma nel suo caso dovrei dire anni pisano-spezzini, anche Marco Venturini, l’unico (almeno finora) capo del Capo: se fosse stato pi`u severo non sarei arrivata alla laurea in tempi ragionevoli.

In questa sede mi sembra anche giusto rendere merito a due persone alle quali, per motivi ovviamente diversi, devo gran parte della mia formazione: il professor Mario Arcamone, perch´e grazie a lui ho capito, mentre me ne stavo dietro ad un banco di liceo -irriverente, ironica, irrequieta-, che avevo davvero passione per la matematica; don Gianni Satta, perch´e ascoltare per anni le sue parole, mai vuote, n´e casuali o inutili, `e stata una fondamentale esperienza di vita.

Inoltre vorrei rivolgere un ringraziamento a tutti quanti mi hanno vo- luto bene e hanno tifato per me, specialmente dall’altra sponda del mare: `e imbarazzante ammettere che mi basta sentire l’aria della Sardegna per commuovermi... evidentemente un motivo c’`e...

In particolare, grazie a mio padre, mia madre e mio fratello Paolo: sorridete, abbiamo finito!