1、信息科學與技術學院信息科學與技術學院 計算方法是一門應用數值計算方法（近似計算）計算方法是一門應用數值計算方法（近似計算）來求解數學問題的算法體系。來求解數學問題的算法體系。 介紹微分、積分、線性方程組、常微分方程組和介紹微分、積分、線性方程組、常微分方程組和非線性方程等問題數值解法的設計原理及實現方法。非線性方程等問題數值解法的設計原理及實現方法。 本課程共本課程共3232學時，上課時間學時，上課時間112112周，周，1212周考試。周考試。 計算方法簡明教程，王能超編著，高等教育出版計算方法簡明教程，王能超編著，高等教育出版社，社，20042004年。年。 計算方法（第計算方法（第2 2

2、版），鄧建中、劉之行編著，西版），鄧建中、劉之行編著，西安交通大學出版社，安交通大學出版社，20012001年年 E-mailE-mail： 所謂所謂算法算法，就是計算機上使用的計算方法。，就是計算機上使用的計算方法。 科學計算離不開計算機，更離不開算法設計。人類科學計算離不開計算機，更離不開算法設計。人類計算能力是計算機的研制能力與算法設計能力兩者的計算能力是計算機的研制能力與算法設計能力兩者的總和。人們往往片面地強調高性能計算機是高性能計總和。人們往往片面地強調高性能計算機是高性能計算的物質基礎，其實，高效算法的設計才是高性能計算的物質基礎，其實，高效算法的設計才是高性能計算的靈魂。算的靈

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

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

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

6、會終結。 ZenoZeno的論證過程可描的論證過程可描述如下：述如下：t0vVS0t1vVS1Sk-1tk-1vVtkSkVv 人龜追趕過程人龜追趕過程 盡管盡管ZenoZeno悖論的論斷極其荒謬，但從算法設計思想悖論的論斷極其荒謬，但從算法設計思想的角度來看它卻是極為精辟的。的角度來看它卻是極為精辟的。 ZenoZeno悖論將人龜追趕問題表達為一連串追趕的逐步悖論將人龜追趕問題表達為一連串追趕的逐步逼近過程。逼近過程。 設人與龜的速度分別為設人與龜的速度分別為V與與v，記，記Sk表示逼近過程的表示逼近過程的第第k步人與龜的間距，另以步人與龜的間距，另以tk表示相應的時間，相鄰兩表示相應的時間

7、，相鄰兩步的時間差：步的時間差： tk = = tk - - tk-1 Zeno Zeno悖論將人龜追趕問題分解為一追一趕兩個過程：悖論將人龜追趕問題分解為一追一趕兩個過程：追的過程追的過程：先令龜不動，計算人追上龜所費的時間：先令龜不動，計算人追上龜所費的時間 tk = =Sk-1 / V趕的過程趕的過程：在令人不動，計算龜在這段時間內爬行的：在令人不動，計算龜在這段時間內爬行的路程路程 Sk = =v tk 經過這兩步加工得出的雖然仍是追趕問題，但新問經過這兩步加工得出的雖然仍是追趕問題，但新問題的題的“規模規模” ” Sk卻被壓縮了卻被壓縮了v / V倍，由于壓縮系數倍，由于壓縮系數v

8、/ V很小，按上述過程進行幾步，追趕問題的很小，按上述過程進行幾步，追趕問題的“規模規模” ” Sk便可忽略不計，從而可得出人追上龜所花費的時間便可忽略不計，從而可得出人追上龜所花費的時間tk 。 稱這一算法稱這一算法 S0= =S Sk = = Sk 1v/V ，k=1,2,3,為為ZenoZeno算法算法，它是，它是ZenoZeno悖論的算法描述。悖論的算法描述。 可見，可見，ZenoZeno算法的算法的設計思想設計思想是將人龜追趕計算化歸是將人龜追趕計算化歸為簡單行程計算的重復為簡單行程計算的重復，它的設計方法是逐步壓縮計，它的設計方法是逐步壓縮計算模型的規模，這種算模型的規模，這種“化

9、大為小化大為小”的設計策略稱為的設計策略稱為規規模縮減技術模縮減技術，簡稱簡稱縮減技術縮減技術。 縮減技術是算法設計的一種基本技術。下面將舉例縮減技術是算法設計的一種基本技術。下面將舉例說明這種設計技術的具體運用。說明這種設計技術的具體運用。 (2) , 2 , 1 ,100 nkabbabkkk 可見，上述累加求和算法的設計思想是將多項求和可見，上述累加求和算法的設計思想是將多項求和式（式（1 1）化歸為兩項求和（）化歸為兩項求和（2 2）的重復，最終加工成一）的重復，最終加工成一項和式（項和式（3 3）的退化情形從而得出和值）的退化情形從而得出和值S。 這樣，如果定義和式的項數為數列求和問

10、題的規模，這樣，如果定義和式的項數為數列求和問題的規模，則所求和值為（則所求和值為（1 1）的退化情形。因之，只要令和式的）的退化情形。因之，只要令和式的規模逐次減規模逐次減1 1，最終當規模為，最終當規模為1 1時即可直接得出所求的時即可直接得出所求的和值，而這樣設計出來的算法就是累加求和算法（和值，而這樣設計出來的算法就是累加求和算法（2 2）。）。n+1 項和式項和式 n項和式項和式 n-1 項和式項和式 1 項和式項和式 計算規模計算規模 計算結果計算結果 nkknknnnnxaaxaxaxaP01110 nkknknxaxaxaP2110)( 如果算出一次式的如果算出一次式的v1=a

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

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

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

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

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