Chap00-計(jì)算方法引論

1、信息科學(xué)與技術(shù)學(xué)院信息科學(xué)與技術(shù)學(xué)院 計(jì)算方法是一門(mén)應(yīng)用數(shù)值計(jì)算方法（近似計(jì)算）計(jì)算方法是一門(mén)應(yīng)用數(shù)值計(jì)算方法（近似計(jì)算）來(lái)求解數(shù)學(xué)問(wèn)題的算法體系。來(lái)求解數(shù)學(xué)問(wèn)題的算法體系。 介紹微分、積分、線性方程組、常微分方程組和介紹微分、積分、線性方程組、常微分方程組和非線性方程等問(wèn)題數(shù)值解法的設(shè)計(jì)原理及實(shí)現(xiàn)方法。非線性方程等問(wèn)題數(shù)值解法的設(shè)計(jì)原理及實(shí)現(xiàn)方法。 本課程共本課程共3232學(xué)時(shí)，上課時(shí)間學(xué)時(shí)，上課時(shí)間112112周，周，1212周考試。周考試。 計(jì)算方法簡(jiǎn)明教程，王能超編著，高等教育出版計(jì)算方法簡(jiǎn)明教程，王能超編著，高等教育出版社，社，20042004年。年。 計(jì)算方法（第計(jì)算方法（第2 2

2、版），鄧建中、劉之行編著，西版），鄧建中、劉之行編著，西安交通大學(xué)出版社，安交通大學(xué)出版社，20012001年年 E-mailE-mail： 所謂所謂算法算法，就是計(jì)算機(jī)上使用的計(jì)算方法。，就是計(jì)算機(jī)上使用的計(jì)算方法。 科學(xué)計(jì)算離不開(kāi)計(jì)算機(jī)，更離不開(kāi)算法設(shè)計(jì)。人類(lèi)科學(xué)計(jì)算離不開(kāi)計(jì)算機(jī)，更離不開(kāi)算法設(shè)計(jì)。人類(lèi)計(jì)算能力是計(jì)算機(jī)的研制能力與算法設(shè)計(jì)能力兩者的計(jì)算能力是計(jì)算機(jī)的研制能力與算法設(shè)計(jì)能力兩者的總和。人們往往片面地強(qiáng)調(diào)高性能計(jì)算機(jī)是高性能計(jì)總和。人們往往片面地強(qiáng)調(diào)高性能計(jì)算機(jī)是高性能計(jì)算的物質(zhì)基礎(chǔ)，其實(shí)，高效算法的設(shè)計(jì)才是高性能計(jì)算的物質(zhì)基礎(chǔ)，其實(shí)，高效算法的設(shè)計(jì)才是高性能計(jì)算的靈魂。算的靈

3、魂。 有人這樣概括數(shù)學(xué)家的思維特征：他們往往不是對(duì)有人這樣概括數(shù)學(xué)家的思維特征：他們往往不是對(duì)問(wèn)題進(jìn)行正面的問(wèn)題進(jìn)行正面的“攻擊攻擊”，而是不斷地將問(wèn)題加工變，而是不斷地將問(wèn)題加工變形，直到把它轉(zhuǎn)化歸納為能夠解決的問(wèn)題，這就是所形，直到把它轉(zhuǎn)化歸納為能夠解決的問(wèn)題，這就是所謂謂化歸策略化歸策略。 關(guān)于化歸策略，笛卡爾曾提出過(guò)被后世尊為萬(wàn)能法關(guān)于化歸策略，笛卡爾曾提出過(guò)被后世尊為萬(wàn)能法則的一般模式：則的一般模式： （1 1）將實(shí)際問(wèn)題化歸為數(shù)學(xué)問(wèn)題；）將實(shí)際問(wèn)題化歸為數(shù)學(xué)問(wèn)題； （2 2）將數(shù)學(xué)問(wèn)題化歸為代數(shù)問(wèn)題；）將數(shù)學(xué)問(wèn)題化歸為代數(shù)問(wèn)題； （3 3）將代數(shù)問(wèn)題化歸為解方程。）將代數(shù)問(wèn)題化歸為

4、解方程。 化歸策略同樣是數(shù)值算法設(shè)計(jì)的基本策略。后文將化歸策略同樣是數(shù)值算法設(shè)計(jì)的基本策略。后文將基于化歸策略提供三種基本的算法設(shè)計(jì)技術(shù)：基于化歸策略提供三種基本的算法設(shè)計(jì)技術(shù)： （1 1）化大為小的縮減技術(shù)；）化大為小的縮減技術(shù)； （2 2）化難為易的校正技術(shù)；）化難為易的校正技術(shù)； （3 3）化粗為精的松弛技術(shù)。）化粗為精的松弛技術(shù)。 古希臘哲學(xué)家古希臘哲學(xué)家ZenoZeno在兩千多年前提出過(guò)一個(gè)駭人在兩千多年前提出過(guò)一個(gè)駭人聽(tīng)聞的命題：一個(gè)人不管跑得多快，也追不上爬在聽(tīng)聞的命題：一個(gè)人不管跑得多快，也追不上爬在他前面的一只烏龜。這就是著名的他前面的一只烏龜。這就是著名的ZenoZeno悖

5、論悖論。 咱們兩個(gè)比賽吧，咱們兩個(gè)比賽吧，看誰(shuí)跑的快！嘻嘻看誰(shuí)跑的快！嘻嘻好吧，好吧，我還怕你。我還怕你。 Zeno Zeno在論證這個(gè)命題時(shí)采取了如下形式的邏輯推在論證這個(gè)命題時(shí)采取了如下形式的邏輯推理：理： 設(shè)人與龜同時(shí)同向起跑，如果龜不動(dòng)，那么人經(jīng)設(shè)人與龜同時(shí)同向起跑，如果龜不動(dòng)，那么人經(jīng)過(guò)某個(gè)時(shí)刻便能追上它。但實(shí)際上在這段時(shí)間內(nèi)龜過(guò)某個(gè)時(shí)刻便能追上它。但實(shí)際上在這段時(shí)間內(nèi)龜又爬了一段路程，從而人又得重新追趕，這樣每追又爬了一段路程，從而人又得重新追趕，這樣每追趕一次所歸結(jié)的是同樣類(lèi)型的追趕問(wèn)題，因而這種趕一次所歸結(jié)的是同樣類(lèi)型的追趕問(wèn)題，因而這種追趕過(guò)程追趕過(guò)程“永遠(yuǎn)永遠(yuǎn)”不會(huì)終結(jié)。不

6、會(huì)終結(jié)。 ZenoZeno的論證過(guò)程可描的論證過(guò)程可描述如下：述如下：t0vVS0t1vVS1Sk-1tk-1vVtkSkVv 人龜追趕過(guò)程人龜追趕過(guò)程 盡管盡管ZenoZeno悖論的論斷極其荒謬，但從算法設(shè)計(jì)思想悖論的論斷極其荒謬，但從算法設(shè)計(jì)思想的角度來(lái)看它卻是極為精辟的。的角度來(lái)看它卻是極為精辟的。 ZenoZeno悖論將人龜追趕問(wèn)題表達(dá)為一連串追趕的逐步悖論將人龜追趕問(wèn)題表達(dá)為一連串追趕的逐步逼近過(guò)程。逼近過(guò)程。 設(shè)人與龜?shù)乃俣确謩e為設(shè)人與龜?shù)乃俣确謩e為V與與v，記，記Sk表示逼近過(guò)程的表示逼近過(guò)程的第第k步人與龜?shù)拈g距，另以步人與龜?shù)拈g距，另以tk表示相應(yīng)的時(shí)間，相鄰兩表示相應(yīng)的時(shí)間

7、，相鄰兩步的時(shí)間差：步的時(shí)間差： tk = = tk - - tk-1 Zeno Zeno悖論將人龜追趕問(wèn)題分解為一追一趕兩個(gè)過(guò)程：悖論將人龜追趕問(wèn)題分解為一追一趕兩個(gè)過(guò)程：追的過(guò)程追的過(guò)程：先令龜不動(dòng)，計(jì)算人追上龜所費(fèi)的時(shí)間：先令龜不動(dòng)，計(jì)算人追上龜所費(fèi)的時(shí)間 tk = =Sk-1 / V趕的過(guò)程趕的過(guò)程：在令人不動(dòng)，計(jì)算龜在這段時(shí)間內(nèi)爬行的：在令人不動(dòng)，計(jì)算龜在這段時(shí)間內(nèi)爬行的路程路程 Sk = =v tk 經(jīng)過(guò)這兩步加工得出的雖然仍是追趕問(wèn)題，但新問(wèn)經(jīng)過(guò)這兩步加工得出的雖然仍是追趕問(wèn)題，但新問(wèn)題的題的“規(guī)模規(guī)?！?” Sk卻被壓縮了卻被壓縮了v / V倍，由于壓縮系數(shù)倍，由于壓縮系數(shù)v

8、/ V很小，按上述過(guò)程進(jìn)行幾步，追趕問(wèn)題的很小，按上述過(guò)程進(jìn)行幾步，追趕問(wèn)題的“規(guī)模規(guī)?！?” Sk便可忽略不計(jì)，從而可得出人追上龜所花費(fèi)的時(shí)間便可忽略不計(jì)，從而可得出人追上龜所花費(fèi)的時(shí)間tk 。 稱(chēng)這一算法稱(chēng)這一算法 S0= =S Sk = = Sk 1v/V ，k=1,2,3,為為ZenoZeno算法算法，它是，它是ZenoZeno悖論的算法描述。悖論的算法描述。 可見(jiàn)，可見(jiàn)，ZenoZeno算法的算法的設(shè)計(jì)思想設(shè)計(jì)思想是將人龜追趕計(jì)算化歸是將人龜追趕計(jì)算化歸為簡(jiǎn)單行程計(jì)算的重復(fù)為簡(jiǎn)單行程計(jì)算的重復(fù)，它的設(shè)計(jì)方法是逐步壓縮計(jì)，它的設(shè)計(jì)方法是逐步壓縮計(jì)算模型的規(guī)模，這種算模型的規(guī)模，這種“化

9、大為小化大為小”的設(shè)計(jì)策略稱(chēng)為的設(shè)計(jì)策略稱(chēng)為規(guī)規(guī)?？s減技術(shù)?？s減技術(shù)，簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)縮減技術(shù)縮減技術(shù)。 縮減技術(shù)是算法設(shè)計(jì)的一種基本技術(shù)。下面將舉例縮減技術(shù)是算法設(shè)計(jì)的一種基本技術(shù)。下面將舉例說(shuō)明這種設(shè)計(jì)技術(shù)的具體運(yùn)用。說(shuō)明這種設(shè)計(jì)技術(shù)的具體運(yùn)用。 (2) , 2 , 1 ,100 nkabbabkkk 可見(jiàn)，上述累加求和算法的設(shè)計(jì)思想是將多項(xiàng)求和可見(jiàn)，上述累加求和算法的設(shè)計(jì)思想是將多項(xiàng)求和式（式（1 1）化歸為兩項(xiàng)求和（）化歸為兩項(xiàng)求和（2 2）的重復(fù)，最終加工成一）的重復(fù)，最終加工成一項(xiàng)和式（項(xiàng)和式（3 3）的退化情形從而得出和值）的退化情形從而得出和值S。 這樣，如果定義和式的項(xiàng)數(shù)為數(shù)列求和問(wèn)

10、題的規(guī)模，這樣，如果定義和式的項(xiàng)數(shù)為數(shù)列求和問(wèn)題的規(guī)模，則所求和值為（則所求和值為（1 1）的退化情形。因之，只要令和式的）的退化情形。因之，只要令和式的規(guī)模逐次減規(guī)模逐次減1 1，最終當(dāng)規(guī)模為，最終當(dāng)規(guī)模為1 1時(shí)即可直接得出所求的時(shí)即可直接得出所求的和值，而這樣設(shè)計(jì)出來(lái)的算法就是累加求和算法（和值，而這樣設(shè)計(jì)出來(lái)的算法就是累加求和算法（2 2）。）。n+1 項(xiàng)和式項(xiàng)和式 n項(xiàng)和式項(xiàng)和式 n-1 項(xiàng)和式項(xiàng)和式 1 項(xiàng)和式項(xiàng)和式 計(jì)算規(guī)模計(jì)算規(guī)模 計(jì)算結(jié)果計(jì)算結(jié)果 nkknknnnnxaaxaxaxaP01110 nkknknxaxaxaP2110)( 如果算出一次式的如果算出一次式的v1=a

11、0 x+a1值，則所給計(jì)算模型便值，則所給計(jì)算模型便可化歸為可化歸為n-1次式次式： nkknknxaxvP211的計(jì)算，從而使問(wèn)題的次數(shù)的計(jì)算，從而使問(wèn)題的次數(shù)( (規(guī)模規(guī)模) )減減1 1。不斷重復(fù)著這。不斷重復(fù)著這種加工手續(xù)，即可得如下多項(xiàng)式求值的秦九韶算法：種加工手續(xù)，即可得如下多項(xiàng)式求值的秦九韶算法： 秦九韶算法：秦九韶算法： , 2 , 1 ,100nkaxvvavkkk P = vn即為所求。即為所求。 n次次式求值式求值 n-1 次次式求值式求值 0 次次式求值式求值 計(jì)算規(guī)模計(jì)算規(guī)模 計(jì)算結(jié)果計(jì)算結(jié)果 直接法的縮減技術(shù)主要針對(duì)規(guī)模為正整數(shù)的一類(lèi)問(wèn)直接法的縮減技術(shù)主要針對(duì)規(guī)模為

12、正整數(shù)的一類(lèi)問(wèn)題求解。題求解。 直接法的縮減技術(shù)主要是采用直接法的縮減技術(shù)主要是采用大事化小，小事化大事化小，小事化了的方法解決了的方法解決問(wèn)題的，問(wèn)題的，有些問(wèn)題的有些問(wèn)題的“大事化小大事化小”過(guò)過(guò)程似乎無(wú)法了結(jié)。程似乎無(wú)法了結(jié)。ZenoZeno悖論強(qiáng)調(diào)人悖論強(qiáng)調(diào)人“永遠(yuǎn)永遠(yuǎn)”趕不上趕不上龜正是為了突出這層含義。這是一類(lèi)無(wú)限逼近的過(guò)龜正是為了突出這層含義。這是一類(lèi)無(wú)限逼近的過(guò)程，適于用所謂程，適于用所謂預(yù)報(bào)校正技術(shù)預(yù)報(bào)校正技術(shù)來(lái)處理。來(lái)處理。 還是以人龜比賽為例。還是以人龜比賽為例。 設(shè)人龜起初相距設(shè)人龜起初相距S，兩者的速度分別為，兩者的速度分別為V和和v，則有，則有方程：方程： Vt -

13、 vt = S (1)則人追上龜所花的時(shí)間是則人追上龜所花的時(shí)間是： t* = S / (V- v) 設(shè)解設(shè)解t*有某個(gè)有某個(gè)預(yù)報(bào)值預(yù)報(bào)值t0 ，希望提供，希望提供校正值校正值t1 = t0+t ，使校正值能更好的滿足所給方程（使校正值能更好的滿足所給方程（1 1），即使），即使 V (t0+t )- v (t0+t ) S 注意到注意到v是個(gè)小量，設(shè)是個(gè)小量，設(shè)t也是個(gè)小量，則可從上式中也是個(gè)小量，則可從上式中略去略去vt ，即令校正值滿足如下方程：，即令校正值滿足如下方程： V t1- vt0 =S求解上述方程即可定出校正值求解上述方程即可定出校正值 t1=(S+ vt0) /V 進(jìn)一步視

14、進(jìn)一步視 t1為新的預(yù)報(bào)值，重復(fù)上述過(guò)程求出新的為新的預(yù)報(bào)值，重復(fù)上述過(guò)程求出新的校正值校正值t2，再由，再由t2求出求出t3，如此反復(fù)可生成一系列近似，如此反復(fù)可生成一系列近似值值t1, , t2, , t3 ，這就定義了一個(gè)迭代過(guò)程：，這就定義了一個(gè)迭代過(guò)程： tk+1=(S+ vtk) /V k=1,2,3, (2) Zeno Zeno悖論所描述的逼近過(guò)程正是這種迭代過(guò)程，悖論所描述的逼近過(guò)程正是這種迭代過(guò)程，當(dāng)當(dāng)k k時(shí)，時(shí)，tkt*。 任何形式的重復(fù)都可看成是任何形式的重復(fù)都可看成是“時(shí)間時(shí)間”的量度。的量度。ZenoZeno在刻畫(huà)人龜追趕問(wèn)題中設(shè)置了兩個(gè)在刻畫(huà)人龜追趕問(wèn)題中設(shè)置了兩

15、個(gè)“時(shí)鐘時(shí)鐘”：一個(gè)是：一個(gè)是日常的鐘，另外日常的鐘，另外ZenoZeno又將迭代次數(shù)又將迭代次數(shù)k視為另一種時(shí)鐘，視為另一種時(shí)鐘，稱(chēng)之為稱(chēng)之為ZenoZeno鐘鐘。 ZenoZeno公式（公式（2 2）表明，當(dāng)）表明，當(dāng)ZenoZeno鐘趨于鐘趨于時(shí)人才能追時(shí)人才能追上龜，上龜，ZenoZeno正是據(jù)此斷言人永遠(yuǎn)追不上龜。正是據(jù)此斷言人永遠(yuǎn)追不上龜。a 設(shè)給定某個(gè)預(yù)報(bào)值設(shè)給定某個(gè)預(yù)報(bào)值x0 ，希望借助于某種簡(jiǎn)單方法確，希望借助于某種簡(jiǎn)單方法確定校正量定校正量x，使校正值，使校正值x1 = x0+x能夠比較準(zhǔn)確地滿能夠比較準(zhǔn)確地滿足所給方程（足所給方程（1 1），即使），即使( (x0+x) 2 a成立，設(shè)校正值成立，設(shè)校正值x是個(gè)小量，舍去上式中的高階小量是個(gè)小量，舍去上式中的高階小量(x)2，令，令x02+2x0 x=a從中定出從中定出x，繼而可得校正值繼而可得校正值 )(21001xaxx 反復(fù)實(shí)施這種預(yù)報(bào)校正方法，即可求出開(kāi)方公式反復(fù)實(shí)施這種預(yù)報(bào)校正方法，即可求出開(kāi)方公式：1,2, )(211 kxaxxkkk 開(kāi)方算法：開(kāi)方算法： 任給初值任給初值x000，利用上式反復(fù)迭代即可獲得滿足，利用上式反復(fù)迭代即可獲