数值分析1.1讲义.

数值分析NumericalAnalysis《数值分析》(第2版)朱晓临主编中国科学技术大学出版社教材《数值分析》（第5版）李庆阳，王能超，易大义编著清华大学大学出版社《数值分析》（第3版）颜庆津著，北京航空航天大学出版社《NumericalAnalysis》(Ninthed.)RichardBurden,DouglaFaires,Brooks/Cole,CengageLearning,2011参考书目微积分线性代数常微分方程算法语言预备知识一、为什么要学习数值分析？课程简介现实世界的问题可以归结为各种各样的数学问题—方程求根问题—解线性方程组的问题—定积分问题—常微分方程初值问题—…….方程求根问题在科学计算中常要遇到求解各种方程，例如：高次代数方程x5－3x＋7＝003cosxex超越方程高次线性方程和超越方程看似简单，但难于求其精确解。对于高次代数方程，由代数基本定理知多项式根的数目和方程的阶相同，但对超越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。解线性方程组的问题线性方程组的一般形式nnnnnnnnnnbxaxaxabxaxaxabxaxaxa............22112222212111212111(1)当b≠0时称为非齐次线性方程组，其可能有唯一解、无解或者无穷多个解。当b=0时称为线性齐次方程组，必有零解。(2)由线性代数知识可知：当系数矩阵A非奇异(即detA≠0)时，方程组有唯一解，可用克莱姆法则求解，但它只适合于n很小的情况。克莱姆法则DDxDDxDDxnn,,,2211其中nnnnaaaaD1111nnnnababD111例如用克莱姆法则求解一个n阶方程组，要算n+1个n阶行列式的值，总共需要n!(n-1)(n+1)次乘法。当n充分大时，计算量是相当惊人的。比如一个20阶不算太大的方程组，大约要做1021次乘法，这项计算即使每秒1亿次浮点数乘法计算的计算机去做，也要连续工作30万年才能完成。当然这是完全没有实际意义的，故需要寻找有效算法!定积分问题)()()(aFbFdxxfba对于积分badxxfI)(由微积分知识可知：只要找到被积函数f(x)的原函数F(x)，便有下列牛顿—莱布尼兹公式为何要进行数值积分？原因之一：许多形式上很简单的函数，例如等等babadxxxdxxsin,sin2已证明它们的原函数不能用初等函数表示成有限形式。原因之二：有些被积函数的原函数过于复杂，例如32)(22xxxf的一个原函数是)322ln(216916323432)(2223xxxxxxxF要计算f(x)定积分的近似值，上式就不见得方便。原因之三：f(x)以离散数据点形式给出xix0x1…xnyi=f(xi)y0y1…yn常微分方程初值问题一阶常微分方程的初值问题，即00)(),('yxyyxfy例0)0(2'yxy0)0(21'yxyy常微分方程的一般解(解析解)对一些典型的微分方程(可分离变量方程，一阶线性方程等等)，有可能找出它们的一般解表达式，然后用初始条件确定表达式中的任意常数，这样解即能确定。例如求解0)0(2'yxy解：分离变量得dy=2xdx积分得y=x2+c由初值得c=0故解为y=x2但是对于求解无法求出一般解！0)0(2'yxyy二、如何学习数值分析？课程简介1.注意掌握各种方法的基本原理2.注意各种方法的构造手法3.重视各种方法的误差分析4.做一定量的习题5.注意与实际问题相联系第一章绪论数值分析§1数值分析研究的对象与特点一、数值分析研究的对象二、数值分析研究的特点1.数值分析研究的对象数值分析是计算数学的一个主要部分，计算数学是数学科学的一个分支，它研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现.用计算机解决科学计算问题通常经历以下过程实际问题数学模型数值计算方法程序设计上机计算结果应用数学计算数学2.数值分析研究的内容—函数的数值逼近(插值与拟合)—数值积分与数值微分—非线性方程数值解—数值线性代数—常微和偏微数值解，……数值分析实质上是以数学问题为研究对象，不像纯数学那样只研究数学本身的理论，而是把理论与计算紧密结合，着重研究数学问题的数值方法及理论。3.数值分析的特点(1)面向计算机，要根据计算机特点设计切实可行的有效算法.(2)有可靠的理论分析，能任意逼近并达到精度要求，对近似计算要保证收敛性和数值稳定性.(3)要有好的计算复杂性，时间复杂性好是指节省时间，空间复杂性好是指节省存贮量，这也是建立算法要研究的问题.(4)要有数值试验，即任何一个算法除了从理论上要满足上述三点外，还要通过数值试验证明是行之有效的.§2数值计算的误差一、误差来源的分类二、误差分析的重要性三、绝对误差和绝对误差限四、相对误差和相对误差限五、有效数字一、误差来源的类型1.模型误差从实际问题中抽象出数学模型——模型误差/*ModelingError*/2.观测误差通过测量得到模型中参数的值——观测误差/*MeasurementError*/注：通常根据测量工具的精度，可以知道这类误差的上限值。当数学模型得不到精确解时，要用数值计算方法求它的近似解，由此产生的误差称为截断误差或方法误差3.截断误差求近似解——方法误差(截断误差)/*TruncationError*/例如：在微积分中sinx可展开成xxxxxx,!7!5!3sin753但在计算机中计算时，常用前几项来代替，即抛弃了无穷级数的后段，这样就产生了截断误差。当|x|很小时，常用x代替sinx，其截断误差大约为x3/6。由于计算机字长有限，原始数据的输入及浮点数运算过程中都有可能产生误差，这样产生的误差称为舍入误差4.舍入误差机器字长有限——舍入误差/*RoundoffError*/在数值分析课程中，主要研究截断误差舍入误差二、误差分析的重要性考察如下两个方程组9999.19999.022121xxxx0001.29999.022121xxxx试思考这两个方程组的解的关系？容易看出系数矩阵完全相同，而常数项矩阵有微小差别，右端系数1.9999变成2.0001，其误差为2.0001-1.9999=0.0002=0.02%但对应的解为由此看出系数矩阵完全相同，而常数项矩阵有微小差别的方程组，其解竟然相差得很大！1121xx1321xx解的最大误差=2=200%据说，美军1910年的一次部队的命令传递是这样的:营长对值班军官:明晚大约8点钟左右，哈雷彗星将可能在这个地区看到，这种彗星每隔76年才能看见一次。命令所有士兵着野战服在操场上集合，我将向他们解释这一罕见的现象。如果下雨的话，就在礼堂集合，我为他们放一部有关彗星的影片。值班军官对连长:根据营长的命令，明晚8点哈雷彗星将在操场上空出现。如果下雨的话，就让士兵穿着野战服列队前往礼堂，这一罕见的现象将在那里出现。连长对排长:根据营长的命令，明晚8点，非凡的哈雷彗星将身穿野战服在礼堂中出现。如果操场上下雨，营长将下达另一个命令，这种命令每隔76年才会出现一次。排长对班长:明晚8点，营长将带着哈雷彗星在礼堂中出现，这是每隔76年才有的事。如果下雨的话，营长将命令彗星穿上野战服到操场上去。班长对士兵:在明晚8点下雨的时候，著名的76岁哈雷将军将在营长的陪同下身着野战服，开着他那“彗星”牌汽车，经过操场前往礼堂。三、绝对误差和绝对误差限定义设某一量的准确值为x，近似值为x*，则x*与x之差叫做近似值x*的绝对误差(简称误差)，记为xxxee**)(*？判断题：绝对误差是误差的绝对值．绝对误差的性质(1)绝对误差e(x*)可正可负(2)|e(x*)|的大小标志着x*的精确度(3)绝对误差e(x*)未知定义若指定一个适当小的正数，使*|*||*)(|xxxe有时用表示近似值x*的精度或准确值的所在范围。*xx则称为近似值x*的绝对误差限。**绝对误差限的性质(1)在实际问题中，绝对误差一般是有量纲的，绝对误差限也是有量纲的。例如，测得某物体的长度为5m，其误差限为0.01m(2)绝对误差限是正的，有无穷多个。|*||*)(|xxxe若已知是绝对误差限，由于则比大的任意正数均是绝对误差限。思考题：设有两个温度计，其一测量1000℃时的绝对误差限为5℃，而另一个测量100℃时的绝对误差限为1℃。问：哪一个温度计更精确？四、相对误差和相对误差限答：虽然后者绝对误差限的数值较小，但第一种温度计更为精确。决定一个量的近似值的精确度除了要看绝对误差的大小外，还要考虑到该量本身的大小。定义:绝对误差与准确值之比0,**)(*)(*xxxxxxexeerr称为x*的相对误差.(2)由于准确值x未知，故实际问题中，当||较小时，常取*)(xer**)(*)(xxexer注(1)相对误差是个无量纲量,值小者精度高。*)(|||*)(||*)(|xxxexerr当||较小时，可用下式计算*)(xer||*)(*)(xxxr定义若指定一个适当小的正数，使*)(xr则称为近似值x*的相对误差限*)(xr当x有很多位数字时，常按照“四舍五入”原则取前几位数字作为x的近似值例：设x=π=3.1415926···取x1*=3作为π的近似值，则0110211415.0||e五、有效数字取x2*=3.14作为π的近似值，则22102100159.0||e取x3*=3.1416作为π的近似值，则43102100000734.0||e它们的误差都不超过某一数位的半个单位。若近似值x*的绝对误差限是某一位的半个单位，该位到x*的第一位非零数字一共有n位，则称近似值x*有n位有效数字，或说x*精确到该位。定义：有效数字若将准确值x的近似值x*表示成标准形式12*0.10mnxaaa而其误差限nmxx1021*则说近似值x*具有n位有效数字。这里n为正整数，m为整数，每个均为0,1，…，9中的一个数字，),,2,1(niai10a注：有效数字的等价定义定理1.1若x*具有n位有效数字，则其相对误差限满足)1(1*1021nrae反之，若x*的相对误差限满足*re)1(1*10)1(21nrae则近似值x*至少具有n位有效数字。例：为使的相对误差小于0.001%,至少应取几位有效数字？*π解：假设*取到n位有效数字，则其相对误差上限为111*102nrεa要保证其相对误差小于0.001%，只要保证其上限满足111*100.001%2nrεa已知a1=3，则从以上不等式可解得n6log6，即n6，应取*=3.14159。§3避免误差危害的若干原则(一)要避免相近两数相减(二)要防止大数“吃掉”小数(三)注意简化计算步骤，减少运算次数(四)要避免绝对值小的数作除数(五)设法控制误差的传播(一)要避免相近两数相减1yxx的值。例:求当x=1000，y的准确值为0.01580.(1)直接相减1001100031.6431.620.02y(2)若将原式改写为111yxxxx则y=0.01581几种经验性避免方法：;xεxεxεx;1lnlnlnxεxεx||x很小，3261211xxxex(二)要防止大数“吃掉”小数例：用单精度计算的根。299(101)100xx精确解为110291x,x算法1：利用求根公式aacbbx242在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1的指数部分须变为1010，则：1=0.0000000001