ch2：代数插值1.ppt

第2章插值 Interpolation 当精确函数y f x 非常复杂或未知时 在一系列节点x0 xn处测得函数值y0 f x0 yn f xn 由此构造一个简单易算的近似函数g x f x 满足条件g xi f xi i 0 n 这里的g x 称为f x 的插值函数 最常用的插值函数是 多项式 g x f x 1拉格朗日多项式 LagrangePolynomial n 1 可见P1 x 是过 x0 y0 和 x1 y1 两点的直线 称为拉氏基函数 LagrangeBasis 满足条件li xj ij KroneckerDelta 1LagrangePolynomial n 1 LagrangePolynomial 1LagrangePolynomial 定理 唯一性 满足的n阶插值多项式是存在且唯一的 证明 存在性证明 p 161利用Vandermonde行列式论证 唯一性用反证法 若不唯一 则除了Ln x 外还有另一n阶多项式Pn x 满足Pn xi yi 注 若不将多项式次数限制为n 则插值多项式不唯一 例如也是一个插值多项式 其中可以是任意多项式 1LagrangePolynomial 插值余项 Remainder Rolle sTheorem 若充分光滑 则存在使得 推广 若 使得 Rn x 至少有个根 n 1 x 有n 2个不同的根x0 xnx 注意这里是对t求导 1LagrangePolynomial 注 通常不能确定 x 而是估计 x a b 将作为误差估计上限 当f x 为任一个次数 n的多项式时 可知 即插值多项式对于次数 n的多项式是精确的 Q 给定xi i 1 i 0 1 2 3 4 5 下面哪个是l2 x 的图像 1LagrangePolynomial 解 n 1 分别利用x0 x1以及x1 x2计算 利用 这里 而 sin50 0 7660444 外推 extrapolation 的实际误差 0 0101 利用 内插 interpolation 的实际误差 0 0059 内插通常优于外推 选择要计算的x所在的区间的端点 插值效果较好 1LagrangePolynomial n 2 sin50 0 7660444 2次插值的实际误差 0 0006 高次插值通常优于低次插值 但绝对不是次数越高就越好 嘿嘿 2牛顿插值 Newton sInterpolation 差商 亦称均差 divideddifference 1阶差商 the1stdivideddifferenceoffw r t xiandxj 2阶差商 2Newton sInterpolation k 1 阶差商 Warning myheadisexploding Whatisthepointofthisformula 差商的值与xi的顺序无关 2Newton sInterpolation 牛顿插值 Newton sInterpolation Nn x Rn x ai f x0 xi 2Newton sInterpolation 注 由唯一性可知Nn x Ln x 只是算法不同 故其余项也相同 即 实际计算过程为 f x0 f x1 f x2 f xn 1 f xn f x0 x1 f x1 x2 f xn 1 xn f x0 x1 x2 f xn 2 xn 1 xn f x0 xn f xn 1 f xn xn 1 f xn 1 xn xn 1 f x1 xn 1 f x0 xn 1 2Newton sInterpolation 等距节点公式 FormulaewithEqualSpacing 向前差分 forwarddifference 向后差分 backwarddifference 中心差分 centereddifference 其中 当节点等距分布时 Moregivenonp 174 2Newton sInterpolation 差分的重要性质 线性性质 例如 若f x 是m次多项式 则是次多项式 而 差分值可由函数值算出 函数值可由差分值算出 2Newton sInterpolation 牛顿公式 牛顿前差公式 Newton sforward differenceformula 牛顿后差公式 Newton sbackward differenceformula 将节点顺序倒置 注 一般当x靠近x0时用向前插值 靠近xn时用向后插值 故两种公式亦称为表初公式和表末公式 3埃尔米特插值 HermiteInterpolation 不仅要求函数值重合 而且要求若干阶导数也重合 即 要求插值函数 x 满足 xi f xi xi f xi mi xi f mi xi 注 N个条件可以确定阶多项式 N 1 一般只考虑f与f 的值 3HermiteInterpolation 例 设x0 x1 x2 已知f x0 f x1 f x2 和f x1 求多项式P x 满足P xi f xi i 0 1 2 且P x1 f x1 并估计误差 模仿Lagrange多项式的思想 设 解 首先 P的阶数 3 h0 x 有根 x1 x2 且h0 x1 0 x1是重根 又 h0 x0 1 C0 h2 x h1 x 有根x0 x2 由余下条件h1 x1 1和h1 x1 0可解 与h0 x 完全类似 有根x0 x1 x2 与Lagrange分析完全类似 3HermiteInterpolation 一般地 已知x0 xn处有y0 yn和y0 yn 求H2n 1 x 满足H2n 1 xi yi H 2n 1 xi yi 解 设 hi x 由余下条件hi xi 1和hi xi 0可解Ai和Bi 有根x0 xn 除了xi外都是2重根 这样的Hermite插值唯一 3HermiteInterpolation 斜率 1 求Hermite多项式的基本步骤 根据多项式的总阶数和根的个数写出表达式 根据尚未利用的条件解出表达式中的待定系数 最后完整写出H x 4分段低次插值 piecewisepolynomialapproximation RememberwhatIhavesaid IncreasingthedegreeofinterpolatingpolynomialwillNOTguaranteeagoodresult sincehigh degreepolynomialsareoscillating 例 在 5 5 上考察的Ln x 取 n越大 端点附近抖动越大 称为Runge现象 4PiecewisePolynomialApproximation 分段线性插值 piecewiselinearinterpolation 在每个区间上 用1阶多项式 直线 逼近f x 分段Hermite插值 Hermitepiecewisepolynomials Howcanwemakeasmoothinterpolationwithoutaskingtoomuchfromf Headache 5三次样条 CubicSpline 注 三次样条与分段Hermite插值的根本区别在于S x 自身光滑 不需要知道f的导数值 除了在2个端点可能需要 而Hermite插值依赖于f在所有插值点的导数值 f x H x S x 5CubicSpline 构造三次样条插值函数的三弯矩法 methodofbendingmoment 对每个j 此为3次多项式 则S j x 为次多项式 需个点的值确定之 1 2 设S j xj 1 Mj 1 S j xj Mj 对应力学中的梁弯矩 故名 对于x xj 1 xj 可得到 S j x 积分2次 可得S j x 和S j x 5CubicSpline 下面解决Mj 利用S 在xj的连续性 xj 1 xj S j x xj xj 1 S j 1 x j 1 n 1 即 有个未知数 个方程 n 1 n 1 还需2个边界条件 boundaryconditions 5CubicSpline 第1类边条件 clampedboundary S a y0 S b yn 类似地利用 xn 1 b 上的S n x 第2类边条件 S a y0 M0 S b yn Mn 这时 特别地 M0 Mn 0称为自由边界 freeboundary 对应的样条函数称为自然样条 NaturalSpline 第3类边条件 periodicboundary 当f为周期函数时 yn y0 S a S b M0 Mn 5CubicSpline 注 另有三转角法得到样条函数 即设S j xj mj 则易知 xj 1 xj 上的S j x 就是Hermite函数 再利用S 的连续性 可导出关于mj的方程组 加上边界条件即可解 CubicSpline由bound