數(shù)值分析PPT-顏慶津-北京航空航天大學出版社-2000

數(shù)值分析

NumericalAnalysis

教材

(TextBook)

數(shù)值分析（第

3

版）,顏慶津,

北京航空航天大學出版社.參考書目

(Reference)

NumericalAnalysis(SeventhEdition)

數(shù)值分析（第七版影印版）

RichardL.Burden&J.DouglasFaires

（高等教育出版社）

現(xiàn)代數(shù)值分析,李慶揚、易大義、王能超編著（高等教育出版社）.第1章緒論§1.1

數(shù)值分析的研究對象提問：數(shù)值分析是做什么用的？輸入復雜問題或運算計算機近似解§1.1Introduction:Source&Classification數(shù)值分析研究內(nèi)容線性方程組的數(shù)值解；矩陣特征值與特征向量計算；非線性方程的數(shù)值解；數(shù)值逼近；數(shù)值積分；常微、偏微方程的數(shù)值解；研究方法理論分析算法分析誤差分析收斂性分析收斂速度討論§1.2

誤差知識與算法知識1.2.1誤差的來源與分類

從實際問題中抽象出數(shù)學模型

——模型誤差

(ModelingError)

通過測量得到模型中參數(shù)的值

——觀測誤差

(MeasurementError)

求近似解

——截斷誤差

(TruncationError)

機器字長有限

——舍入誤差(RoundoffError)模型誤差處理實際問題時，要建立數(shù)學模型，通常模型只是近似的。由此產(chǎn)生的數(shù)學模型解與實際問題的解之間的誤差叫模型誤差。例如 是實際問題的解，而若數(shù)學模型的解是 由此產(chǎn)生的誤差叫作模型誤差?！?ErrorandSignificantDigits

觀測誤差數(shù)學模型中包含某些變量，如時間、長度、電壓等，它們一般是通過觀測來獲得。由于觀測得到的數(shù)據(jù)與實際數(shù)據(jù)之間有誤差，這種誤差叫觀測誤差。截斷誤差求解數(shù)學模型所用的數(shù)值計算方法，如果是一種近似的方法，只能得到模型的近似解，由此產(chǎn)生的誤差稱為截斷誤差或方法誤差?！?ErrorandSignificantDigits

舍入誤差由于計算機的字長有限，參加運算的數(shù)據(jù)及其運算結(jié)果在計算機中存放會產(chǎn)生誤差。這種誤差叫舍入誤差或計算誤差。例如，在16位微機上計算，單精度實數(shù)存放僅有7位有效數(shù)字。在其上運算，會有

130.3333333,(1.000002)21.0000040;

后者的準確結(jié)果是41012?！?ErrorandSignificantDigits

大家一起猜？1解法之一：將作Taylor展開后再積分S4R4

(Remainder)取則稱為截斷誤差

(TruncationError).|

舍入誤差

(RoundoffError)|=0.747……由截掉部分引起(excludedterms)由留下部分引起(includedterms)1.2.2

誤差傳播與積累——算法的穩(wěn)定性例：計算公式一：§2ErrorandSignificantDigits

此公式成立,因為記為則初始誤差

????!!!Whathappened?!考察第

n

步的誤差(unstablealgorithm),我們有責任改變。這種算法是不穩(wěn)定的算法

迅速積累,可見初始的小擾動誤差遞增.可取當N時，

公式方法：先估計一個IN

,再反推要求的In(n<<N)。避免誤差積累的方法取

Wejustgotlucky?考察反推一步的誤差：以此類推，對n<N

有：誤差逐步遞減,這樣的算法稱為穩(wěn)定的算法

(stablealgorithm)在我們今后的討論中,誤差將不可回避,算法的穩(wěn)定性會是一個非常重要的話題。1.2.3

誤差與有效數(shù)字

(ErrorandSignificantDigits)定義

設

x為精確值，a

為x的近似值。近似值a

的絕對誤差

(absoluteerror)為例如：|e|的上界記為

e,稱為近似值a的絕對誤差限

(界，accuracy),工程上常記為x=a

±e.注:理論上講,e

是唯一確定的,可能取正,也可能取負;由定義e

>0不唯一，當然e越小越具有參考價值。例如，a

3.140作為圓周率的一個近似值，它的絕對誤差是e3.14

又|e|

0.002.

故，a

3.14作為的一個近似值，它的一個絕對誤差限是0.002。

下面定義的相對誤差更全面地刻畫了近似值與精確值之間差異的情況.定義

近似值a的相對誤差(relativeerror)為定義

近似值a的相對誤差(上)限(界)定義為

(relativeaccuracy)由于精確值x未知,實際上總把作為a的相對誤差，并且仍記為er,即例1

用最小刻度為毫米的卡尺測量直桿甲和直桿乙，分別讀出長度a312mm,b24mm.

問：(a),(b),r(a),r(b)各是多少？兩直桿實際長度x和y

在什么范圍？

解由最小刻度為毫米知,

(a)(b)0.5mm,，同理例2

設a2.18和b2.1200分別由準確值x和y經(jīng)過四舍五入而得到的近似值.

問：(a),(b),r(a),r(b)各是多少？

解

(a)0.005，(b)0.00005，預備知識：稱1位于102位，4位于101位，……有效數(shù)字

(significantdigits)四舍五入帶來的絕對誤差限

凡是由準確值x經(jīng)四舍五入而得到近似值a，其絕對誤差限等于該近似值末位的半個單位。定義有效數(shù)字設

a

是數(shù)

x的近似值，如果a

的絕對誤差限是它的某一位(設為10t

位)的半個單位,并且從該位到它的第一位非零數(shù)字共有n位，則稱用a

近似x時，具有

n位有效數(shù)字。例如，*3.142作為圓周率3

的一個近似值，它的絕對誤差限是 誤差限是102

位的半個單位，從102位到*的第一位非零數(shù)字共有3位，故依定義知,用3.142去近似時，具有3

位有效數(shù)字。*精確

到小數(shù)點后第2

位。近似數(shù)!精確數(shù)!定理1

把準確數(shù)x

的近似值a寫成a0.a1a2ak

10

m,

a10,mZ.

又絕對誤差限

(a)

0.510

t,則

a的有效數(shù)字位數(shù)n

mt

。證明(a)

0.510t,僅證情況m0，其它同理。因為,而，位10t

到10(m1)

位共有(m

1)

t

1

m

t個數(shù)，依有效數(shù)字位數(shù)的定義，知nmt

。注：絕對誤差限與有效數(shù)字位數(shù)n可互相確定！1.

用科學計數(shù)法，記近似數(shù)2.

表絕對誤差界則a(至少)有n

m

t位有效數(shù)字,且精確到10

t位.有效數(shù)字的確定方法有效數(shù)字的位數(shù)

n

近似數(shù)科學記數(shù)法的冪指數(shù)

絕對誤差限科學記數(shù)法的冪指數(shù).當差mt為負整數(shù)時，表示沒有效數(shù)字!

把誤差限表示為

0.510

t,當指數(shù)

t

是最小的整數(shù)時,有效數(shù)字的位數(shù)精確地是

n

m

t.

注意：t

mn！教材中表為

(a)0.510mn例問：有幾位有效數(shù)字？請證明你的結(jié)論。證明有

位有效數(shù)字，精確到小數(shù)點后第

位。43注：0.2300有4位有效數(shù)字，而00023只有2位有效。12300如果寫成0.123105，則表示只有3位有效數(shù)字。數(shù)字末尾的0不可隨意省去！例3

下列近似值的絕對誤差都是0.005,a

1.38,b0.0312,c0.86104,

問，各個近似數(shù)有幾位有效數(shù)字？(提示,使用定理1)解因為，a0.138101,(a)0.5102,

知a有3位有效數(shù)字，精確到小數(shù)點后第2位.b0.312101, (b)0.5102,

知b有1位有效數(shù)字：3,精確到小數(shù)點后第2位.對于c,m4,t2,nmt2,故c無有效數(shù)字。

有效數(shù)字

相對誤差限已知a

有n位有效數(shù)字，則其相對誤差限為相對誤差限有效數(shù)字已知a

的相對誤差限可寫為則可見a

至少有n位有效數(shù)字.

1.2.4

有效數(shù)字與相對誤差的關(guān)系§2ErrorandSignificantDigits

例：為使*的相對誤差小于0.001%,至少應取幾位有效數(shù)字？解:假設*取到n位有效數(shù)字,則其相對誤差上限為要保證其相對誤差小于0.001%，只要保證其上限滿足已知a1=3，則從以上不等式可解得n>6log6，即n6，應取*=3.14159。

1.2.5函數(shù)的誤差估計一元函數(shù)的誤差設u=f(x)有足夠高階的導數(shù),a是自變量x的近似值,則u*=f(a)是函數(shù)值u=f(x)的近似值.如果(a)0,且當a與x

很接近時,有誤差估計e(u*)f(x)f(a)()(xa)(a)e(a),

因|e(u*)||(a)||e(a)||(a)|(a),故(u*)|(a)|(a).

如果(a)(a)…(k1)(a)0,(k)(a)0,當a與x

很接近時,由Taylor公式,可得u*=f(a)的誤差估計中值定理!導數(shù)連續(xù)!多元函數(shù)的誤差

設n元函數(shù)u

f(x1,x2,,xn)充分可微,ai是xi的近似值,

i=1,2,…,n,

則

u*=f(a1,a2,,an)

是函數(shù)值u

f(x1,x2,,xn)的近似值.由多元函數(shù)的Taylor公式,可得u*的誤差估計誤差限的四則運算 設a和b分別是準確值x和y的近似值,則ab,ab,ab,ab(b

0),分別是xy,xy,xy,xy的近似值.由式(1.1)可以得例4

設有三個近似數(shù)a2.31,b1.93,c2.24.它們都有三位有效數(shù)字，試計算p

a+bc，(p),r(p),并問：p的計算結(jié)果能有幾位有效數(shù)字？解因為(p)0.02585<0.05

0.5101，所以p

能有2

位有效數(shù)字。解

由于

所以因而，u*=0.49543能有2位有效數(shù)字。例5設如果用作為f(x,y)的近似值,則u*能有幾位有效數(shù)字？1.2.6

算法與計算復雜性定義

算法的計算復雜性

是指在達到給定精度時,該算法所需的計算量和所占的內(nèi)存空間.前者叫時間復雜性，后者叫空間復雜性.

在同一精度要求下，算法所需計算量小，稱為時間復雜性好；所占內(nèi)存空間少，叫空間復雜性好。例子計算下面的多項式的值。輸入數(shù)據(jù)為aj

和x,輸出數(shù)據(jù)為p(x)的值。算法一算法二（秦九韶法）算法一所需乘法次數(shù)為n(n+1)/2,加法次數(shù)為n。秦九韶法原理Tn=anTn-1=

xTn+an-1T0=

xT1+a0T1=

xT2+a1算法二

所需乘法次數(shù)為n,加法次數(shù)為n。兩種算法所占內(nèi)存空間基本相同。算法二是1247年我國數(shù)學家秦九韶首次提出的。1.相近二數(shù)相減，會損失有效數(shù)字例：a1=0.12345，a2=0.12346，各有5位有效數(shù)字.

而a2

a1=0.00001，只剩下1位有效數(shù)字。

“避免相近兩數(shù)減”的經(jīng)驗性方法：當|x|<<1時：設計算法時應遵循的原則2.避免小分母:分母小會造成浮點溢出(overflow)3.避免大數(shù)吃小數(shù)例：用單精度計算的根。精確解為算法1:利用求根公式在計算機內(nèi)，109存為0.11010，1存為0.1101。做加法時，兩加數(shù)的指數(shù)先向大指數(shù)對齊，再將浮點部分相加。即1的指數(shù)部分須變?yōu)?010，則：1=0.00000000011010，取單精度時就成為：109+1=0.100000001010+0.000000001010=0.100000001010大數(shù)吃小數(shù)算法2:先解出再利用注：求和時從小到大相加，可使和的誤差減小.例：按從小到大、以及從大到小的順序分別計算1+2+3+…+40+1094.先化簡再計算，減少步驟，避免誤差積累。一般來說，計算機處理下列運算的速度為5.選用穩(wěn)定的算法?！?.3向量與矩陣的范數(shù)1向量的范數(shù)定義

向量的范數(shù)是刻畫向量大小的量,又叫向量的模.(1)正定性:,且;(2)齊次性:對,有;(3)三角不等式:.定義

Rn

上的實值函數(shù)||·||稱為向量范數(shù)，如果對任意的x,

y∈Rn,

它均滿足下列條件:上3個條件,叫范數(shù)公理.定理1.1

對

Rn

中的任一向量則和都是向量范數(shù).記,,,

3種常用的范數(shù)滿足正定性是顯然的.(1)證明

僅證是向量范數(shù).(2)

對任意的實數(shù)

k,有(3)設,則■p-范數(shù)叫1-范數(shù);叫2-范數(shù),(Euclid范數(shù));叫-范數(shù).其中,這是因為,從而有,令p,在上不等式兩端取極限,有定義

Rn

上的兩個范數(shù)||·||

與||·||

稱為等價存在與x無關(guān)的兩個正常數(shù)C1

C2,使引理任一個向量范數(shù)||x||都是x

的每一個分量xi

(i=1,2,…,n)

的連續(xù)函數(shù).

證明見,計算方法,哈爾濱工業(yè)大學,張池平,科學出版社,2005.7,p64.若等價,則也等價.因為由式(*)可推知:范數(shù)等價具有對稱性,反身性,還有傳遞性.即,若有使則用傳遞性與引理,可以證明范數(shù)的等價性定理.任2種范數(shù)在刻畫收斂性時等價定理1.2

對

Rn

上的任意二種向量范數(shù)||

·||a,||·||b,均有與向量

x無關(guān)的常數(shù)

m與M(0<m<M)，使下列的關(guān)系成立滿足定理條件的兩范數(shù)稱為等價。證明，見計算方法，張池平．2

矩陣的范數(shù)定義

矩陣的范數(shù)是刻畫矩陣大小的量,又叫矩陣的模.定義

Rnn上的實值函數(shù)‖·‖叫矩陣范數(shù),如果對Rnn中任意的矩陣A和B,均滿足下列4個條件:正定性齊次性三角不等式積的范數(shù)小于等于范數(shù)的積矩陣范數(shù)與向量范數(shù)的相容性定義

給定向量范數(shù)||·||和矩陣范數(shù)||·||,

如果對任意的向量xRn和任意的矩陣ARn×n,它們總滿足則稱所給的矩陣范數(shù)與向量范數(shù)是相容的。定理1.3

設在Rn

中給定一種向量范數(shù),對任意的矩陣ARn×n，下式(1.2)中定義的函數(shù)是一種矩陣范數(shù),并且它與給定的向量范數(shù)是相容的.,單位球上的最大像值證明

先證相容性.對任意的n

n矩陣A和n維非零向量y.由于所以有此結(jié)果對y=0也成立.再證(1.2)

式定義的函數(shù)為矩陣范數(shù).(1)當A0時,||A||0；當A

0時,必有x0Rn,||x0||1,滿足Ax0

0,因而,必有||A||>0.(2)對任意的數(shù)k

R，有(3)對任意的n×n

矩陣A和

B,

有(4)對任意的n×n

矩陣A和B,

有■相容性(1.2)式所定義的矩陣范數(shù)叫做從屬于所給定向量范數(shù)的矩陣范數(shù),又稱為矩陣的算子范數(shù).設給定的向量范數(shù)為

||·||p,則從屬于向量范數(shù)的矩陣范數(shù)為:上式中矩陣范數(shù)||A||p也叫A的p-范數(shù).矩陣的p-范數(shù)與向量的p-范數(shù)是相容的,即,||Ax||p≤||A||p·

||x||p.常用的算子范數(shù)：定理1.4當p1,2,時，

證明

對于2-范數(shù),設n維向量x滿足||x||21.注意到因為，ATA是正定或半正定的,故它的全部特征值i非負,設其中，max(ATA)

表示矩陣ATA的最大特征值.列向量1范數(shù)的最大.行向量1范數(shù)的最大.設ATA

相應的規(guī)范正交特征向量為u1,

u2,…,

un,因而存在實數(shù)k1,k2,…,kn，使并且有由此可得所以取,則有,以及■▼1,∞-范數(shù)公式證明再證明||A||2可以取到max.Frobenius

范數(shù)：性質(zhì)：單位矩陣I

的任何一種算子范數(shù)都有定理1.5

設矩陣A∈Rn×n

的某種范數(shù)||A||

1，則I±A為非奇異矩陣，并且當該種范數(shù)為算子范數(shù)時，還有下式成立。證明假定I±A奇異，則齊次線性方程組在上式兩邊同取與所用矩陣范數(shù)相容的向量范數(shù)，得因，故由上式得。與已知條件矛盾，因而I±A

必非奇異。由于在最后一式兩端取范數(shù)，得因為，故例6設，求以及又，及故解列向量1范數(shù)的最大.行向量1范數(shù)的最大.特征多項式為最大的根為注:求矩陣的特征值,可使用Matlab

命令[V,D]=eig(X) [V,D]=EIG(X)producesadiagonalmatrixDofeigenvaluesandafullmatrixVwhosecolumnsarethecorrespondingeigenvectorssothatX*V=V*D.第一章作業(yè)1下列各近似值均有四位有效數(shù)字,a0.01347,b

12.341,c

1.200

試指出它們的絕對誤差限與相對誤差限.2下列各近似值的絕對誤差限都是0.0005,a

1.00031,b0.042,c

0.00032

試指出它們有幾位有效數(shù)字.4已知x2.140.005,y1.2310.0005, (1)用作為的近似值; (2)用作為的近似值.

試求的絕對誤差限和相對誤差限,并指出能有幾位有效數(shù)字.7

在四位十進制的限止下,試選擇精度最高的算法,計算下式的值.8

設,在四位十進制的限止下,尋找一個數(shù)值穩(wěn)定的算法,計算的近似值.12已知 試求:以及第一章內(nèi)容結(jié)束！對于1-范數(shù),設

.矩陣A可表示為其中,定理1.4第1個結(jié)論的證明取

,它的第r個分量是1,顯然,且

于是有

■對于∞-范數(shù),設向量