第一章数值计算方法

第一章数值计算方法第一页，共五十八页，编辑于2023年，星期四在数学发展中，理论和计算是紧密联系的。现代计算机的出现为大规模的数值计算创造了条件，集中而系统的研究适用于计算机的数值方法变得十分迫切和必要。数值计算方法正是在大量的数值计算实践和理论分析工作的基础上发展起来的，它不仅仅是一些数值方法的简单积累，而且揭示了包含在多种多样的数值方法之间的相同的结构和统一的原理。数值算法是进行科学计算必不可缺少的起码常识；更为重要的是通过对它们的讨论，能够使人们掌握设计数值算法的基本方法和一般原理，为在计算机上解决科学计算问题打下基础。因此，计算方法已经成为工科大学生必修课程。为什么要开设这个课呢？第二页，共五十八页，编辑于2023年，星期四1.认识建立算法和对每个算法进行理论分析是基本任务，主动适应“公式多”的特点；

2.注重各章建立算法的问题的提法，搞清问题的基本提法，逐步深入；

3.理解每个算法建立的数学背景，数学原理和基本线索，对最基本的算法要非常熟悉；

4.认真进行数值计算的训练，学习各章算法完全是为用于实际计算，必须真会算。如何进行学习？第三页，共五十八页，编辑于2023年，星期四科学素质：拓宽对21世纪科学的了解；

加深对数学思想的理解；

培养用数学思考世界的习惯

数学能力：数学知识的运用能力；

对专业中问题建立数学求解方法与

实际计算能力

应用问题中数学创造性能力

计算知识：常用算法的数学理论；

在“误差、存贮、速度”之下的实

际计算方法；

对结果的数值分析方法

第四页，共五十八页，编辑于2023年，星期四•记好课堂笔记•保证课堂纪律•按时完成作业•按时上课，不迟到早退几点要求第五页，共五十八页，编辑于2023年，星期四数值分析讲述的基本内容如何把数学模型归结为数值问题如何制定快速的算法如何估计一个给定算法的精度分析误差在计算过程中的积累和传播如何构造精度更高的算法如何使算法较少的占用存储量如何分析算法的优缺点第六页，共五十八页，编辑于2023年，星期四本课程的基本要求掌握数值方法的基本原理掌握常用的科学与工程计算的基本方法能用所学方法在计算机上算出正确结果

第七页，共五十八页，编辑于2023年，星期四

本章内容§1引言§2误差的来源及分类§3误差的度量§4误差的传播§5减少运算误差的原则第一章计算方法与误差小结第八页，共五十八页，编辑于2023年，星期四要求掌握的内容第一章计算方法与误差概念包括有效数字、绝对误差、绝对误差限、相对误差、相对误差限等误差 截断误差、舍入误差的详细内容，误差种类等分析运算误差的方法和减少运算误差的若干原则第九页，共五十八页，编辑于2023年，星期四1.1引言数值分析又称计算方法,它是研究各种数学问题的数值解法及其理论的一门学科。数值分析的任务实际问题数学模型数值计算方法程序设计上机计算数值结果

根据数学模型提出求解的数值计算方法直到编出程序上机算出结果，这一过程边是数值分析研究的对象第十页，共五十八页，编辑于2023年，星期四1.对于要解决的问题建立数学模型2.研究用于求解该数学问题近似解的算法和过程3.按照2进行计算，得到计算结果建立数学模型转化为数值公式进行计算数值方法解题的一般过程第十一页，共五十八页，编辑于2023年，星期四

数值计算以及计算机模拟（包括当前流行的虚拟现实的方法），已经是在工程技术研究和经济、社会科学中广泛应用的方法，带来巨大的经济效益天气预报与亿次计算机波音777的无纸设计与有限元CT、核磁共振计算流体力学与爆炸工程能源问题与大型计算第一章计算方法与误差计算作为工程技术研究方法第十二页，共五十八页，编辑于2023年，星期四计算方法课程主要讨论如何构造求数学模型近似解的算法，讨论算法的数学原理、误差和复杂性，配合程序设计进行计算试验并分析试验结果。与纯数学的理论方法不同，用数值计算方法所求出的结果一般不是解的精确值或者准确的解析表达式，而是所求真解的某些近似值或近似曲线。第一章计算方法与误差第十三页，共五十八页，编辑于2023年，星期四例如方程x2=2sinx，在区间(1,2)内有唯一根,但找不出求根的解析式,只能用数值计算方法求其近似解。有些数学问题虽有理论上的准确的公式解,但不一定实用,例如行列式解法的Cramer法则原则上可用来求解线性方程组,用这种方法解一个n元方程组,要算n+1个阶行列式的值,总共需要n!(n-1)(n+1)次乘法,当n=20时,其乘除法运算次数约需1021次方,即使用每秒千亿次的计算机也得需要上百年,而用高斯（Guass）消去法约需2660次乘除法运算,并且愈大,相差就愈大。可见研究和选择好的算法是非常重要的。

第十四页，共五十八页，编辑于2023年，星期四算法(数值算法):是指有步骤地完成解数值问题的过程。数值算法的特点•目的性，条件和结论、输入和输出数据均要有明确的规定与要求。•确定性，精确地给出每一步的操作(不一定都是运算)定义,不容许有歧义。•可执行性，算法中的每个操作都是可执行的•有穷性，在有限步内能够结束解题过程计算机上的算法，按面向求解问题的不同，分为数值算法和非数值算法。第十五页，共五十八页，编辑于2023年，星期四第一章计算方法与误差1.2误差的来源及分类

早在中学我们就接触过误差的概念，如在做热力学实验中，从温度计上读出的温度是23.4度，就不是一个精确的值，而是含有误差的近似值。事实上，误差在我们的日常生活中无处不在，无处不有。如量体裁衣，量与裁的结果都不是精确无误的，都含有误差。第十六页，共五十八页，编辑于2023年，星期四在用数值方法解题过程中可能产生的误差归纳起来有如下几类：1.模型误差2.观测误差3.截断误差4.舍入误差第一章计算方法与误差第十七页，共五十八页，编辑于2023年，星期四用数学方法解决一个具体的实际问题，首先要建立数学模型，这就要对实际问题进行抽象、简化，因而数学模型本身总含有误差，这种误差叫做模型误差数学模型是指那些利用数学语言模拟现实而建立起来的有关量的描述数学模型的准确解与实际问题的真解不同实际问题的真解数学模型的真解为减化模型忽略次要因素定理在特定条件下建立与实际条件有别1.模型误差第十八页，共五十八页，编辑于2023年，星期四在数学模型中通常包含各种各样的参变量，如温度、长度、电压等，这些参数往往是通过观测得到的，因此也带来了误差，这种误差叫观测误差数学模型中的参数和原始数据，是由观测和试验得到的由于测量工具的精度、观测方法或客观条件的限制,使数据含有测量误差,这类误差叫做观测误差或数据误差根据实际情况可以得到误差上下界数值方法中需要了解观测误差,以便选择合理的数值方法与之适应2.观测误差第十九页，共五十八页，编辑于2023年，星期四精确公式用近似公式代替时,所产生的误差叫截断误差例如,函数f(x)用泰勒(Taylor)多项式

3.截断误差（介于0与x之间）近似代替，则数值方法的截断误差是截断误差的大小直接影响计算结果的精度和计算工作量，是数值计算中必须考虑的一类误差第二十页，共五十八页，编辑于2023年，星期四在数值计算中只能对有限位字长的数值进行运算需要对参数、中间结果、最终结果作有限位字长的处理工作，这种处理工作称作舍入处理用有限位数字代替精确数，这种误差叫做舍入误差，是数值计算中必须考虑的一类误差4.舍入误差第二十一页，共五十八页，编辑于2023年，星期四第一章计算方法与误差例如在计算时用3.14159近似代替，产生的误差R=-3.14159=0.0000026…就是舍入误差。上述种种误差都会影响计算结果的准确性，因此需要了解与研究误差，在数值计算中将着重研究截断误差、舍入误差，并对它们的传播与积累作出分析第二十二页，共五十八页，编辑于2023年，星期四1.3

误差的度量

1.3.1绝对误差和绝对误差限定义1.1

设精确值x的近似值

x*

，称差

e(x*)

=x-x*近似值x*的绝对误差，简称误差。e(x*)又记为e*

当e*>0时，x*称为弱近似值，当e*<0时，x*称为强近似值,|e*|越小，x*的精度越高由于精确值一般是未知的,因而e*

不能求出来,但可以根据测量误差或计算情况设法估计出它的取值范围，即误差绝对值的一个上界或称误差限。第二十三页，共五十八页，编辑于2023年，星期四1.3

误差的度量

定义1.2

设存在一个正数，使则称为近似值的绝对误差限，简称误差限或精度。实际应用中经常使用这个量来衡量误差限,这就是说,如果近似数的误差限为,则表明准确值x必落在上,常采用下面的写法来表示近似值的精度或准确值x所在的范围。第二十四页，共五十八页，编辑于2023年，星期四1.3误差的度量a-εa+εaA例1

设x

==3.1415926…

近似值x*

=3.14,它的绝对误差是0.0015926…，有

‌‌x-x*=0.0015926…

0.002=0.210-2例2又近似值x*

=3.1416，它的绝对误差是

0.0000074…，有x-x*=0.0000074…

0.000008=0.810-5例3

而近似值x*

=3.1415，它的绝对误差是0.0000926…，有x-x*=0.0000926…

0.0001=0.110-3可见，绝对误差限*不是唯一的，但*越小越好第二十五页，共五十八页，编辑于2023年，星期四1.3.2相对误差和相对误差限只用绝对误差还不能说明数的近似程度,例如甲打字每100个错一个,乙打字每1000个错一个,他们的误差都是错一个,但显然乙要准确些,这就启发我们除了要看绝对误差外,还必须顾及量的本身。定义1.3绝对误差与精确值x的比值

称为相对误差。简记为第二十六页，共五十八页，编辑于2023年，星期四1.3.2相对误差和相对误差限

相对误差越小,精度就越高,实际计算时,x通常是不知道的,因此可用下列公式计算相对误差定义1.4设存在一个正数，使

则称为近似值的相对误差限。简记为第二十七页，共五十八页，编辑于2023年，星期四1.3.2相对误差和相对误差限例4.甲打字每100个错一个，乙打字每1000个错一个，求其相对误差解：根椐定义:甲打字时的相对误差

乙打字时的相对误差第二十八页，共五十八页，编辑于2023年，星期四1.3.3

有效数字定义1.5设x的近似值

其中是0到9之间的任一个数,但n是正整数,m是整数,若

则称为x的具有n位有效数字的近似值，准确到第n位，是的有效数字。

第二十九页，共五十八页，编辑于2023年，星期四1.3.3有效数字例5.3.142作为π的近似值时有几位有效数字解：3.141592…=0.3141592…×3.142=0.3142×

m=1|π-3.142|=|0.3141592…×-0.3142×|＜0.000041×＜0.0005=×

m–n=1–n=-3所以n=4，具有4位有效数字第三十页，共五十八页，编辑于2023年，星期四例6.当取3.141作为的近似值时-3.141=0.3141592…101

-0.3141101

≤0.0000592101

<0.0005=1/210-2

m-n=1-n=-2所以n=3具有3位有效数字推论如果近似数x*误差限是某一位的半个单位,由该位到x*的第一位非零数字一共有n位

x*就有n位有效数字,也就是说准确到该位第三十一页，共五十八页，编辑于2023年，星期四再如3.1416作为的近似值时-3.1416=0.3141592…101-0.31416101

≤0.00000074101

≤0.0000074<0.00005<0.510-4m-n=1-n=-4所以n=5x*=3.1416有5位有效数字第三十二页，共五十八页，编辑于2023年，星期四关于有效数字说明①用四舍五入取准确值的前n位x*作为近似值,则

x*必有n位有效数字。如3.142作为的近似值有4位有效数字，而3.141为3位有效数字②有效数字相同的两个近似数，绝对误差不一定相同。例如，设x1*=12345,设x2*=12.345,两者均有5位有效数字但绝对误差不一样x-x1*=x-12345≤0.5=1/2100

x-x2*=x-12.345≤0.0005=1/210-3③把任何数乘以10p(p=0,1,…)不影响有效位数④准确值具有无穷多位有效数字,如三角形面积S=1/2ah=0.5ah

因为0.5是真值,没有误差*=0,因此n,准确值具有无穷位有效数字第三十三页，共五十八页，编辑于2023年，星期四1.3.4有效数字与相对误差定理1.1若近似数x*=0.x1x2…xn10m具有n位有效数字，则其相对误差证:∵x*

=0.x1x2…xn10m

∴x*≥x110m-1

又∵x*具有n位有效数字,则x-x*≤1/210m-n∴第三十四页，共五十八页，编辑于2023年，星期四

一般应用中可以取r*=1/2x110-(n-1),n越大,r*越小,∴有效数字越多，相对误差就越小例7取3.14作为的四舍五入的近似值时，求其相对误差解：3.14=0.314101x1=3m=1∵四舍五入的近似值,其各位都是有效数字∴n=3

r*=1/2x110-(n-1)=1/2*310-2=17%1.3.4有效数字与相对误差第三十五页，共五十八页，编辑于2023年，星期四例8已知近似数x*有两位有效数字，试求其相对误差限解：已知n=2代入公式r*=1/2x110-(n-1)得

r*=1/2x110-1

x*的第一位有效数字x1没有给出，可进行如下讨论：当

x1=1r*=1/2x110-1=1/2*110-1=5%

x1=9r*=1/2x110-1=1/2*910-1=0.56%

取x1=1时相对误差为最大，即5%1.3.4有效数字与相对误差第三十六页，共五十八页，编辑于2023年，星期四1.3.4有效数字与相对误差定理1.2若近似数x*=0.x1x2…xn10m相对误差

则该近似数具有n位有效数字证:∵x*=0.x1x2…xn10m

∴x*≤(x1+1)10m-1由有效数字定义可知,x*具有n位有效数字。证毕第三十七页，共五十八页，编辑于2023年，星期四例9已知近似数x*的相对误差限为0.3%，问x*有几位有效数字？解：由得ⅰ当x1=1时,310-3=1/410-(n-1)1210-3=10-(n-1)

上式两边取以10为底的对数得

lg22+lg3+(-3)=-n+1∵lg2=0.3010lg3=0.477120.3010+0.4771-4=-n∴n=2.9209ⅱ当x1=9时,310-3=1/2010-(n-1)610-3=10-n上式两边取以10为底的对数得

lg2+lg3+(-3)=-n∴n=2.2219∴x*至少有3位有效数字

第三十八页，共五十八页，编辑于2023年，星期四例10为使的近似数的相对误差小于0.1%，问查开方表时，要取几位有效数字？解：∵8<<9∴x1=8

∴-(n-1)<lg2+2lg3+(-3)-n<1.2552-4-n<-2.7448

∴n>2.7448取n=3即查平方表时

8.37取三位有效数字

∴第三十九页，共五十八页，编辑于2023年，星期四

注意:已知有效数字,求相对误差用公式

已知相对误差,求具有几位有效数字公式第四十页，共五十八页，编辑于2023年，星期四两边除以得

(1.3)和（1.4）给出了由自变量的误差引起的函数值的误差的近似式（误差传播）。1.4.2、算术运算的误差估计

1.一元函数情形设则，由Taylor展开公式

(1.4)（1.3）第四十一页，共五十八页，编辑于2023年，星期四2.多元函数情形

设，则，由多元函数的Taylor展开公式类似可得（1.5）（1.6）在（1.6）式中，分别取,可得同号)（1.7）（1.8）（1.9）(,第四十二页，共五十八页，编辑于2023年，星期四由d(x±y)=dx±dy可得两数之和(差）的误差等于两数的误差之和（差）；由可得两数之积的相对误差等于两数的相对误差之和；由可得两数商的相对误差可看作是被除数与除数的相对误差之差。第四十三页，共五十八页，编辑于2023年，星期四例12正方形的边长约为100cm,怎样测量才能使其面积误差不超过1cm2?解：设正方形边长为xcm,测量值为x*cm,面积

y=f(x)=x2由于f

(x)=2x记自变量和函数的绝对误差分别是e*、e(y*),则

e*=x-x*

e(y*)=y-y*f(x*)(x-x*)=2x*e*=200e*现要求e(y*)200e*<1,于是e*≤（1/200）cm=0.005cm要使正方形面积误差不超过1cm2，测量边长时绝对误差应不超过0.005cm。第四十四页，共五十八页，编辑于2023年，星期四1.5减少运算误差原则误差是用来衡量数值方法好与坏的重要标志为此对每一个算法都要进行误差分析(1)两个相近的数相减，会严重损失有效数字例如x=1958.75，y=1958.32都具有五位有效数字，但x-y=0.43只有两位有效数字通常采用的方法是改变计算公式,例如当与很接近时,由于用右端代替左端公式计算,有效数字就不会损失

第四十五页，共五十八页，编辑于2023年，星期四1.5减少运算误差原则当x很大时可作相应的变换

则用右端来代替左端。

第四十六页，共五十八页，编辑于2023年，星期四1.5减少运算误差若干原则当x接近0时一般情况，当f(x)≈f(x*)时，可用泰勒展开取右端的有限项近似左端。如果计算公式不能改变，则可采用增加有效位数的方法保证精度

第四十七页，共五十八页，编辑于2023年，星期四（2）防止大数“吃掉”小数例求二次方程x2-105x+1=0的根解：按二次方程求根公式

x1=(105+(1010-4)1/2)/2x2=(105-(1010-4)1/2)/2在8位浮点数计算得

x1=(105+105)/2=105(正确）,

x2=(105-105)/2=0(错误）产生错误的原因 ①出现大数1010吃掉小数4的情况 ②分子部分出现两个相近数相减而丧失有效数位常称为灾难性的抵消第四十八页，共五十八页，编辑于2023年，星期四（3）绝对值太小的数不宜做除数当分母为两个相近数相减时,会丧失有效数字这里分子的误差被扩大104倍,再如若将分母变为0.0011,即分母只有0.0001的变化时,计算结果却有了很大变化1.5减少运算误差若干原则第四十九页，共五十八页，编辑于2023年，星期四例1.8计算 解:分子分母分别计算后相除(取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只准确到小数后一位1.5减少运算误差若干原则例：计算第五十页，共五十八页，编辑于2023年，星期四算法2。分成三组因子。每组只取六位小数计算

a=0.0005/0.0003=1.666667(有舍入)

b=0.0143/0.0125=1.144000c=0.0012/0.0135=0.088889(有舍入)

D=a*b*c=1.666667*1.144000*0.088889=0.169482,准确到小数后5位。bca1.5减少运算误差若干原则第五十一页，共五十八页，编辑于2023年，星期四（4）简化计算步骤，减少运算次数

x255=xx2x4x8x16x32x64x128原先要做254次乘法现只需14次即可又如计算多项式

p(x)=anxn

an-1x