MatrixNorms

MatrixnormsanderroranalysisStevenL.CarnieHerewesummarizetheimportantpropertiesofthevectorandmatrixnormsweneedfor620-333.Indoingerroranalysisforproblemsinvolvingvectorsandmatrices(e.g.solvinglinearsystems),weneedtomeasurethe`size'oftheerrorsinavectorormatrix.Therearetwocommonkindsoferroranalysisinnumericallinearalgebra:componentwiseandnormwise.Ingeneral,normwiseerroranalysisiseasier(butlessprecise).Forthatweneedtointroducevectornormsandmatrixnorms.1VectornormsFrom620-156/157youshouldhaveseentheideaofavectornorm.HereweworkwithrealvectorspacesRnbuteverythinggoesovertocomplexspaces(replacetransposebyHermitiantranspose,symmetricmatrixbyHermitian,orthogonalmatrixbyunitaryetc.wherenecessary).Denition1ThenormofavectorspaceVisafunctionk
k:V7!Rwiththeproperties:1.kxk08x2Vwherekxk=0,x=0(normsarepositivefornonzerovectors)2.kxk=jjkxk(scalingavectoruniformlyscalesthenormbythesameamount)3.kx+ykkxk+kxk8x;y2V(triangleinequality)CExampleThe3mostcommonvectornormsare:1.kxk1=Pjxij(the1-norm)12.kxk2=(Px2i)1=2=pxTx(the2-normi.e.theusualEuclideannorm)3.kxk1=maxijxij(the1-norm)whichareallspecialcasesofthep-norm:kxkp=(Xjxijp)1=pExercise1PlotthesetofallunitvectorsinR2ina)the1-normb)the1-norm.The2-normisspecialbecauseitsvaluedoesn'tchangeunderorthogonaltransformations.kQxk2=p(Qx)T(Qx)=pxTQTQx=pxTx=kxk2sinceQTQ=Iforanorthogonalmatrix.It'salsotheonlynormwithacloseconnectiontotheinnerproduct(dotproduct)betweenvectors.Innite-dimensionalspaces,itdoesn'tmattermuchpreciselywhichnormyouuse,sincetheycan'tdierbymorethanafactornfromeachother.Thispropertyiscallednormequivalence.Theorem1kxk2kxk1pnkxk2kxk1kxk2pnkxk1kxk1kxk1nkxk1Soyoumayaswellusewhicheveroneisconvenient.Somesensiblepropertiesthatsomenormshaveare:monotonejxjjyj)kxkkykwherejxjjyjmeansacomponentwiseinequalityi.e.jxijjyij8i.absolutekjxjk=kxkwherejxjisthevectorwithcomponentsgivenbytheabsolutevaluesofthecomponentsofx.2Itisnotobvious,buttrue,thatthesetwopropertiesareequivalenti.e.anormthatismonotoneisabsoluteandviceversa.Noteveryvectornormhasthesepropertiesbutthep-normsdo.Weusevectornormstomeasurethe`size'oferrorsin,forexample,theRHSbofalinearsystem.2MatrixnormsSimilarlywewillwanttomeasurethesizeoferrorsinthecoecientmatrixAofalinearsystem.Forthatweneedmatrixnorms.Amatrixnormisjustavectornormonthem
ndimensionalvectorspaceofmnmatrices.HenceDenition2Amatrixnormisafunctionk
k:Mmn7!Rwiththeprop-erties:1.kAk08A2MmnwherekAk=0,A=0(normsarepositivefornonzeromatrices)2.kAk=jjkAk(scalingamatrixuniformlyscalesthenormbythesameamount)3.kA+BkkAk+kBk8A;B2Mmn(triangleinequality)CExampleThefollowingarematrixnorms:1.kAkF=(Pa2ij)1=2(theFrobeniusnorm)2.kAkM=maxi;jjaijj(themax-norm)Exercise2Arethesenormsmonotone?Hint:aretheyabsolute?We'llmostlyusenotthesenorms,butacommonclassofmatrixnorms,calledsubordinatematrixnormsorinducedmatrixnormsor(Demmel)op-eratornorms:3Denition3Thesubordinatenormofa(square)matrixAisgivenbykAk=maxx6=0kAxkkxkforanyvectornorm.Thisisequivalentto:kAk=maxkxk=1kAxkInwords,the(subordinate)normofamatrixisthenormofthelargestimageunderthemapAofaunitvector.Exercise3ProvethatanysubordinatenormisamatrixnormCExampleThesubordinatenormswe'llusearethosecorrespondingtothevectornormslistedabove:1.kAk1=maxjPijaijj(themaximumcolumnsum)2.kAk2(the2-norm)3.kAk1=maxiPjjaijj(themaximumrowsum)Thesearetheonlysubordinatep-normsthatareeasytocompute.Exercise4ProvethatkAk1=maxiPjjaijjThesubordinatenormshavesomeusefulsubmultiplicativeproperties:kAxkkAkkxkbydenition;andkABkkAkkBkAnymatrixnormwiththelatterpropertyiscalledconsistent.Similarly,wehavenormequivalenceformatrixnorms,sincetheyarewithinafactorofnofeachother:Theorem21pnkAk2kAk1pnkAk21pnkAk1kAk2pnkAk11nkAk1kAk1nkAk1Soyoumayaswellusewhicheveroneisconvenient.42.1Thematrix2-normThe2-normhasasurprisingconnectiontoeigenvalues.Theorem3kAk2=pmax(ATA)wheremax(ATA)isthemaximumeigenvalueofATA.Proof:kAk2=maxx6=0kAxk2kxk2=maxx6=0(xTATAx)1=2kxk2SinceATAissymmetric,ithasanorthogonaldiagonalisation(thespectraldecomposition)ATA=QQTwhereisadiagonalmatrixcontainingtheeigenvaluesofATA,allreal.ThenkAk2=maxx6=0(xT(QQT)x)1=2kxk2=maxx6=0((QTx)T(QTx))1=2kQTxk2sinceorthogonaltransformationsdon'tchangethe2-normofavector.SinceATAispositivedenite,alltheeigenvaluesarepositive.kAk2=maxy6=0(yTy)1=2kyk2=maxy6=0sPiy2iPy2ismaxPy2iPy2i=pmaxwhichcanbeattainedbychoosingytobethejthcolumnvectoroftheidentitymatrixif,say,jisthelargesteigenvalue.Thematrix2-normisthenaturalnormtousefortheproblemofLeastSquarestting.3SensitivityNowweknowhowtomeasure`size'inourvariousvectorspaces,weask:howdosmallchangesinthecoecientmatrixandRHSofalinearsystemaectthesolution?Sincewecanchangeamatrixinmanydierentways,wejustaskthatthechangeisarbitrarybutthatthenormofthedierenceissmall,relativetothenormofthematrixi.e.weconsidersmallnormwiserelativechangestothematrix.Thismeanswearedoingaworstcaseanalysissincewe'relookingfortheworstthatcanhappen.5Werstask:howdosmall(relativenormwise)changestoA;baectthesolutionx?Wehave(A+
A)^x=b+
bwhere^x=x+
x,andAx=bSubtractingthesegivesA
x=
b