第1章_计算方法概论

计算方法课件第1章计算方法概论运用数学方法解决科学研究或工程技术问题，一般按如下途径进行：实际问题模型设计算法设计程序设计上机计算问题的解其中算法设计是计算方法课程的主要内容.结束1计算方法又称数值分析，是计算数学的重要组成部分。计算方法课件§1.1引言结束21.1.1计算方法的意义计算方法对于计算速度与增强计算结果的准确性来说，与计算机硬件同等重要。这就导致了计算方法研究领域的空前活跃。1.1.2计算方法的任务计算方法课程研究常见的基本数学问题的数值解法.包含了数值代数(线性方程组的解法、非线性方程的解法、矩阵求逆、矩阵特征值计算等)、数值逼近、数值微分与数值积分、常微分方程及偏微分方程的数值解法等.它的基本理论和研究方法建立在数学理论基础之上，研究对象是数学问题，因此它是数学的分支之一.计算方法课件§1.2算法与效率结束31.2.1算法进行科学计算，需要构造确定型数值算法，确定型算法可定义为：从给定的已知量出发，按指定的运算顺序，经过有限次的四则运算及逻辑运算，可求出给定问题的数值解的完整的计算步骤。1.2.2算法的效率一个算法所需要四则浮点运算的总次数定义为它的计算量，单位是flop。由于+，-运算速度很快，可忽略，因此，算法的计算量简化为该算法所需要的乘法和除法运算的总次数。计算量越小，计算效率就越高。计算方法课件1.2.3算法的表述形式算法的表述形式是多种多样的.1用数学公式和文字说明描述，这种方式符合人们的理解习惯，和算法的推证相衔接，易于学习接受，但离上机应用距离较大.2用框图描述，这种方式描述计算过程流向清楚，易于编制程序，详略难以掌握.4算法程序，即用计算机语言描述的算法，它是面对计算机的算法。我们以后讨论的算法，都有现成的程序文本和软件可资利用.但从学习算法的角度看，这种描述方式并不有利.结束3算法描述语言，它是表述算法的一种通用语言。有特定的表述程序和语句。可以很容易地转化为某种计算机语言，同时也具有一定的可读性。4计算方法课件本教材将采用前三种方式表述各种算法.1.2.4算法的基本特点1算法常表现为一个无穷过程的截断：例1计算sinx的值，4π0,x根据sinx的无穷级数)!12()1(!7!5!3sin12753nxxxxxxnn(1.1)这是一个无穷级数，我们只能在适当的地方“截断”，使计算量不太大，而精度又能满足要求.如计算sin0.5，取n=3479625.0!75.0!55.0!35.05.05.0sin753结束5计算方法课件据泰勒余项公式，它的误差应为!9)1(94R4,0(1.2)791013.3362880)4/(R可见结果是相当精确的.实际上结果的六位数字都是正确的.2算法常表现为一个连续过程的离散化例2计算积分值.1011dxxI将［0，1］分为4等分，分别计算4个小曲边梯形的面积的近似值，然后加起来作为积分的近似值(如图1-1).记被积函数为f(x)，即结束6xxf11)(计算方法课件011yxxy11图1-1计算有：I≈0.697024，与精确值0.693147比较，可知结果不够精确，如进一步细分区间，精度可以提高.3,2,1,0,,41iihxhihxfxfTiii2)()(13算法常表现为“迭代”形式.迭代是指某一简单算法的多次重复，后一次使用前一次的结果.这种形式易于在计算程序中实现，在程序中表现为“循环”过程.例3多项式求值.结束7nnnxaxaxaaxP2210)(30iiTI计算方法课件用tk表示xk，uk表示(1.4)式前k+1项之和.作为初值令：(1.5)0001aut对k=1,2,…,n，反复执行：(1.6)kkkkkktauuxtt11显然Pn(x)=un，而(1.6)式是一种简单算法的多次循环.令k=1,2,,n(1.7)knkknaxvvav10结束对此问题还有一种更好的迭代算法.8011012312012110111))(())(()()(axaxaxaaxaxaxaxaaxaxaxaaxaxaxaxPnnnnnnnnnnnnnnn计算方法课件显然Pn(x)=vn.这两种算法都是将n次多项式化为n个一次多项式来计算，这种化繁为简的方法在数值分析中经常使用.下面估计一下以上两种算法的计算量：第一法：执行n次(1.6)式，每次2次乘法，一次加法，共计2n次乘法，n次加法；第二法：执行n次(1.7)式，每次1次乘法，一次加法，共计n次乘法，n次加法.显然第二种方法运算量小，它是我国宋代数学家秦九韶最先提出的，被称为“秦九韶算法”.例4不用开平方计算(a＞0)的值.a假定x0是的一个近似值，x0＞0，则≈也是的一个近似值，且x0和两个近似值必有一个大于，另aaaa0xa0xa结束9计算方法课件a一个小于，可以设想它们的平均值应为的更好的平均值，于是设计一种算法：a10(k=0,1,2,)(1.8)如计算，取x0=2，有(k=0,1,2,)3kkkxaxx211kkkxxx3211计算有：x0=2x1=1.75x2=1.7321429x3=1.7320508…可见此法收敛速度很快，只算三次得到8位精确数字.迭代法应用时要考虑是否收敛、收敛条件及收敛速度等问题，今后课程将进一步讨论.结束计算方法课件§1.4误差1.4.1误差的来源在运用数学方法解决实际问题的过程中，每一步都可能带来误差.1模型误差在建立数学模型时，往往要忽视很多次要因素，把模型“简单化”，“理想化”，这时模型就与真实背景有了差距，即带入了误差.2测量误差数学模型中的已知参数，多数是通过测量得到.而测量过程受工具、方法、观察者的主观因素、不可预料的随机干扰等影响必然带入误差.3截断误差数学模型常难于直接求解，往往要近似替代，简化为易于求解的问题，这种简化带入误差称为方法误差或截断误差.4舍入误差计算机只能处理有限数位的小数运算，初始参数或中间结果都必须进行四舍五入运算，这必然产生舍入误差.结束11计算方法课件在数值分析课程中不分析讨论模型误差；截断误差是数值分析课程的主要讨论对象，它往往是计算中误差的主要部分，在讲到各种算法时，通过数学方法可推导出截断误差限的公式(如(1.2)式)；舍入误差的产生往往带有很大的随机性，讨论比较困难，在问题本身呈病态或算法稳定性不好时，它可能成为计算中误差的主要部分；至于测量误差，我们把它作为初始的舍入误差看待.误差分析是一门比较艰深的专门学科.在数值分析中主要讨论截断误差及舍入误差.但一个训练有素的计算工作者，当发现计算结果与实际不符时，应当能诊断出误差的来源，并采取相应的措施加以改进，直至建议对模型进行修改.结束12计算方法课件1.4.2误差的基本概念1误差与误差限定义1.1设x*是准确值，x是它的一个近似值，称e=x-x*为近似值x的绝对误差，简称误差.误差是有量纲的量，量纲同x，它可正可负.误差一般无法准确计算，只能根据测量或计算情况估计出它的绝对值的一个上限，这个上界称为近似值x的误差限，记为ε｜x-x*｜≤ε，其意义是：x-ε≤x*≤x+ε在工程中常记为：x*=x±ε.如l=10.2±０.０５mm，R=1500±100Ω2相对误差与相对误差限误差不能完全刻画近似值的精度.如测量百米跑道产生10cm的误差与测量一个课桌长度产生1cm的误差，我们不能简单地认为后者更精确，还应考虑被测值的大小.下面给出定义：结束13计算方法课件定义1.2误差与精确值的比值称为x的相对误差，记作er.***xxxxe相对误差是无量纲的量，常用百分比表示，它也可正可负.相对误差也常不能准确计算，而是用相对误差限来估计.相对误差限：||||||||***rrexxxx实际上由于x*不知道，用上式无法确定εr，常用x代x*作分母，此时：结束14||xr计算方法课件以后我们就用表示相对误差限.||x例5在刚才测量的例子中，若测得跑道长为100±0.1m，课桌长为120±1cm，则显然后者比前者相对误差大.%1.01001.0)1(r%83.01201)2(r1.4.3有效数字定义1.3结束15设*x的近似值为mnaaax10.021，其中，naaa,,,21都是0~9中的任一整数，且01a。若x的绝对误差限满足：lmxxe105.0||*则称近似数x具有l位有效数字。计算方法课件例如：用722作为园周率14159265.3的近似值，它有多少位有效数字？如果用它计算半径为91.7r（它有3位有效数字）的园面积，问面积的误差有多少位有效数字？解：14285714.3722，110314.014159265.3，因31105.00012645.0|722|。所以，有3位有效数字。面积2rS，其近似值321019.05635.19691.7722S231222*105.0105.05614405.01021)91.7722291.7(2||||rrrSSS故S有2位有效数字。定义1.4近似数nmmaaaaax110.从x的第一位（自左至右）非0数字到最右边的数字为止的所有数字都叫有效数字。其个数为有效数字的位数。结束16计算方法课件如：π=3.14159265则3.14和3.1416分别有3位和5位有效数字.而3.143相对于π也只能有3位有效数字如a=0.034537…，则近似数0.0345有3位有效数字又如近似数c=30.4和d=30.40分别有3位和4位有效数字如计算机上得到方程x3-x-1=0的一个正根为1.32472，保留4位有效数字的结果为1.325，保留5位有效数字的结果为1.3247.相对误差与有效数位的关系十分密切.定性地讲，相对误差越小，有效数位越多，反之亦正确.定量地讲，有如下两个定理.定理1.1设近似值x=0.a1a2an×10m有n位有效数字，则其相对误差限此定理的证明不难，可作为习题完成.111021nra结束17计算方法课件定理1.2设近似值x=±0.a1a2an×10m的相对误差限不大于，则它至少有n位有效数字.1110)1(21na证｜x|≤(a1+1）×10m-1由定义1.3知x有n位有效数字.nmmnaaxxxxxx105.010)1(10)1(21||||||||1111**例6计算sin1.2，问要取几位有效数字才能保证相对误差限不大于0.01%.解sin1.2=0.93，故a1=9,m=0解关于n的不等式10-n≤18×10-5=1.8×10-4.41110%01.01021nra结束18计算方法课件所以取n=4，即可满足要求.对有效数字的观察比估计相对误差容易得多，故监视有效数字是否损失，常可发现相对误差的突然扩大.例6计算，视已知数为精确值，用4位浮点数计算.76017591解原式=0.1318×10-2-0.1316×10-2=0.2×10-5.结果只剩一位有效数字，有效数字大量损失，造成相对误差的扩大.若通分后再计算：原式=就得到4位有效数字的结果.下文将会提到相近数字相减会扩大相对误差.56101734.0105768.017607591结束19计算方法课件§1.5设计算法时应注意的原则1.5.1~数值运算时误差的传播当参与运算的数值带有误差时，结果也必然带有误差，问题是结果的误差与原始误差相比是否扩大.1)对函数f(x)的计算:设x是x*的近似值，则结果误差用泰勒展式分析2)*()()*)(()(*)(2xxfxxxfxfxf*)()())((xfxfxfe2*)()(*