搜索
SU326P30-11SOMEMODIFIED~IGENVALUEPROBLEMSBYGENEH.GOLUBSTAN-CS-234-71AUGUST1971COMPUTERSCIENCEDEPARTMENTSchoolofHumanitiesandSciencesSTANFORDUNIVERSITYsu326PRO-uSOMEMODIFIEDEIGEWALUEPROBLEMS*GeneH.Golub=*PresentedbyinvitationattheDundeeConferenceonNumericalAnalysisatDundee,Scotland,inMarch,1971.**ComputerScienceDepartment,StanfordUniversity,Stanford,California94305lThisworkwassupportedinpartbygrantsfromtheNationalScienceFoundationandtheAtomicEnergyCommission.tli!ABmOFCONTENTS0.1.2.394.5-6.70IntroductionandnotationStationaryvaluesofaquadraticformsubjecttolinearconstraints-.StationaryvaluesofabilinearformsubjecttolinearconstraintsSomeinverseeigenvalueproblemsIntersectionofspacesEigenvaluesofamatrixmodifiedbyamatrixofrankoneLeastsquaresproblemsGauss-typequadratureruleswithpreassignednodesAbstractWeconsiderthenumericalcalculationofseveraleigenvalueproblemswhichrequiresomemanipulationbeforethestandardalgorithmsmaybe-.used.Thisincludesfindingthestationaryvaluesofaquadraticformsubjecttolinearconstraintsanddeterminingtheeigenvaluesofamatrixwhichismodifiedbyamatrixofrankone.Wealsoconsiderseveralinverseeigenvalueproblems.ThisincludestheproblemofcomputingtheGauss-RadauandGauss-I,obattoquadraturerules.Inaddition,westudyseveraleigenvalueproblemswhichariseinleastsquares.0.IntroductionandnotationInthelastseveralyears,therehasbeenagreatdevelopmentindevisingandanalyzingalgorithmsforcomputingeigensystemsofmatrixequations.Inparticular,theworksofH.RutishauserandJ.H.Wilkinsonhavehadgreatinfluenceonthedevelopmentofthissubject.Itoftenhappensinappliedsituationsthatonewishestocomputetheeigensystemofaslightlymodifiedsystemoronewishestospecifysomeoftheeigenvaluesandthencomputeanassociatedmatrix.Inthispaperweshallconsidersomeoftheseproblemsandalsosomestatisticalproblemswhichleadtointerestingeigenvalueproblems.Ingeneral,weshowhowtoreducethemodifiedproblemstostandardeigenvalueproblemssothatthestandardalgorithmsmaybeused.Weassumethatthereaderhassomefamiliaritywithsomeofthestandardtechniquesforcomputingeigensystems.WeordinarilyindicatematricesbycapitalletterssuchasA,B,A;vectorsbylowercaseletterssuchasx,y,a,,andscalarsbylowercaseMmletters.Weindicatetheeigenvaluesofamatrixash(X)whereXmaybeanexpression,e.g.,h(A2+I)indicatestheeigenvaluesofA2+I,andinasimilarfashionweindicatethesingularvaluesofamatrixbyo(X).UsuallyweordertheeigenvaluesandsingularvaluesofamatrixsothatAl(A)5h2(A)5...5$(A)andal(A),02(A)5...oN(A).Weassumethatthereaderhassomefamiliaritywithsingularvalues(cf.[g])*1.StationaryvaluesofaquadraticformsubjecttolinearconstraintsLetAbearealsymmetricmatrixofordern,andcagivenCITvectorwithcc=1.WNInmanyapplications(cf.[lo]itisdesirabletofindthestationaryvaluesof..TXAXNNsubjecttotheconstraintsTxx=1NN(1.1)(14(1.3)Letcp(x)=xTAx-lLxTx+T2pxcW)Nm-cIc1GINwhereob4areLagrangemultipliers.Differentiating(1.4),weareledtotheequationAx-xx+pc=ol(le5)LIHc1c1Multiplying(1.5)ontheleftbycTandusingtheconditionthatHIIIIE2=1,wehaveTP=-cAx.(14NNThensubstituting(1.6)into(1.5),weobtainPAX=?LXMm(1*7)whereP=I-ccT.AlthoughPandAaresymmetric,PAisnotNWnecessarilySO.Notethat2P=P,sothatPisaprojectionmatrix.Thush(PA)=A(P2A)=A(PAp)lThematrixPAPissymmetricandhenceonecanuseoneofthestandardalgorithmsforfindingitseigenvalues.ThenifK=PAPandifKZi=hiZitNitfollowsthatX.=Pfi(i-1=1,2,...,n).Atleastone-eigenvalueofKwillbeequaltozero,andcwillbeNaneigenvectorassociatedwithazeroeigenvalue.Nowsupposewereplacetheconstraint(1.3)bythesetofconstraintsCTx=o(l-8)wwhereCisannxpmatrixofrankr.Itcanbeverifiedthatiff=I-cc-&9whereC-isageneralizedinversewhichsatisfiescc-c=c(1.10)cc-=(CC-)TthenthestationaryvaluesareeigenvaluesofK=PAP.AtleastroftheeigenvaluesofKwillbeequaltozero,andhenceitwouldbedesirabletodeflatethematrixKsothattheseeigenvaluesareeliminated.l-2BypermutingthecolumnsofC,wemaycomputetheorthogonaldecompositionC=QT;;TT[1(1J-lwhereRisanuppertriangularmatrixoforderr,Sisrx(p-r),QTQ=InandTTisapermutationmatrix.ThematrixQmaybeconstructedastheproductofrHouseholdertransformations(cf.[8]).AsimplecalculationshowsPQ--_andthusWA@=h(QTJQ,AQTJQ)=A(JQAQTJ)lThenif(1.12)whereGilisanrxrmatrixandG22isan(n-r)x(n-r)matrix,JQAQTJ=00[1OG22.Hencethestationaryvaluesaresimplytheeigenvaluesofthe(n-r)x(n-r)matrixG22.FinallyifG22ziII=hiZi(i=1,2,...,n-r),l-3thenX.-1=QTcI;n-r5lThedetailsofthealgorithmaregivenin[lo]...Fromequation(1.13)weseethath(G)=h(A).ThenbytheCourant-Fischertheorem,'jtA)jtG225h,+jtA)(j=1,2,...,n-r)(1.14)whenFurthermore,ifthecolumnsofthematrixCspanthesamespaceasthereigenvectors-associatedwithrsmallesteigenvaluesofA,Thus,weseethatthereisastrongrelationshipbetweentheeigenvaluesofAandthestationaryvaluesofthefunctionq(x)=xTAxTTT-Axx+2pcx,mCINNNwwherepisavectorofLagrangemultipliers.(1.16)l-42.StationaryvaluesofabilinearformsubjecttolinearconstraintsNOWletusconsidertheproblemofdeterminingthenon-negativestationaryvaluesof(XTAYAll$I,-CIII&1(24whereAisanmxnmatrix,subjecttotheconstraintscTx=0,DTy=0.NCI(24Thenon-negativestationaryvaluesof(2.1)arethesingularvaluesofA(i.e.,o(A)=[h(~~A)]l/~).Itiseasytoverifythatt