数值分析 第二章 代数插值

数值分析 Numerical Analysis,第二章 代 数 插 值,郑州大学硕士研究生课程（2015-2016学年第一学期）,2/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,第二章 代 数 插 值,§2.1 代数插值问题 问题提出 §2.2 代数插值多项式的存在唯一性 可解性 §2.3 拉格朗日插值方法 解决方法和理论分析 §2.4 牛顿(Newton)插值 算法实现 §2.5 分段线性插值 §2.6 Hermite插值 §2.7 样条插值,计算机数值算法 设计思路,3/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,y= f (x),y=p (x),例2.1.1 设计某工件的外形，要求其轮廓线是光 滑的，且必须过n+1个互异的点(xi,yi)(i=0,1,n). 轮廓线应如何设计呢？,§2.1 代数插值问题的提出,4/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,解： 满足要求的轮廓线不妨取为n次多项式Pn(x).设,这里 Pn(x)是光滑的，且它满足,将(2.1)带入(2.2)可得下面线性代数方程组,§2.1 代数插值问题的提出,5/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,则(2.3)的系数行列式为范德蒙德行列式,因xixj（ij），故V0. 从而方程组(2.3)的解存在唯一. 求出未知量a0,an代入(2.1)即得所求轮廓线. ,§2.1 代数插值问题,6/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,代数插值问题： 设函数 y=f (x)定义在区间a, b上，而 x0, x1, xn是在a, b上取定的n+1个互异节点, 则在这些点 处的函数值为 yi=f (xi), i=0,1,n. 求一个次数不超过 n 的多项式Pn(x)，使它满足,则称Pn(x)为f (x)的n次代数插值多项式. 求满足以上条件多项式Pn(x)的问题叫做代数插值问题. 称 x0,x1,xn 为插值节点， a, b为插值区间，（2.5）为插值条件.,§2.1 代数插值问题的提出,7/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,代数插值问题是否可解？,§2.2 代数插值多项式的存在唯一性,8/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,多项式 局部近似 以直代曲 以简代繁,多项式 整体近似 以直代曲,§2.2 代数插值多项式的存在唯一性,9/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,定理2.2.1 n次代数插值问题的解是存在且惟一的.,证： 因为 x0, x1, xn 是在a, b上取定的n+1个互异节点, 由例2.1.1中分析过程可知，代数方程组的解存在唯一，从 而满足插值条件(2.5)的n次代数插值多项式Pn(x)也是 存在唯一的.,§2.2 代数插值多项式的存在唯一性,10/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,目标： 设计计算量小、实现简单的计算 机算法，根据输入的n+1个点生 产n次代数插值多项式.,约瑟夫.路易斯.拉格朗日（17351813）,评价： 采用例2.1.1中的待定系数法求n次代 数插值多项式不符合目标. 拉格朗日提出直接构造多项式的方法.,§2.3 代数插值多项式的存在唯一性,11/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,线性插值（n=1),给定两个互异点(x0，y0)，(x1，y1），确定一 次插值多项式P1(x)的问题，称为线性插值问题.,称(2.6)为一次拉格朗日插值多 项式或线性插值多项式.,§2.3 拉格朗日插值方法,12/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,线性插值（n=1),引入记号,则它们满足,则 分别称为节点x0 ,x1的插值标准基函数. 线性插值多 项式可表示为函数值 y0, y1 与插值基函数的线性组合,§2.3 拉格朗日插值方法,13/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,线性插值（n=1),§2.3 拉格朗日插值方法,插值标准基函数,14/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,抛物插值（n=2),给定3个互异点(xi，yi)(0=0,1,2)，确定一个不超过2 次的插值多项式P2(x)的问题，称为二次插值问题.,受线性插值多项式的启发，猜想可通过如下方式构造P2(x),构造2次插值基函数li(x)(i=0,1,2),满足li(xj)=ij(i,j=0,1,2).,构造2次插值多项式P2(x)=y0l0(x)+y1l1(x)+y2l2(x).,§2.3 拉格朗日插值方法,15/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,线性插值（n=1),§2.3 拉格朗日插值方法,插值标准基函数,16/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,抛物插值（n=2),因为 是 的两个零点，于是,再由另一条件 确定系数,从而导出,类似可得,§2.3 拉格朗日插值方法,17/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,抛物插值（n=2),则 称为二次插值基函数.,取 为线性组合系数,将基函数 线性组合可得,容易看出,P2(x)满足条件因其图形为抛物线，二次插值又称为抛物插值.,§2.3 拉格朗日插值方法,18/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,x0,x1,x2,§2.3 拉格朗日插值方法,19/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,n次插值,由抛物插值中构造性方法启发，解决一般的n次代数插值问题.,分别构造x0 , x1, , xn 上的 n 次插值基函数 l0(x), l1(x), , ln(x),满足,n次插值基函数,§2.3 拉格朗日插值方法,20/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,N次插值,由上表， x1 , x2, , xn 为 l0(x) 的零点，设,由l0(x0)=1，得,§2.3 拉格朗日插值方法,21/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,N次插值,类似可得节点 xi 对应的n次插值基函数,从而可得n次代数插值多项式,显然Pn(x)是次数不超过n的多项式，且Pn(xi)=yi(i=0,1,n),§2.3 拉格朗日插值方法,22/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,N次插值,拉格朗日(Lagrange)插值方法总结 根据问题特征，构造对应每个节点的插值基函数，是解决问题的关键. 其数学思想是以直代曲，以简代繁，是高等数学思想方法的延伸. 直接构造n次插值多项式的方法过程简单，容易在计算机上实现.,§2.3 拉格朗日插值方法,23/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,插值函数Pn(x)在n+1个互异插值节点xi(i=0,1,n )处与f(xi)相等,在不等于xi 的点x处就用Pn(x)的值作为f(x) 的近似值，这一过程称为插值，点x称为插 值点. 误差函数Rn(x)=f(x)- Pn(x)称为插值余项, 区间a, b称为插值区间, 插值点x在插值区间内时称为内插, 否则称外插. (插值误差属于截断误差),y= f (x),y=pn (x),y= Rn(x),§2.3 拉格朗日插值方法,24/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,线性插值误差,定理 2.3.1 设f(x)在a, b上一阶导数连续，且存在二阶导数, x0, x1为a, b上两个互异的节点, P1(x)为满足P1(xi) = f(xi) (i=0,1) 的线性插值多项式，则对于任何x a, b , 至少存在一点 a, b，使得,§2.3 拉格朗日插值方法,25/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,证明： 显然x0, x1 为R1(x)的两个零点，可设R1(x)为R1(x) = k(x)(x-x0)(x-x1).,固定x，作辅助函数，令则 (xi )=0, i =0,1,且 (x)=0, 即 (t )有3个零点 x0, x1, x.不妨设x0 < x < x1 , 分别在x0，x和x，x1上应用洛尔定理可知 (t) 在每个区间上至少存在一个零点1和2，使 (1)=0， (2)=0，即 (t)有2个零点. 再次利用洛尔定理知， (t)在1, 2上至少有一个零 点，使 ()=0. 则由 (t) = f (t) -2!k(x)以及 ()=0可得 k(x) = f () /2!，从而 定理2.1得证. ,§2.3 拉格朗日插值方法,26/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,插值误差定理,定理 2.3.2 设f(x)在a, b上n阶导数连续，且存在n+1阶导数, x0, x1 , xn为a, b上n+1个互异的节点, Pn(x)为满足Pn(xi) = f(xi) (i=0,1,n) 的n次插值多项式，则对于任何x a, b , 至少存在一点 a, b，使得,§2.3 拉格朗日插值方法,27/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,例2.3.1 给定sin11°=0.190809,sin12°=0.207912, 求y=sinx的线性插值多项式，计算sin11°30并估计误差.,解: x0= 11°, x1= 12°, y0= 0.190809, y1= 0.207912，sin11°30'P1(11.5)=0.199361, 由定理2.3.1知，误差为,§2.3 拉格朗日插值方法,28/168,郑州大学2015-2016学年硕士研究生课程 数值分析 Numerical Analysis,例2.3.2 已知f (x)的观测数据 x 0 1 2 4f (x) 1 9 23 3利用这些节点构造f(x)的Lagrange插值多项式.,