solutions-for-applied-numerical-linear-algebra

SolutionsforAppliedNumericalLinearAlgebraZhengJinchangJanuary25,2014ThissolutionisforAppliedNumericalLinearAlgebra,writtenbyJames.W.Demmel.ItcoversthemajorityofthequestionsfromChapterItoChapterVIexcepttheprogrammingandfewotherquestions.Asitisdonebymyself,surelyitwillhaveerrors.Thus,iftherearesomeerrorsorsomethingelse,[e-mail]ul:)CONTENTS1SolutionsforChapterI:Introduction22SolutionsforChapterII:LinearEquationSolving153SolutionsforChapterIII:LinearLeastSquaresProblems294SolutionsforChapterIV:NonsymmetricEigenvalueProblems425SolutionsforChapterV:TheSymmetricEigenproblemandSingularValueDecomposition516SolutionsforChapterVI:IterativeMethodsforLinearSystems6711SOLUTIONSFORCHAPTERI:INTRODUCTIONQuestion1.1.LetAbeanorthogonalmatrix.Showthatdet(A)Ƨ1.ShowthatifBisalsoorthogonalanddet(A)Æ¡det(B),thenAÅBissingular.Solution.Accordingtothedefinitionoforthogonalmatrix,wehaveAATÆI.Takedeterminantonbothsides.Sincedet(A)Ædet(AT),itresults¡det(A)¢2Æ1.Consequently,det(A)Ƨ1.ToproofAÅBissingular,considerdet(AÅB)Ædet(ATÅBT),yieldingdet(IÅBAT)det(A)Ædet(AÅB)Ædet(ATÅBT)Ædet(BT)det(BATÅI).Sincedet(A)Æ¡det(B),itfollowsdet(BATÅI)Æ0.Thusdet(AÅB)Æ0.i.e,AÅBissingular.Question1.2.Therankofamatrixisthedimensionofthespacespannedbyitscolumns.ShowthatAhasrankoneifandonlyifAÆabTforsomecolumnvectorsaandb.Remark.Forthisquestiontohold,wehavetoassumethatbothaandbisnot0.Proof.IfAÆabT,letbÆ{b1,b2,...,bn}.PartitionAbycolumnsasAÆ¡®1,®2,...,®n¢.Wehave®iÆbia.Therefore,allcolumnvectorsofAarelineardependentona.Asa,b6Æ0,resultinginA6Æ0.Then,dim¡span¡®1,®2,...,®n¢¢Æ1,i.e.rank(A)Æ1.Ontheotherhand,ifrank(A)Æ1,partitionAbycolumnsasAÆ¡®1,®2,...,®n¢.Withoutlosinganygeneralities,suppose®16Æ0.Becauseofrank(A)Æ1,thereisonlyonelinearinde-pendentcolumnvectorofA,whichmeans®iÆbi®1.DenoteaÆ®1,bÆ¡b1,b2,...,bn¢.Thena,b6Æ0,andAÆabT.Question1.3.Showthatifamatrixisorthogonalandtriangular,thenitisdiagonal.Whatareitsdiagonalelements?2Proof.Withoutlosinganygeneralities,supposeAÆ(aij)isorthogonalanduppertrangular.BecauseAisorthogonal,weget0BBBB@a11a12...a1na22...a2n......ann1CCCCA0BBBB@a11a12a22.........a1na2n...ann1CCCCAÆ0BBBB@a11a12a22.........a1na2n...ann1CCCCA0BBBB@a11a12...a1na22...a2n......ann1CCCCAÆ1.Equatethe(1,1)entry,yieldinga1iƧ±1i.Then,conditionbecomes0BBBB@1a22...a2n......ann1CCCCA0BBBB@1a22......a2n...ann1CCCCAÆ0BBBB@1a22......a2n...ann1CCCCA0BBBB@1a22...a2n......ann1CCCCAÆ1,whichmeansA(2:n,2:n)isorthogonalanduppertriangular.Thus,theresultfollowsbyinduction,andthediagonalentriesare§1.Question1.4.Amatirxisstictlyuppertriangularifitisuppertriangluarwithzerodiagonalelements.ShowthatifAisstrictlyuppertriangularandn-by-nthenAnÆ0.Proof.SupposeBisan-by-nmatrix,andpartitionBbyitscolumnsasBÆ¡b1,b2,...,bn¢.ConsidertheithcolumnofBA,whichis(BA)(:,i)Æi¡1XjÆ1A(j,n)bj.Thus,theithcolumnofBAisthelinearcombinationofthefirsttothe(i¡1)thcolumnsofB.SubsititueBbyA,yieldingthediagonalandfirstsuperdiagonalofA2becomingzero,becauseonlythefirsti¡1entriesofithcolumnofAarenonzeros.Consequently,thesecondsuperdiagonalofA3becomeszero.Inthisananlogy,afterntimes,then¡1superdiagonalofAnbecomeszero,i.e.AnÆ0.Question1.5.Letk¢kbeavectornormonRmandassumethatC2Rm£n.Showthatifrank(C)Æn,thenkxkC´kCxkisavectornorm.Proof.1.Positivedefiniteness.Foranyx2Rn,sincek¢kisavectornorm,wehavekCxk¸0,andifandonlyifCxÆ0,kCxkÆ0.ConsiderthelinearsystemofequationsCxÆ0.BecauseChasfullcolumnrank,theaboveequationshaveonlyzerosolution.Thisprovesthepositivedefinitenessproperty.32.Homogeneity.Foranyx2Rn,®2R,k®xkCÆk®CxkÆj®jkCxkÆj®jkxkC.Thisprovesthehomogeneityproperty.3.Thetriangleinequality.Foranyx,y2Rn,kxÅykCÆkCxÅCyk·kCxkÅkCykÆkxkCÅkykC.Thisprovesthetriangluarinequality.Consequently,thekxkC´kCxkisavectornorm.Question1.6.Showthatif06Æs2RnandE2Rm£n,then°°°°EµI¡ssTsTs¶°°°°2FÆkEk2F¡kEsk22sTs.Proof.SinceEµI¡ssTsTs¶µEµI¡ssTsTs¶¶TÆEµI¡ssTsTs¶ETÆEET¡Es(Es)TsTs,itfollows°°°°EµI¡ssTsTs¶°°°°2FÆtr(EET)¡tr(Es(Es)T)sTsÆkEk2F¡kEsk22sTs.Therefore,thequestionisproved.Remark.Itcouldalsobeprovedbyprojectionproperty,becauseforanyu2Rn,PÆuuT/uTuistheorthogonalprojectionofthesubspacespannedbyu,andI¡Pisitscomplementpro-jection.Question1.7.Verifythatkxy¤kFÆkxy¤k2Ækxk2kyk2foranyx,y2Cn.Proof.BecausetheFrobeniusnormcanbeevaluatedaskAk2FÆtr(AA¤),itfollowskxy¤k2FÆtr(xy¤yx¤)Æ(y¤y)tr(xx¤)Ækyk22kxk22.Fortwo-norm,sincewehavetheequationabouttwo-norm:kAk22Ƹmax(AA¤),subsititueAbyxy¤.Wehavekxy¤k22Ƹmax(xy¤yx¤)Æ(y¤y)¸max(xx¤)Ækyk22¸max(xx¤).Now,whatremainsistodetermine¸max(xx¤).Becausexx¤ishermitian,weget¸2max(xx¤)Æmaxv6Æ0v¤xx¤vv¤vÆmaxv¤vÆ1(v¤x)2,foranyv2C.4AccordingtoCauchy-Schwartzinequality,onlywhenvisproportionaltox,(v¤x)getthegreatestabsolutevalue.Therefore,¸2max(xx¤)·kxk22,andwhenvÆxtheinequalitybecomesequality.Consequently,kxyHk2Ækyk22¸max(xx¤)Ækxk2kyk2.Combiningthetwoeqautionsprovesthequestion.Remark.Ifweregardvectorxandyasn-by-1matrices,bytheconsistancyoftwo-norm,kxyk2·kxk2kyk2holds,andthisupperboundisattainablebyapplyingvectory.Sincewehavenotprovedtheconsistancy,Iusetheabovemethod,instead.Question1.