《計(jì)算方法》第一章 緒論

1、1計(jì) 算 方 法計(jì)算方法課程組華中科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院第一章第一章 緒緒 論論2 1 1 緒緒 論論 1.1 數(shù)值算法概論數(shù)值算法概論 1.2 預(yù)備知識預(yù)備知識 1.3 誤差誤差 1.4 題型分析與小結(jié)題型分析與小結(jié)3 “ “計(jì)算方法計(jì)算方法”是計(jì)算數(shù)學(xué)的一個(gè)主要部分。而計(jì)是計(jì)算數(shù)學(xué)的一個(gè)主要部分。而計(jì)算數(shù)學(xué)是數(shù)學(xué)科學(xué)的一個(gè)重要分支，它算數(shù)學(xué)是數(shù)學(xué)科學(xué)的一個(gè)重要分支，它研究用計(jì)算研究用計(jì)算機(jī)求解數(shù)學(xué)問題的數(shù)值計(jì)算方法及其軟件實(shí)現(xiàn)機(jī)求解數(shù)學(xué)問題的數(shù)值計(jì)算方法及其軟件實(shí)現(xiàn). . 數(shù)值計(jì)算已經(jīng)成為計(jì)算機(jī)處理實(shí)際問題的一種數(shù)值計(jì)算已經(jīng)成為計(jì)算機(jī)處理實(shí)際問題的一種關(guān)鍵手段，它使各科學(xué)領(lǐng)域從定性分析階段

2、走向定關(guān)鍵手段，它使各科學(xué)領(lǐng)域從定性分析階段走向定量分析階段，從粗糙走向精密。量分析階段，從粗糙走向精密。 科學(xué)理論、科學(xué)試驗(yàn)和科學(xué)計(jì)算科學(xué)理論、科學(xué)試驗(yàn)和科學(xué)計(jì)算( (計(jì)算的方法計(jì)算的方法) )是現(xiàn)代科學(xué)的三個(gè)組成部分。是現(xiàn)代科學(xué)的三個(gè)組成部分。1.1 1.1 數(shù)值算法概論數(shù)值算法概論4 方程求解方程求解 非線性方程或方程組、常微分方程、偏微分非線性方程或方程組、常微分方程、偏微分方程數(shù)值解法。方程數(shù)值解法。 數(shù)值代數(shù)數(shù)值代數(shù) 求解線性方程組的解法（分直接方法和間接求解線性方程組的解法（分直接方法和間接方法），求矩陣的特征值與特征向量。方法），求矩陣的特征值與特征向量。 數(shù)值逼近數(shù)值逼近 插

3、值和數(shù)值逼近，數(shù)值微分和數(shù)值積分。插值和數(shù)值逼近，數(shù)值微分和數(shù)值積分。 1.1 1.1 數(shù)值算法概論數(shù)值算法概論研究內(nèi)容研究內(nèi)容 5例如例如: :03832 xx 1 , 0*x1. 求方程求方程在在上的根上的根;；2. 求解線性方程組求解線性方程組 , 其中其中為為3階可逆方陣階可逆方陣,AXb A123(,)TXx xx 為為3. 已知已知上的直線，滿足上的直線，滿足求求 ；)(xPy ,10 xx(),00P xy(),11P xy(,),01xxx)(xP4. 計(jì)算定積分計(jì)算定積分badxxI1)1 (ba 5. 解常微分方程初值問題解常微分方程初值問題00()yxyy xy 6 計(jì)算

4、方法是一門與計(jì)算機(jī)應(yīng)用密切結(jié)合的實(shí)計(jì)算方法是一門與計(jì)算機(jī)應(yīng)用密切結(jié)合的實(shí)用性很強(qiáng)的學(xué)科；思維方法是歸納法，核心問題用性很強(qiáng)的學(xué)科；思維方法是歸納法，核心問題是是“誤差誤差”或或誤差分析誤差分析。 計(jì)算方法這門課程討論連續(xù)變量問題又要討計(jì)算方法這門課程討論連續(xù)變量問題又要討論離散變量問題，關(guān)心的是論離散變量問題，關(guān)心的是數(shù)值結(jié)果數(shù)值結(jié)果。 計(jì)算方法、計(jì)算數(shù)學(xué)、數(shù)值分析或數(shù)值方法計(jì)算方法、計(jì)算數(shù)學(xué)、數(shù)值分析或數(shù)值方法這門課程已成為近代數(shù)學(xué)的一個(gè)重要分支。這門課程已成為近代數(shù)學(xué)的一個(gè)重要分支。1.1 1.1 數(shù)值算法概論數(shù)值算法概論研究對象研究對象 7 面向計(jì)算機(jī)面向計(jì)算機(jī) 將計(jì)算機(jī)上不能執(zhí)行的運(yùn)算

5、化為在計(jì)算機(jī)上可執(zhí)行的將計(jì)算機(jī)上不能執(zhí)行的運(yùn)算化為在計(jì)算機(jī)上可執(zhí)行的運(yùn)算。運(yùn)算。 有可靠的理論分析有可靠的理論分析（收斂性、穩(wěn)定性、誤差分析）。（收斂性、穩(wěn)定性、誤差分析）。 因?yàn)榭赡懿捎昧私频葍r(jià)運(yùn)算因?yàn)榭赡懿捎昧私频葍r(jià)運(yùn)算, ,故要進(jìn)行誤差分析故要進(jìn)行誤差分析, ,即即數(shù)值的性態(tài)及數(shù)值方法的穩(wěn)定性。數(shù)值的性態(tài)及數(shù)值方法的穩(wěn)定性。 要有好的算法，并考慮計(jì)算復(fù)雜性要有好的算法，并考慮計(jì)算復(fù)雜性（時(shí)間、空間）（時(shí)間、空間） 針對所求解的數(shù)值問題研究在計(jì)算機(jī)上可執(zhí)行的且有針對所求解的數(shù)值問題研究在計(jì)算機(jī)上可執(zhí)行的且有效的計(jì)算公式。效的計(jì)算公式。 要有數(shù)值試驗(yàn)要有數(shù)值試驗(yàn)1.1 1.1 數(shù)值算法概

6、論數(shù)值算法概論特點(diǎn)特點(diǎn) 8現(xiàn)實(shí)科學(xué)與工程問題的解決步驟：現(xiàn)實(shí)科學(xué)與工程問題的解決步驟：實(shí)際問題實(shí)際問題建立數(shù)學(xué)模型建立數(shù)學(xué)模型構(gòu)造數(shù)值算法構(gòu)造數(shù)值算法編程上機(jī)編程上機(jī)獲取近似結(jié)果獲取近似結(jié)果計(jì)算方法是一種研究并計(jì)算方法是一種研究并解決數(shù)學(xué)問題的數(shù)值解決數(shù)學(xué)問題的數(shù)值近近似解似解方法方法 隨著計(jì)算機(jī)的飛速發(fā)展，數(shù)值分析隨著計(jì)算機(jī)的飛速發(fā)展，數(shù)值分析方法已深入到計(jì)算物理、計(jì)算力學(xué)、方法已深入到計(jì)算物理、計(jì)算力學(xué)、計(jì)算化學(xué)、計(jì)算生物學(xué)、計(jì)算經(jīng)濟(jì)學(xué)計(jì)算化學(xué)、計(jì)算生物學(xué)、計(jì)算經(jīng)濟(jì)學(xué)等各個(gè)領(lǐng)域。本課僅介紹最常用的數(shù)等各個(gè)領(lǐng)域。本課僅介紹最常用的數(shù)學(xué)模型的最基本的數(shù)值分析方法。學(xué)模型的最基本的數(shù)值分析方法。

7、1.1 1.1 數(shù)值算法概論數(shù)值算法概論數(shù)值算法數(shù)值算法 9 良態(tài)與病態(tài)問題良態(tài)與病態(tài)問題 良態(tài)與病態(tài)良態(tài)與病態(tài): : 初始數(shù)據(jù)的的微小變化初始數(shù)據(jù)的的微小變化( (擾動擾動) )，導(dǎo)致計(jì)算結(jié)果的相，導(dǎo)致計(jì)算結(jié)果的相對誤差很大，這樣的問題稱為對誤差很大，這樣的問題稱為病態(tài)病態(tài)的，相反稱為的，相反稱為良態(tài)良態(tài)的。的。 1.1 1.1 數(shù)值算法概論數(shù)值算法概論算法的數(shù)值穩(wěn)定性算法的數(shù)值穩(wěn)定性 例：例：蝴蝶效應(yīng)蝴蝶效應(yīng) 紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北京紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北京就刮起臺風(fēng)來了？！就刮起臺風(fēng)來了？！NYBJ誤差的傳播與積累誤差的傳播與積累導(dǎo)致以上問題是一個(gè)導(dǎo)致以上問題

8、是一個(gè)病態(tài)問題病態(tài)問題10良態(tài)與病態(tài)問題良態(tài)與病態(tài)問題 2* ( )1150 x100 /3f xxx在 的值?1.1 1.1 數(shù)值算法概論數(shù)值算法概論算法的數(shù)值穩(wěn)定性算法的數(shù)值穩(wěn)定性 例例1 111良態(tài)與病態(tài)問題良態(tài)與病態(tài)問題 2* ( )1150 x100 /3f xxx在的值?1.1 1.1 數(shù)值算法概論數(shù)值算法概論算法的數(shù)值穩(wěn)定性算法的數(shù)值穩(wěn)定性 50 f100/35.6 9 f3328 , . （），（） 該函解數(shù)是病態(tài)的：例例1 112良態(tài)與病態(tài)問題良態(tài)與病態(tài)問題 例例1 2* ( )1150 x100 /350 f100/35.6 9 f3328 , .fxxx在的 值解 ： （

9、） ，（） 該 函 數(shù) 是 病 態(tài) 的%.40095028950)()()(, %1310031, 4 .22)()(, 34. 031*xfxfxfxxxxfxfxx1.1 1.1 數(shù)值算法概論數(shù)值算法概論算法的數(shù)值穩(wěn)定性算法的數(shù)值穩(wěn)定性 分析分析: :13例例2 2dxxxInn105計(jì)算計(jì)算數(shù)值穩(wěn)定性分析數(shù)值穩(wěn)定性分析14例例2 2dxxxInn105計(jì)算計(jì)算數(shù)值穩(wěn)定性分析數(shù)值穩(wěn)定性分析15例例2 2dxxxInn105計(jì)算計(jì)算數(shù)值穩(wěn)定性分析數(shù)值穩(wěn)定性分析16dxxxInn105例例2(2(續(xù)續(xù)) )11111005155nnnnnxxIIdxxdxxn 構(gòu)造算法如下：構(gòu)造算法如下：10

10、165 , ln5nnIIIn nI 1.1811 , 0.0195nnIIIn nI2.17n n0 00.18200.18200.18200.18200.18200.18201 10.08800.08800.09000.09000.08800.08802 20.05800.05800.05000.05000.05800.05803 30.04310.04310.08300.08300.04310.04314 40.03430.0343-0.165-0.1650.03430.03435 50.02840.02841.02501.02500.02840.02846 60.02400.0240-

11、4.958-4.9580.02400.02407 70.02100.021024.93324.9330.02100.02108 80.01900.0190-124.540-124.5400.01900.0190nInI nI105nnxIdxx 01811615 , ln51 12 , 0.0195nnnnnnIInnIIIIII 18對格式對格式1 1，如果前一步有誤差，如果前一步有誤差， 則被放大則被放大5 5倍加到這一步倍加到這一步稱為不穩(wěn)定稱為不穩(wěn)定格式格式對格式對格式2，為，為穩(wěn)定格式，對舍入誤差有抑制作用穩(wěn)定格式，對舍入誤差有抑制作用01811615 , ln51 12 , 0.0

12、195nnnnnnIInnIIIIII 原因：19例如例如:求解微分方程求解微分方程:0)0(32yxy23yxx 其其解解: :針對輸入與輸出的都是數(shù)值的數(shù)學(xué)問題針對輸入與輸出的都是數(shù)值的數(shù)學(xué)問題.1.1 1.1 數(shù)值算法概論數(shù)值算法概論數(shù)值算法數(shù)值算法 20例如例如:求解微分方程求解微分方程:0)0(32yxy23yxx 其其解解: :將其變成數(shù)值問題，即將其將其變成數(shù)值問題，即將其“離散化離散化”12(),(),()nyxyxyx“離散化離散化”是將非數(shù)值問題的數(shù)學(xué)模型化為數(shù)值問題是將非數(shù)值問題的數(shù)學(xué)模型化為數(shù)值問題的主要方法，這也是計(jì)算方法的任務(wù)之一的主要方法，這也是計(jì)算方法的任務(wù)之一

13、.121,niixxxxxh 針對輸入與輸出的都是數(shù)值的數(shù)學(xué)問題針對輸入與輸出的都是數(shù)值的數(shù)學(xué)問題.()( )( )y xhy xy xh1.1 1.1 數(shù)值算法概論數(shù)值算法概論數(shù)值算法數(shù)值算法 21Rn空間的向量范數(shù)空間的向量范數(shù) | | 對任意對任意 , ,滿足下列條件：滿足下列條件：nxR(1)|0; |00 xxx（正定性正定性)對任意對任意(2) | | | |xxC (齊次性齊次性) (3) | | |xyxy（三角不等式三角不等式)1.2 1.2 預(yù)備知識預(yù)備知識向量范數(shù)向量范數(shù)22TnnnxxxxCR),(,)(21設(shè)中在向量空間21222212)xxx(xn 范數(shù)或歐氏范數(shù)的

14、 2x1xnxxx21范數(shù)的1xxinix1max范數(shù)或最大范數(shù)的x-(1)-(2)-(3)pxppnppxxx121)(-(4)1,ppx范數(shù)的常用的向量x的范數(shù)有23下述范數(shù)的幾何意義是下述范數(shù)的幾何意義是: :2121max(,)xxxyy21211xxxyy2221212()()xyyxx24求下列向量的各種常用范數(shù)求下列向量的各種常用范數(shù)Tx)1,3,4,1(25求下列向量的各種常用范數(shù)求下列向量的各種常用范數(shù)Tx)1,3,4,1(:1x421xxx92x21242221)(xxx3327 xiix41max41 1* *499/4499/4* *4=94=9即即本例中本例中顯然顯然

15、, 211 xcxxc,26范數(shù)等價(jià)的定義: 設(shè)設(shè)A A 和和B B 是是R R上任意兩種范數(shù)，若上任意兩種范數(shù)，若存在存在常數(shù)常數(shù) C1、C2 0 0 使得使得|1BA2BCxxCx則稱則稱 和和 等價(jià)等價(jià)。| |Bx| |Ax Rn 上上一切范數(shù)一切范數(shù)都等價(jià)都等價(jià)。定理定理1 1272x和1x顯然顯然時(shí)的特例和在是21ppxp并且由于并且由于ppnppxxx121)(inix1maxppinixn11)max(inipxn11max)(max1pxini x所所以以的特例也是px),(時(shí)pxxp12xxx且:一般有向量的等價(jià)關(guān)系一般有向量的等價(jià)關(guān)系 )c,c;1,2,qp,q,(p 21

16、21 Rxcxxcpqp28 對對 任意一種向量范數(shù)任意一種向量范數(shù)而言，向量序而言，向量序列列xk k收斂于向量收斂于向量x* *的充分必要條件是的充分必要條件是*lim |0kkxx 定理定理2 2nR29定義定義：設(shè)是一種向量范數(shù)是一種向量范數(shù)AxxAxAxRxxRxnn1,0,supsup稱之為由向量范數(shù)派生的稱之為由向量范數(shù)派生的矩陣算子范數(shù)矩陣算子范數(shù).定義定義 設(shè)設(shè) 是以是以n n階方陣為變量的實(shí)值函數(shù)階方陣為變量的實(shí)值函數(shù), ,且滿足條件且滿足條件: : (1) 非負(fù)性非負(fù)性: : A0 ,且A=0當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A=0=0 (2) 齊次性齊次性: : A=| |A, R (3

17、) 三角不等式三角不等式: :A+BA+B (4) 相容性相容性: : ABAB則稱則稱A為矩陣為矩陣A的的范數(shù)范數(shù). 1.2 1.2 預(yù)備知識預(yù)備知識矩陣范數(shù)矩陣范數(shù)( (續(xù)續(xù)) ) 30常用的矩陣范數(shù)常用的矩陣范數(shù)1(1)Aniijnja11max,大值的每列絕對值之和的最A(yù)的列范數(shù)稱A A(2)njijnia11max,大值的每行絕對值之和的最A(yù)的行范數(shù)稱A2(3)A)(maxAAT大值大值的特征值的絕對值的最的特征值的絕對值的最為為其中其中AA)AA(TTmax范范數(shù)數(shù)的的稱稱 2A-(5)-(6)-(7) ninjijFaA112| 向量向量| |2的推廣的推廣 Frobenius

18、Frobenius 范數(shù)范數(shù)(4)-(8)31110121021A求矩陣求矩陣A A的各種常用范數(shù)的各種常用范數(shù)1Aniijnja11max25234252 ,5 ,2max1njAnjijnia11max42 ,4 ,3max1ni2A)(maxAAT由于由于32110121021A求矩陣求矩陣A A的各種常用范數(shù)的各種常用范數(shù)2A)(maxAAT由于由于的特征值因此先求AATAAT110121021110122011211190102特征方程為特征方程為)det(AAIT211190102033110121021A求矩陣求矩陣A A的各種常用范數(shù)的各種常用范數(shù)2A)(maxAAT由于由于的

19、特征值因此先求AAT特征方程為特征方程為)det(AAIT2111901020的特征值為可得AAT9361. 0,9211. 2,1428. 93211428. 9)(maxAAT2A)(maxAAT3.0237342A)(maxAAT0237. 3FA2926056. 31AA2AFA51 A4 A110121021A35稱的特征值為設(shè),21nnnRA,max)(21nA的譜半徑為矩陣 A-(9)顯然顯然2A)(maxAAT)(AATReIm 36設(shè)設(shè)A為為n階方陣階方陣,則對任意算子范數(shù)則對任意算子范數(shù) | | 有有(A) | A |證明：證明：由算子范數(shù)的相容性，得到由算子范數(shù)的相容性，

20、得到| | |AxAx將任意一個(gè)特征根將任意一個(gè)特征根 所對應(yīng)的特征向量所對應(yīng)的特征向量 代入代入u| | |AuAu| | | |uu.即即 A A . . 故故( (A A) ) A A 定理定理3 3任何一種算子范數(shù)的譜半徑不超過矩陣的即矩陣A37若若A對稱，則有對稱，則有)(|2AA 證明：證明：)()(|2maxmax2AAAAT 若若 是是 A 的一個(gè)特征根，則的一個(gè)特征根，則 2 必是必是 A2 的特征根。的特征根。又對稱矩陣的特征根為實(shí)數(shù)，即又對稱矩陣的特征根為實(shí)數(shù)，即 2(A) 為非負(fù)實(shí)數(shù)，為非負(fù)實(shí)數(shù)，故得證。故得證。)()(22maxAA 對某個(gè)對某個(gè) A 的特征根的特征根

21、 成立成立定理定理4 438定理定理.,nnnnRAR上的一種算子范數(shù)是設(shè)且非奇異則滿足若, 1AIAAAAI11)(1證明證明:略略39 現(xiàn)現(xiàn) 實(shí)實(shí) 世世 界界 研 究研 究對 象對 象測 量測 量數(shù) 據(jù)數(shù) 據(jù)建立數(shù)學(xué)模型建立數(shù)學(xué)模型構(gòu)成數(shù)值算法構(gòu)成數(shù)值算法數(shù)值運(yùn)算的執(zhí)行數(shù)值運(yùn)算的執(zhí)行測 量測 量誤 差誤 差模型誤差模型誤差方法誤差方法誤差舍入誤差舍入誤差1. 3. 1. 3. 誤差的種類及來源誤差的種類及來源40總體設(shè)計(jì)總體設(shè)計(jì)( (含數(shù)學(xué)模型的建立與模型細(xì)化等含數(shù)學(xué)模型的建立與模型細(xì)化等) )詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)( (主要是算法設(shè)計(jì)主要是算法設(shè)計(jì)),),包括：包括： (1) (1) 連續(xù)系統(tǒng)

22、的離散化連續(xù)系統(tǒng)的離散化; ; (2) (2) 離散型方程的數(shù)值求解離散型方程的數(shù)值求解. .實(shí)驗(yàn)驗(yàn)證實(shí)驗(yàn)驗(yàn)證以計(jì)算機(jī)為工具解決實(shí)際問題需經(jīng)歷三個(gè)過程：以計(jì)算機(jī)為工具解決實(shí)際問題需經(jīng)歷三個(gè)過程：41(1) 模型誤差模型誤差 在建立數(shù)學(xué)模型過程中在建立數(shù)學(xué)模型過程中, 要將復(fù)雜的現(xiàn)象抽象要將復(fù)雜的現(xiàn)象抽象歸結(jié)為數(shù)學(xué)模型歸結(jié)為數(shù)學(xué)模型, 往往要忽略一些次要因素的影往往要忽略一些次要因素的影響響, 而對問題作一些簡化而對問題作一些簡化, 因此和實(shí)際問題有一因此和實(shí)際問題有一定的區(qū)別。定的區(qū)別。(2) 觀測誤差觀測誤差 在建模和具體運(yùn)算過程中所用的數(shù)據(jù)往往是在建模和具體運(yùn)算過程中所用的數(shù)據(jù)往往是通過觀

23、察和測量得到的通過觀察和測量得到的, 由于精度的限制由于精度的限制, 這這些數(shù)據(jù)一般是近似的些數(shù)據(jù)一般是近似的, 即有誤差。即有誤差。42(3) 截?cái)嗾`差截?cái)嗾`差 由于計(jì)算機(jī)只能完成有限次算術(shù)運(yùn)算和邏輯運(yùn)由于計(jì)算機(jī)只能完成有限次算術(shù)運(yùn)算和邏輯運(yùn)算算,因此要將有些需用極限或無窮過程進(jìn)行的運(yùn)算因此要將有些需用極限或無窮過程進(jìn)行的運(yùn)算有限化有限化,對無窮過程進(jìn)行截?cái)鄬o窮過程進(jìn)行截?cái)?這就帶來誤差。這就帶來誤差。(4) 舍入誤差舍入誤差 在數(shù)值計(jì)算過程中還會遇到無窮小數(shù)在數(shù)值計(jì)算過程中還會遇到無窮小數(shù), ,因計(jì)算機(jī)因計(jì)算機(jī)受到機(jī)器字長的限制受到機(jī)器字長的限制, ,它所能表示的數(shù)據(jù)只能有一它所能表示的

24、數(shù)據(jù)只能有一定的有限位數(shù)定的有限位數(shù), ,如按四舍五入規(guī)則取有限位數(shù)如按四舍五入規(guī)則取有限位數(shù), ,由由此引起的誤差。此引起的誤差。43! 3! 2132xxxex! 7! 5! 3sin753xxxxx! 4! 3! 2)1ln(432xxxxx如如:若將前若干項(xiàng)的部分和作為函數(shù)值的近似公式若將前若干項(xiàng)的部分和作為函數(shù)值的近似公式, ,由于以后各項(xiàng)都舍棄了由于以后各項(xiàng)都舍棄了, ,自然產(chǎn)生了誤差。自然產(chǎn)生了誤差。TaylorTaylor展開展開 截?cái)嗾`差截?cái)嗾`差4414159265.3414213562. 12 166666666. 061! 311415927. 34142136. 12

25、16666667. 0! 31 數(shù)學(xué)模型一旦建立數(shù)學(xué)模型一旦建立, ,進(jìn)入具體計(jì)算時(shí)所考慮和進(jìn)入具體計(jì)算時(shí)所考慮和分析的就是分析的就是截?cái)嗾`差和舍入誤差截?cái)嗾`差和舍入誤差. . 舍入誤差舍入誤差45u 絕對誤差絕對誤差* ex x其中其中 x*為精確值，為精確值，x為為x*的近似值。的近似值。 10006074302.dxex例如：例如：*xx工程上常記為工程上常記為|*e*的上限記為的上限記為 , , 稱為稱為絕對誤差限絕對誤差限。 u 相對誤差相對誤差*reex*|rxx 的的相對誤差上限相對誤差上限 定義為定義為2. 2. 誤差與有效數(shù)字誤差與有效數(shù)字46u 有效數(shù)字有效數(shù)字12010m

26、nx.a aa 01 ananm 10用科學(xué)計(jì)數(shù)法，記用科學(xué)計(jì)數(shù)法，記其中其中nm.xx 1050|*x若若則稱則稱有有n 位有效數(shù)字，精確到位有效數(shù)字，精確到 。，的截取按四舍五入規(guī)則的截取按四舍五入規(guī)則47例例4解解: :*| |0.000 00182ee 002000. 06102|*er28718. 2102628718. 2102661071. 02.718 28182,e *2.718 28,e *e已知近似值為已知近似值為: :精確值為精確值為: :求求 的絕對誤差、相對誤差的絕對誤差、相對誤差絕對誤差絕對誤差相對誤差相對誤差*|re 或或4810 3141510 *.,證明：證

27、明：3.1415926535897932; 例例5問：問： 有幾位有效數(shù)字？請證明你的結(jié)論。有幾位有效數(shù)字？請證明你的結(jié)論。* *3.1415 31 4*0.0000926. 0.0005 0.5*1005 10 |.有有4 位有效數(shù)字，位有效數(shù)字，*精確到小數(shù)點(diǎn)后第精確到小數(shù)點(diǎn)后第 3 位。位。49數(shù)值算法數(shù)值算法是是從給定的已知量出發(fā)，經(jīng)過有限次四則運(yùn)算從給定的已知量出發(fā)，經(jīng)過有限次四則運(yùn)算及規(guī)定的運(yùn)算順序，最后求出未知量的數(shù)值解，這樣構(gòu)成及規(guī)定的運(yùn)算順序，最后求出未知量的數(shù)值解，這樣構(gòu)成的完整計(jì)算步驟稱為算法。的完整計(jì)算步驟稱為算法。數(shù)值算法有四個(gè)特點(diǎn)數(shù)值算法有四個(gè)特點(diǎn): :(1)(1)

28、目的明確目的明確算法必須有明確的目的算法必須有明確的目的, ,其條件其條件和結(jié)論均應(yīng)有清楚的規(guī)定和結(jié)論均應(yīng)有清楚的規(guī)定(2)(2)定義精確定義精確對算法的每一步都必須有精確的定義對算法的每一步都必須有精確的定義(3)(3)算法可執(zhí)行算法可執(zhí)行算法中的每一步操作都是可執(zhí)行的算法中的每一步操作都是可執(zhí)行的(4)(4)步驟有限步驟有限算法必須在有限步內(nèi)能夠完成解題算法必須在有限步內(nèi)能夠完成解題過程過程1.4 1.4 題型分析與小結(jié)題型分析與小結(jié) - - 算法和計(jì)算量算法和計(jì)算量50計(jì)算量：計(jì)算量：一個(gè)算法所需的乘除運(yùn)算總次數(shù)，單位是一個(gè)算法所需的乘除運(yùn)算總次數(shù)，單位是flop. 計(jì)算量是衡量算法好壞

29、的一個(gè)重要標(biāo)準(zhǔn)。計(jì)算量是衡量算法好壞的一個(gè)重要標(biāo)準(zhǔn)。例例1 求求 Ax=b， Det(A)0，A=(aij)20 20的計(jì)算量。的計(jì)算量。結(jié)論：結(jié)論：分析算法的效率，選擇算法非常重要。分析算法的效率，選擇算法非常重要。解解：2. 使用使用Gauss消去法，消去法， n=20， N3060次次= O(n3 /3)次次.解：解：1. 用用Cramar法則求解，總的計(jì)算量法則求解，總的計(jì)算量 N = ( ( n+1)(n-1)n!+n) 次次 當(dāng)當(dāng)n=20, N9.7 1020 次次. 以一臺以一臺10億億/秒的計(jì)算機(jī)需約秒的計(jì)算機(jī)需約3萬年萬年.511210( )( ( () nnnnP xx x

30、 xx a xaaaa101,2,1,0( )nnkkknsasxsaknP xs1110( )nnnnnP xa xaxa xa例例2 計(jì)算計(jì)算n 次多項(xiàng)式次多項(xiàng)式 的值。的值。 算法算法: 采用采用秦九韶算法秦九韶算法(1247) (又稱為又稱為Horner算法算法(1819)計(jì)算計(jì)算 說明：說明：算法需乘法算法需乘法n次，加法次，加法n次，存儲單元次，存儲單元n+3個(gè)。個(gè)。52上述秦九韶算法的結(jié)構(gòu)是遞歸的，它通過一次式上述秦九韶算法的結(jié)構(gòu)是遞歸的，它通過一次式的反復(fù)計(jì)算，逐步降低多項(xiàng)式的次數(shù)，直到歸結(jié)為零次式為止的反復(fù)計(jì)算，逐步降低多項(xiàng)式的次數(shù)，直到歸結(jié)為零次式為止。若以多項(xiàng)式的次數(shù)（或

31、項(xiàng)數(shù)）定義為求值問題的規(guī)模，若以多項(xiàng)式的次數(shù)（或項(xiàng)數(shù)）定義為求值問題的規(guī)模，秦九韶算法的特點(diǎn)秦九韶算法的特點(diǎn): : 在遞歸計(jì)算的過程中問題的規(guī)模逐次減在遞歸計(jì)算的過程中問題的規(guī)模逐次減1。1kkksxsa53算法算法程序程序QinJiushao.m1.1.輸入多項(xiàng)式系數(shù)輸入多項(xiàng)式系數(shù)function s=QinJiushao(a,x) n=length(a); s=a(1); for k=2:n s=s*x+a(k); end實(shí)例實(shí)例運(yùn)行及結(jié)果運(yùn)行及結(jié)果求多項(xiàng)式求多項(xiàng)式 a=1 -3 0 4 -1 1; s=QinJiushao(a,3)s = 3401,na aa542( )341p xxx

32、xx 在在 時(shí)的值時(shí)的值. 3x 及 ;x2.2.迭代計(jì)算迭代計(jì)算101,2,1,0( )nnkkknsasxsaknP xs 3.3.輸出結(jié)果輸出結(jié)果注注: 編寫程序時(shí)多項(xiàng)式系數(shù)按降冪排列編寫程序時(shí)多項(xiàng)式系數(shù)按降冪排列.54 例例3 計(jì)算計(jì)算x255的復(fù)雜度的復(fù)雜度 1. 計(jì)算計(jì)算 X255 = X X X X X 工作量：工作量：N254 flop 254個(gè)個(gè)乘法乘法2. 計(jì)算計(jì)算 X255 = X X2 X4 X8 X16 X32 X64 X128 工作量：工作量：N14 flop ，8個(gè)儲存空間個(gè)儲存空間 55604751413112134131216113121 321321321x

33、xxxxxxxx78. 020. 025. 033. 01 . 1 25. 033. 0.5008 . 133. 0.500 321321321xxxxxxxxx例例1 求解線性方程組解求解線性方程組解: :則其解為則其解為x1=-6.222, x2=38.25 , x3=-33.65, 可見這是一個(gè)可見這是一個(gè)病態(tài)問題病態(tài)問題(初始初始數(shù)據(jù)的的微小變化數(shù)據(jù)的的微小變化(擾動擾動)，導(dǎo)，導(dǎo)致計(jì)算結(jié)果的相對誤差很大致計(jì)算結(jié)果的相對誤差很大)與解法無關(guān)與解法無關(guān).二二. .求解線性方程組求解線性方程組方程組的準(zhǔn)確解為方程組的準(zhǔn)確解為 x1=x2=x3=1若把方程組的系數(shù)舍入為兩位有效數(shù)字若把方程組

34、的系數(shù)舍入為兩位有效數(shù)字,變?yōu)樽優(yōu)?6解解: x x1 1=10=109 9, , x x2 2=1=1.算法算法A: xA: x1,21,2= (- b= (- b sqrt (b sqrt (b2 2- 4ac)/ 2a,- 4ac)/ 2a,出現(xiàn)小誤差時(shí)有出現(xiàn)小誤差時(shí)有, , - b = 10- b = 109 9+1 = 0.10000000+1 = 0.10000000101010 10 + 0.000000001+ 0.00000000110101010 = 0.10000000= 0.1000000010101010 而而 b b2 2- 4ac b- 4ac b2 2 , ,

35、sqrt (bsqrt (b2 2- 4ac) - 4ac) b b 于是于是 x x1 1= (- b+= (- b+|b|)/2 = |b|)/2 = 0.10000000 0.10000000 10101010, , x x2 2= (- b-= (- b-|b|)/2 = |b|)/2 = 0 0算法算法B: x x1 1 = ( - b= ( - b- sign(b)- sign(b) sqrt(sqrt(b b2 2- 4ac)/ 2a- 4ac)/ 2a x x2 2 = c/ax= c/ax1 1則則 x x1 1 = 0.10000000= 0.10000000101010

36、10 =10=109 9 x x2 2 = 0.10000000= 0.1000000010101 1 = 1= 1 算法算法A A不穩(wěn)定不穩(wěn)定; ;算法算法B穩(wěn)定穩(wěn)定, ,算法算法B準(zhǔn)確準(zhǔn)確.結(jié)論結(jié)論:良態(tài)問題選擇穩(wěn)定算法良態(tài)問題選擇穩(wěn)定算法,才能得到滿意解才能得到滿意解大數(shù)大數(shù)”吃掉吃掉”小數(shù)小數(shù) 例例2: 2: 求解求解 x2 +(-10 x2 +(-109 9-1) x + 10-1) x + 109 9=0=057例例3.,28718. 2,82281718. 2*reee和相對誤差限的絕對誤差限求其近似值為已知解:eeE*絕對誤差82001000. 082001000. 0|E002000. 061026102|*er28718. 2102628718. 2102661071. 0是唯一的并不和*r58例例4 4.,7 ,5 ,3求絕對誤差限位數(shù)的近似值經(jīng)四舍五入取小數(shù)點(diǎn)后若解:65592141. 359141. 3*142. 3*7592141. 3*|*407000. 065002000. 004000000. 03105 . 05105 . 07105 . 0可見,經(jīng)四舍五入取近似值,其絕對誤差限將不超過其末位數(shù)字的半個(gè)單位59例例5 5：為使：為使 的相對誤差小于的相對誤差小于0.001%, ,至少應(yīng)取幾位有效數(shù)字？至少應(yīng)取幾位有效數(shù)字？*解：假設(shè)解：假