第2章 插值法.ppt

在工程技术与科学研究中 常会遇到函数表达式过于复杂而不便于计算 且又需要计算众多点处的函数值 或已知由实验 测量 得到的某一函数y f x 在区间 a b 中互异的n 1个xi i 0 1 n 处的值yi f xi i 0 1 n 需要构造一个简单易算的函数P x 作为y f x 的近似表达式 y f x P x 使得P xi f xi yi i 0 1 n 这类问题就称为插值问题 P x 称为插值函数 P x 一般取最简单又便于计算得函数 第2章插值法 P x f x f x y f x P x 使得P xi f xi yi i 0 1 n 其它点P x f x y 2 1 1插值问题 设y f x 是区间 a b 上的一个实函数 xi i 0 1 n 是 a b 上n 1个互异实数 已知y f x 在xi的值yi f xi i 0 1 n 求一个次数不超过n的多项式Pn x 使其满足 Pn xi yi i 0 1 n 5 1 这就是多项式插值问题 2 1引言 其中Pn x 称为f x 的n次插值多项式 f x 称为被插函数 xi i 0 1 n 称为插值节点 xi yi i 0 1 n 称为插值点 a b 称为插值区间 式 5 1 称为插值条件 从几何意义来看 上述问题就是要求一条多项式曲线y Pn x 使它通过已知的n 1个点 xi yi i 0 1 n 并用Pn x 近似表示f x 即P x a0 a1x a2x2 anxn 其中ai为实数 就称P x 为插值多项式 相应的插值法称为多项式插值 若P x 为分段的多项式 就称为分段插值 若P x 为三角多项式 就称为三角插值 本章只讨论插值多项式与分段插值 本章主要研究如何求出插值多项式 分段插值函数 样条插值函数 讨论插值多项式P x 的存在唯一性 收敛些及误差估计等 定理1设节点xi i 0 1 n 互异 则满足插值条件Pn xi yi i 0 1 n 的次数不超过n的多项式存在且唯一 证设所求的插值多项式为 Pn x a0 a1x a2x2 anxn 5 2 则由插值条件式Pn xi yi i 0 1 n 可得关于系数a0 a1 an的线性代数方程组 2 1 2插值多项式的存在性和唯一性 此方程组有n 1个方程 n 1个未知数 其系数行列式是范德蒙 Vandermonde 行列式 5 3 由克莱姆法则知方程组 5 3 的解存在唯一 证毕 考虑最简单 最基本的插值问题 求n次插值多项式li x i 0 1 n 使其满足插值条件 2 2 1基函数 可知 除xi点外 其余都是li x 的零点 故可设 Lagrange法1736 1813 2 2拉格朗日插值 其中A为常数 由li xi 1可得 称之为拉格朗日基函数 都是n次多项式 n 1时的一次基函数为 即已知函数f x 在点x0和x1点的函数值y0 f x0 y1 f x1 求线性函数L x a0 a1x使满足条件 L x0 y0 L x1 y1 此为两点线性插值问题 或用直线的两点式表示为 插值基函数的特点 记 n 2时的二次基函数为 可知其满足 2 2 2拉格朗日插值多项式 利用拉格朗日基函数li x 构造次数不超过n的多项式 称为拉格朗日插值多项式 再由插值多项式的唯一性 得 特别地 当n 1时又叫线性插值 其几何意义为过两点的直线 当n 2时又叫抛物 线 插值 其几何意义为过三点的抛物线 注意 1 对于插值节点 只要求它们互异 与大小次序无关 以xi i 0 1 n 为插值节点 函数f x 1作插值多项式 由插值多项式的唯一性即得基函数的一个性质 2 插值基函数li x 仅由插值节点xi i 0 1 n 确定 与被插函数f x 无关 3 插值基函数li x 的顺序与插值节点xi i 0 1 n 的顺序一致 这是因为若取 x xk k 0 1 n 由插值多项式的唯一性有 特别当k 0时 就得到 所以 例1已知用线性插值 即一次插值多项式 求的近似值 插值多项式为 例2求过点 1 2 1 0 3 6 4 3 的抛物线插值 即三次插值多项式 解以 以为节点的基函数 分别为 则拉格朗日的三次插值多项式为 截断误差Rn x f x Ln x 也称为n次Lagrange插值多项式的余项 以下为拉格朗日余项定理 定理2设f x 在区间 a b 上存在n 1阶导数 xi a b i 0 1 n 为n 1个互异节点 则对任何x a b 有 2 2 3插值余项 且与x有关 证由插值条件和 n 1 x 的定义 当x xk时 式子显然成立 并且有 n 1 xk 0 k 0 1 n 这表明x0 x1 xn都是函数 n 1 x 的零点 从而 n 1 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 使 即 所以 一般来说 外推比内插效果差 在估计误差时下列不等式很有用 解 插值多项式为 因为 故 于是 另见书p29的例1 用二次插值计算ln11 25的近似值 并估计误差 例4给定函数表 解取节点x0 10 x1 11 x2 12 作二次插值有 ln11 25 L2 11 25 在区间 10 12 上lnx的三阶导数的上限M3 0 002 可得误差估计式 实际上 ln11 25 2 420368 R2 11 25 0 000058 2 3 1均差及其基本性质 定义1称 为f x 在x0 x1点的一阶均差 一阶均差的均差 差商 称为函数f x 在x0 x1 x2点的二阶均差 英1642 1727 2 3均差与牛顿插值公式 一般地 n 1阶均差的均差 称为f x 在x0 x1 xn点的n阶均差 差商的计算步骤与结果可列成均差表 如下 一般f xi 称为f x 在xi点的零阶均差 记作f xi 表5 1 均差表 给出节点x0 x1 xn和函数值 x0 x1 xn 可按如下的差商表顺序逐次计算各阶差商值 这一性质可以用数学归纳法证明 它表明均差与节点的排列次序无关 即 f x0 x1 x2 xn f x1 x0 x2 xn f x1 x2 xn x0 性质1均差可以表示为函数值的线性组合 即 称之为均差的对称性 也称为对称性质 性质2由性质1立刻得到 或 性质3n次多项式f x 的k阶差商 当k n时是一个n k次多项式 当k n时恒等于0 性质4若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 2 3 2牛顿插值多项式 设x是 a b 上一点 由一阶均差定义得 同理 由二阶均差定义 如此继续下去 可得一系列等式 得 得 依次把后式代入前式 最后得 其中 可见 Nn x 为次数不超过n的多项式 且易知Rn xi 0即Nn xi yi i 0 1 n 满足插值条件 故其为插值问题的解 Nn x 称为牛顿插值多项式 Rn x 称为牛顿型插值余项 由插值多项式的唯一性知 它与拉格朗日插值多项式是等价的 即Ln x Nn x 且有如下递推形式 和余项公式 由此即得性质4 且 例1已知f x shx的数表 求二次牛顿插值多项式 并由此计算f 0 596 的近似值 解由上表可得过前三点的二次牛顿插值多项式为 又 可得过前四点的三次牛顿插值多项式 故 可得N3 x 的截断误差 设函数y f x 在等距节点xi x0 ih i 0 1 n 上的函数值为fi f xi h为步长 定义2 fi fi 1 fi和 fi fi fi 1分别称为函数f x 在点xi处的一阶向前差分和一阶向后差分 一般地 f x 在点xi处的m阶向前差分和m阶向后差分分别为 mfi m 1fi 1 m 1fi和 mfi m 1fi m 1fi 1 2 4差分与等距节点插值 2 4 1差分及其性质 构造差分表5 2 容易证明 差分有如下基本性质 性质1各阶差分均可用函数值表示 即 且有等式 nfi nfi n 性质3均差与差分的关系式为 性质2函数值均可用各阶差分表示 即 且有差分与微商的关系式为 差分的其它性质参看本章p59习题8 9 10 11 代入牛顿插值公式 可得 称为牛顿向前插值公式 其余项为 插值节点为xi x0 ih i 0 1 n 如果要计算x0附近点x处的函数值f x 可令x x0 th 0 t n 2 4 2等距节点差值公式 类似地 若计算xn附近的函数值f x 可令x xn th n t 0 可得牛顿向后插值公式 及其余项 例2设y f x ex xi 1 1 5 2 2 5 3 用三次插值多项式求f 1 2 及f 2 8 的近似值 解相应的函数值及差分表如下 求f 1 2 用牛顿前插公式 且由1 2 1 0 5t 得t 0 4 求f 2 8 用牛顿后插公式 且由2 8 3 0 5t 得t 0 4 2 5 1三次埃尔米特插值多项式 设y f x 是区间 a b 上的实函数 x0 x1是 a b 上相异两点 且x0 x1 y f x 在xi上的函数值和一阶导数值分别为yi f xi i 0 1 和mi f xi i 0 1 求三次多项式H3 x 使其满足 H3 x 称为三次埃尔米特插值多项式 法1822 1901 2 5埃尔米特 Hermite 插值 构造三次埃尔米特插值多项式如下 定理3满足条件式的三次埃尔米特插值多项式存在且唯一 由 可将它写成 即 可得满足条件的三次埃尔米特插值多项式为 定理4设f x 在包含x0 x1的区间 a b 内存在四阶导数 则当x a b 时有余项 设 则当x x0 x1 时 余项有如下估计式 误差限 2 5 2误差估计 且与x有关 例2已知f x x1 2及其一阶导数的数据见下表 用埃尔米特插值公式计算1251 2的近似值 并估计其截断误差 解 得 由 可求得 2 6分段低次插值 先看下面的例子 对 x 1 25x2 1 在区间 1 1 上取等距节点xi 1 ih i 0 1 10 h 0 2 作 x 关于节点xi i 0 1 10 的10次插值多项式L10 x 如图所示 x y o 1 1 0 5 1 1 5 y L10 x 这个现象被称为Runge现象 表明高次插值的不稳定性 实际上 很少采用高于7次的插值多项式 2 6 1分段线性插值 求一个分段函数P x 使其满足 P xi yi i 0 1 n 在每个子区间 xi xi 1 上是线性函数 称满足上述条件的函数P x 为分段线性插值函数 或 由线性插值的误差即得分段线性插值在区间 xi xi 1 上的余项估计式为 因此 在插值区间 a b 上有余项 2 6 2分段抛物线插值 2 6 3分段三次Hermite插值 已知 求一个分段函数H x 使其满足 2 在每个子区间 xi xi 1 上 H x 是次数不超过3的多项式 称满足上述条件的函数H x 为分段三次Hermite插值函数 或 分段三次埃尔米特插值在区间 xi xi 1 上的余项估计式为 因此 在插值区间 a b 上有余项 例3构造函数f x lnx在1 x 10上的数表 应如何选取步长h 才能使利用数表进行分段插值时误差不超过0 5 10 4 解 欲使 即进行分段线性插值时 应取h 2 10 2 误差不超过0 5 10 4 欲使 即进行分段三次埃尔米特插值时 应取误差不超过0 5 10 4 2 7 1问题的提出 定义给定区间 a b 的一个划分a x0 x1 xn b yi f xi i 0 1 n 如果函数S x 满足 S xi yi i 0 1 n 在每个小区间 xi xi 1 i 0 1 n 1 上是次数不超过3的多项式 3 在每个内节点xi i 1 2 n 1 上具有二阶连续导数 则称S x 为关于上述划分的一个三次多项式样条函数 简称三次样条 2 7三次样条插值 S x 在每个小区间 xi xi 1 上是一个次数不超过3的多项式 因此需确定四个待定常数 一共有n个小区间 故应确定4n个系数 S x 在n 1个内节点上具有二阶连续导数 应满足条件 即有3n 3个连续条件 再加上S x 满足的插值条件n 1个 共计4n 2个 因此还需要2个条件才能确定S x 通常补充两个边界条件 2 7 2三弯矩方程 在 x