計算機如何表達函數(shù)

第1章插值

實際中，f(x)多樣，復(fù)雜，通常只能觀測到一些離散數(shù)據(jù)；或者f(x)過于復(fù)雜而難以運算。這時我們要用近似函數(shù)g(x)來逼近f(x)。

自然地，希望g(x)通過所有的離散點x0x1x2x3x4xg(x)

f(x)定義：為定義在區(qū)間上的函數(shù)，為區(qū)間上n+1個互不相同的點，為給定的某一函數(shù)類。求上的函數(shù)滿足問題是否存在唯一如何構(gòu)造誤差估計設(shè)則所以有唯一解，當且僅當m=n，且系數(shù)行列式不為0存在唯一定理定理1.1：為n＋1個節(jié)點，

n+1維空間，則插值函數(shù)存在唯一，當且僅當與基函數(shù)無關(guān)與原函數(shù)f(x)無關(guān)基函數(shù)個數(shù)與點個數(shù)相同特點：對應(yīng)于則Vandermonde行列式病態(tài)多項式插值的Lagrange型如何找？在基函數(shù)上下功夫，取基函數(shù)為要求則求，易知：記線性插值二次插值例：算法：fx=0.0for(i=0;i<=n;i++){

tmp=1.0;

for(j=0;j<i;j++)

tmp=tmp*(x-x[j])/(x[i]-x[j]);

for(j=i+1;j<=n;j++)

tmp=tmp*(x-x[j])/(x[i]-x[j]);

fx=fx+tmp*y[i];}returnfx;Lab02

Lagrange插值對函數(shù)構(gòu)造插值，并求為近似的誤差。插值節(jié)點取為：(1)(2)對N=5，10，20，40比較以上兩組節(jié)點的結(jié)果。Chebyshev點SampleOutput(

representsaspace)第1組節(jié)點，誤差為n=5

,

0.244934066848e+001n=10

,

0.534607244904e+001...第2組節(jié)點，誤差為n=5

,

0.244934066848e+001n=10

,

0.534607244904e+001...誤差解：求設(shè)易知有n+2個零點由a的任意性例：已知分別利用sinx的1次、2次Lagrange插值計算sin50

并估計誤差。解：n=1分別利用x0,x1

以及x1,x2

計算

利用這里而

sin50=0.7660444…)185(50sin10

pL0.77614外推

/*extrapolation*/

的實際誤差

0.01001

利用sin50

0.76008,內(nèi)插

/*interpolation*/

的實際誤差

0.00596內(nèi)插通常優(yōu)于外推。選擇要計算的x

所在的區(qū)間的端點，插值效果較好。n=2)185(50sin20

pL0.76543

sin50=0.7660444…2次插值的實際誤差

0.00061高次插值通常優(yōu)于低次插值事后誤差估計給定任取n+1個構(gòu)造如：另取則近似則HomeWork1.證明線性無關(guān)2.若，記為節(jié)點上的k次插值多項式試證明：Lagrange

插值的缺點無承襲性。增加一個節(jié)點，所有的基函數(shù)都要重新計算為實數(shù)Newton型多項式插值易知同樣承襲性：而且有：這樣：稱為k階差商稱為1階差商定義：差商差商的一個性質(zhì)：（用歸納法易證）

對稱性：定義關(guān)鍵：找不同的元素相減作分母由歸納：Newton插值構(gòu)造1、先構(gòu)造差商表例子2點Newton型插值2、利用差商表的最外一行，構(gòu)造插值多項式差商表求值算法：for(i=1;i<=n;i++){

for(j=n;j>=i;j--)

y[j]=(y[j]-y[j-1])/(x[j]-x[j-i]);}fx=y[n];for(i=n;i<=1;i--){

fx=y[i-1]+(x-x[i-1])fx;}問題：如果要做到增加一個點，而盡可能減少重復(fù)計算，要如何改進前面的算法？一些性質(zhì)性質(zhì)2誤差性質(zhì)3差商性質(zhì)總結(jié)證明作為作業(yè)1.4Hermite插值

有時候，構(gòu)造插值函數(shù)除了函數(shù)值的條件以外，還需要一定的連續(xù)性條件，如一階導(dǎo)數(shù)值等，這種插值稱為Hermite插值。稱為二重密切Hermite插值例：設(shè)x0

x1

x2,已知f(x0)、f(x1)、f(x2)

和f’(x1),求多項式P(x)

滿足P(xi)=f(xi)，i=0,1,2，且P’(x1)=f’(x1),并估計誤差。模仿Lagrange多項式的思想，設(shè)解：首先，P

的階數(shù)=3

+=213)()()()()(=0iiixhx1f’xhxfxP

h0(x)有根x1,x2，且h0’(x1)=0

x1是重根。)()()(22100xxxxCxh--=又:h0(x0)=1C0h2(x)與h0(x)完全類似。其中hi(xj)=

ij,hi’(x1)=0,

(xi)=0,

’(x1)=1

h1

h1h1(x)有根x0,x2

))()(()(201xxxxBAxxh--+=由余下條件h1(x1)=1和

h1’(x1)=0可解。

(x)

h1有根x0,x1,x2

h1))()(()(2101xxxxxxCx---=

h1又:’(x1)=1C1

可解。與Lagrange分析完全類似

仿照Lagrange插值的做法，首先確定多項式插值空間的維數(shù)，注意到，我們的條件共有2(n+1)個條件，所以，最高次數(shù)為2n+1對二重密切Hermite插值

整個構(gòu)造步驟如下：1、確定多項式的最高項次數(shù)，就是函數(shù)空間的維數(shù)2、假設(shè)一組基函數(shù)，列出插值多項式3、列出基函數(shù)滿足的公式（畫表），求基函數(shù)稱為構(gòu)造基函數(shù)方法誤差分析類似Lagrange插值的分析方法二重密切Hermite插值誤差例：在[5,5]上考察的Ln(x)。取

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

n

越大，端點附近抖動越大Ln(x)

f(x)

是否次數(shù)越高越好呢？分段低階插值Runge現(xiàn)象例：等距節(jié)點構(gòu)造10次Lagrange插值多項式-0.900.047061.57872-0.700.07547-0.22620-0.500.137930.25376-0.300.307690.235351901年，Runge等距高次插值，數(shù)值穩(wěn)定性差，本身是病態(tài)的。分段線性插值每個小區(qū)間上，作線性插值(1)(2)在每個小區(qū)間上為一個不高于1次的多項式特性誤差可以看出收斂，可惜只一階精度，不夠光滑。類似，可以作二重密切Hermite插值關(guān)鍵：

分段、低階插值三次樣條插值

分段低階插值，收斂性好，但光滑性不夠理想。在工業(yè)設(shè)計中，對曲線光滑性要求高，如：流線型設(shè)想這樣一曲線：插值，次數(shù)不高于3次，整個曲線2階連續(xù)導(dǎo)數(shù)，稱為三次樣條函數(shù)插值。每個小區(qū)間不高于3次，有4n個未知數(shù)，我們的已知條件如下：共3n-3+n+1