数值分析中的(插值法).ppt

数值分析第二章插值法 李庆扬王能超易大义编 8三次样条插值 2Lagrange插值 1引言 7分段低次插值 6Hermite插值 5差分与等距节点插值公式 4均差与Newton插值公式 3逐次线性插值法 自学 9评述 第二章插值法 数值分析第二章插值法 李庆扬王能超易大义编 第一节引言 一 一个实例 那么如何计算 数值分析第二章插值法 李庆扬王能超易大义编 二 插值问题的一般性提法 即简单函数P x 的曲线要经过上已知的n 1个点 数值分析第二章插值法 李庆扬王能超易大义编 同时在其它点上估计误差为 数值分析第二章插值法 李庆扬王能超易大义编 若p x 是次数不超过n的代数多项式 即 2 1 2 则称p x 为插值多项式 相应的插值法称为多项式插值 若p x 为分段多项式 就是分段插值 若p x 为三角多项式 就是三角插值 还有有理插值等 本章主要讨论多项式插值与分段插值 注 插值法还有其他许多用途 如函数的近似表示 曲线曲面拟合 导出其它数值方法的依据 导出数值积分 数值微分 微分方程数值解 等 数值分析第二章插值法 李庆扬王能超易大义编 若满足条件的存在 又如何构造 三 多项式插值问题中需要研究的问题 满足插值条件的多项式是否存在 唯一 用近似代替的误差估计 数值分析第二章插值法 李庆扬王能超易大义编 定理1设节点xi i 0 1 n 互异 则满足插值条件Pn xi yi的次数不超过n的多项式存在且唯一 下面先研究第一个问题 定理1不仅解决了问题1 其证明过程也给出了问题2 求插值多项式的一种方法 但一般不用这种方法 因为范得蒙矩阵一般是病态的 即使求解过程是精确的 多项式求值的误差也是可观的 数值分析第二章插值法 李庆扬王能超易大义编 拉格朗日插值多项式的优缺点 截断误差 拉格朗日插值多项式 数值实例 第二节拉格朗日插值 数值分析第二章插值法 李庆扬王能超易大义编 一 拉格朗日插值多项式 其中 1 两个互异节点 x0 y0 x1 y1 且满足 数值分析第二章插值法 李庆扬王能超易大义编 2 三个节点 x0 y0 x1 y1 x3 y3 其中 令 满足 数值分析第二章插值法 李庆扬王能超易大义编 3 有n 1个互异节点 x0 y0 x1 y1 xn yn 我们称n次多项式Ln x 为拉格朗日插值多项式 Li x 为插值基函数 数值分析第二章插值法 李庆扬王能超易大义编 注 1 插值基函数li x i 0 1 n 仅由插值节点xi i 0 1 n 确定 与被插函数f x 无关 3 对于插值节点 只要求它们互异 与大小次序无关 2 以xi i 0 1 n 为插值节点 函数f x 1作插值多项式 则由插值多项式的唯一性立即得到基函数的一个性质 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 关于截断误差Rn x f x Ln x 有下面定理 定理2设f x 在区间 a b 上存在n 1阶导数 xi a b i 0 1 n 为n 1个互异节点 则对任何x a b 有 且与x有关 二 截断误差 插值余项 数值分析第二章插值法 李庆扬王能超易大义编 证由插值条件和 n 1 x 的定义 当x xk时 式子显然成立 且x0 x1 xn都是函数 n 1 x 的零点 也是Rn x 的零点 从而Rn x 可表示为 其中K x 是待定函数 对于任意固定的x a b x xk 构造自变量t的辅助函数 数值分析第二章插值法 李庆扬王能超易大义编 由式 n 1 xk 0和式Ln xk yk k 0 1 n 以及 可知 x0 x1 xn和x是 t 在区间 a b 上的n 2个互异零点 因此根据罗尔 Rolle 定理 至少存在一点 x a b 使 即 所以 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 例已知sin0 32 0 314567 sin0 34 0 333487 sin0 36 0 352274 用Lagrange插值计算sin0 3367的值 并估计截断误差 解 f x sinx 取 三 数值实例 数值分析第二章插值法 李庆扬王能超易大义编 于是有 可以发现 结果与有六位有效数字的sinx表完全一致 数值分析第二章插值法 李庆扬王能超易大义编 截断误差为其中故有 数值分析第二章插值法 李庆扬王能超易大义编 记 数值分析第二章插值法 李庆扬王能超易大义编 四 Lagrange插值公式优缺点 优点 结构清晰 紧凑 适用于作理论分析 缺点 当节点个数有所变动 整个插值公式发生变化 在实际应用时不方便 数值分析第二章插值法 李庆扬王能超易大义编 第四节均差与牛顿插值公式 数值分析第二章插值法 李庆扬王能超易大义编 一 差商及其基本性质 英1642 1727 数值分析第二章插值法 李庆扬王能超易大义编 差商的计算步骤与结果可列成差商表如下 数值分析第二章插值法 李庆扬王能超易大义编 表4 1 数值分析第二章插值法 李庆扬王能超易大义编 性质1差商可以表示为函数值的线性组合 即 数值分析第二章插值法 李庆扬王能超易大义编 性质2若f x 在 a b 上存在n阶导数 且节点x0 x1 xn a b 则至少存在一点 a b 满足下式 例1f x 6x8 7x5 10 求f 1 2 9 及f 1 2 10 解f 8 x 6 8 f 1 2 9 6 f 9 x 0 f 1 2 10 0 数值分析第二章插值法 李庆扬王能超易大义编 二 牛顿插值多项式 设x是 a b 上一点 由各阶差商定义得 数值分析第二章插值法 李庆扬王能超易大义编 依次把后式代入前式 最后得 其中 最后一项中 差商部分含有x 为余项部分 记作Rn x 而前n 1项中 差商部分都不含有x 因而前n 1项是关于x的n次多项式 记作Nn x 数值分析第二章插值法 李庆扬王能超易大义编 可见 Nn x 为次数不超过n的多项式 且易知Rn xi 0即Nn xi yi i 0 1 n 满足插值条件 称Nn x 为牛顿均差插值多项式 由插值多项式的唯一性知 Ln x Nn x 即 数值分析第二章插值法 李庆扬王能超易大义编 余项公式 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 三 拉格朗日插值与牛顿插值的比较 1 与均是n次多项式 且均满足插值条件 由插值多项式的唯一性 因而两个公式的余项是相等的 即 数值分析第二章插值法 李庆扬王能超易大义编 则可知n阶差商与导数的关系如下 性质2 2 当插值多项式从n 1次增加到n次时 拉格朗日型插值必须重新计算所有的所有的插值基函数 而对于牛顿型插值 只需用表格再计算一个n阶差商 然后加上一项即可 节省计算量 便于编程 3 牛顿型插值余项公式对是由离散点给出或导数不存在时均适用 因此更具一般性 数值分析第二章插值法 李庆扬王能超易大义编 五 数值实例 例1根据下表建立不超过三次的拉格朗日插值多项式和牛顿插值多项式 并验证插值多项式的唯一性 例2教材P24例2 3 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 解从均差表看到四阶均差近似常数 故取四次牛顿插值多项式N4 x 做近似即可 数值分析第二章插值法 李庆扬王能超易大义编 第五节差分与等距节点插值公式 差分及其性质 等距节点的Newton向前插值公式 等距节点的Newton向后插值公式 数值实例 数值分析第二章插值法 李庆扬王能超易大义编 一 差分及其性质 数值分析第二章插值法 李庆扬王能超易大义编 一阶向前差分 一 差分的概念 二阶向前差分 注 称为向前差分算子 表示向后差分算子 各阶差分可用下表表示 n阶向前差分 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 除差分算子外 常用的算子符号还有 不变算子I 移位算子E 由上面各种算子的定义可得算子间的关系 由可得 同理可得 数值分析第二章插值法 李庆扬王能超易大义编 二 差分的性质 步长均为h 性质1 各阶差分均可用函数值表示 数值分析第二章插值法 李庆扬王能超易大义编 性质3 各种差分之间可以互化 如 性质4 性质2 可用各阶差分表示函数值 如 数值分析第二章插值法 李庆扬王能超易大义编 称为牛顿前插公式 插值节点为xi x0 ih i 0 1 n 如果要计算x0附近点x处的函数值f x 可令x x0 th 0 t 1 代入牛顿插值公式 可得 二 Newton向前插值公式 数值分析第二章插值法 李庆扬王能超易大义编 其余项为 数值分析第二章插值法 李庆扬王能超易大义编 及其余项 三 Newton向后插值公式 类似地 若计算xn附近的函数值f x 可令x xn th 1 t 0 可得牛顿后插公式 数值分析第二章插值法 李庆扬王能超易大义编 例设y f x ex xi 1 1 5 2 2 5 3 用三次牛顿插值多项式求f 1 2 相应的函数值及差分表如下 四 数值实例 解用牛顿前插公式 由1 2 1 0 5t 得t 0 4 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 第六节埃尔米特 Hermite 插值 数值分析第二章插值法 李庆扬王能超易大义编 一 Hermite插值问题的提出 由于理论与实践的需要 在构造插值函数时 不但要求在节点上函数值相等 而且还要求它的 高阶 导数值也相等 即要求在节点上具有一定的光滑度 使得插值函数与被插函数贴近程度更好 满足这种要求的插值多项式就是Hermite插值多项式 有时也称为具有重节点插值或切触插值 数值分析第二章插值法 李庆扬王能超易大义编 二 三次Hermite插值 问题 求作三次多项式 使之满足 称之为两点三次Hermite插值问题 称满足插值条件 2 6 1 的为三次Hermite插值多项式 下面采用构造基函数的方法来确定多项式 数值分析第二章插值法 李庆扬王能超易大义编 设则若满足则H3 x 即为所求 数值分析第二章插值法 李庆扬王能超易大义编 由于由 2 6 3 可设再由 2 6 2 可求得 2 6 2 2 6 3 数值分析第二章插值法 李庆扬王能超易大义编 同理可得 数值分析第二章插值法 李庆扬王能超易大义编 故 数值分析第二章插值法 李庆扬王能超易大义编 三 2n 1次Hermite插值多项式 数值分析第二章插值法 李庆扬王能超易大义编 由 点 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 四 Hermite插值余项 数值分析第二章插值法 李庆扬王能超易大义编 例1已知f x x1 2及其一阶导数的数据见下表 用埃尔米特插值公式计算1251 2的近似值 并估计其截断误差 五 数值实例 数值分析第二章插值法 李庆扬王能超易大义编 解 数值分析第二章插值法 李庆扬王能超易大义编 得 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 第七节分段低次插值 数值分析第二章插值法 李庆扬王能超易大义编 一 多项式插值的问题 前面介绍了构造插值公式的方法 并分析了它们的余项 在实际应用插值函数作近似计算时 总希望插值公式余项的绝对值小一些 即使得误差尽量小一些 从表达式看 似乎提高插值多项式的次数便可达到目的 但实际上并非如此 数值分析第二章插值法 李庆扬王能超易大义编 例给定函数取其等距节点 构造的Lagrange插值多项式为 实际上 当时 只能在内收敛 而在这个区间以外是发散的 这种畸形现象通常叫做Runge现象 数值分析第二章插值法 李庆扬王能超易大义编 n越大 端点附近抖动越大 称为Runge现象 数值分析第二章插值法 李庆扬王能超易大义编 在插值过程中有两种误差 1 由插值函数替代被插函数所引起的截断误差 2 节点数据的误差 这种误差在插值过程中是否会被扩散或放大呢 这就是插值过程的稳定性问题 对任意的插值节点 当时 不一定收敛到 事实上 当n变大时 插值过程对于节点的数据误差非常敏感 也就是说高次插值具有数值不稳定性 数值分析第二章插值法 李庆扬王能超易大义编 二 分段线性插值 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 因此 在插值区间 a b 上有 可以证明 P x 在 a b 上一致收敛于f x 在区间 xi xi 1 上的余项估计式为 数值分析第二章插值法 李庆扬王能超易大义编 例已知函数在区间上取等距插值节点 如下表 求区间上分段线性插值函数 并利用它求出的近似值 数值分析第二章插值法 李庆扬王能超易大义编 于是 解在每个小区间上 数值分析第二章插值法 李庆扬王能超易大义编 三 分段三次Hermite插值 i 数值分析第二章插值法 李庆扬王能超易大义编 分段三次埃尔米特插值在区间 xi xi 1 上的余项估计式为 i i i 数值分析第二章插值法 李庆扬王能超易大义编 因此 在插值区间 a b 上有 可以证明 3 x 在 a b 上一致收敛于f x 数值分析第二章插值法 李庆扬王能超易大义编 四 小结 分段插值简便易行 收敛性能得到保证 只要节点间的间距充分小 就能保证它的误差要求 分段插值具有局部性质 如果修改某个数据 插值曲线仅在与该数据有关的相邻两个区间内受到影响 而前面讲的代数插值确会影响整个区间 数值分析第二章插值法 李庆扬王能超易大义编 问题的提出 三次样条函数 三弯矩方程 三转角方程 自学 数值实例 第八节三次样条插值 数值分析第二章插值法 李庆扬王能超易大义编 一 问题的提出 数值分析第二章插值法 李庆扬王能超易大义编 二 三次样条函数 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 设在 xi xi 1 上是一次多项式且 三 三弯矩方程 设在 xi xi 1 上是一次多项式且 x i i i i i i i i i i i i i i i h x x M h y h x x M h y M h x x Mi h x 6 6 6 6 1 2 1 1 2 1 3 1 S x x xi xi 1 i 0 1 n 1 3 数值分析第二章插值法 李庆扬王能超易大义编 所以 数值分析第二章插值法 李庆扬王能超易大义编 数值分析第二章插值法 李庆扬王能超易大义编 即 1 数值分析第二章插值法 李庆扬王能超易大义编 所以有 从中解出Mi i 0 1 n 代入S x 的表达式即可 数值分析第二章插值法 李庆扬王能超易大义编 2 M0 Mn已知 即满足边界条件 从中解出Mi i 1 2 n 1 代入S x 的表达式即可 数值分析第二章插值法 李庆扬王能超易大义编 3 满足边界条件 得 由 整理得 其中 数值分析第二章插值法 李庆扬王能超易大义编 注意到 M0 Mn 故有 解出Mi i 1 n 代入S x 的表达式即可 数值分析第二章插值法 李庆扬王能超易大义编 四 数值实例 数值分析第二章插值法 李庆扬王能超易大义编 解 1 边界条件