代數(shù)插值法的論述

1、代數(shù)插值法的論述代數(shù)插值法1. 插值法概述插值法是函數(shù)逼近的重要方法之一，有著廣泛的應(yīng)用 。在生產(chǎn)和實驗中，函數(shù)f(x)或者其表達(dá)式不便于計算復(fù)雜或者無表達(dá)式而只有函數(shù)在給定點的函數(shù)值(或其導(dǎo)數(shù)值) ，此時我們希望建立一個簡單的而便于計算的函數(shù)j(x)，使其近似的代替f(x)，有很多種插值法,其中以拉格朗日(Lagrange)插值和牛頓(Newton)插值為代表的多項式插值最有特點,常用的插值還有Hermit插值,分段插值和樣條插值.這里主要介紹拉格朗日(Lagrange)插值和牛頓(Newton)插值。1.1拉格朗日插值1.1.1基本原理構(gòu)造n次多項式Pn (x)= yk lk (x)=y0

2、l0 (x)+y1l1 (x)+ynln (x)，這是不超過n次的多項式，其中基函數(shù)lk(x)=顯然lk (x)滿足lk (xi)=此時 Pn(x)f(x),誤差Rn(x)=f(x)-Pn(x)= 其中(a,b)且依賴于x，=（x-x0）(x-x1)(x-xn)很顯然，當(dāng)n=1、插值節(jié)點只有兩個xk,xk+1時 P1(x)=yklk(x)+yk+1lk+1(x)其中基函數(shù)lk(x)= lk+1(x)= 1.1.2優(yōu)缺點可對插值函數(shù)選擇多種不同的函數(shù)類型，由于代數(shù)多項式具有簡單和一些良好的特性，故常選用代數(shù)多項式作為插值函數(shù)。利用插值基函數(shù)很容易得到拉格朗日插值多項式，公式結(jié)構(gòu)緊湊，在理論分析中

3、甚為方便，但當(dāng)插值節(jié)點增減時全部插值基函數(shù)Lk(x)(k=0,1,n)均要隨之變化，整個公式也將發(fā)生變化，這在實際計算中是很不方便的，為了克服這一缺點，提出了牛頓插值可以克服這一缺點。1.1.3數(shù)值實驗程序如下：#include#define TRUE 1#define FALSE 0#define N 10#define M 2void main(void) double xN,yN,a,lN; int i,j,n,flag; double answer=0.00f; do printf(創(chuàng)建Lagrange插值多項式共用到N組(X,Y)值，請輸入N:); scanf(%d,&n); if(

4、n=M) flag=FALSE; else if(nN|n=1) printf(對不起，你輸入錯誤!n請確保你輸入的N滿足2=N=%d.,N); printf(n); flag=TRUE; while(flag=TRUE); printf(n請輸入需要計算的X值:); scanf(%lf,&a); for(i=0;in;i+) printf(請輸入第%d組(X,Y)的值:,i+1); scanf(%lf%lf,x+i,y+i); for(i=0;in;i+) li=1.0f; for(j=0;jN;j+) if(i!=j) li*=(a-xj)/(xi-xj); else continue;

5、answer+=li*yi; printf(f(%.3lf)=%lfn,a,answer); 實驗結(jié)果Input n:4Input xn:O,4 0.55 0.65 0.8 0.9Input yn0.41075 0.57815 0.69675 0.88811 1.02652Please input x:0.596Nn(0.596)=0.6319141.2牛頓插值1.2.1基本原理構(gòu)造n次多項式Nn(x)=f(x0)+f(x0,x1)(x-x0)+f(x0,x1,x2)(x-x0)(x-x1)+f(x0,x1,x2,xn)(x-x0)(x-x1)(x-xn)稱為牛頓插值多項式，其中 (二個節(jié)點，

6、一階差商) (三個節(jié)點，二階差商) (n+1個節(jié)點，n階差商)注意：由于插值多項式的唯一性，有時為了避免拉格朗日余項Rn(x)中n+1階導(dǎo)數(shù)的運(yùn)算，用牛頓插值公式Rn (x)=f(x)-Nn(x)=f(x,x0,xn)n+1(x),其中n+1(x)=(x-x0)(x-x1)(x-xn)1.2.2優(yōu)缺點牛頓插值法具有承襲性和易變性的特點，當(dāng)增加一個節(jié)點時，只要再增加一項就可以了即而拉格朗日插值若要增加一個節(jié)點時全部基函數(shù)都需要重新算過。牛頓插值法既適合于用來計算函數(shù)值，也適合于做理論推導(dǎo)，比如說可用來推導(dǎo)微分方程的數(shù)值求解公式。 1.2.3數(shù)值實驗一、差商相關(guān)公式二、題目已知函數(shù)表如下：0.00

7、.51.01.52.02.50.841470.857700.899240.948980.987770.999551計算用3次Newton插值多項式。2計算用5次Newton插值多項式。三、程序思想 根據(jù)實際計算理論，利用Newton插值多項式計算，事先應(yīng)知道其節(jié)點個數(shù)。所以，本程序設(shè)置在100個節(jié)點即最高次可達(dá)99次的多項式計算，通過輸入節(jié)點個數(shù)來控制每次要計算的多項式的次數(shù)。 首先，計算各階的函數(shù)值。 根據(jù)節(jié)點的個數(shù)與每階階商具有的階商個數(shù)循環(huán)計算各階商的值，并根據(jù)相應(yīng)的節(jié)點下標(biāo)控制輸出各階商值。 其次，輸出最高階表達(dá)式。 由于最高階表達(dá)式是從0位開始計算的，所以，在知道節(jié)點下標(biāo)的基礎(chǔ)上，每

8、次以二維數(shù)組兩下標(biāo)是否相等來輸出相應(yīng)的階商，及x的值與節(jié)點的起止下標(biāo)輸出相應(yīng)的表達(dá)式。 最后，根據(jù)輸入的節(jié)點數(shù)計算其對應(yīng)的函數(shù)值。3階計算表達(dá)式，任意輸入節(jié)點值，根據(jù)輸入的節(jié)點值的大小判斷其所在的范圍，以輸出表達(dá)式同樣的思想計算節(jié)點對應(yīng)的函數(shù)值。最高階表達(dá)式，亦是通過循環(huán)計算獲得相應(yīng)的函數(shù)值。四、計算結(jié)果：五、程序源代碼。#include stdafx.h#includevoid main(int argc,char* argv) int i1,i2,p,j,k,w,n=0; float x100,f100100,f1100,x1,x2,N1,N2=1.0,N3=0.0; printf(請輸入

9、節(jié)點個數(shù)w=100: ); /輸入節(jié)點個數(shù) scanf(%d,&w); for(n=0;nw;n+) /根據(jù)節(jié)點個數(shù)和階商的關(guān)系，用節(jié)點控制輸入節(jié)點及對應(yīng)的函數(shù)值 printf(x=); scanf(%f,&xn); printf(f(x)=); scanf(%f,&f1n); for(n=0;nw;n+) /將節(jié)點對應(yīng)的函數(shù)值送給二維數(shù)組 fn0=f1n; for(j=1;jn;j+) /循環(huán)計算差商的值 k=j; for(p=0;kn;k+,p+) /用k控制同一維的下標(biāo)，用j控制維數(shù)，用p控制節(jié)點的起始下標(biāo) fkj=(fkj-1-fk-1j-1)/(xk-xp); printf( xi

10、f(xi) 1階差商); /輸出固定格式 for(i1=1;i1n-1;i1+) /用i1作循環(huán)，循環(huán)輸出（i1+1)階差商作固定格式 printf( %d階差商,(i1+1); for(i1=0;i1=0) /作判斷一控制輸出空格的長度以使每次輸出起始位置對齊 if(xi1=10&xi1=100) printf(n%.5f ,xi1); else printf(n%.5f ,xi1); else if(xi1=-10) printf(n%.5f ,xi1); else if(xi1=-100) printf(n%.5f ,xi1); else printf(n%.5f ,xi1); for(

11、i2=0;i2=0) if(fi1i210) if(fi1i2=100) printf(%.5f ,fi1i2); else printf(%.5f ,fi1i2); else printf(%.5f ,fi1i2); else if(fi1i2=-10) if(fi1i2=-100) printf(%.5f ,fi1i2); else printf(%.5f ,fi1i2); else printf(%.5f ,fi1i2); printf(nN%d(x)=%.5f+,n-1,f00); /輸出最高階表達(dá)式 for(i1=1;i1n;i1+) for(j=1;jn;j+) if(i1=j)

12、/用i1,j的下標(biāo)相等的差商值輸出 if(fi1j0) /負(fù)數(shù)加括號輸出 printf(%.5f),fi1j); else printf(%.5f,fi1j); for(k=0;kj;k+) /用k循環(huán)控制輸出節(jié)點的值 printf(x-%.5f),xk); printf(n); if(jn-1) /根據(jù)判斷在輸出每一項后是否輸出“+” printf( +); printf(輸入節(jié)點x1(用3次多項式計算)，x2(用%d次多項式計算):n,n-1); scanf(%f%f,&x1,&x2); /提示輸入兩個要計算的節(jié)點 for(i1=0;i1xi1) break; /判斷下標(biāo)后退出 if(n-

13、i1)=3) /判斷其下標(biāo)后是否還有3個節(jié)點，如果有就以次區(qū)間作計算 i2=i1; else /如果次下標(biāo)后沒有3個節(jié)點，將下標(biāo)i1減2再作判斷 i1=i1-2; if(i1=0) i2=i1; /此時i1=0就以次下標(biāo)開始作區(qū)間 else i2=i1+1; /在前邊i1-2如果0,則將其下標(biāo)加1 i1=i2; N1=fi10; for(j=1;j4;j+,i1+) N2=N2*fi1+1i1+1; /根據(jù)節(jié)點的區(qū)間和階商的具有同一下標(biāo)的關(guān)系，循環(huán)計算階商的值 for(k=i2;ki2+j;k+) /在前一循環(huán)基礎(chǔ)上循環(huán)計算每階商后對應(yīng)節(jié)點間的值，并控制節(jié)點的末位 N2=N2*(x1-xk);

14、 N3=N2+N3; N2=1.0; N3=N1+N3; /將計算的值賦給N3并輸出 printf(N3(%.5f)=%.5fn,x1,N3); N3=0.0; N1=f00; for(i1=1;i1n;i1+) /以同樣的方式計算最高階的值 for(i2=0;i2i1;i2+) N2=N2*(x2-xi2); N2=N2*fi1i1; N3=N2+N3; N2=1.0; N3=N1+N3; printf(N%d(%.5f)=%.5fn,n-1,x2,N3); /輸出最高階計算節(jié)點的值2.誤差分析 依據(jù)f（x）數(shù)據(jù)表構(gòu)造出來它的插值函數(shù)P（x）,然后，在給定點x計算P（x）的值作為f（x）的近似值，這一過程稱插值。所謂“插值”，通俗地說，就是依據(jù)f（x）所給的函數(shù)表“