《计算方法》第一章 绪论

1、1计 算 方 法计算方法课程组华中科技大学数学与统计学院第一章第一章 绪绪 论论2 1 1 绪绪 论论 1.1 数值算法概论数值算法概论 1.2 预备知识预备知识 1.3 误差误差 1.4 题型分析与小结题型分析与小结3 “ “计算方法计算方法”是计算数学的一个主要部分。而计是计算数学的一个主要部分。而计算数学是数学科学的一个重要分支，它算数学是数学科学的一个重要分支，它研究用计算研究用计算机求解数学问题的数值计算方法及其软件实现机求解数学问题的数值计算方法及其软件实现. . 数值计算已经成为计算机处理实际问题的一种数值计算已经成为计算机处理实际问题的一种关键手段，它使各科学领域从定性分析阶段

2、走向定关键手段，它使各科学领域从定性分析阶段走向定量分析阶段，从粗糙走向精密。量分析阶段，从粗糙走向精密。 科学理论、科学试验和科学计算科学理论、科学试验和科学计算( (计算的方法计算的方法) )是现代科学的三个组成部分。是现代科学的三个组成部分。1.1 1.1 数值算法概论数值算法概论4 方程求解方程求解 非线性方程或方程组、常微分方程、偏微分非线性方程或方程组、常微分方程、偏微分方程数值解法。方程数值解法。 数值代数数值代数 求解线性方程组的解法（分直接方法和间接求解线性方程组的解法（分直接方法和间接方法），求矩阵的特征值与特征向量。方法），求矩阵的特征值与特征向量。 数值逼近数值逼近 插

3、值和数值逼近，数值微分和数值积分。插值和数值逼近，数值微分和数值积分。 1.1 1.1 数值算法概论数值算法概论研究内容研究内容 5例如例如: :03832 xx 1 , 0*x1. 求方程求方程在在上的根上的根;；2. 求解线性方程组求解线性方程组 , 其中其中为为3阶可逆方阵阶可逆方阵,AXb A123(,)TXx xx 为为3. 已知已知上的直线，满足上的直线，满足求求 ；)(xPy ,10 xx(),00P xy(),11P xy(,),01xx x)(xP4. 计算定积分计算定积分badxxI1)1 (ba 5. 解常微分方程初值问题解常微分方程初值问题00()yxyy xy 6 计

4、算方法是一门与计算机应用密切结合的实计算方法是一门与计算机应用密切结合的实用性很强的学科；思维方法是归纳法，核心问题用性很强的学科；思维方法是归纳法，核心问题是是“误差误差”或或误差分析误差分析。 计算方法这门课程讨论连续变量问题又要讨计算方法这门课程讨论连续变量问题又要讨论离散变量问题，关心的是论离散变量问题，关心的是数值结果数值结果。 计算方法、计算数学、数值分析或数值方法计算方法、计算数学、数值分析或数值方法这门课程已成为近代数学的一个重要分支。这门课程已成为近代数学的一个重要分支。1.1 1.1 数值算法概论数值算法概论研究对象研究对象 7 面向计算机面向计算机 将计算机上不能执行的运

5、算化为在计算机上可执行的将计算机上不能执行的运算化为在计算机上可执行的运算。运算。 有可靠的理论分析有可靠的理论分析（收敛性、稳定性、误差分析）。（收敛性、稳定性、误差分析）。 因为可能采用了近似等价运算因为可能采用了近似等价运算, ,故要进行误差分析故要进行误差分析, ,即即数值的性态及数值方法的稳定性。数值的性态及数值方法的稳定性。 要有好的算法，并考虑计算复杂性要有好的算法，并考虑计算复杂性（时间、空间）（时间、空间） 针对所求解的数值问题研究在计算机上可执行的且有针对所求解的数值问题研究在计算机上可执行的且有效的计算公式。效的计算公式。 要有数值试验要有数值试验1.1 1.1 数值算法

6、概论数值算法概论特点特点 8现实科学与工程问题的解决步骤：现实科学与工程问题的解决步骤：实际问题实际问题建立数学模型建立数学模型构造数值算法构造数值算法编程上机编程上机获取近似结果获取近似结果计算方法是一种研究并计算方法是一种研究并解决数学问题的数值解决数学问题的数值近近似解似解方法方法 随着计算机的飞速发展，数值分析随着计算机的飞速发展，数值分析方法已深入到计算物理、计算力学、方法已深入到计算物理、计算力学、计算化学、计算生物学、计算经济学计算化学、计算生物学、计算经济学等各个领域。本课仅介绍最常用的数等各个领域。本课仅介绍最常用的数学模型的最基本的数值分析方法学模型的最基本的数值分析方法。

7、1.1 1.1 数值算法概论数值算法概论数值算法数值算法 9 良态与病态问题良态与病态问题 良态与病态良态与病态: : 初始数据的的微小变化初始数据的的微小变化( (扰动扰动) )，导致计算结果的，导致计算结果的相相对误差很大对误差很大，这样的问题称为，这样的问题称为病态病态的，相反称为的，相反称为良态良态的。的。 1.1 1.1 数值算法概论数值算法概论算法的数值稳定性算法的数值稳定性 例：例：蝴蝶效应蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和日丽的北京纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！就刮起台风来了？！NYBJ误差的传播与积累误差的传播与积累导致以上问题是一个导致以上问题

8、是一个病态问题病态问题10良态与病态问题良态与病态问题 2* ( )1150 x100 /3f xxx在 的值?1.1 1.1 数值算法概论数值算法概论算法的数值稳定性算法的数值稳定性 例例1 111良态与病态问题良态与病态问题 2* ( )1150 x100 /3f xxx在的值?1.1 1.1 数值算法概论数值算法概论算法的数值稳定性算法的数值稳定性 50 f100/35.6 9 f3328 , . （），（） 该函解数是病态的：例例1 112良态与病态问题良态与病态问题 例例1 2* ( )1150 x100 /350 f100/35.6 9 f3328 , .fxxx在的 值解 ： （

9、） ，（） 该 函 数 是 病 态 的%.40095028950)()()(, %1310031, 4 .22)()(, 34. 031*xfxfxfxxxxfxfxx1.1 1.1 数值算法概论数值算法概论算法的数值稳定性算法的数值稳定性 分析分析: :13例例2 2dxxxInn105计算计算数值稳定性分析数值稳定性分析14例例2 2dxxxInn105计算计算数值稳定性分析数值稳定性分析15例例2 2dxxxInn105计算计算数值稳定性分析数值稳定性分析16dxxxInn105例例2(2(续续) )11111005155nnnnnxxIIdxxdxxn 构造算法如下：构造算法如下：10

10、165 , ln5nnIIIn nI 1.1811 , 0.0195nnIIIn nI2.17n n0 00.18200.18200.18200.18200.18200.18201 10.08800.08800.09000.09000.08800.08802 20.05800.05800.05000.05000.05800.05803 30.04310.04310.08300.08300.04310.04314 40.03430.0343-0.165-0.1650.03430.03435 50.02840.02841.02501.02500.02840.02846 60.02400.0240-

11、4.958-4.9580.02400.02407 70.02100.021024.93324.9330.02100.02108 80.01900.0190-124.540-124.5400.01900.0190nInI nI105nnxIdxx 01811615 , ln51 12 , 0.0195nnnnnnIInnIIIIII 18对格式对格式1 1，如果前一步有误差，如果前一步有误差， 则被放大则被放大5 5倍加到这一步倍加到这一步称为不稳定称为不稳定格式格式对格式对格式2，为，为稳定格式，对舍入误差有抑制作用稳定格式，对舍入误差有抑制作用01811615 , ln51 12 , 0.0

12、195nnnnnnIInnIIIIII 原因：19例如例如:求解微分方程求解微分方程:0)0(32yxy23yxx 其其解解: :针对输入与输出的都是数值的数学问题针对输入与输出的都是数值的数学问题.1.1 1.1 数值算法概论数值算法概论数值算法数值算法 20例如例如:求解微分方程求解微分方程:0)0(32yxy23yxx 其其解解: :将其变成数值问题，即将其将其变成数值问题，即将其“离散化离散化”12(),(),()nyxyxyx“离散化离散化”是将非数值问题的数学模型化为数值问题是将非数值问题的数学模型化为数值问题的主要方法，这也是计算方法的任务之一的主要方法，这也是计算方法的任务之一

13、.121,niixxxxxh 针对输入与输出的都是数值的数学问题针对输入与输出的都是数值的数学问题.()( )( )y xhy xy xh1.1 1.1 数值算法概论数值算法概论数值算法数值算法 21Rn空间的向量范数空间的向量范数 | | 对任意对任意 , ,满足下列条件：满足下列条件：nxR(1)|0; |00 xxx（正定性正定性)对任意对任意(2) | | | |xxC (齐次性齐次性) (3) | | | | |xyxy（三角不等式三角不等式)1.2 1.2 预备知识预备知识向量范数向量范数22TnnnxxxxCR),(,)(21设中在向量空间21222212)xxx(xn 范数或欧

14、氏范数的 2x1xnxxx21范数的1xxinix1max范数或最大范数的x-(1)-(2)-(3)pxppnppxxx121)(-(4)1,ppx范数的常用的向量x的范数有23下述范数的几何意义是下述范数的几何意义是: :2121max(,)xxxyy21211xxxyy2221212()()xyyxx24求下列向量的各种常用范数求下列向量的各种常用范数Tx)1,3,4,1(25求下列向量的各种常用范数求下列向量的各种常用范数Tx)1,3,4,1(:1x421xxx92x21242221)(xxx3327 xiix41max41 1* *499/4499/4* *4=94=9即即本例中本例中

15、显然显然, 211 xcxxc,26范数等价的定义: 设设A A 和和B B 是是R R上任意两种范数，若存在上任意两种范数，若存在常数常数 C1、C2 0 0 使得使得|1BA2BCxxCx则称则称 和和 等价等价。| |Bx| |Ax Rn 上上一切范数一切范数都等价都等价。定理定理1 1272x和1x显然显然时的特例和在是21ppxp并且由于并且由于ppnppxxx121)(inix1maxppinixn11)max(inipxn11max)(max1pxini x所所以以的特例也是px),(时pxxp12xxx且:一般有向量的等价关系一般有向量的等价关系 )c,c;1,2,qp,q,(

16、p 2121 Rxcxxcpqp28 对对 任意一种向量范数任意一种向量范数而言，向量序列而言，向量序列xk k收敛于向量收敛于向量x* *的充分必要条件是的充分必要条件是*lim |0kkxx 定理定理2 2nR29定义定义：设是一种向量范数是一种向量范数AxxAxAxRxxRxnn1,0,supsup称之为由向量范数派生的称之为由向量范数派生的矩阵算子范数矩阵算子范数.定义定义 设设 是以是以n n阶方阵为变量的实值函数阶方阵为变量的实值函数, ,且满足条件且满足条件: : (1) 非负性非负性: : A0 ,且A=0当且当且仅当仅当A=0=0 (2) 齐次性齐次性: : A=| |A,

17、R (3) 三角不等式三角不等式: :A+BA+B (4) 相容性相容性: : ABAB则称则称A为矩阵为矩阵A的的范数范数. 1.2 1.2 预备知识预备知识矩阵范数矩阵范数( (续续) ) 30常用的矩阵范数常用的矩阵范数1(1)Aniijnja11max,大值的每列绝对值之和的最A的列范数称A A(2)njijnia11max,大值的每行绝对值之和的最A的行范数称A2(3)A)(maxAAT大大值值的的特特征征值值的的绝绝对对值值的的最最为为其其中中AA)AA(TTmax范范数数的的称称 2A-(5)-(6)-(7) ninjijFaA112| 向量向量| |2的推广的推广 Froben

18、ius Frobenius 范数范数(4)-(8)31110121021A求矩阵求矩阵A A的各种常用范数的各种常用范数1Aniijnja11max25234252 ,5 ,2max1njAnjijnia11max42 ,4 ,3max1ni2A)(maxAAT由于由于32110121021A求矩阵求矩阵A A的各种常用范数的各种常用范数2A)(maxAAT由于由于的特征值因此先求AATAAT110121021110122011211190102特征方程为特征方程为)det(AAIT211190102033110121021A求矩阵求矩阵A A的各种常用范数的各种常用范数2A)(maxAAT由

19、于由于的特征值因此先求AAT特征方程为特征方程为)det(AAIT2111901020的特征值为可得AAT9361. 0,9211. 2,1428. 93211428. 9)(maxAAT2A)(maxAAT3.0237342A)(maxAAT0237. 3FA2926056. 31AA2AFA51 A4 A110121021A35称的特征值为设,21nnnRA,max)(21nA的谱半径为矩阵A-(9)显然显然2A)(maxAAT)(AATReIm 36设设A为为n阶方阵阶方阵,则对任意算子范数则对任意算子范数 | | 有有(A) | A |证明：证明：由算子范数的相容性，得到由算子范数的相

20、容性，得到| | |AxAx将任意一个特征根将任意一个特征根 所对应的特征向量所对应的特征向量 代入代入u| | |AuAu| | | |uu.即即 A A . . 故故( (A A) ) A A 定理定理3 3任何一种算子范数的谱半径不超过矩阵的即矩阵A37若若A对称，则有对称，则有)(|2AA 证明：证明：)()(|2maxmax2AAAAT 若若 是是 A 的一个特征根，则的一个特征根，则 2 必是必是 A2 的特征根。的特征根。又对称矩阵的特征根为实数，即又对称矩阵的特征根为实数，即 2(A) 为非负实数，为非负实数，故得证。故得证。)()(22maxAA 对某个对某个 A 的特征根的

21、特征根 成立成立定理定理4 438定理定理.,nnnnRAR上的一种算子范数是设且非奇异则满足若, 1AIAAAAI11)(1证明证明:略略39 现现 实实 世世 界界 研 究研 究对 象对 象测 量测 量数 据数 据建立数学模型建立数学模型构成数值算法构成数值算法数值运算的执行数值运算的执行测 量测 量误 差误 差模型误差模型误差方法误差方法误差舍入误差舍入误差1. 3. 1. 3. 误差的种类及来源误差的种类及来源40I.I. 总体设计总体设计( (含数学模型的建立与模型细化等含数学模型的建立与模型细化等) )II.II. 详细设计详细设计( (主要是算法设计主要是算法设计),),包括：包

22、括： (1) (1) 连续系统的离散化连续系统的离散化; ; (2) (2) 离散型方程的数值求解离散型方程的数值求解. .III.III.实验验证实验验证以计算机为工具解决实际问题需经历三个过程：以计算机为工具解决实际问题需经历三个过程：41(1) 模型误差模型误差 在建立数学模型过程中在建立数学模型过程中, 要将复杂的现象抽象要将复杂的现象抽象归结为数学模型归结为数学模型, 往往要忽略一些次要因素的影往往要忽略一些次要因素的影响响, 而对问题作一些简化而对问题作一些简化, 因此和实际问题有一因此和实际问题有一定的区别。定的区别。(2) 观测误差观测误差 在建模和具体运算过程中所用的数据往往

23、是在建模和具体运算过程中所用的数据往往是通过观察和测量得到的通过观察和测量得到的, 由于精度的限制由于精度的限制, 这这些数据一般是近似的些数据一般是近似的, 即有误差。即有误差。42(3) 截断误差截断误差 由于计算机只能完成有限次算术运算和逻辑运由于计算机只能完成有限次算术运算和逻辑运算算,因此要将有些需用极限或无穷过程进行的运算因此要将有些需用极限或无穷过程进行的运算有限化有限化,对无穷过程进行截断对无穷过程进行截断,这就带来误差。这就带来误差。(4) 舍入误差舍入误差 在数值计算过程中还会遇到无穷小数在数值计算过程中还会遇到无穷小数, ,因计算机因计算机受到机器字长的限制受到机器字长的

24、限制, ,它所能表示的数据只能有一它所能表示的数据只能有一定的有限位数定的有限位数, ,如按四舍五入规则取有限位数如按四舍五入规则取有限位数, ,由由此引起的误差。此引起的误差。43! 3! 2132xxxex! 7! 5! 3sin753xxxxx! 4! 3! 2)1ln(432xxxxx如如:若将前若干项的部分和作为函数值的近似公式若将前若干项的部分和作为函数值的近似公式, ,由于以后各项都舍弃了由于以后各项都舍弃了, ,自然产生了误差。自然产生了误差。TaylorTaylor展开展开 截断误差截断误差4414159265.3414213562. 12 166666666. 061! 3

25、11415927. 34142136. 12 16666667. 0! 31 数学模型一旦建立数学模型一旦建立, ,进入具体计算时所考虑和进入具体计算时所考虑和分析的就是分析的就是截断误差和舍入误差截断误差和舍入误差. . 舍入误差舍入误差45u 绝对误差绝对误差* ex x其中其中 x*为精确值，为精确值，x为为x*的近似值。的近似值。 10006074302.dxex例如：例如：*xx工程上常记为工程上常记为|*e*的上限记为的上限记为 , , 称为称为绝对误差限绝对误差限。 u 相对误差相对误差*reex*|rxx 的的相对误差上限相对误差上限 定义为定义为2. 2. 误差与有效数字误差

26、与有效数字46u 有效数字有效数字12010mnx.a aa 01 ananm 10用科学计数法，记用科学计数法，记其中其中nm.xx 1050|*x若若则称则称有有n 位有效数字，精确到位有效数字，精确到 。，的截取按四舍五入规则的截取按四舍五入规则47例例4解解: :*| |0.000 00182ee 002000. 06102|*er28718. 2102628718. 2102661071. 02.718 28182,e *2.718 28,e *e已知近似值为已知近似值为: :精确值为精确值为: :求求 的绝对误差、相对误差的绝对误差、相对误差绝对误差绝对误差相对误差相对误差*|re

27、 或或4810 3141510 *.,证明：证明：3.1415926535897932; 例例5问：问： 有几位有效数字？请证明你的结论。有几位有效数字？请证明你的结论。* *3.1415 31 4*0.0000926. 0.0005 0.5*1005 10 |.有有4 位有效数字，位有效数字，*精确到小数点后第精确到小数点后第 3 位。位。49数值算法数值算法是是从给定的已知量出发，经过有限次四则运算从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。的完整计算步骤称为算法。数值算法

28、有四个特点数值算法有四个特点: :(1)(1)目的明确目的明确算法必须有明确的目的算法必须有明确的目的, ,其条件其条件和结论均应有清楚的规定和结论均应有清楚的规定(2)(2)定义精确定义精确对算法的每一步都必须有精确的定义对算法的每一步都必须有精确的定义(3)(3)算法可执行算法可执行算法中的每一步操作都是可执行的算法中的每一步操作都是可执行的(4)(4)步骤有限步骤有限算法必须在有限步内能够完成解题算法必须在有限步内能够完成解题过程过程1.4 1.4 题型分析与小结题型分析与小结 - - 算法和计算量算法和计算量50计算量：计算量：一个算法所需的乘除运算总次数，单位是一个算法所需的乘除运算

29、总次数，单位是flop. 计算量是衡量算法好坏的一个重要标准。计算量是衡量算法好坏的一个重要标准。例例1 求求 Ax=b， Det(A)0，A=(aij)20 20的计算量。的计算量。结论：结论：分析算法的效率，选择算法非常重要。分析算法的效率，选择算法非常重要。解解：2. 使用使用Gauss消去法，消去法， n=20， N3060次次= O(n3 /3)次次.解：解：1. 用用Cramar法则求解，总的计算量法则求解，总的计算量 N = ( ( n+1)(n-1)n!+n) 次次 当当n=20, N9.7 1020 次次. 以一台以一台10亿亿/秒的计算机需约秒的计算机需约3万年万年.511

30、210( )( ( ()nnnnP xx x xx a xaaaa101,2,1,0( )nnkkknsasxsaknP xs1110( )nnnnnP xa xaxa xa例例2 计算计算n 次多项式次多项式 的值。的值。 算法算法: 采用采用秦九韶算法秦九韶算法(1247) (又称为又称为Horner算法算法(1819)计算计算 说明：说明：算法算法需乘法需乘法n次，加法次，加法n次，存储单元次，存储单元n+3个。个。52上述秦九韶算法的结构是递归的，它通过一次式上述秦九韶算法的结构是递归的，它通过一次式的反复计算，逐步降低多项式的次数，直到归结为零次式为止的反复计算，逐步降低多项式的次数

31、，直到归结为零次式为止。若以多项式的次数（或项数）定义为求值问题的规模，若以多项式的次数（或项数）定义为求值问题的规模，秦九韶算法的特点秦九韶算法的特点: : 在递归计算的过程中问题的规模逐次减在递归计算的过程中问题的规模逐次减1。1kkksxsa53算法算法程序程序QinJiushao.m1.1.输入多项式系数输入多项式系数function s=QinJiushao(a,x) n=length(a); s=a(1); for k=2:n s=s*x+a(k); end实例实例运行及结果运行及结果求多项式求多项式 a=1 -3 0 4 -1 1; s=QinJiushao(a,3)s = 34

32、01,na aa542( )341p xxxxx 在在 时的值时的值. 3x 及 ;x2.2.迭代计算迭代计算101,2,1,0( )nnkkknsasxsaknP xs 3.3.输出结果输出结果注注: 编写程序时多项式系数按降幂排列编写程序时多项式系数按降幂排列.54 例例3 计算计算x255的复杂度的复杂度 1. 计算计算 X255 = X X X X X 工作量：工作量：N254 flop 254个个乘法乘法2. 计算计算 X255 = X X2 X4 X8 X16 X32 X64 X128 工作量：工作量：N14 flop ，8个储存空间个储存空间 556047514131121341

33、31216113121 321321321xxxxxxxxx78. 020. 025. 033. 01 . 1 25. 033. 0.5008 . 133. 0.500 321321321xxxxxxxxx例例1 求解线性方程组解求解线性方程组解: :则其解为则其解为x1=-6.222, x2=38.25 , x3=-33.65, 可见这是一个可见这是一个病态问题病态问题(初始初始数据的的微小变化数据的的微小变化(扰动扰动)，导，导致计算结果的相对误差很大致计算结果的相对误差很大)与解法无关与解法无关.二二. .求解线性方程组求解线性方程组方程组的准确解为方程组的准确解为 x1=x2=x3=1

34、若把方程组的系数舍入为两位有效数字若把方程组的系数舍入为两位有效数字,变为变为56解解: x x1 1=10=109 9, , x x2 2=1=1.算法算法A: xA: x1,21,2= (- b= (- b sqrt sqrt (b (b2 2- 4ac)/ 2a,- 4ac)/ 2a,出现小误差时有出现小误差时有, , - b = 10- b = 109 9+1 = 0.10000000+1 = 0.10000000101010 10 + 0.000000001+ 0.00000000110101010 = 0.10000000= 0.1000000010101010 而而 b b2 2

35、- 4ac b- 4ac b2 2 , , sqrtsqrt (b (b2 2- 4ac) - 4ac) b b 于是于是 x x1 1= (- b+= (- b+|b|)/2 = |b|)/2 = 0.10000000 0.10000000 10101010, , x x2 2= (- b-= (- b-|b|)/2 = |b|)/2 = 0 0算法算法B: x x1 1 = ( - b= ( - b- sign(b)- sign(b) sqrt(sqrt(b b2 2- 4ac)/ 2a- 4ac)/ 2a x x2 2 = c/ax= c/ax1 1则则 x x1 1 = 0.10000

36、000= 0.10000000101010 10 =10=109 9 x x2 2 = 0.10000000= 0.1000000010101 1 = 1= 1 算法算法A A不稳定不稳定; ;算法算法B稳定稳定, ,算法算法B准确准确.结论结论:良态问题选择稳定算法良态问题选择稳定算法,才能得到满意解才能得到满意解大数大数”吃掉吃掉”小数小数 例例2: 2: 求解求解 x2 +(-10 x2 +(-109 9-1) x + 10-1) x + 109 9=0=057例例3.,28718. 2,82281718. 2*reee和相对误差限的绝对误差限求其近似值为已知解:eeE*绝对误差8200

37、1000. 082001000. 0|E002000. 061026102|*er28718. 2102628718. 2102661071. 0是唯一的并不和*r58例例4 4.,7 ,5 ,3求绝对误差限位数的近似值经四舍五入取小数点后若解:65592141. 359141. 3*142. 3*7592141. 3*|*407000. 065002000. 004000000. 03105 . 05105 . 07105 . 0可见,经四舍五入取近似值,其绝对误差限将不超过其末位数字的半个单位59例例5 5：为使：为使 的相对误差小于的相对误差小于0.001%, ,至少应取几位有效数字？至少应取几位有效数字？*解：假设