插值法第一次newPPT课件

1 第二章插值 INTERPOLATION 法 了解插值的概念 掌握拉格朗日 Lagrange 插值法及其余项公式 了解均差的概念及基本性质 掌握牛顿插值法 了解差分的概念 会牛顿前插公式 后插公式 会埃尔米特 Hermite 插值及其余项公式 知道高次插值的病态性质 会分段线性插值和分段埃尔米特插值及其误差和收敛性 会三次样条插值 知道其误差和收敛性 2 问题实例 更一般情况 问题 需要计算函数的近似关系表达式 在未知点的函数值 条件 一组有函数关系的自变量和因变量的测量数据 3 本节课主要内容 插值问题的描述Lagrange插值多项式的存在唯一性 构造形式 基函数性质误差分析应用 4 描述事物之间的数量关系 函数 有两种情况 一是表格形式 一组离散的数据来表示函数关系 另一种是函数虽然有明显的表达式 但很复杂 不便于研究和使用 从实际需要出发 对于计算结果允许有一定的误差 可以把函数关系用一个简单的便于计算和处理的近似表达式来代替 从而使问题得到简化 一般地 构造某种简单函数代替原来函数 插值法就是一种基本方法 0引言 5 当精确函数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 6 1 1 设函数在区间上有定义 且已知在点上的值 若存在一简单函数 使 成立 就称为的插值函数 点称为插值节点 包含节点的区间称为插值区间 求插值函数的方法称为插值法 2 1 1插值问题的提出 7 1 2 若是次数不超过的代数多项式 其中为实数 就称为插值多项式 相应的插值法称为多项式插值 本章只讨论多项式插值与分段插值 若为分段的多项式 就称为分段插值 若为三角多项式 就称为三角插值 即 插值函数 Lagrange Newton Hermite Spline 8 由此可以得到关于系数的元线性方程组 上的函数值 求次数不超过的多项式 使 2 1 2多项式插值 1 3 设在区间上给定个点 9 1 4 此方程组的系数矩阵为 称为范德蒙德 Vandermonde 矩阵 由于互异 故 1 5 10 因此线性方程组 1 4 的解存在且唯一 定理1满足条件 1 3 的插值多项式是存在唯一的 证明 11 1拉格朗日多项式 n 1 可见P1 x 是过 x0 y0 和 x1 y1 两点的直线 1 1线性插值 两点式 点斜式 解的存在唯一性 12 1 2二次插值 n 2 为求P2 x 将三点代入其表达式 即可得到三个方程式 从而联立方程组解出系数a0 a1 a2即可 方程组的解是否存在 若存在解 是否唯一 当x0 x1 x2互异时 方程组的解存在且唯一 注 显然有 求n次插值时 由n 1个点可有n 1个方程 联立方程组即可求出插值多项式的n 1个系数 然而 方程组的求解也并不是一件容易的事 1 2 1待定系数法 13 对于线性插值的两种形式解进行适当的分析 从中寻求规律而得到启发 就有了所谓的拉格朗日插值法 公式 和牛顿插值 公式 我们先来看看如何得到二次拉格朗日插值公式 和牛顿插值公式 为讨论方便 留待后述 14 首先 线性插值的两点式可看作是两个特殊的一次式的一种线性组合 两点式 的一次插值多项式 称l0 x 和l1 x 为以x0 x1为节点的基本插值多项式 也称为线性插值的插值基函数 于是 线性插值即是用基函数的线性组合来构造的 1 2 2基函数法 称为拉氏基函数 满足li xj ij 显然有l0 x l0 x 1 这里 l0 x 和l1 x 具有如下性质 l0 x0 1 l0 x1 0 l1 x0 0 l1 x1 1 15 由此启发 我们希望二次插值也能由一些二次插值基函数来线性组合 这时 l0 x l1 x l2 x 都是二次多项式 且应满足 满足 2 1 式的li x 是否存在 若存在 具有什么形式呢 2 1 16 同理可得 l1 x 1 x x0 x x2 l2 x 2 x x0 x x1 此即二次拉格朗日插值公式 其中 l0 x l1 x l2 x 是满足 2 1 的特殊 基本 二次插值多项式 称为二次插值基函数 先考虑l0 x 因l0 x 是以x1 x2为零点的二次多项式 所以它可写成l0 x 0 x x1 x x2 其中 0是待定系数 又因为l0 x0 1 所以 0 x0 x1 x0 x2 1 则可有 l0 x 0 x x1 x x2 17 n 1 拉格朗日多项式 与有关 而与无关 节点 f 1 3n次插值 18 证明 存在性可利用Vandermonde行列式论证 反证 若不唯一 则除了Ln x 外还有另一n阶多项式Pn x 满足Pn xi yi 考察则Qn的阶数 n 而Qn有个不同的根 注 若不将多项式次数限制为n 则插值多项式不唯一 例如也是一个插值多项式 其中可以是任意多项式 19 Rolle sTheorem 若充分光滑 则存在使得 推广 若 使得 Rn x 至少有个根 n 1 x 有n 2个不同的根x0 xnx 注意这里是对t求导 20 注 通常不能确定 x 而是估计 x a b 将作为误差估计上限 当f x 为任一个次数 n的多项式时 可知 即插值多项式对于次数 n的多项式是精确的 21 例1求经过A 0 1 B 1 2 C 2 3 三个插值点的插值多项式 解 三个插值节点及对应的函数值为 由抛物插值公式得 n 1个节点的Lagrange插值多项式不超过n次 22 解 n 1 分别利用x0 x1以及x1 x2计算 利用 这里 而 sin50 0 7660444 外推 extrapolation 的实际误差 0 01010 利用 内插 interpolation 的实际误差 0 00596 内插通常优于外推 选择要计算的x所在的区间的端点 插值效果较好 23 n 2 sin50 0 7660444 2次插值的实际误差 0 00061 高次插值通常优于低次插值 但绝对不是次数越高就越好 嘿嘿 24 例3考虑下述的插值法问题 求二次多项式P x 满足P x0 y0 其中是已给的数据并给出使这一问题的解存在且唯一的条件 解 设则由已知条件有 即所以 故原问题的唯一可解性就归结为上述方程组的唯一可解性而后者唯一可解的充要条件为 这就是P x 存在且唯一的条件 25 HW p 481 2 4 5 1 1 5拉格朗日插值公式的优缺点 26 27 28 课堂练习 证明 29 本节主要内容 Newton插值等距差分公式 30 Lagrange插值公式 利用插值基函数很容易得到 含义直观 结构紧凑 在理论分析中非常方便 计算机上实现也很容易 也有一些缺点 一是计算量大 这是显然的 另外 还有一个更严重的缺点 当插值节点增加时 全部插值基函数均要随之变化 整个计算工作必须从头开始 不仅原来的每一项都要改变 还要增加一项计算 为克服上述两个缺点 努力 把插值多项式变形为便于计算的形式 希望 计算改变的过程中 尽可能能利用已有的计算结果 下面我们将看到 这是可能的 我们可以有具有 承袭性 的所谓牛顿公式 31 二次牛顿插值多项式 我们再看线性插值的点斜式 常数 差商 由此启发 我们希望二次插值也能类似地有有规律的组合表达式 P2 x 0 1 x x0 2 x x0 x x1 利用P2 x0 y0有 0 y0 利用P2 x1 y1有 1 f x0 x1 利用P2 x2 y2有 2 f x0 x1 f x0 x1 x2 f x0 x2 x x0时 0 32 注 1 事实上 从上述可看出二次牛顿插值公式是用待定系数法求得的 2 它也可看作是三个特殊函数的一种线性组合 本质上还是基函数法 33 更一般地 n 1个节点的插值多项式 我们希望由上述类似的一组特殊函数 来线性组合为 那么其组合系数是什么样的呢 怎么求呢 我们同样可用待定系数法 容易发现 计算a0 a1 a2 an是很有规律的 34 均差有如下的基本性质 1 k阶均差可表示为函数值f x0 f x1 f xk 的线性组合 即 这个性质可用归纳法证明 这个性质也表明均差与节点的排列次序无关 称为均差的对称性 即 f x0 x1 xk f x1 x0 x2 xk f x1 xk x0 35 3 若f x 在 a b 上存在n阶导数 且节点x0 x1 xn a b 则n阶均差与导数关系如下 证明推后到余项分析 36 Nn x Rn x ai f x0 xi 二 牛顿插值公式 37 Rn x Nn x n 1 x 多项式Nn x 显然满足插值条件 即Nn xj f xj j 1 n 且次数不超过n 由唯一性定理它就是前述的Ln x 其系数为 Nn x 称为牛顿均差插值多项式 它比拉格朗日插值多项式计算量省 且便于程序设计 38 注 由唯一性可知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 均差计算可列均差表如下 39 例1依据如下函数值表建立不超过3次的拉格朗日插值多