数值分析(插值方法)总结.ppt

插值的应用背景拉格朗日插值公式牛顿插值公式插值误差余项Runge反例 数值分析 12 趣例1 图像放大 趣例2 工业设计 先是雷诺和雪铁龙工作的PauldeCasteljau和PierreB zier 随后美国通用汽车的其它人一起推动了现在称为三次样条和B zier样条的建立 样条是通过很少的控制点就能够生成复杂平滑曲线的方法 趣例3 数据可视化 趣例4 游戏与电影 Ref Demo1 figure position get 0 screensize axes position 0011 x y ginput n length x s 1 n t 1 05 n u splinetx s x t v splinetx s y t clfresetplot x y u v 数据和插值函数 如果一个函数P x 满足yi P xi i 0 n 那么函数P x 插值了一系列数据点 x0 y0 xn yn 其中P x 称为插值函数 点x0 xn称为插值节点 P x 函数是描述自然界客观规律的重要工具 插值问题研究包括如下三个方面 插值函数的选择和构造 插值函数的存在唯一性 插值误差估计的问题 过两点直线方程 已知函数表求满足 L x0 y0 L x1 y1的线性函数L x 例求的近似值 函数值 10 7238 真实值 10 7238 12 线性插值函数 x0 x1 x0 y0 x1 y1 L1 x 可见是过和两点的直线 13 抛物插值函数 x0 x1 x2 因过三点的二次曲线为抛物线 故称为抛物插值 选择多项式函数的理由 理论方面多项式函数简单明了的数学性质 有一个简单的原理可以说明什么时候存在给定次数的插值多项式 更重要的是计算方面多项式函数是计算机最基本的函数 计算多项式函数的值只需用加和乘运算 且积分和微分均非常方便 插值函数的选择 则称P x 为插值多项式 称x0 x1 xn为插值节点 如果P x a0 a1x anxn满足P xk yk k 0 1 n 考虑区间 a b 上 n 1 个点a x0 x1 xn b 代数插值问题 插值条件 点 则满足插值条件L xk yk k 0 1 n 的次数小于等于n次的插值多项式L x a0 a1x anxn存在而且唯一 定理5 1若插值结点x0 x1 xn是 n 1 个互异 回顾1 非齐次方程组有唯一解的充分必要条件是系数矩阵可逆 矩阵可逆的充分必要条件是行列式不等于零 系数矩阵行列式不等于零 则方程组有唯一解 因此插值多项式L x 存在且唯一 回顾2 范德蒙 Vandermonde 矩阵 注释 插值多项式的存在唯一性说明满足插值条件的多项式存在而且与构造方法无关 只要插值节点互异 则Vandermonde矩阵总是非奇异 然而范得蒙矩阵条件数通常很大 故直接求解方程组是危险的 Hilbert和Vandermonde条件数 fori 1 10c i cond hilb i 2 vander 1 i endplot 1 10 c 过两点直线方程 已知函数表求满足 L x0 y0和L x1 y1的线性函数L x 记 对称形式 二次插值问题 已知函数表 求函数L x a0 a1x a2x2满足 L x0 y0 L x1 y1 L x2 y2 L x l0 x y0 l1 x y1 l2 x y2 二次插值函数 L x l0 x y0 l1 x y1 l2 x y2 二次插值基函数图形 取x0 0 x1 0 5 x2 1 l0 x 2 x 0 5 x 1 l1 x 4x x 1 l2 x 2 x 0 5 x 拉格朗日插值公式 插值条件 L xk yk k 0 1 n 其中第k个插值基函数 k 0 1 n 或 例1求插值于点 0 2 1 1 2 0 3 1 的次数小于等于3的插值多项式的拉格朗日形式 例2求插值于点 2 56 1 16 0 2 1 2 3 4 的次数小于等于4的插值多项式拉格朗日形式 程序片段1 MatlabCode 多项式插值 拉格朗日形式 functionv polyinterp x y u POLYINTERPPolynomialinterpolation v POLYINTERP x y u computesv j P u j wherePisthe polynomialofdegreed length x 1withP x i y i UseLagrangianrepresentation Evaluateatallelementsofusimultaneously n length x v zeros size u fork 1 nw ones size u forj 1 k 1k 1 n w u x j x k x j w endv v w y k end Demo2x 0 3 y 5 6 116 u 25 01 3 25 v polyinterp x y u plot x y o u v symx sym x L polyinterp x y symx L simplify L 拉格朗日形式结构紧凑且形式对称 然而很少用它来计算 这是因为等价的牛顿形式更具操作性而且计算复杂度更低 牛顿形式相对简单 但是某些记号首先需要掌握 把数据点看作由某个函数给出 并把数据点列成下表 插值多项式的牛顿形式 给定x0 x1和x2 求二次函数P x a0 a1 x x0 a2 x x0 x x1 满足条件P x0 f x0 P x1 f x1 P x2 f x2 满足插值条件的关于a0 a1和a2方程 插值多项式牛顿形式 解下三角方程组过程中引入符号 a0 f x0 a1 f x0 x1 a2 f x0 x1 x2 P x f x0 f x1 x2 x x0 f x0 x1 x2 x x0 x x1 牛顿插值公式 定义5 3若已知函数f x 在点x0 x1 xn处的值f x0 f x1 f xn 如果i j 则 j 0 1 n 1 一阶差商 n阶差商 二阶差商 三阶差商 差商 divideddifference 更加一般地考虑 牛顿插值形式 求解该方程组可得待定系数如下 a0 f x0 a1 f x0 x1 a2 f x0 x1 x2 an f x0 x1 xn 例3已知数据如下表 试计算数据的差商 例2求插值于点 2 56 1 16 0 2 1 2 3 4 的次数小于等于4的插值多项式拉格朗日形式 例4已知数据如下表 试计算数据的插值多项式 例5已知数据如下表 试计算数据的插值多项式 加入一个新的点到Lagrange形式所需要额外工作与牛顿形式进行比较是很有趣的 牛顿形式具有Lagrange形式所缺少的 实时更新 性质 差商的性质 差商的值不依赖于x0 x1 xn的次序 压缩的概念 观测的离散数据可以想象成现实中无穷多信息的代表 通过给定数据求出插值函数意味着用简单的规则代替无穷多信息 尽管期待这种简单规则精确地反映实际情况是不现实的 但是它可以充分接近实际 这一类压缩是有损的压缩 即它会产生误差 用简单规则代替无穷多信息时会产生多大的误差 这是我们下面研究的内容 两点线性插值 插值误差余项 R x f x L1 x 由插值条件知R x C x x x0 x x1 即f x L x C x x x0 x x1 C x Rolle过山车 回顾 拉格朗日中值定理 Ln x 是满足Ln xk f xk 的n次插值多项式 则对任何x a b 在 a b 内存在一点使得 其中 定理5 2设f x 在 a b 连续且在 a b 具有n 1阶导数 x0 x1 xn是 a b 内互不相同的节点 证明 记 n 1 x x x0 x xn 注释 例1给出如下数据 用线性插值及抛物插值计算sin0 3367的值并估计误差 例2设y f x 在区间 a b 上连续 且f x 在 a b 内具有2阶导数 已知f x 在区间端点处的值 如果当x a b 时有 f x M 证明 证明由Lagrange插值误差公式 令h x x a x b Runge反例 rungeinterp f x 1 x 2 1 5 x 5 x 5 5 y 1 x 2 1 u 5 01 5 v polyinterp x y u plot x y o u v 一般认为Ln x 的