《内插和外推方法》PPT课件.ppt

Chapter3 InterpolationandExtrapolation Interpolation Extrapolation xi yi Findananalyticfunctionf x thatpassesthroughgivenNpointsexactly 低级多项式 高级多项式 低级多项式 高级多项式 PolynomialInterpolation UsepolynomialofdegreeN 1tofitexactlywithNdatapoints xi yi i 1 2 N Thecoefficientciisdeterminedbyasystemoflinearequations VandermondeMatrixEquation Butitisnotadvisabletosolvethissystemnumericallybecauseofill conditioning ConditionNumber cond A A A 1 Forsingularmatrix cond A Alinearsystemisill conditionedifcond A isverylarge Norms Vectorp normMatrixnorm sup supremum CommonlyUsedNorms VectornormMatrixnorm Where isthemaximumeigenvalueofmatrixATA Lagrange sFormula ItcanbeverifiedthatthesolutiontotheVandermondeequationisgivenbytheformulabelow li x hasthepropertyli xi 1 li xk 0 k i Joseph LouisLagrange 1736 1813 Italian Frenchmathematicianassociatedwithmanyclassicmathematicsandphysics Lagrangemultipliersinminimizationofafunction Lagrange sinterpolationformula Lagrange stheoremingrouptheoryandnumbertheory andtheLagrangian L T V inmechanicsandLagrangeequations Neville sAlgorithm EvaluateLagrange sinterpolationformulaf x atx giventhedatapoints xi yi InterpolationtableauP x x1 y1 P1P12x2 y2 P2P123P23P1234x3 y3 P3P234P34x4 y4 P4 Pi i 1 i 2 i nisapolynomialofdegreeninxthatpassesthroughthepoints xi yi xi 1 yi 1 xi n yi n exactly DetermineP12fromP1 P2 GiventhevalueP1andP2atx x1andx2 wefindlinearinterpolationP12 x x P1 1 x P2SinceP12 x1 P1andP12 x2 P2 wemusthave x1 1 x2 0so x 12 x x2 x1 x2 DetermineP123fromP12 P23 WewriteP123 x x P12 x 1 x P23 x P123 x2 P2alreadyforanychoiceof x WerequirethatP123 x1 P12 x1 P1andP123 x3 P23 x3 P3 thus x1 1 x3 0Or RecursionRelationforP Giventwom pointinterpolatedvaluePconstructedfrompointi i 1 i 2 i m 1 andi 1 i 2 i m thenextlevelm 1pointinterpolationfromitoi misaconvexcombination UseSmallDifferenceC D P1 P2 P3 P4 P12 P23 P34 P123 P234 P1234 C1 1 P12 P1 D1 1 C1 2 C1 3 D1 2 D1 3 C2 1 P123 P12 C2 2 D2 1 C3 1 P1234 P123 D3 1 P1234 P234 D2 2 P234 P34 DerivingtheRelationamongC D P PA 1 PB PA PB P0 C2 P PA C1 PB P0 D2 P PB D1 PA P0 EvaluateP 3 given4 points 0 1 1 2 2 3 4 0 P1234 11 4 C1 1 3 D1 1 2 C1 2 2 C1 3 3 2 D1 2 1 D1 3 3 2 C2 1 0 C2 2 5 3 D2 1 0 C3 1 5 4 D3 1 5 12 D2 2 5 6 x1 0 y1 1 P1 x2 1 y2 2 P2 x3 2 y3 3 P3 x4 4 y4 0 P4 C0 1 1 D0 1 1 C0 2 2 D0 2 2 C0 3 3 D0 3 3 D0 4 0 C0 4 0 polint Program polint continued Subroutinepolint xa ya n x y dy Integern nmaxParameter nmax 10 Integeri m nsRealden dif dift ho hp w c nmax d nmax Ns 1Dif abs x xa 1 Do11i 1 nDift abs x xa i If dift lt dif thenNs iIdf diftEndif C i ya i D i ya i Enddo11Y ya ns Ns ns 1Do13m 1 n 1Do12i 1 n mHo xa i xHp xa i m xW c i 1 d i Den ho hpIf den eq 0 pause failureinpolint Den w den D i hp denC i ho denEnddo12If 2 ns lt n m thenDy c ns 1 ElseDy d ns Ns ns 1EndifY y dyEnddo13Returnend PiecewiseLinearInterpolation x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 P12 x P23 x P34 x P45 x x y PiecewisePolynomialInterpolation x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 P1234 x P1234 x P2345 x P2345 x x y Discontinuousderivativesacrosssegment CubicSpline GivenNpoints xi yi i 1 2 N foreachintervalbetweenpointsitoi 1 fittocubicpolynomialssuchthatPi xi yiandPi xi 1 yi 1 Make1stand2ndderivativescontinuousacrossintervals i e Pi n xi 1 P n i 1 xi 1 n 1and2 FixboundaryconditiontoP x1orN 0 orP x1orN const tocompletelyspecify CurveFittingbyInterpolation 2 WenowdiscussInterpolation ExtrapolationThefunctionpassesthroughall oratleastmost points CurveFitting 1 WehavediscussedLeast SquaresRegressionwherethefunctionis bestfit topointsbutdoesnotnecessarilypassthroughthepoints CurveFittingbyInterpolation C Ccoversfourapproaches Polynomials C C18 1 18 5 skim only n 1equations n 1unknownsLagrangePolynomialsNewton sDividedDifference NDD PolynomialsSplines C C18 6 assignedreading Thefirst3approachesfindthesamepolynomial Wewillonlycoversuperficially andconcentrateonSplines CurveFittingbyInterpolation GeneralSchemeGiven Setofpoints xi yi notnecessarilyevenlyspacedorinascendingorder Assume x independentvariable y dependentvariable Find y f x atsomevalueofxnotintheset xi Method Determinethefunctionf x whichpassesthroughall ormost points n 1Equationsandn 1Unknowns C C18 3 Givenn 1datapoints xi yi findannthorderpolynomial y a0 a1x a2x2 anxnthatwillpassthroughallthepoints Toomuchwork Equationsarenotoriouslyill conditionedforlargen Equationsarenotdiagonallydominant Methodisrarelyused LagrangeInterpolatingPolynomials C C18 2 Givenn 1datapoints xi yi findthenthorderpolynomial y pn x a0 a1x a2x2 anxnthatpassesthroughallofthepoints TheLagrangianpolynomialsapproachemploysasetofnthorderpolynomials Li x suchthat whereLi x satisfiesthecondition Newton sDividedDifference NDD Polynomial C C18 1 GivesthesamepolynomialastheLagrangemethodbutiscomputationallyeasier Generalformforn 1datapoints pn x b0 b1 x x0 b2 x x0 x x1 bn x x0 x x1 x x2 x xn 1 withb0 b1 bnallunknown Notethatithtermiszeroatxjforj i Eachterminsuresthatthepolynomialcorrectlyinterpolatesatonenewpoint Thealgorithmisrecursiveandreadilysuitedforspreadsheetorotherprogrammedcalculation Newton sDividedDifferences NDD versusLagrangePolynomials 1 Bothmethodsgivethesameresults 2 ComparisonbasedonacountoftheFLOPS Evaluatecoefficients Interpolateforonex Lagrange n 1 n 1 n2 n 1 n 1 n2NDD n 1 n 1 2 n2 2n3 EasytoaddanodewithNDD NeedtostartoverwithLagrange 4 Bothmethodsshareamajorproblem asthenumberofpointsincreases sodoestheorderofpolynomial Thismaycauseexcessive wiggles or waves betweenpoints Splines C C18 6 Issue Needtoovercomethe wiggle or wave problemIdea UseapiecewisepolynomialapproximationSimplestidea Straightlineoneachsegment Theproblemisthatg x andg x arediscontinuous Splines cont Mostfrequentlyused CubicSplines SeparateCubicpolynomialoneachinterval Thisistheanalytical numericalanalogofaflexibleedge spline whichisusedbydraftsmen Withthistoolthefirstandsecondderivatives curvature arecontinuous andthefunctionappears smooth CubicSplines Objective Definea3rd orderpolynomialforeachinterval fi x aix3 bix2 cix diForn 1datapoints x0 y0 x1 y1 xn yn therearenintervalswith4unknownsperinterval ai bi ci anddi Total4nunknowns n 3 3segments n 1points Weneed4nequationstocomputeall4unknownsforeachinterval CubicSplines Howdoweobtaintherequired4nequations functionsmustpassthroughfi x atknots points yi 1 ai xi 1 3 bi xi 1 2 ci xi 1 diyi ai xi 3 bi xi 2 ci xi di 2equations interval 2n 1stand2ndderivativesmustbeequalatinteriorknots xi yi 3ai xi 2 2bixi ci 3ai 1 xi 2 2bi 1xi ci 16aixi 2bi 6ai 1xi 2bi 1 2equations interiorknot 2n 2 TOTAL 2n 2n 2 4n 2 CubicSplines Weneedanextra2conditionsforCubicSplinesNaturalSplinesSettingthe2ndderivativesatexteriorknotsequaltozeroallowsthefunctionto relax 0 6a1x0 2b1 0 6anxn 1 2bn 1equations exteriorknot 2 TOTAL 2n 2n 2 2 4n CubicSplines Alternativesfortwoextraconditions insteadofsetting2ndderivative 0 1 Specify1stderivativesatexteriorknots f x0 3a1x02 b1x0f xn 1 3anxn 12 bnxn 12 Addanextrapointtothefirstandlastintervalsthroughwhichsplinemustpass not a knotsplines CubicSplinesComputation Ifsetupcleverly the4nx4nsystemofequationscanbereducedtosolvingan n 1 x n 1 tridiagonalsystemofequations Defineanewsetofunknowns Letsi f xi bethesecondderivativeofthecubicsplineatinteriorpointi i 1 n 1 Firstsetupthen 1equationstosolveforcurvatures f x ateachoftheinteriorknots seeC CBox18 3 xi xi 1 si 1 2 xi 1 xi 1 si xi 1 xi si 1 NaturalCubicSplines Convenienttridiagonalequationsfornaturalsplines Thesebasicequationsforthesecondderivativescanalsobewrittenintermsofthedistanceshi xi 1 xi betweenthepointsorknotsandofyi f xi Fori 0 s0 0 naturalsplinecondition Fori 1 2 h0 h1 s1 h1s2 RHS1Fori 2ton 2 hi 1si 1 2 hi 1 hi si hisi 1 RHSiFori n 1 hn 2sn 2 2 hn 2 hn 1 sn 1 RHSn 1Fori n sn 0 naturalsplinecondition NaturalCubicSplines Notingthatthisisatriangularbandedsystemofequationsofordern 1 wesolvewithamethodwhichtakesadvantageofthis i e theThomasalgorithmgiveninC CSection11 1 Solvethetriangularbandedsystem e g forn 7lookslike s1s2s3s4s5s6xx xxx xxx xxx xxx xx CubicSplineInterpolation Ifwewanttofindspecificinterpolants wedonotneedtodeterminethecubicfunctionsinalloftheintervals ratherjusttheintervalinwhichthexlies Fortheithintervalspanning xi 1 xi fi x ai x xi 1 3 bi x xi 1 2 ci x xi 1 diinwhich di yi 1 Obtainadifferentcubicpolynomialforeachinterval xi 1 xi However firstneedtosolveforthevaluesofallthesi NaturalCubicSplines Example Setupequationstosolvefortheunknowncurvaturesateachinteriorknotforthefollowingdata xi xi 1 si 1 2 xi 1 xi 1 si xi 1 xi si 1 Splines Example cont d Fori 1 2 1 s0 2 3 1 s1 3 2 s2 or4s1 s2 12Fori 2 s1 6s2 2s3 36Fori 3 2s2 6s3 90 Splines Example cont d Solvebyanyappropriatemethod e g Thomasalgorithm EngineeringComputationCurveFitting Interpolation48 Splines Example cont d Nowestimatef 2 4 byusingthespline Weneedonlysolvefortheith 2ndinterval i e x1 2 x x2 3 f2 x a2 x x1 3 b2 x x1 2 c2 x x1 d2 EngineeringComputationCurveFitting Interpolation49 Splines Example cont d Solving f2 x a2 x x1 3 b2 x x1 2 c2 x x1 d2 d2 f x1 4 00f2 2 4 0 377 2 4 2 3 1 43 2 4 2 2 0 202 2 4 2 4 00 4 29 x 0 10 y sin x xx 0 0 25 10 yy spline x y xx plot x y o xx yy Splines ExampleinMatlab x 0 10 y sin x xx 0 0 25 10 yy spline x 0y0 xx plot x y o xx yy npts 10 xy randn 1 npts randn 1 npts plot xy 1 xy 2 ro LineWidth 2 forn 1 npts text xy 1 n xy 2 n num2str n endset gca XTick YTick cv cscvn xy fnplt cv r 2 fnplt cscvn xy r 2