数值计算方法第一章

1数值计算方法徐晶理学院数学系Mobile-mail:309807913@Office:理学院数学系2102教材

(TextBook)数值计算方法令锋傅守忠等编著

（国防工业出版社）

参考书目

(Reference)

数值分析王金铭刘艳秋陈欣大连理工大学出版社

数值分析李庆扬王能超易大义华中科技大学出版社计算方法典型例题与解法高培旺等国防科技大学出版社

计算方法典型例题与分析孙守忠科学出版社教材及参考书微积分线性代数常微分方程C、C++语言预备知识教学进度课次教学内容1第1章数值计算方法概论2§2.1对分区间法§2.2简单迭代法3§2.3加速收敛迭代法

§2.4牛顿迭代法§2.5正割法4§3.1Gauss列主元消去法5§3.2LU分解法

6§3.3三对角方程组的追赶法7§4.1向量范数与矩阵范数8§4.2Jacobi迭代法§4.3Gauss-Seidel迭代法9§4.4迭代法的收敛性§4.5逐次超松弛迭代法10§5.1代数插值法及其唯一性

§5.2Lagrange插值法11

§5.3Newton插值法§5.4Hermite插值法12

§5.5三次样条插值法13§5.6最小二乘拟合法14§6.1插值型求积公式§6.2三个常用的求积公式及其误差

15§6.3复化求积公式16§6.4Romberg求积公式§6.5Gauss求积公式

§6.6数值微分法

17§7.1Euler方法§7.2高阶Taylor方法18§7.3Runge-Kutta法51.闭卷考试占60%2.出勤占10%3.测验及平时作业占30%成绩构成一、数值计算方法

能够做什么？§1.1数值计算方法的基本内容与特点今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗。问上、中、下禾实一秉各几何？答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。-------《九章算术》1、一个两千年前的例子线性方程组的求解！2、天体力学中的Kepler方程x是行星运动的轨道，它是时间t的函数.非线性方程求根！全球定位系统：在地球的任何一个位置，至少可以同时收到4颗以上卫星发射的信号

3、全球定位系统（GlobalPositioningSystem,GPS)

表示地球上一个接收点R的当前位置，卫星Si的位置为，则得到下列非线性方程组记为其中，非线性方程组的求解！4、已经测得在某处海洋不同深度处的水温如下：深度（M）46674195014221634水温（oC）7.044.283.402.542.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米…）处的水温.插值法！5、人口预测

下面给出的是中国1900年到2000年的人口数，我们的目标是预测未来的人口数（数据量较大时）19505519619606620719708299219809870519901143332000126743数据拟合！6、铝制波纹瓦的长度问题建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的.假若要求波纹瓦长4英尺,每个波纹的高度(从中心线)为1英寸,且每个波纹以近似2π英寸为一个周期.求制做一块波纹瓦所需铝板的长度L.

这个问题就是要求由函数f(x)=sinx

给定的曲线从x=0到x=48英寸间的弧长L.

由微积分学我们知道,所求的弧长可表示为:上述积分称为第二类椭圆积分,它不能用普通方法来计算.数值积分！计算机辅助设计：波音777应用三维立体建模，数字化设计与有限元计算的第一架喷气客机。天气预报：计算能力的发展将把海洋、大气和生态系统的综合知识融合成一个气象变化模型。医学与生物工程：CT、核磁共振与Radon变换；至病基因与药物设计；人造生物材料的彷真响应；传染病动力学模型。现代科学计算在工程计算中的应用电子系统自动化设计：大规模集成电路的设计与逻辑检测。材料设计：性能设计的大规模计算与模拟：设计用于生产新的高热值、高压材料中的化学蒸发沉淀反应器。车辆与道路工程设计与模拟：车辆与道路相互作用综合系统设计。存储与物流系统：工农业发展使得产品的存储、交流和时效性极大提高；废物和垃圾问题成为城市生活的重大问题。规划计算和系统分析成为常用计算方法。燃烧与爆炸工程：燃烧对环境的影响；计算流体力学与爆炸工程。网络设计与计算：搜索引擎的设计航空航天工程：神州飞船系列信息与通信工程：GPS卫星导航二、数值计算方法的意义、内容与方法软件的核心就是算法。20世纪最伟大的科学技术发明---计算机

计算机是对人脑的模拟，它强化了人的思维智能；计算机的发展和应用，已不仅仅是一种科学技术现象，而且成了一种政治、军事、经济和社会现象；没有软件的支持，超级计算机只是一堆废铁而已；算法犹如乐谱，软件犹如CD盘片，硬件如同CD唱机。理论研究科学实验科学计算计算数学诺贝尔奖得主,计算物理学家Wilson提出现代科学研究的三大支柱

科学方法论的巨大变革：如果说伽利略和牛顿在科学发展史上奠定了实验和理论这两大科学方法的支柱，那么由冯.诺依曼研制的现代电子计算机把计算推上了人类科学活动的前沿，使计算成为第三种方法。21世纪信息社会的两个主要特征：“计算机无处不在”“数学无处不在”21世纪信息社会对科技人才的要求：--会用数学解决实际问题--会用计算机进行科学计算建立数学模型选取计算方法编写上机程序计算得出结果科学计算解题过程数值计算方法是计算数学的一个主要组成部分，“什么是数值计算方法？”它主要研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法）;对求得的解的精度进行评估以及在计算机上实现求解等。

数值计算方法已经成为计算机处理实际问题的一个重要手段，从宏观天体运动学到微观分子细胞学，从工程系统到社会经济系统，无一能离开数值计算方法。因此，数值计算与计算机模拟被称为“第三种科学研究方法”。

科学计算可视化是目前研究的热门问题，下面的艺术图形是基于科学计算的数据表示的例子分形图混沌图1、数值逼近

插值与拟合、FFT、数值积分与微分2、数值代数

代数基础、线性代数方程组的解法、非线性代数方程（组）的解法、特征值与特征向量3、微分方程数值解

ODE、PDE和有限元法4、最优化方法*无约束优化与约束优化方法融进了机器学习计算、仿生计算、网络计算、以数据为核心的计算和各种普适计算、非线性科学计算等内容。传统的数值计算的主要研究内容

现代计算方法：数值计算方法的主要特点借助计算机提供切实可行的数学算法.想的精确度;收敛且稳定;误差可以分析或估计.所提出的算法必须具有：可靠的理论分析;理时间复杂性好__指节省时间；空间复杂性好__指节省存储量。计算复杂性好

通过数值实验证明算法行之有效.采用“近似替代”方法→逼近采用“构造性”方法采用“离散化”方法

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

复杂的计算归结为简单过程的多次重复，易于用循环结构来实现（迭代法）。采用各种搜索方法构造数值算法的主要手段

希望：求近似解，但方法简单可行，行之有效（计算量小，误差小,需存储单元少等）,

以计算机为工具，易在计算机上实现。计算机运算:

只能进行加，减，乘，除等算术运算和一些逻辑运算。数值计算方法：

把求解数学问题转化为按一定次序只进行加，减，乘，除等基本运算.设计数值算法的出发点？三、如何学好数值计算方法？hhhhhhhhhhhhhgggg几点纪律要求上课至少提前2分钟到教室，不早退上课期间手机静音课前预习，课后复习，及时解决存在的问题课堂上认真听讲，适当记笔记，积极回答问题作业独立完成，保质保量按时上交有事提前请假，否则，记无故旷课威尔金森（JamesHardy.Wilkinson，1919-1986）Wilkinson是数值分析和数值计算的开拓者和奠基人。1940年，开始研究弹道的数学模型与数值计算。1946年成为Turing的助手，协助设计PilotACE计算机。1969年他当选为英国皇家学会院士；1970年工业和应用数学会(s1am)授予他冯·诺伊曼奖；1987年他获得美国数学会的chauvenet奖。著名的美国阿尔贡国家实验室曾聘威尔金森为荣誉高级研究员并两次向他授奖。

Wilkinson在数值分析研究领域作出了杰出贡献，是数值计算的早期开拓者，其工作加速了数字计算机(在科学计算中)的使用。他研究的主要问题是线性代数方程组和矩阵特征值问题的数值解法，特别是他的向后误差分析法(backwarderroranalysis)的创造性工作奠定了数值分析和数值计算早期的理论基础。

1975年J.H.Wilkinson成为第五位图灵奖获得者。36用计算机进行实际问题的数值计算时，往往求得是问题的近似解，都存在误差。误差公理：任何测量（观测）都存在误差。误差是不可避免的，即要允许误差，又要控制误差。§1.2误差的基本理论一、误差的来源与分类从实际问题中抽象出数学模型

——模型误差ModelError

例:质量为m的物体，在重力作用下,自由下落，其下落距离s与时间t的关系是：

其中g

为重力加速度。通过测量得到模型中参数的值

——观测误差ObservationError

截断误差——方法误差TruncationError例如，当函数用Taylor多项式

近似代替时，数值方法的截断误差是

与0之间。在舍入误差——Round-offError

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

=3.1415926…

小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：四舍五入后……在数值计算方法中，主要研究截断误差和舍入误差（包括初始数据的误差）对计算结果的影响！二、误差的概念1、绝对误差AbsoluteError是近似值的绝对误差,简称为误差。

若近似值偏大，称“强近似”或“盈近似”若近似值偏小，称“弱近似”或“亏近似”注

越小，精度越高；定义1-1：设是准确值，为

的一个近似值，称例1、用毫米刻度尺测量长度为的物体，测得其长度为，是物体实际长度的一个近似值，由于直尺以毫米为刻度，故误差不超过半个毫米，则有：通常记为：绝对误差限

例2、真空中光速c的近似值为例1、用毫米刻度尺测量长度为的物体，测得其长度为，是物体实际长度的一个近似值，由于直尺以毫米为刻度，故误差不超过半个毫米，则有：在应用上，常常采用下列写法来刻划的精度。因准确值往往无法知道，只能估计：（上界）叫做的绝对误差限。即落在内。44例如，有两个量，则虽然比大4倍，但比

所以除考虑误差的大小外，还应考虑准确值本身的大小.要小得多，这说明近似的程度比近似的程度好.45定义1-2：相对误差

实际计算中，常用下式代替：2、相对误差：RelativeError因实际误差未知，常采用：相对误差限

近似值的误差与准确值x的比值

46定义1-3：若近似值的误差限是某一位的半个单位，该位到的第一位非零数字共有位，就说有位有效数字。例意义：有效数字越多，误差限越小，数值越准确。3、有效数字significantdigits

如果一个近似数的所有数字均为有效数字，则称之为有效数。47则有位有效数字，精确到。类似科学计数法式中,(小数点后1位）；可以为零；为整数。如果48有效数字与相对误差的关系

有效数字

相对误差限已知x*有n位有效数字，则其相对误差限为相对误差限有效数字已知x*的相对误差限可写为则可见x*至少有n位有效数字。Th1.2：

设反之,若的相对误差的绝对值大于，其中为整数,为正整数,。有位有效数字。则至多若至多有位有效数字,即是有效数字,而不是有效数字,则的相对误差的绝对值必大于;证明：不是有效数字

反之,若

则

不是有效数字，

即至多有位有效数字.

51例为使的相对误差小于0.001%,至少应取几位有效数字？解假设*取到n

位有效数字，则其相对误差上限为要保证其相对误差小于0.001%，只要保证其上限满足已知a1=3，则从以上不等式可解得n>6log6，即n6，应取*=3.14159。52注意：①准确值经“四舍五入”后，都为有效数字；②有效数字位数相同，误差可能不同；例如：但相同时，有效位数越多，误差越小。③移动小数点时，不要改变有效数字；例如：④常数、系数、准确数有无数多个有效数字。例如：，，，

0.02030有4位有效数字，而0.0203只有3位有效。12300如果写成0.123105，则表示只有3位有效数字。

数字末尾的0不可随意省去！53按四舍五入原则写出下列各数具有5位有效数字的近似数：解：按定义，187.93,的5位有效数字近似数是8.0000，而不是8，例187.9325,0.03785551,8.000033,2.7182818.上述各数具有5位有效数字的近似数分别是因为8只有1位有效数字.注意：0.037856,8.0000,2.7183.54加、减、乘、除运算的误差为：

4、数值运算的误差估计

（避免绝对值很大的数为乘数）（避免为很小的数为除数）

（避免两相近数相减运算）5、函数的误差估计当自变量有误差时，计算函数值也会产生误差，其误差限可利用函数的Taylor展开式进行估计。

设是一元函数，的近似值为,以近似，其误差限记作，可用Taylor展开

介于之间.取绝对值得假定与的比值不太大,,可忽略的高阶项,于是可得计算函数的误差限为

当为多元函数时计算,如果的近似值为,则的近似为于是函数值的误差由Taylor展开,得：假定与的比值不太大,,可忽略的高阶项,于是可得计算函数的误差限为

于是误差限为而的相对误差限为(1.2.1)(1.2.2)例:已测得某场地长的值为,宽的值为,已知,.试求面积的绝对误差限与相对误差限.其中由式(1.2.1)得解:因

而于是绝对误差限为相对误差限为

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

1.3数值算法设计的原则61（3）不在计算机数系中的数做四舍五入处理。例在四位浮点十进制数的计算机上计算1+104（1）加法先对阶,后运算,再舍入；（2）乘法先运算,再舍入；=0.1000105=104=

0.10001105

=0.00001105+0.1000105

(对阶，靠高阶)解1+104=0.1000101+0.1000105

(浮点数形式)(运算)(舍入)计算机中数的计算特点例：求定积分的值.

解：直接积分可产生递推公式若取初值可得递推公式按公式就可以逐步算出注意此公式精确成立，且Whathappened?!不稳定的算法！这就是误差传播所引起的危害!

NYBJ蝴蝶效应——纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！这是一个病态问题由题设中的递推公式（1）可看出，

的误差扩大了5倍后传给

，因而初值

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

的增大愈来愈严重。要怎么做才能解决这个问题呢?可求得I90.017，按改写后的公式可逐次求得不妨设I9I10，于是由将公式变为

I80.019I70.021 I60.024I80.028 I40.034I30.043 I20.058I10.088 I00.182稳定的算法！

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

因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定的算法，称为无条件稳定。而对某些数据数值稳定，对其它数据数值不稳定的算法，称为条件稳定。1.简化计算步骤，避免误差积累。一般来说，计算机处理下列运算的速度为例：多项式求值：给定的x

求下列n次多项式的值。

解：1.用一般算法，即直接求和法；

2.逐项求和法；3.秦九韶方法(即Hornor算法）；先计算x2,x3,…,

xn,再作线性组合，需做2n-1次乘法和n次加法。解法一：直接求和法解法二：逐项求和法按顺序依次计算每一项的值再求和，需做n(n+1)/2次乘法和n次加法。解法三：秦九韶算法（即Horner算法）只需做n次乘法和n次加法。且可以递推实现。好处：①节省计算时间；②减少舍入误差。2.要避免两个相近的数相减在数值计算中，两个相近的数作减法时有效数字会损失。例:

求的值。当x=1000，y

的准确值为0.01580

放大相对误差限，导致计算结果有较大误差！类似地

(2)若将原式改写为则y=0.01581(1)直接相减有3位有效数字！只有1位有效数字当|x|<<1时：3.尽量避免绝对值太小的数作分母例：如分母变为0.0011，也即分母只有0.0001的变化时结果相差这么大!4.避免大数吃小数精确解为算法1：利用求根公式例：用单精度计算的根。在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1的指数部分须变为1010，则：1=0.00000000011010，取单精度时就成为：109+1=0.100000001010+0.000000001010=0.100000001010算法2：先解出再利用注：求和时从小到大相加，可使和的误差减小。例：按从小到大、以及从