計算方法信息科學與技術學院本課程的研究對象

計算方法是一門應用數值計算方法（近似計算）來求解數學問題的算法體系。

教學目標

介紹微分、積分、線性方程組、常微分方程組和非線性方程等問題數值解法的設計原理及實現方法。教學計劃

本課程共32學時，上課時間1~12周，12周考試。計算方法

課程簡介教材

計算方法簡明教程，王能超編著，高等教育出版社，2004年。參考書

計算方法（第2版），鄧建中、劉之行編著，西安交通大學出版社，2001年

聯系方式

E-mail：chengyong@

引論本章介紹主要內容：

算法重在設計

化大為小的縮減技術化難為易的校正技術化粗為精的松弛技術計算方法1-1

科學計算離不開算法設計所謂算法，就是計算機上使用的計算方法。科學計算離不開計算機，更離不開算法設計。人類計算能力是計算機的研制能力與算法設計能力兩者的總和。人們往往片面地強調高性能計算機是高性能計算的物質基礎，其實，高效算法的設計才是高性能計算的靈魂。

1算法重在設計1-2

數學思維的化歸策略有人這樣概括數學家的思維特征：他們往往不是對問題進行正面的“攻擊”，而是不斷地將問題加工變形，直到把它轉化歸納為能夠解決的問題，這就是所謂化歸策略。關于化歸策略，笛卡爾曾提出過被后世尊為萬能法則的一般模式：（1）將實際問題化歸為數學問題；（2）將數學問題化歸為代數問題；（3）將代數問題化歸為解方程?；瘹w策略同樣是數值算法設計的基本策略。后文將基于化歸策略提供三種基本的算法設計技術：（1）化大為小的縮減技術；（2）化難為易的校正技術；（3）化粗為精的松弛技術。

2

化大為小的縮減技術2-1Zeno悖論的啟示古希臘哲學家Zeno在兩千多年前提出過一個駭人聽聞的命題：一個人不管跑得多快，也追不上爬在他前面的一只烏龜。這就是著名的Zeno悖論。咱們兩個比賽吧，看誰跑的快！嘻嘻好吧，我還怕你。

Zeno在論證這個命題時采取了如下形式的邏輯推理：設人與龜同時同向起跑，如果龜不動，那么人經過某個時刻便能追上它。但實際上在這段時間內龜又爬了一段路程，從而人又得重新追趕，這樣每追趕一次所歸結的是同樣類型的追趕問題，因而這種追趕過程“永遠”不會終結。Zeno的論證過程可描述如下：t0vVS0t1vVS1……Sk-1tk-1vVtkSkVv

人龜追趕過程……盡管Zeno悖論的論斷極其荒謬，但從算法設計思想的角度來看它卻是極為精辟的。

Zeno悖論將人龜追趕問題表達為一連串追趕的逐步逼近過程。設人與龜的速度分別為V與v，記Sk表示逼近過程的第k步人與龜的間距，另以tk表示相應的時間，相鄰兩步的時間差：

△tk=tk-tk-1Zeno悖論將人龜追趕問題分解為一追一趕兩個過程：追的過程：先令龜不動，計算人追上龜所費的時間

△tk

=Sk-1/V趕的過程：在令人不動，計算龜在這段時間內爬行的路程

Sk

=v△

tk

經過這兩步加工得出的雖然仍是追趕問題，但新問題的“規?！盨k卻被壓縮了v

/V倍，由于壓縮系數v

/V很小，按上述過程進行幾步，追趕問題的“規?！盨k便可忽略不計，從而可得出人追上龜所花費的時間tk。稱這一算法

S0=S

Sk

=

Sk

–1v/V，k=1,2,3,······為Zeno算法，它是Zeno悖論的算法描述?？梢姡琙eno算法的設計思想是將人龜追趕計算化歸為簡單行程計算的重復，它的設計方法是逐步壓縮計算模型的規模，這種“化大為小”的設計策略稱為規模縮減技術，簡稱縮減技術?？s減技術是算法設計的一種基本技術。下面將舉例說明這種設計技術的具體運用。2-2數列求和的累加算法數列求和問題：

S=a0+a1+···+an

(1)是最簡單的計算模型。若記bk表示前k+1項的和a0+a1+···+an

，則有：則計算結果bn即為所求的和值S：

S=

bn

(3)

可見，上述累加求和算法的設計思想是將多項求和式（1）化歸為兩項求和（2）的重復，最終加工成一項和式（3）的退化情形從而得出和值S。

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

項和式n項和式

n-1

項和式···1

項和式

計算規模計算結果2-3縮減技術的設計思想

許多數值計算問題可以引進某個實數—即所謂問題的規模來刻畫其“大小”，而問題的解恰好是其規模為足夠小的退化情形。求解這類問題的一種行之有效的方法是通過某種簡單的運算手續逐步縮減問題的規模，直到加工出問題的解。算法設計的這種技術稱為規?？s減技術，簡稱縮減技術。

縮減技術的設計思想可用大事化小，小事化了這句俗話來概括。所謂大事化小即指逐步壓縮問題的規模，這個處理過程應具有結構遞歸和規模遞減兩項基本特征。小事化了即是指當問題的規模變得足夠小時即可直接或方便得出問題的解。通常對于規模大但有限的問題如上述數列求和問題設計出來的一類算法統稱直接法。下面介紹的多項式求值的秦九韶算法也是直接法。

2-4多項式求值的秦九韶算法設要對給定點計算下列多項式的值

由于上式可改寫為如下形式

如果算出一次式的v1=a0x+a1值，則所給計算模型便可化歸為n-1次式：的計算，從而使問題的次數(規模)減1。不斷重復著這種加工手續，即可得如下多項式求值的秦九韶算法：秦九韶算法：

P=

vn即為所求。

n次式求值n-1

次式求值···0次式求值

計算規模計算結果

直接法的縮減技術主要針對規模為正整數的一類問題求解。

3化難為易的校正技術3-1Zeno悖論中的“Zeno鐘”

直接法的縮減技術主要是采用大事化小，小事化了的方法解決問題的，有些問題的“大事化小”過程似乎無法了結。Zeno悖論強調人“永遠”趕不上龜正是為了突出這層含義。這是一類無限逼近的過程，適于用所謂預報校正技術來處理。還是以人龜比賽為例。

設人龜起初相距S，兩者的速度分別為V和v，則有方程：

Vt

-

vt

=S

(1)則人追上龜所花的時間是：

t*

=S/(V-v)

設解t*有某個預報值t0

，希望提供校正值t1=t0+△t

，使校正值能更好的滿足所給方程（1），即使

V(t0+△t)-v(t0+△t)

S

注意到v是個小量，設△t也是個小量，則可從上式中略去v△t，即令校正值滿足如下方程：

Vt1-vt0

=S求解上述方程即可定出校正值

t1=(S+vt0)

/V

進一步視t1為新的預報值，重復上述過程求出新的校正值t2，再由t2求出t3，如此反復可生成一系列近似值t1,t2,t3···，這就定義了一個迭代過程：

tk+1=(S+vtk)

/Vk=1,2,3,···

(2)Zeno悖論所描述的逼近過程正是這種迭代過程，當k∞時，tkt*。

任何形式的重復都可看成是“時間”的量度。Zeno在刻畫人龜追趕問題中設置了兩個“時鐘”：一個是日常的鐘，另外Zeno又將迭代次數k視為另一種時鐘，稱之為Zeno鐘。

Zeno公式（2）表明，當Zeno鐘趨于∞時人才能追上龜，Zeno正是據此斷言人永遠追不上龜。3-2求開方值的迭代公式給定a>0，求開方值的問題就是要解方程：

x2–a=0

(1)設給定某個預報值x0，希望借助于某種簡單方法確定校正量△x，使校正值x1=x0+△x能夠比較準確地滿足所給方程（1），即使(x0+△x)2a成立，設校正值△x是個小量，舍去上式中的高階小量(△x)2，令x02+2x0△x=a從中定出△x，繼而可得校正值反復實施這種預報校正方法，即可求出開方公式：

開方算法：任給初值x0>0，利用上式反復迭代即可獲得滿足精度要求的開方值。

直到|xk+1-xk|<ε（ε為給定的精度）為止，xk

即為所求。例0-1用開方算法求，取x0=1，ε=10-6解：求解過程見下表：因此，

1.414214kxk0111.50000021.46666731.41421641.41421451.4142143-3校正技術的設計思想由校正技術得到的迭代法突出地體現了刪繁就簡，逐步求精的設計思想?！皠h繁就簡”的含義是，刪去所給復雜方程中某些高階小量而簡化生成所謂的校正方程以確定所給預報值的校正量，其中校正方程應滿足逼近性和簡單性兩項要求。利用校正方程獲得所給復雜方程解的一種行之有效的途徑就是遞推化，反復預報校正直到達到精度要求為止。4-1Zeno算法的升華再考察Zeno算法。對于給定的預報值t0

，有

Vt1-vt0

=S兩端同除V–v，有

4化粗為精的松弛技術由于

為Zeno悖論的精確解，由此可見，精確解t*等于任給預報值t0同它的校正值t1兩者的加權平均：

t*

=(1+ω)t1-ωt0

其中ω=v/(V-v)。