数值分析与科学计算引论课件

1、第1章 数值分析与科学计算引论1.1 数值分析的对象、作用与特点什么是数值分析(Numerical Analysis)？数值分析是计算数学的一个主要部分,计算数学是数学科学的一个分支,它研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现。实际问题数学模型数值计算方法 程序设计上机计算求出结果数值分析的基本内容计算机只能进行加减乘除四则运算和一些简单的函数计算(即使是函数也是通过数值分析方法处理，转化为四则运算而形成了的一个小型论软件包)。数值代数：求解线性和非线性方程的解法插值和数值逼近数值微分和数值积分常微方程数值解法和偏微方程数值解法数值分析的特点面向计算机，要根据计算机的特点提

2、供切实可行的有效算法有可靠的理论分析，能任意逼近并达到精度要求。要有良好的计算复杂性，时间复杂性和空间复杂性。要有数值实验，即任何一个算法除从理论上要满足上述三点外，还要通过数值试验证明是行之有效的。例：求解一个20阶线性方程组，用加减消元法需3000次乘法运算；而用克莱姆（Cramer）法则要进行9.7*1020次运算，若用每秒亿次乘法运算的计算机要30万年。 例: 一元二次方程x2-(109+1)x+109=0其精确解为X1=109, X2=1。如用求根公式和字长为8位的计算器求解,有与精确解有天壤之别。,若因此,算法的选用很重要。 1.2 数值计算的误差(Error)误差来源与分类模型误

3、差观测误差截断误差(Truncation Error) 舍入误差(Round-off Error)用数学方法解决一个具体的实际问题，首先要建立数学模型，这就要对实际问题进行抽象、简化，因而数学模型本身总含有误差，这种误差叫做模型误差数学模型是指那些利用数学语言模拟现实而建立起来的有关量的描述数学模型的准确解与实际问题的真解不同实际问题的真解数学模型的真解为减化模型忽略次要因素定理在特定条件下建立与实际条件有别模型误差在数学模型中通常包含各种各样的参变量，如温度、长度、电压等，这些参数往往是通过观测得到的，因此也带来了误差，这种误差叫观测误差数学模型中的参数和原始数据，是由观测和试验得到的由于测

4、量工具的精度、观测方法或客观条件的限制,使数据含有测量误差,这类误差叫做观测误差或数据误差根据实际情况可以得到误差上下界数值方法中需要了解观测误差,以便选择合理的数值方法与之适应观测误差精确公式用近似公式代替时,所产生的误差叫截断误差 例如, 函数f(x)用泰勒(Taylor)多项式 截断误差（介于0与x之间）近似代替，则数值方法的截断误差是 截断误差的大小直接影响计算结果的精度和计算 工作量，是数值计算中必须考虑的一类误差在数值计算中只能对有限位字长的数值进行运算需要对参数、中间结果、最终结果作有限位字长的处理工作，这种处理工作称作舍入处理用有限位数字代替精确数，这种误差叫做舍入误差，是数值

5、计算中必须考虑的一类误差舍入误差误差与有效数字(Significant digits/figures)定义1 绝对误差absolute error，简称误差：误差限：相对误差relative error ：相对误差限：定义2 例1 42.195, 0.0375551, 8.00033, 2.71828,按四舍五入写出上述各数具有四位有效数字的近似数.例2 考察三位有效数字重力加速度g,若以m/s2为单位, g9.80m/s2, 若以km/s2为单位, g0.00980km/s2,解1：若取近似值x*=3.1415，绝对误差是0.0000926，有，即m=0,n4，故近似值x*=3.1415只有

6、4位有效数字解2：x*3.1415的绝对误差限0.0005，它是x的小数后第3位的半个单位，故近似值x*=3.1415准确到小数点后第3位故近似值x*=3.1415只有4位有效数字例3 设x= =3.1415926，求x*=3.1415近似值的有效数字定理 例4 解：设取n位有效数字，相对误差限*r=，例5 指出下列各数具有几位有效数字，及其绝对误差限和相对误差限：0.002 009 000.00解 因为x1*=0.002 00， m=3绝对误差限0.000 005= 因为m=3，n=3，x1*= 0.002 00有3位有效数字. a1=2，相对误差限r=x2*=9 000.00，绝对误差限0

7、.005，因为m=3，n=6，x2*=9 000.00有6位有效数字，相对误差限为r 如果认为小数点后边的0无用，将9 000.00随便写作90009103，那么它的绝对误差就是=0.5=0.51034+1，即m=3，n=4，表明这个数有4位有效数字可见，小数点之后的0，不是可有可无的，它是有实际意义的.数值运算的误差估计误差分析简介 向后误差分析法区间分析法概率分析法1.3 误差定性分析、避免误差危害算法的数值稳定性考虑初始数据误差在计算中的传播问题. 方案（A）不稳定，方案（B）稳定设计算法时应遵循的原则要有数值要稳定性,即能控制误差的传播.避免大数吃小数,即两数相加时,防止较小的数加不到

8、较大的数上.避免两相近的数相减,以免有效数字的大量丢失.避免分母很小(或乘法因子很大),以免产生溢出.避免误差危害的若干原则除了分清问题是否病态和算法是否数值稳定外,还要考虑避免误差危害和防止有效数字损失的如下原则：1.避免大数除以小数例 仿计算机，采用3位十进制，用消元法求解方程组 解：错.为什么,怎么办？减少运算误差源2、两个相近的数相减，会严重损失有效数字 例如x =1958.75，y =1958.32都具有五位 有效数字，但x-y=0.43只有两位有效数字 通常采用的方法是改变计算公式,例如当与 很接近时,由于用右端代替左端公式计算,有效数字就不会损失 当x很大时可作相应的变换 则用右

9、端来代替左端。 减少运算误差源减少运算误差若干原则当x接近0时 一般情况，当f(x)f(x*)时，可用泰勒展开 取右端的有限项近似左端。 如果计算公式不能改变，则可采用增加有效位数的方法保证精度 例 仿计算机在3位十进制下，、防止大数吃小数例 求二次方程x2-105x+1=0的根 解：按二次方程求根公式 x1=(105+(1010-4)1/2)/2 x2=(105-(1010-4)1/2)/2 在8位浮点数计算得 x1=(105+105 )/2=105 (正确）, x2=(105-105 )/2=0 (错误）产生错误的原因 出现大数1010吃掉小数4的情况 分子部分出现两个相近数相减而丧失有

10、效数位常称为灾难性的抵消4、绝对值太小的数不宜做除数当分母为两个相近数相减时,会丧失有效数字这里分子的误差被扩大104倍,再如若将分母变为0.0011,即分母只有0.0001的变化时,计算结果却有了很大变化 例 计算 解: 分子分母分别计算后相除(取9位小数)A=0.0005*0.0143*0.0012=0.00000715*0.0012 =0.000000009(有舍入)B=0.0003*0.0125*0.0135=0.00000375*0.0135 =0.000000051(有舍入)D=A/B=0.17647真值为0.16948148，所以D只准确到小数后一位 算法2：分成三组因子。每组只

11、取六位小数计算 a=0.0005/0.0003=1.666667(有舍入) b=0.0143/0.0125=1.144000 c=0.0012/0.0135=0.088889 (有舍入) D=a*b*c=1. 666667* 1.144000* 0.088889 =0.169482,准确到小数后5位。bca5、简化计算步骤，减少运算次数减少运算次数可以不但节省时间，而且减少舍入误差 例x255=xx2x4x8x16x32x64x128 原先要做254次乘法现只需14次即可 例 如计算多项式 p(x)=anxn an-1xn-1 a1x a0 的值 若直接计算akxk,再逐项相加，一共要做 n+

12、(n-1)+2+1=n(n+1)/2次乘法和n次加法 如果将前n项提出x，则有 p(x)=（anxn-1 an-1xn-2 a1 ）x a0 =(anxn-2an-1xn-3 a2)xa1）x a0 =(anx an-1)xa2)x a1)x a0写成递推公式 于是 ,这种多项式求值的算法称为秦九韶算法,只做n次乘法和n次加法,程序实现简单 1.5 数学软件针对高级语言(FORTRAN,C,C+)的通用软件包LAPACKIMSL (International Mathematical and Statistical Libraries)NAG (Numerical Algorithms Gro

13、up)Maple和Mathematic符号计算、数值计算和工作表的特性MATLAB针对矩阵计算的数值计算系统Python开源多用途解释语言，MIT教学用语言，与多种系统嵌入式使用第1次软件危机(The first Software Crisis)60s-70s，汇编语言Assembly Language Programing为主，计算机需要处理更复杂问题，诞生了FORTRAN和C高级语言，用共同的机器语言来处理不同的处理器第2次软件危机(The Second Software Crisis)80s-90s，无法处理和维护复杂和鲁棒的应用，需要大量程序员和大量程序去处理更复杂问题，诞生了面向对象的程序设计OOP（C+,C# and Java）第3次软件危机？(The Origins of a Third Crisis)2005-20?，摩尔定律，并行计算、多核处理、云计算？面向对象编程(Object Oriented Programming，OOP)封装（Encapsulation）继承（Inheritance）多态（Polymorphism）摩尔定律：当价格不变时，集成电路上可容纳的晶体管数目，约每隔18个月便会增加一倍，性能也将提升一倍。换言之，每一美元所能买到的电脑性能，将每隔18个月翻两倍