代數(shù)插值多項(xiàng)式

1、第六章 代數(shù)插值多項(xiàng)式所謂函數(shù)逼近實(shí)際上就是用簡(jiǎn)單的性質(zhì)良好的函數(shù)代替復(fù)雜的或者無法用解析算式所表示的函數(shù)。函數(shù)逼近分為非插值逼近和插值逼近兩類，本書只介紹后者。插值逼近分為有理插值、代數(shù)插值、樣條插值三種，其共同特點(diǎn)就是插值函數(shù)在所選取點(diǎn)，即節(jié)點(diǎn)處和被逼近函數(shù)的值相等。顯然最容易想到的插值函數(shù)是代數(shù)多項(xiàng)式。函數(shù)逼近的理論基礎(chǔ)是Weierstrass定理。Weierstrass第一定理 任何連續(xù)函數(shù)都可用多項(xiàng)式一致逼近。Weierstrass第二定理 任何連續(xù)函數(shù)都可用三角函數(shù)一致逼近。由于這兩個(gè)定理都屬于存在性定理，存在性算法不在計(jì)算方法研究范圍之內(nèi)，故不作詳細(xì)介紹，不予證明*?！径x】 對(duì)

2、于連續(xù)函數(shù)，若有次多項(xiàng)式滿足，互異且，則稱是的n階插值多項(xiàng)式。下面是代數(shù)插值多項(xiàng)式收斂性定理。【定理】 對(duì)于連續(xù)函數(shù)，假設(shè)在內(nèi)只有有限個(gè)奇點(diǎn)，是其n階代數(shù)插值多項(xiàng)式，節(jié)點(diǎn)，且含所有奇點(diǎn)，）則有【證明】 當(dāng)時(shí)，由代數(shù)插值多項(xiàng)式的定義有，定理成立。當(dāng)時(shí)，= 當(dāng)上式,即。證畢。上面定理說明代數(shù)插值多項(xiàng)式是收斂的，但是節(jié)點(diǎn)必須包含所有奇點(diǎn)，而且相鄰兩點(diǎn)距離須充分小。6.1 Lagrange插值多項(xiàng)式n階Lagrange插值多項(xiàng)式由個(gè)對(duì)稱的結(jié)構(gòu)相同的n次多項(xiàng)式組成。Lagrange插值多項(xiàng)式主要用于數(shù)值積分的算法推導(dǎo)，在分享密鑰中也用到它。我們用表示n階Lagrange插值多項(xiàng)式。6.1.1線性Lagr

3、ange插值多項(xiàng)式設(shè)連續(xù)函數(shù)現(xiàn)用線性Lagrange插值多項(xiàng)多逼近，使，（通常取為兩個(gè)端點(diǎn)，顯然）。令，由代數(shù)插值多項(xiàng)式的性質(zhì)有 （6.1）6.1.2 二階Lagrange插值多項(xiàng)式若對(duì)函數(shù)作二階Lagrange插值多項(xiàng)式，互異，常取節(jié)點(diǎn)，令由代數(shù)插值多項(xiàng)式的性質(zhì)有 （6.2）6.1.3 n階Lagrange插值多項(xiàng)式由1階和2階Lagrange插值多項(xiàng)式的表述算式以及推導(dǎo)過程可看出1n階Lagrange插值多項(xiàng)式由n+1個(gè)n次多項(xiàng)式組成；2第i個(gè)多項(xiàng)式分成兩部份，后面是形如的次多項(xiàng)式，該多項(xiàng)式的因子只缺,前面部分是系數(shù) 當(dāng)節(jié)點(diǎn)互異時(shí)的計(jì)算公式為 （6.3）令 （6.4）式(6.4) 是常見的

4、n階Lagrange插值多項(xiàng)式，式（6.3）是本教材介紹的Lagrange插值多項(xiàng)式，和式(6.4)相比區(qū)別在于后者給出了常數(shù)的計(jì)算公式。1階和2階Lagrange插值多項(xiàng)式是根據(jù)代數(shù)插值多項(xiàng)式定義生成的，n階Lagrange插值多項(xiàng)式是根據(jù)1階和2階公式歸納出的，現(xiàn)在證明兩式是插值多項(xiàng)式。引理 證明略由引理立即得到定理 式（6.3）、式（6.4）是n階Lagrange插值多項(xiàng)式。證明：即滿足插值多項(xiàng)式定義。式(6.3)僅僅是式(6.4)的恒等變換，所以也滿足定義。證畢。6.1.4 代數(shù)插值多項(xiàng)式余項(xiàng)計(jì)算前面介紹了n階Lagrange插值多項(xiàng)式，現(xiàn)在介紹它和本身的關(guān)系。定理2 設(shè)是n 階Lag

5、range插值多項(xiàng)式是所選互異節(jié)點(diǎn)。在插值區(qū)間有n+1階連續(xù)導(dǎo)數(shù)，則 （6.5）稱為余項(xiàng)。證明：作輔助函數(shù)顯然 共n+2個(gè)零點(diǎn)。由Roll定理有有n+1個(gè)零點(diǎn)，有n個(gè)零點(diǎn)，有一個(gè)零點(diǎn)，令該零點(diǎn)為，則有由此有證畢推論 若是不高于n次的多項(xiàng)式，則。證明略。對(duì)于2個(gè)n次多項(xiàng)式，若有點(diǎn)值相同，則這2個(gè)多項(xiàng)式相等。由此知道節(jié)點(diǎn)相同的不同插值多項(xiàng)式相等，式（6.5）不僅僅是Lagrange插值多項(xiàng)式余項(xiàng)，也是所有不帶重節(jié)點(diǎn)的代數(shù)插值多項(xiàng)式的余項(xiàng)。除了出現(xiàn)重節(jié)點(diǎn)以外，以后不再介紹其它算式表述的余項(xiàng)。6.1.5 n階Lagrange插值多項(xiàng)式計(jì)算量顯然就計(jì)算而言，式(6.3)比式（6.4）科學(xué)，計(jì)算量省。 1

6、用n階Lagrange插值多項(xiàng)式作插值計(jì)算的步驟（1）形成插值多項(xiàng)式，即算出系數(shù)Ai。（2）對(duì)于任給，按式（6.3）算值。 2計(jì)算量（1）計(jì)算Ai的計(jì)算量 次乘法（2）插值計(jì)算量：次乘法雖然，插值計(jì)算量可使之成3n次乘法，但由于目前很少有人使用高階Lagrange插值多項(xiàng)式作代數(shù)插值，為了計(jì)算和程序設(shè)計(jì)方便，這里不考慮這種簡(jiǎn)化，也不詳述計(jì)算過程。Lagrange插值主要用于Newton-Cotes積分和Gauss積分的公式推導(dǎo)，用于分享密鑰系統(tǒng)的密鑰分解和還原，這一切均不必考慮計(jì)算速度，故不用上述簡(jiǎn)化。由此知對(duì)m點(diǎn)作Lagrange插值計(jì)算（對(duì)m點(diǎn)插值）的總計(jì)算為次乘法。6.1.6 Lagra

7、nge插值多項(xiàng)式計(jì)算步驟用Lagrange插值多項(xiàng)式作插值計(jì)算由二個(gè)部分組成1輸入階n,節(jié)點(diǎn)值,函數(shù)值，i=0,1,n，待插值點(diǎn)X2輸出插值結(jié)果3計(jì)算過程1）形成插值多項(xiàng)式系數(shù)計(jì)算公式為 所對(duì)應(yīng)的程序語句為for(i=0;i<n;i+) ai=f(xi); for(j=0;j<=n;j+) if(j!=i) ai=ai/(xi-xj);計(jì)算的算式實(shí)際上一求連乘積算式，為特殊項(xiàng)，通項(xiàng)為。2）求的值計(jì)算公式為上面對(duì)應(yīng)一個(gè)兩重循環(huán)，外循環(huán)是求累加和，內(nèi)循環(huán)（外循環(huán)的循環(huán)體）求連乘積。所對(duì)應(yīng)的程序語句為l=0;for(i=0;i<=n;i+) p=ai; for(j=0;j<=

8、n;j+) if(j!=i) p=p*(X-xj); l=l+p; 為了和節(jié)點(diǎn)值有所區(qū)別，程序中用X代替x6.1.7 Lagrange插值多項(xiàng)式的計(jì)算實(shí)例例 求一不高于3次的Lagrange插值多項(xiàng)式，使得，。解 節(jié)點(diǎn)及其函數(shù)值見表6-1表6-1 節(jié)點(diǎn)數(shù)據(jù)x0123y0133計(jì)算的值, , 由此得：計(jì)算L3的值6.2 Newton插值多項(xiàng)式Lagrange插值多項(xiàng)式由n+1個(gè)n次多項(xiàng)式組成，形態(tài)復(fù)雜，手算不便驗(yàn)算，作插值計(jì)算計(jì)算量大，增加一個(gè)節(jié)點(diǎn)后，原插值多項(xiàng)式不便利用，當(dāng)節(jié)點(diǎn)帶導(dǎo)數(shù)值時(shí)，Lagrange插值多項(xiàng)式無能為力。Newton給出了新的插值多項(xiàng)式Newton插值多項(xiàng)式，Newton插

9、值多項(xiàng)式有三大優(yōu)點(diǎn)：（1）增加一個(gè)節(jié)點(diǎn)時(shí)，只須在原n次插值多項(xiàng)式上增加一個(gè)n+1次多項(xiàng)式（2）能生成帶導(dǎo)數(shù)的Newton插值多項(xiàng)式（3）計(jì)算量小我們用表示Newton插值多項(xiàng)式。6.2.1 一階Newton插值多項(xiàng)式假設(shè)已知,，求，使,。前面已經(jīng)介紹了Lagrange方法，現(xiàn)在介紹Newton的方法。令由， 得 由，即，得由此得 （6.6）6.2.2 二階Newton插值多項(xiàng)式假設(shè)已知求一個(gè)二次多項(xiàng)式，使得 。令 由，由，由由此得 （6.7）6.2.3 n階Newton插值多項(xiàng)式比較式（6.6）和式（6.7）知，后者比前者多一個(gè)二次項(xiàng)，下面將結(jié)合這一特點(diǎn)介紹n階Newton插值多項(xiàng)式，為此先介

10、紹一些相關(guān)知識(shí)。定義1 給出函數(shù) 在n+1個(gè)互異點(diǎn)，稱 （6.8）為k階差商，并稱為0階差商。性質(zhì)1 k 階差商是函數(shù)值的線性組合,且滿足= （6.9）證明 當(dāng)，由一階差商的定義有性質(zhì)成立?，F(xiàn)假設(shè)，時(shí)性質(zhì)成立，即有由m階差商的定義有=+=證畢。定理1 設(shè)，互異 (6.10)則即是代數(shù)插值多項(xiàng)式。證明: 設(shè)是過節(jié)點(diǎn)的k階Lagrange插值多項(xiàng)式顯然-是k次多項(xiàng)式，且有零點(diǎn)，令-當(dāng)， =證畢。式（6-10）稱為n階Newton插值多項(xiàng)式6.2.4 Newton插值多項(xiàng)式的進(jìn)一步研究同Lagrange插值多項(xiàng)式一樣，Newton插值多項(xiàng)式插值計(jì)算由兩部份組成。1生成Newton插值多項(xiàng)式前面介紹了

11、Newton插值多項(xiàng)式系數(shù)是階差商，下面介紹差商的計(jì)算過程及算式。由=知要計(jì)算n階差商須先算出兩個(gè)n-1階差商，要算出兩個(gè)n-1階差商須算出三個(gè)n-2階差商，要算出n個(gè)一階差商須給出n+1個(gè)0階差商，即要給出n+1個(gè)函數(shù)值。 通常各階差商的計(jì)算過程是借助于一個(gè)差商表進(jìn)行的。例1 求一不高于4次的Newton插值多項(xiàng)式，使,，。下面是生成的系數(shù)時(shí)，繪制的差商表6-2表6-2 傳統(tǒng)Newton差商表0 0 11 1 12 2 23 3 34 4 3 0.50001-0.510按前面定義，表中有下劃線的數(shù)據(jù)為Newton插值多項(xiàng)式的系數(shù)。 =上面差商表稱為Newton傳統(tǒng)差商表,該表中數(shù)據(jù)列的位置準(zhǔn)

12、確，但行號(hào)不能用整數(shù)表示,因此既不能用代數(shù)中矩陣表示又無法用語言中數(shù)組(元素)表示，當(dāng)然也就無法用帶計(jì)算過程和計(jì)算條件的數(shù)學(xué)公式表示。下面是改進(jìn)差商表6-3。表6-3 改進(jìn)Newton差商表 0 0 1 0 0.5 -1/6 0 1 1 1 1 0 -1/6 2 2 2 1 0.5 3 3 3 0 4 4 3改進(jìn)差商表僅將傳統(tǒng)差商表的數(shù)字及輔助線轉(zhuǎn)了一個(gè)角度,但是卻將數(shù)據(jù)的行位置確定了,設(shè)第行第列的數(shù)字為,則有 (6.11)為Newton插值多項(xiàng)式所求系數(shù)，是表的最上一行數(shù)據(jù)，顯然便于查找。顯然改進(jìn)差商表比傳統(tǒng)差商表優(yōu)越，沒有改進(jìn)差商表就沒有(6.11)式，即使手算，按改進(jìn)差商表也比傳統(tǒng)的好。

13、2插值計(jì)算現(xiàn)將（6.10）式用壓縮格式表述 （6.12）通常教材和文獻(xiàn)都按（6.12）作插值計(jì)算，實(shí)際上用仿秦九韶法可大大簡(jiǎn)化計(jì)算，下面是仿秦九韶法計(jì)算公式： （6.13）將式（6.13）中換成就是帶計(jì)算過程和計(jì)算條件的秦九韶法計(jì)算公式，因而我們將式（6.13）稱為仿秦九韶法。6.2.5 Newton插值多項(xiàng)式計(jì)算步驟1.輸入階n,節(jié)點(diǎn)值,函數(shù)值，待插值點(diǎn)2.輸出插值結(jié)果3.計(jì)算過程1)生成Newton插值多項(xiàng)式系數(shù)計(jì)算公式為 ， 對(duì)應(yīng)的程序語句為 for(j=0;j<=n;j+) c0j=yj;計(jì)算公式為對(duì)應(yīng)的程序語句為 for(j=1;j<=n;j+) for(i=0;i<

14、;=n-j;i+) cij=(ci+1j-1-cij-1)/(xi+j-xi);2)插值計(jì)算計(jì)算公式為： 對(duì)應(yīng)的程序語句為： sn=c0n;計(jì)算公式為： 對(duì)應(yīng)的程序語句為： for(i=n-1;i>=0;i-) si=si+1*(X-xi-1)+c0i;具體插值計(jì)算作為習(xí)題，讓同學(xué)課后練習(xí)。前面算例中我們未象某些教材將計(jì)算結(jié)果“化簡(jiǎn)”成冪級(jí)數(shù)，原因是：（1）將結(jié)果表述成（6.10）式，便于驗(yàn)算。（2）可直接利用仿秦九韶法計(jì)算插值多項(xiàng)式值。附注：上面例子實(shí)為三次多項(xiàng)式，說明不高于4階是確切的，該例是特例。6.2.6帶重節(jié)點(diǎn)的Newton插值多項(xiàng)式Newton插值多項(xiàng)式優(yōu)點(diǎn)之一就是可以帶重節(jié)

15、點(diǎn)。 定義2 作插值多項(xiàng)式時(shí)，若還知道節(jié)點(diǎn)的導(dǎo)數(shù)值，該節(jié)點(diǎn)被稱為重節(jié)點(diǎn)，若還知道它的k階導(dǎo)數(shù)值則稱為K-1重節(jié)點(diǎn)，之所以稱為重節(jié)點(diǎn)是因?yàn)樵摴?jié)點(diǎn)要連續(xù)占幾個(gè)編號(hào)，K重節(jié)點(diǎn)占K+1個(gè)編號(hào)。帶重節(jié)點(diǎn)的Newton插值多項(xiàng)式的生成表和不帶重節(jié)點(diǎn)的類似，不同之處在算例中具體說明其，計(jì)算公式不再推導(dǎo)和證明，只直接使用。例2 求一不高于4次的Newton插值多項(xiàng)式使得，并計(jì)算的值。解 本例中和都是重節(jié)點(diǎn)，其編號(hào)分別為1、2和3、4，帶重節(jié)點(diǎn)的差商計(jì)算公式為 作帶重節(jié)點(diǎn)的Newton差商表（數(shù)字有下劃線者是已知導(dǎo)數(shù)值，用它們直接代替一階差商值）。表6-4 帶重節(jié)點(diǎn)的Newton差商表 0 0 1 1 1 -1

16、.5 3.25 1 1 2 2 -2 5 1 1 2 0 3 2 2 2 3 2 2 2由差商表計(jì)算結(jié)果知=2.087125例3 作一不高于4次的多項(xiàng)式，使，解 本例為重節(jié)點(diǎn)的編號(hào)，帶多重節(jié)點(diǎn)的改進(jìn)Newton差商表中的系數(shù)計(jì)算公式為 作帶多階重節(jié)點(diǎn)的Newton差商表如下表6.5 帶重節(jié)點(diǎn)的Newton差商表 0 0 1 1 0 1 02 0 1 13 0 1 4 1 3 由差商表計(jì)算結(jié)果知：6.2.7 帶重節(jié)點(diǎn)的Newton插值多項(xiàng)式的計(jì)算步驟（略）6.2.8 帶重節(jié)點(diǎn)的Newton插值多項(xiàng)式的余項(xiàng)估計(jì)對(duì)于帶重節(jié)點(diǎn)的Newton插值多項(xiàng)式，由于節(jié)點(diǎn)編號(hào)不影響多項(xiàng)式本身的特性，不妨將所帶重節(jié)

17、點(diǎn)的點(diǎn)的編號(hào)優(yōu)先。定理2 設(shè)()為重節(jié)點(diǎn)，為一般節(jié)點(diǎn)，且2k+2+p=n。是帶k+1個(gè)重節(jié)點(diǎn)的n階Newton插值多項(xiàng)式，是被逼近函數(shù)，在插值區(qū)間至少有n+1階連續(xù)導(dǎo)數(shù)，則證明 作輔助函數(shù)顯然，當(dāng)時(shí)=0，=0 當(dāng)時(shí)，=0 當(dāng)時(shí)，=0反復(fù)利用Roll定理，存在有由此有 注：上式中節(jié)點(diǎn)的編號(hào)為原始編號(hào)，重節(jié)點(diǎn)也占一個(gè)編號(hào)。證畢。 6.3 新代數(shù)插值Lagrange插值多項(xiàng)式，Newton插值多項(xiàng)式都要涉及形如的計(jì)算，當(dāng)較大，且都小于1時(shí)，分母接近0。在第1章里我們提到，因通常至少有舍入誤差，此時(shí)計(jì)算誤差會(huì)很大，算法穩(wěn)定性不好，19世紀(jì)的Runge對(duì)此作了研究。6.3.1 Runge現(xiàn)象Runge用

18、高階（等距）Lagrange插值多項(xiàng)式對(duì)作了逼近，結(jié)果出現(xiàn)了Runge現(xiàn)象，計(jì)算機(jī)問世之后，不少學(xué)者對(duì)此進(jìn)行了驗(yàn)證，都發(fā)現(xiàn)只要用高階Lagrange插值多項(xiàng)式或高階Newton插值多項(xiàng)式逼近都會(huì)產(chǎn)生Runge現(xiàn)象，由于Runge誤導(dǎo)，研究高階代數(shù)插值者甚少，高階代數(shù)插值多項(xiàng)式許多優(yōu)良性質(zhì)鮮為人知。表6-6是Runge現(xiàn)象表，即取，用Lagrange插值多項(xiàng)式逼近函數(shù)時(shí)的結(jié)果。表6-6 Runge現(xiàn)象表xx-1.000.038460.03846-0.460.158980.24145-0.960.041601.80438-0.400.200000.20000-0.900.047061.57827-

19、0.360.235850.18878-0.860.051310.88808-0.300.307690.23535-0.800.058820.05882-0.260.371750.31650-0.760.06477-0.20130-0.200.500000.50000-0.700.07547-0.22620-0.160.609760.64316-0.660.08410-0.10832-0.100.800000.84340-0.600.100000.10000-0.060.917430.94090-0.560.113120.198730.001.000001.00000-0.500.137930.

20、25376注：表中帶下劃線為節(jié)點(diǎn)。函數(shù)在整個(gè)數(shù)軸上都是連續(xù)的，且存在任意階導(dǎo)數(shù)，當(dāng)時(shí)，插值余項(xiàng)應(yīng)滿足：=就而言，容易知道從上表可看出逼近得不好，確實(shí)產(chǎn)生了Runge現(xiàn)象，這里得指出，該表雖然結(jié)果不好，但比之一般文獻(xiàn)講，則好一些，若用雙精度計(jì)算，則Runge現(xiàn)象消失，Runge所處時(shí)代無計(jì)算機(jī)，手算取小數(shù)點(diǎn)四位已夠費(fèi)力，加上插值計(jì)算要計(jì)算 這類分母接近0的算式，因而大大放大了計(jì)算誤差，自然會(huì)出現(xiàn)Runge現(xiàn)象，現(xiàn)在介紹一種穩(wěn)定性較好的新插值算法。6.3.2 新代數(shù)插值多項(xiàng)式定 義 設(shè) （6.14）若，稱為新代數(shù)插值多項(xiàng)式，為插心。Newton插值多項(xiàng)式系數(shù)是通過Lagrange插值多項(xiàng)式推導(dǎo)出來

21、的，新代數(shù)插值多項(xiàng)式的系數(shù)也可通過Lagrange插值多項(xiàng)式算出。設(shè)是通過節(jié)點(diǎn)的n階Lagrange插值多項(xiàng)式，則 （6.15）式（6.15）中由得 （6.16）將（6.16）代入（6.14）化簡(jiǎn)得 （6.17）由式（6.17）得 （6.18）類推得 （6.19）式（6.19）稱為新代數(shù)插值多項(xiàng)式系數(shù)計(jì)算公式。當(dāng)時(shí)，（6.19）式可簡(jiǎn)化成 （6.20） 式（6.20）稱為等距新代數(shù)插值多項(xiàng)式。當(dāng)時(shí)，式（6-19）可簡(jiǎn)化成 （6.21）式（6.21）稱為節(jié)點(diǎn)距離平方相等插值公式。6.3.3新代數(shù)插值多項(xiàng)式性質(zhì)引理 （6.22）證明略定理 設(shè)f(x)在插值區(qū)間至少有n+1階連續(xù)導(dǎo)數(shù)，且有是以為插心

22、的n階等距新代數(shù)插值多項(xiàng)式，i=0，1，n，若忽略，則 (6.23) 我們用歸納法證明定理。(1)當(dāng)j=1時(shí)= = i=1,2,，n=由此知j=1時(shí)定理成立（2）現(xiàn)假設(shè)j=P-1時(shí)定理成立，考察j=p=由（1），（2）知定理成立證畢。同樣可證明式（6.21）中系數(shù)具有同樣性質(zhì)，證明略?？梢娦麓鷶?shù)插值系數(shù)計(jì)算公式就是Taylor級(jí)數(shù)系數(shù)的數(shù)值計(jì)算公式。下面探討穩(wěn)定性。不失一般性，我們?cè)O(shè)，,由于節(jié)點(diǎn)是人為選取的，其選取原則是：（1）計(jì)算方便，測(cè)試f(x)方便；（2）計(jì)算誤差小；（3）截?cái)嗾`差小。代數(shù)插值也屬于“條件”問題，為了保證算法穩(wěn)定性，我們選用式（6.21），現(xiàn)假設(shè)f(x)存在n+1階導(dǎo)數(shù)，

23、設(shè)的舍入誤差或測(cè)試誤差為，則的計(jì)算誤差為，為了計(jì)算方便不妨假設(shè)，則 （6.24）從（62.4）可看出當(dāng)時(shí)，算法是絕對(duì)穩(wěn)定的，若用上式可寫成設(shè)插值公式的截?cái)嗾`差，也就是說只要 （6.25）時(shí)算法也是穩(wěn)定的。注：當(dāng)f(x)在插值區(qū)間有奇點(diǎn)時(shí)，代數(shù)插值多項(xiàng)式的余項(xiàng)難以表示，因而我們假設(shè)6.3.4 平方等距插值的計(jì)算步驟式（6.20）和式(6.21)就計(jì)算而言是類似的，顯然式(6.21)的計(jì)算量小且穩(wěn)定性好，因此這一節(jié)后面的諸多例子都用式（6.21）顯示，為了節(jié)省篇幅這里僅給出式（6.21）式的計(jì)算過程：1輸入階n,節(jié)點(diǎn)值xi,函數(shù)值yi，i=0,1,2,n，待插值點(diǎn)X2輸出插值結(jié)果s3計(jì)算過程1）計(jì)

24、算楊輝三角 計(jì)算公式為：對(duì)應(yīng)的語句為： for(i=0;i<=m;i+) cii=ci0=1; for(i=2;i<=m;i+) for(j=1;j<i;j+) cij=ci-1j+ci-1j-1;2）計(jì)算,計(jì)算公式為： i=1,2,m對(duì)應(yīng)的程序語句為：for(i=1;i=m;i+） ui=(y2*i-1-y2*i)/（2*sqrt(i*h)）；vi=(y2*i-1+y2*i-2*y0)/(2*i*h）； 3）計(jì)算系數(shù)計(jì)算公式為： j=1,2,m；i=1,2,m-j對(duì)應(yīng)的程序語句為：for(j=1;j<=m;j+) k=1; for(i=1;i<m-j+1;i+)

25、 a2*j-1=a2*j-1+k*cm-j+1i*ui;a2*j=a2*j+k*cm-j+1i*vi; k=-k;for(i=1;i<=m-j;i+) ui=(ui-a2*j-1)/(i*h);vi=(vi-a2*j)/(i*h); 注:對(duì)a在說明時(shí)賦初值0。4）利用秦九韶作插值計(jì)算（計(jì)算冪級(jí)數(shù)值）計(jì)算公式為： 用X表示待插值點(diǎn)值,xs表示x*，則所對(duì)應(yīng)的程序語句為：X=X-xs;sn=an;for(i=n-1;i>=0;i-)si=si+1*X -ai;6.3.5新代數(shù)插值計(jì)算量新代數(shù)插值計(jì)算量由兩部分組成（1）生成新代數(shù)插值多項(xiàng)式系數(shù)時(shí)的計(jì)算量由式（6.21）可看出，生成系數(shù)前

26、要計(jì)算楊輝三角系數(shù)，從式(6.16)可看出計(jì)算量為次加法。從式（6.21）可看出，計(jì)算系數(shù)共用次乘法，計(jì)算右端項(xiàng)共用次除法（一次除法計(jì)算量和一次乘法計(jì)算量相等），即生成插值多項(xiàng)式共需要 （6.26）次乘法。（2）插值計(jì)算時(shí)的計(jì)算量由式（6.24）可看出，若用秦九韶法對(duì)一點(diǎn)作插值計(jì)算只需用n次乘法，自然對(duì)點(diǎn)作插值計(jì)算就用 （6.27）次乘法。則總計(jì)算量為 （6.28）次乘法。 就計(jì)算量而言，新代數(shù)插值計(jì)算量最小。6.3.6新代數(shù)插值的計(jì)算實(shí)例由于新代數(shù)值多項(xiàng)式的許多性質(zhì)鮮為人知，因而本書盡可能多給實(shí)例。例1 用一不高于2次的等距新代數(shù)插值多項(xiàng)式逼近，節(jié)點(diǎn)值為1.2,1.4,1.6，插心取x*=1

27、.2，并計(jì)算的值。解：S1：節(jié)點(diǎn)值及節(jié)點(diǎn)處函數(shù)值（h=0.2） x 1.2 1.4 1.6 y 0.1823216 0.3364722 0.4700036 S2：計(jì)算系數(shù) 新代數(shù)插值多項(xiàng)式為例2 同例1，要求使用式（6.21）計(jì)算，插心取x*=1.4。解：S1：節(jié)點(diǎn)值及節(jié)點(diǎn)處函數(shù)值(,h=0.04) i 0 1 2 x 1.4 1.6 1.2 y 0.3364722 0.4700036 0.1823216 S2：計(jì)算系數(shù)新代數(shù)插值用于高階插值才會(huì)顯示其優(yōu)越性，以下各例均不是手算結(jié)果。因平方等距算法穩(wěn)定性好，計(jì)算量小，后面所有實(shí)例皆用（6-21）式計(jì)算。例3 ，計(jì)算的各系數(shù)，驗(yàn)證可用新代數(shù)插值多

28、項(xiàng)式計(jì)算Taylor級(jí)數(shù)系數(shù)，計(jì)算結(jié)果見表6-7。例4 ，計(jì)算在給出點(diǎn)值，驗(yàn)證對(duì)于插值區(qū)間有奇點(diǎn)的函數(shù)，也可用新代數(shù)插值多項(xiàng)式逼近，計(jì)算結(jié)果見表68。例5 ，計(jì)算函數(shù)值和一階導(dǎo)數(shù)值，計(jì)算結(jié)果見表6-9。例6 ，計(jì)算函數(shù)值及15階導(dǎo)數(shù)值，計(jì)算結(jié)果見表6-10。表67 的Taylor級(jí)數(shù)的前41個(gè)系數(shù)01.000 000 014-16 370.125 082890 359 295.63810.000 000 0150.000 000 0290.000 000 02-4.000 000 01665 259.643 45830-180 388 318.930.000 000 0170.000 000

29、0310.000 000 0416.000 000 018-257 822.359 832275 978 445.1350.000 000 0190.000 000 0330.000 000 06-63.999 995 620994 657.113 8534-309 341 768.370.000 000 0210.000 000 0350.000 000 08255.999 682 322-3 650 448.38336258 290 043.5890.000 000 0230.000 000 0370.000 000 010-1 023.984 5742412 287 220.22438-

30、148 178 592.0110.000 000 0250.000 000 0390.000 000 0124 095.464 509 526-36 347 025.274060 733 964.630130.000 000 0270.000 000 0表68 的逼近值和理論值00.000 0000.000 0000.520.519 895 80.520 000 00.040.009 444 80.040 00000.560.560033 20.560 000 00.080.036 367 90.800 000 00.600.600 050 40.600 000 00.120.076923 4

31、0.120 000 00.640.639988 70.640 000 00.160.125 867 10.160 000 00.680.679 972 40.680 000 00.200.177 894 60.200 000 00.720.720 014 30.720 000 00.240.228 848 00.240 000 00.760.760 016 90.760 000 00.280.276 424 20.280 000 00.800.799971 00.800 000 00.320.320 214 80.320000 00.840.840 007 40.840 000 00.360.

32、361 160 80.360 000 00.000.880053 00.880 000 00.400.400 714 70.400 000 00.920.919 832 10.920 000 00.440.440 080 20.440 000 00.960.960 35610.960 000 00.480.479 817 90.480 000 011.000 0001.000 000表6-9 的 01階導(dǎo)逼近值和理論值00.000 0001.000 0001.000 0000.260.259 802 0.999 238 50.996 193 40.020.020 000 01.000 0000

33、.999 999 90.280.279 713 20.998 975 90.994 880 70.040.040 000 00.999 999 60.999 997 90.300.299 595 20.998 650 50.993 254 90.060.59 999 90.999 997 80.999 989 20.320.319 441 00.998 253 30.991 270 10.080.079 999 50.999 993 20.999 965 90.340.339 243 20.997 774 30.998 877 30.100.099 998 30.999 983 30.999

34、916 70.360.358 993 10.997 203 00.986 024 30.120.119 995 90.999 965 40.999 827 20.380.378 680 80.996 528 40.982 656 50.140.139 991 00.999 936 00.999 679 90.400.398 295 50.995 738 80.978 715 80.160.159 982 50.999 890 80.999 453 90.420.417 825 20.994 821 90.974 141 70.180.179 968 50.999 825 00.999 125

35、30.440.437 256 50.993 764 90.968 871 10.200.199 946 70.999 733 40.998 666 90.460.456 575 00.992 764 30.962 838 00.220.219 914 10.999 609 60.998 048 30.480.475 764 50.991 176 10.955 974 20.240.239 867 30.999 447 10.997 236 00.500.494 807 90.989 615 80.948 209 0表6-10 的05階導(dǎo)數(shù)插值11.414 213 60.353 553 4-0.

36、088 388 30.066 291 3-0.082 864 10.145 012 21.021.428 285 70.351 798 8-0.087 078 90.064 662 6-0.080 027 90.138 662 21.041.442 220 50.350 070 0-0.085 801 50.063 089 3-0.077 315 30.132 648 91.061.456 022 00.348 366 5-0.084 555 00.061 569 2-0.074 719 90.126 951 21.081.469 693 80.346 687 6-0.083 338 40.0

37、60 099 8-0.072 235 30.121 549 81.101.483 239 70.345 032 8-0.082 150 70.058 679 0-0.069 856 00.116 426 71.121.496 663 00.343 401 4-0.080 990 90.057 304 9-0.067 575 60.111 565 01.141.509 966 90.341 793 0-0.079 858 20.055 975 4-0.065 391 80.106 946 11.161.523 154 60.340 206 9-0.078 751 60.054 688 6-0.0

38、63 297 00.102 564 61.181.536 229 10.338 642 7-0.077 670 40.053 442 9-0.061 287 70.098 397 71.201.549 193 30.337 099 9-0.076 613 60.052 236 6-0.059 359 70.094 435 91.221.562 049 90.335 578 0-0.075 580 60.051 068 0-0.057 509 00.090 667 41.241.574 801 60.334 076 6-0.074 570 70.049 935 7-0.055 731 80.087 081 01.261.587 560 80.332 595 1-0.073 583 00.048 838 3-0.054 024 60.083 666 51.281.600 000 00.331 133 1-0.072 616 90.047 774 3-0.052 384 10.080 414 21.301.612 451 50.329 690 2-0.071 671 80.046 742 5-0.050 807 00.077 315 11.321.624 807 70.32