An Optimal Algorithm for the Local Solution of Int

LecturesinAppliedMathematicsVolume00,19xxAnOptimalAlgorithmfortheLocalSolutionofIntegralEquationsKarinFrankAbstract.ThelocalsolutionproblemofmultivariateFredholmintegralequa-tionsisstudied.RecentresearchprovedthatforseveralfunctionclassesthecomplexityofthisproblemiscloselyrelatedtotheGelfandnumbersofsomecharacterizingoperators.ThegeneralizationofthisapproachtothesituationofarbitraryBanachspacesisthesubjectofthepresentpaper.Furthermore,aniterativealgorithmisdescribedwhich{undersomeadditionalconditions{realizestheoptimalerrorrate.Thewaythesegeneraltheoremsworkisdemon-stratedbyapplyingthemtointegralequationsinaSobolevspaceofperiodicfunctionswithdominatingmixedderivativeofvariousorder.Thereby,theex-actrateofinformationcomplexityisderived,andanimplementableoptimalalgorithmisformulated.1.IntroductionFredholmintegralequationsofthesecondkindappearinmanyphysicalapplica-tions,e.g.inboundaryvalueproblems.Localsolutionofintegralequationsmeansthatinsteadofthesolutionfunctiononthewholedomainonlythevalueofasinglelinearfunctionalappliedtoitistobecomputed.Thismaybee.g.thevalueinasinglepoint,somesinglebasiscoecientofthesolutionfunctionoraweightedmean.Usually,innumericalapplicationswedonothavefullinformationaboutboththekernelfunctionandtherighthandside,butratherpartialinformationsuchaspointvaluesorasetofbasiscoecients.Information{basedcomplexitytheoryconsidersthissituation,studyingthequestionhowmanyinformationandoperationsareatleastrequiredtondanapproximationtothesolutionwithanerrorofatmost.Thisquantity,whichiscalled{complexity,characterizestheintrinsicdicultyofanumericalproblem.LocalsolutionofFredholmintegralequationswasrstconsideredbyHeinrich[7],lateronbyFrankandHeinrich[5],[3].Inthesepapers,foreachspecialfunctionclasssimilartheoremswereshownstatingtheequivalenceofthen{thminimalradiusofinformationtoGelfandnumbersofsomeoperators(fordenitionssee1991MathematicsSubjectClassication.Primary65Y20,45L10;Secondary47B06,45B05.c0000AmericanMathematicalSociety0075-8485/00$1.00+$.25perpage12KARINFRANKsections2and3).Furthermore,forseveralfunctionclassesalgorithmswerefoundrealizingtheoptimalerror,whichbaseoncommonprinciples.Similaralgorithmsprovedtobeoptimalalsoforthefullsolutionproblemincertainfunctionclasses(see[2],[4]).Itseemedtobequitenaturaltotrytogeneralizethisapproachtoawiderclassofequations.Thisistheaimofthepresentpaper.Thepaperleadsoutasfollows:Insection2,theproblemisformulatedinthesettingofinformation{basedcomplexity.Therealsothemostimportantdenitionsarerecalled.Insection3,undersomeverygeneralassumptionstheequivalenceofthen{thminimalradiusofinformationandtheGelfandnumbersofthreeoperatorscharacterizingtheproblemisshown.Aniterativealgorithmisproposedinsection4whoseoptimalityinthesenseofinformationcomplexityisshowninsection5undercertainadditionalconditions.ThesegeneralresultsareappliedtoFredholmintegralequationsofthesecondkindinSobolevspacesofperiodicfunctionswithdominatingmixedderivativeHr1;:::;rd([0;1]d)insection6,wheretheexactorderofthen{thminimalradiusofinformationisderived.Moreover,thegeneralschemeofaniterativealgorithmformulatedinsection4isconcretizedandanimplementableoptimalalgorithmforthisfunctionclassisgiven,whichisbasedonahyperboliccrossapproximationofthekernelfunction.2.FormulationoftheproblemLetV,EandKbeBanachspaces.Asusual,forthespaceofallboundedlinearoperatorsfromVintoEweshallwriteL(V;E),andL(E)=L(E;E).EdenotesthedualspacetoE,BEtheunitballinE.WeassumethatViscontinuouslyembeddedintoE,i.e.thereexistsalinearandcontinuousembeddingoperatorJV:V!E.Moreover,thereissomelinearcontinuousoperatorTassigningtoeachelementk2KanoperatorTk2L(E).WeconsidersuchsubsetsV0V,K0K,thattheoperator(ITk)1:E!Eisboundedforanyk2K0.HereandfurtherIdenotestheidentityoperator.SettingX0=K0V0westudytheclassofoperatorequationsuTku=f;(k;f)2X0:(1)Theproblemhastobeformulatedwithintheframeworkofinformation{basedcom-plexitytheory(IBC).Hereonlythemostimportantdenitionsareoutlined,formoredetailsthereaderisreferredto[11].Insteadofsearchingthesolutionuofequation(1)onthewholedomain,weareinterestedonlyinthevalueofonesinglefunctional2Eappliedtothesolutionu2E.Thisproblemsettingiscalledlocalsolutionoftheoperatorequation(1).Inspecialcases,whenV;Earefunctionspaces,thefunctionalcanbee.g.at0{functionalwhichgivesthevalueofuinasinglepointt0,oraweightedmean,orasinglecoecientintherepresentationofuinsomebasisinE.TheoperatorS:X0!IRdenedasS(k;f)=h(ITk)1f;i(2)iscalledthelocalsolutionoperatorofequation(1).Usually,wehavenofullinformationaboutthedatak2K0,f2V0,butonlypartialinformation.Weassume,thatwearegivenlinearinformationabout(k;f)2X0,ANOPTIMALALGORITHMFORTHELOCALSOLUTIONOFINTEGRALEQUATIONS3sowedenetheinformationoperatorN=(N;M),N:X0!IRn1+n2asNk=(hk;ii)i=1;::;n1;i2K;Mf=(hf;ii)i=1;::;n2;i2V:(3)Anyoperator’:IRn1+n2!IRiscalledanalgorithmassigninganapproximatesolution’(N(k;f))toanyinformationvectorN(k;f).Theerrorofanalgorithm’:IRn1+n2!IRisdenedastheworst{caseerrore(S;N;’)=sup(k;f)2X0jS(k;f)’(N(k;f))j:AnessentialquantityinIBCistheso{calledradi