2.-第二章-数值插值方法

第二章插值方法电子科技大学生命学院陈华富2007年3月第二章插值方法插值的基本概念Lagrange插值三次样条插值2.1代数插值问题例.某地区某年夏季时节间隔30天的日出日落时间为5月1日5月31日6月30日日出5：515：175：10日落19：0419：3819：50插值：研究用简单函数为各种离散数据建立连续数学模型的方法。日照时间的变化设为y(x)=a0+a1x+a2x2,6614616135143131211322102210210.)(.)(.aaaaaaaaa求出a0,a1,a2，即可得到5、6月份的日照时间的变化规律。根据三组数据:(1,15.2167),(31,14.35),(61,14.6667)导出关于a0,a1,a2的线性方程组定义已知函数y=f(x)在[a,b]有定义，且已知它在n+1个互异节点a≤x0x1…xn≤b上的函数值y0=f(x0)，y1=f(x1),…,yn=f(xn)，若存在一个次数不超过n次的多项式Pn(x)=a0+a1x+a2x2+……+anxn满足条件Pn(xk)=yk(k=0,1,…,n)则称Pn(x)为f(x)的n次插值多项式。点x0,x1,…,xn称插值节点，f(x)为被插值函数。[a,b]称插值区间，点x称插值点。插值点在插值区间内的叫内插，否则叫外插。设Pn(x)=a0+a1x+a2x2+……+anxn是y=f(x)在[a,b]上的n+1个互异节点x0,x1,…,xn的插值多项式，则求Pn(x)问题归结为求系数a0,a1,…,an。nnnnnnnnnyxaxaayxaxaayxaxaa101111000010定理n次插值问题的解是存在而且唯一的。证明：由插值条件：Pn(xk)=yk(k=0,1,…,n)得关于a0,a1,…,an的n+1阶线性方程组故Pn(x)存在且唯一。njinjinnnnnnnxxxxxxxxxxxxxxV121211020010)(111),,()(jixxji因故上式不为0。据Cramer法则，方程组解存在且唯一。其系数行列式是Vandermonde行列式给定插值节点x0,x1，y0=f(x0)，y1=f(x1).求线性插值多项式L1(x)=a0+a1x，使满足:L1(x0)=y0,L1(x1)=y1.2.2Lagrange插值)()(0010101xxxxyyyxL001110101yxxxxyxxxxxL)(一、线性插值与抛物插值1.线性插值：n=1情形y=L1(x)的几何意义就是过点(x0,y0)，(x1,y1)的直线。L1(x)的表达式：点斜式:两点式:由两点式可以看出，L1(x)是由两个线性函数01010110xxxxxlxxxxxl)(,)(11001)()()(yxlyxlxLkjkjxljk01)(的线性组合得到，其系数分别为y0，y1。即显然，l0(x)及l1(x)也是线性插值多项式，在节点x0,x1上满足条件：l0(x0)=1,l0(x1)=0.l1(x0)=0,l1(x1)=1.称l0(x)及l1(x)为线性插值基函数。(j,k=0,1)即l0(x0)=1,l0(x1)=0,l0(x2)=0.l1(x0)=0,l1(x1)=1,l1(x2)=0.l2(x0)=0,l2(x1)=0,l2(x2)=1.2.抛物插值：n=2情形假定插值节点为x0,x1,x2，求二次插值多项式L2(x)，使L2(xj)=yj(j=0,1,2)y=L2(x)的几何意义就是过(x0,y0)，(x1,y1)，(x2,y2)三点的抛物线。采用基函数方法，设L2(x)=l0(x)y0+l1(x)y1+l2(x)y2此时基函数l0(x),l1(x),l2(x)是二次函数，且在节点上满足：满足上式的插值基函数很容易求出。如求l0(x),因x1,x2为其零点，故可表为kjkjxljk01)())(()(210xxxxAxl))((12010xxxxA))(())(()(2010210xxxxxxxxxl故即(j,k=0,1,2)其中A为待定系数，由l0(x0)=1,得显然L(x)=l0(x)y0+l1(x)y1+l2(x)y2满足条件L2(xj)=yj(j=0,1,2)))(())(()(2101201xxxxxxxxxl))(())(()(1202102xxxxxxxxxl2120210121012002010212yxxxxxxxxyxxxxxxxxyxxxxxxxxxL))(())(())(())(())(())(()(同理将l0(x),l1(x),l2(x)代入得取x0=4,y0=2，x1=9,y1=3，x2=16,y2=4.416,39,24734942499)(1xxxL6251347537952771.)()()(L4)916)(416()97)(47(3)169)(49()167)(47(2)164)(94()167)(97()7(72L6286.2)6458.27(取x0=4,x1=9,x2=16例已知求解（1）线性插值：取x0=4,x1=9（2）抛物插值：设有n+1个互异节点x0x1…xn，且yi=f(xi)(i=0,1,2…,n)构造Ln(x)，使Ln(xj)=yj(j=0,1,2,…,n)kjkjxljk01)(二、Lagrange插值多项式定义若n次多项式lj(x)(j=0,1,…,n)在n+1个节点x0x1…xn上满足条件(j,k=0,1,…,n)则称这n+1个n次多项式l0(x),l1(x),…,ln(x)为节点x0,x1,…,xn上的n次插值基函数。由n=1,2时的讨论可得Lxlxylxylxynnn()()()()0011nkiiikikxxxxxl0)()()()())(()()())(()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl(k=0,1,2,…,n)或记为(k=0,1,2,…n)故满足插值条件的多项式为称Lagrange插值多项式。定理设f(x)在[a,b]上具有n阶连续导数,且f(n+1)(x)存在,节点a≤x0x1…xn≤b，Ln(x)是满足条件Ln(xj)=yj(j=0,1,2,…,n)的插值多项式，则对任何x[a,b]，插值余项)()!1()()()()(1)1(xnfxLxfxRnnnn],[ba)())(()(101nnxxxxxxx三、插值余项与误差估计定义若在[a,b]上用Ln(x)近似f(x)，则其截断误差Rn(x)＝f(x)-Ln(x)称插值多项式的余项。其中当f(x)是n次的多项式时,Ln(x)=f(x)。即n次多项式的n次插值函数即为该n次多项式本身。))()((21)()(21)(1021xxxxfxfxR]),[(10xx))()()((61)(2102xxxxxxfxR]),[(20xx说明：n=1时，n=2时，例:225,169,144,)(三个节点为若xxf线性插值的余项为设LagrangexR)(1插值的余项为二次LagrangexR)(2解:.)175(截断误差近似值的线性和二次插值做试估计用fLagrangexxf21)(2341)(xxf2583)(xxf|)(|max2251692xfMx|)169(|f41014.1|)(|max2251443xfMx|)144(|f61051.1|)(|22xN|)225175)(169175(|300|)(|33xN|)225175)(169175)(144175(|9300|)(|1xR22!21NM3001014.121421071.1|)(|2xR33!31NM93001051.161631035.2误差更小二次插值比线性插值的用时在求从以上分析可知Lagrange175,3.3三次样条插值样条：是指飞机或轮船等的制造过程中为描绘出光滑的外形曲线(放样)所用的工具。样条本质上是一段一段的三次多项式拼合而成的曲线，在拼接处，不仅函数是连续的，且一阶和二阶导数也是连续的。1946年，Schoenberg将样条引入数学，即所谓的样条函数。因分段线性插值导数不连续，埃尔米特插值导数连续但需要已知，故引入样条插值概念。一、三次样条插值函数的定义定义：给定区间[a,b]上的一个划分：a=x0x1…xn=b，已知函数f(x)在点xj上的函数值为f(xj)=yj,(j=0,1,2,···,n)如果存在分段函数],[)(],[)(],[)()(1212101nnnxxxxSxxxxSxxxxSxS满足下述条件：(1)S(x)在每一个子区间[xj-1,xj](j=0,1,2,···,n)上是一个三次多项式；(2)S(x)在每一个内接点xj(j=0,1,2,···,n)上具有直到二阶的连续导数；则称S(x)为节点x0,x1,…,xn上的三次样条函数。若S(x)在节点x0,x1,…,xn上还满足插值条件：(3)S(xj)=yj(j=0,1,2,···,n)则称S(x)为三次样条插值函数。（即全部通过样点的二阶连续可微的分段三次多项式函数）三次样条插值多项式的确定：由(1)知，S(x)在每一个小区间[xj-1,xj]上是一三次多项式，若记为Sj(x),则可设jjjjjdxcxbxaxS23)()0()0(jjxSxS)0()0(jjxSxS要确定函数S(x)的表达式，须确定4n个未知系数{aj，bj，cj，dj}(j=1,2,…,n)。由(2)知，S(x)，S`(x)，S``(x)在内节点x1,x2,…,xn-1上连续，则)0()0(jjxSxSj=1,2,…,n-1可得3n-2个方程，又由条件(3)jjyxS)(0)()(0nxSxS)()(),()(00nnxfxSxfxSj=1,2,…,n得n+1个方程，共可得4n-2个方程。要确定4n个未知数，还差两个方程。通常在端点x0=a,xn=b处各附加一个条件，称边界条件，常见有三种：(1)自然边界条件：(2)固定边界条件：)()(),()(00nnxSxSxSxS－自然样条（最光滑）(3)周期边界条件：共4n个方程，可唯一地确定4n个未知数。例已知f(x):f(-1)=1,f(0)=0,f(1)=1，求f(x)在[-1,1]上的三次自然样条插值函数。]1,0[]0,1[)(222232112131xdxcxbxaxdxcxbxaxS11111dcba01d02d12222dcba解设由插值条件和函数连续条件得：21cc21bb02611ba02622ba023,2121212121ddccbbaa]1,0[2321]0,1[2321)(2323xxxxxxxS由一阶及二阶导数连续得：由自然边界条件得：联立上面8个方程，求解得故1.当x=1,-1,2时，f(x)=0,-3,4，求f(x)的二次插值多项式。2.已知函数y=f(x)满足如下条件：i012xi-101yi-101yi’0求一个次数不超过3次的Hermite插值多项式H3(x)，使得H3(xi)=yi，(i=0,1,2),H’3(x1)=y1’。3.考虑下述的插