中南大学数值分析介绍

InterpolationInterpolationInterpolationisimportantconceptinnumericalanalysis.Quiteoftenfunctionsmaynotbeavailableexplicitlybutonlythevaluesofthefunctionatasetofpoints.InterpolationInterpolationisimportantconceptinnumericalanalysis.Quiteoftenfunctionsmaynotbeavailableexplicitlybutonlythevaluesofthefunctionatasetofpoints.Thevaluesforf(xi)maybetheresultsfromaphysicalmeasurement(conductivityatdifferentpointsaroundUWI)InterpolationItmayalsobefromsomelongnumericalcalculationwhichcan’tbeputintoasimpleequation.InterpolationItmayalsobefromsomelongnumericalcalculationwhichcan’tbeputintoasimpleequation.Whatisrequiredisthatweestimatef(x)!i.e.Drawasmoothcurvethroughxi.InterpolationThemethodofestimatingbetweentwoknownpoints(values)iscalledinterpolation.Whileestimatingoutsideofknowvaluesiscalledextrapolation.InterpolationInterpolationiscarriedoutusingapproximatingfunctionssuchas:PolynomialsTrigonometricfunctionsExponentialfunctionsFouriermethodsInterpolationTheoryYesapproximatebutwhatisagoodapproximation?Clearlyagoodapproximationshouldbe,suchthattheerrorbetweenthetruefunctionandtheapproximationfunctionshouldbeverysmall.Otherthanthisapproximatingfunctionsshouldhavethefollowingproperties:ThefunctionshouldbeeasytodetermineItshouldbeeasytodifferentiateItshouldbeeasytoevaluateItshouldbeeasytointegrateTherearenumeroustheoremsonthesortsoffunctions,whichcanbewellapproximatedbywhichinterpolatingfunctions.Generallythesefunctionsareoflittleuse.Therearenumeroustheoremsonthesortsoffunctions,whichcanbewellapproximatedbywhichinterpolatingfunctions.Generallythesefunctionsareoflittleuse.Thefollowingtheoremisusefulpracticallyandtheoreticallyforpolynomialinterpolation.WeierstrassApproximationTheorem

WeierstrassApproximationTheoremIff(x)isacontinuousreal-valuedfunctionon[a,b]thenforany>0,thenthereexistsapolynomialPnon[a,b]suchthat|ƒ(x)–Pn(x)|<forallx[a,b].WeierstrassApproximationTheoremThistellsusthat,anycontinuousfunctiononaclosedandboundedintervalcanbeuniformlyapproximatedonthatintervalbypolynomialtoanydegreeofaccuracy.Howeverthereisnoguaranteethatwewillknowf(x)toanaccuracyforthetheoremtohold.WeierstrassApproximationTheoremConsequently,anycontinuousfunctioncanbeapproximatedtoanyaccuracybyapolynomialofhighenoughdegree.PolynomialApproximationPolynomialssatisfyauniquenesstheorem:Apolynomialofdegreenpassingexactlythroughn+1pointsisunique.Thepolynomialthroughaspecificsetofpointsmaytakedifferentforms,butallformsareequivalent.Anyformcanbemanipulatedintoanotherformbysimplealgebraicrearrangement.PolynomialApproximationTheTaylorseriesisapolynomialofinfiniteorder.Thus

ƒ(x)=ƒ(x0)+ƒ'(x0)(x-x0)+1/2!ƒ''(x0)(x-x0)2+..Howeveritisimpossiblecomputationallytoevaluateaninfinitenumberofterms.PolynomialApproximationTaylorpolynomialofdegreenisthereforeusuallydefinedas

ƒ(x)=Pn(x)+Rn

+1(x)wheretheTaylorpolynomialPn(x)andtheremaindertermRn

+1(x)aregivenby

Pn(x)=ƒ(x0)+ƒ'(x0)(x-x0)+…+1/n!ƒn(x0)(x-x0)n

Rn

+1(x)=1/(n+1)!ƒn+1(ξ)(x-x0)n+1wherex0≤ξ<x.PolynomialApproximationTheTaylorpolynomialisatruncatedTaylorseries,withanexplicitremainder,orerrorterm.TheTaylorpolynomialcannotbeusedasanapproximatingfunctionfordiscretedata,becausethederivativesrequiredinthecoefficientscannotbedetermined.Itdoeshavegreatsignificance,however,forpolynomialapproximationbecauseithasanexpliciterrorterm.PolynomialApproximationWhenapolynomialofdegreen,Pn(x),isfittedexactlytoasetofn+1discretedatapoints,(x0,f0),(x1,f1),…,(xn,fn),thepolynomialhasnoerroratthedatapointsthemselves.However,atthelocationsbetweenthedatapoints,thereisanerror,whichisdefinedby

E(x)=ƒ(x)-Pn(x)Thiserrortermhastheform

E(x)=1/(n+1)!(x-x0)(x–x1)…(x–xn)ƒn+1(ξ);x0≤ξ≤x.InterpolationInPracticeInterpolatingPolynomialsInterpolatingPolynomials

Supposewearegivensomevalues,theprincipleisthatwefitapolynomialcurvetothedata.Thereasonforthisisthatpolynomialsarewell-behavedfunctions,requiringsimplearithmeticcalculations.InterpolatingPolynomials

Approximatingpolynomial(interpolatingpolynomial)shouldpassthroughalltheknownpoints.Whereitdoesnotpassthroughthepointsitshouldbeclosetothefunction.InterpolatingPolynomials

Approximatingpolynomial(interpolatingpolynomial)shouldpassthroughalltheknownpoints.Whereitdoesnotpassthroughthepointsitshouldbeclosetothefunction.

Truefunction Approx1 Approx2InterpolatingPolynomials

Notethattheinterpolatingpolynomialmaymisspointsofdiscontinuity.ThereisonlyoneinterpolatingpolynomialP(xi)orlessthatmatchestheexactvalues;f(x0),f(x1),…,f(xn)atn+1distinctbasepoints.

Truefunction Approx1 Approx2InterpolatingPolynomials

UsingPolynomialstoapproximateafunctiongivendiscretepointsInterpolatingPolynomials

Wewillbelookingattwointerpolatingmethods:LagrangeInterpolationDividedDifferenceLagrangeInterpolationLagrangePolynomials

AstraightforwardapproachistheuseofLagrangepolynomials.TheLagrangePolynomialmaybeusedwherethedatasetisunevenlyspaced.LagrangePolynomials

Theformulausedtointerpolatebetweendatapairs(x0,f(x0)),(x1,f(x1)),…,(xn,f(xn))isgivenby,WherethepolynomialPj(x)isgivenby,LagrangePolynomials

Ingeneral,LagrangePolynomials

Considerthetableofinterpolatingpointswewishtofit.ixf(x)0x0f(x0)1x1f(x1)2x2f(x2)3x3f(x3)LagrangePolynomials

Theinterpolationpolynomialis,ixf(x)0x0f(x0)1x1f(x1)2x2f(x2)3x3f(x3)LagrangePolynomials

LagrangePolynomials

NotethattheLagrangianpolynomialpassesthrougheachofthepointsusedinitsconstruction.Advantages

TheLagrangeformulaispopularbecauseitiswellknownandiseasytocode.Also,thedataarenotrequiredtobespecifiedwithxinascendingordescendingorder.Disadvantages

AlthoughthecomputationofPn(x)issimple,themethodisstillnotparticularlyefficientforlargevaluesofn.Whennislargeandthedataforxisordered,someimprovementinefficiencycanbeobtainedbyconsideringonlythedatapairsinthevicinityofthexvalueforwhichPn(x)issought.ThepriceofthisimprovedefficiencyisthepossibilityofapoorerapproximationtoPn(x).

DiagramshowingInterpolation(incrementallyfromoneto5points)Newton’sDivideddifferencesNewton’sDivideddifferencesThenthdegreepolynomialmaybewritteninthespecialform:

Newton’sDivideddifferencesThenthdegreepolynomialmaybewritteninthespecialform:IfwetakeaisuchthatPn(x)=ƒ(x)atn+1knownpointssothatPn(xi)=ƒ(xi),i=0,1,…,n,thenPn(x)isaninterpolatingpolynomial.Newton’sDivideddifferencesAdivideddifferenceisdefinedasthedifferenceinthefunctionvaluesattwopoints,dividedbythedifferenceinthevaluesofthecorrespondingindependentvariable.Thus,thefirstdivideddifferenceatpointisdefinedas

Newton’sDivideddifferencesThus,thefirstdivideddifferenceatpointisdefinedas

Theseconddifferenceisgivenas:Ingeneral,Newton’sDivideddifferencesAdivideddifferencetable.Newton’sDivideddifferencesOnewithactualvalues.Newton’sDivideddifferencesThe3rddegreepolynomialfittingallpointsfromx0=3.2tox3=4.8isgivenbyP3(x)=22.0+8.400(x-3.2)+2.856(x-3.2)(x-2.7)–0.528(x-3.2)(x-2.7)(x-1.0)The4thdegreepolynomialfittingallpointsisgivenbyP4(x)=P3(x)+0.256(x-3.2)(x-2.7)(x-1.0)(x-4.8)Theinterpolatedvalueatx=3.0givesP3(x)=20.2120.Newton’sDivideddifferencesTherearetwodisadvantagestousingtheLagrangianinterpolationpolynomialforinterpolation.Itinvolvesmorearithmeticoperationsthandoesthedivideddifferences.2.Ifwedesiretoaddorsubtractapointfromthesettoconstructthepolynomial,weessentiallyhavetostartoverinthecomputat