第3章(1) 插值法与最小二乘法

第3章插值法与最小二乘法本章研究插值法和数据拟合的最小二乘法，它们都是用简单函数近似已知（或未知）的复杂函数。前者要求简单函数和复杂函数在某些点处的函数值相等；后者不要求相等，但要求两个函数之间的“距离”最小。§1插值法插值法要解决什么问题？用简单函数近似复杂函数，要求两者在某些点处函数值相等。为什么要研究插值法？两类问题：（1）函数)(xfy的表达式未知，只能通过实验或观测得到某些点处的函数值，要求一个过这些已知点的简单函数作为)(xfy的近似函数。如数控机床加工部件。（2）函数)(xfy的表达式已知，但只能利用过某些特定点的简单函数作为)(xfy的近似函数，计算才能够实现。如用数值方法计算定积分的值。定义1：设函数)(xfy在区间],[ba上有定义，且已知在点bxxxan10上的函数值nyyy,,,10。若存在一个简单函数)(xp，使),,1,0(,)(niyxpii成立，则称)(xp为)(xf的插值函数，点nxxx,,,10称为插值节点，)(xf称为被插值函数。插值函数通常是简单函数，如多项式，分段表达的多项式，有理函数，三角函数等。§2拉格朗日插值一、线性插值与抛物插值（一次、二次多项式插值）设函数)(xfy在区间],[ba上有定义，且已知在点bxxxan10上的函数值),,1,0(),(nixfyii。（1）线性插值（一次插值）考虑两个插值节点1,kkxx，要求线性插值多项式)(1xL，使它满足1111)(,)(kkkkyxLyxL。容易求出11111)(kkkkkkkkyxxxxyxxxxxL函数)(1xL是两个线性函数11)(kkkkxxxxxl，kkkkxxxxxl11)(的线性组合，其组合系数分别为ky和1ky。即)()()(111xlyxlyxLkkkk。这里)(),(1xlxlkk称为线性插值基函数，在节点1,kkxx处满足0)(,1)(1kkkkxlxl1)(,0)(111kkkkxlxl（2）抛物插值（二次插值）现考虑有三个插值节点11,,kkkxxx，要求二次插值多项式)(2xL，使它满足)1,,1(,)(2kkkiyxLii令插值基函数))(())(()(11111kkkkkkkxxxxxxxxxl))(())(()(1111kkkkkkkxxxxxxxxxl))(())(()(11111kkkkkkkxxxxxxxxxl它们满足0)(,0)(,1)(11111kkkkkkxlxlxl0)(,1)(,0)(11kkkkkkxlxlxl1)(,0)(,0)(11111kkkkkkxlxlxl因此二次多项式)()()()(11112xlyxlyxlyxLkkkkkk就是满足插值条件的多项式。二、拉格朗日插值多项式拉格朗日插值多项式是插值多项式的一般情况，讨论的是经过1n个节点nxxx10的次数不超过n的插值多项式)(xLn，使它满足条件iinyxL)(，ni,,1,0定义2：n次多项式nkxxxxxxxxxxxxxxxxxlnkkkkkknkkk,,1,0,)())(()()())(()()(110110称为节点nxxx,,,10上的n次插值基函数。容易验证),,1,0,(,0,1)(nkjjkjkxlkj利用插值基函数，满足插值条件的插值多项式为nkkknxlyxL0)()(上式称为拉格朗日插值多项式。三、插值多项式的存在唯一性定理1（插值多项式的存在唯一性）在次数不超过n的多项式集合nH中，满足niyxLiin,,1,0,)(的插值多项式是存在且唯一的。证明存在性已经构造出来，下面证明唯一性。反证法。假设另有nHxP)(，满足nkyxPkk,,1,0,)(令)()()(xPxLxQn，则)(xQ是次数不超过n的多项式。一方面，由代数基本定理，)(xQ在复数域上至多有n个零点；另一方面，nkxPxLxQkknk,,1,0,0)()()(，说明)(xQ在复数域上有1n个不同的根，这是矛盾。故有)()(xPxLn。四、插值余项与误差估计若在],[ba上用)(xLn近似)(xf，则其截断误差为)()()(xLxfxRnn)(xRn也称为插值余项。定理2（插值多项式的余项）设)()(xfn在],[ba上连续，)()1(xfn在),(ba内存在，节点bxxxan10，)(xLn是满足条件)()(kknxfxL，nk,,1,0的插值多项式。则对任何],[bax，插值余项)()!1()()()()(1)1(xwnfxLxfxRnnnn这里依赖于x，)())(()(101nnxxxxxxxw。证明因为)()()(xLxfxRnn有1n个根],[,,,10baxxxn，可设)()()()()(1xwxKxLxfxRnnn，对于给定的],[bax，构造辅助函数)())()(()()()(10nnxtxtxtxKtLtft则)(t有2n个互异根xxxxn,,,,10。根据Roll定理，)(t有1n个互异根，)(t有n个互异根，…，)()1(tn有一个根，即存在),(ba，0)()!1()()()1()1(xKnfnn所以)!1()()()1(nfxKn从而)()!1()()()()(1)1(xwnfxLxfxRnnnn。由于),(ba的位置不能确定，故余项的大小难以确定，通常给出截断误差限。令)(max)1(],[1xfMnbaxn则插值多项式)(xLn近似)(xf的误差限为)()!1()(11xwnMxRnnn。例1已知352274.036.0sin,333487.034.0sin,314567.032.0sin，用线性插值以抛物插值计算3367.0sin的值，并估计截断误差。解由题意取352274.0,36.0333484.0,34.0314567.0,32.0221100yxyxyx（1）用线性插值计算。)3367.0(3367.0sin1L010110103367.03367.0xxxyxxxy330365.0。截断误差))((!2)(1021xxxxMxR，其中3335.0sinsinmax)(max121010xxxfMxxxxxx。于是5111092.00033.00167.03335.021)3367.0(3367.0sin)3367.0(LR（2）抛物插值计算)3367.0(3367.0sin2L))(())(())(())(())(())((120210221012012010210xxxxxxxxyxxxxxxxxyxxxxxxxxy0008.0105511.0352274.00004.01089.3333487.00008.0107689.0314567.0444330374.0截断误差))()((!3)(21032xxxxxxMxR其中828.0cos)(max0],[320xxfMxxx于是0233.0033.00167.0828.061)3367.0(3367.0sin)3367.0(22LR610178.0。例2给定xxf)(的函数表如下：x144169225)(xf121315写出二次Lagrange插值多项式，并计算)175(f的近似值。解：设225,169,144210xxx。二次Lagrange插值基函数为)225)(169(20251))(())(()(2010210xxxxxxxxxxxl)225)(144(14001))(())(()(2101201xxxxxxxxxxxl)169)(144(45361))(())(()(1202102xxxxxxxxxxxl二次Lagrange插值多项式为：)()(13)(12)()()()(22102211002xlyxlxlxlyxlyxlyxL将175x代入)(2xL，得23015873.13)175(175)175(2Lf取10位有效数字：613.2287565175)175(f精确误差：321040217.1)175()175(fL截断误差的估计：))()((!3)(21032xxxxxxMxR其中6250],[31050701.183)(max20xxfMxxx因此321033591.2)175(R。§3分段插值法一、高次多项式插值的Runge现象根据区间],[ba上给出的节点作插值多项式)(xLn，并非)(xLn的次数越高逼近)(xf的效果就越好。一般情况下，即使插值节点数n，也不能保证)(xLn在],[ba上一致收敛于)(xf。换言之，不论n多大，总可能存在点],[bax，)(xLn与)(xf的差异很大。这种现象称为Runge现象。因此，通常不用高次插值，而用低次插值，即采用分段低次插值函数近似给定的函数)(xf。二、分段线性Lagrange插值所谓分段线性插值，就是用折线段将曲线上的点),,1,0(),,(nkfxkk连接起来，用来近似曲线)(xf。设已知节点bxxxan10上的函数值nfff,,,10.取相邻的两个节点1,kkxx形成插值子区间],[1kkxx，做线性插值多项式)1,,1,0()(1111)(nkxxxxyxxxxyxLkkkkkkkkkh令],[),(],[),(],[),()(1)1(21)1(10)0(nnnhhhhxxxxLxxxxLxxxxLxL则有),,1,0()(niyxLiih故称)(xLh为)(xf的分段线性插值多项式。下面估计分段线性插值多项式的误差界。记)(max,max,2101xfMhhxxhbxaknkkkk由于当],[1kkxxx时，))((2)()()()()()(1)(1kkkhhxxxxfxLxfxLxfxR其中],[1kkxx。所以在区间],[1kkxx上，有2212118))((max2))((2)()(1kkkxxxkkhMxxxxMxxxxfxRkk于是在],[ba上，有222210188max)(hMhMxRknk用线性插值函数)(1xL求)(xf在uz处的近似值，选择哪个)()(xLkh？按与u临近的原则：建议选择2个与u最近的节点。如果1iixux，选择)()(xLih，即计算)()(uLih；如果0xu，选择)()0(xLh，即计算)()0(uLh；如果nxu，选择)()1(xLnh，即计算)()1(uLnh。三、分段二次Lagrange插值分段二次插值表述上要复杂些。这里仅考虑在某点处，用分段二次插值多项式的值近似被插值函数的函数值。令以11,,kkkxxx为节点的插值基函数))(())(()(11111kkkkkkkxxxxxxxxxl))(())(()(1111kkkkkkkxxxxxxxxxl))(())(()(11111kkkkkkkxxxxxxxxxl构造二次插值多项式)()()()(1111)(xlyxlyxlyxLkkkkkk