Analysis of the finite precision Bi-Conjugate Grad

ANALYSISOFTHEFINITEPRECISIONBI-CONJUGATEGRADIENTALGORITHMFORNONSYMMETRICLINEARSYSTEMSCHARLESH.TONGyANDQIANGYEzAbstract.InthispaperweanalyzetheBiCGalgorithminniteprecisionarithmeticandsuggestreasonsforitsoftenobservedrobustness.Byusingatridiagonalstructure,whichispreservedbytheniteprecisionBiCGiteration,weareabletobounditsresidualnormbyaminimumpolynomialofaperturbedmatrix(i.e.theexactGMRESresidualnormappliedtoaperturbedmatrix)multipliedbysomeamplicationfactors.Furthermore,thesameanalysiscanbeappliedtotheCGalgorithmandweareabletorelatetheslowingdownofconvergencetolossoforthogonalityinniteprecisionarithmetic.Finally,numericalexamplesaregiventogaininsightsintothesebounds.Keywords.Bi-conjugategradientalgorithm,erroranalysis,convergenceanalysis,nonsymmet-riclinearsystemsAMSsubjectclassications.65F10,65N201.Introduction.SinceitsintroductionbyLanczos[14]andlaterre-discoverybyFletcher[5]initspresentform,thebi-conjugategradient(BiCG)algorithmhasevolvedmanyvariations(e.g.CGS,BiCGSTAB,QMR,CSBCG[19,21,6,2]),eachofwhichwasspeciallydesignedtoovercomesomeofitsinherentdiculties(theneedforadjointmatrixvectorproduct,potentialbreakdowns,erraticconvergencebehavior,etc.).However,ithasbeenobservedbyBankandChan[2]andTong[20]that,inniteprecisionarithmetic,BiCGremainscompetitive(intermsofconvergenceandconvergencerates),especiallywhencoupledwithnoorrelativelypoorpreconditioners.OneofmajorconcernsinusingBiCGisthetwotypesofpotentialbreakdownproblems,whichcancausenumericalinstability.Inaddition,inniteprecisionarith-meticthebiorthogonalityislost,asisexperiencedbyotherLanczos-typealgorithms.Inspiteofthesediculties,BiCGoftenexhibitsexceptionalnumericalrobustnessinpractice[2,20].Ontheotherhand,convergenceofthepreconditionedconjugategradientmethodwithinexactmatrix-vectormultiplicationhasbeenobservedandstudiedbyGolubandOverton[7,8]inthecontextofinner-outeriterations.ItseemsthattheconvergenceoftheBiCG(orCG)residualsisnotsensitivetoperturbationsintherecurrence.However,thereisnotheoreticalresulttoexplainsuchrobustness.ThepresentpaperaddressestheconvergencebehaviorofBiCGinniteprecisionarithmetic.Intheexactarithmetic,approximationboundsonerrors(orresiduals)inthequantitiescomputedbytheBiCGprocesshavebeenobtainedbyBankandChan[2].ItwasalsoshownrecentlybyBarthandManteufel[15]thattheBiCGresidualin-deedgivesoptimalapproximationfromKrylovsubspacesconsideredincertainnorm.Sinceprovingtheseresults[2]reliesontheGalerkincondition(i.e.,bi-orthogonality),ThisversionisdatedAugust30,1995.yAddress:Dept.ofMathematics,TheHongKongUniversityofScienceandTechnology,ClearWaterBay,HongKong.E-mail:[e-mail]:Dept.ofAppliedMathematics,UniversityofManitoba,Winnipeg,Manitoba,CanadaR3T2N2.E-mail:[e-mail]alSciencesandEngineeringResearchCouncilofCanada.PartofthisworkwascompletedwhilethisauthorvisitedStanfordUniversityduringthesummerof1995.HewouldliketothankProfessorGeneGolubforprovidingthisopportunityandforhisgreathospitality.1whichislostinniteprecisionarithmetic,itisdiculttogeneralizetheseanalysestotheniteprecisioncase.Furthermore,occurrenceofnear-breakdownmayresultinsignicantdeviationoftheniteprecisionBiCGiterationfromtheexactone.Inthispaper,weshallproveaposterioriresidualboundssimilartothosein[2],usinganapproachthatisbasedonatridiagonalstructureimplicitinthealgorithm.ThisapproachwasalsousedbyYe[23]toanalyzeconvergenceoftheLanczosalgorithmsfortheeigenvalueproblems.Anadvantageofthisapproachisthatourboundsincludetheniteprecisioncaseandthenear-breakdowncase,andexplainitsconvergence,possiblyinthepresenceoflargeroundoerrors.WealsoapplyourtechniquetotheniteprecisionCGalgorithmandobtainanewconvergencebound.Finiteprecisionanalysesofconjugategradient-typeandLanczos-typealgorithmshaveplayedanimportantroleinunderstandingthesealgorithms.PioneeringworksareduetoC.Paige[17]forthesymmetricLanczosalgorithmandA.Greenbaum[10]fortheclassicalconjugategradientalgorithmaswellasthesymmetricLanczosalgorithm.Paigeshowedin[17]thatthelossoforthogonalitycomeswithbutdoesnotpreventconvergenceoftheRitzvalues,i.e.usefulresultscanstillbeobtainedfromthealgorithmevenwhentheiteratesdeviatesignicantlyfromwhatwouldhavebeenproducedinexactarithmetic.AgeneralizationtothenonsymmetriccasewasgivenbyBai[1]andnearbreakdownsandlossofbiorthogonalitywerediscussedbyDay[3].Greenbaumestablishedbackwardstabilityresultsinageneralizedsense[10],showingthattheiterativeresidualsproducedbytheniteprecisionconjugategradient(ortheLanczosvectorsinthesymmetricLanczosalgorithm)areequivalenttowhatwouldhavebeenproducedbyapplyingtheexactCGtoalargermatrix.Thusthebehavioroftheniteprecisioncasecanbeunderstoodfromwhatweknowintheexactcase(cf[12]).Someestimatesonthelargermatrixweregivenbutmayvaryfromsteptostep.WeremarkthatitisnecessarytoconsiderthebackwardstabilityinthisnewsensebecauseCGisnotbackwardstableintheclassicalsense.ItwouldbeinterestingtoseeifGreenbaum’sbackwardstabilityresultscanbegeneralizedtoBiCGandweare