第五版数值分完整析课件

数值分析电子课件工科研究生公共课程数学系列第1章绪论内容提要：1.1数值分析研究对象与特点1.2数值计算的误差1.3误差定性分析与避免误差危害1.1数值分析研究对象与特点一、数值分析研究对象计算机解决科学计算问题时经历的过程实际问题模型设计算法设计问题的解上机计算程序设计求方程求根牛顿法

程序设计解上机计算实例

数值分析的内容包括函数的数值逼近、数值微分与数值积分、非线性方程数值解、数值线性代数、常微和偏微数值解等。数值分析研究对象以及解决问题方法的广泛适用性，著名流行软件如Maple、Matlab、Mathematica等已将其绝大多数内容设计成函数，简单调用之后便可以得到运行结果。

但由于实际问题的具体特征、复杂性,以及算法自身的适用范围决定了应用中必须选择、设计适合于自己特定问题的算法，因而掌握数值方法的思想和内容是至关重要的。

本课程内容包括了微积分、代数、常微分方程的数值方法，必须掌握这几门课程的基础内容才能学好这门课程。二、数值分析的特点面向计算机，要根据计算机的特点提供切实可行的有效算法。有可靠的理论分析，能任意逼近并达到精度要求，对近似算法要保证收敛性和数值稳定性，还要对误差进行分析。这些都是建立在数学理论的基础上，因此不应片面的将数值分析理解为各种数值方法的简单罗列和堆积。要有好的计算复杂性，时间复杂性好是指节省时间，空间复杂性好是指节省存储量，这也是建立算法要研究的问题，它关系到算法能否在计算机上实现。要有数值实验，即任何一个算法除了从理论上要满足上述三点外，还要通过数值实验证明是行之有效的。三、数值分析的学习方法初学可能仍会觉得公式多，理论分析复杂。给出如下的几点学习方法。认识建立算法和对每个算法进行理论分析是基本任务，主动适应公式多和讲究理论分析的特点。注重各章节所研究算法的提出，掌握方法的基本原理和思想，要注意方法处理的技巧及其与计算机的结合。理解每个算法建立的数学背景、数学原理和基本线索，而且对一些最基本的算法要非常熟悉。要通过例子，学习使用各种数值方法解决实际计算问题。为掌握本课的内容，还应做一些理论分析和计算练习。1.2数值计算的误差一、误差的来源

在运用数学方法解决实际问题的过程中，每一步都可能带来误差。1、模型误差在建立数学模型时，往往要忽视很多次要因素，把模型“简单化”，“理想化”，这时模型就与真实背景有了差距，即带入了误差。2、测量误差数学模型中的已知参数，多数是通过测量得到。而测量过程受工具、方法、观察者的主观因素、不可预料的随机干扰等影响必然带入误差。3、截断误差数学模型常难于直接求解，往往要近似替代，简化为易于求解的问题，这种简化带入误差称为方法误差或截断误差。4、舍入误差计算机只能处理有限数位的小数运算，初始参数或中间结果都必须进行四舍五入运算，这必然产生舍入误差。误差分析是一门比较艰深的专门学科。在数值分析中主要讨论截断误差及舍入误差。但一个训练有素的计算工作者，当发现计算结果与实际不符时，应当能诊断出误差的来源，并采取相应的措施加以改进，直至建议对模型进行修改。二、绝对误差、相对误差与有效数字1、绝对误差与绝对误差限误差是有量纲的量，量纲同x，它可正可负。误差一般无法准确计算，只能根据测量或计算情况估计出它的绝对值的一个上界，这个上界称为近似值x*的误差限，记为ε*。2、相对误差与相对误差限

3、有效数字

定义3如果近似值x*的误差限是它某一数位的半个单位，我们就说x*准确到该位，从这一位起直到前面第一个非零数字为止的所有数字称x的有效数字.4、绝对误差，相对误差与有效数字的关系

绝对误差与相对误差：由两者定义可知。

绝对误差与有效数字：绝对误差不超过末位有效数字的半个单位。有效数字与相对误差限定理说明有效数位越多，相对误差限越小。定理也给出了相对误差限的求法。三、数值运算的误差估计1、四则运算2、函数误差当自变量有误差时计算函数值也产生误差，可以利用函数的泰勒展开式进行估计。1.3误差定性分析与避免误差危害一、病态问题与条件数1、病态问题：对一个数值问题本身如果输入数据有微小扰动（即误差），引起输出数据（即问题解）相对误差很大，就是病态问题。二、算法的稳定性

用一个算法进行计算，由于初始数据误差在计算中传播使计算结果误差增长很快就是数值不稳定的，先看下例。计算结果：n法一(A)法二(B)01234567890.63210.36790.26420.20740.17040.14800.11200.2160-0.72807.5520.63210.36790.26430.20730.17080.14550.12680.11210.10350.0684三、避免误差危害的若干原则1、要避免除数绝对值远远小于被除数绝对值的除法。用绝对值小的数作除数舍入误差会增大，如计算x/y，若0<|y|<<|x|，则可能对计算结果带来严重影响，应尽量避免。2、要避免两相近数相减

在数值中两相近数相减有效数字会严重损失。例如，x=532.65，y=532.52都具有五位有效数字，但x-y=0.13只有两位有效数字。通过改变算法可以避免两相近数相减。3、要防止“大数”吃掉小数

数值运算中参加运算的数有时数量级相差很大，而计算机位数有限，如不注意运算次序就可能出现大数“吃掉”小数的现象，影响计算结果的可靠性。

如用六位浮点数计算某市的工业总产值，原始数据是各企业的工业产值，当加法进行到一定程度，部分和超过100亿元（0.1×1011），再加产值不足10万元的小企业产值，将再也加不进去。而这部分企业可能为数不少，合计产值相当大.这种情况应将小数先分别加成大数，然后相加，结果才比较正确。这个例子告诉我们，在计算机数系中，加法的交换律和结合律可能不成立，这是在大规模数据处理时应注意的问题。4、注意简化计算步骤，减少运算次数

减少算术运算的次数不但可计算机的计算时间，还能减少误差的积累效应。使参加运算的数字精度应尽量保持一致，否则那些较高精度的量的精度没有太大意义。误差及算法误差算法数值稳定性概念算法设计注意要点分类度量传播舍入误差的产生及定义截断误差的产生及定义绝对误差（限）相对误差（限）有效数字三者的联系一元函数n元函数计算函数值问题的条件数二元算术运算知识结构图一第2章插值法内容提要2.1引言2.2拉格朗日插值2.3均差与牛顿插值公式2.4埃尔米特插值2.5分段低次插值2.6三次样条插值2.1引言许多实际问题都用函数y=f(x)来表示某种内在规律的数量关系。若已知f(x)在某个区间[a,b]上存在、连续，但只能给出[a,b]上一系列点的函数值表时，或者函数有解析表达式，但计算过于复杂、使用不方便只给出函数值表（如三角函数表、对数表等）时，为了研究函数的变化规律，往往需要求出不在表上的函数值。因此我们希望根据给定的函数表做一个既能反映函数f(x)的特性，又便于计算的简单函数P(x)，用P(x)近似f(x)。这就引出了插值问题。1、提出问题（插值法的定义）2、几何意义、外插、内插P(x)

f(x)x*(外插)x0x1x(内插)x2x3P(x*)

f(x*)3、插值的种类选取不同的函数族构造

P(x)得到不同类型的插值若P(x)是次数不超过n的代数多项式，就称为多项式插值；若P(x)为分段的多项式，就称为分段插值；若P(x)为三角多项式，就称为三角插值。本章只讨论多项式插值与分段插值。主要研究内容为如何求出插值多项式，分段插值函数；讨论插值多项式P(x)的存在唯一性、收敛性及估计误差等。4、多项式插值问题插值多项式的存在唯一性

定理1(存在唯一性)满足插值条件的不超过n次的插值多项式是存在唯一的。2.2拉格朗日插值一、线性插值与抛物插值1、线性插值y=f(x)L1(x)yxxk+1xk02、抛物插值求解基函数二、拉格朗日插值多项式

上面针对n=1和n=2的情况，得到了一次和二次插值多项式，这种用基函数表示的方法很容易推广到一般情况。下面讨论如何构造n+1个节点的n次插值多项式。定理表明：(1)插值误差与节点和点x之间的距离有关,节点距离x越近,插值误差一般情况下越小。

(2)若被插值函数f(x)本身就是不超过n次的多项式,则有f(x)≡g(x)。

3、应用举例用二次插值计算ln(11.25)的近似值,并估计误差。例2-2给定函数值表在区间[10,12]上lnx的三阶导数(2/x3)的上限M3=0.002,可得误差估计式注：实际上,ln(11.25)=2.420368,|R2(11.25)|=0.0000580

?分析：求解如上问题等价于求解x关于y的反函数问题。2.3均差与牛顿插值公式一、均差及其性质问题的引入：拉格朗日插值多项式，公式结构紧凑，理论分析方便，但插值节点增减时全部插值及函数均要随之变化，实际计算不方便，希望把公式表示为如下形式。1、均差定义2、均差的基本性质2、均差的基本性质2、均差的基本性质均差计算表例如由函数y=(x)的函数表写出均差表.解均差表如下二、牛顿插值公式解由差商表知[x0,x1]=-2,[x0,x1,x2]=3,[x0,x1,x2,x3]=-1,于是有N1(x)=5-2(x+2)=1-2xN2(x)=1-2x+3(x+2)(x+1)=3x2+7x+7N3(x)=3x2+7x+7-(x+2)(x+1)(x-1)=-x3+x2+8x+9例2-6

对例如中的(x),求节点为x0,x1的一次插值，x0,x1,x2的二次插值和x0,x1,x2,x3的三次插多项式.

例2-7给出f(x)的函数表，求4次牛顿插值多项式，并计算f(0.596)的近似值。2.4埃尔米特插值

不少实际的插值问题不但要求在节点上函数值相等，而且还要求对应的导数值也相等，甚至要求高阶导数也相等，满足这种要求的插值多项式就是埃尔米特（Hermite）插值多项式。

y=L10(x)y=L10(x)解法二（用重节点的均差表建立埃尔米特多项式）2.5分段低次插值一、高次插值的病态性质一般总认为Ln(x)的次数n越高逼近f(x)的精度越好，但实际上并非如此。这是因为对任意的插值节点，当n->∞时，Ln(x)不一定收敛于f(x)。20世纪初龙格（Runge）就给了一个等距节点插值多项式Ln(x)不一定收敛于f(x)的例子。

y=L10(x)

x1y=L10(x)o-10.5y1.51龙格现象二、分段线性插值分段线性插值就是通过插值点用折线段连接起来逼近f(x).分段线性插值三、分段抛物插值三、分段抛物插值2.6三次样条插值

样条曲线实际上是由分段三次曲线并接而成，在连接点即样点上要求二阶导数连续，从数学上加以概括就得到数学样条这一概念。下面我们讨论最常用的三次样条函数。一、三次样条函数y=L10(x)每个小区间上要确定4个待定系数，共有n个小区间，故应确定4n个参数。y=L10(x)二、三次样条插值函数的建立y=L10(x)y=L10(x)y=L10(x)y=L10(x)系数矩阵为严格对角占优阵，方程组有为一解。求法见5.3节追赶法。y=L10(x)y=L10(x)知识结构图二插值法工具分段多项式插值存在唯一性多项式插值Hermite插值插值公式误差估计差商、差分Lagrange插值基及函数定义性质定义性质导数型差商型Lagrange插值多项式Newton插值多项式等距节点插值公式存在唯一性误差估计插值公式分段线性插值（公式、误差估计、收敛性）分段三次Hermite插值（公式、误差估计、收敛性）三次样条插值（公式、存在唯一性、误差估计、收敛性）第三章函数逼近内容提要3.1基本概念3.2最佳平方逼近3.3曲线拟合的最小二乘法3.1基本概念

x0x3x5x7x1x4x6x2f(x)p(x)2、范数与赋范线形空间3、内积与内积空间1、最佳平方逼近3.2最佳平方逼近一、最小二乘法及其计算3.3曲线拟合的最小二乘法例3-3已知实测数据表如下,求它的拟合曲线0xy2468642例3-4

已知实测数据表如下,确定数学模型y=aebx,用最小二乘法确定a，b。分析：根据给定数据描图也可确定拟合曲线方程，但它不是线性形式。因此首先要将经验曲线线性化。本题可以采取等式两边取对数的形式线性化。数据表中的数值也相应的转化为取对数之后的数值，见下表。知识结构图三函数逼近理论预备知识范数（定义、常用范数）内积（定义、柯西-施瓦茨不等式、内积诱导范数）正交多项式（性质、正交化方法、常用正交多项式的定义和性质）函数逼近方法最佳一致逼近多项式最佳平方逼近定义存在唯一性定理切比雪夫定理最佳一次逼近多项式的确定最小二乘拟合定义法方程组和平方误差基于正交基的最佳平方逼近离散内积定义法方程组及哈尔条件基于正交基的最小二乘拟合第四章数值积分和数值微分内容提要4.1引言4.2牛顿-柯特斯公式4.3复化求积公式4.4龙贝格求积公式4.5高斯求积公式4.6数值微分4.1引言一、数值求积的基本思想对定义在区间［a,b］上的定积分但有时原函数不能用初等函数表示，有时原函数又十分复杂，难于求出或计算；另外如被积函数是由测量或数值计算给出的一张数据表示时，上述方法也不能直接运用。因此有必要研究积分的数值计算问题。积分中值定理告诉我们：平均高度f(ζ)

a

ζ

b

yxy=f(x)0

a

f((a+b)/2)

b

yxy=f(x)0

a

b

yxy=f(x)0梯形公式平均高度中矩形公式平均高度更一般地，我们构造具有下列形式的求积公式求积节点求积系数这类数值方法通常称为机械求积，其特点是将积分求值问题归结为函数值的计算，这就避开了牛顿-莱布尼兹公式需要寻求原函数的困难。二、代数精度的概念利用代数精度的概念构造求积公式三、插值型的求积公式4.2牛顿-柯特斯公式一、牛顿-柯特斯公式的导出柯特斯系数牛顿-柯特斯公式的代数精度4.3复合求积公式

一、问题与基本思想在使用牛顿-柯特斯公式时将导致求积系数出现负数(当n≥8时,牛顿.柯特斯求积系数会出现负数)，因而不可能通过提高阶的方法来提高求积精度。为了提高精度通常采用将积分区间划分成若干个小区间，在各小区间上采用低次的求积公式(梯形公式或辛普森公式)，然后再利用积分的可加性，把各区间上的积分加起来，便得到新的求积公式，这就是复化求积公式的基本思想。本节只讨论复化的梯形公式和复化的辛普森公式。二、复合梯形公式三、复合辛普森公式4.4龙贝格求积公式

一、梯形法的递推化(变步长求积法)

于是可以逐次对分形成一个序列{T1,T2,T4,T8,…},此序列收敛于积分真值I。当|T2n-Tn|<ε时，取T2n为I的近似值。以上算法称为变步长求积法。但由于此序列收敛太慢。下节我们将其改造成为收敛快的序列。二、龙贝格算法如何提高收敛速度以节省计算量是龙贝格算法要讨论的中心问题。这样我们从收敛较慢的{Tn}序列推出了收敛较快的{Sn}序列。可以证明{Sn}序列实际上就是逐次分半的复化辛普森公式序列。

这样我们从{Cn}序列又推出了收敛更快的{Rn}序列.{Rn}序列也称为龙贝格序列。我们从收敛较慢的{Tn}序列只用了一些四则运算，便推出了收敛更快的{Sn}序列,{Cn}序列和{Rn}序列。运算顺序表这里利用二分3次的数据（它们的精度都很差，只有两三位有效数字）通过三次加速求得R1=0.9460831,这个结果的每一位数字都是有效数字，可见加速效果是十分显著的。4.5高斯求积公式

一、一般理论

4.6数值微分一、中点方法与误差分析数值微分就是要用函数值的线性组合近似函数在某点的导数值。由导数定义差商近似导数得到数值微分公式。二、插值型的求导公式知识结构图四数值积分与数值微分数值积分基本概念牛顿-柯特斯公式复合求积公式数值微分中点方法插值型求导公式龙贝格求积公式高斯求积公式第五章解线性方程组的直接方法内容提要5.1引言与预备知识5.2高斯消去法5.3高斯列主元消去法5.4矩阵三角分解法5.5向量与矩阵的范数5.6误差分析5.1引言关于线性方程组的数值解法一般有两类：1、直接解法：经过有限次的算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）。但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。本章主要研究此类问题的解法。2、迭代法：用某种极限过程去逐步逼近现行方程组精确解的方法。迭代法具有需要计算机的存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点。5.2高斯消去法在求解三角方程组,得高斯消去法的条件5.3高斯主元素消去法列主元消去法5.4矩阵三角分解法Ax=b是线性方程组,A是n×n方阵,并设A的各阶顺序主子式不为零。令A(1)=A,当高斯消元法进行第一步后,相当于用一个初等矩阵左乘A(1)

。不难看出，这个初等矩阵为重复这个过程，最后得到一般地

这就是说，高斯消去法实质上产生了一个将A分解为两个三角形矩阵相乘的因式分解，于是我们得到如下重要定理。当A进行LU分解后，Ax=b就容易解了.即Ax=b等价于:

追赶法在一些实际问题中，例如解常微分方程边值问题，热传导方程以及船体数学放样中建立三次样条函数等，都会要求解系数矩阵为对角占优的三对角线方程组其中|i-j|>1时,aij=0,且满足如下的对角占优条件:(1)|b1|>|c1|>0,|bn|>|an|>0(2)|bi|≥|ai|+|ci|,aici≠0,i=2,3,…,n-1.5.5向量和矩阵的范数定义1(向量范数)x和y是Rn中的任意向量,向量范数‖•‖是定义在Rn上的实值函数,它满足:(1)‖

x

‖≥0,并且当且仅当x=0时,‖

x

‖=0;(2)‖k

x

‖=|k|‖

x

‖,k是一个实数;(3)‖

x+y

‖≤‖

x

‖+‖

y

‖常使用的向量范数有三种,设x=(x1,x2,…,xn)T

常使用的矩阵范数有三种,设x=(x1,x2,…,xn)T

5.6误差分析知识结构图五直接法解方程组高斯消去法矩阵的正交三角化及应用定义常用范数范数的性质初等反射阵平面旋转变换矩阵矩阵的QR分解应用：求解超定方程组高斯消去法高斯若当消去法列主元消去法矩阵三角分解法LU分解平方根分解LDLT分解追赶法解三对角方程组向量和矩阵的范数矩阵条件数及迭代改善法第六章解线性代数方程组的迭代法内容提要6.1引言6.2基本迭代法6.3迭代法的收敛性即AX=b其中A为非奇异矩阵，当A为低阶稠密矩阵时，线性方程组用直接法(如高斯消去法和三角分解法)是有效的，但对于由工程技术中产生的大型稀疏矩阵方程组（A的阶数n很大，但零元素较多），利用迭代法求解是适合的。在计算机内存和运算两方面，迭代通常都可利用A中有大量零元素的特点。考虑线性方程组6.1引言本章将介绍迭代法的一般理论及雅可比迭代法、高斯—塞德尔迭代法、超松弛迭代法，研究它们的收敛性。6.2基本迭代一、雅可比迭代法二、高斯—塞德尔迭代法SOR迭代法的计算公式:对k=0,1,…,三、逐次超松驰(SOR)迭代法说明:1)ω=1,即为GS（高斯-赛德尔迭代法）;2)ω>1，称为超松驰法；

ω<1，称为低松驰法；3)SOR方法每迭代一次主要运算量是计算一次矩阵与向量的乘法。例6-3

用SOR迭代法解线性代数方程组6.3迭代法的收敛性一、一阶定常迭代法的基本定理

注：定理5中的矩阵是迭代矩阵，常用格式的迭代矩阵如下：1)雅可比迭代法:BJ=D-1(L+U)，fJ=D-1b;2)高斯-赛德尔迭代法:BG=(D-L)-1U，fG==(D-L)-1b;3)SOR迭代法:BSOR=(D-ωL)-1{(1-ω)D+ωU}，fSOR=ω(D-ωL)-1b.例6-4考察用雅可比迭代法求解线性方程组二、某些特殊方程组的迭代收敛性定义3（1）按行严格对角占优（2）按行弱对角占优上式至少有一个不等号严格成立。定理8(对角占优定理)若矩阵A按行(或列)严格对角占优，或按行(或列)弱对角占优且不可约；则矩阵A非奇异。

定理9若矩阵A按行(或列)严格对角占优,或按行(或列)弱对角占优不可约；则Jacobi迭代、Gauss-Seidel迭代都收敛。定理12对于线性方程组Ax=b，若(1)A为对称正定矩阵，(2)0<ω<2，则解Ax=b的SOR迭代收敛。

定理13对于线性代数方程组Ax=b，若A按行(或列)严格对角占优，或按行(或列)弱对角占优不可约；则当0<ω≤1时，SOR迭代收敛。知识结构图六迭代法解方程组迭代法基本概念高斯-赛德尔迭代法迭代格式收敛条件（充要条件、充分条件四个）SQR迭代法迭代法收敛速度雅可比迭代法迭代格式收敛条件（充要条件、充分条件四个）迭代格式收敛条件（充要条件、必要条件、充分条件五个）第七章解非线性方程求根内容提要7.1方程求根与二分法7.2迭代法及其收敛性7.3牛顿法7.4弦截法7.1方程求根与二分法一、引言非线性方程的分类由此可知方程的有根区间为[1,2][3,4][5,6]求根问题的三个方面：存在性，分布，精确化。二、二分法0xyX*x0aby=f(x)a1b1二分法的优点是算法简单，且总是收敛的，缺点是收敛太慢,故一般不单独将其用于求根，只用其为根求得一个较好的近似值。7.2迭代法一、不动点迭代与不动点迭代法上述迭代法是一种逐次逼近法，其基本思想是将隐式方程归结为一组显示的计算公式，就是说，迭代过程实质上是一个逐步显示的过程。继续迭代下去已经没有必要，因为结果显然会越来越大，不可能趋于某个极限。这种不收敛的迭代过程称作是发散的。一个发散的迭代过程，纵使进行了千百次迭代，其结果也毫无价值。因此，迭代格式形式不同，有的收敛，有的发散，只有收敛的迭代过程才有意义，为此要研究不动点的存在性及迭代法的收敛性。二、不动点的存在性与迭代法的收敛性三、局部收敛性与收敛阶7.3牛顿法一、牛顿法及其收敛性二、牛顿法应用举例三、简化牛顿法与牛顿下山法四、重根情形7.4弦截法知识结构图七方程近似求根基本概念（单根、重根、有根区间、不动点、收敛阶）求根