數(shù)值分析慶課件群共享第一章

1、Introduction to Numerical AnalysisChapter 1: Introduction慶本人所有2015 年 9 月 7 日慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日1 / 65及作業(yè)：數(shù)值分析（第三版），2012年3月印刷（有部分修訂）。參考書(shū)：數(shù)值分析全真試題（2007-2012）。無(wú)責(zé)任: 在校本部上課的學(xué)生，可讓他們?nèi)バ６Y堂東樓北20米的書(shū)庫(kù)去買(mǎi)書(shū)；九龍湖上課的學(xué)生還請(qǐng)您讓班長(zhǎng)統(tǒng)計(jì)一下人數(shù)然后和我，我直接送過(guò)去。書(shū)售價(jià)定為：?jiǎn)钨I(mǎi)數(shù)值分析，35元（80折）；單買(mǎi)數(shù)值分析全真試題

2、解析，25元（74 折）；數(shù)值分析+數(shù)值分析全真試題解析，55元（71折）。比重：期末80，課堂作業(yè)10，上機(jī)作業(yè)10（至少交5次，程序+數(shù)值結(jié)果+心得+紙質(zhì)版）。信箱：liyq.慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日2 / 65Q1：什么是數(shù)值分析？（1）傳統(tǒng)稱(chēng)謂：數(shù)值分析（Numerical Analysis）；最新叫法：科學(xué)計(jì)算（Scientific Computing）；主要目的：很多領(lǐng)域（尤其是科學(xué)研究和工程領(lǐng)域）中所提出的數(shù)學(xué)問(wèn)題進(jìn)行數(shù)值算法的設(shè)計(jì)與分析。：Modern scientific c

3、omputing using electronic computershas its origin in research and developments during the secondworld war （20世紀(jì)40年代末50年代初，數(shù)值分析作為的數(shù)學(xué)分現(xiàn)，這是現(xiàn)代科學(xué)計(jì)算的真正）。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日3 / 65Q1：什么是數(shù)值分析？（2）功用：The new capabilities（能力）of performing millions of operations led to

4、 new classes of algorithms, which needed a careful analysis to ensure their accuracy and stability（計(jì)算能力的提高-¿問(wèn)題規(guī)模的擴(kuò)大-¿新的算法-¿必須分析這些算法的 精確性和穩(wěn)定性）。：As a rule, applications lead to mathematical problemswhich in their complete form cannot be conveniently solved with exact formulas, unless on

5、e restricts oneself to specialcases or simplified ms.（實(shí)際應(yīng)用導(dǎo)出了很多的數(shù)學(xué)問(wèn)題，通常而言，這些問(wèn)題很難找到一個(gè)確定的公式解，除非把問(wèn)題做很多的限制或者簡(jiǎn)化模型）！慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日4 / 65Q1：什么是數(shù)值分析？（3）策略：In many cases, one thereby reduces the problem to a linear problemfor example, a linear system of differ

6、ential equations. Such an approach can quite often lead to concepts andpoints of view which, at least qualitatively, can be used even in the unreduced problems.先將復(fù)雜問(wèn)題簡(jiǎn)單化，構(gòu)造相應(yīng)的數(shù)值算法，再應(yīng)用在一般問(wèn)題上（需要一定程度的變化），對(duì)很多問(wèn)題來(lái)說(shuō)，都是一條值得嘗試的解決方案。地位：計(jì)算機(jī)硬件的發(fā)展（速度更快、了數(shù)值方法的應(yīng)用范圍，但這不是全部更大）大大的刺激。Gains in problemsolving capabiliti

7、es through better mathematical algorithmshave in many cases played an equally important role!慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日5 / 65Q1：什么是數(shù)值分析？（4）現(xiàn)狀：Today one can treat much more complex and less simplified problems through massive amounts of numericalcalculations. Adva

8、nced mathematical ms and methods arenow used more and more also in areas like medicine, economics and social sciences. It is fair to say that today experiment and theory, the two classical elements of scientific method, in many fields of science and engineering are supplemented bycomputations as an

9、equally important component. （數(shù)值模擬已經(jīng)同實(shí)驗(yàn)、理論研究一起成為科學(xué)研究的三大）。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日6 / 65Q1：什么是數(shù)值分析？（5）數(shù)值分析具有的主要特點(diǎn)：特點(diǎn)1：同一般計(jì)算機(jī)科學(xué)不同，它處理的是連續(xù)量。特點(diǎn)2：同一般的論科學(xué)不同，它強(qiáng)調(diào)近似效果。通常而言，數(shù)值算法和數(shù)值計(jì)算本身都是近似的，因此數(shù)值計(jì)算的基本要求就是：準(zhǔn)確(Accurate) 、快速(Fast)、可靠(Reliable)。換句話說(shuō)：這是一座橋梁？慶 (本人所有)Introducti

10、on to Numerical Analysis Chapte2015 年 9 月 7 日7 / 65Q2：為什么我們需要科學(xué)計(jì)算？理由1：很多連續(xù)的數(shù)學(xué)問(wèn)題沒(méi)有辦法精確求解。例如：Z1ex2 dx0無(wú)法精確計(jì)算，但它非常重要，同概率中的正態(tài)分布有關(guān)。理由2：理論求解往往通過(guò)一個(gè)無(wú)限的過(guò)程來(lái)完成，因此理論 解可能不具有實(shí)際操作性！例如：分析迭代序列xk+1 = (xk )極限是否存在時(shí)，我們通常會(huì)取極限。理由3：隨著科技的發(fā)展，問(wèn)題的規(guī)模越來(lái)越大，理論求解往往 為力，通常會(huì)借助計(jì)算機(jī)完成某些研究。此時(shí)，The errorcan not be avoided?。ㄓ涀∵@句話？）理由n：慶 (本人所

11、有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日8 / 65計(jì)算模擬計(jì)算模擬就是利用計(jì)算機(jī)來(lái)實(shí)現(xiàn)或者模擬或過(guò)程?；竟ぞ撸篶omputer?。私庥?jì)算機(jī)如何“想”是一個(gè)前提？）研究的傳統(tǒng)方法：理論研究，觀察，實(shí)驗(yàn)等。Q3：現(xiàn)在，我們?yōu)槭裁葱枰?jì)算模擬？傳統(tǒng)方法可能很難或者不可能完成研究，如兩個(gè)黑洞的碰撞。1數(shù)值模擬能夠比傳統(tǒng)方法更快、更、更安全的解決“常規(guī)問(wèn)2題”，比如在計(jì)算機(jī)上進(jìn)行汽車(chē)的碰撞實(shí)驗(yàn)要比實(shí)際碰撞要更便宜、更安全，也更容易得到精確的設(shè)計(jì)參數(shù)。3慶 (本人所有)Introduction to Numerical Ana

12、lysis Chapte2015 年 9 月 7 日9 / 65Q4：如何進(jìn)行計(jì)算模擬？數(shù)學(xué)建模（非常關(guān)鍵的一步）；設(shè)計(jì)數(shù)值算法（我們課程主要關(guān)注的部分）；實(shí)現(xiàn)算法（一個(gè)“好”的實(shí)現(xiàn)更重要，什么是好？）；實(shí)際模擬；表示結(jié)果；解釋并確認(rèn)計(jì)算結(jié)果，如果需要，重復(fù)某些或者全部步驟!123456慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日10 / 65Q5：以上步驟具有什么樣的關(guān)系？Each aspect affects and is affected by the others！特別是第一步：數(shù)學(xué)建模！物理規(guī)律通常有其

13、適用的范圍，超出這個(gè)范圍，物理規(guī)律就會(huì) 發(fā)生變化，進(jìn)而物理模型也會(huì)隨之發(fā)生變化。正確的理解問(wèn)題，然后再去建模（建模需要簡(jiǎn)化，但不能想當(dāng)然？）。物理問(wèn)題到數(shù)學(xué)模型需要簡(jiǎn)化，簡(jiǎn)化的原則是什么？（問(wèn)題的主要部分，“站位”要正確？）?？偠灾?，the problems affect the computational process.只有正確理解問(wèn)題，正確的描述問(wèn)題，才能構(gòu)建合理的算法！7慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日11 / 65Q6：拿到一個(gè)問(wèn)題，“好”問(wèn)題還是“壞問(wèn)題？一個(gè)“好”問(wèn)題（well-pos

14、ed ）的要求：解存在、唯一、并連續(xù)依賴(lài)于數(shù)據(jù)。（傳統(tǒng)意義？）Q7：什么是連續(xù)依賴(lài)性？粗略地，輸入數(shù)據(jù)的輕微擾動(dòng)沒(méi)有引起輸出的大幅度變化。一個(gè)“壞”（ ill-posed）問(wèn)題則不具備上述性質(zhì)。特別注意：一個(gè)“壞”問(wèn)題是不能奢望通過(guò)算法改變其內(nèi)在性質(zhì)的！只能通過(guò)轉(zhuǎn)化，將 ill-posed 問(wèn)題轉(zhuǎn)化成 well-posed 問(wèn)題再解決（出身很重要。？）。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日12 / 65ffffff ”好壞”問(wèn)題舉ff 例微分是非常敏感的，數(shù)據(jù)的微小擾動(dòng)會(huì)使結(jié)果產(chǎn)生很大變化。ffff是一個(gè)

15、相對(duì)平滑的過(guò)程，具有很強(qiáng)的穩(wěn)定性！對(duì)比圖：Two functions whose integrals equal but derivatives notffff. . . . . . . . . . . . . . . . . . . . . . . . . . 2015 年 9 月 7 日13 / 65 ff慶 (本人所有)Introduction to Numerical Analysis ChapteQ8：我們對(duì)數(shù)值算法的期望是什么？基本期望：accurate（精確）; quick（快速）; robust（穩(wěn)?。?the programming is not too hard（實(shí)現(xiàn)不太復(fù)

16、雜）; transplantable（可移植性）.12345這些要求，是設(shè)計(jì)算法時(shí)必須關(guān)注的內(nèi)容，除此之外：It is natural to look forward to those discrete systems which preserve as much as possible intrinsic properties of the continuous system.By K. Feng (1985)慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日14 / 65Q9：計(jì)算模擬中的基本策略是什么？詞匯：Re

17、placing！具體則是：無(wú)限-有限1無(wú)限的過(guò)程-有限的過(guò)程微分方程-代數(shù)方程非線性問(wèn)題-線性問(wèn)題高維問(wèn)題-低維問(wèn)題復(fù)雜函數(shù)-簡(jiǎn)單函數(shù)一般矩陣問(wèn)題-特殊矩陣問(wèn)題2345678總而言之，“解決不了的”變成“能解決的”？慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日15 / 65Q10：如何使用這些基本策略呢？例如：非線性微分方程 非線性代數(shù)方程 線性代數(shù)方程 特殊形式的線性系統(tǒng)。（不唯一？）基本原則：Solutions unchanged, or at least within some required toler

18、ance of the true solution.You need:An alternative problem, or class of problems, that is easier solve.A transformation of the given problem into a problem of thisalternative type that preserves the solution in some sense.1to2具體問(wèn)題具體分析！慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日16

19、/ 65Q11：誤差的來(lái)源有哪些呢？（1）Before a computation begins:Ming.1Empirical measurements.Previous computations.23During computation:Truncation or discretization.（截?cái)嗾`差） Rounding（舍入誤差）.12一個(gè)故事：The first American Venus probe was lost due to a program fault caused by the inadvertent substitution of a statement in a

20、 Fortran program of the form DO 3 I = 1.3 for one of the form DO 3 I = 1,3. The erroneous replaced comma“,”with adot“.”converts the intended loop statement into an assignment statement!（循環(huán)變成了賦值!） 慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日17 / 65Q11：誤差的來(lái)源有哪些呢？(2)最終誤差：combination

21、all or part of them.誤差可能會(huì)被放大，可能源自于問(wèn)題本身，也可能是算法的問(wèn)題。必須做簡(jiǎn)單的誤差分析，了解誤差的大致。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日18 / 65Q12：如何衡量誤差的大??？誤差的意義與其度量或者計(jì)算的量的大小有關(guān)系！比如人口普查時(shí)的誤差 1 的意義要遠(yuǎn)遠(yuǎn)小于一個(gè)房間里人數(shù)的誤差 1 的意義（點(diǎn)名？）。設(shè) x 是的某個(gè)近似值，則：x 絕對(duì)誤差 Absolute error e = x x（真實(shí)值減去近似值）.相對(duì)誤差 Relative error er = e .x

22、 誤差可正可負(fù)。真實(shí)值通常是未知的，這時(shí)候我們需要考慮誤差限。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日19 / 65Q13：什么是誤差界（限）？如果 |e| ，則 稱(chēng)為絕對(duì)誤差 e 的一個(gè)絕對(duì)誤差限。找到其誤差限或者估計(jì)其大小比精確計(jì)算更有意義。同樣有相對(duì)誤差限：|er | r .需要指出的是，我們總是期望誤差限越小越好，但這通常很難做到?；旧纤械恼`差估計(jì)都是“悲觀”估計(jì)。e通常會(huì)用 e = e ，這是“合理（都有前提？）”的：¯rrxx x(x x )2e2x xre¯r er =x

23、x = 1 erxx 慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日20 / 65Q14：Precision 和 Accuracy 有什么區(qū)別？在進(jìn)一步討論誤差之前，先區(qū)分這兩個(gè)概念：精度（Precision）與所表示的數(shù)的數(shù)字個(gè)數(shù)有關(guān)。準(zhǔn)確度（精確度）（Accuracy）與近似某個(gè)量時(shí)的有效數(shù)字的個(gè)數(shù)有關(guān)，同相對(duì)誤差有關(guān)！例如：3.25603764689720 是一個(gè)精度很高的數(shù)字，但是將其作為 的近似值，顯然是很確的。精度更可以看做是系統(tǒng)提供的，如計(jì)算機(jī)里的單、雙精度。當(dāng)用給定的精度去計(jì)算一個(gè)量時(shí)，絕對(duì)不能說(shuō)明

24、結(jié)果可以達(dá)到那個(gè)精確度！慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日21 / 65Q15：什么是有效數(shù)字（significant digits）？significant digits（源自Wiki）：Those digits that carry meaning contributing to its accuracy, this includes all digits except:leading and trailing zeros (unless a decimal point is present) wh

25、ere they serve merely as placeholders to indicate the scale of the number;spurious digits introduced, for example, by calculations carried outto greater accuracy than that of the original data, or measurements reported to a greater precision than the equipment supports.12因此，在分析有效數(shù)字之前，必須要明了其來(lái)源。關(guān)于有效數(shù)字

26、，有更為詳細(xì)的定義方式，隨后介紹。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日22 / 65Q16：數(shù)據(jù)誤差和計(jì)算誤差有何不同？有些誤差是由初始數(shù)據(jù)（測(cè)量、預(yù)處理等）引起的，有些誤差是在隨后的計(jì)算過(guò)程（截?cái)?、舍入）中引入的。一般情況下，我們暫不分析舍入誤差（見(jiàn)第三節(jié)）。以計(jì)算函數(shù)值 f (x ),f : R R 為例：如果 x x,f f ，那么：f (x ) f (x ) = f (x ) f (x ) + f (x ) f (x ).f (x ) f (x ) 稱(chēng)為計(jì)算誤差（computational err

27、or）。f (x ) f (x ) 稱(chēng)為遺傳誤差（propagated error）。要減少誤差，必須從這兩方面入手，減少兩部分誤差。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日23 / 65Q17：計(jì)算誤差主要指什么？分析計(jì)算誤差時(shí)主要考慮截?cái)嗾`差（Truncation error）：真實(shí)結(jié)果與給定算法經(jīng)精確計(jì)算得到的結(jié)果之間的差。一般由無(wú)窮級(jí)數(shù)的截?cái)?、有限差分代替?dǎo)數(shù)、迭代收斂序列終 止迭代等產(chǎn)生！例 6 ：有限差分格式：f 0(x ) f (x + h) f (x ) .h根據(jù)Taylor展開(kāi)：f (x +

28、 h) = f (x ) + f 0(x )h + f 00( )h2/2.截?cái)嗾`差界為：Mh/2，其中 M 是導(dǎo)數(shù)在 x附近的界。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日24 / 65Q18：如何分析誤差？首先強(qiáng)調(diào)一點(diǎn)：如果輸入數(shù)據(jù)只精確到4位有效數(shù)字，那么無(wú) 論隨后的計(jì)算多么精確，結(jié)果的有效數(shù)字也超過(guò)4位！ 所謂的“廢料進(jìn)，廢料出”（Garbage In，Garbage Out）！以計(jì)算函數(shù)值 f (x ) 為例，實(shí)際計(jì)算中得到 y，則：y = y y 稱(chēng)為向前誤差 forward error；1如果 f

29、 (x) = y，則 x = x x 稱(chēng)為誤差 backward error。2一般來(lái)說(shuō)，誤差是一個(gè)更為有用的工具。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日25 / 65向前誤差誤差圖示fx . .f (x).|forward error.f.backward error.|.|.f. .xf (x) = f (x). 慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日26 / 65 Q19：如何圖示向前誤差誤差？Q20：什么是浮點(diǎn)數(shù)

30、？例如：2347 和 0.0007396 可以寫(xiě)成 2.347 × 103, 7.396 × 104等。這種格式下，小數(shù)點(diǎn)隨著通常來(lái)說(shuō)，一個(gè)浮點(diǎn)10 的冪次的變化而移動(dòng)或浮動(dòng)。具有如下的幾個(gè)量： Base or radix;p Precision;L, U Exponent range.123ddp11Ex =(d + · · · +) , 0 d 1, E integer±0ip1L E U.括號(hào)中的部分用 進(jìn)制數(shù)值 d0d1 · · · dp1 表示，稱(chēng)為尾數(shù)或則稱(chēng)為指數(shù)。者有效數(shù)字（?。?，E慶 (本

31、人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日27 / 65Q21：何謂標(biāo)準(zhǔn)化（Normalization）？通常取 = 2。Normalization：d0 非 0，除非表示的數(shù)字為 0。優(yōu)點(diǎn)：The representation of each number is then unique. No digits are wasted on leading zeros, thereby precision.izingThe leading bit is always 1 and thus need not be store

32、d.基于以上優(yōu)點(diǎn)，一般的浮點(diǎn)系統(tǒng)都是要正規(guī)化的。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日28 / 65能精確表示的浮點(diǎn)數(shù)的總個(gè)數(shù)為：2( 1)p1(U L + 1) + 1.浮點(diǎn)是一個(gè)有限離散系統(tǒng)。上溢 overflow: OFL = U+1(1 p)，最大數(shù)。下溢 underflow: UFL = L，最小正數(shù)。在浮點(diǎn)數(shù)范圍內(nèi)，浮點(diǎn)數(shù)并不均勻分布，但在 的相同冪次間均勻分布。如圖：.Floating system 舉例. . . . . . . . .432101234ff慶 (本人所有)Introduct

33、ion to Numerical Analysis Chapte2015 年 9 月 7 日29 / 65Q22：浮點(diǎn)具有什么樣的性質(zhì)呢？Q23：舍入誤差是怎么來(lái)的？數(shù)指的是能被浮點(diǎn)系統(tǒng)準(zhǔn)確表示的數(shù)，只有有限個(gè)！x 不是數(shù)，由其附近的某個(gè)浮點(diǎn)數(shù)近似表示，為 fl(x )。Q24：近似規(guī)則有哪些呢？截?cái)啵╟hop）：將 x 的 基底展開(kāi)的第 p 1 位以后的又稱(chēng)round toward zero。四舍五入法（Round to nearest）：fl(x ) is the nearest floating-point number to x ;In case of a tie, we use th

34、e floating-point number whose last stored digit is even, round to even.，慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日30 / 65Q25：有效數(shù)字能否有其他的定義方式？標(biāo)準(zhǔn)化浮點(diǎn)中，尾數(shù)又稱(chēng)為有效數(shù)字。注意末尾的0!一個(gè)經(jīng)常的問(wèn)題：x 是的近似值，x 具有幾位精度？x 有效數(shù)字的其他定義：如果近似值x的絕對(duì)誤差限是其某一位的半個(gè)，且該位直到x的第一位非零數(shù)字之間共有n位，則稱(chēng)x具有n位有效數(shù)字, 用這n位有效數(shù)字表示的近似數(shù)稱(chēng)為有效數(shù)。慶 (

35、本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日31 / 65關(guān)于有效數(shù)字的進(jìn)一步的例子（1）例：如 的近似值取 x1 = 3.14，則：| 3.14| = 0.0012926 · · · < 1/2 × 102 = 0.005所以如取x1 有 3 位有效數(shù)字！x2 = 3.1416，則14| x | < 000005 =× 10 ,.22所以如取x2 有 5 位有效數(shù)字;x3 = 3.1415，則13 x | = 000009 · · &#

36、183;< 00005 =× 10 ,|.32所以x3 只有 4 位有效數(shù)字.慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日32 / 65關(guān)于有效數(shù)字的進(jìn)一步的例子（2）例：x = 0.045113, x = 0.04518，問(wèn)具有幾位有效數(shù)字？方法：x 0.5 × 104 < |x x | = 0.000067 < 0.5 × 103,因此具有 2 位有效數(shù)字 -0.045。慶 (本人所有)Introduction to Numerical Analysis Cha

37、pte2015 年 9 月 7 日33 / 65Q26：什么是precision）(1)？精度（Machine精度：滿足 fl(1 + ) > 1 最小的正 。精度說(shuō)明了一個(gè)非 0 實(shí)數(shù)最大可能的相對(duì)誤差，即：fl(x ) x .mach x這句話可理解為如果兩個(gè)數(shù)的相對(duì)誤差比計(jì)算機(jī)而言，它們是一個(gè)數(shù)。精度還小，則對(duì)精度還有其他定義，可能略微不同，但其根本都是對(duì)浮點(diǎn)顆粒性的度量。通常有關(guān)系式：0 < UFL < mach < OFL。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日34 / 6

38、5Q26：什么是precision）？(2)精度（Machine中的eps函數(shù):eps Spacing of floating point numbers. D = eps(X), is the positive distance from ABS(X) to the next larger in magnitude floating point number of the same precision as X. X may be either double precision or single precision. For all X, eps(X) is equal to eps(AB

39、S(X).eps, with no arguments, is the distance from 1.0 to the next largerdouble precision number, that is eps with no arguments returns 252.慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日35 / 65Q27：浮點(diǎn)運(yùn)算同普通的代數(shù)運(yùn)算和不同？+, , ×, ÷ 都不再精確！一些熟知的結(jié)理論不再成立，如加法的結(jié)合律不再成立！兩個(gè)浮點(diǎn)數(shù)的運(yùn)算也不一定產(chǎn)生另一個(gè)浮點(diǎn)數(shù)

40、！比如 + 法，先對(duì)指數(shù)，然后再操作尾數(shù)，有可能大數(shù)吃小數(shù)！浮點(diǎn)運(yùn)算都是 fl(x op y ) = (x op y )(1 + ) 的形式。浮點(diǎn)運(yùn)算是一個(gè)復(fù)雜的運(yùn)算過(guò)程，應(yīng)盡可能的主動(dòng)去避免一些糟糕情形的發(fā)生！慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日36 / 65Q28：如何分析數(shù)據(jù)誤差的影響？（1）設(shè) x1, x2 為準(zhǔn)確值，y = f (x1, x2)，x1, x2 為對(duì)應(yīng)的近似值，y = f (x1, x2)，分析二元函數(shù)的誤差：e(y )。Taylor 展開(kāi)得到：由二元函數(shù)e(y )= y y =

41、f (x1, x2) f (x1, x2)f (x , x )f (x , x )1 2x11 2(x x ) +(x x ),1212x2即是：f (x , x )f (x , x )1 2x11 2x2e(y ) e(x ) +e(x ).12慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日37 / 65Q28：如何分析數(shù)據(jù)誤差的影響？（2）相對(duì)誤差：f er (y ) = e(y )(x , x )x1 21e (x )r1x1f (x1, x2)yf (x1, x2)x2x2f (x1, x2) er (x2

42、).+利用上述兩個(gè)關(guān)系式，可以分析和差積商的關(guān)系式。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日38 / 65Q28：如何分析數(shù)據(jù)誤差的影響？（3）具體結(jié)果為：e(x1 + x2) = e(x1) + e(x2),e(x1 x2) = e(x1) e(x2),e(x1x2) x2e(x1) + x1e(x2), x 1x11ee(x ) e(x ),12x2x2x 22 x x12e (x + x ) e (x ) +e (x ),r12r1r2x1 + x2x1 + x2 x1x2er (x1 x2) er (

43、x1) er (x2),x1 x2x1 x2er (x1x2) er (x1) + er (x2), x1e e (x ) e (x ).rr1r2x2慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日39 / 65數(shù)據(jù)誤差分析舉例（1）例：設(shè) x1 = 2001，x2 = 1999，x1 = 44.7325，x2 = 44.7102，已知 x1, x2 分別是 x1, x2 的具有 6 位有效數(shù)字的近似值。計(jì)算 2001 1999，現(xiàn)有下面兩種算法：方法 1：1x1 x2 x1 x2 = 44.7325 44.710

44、2 = 0.0223.方法 2：x1 x2=2 2 2x1 + x2 244.7325 + 44.7102=x1 + x2= 0.0223606845 · · · .試分析上述兩種算法所得結(jié)果的有效數(shù)字。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日40 / 65數(shù)據(jù)誤差分析舉例（2）由條件得11|e(x1)| 2 × 104,|e(x2)| 2 × 104.|e(x1 x2)| = |e(x1) e(x2)| |e(x1)| + |e(x2)|1114443 2

45、× 10+ 2 × 10= 10< 2 × 10.因此方法 1 所得結(jié)果至少具有 2 位有效數(shù)字。輸入數(shù)據(jù)有 6 位有效數(shù)字，輸出結(jié)果只具有 2 位有效數(shù)字。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日41 / 65數(shù)據(jù)誤差分析舉例（3）22|e( x1 + x2 )| (x1 + x2)2 e(x1 + x2)|=2| (x1 + x2)2 e(x1) + e(x2)|2(x1 + x2)2 |e(x1)| + |e(x2)| 21144× 10 +× 1

46、0(44.7325 + 44.7102)22217725 × 10 <× 100.2按方法 2顯然方法得到的結(jié)果至少具有 6 位有效數(shù)字。2 優(yōu)于方法 1，為什么會(huì)如此？慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日42 / 65Q29：什么導(dǎo)致了不精確的解？一個(gè)不精確解的出現(xiàn)并不一定是源自一個(gè)不好的算法，也很有可能源自問(wèn)題本身！重述：?jiǎn)栴}條件性的概念：A problem is said to be insensitive, or well-conditioned, if a given

47、relative change in the input data causes a reasonably commensurate relative change in the solution. A problem is said to be sensitive, or ill-conditioned, if the relative change in the solution can be much larger than that in the input data.ill-conditioned 的問(wèn)題和不穩(wěn)定的數(shù)值算法都可能導(dǎo)致不精確解的出現(xiàn)。要避免不精確解，必須兩個(gè)方面都要考慮

48、。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日43 / 65Q30：如何去衡量一個(gè)問(wèn)題的好壞呢？工具：條件數(shù)（Condition number），誤差的放大因子！例如：對(duì)函數(shù)求值問(wèn)題 y = f (x )，Condition number = |(f (x ) f (x)/f (x )| = |y/y | .|(x x)/x |x/x |上述稱(chēng)為相對(duì)條件數(shù)，當(dāng) x = 0 or y = 0，用絕對(duì)條件數(shù)|y |。|x |條件數(shù)的具體表和計(jì)算方法因問(wèn)題而異。慶 (本人所有)Introduction to Numer

49、ical Analysis Chapte2015 年 9 月 7 日44 / 65Q31：能否舉一個(gè)簡(jiǎn)單的 ill-posed 的例子？尋找多項(xiàng)式的實(shí)根的數(shù)目就是一個(gè)壞問(wèn)題。比如多項(xiàng)式p(x ) = x 4 x 2(2a 1) + a(a 1),當(dāng) a 連續(xù)變化時(shí)，根的個(gè)數(shù)則是不連續(xù)變化的。具體結(jié)果是：4 a 1;2 0 a < 1;0 a < 0.number of real roots =慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日45 / 65Q31：什么是算法的穩(wěn)定性（Stability）？簡(jiǎn)

50、單地說(shuō)，算法穩(wěn)定性的概念同問(wèn)題的條件性概念是類(lèi)似的， 也與擾動(dòng)的影響有關(guān)。粗略地講，一個(gè)算法稱(chēng)為是 stable 的， 指的是它的結(jié)果對(duì)計(jì)算過(guò)程中所產(chǎn)生的近似擾動(dòng)相對(duì)不敏感。對(duì)于某一種算法，如果初始數(shù)據(jù)很小的誤差僅使最終結(jié)果產(chǎn)生 較小的誤差，則稱(chēng)該算法是數(shù)值穩(wěn)定的, 否則稱(chēng)為不穩(wěn)定的。insensitive problem + stable algorithm accurate result!設(shè)計(jì)穩(wěn)定性好的算法是算法設(shè)計(jì)的目標(biāo)之一。慶 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日46 / 65Q32：能否給出一個(gè)算法不穩(wěn)定的例子？（1）例：建立計(jì)算Z1xnex 1dxI(n = 0 1 2 · · ·。, , , 20n =)0的遞推公式，并研究其誤差利用分部得到：In = 1 nIn1.則可以得到算法：I0= 1 e1In= 1 nIn