1、实际问题实际问题模型设计模型设计算法设计算法设计问题的解问题的解上机计算上机计算程序设计程序设计 其中其中是数值分析课程的主要内容是数值分析课程的主要内容.数值分析课程研究常见的基本数学问题的数值解法数值分析课程研究常见的基本数学问题的数值解法.包含包含了了数值代数数值代数(线性方程组的解法、非线性方程的解法、矩阵求线性方程组的解法、非线性方程的解法、矩阵求逆、矩阵特征值计算等逆、矩阵特征值计算等)、数值逼近、数值微分与数值积分、数值逼近、数值微分与数值积分、常微分方程常微分方程及及偏微分方程偏微分方程的数值解法等的数值解法等.它的基本理论和研究它的基本理论和研究方法建立在数学理论基础之上，研
2、究对象是数学问题，因此方法建立在数学理论基础之上，研究对象是数学问题，因此它是数学的分支之一它是数学的分支之一.但它又与计算机科学有密切的关系但它又与计算机科学有密切的关系.我们在考虑算法时我们在考虑算法时，往往要同时考虑计算机的特性，如计算速度、存贮量、，往往要同时考虑计算机的特性，如计算速度、存贮量、字长等技术指标，考虑程序设计时的可行性和复杂性字长等技术指标，考虑程序设计时的可行性和复杂性.如果如果我们具备了一定的计算机基础知识和程序设计方法，学习我们具备了一定的计算机基础知识和程序设计方法，学习数值分析的理论和方法就会更深刻、更实际，选择或设计数值分析的理论和方法就会更深刻、更实际，选
3、择或设计的算法也会更合理、更实用的算法也会更合理、更实用.在科学研究、工程实践和经济管理等工作中，存在大在科学研究、工程实践和经济管理等工作中，存在大量的科学计算、数据处理等问题量的科学计算、数据处理等问题.应用计算机解决数值计算应用计算机解决数值计算问题是理工科研究生应当具备的基本能力问题是理工科研究生应当具备的基本能力.解决某类数学问题的数值方法称为解决某类数学问题的数值方法称为.为使算法能为使算法能在计算机上实现，它必须将一个数学问题分解为有限在计算机上实现，它必须将一个数学问题分解为有限次的次的+、-、运算和一些简单的基本函数运算运算和一些简单的基本函数运算.1 1、用数学公式和文字说
4、明描述用数学公式和文字说明描述，这种方式符合人们的理解，这种方式符合人们的理解习惯，和算法的推证相衔接，易于学习接受，但离上机应习惯，和算法的推证相衔接，易于学习接受，但离上机应用距离较大用距离较大.2 2、用框图描述用框图描述，这种方式描述计算过程流向清楚，易于编，这种方式描述计算过程流向清楚，易于编制程序，但对初学者有一个习惯过程制程序，但对初学者有一个习惯过程.此外框图描述格式不此外框图描述格式不很统一，详略难以掌握很统一，详略难以掌握.1.1.1 1.1.1 算法的表述形式算法的表述形式算法的表述形式是多种多样的算法的表述形式是多种多样的.3 3、算法描述语言算法描述语言，它是表述算法
5、的一种通用语言。有特，它是表述算法的一种通用语言。有特定的表述程序和语句。可以很容易地转化为某种计算机语定的表述程序和语句。可以很容易地转化为某种计算机语言，同时也具有一定的可读性。言，同时也具有一定的可读性。4 4、算法程序算法程序，即，即用计算机语言描述用计算机语言描述的算法，它是面的算法，它是面对计算机的算法。我们以后讨论的算法，都有现成的程序对计算机的算法。我们以后讨论的算法，都有现成的程序文本和软件可资利用文本和软件可资利用.但从学习算法的角度看，这种描述但从学习算法的角度看，这种描述方式并不有利方式并不有利.我们将采用前三种方式表述各种算法我们将采用前三种方式表述各种算法1.1.2
6、 1.1.2 算法的基本特点算法的基本特点 1算法常表现为一个无穷过程的算法常表现为一个无穷过程的截断截断：例例1 1 计算计算 sin sin x的值，的值，40,x 根据根据sinsin x 的无穷级数的无穷级数)!12()1(!7!5!3sin12753nxxxxxxnn(1.1)这是一个无穷级数，我们只能在适当的地方这是一个无穷级数，我们只能在适当的地方“截断截断”，使计算量不太大，而精度又能满足要求，使计算量不太大，而精度又能满足要求.如计算如计算 sin 0.5sin 0.5，取，取n=3n=3479625.0!75.0!55.0!35.05.05.0sin753据泰勒余项公式，它
7、的误差应为据泰勒余项公式，它的误差应为!9)1(99R4,0(1.2)791013.3362880)4/(R可见结果是相当精确的可见结果是相当精确的.实际上结果的六位数字都是正确的实际上结果的六位数字都是正确的.2算法常表现为一个连续过程的算法常表现为一个连续过程的离散化离散化例例2 2 计算积分值计算积分值1011dxxI将将0 0，1 1分为分为4 4等分，分别计算等分，分别计算4 4个小曲边梯形的面积的个小曲边梯形的面积的近似值，然后加起来作为积分的近似值近似值，然后加起来作为积分的近似值(如图如图1-1).1-1).记被积记被积函数为函数为 f(x)，即，即xxf11)(图1-1计算有
8、：计算有：I0.697 024，与精确值，与精确值0.693 147比较，可知结果不够精确，如进一比较，可知结果不够精确，如进一步细分步细分区区间，精度可以提高间，精度可以提高.3,2,1,0,41iihxhihxfxfTiii2)()(130iiTI3 3、算法常表现为、算法常表现为“迭代迭代”形式形式.迭代是指某一简单算法的迭代是指某一简单算法的多次重复，后一次使用前一次的结果多次重复，后一次使用前一次的结果.这种形式易于在计算这种形式易于在计算程序中实现，在程序中表现为程序中实现，在程序中表现为“循环循环”过程过程.例例3 3 多项式求值。多项式求值。2012()1.4nnnP xaa
9、xa xa x用用tk表示表示 xk，uk表示表示(1.4)(1.4)式前式前k+1项之和项之和.作为初值令作为初值令：0001aut(1.5)对对k=1,2,n，反复执行：，反复执行：11 (1.6)kkkkkktxtuua t显然显然Pn(x)=un，而，而(1.6)(1.6)式是一种简单算法的多次循环式是一种简单算法的多次循环.对此问题还有一种更好的迭代算法对此问题还有一种更好的迭代算法.011012312012110111)()()()(axaxaxaaxaxaxaxaaxaxaxaaxaxaxaxPnnnnnnnnnnnnnnn k=1,2,n (1.7)knkknaxvvav10
10、显然显然 Pn(x)=vn.这两种算法都是将这两种算法都是将n次多项式化为次多项式化为n个一次多项式来计算，这个一次多项式来计算，这种化繁为简的方法在数值分析中种化繁为简的方法在数值分析中经常使用经常使用.下面估计一下以上两种算法的计算量：下面估计一下以上两种算法的计算量：第一法：执行第一法：执行n次次(1.6)(1.6)式，每次式，每次2 2次乘法，一次加法，次乘法，一次加法，共计共计 2 2n 次乘法，次乘法，n 次加法次加法；第二法：执行第二法：执行n 次次(1.7)(1.7)式，每次式，每次1 1次乘法，一次加法，次乘法，一次加法，共计共计n次乘法，次乘法，n 次加法次加法.令令 显然
11、第二种方法运算量小，它是我国宋代数学家秦九韶显然第二种方法运算量小，它是我国宋代数学家秦九韶最先提出的（最先提出的（12471247年），被称为年），被称为“秦九韶算法秦九韶算法”.例例4 4 不用开平方计算不用开平方计算aa一个小于一个小于a(a0)0)的值的值.,可以设想它们的平均值应为可以设想它们的平均值应为平均值，于是设计一种算法：平均值，于是设计一种算法：的更好的的更好的如计算如计算 ，取，取 x0 =2=2，有，有3kkkxaxx211kkkxxx3211计算有：计算有：x0 0=2=2 x1 1=1.75=1.75 x2 2=1.732 142 9=1.732 142 9 x3
12、3=1.732 050 8=1.732 050 8 可见此法收敛速度很快，只算三次得到可见此法收敛速度很快，只算三次得到8 8位精确数字位精确数字.迭代法应用时要考虑是否收敛、收敛条件及收敛速度等迭代法应用时要考虑是否收敛、收敛条件及收敛速度等问题，今后课程将进一步讨论问题，今后课程将进一步讨论.(k=0,1,2,)(1.8)(k=0,1,2,)1.2.1 误差的来源误差的来源 在运用数学方法解决实际问题的过程中，每一步都可在运用数学方法解决实际问题的过程中，每一步都可能带来误差能带来误差.1、模型误差模型误差 在建立数学模型时，往往要忽视很多次要因在建立数学模型时，往往要忽视很多次要因素，把
13、模型素，把模型“简单化简单化”，“理想化理想化”，这时模型就与真实，这时模型就与真实背景有了差距，即带入了误差背景有了差距，即带入了误差.2、测量误差测量误差 数学模型中的已知参数，多数是通过测量得数学模型中的已知参数，多数是通过测量得到到.而测量过程受工具、方法、观察者的主观因素、不可而测量过程受工具、方法、观察者的主观因素、不可预料的随机干扰等影响必然带入误差预料的随机干扰等影响必然带入误差.3、截断误差截断误差 数学模型常难于直接求解，往往要近似替数学模型常难于直接求解，往往要近似替代，简化为易于求解的问题，这种简化带入误差称为方法误代，简化为易于求解的问题，这种简化带入误差称为方法误差
14、或截断误差差或截断误差.4、舍入误差舍入误差 计算机只能处理有限数位的小数运算，初计算机只能处理有限数位的小数运算，初始参数或中间结果都必须进行四舍五入运算，这必然产生舍始参数或中间结果都必须进行四舍五入运算，这必然产生舍入误差入误差.在数值分析课程中不分析讨论模型误差；在数值分析课程中不分析讨论模型误差；截断误差截断误差是数是数值分析课程的主要讨论对象，它往往是计算中误差的主要部值分析课程的主要讨论对象，它往往是计算中误差的主要部分，在讲到各种算法时，通过数学方法可推导出截断误差限分，在讲到各种算法时，通过数学方法可推导出截断误差限的公式的公式(如如(1.2)(1.2)式式)；舍入误差舍入误
15、差的产生往往带有很大的随机性，讨论比较困难，的产生往往带有很大的随机性，讨论比较困难，在问题本身呈病态或算法稳定性不好时，它可能成为计算中在问题本身呈病态或算法稳定性不好时，它可能成为计算中误差的主要部分；至于测量误差，我们把它作为初始的舍入误差的主要部分；至于测量误差，我们把它作为初始的舍入误差看待误差看待.误差分析是一门比较艰深的专门学科误差分析是一门比较艰深的专门学科.在数值分析中主要在数值分析中主要讨论讨论截断误差及舍入误差截断误差及舍入误差.但一个训练有素的计算工作者，但一个训练有素的计算工作者，当发现计算结果与实际不符时，应当能诊断出误差的来源，当发现计算结果与实际不符时，应当能诊
16、断出误差的来源，并采取相应的措施加以改进，直至建议对模型进行修改并采取相应的措施加以改进，直至建议对模型进行修改.1.2.2 误差的基本概念误差的基本概念 1、误差与误差限误差与误差限 定义定义1.11.1 设设x*是准确值，是准确值，x是它的一个近似值，是它的一个近似值，称称e e=x-x*为近似值为近似值 x的的绝对误差绝对误差，简称，简称误差误差.误差是有量纲的量，量纲同误差是有量纲的量，量纲同x，它可正可负，它可正可负.误差一般无法准确计算，只能根据测量或计算情况估计误差一般无法准确计算，只能根据测量或计算情况估计 出它的绝对值的一个上限，这个上界称为近似值出它的绝对值的一个上限，这个
17、上界称为近似值 x的误的误 差限，记为差限，记为 x-x*，其意义是：，其意义是：x-x*x+在工程中常记为：在工程中常记为：x*=x.如如 l=10.2=10.2.mmmm，R=1500=1500100100 2、相对误差与相对误差限相对误差与相对误差限 误差不能完全刻画近似值的误差不能完全刻画近似值的精度精度.如测量百米跑道产生如测量百米跑道产生10cm10cm的误差与测量一个课桌长度的误差与测量一个课桌长度产生产生1cm1cm的误差，我们不能简单地认为后者更精确，还应的误差，我们不能简单地认为后者更精确，还应考考虑被测值的大小虑被测值的大小.下面给出定义下面给出定义：定义定义1.21.2
18、 误差与精确值的比值误差与精确值的比值 称为称为x的的相对误差相对误差，记作记作er.*xxxxe 相对误差是无量纲的量，常用百分比表示，它也可正可相对误差是无量纲的量，常用百分比表示，它也可正可负负.相对误差也常不能准确计算，而是用相对误差限来估计相对误差也常不能准确计算，而是用相对误差限来估计.相对误差限相对误差限：|*rrexxxx 实际上由于真值实际上由于真值x*不知道，用上式无法确定不知道，用上式无法确定r，常用，常用 x代代 x*作作 分母，此时：分母，此时：|xr以后我们就用以后我们就用 表示相对误差限表示相对误差限.|x 例例5 5 在刚才测量的例子中，若测得跑道长为在刚才测量
19、的例子中，若测得跑道长为 1001000.1m0.1m，课桌长为，课桌长为1201201cm 1cm，则，则 显然后者比前者相对误差大显然后者比前者相对误差大.%1.01001.0)1(r%83.01201)2(r 1.2.3 有效数字有效数字 定义定义1.31.3 如果近似值如果近似值 x 的误差限的误差限是它某一数位的半个是它某一数位的半个 单位，我们就说单位，我们就说 x 准确到该位，从这一位起直准确到该位，从这一位起直 到前面第一个非零数字为止的所有数字称到前面第一个非零数字为止的所有数字称 x 的的 有效数字有效数字.如：如：x=0.a1a2an10m，其中，其中a1，a2，an是是
20、 0 09 9之之 中的整数，且中的整数，且a10，如，如e=|x-x*|=0.510m-l，1 ln 则称则称x有有 l 位有效数字位有效数字.如：如：=3.14159265=3.14159265 则则3.143.14和和3.14163.1416分别有分别有3 3位和位和5 5位有效数字位有效数字.而而3.1433.143相对于相对于也只能有也只能有3 3位有效数字位有效数字 在更多的情况，我们不知道准确值在更多的情况，我们不知道准确值x*.如果我们认为计算如果我们认为计算结果各数位可靠，将它四舍五入到某一位，这时从这一位起结果各数位可靠，将它四舍五入到某一位，这时从这一位起到前面第一个非零
21、数字共到前面第一个非零数字共 l 位，它与计算结果之差必小于该位，它与计算结果之差必小于该位的半个单位位的半个单位.我们习惯上说将计算结果保留我们习惯上说将计算结果保留 l 位有效数字位有效数字.如计算机上得到方程如计算机上得到方程 x3 3-x-1=0-1=0 的一个正根为的一个正根为 1.324721.32472，保留保留4 4位有效数字的结果为位有效数字的结果为1.3251.325，保留，保留5 5位有效数字的结果为位有效数字的结果为1.3247.1.3247.相对误差与有效数位的关系十分密切相对误差与有效数位的关系十分密切.定性地讲，定性地讲，相对相对误差越小，有效数位越多，反之亦正确
22、误差越小，有效数位越多，反之亦正确.定量地讲，有如下两定量地讲，有如下两个定理个定理.定理定理1.1 设近似值设近似值x=0.=0.a1a2an1010m m有有n位有效数字，位有效数字，则其相对误差限则其相对误差限 此定理的证明不难，可作为习题完成此定理的证明不难，可作为习题完成.111021nra 定理定理1.21.2 设近似值设近似值 x=0.0.a1a2an1010m m 的相对误差限的相对误差限 不大于不大于 ，则它至少有，则它至少有 n位有位有 效数字效数字.1110)1(21na由定义由定义1.3知知x有有n位有效数字位有效数字.*1111|110(1)100.5 102(1)n
23、mm nx xx xxxaa 证明证明:x|(|(a1+1+1）1010m-1m-1 例例6 6 计算计算sin 1.2sin 1.2，问要取几位有效数字才能保证相，问要取几位有效数字才能保证相 对误差限不大于对误差限不大于0.0.01%.解关于解关于n的不等式的不等式 10-n1810-5=1.810-4.所以取所以取n=4，即可满足要求，即可满足要求.对有效数字的观察比对有效数字的观察比 估计相对误差容易得多，故监视有效数字是否损估计相对误差容易得多，故监视有效数字是否损 失，常可发现相对误差的突然扩大失，常可发现相对误差的突然扩大.41110%01.01021nra解解 sin1.2=0
24、.93sin1.2=0.93，故，故a1 1=9,=9,m=0=0 例例6 6 计算计算 ，视已知数为，视已知数为精确值，用精确值，用4位浮点位浮点 数计算数计算.76017591 解解 原式原式=0.1318=0.13181010-2-2-0.1316-0.13161010-2-2=0.2=0.21010-5-5.结果只剩一位有效数字，有效数字大量损失，造成相对结果只剩一位有效数字，有效数字大量损失，造成相对 误差的扩大误差的扩大.若通分后再计算：若通分后再计算：原式原式=就得到就得到4 4位有效数字的结果位有效数字的结果.下文将会提到相近数字相减下文将会提到相近数字相减 会扩大相对误差会扩
25、大相对误差.56101734.0105768.017607591 1.3.1数值运算时误差的传播数值运算时误差的传播 当参与运算的数值带有误差时，结果也必然带有误差，当参与运算的数值带有误差时，结果也必然带有误差，问题是结果的误差与原始误差相比是否扩大问题是结果的误差与原始误差相比是否扩大.1.3 设计算法时应注意的原则设计算法时应注意的原则 1)对函数对函数 f(x)的计算的计算:设设 x 是是x*的近似值，则结果误差的近似值，则结果误差用泰勒展式分析用泰勒展式分析*)()()(xfxfxfe2)*()()*)()(*)(2xxfxxxfxfxf 2*)()(*)()(2xxfxxxfxfe
26、)(|2)(|)(|)(|)(|2xfxxfxfe)(|)(|)(|xxfxfe 忽略第二项高阶无穷小之后，可得函数忽略第二项高阶无穷小之后，可得函数f(x)的误差限估计式的误差限估计式2)对多元函数对多元函数 f(x1*,x2*,xn*)=A*,设设 x1,x2,xn 是是 x1*,x2*,xn*的近似值，则的近似值，则A=f(x1,x2,xn)是结果的近似值。是结果的近似值。其中其中),(),()(*2*121nnxxxfxxxfAe|),(),(|21*2*1*nnxxxfxxxfAA)(|),(2*211xOxxxxxxfkkknnk|max*kkkxxx略去高阶项后略去高阶项后)()
27、,()(211kknnkxxxxxfA)10.1(3）四则运算中误差的传播）四则运算中误差的传播 按（按（1.10）易得）易得:)()()(2121xxxx)(|)(|)(122121xxxxxx22122121)(|)(|xxxxxxx)11.1()12.1()13.1(例例7：若电压若电压V=220 5V，电阻，电阻R=300 10，求电流，求电流I并计并计 算其误差限及相对误差限。算其误差限及相对误差限。解：解：)(7333.0300220AI2|()|()()220 10300 50.0411()90000VRRVIRA所以所以)(0411.07333.0AI%67333.00411.
28、0)(Ir1.3.2 算法中应避免的问题算法中应避免的问题1）避免相近数相减）避免相近数相减 由公式由公式(1.11)121212112212112212121212()()|()|()|()()|rrrxxxxxxxxxxxxxxxxxxxxxxxx)()()(2121xxxx当当 x1 和和 x2 十分相近时，十分相近时，x1-x2接近零，接近零，将很大，所以将很大，所以|211xxx)(21xxr和和|212xxx12(),()rrxx从直观上看，相近数相减会造成有效数位的减少，从直观上看，相近数相减会造成有效数位的减少，本章例本章例6就是一个例子就是一个例子.有时，通过改变算法可以避有
29、时，通过改变算法可以避免相近数相减免相近数相减.大很多，即相对误差将显著扩大大很多，即相对误差将显著扩大.将比将比例例8:解方程解方程 x 2-18 x+1=0，假定用，假定用4位浮点计算位浮点计算.解解:用公式解法用公式解法94.1780924181821x056.08092x可见第二个根只有两位有效数字可见第二个根只有两位有效数字,精度较差精度较差.若第二个根若第二个根改为用韦达定理计算改为用韦达定理计算05574.0112xx可得较好结果。可得较好结果。)1(1xxx如如等等等等,都可以得到比直接计算好的结果。都可以得到比直接计算好的结果。可改为可改为,11xx)1|(|)cos(1xx
30、如如可改为可改为2sin22x)(1)(|12222121xxxxxxx|12xx 若若则则1|221xx这时这时21xx将比将比)(2x扩大很多。扩大很多。3)防止小数被大数防止小数被大数“吃掉吃掉”在大量数据的累加运算中，在大量数据的累加运算中，由由于加法必须进行对位，有可能出现小数被大数于加法必须进行对位，有可能出现小数被大数“吃掉吃掉”.2)避免除法中除数的数量级远小于被除数避免除法中除数的数量级远小于被除数 由公式由公式(1.13)如用六位浮点数计算某市的工业总产值，原始数据是各企业如用六位浮点数计算某市的工业总产值，原始数据是各企业的工业产值，当加法进行到一定程度，部分和超过的工业
31、产值，当加法进行到一定程度，部分和超过100亿元亿元 （0.11011），再加产值不足），再加产值不足10万元的小企业产值，将再也加万元的小企业产值，将再也加不进去不进去.而这部分企业可能为数不少，合计产值相当大而这部分企业可能为数不少，合计产值相当大.这种情这种情况应将小数先分别加成大数，然后相加，结果才比较正确况应将小数先分别加成大数，然后相加，结果才比较正确.这个例子告诉我们，在计算机数系中，加法的交换律和结合律这个例子告诉我们，在计算机数系中，加法的交换律和结合律可能不成立，这是在大规模数据处理时应注意的问题可能不成立，这是在大规模数据处理时应注意的问题.4)注意运算步骤的简化注意运算步骤的简化减少算术运算的次数以减少误差的积减少算术运算的次数以减少误差的积累效应。累效应。
