插值法與曲線擬合插值法

插值法與曲線擬合插值法第1頁，共58頁，2023年，2月20日，星期五上一講的簡單回顧●

插值多項式的存在惟一性:

滿足插值條件

Pn(xi)=f(xi),(i=0,1,2,…,n)n次插值多項式Pn(x)=a0+a1x+a2x2+……+anxn存在而且惟一.●

插值余項:Rn(x)=f(x)-Pn(x)=,

●

Lagrange插值多項式其中,i=0,1,…,n稱為Lagrange插值基函數(shù)第2頁，共58頁，2023年，2月20日，星期五§1.3牛頓途徑對于n+1個不同的節(jié)點，考慮n次多項式（6）如果滿足：，那么它就是n+1個點上的n次插值多項式，對于這樣的，有第3頁，共58頁，2023年，2月20日，星期五

優(yōu)點:具有嚴格的規(guī)律性,便于記憶.

缺點:不具有承襲性,即每當(dāng)增加一個節(jié)點時,不僅要增加求和的項數(shù),而且以前的各項也必須重新計算.

為了克服這一缺點,本講將建立具有承襲性的插值公式—Newton插值公式.本講主要內(nèi)容:●

Newton插值多項式的構(gòu)造●

差商的定義及性質(zhì)●

差分的定義及性質(zhì)●

等距節(jié)點Newton插值公式第4頁，共58頁，2023年，2月20日，星期五一基函數(shù)

問題1

求作n次多項式使?jié)M足(2)為了使的形式得到簡化,引入如下記號(3)(1)第5頁，共58頁，2023年，2月20日，星期五

定義

由式(3)定義的n+1個多項式稱為Newton插值的以x0,,x1,…,xn為節(jié)點的基函數(shù),即

可以證明,這樣選取的基函數(shù)是線性無關(guān)的,由此得出的問題4.1的解便于求值,而且新增加一個節(jié)點xn+1時只需加一個新項

即

而

(4)第6頁，共58頁，2023年，2月20日，星期五

依據(jù)條件(2),可以依次確定系數(shù)c0,c1,…,cn..例如,

取x=x0,,得

取x=x1,得

取x=x2,得第7頁，共58頁，2023年，2月20日，星期五.

為了得到計算系數(shù)ci的一般方法,下面引進差商的概念.第8頁，共58頁，2023年，2月20日，星期五二差商的定義

給定[a,b]中互不相同的點x0,x1,x2,…,以及f(x)在這些點處相應(yīng)的函數(shù)值f(x0),f(x1),f(x2),…,用記號表示f(x)在x0及x1兩點的一階差商.用記號表示f(x)在x0,x1,x2三點的二階差商.一般地,有了k-1階差商之后,可以定義f(x)在x0,x1,..,xk的k階差商第9頁，共58頁，2023年，2月20日，星期五三Newton插值公式由差商定義,有

f(x)=f[x0]+(x-x0)f[x,x0]

f[x,x0]=f[x0,x1]+(x-x1)f[x,x0,x1]

f[x,x0,x1]=f[x0,x1,x2]+(x-x2)f[x,x0,x1,x2]………..

f[x,x0,…xn-1]=f[x0,…,xn]+(x-xn)f[x,x0,….,xn]將以上各式，由下而上逐步代入，得到

f(x)=f(x0)+(x-x0)f[x0,x1]+(x-x0)(x-x1)f[x0,x1,x2]

+…+(x-x0)…(x-xn-1)f[x0,…,xn]

+(x-x0)…(x-xn-1)(x-xn)f[x,x0,…xn](5)第10頁，共58頁，2023年，2月20日，星期五記

Nn(x)=

f(x0)+(x-x0)f[x0,x1]+(x-x0)(x-x1)f[x0,x1,x2]

+…+(x-x0)…(x-xn-1)f[x0,…,xn](6)

Rn(x)=(x-x0)…(x-xn)f[x,x0,…,xn]=f[x,x0,…,xn]wn+1(x)(7)則(5)可表示為

f(x)=Nn(x)+Rn(x)

(8)顯然,

Nn(x)是次數(shù)不超過n的多項式,且有

Rn(xi)=f[x,x0,…,xn]wn+1(xi)=0,i=0,1,…,n即Nn(xi)=f(xi),i=0,1,…,n由此可知,如此構(gòu)造的函數(shù)Nn(x)就是問題1的解,且

ci=f[x0,…,xi],i=0,1,…,n(9)第11頁，共58頁，2023年，2月20日，星期五

公式(6)稱為函數(shù)f(x)在節(jié)點x0,…,xn上的n階Newton插值公式,(7)式稱為Newton插值公式余項,即截斷誤差.注意到,余項表達式(7)只要求被插值函數(shù)f(x)在插值區(qū)間[a,b]上連續(xù).

由函數(shù)f(x)的插值多項式的惟一性,函數(shù)f(x)

的Newton插值多項式與Lagrange插值多項式實為同一個多項式,即

Nn(x)≡Ln(x)

兩者不過是表現(xiàn)形式不同而已.由此有:若f(x)∈Cn+1[a,b],則有

Rn(x)=f[x,x0,…,xn]wn+1(x)=,(10)第12頁，共58頁，2023年，2月20日，星期五四差商的性質(zhì)性質(zhì)1(差商與函數(shù)值的關(guān)系)證明：性質(zhì)2(對稱性)其中i0,…,ik是0,1,…k的任排列.證明:

由性質(zhì)1可知.第13頁，共58頁，2023年，2月20日，星期五

性質(zhì)3(差商與導(dǎo)數(shù)的關(guān)系)f(x)∈Ck[a,b],,

證明:

由式(10)即得.

性質(zhì)4(多項式的差商)設(shè)f(x)為n次多項式,則其一階差商

是x的n-1次多項式推論

n次多項式pn(x)的k階差商pn[x0,…xk],當(dāng)k≤n時是n-k次多項式,當(dāng)k>n時恒為0證明:第14頁，共58頁，2023年，2月20日，星期五

運用Newton插值公式(6)進行計算時,先計算f(x)關(guān)于

節(jié)點x0,…,xn的各階差商.計算過程如下表所示

..

xk

f(xk)

一階差商二階差商三階差商n階差商第15頁，共58頁，2023年，2月20日，星期五計算Nn(x)時,常采用秦九韶算法,即.下面給出Newton插值法的計算機算法.開始時,f(k)存放函數(shù)值f(xk),運算完畢f(xié)(k)存放k階差商f[x0,…,xk]第16頁，共58頁，2023年，2月20日，星期五Newton插值算法(1)輸入:xi,fi;di=fi(i=0,1,…,n);計算差商

對i=1,2,…,n做

(3.1)對j=i,i+1,…,n

做

fj=(dj-dj-1)/(xj-xj-i);(3.2)對j=i,i+1,…,n做dj=fj;(4)

計算插值N(u)(4.1)輸入插值點u;

(4.2)v=0;(4.3)對i=n,n-1,…,1,0做v=v(u-xi)+fi;(5)輸出u,v.第17頁，共58頁，2023年，2月20日，星期五五等距節(jié)點的Newton插值公式與差分

當(dāng)插值節(jié)點x0,…,xn為等距分布時,Newton插值公式(6)可以簡化.

設(shè)插值節(jié)點xj=x0+jh,j=0,1,…,n;h=(b-a)/n稱為步長,且x0=a,xn=b.令x=x0+th,則當(dāng)x0≤x≤xn時,0≤t≤n.基函數(shù)

此時差商也可進一步化簡,為此引進差分的概念.

定義

稱△f(xi)=f(xi+h)-f(xi)

和▽f(xi)=f(xi)-f(xi-h)分別為函數(shù)f(x)在點xi處的一階向前差分和一階向后差分.第18頁，共58頁，2023年，2月20日，星期五

一般地,稱k階差分的差分為k+1階差分,如二階向前和向后差分分別為

計算各階差分可按如下差分表進行.第19頁，共58頁，2023年，2月20日，星期五

向前差分表第20頁，共58頁，2023年，2月20日，星期五

差分具有如下性質(zhì):.

性質(zhì)1(差分與函數(shù)值的關(guān)系)各階差分均可表示為函值fj=f(xj)的線性組合:

性質(zhì)2(前差與后差的關(guān)系):

性質(zhì)3(多項式的差分)若f(x)∈Pn(n次多項式類),則其中第21頁，共58頁，2023年，2月20日，星期五

性質(zhì)4(差分與差商的關(guān)系):

性質(zhì)5(差分與導(dǎo)數(shù)的關(guān)系

利用這些性質(zhì),可將Newton公式

Nn(x)=f(x0)+(x-x0)f[x0,x1]+(x-x0)(x-x1)f[x0,x1,x2]

+…+(x-x0)…(x-xn-1)f[x0,…,xn]進一步簡化第22頁，共58頁，2023年，2月20日，星期五(11)稱公式(11)為Newton向前差分插值公式,其余項為(12)如果將式(6)改為按節(jié)點xn,xn-1,…,x0的次序排列的Newton插值公式,即第23頁，共58頁，2023年，2月20日，星期五

令x=xn-th,則當(dāng)x0≤x≤xn時,0≤t≤n.利用差商與向后差分的關(guān)系,式(13)可簡化為(13)(14)稱式(14)為Newton向后差分插值公式,其余項為第24頁，共58頁，2023年，2月20日，星期五

若要計算的插值點x較靠近點x0,則用向前插值公式(4.8),這時t=(x-x0)/n的值較小,數(shù)值穩(wěn)定性較好.反之,若x靠近xn,,,則用向后插值公式(14).

利用向前與向后差分的關(guān)系(差分性質(zhì)2):式(14)可表示成(15)這樣,計算靠近x0或xn的點的值時,都只需構(gòu)造向前差分表第25頁，共58頁，2023年，2月20日，星期五例給定f(x)在等距節(jié)點上的函數(shù)值表如下:

xi

0.40.60.81.0

f(xi)1.51.82.22.8分別用Newton向前和向后差分公式,求f(0.5)及f(0.9)的近似值.

解先構(gòu)造向前差分表如下:

xi

fi

△fi

△2fi△3fi

0.41.50.61.80.30.82.20.40.11.02.80.60.20.1

x0=0.4,h=0.2,x3=1.0.由(4.8)和(4.12),分別用差分表中對角線上的值和最后一行的值,得Newton向前和向后插值公式如下:第26頁，共58頁，2023年，2月20日，星期五(1)(2)當(dāng)x=0.5時,用公式(1),這時t=(x-x0)/h=0.5.將t=0.5代入(1),得

f

(0.5)≈N3(0.5)=1.64375.當(dāng)x=0.9時,用公式(2),這時t=(x3-x)/h=0.5.將t=0.5代入(2),得

f(0.9)≈N3(0.9)=2.46875.第27頁，共58頁，2023年，2月20日，星期五課后練習(xí)題

P217:第2題,第4題,P219:第11題.第28頁，共58頁，2023年，2月20日，星期五§6曲線擬合6.1.2曲線擬合問題仍然是已知x1…xm

;y1…ym,求一個簡單易算的近似函數(shù)f(x)

來擬合這些數(shù)據(jù)。但是①m很大；②

yi本身是測量值，不準確，即yi

f(xi)這時沒必要取

f(xi)=yi,而要使i=f(xi)yi總體上盡可能地小。這種構(gòu)造近似函數(shù)的方法稱為曲線擬合，f(x)

稱為擬合函數(shù)稱為“殘差”第29頁，共58頁，2023年，2月20日，星期五常見做法：使最小較復(fù)雜，P284使最小不可導(dǎo)，求解困難，P283使最小“使i=P(xi)yi盡可能地小”有不同的準則第30頁，共58頁，2023年，2月20日，星期五6.2線性擬合問題6.2.1||.||2意義下的線性擬合（線性最小二乘問題）確定擬合函數(shù)，對于一組數(shù)據(jù)(xi,yi)(i=1,2,…,m)使得達到極小，這里n

<＝

m。Denote:第31頁，共58頁，2023年，2月20日，星期五稱方程組Ax=b為超定方程組第32頁，共58頁，2023年，2月20日，星期五記E實際上是c0,c1,…,cn

的多元函數(shù)，在E

的極值點應(yīng)有第33頁，共58頁，2023年，2月20日，星期五得到關(guān)于c1,c2,…,cn的方程組法方程組(或正規(guī)方程組)第34頁，共58頁，2023年，2月20日，星期五例1數(shù)據(jù)ti020406080100fi81.477.774.272.470.368.8第35頁，共58頁，2023年，2月20日，星期五6.3線性最小二乘問題設(shè)A是m×n階矩陣(m>n),稱線性方程組Ax=b(1)

為超定方程組;這里x∈Rn,b∈Rm.如果A的秩r(A)=n,稱A為列滿秩矩陣.

記殘向量r=b-Ax，考慮確定一個向量x，使‖r‖22＝‖b-Ax‖22,達到最小的問題稱為線性最小二乘問題，這樣的x稱為方程組(1)的最小二乘解.第36頁，共58頁，2023年，2月20日，星期五6.3.4最小二乘解的存在惟一性

結(jié)論1：設(shè)A是m×n階矩陣，x∈Rn,b∈Rm.由線性方程組理論可知，線性方程組

Ax=b(24)

有解的充分必要條件是r(A)=r(A|b).(25)

第37頁，共58頁，2023年，2月20日，星期五

定理6.3.7假設(shè)方程組(24)有解，令x是其一個解.那么，方程組(24)的所有解的集合為{x}+N(A).方程組(24)有惟一解的充分必要條件是null(A)=0.這里，null(A)表示A的核子空間的維數(shù).第38頁，共58頁，2023年，2月20日，星期五

證明:首先證明任意的向量y∈{x}+N(A)都是方程組(24)的解.

事實上，將y記為y=x+z,

其中z∈N(A)，即Az=0，x∈{x}.因此，

Ay=Ax+Az=b,即y滿足方程組(24).

反過來，若y滿足方程組(24)，有

Ay-Ax=A(y-x)=0，即y-x∈N(A).

記y=x+(y-x)，從而有y∈｛x｝+N(A).

惟一性.因為齊次方程組Ax=0有惟一零解的充分必要條件是A為滿秩矩陣，即null(A)=0.第39頁，共58頁，2023年，2月20日，星期五定理6.3.8當(dāng)m>n時，超定方程組(1)的最小二乘解總是存在的.最小二乘解惟一的充分必要條件是null(A)=0.

第40頁，共58頁，2023年，2月20日，星期五證:記b=b１＋b２，其中b1∈R(A)，b2∈N(AＴ）.

對任意x∈Rn,Ax∈R(A),b1-Ax∈R(A).因此，

‖r‖22＝‖b-Ax‖22＝‖(b１-Ax)+b２‖22.

由定理6.3.3的推論1和定理6.3.2，

‖r‖22＝‖b１-Ax‖22+‖b２‖22．要使‖r‖22達到最小等價于確定x，使‖b１-Ax‖22

為0，即求方程組Ax=b１的解x.

因為b１,Ax,b１－Ax都是R(A)中的向量，因此，可以把b１看成由A的列向量線性表示，即b１＝Ax.

換句話說，方程組Ax=b１的解總是存在的，從而方程組(1)的最小二乘解也總是存在的.

惟一性的證明可直接由定理6.3.7得到.第41頁，共58頁，2023年，2月20日，星期五6.3.1正交性的有關(guān)性質(zhì)

在線性代數(shù)歐氏空間理論中，將R3中兩個向量x,y之間的夾角φ滿足的關(guān)系式

xTy=‖x‖2‖y‖2cosφ(2)

推廣到Rn.設(shè)x,y∈Rn，由Cauchy不等式

-1≤

≤1

從而得到Rn中兩個向量之間的夾角為

φ=arccos(3)第42頁，共58頁，2023年，2月20日，星期五

定理6.3.1

設(shè)x,y是Rn中的向量，x與y正交的充分必要條件為xＴy=0.

證：必要性.當(dāng)x與y正交，它們的夾角φ=π/2，由(2)式，有xＴy=0.

充分性.當(dāng)xＴy=0,由(3)式，φ=π/2,

即x與y正交.

注：如果x與y正交，記為x⊥y第43頁，共58頁，2023年，2月20日，星期五定理6.3.2：設(shè)x，y∈Rn，且x⊥y，那么：

‖x+y‖22＝‖x‖22＋‖y‖22．證：由‖x+y‖22=(x+y)Ｔ

(x+y)=xＴx+2yＴx+yＴy

而xＴy=yＴx=0,因此

‖x+y‖22＝‖x‖22+‖y‖22注：推廣到Rn中的向量組α１，α２，…，αk，如果αiＴαj=0(i≠j),稱α1，α2，…，αk是

正交向量組.

特別地:

如果‖αi‖2=1(i=1,2,…，k)，即

αiTαj=δij，稱α1，α2，…，αk

為標準正交向量組.

第44頁，共58頁，2023年，2月20日，星期五設(shè)U是Rn中的子空間，x∈Rn.如果x與U中任意向量正交，稱向量x與子空間U正交，記為x⊥U.設(shè)U，V是Rn中兩個子空間，如果任意x∈U和任意y∈V是正交的，稱子空間U與子空間V正交，記為U⊥V.設(shè)U，V是Rn中互補的子空間.如果U⊥V，那么稱U，V互為正交補子空間，記U=V⊥或V=U⊥.可以證明，一個子空間的正交補子空間是惟一的.第45頁，共58頁，2023年，2月20日，星期五定理6.3.3

設(shè)A是n×k階矩陣，x∈Rn,那么下列三種情況是等價的：①x⊥R(A);②AＴx=0;③x∈N(AＴ).

這里，N(AＴ)={AＴx=0,x∈Rn}稱為AＴ的核子空間.證：由N(AＴ)的定義，②與③顯然等價.

下面證明①與②等價.

記A=(α1,α2,…，αk)，那么，αi∈R(A)(i=1,2,…,k).

假設(shè)x⊥R(A),即αiＴx=0(i=1,2,…，k).從而AＴx=0.

另一方面，如果AＴx=0,那么有z∈Rk，使Az=y∈R(A).

這時，yＴx=zＴAＴx=0,即x⊥y.

由z的任意性，得Az是任意的，因此x⊥R(A).由這個定理，容易得到：推論1設(shè)A是n×k階矩陣，那么R(A)有惟一的正交補子空間N(AＴ).第46頁，共58頁，2023年，2月20日，星期五6.3線性最小二乘問題設(shè)A是m×n階矩陣(m>n),稱線性方程組Ax=b(1)

為超定方程組;這里x∈Rn,b∈Rm.如果A的秩r(A)=n,稱A為列滿秩矩陣.

記殘向量r=b-Ax，考慮確定一個向量x，使‖r‖22＝‖b-Ax‖22,達到最小的問題稱為線性最小二乘問題，這樣的x稱為方程組(1)的最小二乘解.第47頁，共58頁，2023年，2月20日，星期五6.3.1正交性的有關(guān)性質(zhì)

在線性代數(shù)歐氏空間理論中，將R3中兩個向量x,y之間的夾角φ滿足的關(guān)系式

xTy=‖x‖2‖y‖2cosφ(2)

推廣到Rn.設(shè)x,y∈Rn，由Cauchy不等式

-1≤

≤1

從而得到Rn中兩個向量之間的夾角為

φ=arccos(3)第48頁，共58頁，2023年，2月20日，星期五

定理6.3.1

設(shè)x,y是Rn中的向量，x與y正交的充分必要條件為xＴy=0.

證：必要性.當(dāng)x與y正交，它們的夾角φ=π/2，由(2)式，有xＴy=0.

充分性.當(dāng)xＴy=0,由(3)式，φ=π/2,

即x與y正交.

注：如果x與y正交，記為x⊥y第49頁，共58頁，2023年，2月20日，星期五定理6.3.2：設(shè)x，y∈Rn，且x⊥y，那么：

‖x+y‖22＝‖x‖22＋‖y‖22．證：由‖x+y‖22=(x+y)Ｔ

(x+y)=xＴx+2yＴx+yＴy

而xＴy=yＴx=0,因此

‖x+y‖22＝‖x‖22+‖y‖22注：推廣到Rn中的向量組α１，α２，…，αk，如果αiＴαj=0(i≠j),稱α1，α2，…，αk是

正交向量組.

特別地:

如果‖αi‖2=1(i=1,2,…，k)，即

αiTαj=δij，稱α1，α2，…，αk

為標準正交向量組.

第50頁，共58頁，2023年，2月20日，星期五設(shè)U是Rn中的子空間，x∈Rn.如果x與U中任意向量正交，稱向量x與子空間U正交，記為x⊥U.設(shè)U，V是Rn中兩個子空間，如果任意x∈U和任意y∈V是正交的，稱子空間U與子空間V正交，記為U⊥V.設(shè)U，V是Rn中互補的子空間.如果U⊥V，那么稱U，V互為正交補子空間，記U=V⊥或V=U⊥.可以證明，一個子空間的正交補子空間是惟一的.第51頁，共58頁，2023年，2月20日，星期五定理6.3.3

設(shè)A是n×k階矩陣，x∈Rn,那么下列三種情況是等價的：①x⊥R(A);②AＴx=0;③x∈N(AＴ).

這里，N(AＴ)={AＴx=0,x∈Rn}稱為AＴ的核子空間.證：由N(AＴ)的定義，②與③顯然等價.

下面證明①與②等價.

記A=(α1,α2,…，αk)，那么，αi∈R(A)(i=1,2,…,k).

假設(shè)x⊥R(A),即αiＴx=0(i=1,2,…，k).從而AＴx=0.

另一方面，如果AＴx=0,那么有z∈Rk，使Az=y∈R(A).

這時，yＴx=zＴAＴx=0,即x⊥y.

由z的任意性，得Az是任意的，因此x⊥R(A).由這個定理，容易得到：推論1設(shè)A是n×k階矩陣，那么R(A)有惟一的正交補子空間N(AＴ).第52頁，共58頁，2023年，2月20日，星期五6.3.2矩陣的QR分解定理6.3.4

設(shè)A=(α1,α2,…，αn)是列滿秩矩陣，αi∈Rm(i=1,2,…，n)且m≥n.那么，A有惟一的QR分解，記為

A=QR，(4)這里，Q是有n個標準正交列的m×n階矩陣，R是有正對角元的n階上三角矩陣.證：由A是列滿秩矩陣可知，AＴA是n階正定矩陣，因此有惟一的Cholesky分解：

AＴA=RＴR,(5)

這里R是有正對角元的上三角矩陣，R－１存在.

令Q=AR－１,(6)

那么，QＴQ=R－ＴAＴAR－１＝In,即Q是有標準正交列的m×n階矩陣.由(6)式，(4)式成立，且由(5)式的惟一性，分解式(4)也是惟一的.第53頁，共58頁，2023年，2月20日，星期五6.3.3Householder矩陣與矩陣的正交三角化定義1設(shè)w是歐氏空間Rn中的單位向量，形如H=I-2wwＴ

(10)

的n階矩陣稱為Householder