计算方法概论与理论基础(1,2)

1、北京科技大学数理学院北京科技大学数理学院 卫宏儒卫宏儒科学与工程计算科学与工程计算公用邮箱： 密码：lhl213参考书：请看本教材的参考文献。课程性质和计划课程性质和计划计算方法计算方法概论概论数值计算的理论基础数值计算的理论基础矩阵特征值与特征向量的计算矩阵特征值与特征向量的计算方程组及非方程组及非线性方程的线性方程的数值解法数值解法线性方程组的解法线性方程组的解法非线性方程求根非线性方程求根数值逼近与曲线拟合数值逼近与曲线拟合数值逼近方法数值逼近方法常微分方程初值常微分方程初值(边值边值)问题的数值解法问题的数值解法插值法插值法数值积分与数值微分数值积分与数值微分计算方法计算方法概论概论数

2、值计算的理论基础数值计算的理论基础矩阵特征值与特征向量的计算矩阵特征值与特征向量的计算方程组及非方程组及非线性方程的线性方程的数值解法数值解法线性方程组的解法线性方程组的解法非线性方程求根非线性方程求根第一章第一章 计算方法概论计算方法概论 简要地介绍计算数学的一些基本概念。包简要地介绍计算数学的一些基本概念。包括计算数学的对象、应用和发展，计算机中数括计算数学的对象、应用和发展，计算机中数的浮点运算，误差的基本概念、问题的性态以的浮点运算，误差的基本概念、问题的性态以及算法的数值稳定性等及算法的数值稳定性等 ；1 1、计算数学引论、计算数学引论计算数学的对象；计算数学的对象；计算数学的应用与

3、发展；计算数学的应用与发展；2 2、算法及其效率、算法及其效率算法；算法；算法的计算量算法的计算量3 3、机器数系、机器数系4 4、误差的基本概念、误差的基本概念误差的来源误差的来源 模型误差；观测误差；截断误差；模型误差；观测误差；截断误差；舍入误差。舍入误差。误差与有效数字误差与有效数字 误差（绝对误差）；误差限；相误差（绝对误差）；误差限；相对误差；相对误差限；有效数字。对误差；相对误差限；有效数字。和、差、积、商的误差；和、差、积、商的误差；数据的机器浮点数数据的机器浮点数浮点数的算术运算浮点数的算术运算5 5、问题的性态与算法的数值稳定性、问题的性态与算法的数值稳定性良态与病态问题良

4、态与病态问题算法的数值稳定性算法的数值稳定性数值计算中值得注意的事项数值计算中值得注意的事项6 6、应用实例与、应用实例与MatlabMatlab 计算机解决实际问题的步骤计算机解决实际问题的步骤建立数学模型建立数学模型选择数值方法选择数值方法编写程序编写程序上机计算上机计算实际问题数学问题提供计算方法实际问题数学问题提供计算方法程序设计上机计算结果分析程序设计上机计算结果分析研究例子研究例子:求解线性方程组求解线性方程组其准确解为其准确解为x1=x2=x3=1604751413112134131216113121321321321xxxxxxxxx78. 020. 025. 033. 01

5、. 125. 033. 050. 08 . 133. 050. 0321321321xxxxxxxxx如把方程组的系数舍入如把方程组的系数舍入成两位有效数字成两位有效数字它的解为它的解为x1 =-6.222. x2=38.25 x3=-33.65. 研究数值方法的研究数值方法的设计设计、分析分析和和有有关理论关理论基础与基础与软件实现。软件实现。F 连续系统的离散化连续系统的离散化F 离散性方程的数值求解离散性方程的数值求解 串行计算方法串行计算方法与与并行计算方法并行计算方法的关系：并行的关系：并行计算方法计算方法70年代初随并行计算机的出现而产生，年代初随并行计算机的出现而产生，是计算数学

6、中最活跃的新领域。是计算数学中最活跃的新领域。算法算法：从给定的已知量出发，经过有限次四则运算从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。样构成的完整计算步骤称为算法。计算量计算量：一个算法所需的乘除运算总次数，单位是一个算法所需的乘除运算总次数，单位是flop.flop.计算量是衡量一个算法好坏的重要标准。计算量是衡量一个算法好坏的重要标准。例题：矩阵乘法的计算量。例题：矩阵乘法的计算量。F 规格化浮点数规格化浮点数 x= 0.a1 a2.at10c ai0,1,2,9, a10，

7、Lc U一般情况：一般情况： x= x= 0.a 0.a1 1 a a2 2.a.at tc ,c , =2,8,10,16,=2,8,10,16, a ai i 0,1,2,0,1,2, , -1, L-1, L c c U UF(F( ,t.L,U),t.L,U)表示以上数集全体加数表示以上数集全体加数0 0，它是计算机中使用有限离散集它是计算机中使用有限离散集。阶码尾数溢出错误 计算机中数的计算特点计算机中数的计算特点1. 加法先对阶加法先对阶,后运算后运算,再舍入。再舍入。2. 乘法先运算乘法先运算,再舍入。再舍入。3. 不在计算机数系中的数做四舍五入处理。不在计算机数系中的数做四舍五

8、入处理。例如例如:在四位浮点十进制数的计算机上计算在四位浮点十进制数的计算机上计算1+ 104 解解: 1+ 104 =0.1000 101+ 0.1000 105 = 0.00001 105 + 0.1000 105 (对阶计算对阶计算) = 0.10001 105 = 0.1000 105 = 1041、模型误差、模型误差2、观测误差、观测误差3、截断误差截断误差4、舍入误差舍入误差绝对误差：绝对误差：e = xe = x* * - x , x- x , x* * 是准确数是准确数 x x是近似数是近似数绝对误差限绝对误差限 ：|e| = |x|e| = |x* * - x|- x| 常表

9、示为常表示为x= x= x x* * 或或x x* * - - x x x x* * + + 相对误差：相对误差：e er r =(x =(x* *-x)/x-x)/x* * , x , x* * 是准确数是准确数, x, x是近似数是近似数相对误差限相对误差限 r r：|e|er r/ x/ x* *|= |x|= |x* * - x|/|x- x|/|x* *| | r r相对误差比绝对误差更能反映准确数与近似数的差异相对误差比绝对误差更能反映准确数与近似数的差异例例: :考虑考虑 1 1.x.x* * =10, x=11 e=-1 e=10, x=11 e=-1 er r=-0.1=-0

10、.1 2 2.x.x* * =1000, x=1001 e=-1 e=1000, x=1001 e=-1 er r=-0.001=-0.001 如果如果|e| = |x|e| = |x* * - x|- x| 0.5 0.5 10-k 称近似数称近似数x准确到小数点后第准确到小数点后第k位位,从这小从这小数点后第数点后第k位数字直到最左边非零数字之位数字直到最左边非零数字之间的所有数字都称为有效数字间的所有数字都称为有效数字. 用四舍五入得到的数都是有效数字用四舍五入得到的数都是有效数字有效数字越多有效数字越多,误差越小误差越小,计算结果越精确计算结果越精确.例如例如:设设x1=1.73, x

11、2=1.7321, x3=1.7320是其近似值是其近似值,问它们分问它们分别有几位有效数字别有几位有效数字?有三位有效数字故1221*105.010.20508.0.0020508.0|73.13|xxx有四位有效数字故3343*105 .010.508.0.0000508.0|7320.13|xxx有五位有效数字故2442*105.010.491.0.0000491.0|7321.13|xxx3*x四则运算的误差四则运算的误差绝对误差：绝对误差：e = xe = x* * - x =- x = x x dxdx 相对误差：相对误差：e er r =(x =(x* *-x)/x-x)/x*

12、* dx/dx/x=dlnxx=dlnx利用这个关系可以讨论四则运算的误差和函数的误利用这个关系可以讨论四则运算的误差和函数的误差。例如下列式子说明什么误差结果差。例如下列式子说明什么误差结果? ? d(x+y)=dx+dy d(x+y)=dx+dy dln(xy)=dlnx+dlny dln(xy)=dlnx+dlny dln(x dln(xn n)=ndlnx)=ndlnx 数值计算中值得注意的问题数值计算中值得注意的问题一、防止相近的两数相减一、防止相近的两数相减(会耗失许多有效数字会耗失许多有效数字,可以用数学公式化简后再做可以用数学公式化简后再做.)例例1: 各有五位有效数字的各有五

13、位有效数字的23.034与与22.993相减相减. 23.034-22.993=0.041 0.041只有两位有效数字只有两位有效数字,有效数字的耗失有效数字的耗失,说明准确说明准确度减小度减小,因此因此,在计算时需要加工计算公式在计算时需要加工计算公式,以免这种以免这种情况发生情况发生.例例2:当当x较大时较大时,计算计算xx 1xxxx111 化成二、防止大数吃小数二、防止大数吃小数. 当两个绝对值相差很大的数进行加法或减法运算当两个绝对值相差很大的数进行加法或减法运算时时,绝对值小的数有可能被绝对值大的数绝对值小的数有可能被绝对值大的数吃掉吃掉从而引从而引起计算结果很不可靠起计算结果很不

14、可靠. 例例:求一元二次方程求一元二次方程x2-(108 +1)x+108=0 的实数根的实数根. 采用因式分解法采用因式分解法,很容易得到两个根为很容易得到两个根为x1=108,x2=1.如采用字长为如采用字长为16位的单精度计算机来计算位的单精度计算机来计算,求得根为求得根为x1108 ,x20.(怎样计算可得较好的结果怎样计算可得较好的结果?) 两者结果不同两者结果不同,因为计算机计算时做加减法要因为计算机计算时做加减法要 “对对阶阶”,“对阶对阶”的结果使大数吃掉了小数的结果使大数吃掉了小数.产生了误差产生了误差.为为了避免由于上述原因引起的计算结果严重失真了避免由于上述原因引起的计算

15、结果严重失真,可以根可以根据一些具体情况据一些具体情况,存在需要把某些算式改写成另一种等存在需要把某些算式改写成另一种等价的形式价的形式.三、防止接近零的数做除数三、防止接近零的数做除数分母接近零的数会产生溢出错误分母接近零的数会产生溢出错误,因而产生大的误差因而产生大的误差,此时可以用数此时可以用数学公式化简后再做学公式化简后再做.四、注意计算步骤的简化四、注意计算步骤的简化, ,减小运算次数减小运算次数。 简化计算步骤是提高程序执行速度的关键，它不仅可以简化计算步骤是提高程序执行速度的关键，它不仅可以节省时间，还能减少舍入误差。节省时间，还能减少舍入误差。例例1：计算：计算9255的值，若

16、逐个相乘要用的值，若逐个相乘要用254次乘法，但若写成次乘法，但若写成 9255 = 9 92 94 98 916 932 964 9128只需做只需做14次乘法运算即可。次乘法运算即可。例例2：设：设A、B、C、D分别是分别是10 20、 20 50、 50 1、 1 100的的矩阵，试按不同的算法求矩阵乘积矩阵，试按不同的算法求矩阵乘积E=ABCD.解：由矩阵乘法的结合律，可有如下算法解：由矩阵乘法的结合律，可有如下算法1. E=(AB)C)D. 计算量计算量N=11500flop2. E=A(B(CD). 计算量计算量N=125000flop3. E=(A(BC)D. 计算量计算量N=2

17、200flop矩阵乘积矩阵乘积AB的计算量分析的计算量分析a11 a12 a13 a1na21 a22 a23 a2n. . . am1 am2 amm-1 amnb11 b12 b13 b1sb21 b22 b23 b2s. . . bn1 bn2 bnn-1 bns=cijms因为因为 cij= aik bkj 计算量为计算量为N所以上面所以上面A m n B n s的计算量为的计算量为N= m n s第二章第二章 数值计算的理论基础数值计算的理论基础 泛函分析这门现代数学学科，虽然起源于泛函分析这门现代数学学科，虽然起源于世纪，但形成一门系统的数学却是世纪的事；世纪，但形成一门系统的数学

18、却是世纪的事；它从早期数学的许多分枝中抽取精华，并且不断地它从早期数学的许多分枝中抽取精华，并且不断地加以系统化成为更一般的抽象形式。而数值计算却加以系统化成为更一般的抽象形式。而数值计算却是一门实用学科，主要以来自实际的数值问题为研是一门实用学科，主要以来自实际的数值问题为研究对象，虽然计算中用了非常复杂的现代工具，但究对象，虽然计算中用了非常复杂的现代工具，但本质上只是数的四则运算。表面上看来这两门学科本质上只是数的四则运算。表面上看来这两门学科没有什么联系，但事实上数值计算发生革命性变化没有什么联系，但事实上数值计算发生革命性变化的原因之一，正是运用了泛函分析。的原因之一，正是运用了泛函

19、分析。 本章介绍泛函分析中的一些基本概念。这一方本章介绍泛函分析中的一些基本概念。这一方面有利于后面各章中对数值问题的讨论；另一方面，面有利于后面各章中对数值问题的讨论；另一方面，通过数值问题导出泛函分析的一些概念，也有利于通过数值问题导出泛函分析的一些概念，也有利于我们理解泛函分析的一些内容。这样可以培养我们我们理解泛函分析的一些内容。这样可以培养我们建立和运用现代数学知识的意识。建立和运用现代数学知识的意识。 、距离与极限、距离与极限 距离是常见的概念之一。几何中线段的长度是距离是常见的概念之一。几何中线段的长度是其两个端点的距离，一个实数与其近似值的绝对其两个端点的距离，一个实数与其近似

20、值的绝对误差也是距离。仔细研究来自通常距离的一些结误差也是距离。仔细研究来自通常距离的一些结论，会发现它们所依赖的基础论，会发现它们所依赖的基础距离定义是很距离定义是很简单的，如果抛开直观的几何假设，可以把普通简单的，如果抛开直观的几何假设，可以把普通的距离概念推广到任何一个集合中的两个元素。的距离概念推广到任何一个集合中的两个元素。 定义如下：定义如下： 设设X X是一个非空集合，如果对任何一对元素，是一个非空集合，如果对任何一对元素，XX，都有一个实数（，）与之对应，而，都有一个实数（，）与之对应，而且满足下面两个条件：且满足下面两个条件： （）非负性（，）（）非负性（，），且（，且（，）

21、的充要条件是。）的充要条件是。 （）成立三角不等式（）成立三角不等式 （，）（，）（，）（，），（，）（，），X X 则称（，）是和两个元素之间的则称（，）是和两个元素之间的距离，而称定义了距离的非空集合距离，而称定义了距离的非空集合X X为度量空间或为度量空间或距离空间。记为（距离空间。记为（X X，），此时，），此时X X中的元素可称中的元素可称为点。为点。 根据上面的定义，容易得出距离还有对称根据上面的定义，容易得出距离还有对称性，即（，）（，），这与通常性，即（，）（，），这与通常的几何距离是一致的。定义抽取了通常距离概念的几何距离是一致的。定义抽取了通常距离概念中最本质的内容，利用这

22、定义不但可以描述通常中最本质的内容，利用这定义不但可以描述通常的距离，而且可以很容易地将这距离概念推广到的距离，而且可以很容易地将这距离概念推广到抽象的距离空间上。抽象的距离空间上。距离是衡量集合中两个元素距离是衡量集合中两个元素“相差相差”多少的一个量，这种多少的一个量，这种“相差相差”含义就是含义就是广义的距离广义的距离。它一般可以根据具体的集合和要讨它一般可以根据具体的集合和要讨论的问题来定义，需要指出的是，论的问题来定义，需要指出的是，同一集合上可同一集合上可以定义出几种不同的距离以定义出几种不同的距离。例如，由平面上的二例如，由平面上的二维点组成的集合维点组成的集合X X中，对任意的

23、，中，对任意的，XX，可定，可定义出至少如下三种距离义出至少如下三种距离(P26,(P26,例例2-1)2-1)。 （例（例2-2;2-3;2-4)2-2;2-3;2-4)。 极限极限 微积分中的极限描述的是一组变元的变化趋势，其微积分中的极限描述的是一组变元的变化趋势，其本质是通过本质是通过“充分靠近充分靠近”某个固定量引入的，而体现某个固定量引入的，而体现“靠近靠近”的描述正是距离的意思。因此，可以在距离空的描述正是距离的意思。因此，可以在距离空间中引入极限概念。间中引入极限概念。 定义定义2-3；定理；定理2-12 2、压缩映射、压缩映射例例2-5；2-6G的的映内性映内性和和压缩性压缩

24、性例例2-7定义定义2-6 3、内积、内积 (1)线性空间线性空间 通常集合中的元素并非是没有任何联系通常集合中的元素并非是没有任何联系的一堆的一堆“东西东西”，有些集合的元素之间可以，有些集合的元素之间可以进行运算，例如实数集中的元素就有加法进行运算，例如实数集中的元素就有加法和乘法等运算，当把看成是一般的集合，和乘法等运算，当把看成是一般的集合，并抽取实数上的某些运算性质，就得到比集并抽取实数上的某些运算性质，就得到比集合更为丰富的内容合更为丰富的内容线性空间。线性空间。 具体定义见具体定义见P29页。页。例例2-8；2-9；2-10。 复习线性相关，线性无关，线性子复习线性相关，线性无关

25、，线性子空间，基，生成子空间的定义。空间，基，生成子空间的定义。定义定义2-8，例，例2-11，2-12。 定义：设定义：设X是实数域是实数域R上的线性空间，如果任上的线性空间，如果任取，取， X，都对应着一个实数（，）满，都对应着一个实数（，）满足条件：足条件： （）对称性：（，）（，）（）对称性：（，）（，） （）齐次可加性：（）齐次可加性：（，），）（，）（，）（，）（，） ，R，X （）正定性：对任何（）正定性：对任何X，有（，），有（，），且（，）当且仅当，且（，）当且仅当， 则称（，）是则称（，）是X中的中的内积内积。称定义了内。称定义了内积的线性空间为积的线性空间为内积空间内积空

26、间。（2）内积空间与元素的夹角）内积空间与元素的夹角例：例：向量内积的定义。还有例向量内积的定义。还有例2-13。 定理中的不等式称为定理中的不等式称为不等式。不等式。 按例按例2-13中所定义的向量空间和函数空间中所定义的向量空间和函数空间上的内积上的内积 ，可以得到两个重要不等式。，可以得到两个重要不等式。 见见P31：；：；定义：内积空间两个元素的夹角；定义：内积空间两个元素的夹角；定义：内积空间两个元素正交；定义：内积空间两个元素正交；定义：内积空间的正交元素组；定义：内积空间的正交元素组；定理：定理：内积空间中的正交元素组一内积空间中的正交元素组一定线性无关。定线性无关。 4、范数、

27、范数 范数是与距离相类似的概念，不范数是与距离相类似的概念，不过范数是定义在线性空间上的，它过范数是定义在线性空间上的，它利用了线性空间的代数结构，范数利用了线性空间的代数结构，范数的本质是描述线性空间中元素的的本质是描述线性空间中元素的“长度长度”或或“大小大小”，它也能表示，它也能表示元素之间的距离。元素之间的距离。在误差估计和迭在误差估计和迭代法的收敛性研究中具有很重要的代法的收敛性研究中具有很重要的作用。作用。几个基本概念及性质几个基本概念及性质 1. 向量范数向量范数： 对任一向量对任一向量X，按一定规则确定一个实数与，按一定规则确定一个实数与其相对应，该实数记为其相对应，该实数记为|X|，若，若|X|满足下满足下面三个性质：面三个性质： （1）|X| 0，|X|=0当且仅当当且仅当X=0。 （2）对任意实数）对任意实数 ，| X|=| | |X|。 （3）对任意向量）对任意向量Y Rn，|X+Y| |X|+|Y|。 则称该实数则称该实数|X|为向量为向量X的范数的范数