qr

March10,2004 TheQRFactorization Gaussian elimination, andtheclosely-related LUandPLU factorizations, provideone approac htosolving alinear system Ax=b.Thisapproac hisbased onusing elemen tary matrices, whichsimply implemen trowoperations. Amuchnewerapproac histheQR factorization ,whichisbased onHouseholder matrices. Weareinterested inthisalgorithm because itwillprovidesome niceexamples ofalgorithm developmen tandanalysis. TheHouseholder Matrix Thefollowingdevelopsaspecialutilitymatrix that,liketherowoperation-based matrices, canbeusedtoperform amatrix factorization. Consider amatrix Hoftheform H=IuuT; where Iisthenbynidentitymatrix, uisannby1matrix|basically avector|and is some xedbutunkno wnrealnumber. 4 Compute byhand thematrix Hthatresults fromu=2 41 2 33 5and=1. Nowwewanttogure outhowtopickuandtomakeHespecially nice. First, notethatHissymmetric, nomatter what values uandhave.Toseethis,just usebasicproperties ofthetransp oseoperation, namely (AT)T=A,(A+B)T=AT+BT, (AB)T=BTAT,and(A)T=ATwhere AandBareanymatrices forwhichthegiven operations aredened, andisanyrealnumber. Specically , HT=(IuuT)T=IT(uuT)T=I(uuT)T=I(uT)TuT=IuuT=H: 4 Aretheelemen tarymatrices usedinthePLUfactorization symmetric? Aretheinverses oftheelemen tarymatrices easytocompute? Next, wewanttogure outhowtopicktomakeHhaveaniceinverse. Itturns out thatwecanpicksothatHisitsowninverse,namely HH=I. Thefollowingderivation usesbasic matrix algebra properties, whichsaythatyoucan doalgebra justlikeyou'reusedto,except thatyoumustkeepthings thataremultiplied together inthecorrect order. And,youcancomm utescalars withmatrices freely. Leavingoutalotofbasic algebra steps, wehave HH=(IuuT)(IuuT)=I+(2uTu2)uuT; soifwepicktomake 2uTu2=0; CSI4050 Page1 March10,2004 wehave=0or=2 uTu.Clearly =0doesyieldaniceH,namely H=I,butthat's notveryhelpful, sowetake=2 uTu. Wenowocially dene aHouseholder matrix foragivenvectorutobe H=I2 uTuuuT: 4 Letu=2 41 2 33 5andcompute thecorresp onding Householder matrix. Verifydirectly that HT=HandHH=I. We'realmost donewiththepreliminaries beforewecandene theQRfactorization. Now wereachthecrucial point,namely pickingusothatthecorresp onding Householder matrix \zeroesout"agivencolumn ofamatrix belowthediagonal. Specically ,letv(for\victim," perhaps) beanyvector andassume thatwewanttond aHouseholder matrix HsuchthatHv=2 664 0 ... 03 775: Let'sjustformHvandseeifwecangure outhowtodothis: Hv=(IuuT)v=vuTvu: 4 Thisinnocent-looking calculation alsoshowshowHvcanbeecien tlycomputed for anyvectorv.Ingeneral, whatistheeciency classformultiplying annbynmatrix by annvector? What istheeciency classforthealgorithm suggested bythepreceding calculation? Now,looking attheformulaabove,withourfavoritevalueforplugged in,wehave Hv=v2uTv uTuu: Ifwewantthatquantitytohaveallzeroes,except intherstspot,oneobvious thing suggests itself: takeutomatchvinpositions 2through n,andddle withu1tomakethe scalar equal to1. So,wewanttosolvetheequation 2uTv uTu=1 for,where u=2 664 v2 ... vn3 775: CSI4050 Page2 March10,2004 After some algebraic suering, weobtain theequivalentequation 22v1v2 2:::v2 n=0; whichisaquadratic equation withunkno wnandhasthesolutions =2v1p 4v2 1+4(v2 2+:::+v2n 2: Thissimplies inconvincing fashion to =v1q v2 1+v2 2+:::+v2n: Either solution doeswhat wewantingeneral, sowecanpickthesigntomatchthe signofv1. So,theupshot ofthiswhole discussion isthatifwehaveamatrix Athatwewantto transform, webeginbyforming avectoruthatisidenticaltotherstcolumn ofAexcept intherstposition, where ithastheoriginal valueofAwiththesumofthesquares ofall thecomponentsoftherstcolumn added orsubtracted. Then wetakethatu,compute thecorresp onding ,andtheresulting Histhematrix we multiply Abyzeroitoutbelowthediagonal, justlikeinGaussian elimination. 4 Here's amajorpointofthisdiscussion: howecien tlycanHAbeformed? Should H beformed? Should Hbestored? Then, theprocessisrepeated, justlikeinGaussian elimination, atstepkzeroing out column kofHk1


H2H1Abelowrowk,while leavingrows1through k1unchanged. 4 Verifythatforming uforcolumn kbyputting 0inspots1through k1worksas desired. So,eventually weobtain Hn


H2H1A=R; where Risuppertriangular. Then wemultiply bothsidesrepeatedly byHn,Hn1,ldots, H2,H1,toobtain A=H1H2


HnR anddenote H1H2


HnbyQ,soA=QRasdesired, where Risuppertriangular andQ is,well,whataboutQ? Itturns outthatQ,asaproductofHouseholder matrices, isaverynicematrix, having muchbetterproperties ingeneral thanthematrix LfromGaussian elimination. QhastheverynicepropertythatQTQ=I. 4 Verifythis. CSI4050 Page3 March10,2004 Thismeans thatthecolumns ofQformasetofmutually perpendicular vectors oflength 1 (intheusual Euclidean wayofmeasuring thelength ofavector). Infact,theQRfactoriza- tionisabettermetho dfornding anorthogonal basisforasubspace spanned byagiven setofvectors thanthemucholder andmore famous \Gram Schmidt orthogonalization algorithm." Now,tosolveAx=boncewehaveA=QR,wenotethatwewantAx=QRx=b,so ifwemultiply bothsidesbyQT,wehaveQTQRx=QTb,orRx=QTb.Thus,givena newright-hand sidevectorb,werstformQTb,andthenusebacksubstitution tondx, whichwecandobecause Risuppertriangular. Atthispointyoumightbeexpecting aniceexample workedout,showingthisprocess on,say,a4by4matrix, butyou're notgoing togetit,because there wouldn't bemuch point!Thedeepfacthereisthatthisalgorithm alwaysleadstohorrible numbers,andonly thetiniest ofexamples canbe\rigged" toworkoutdecently.Thiswhole thing isreally anadvertisemen tforyoureducation: bystudying complex algorithms andmathematics indepth, yougaintheabilitytodealwithalgorithms thataresimply tohideous todo byhand. Youcan't understand theQRalgorithm byjustworking through anexample (though working through asmall onewouldhelpalittle), youcanonlyunderstand it through abstract analysis, andbyprogramming itup. 4 Havingsaidallthat,formbyhand theQRfactorization ofthematrix A=2 4221 124=52 27=533 5: While doing this,think abouthowtheQRfactorization processcanbeecien tly implemen ted,andwhatit'seciency classwillbe. So,itturns outthattheQRapproac hiscompetitive,interms ofrun-time eciency ,with Gaussian elimination withpartial pivoting. But,itistypically betterthanthatalgorithm inthepresence ofill-conditioning. Also, itcanbeusedasatoolforother purposes. Asmentioned above,itcanbeusedas apractical alternativ etotheGram-Sc hmidt algorithm. Itprovides atypically superior alternativ etothe\normal equations" when doing least-squares regression. And, itisthe corecomputational elemen tinalgorithms tocompute eigenvalues. CSI4050 Page4