机器学习计算方法函数插值与曲线拟合

计算方法1第5章函数插值与曲线拟合5.1引入——图像缩放5.2拉格朗日插值法5.3牛顿插值法5.4三次埃尔米特插值5.5差分与等距节点地插值公式5.6曲线拟合与最小二乘法2第5章函数插值与曲线拟合5.1引入——图像缩放5.2拉格朗日插值法5.3牛顿插值法5.4三次埃尔米特插值5.5差分与等距节点地插值公式5.6曲线拟合与最小二乘法35.1引入——图像缩放我们所说地图像都是指点阵图,也就是用一个像素矩阵来描述图像对于另一种图像:用函数来描述图像地矢量图,不在本文讨论之列。4当点阵图类型地图像放大时,像素也会相应地增加,那么这些增加地像素从何而来呢？这时插值方法就派上用场了。插值可以在不生成光学像素地情况下增加图像像素大小其方法是在缺失像素周围像素值地基础上使用数学公式计算该缺失像素值。所以在放大图像时,图像看上去会比较平滑,干净。但需要注意地是插值并不能增加图像地光学信息。5常见地图像处理方法最近邻插值算法双线性插值算法双三次插值算法6最近邻插值算法7当图片放大时,"照搬"旁边地像素也就是缺失地像素值通过直接使用与之最接近地原有像素值生成假设有一个3×3地256级灰度图地像素矩阵A:放大成一个4×4大小地256级灰度图地像素矩阵为B最近邻插值算法8用A矩阵地元素值填充B矩阵地元素值。设矩阵地行坐标与列坐标为从0开始地整数Bx为欲填充地矩阵B某个位置地横坐标By为欲填充地矩阵B某个位置地纵坐标Ax为B映射回矩阵A之后该位置地横坐标Ay为B映射回矩阵A之后该位置地纵坐标则有对应关系如下:Ax=Bx×(A地列数/B地列数)(5.1.1)Ay=By×(A地行数/B地行数)(5.1.2)最近邻插值算法9Ax或Ay出现小数时,采用四舍五入地方法把非整数坐标转换成整数。也可以采用直接舍掉小数位地方法B(1,0)对应地A地坐标(1,0),计算方法为:(1×(3/4),0×(3/4))=>(0.75,0)=>(1,0)由此可得B(1,0)=A(1,0)=88放大后地像素矩阵B为:10插值像素数码变焦公元六世纪,我国刘焯将等距二次插值应用于天文计算;十七世纪,牛顿,格雷哥里建立了等距节点上地一般插值公式;十八世纪,拉格朗日给出了非等距节点上地插值公式。插值方法在数值分析地许多分支(例如,数值积分,数值微分,微分方程数值解,曲线曲面拟合,函数值近似计算,等等)均有应用。11第5章函数插值与曲线拟合5.1引入——图像缩放5.2拉格朗日插值法5.3牛顿插值法5.4三次埃尔米特插值5.5差分与等距节点地插值公式5.6曲线拟合与最小二乘法125.2拉格朗日插值法基本原理函数是通过实验与观测得到地,不知道具体地解析表达式有明确地解析表达式,但由于形式复杂,不便于进行分析与计算13数学描述设函数y=f(x)在[a,b]上是有定义地,已知x0,x1,···,xn∈[a,b]与f(x)在xi(i=0,1,...,n)点地值yi=f(xi)或直至r阶导数值f(k)(xi)k=1,...,r.若存在一个简单函数,使14(5.2.1)(5.2.2)或还有成立则称(x)插值函数f(x)被插值函数xi(i=0,1,...,n)插值节点[a,b]插值区间(5.2.1)（5.2.2）式插值条件求插值函数(x)地方法称为插值法15数学描述设为次数不超过n地代数多项式,其中a0,a1,···,an为系数。当取插值函数(x)=Pn(x)时,称此插值法为代数多项式插值Pn(x)称为代数插值多项式。16数学描述175.2.1Lagrange插值设函数y=f(x)在[a,b]上有定义,x0,x1,···,xn为[a,b]上n+1个互异地点。已知f(x)于点xi地值yi,求一个不高于n次地代数多项式

使之满足(5.2.3)1818Ln(x)地存在性与唯一性由插值条件(5.2.3)式可知,Ln(x)地系数a0,a1,···,an满足(5.2.4)1919要证明Ln(x)是存在地且唯一地,只需求证明a0,a1,…,an地存在且唯一即可。而(5.2.4)是一个以a0,a1,…,an作为未知数地n+1阶线性方程组,此方程组解存在且唯一地充分必要条件是此方程组系数行列式不为零。由于此系数行列式2020是Vandermonde行列式,利用节点互异,知Vn(x0,x1,…,xn)≠0此方程组有唯一解,从而插值多项式Pn(x)是存在地且唯一地.通常我们并不使用解线性方程组地方法去求插值多项式,而是采用不同地方法去构造插值多项式。21215.2.2插值余项函数f(x)地插值多项式Ln(x)只是在x0,x1,…xn处有若x≠xi(i=0,1,…,n),则一般地令Rn(x)=f(x)-Ln(x),则Rn(x)表示用Ln(x)代替f(x)时,在点x处产生地误差,称为插值余项或截断误差项。222223定理5.1设,在内存在,节点,,则对任何有(5.2.7)23若f(x)在[a,b]区间上有直到n+1阶导数,xi(i=0,1,…,n)为[a,b]上地插值节点,xi互异,Ln(x)为f(x)满足(5.2.3)式地n次插值多项式,对[a,b]上任何取定地x≠xi,记从而有函数24在t=x,x0,x1,…xn这n+2个点处取零值,反复应用Rolle定理n+1次,则至少存在一个点ξ∈(a,b),使得从而有25(5.2.5)(5.2.6)25将F地表达式代入(5.2.6)式,得插值余项公式26其中ξ∈(a,b).

265.2.3插值公式27已知函数表要构造一个次数不超过1次地多项式L1(x),使得它满足插值条件xx0x1yy0y11线性插值28线性插值290xyx1x0y0y1y=f(x)y=L1(x)点斜式对称式301线性插值31l1(x)l0(x)(5.2.11)322抛物线插值已知函数表要构造一个次数不超过2次地多项式L2(x),使得它满足插值条件:xx0x1x2yy0y1y22抛物线插值330xyy=f(x)x0x1y0y1y2x2y=L2(x)342抛物线插值(5.2.12)其中3一般插值公式35已知要构造一个次数不超过n地多项式Ln(x),使得它满足(n+1)个插值条件:xx0x1x2··········xnyy0y1y2··········yn3一般插值公式构造n次多项式li(x)使其满足如下条件36(5.2.8)由于li(x)=0有n个根x0,x1,···,xi-1,xi+1,···,xn,故设由li(xi)=1,可求出称li(x)为以x0,x1,…xn为节点地插值基函数n次拉格朗日插值多项式为(5.2.9)(5.2.10)3738带余项地Lagrange插值公式余项为例5.1已知,求解1:选择x0=121,x1=144为插值节点,则

3939例5.1已知,求解2:选取x0=100,x1=121,x2=144,则40

故有40结果比较线性插值(n=1)11.17391抛物线插值(n=2)11.18107拉格朗日插值(n=3)11.18047准确值11.1803441是否插值多项式地次数越高,结果越准确呢？一般情况下,如何估计拉格朗日插值结果地精度呢？42?Runge现象蓝:f(x)绿:L5(x)黑:L6(x)红:L10(x)43例5.2已知函数分别用线性插值与抛物线插值计算sin0.3367地值,并估计误差。44x0.320.340.36sinx0.3145670.3334870.352274解:1用线性插值计算由定理5.1知误差为45解:1用线性插值计算

46

2用抛物线插值计算472用抛物线插值计算

48第5章函数插值与曲线拟合5.1引入——图像缩放5.2拉格朗日插值法5.3牛顿插值法5.4三次埃尔米特插值5.5差分与等距节点地插值公式5.6曲线拟合与最小二乘法4949拉格朗日插值已知要构造一个次数不超过n地多项式Ln(x),使得它满足插值条件xx0x1x2··········xnyy0y1y2··········yn5050定义5.1称函数f(x)于点xi,xj(xi≠xj)上地平均变化率为f(x)在xi,xj处地一阶差商,记作f[xi,xj],即一阶差商地差商为f(x)在点xi,xj,xk处地二阶差商,记作f[xi,xj,xk],即51(5.3.1)(5.3.2)51一般地,在求出f(x)地m-1阶差商之后,就可以构造f(x)地m阶差商,称

为f(x)在点xi0,xi1,…,xim处地m阶差商特别地,规定零阶差商f[xi]=f(xi)52(5.3.3)52差商地性质零阶差商f[xi]=f(xi)k阶差商5353差商地性质54k阶差商可表示为函数值f(x0),…,f(xk)地线性组合,即各阶差商均具有对称性,即改变节点地位置,差商值不变.f[x0,…,xk]=f[x1,x0,x2,…,xk]=f[x1,x2,…,xk,x0](5.3.4)(5.3.5)54差商地性质差商与导数地关系若f(x)是n次多项式,则一阶差商是n-1次多项式计算各阶差商,可按差商表进行55(5.3.6)55差商表构造按照给定顺序x0,x1,…,xn,计算差商表56节点零阶差商一阶差商二阶差商三阶差商四阶差商x0f(x0)x1f(x1)f[x0,x1]x2f(x2)f[x1,x2]f[x0,x1,x2]x3f(x3)f[x2,x3]f[x1,x2,x3]f[x0,x1,x2,x3]x4f(x4)f[x3,x4]f[x2,x3,x4]f[x1,x2,x3,x4]f[x0,x1,x2,x3,x4]5657Newton插值多项式575858595960606161n次Newton插值多项式62(5.3.8)62由插值多项式地唯一性可知,当f(n+1)(x)存在时,n次Newton插值多项式地余项与n次Lagrange插值多项式地余项相同,即介于x,x0,x1,…,xn之间6363在实际计算中,特别当函数f(x)地高阶导数比较复杂或f(x)地表达式没有给出时,常用差商来表示插值余项公式。由差商与导数地关系(5.3.6)式,有64(5.3.10)64Newton插值法1）各阶差商可以由差商表给出,Newton插值法使用地是差商表中斜线部分（带横线差商）2）每当增加一个插值节点,只需求增加一项就行了,即有3）Newton余项与Lagrange方法相同65654）牛顿插值法求解过程根据给定节点构造差商表;根据差商表写出Nn(x);将x代入66665）插值节点地选择极小值原则避免出现高次插值,不稳定6767红色曲线是龙格函数

蓝色曲线是5阶多项式

绿色曲线是9阶多项式

随着阶次地增加,误差逐渐变大68龙格现象68例5.3已知函数地函数表,69xkf(xk)0.400.410750.550.578150.650.696750.800.888110.901.026521.051.25386作插值多项式计算f(0.596)=sh0.596地值69解:差商表地计算结果见表。由表中可以看出其四阶差商相同,则五阶差商为0,因此可取四次插值多项式。根据极小化原理选择0.40~0.90地5个节点作为插值节点,由(5.3.8)式,有于是,f(0.596)=sh(0.596)≈N4(0.596)=0.63192.70f(0.596)地差商表计算结果节点零阶差商一阶差商二阶差商三阶差商四阶差商0.400.410751.11600.550.578150.28001.18600.1970.650.696750.35880.0341.27570.2140.800.888110.43360.0341.38410.2370.901.026520.52601.51561.051.2538671第5章函数插值与曲线拟合5.1引入——图像缩放5.2拉格朗日插值法5.3牛顿插值法5.4三次埃尔米特插值5.5差分与等距节点地插值公式5.6曲线拟合与最小二乘法7272许多应用问题不但要求构造插值函数在节点上地值与被插函数值相等地条件外,还要求它地导数值也要与被插函数地导数值相等,如一阶导数值,高阶导数等这种插值称为Hermite(埃尔米特)插值。7373整齐地Hermite插值,节点处地函数值与导数值成对出现。非整齐地Hermite插值,节点处地函数值与导数值不成对出现。7474问题一整齐地已知下面地函数表,构造Hermite插值多项式H3(x),使得xx0x1yy0y1y’m0m17575解1基于插值基函数构造插值多项式(5.4.2)令

容易验证H3(x)满足Hermite插值条件7677插值基函数应有下面形式其中:a,b,c,d,e,f为待定系数。7778由基函数固有性质带回到式(5.4.2)中,即可得到满足插值条件地多项式H3(x)78插值余项(5.4.7)79已知x0,x1处函数值与导数值,在构造差商表时,引入重点x0,x1,（已知导数值地点为重合节点）。对于差商表中地一阶差商f[z0,z1],根据导数定义8080解2（利用差商地方法）写出差商表z0=x0f(z0)z1=x0f(z1)f’(x0)z2=x1f(z2)f[z1,z2]f[z0,z1,z2]z3=x1f(z3)f’(x1)f[z1,z2,z3]f[z0,z1,z2,z3]8181问题二非整齐地已知下面地函数表,构造Hermite插值多项式H2(x),使得82xx0x1x1yy0y1m1y’m182解1基于插值基函数构造插值多项式(5.4.11)

容易验证H3(x)满足Hermite插值条件(5.4.10)83解1基于插值基函数构造插值多项式根据多项式零点性质,易知四个基函数应具有如下形式:其中A,B,C,D,E为待定系数,可根据(5.4.10)中地非零点条件确定。这样,最后可以得到四个基函数为84解1基于插值基函数构造插值多项式其中A,B,C,D,E为待定系数,可根据(5.4.10)中地非零点条件确定。这样,最后可以得到四个基函数为

这样,Hermite插值多项式H3(x)可由(5.4.11)-(5.4.15)式确定,插值余项为:其中85解2（利用差商地方法）写出差商表z0=x0f(z0)z1=x1f(z1)f[z0,z1]z2=x1f(z2)f’(x1)f[z0,z1,z2]z3=x2f(z3)f[z1,z2]f[z1,z2,z3]f[z0,z1,z2,z3]8686三次Hermite插值非整齐地插值余项

i地取值取决于给定地插值条件整齐地插值余项8787第5章函数插值与曲线拟合5.1引入——图像缩放5.2拉格朗日插值法5.3牛顿插值法5.4三次埃尔米特插值5.5差分与等距节点地插值公式5.6曲线拟合与最小二乘法88885.5差分与等距节点地插值公式在计算过程中,常常遇到插值节点均匀分布地情况,即节点等距表示为xi=x0+ih(i=0,1,…,n)其中h是正常数,称为步长.这时差商与Newton插值公式可借助于差分地概念进行简化89设函数f(x)在等距节点xi=x0+ih上地值为yi=f(xi)(i=0,1,…,n)定义4.2称yi＋1－yi为函数f(x)在xi节点处地以h为步长地一阶向前差分,简称为一阶差分,记为△yi,即(5.5.1)90类似地,称节点xi与xi＋1处地一阶差分地差分△yi＋1－△yi为f(x)在点xi处地二阶差分,记为一般称m-1阶差分地差分

为f(x)在点xi处地m阶差分(5.5.2)91定义4.3称

为函数f(x)在xi节点处地以h为步长地一阶向后差分,称

为f(x)在xi处以h为步长地m阶向后差分(5.5.3)(5.5.4)92差分地性质各阶差分均可表示为函数值地线性组合93(5.5.5)(5.5.6)差商与向前差分地关系差商与向后差分地关系(5.5.7)(5.5.8)94各种差分之间可以转化向前差分与导数地关系仿照差商表地构造,各种差分计算也可以排列成表(5.5.10)95(5.5.9)向前差分表96xiyiΔyiΔ2yiΔ3yiΔ4yix0y0

x1y1Δy0

x2y2Δy1Δ2y0

x3y3Δy2Δ2y1Δ3y0

x4y4Δy3Δ2y2Δ3y1Δ4y0向后差分表97xiyi∇yi∇2yi∇3yi∇4yix4y4

x3y3∇y4

x2y2∇y3∇2y4

x1y1∇y2∇2y3∇3y4

X0y0∇y1∇2y2∇3y3∇4y4Newton向前插值公式用来计算函数表靠近前面x0附近(x∈[x0,x1],此时0<t<1)地函数值98前插公式地余项为99Newton向后插值公式用来计算函数表靠近前面xn附近(x∈[xn-1,xn],此时(-1<t<0)地函数值,因此也称为表末插值公式100后插公式地余项为101例5.6已知f(x)=sinx地函数表,分别用二次前插,后插公式计算sin0.57891地值与误差。x0.40.50.60.7sinx0.389420.479430.594640.64422102例5.6已知f(