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

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

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

3、甚為方便，但當(dāng)插值節(jié)點(diǎn)增減時(shí)全部插值基函數(shù)Lk(x)(k=0,1,n)均要隨之變化，整個(gè)公式也將發(fā)生變化，這在實(shí)際計(jì)算中是很不方便的，為了克服這一缺點(diǎn)，提出了牛頓插值可以克服這一缺點(diǎn)。1.1.3數(shù)值實(shí)驗(yàn)程序如下：#include<stdio.h>#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插值多項(xiàng)式共用到N組(X,Y)值，請輸入N

4、:"); scanf("%d",&n); if(n<=N&&n>=M) flag=FALSE; else if(n>N|n<=1) printf("對不起，你輸入錯(cuò)誤!n請確保你輸入的N滿足2<=N<=%d.",N); printf("n"); flag=TRUE; while(flag=TRUE); printf("n請輸入需要計(jì)算的X值:"); scanf("%lf",&a); for(i=0;i<n;i+)

5、 printf("請輸入第%d組(X,Y)的值:",i+1); scanf("%lf%lf",x+i,y+i); for(i=0;i<n;i+) li=1.0f; for(j=0;j<N;j+) if(i!=j) li*=(a-xj)/(xi-xj); else continue; answer+=li*yi; printf("f(%.3lf)=%lfn",a,answer); 實(shí)驗(yàn)結(jié)果Input n:4Input xn:O,4 0.55 0.65 0.8 0.9Input yn0.41075 0.57815 0.6967

6、5 0.88811 1.02652Please input x:0.596Nn(0.596)=0.6319141.2牛頓插值1.2.1基本原理構(gòu)造n次多項(xiàng)式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)稱為牛頓插值多項(xiàng)式，其中 (二個(gè)節(jié)點(diǎn)，一階差商) (三個(gè)節(jié)點(diǎn)，二階差商) (n+1個(gè)節(jié)點(diǎn)，n階差商)注意：由于插值多項(xiàng)式的唯一性，有時(shí)為了避免拉格朗日余項(xiàng)Rn(x)中n+1階導(dǎo)數(shù)的運(yùn)算，用牛頓插值公式Rn (x)=f(x)-Nn(x)=f(x,x0,xn)n+1(x),其中n+

7、1(x)=(x-x0)(x-x1)(x-xn)1.2.2優(yōu)缺點(diǎn)牛頓插值法具有承襲性和易變性的特點(diǎn)，當(dāng)增加一個(gè)節(jié)點(diǎn)時(shí)，只要再增加一項(xiàng)就可以了即而拉格朗日插值若要增加一個(gè)節(jié)點(diǎn)時(shí)全部基函數(shù)都需要重新算過。牛頓插值法既適合于用來計(jì)算函數(shù)值，也適合于做理論推導(dǎo)，比如說可用來推導(dǎo)微分方程的數(shù)值求解公式。 1.2.3數(shù)值實(shí)驗(yàn)一、差商相關(guān)公式二、題目已知函數(shù)表如下：0.00.51.01.52.02.50.841470.857700.899240.948980.987770.999551計(jì)算用3次Newton插值多項(xiàng)式。2計(jì)算用5次Newton插值多項(xiàng)式。三、程序思想 根據(jù)實(shí)際計(jì)算理論，利用Newton插值多項(xiàng)

8、式計(jì)算，事先應(yīng)知道其節(jié)點(diǎn)個(gè)數(shù)。所以，本程序設(shè)置在100個(gè)節(jié)點(diǎn)即最高次可達(dá)99次的多項(xiàng)式計(jì)算，通過輸入節(jié)點(diǎn)個(gè)數(shù)來控制每次要計(jì)算的多項(xiàng)式的次數(shù)。 首先，計(jì)算各階的函數(shù)值。 根據(jù)節(jié)點(diǎn)的個(gè)數(shù)與每階階商具有的階商個(gè)數(shù)循環(huán)計(jì)算各階商的值，并根據(jù)相應(yīng)的節(jié)點(diǎn)下標(biāo)控制輸出各階商值。 其次，輸出最高階表達(dá)式。 由于最高階表達(dá)式是從0位開始計(jì)算的，所以，在知道節(jié)點(diǎn)下標(biāo)的基礎(chǔ)上，每次以二維數(shù)組兩下標(biāo)是否相等來輸出相應(yīng)的階商，及x的值與節(jié)點(diǎn)的起止下標(biāo)輸出相應(yīng)的表達(dá)式。 最后，根據(jù)輸入的節(jié)點(diǎn)數(shù)計(jì)算其對應(yīng)的函數(shù)值。3階計(jì)算表達(dá)式，任意輸入節(jié)點(diǎn)值，根據(jù)輸入的節(jié)點(diǎn)值的大小判斷其所在的范圍，以輸出表達(dá)式同樣的思想計(jì)算節(jié)點(diǎn)對應(yīng)的函

9、數(shù)值。最高階表達(dá)式，亦是通過循環(huán)計(jì)算獲得相應(yīng)的函數(shù)值。四、計(jì)算結(jié)果：五、程序源代碼。#include "stdafx.h"#include<stdio.h>void 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("請輸入節(jié)點(diǎn)個(gè)數(shù)w<=100: "); /輸入節(jié)點(diǎn)個(gè)數(shù) scanf("%d",&w); for(n=0;n<w;n+) /根據(jù)節(jié)點(diǎn)個(gè)

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

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

12、ot;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(i2=0;i2<=i1;i2+) /此循環(huán)嵌在上一循環(huán)里作循環(huán)輸出并判斷，控制輸出空格的長度使輸出對齊 if(fi1i2>=0) if(fi1i2>10) if(fi1

13、i2>=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+&q

14、uot;,n-1,f00); /輸出最高階表達(dá)式 for(i1=1;i1<n;i1+) for(j=1;j<n;j+) if(i1=j) /用i1,j的下標(biāo)相等的差商值輸出 if(fi1j<0) /負(fù)數(shù)加括號輸出 printf("(%.5f)",fi1j); else printf("%.5f",fi1j); for(k=0;k<j;k+) /用k循環(huán)控制輸出節(jié)點(diǎn)的值 printf("(x-%.5f)",xk); printf("n"); if(j<n-1) /根據(jù)判斷在輸出每一項(xiàng)后是

15、否輸出“+” printf(" +"); printf("輸入節(jié)點(diǎn)x1(用3次多項(xiàng)式計(jì)算)，x2(用%d次多項(xiàng)式計(jì)算):n",n-1); scanf("%f%f",&x1,&x2); /提示輸入兩個(gè)要計(jì)算的節(jié)點(diǎn) for(i1=0;i1<n;i1+) /對x1進(jìn)行判斷早出其所在的區(qū)間的節(jié)點(diǎn)的下標(biāo)值 if(x1>xi1) break; /判斷下標(biāo)后退出 if(n-i1)>=3) /判斷其下標(biāo)后是否還有3個(gè)節(jié)點(diǎn)，如果有就以次區(qū)間作計(jì)算 i2=i1; else /如果次下標(biāo)后沒有3個(gè)節(jié)點(diǎn)，將下標(biāo)i1減2再作判

16、斷 i1=i1-2; if(i1>=0) i2=i1; /此時(shí)i1>=0就以次下標(biāo)開始作區(qū)間 else i2=i1+1; /在前邊i1-2如果<0,則將其下標(biāo)加1 i1=i2; N1=fi10; for(j=1;j<4;j+,i1+) N2=N2*fi1+1i1+1; /根據(jù)節(jié)點(diǎn)的區(qū)間和階商的具有同一下標(biāo)的關(guān)系，循環(huán)計(jì)算階商的值 for(k=i2;k<i2+j;k+) /在前一循環(huán)基礎(chǔ)上循環(huán)計(jì)算每階商后對應(yīng)節(jié)點(diǎn)間的值，并控制節(jié)點(diǎn)的末位 N2=N2*(x1-xk); N3=N2+N3; N2=1.0; N3=N1+N3; /將計(jì)算的值賦給N3并輸出 printf("N3(%.5f)=%.5fn",x1,N3); N3=0.0; N1=f00; for(i1=1;i1<n;i1+) /以同樣的方式計(jì)算最高階的值 for(i2=0;i2<i1;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); /輸出最高階計(jì)算節(jié)點(diǎn)的值2.誤差分析 依據(jù)f（x）數(shù)據(jù)表構(gòu)造出來它的插值函數(shù)P（x）,然后，在給定點(diǎn)x計(jì)算P（x）的值作為