A NUMERICAL METHOD FOR SOLVING INVERSE EIGENVALUE

ANUMERICALMETHODFORSOLVINGINVERSEEIGENVALUEPROBLEMSHUADAI1DepartmentofMathematicsNanjingUniversityofAeronauticsandAstronauticsNanjing210016,People’sRepublicofChinaCERFACSTechnicalReport-TR/PA/98/33AbstractBasedonQR-likedecompositionwithcolumnpivoting,anewandecientnumericalmethodforsolvingsymmetricmatrixinverseeigenvalueproblemsisproposed,whichissuitableforboththedistinctandmultipleeigenvaluecases.Alocallyquadraticcon-vergenceanalysisisgiven.Somenumericalexperimentsarepresentedtoillustrateourresults.Keywords:inverseeigenvalueproblems,QR-likedecomposition,leastsquares,Gauss-NewtonmethodAMS(MOS)subjectclassication:65F15,65H151ThisresearchwassupportedinpartbytheNationalNaturalScienceFoundationofChinaandtheJiangsuProvinceNaturalScienceFoundation.TheworkoftheauthorwasdoneduringavisittoCERFACS,FranceinMarch-August1998.11.IntroductionLetA(c)betheanefamilyA(c)=A0+nXi=1ciAi(1)whereA0;A1;;Anarerealsymmetricnnmatrices,andc=(c1;;cn)T2Rn.Weconsiderinverseeigenvalueproblems(IEP)ofthefollowingform.IEP.Givenrealnumbers12n,ndc2Rnsuchthattheeigenvalues1(c)2(c)n(c)ofA(c)satisfyi(c)=i;i=1;2;;n(2)TheIEPareofgreatimportancetomanyapplications.AgoodcollectionofinterestingapplicationswheretheIEPmayariseisincludedin[13].ThereisalargeliteratureonconditionsforexistenceofsolutionstotheIEP.See,forexample,[2,9,19,20,27-31,33].AspecialcaseoftheIEPisobtainedwhenthelinearfamily(1)isdenedbyAi=eieiT;i=1;;nwhereeiistheithunitvector,sothatA(c)=A0+D,whereD=diag(c1;;cn).Thisproblemiswellknownastheadditiveinverseeigenvalueproblem.Fordecadestherehasbeenconsiderablediscussionabouttheadditiveinverseeigenvalueproblem.Sometheoreticalresultsandcomputationalmethodscanbefound,forexample,inthearticles[7,8,11,12,15,17,24,32],andthebook[33]andthereferencescontainedtherein.NumericalalgorithmsforsolvingtheIEPcanbefound,forexample,in[1,3,4,6,13,16,23,33].Friedland,Nocedal,andOverton[13]havesurveyedfourquadraticallyconvergentnumericalmethods.Oneofthealgorithmsanalyzedin[13](alsosee[1,4,16])isNewton’smethodforsolvingthenonlinearsystem(2).EachstepinthenumericalsolutionbyNewton’smethodofthesystem(2)involvesthesolutionofcompleteeigen-problemforthematrixA(c).Twooftheothermethodsanalyzedin[13]aremotivatedasmodicationstoNewton’smethodinwhichcomputingtimeissavedbyapproximat-ingtheeigenvectorswhenthematrixA(c)changes,ratherthanrecomputingthem.Thefourthmethodconsideredin[13]isbasedondeterminantevaluationandoriginatedwithBiegler-konig[3],butitisnotcomputationallyattractive[13]forrealsymmetricmatrices.When1;;nincludemultipleeigenvalues,however,theeigenvalues1(c);;n(c)ofthematrixA(c)arenot,ingeneral,dierentiableatasolutionc.Furthermore,theeigenvectorsarenotunique,andtheycannotgenerallybedenedtobecontinuousfunc-tionsofcatc.ThemodicationtotheIEPhasbeenconsideredin[13],butthenumberofthegiveneigenvaluesandtheirmultiplicitiesshouldbesatisedacertainconditioninthemodiedproblem.Basedonthedierentiabilitytheory[21]ofQRdecompositionofamatrixdependingonseveralvariables,Li[23]presentedanumericalmethodforsolvinginverseeigenvalueproblemsinthedistincteigenvaluecase.Inthispaper,weconsidertheformulationandlocalanalysisofaquadraticallycon-vergentmethodforsolvingtheIEP,assumingtheexistenceofasolution.Thepaperisorganizedasfollows.Insection2werecallsomenecessarydierentiabilitytheoryforQR-likedecompositionofamatrixdependentonseveralparameters.Insection3anewalgorithmbasedonQR-likedecompositionisproposed.ItconsistsofextensionofideasdevelopedbyLi[22,23],DaiandLancaster[10],andissuitableforboththedistinctandmultipleeigenvaluescases.Itslocallyquadraticconvergenceanalysisisgiveninsection4.Finallyinsection5somenumericalexperimentsarepresentedtoillustrateourresults.Weshallusethefollowingnotation.AsolutiontotheIEPwillalwaysbedenotedbyc.Forthegiveneigenvalues1;;n,wewrite=(1;;n).k:k2denotesthe2Euclideanvectornormorinducedspectralnorm,andk:kFtheFrobeniusmatrixnorm.ForannmmatrixA=[a1;;am],whereaiistheithcolumnvectorofA,wedeneavectorcolAbycolA=[a1T;;amT]T,andthenormkAk:=maxj=1;;m(kajk2).ThesymboldenotestheKroneckerproductofmatrices.2.QR-likedecompositionanddierentiabilityLetA2Rnnandm(1mn)beaninteger.FollowingLi[22],wedeneaQR-likedecompositionofAwithindexmtobeafactorizationA=QR;R=R11R120R22!(3)whereQ2Rnnisorthogonal,R11is(nm)(nm)uppertriangular,andR22ismmsquare.Whenm=1,thisisaQRdecompositionofA.Clearly,aQR-likedecompositionofamatrixexistsalways.Infact,weneedonlyconstructa\partialQRdecomposition,see[14],forexample.Ingeneral,however,itisnotuniqueasthefollowingtheoremshows.Theorem2.1(see[10,22]).LetAbeannnmatrixwhoserstnmcolumnsarelinearlyindependentandletA=QRbeaQR-likedecompositionwithindexm.ThenA=bQbRisalsoaQR-likedecompositionwithindexmifandonlyifQ=bQD;R=DTbR(4)whereD=diag(D11;D22),D11isanorthogonaldiagonalmatrix,andD22isanmmorthogonalmatrix.NotethatthelinearindependencehypothesisensuresthattheR11blocksofRandbRarenonsingular.InordertoensurethatthesubmatrixR11ofsuchadecompositionisnonsingular,weadmitapermutationoft