数值分析第一章

数值分析第一章1.认识建立算法和对每个算法进行理论分析是基本任务，主动适应“公式多”的特点；

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

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

4.认真进行数值计算的训练，学习各章算法完全是为用于实际计算，必须真会算。如何进行学习？第2页,共58页，星期六，2024年，5月数值分析简史1955周恩来领导10年科技规划，提出发展几个新技术，包括计算技术（计算机，程序设计，计算数学），半导体技术，自动化技术。1956成立计算技术研究所筹备处，主任华罗庚，手下有两个组（计算机与计算数学）。在其领导下于数学所成立计算方法讨论班。1958计算所成立，带半军事性质，并且与苏联合作在中科院计算研究所造出104机。北大，吉大，复旦，南大相继成立计算数学专业。57－59年吉大聘请苏联梅索夫斯基开办讲义班，其中参与者有李荣华，冯果忱，李岳生，李庆扬，蒋尔雄，康立山，徐翠薇等。第3页,共58页，星期六，2024年，5月数值分析简史1977年开始写国内的教材李荣华，冯果忱《微分方程数值解》李岳生等《数值逼近论》曹志浩等《数值代数》和《矩阵计算与方程求根》这三门课程为1984年在国内几所重点大学开设的“计算数学及其应用软件"专业主干课程。第4页,共58页，星期六，2024年，5月信息与计算科学简史1958年计算数学专业1984年“计算数学及其应用软件”

加强计算机课程的分量1998年“信息与计算科学”

加强信息课程的分量

第5页,共58页，星期六，2024年，5月数值分析又称计算方法或数值计算方法，是一门与计算机应用密切结合的实用性很强的数学课程，它研究的是各种数学问题的一类近似解法——数值方法，即从一组原始数据（如模型中的某些参数）出发，按照确定的运算规则进行有限步运算，最终获得数学问题数值形式的满足精度要求的近似解。1.1研究对象第6页,共58页，星期六，2024年，5月通信卫星覆盖地球面积数学模型实际问题获取数据数值方法、程序数据结果将地球考虑成一个球体,设R为地球半径,h为卫星高度,D为覆盖面在平面的投影第7页,共58页，星期六，2024年，5月

数值分析方法课程主要讨论如何构造求数学模型近似解的算法，讨论算法的数学原理、误差和复杂性，配合程序设计进行计算试验并分析试验结果。

与纯数学的理论方法不同，用数值分析所求出的结果一般不是解的精确值或者准确的解析表达式，而是所求真解的某些近似值或近似曲线。第8页,共58页，星期六，2024年，5月实际问题数学模型数值计算方法程序设计上机计算数值结果根据数学模型提出求解的数值计算方法直到编出程序上机算出结果，这一过程便是数值分析研究的对象数值计算方法的任务第9页,共58页，星期六，2024年，5月数值计算方法的主要特点借助计算机提供切实可行的数学算法.想的精确度;收敛且稳定;误差可以分析或估计.所提出的算法必须具有：可靠的理论分析;理时间复杂性好__指节省时间；空间复杂性好__指节省存储量。计算复杂性好

通过数值实验证明算法行之有效.第10页,共58页，星期六，2024年，5月采用“近似替代”方法→逼近采用“构造性”方法采用“离散化”方法

把求连续变量的问题转化为求离散变量的问题采用“递推化”方法

复杂的计算归结为简单过程的多次重复，易于用循环结构来实现（迭代法）。采用各种搜索方法构造数值算法主要手段第11页,共58页，星期六，2024年，5月1、数值逼近

插值与拟合、数值积分与微分2、数值代数线性代数方程组的解法、非线性代数方程（组）的解法3、微分方程数值解

ODEPDE1.2研究内容第12页,共58页，星期六，2024年，5月1.3.1误差的来源与分类从实际问题中抽象出数学模型

——模型误差例:质量为m的物体，在重力作用下,自由下落，其下落距离s

与时间t的关系是：

其中g

为重力加速度。1.3

误差第13页,共58页，星期六，2024年，5月通过测量得到模型中参数的值

——观测误差求近似解——方法误差（截断误差）例如，当函数用maclaurin多项式

近似代替时，数值方法的截断误差是与0之间。在第14页,共58页，星期六，2024年，5月机器字长有限——

舍入误差

用计算机、计算器和笔算，都只能用有限位

=3.1415926…

小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：第15页,共58页，星期六，2024年，5月四舍五入后……在数值计算方法中，主要研究截断误差和舍入误差（包括初始数据的误差）对计算结果的影响！第16页,共58页，星期六，2024年，5月1.3.2误差与有效数字1、绝对误差与绝对误差限例:若用以厘米为最小刻度的尺去量桌子的长，大约为1.45米，求1.45米的绝对误差。1.45米的绝对误差=？不知道！定义：设是准确值，为

的一个近似值，称是近似值的绝对误差,简称为误差。

第17页,共58页，星期六，2024年，5月但实际问题往往可以估计出不超过某个正数，即则称为绝对误差限，有了绝对误差限就可以知道的范围为即落在内。在应用上，常常采用下列写法来刻划的精度。第18页,共58页，星期六，2024年，5月例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可见，绝对误差限

*不是唯一的，但*越小越好第19页,共58页，星期六，2024年，5月2、相对误差与相对误差限定义：设是准确值，是近似值，是近似值的误差，通常取为近似值的相对误差，记作，称一般情况下是不知道的，怎么办？第20页,共58页，星期六，2024年，5月事实上，当较小时是的二次方项级,故可忽略不计.相应地，若正数满足

则称为的相对误差限。第21页,共58页，星期六，2024年，5月例4.甲打字每100个错一个，乙打字每1000个错一个，求其相对误差限解：根椐定义:甲打字时的相对误差限

乙打字时的相对误差限第22页,共58页，星期六，2024年，5月3、有效数字定义：如果则说近似表示准确到小数后第位，并从这由上述定义第位起直到最左边的非零数字之间的一切数字都称为有效数字，并把有效数字的位数称为有效位数。第23页,共58页，星期六，2024年，5月定义:若近似值的误差限是某一位的半个单位,也即，若有位有效数字。则称其中，是1到9中的一个数字；是0到9中一个数字；为整数，且该位到的左边第一位非零数字共有位,就说有位有效数字。第24页,共58页，星期六，2024年，5月取作的近似值，就有三位有效数字；取作的近似值，就有五位有效数字。例如：

x-x*=0.0015926…0.002=0.210-20.510-2前面例1前面例2

x-x*=0.0000074…0.000008=0.810-50.510-4

第25页,共58页，星期六，2024年，5月关于有效数字说明①用四舍五入取准确值的前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,准确值具有无穷位有效数字第26页,共58页，星期六，2024年，5月4、误差限与有效数字的关系

则

至少具有位有效数字。Th1：

对于用式表示的近似数，若具有位有效数字，则其相对误差限为反之，若的相对误差限为第27页,共58页，星期六，2024年，5月例5已知近似数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%第28页,共58页，星期六，2024年，5月例6已知近似数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位有效数字

第29页,共58页，星期六，2024年，5月例7为使的近似数的相对误差小于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取三位有效数字

∴第30页,共58页，星期六，2024年，5月1.3.3数值运算的误差估计1、四则运算的误差估计两个近似数与,其误差限分别为及,它们进行加减乘除运算得到的误差限分别为第31页,共58页，星期六，2024年，5月从而有

的相对误差

对于近似值，函数在舍去右边第二项得到即的绝对误差可以得到附近按泰勒展式展开得到2、函数误差估计当自变量有误差时，计算函数值也会产生误差，其误差限可利用函数的Taylor展开式进行估计。

第32页,共58页，星期六，2024年，5月对绝对误差式两边取绝对值得

故的相对误差限的误差限而解释：第33页,共58页，星期六，2024年，5月

当为多元函数时计算,如果的近似值为,则的近似为于是函数值的误差由Taylor展开,得：多元函数的情况第34页,共58页，星期六，2024年，5月于是误差限为而的相对误差限为式(1)第35页,共58页，星期六，2024年，5月第36页,共58页，星期六，2024年，5月第37页,共58页，星期六，2024年，5月例8:已测得某场地长的值为,宽的值为,已知,.试求面积的绝对误差限与相对误差限.解:因

其中由式(1)得第38页,共58页，星期六，2024年，5月而于是绝对误差限为相对误差限为第39页,共58页，星期六，2024年，5月3、算法的数值稳定性

数值计算在设计算法时首先关心的是由它产生的计算结果的稳定性，而算法的稳定性与舍入误差是否增长密切相关。一个算法如果输入数据有微小扰动（即误差），而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称其为数值不稳定。

第40页,共58页，星期六，2024年，5月例9：求定积分的值.解：直接积分可产生递推公式若取初值第41页,共58页，星期六，2024年，5月可得递推公式按公式就可以逐步算出Whathappened?!不稳定的算法！这就是误差传播所引起的危害!

注意此公式精确成立，且第42页,共58页，星期六，2024年，5月由题设中的递推公式（1）可看出，

的误差扩大了5倍后传给

，因而初值

的误差对以后各步这就造成的计算结果严重失真。计算结果的影响，随着

的增大愈来愈严重。要怎么做才能解决这个问题呢?第43页,共58页，星期六，2024年，5月可求得I9

0.017，按改写后的公式可逐次求得不妨设I9

I10，于是由将公式变为(2)第44页,共58页，星期六，2024年，5月

I8

0.019I7

0.021 I6

0.024I5

0.028 I4

0.034I3

0.043 I2

0.058I1

0.088 I0

0.182稳定的算法！

在我们今后的讨论中，误差将不可回避，算法的稳定性会是一个非常重要的话题。第45页,共58页，星期六，2024年，5月注：递推公式(1)的舍入误差以5的幂次增长进行传播，因此是数值不稳定的，而递推公式(2)的舍入误差在一定范围内以0.2的幂次进行传播，随着n的增大，误差逐步减少，因此该算法是数值稳定的。

因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定的算法，称为无条件稳定。而对某些数据数值稳定，对其它数据数值不稳定的算法，称为条件稳定。第46页,共58页，星期六，2024年，5月病态问题和条件数

如果问题的输入数据有微小扰动，就会引起输出结果数据（即解）的很大扰动，称这样的问题为病态问题。相反的情形称为良态问题。对于病态的数学问题，用通常的算法求数值解都是不稳定的。病态和良态是相对的，没有严格的界限，通常用条件数大小来衡量问题的病态程度，条件数越大病态可能越严重。

条件数c(x)越大，f(x)的相对误差越大，通常认为时，问题是病态的。第47页,共58页，星期六，2024年，5月1.3.4数值计算中应该注意的一些原则1.要选择数值稳定的计算公式

定义一种数值方法，若原始数据有误差，而在计算的过程中，由于舍入误差的传播，使得近似计算结果与准确值相差很大，则称这种数值方法是不稳定的。否则，在计算的过程中，若舍入误差得到控制，近似计算结果能逼近准确值，则称这种数值方法是稳定的。第48页,共58页，星期六，2024年，5月，试问用递推公式例10给定采用正向递推和逆向递推求的值是否稳定？解设的近似值为则有从而有

对上式两边求绝对值得按给定的递推公式采用正向递推计算的值是不稳定的。第49页,共58页，星期六，2024年，5月2.要避免两个相近的数相减在数值计算中，两个相近的数作减法时有效数字会损失。例11:求当x=1000，y的准确值为0.01580

的值。第50页,共58页，星期六，2024年，5月类似地

(2)若将原式改写为则y=0.01581(1)直接相减有3位有效数字！只有1位有效数字第51页,共58页，星期六，2024年