数值分析简明教程.pdf

《数值分析简明教程.pdf》由会员分享，可在线阅读，更多相关《数值分析简明教程.pdf（159页珍藏版）》请在三一文库上搜索。

1、数值分析简明教程 王能超 编著 1.1 教材及授课教师简介 数值分析简明教程（修订版） 王能超 编著 华中科技大学出版社 数值分析简明教程（修订版） 王能超 编著 华中科技大学出版社 授课教师：陈爱斌 电话： 授课教师：陈爱斌 电话：2315203 13755188894 Email: homepage: http:/ QQ: 5708111 数值分析简明教程 王能超 编著 1.2 数学是计算机的基础 数学知识数学知识对计算机的学习和研究十分重要！许多计算机著 名专家学者，其大学时期是学计算数学计算数学专业。 王选王选，教授，男，1937年2月出生，江苏无锡人。1958年 毕业于北京大学数学

2、力学系计算数学专业(本科)。现为北京大 学计算机研究所所长、教授、博士生导师，中国科学院院士 、中国工程院院士、第三世界科学院院士，文字信息处理国 家重点实验室主任，电子出版新技术国家工程研究中心主任 ，方正(香港)董事局主席，中国科协副主席，九三学社中央副 主席，全国人大常委，全国人大教科文卫委员会副主任。 数值分析简明教程 王能超 编著 1.3 石钟慈石钟慈中国科学院院士，男，1933年12月15日生，浙江宁 波人。1991年当选为中国科学院院士。1955年毕业于上海复 旦大学数学系。1956年首批赴苏联攻读计算数学。1960年到 中国科学院计算所工作。曾任中国科技大学数学系主任，中 国科

3、学院计算中心主任,科学与工程计算国家重点实验室主任 ，中国数学学会副理事长。现任中国计算数学学会理事长， 国家攀登计划预选项目大规模科学与工程计算的方法和理 论首席科学家，国内外多种学术刊物的主编和编委。 数值分析简明教程 王能超 编著 1.4 杨芙清杨芙清教授，女，1932年生。江苏无锡人。计算机软件专 家；中国科学院院士（1991年）；北京大学教授、北京大学 信息与工程科学学部主任，软件工程国家工程研究中心主任 ，北京大学软件学院理事长、名誉院长；兼任国务院学位委 员会委员及学科评议组第一召集人，中国计算机学会、中国 软件行业协会副理事长，北京市人民政府专家顾问团顾问, IEEE Fell

4、ow，贝尔实验室基础科学研究院（中国）高级顾问, 中国科学、科学通报、电子学报副主编，复旦 大学、浙江大学、香港科技大学等校兼职教授。 1958年毕业于北京大学数学力学系（研究生）。1957- 1959年在前苏联科学院计算中心和莫斯科大学数力系学习， 1962-1964年任前苏联杜勃纳联合核子物理所计算中心中国 专家。 数值分析简明教程 王能超 编著 1.5 数值分析的基本内容数值分析的基本内容 数值分析的基本内容是数值算法的设计与分析。 对于数值微积分，无论是算法的设计还是算法的分析，其 高等数学的基础都是泰勒公式。 微积分的精华是逼近法，逼近法的精髓是泰勒公式。 泰勒公式包打天下泰勒公式包

5、打天下! 数值分析简明教程 王能超 编著 1.6 引论 许多科学问题（核武器的研制、导弹的发射、气象预报）的 解决都离不开科学计算。 本门课程将着重绍进行科学计算所必须掌握的一些最基本、 最常用的算法,并分析其误差。 数值分析简明教程 王能超 编著 1.7 研究算法的意义 尽管计算机的运算速度高， 可以承担大运算量的工作，但这并 不意味着我们可随意选择 计算机上的算法，相反的，算法的优劣决 定着计算效率的高低，能否正确地制定算法也是科学计算成败的关 键。 例：行列式解法-克莱姆法则 一个n阶方程组，要算n+1个n阶行列式的值，为此总共需要做 n!(n-1)(n+1)次乘法， 对于n=20，大约

6、要做1021次乘法，百万次每秒的电子计算机需 连续工作千百万年才能完成！ 数值分析简明教程 王能超 编著 1.8 一个具体数学问题的多种解法 例1：证明二次方程 x2+2bx+c=0 至多有两个不同的实根。 （1）反证法 （2）图解法 （3）公式法 上述三种方法，反证法不是构造性的；作图法虽是构造性的， 但不是数值的。 数值分析简明教程 王能超 编著 1.9 什么是算法 我们所说的“ 算法”必须是构造性的数值方法，即不但要论证问 题的可解性，而且解的构造是通过数值演算过程来完成的。同传统 的近似计算方法不同，我们要研究的算法是为电子计算机提供的， 解题方案中的每个细节都必须准确的定义，并且要完

7、整地描述整个 解题过程。我们所说的“算法”不仅仅是单纯的计算公式，而是指解 题方案的准确而完整的描述。 计算公式是算法的核心概念。计算机上使用的算法，其计算公 式常采用递推化的形式。递推化的基本思想是将一个复杂的计算过 程归结为简单过程的多次重复。 这种重复在算法上表现为循环，描 述是容易的。 数值分析简明教程 王能超 编著 1.10 算法的框图描述 开始 结束 叙述框 检查框 标志计算过程开始启动 表示计算过程的最终结束 指明各框执行的顺序 数值分析简明教程 王能超 编著 1.11 递推化的基本思想 递推化的基本思想是： 将一个复杂的计算过程归结为简单过程的多次重复，这种重复在 算法上表现为

8、循环，描述是容易的。 例如：设要求对给定 x 的求下列多项式的值 一种看起来很“自然”的算法是直接逐项求和。我们假设： 则： 作为初值： 总的计算量为2n次乘法 n nx axaxaaxp+=.)( 2 210 k k xt = k kk xaxaxaau+=. 2 210 1 = kk xtt kkkk tauu+= 1 1 0 =t 00 au = 数值分析简明教程 王能超 编著 1.12 多项式求值的秦九韶算法 设要求对给定的求下列多项式的值 由于该式有如下嵌套形式： 故有如下求该多项式值的秦九韶算法秦九韶算法： 秦九韶算法的特点在于，它通过一次式的反复计算，逐步得出 高次多项式的值。具

9、体的说，他将一个次多项式的求值问题归结 为重复计算个 一次式来实现。总共n次乘法！ x ( ) 2 012 n n p xaa xa xa x=+? ( )()()() 1210nnn p xa xaxaaxa =+? 0 1 1,2, n kkn k va kn vxva = = =+ ?， n n 1kkn k vxva =+ 数值分析简明教程 王能超 编著 1.13 秦九韶算法流程图 数值分析简明教程 王能超 编著 1.14 方程求根的二分法 设函数在上连续，且，假定 在上有唯一的实根。 考察有根区间，取中点将它分为两半。然后 进行根的搜索，即检查和是否同号。若确定同号，说明所 求的根在

10、的右侧，这时令，否则必在左侧，这 时令，于是我们就得到了一个长度压缩了一半的有根 区间，对于有根区间施行同样手续可得到新的有根区 间，反复如此我们可得到一系列的有根区间： 令，则二分过程中可获得一个近似根的序列 逐步逼近所求的根。 ( )f x, a b( ) ( ) 0f a f b 数值分析简明教程王能超 编著4.14 亚当姆斯格式 亚当姆斯（Adams)方法的设计思想是充分利用计算之前已 得到一系列节点上的斜率值来减少计算量。譬如，我们可 以用两点的斜率的加权平均作为区间上的平均斜率， 于是可设计出如下二阶亚当姆斯格式 ： 类似的，可导出如下三阶和四阶亚当姆斯格式： 1n y + 1 ,

11、 nn xx ? 1 , nn xx 1 , nn xx + 11 3/2 nnnn yyhyy + =+ 112 23165/12 nnnnn yyhyyy + =+ 1123 5559379/24 nnnnnn yyhyyyy + =+ 数值分析简明教程王能超 编著4.15 隐式亚当姆斯格式 同样，我们也可导出如下隐式的二阶、三阶和四阶亚当姆斯格 式： 11 /2 nnnn yyh yy + =+ 111 58/12 nnnnn yyhyyy + =+ 1112 9195/24 nnnnnn yyhyyyy + =+ 数值分析简明教程王能超 编著4.16 亚当姆斯预报-校正系统 仿照改进的

12、欧拉格式的构造方法，将显式和隐式两种亚当姆斯格 式相匹配，可构成下列亚当姆斯预报校正系统亚当姆斯预报校正系统： 预报 校正 () () 1123 111 5559379/24 , nnnnnn nnn yyhyyyy yf xy + + =+ = () () 1123 111 9195/24 , nnnnnn nnn yyhyyyy yf xy + + =+ = 数值分析简明教程王能超 编著4.17 改进的亚当姆斯预报-校正系统 我们可以方便地估计出亚当姆斯预报校正系统的截断误差，从而 依据这种估计将该系统 就可改进为如下精度更高的计算方案： 预报 改进 校正 改进 () () () 1123

13、 11 111 5559379/24 251 270 , nnnnnn nnnn nnn pyhyyyy mpcp mf xm + + + =+ =+ = () () () 1112 1111 111 9195/24 19 270 , nnnnnn nnnn nnn cyhmyyy yccp yf xy + + + =+ = = 数值分析简明教程王能超 编著4.18 收敛性问题 在用差分格式求解微分方程时我们要考虑差分格式的收敛性。我 们称差分格式是收敛的，如果对任意固定的，数值解 当（同时）时趋于准确解。 以下我们研究欧拉方法的收敛性。我们记，记 为关于的李普希兹常数，经反复递推，可得 其中

14、为常数。 若初始是准确的，即，则当时，有。 这说明欧拉方法是收敛收敛的。 0n xxnh=+ n y 0h n () n y x () nnn ey xy=L fy () 0 1 TLTL n C ee eeh L + ,C T 0 y 0 0e = 0h 0 n e 数值分析简明教程王能超 编著4.19 稳定性问题 关于收敛性的讨论有个前提，即必须假定差分方法的每一步计 算都是准确的。然而实际计算中往往由于有舍入误差等原因而产生 扰动，而这些扰动有可能 “淹没” 真解，所以我们还要考虑稳定性问 题。 我们称差分方法是稳定稳定的，如果在节点值上大小为的扰动 于以后各节点值上产生的偏差值均不超过

15、。 稳定性比较复杂。为简化讨论，我们仅考察下列模型方程 可以验证 ，对于该模型方程，欧拉格式是条件稳定条件稳定的，而隐式欧拉 格式是恒稳定恒稳定的。 n y (), m ymn ,0yy= 数值分析简明教程王能超 编著5.10 牛顿下山法 一般地说，牛顿法的收敛性依赖于初值的选取，如果 偏离较远，则牛顿法可能发散。 为了防止发散，通常对迭代过程再附加一项要求，即保证函数 值单调下降： 满足这项要求的算法称为下山法下山法。 牛顿下山法牛顿下山法采用以下迭代公式： 其中称为下山因子。 ()() 1kk f xf x + 01 () () 1 k kk k f x xx fx + = k x k x

16、 * x 数值分析简明教程王能超 编著5.11 弦截法 用差商替代牛顿公式中的导数可得到以下离散化 形式： 从几何图形上看，上面的公式求得的实际上是弦线与轴的交 点，因此称这种方法为弦截法弦截法。 改用差商代替牛顿法中的导数有以下快速弦截 法迭代公式： () ()() () 10 0 k kkk k f x xxxx f xf x + = ()() 1 1 kk kk f xf x xx () ()() () 11 1 k kkkk kk f x xxxx f xf x + = x ()() 0 0 k k f xf x xx 数值分析简明教程王能超 编著6.1 第5章线性方程组的迭代法 1

17、迭代公式的建立 2 向量和矩阵的范数 3 迭代过程的收敛性 数值分析简明教程王能超 编著6.2 引言 前几章研究过的几个课题，无论是插值公式与求积公式的建立， 还是常微分方程差分格式的构造，其基本思想都是将其转化为代数 问题来处理，最后归结为解线性方程组。工程技术的科学计算中， 线性方程组也会经常遇到。因此，线性方程组的解法在数值分析中 占有极其重要的地位。 线性方程组的解法大致分为直接法和迭代法两大类。本章将先 介绍迭代法，这类算法一个突出优点就是算法简单，因而编制程序 比较容易。但是迭代法也有缺点,它要求方程组的系数矩阵具有某种 特殊性质，以保证迭代过程的收敛性。发散的迭代过程是没有实用

18、价值的。 数值分析简明教程王能超 编著6.3 雅可比迭代公式 解线性方程组迭代法的基本思想是将联立方程组的求解归结为重 复计算一组彼此独立的线性表达式，这就使问题得到了简化。 考察一般形式的线性方程组， 从上式中分离出变量，将它改写成 ， 即得到解方程组的雅可比迭代公式雅可比迭代公式: ， 1 n ijji j a xb = = 1, 1 n iiijj jj i ii xba x a = = 1,2,in=? 1,2,in=? i x 1,2,in=? ()( )1 1, 1 n kk iiijj jj i ii xba x a + = = 数值分析简明教程王能超 编著6.4 高斯塞德尔迭代

19、公式 在迭代的每一步设定计算顺序 并且，在计算迭代值充分利用它前面的 新信息 ， 这样设计出来的迭代公式 ， 称为高斯高斯塞德尔迭代公式塞德尔迭代公式。 12n xxx? ()1k i x + ()()()111 121 , kkk i xxx + ? ()()( ) 1 11 11 1 in kkk iiijjijj jj i ii xba xa x a + = + = 1,2,in=? 数值分析简明教程王能超 编著6.5 超松弛法 松弛法实质是高斯塞德尔迭代的一种加速方法。它将前一步 的结果与高斯塞德尔迭代值适当加权平均： 迭代 加速 式中系数称为松弛因子。为保证迭代收敛，要求。 由于迭代

20、值通常比精确，所以加大它的比重，取松 弛因子， 这种方法称为超松弛法超松弛法。 ()()( ) 1 11 11 1 in kkk iiijjijj jj i ii xba xa x a + = + = ? ()() () ( )11 1 kkk iii xxx + =+? 02 12 ( )k i x ()1k i x + ? ()1k i x + ? ( )k i x 数值分析简明教程王能超 编著6.6 迭代公式的矩阵表示 考察线性方程组， 设将系数矩阵分裂为 其中为对角阵，和分别为严格下三角和严格上三角阵。 如果将所给方程改写为 据此建立的迭代公式 即为雅可比迭代公式。如果改写为 据此建立

21、的迭代公式 即为高斯塞德尔迭代公式。 Axb=A ALDU=+ DLU ()LDU xb+=()DxLU xb= + () () ( )111kk xDLU xD b + = + ()DL xUxb+=+ ()()( ) () 1111kkk xDLxUxD b + = + 数值分析简明教程王能超 编著6.7 向量的范数 为了研究迭代过程的收敛性，需要对向量”大小“引入某种度 量。 任给向量，其范数范数记为，它是一个实数 ， 且满足： (1)对任意向量, , 当且仅当时, (2)对任意实数及任意向量, (3)对于任意向量与, 有 其中性质(3)被称为向量范数的三角不等式。 () 12 , T

22、n xx xx=?x x0x 0x = x xy xx= xyxy+ 0x= 数值分析简明教程王能超 编著6.8 矩阵的范数 对给定的阶方阵，我们将比值，的上确界称 为的范数范数，记为。 由定义知，对任意向量，有。 矩阵范数具有以下基本性质： (1) 对任意方阵，当且仅当时 (2) 对任意实数和任意方阵，有 (3) 对任意两个同阶方阵和，有 A ()0Axxx AA x 0A AA= ABAB+ ABA B An A x A 0A =0A = A AB 数值分析简明教程王能超 编著6.9 迭代收敛的充分条件 定理定理 对给定的方阵，若，则矩阵为非奇异。 设将方程组改写成的形式，据此建立迭代公

23、式 定理定理 若迭代矩阵满足，则上迭代公式对任意初值 均收敛。 1G ()( )1kk xGxd + =+ 1G GIG Axb=xGxd=+ G ( )0 x 数值分析简明教程王能超 编著6.10 对角占优方程 称阶方阵是对角占优的，如果其主对角线元素的绝对 值大于同行其它元素绝对值之和： 若线性方程祖的系数矩阵为对角占优阵，则称这个线性方程组为 对角占优方程组。 定理定理 对角占优方程组的雅可比迭代公式和高斯塞德尔迭代公式 均收敛。 () ij n Aa= 1, n ijii jj i aa = 1,2,in=? n 数值分析简明教程王能超 编著7.1 第6章线性方程组的直接法 1 消去法

24、 2 追赶法 3 平方根法 4 误差分析 数值分析简明教程王能超 编著7.2 引言 求解线性方程组的另一类重要方法是直接法。直接法利用一系 列递推公式计算有限步能直接得到方程组的精确解。当然，实际计 算结果仍有误差，譬如舍入误差。舍入误差的积累有时甚至会严重 影响解的精度。 求解线性方程组最基本的一种直接法是消去法。这是一个众所 周知的古老方法，但用在现代电子计算机上仍然十分有效。 数值分析简明教程王能超 编著7.3 约当消去法 消去法的基本思想是，通过将一个方程乘或除以某个常数，以 及将两个方程相加减这两种手续，逐步减少方程中的变元的数目， 最终使每个方程仅含一个变元，从而得出所求的解。 所

25、谓约当消去法约当消去法 ，其特点是，它的每一步仅在一个方程中保留 某个变元，而从其它的各个方程中消去该变元，这样经过反复消元 后，所给方程组中的每个方程最终被加工成仅含一个变元的形式， 从而得出所求的解。 数值分析简明教程王能超 编著7.4 高斯消去法 高斯消去法高斯消去法是约当消去法的一种改进。 高斯消去法的求解过程分为消元过程和回代过程两个环节。消 元过程将所给的方程组加工成上三角方程组。所归结的方程成组再 通过回代过程得出它的解。 高斯消去法由于添加了回代的过程，算法结构稍复杂，但这种 算法的改进明显减少了计算量。 数值分析简明教程王能超 编著7.5 选主元素 我们在高斯消去法的消元过程

26、中检查方程组中变元的各 系数，从中挑选出最大者，称之为第步的主元素。 设主元素在第个方程，即 若不等于，则我们先将第个方程与第个互易位置，使新的 成为主元素，这一手续称为选主元素选主元素。 ()()11 max kk lkik k i n aa = k x k l l ()1k kk a klk 数值分析简明教程王能超 编著7.6 三对角方程组 我们曾碰到下列形式的方程组 我们用矩阵记号将方程组简记作，这里系数矩阵 就是所谓的三对角阵，方程组就是所谓三对角方程组三对角方程组。 三对角方程组可用追赶法追赶法来求解。 1 11 11 2122232 121111 1 nnnnnnn nnnnn b

27、 xc xd a xb xc xd axbxcxd a xb xd += += += += ? Axd=A 数值分析简明教程王能超 编著7.7 追赶法的计算公式 解三对角方程组的追赶法追赶法分 “追” 和 “赶” 两个环节： (1) 追的过程（消元过程） 按顺序计算系数和； (2) 赶的过程（回代过程） 按逆序求出解。 其具体计算公式分别为： 12n uuu? 12n yyy? 11nn xxx ? () () () 111111 1 11 /,/ /,2,3, /,2,3, iiiii iiiiiii ucb ydb ucbu ain ydy abu ain = = = ? ? 1, 1,2

28、,1 nn iiii xy xyu xinn + = = ? Axd= 数值分析简明教程王能超 编著7.8 追赶法的代数基础 定理定理设三对角矩阵为对角占优，则它可唯一分解成下二对角 阵和单位上二对角阵的乘积： 事实上，追赶法的求解过程就是将系数矩阵分解两个简单的 二对角矩阵，从而归结为求解两个简单方程组的过程。 上述定理也表明，追赶法的原理和高斯消去法相同，但考虑到方 程组的特点，计算时会把大量零元素撇开，从而大大节省计算量。 A UL ALU= A 数值分析简明教程王能超 编著7.9 平方根法 线性方程组求解的难易程度取决于系数矩阵的特征， 当是三角阵时，方程组的求解特别方便。 对称正定方

29、程组就可归结为两个三角方程组和 来求解，由于矩阵分解的过程中含有开方运算，故 称此求解方法为平方根法平方根法，其具体求解过程分两步： (1) 由顺序计算： (2)由逆序计算： Axb= A A Axb=Lyb= T L xy= T ALL= Lyb= 12n yyy? 1 1 /,1,2, i iiikiii k ybl yl in = = ? T L xy= 11nn xxx ? 1 /,1,1 n iikikii k i xyl xl in n = + = ? 数值分析简明教程王能超 编著7.10 改进的平方根法 运用平方根法计算量较大，为了避免开方运算，改用单位三角 阵作为分解阵，于是对

30、称正定方程组就可归结为两个三 角方程组和来求解，其中为对角阵，称这 种求解方法为改进的平方根法改进的平方根法，亦称为乔累斯基方法乔累斯基方法，其计算公式 分别为 和 Lyb= 1T L xD y = 1 1 i iiikk k ybl y = =1,2,.,in= LAxb= D 1 n i iikk k i i y xl x d = + = ,1,.,1in n= 数值分析简明教程王能超 编著7.11 方程组的病态 考察方程组 和 上述方程组尽管只是右端项有微小扰动，但解大不相同： 一个 是，一个是。这类方程组称为病态病态的。 方程组的病态程度可由系数矩阵的条件数条件数 来刻画，条件数愈大，

31、扰动对解的影响愈大。 12 12 2 1.00012 xx xx += += 12 1xx= 12 2,0xx= 12 12 2 1.00012.0001 xx xx += += Axb=A ( ) 1 cond AAA= 数值分析简明教程王能超 编著7.12 精度分析 求得方程组的一个近似解以后，自然希望判断其精 度。检验精度的一个简单办法是，将近似解再代回到原方程组去 求出余量， 一般来说，如果很小，就认为解是相 当准确的。 定理定理 设是方程组的近似解，其精确解为，为 的余量，则有如下估计式： 上述定理表明，用余量大小检验近似解精度的方法对于病态方 程组是不可靠的。 x x x Axb= rbAx=? r x Axb= * xr x ( ) * * cond xx r A bx ?