《2016-数值分析课件.ppt》由会员分享，可在线阅读，更多相关《2016-数值分析课件.ppt（282页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数值分析电子课件工科研究生公共课程数学系列辽宁科技大学辽宁科技大学 理学院理学院20162016年年9 9月月机动上页下页首页结束工科研究生公共课程数学系列 第1章 数值分析与科学计算引论内容提要：1.1 数值分析研究对象与特点1.2 数值计算的误差1.3 误差定性分析与避免误差危害机动上页下页首页结束工科研究生公共课程数学系列 1.1 数值分析研究对象与特点数值分析研究对象与特点一、数值分析研究对象一、数值分析研究对象计算机解决科学计算问题时经历的过程计算机解决科学计算问题时经历的过程实际问题实际问题模型设计模型设计算法设计算法设计问题的解问题的解上机计算上机计算程序设计程序设计求求 方程求
2、根方程求根 牛顿法牛顿法 程序设计程序设计 解解上机计算上机计算 实例实例机动上页下页首页结束工科研究生公共课程数学系列 数数值分析的内容分析的内容包括函数的数包括函数的数值逼近、数逼近、数值微分与数微分与数值积分、非分、非线性方程数性方程数值解、数解、数值线性代数、常微和偏微数性代数、常微和偏微数值解等。解等。数数值分析研究分析研究对象以及解决象以及解决问题方法的广泛适用性，著名流行方法的广泛适用性，著名流行软件如件如MapleMaple、MatlabMatlab、MathematicaMathematica等已将其等已将其绝大多数内容大多数内容设计成函数，成函数，简单调用之后便可以得到运行
3、用之后便可以得到运行结果。果。但由于但由于实际问题的具体特征、复的具体特征、复杂性性,以及算法自身的适以及算法自身的适用范用范围决定了决定了应用中必用中必须选择、设计适合于自己特定适合于自己特定问题的算的算法，因而掌握数法，因而掌握数值方法的思想和内容是至关重要的。方法的思想和内容是至关重要的。本本课程内容包括了微程内容包括了微积分、代数、常微分方程的数分、代数、常微分方程的数值方法，方法，必必须掌握掌握这几几门课程的基程的基础内容才能学好本内容才能学好本门课程。程。机动上页下页首页结束工科研究生公共课程数学系列 二、数二、数值分析的特点分析的特点面向面向计算机算机，要根据，要根据计算机的特点
4、提供切算机的特点提供切实可行的有效算可行的有效算法。法。有可靠的有可靠的理理论分析分析，能任意逼近并达到精度要求，能任意逼近并达到精度要求，对近似近似算法要保算法要保证收收敛性和数性和数值稳定性，定性，还要要对误差差进行分析。行分析。这些都是建立在数学理些都是建立在数学理论的基的基础上，因此不上，因此不应片面的将数片面的将数值分析理解分析理解为各种数各种数值方法的方法的简单罗列和堆列和堆积。要有好的要有好的计算复算复杂性性，时间复复杂性好是指性好是指节省省时间，空，空间复复杂性好是指性好是指节省存省存储量，量，这也是建立算法要研究的也是建立算法要研究的问题，它关系到算法能否在它关系到算法能否在
5、计算机上算机上实现。要有要有数数值实验，即任何一个算法除了从理，即任何一个算法除了从理论上要上要满足上述足上述三点外，三点外，还要通要通过数数值实验证明是行之有效的。明是行之有效的。机动上页下页首页结束工科研究生公共课程数学系列 三、数三、数值分析的学分析的学习方法方法 初学可能会初学可能会觉得公式多，理得公式多，理论分析复分析复杂。给出如下的几点出如下的几点学学习方法。方法。认识建立算法和建立算法和对每个算法每个算法进行理行理论分析是分析是基本任基本任务，主，主动适适应公式多和公式多和讲究理究理论分析的特点。分析的特点。注重各章注重各章节所研究算法的提出，掌握方法的所研究算法的提出，掌握方法
6、的基本原理和基基本原理和基本思想本思想，要注意方法，要注意方法处理的技巧及其与理的技巧及其与计算机的算机的结合。合。理解每个算法建立的理解每个算法建立的数学背景、数学原理和基本数学背景、数学原理和基本线索索，而，而且且对一些最基本的算法要非常熟悉。一些最基本的算法要非常熟悉。要通要通过算例算例学学习使用各种数使用各种数值方法解决方法解决实际计算算问题。为掌握本掌握本课的内容，的内容，还应做一些做一些理理论分析和分析和计算算练习。机动上页下页首页结束工科研究生公共课程数学系列 1.2 数数值计算的算的误差差一、误差的来源与分类一、误差的来源与分类 在运用数学方法解决实际问题的过程中，每一步都可能
7、带在运用数学方法解决实际问题的过程中，每一步都可能带来误差。来误差。1、模型误差模型误差 在建立数学模型时，往往要忽视很多次要因素，在建立数学模型时，往往要忽视很多次要因素，把模型把模型“简单化简单化”，“理想化理想化”，这时模型就与真实背景有了，这时模型就与真实背景有了差距，即带入了误差。数学模型与实际问题之间出现的误差称差距，即带入了误差。数学模型与实际问题之间出现的误差称为为模型误差模型误差。2、观测误差（测量误差）观测误差（测量误差）数学模型中的已知参数，多数是通数学模型中的已知参数，多数是通过测量得到。而测量过程受工具、方法、观察者的主观因素、过测量得到。而测量过程受工具、方法、观察
8、者的主观因素、不可预料的随机干扰等影响必然带入误差。不可预料的随机干扰等影响必然带入误差。机动上页下页首页结束工科研究生公共课程数学系列 3、截断误差（方法误差）截断误差（方法误差）数学模型常难于直接求解，往往要数学模型常难于直接求解，往往要用数值方法求近似解替代，这种简化带入误差称为方法误差或用数值方法求近似解替代，这种简化带入误差称为方法误差或截断误差。截断误差。4、舍入误差舍入误差 计算机只能处理有限数位的小数运算，初始参计算机只能处理有限数位的小数运算，初始参数或中间结果都必须进行四舍五入运算，这必然产生舍入误数或中间结果都必须进行四舍五入运算，这必然产生舍入误差。差。机动上页下页首页
9、结束工科研究生公共课程数学系列 误差分析是一门比较艰深的专门学科。在数值分析中主要误差分析是一门比较艰深的专门学科。在数值分析中主要讨论截断误差及舍入误差。但一个训练有素的计算工作者，当讨论截断误差及舍入误差。但一个训练有素的计算工作者，当发现计算结果与实际不符时，应当能诊断出误差的来源，并采发现计算结果与实际不符时，应当能诊断出误差的来源，并采取相应的措施加以改进，直至建议对模型进行修改。取相应的措施加以改进，直至建议对模型进行修改。二、绝对误差、相对误差与有效数字二、绝对误差、相对误差与有效数字1 1、绝对误差与绝对误差限、绝对误差与绝对误差限误差是有量纲的量，量纲同误差是有量纲的量，量纲
10、同 x，它可正可负。，它可正可负。误差一般无无法误差一般无无法准确计算，只能根据测量或计算情况估计出它的误差绝对值的准确计算，只能根据测量或计算情况估计出它的误差绝对值的一个上界，这个上界称为近似值一个上界，这个上界称为近似值 x*的的误差限误差限，记为，记为*。它是。它是正数，有量纲的。如用毫米刻度尺测量长度。误差限是正数，有量纲的。如用毫米刻度尺测量长度。误差限是0.5mm。机动上页下页首页结束工科研究生公共课程数学系列 2 2、相对误差与相对误差限、相对误差与相对误差限 机动上页下页首页结束工科研究生公共课程数学系列 3、有效数字、有效数字 定义定义1-3 如果近似值如果近似值x*的误差
11、限是某一位的半个单位，该的误差限是某一位的半个单位，该位到位到 x*的第一位非零数字共有的第一位非零数字共有n位，就说位，就说x*有有n位位有效数有效数字字.机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 4、绝对误差，相对误差与有效数字的关系、绝对误差，相对误差与有效数字的关系 绝对误差与相对误差绝对误差与相对误差：由两者定义可知。：由两者定义可知。绝对误差与有效数字绝对误差与有效数字：绝对误差不超过末位有效数字的半个单位。绝对误差不超过末位有效数字的半个单位。机动上页下页首页结束工科研究生公共课程数学系列 有效数字与相对误差限有效数字与相对误
12、差限 定理说明有效数位越多，相对误差限越小。定理也给出了定理说明有效数位越多，相对误差限越小。定理也给出了相对误差限的求法。相对误差限的求法。机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 三、数值运算的误差估计三、数值运算的误差估计1、四则运算机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 2、函数误差、函数误差 当自变量有误差时计算函数值也产生误差，可以利用函数的泰勒展开式估计其误差界。机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首
13、页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 1.3 误差定性分析与避免误差危害误差定性分析与避免误差危害一、算法的稳定性一、算法的稳定性 用一个算法进行计算，由于初始数据误差在计算中传播 使计算结果误差增长很快，就是数值不稳定的，先看下例。机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 计算结果n法一(A)法二(B)01234567890.63210.36790.26420.20740.17040.14800.11200.2160-0.72807.5520.63210.36790.26430.20730.17
14、080.14550.12680.11210.10350.0684机动上页下页首页结束工科研究生公共课程数学系列 二、病态问题与条件数二、病态问题与条件数1、病态问题：对一个数值问题本身如果输入数据有微小扰动（即误差），引起输出数据（即问题解）相对误差很大，这就是病态问题。机动上页下页首页结束工科研究生公共课程数学系列 注意注意病态问题不是计算方法引起的，是数值问题自身固有的，因此，对数值问题首先要分清问题是否病态，对病态问题就必须采取相应的特殊方法以减少误差危害。机动上页下页首页结束工科研究生公共课程数学系列 三、避免误差危害的若干原则三、避免误差危害的若干原则1、要避免除数绝对值远远小于被除
15、数绝对值的除法。用绝对值小的数作除数舍入误差会增大，如计算 x/y，若0|y|时，Ln(x)不一定收敛于f(x)。20世纪初龙格（Runge）就给了一个等距节点插值多项式Ln(x)不一定收敛于f(x)的例子。y=L10(x)机动上页下页首页结束工科研究生公共课程数学系列 x1y=L10(x)o-10.5y1.51龙格现象龙格现象机动上页下页首页结束工科研究生公共课程数学系列 二、分段线性插值分段线性插值就是通过插值点用折线段连接起来逼近f(x).机动上页下页首页结束工科研究生公共课程数学系列 分段线性插值分段线性插值三、分段抛物插值三、分段抛物插值三、分段抛物插值三、分段抛物插值机动上页下页首
16、页结束工科研究生公共课程数学系列 2.6 三次样条插值三次样条插值 样条曲线实际上是由分段三次曲线并接而成，在连接点即样点上要求二阶导数连续，从数学上加以概括就得到数学样条这一概念。下面我们讨论最常用的三次样条函数。一、三次样条函数 y=L10(x)每个小区间上要确定4个待定系数，共有n个小区间，故应确定4n个参数。机动上页下页首页结束工科研究生公共课程数学系列 y=L10(x)机动上页下页首页结束工科研究生公共课程数学系列 二、三次样条插值函数的建立 y=L10(x)机动上页下页首页结束工科研究生公共课程数学系列 y=L10(x)机动上页下页首页结束工科研究生公共课程数学系列 y=L10(x
17、)机动上页下页首页结束工科研究生公共课程数学系列 y=L10(x)系数矩阵为严格对角占优阵，方程组有为一解。求法见5.3节追赶法。机动上页下页首页结束工科研究生公共课程数学系列 y=L10(x)机动上页下页首页结束工科研究生公共课程数学系列 y=L10(x)机动上页下页首页结束工科研究生公共课程数学系列 知识结构图二插值法工具分段多项式插值存在唯一性多项式插值Hermite插值插值公式误差估计差商、差分Lagrange插值基及函数定义性质定义性质导数型差商型Lagrange插值多项式Newton插值多项式 等距节点插值公式 存在唯一性误差估计 插值公式 分段线性插值（公式、误差估计、收敛性）分
18、段三次Hermite插值（公式、误差估 计、收敛性）三次样条插值（公式、存在唯一 性、误差估计、收敛性）机动上页下页首页结束工科研究生公共课程数学系列 第三章函数逼近内容提要3.1 基本概念3.2 最佳平方逼近3.3 曲线拟合的最小二乘法机动上页下页首页结束工科研究生公共课程数学系列 3.1基本概念 x0 x3x5x7x1x4x6x2f(x)p(x)机动上页下页首页结束工科研究生公共课程数学系列 2、范数与赋范线性空间、范数与赋范线性空间机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 3、内积与内积
19、空间、内积与内积空间机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 1、最佳平方逼近、最佳平方逼近3.2 最佳平方逼近最佳平方逼近机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 最小二乘法及其计算最小二乘法及其计算3.3 曲线拟合的最小二乘法曲线拟合的最小二乘法 机动上页下页首页结束工科研究生公共课程数学系列
20、机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 例3-3 已知实测数据表如下,求它的拟合曲线 xi1 2 3 4 5 yii4 4.5 6 8 8.5 2 1 3 1 10 xy 2 4 68642机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 例3-4 已知已知实测实测数据表如下数据表如下,确定数学模型确定数学模型 y=aebx,用最小二乘法确定用最小二乘法确定a，b。i0 1 2 3 4 xi yi1
21、.00 1.25 1.50 1.75 2.005.10 5.79 6.53 7.45 8.46分析：根据给定数据描图也可确定拟合曲线方程，但它不是线性形式。因此首先要将经验曲线线性化。本题可以采取等式两边取对数的形式线性化。数据表中的数值也相应的转化为取对数之后的数值，见下表。机动上页下页首页结束工科研究生公共课程数学系列 i0 1 2 3 4 xi yi yi1.00 1.25 1.50 1.75 2.005.10 5.79 6.53 7.45 8.461.629 1.756 1.876 2.008 2.135机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共
22、课程数学系列 i 0 1 2 3 4 xi yi19 25 31 38 4419.0 32.3 49.0 73.3 97.8机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 知识结构图三函数逼近理论预备知识范数（定义、常用范数）内积（定义、柯西-施瓦茨不等 式、内积诱导范数）正交多项式（性质、正交化方法、常用正 交多项式的定义和性质）函数逼近方法最佳一致逼近多项式最佳平方逼近定义存在唯一性定理切比雪夫定理最佳一次逼近多项式的确定最小二乘拟合定义法方程组和平方误差基于正交基的最佳平方逼近离散内积定义法方程组及哈尔条件基于正交基的最小二乘拟合机动上页下
23、页首页结束工科研究生公共课程数学系列 第四章 数值积分和数值微分内容提要4.1 数值积分概论4.2 牛顿-柯特斯公式4.3 复化求积公式4.4 龙贝格求积公式4.5 高斯求积公式4.6 数值微分机动上页下页首页结束工科研究生公共课程数学系列 4.1 数数值积值积分概分概论论4.1.1 数数值值求求积积的基本思想的基本思想 对对定定义义在区在区间间a,b上的定上的定积积分分 但实际使用这种积分方法时往往有困难，有时原函数不但实际使用这种积分方法时往往有困难，有时原函数不能用初等函数表示，有时原函数又十分复杂，难于求出或计算；能用初等函数表示，有时原函数又十分复杂，难于求出或计算；另外如被积函数是
24、由测量或数值计算给出的一张数据表示时，另外如被积函数是由测量或数值计算给出的一张数据表示时，上述方法也不能直接运用。因此有必要研究积分的数值计算上述方法也不能直接运用。因此有必要研究积分的数值计算问题。问题。机动上页下页首页结束工科研究生公共课程数学系列 积分中值定理告诉我们：积分中值定理告诉我们：平均高度平均高度f()a b yxy=f(x)0机动上页下页首页结束工科研究生公共课程数学系列 a f(a+b)/2)b yxy=f(x)0 a b yxy=f(x)0梯形公式梯形公式平均高度平均高度中矩形公式中矩形公式平均高度平均高度机动上页下页首页结束工科研究生公共课程数学系列 更一般地，我们构
25、造具有下列形式的求积公式更一般地，我们构造具有下列形式的求积公式求积节点求积节点求积系数求积系数 这类数值积分方法通常称为机械求积，其特点是将积分这类数值积分方法通常称为机械求积，其特点是将积分求值问题归结为函数值的计算，这就避开了牛顿求值问题归结为函数值的计算，这就避开了牛顿-莱布尼兹公莱布尼兹公式需要寻求原函数的困难。式需要寻求原函数的困难。4.1.2 代数精度的概念代数精度的概念机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 利用代数精度的概念构造求积公式利用代数精度的概念构造求积公式机动上页下页首页结束工科研究生公共课程数学系列 机动上页
26、下页首页结束工科研究生公共课程数学系列 4.1.3 插值型的求积公式插值型的求积公式机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 4.2 牛顿牛顿-柯特斯公式柯特斯公式一、柯特斯系数一、柯特斯系数机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 牛顿牛顿-柯特斯公式的代数精度柯特斯公式的代数精度机动上页下页首页结束工科研究生公共课程数学系列 4.3 复合求积公式复合求积公式 一、问题与基本思想 在使用牛顿-柯特斯公式时将导致求积系数出现负数(当n8时,牛顿.柯特斯求积系数会出现负数)，因而不可能通过
27、提高阶的方法来提高求积精度。为了提高精度通常采用将积分区间划分成若干个小区间，在各小区间上采用低次的求积公式(梯形公式或辛普森公式)，然后再利用积分的可加性，把各区间上的积分加起来，便得到新的求积公式，这就是复化求积公式的基本思想。本节只讨论复化的梯形公式和复化的辛普森公式。机动上页下页首页结束工科研究生公共课程数学系列 二、复合梯形公式二、复合梯形公式机动上页下页首页结束工科研究生公共课程数学系列 三、复合辛普森公式三、复合辛普森公式机动上页下页首页结束工科研究生公共课程数学系列 xi0 1/8 1/4 3/8 1/2 f(xi)1(极限)0.9973978 0.9896158 0.9767
28、267 0.9588510 xi5/8 3/4 7/8 1 f(xi)0.9361556 0.9088516 0.8414709 0.8414709 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 4.4 龙贝格求积公式龙贝格求积公式 一、梯形法的递推化一、梯形法的递推化(变步长求积法变步长求积法)机动上页下页首页结束工科研究生公共课程数学系列 于是可以逐次对分形成一个序列于是可以逐次对分形成一个序列T1,T2,T4,T8,此序列此序列收敛于积分真值收
29、敛于积分真值 I。当。当|T2n-Tn|1|1时时时时,a aij ij=0,=0,且满足如下的对角占优条件且满足如下的对角占优条件且满足如下的对角占优条件且满足如下的对角占优条件:(1)|(1)|b b1 1|c c1 1|0,|0,|b bn n|a an n|0|0(2)|(2)|b bi i|a ai i|+|+|c ci i|,|,a ai ic ci i0,0,i i=2,3,=2,3,n n-1.-1.机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课
30、程数学系列 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 机动上页下页首页结束工科研究生公共课程数学
31、系列 机动上页下页首页结束工科研究生公共课程数学系列 5.6 误差分析误差分析机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 知识结构图五直接法解方程组高斯消去法矩阵的正交三角化及应用定义常用范数范数的性质初等反射阵平面旋转变换矩阵矩阵的QR分解应用：求解超定方程组高斯消去法高斯若当消去法列主元消去法矩阵三角分
32、解法LU分解平方根分解LDLT分解追赶法解三对角方程组向量和矩阵的范数矩阵条件数及迭代改善法机动上页下页首页结束工科研究生公共课程数学系列 第六章解线性代数方程组的迭代法内容提要6.1 引言引言6.2 基本迭代法6.3 迭代法的收敛性机动上页下页首页结束工科研究生公共课程数学系列 即AX=b 其中A为非奇异矩阵，当A为低阶稠密矩阵时，线性方程组用直接法(如高斯消去法和三角分解法)是有效的，但对于由工程技术中产生的大型稀疏矩阵方程组（A的阶数n很大，但零元素较多），利用迭代法求解是适合的。在计算机内存和运算两方面，迭代通常都可利用A中有大量零元素的特点。考虑线性方程组6.1 引言引言机动上页下页
33、首页结束工科研究生公共课程数学系列 本章将介绍迭代法的一般理论及雅可比迭代法、高斯塞德尔迭代法、超松弛迭代法，研究它们的收敛性。机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 6.2 基本迭代基本迭代机动上页下页首页结束工科研究生公共课程数学系列 一、雅可比迭代法一、雅可比迭代法机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 二、高斯二、高斯塞德尔迭代法塞德
34、尔迭代法机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 SOR迭代法的计算公式:对k=0,1,三、逐次超松驰三、逐次超松驰(SOR)(SOR)迭代法迭代法机动上页下页首页结束工科研究生公共课程数学系列 说明说明:1)=1,即为GS（高斯-赛德尔迭代法）;2)1，称为超松驰法；1，称为低松驰法；3)SOR方法每迭代一次主要运算量是计算一次矩阵 与向量的乘法。例6-3 用SOR迭代法解线性代数方程组机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 6.3 迭代法的收敛性迭代法的收敛性一、一阶定常迭代法的基
35、本定理一、一阶定常迭代法的基本定理机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 注：定理6-4中的矩阵是迭代矩阵，常用格式的迭代矩阵如下 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。机动上页下页首页结束工科研究生公共课程数学系列 例如 考察用雅可比迭代法求解线性方程组机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首
36、页结束工科研究生公共课程数学系列 二、某些特殊方程组的迭代收敛性二、某些特殊方程组的迭代收敛性定义定义6-4 （1）按行严格对角占优）按行严格对角占优机动上页下页首页结束工科研究生公共课程数学系列 （2 2）按行弱对角占优）按行弱对角占优 上式至少有一个不等号严格成立。上式至少有一个不等号严格成立。定理定理6-66-6(对角占优定理对角占优定理)若矩阵若矩阵A A按行按行(或列或列)严格对角占优，或按行严格对角占优，或按行(或列或列)弱对角占优且不可约；则矩阵弱对角占优且不可约；则矩阵A A非奇异。非奇异。定理定理6-7 若矩若矩阵阵A按行按行(或列或列)严严格格对对角占角占优优,或按行或按行
37、(或列或列)弱弱对对角占角占优优不不可可约约；则则Jacobi迭代、迭代、Gauss-Seidel迭代都收迭代都收敛敛。机动上页下页首页结束工科研究生公共课程数学系列 定理定理6-9 对于线性方程组对于线性方程组Ax=b，若，若(1)A为对称正定矩阵，为对称正定矩阵，(2)(2)02，则解，则解Ax=b的的SOR迭代收敛。迭代收敛。定理定理6-10 对于线性代数方程组对于线性代数方程组Ax=b，若若A按行按行(或列或列)严格对角占优，严格对角占优，或按行或按行(或列或列)弱对角占优不可约；则当弱对角占优不可约；则当01时，时，SOR迭代收敛。迭代收敛。机动上页下页首页结束工科研究生公共课程数学
38、系列 知识结构图六迭代法解方程组迭代法基本概念高斯-赛德尔迭代法迭代格式收敛条件（充要条件、充分条件四个）SQR迭代法迭代法收敛速度雅可比迭代法迭代格式收敛条件（充要条件、充分条件四个）迭代格式收敛条件（充要条件、必要条件、充分条件五个）机动上页下页首页结束工科研究生公共课程数学系列 第七章解非线性方程求根内容提要内容提要7.1 方程求根与二分法方程求根与二分法7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性7.3 牛顿法牛顿法7.4 弦截法弦截法机动上页下页首页结束工科研究生公共课程数学系列 7.1 方程求根与二分法方程求根与二分法7.1.1 7.1.1 引言引言非线性方程的分类非线性方
39、程的分类机动上页下页首页结束工科研究生公共课程数学系列 由此可知方程的有根区间为由此可知方程的有根区间为1,2 3,4 5,61,2 3,4 5,6。x 0 1 2 3 4 5 6f(x)的符号 +、二分法、二分法0 xyX*x0aby=f(x)a1b1机动上页下页首页结束工科研究生公共课程数学系列 k ak bk xkf(xk)符号0123456 1.0 1.25 1.31251.3203 1.5 1.3751.34381.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 +机动上页下页首页结束工科研究生公共课程数学系列 二分法的优点是算法
40、简单，且总是收敛的，缺点是收敛太慢二分法的优点是算法简单，且总是收敛的，缺点是收敛太慢,故一般故一般不单独将其用于求根，只用其为根求得一个较好的近似值。不单独将其用于求根，只用其为根求得一个较好的近似值。7.2 迭代法迭代法7.2.1 不不动动点迭代与不点迭代与不动动点迭代法点迭代法机动上页下页首页结束工科研究生公共课程数学系列 kxkkxkkxk0121.51.357211.3308634 51.325881.32494 1.324766781.324731.324721.32472 上述迭代法是一种逐次逼近法，其基本思想是将隐式方程归结为一组上述迭代法是一种逐次逼近法，其基本思想是将隐式方
41、程归结为一组显示的计算公式，就是说，迭代过程实质上是一个逐步显示的过程。显示的计算公式，就是说，迭代过程实质上是一个逐步显示的过程。机动上页下页首页结束工科研究生公共课程数学系列 继续迭代下去已经没有必要，因为结果显然会越来越大，继续迭代下去已经没有必要，因为结果显然会越来越大，不可能趋于某个极限。这种不收敛的迭代过程称作是发散的。不可能趋于某个极限。这种不收敛的迭代过程称作是发散的。一个发散的迭代过程，纵使进行了千百次迭代，其结果也毫一个发散的迭代过程，纵使进行了千百次迭代，其结果也毫无价值。因此，迭代格式形式不同，有的收敛，有的发散，只无价值。因此，迭代格式形式不同，有的收敛，有的发散，只
42、有收敛的迭代过程才有意义，为此要研究不动点的存在性及迭有收敛的迭代过程才有意义，为此要研究不动点的存在性及迭代法的收敛性。代法的收敛性。机动上页下页首页结束工科研究生公共课程数学系列 7.2.2 7.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 k xk k xk 1 2 31.4842480341.4727057301.468817314 4 5 6 1.4670479731.46
43、62430101.465876820机动上页下页首页结束工科研究生公共课程数学系列 k xk k xk 1 2 30.10.0894829080.090639135 4 5 6 0.090512616 0.090526468 0.090524951机动上页下页首页结束工科研究生公共课程数学系列 7.2.3 7.2.3 局部收敛性与收敛阶局部收敛性与收敛阶机动上页下页首页结束工科研究生公共课程数学系列 kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123 x0 x1 x2 x3 2398721.521.521.751.734751.73263121.751.7321431.732051
44、机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 k xk|xk-xk-1|0123 1.5 1.481248 1.482671 1.4825630.0187520.0014230.000108机动上页下页首页结束工科研究生公共课程数学系列 7.3 牛顿法牛顿法7.3.1 7.3.1 牛顿法及其收敛性牛顿法及其收敛性机动上页下页首页结束工科研究生公共课程数学系列 kxkkxk010.50.57102230.567160.56714机动上页下页首页结束工科研究生公共课程数学系列 7.3.2 牛顿法应用举
45、例牛顿法应用举例机动上页下页首页结束工科研究生公共课程数学系列 kxk012 341010.75000010.72383710.72380510.723805机动上页下页首页结束工科研究生公共课程数学系列 7.3.3 简化牛顿法与牛顿下山法简化牛顿法与牛顿下山法机动上页下页首页结束工科研究生公共课程数学系列 kxkxkxk f(xk)012341.51.347831.325201.324720.617.9发散0.6 -1.3841.140625 -0.6566431.36181 0.18661.32628 0.006671.32472 0.00000867.3.4 重根情形重根情形机动上页下页
46、首页结束工科研究生公共课程数学系列 kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562机动上页下页首页结束工科研究生公共课程数学系列 7.4 弦截法弦截法机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 kxkkxk0120.50.60.565 32340.567 090.567 14 机动上页下页首页结束工科研究生公共课程数学系列 知
47、识结构图七方程近似求根基本概念（单根、重根、有根区间、不动点、收敛阶）求根方法二分法及其收敛性不动点迭代法及其收敛性定理（不动点迭代法的加速技巧）牛顿迭代法及其收敛性插值型迭代法（多点迭代）弦截法抛物线法机动上页下页首页结束工科研究生公共课程数学系列 第八章 矩阵特征值计算内容提要8.1 引言8.2 幂法及反幂法机动上页下页首页结束工科研究生公共课程数学系列 8.1 特征值问题及其性质特征值问题及其性质 物理、力学和工程技术中很多问题在数学上都归结物理、力学和工程技术中很多问题在数学上都归结为求矩阵的特征值问题。例如，振动问题为求矩阵的特征值问题。例如，振动问题(大型桥梁或大型桥梁或建筑物的振
48、动、机械的振动、电磁震荡等建筑物的振动、机械的振动、电磁震荡等)，物理学中，物理学中的某些临界值的确定。它们都归结为下述数学问题。的某些临界值的确定。它们都归结为下述数学问题。机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 特征值估计与扰动特征值估计与扰动机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 8.2 幂法及反幂法幂法及反幂法8.2.1 幂法幂法幂法是一种计算实矩阵幂法是一种计算实矩阵A A的按模最大的特征值的按模最大的特征值1 1及其对应及其对应的特征向量的特征向量x x1 1的方法。特别
49、适合于大型稀疏矩阵。的方法。特别适合于大型稀疏矩阵。机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 kUk(规范化向量)Max(vk)0 1 51020(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
50、2.750 000 02.558 791 82.538 002 92.536 532 3于是主特征值为：2.536 532 3；对应特征向量为：(0.748221 0.649661167 1)T机动上页下页首页结束工科研究生公共课程数学系列 8.2.2 加速方法加速方法原点平移法原点平移法机动上页下页首页结束工科研究生公共课程数学系列 机动上页下页首页结束工科研究生公共课程数学系列 kUk(规范化向量)Max(vk)0 5 6 7 8 910(1 1 1)(0.7516 0.6522 1)(0.7491 0.6511 1)(0.7488 0.6501 1)(0.7484 0.6499 1)(0