插值法：原理与应用.ppt

插值法 原理与应用 ZhenhuaSong 插值的背景 1 只有n个点处的函数值希望找到一条通过这些点的曲线 连续 光滑 2 函数太麻烦 近似简化找到一个好计算的函数 近似代替3 用多项式代替多项式方便求值 求导 积分等 插值 逼近 拟合 0 给定n个不同的点 构造曲线1 插值 曲线依次通过n个点2 逼近 曲线最接近n个点 接近 在某种意义下 例 最小二乘法3 拟合 插值 逼近 泰勒展开 在某一点x0处展开只在x0处近似性较好远离x0的点误差较大需要n个点近似性较好插值可以胜任 一次插值 用一次函数近似表示 二次插值 用二次函数来表示 多项式插值 示例 给定的n 1个不同的点找到一个n次多项式 依次通过这n 1个点n次多项式必然唯一 多项式插值 唯一性 设n次多项式为 0 1 2 2 在这n 1个点上 满足n 1个方程 0 0 1 0 2 02 0 1 0 1 1 2 12 1 2 0 1 2 2 22 2 0 1 2 2 多项式插值 唯一性 把上述线性方程组写成矩阵形式1 0 02 0 1 1 12 1 1 2 22 2 1 2 0 1 2 0 1 2 系数矩阵行列式不为0 范德蒙行列式 0到 互不相同方程组解唯一多项式系数唯一插值多项式唯一 拉格朗日插值 一种多项式插值算法n次多项式不用求解线性方程组基函数线性组合 0 0 1 1 0 1 称为基函数 拉格朗日插值 2点情形 1 0 1 0 1 1 1 我们希望通过 0 0 1 1这2个点可以取 1 0 0 1 1 1 0 0 1 0 1 0 1 1 1 1 这样 1 0 0 1 0 0 1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1如何实现上述条件 基函数的构建 2点情形 条件 1 0 0 1 1 1 0 0 1 0 1 0 1 1 1 1 构造一次多项式构造 1 0 1 0 1 1 1 0 1 0分子是一次多项式满足 1 0 的条件分母是系数 满足 1 1 的条件实质 的直线 基函数的构建 n 1点情形 条件 1 0 1 1 构造n次多项式构造 0 1 1 1 0 1 1 1 注意 分子没有 分母没有 符合条件约束实质 每个基函数都是n次多项式 拉格朗日插值 n 1点情形 插值函数 0 0 1 1 基函数 0 1 1 1 0 1 1 1 简洁形式 0 0 0 0 0 0 拉格朗日插值 误差估计 拉格朗日是一种近似 存在误差 对于近似代替函数的情形 误差分析 误差项如果 1 误差项 1 1 0 拉格朗日插值 示例 对 1 在 0 2 1 2 75 2 4插值 Nevile迭代插值 对于给定的n 1个点 0 1 通过递推求出n次插值多项式设 1 2 是 的不同自然数 1 2 是定义在 1 2 Nevile迭代插值 对于给定的k 1个点 0 1 插值多项式 在k 1个点上 在除去点j的k个点上的插值多项式 在除去点i的k个点上的插值多项式 Nevile迭代插值 0 1 0 1 2 3 1 2 2 3 0 1 2 1 2 3 0 1 2 3 牛顿差商插值 n次多项式写成多项式和 0 1 0 2 0 1 0 1 1确定系数 可确定插值多项式经过n 1个点确定唯一n次多项式系数可以由差分确定 牛顿差商插值 系数确定 多项式 0 1 0 2 0 1 0 1 1取值 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1为差分形式所有系数都可以写成差商形式定义符号 牛顿差商插值 系数确定 定义符号 零阶差商 1 1 1 一阶差商 1 2 1 2 1 2 二阶差商 1 2 1 2 1 1 k阶差商在 0处差分 0 0 0 0 1 1 0处 阶差分 牛顿差商插值 公式导出 0 1 0 1 2 0 1 定义符号 零阶差商 1 1 1 一阶差商 1 2 1 2 1 2 二阶差商 1 2 1 2 1 1 k阶差商 牛顿差商插值 系数求解 0 1 2 3 0 1 1 2 2 3 0 1 2 1 2 3 0 1 2 3 牛顿差商插值 间距相等 当n 1个点等距排列时 设 1 0 插值多项式变形 0 1 0 1 2 0 1 其中 0 0 0 1 0 1 牛顿差商插值 间距相等 变形处理 0 1 0 1 组合数 定义广义组合数 1 1 0 1 广义组合数 s可以是任意实数 0 1 0 1 0 1 2 牛顿差商插值 反向差商 之前 当n 1个点等距排列时 设 1 0 对于反向差分 多项式形式与 0 类似 Hermite插值 拉格朗日插值缺点在n 1个点处与 值相同导数等不同目的 找到一个多项式函数不光函数值相同k阶导数相同数学语言 0 1 拉格朗日插值缺点 插值多项式形状 走向差异较大 Hermite插值 优势 只取1个点时 取m阶导数信息 相当于泰勒展开取n 1个点时 不考虑导数信息 相当于拉格朗日插值具有更广泛的应用生成的Hermite插值多项式唯一在n 1个点 第i个点 阶导数相同 Hermite 一阶导数相同 在n 1个点处函数值相同 切线相同需要2n 1阶多项式条件 1 0 1 2 思想 与拉格朗日基函数思想相似 Hermite 一阶导数相同 2 1 0 0 当 时 为了保证 2 1 令 1 0 0 0 为了保证 2 1 令 0 0令 1 0 Hermite 一阶导数相同 2 1 0 0 其中 1 2 2 2 为拉格朗日基函数 第j个 n次多项式 回忆拉格朗日基函数 插值函数 0 0 1 1 基函数 0 1 1 1 0 1 1 1 基函数 性质在 处值为0 在 处值为1 Hermite 其他 误差分析如果 2 2 2 1 02 22 22 2 2 后面即为误差项 也可以用差分形式表达形式与n次多项式牛顿差分类似并不是次数越高越精确误差反而可能变大 三次样条插值 背景 给定n 1个点 0 0 0 1 2 分成n段 每一段 是一个分段函数在 0 处 分段函数取值为 尽可能保持光滑 线段连接 粗糙 相邻两点用线段连接形成折线 不够光滑 三次样条插值 特性 每一段 1用3次多项式 表示 1 1 或者说 1 1 1分段函数在 1处连续暂不考虑分段函数两端的情况 1 1 1 分段函数在 1处一阶导数相同 1 1 1 分段函数在 1处二阶导数相同具有较好的光滑性 三次样条插值 边界 对于两端点 处理如下 0 0 0 0 0 0 0 三次样条插值 构建 对于某一段 不考虑端点 设 2 3 2 3 处函数值相同 1 12 13 1 1处函数值相同 1 2 1 3 12 1 1 2 1 1 3 1 12 1两端一阶导数值相同2 6 1 2 1 6 1 1 1两端二阶导数值相同 三次样条插值 构建 所有条件 可以组成线性方程组 为稀疏矩阵求解线性方程组 得到唯一解三次样条缺点 估计误差不方便 三次样条插值 应用 0 0 1 1 2 2 3 3 改变某一个点 改变某一个点 对比 多项式插值 牵一发动全身 整个多项式都变了三次样条插值 在 附近有较大影响 远离 处影响不大 多项式插值 对比 参数曲线 对于n 1个点 0 0 1 1 1满足参数方程以 为参数 n 1个点对应n 1个参数取值 0 1 2 参数曲线 图像 三次参数曲线 定义 输入 点 0 0 1 1 0 0处切线上某点 0 0 0 0 1 1处切线上某点 1 1 1 1输出 是t的3次函数 是t的3次函数 0 0 0 0 1 1 1 1输出三次参数曲线唯一 三次参数曲线 构造 设 0 1 2 2 3 3 0 1 2 2 3 3满足条件 0 0 0 0 0 0 1 1 0 1 2 3 1 1 0 1 2 3 0 0 1 1 0 0 0 0方程解唯一存在8个未知量 8个方程 三次函数曲线 图像 Bezier曲线 n 1个点分成n段 每一段都是三次参数曲线输入 n 1个点n段上端点切向量上某一点输出 n个三次多项式 作为Bezier曲线 Bezier曲线 形状 Bezier曲线 特点 改变某一段 不会对其他段产生影响常用于工业设计设计汽车外形Adobeillustrator可以方便绘制缺点 不方便进行误差分析B样条曲线可以更好地进行误差分析