第四章―插值与拟合

第四章插值与拟合本章内容插值概念与基础理论Lagrange(拉格朗日）插值多项式Newton（牛顿）插值多项式Hermite（埃尔米特）插值分段低次插值与三次样条插值三次样条插值曲线拟合的最小二乘法一.问题提出：两个变量x,y内在关系一般由函数式y=f(x)表达。但在实际问题中，有两种情况：1.由实验观测而得的一组离散数据(函数表),虽然y=f(x)存在且连续,但未知。2.函数解析表达式已知,但计算复杂,不便使用。通常也造函数表。如:y=sin(x),y=lg(x)。有时要求不在表上的函数值,怎么办？§4.1插值概念与基础理论)()()()()()(,],[)()()()(:),...,2,1,0()(,,],[)(,xPxxxPxfxRxbaxfxxfxnixfybaxfyiiiii多项式插值为多项式函数或者取三角插值为三角函数通常取叫截断误差叫插值节点插值区间区间插值法插值条件使被插函数近似代替插值函数用简单函数希望只知离散数据但未知上存在且连续在区间函数实际中§4.1插值概念与基础理论二.几何意义：两条曲线有交点（公共点）从几何上看,插值问题即:已知平面上n+1个不同的点(xi,yi)(i=0,1,2,...n),要寻找一条过这些点的多项式曲线。（不超过n次）问题：（1）满足插值条件的插值多项式P(x)是否存在？应该是几次多项式？（n次）（2）如果满足插值条件的多项式P(x)存在，应如何构造？（3）用插值多项式P(x)近似代替f(x)，误差如何？三.插值多项式的存在和唯一性存在且唯一。的多项式的次数不超过处满足插值条件个互异节点在定理)(),...,2,1,0()()(1:1xpnnkxfxpxnnkknk)(..............................................)(...)(...:....)(:10111100001010nnnnnnnnnnnnxfxaxaaxfxaxaaxfxaxaaxaxaaxp代入插值条件得设证线性代数“方阵的行列式”部分：线性方程组…的系数行列式D0时，方程组…有且仅有一个解…存在唯一。系数即多项式该方程组解存在唯一法则知故由系数行列式)(,,0)(111:01100Cramerxxxxxxxxnijjinnnnn(n+1)阶范德蒙(Vandermonde)行列式范德蒙(Vandermonde)行列式证明用数学归纳法证明1112112222121).(111jinjinnnnnnnxxxxxxxxxxxD§4.2Lagrange插值多项式拉格朗日中值定理：0)('),()()())((')()(),()ba,(2],[1)(fbabfafabfafbfbabaxf，有则存在若。使则存在可导，）在（连续，）在（满足：如§4.2Lagrange插值多项式十八世纪法国数学家Lagrange对以往的插值算法进行研究与整理，提出了易于掌握和计算的统一公式，称为Lagrange插值公式。它的特例是线性插值公式和抛物线插值公式。线性插值抛物线插值Lagrange插值插值多项式的余项——误差估计§4.2Lagrange插值多项式一.线性插值已知两个插值点及其函数值：求一次多项式使得插值节点对应的函数值1010)(ffxfxxx,)(1bxaxL11110001)()(fbxaxPfbxaxP§4.2Lagrange插值多项式由于方程组的系数行列式所以，按Gramer法则，有唯一解于是或（公式1）0110110xxxx01011010011001101100111111xxffxxffbxxfxfxxxxfxfa,)(01010110011xxxffxxfxfxxL101001011)(fxxxxfxxxxxL§4.2Lagrange插值多项式容易验证，过点(x0,f0)与(x1,f1)直线方程就是上式(公式1)，如下图所示。yxx0x1L1(x)f(x)P1(x)f(x)误差§4.2Lagrange插值多项式例：已知解：用线性插值公式(公式1)，计算得到的近似值。求16.3ln,1632.11314.1ln2.31.3xx1505.115048.11632.11.32.31.316.31314.12.31.32.316.3)16.3(1L1505.116.3ln即§4.2Lagrange插值多项式[应用条件]：右图表明，对于象y=lnx这样连续光滑的曲线，当两个插值节点很近并且所求的函数值也很近时，用线性插值方法是足以保证精度的。xy1lnxL1(x)3.13.23.161.16321.13141.1505§4.2Lagrange插值多项式二.抛物线插值已知三个插值节点及其函数值：求二次多项式使得插值节点对应的函数值210210)(fffxfxxxx,)(22cxbxaxL222222121112020002)()()(fcxbxaxPfcxbxaxPfcxbxaxP§4.2Lagrange插值多项式容易得到满足上述条件，所以它就是所求的二次多项式。2120210121012002010212))(())(())(())(())(())(()(fxxxxxxxxfxxxxxxxxfxxxxxxxxxL§4.2Lagrange插值多项式L2(x)是过点(x0,f0)、(x1,f1)与(x2,f2)三点的抛物线，如下图所示。yxx1x0x2L2(x)f(x)f0f1f2§4.2Lagrange插值多项式例：已知解：用(公式2)，计算得到的近似值。用抛物线插值公式求)2.1(,403)(211fxfx1495614)12)(12()1)(1(0)21)(11()2)(1()3()21)(11()2)(1()(22xxxxxxxxxL6667.0142.192.1561)2.1()2.1(22Lf即§4.2Lagrange插值多项式[应用条件]：右图表明，对于象y=f(x)为连续光滑的曲线，当三个插值节点很近但所求的函数值却相差较大时，用抛物线插值方法是可以保证精度的。L2(x)1.20.6667y12345-1-2-3x1-12f0f1f2§4.2Lagrange插值多项式三.Lagrange插值已知n+1个插值节点及其函数值：求次数不超过n的多项式Pn(x)。使得插值节点对应的函数值nnffffxfxxxxx210210)(,)(2210nnnxaxaxaaxLnnnnnnnnnnnnnnnnnfxaxaxaaxLfxaxaxaaxLfxaxaxaaxLfxaxaxaaxL2210222222102112121101002020100)()()()(§4.2Lagrange插值多项式这个n+1阶线性方程组,有唯一解,即Ln(x)是唯一确定的。容易验证:满足这些条件,所以Ln(x)就是所求的次数不超过n的插值多项式(存在性)。显然,式1、式2都是式3的特例。nnnnnnnnnnnfxxxxxxxxxxxxfxxxxxxxxxxxxfxxxxxxxxxxxxxL)())(()())(()())(()())(()())(()())(()(1101101121012000201021公式3§4.2Lagrange插值多项式插值多项式（公式3）插值基函数满足插值条件的多项式显然为：)())(()()())(()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxlnnnnnnnnnnnfxxxxxxxxxxxxfxxxxxxxxxxxxfxxxxxxxxxxxxxL)())(()())(()())(()())(()())(()())(()(1101101121012000201021nnnyxlyxlyxlxL)()()()(1100§4.2Lagrange插值多项式记则从而，对某一节点xk，有niinxxxxxxxxx010)()())(()()())(()())(()())(()(1102021nnnxxxxxxxxxxxxxxxxxxx)())(()()(110nkkkkkkkxxxxxxxxx§4.2Lagrange插值多项式Lagrange插值公式的标准型公式这样其中这改写了Lagrange插值公式，在许多理论分析中是非常有用的。nkkknfxlxL0)()()()()()(kkkxxxxxl§4.2Lagrange插值多项式四.Lagrange插值多项式的存在性、唯一性？首先我们回答两个问题：（1）满足条件式的插值多项式存在吗?（2）是唯一吗?定理满足插值条件式的插值多项式Pn(x)存在且唯一。。),,2,1()(nifyxLiiin了解§4.2Lagrange插值多项式证法1（1）存在性(采用构造性证明)构造基函数则,且令则显然有即我们找到了一个插值多项式Ln(x)nixxxxxlnijjjiji,,1,0)(0nipxl)(njijijixlii,,1,0,01)(niiinyxlxL0)(),,1,0(niyxLpxLiinnn§4.2Lagrange插值多项式证法1（2）唯一性(用反证法证明)假设有两个不同的插值多项式pn(x)和qn(x)存在令则且即有n+1个零点，所以与假设矛盾。证毕。)()(xqxpxrnnnpxr),,2,1,0(0)()(niyyxqxpxriiininixr)()(,0xqxpxrnn§4.2Lagrange插值多项式五.截断误差：xxxxnfxLxfxRbaxnnibaxnxfxLnbaxfininnnnnin且依赖于，，　其中，有意次插值多项式，则对任上的个结点在为阶导数，上有直到在区间若定理)ba()(),(!1)()()()(],[),,1,0](,[1)()(1],[)(3011)1()!1)(()()(1],[)(),()()()()()()()1()())(()(,)n,,1,0i(0)()1()1(100nxktftFnbatFtxtxtxtxktLtftFxxxxxkxRxRnnnnni阶导数上具有在区间则。其自变量为引入　式　　　　　故有形式　　因证：0)('),()()(3),(2],[1)()(fbabfafbabaxfRolle使，则至少存在一点，）（可导。）在（连续，）在（满足：如定理：回顾：罗尔)(max,)()!1()(R1)!1()()(0)!1()()(0)(),,(],[)(1],[)()(0)()()()(,,,)()1(0111)1()1()1(0)1(1010,10xfxxxMxnMxnfxknxkfxxbatFnbaxxtFRollexFxFxFxFxxxxtFnnnn