Chap00-计算方法引论

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，利用上式反复迭代即可获得满足，利用上式反复迭代即可获