Numerical Linear Algebra - Hamilton Institute

1 Course MaterialNetworkMaths Graduate ProgrammeMaynooth 2010 Numerical Linear AlgebraVolker Mehrmann,TU Berlin,August 3, 2010 LiteratureThe material of this course is based on the following textbooks: G. Golub, C. Van computations. Baltimore, 1996. R. B. Lehoucq, D. C. Sorensen and C. Users Guide: Solution ofLarge-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi methods , Philadel-phia, 1989. Y. methods for large eigenvalue problems. Manchester, 1992. L. Trefethen, D. Linear Algebra . Philadelphia, 1997. D. of matrix computations. New York, following books are also useful to complement the material of these notes: J.

2 Numerical Linear Algebra . Philadelphia, 1997. and stability of Numerical algorithms. Philadelphia, 2002. algorithms. Philadelphia, 1998-2001, 2 Volumes. Stewart, perturbation theory. Boston, 0 IntroductionThe main topics ofNumerical Linear Algebraare the solution of different classes ofeigenvalueproblemsandlinear the eigenvalue problem we discuss different classes.(a) Thestandard eigenvalue problem: For a real or complex matrixA Cn,n, determinex Cn, C, such thatAx= standard eigenvalue problem is a special case of thegeneralized eigenvalue problem:For real or complex matricesA,E Cm,n, determinex Cn, C, such thatAx= Ex,In many applications the coefficient matrices have extra properties such as being real andsymmetric or complex Linear systems.

3 Ax=b,x Cn,b CmwithA Cm,nwe again may extra properties for the coefficient will concentrate in this course on the Numerical solution of standard and generalizedeigenvalue problems and the solution of Linear systems. We will briefly review some of thestandard techniques for small scale problems and put an emphasis on large scale :Eigenvalue problems arise in the vibrational analysis of structures and vehicles (classical mechanics); the analysis of the spectra and energy levels of atoms and molecules (quantum mechan-ics); model reduction techniques, where a large scale model is reduced to a small scale modelby leaving out weakly important parts; many other systems arise in almost any area of science and engineering such as3(a) frequency response analysis for excited structures and vehicles.

4 (b) finite element methods or finite difference methods for ordinary and partial differentialequations;(c) data mining, information retrieval;(d) and many will distinguish between small and medium class problems where the full matrices fit intomain memory, these are of today sizesn= 102 105and large sparse problems, where thecoefficient matrices are stored in sparse formats, and have sizesn= 106and larger. We willmainly discuss the case of complex matrices. Many results hold equally well in the real case,but often the presentation becomes more clumsy. We will point out when the real case issubstantially will discuss the following , QZ-AlgorithmLanczos, Arnoldi, Jacobi-DavidsonLSCG, GMRES4 Chapter 1 Matrix Eigenvalues and EigenvectorsLetA,E Cn,n, thenv Cn\{0}and Cthat satisfyAv= Evare calledeigenvector and eigenvalueof the pair (E,A).

5 In the special case thatEis then nidentity matrixIn(I) we have eigenvalues and eigenvectors of the standard sets (A) :={ C| eigenvalue ofA} (E,A) :={ C| eigenvalue of (E,A)}are calledspectrum ofA(the pair(E,A)), Matrix normsLetA Cm,n, then||A||p:= supx6=0||Ax||p||x||pis thematrixp-norm,p N { }and for invertible matricesA p(A) :=||A||p ||A 1||pis called thep-norm condition number cases:(a)p= 1;the column-sum norm:||A||1= maxjm i=1|aij|5(b)p= ;the row-sum norm:||A|| =||AT||1(c)p= 2;the spectral norm||A||2= square root of the largest eigenvalue ofAHAwithAH= :||A||=||A||2, (A) = 2(A)Frobenius norm:||A||F= n j=1m i=1|aij| Isometric and unitary matricesDefinition 1 LetU Cm,n,m n.

6 (a)Uis calledisometricifUHU=Ik;(b)Uis calledunitaryifUis isometric andn= 2 LetU Cn k,k n. Then the following are equivalent.(a)Uis isometric;(b) the columns ofUare orthonormal;(c) Ux,Uy = x,y for allx,y Ck( , :standard real or complex scalar product);(d)||Ux||=||x||for allx Ck;Fork=n, (a)-(d) are equivalent to(e)UUH=In;(f )U 1=UH;(g) the rows ofUare this case, furthermore,||U||= 1 =||U 1||= (U). SubspacesDefinition 3A spaceU Cnis called subspace, if for allx,y U, Cwe havex+y U, x 4 LetU Cnbe a subspace with basis(x1,..,xm)andX= [x1,..,xm], (X) =m.(a) ThenU=R(X) :={Xy|y Cm}(Range or column space ofX).

7 (b) LetY Cn,mwith Rank(Y) =m, thenR(X) =R(Y) X=Y B, B Cm, particular thenBis invertible andXB 1=Y.(c) The Gram-Schmidt method for(x1,..,xm)delivers an orthonormal basis(q1,..,qm)ofUwithSpan{q1,..,qj}=Spa n{x1,..,xj}forj= 1,..,m. This condition is equivalent to:There exists an upper triangular matrixR Cm,mwithX=QRwhereQ= [q1,..,qm].(QR-decomposition) Invariant subspacesDefinition 5 LetA Cn,nandU Cn. ThenUis calledA-invariant, ifx U Ax Ufor allx 6 LetA Cn,n,X Cn,nandU=R(X). Then the following are equivalent:(a)UisA-invariant;(b) There existsB Ck,k, such that:AX= , in this case for Candv Ck:Bv= v AXv= Xv, , every eigenvalue vonBis also an eigenvalue 7 IfA,X,BsatisfyAX=XBand ifXhas only one columnx, thenBis a scalar and we obtain the eigenvalue equationAx=x , ,Xcan be viewed as a generalization of the concept of Matrix Schur decompositionTheorem 8 (Schur, 1909)LetA Cn,n.

8 Then there existsU Cn,nunitary such thatT:=UHAUis upper :By induction:n= 1 is trivial. n 1 n : Letv Cnbe an eigenvector ofAto the eigenvalue C. Letq1:=v||v||andcompleteq1to an orthonormal basis (q1,..,qn) ofCn. ThenQ= [q1,..,qm] is unitary andQ 1AQ=[ A120A22]By the inductive assumption there existsU22unitary, such thatT22:=UH22A22U22is uppertriangular. SettingU=Q[100U22],thenT=UHAUis upper 9In the Schur decompositionUcan be chosen such that the eigenvalues ofAappearin arbitrary order on the 10A matrixT Rn,nis calledquasi-upper triangular matrix, ifTis a block-upper triangular matrix and the diagonal blocks have size maximal2 11 (Murnaghan, Wintner, 1931)LetA Rn,n.

9 Then there exists a real orthogonal matrixQ, ( ,QTQ=I) such thatT=QTAQis quasi-upper :The proof is similar to that of the Theorem of Schur: IfAhas a real eigenvectorthen we can proceed the induction as in the complex case. Otherwise for a complexeigenvectorv=v1+iv2to the complex eigenvalue = 1+i 2, withv1,v2 Rnand 1, 2 R, 26= 0 we have fromA(v1+iv2) = ( 1+i 2) (v1+iv2)thatAv1= 1v1 2v2Av2= 1v2+ 2v1} A[v1v2] = [v1v2][ 1 2 2 1].8 Hence Span{v1,v2}is anA-invariant subspace. Let (q1,q2) be an orthonormal basis ofSpan{v1,v2}and letQ= [q1,q2,q3,..,qn] be orthogonal, thenQHAQ= 1 2 2 1A120A22 .The remaining steps of the induction are as in the complex 12A Cn,nis callednormalifAAH= 13 Hermitian matrices, skew-Hermitian matrices and unitary matrices are 14 LetA Cn,nbe normal andU Cn,nunitary such thatUHAU=[A11A120A22],thenA12= 15 IfA Cn,nis normal, then there existsU Cn,nunitary, such thatUHAUis 16 (Generalized Schur form)LetA,E Cn,nbe such that the pair(E,A)isregular, ,det E A6= 0for all C.

10 Then there existU,V Cn,nunitary such thatS=UHEV, T:=UHAVare upper :Let (Ek) be a sequence of nonsingular matrices that converges toE. For every letQHkAE 1kQk=Tkbe a Schur decomposition ofAE 1kand letZHk(E 1kQk=S 1kbe a QR decomposition. ThenbothQHkAZk=RkSkandQHkEkZk=Skare upper the Bolzano-Weierstra it follows that the bounded sequence (Qk,Zk) has aconverging subsequence with a limit (Q,Z), whereQ,Zare unitary. ThenQHAZ=TandQHEZ=Sare upper The singular value decomposition (SVD)Theorem 17 (Singular value decomposition, SVD)LetA Cm,nwithRank (A) =r. Then there exist unitary matricesU Cm,mandV Cn,nsuch thatA=U VH, = r000 Cm, , 1=||A||2and 1.)