《線性代數(shù)》課件D1-3

第一章§3選用和設(shè)計算法時

應(yīng)遵循的原則

一﹑選用數(shù)值穩(wěn)定的計算公式，控制舍入誤差的傳播三﹑盡量避免兩個相近的數(shù)相減二﹑盡量簡化計算步驟以便減少運算次數(shù)四﹑絕對值太小的數(shù)不宜作除數(shù)五﹑合理安排運算次序，防止大數(shù)“吃掉”小數(shù)2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則2一﹑選用數(shù)值穩(wěn)定的計算公式，控制舍入誤差的傳播對于一個數(shù)值算法，如果原始數(shù)據(jù)或某一步有舍入誤差，但在計算過程中，這些誤差能得到控制（即誤差不會放大或不影響結(jié)果的精度要求），則稱該數(shù)值方法是穩(wěn)定的；否則，若誤差在計算中傳播使計算結(jié)果的誤差增長很快，稱它是不穩(wěn)定的。2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則3

例

計算并估計誤差.

由分部積分可得計算的遞推公式

算法1

先計算I0，再由上式依次計算I1,···,I8.設(shè)In的計算值為In*,則In*=1－nIn-1*，絕對誤差n=1,2,···,8.為E(In*)=In*

－In=-n(In-1*－In-1)=-nE(In-1*)，2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則4I0=1-exp(-1)≈0.63212055882856,取I0*

=0.6321,

記初始誤差E(I0*)=I0*

－I0=-δ，則E(I1*)=-E(I0*)=δ，

E(I2*)=-2E(I1*)=-2δ，

E(I3*)=-3E(I2*)=3!δ，

………E(I8*)=-8!δ=-40320δ≈-0.83，

誤差在計算過程中傳播，增長很快！所以，這是一個不穩(wěn)定的算法。E(In*)=-nE(In-1*)2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則5k=9;I=zeros(k,1);I(1)=0.6321;forn=1:k-1I(n+1)=1-n*I(n);endformatlong;I算算看：

I8*=-0.72800000000019得到：>>f=inline('x.^8.*exp(x-1)');I8=quad(f,0,1)利用Matlab數(shù)值積分內(nèi)置函數(shù)quad檢驗結(jié)果：I8=0.10093212627740得到：

2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則6這樣的誤差還可以接受。但是若k繼續(xù)增加，當k=19，計算I19*，則誤差E(I19*)=-19!δ

=1.216451004088320e+017δ足夠大，使I19*<0.

如果就取I0*

=0.63212055882856,則初始誤差

回顧：I0=1-exp(-1)≈0.63212055882856,

E(I0*)=δ<10-13，E(I8*)=40320δ<10-8,

結(jié)論：即使現(xiàn)在計算機的計算精度大為提高，誤差的傳播仍然可能使得計算結(jié)果完全失真。2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則7k=19;I=zeros(k,1);I(1)=1-exp(-1);forn=1:k-1I(n+1)=1-n*I(n);endformatlong;I算算看：

I19*=-0.02945367075154得到：>>f=inline('x.^19.*exp(x-1)');I19=quad(f,0,1)利用Matlab數(shù)值積分內(nèi)置函數(shù)quad檢驗結(jié)果：I19

=0.04772276471237得到：

2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則8怎樣計算I40？注意到0≤x≤1時，1≤ex≤e,把計算In的遞推公式

改寫一下，得算法2

先計算I40，再由上式依次計算I39,···,I19.(n=40,39,...,20)即可取2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則9或干脆取

設(shè)In的計算值為In*,則In-1*=(1－In*)/n,誤差E(In-1*)=In-1*

－In-1=E(In*)/(-n)，n=40,39,···,20.若E(I40*)=δ,則E(I19*)=-19!δ/(40!),初始誤差的影響逐步減少，到最后甚至可以忽略，算法穩(wěn)定。小結(jié)：要選用數(shù)值穩(wěn)定的計算公式，控制舍入誤差的傳播2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則10k=41;I=zeros(k,1);I(1)=0;forn=k:-1:21I(n-1)=(1-I(n))/(n-1);endformatlong;I(20)算算看：

I19*=0.04772275579621得到：>>f=inline('x.^19.*exp(x-1)');I19=quad(f,0,1)利用Matlab數(shù)值積分內(nèi)置函數(shù)quad檢驗結(jié)果：I19

=0.04772276471237得到：

2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則11二﹑盡量簡化計算步驟以便減少運算次數(shù)例計算多項式

次乘法和

n次加法.若用秦九韶算法（又稱Horner算法）的值，若直接計算再逐項相加，一共需做

2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則12只需做n次乘法和n次加法運算。Matlab命令horner

將符號多項式表為嵌套形式。2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則13三﹑盡量避免兩個相近的數(shù)相減(減法)要盡量避免兩個相近的數(shù)相減，損失有效位數(shù)。四則運算中的穩(wěn)定性問題

如若取4位有效數(shù)字計算，則這個結(jié)果只有1位有效數(shù)字計算，損失了3位有效數(shù)字，嚴重影響了計算結(jié)果的精度。2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則14如果改變計算公式，避免兩個相近的數(shù)相減，它仍有4位有效數(shù)字。又如在實驗課上，用Matlab運行此例，結(jié)果如何？在16位，32位或64位計算機上，舉出合適例子，說明以上問題，并在實驗課上，用Matlab運行。2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則15四﹑絕對值太小的數(shù)不宜作除數(shù)(除法)分母稍微改變：0.001→0.0011在實驗課上，用Matlab運行此例，結(jié)果如何？不僅要盡量避免兩個相近的數(shù)相減，還要特別注意避免再用這個差作除數(shù)。2023/4/22第一章第三節(jié)選用和設(shè)計算法時應(yīng)遵循的原則16（加法）要防止大數(shù)吃掉小數(shù)：注意數(shù)