2014 数值分析课件

数值分析电子课件数值分析电子课件 工科研究生公共课程数学系列 辽宁科技大学 理学院 任 课 教 师：熊 焱 第第 1章章 绪绪 论论 内容提要： 1.1 数值分析研究对象与特点 1.2 数值计算的误差 1.3 误差定性分析与避免误差危害 1.1 数值分析研究对象与特点 一、数值分析研究对象 计算机解决科学计算问题时经历的过程 实际问题 模型设计 算法设计 问题的解上机计算程序设计 求 方程求根 牛顿法 程序设计 解上机计算 实例 数值分析的内容包括函数的数值逼近、数值微分与数值积 分、非线性方程数值解、数值线性代数、常微和偏微数值解等 。 数值分析研究对象以及解决问题方法的广泛适用性，著名流 行软件如 Maple、 Matlab、 Mathematica等已将其绝大多数内容 设计成函数，简单调用之后便可以得到运行结果。 但由于实际问题的具体特征、复杂性 , 以及算法自身的适 用范围决定了应用中必须选择、设计适合于自己特定问题的算 法，因而掌握数值方法的思想和内容是至关重要的。 本课程内容包括了微积分、代数、常微分方程的数值方法 ，必须掌握这几门课程的基础内容才能学好这门课程。 二、数值分析的特点 面向计算机，要根据计算机的特点提供切实可行的有效算 法。 有可靠的理论分析，能任意逼近并达到精度要求，对近似 算法要保证收敛性和数值稳定性，还要对误差进行分析。 这些都是建立在数学理论的基础上，因此不应片面的将数 值分析理解为各种数值方法的简单罗列和堆积。 要有好的计算复杂性，时间复杂性好是指节省时间，空间 复杂性好是指节省存储量，这也是建立算法要研究的问题 ，它关系到算法能否在计算机上实现。 要有数值实验，即任何一个算法除了从理论上要满足上述 三点外，还要通过数值实验证明是行之有效的。 三、数值分析的学习方法 初学可能仍会觉得公式多，理论分析复杂。给出如下的 几点学习方法。 认识建立算法和对每个算法进行理论分析是基本任务，主 动适应公式多和讲究理论分析的特点。 注重各章节所研究算法的提出，掌握方法的基本原理和思 想，要注意方法处理的技巧及其与计算机的结合。 理解每个算法建立的数学背景、数学原理和基本线索，而 且对一些最基本的算法要非常熟悉。 要通过例子，学习使用各种数值方法解决实际计算问题。 为掌握本课的内容，还应做一些理论分析和计算练习。 1.2 数值计算的误差 一、误差的来源 在运用数学方法解决实际问题的过程中，每一步都可能带 来误差。 1、模型误差 在建立数学模型时，往往要忽视很多次要因素， 把模型 “简单化 ”， “理想化 ”，这时模型就与真实背景有了差距 ，即带入了误差。 2、测量误差 数学模型中的已知参数，多数是通过测量得到。 而测量过程受工具、方法、观察者的主观因素、不可预料的随 机干扰等影响必然带入误差。 3、截断误差 数学模型常难于直接求解，往往要近似替代，简 化为易于求解的问题，这种简化带入误差称为方法误差或截断 误差。 4、舍入误差 计算机只能处理有限数位的小数运算，初始参 数或中间结果都必须进行四舍五入运算，这必然产生舍入误 差。 误差分析是一门比较艰深的专门学科。在数值分析中主要 讨论截断误差及舍入误差。但一个训练有素的计算工作者，当 发现计算结果与实际不符时，应当能诊断出误差的来源，并采 取相应的措施加以改进，直至建议对模型进行修改。 二、绝对误差、相对误差与有效数字 1、绝对误差与绝对误差限 误差是有量纲的量，量纲同 x，它可正可负。 误差一般无 法准确计算，只能根据测量或计算情况估计出它的误差绝对值 的一个上界，这个上界称为近似值 x* 的误差限，记为 *。它 是正数，有量纲的。 2、相对误差与相对误差限 3、有效数字 定义 1-3 如果近似值 x*的误差限是某一位的半个单位，该 位到 x *的第一位非零数字共有 n位，就说 x *有 n位有效数 字 . 4、绝对误差，相对误差与有效数字的关系 绝对误差与相对误差：由两者定义可知。 绝对误差与有效数字： 绝对误差不超过末位有效数字的半个单位。 有效数字与相对误差限 定理说明有效数位越多，相对误差限越小。定理也给出了 相对误差限的求法。 三、数值运算的误差估计 1、四则运算 2、函数误差 当自变量有误差时计算函数值也产生误差，可以利用 函数的泰勒展开式进行估计。 1.3 误差定性分析与避免误差危害 一、病态问题与条件数 1、病态问题： 对一个数值问题本身如果输入数据有微小扰动（ 即误差），引起输出数据（即问题解）相对误差很大，这就是 病态问题。 二、算法的稳定性 用一个算法进行计算，由于初始数据误差在计算中传播使 计算结果误差增长很快，就是数值不稳定的，先看下例。 计算结果 n 法一 (A) 法二 (B) 0 1 2 3 4 5 6 7 8 9 0.6321 0.3679 0.2642 0.2074 0.1704 0.1480 0.1120 0.2160 -0.7280 7.552 0.6321 0.3679 0.2643 0.2073 0.1708 0.1455 0.1268 0.1121 0.1035 0.0684 三、避免误差危害的若干原则 1、 要避免除数绝对值远远小于被除数绝对值的除法。 用绝对值小的数作除数舍入误差会增大，如计算 x/y， 若 0时， Ln(x)不一定收敛于 f(x)。 20世纪初龙格（ Runge）就给了一 个等距节点插值多项式 Ln(x)不一定收敛于 f(x)的例子。 y=L10(x) x1 y=L10(x) o-1 0.5 y1.5 1 龙格现象 二、分段线性插值 分段线性插值就是通过插值点用折线段连接起来逼近 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基本概念 x0 x3 x5 x7x1 x4 x6x2 f(x) p(x) 2、范数与赋范线性空间 3、内积与内积空间 1、最佳平方逼近 3.2 最佳平方逼近 一、最小二乘法及其计算 3.3 曲线拟合的最小二乘法 例 3-3 已知 实测 数据表如下 ,求它的 拟 合曲 线 xi 1 2 3 4 5 yi i 4 4.5 6 8 8.5 2 1 3 1 1 0 x y 2 4 6 8 6 4 2 例 3-4 已知 实测 数据表如下 ,确定数学模型 y=aebx, 用最小二乘法确定 a， b。 i 0 1 2 3 4 xi yi 1.00 1.25 1.50 1.75 2.00 5.10 5.79 6.53 7.45 8.46 分析：根据给定数据描图也可确定拟合曲线方程，但它不是 线性形式。因此首先要将经验曲线线性化。本题可以采取等 式两边取对数的形式线性化。数据表中的数值也相应的转化 为取对数之后的数值，见下表。 i 0 1 2 3 4 xi yi yi 1.00 1.25 1.50 1.75 2.00 5.10 5.79 6.53 7.45 8.46 1.629 1.756 1.876 2.008 2.135 i 0 1 2 3 4 xi yi 19 25 31 38 44 19.0 32.3 49.0 73.3 97.8 知 识 结 构 图 三 函数 逼近 理论 预备知识 范数（定义、常用范数） 内积（定义、柯西 -施瓦茨不等 式、内积诱导范数） 正交多项式（性质、正交化方法、常用正 交多项式的定义和性质） 函数逼 近方法 最佳一致 逼近多项式 最佳平方 逼近 定义 存在唯一性定理 切比雪夫定理 最佳一次逼近多项式的确定 最小二乘 拟合 定义 法方程组和平方误差 基于正交基的最佳平方逼近 离散内积定义 法方程组及哈尔条件 基于正交基的最小二乘拟合 第四章第四章 数值积分和数值微分数值积分和数值微分 内容提要 4.1 数值积分概论 4.2 牛顿 -柯特斯公式 4.3 复化求积公式 4.4 龙贝格求积公式 4.5 高斯求积公式 4.6 数值微分 4.1 数 值积 分概 论 一、数 值 求 积 的基本思想 对 定 义 在区 间 a,b上的定 积 分 但实际使用这种积分方法时往往有困难，有时原函数不 能用初等函数表示，有时原函数又十分复杂，难于求出或计算； 另外如被积函数是由测量或数值计算给出的一张数据表示时， 上述方法也不能直接运用。因此有必要研究积分的数值计算 问题。 积分中值定理告诉我们： 平均高度 f() a b y x y=f(x) 0 a f(a+b)/2) b y x y=f(x) 0 a b y x y=f(x) 0 梯形公式 平均高度 中矩形公式 平均高度 更一般地，我们构造具有下列形式的求积公式 求积节点求积系数 这类数值积分方法通常称为机械求积，其特点是将积分 求值问题归结为函数值的计算，这就避开了牛顿 -莱布尼兹公 式需要寻求原函数的困难。 二、代数精度的概念 利用代数精度的概念构造求积公式 三、插值型的求积公式 4.2 牛顿 -柯特斯公式 一、牛顿 -柯特斯公式的导出 柯特斯系数 牛顿 -柯特斯公式的代数精度 4.3 复合求积公式 一、问题与基本思想 在使用牛顿 -柯特斯公式时将导致求积系数出现负数 (当 n8 时 ,牛顿 .柯特斯求积系数会出现负数 )，因而不可能通过提 高阶的方法来提高求积精度。为了提高精度通常采用将积 分区间划分成若干个小区间，在各小区间上采用低次的求 积公式 (梯形公式或辛普森公式 )，然后再利用积分的可加 性，把各区间上的积分加起来，便得到新的求积公式，这 就是复化求积公式的基本思想。本节只讨论复化的梯形公 式和复化的辛普森公式。 二、复合梯形公式 三、复合辛普森公式 xi 0 1/8 1/4 3/8 1/2 f (xi) 1 (极限 ) 0.9973978 0.9896158 0.9767267 0.9588510 xi 5/8 3/4 7/8 1 f (xi) 0.9361556 0.9088516 0.8414709 0.8414709 4.4 龙贝格求积公式 一、梯形 法 的递推化 (变步长求积法 ) 于是可以逐次对分形成一个序列 T1,T2,T4,T8, 此序列 收敛于积分真值 I。当 |T2n-Tn|1时时 ,aij=0,且满足如下的对角占优条件且满足如下的对角占优条件 : (1)|b1|c1|0,|bn|an|0 (2)|bi|ai|+|ci|, aici0, i=2,3, n-1. 5.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 （ 1）按行严格对角占优 （ 2）按行弱对角占优 上式至少有一个不等号严格成立。 定理 6-8(对角占优定理 )若矩阵 A按行 (或列 )严格对角占优， 或按行 (或列 )弱对角占优且不可约；则矩阵 A非奇异。 定理 6-9 若矩阵 A按行 (或列 )严格对角占优 ,或按行 (或列 )弱 对角占优不可约；则 Jacobi迭代、 Gauss-Seidel迭代都收敛 。 定理 6-12 对于线性方程组 Ax=b，若 (1) A为对称正定矩阵， (2)0 2，则解 Ax=b的 SOR迭代收敛。 定理 6-13 对于线性代数方程组 Ax=b， 若 A按行 (或列 )严格 对角占优，或按行 (或列 )弱对角占优不可约；则当 0 1时， SOR迭代收敛。 知 识 结 构 图 六 迭代 法 解 方 程 组 迭代法基本概念 高斯 -赛德 尔迭代法 迭代格式 收敛条件（充要条件、充分条件四个） SQR迭代法 迭代法收敛速度 雅可比迭代法 迭代格式 收敛条件（充要条件、充分条件四个） 迭代格式 收敛条件（充要条件、必要条件 、 充分条件五个） 第七章解非线性方程求根第七章解非线性方程求根 内容提要 7.1 方程求根与二分法 7.2 迭代法及其收敛性 7.3 牛顿法 7.4 弦截法 7.1 方程求根与二分法 一、引言 非线性方程的分类 由此可知方程的有根区间为 1,2 3,4 5,6 求根问题的三个方面：存在性，分布，精确化。 x 0 1 2 3 4 5 6 f(x)的符号 + + + 二、二分法 0 x y X* x0a b y=f(x) a1 b1 k ak bk xk f(xk)符号 0 1 2 3 4 5 6 1.0 1.25 1.3125 1.3203 1.5 1.375 1.3438 1.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 + + + 二分法的优点是算法简单，且总是收敛的，缺点是收 敛太慢 ,故一般不单独将其用于求根，只用其为根求 得一个较好的近似值 。 7.2 迭代法 一、不动点迭代与不动点迭代法 上述迭代法是一种逐次逼近法，其基本思想是将隐式方 程归结为一组显示的计算公式，就是说，迭代过程实质上是 一个逐步显示的过程。 k xk k xk k xk 0 1 2 1.5 1.35721 1.33086 3 4 5 1.32588 1.32494 1.32476 6 7 8 1.32473 1.32472 1.32472 继续迭代下去已经没有必要，因为结果显然会越来越大， 不可能趋于某个极限。这种不收敛的迭代过程称作是发散的。 一个发散的迭代过程，纵使进行了千百次迭代，其结果也毫 无价值。因此，迭代格式形式不同，有的收敛，有的发散，只 有收敛的迭代过程才有意义，为此要研究不动点的存在性及迭 代法的收敛性。 二、不动点的存在性与迭代法的收敛性 k xk k xk 1 2 3 1.484248034 1.472705730 1.468817314 4 5 6 1.467047973 1.466243010 1.465876820 k xk k xk 1 2 3 0.1 0.089482908 0.090639135 4 5 6 0.090512616 0.090526468 0.090524951 三、局部收敛性与收敛阶 k xk 迭代法 (1) 迭代法 (2) 迭代法 (3) 迭代法 (4) 0 1 2 3 x0 x1 x2 x3 2 3 9 87 2 1.5 2 1.5 2 1.75 1.73475 1.732631 2 1.75 1.732143 1.732051 k xk | xk- xk-1| 0 1 2 3 1.5 1.481248 1.482671 1.482563 0.018752 0.001423 0.000108 7.3 牛顿法 一、牛顿法及其收敛性 k xk k xk 0 1 0.5 0.57102 2 3 0.56716 0.56714 二、牛顿法应用举例 k xk 0 1 2 3 4 10 10.750000 10.723837 10.723805 10.723805 三、简化牛顿法与牛顿下山法 k xk xk xk f(xk) 0 1 2 3 4 1.5 1.34783 1.32520 1.32472 0.6 17.9 发散 0.6 -1.384 1.140625 -0.656643 1.36181 0.1866 1.32628 0.00667 1.32472 0.0000086 四、重根情形 k xk (1) (2) (3) 0 1 2 3 x0 x1 x2 x3 1.5 1.458333333 1.436607143 1.425497619 1.5 1.416666667 1.414215686 1.414213562 1.5 1.411764706 1.414211438 1.414213562 7.4 弦截法 k xk k xk 0 1 2 0.5 0.6 0.565 32 3 4 0.567 09 0.567 14 知 识 结 构 图 七 方程 近 似 求 根 基本概念（单根、重根、有根区间、不动点、收敛阶） 求根方法 二分法及其收敛性 不动点迭代法及其收敛性定理 （不动点迭代法的加速技巧） 牛顿迭代法及其收敛性 插值型迭代法（多点迭代） 弦截法抛物线法 第八章第八章 矩阵特征值问题计算矩阵特征值问题计算 内容提要 8.1 引言 8.2 幂法及反幂法 8.1 引言 物理、力学和工程技术中很多问题在数学上都归结 为求矩阵的特征值问题。例如，振动问题 (大型桥梁或 建筑物的振动、机械的振动、电磁震荡等 )，物理学中 的某些临界值的确定。它们都归结为下述数学问题。 8.2 幂法及反幂法 一、幂法 幂法是一种求实矩阵 A的按模最大的特征值 1及其对应的特征 向量 x1的方法。特别适合于大型稀疏矩阵。 k Uk(规范化向量 ) Max(vk) 0 1 5 10 20 (1 1 1) T (0.9091 0.8182 1) T (0.7651 0.6674 1) T (0.7494 0.6508 1) T (0.7482 0.6497 1) T 2.750 000 0 2.558 791 8 2.538 002 9 2.536 532 3 于是主特征值为： 2.536 532 3； 对应特征向量为： (0.748221 0.649661167 1) T 二、 加速方法 k Uk(规范化向量 ) Max(vk) 0 5 6 7 8 9 10 (1 1 1) (0.7516 0.6522 1) (0.7491 0.6511 1) (0.7488 0.6501 1) (0.7484 0.6499 1) (0.7483 0.6497 1) (0.7482 0.6497 1) 1.7914011 1.7888443 1.7873300 1.7869152 1.7866587 1.7865914 三、反幂 法 反幂法可求非奇异实矩阵的按模最小特征值及特征向量。 也可用来计算对应于一个给定近似特征值的特征向量。 加速后的反幂法计算公式： k UkT(规范化向量 ) p+1/Max(vk) 0 1 2 3 4 5 (1 1 1) (1 -0.271604938 -0.197530864) (1 -0.23453776 -0.171305338) (1 -0.235114344 -0.171625203) (1 -0.23510535 -0.171621118) (1 -0.235105489 -0.171621172) -13.40740741 -13.21752930 -13.22021864 -13.22017941 -13.22017998 k UkT(规范化向量 ) p+1/Max(vk) 0 1 2 3 4 5 6 7 (1 1 1 ) (1 0.498855835 0.114416475) (1 0.534907597 0.276180698) (1 0.518105446 0.233487833) (1 0.524707939 0.244518023) (1 0.522250689 0.241557235) (1 0.52312807 0.242370209) (1 0.522821544 0.242140245) 6.61784897 7.345995896 7.269698727 7.293933905 7.286058616 7.288626351 7.287783336 知 识 结 构 图 八 矩 阵 特 征 值 与 特 征 向 量 的 计 算 重要概念（特征值，特征向量，正交相似变换， 反射变换，平面旋转变换， QR分解） 迭代法 幂法（原理、计算公式、加速技巧）反幂法（原理、计算方法、加速技巧） 雅可比方法（原理、方法、收敛性） 变换法 QR方法 基本 QR方法 原点平移 QR方法 双步原点平移 QR方法 第九章第九章 常微分方程初值问题常微分方程初值问题 的数值解法的数值解法内容提要 9.1 引言 9.2 简单的数值方法与基本概念 9.3