选矿过程模拟与优化插值PPT课件

1、 二、插值法的基本思想 1概念 插值就是从一组离散的数据中，求出某些需要的中间值。例如有一组离散数据，其中点 称为结点， 是它的函数值，若用 表示它的函数（未知），插值就是在这个函数表中再插进一些所需的中间值。Nxxx,10 x0 x1x2xNx)(xfy 0y1y2yNyNyyy,10)(xfy 第1页/共59页 2基本思想 （1）设法构造一个简单函数 作为该函数 的近似式； （2）利用 ，若已知插值点， 求 的近似值。)(xPy )(xf)(xPy )(uf第2页/共59页 3插值方法 插值所用的简单函数一般都是代数多项式，可以用以下几种方法来建立： （1）利用离散数据中的任意两点，建立一

2、次插值多项式，这种方法称为线性插值。 （2）利用其中任意三点，建立二项插值多项式，这种方法称为抛物线插值。 （3）顺序选取三点，建立彼此有联系的三次多项式，这种方法称为样条插值。 （4）如果利用全部N+1点，建立N次多项式，则称为高阶插值。第3页/共59页 4插值模型的特点 （1）插值模型虽然是原函数的近似表达式，但在插值结点处，原函数值与插值函数值是相等的。 （2）插值法主要是用在一元函数的计算中。 第4页/共59页 （3）插值法只能用于内插，若要进行外插，需十分慎重，因为插值函数是在结点范围内建立的，超出这个范围，就很难保证准确性。 （4）插值多项式的最高阶次m应比插值结点N小1，若要建立

3、更低阶次的多项式作为解析表达式，就应建立分段插值。第5页/共59页3-2 线性插值一、线性插值模型建立 线性插值是最简单的插值，它仅需要二个点数据，建立直线方程来近似代替原函数 ，然后在二点之间（区间）进行插值。 在选煤模拟过程中，常常碰到一些试验数据，如筛分、浮沉等一些表格函数，如果数据间隔小，则可以用线性插值解决。)(xf第6页/共59页 设所建立的直线方程为 ，根据插值模型特点，在结点中选取与插值点相邻的两点（ ），（ ）作为插值区间。 根据解析几何可在两点之间建立直线方程： 并且有 ， 这样，利用上式，就可以计算0，1两点之间任一插值点x的函数值。)(1xPy 00, yx11, yx

4、)()(0010101xxxxyyyxPy001)(yxP111)(yxP第7页/共59页 二、线性插值算法 分段插值的方法，实质上是在众多结点中根据插值点优选出所需的结点，一旦最优构模结点选定后，就变为相应的多项式插值问题。 假定给出N+1对列表函数： 它们有k个区间，k=1，2，n，给定插 值点U ，求对应的插值函数V。 NNyyyyxxxx210210第8页/共59页如果 ，则优选的结点为： 使用计算机计算时，可根据插值点u自动选定插值结点。 kkxux11010kkyyxxkkyyxx11K从1到N循环Uxx(x(k)X(k)-u0 THEN X0=X(K1); Y0=Y（K1） X1

5、=X（K）; Y1=Y（K）NEXT K V=Y0+（Y1Y0）*（U-X0）/（X1X0）RETURN 第11页/共59页 3-3 3-3 抛物线（一元三点）和抛物线（一元三点）和拉格朗日插值模型拉格朗日插值模型 线性插值仅仅和用两个点的数据，精度自然一般很低，为了改善精度，我们可试图充分利用得到的数据，构造高阶多项式插值模型。第12页/共59页 一、抛物线插值 a过渡：上节中所构造的线性插值模型为： 变化后： 令 则上式可写成： )()(0010101xxxxyyyxP101001011)(yxxxxyxxxxxP)(0101xAxxxx)(1010 xAxxxx11001)()()(yx

6、AyxAxP第13页/共59页 当 时 ， 当 时 ， 与 称为基本插值多项式。 与 通过线性组合可以构造成一元插值多项式。0 xx1)(1010 xxxxxA0)(0101xxxxxA1xx0)(0 xA1)(1xA)(0 xA)(1xA)(1xA)(0 xA第14页/共59页 b现在我们来讨论抛物线插值模型 假如我们有原函数三个点的列表函数： 按基本多项式插值研究方法，设所求的抛物线 方程形式为： 根据插值思想，该方程应满足条件：ix1xiy2x2y0y1y0 x)()()()(2211002xAyxAyxAyxP222112002)(,)(,)(yxPyxPyxP第15页/共59页 那么

7、所构造的二次基本多项式 应满足 对第一个 多项式 ，而 都是x的二次函数，)(xA100010001)(xAi)(1xA0 x1x2x)(0 xA0)(,0)(, 1)(201000 xAxAxA0)()(2010 xAxA)(0 xA)(2xA第16页/共59页 中必含有 和 两个因子， 令 用 代入上式，同时 因为 所以： 则得到： )(0 xA1xx 2xx)()(210 xxxxxA0 xx1)(00 xA1)()(201000 xxxxxA)(12010 xxxx)()()(2010210 xxxxxxxxxA第17页/共59页 同理构造基本二次多项式 ， 使其满足 条件： 则有：)

8、(1xA)(2xA0)(, 1)(, 0)(211101xAxAxA1)(, 0)(, 0)(221202xAxAxA)()()(2101201xxxxxxxxxA)()()(1202102xxxxxxxxxA第18页/共59页 其线性组合为，即抛物线插值模型为：)()()()(2211002xAyxAyxAyxP12101200201021)()()()(yxxxxxxxxyxxxxxxxx2120210)()(yxxxxxxxx第19页/共59页 二、一元三点插值算法 （1）同样假定给出N+1对列表函数： 假定给出N+1对列表函数： 它们有k个区间，k=1，2，n，给定插值点U，求对应的插

9、值函数V。 优选构模结点有三种情况： 若 ，则选 三点。 若 ，则应取 三点NNyyyyxxxx2102101xu 210,xxx1nxuNNNxxx,12第20页/共59页 若 ，又可分两种情况：当u靠近 时，则选 ；当u靠近 时，则选 。 1kkxUxkx1kx11,kkkxxx21,kkkxxx第21页/共59页 （2）子程序： 拉格朗日一元三点插值子程序 K：=0； WH1LE DO K：=K+1； IF K=N-1 THEN K：=N2； ELSE IF K0 THEN IF THEN K:=K1；)1(kxu) 1()(ukxkxu);2(: )2();1(: ) 1 ();(:

10、)0(kxxkxxkxx);2(: )2();1(: ) 1 ();(: )0(kyykyykyy第22页/共59页);2()0(*)1 ()0(/()2(*)1 (:xxxxxuxuP);2() 1 (*)0() 1 (/()2(*)1 (:xxxxxuxuQ);1 () 2(*)0() 2(/()1 (*)1 (:xxxxxuxuR);2(*)1(*)(*:kYRkYQkYPV第23页/共59页 三、拉格朗日插值模型 从一元二点，一元三点插值模型的构造中，找出规律加以推广。 （1）关于基本插值多项式 一元二点基本插值多项式中： ，其中 一元三点基本插值多项式中：1)(, 0)(0)(, 1

11、)(11011000 xAxAxAxAjijixxxxxAxxxxxAxxxxxA)()()(01011010ji jijkijjixxxxxAxAxAxAxAxAxAxAxAxA10221202211101201000)(1)(, 0)(, 0)(0)(, 1)(0)(0)(, 0)(, 1)(第24页/共59页 （2） 关于插值模型 一元二点中： 一元三点中： 推广到一元k点应为： 由此可以得到拉格朗日插值模型为： 对N+1个结点有： 11001)()()(yxAyxAxP2211002)()()()(yxAyxAyxAxP101)()(kiiikyxAxP1,2, 1 ,0ki第25页/

12、共59页 其中 不难看出，一元二点，一元三点插值模型是拉格朗日 插值模型在 时的特例。 拉格朗日插值模型的优点在于能充分利用多点数据信 息，但多项式阶数越高，越难于计算，同时精度又不一定 提高，所以在处理实际问题时，我们则更多地采用分段插 值办法。niijijnijjniiinyxxxxyxAxP000)()(niiniiiiiiniiyxxxxxxxxxxxxxxxx0110110)()()()()()(njni,2, 1,0,2, 1,02, 1nn第26页/共59页四、拉格朗日插值算法： （1）拉格朗日插值 设给定函数 的n+1个数据点( )，( )，( )，定义的插值基函数或插值多项式

13、为： 易知： )(xfy 00, yxnnyx ,11, yxnAAA,10)()()()()()()(110110niiiiiiniiixxxxxxxxxxxxxxxxxAnkikniikxAki, 2, 1, 00, 2, 1, 01)(第27页/共59页 令： 则： ， 这说明n次多项式 正好经过全部数据点，因此 就是要求的插值多项式。称形如式的多项式为拉格朗日多项式。niiinyxAxP0)()()()(iiinxfyxPni, 2, 1, 1)(xPn)(xPn第28页/共59页 （2）算法 对 做循环 对 做循环 若 ，则 0 . 1Ani, 1 , 0nj, 1 , 0ji )/

14、()(jijxxxxAA)()()(ixfAxfxf第29页/共59页 （3）程序 TYPE ARR=ARRAY1N of real； Procedupe Lagran (N:integer; x,y:ARR; X1:real; var y1:real); LABEL EXIT; Var EPS,A:real; I,j,k:integer; Begin EPS:=1.0E30; y1:=0.0; For i:=1 to N do Begin A:=1.0; For j:=1 to N do Begin第30页/共59页 IF (JI) THEN IF(ABS(Xi-Xj)=EPS) THEN

15、BEGINWriteln (数据点有误！)；GOTO EXIT END ELSE A：=A*（x1-xj）/(xi-xj) END; ; EXIT;END; END;*1:1iyAyy第31页/共59页 例：给定列表函数 求 时的五位数近似插值P(23)。 解： )(xfy202224260.342020.374610.40674 0.43837ix)(ixf23x0625. 0)23(;)(0000AxxxxxAiii5625. 0)23(;)(1101AxxxxxAiii5625. 0)23(;)(2222AxxxxxAiii第32页/共59页0625. 0)23(;)(3333Axxxx

16、xAiii39074. 0)23()()23(30iiiAxfy第33页/共59页 作业3： 某厂原煤浮沉资料如下，试分别用线性插值，拉格朗日一元三点插值和拉格朗日插值计算密度为1.35, 1.45和1.55时的浮物累积产率和灰分。 1.31.31.41.41.51.51.61.61.8+1.8y%23.7447.569.393.282.1013.93Ag%5.7610.1119.3128.7538.9680.18第34页/共59页3-4 样条插值的应用 1为何要建立样条插值 分段插值的缺点是在连接处不能保证光滑地过渡，如果采用其插值结果绘制曲线，则很难保证曲线光滑，用高阶插值虽可弥补这个缺点

17、，但因次数越高、计算越繁，误差往往也大，要保证连接处有一定的光滑性，一般采用样条插值。 2什么是样条插值 样条插值是一种改进的分段插值，它在每个由相邻节点组成的小区间，都构造一个三次或两次函数，为了在连接处保持光滑，在节点上保持一阶连续导数。第35页/共59页 3三次样条函数的建立 设给定节点的序列为： 其中， 要求构造一个函数 ，使其满足三次样条函数的三个条件： (1)函数通过相应的节点，即 (2)在区间 上， 具有一阶和二阶连续导数。 (3)在每个小区间 上， 是x的三次多项式。 iiyx ,Ni,2, 1 ,0nxxxx210)(xSNiyxSii, 2 , 1 , 0)(Nxx ,0)

18、(xS1,iixx)(xS第36页/共59页 根据上述条件可以导出三次样条函数表达式： 设三次样条函数为 ，在 上， 若要满足插值条件，则三次多项式可构造为： 根据第一个条件，显然 将式对x求导： )(xS1,iixx)()(xSxSi)()()(11111iiiiiiiiiiixxxxbaxyxxxxyxxxxxSiiiyxS)(11)(iiiyxS)()()()(11111iiiiiiiiiiixxbaxxxbaxxxxxaxxyxxyxS第37页/共59页 若用 表示 在 处的一阶导数，则： ， 将 和 分别代入式得 式中 解上面方程组可得： im)(xSiixiiimxS)(11)(i

19、iimxSixx1ixxiiiiiiiiiiiihbaxhyymhbaxhyym)()(1111iiixxh1第38页/共59页 的二阶导数为：3121)(2iiiiiihyyhmma211311)(iiiiiiiiiihmxmxhyyxxb)(xS132132)(126)(126)( iiiiiiiiyxxhhyxxhhxS132132)(62)(62iiiiiiiiiimxxhhhmxxhhh第39页/共59页 于是有：11222466)( iiiiiiiiimhmhyhyhxS112214266)( iiiiiiiiimhmhyhyhxS第40页/共59页 因此同样有： 在区间 的右端点

20、 的二阶左导数为： 而在子区间 左端点 的二阶右导数为： ,1iixxixiiiiiiiiimhmhyhyhxS111211214266)( ,1iixxix11222466)( iiiiiiiiimhmhyhyhxS第41页/共59页 根据 在 连接点处二阶导数连续, 则有： 即: 式中 该式对所有连接点 均成立，由此可以得到N1个含 的方程式。)(xSix)()( iixSxS)()(132)1 (11111iiiiiiiiiiiiyyhayyhamammaiiiihhha11121,Nxxx), 1 , 0(Nimi第42页/共59页 将a、b值代入式得 ： 式中： 插值节点及函数值 ;

21、 系数， ; 表示 在 处的一阶导数。 只要求出了 ，即求出了三次样 条函数。 可以通过二阶导数连续来求。(2)(3)(2)(3)(iiiiiiiiiiiyxxhxxhyxxhxxhxS1332231321)(1)(1)(1)(1iiiiiiiiiiiimxxhxxhhmxxhxxhhiiyx ,ihiiixxh1im)(xsix), 1 , 0(Nimiim第43页/共59页 注意：二个边界点的二阶导数取 ， 即按自然样条处理。可得三条角线方程组：00nmm111212322121211010010102)1(2)1(2)1()(32NNNNNNmammamamma

22、mammayyhmm第44页/共59页NNNNNNmmmmmaaaaaa12101210112211212)1 (2)1 (2)1 (12第45页/共59页 补充补充：“追赶法追赶法”解三对角线方程组解三对角线方程组： 简记 nnnnnnniiifffxxxbacbacbacbacb212111122211fax第46页/共59页 其中： 当 时， (a) (b) (c) 解：解：首先将系数矩阵A分解为二个矩阵，即 A=LU 其中L为下三角矩阵，U为单位上三角矩阵，则 有：, 0ija1 ji011 cb0,iiiiicacab)1, 3 ,2(ni0nnab第47页/共59页 其中 为待定系

23、数。 比较上面矩阵两边和已知条件，可得分解的二个 矩阵系数。 11112122111122211nnnnnnnniiirrbacbacbacbacbAiiir,第48页/共59页 求解 等价于解二个三角形方程组 （1） ，求y （2） ，求x 从而得到解三对角线方程组的追赶法公式：), 3 , 2(), 3 , 2()1, 3 , 2()/(/111111niavniabniabcbcbiiiiiiiiiiifAxyUxfLUx ,fLy yUx 第49页/共59页 1计算 的递推公式 2解 3解 i), 3 , 2()/(/1111niabcBbciiiiifLy ), 3 , 2()/()

24、(/11111niabyafybfyiiiiiiiyUx ) 1 , 2, 2, 1(1nnixyxyxiiiinn第50页/共59页 我们将计算系数 及 过程称为“追”的过程，将计算方程组的解 的过程称为“赶”的过程。 121nnyyy2111xxxnn第51页/共59页 3-4 埃尔米特插值的应用 一、插值思想方法： 这种插值方法是在相邻节点之间建立一个三次多项式 ，这个多项式不但要通过节点，同时，在节点处的一阶导数应等于原函数的一阶导数，即： 这样从几何上来看，近似式 和原函数 不但通过共同点，而且在这些点上的切线也相等，保证了插值函数所画出的曲线的光滑性。 )(xP)()(),()(iiiixfxPxfxP)(xP)(xf第52页/共59页 二、函数的建立 设有N+1组数据 ，因此 可以分为N个分段，在每个分段中，相邻两节点 可以建立一个三次多项式： 根据埃尔米特插值思想，即：通过结点，节点处一阶导数等于原函数一阶导数。则对相邻节点 可列出下列方程组： ), 2 , 1 , 0(,Niyxii,N,idxcxbxayiiii2123),(),(11iiiiyxyx第53页/共59页 其