高等教育数值分析教案1

《高等教育数值分析教案1》由会员分享，可在线阅读，更多相关《高等教育数值分析教案1（63页珍藏版）》请在装配图网上搜索。

1、高等教育数值分析教案Ch1、引 论1、数值分析及其特点1、数值分析及其主要内容数值分析也称计算方法，主要研究用计算机求解数学问题的数值方法及理论，内容主要包括：(1)数值逼近插值与拟合、多项式逼近、有理逼近等(Ch2Ch3)；(2)数值积分与微分(Ch4)；(3)数值代数求解方程(组)以及特征问题的数值方法(Ch6Ch9)；(4)常微分方程的数值解法(Ch5)。2、数值分析的特点(1)首先要有可靠的理论分析，以确保算法在理论上的收敛性和数值稳定性；(2)其次要对计算结果进行误差估计，以确定其是否满足精度；（见例3）(3)还要考虑算法的运行效率，即算法的计算量与存储量。例如Cooley和Tuke

2、y1965年提出FFT，N=32K，1000倍。例1、分析用Cramer法则解一个阶线性方程组的计算量。解：计算机的计算量主要取决于乘除法的次数。用Cramer法则解一个阶线性方程组需计算个阶行列式，而用定义计算阶行列式需次乘法，故总计共需。此外，还需次除法。当时，计算量约为次乘法。即使用每秒百亿次乘法的计算机，也需计算3000多年才能完成。可见，Cramer法则仅仅是理论上的，不是面向计算机的。2、数值分析中的误差1、误差的类型与来源(1)模型误差；(2)观测误差；(3)截断误差(方法误差) 模型的准确解与数值方法准确解之间的误差；(4)舍入误差实数形式的原始数据与有限字长的计算机数据之间的

3、误差。数值分析主要研究截断误差与舍入误差。例2、根据Taylor展式计算(误差小于0.01)。解： (截断误差) (舍入误差)。2、误差的基本概念(1)误差与误差限设为某量的精确值，为的一个近似值，则称为的（绝对）误差，为的相对误差。用某种方法确定的误差的某个上界称为的误差限，显然，即，称为的相对误差限。误差限取决于测量工具和计算方法。(2)函数值的计算误差设，为的近似值，则(多元函数一阶Taylor展式)，。3、算法的数值稳定性与病态问题1、算法的数值稳定性例3、计算，并做误差分析。解：。算法1：，结果见下表。又, 。算法2：，结果见下表。 n算法1算法2准确值01234560.18230.

4、08850.05750.04580.02080.0958-0.31250.18230.08840.05800.04310.03440.02810.02620.18230.08840.05800.04310.03430.02850.0243误差分析:算法1：，即在计算过程中误差放大了倍。算法2：，即误差缩小了倍。定义1：若某算法受初始误差或计算过程中产生的舍入误差的影响较小，则称之是数值稳定的，反之称为不稳定算法。2、病态问题例4、将方程，即改为摄动方程，即，其中。Wilkinson用精密方法计算出其根为：。令，其根为，则当时，。显然反映了初始数据的微小摄动对的影响程度即问题的条件数。因，故 1

5、 4 6 8 1019 20 （坏条件问题）定义2：若初始数据的微小误差都会对最终的计算结果产生极大的影响，则称这种问题为病态问题（坏条件问题），反之称其为良态问题。例5、分别将线性方程组的右端向量和系数矩阵中数据做一个微小变化，具体数据如下：然后用精确方法求解，发现其解与原方程解相比发生了很大的变化。 这表明此方程组为病态方程组。4、算法的实现与常用的数学软件用计算机实现数值分析中的算法通常有两种途径：(1)用Fortran、C、VB、VC等自编程序；(2)借助于现成的数学工具软件。目前常用的数学软件约30余个，可分为通用与专用两大类。专用系统主要是为解决数学中某个分支的特殊问题而设计的。1

6、、 SAS和SPSS（统计分析）；2、 Lindo、Lingo和CPLEX（运筹与优化计算）；3、 Cayley和GAP（群论研究）；4、 PARI（数论研究）；5、 Origin（科技绘图与数据分析）；6、 DELiA（微分方程分析）等。通用系统中又可分为数值计算型与解析计算型。数值计算型：Matlab、Xmath、Gauss、MLAB和Origin等。解析计算型：Maple、Mathematica、Macsyma、Axiom和Reduce等。其中Matlab、Mathematica、Maple与另一个面向大众的普及型数学软件Mathcad并称数学软件中的“四大天王”。Matlab意思为“矩

7、阵实验室”，是美国计算机科学家Cleve Moler在70年代末开发出的以矩阵数值计算为主的数学软件，如今已发展成为融科技计算、图形可视化与程序语言为一体的功能强大的通用数学软件。Matlab最突出的特点是其带有一系列的“工具包”，可广泛应用于自动控制、信号处理、数据分析、通讯系统和动态仿真等领域。高版本的Matlab也可进行符号计算，不过它的代数运算系统是从Maple移植过来的。Mathematica是美国物理学家Stephen Wolfram开发出的第一个将符号计算、数值计算和图形显示很好地结合在一起的数学软件，在国内较为流行，拥有广泛的用户。Mathcad是MathSoft公司在80年代

8、开发的一个交互式数学文字软件，与Matlab和Mathematica不同的是，该软件的市场定位是：向广大教师、学生、工程技术人员提供一个兼备文字、数学和图形处理能力的集成工作环境，而并不致力于复杂的数值计算与符号计算问题，具有面向大众普及的特点。不过，新版Mathcad的计算能力已远远超出了其早期的设计目标。Maple是加拿大Waterloo大学符号计算研究小组于80年代初开始研发，1985年才面世的计算机代数软件，起初并不为人们所注意，但Maple V release 2于1992年面世后，人们发现它是一个功能强大、界面友好的计算机代数系统。随着版本的不断更新，Maple已日益得到广泛的承认

9、和欢迎，用户越来越多，声誉越来越高，从1995年以后，Maple一直在IEEE的数学软件评比中居符号计算软件的第一名。目前，Maple的最高版本为Maple V release 11。第一章上机实验目的：1、 熟悉Maple中的定义函数、解方程、积分、循环语句和列表等命令；2、 通过具体问题的计算，加深对数值稳定性和病态问题的理解。实验内容：1、 设，由得算法一：；又，取，从而又得算法二：。分别用上述两种算法计算，根据计算结果判定其数值稳定性，并给予证明。2、将方程，即改为摄动方程，对不同的求解此方程，观察对解的影响程度，判定此方程是否为病态方程。15、已知三角形面积，其中为弧度，且测量的误差

10、分别为，证明面积的误差满足。证：根据零阶多元Taylor公式，令，则，因，从而，得，即。又，故，即。从而。Ch2、插值法1、插值问题引例：矿井中某处的瓦斯浓度与该处距地面的距离有关，现用仪器测得从地面到井下500米每隔50米的瓦斯浓度数据，根据这些数据完成下列工作：(1)寻找一个函数，要求从此函数中可近似求得从地面到井下500米之间任意一点处的瓦斯浓度；(2)估计井下600米处的瓦斯浓度。第一个问题可归结为“已知函数在处的值，求函数在区间内其它点处的值”，这种问题适宜用插值方法解决。但对第二个问题不宜用插值方法，因为600米已超出所给数据范围，用插值函数外推插值区间外的数据会产生较大的误差。解

11、决第二个问题的常用方法是，根据地面到井下500处的数据求出瓦斯浓度与地面到井下距离之间的函数关系，由求井下600米处的瓦斯浓度。定义：设在中个点处的值为已知，现根据上述数据构造一个简单函数，使，这种问题称为插值问题。,分别称为被插值函数、插值函数、插值节点和插值条件。若为多项式，则此问题称为多项式插值或代数插值。定理1：在插值节点处，取给定值，且次数不高于的插值多项式是存在且唯一的。证：令，则根据插值条件有下列等式 （关于的阶线性方程组），其系数行列式是范德蒙（Vandermonde）行列式。根据克莱姆法则，此方程组存在唯一解，即存在且唯一。2、Lagrange插值1、线性插值与抛物插值(1)

12、线性插值，其中称为线性插值的基函数。(2)抛物插值设，分别令，即得， 故，其中称为抛物插值的基函数。2、Lagrange插值多项式定义：对个插值节点，令，则显然。此时，满足 称之为Langrange插值多项式，称为Lagrange插值的基函数。编程时宜用。3、插值公式的余项定理2：设上连续，在内可导，则以插值多项式逼近的截断误差（即余项）。例1、已知函数的数据如下，分别用线性插值和二次插值求的近似值。 0.5 0.6 0.7 -0.693147 -0.510826 -0.356675解：，3、逐次线性插值法对插值节点及对应的函数值，用表示一个非负整数序列，将个节点所确定的不高于次的插值多项式记

13、为，则 ，即次插值多项式可以用两个次插值多项式通过线性插值获得逐次线性插值。Aitken算法：例2、根据下表近似计算在处的值。同理可得。类似可得。，故。4、均差与牛顿插值公式1、均差（差商）及其性质定义：称为关于的一阶均差； 称为关于的二阶均差；类似地可定义阶均差 。定理：，即阶均差可表示为的线性组合，从而阶均差与节点的排列次序无关。证：当时，右左不妨假设成立，则 。2、牛顿插值公式设插值节点上的插值多项式为。分别令，则有；从而，故 牛顿插值公式。例3、 P340.400.550.650.800.901.05K=00.410750.578150.696750.888111.026521.253

14、82K=11.116001.186001.275731.384101.51533K=20.280000.358930.433480.52493K=30.197330.213000.22863K=40.031340.03126K=5-0.00012，。5、差分与等距节点插值公式1、差分及其性质定义：对等距节点，记。向前差分：；向后差分：；中心差分：；二阶差分：；阶差分：。不变算子与移位算子，即。由，得。(1)差分类似于微分的性质 (2)函数值与差分可相互线性表示(3)差分与均差的关系。证：时，。假设时成立，则。2、等距节点插值公式令，则，。代入牛顿插值公式得 。6、Runge现象与高次插值的讨论

15、1、Runge现象例4、，节点，求插值多项式。解： 10次Langrange插值多项式结果如下：2、讨论(1)节点的增多固然能使插值函数在更多的地方与相等，但在两个节点之间不一定能很好地逼近，有时差异很大，所以在实际中，高次插值（7次以上）很少使用；(2)可将分成若干小区间，在小区间内用低次（二次，三次）插值，即分段低次插值，如样条函数插值。7、三次样条插值分段低次插值：(1)分段线性插值(连续)；(2)分段Hermite插值(导数连续)；(3)三次样条插值(二阶导数连续)。1、三次样条插值函数能够逐段表示成三次多项式且二阶导数连续(具有二阶光滑度)的函数。定义：设，且在上为三次多项式，其中，

16、则称为上的三次样条函数。若对给定的，满足，则称为三次样条插值函数。边界条件：第一种边界条件： 固支梁条件；第二种边界条件： 简支梁条件。特别地，时的样条称为自然样条。2、三弯距方程与三次样条的计算记弯距，因在上为三次多项式，故为一次多项式，可令Lagrange线性插值。对积分两次并代入，得其中。对求导得，从而可得，类似可得。利用得，其中。对第二种边界条件，则关于弯距的矩阵方程为，其中。上述方程称为三弯距方程，其系数矩阵为三对角，可用追赶法求解。求出代入即可得每个上的表达式。例5、 求6例中的三次样条插值函数(自然样条)。解：表达式如下： 3、三次样条插值的存在唯一性定理：三弯矩方程中的系数矩阵

17、是可逆的，即三次样条插值存在、唯一。证：设为的解，满足，因，故。又有，即。若不可逆，则有非零解，由前所证，应有，矛盾，故可逆，存在唯一的。4、样条函数的极性极性定理：对若为满足的三次样条插值函数，则，其中。证：，而，故，得，即，二阶导数的范数最小。第二章上机实验目的：3、 熟悉Maple中的一般插值、样条插值和序列等命令；4、 通过对具体数据做高次插值、样条插值，加深对龙格现象以及样条插值优越性的理解与认识。实验内容：对数据x1 2 5 6 7 8 10 13 17f(x)3.0 3.7 3.9 4.2 5.7 6.6 7.1 6.7 4.51、 做出折线图，得出的大致形状；2、 求出一般插值

18、多项式（8次）；3、 求出三次样条插值多项式；4、 将与、与分别做图对照，观察高次插值的危害性以及样条插值的优越性。1矩形区域二元函数的分片线性插值已知平面上一矩形域内四个顶点顶点处的函数值分别为。分两片的函数表达式如下：第一片(下三角形区域)：满足，插值函数为：。第二片(上三角形区域)：满足，插值函数为：。2矩形区域二元函数的双线性插值双线性插值函数的形式如下：，它是分片空间二次曲面。利用该函数在矩形的四个顶点（插值节点）的函数值，得到四个代数方程，可以确定四个待定系数。双线性插值函数可按下方法计算。已知平面上一矩形域内四个顶点顶点处的函数值分别为，求函数，使其满足条件：。令，则有。Ch3、

19、函数逼近与计算1、引言1、引例某气象仪器厂要在某仪器中设计一种专用计算芯片，以便于计算观测中经常遇到的三角函数以及其它初等函数。设计要求在区间中变化时，近似函数在每一点的误差都要小于某一指定的正数。(1)由于插值法的特点是在区间中的个节点处，插值函数与被插值函数无误差，而在其它点处。对于，逼近的效果可能很好，也可能很差。在本问题中要求在区间中的每一点都要“很好”地逼近，应用一般的插值方法显然是不可行的，龙格现象就是典型的例证。采用样条插值固然可以在区间的每一点上满足误差要求。但由于样条插值的计算比较复杂，需要求解一个大型的三对角方程组，在芯片中固化这些计算过程较为复杂。(2)可以采用泰勒展式解

20、决本问题。将在特殊点处做泰勒展开取其前项作为的近似，即但泰勒展式仅对附近的点效果较好，为了使得远离的点的误差也小于，只好将项数取得相当大，这大大增加了计算量，降低了计算速度。因此，从数值计算的角度来说，用泰勒展式做函数在区间上的近似计算是不合适的。(3)引例提出了一个新的问题，即能否找到一个近似函数，比如说，它仍然是一个次多项式，不一定要在某些点处与相等，但却在区间中的每一点处都能“很好”地、“均匀”地逼近。2、逼近问题对，求一个多项式，使在某种衡量标准下最小。(1)一致逼近（均匀逼近）无穷范数：最小(2)平方逼近（均方逼近）欧氏范数：最小。3、维尔斯特拉斯定理定理：设，则对任意，有多项式，使

21、在上一致成立。本定理的证法很多，伯恩斯坦在1921年引入了一个多项式他证明了。伯恩斯坦多项式在自由外形设计中有较好的应用。但它有一个致命的缺点，就是收敛太慢。要提高逼近精度，只好增加多项式的次数，这在实际中是很不合算的。切比雪夫从另一个角度去研究逼近问题。他不让多项式的次数趋于无穷，而是先把固定。对于，他提出在次多项式集合中，寻找一个多项式，使在上“最佳地逼近”。2、正交多项式一、正交多项式的概念及性质定义1：设区间上非负函数满足(1)存在；(2)对非负连续函数，若，则在上，则称为区间上的权函数。定义2：设，为上的权函数，则积分 称为与在上的内积。定义3：设为上的次多项式，若满足 ，则称为上关

22、于权函数的正交多项式系。定理：上的正交多项式在内有个不同的实零点。二、Legendre多项式1、定义，称为Legendre多项式。2、性质(1)正交性：。(2)奇偶性：，即为奇（偶）数时，为奇（偶）函数。(3)递推公式：。三、Chebyshev多项式1、定义称为第一类Chebyshev多项式。若记，即，则。2、性质(1)在上关于权正交，即。证：。(2)当为奇（偶）数时，为奇（偶）函数。证：。(3)递推关系。证：，即。(4)是次多项式，其最高项系数为。证：由易知为次多项式。故，即最高项系数为。3、最佳平方逼近1、问题 对，在生成的子集中求一函数，使最小。2、求解记，令，得，即，也可改写为下列矩阵

23、形式 法方程。3、用正交多项式做最佳平方逼近若取，因，由法方程可得，从而即为的最佳平方逼近多项式。若取，因，由法方程可得，从而即为的最佳平方逼近多项式。例1、用正交多项式求在上的三次最佳平方逼近多项式。解：用Chebyshev多项式，故。用Legendre多项式，故。4、函数按切比雪夫多项式展开定义：称为切比雪夫级数或广义傅立叶级数，其中 根据切比雪夫多项式的性质，切比雪夫级数的部分和可作为的近似最佳一致逼近多项式。例2、将在上展成切比雪夫级数。解：因为奇函数，从而也为奇函数，故从而注：的泰勒展式为 即切比雪夫展式可用较小的项数达到泰勒展式的精度，如对要达到10位有效数字，泰勒展式要25项，而

24、切比雪夫展式仅要10项。5、离散数据的拟合与最小二乘法1、离散数据的拟合问题引例1：矿井中某处的瓦斯浓度与该处距地面的距离有关，现用仪器测得从地面到井下500米每隔50米的瓦斯浓度数据，根据这些数据完成下列工作：(1)寻找一个函数，要求从此函数中可近似求得从地面到井下500米之间任意一点处的瓦斯浓度；(2)估计井下600米处的瓦斯浓度。根据所学内容，分别给出解决上述问题的方法，并说明理由。对于第一个问题，可根据已有瓦斯浓度数据，求出其样条插值函数，由即可较为准确地求得从地面到井下500米之间任意一点处的瓦斯浓度。但对第二个问题不宜用插值方法，因为600米已超出所给数据范围，用插值函数外推插值区

25、间外的数据会产生较大的误差。解决第二个问题的常用方法是，根据地面到井下500米处的数据求出瓦斯浓度与地面到井下距离之间的函数关系，由求井下600米处的瓦斯浓度。引例2：在某化学反应中，根据实验测得生成物浓度与时间的关系如下表，求浓度与时间的对应函数关系，并据此求出反应速度曲线。时间x12345678910浓度y4.006.408.008.809.229.509.709.8610.0010.2011121314151610.3210.4210.5010.5510.5810.60显然，从理论上讲是客观存在的，但在实际中仅由离散数据 是不可能得出的精确表达式的，只能寻找的一个近似表达式，这种问题称为

26、离散数据的曲线拟合问题。曲线拟合需解决如下两个问题：(1)线型的选择；(2)中参数的计算。2、线型的选择通常主要根据专业知识和散点图确定的线型，常见的线型有：(1)线性函数：；(2)可化为线性函数的非线性函数，如(1)(3)非线性函数。3、计算线性拟合的最小二乘法做数据的散点图，若近似为直线，则可用线性函数拟合。对于本问题通常采用最小二乘法，即所求参数使得在处的值与之差的平方和最小，将上式视为关于的二元函数，对分别关于求偏导并令其为零 ，即，解上方程组得，。例1、观测物体的直线运动，得出以下数据，求运动方程。时间t 0 0.9 1.9 3.0 3.9 5.0距离s 0 10 30 50 80

27、110解：数据点的折线图所求运动方程为可用相关系数衡量数据线性化程度，本例中相关系数，这表明数据的线性相关性较好。拟合运动方程与数据点对照图4、可线性化的非线性拟合例2、根据本节引例中的数据拟合出生成物浓度与时间的近似表达式。解：数据的散点图(1) 用双曲线型拟合令，则为线性函数。经计算，从而(2) 用指数线型拟合两边取对数，令，则为线性函数。经计算，从而两种线型的误差分析：令（均方误差），分别将和代入计算得，显然，此结果表明，线型(2)优于线型(1)。作业：在某化学反应中，根据实验所得分解物的浓度与时间关系如下，求浓度y与时间t的拟合曲线。(用指数线型拟合)时间x51015202530354

28、0455055浓度y1.272.162.863.443.874.154.374.514.584.624.64拟合结果的评价准则：设数据点为，拟合函数为，则称为拟合残差。准则1：最大误差准则，即最小。准则2：平均误差准则，即最小。准则3：均方误差准则，即最小。上述三准则与数据的大小、量纲有关，不具可比性。下面给出一种规范的误差准则，其中显然，越接近于1，拟合效果越好。7、Fourier逼近与FFT一、周期函数的最佳平方逼近设以为周期，则称为的傅立叶级数，其中。称为傅立叶级数的部分和，也称为次三角多项式，下面讨论三角多项式对周期函数的最佳平方逼近。1、连续情形设是以为周期的平方可积函数，则因= 为

29、上的正交函数系，事实上， 故根据用正交多项式作最佳平方逼近的法方程，在上的最佳平方逼近多项式存在且唯一，其系数即傅氏级数的部分和即为的最佳平方逼近三角多项式。2、离散情形 在上取的个观测值，其中记可证，即共个向量构成正交系。 取正交系对进行最佳逼近，则其中二、快速Fourier变换(FFT)1、Fourier变换Fourier级数的推广对任意函数，则称为的Fourier变换，称为的Fourier逆变换，与称为Fourier变换对。 常用的Fourier变换有(1) 方脉冲， 函数 (2)2、离散的Fourier变换对给定序列，分别称为离散Fourier变换与离散Fourier逆变换。若给出在上

30、的值，则的离散Fourier变换为。采样定理：若的频率范围为，则只有当采样间隔时，才能正确恢复。此时，采样频率，称为Nyguist频率。3、快速Fourier变换(FFT)的计算从的表达式中可以看出，计算一个需要次乘法、次加法，计算所有需要次乘法。当较大时，就很大，即常规离散Fourier变换计算量太大。1965年Cooley和Tukey提出了一种快速Fourier变换，其乘法次数仅为 ，大大降低了计算量。例如，当时，。第三章上机实验目的：5、 熟悉Maple中的拟合、求相关系数等命令；6、 通过对具体数据做可线性化的非线性拟合，了解曲线拟合的具体步骤。实验内容：在某化学反应中，根据实验所得分

31、解物的浓度与时间关系如下，求浓度y与时间x的拟合曲线。时间x510152025303540455055浓度y1.272.162.863.443.874.154.374.514.584.624.645、 做出数据的散点图，根据的大致形状，选择相应的线型(用指数线型或双曲线型拟合)；6、 将方程线性化，用Maple相应命令求出此线性方程及相关系数；7、 将线性方程还原为原非线性方程，并将此方程的图形与散点图加以对照，观察拟合效果。Pade逼近（有理逼近）简介借助函数的Taylor级数来研究函数的性质，或直接用它的部分和逼近该函数，不仅是纯数学领域中经常使用的手段，也是应用中赖以发展的方法之一。在数

32、值计算领域中，用Taylor多项式来逼近一个函数并进而导致各种有效的数值方法巳司空见惯，并在很多情况下获得了成功。但有时这种方法的应用显露出某些缺陷。这些缺陷一般来说是由于函数的Taylor级数的收敛速度较慢或其收敛范围较狭。如果采用有理函数作为逼近工具则能常常获得出人意外的好结果。例1、的Taylor级数为其部分和为 用计算的近似值，收敛速度很慢。比如为了保证误差不超过，就需要取。 若取有理函数对其进行逼近，则效果大不相同。例2、的Taylor级数为当时，上述级数发散，但用有理函数逼近可扩大其逼近范围。Ch4、数值积分与数值微分1、引言1、对采用数值积分的原因的原函数不是初等函数或过于复杂，

33、如等；为离散形式。2、数值积分的基本思想机械求积 将表示为在若干点处值的线性组合即 ，、和分别称为求积节点、求积系数和余项。称为求积公式3、代数精度定义：若对于不高于次的多项式，余项，而总存在次多项式使，则称求积公式代数精度为。4、插值型求积公式定义：对及，做插值，则，称此求积公式为插值型求积公式。显然，插值型求积公式的代数精度至少为。2、Newton-Cotes公式一、Newton-Cotes公式1、定义：对插值型求积公式，若取等距节点， ，则，此时称求积公式为Newton-Cotes公式。当时， 梯形公式当时，称为Simpson公式当时，称为Simpson-3/8公式 2、余项 Newto

34、n-Cotes公式的代数精度为3、收敛性与数值稳定性 求积公式收敛的必要条件为有界； 对较大的，Newton-Cotes公式不稳定，不宜采用。二、复化求积法将等分，在每个小区间上用低阶Newton-Cotes公式求得该区间的积分值，则，此方法称为复化求积法。1、复化梯形公式 2、复化Simpson公式 例1、分别用复化梯形公式(n=8)和复化Simpson公式(n=4)计算。解：x 0 1/8 2/8 3/8 4/8 5/8 6/8 7/8 1f(x) 1 0.9973978 0.9896158 0.9767267 0.9588510 0.9361556 0.9088516 0.8771925

35、 0.84147093、复化公式的误差复化公式余项为3、Romberg加速收敛法1、加速收敛技巧在用序列逼近时，若能从产生出新序列，它比更快地收敛于，此即加速收敛技巧。例如用逼近时，类似地此加速收敛算法称为Richardson外推算法。2、Romberg求积法将步长逐次减半，得序列，分析误差可得新序列。 用逼近I的算法称为Romberg算法。4、高斯型求积公式1、高斯公式与高斯点定义：对插值型求积公式，若能选择适当的使其具有次代数精度，则称此求积公式为高斯公式，其节点称为高斯点。2、高斯公式的构造定理：求积公式为高斯公式的充要条件是以为零点的多项式与任意不超过次的多项式均正交，即。证：必要性：

36、设为次数不超过的多项式，则不超过次，因为高斯公式，故，又，从而。充分性：对次数不超过的多项式，用除，商为，余式为，则次数均不超过，且，又，故推论：上次正交多项式的零点即为Gauss点。证：因为正交多项式与比它次数低的任意多项式都正交，且上次正交多项式恰好有个不同的实零点，故得证。3、Gauss-Legendre公式对积分区间，取其上次Legendre多项式的零点为节点，则称为Gauss-Legendre求积公式。此时，令又故。两点Gauss公式：三点Gauss公式：例、解：两点Gauss公式：两点梯形公式：三点Gauss公式：三点Simpson公式：若积分区间为，可作代换，则4、高斯公式的稳定

37、性Gauss公式中的证：因为次多项式，为次，Gauss公式准确成立，故。Gauss公式是数值稳定的。证：设的近似值，则为的近似值，Ch5、常微分方程的数值解法1、基本概念与Euler公式1、数值解法的必要性 不能给出解的解析表达式； 求封闭形式的解计算量太大。例如 2、数值解法的基本思想离散化对初值问题求出解在节点上值的近似值，其中。3、Euler公式将在上积分，得，用数值积分法求。 （矩形公式），得 Euler公式 （矩形公式），得 后退的Euler公式 （梯形公式）得 梯形公式（隐形）4、改进的Euler公式Euler公式计算简便，但精度差，梯形公式为隐式，计算较复杂，但精度较高，可将两者

38、结合。称为改进的Euler公式，上式也可写为 例1、求解初值问题 ()解：Euler公式 改进的Euler公式 x0.10.20.30.40.50.60.70.80.91.0Euler1.1001.1921.2771.3581.4351.5091.5801.6501.7171.785Euler改1.0961.1841.2661.3431.4161.4861.5531.6161.6781.738准确1.0951.1831.2651.3421.4141.4831.5491.6121.6731.7322、Runge-Kutta方法1、Taylor级数方法与阶对，有Taylor级数将此级数截断，并用代

39、替，得阶Taylor公式 显然截断误差为定义：若某方法的截断误差为，则称此方法精度为阶。2、Runge-Kutta方法基本思想， 平均斜率取，即为Euler公式；取，即为后退的Euler公式；取，即为梯形公式。借用Taylor级数法的思想，将中的(平均斜率)表示为在若干点处值的线性组合，通过选择组合系数使公式达到一定的阶。3、二阶Runge-Kutta方法选为在某两点处值的线性组合，即，其中，待定。将代入得将上式与二阶Taylor公式对比得（*）。根据Euler公式， ，代入得，其中满足（*）式，称之为二阶Runge-Kutta公式。特别地，当时， 改进的Euler公式4、四阶Runge-Ku

40、tta方法三阶Runge-Kutta方法较少使用，仿二阶Runge-Kutta方法，可得四阶Runge-Kutta公式，经典的四阶Runge-Kutta公式为特点：单步、自开始；精度高，误差为，四阶；数值稳定；要计算四次函数值；对解的光滑性要求高。3、单步法的收敛性与稳定性1、收敛性定义：若某数值解法对固定的，当时（此时），则称此方法收敛。例2、对典型方程考察Euler方法的收敛性。解：Euler公式为，而，即， 故收敛。定理：若数值方法中的关于满足Lipschitz条件，则该方法收敛。2、稳定性定义：若某方法在节点值上有大小为的摄动，而其后各节点上的误差无效不超过，则称此方法是稳定的。例3、

41、对方程，考察Euler公式和后退的Euler公式的稳定性。解：对应的Euler公式为，若在上有摄动值，而它使产生的摄动值为，则，显然，即时，Euler公式稳定，称之为条件稳定。后退的Euler公式为， 即后退的Euler公式无条件稳定。Ch6、解非线性方程的数值方法1、二分法零点定理：设，且，则在内至少有一根。令为的中点，若，则内有根，否则内有根。类似地进行步之后，设有根区间为，则，可取为的近似根，显然误差。特点：2、迭代法1、迭代格式对非线性方程，给定一个初值，按照某种方法产生一个序列，使得，且。例如，将改写为，令(Picard迭代)2、收敛性与误差估计定理1：若对任意，有(压缩映射)；存在

42、正数，使对任意，有(Lipschitz条件)，则对任意，迭代序列收敛于的唯一根，且有误差估计式证：令，由Lipschitz条件，又若，则即为的根，否则由零点定理，在内至少有一根，故在上至少有一根。（存在性）若有两个根，即从而有矛盾，故。（唯一性）由于，故 即 。（收敛性）而得令，则有3、收敛速度与收敛阶定义：设迭代公式收敛于的根，如迭代误差满足，则称为P阶收敛，特别地P=1，2时称为线性、平方收敛。定理2：对迭代公式，若，为的根，则迭代在附近是P阶收敛的。（局部收敛）3、牛顿法（切线法）1、迭代格式设为根的近似值，由Taylor公式若，则略去最后一项后作为新的近似值，即 称之为牛顿公式2、牛顿

43、法的几何意义 如图，作曲线在处的切线，令，即为此切线在轴上的截距。3、牛顿法的收敛性设为的单根，即，此时， ，故在的某邻域内，从而，由定理1，牛顿法对附近的初值收敛，即局部收敛，再由定理2知，牛顿法为二阶收敛的。例1、用牛顿法求的一个根。解：例2、应用牛顿法于方程，导出求立方根的迭代公式，并讨论其收敛性。解：，因，即有下界，又，即单调下降，故收敛。Ch7、解线性方程组的直接方法1、引言对线性方程组 (1)令，则(1)可记为 (2)求解的数值方法有如下两类：1、直接法 2、迭代法存贮量大； 存贮量小；计算时间短； 计算时间长；程序复杂； 程序简单；适用于A为低阶矩。 适用于A为高阶稀疏矩阵。2、

44、 Gauss消去法1、消元过程记为 (3)若，令，用乘第一个方程后加到第个方程上，则(3)变为 记为一般地，对若，令，类似地可消去从第到第个方程中的，直至将方程化为上三角方程。 记为2、回代过程3、矩阵的LU分解矩阵A的第一行乘后加到第行的变换，相当于用矩阵左乘矩阵A一般地，第步所用变换对应于矩阵Gauss消去法可用矩阵描述如下： ，即，记上三角，下三角，则 矩阵的LU分解。定理1：当方阵A的顺序主子式时，A可唯一地分解为单位下三角阵L与上三角阵U之积，即A=LU。设，则对，即，只要经两次回代即可解出方程。3、Gauss列主元消去法1、Gauss消去法中的称为主元，从理论上讲仅需即可，但从数值

45、计算的角度来看，其绝对值越小，引起的舍入误差就越大，反之舍入误差就小。为了减小舍入误差，提高算法的数值稳定性，可在每步消元过程中选主元，具体有：总体选主元(每步系数矩阵中绝对值最大者)按列选主元(在第k步中，从中选绝对值最大者)2、计算过程只须在Gauss消去法中加入选主元过程。在中选出绝对值最大者，然后放在(k,k)位置（交换行）。4、追赶法与Cholesky分解1、追赶法对三对角方程 首先由第一个方程解出，令，则，代入第二个方程得，即，令，有，类似地可推出下列公式 其中 ，将代入最后一个方程，令，则，代入即可依次求出。上述求解过程可分为两个部分：依次确定，称之为追的过程；依相反次序确定，称

46、之为赶的过程。即2、对称正定阵的分解定理2：设A对称，且A的各阶顺序主子式均不为零，则A可唯一地分解为，其中L为单位下三角阵，D为对角阵。定理3：设A对称正定，则A可唯一地分解为，其中L为对角元大于零的下三角阵。证：由定理2，又A正定，有中的，故其中为下三角。（Cholesky分解）设A对称正定，则可化为，即，经回代即可解。计算机解法：A为一般方阵时，用LU分解（Gauss消去法）；A对称正定时，用Cholesky分解。5、向量和矩阵的范数一、向量的范数1、定义：设或，为定义在上的一个实值函数，若满足非负性：，当且仅当；齐次性：对，有；三角不等式：对，有；则称为上的一个向量范数。2、常用向量范

47、数对，有范数 ；1-范数 ；2-范数 ；p-范数 定理4：中的一切范数都是等价的，即对任意两种范数，总有正数m和M，使3、向量序列的收敛性定义：设为中的向量序列，并记，若，则称收敛于，记为定理5：，为任一范数。二、矩阵的范数1、定义：若矩阵的某个实值函数满足； 相容性；则称为上的一个矩阵范数。2、常用矩阵范数 行范数； 列范数 2-范数； F-范数3、谱半径定义：设A的特征值为，称为A的谱半径。定理6：A的谱半径不超过A的范数，即。证：设为A的任一特征值，为相应的特征向量，即，则 相容性，故，即。定理7：若，则可逆，且。证：若不可逆，即，有非零解亦即有，使， ，矛盾，故可逆。，得6、误差分析和

48、矩阵的条件数1、右端向量误差对解的影响设的右端向量有误差，相应的解为，则，又，故2、系数矩阵误差对解的影响设的系数矩阵有误差，相应的解为，则，由定理7，若，则可逆，且，故3、矩阵的条件数定义：设A非奇异，则称为的条件数。；若A为正交阵，则。 常用条件数：；4、病态方程组 条件数刻画了方程组的解对原始数据误差的敏感程度。当条件数很大时，或的扰动所引起的的误差可能很大，此时称为病态的或坏条件的，对应的方程组称为病态方程组，反之称为良态的或好条件的。例、，Ch8、解线性方程组的迭代法1、基本概念1、迭代法对线性方程组，给定初始向量，按某种方法生成向量序列 ，且，使。2、迭代法的一般格式设，其中可逆，

49、则。令，则，故可建立迭代公式。若收敛，即，则，即为的解。3、误差向量令 (误差向量)，显然，即，迭代收敛，即。2、Jacobi迭代与Gauss-Seidel迭代设的主对角元均不为零，将分解为，其中为对角阵，和分别为的除主对角元以外的下三角和上三角部分，即，1、Jacobi迭代由，即，得迭代公式，或。2、Gauss-Seidel迭代由，即，得迭代公式, 或 3、迭代法的收敛性例1、取，分别用Jacobi迭代与Gauss-Seidel迭代解下列方程组。； ； ； 解：方程精确解为，Jacobi和G-S迭代均发散。方程精确解为，Jacobi迭代和G-S迭代均收敛，但收敛到同样精度，Jacobi迭代用

50、了125次而G-S迭代仅用了9次。方程精确解为，Jacobi迭代发散，而G-S迭代仅用7次即收敛。方程精确解为， G-S迭代迭代发散，而Jacobi仅用4次即收敛。1、矩阵序列的收敛性定义：对矩阵序列及，若，则称收敛于A，记为。定理1：2、迭代法收敛定理定理2：迭代法收敛的充要条件为。3、收敛的充分条件若A为严格对角占优矩阵，即，则Jacobi迭代和G-S迭代收敛；若A对称正定，则G-S迭代收敛。4、逐次超松弛（SOR）迭代法1、基本思想计算表明，当阶数较高时，G-S迭代收敛速度仍然较慢，可在G-S迭代基础上对其加速收敛超松弛法。从G-S迭代公式求得的结果不作为第次近似解，而仅作为中间结果，然

51、后再将与进行加权平均后作为第次近似解，即。时，即为G-S迭代，时称为超（低）松弛法。2、具体计算公式由G-S迭代公式得，再令，代入得改成矩阵形式为 故 记为3、SOR法收敛条件定理3：SOR法收敛。定理4：SOR法收敛。证：设的特征值为，则又SOR法收敛，即，有，而，从而，即。定理5：若对称正定，且，则SOR法收敛。定理6：最佳松驰因子，其中为Jacobi迭代的迭代矩阵。例2、用SOR方法解方程组解：方程组的精确解为，取，迭代次数见下表。 最佳松驰因子，与实际计算结果基本吻合。Ch9、矩阵特征问题的计算方法1、引言定理1：（圆盘定理）设，则的任一特征值必属于下列在复平面上以为圆心、为半径的某圆

52、盘 。证：设为的任一特征值，为对应的特征向量，即，令，故定义：设为实对称阵，则称为Rayleigh商。定理2：设为阶实对称阵，其特征值为，则对任意，；。证：因为实对称阵，故可令与对应的正交规范特征向量为，即，从而对任意，有，故若为与对应的特征向量，即，则，即，同理。2、幂法一、迭代格式设有个特征值，个线性无关的特征向量，且，称为的主（强）特征值。对任意，有，令，则记的最大分量为，其中幂法的迭代公式为：，即与仅差一个常数因子。又的最大分量总是1，故若，则当时，此时， 即收敛于，收敛于规范化的特征向量。二、幂法的加速1、原点平移法幂法的收敛速度取决于，若把幂法应用于，则由于的特征值为，只要仍为主特

53、征值，收敛速度就取决于，对适当的，此比值远小于。2、Rayleith商加速由定理2，设为阶实对称阵，特征值满足，其正交规范特征向量为。由幂法 3、Jacobi方法一、平面旋转矩阵1、对实对称矩阵，总存在正交阵，使 其中为的特征值，为A的与对应的正交规范特征向量。例如，对二阶对称阵，可取正交阵，即平面旋转矩阵，使，其中。2、在中定义平面旋转变换，其中 称为中平面上的平面旋转矩阵。为正交阵；仅改变A的第行与第列的元素。二、Jacobi方法1、基本思想通过一系列平面旋转变换，逐步缩小非对角元的大小，最终将化为对角阵，从而求得其特征值，特征向量。2、有关定理定理3：设为对称阵，为正交阵，则，。证：因相

54、似变换不改变矩阵的特征值，故可令与的特征值均为定理4：设为对称阵，为旋转矩阵，则 定理5：设为对称阵，为一非对角元，则存在旋转阵，使中的非对角元，且，其中分别表示对角元、非对角元平方和。3、具体算法选取非对角元中绝对值最大的元素，。若，则由定理5，有一旋转矩阵，使中的，类似地可将中绝对值最大的非对角元化为零，继续此过程，可证：，且，即趋向一对角形，从而求出的特征值。4、收敛性定理6：设为实对称阵，为旋转矩阵，则（对角阵）。证：记，由定理5，其中代入有故，即（对角形）5、Jacobi方法的不足与改进Jacobi方法每次要寻找绝对值最大的非对角元，计算量较大；在某步被化为零的非对角元，在以后的各步中可能变成非零元，因此Jacobi法有时收敛较慢。改进：循环Jacobi法；阈Jacobi法。4、Householder变换一、Householder变换矩阵