计算方法教案.pdf

《计算方法教案.pdf》由会员分享，可在线阅读，更多相关《计算方法教案.pdf（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 1章误差分析与数值计算.31.1 引言.31.2 绝对误差与相对误差、有效数字91.3 近似数的简单算术运算.121.4 数值计算中误差分析的一些原则.14第 2 章 非线性方程（组）的近似解法.172.1 引言.172.2 根的隔离.182.3 对分法.192.4 迭代法.212.6 弦截法.242.6 弦截法.251.7用牛顿法解方程组.26本章小结.28第 3 章 线性方程组的解法.293.1 引言.293.2 高斯消去法.313.3 矩阵的LU 分解.353.4 对称矩阵的LD1J分解.363.5 线性方程组解的可靠性.373.6 简单迭代法.40本章小结.46第 4 章矩阵特征值

2、与特征向量的计算.474.1 引言.474.2 嘉法和反黑法.484.3 雅可比方法.494.4 QR 方法*.51本章小结 52第 5 章 插值与拟合.535.1 引言.535.2 插值多项式的存在和唯一性.545.3 拉格朗日插值多项式.555.4 均差插值公式.575.5 差分等距结点插值公式.595.6 爱尔米特插值公式.615.7 分段低次插值.625.8 三次样条函数.63 5.9 曲线拟合的最小二乘法.68本章小结.71第 6 章数值积分和数值微分.726.1 弓 I 言.726.2 牛顿一科特斯型积分公式.736.3 复合求积公式.756.4 龙贝格求积公式.796.5 高斯求

3、积公式.806.6 二重积分的数值积分法.846.7 数值微分.85本章小结 87第7章常微分方程的数值解法.887.1 引言.887.2 欧拉法和改进的欧拉法.897.3 龙格-库塔方法.907.4 线性多步法.967.5 算法的稳定性与收敛性.987.6 微分方程组和高阶微分方程解法.99本章小结.101第 1 章误差分析与数值计算1.1引言I、课程任务和目的：在第七届国际软件工程学术会议上，“计算方法”被列入应用方法学的研究领域，强调了计算方法的研究应用与软件方法学的研究密切结合。这就说明了计算方法与软件之间的联系以及在应用软件研制中的地位与作用，计算方法是研究各种数学问题求解的数值计算

4、方法。在计算机成为数值计算的主要工具的今天，则要求研究适合于计算机使用的数值计算方法。计算方法就是研究用计算机解决数学问题的数值方法及其理论，它的内容包括函数的数值逼近、数值微分与数值积分、非线性方程值解、线性方程组数值解、常微和偏微数值解等，即都是以数学问题为研究对象的。因此，计算方法是数学的一个分支，只是它不象纯数学那样只研究数学本身的理论，是把理论与计算紧密结合，着重研究数学问题的数值方法及其理论，计算方法是计算机应用和软件研制开发的重要组成部分，通过本课程的学习和上机实习，使学生掌握利用计算机进行科学计算的基本理论和基本方法，并且学会将基本理论和基本方法应用于软件开发以及软件研制。2、

5、本课程基本要求(1)掌握方法的基本原理和思想。(2)掌握方法处理的技巧及与计算机的结合。(3)掌握误差分析，收敛性及稳定性的基本理论。(4)学会进行可靠的理论分析，对近似计算要确保精度要求，要进行误差分析。(5)通过例子，学习使用各种计算方法解决实际计算问题。(6)通过上机实践，能编写算法和实现算法。(7)掌握数值计算中一些最基本、最常用的计算方法和算法。3、本课程与各课程的关系：山于本课内容包括了微积分、代数、常微分方程的数值方法，学生必须掌握这几门课的基本内容才能学好这一课程，同时，学习此课程还必须具备计算机系统的初步知识，掌握一门常用的高级语言，如：B A S I C、P A S C A

6、 L.C语言等，并须具备一定的编程能力。4、本课程的特点：（1）面向计算机，要根据计算机特点提供实际可行的有效算法。即算法只能包括加、减、乘、除运算和逻辑运算，是计算机能直接处理的。（2）有可靠的理论分析，能任意逼近并达到精度要求，对近似算法要保证收敛性和数值稳定性，还要对误差进行分析，而且都是建立在相应数学理论基础上的。（3）有好的计算复杂性。时间复杂性好是指节省时间；空间复杂性好是指节省存储量。这也是建立算法时要研究的问题，因为它关系到算法能否在计算机上 完成。（4）要有数值实验。即任何一种算法除了从理论上要满足上述三点外，还要通过数值实验证明是行之有效的。计算方法最基本的立足点是容许误差

7、，在误差容许的范围内对某一数学问题进行近似计算，得到能满足要求的近似结果。现实世界中误差是普遍存在的，由于世界上没有绝对精确的量具（绝对精确的量具是没有刻度的），因此人类通过量具采集的数据都是近似值，另一方面，我们的生产、实验工具都不是绝对精确的，这就使得人类在生产和科学实验中必需容许误差。计算机的应用可以分为二个方面，即数值计算和非数值计算。利用计算机进行数值计算的过程如下图所示:实际问题 一 数学模型 一 计算方法 一 程序设计 一 上机求解在上图中，计算方法的任务是：由建立的数学模型给出可编程并由计算机能完成的计算方法，然后编程和上机求解。由于计算方法是编程后可由计算机求解的近似计算方法

8、，如何确保近似解的精度显得尤为重要，必须深入讨论有关误差的基本概念和基本理论，为近似计算的精度分析打下基础。1、误差的来源(种类)误差的来源主要有以下四种(1)模型误差：建立数学模型时的误差。例如：在求重量的数学模型 G=m*g中，重量G不是仅与质量和重力加速度有关，它还与温度、测量地点的海拔、地层结构等众多因素有关，为了使模型较为简单和实用，采用抓住主要矛盾的方法，去掉了大量对重量影响不大的次要因素，建立了上述重量的近似模型，由此产生了模型误差。(2)观测误差：采集数据时的误差。采集数据时，通常是依靠仪器和量具，由于没有绝对精确的仪器和量具，因此采集的数据有误差，此误差称为观测误差。(3)舍

9、入误差：由于计算机字长有限而产生的误差。硬件再发展，计算机的字长总是有限的，在计算过程中，当数据的长度超过了计算机的字长时，计算机就会进行四舍五入，由此产生的误差称为舍入误差。(4)截断误差：无限形式的有限化而产生的误差。在计算中有时会运用无限形式的计算公式，例如台劳公式：f(x)=f(xo)+f-X o)(x-xo)+-+-)(X o)(x-xo)n+1!n!显然此公式无法进行计算，因此必需根据实际需要，从某项起将后面的各项截断，即f(x)f(x0)+f(X()(x-x0)+-+f()(X o)(x-xo)n1!n!由此产生的误差称为截断误差。1.2绝对误差与相对误差、有效数字为描述方便，首

10、先约定x*是精确值x的近似值。引入误差的概念，其目的是为了衡量近似值x*的好坏。(1 )绝对误差：x*-x由于精确值X通常无法确定，因此绝对误差无法计算，由此引入绝对误差限的概念。绝对误差限：绝对误差的一个上界。即：若|x*-x|4 e,则称e为X*的绝对误差限。绝对误差限的性质是：A.不唯一这是因为|x*-x|的上界是不唯一的。B.可确定只要我们对x*的实际背景有一定的了解，就不难确定|x*-x|的上界。例如，x*表示身高，则|x*-x|的上界可为3米。当x*是你求出的，那么为了说明你的工作认真，你 一 定会将|x*-x|的上界估计得尽量小，因此在这种意义上绝对误差限可用来衡量X*的好坏。山

11、于绝对误差限没有考虑问题的规模，因此有时它也不能衡量x*的好坏。例如：x是地球与太阳的距离，y是分子中二个原子间的距离，若|x*-x|W 1公里，|y*-y|1厘米，则并不能说y*比x*精确。由此引入相对误差和相对误差限的概念。(2)相对误差：(x*-x)/x*相对误差限：相对误差绝对值的一个上界。3、有效数字这里我们必须搞清楚什么是有效数字以及如何确定X*有几位有效数字。(1)有效数字的定义若|x*-x|x*的某一位的半个单位，则 称 X*精确到这一位，并从这一位开始，一直到前面第一个不为零的数都是X*的有效数字。此定义实际上定义了什么叫精确到某一位和什么叫有效数字。例如:若X*精确到小数点

12、后第3位，即指|x*-x14 0.5x10-3。(2)有效数字的判定方法方法一：四舍五入此方法首先确定x*是由x 的哪一位四舍五入产生的，然后从这一位的前一位开始一直到前面第一个不为零的数都是X*的有效数字。例 1若 x=0.872596,x*=0.87,求 x*的有效位数。解：x*是由x 的小数点后第三位四舍五入产生的，所以X*有二位有效数字。注意，方法一判定有效数字很简单，但有时会失效。例如，若 x=0.272987 x*=0.273102,此时无法用方法一确定x*的有效位数，原因是x*不是山x 四舍五入产生的，在这种情况下，必须用有效数字的定义来确定 X*的有效位数。即方法二：用定义此方

13、法首先计算I x*-x I，再判断它小于等于X*的哪一位的半个单位，然后从近一位开始，一直到第一个不为零的数都是有效数字。例 2若 x=0.62073,x*=0.6207,确定x*的有效位数。解：因为|x*-x|4 0.0003 4 0.5x10-4,x*精确到小数点后第4 位，所以x*有四位有效数字。例 3 若 x=0.080199,x*=0.802,确定x*的有效位数。解：因为|x*-x 1=0.0000140.5x10-5,所以wo.SxlO、,推出x*有三位有效数字。例 4若 x=6.28936,x*=7.3132,确定x*的有效位数。解：|x*-x|=0.02357 0 (k=l,2

14、,.n),其准确值为 xk 0,(k=l,2,.n)/=；的绝对误差限E(x*)左=1E(x*)这4-匕这()=、()女=1 k=l k=k=T|E(x*)归 幻 E(x：)|)t=i(1)和的绝对误差等于各项绝对误差之和。(2)和的绝对误差限不超过各项绝对误差限之和。类似的可以得到：和的相对误差限介于各项相对误差限的最小者与最大者之间。1.3.2 近似数的乘法结论：乘积的相对误差限不超过各项相对误差限之和。1.3.3 近似数的除法结论：商的相对误差限不超过被除数与除数相对误差限之和。1.3.4 近似数的幕和根（见教材p9）1 3 5 近似数的对数（见教材p9）1 3 6 近似数的减法结论：差

15、的绝对误差等于各项绝对误差之和。注意两个儿乎相等的近似数相减会使结果的有效数字损失，影响整个计算工作的准确性，应尽量避免。13.01-73.00=；01；-1 -cos(x)=2 sin2()ln(x,)-ln(x2)=ln()J3.01+J3.00 2 Z 无 2（当冈很小时，X 与 X2很接近时）1.4数值计算中误差分析的一些原则为保证计算结果的高精度，在进行数值计算时应遵循下述几个原则。(1)在进行除法时，要避免除数的绝对值 被除数的绝对值。为什么要“避免”？若 不“避免”，则除出的结果很大，由于计算机字长有限，它装不下，因此会进行四舍五入，一个很大的数进行四舍五入时舍去的部分也会很大，

16、这会使舍入误差变大。怎 样“避免”？因为用户只关心最后的计算结果，当中间计算过程中出现了除数的绝对值 被除数的绝对值时，就应该换一种计算方法，以避免这种情况的发生，以后我们将会针对具体的计算问题来讨论“避免”的方法。(2)在进行减法时，要避免二个相近的数相减。为什么要“避免”？若 不“避免”，就可能失去大量的有效数字，例如：若 a=30001和 b=30000都有五位有效数字，因为a-b=l,所以结果至多有1位有效数字。怎 么“避免”？“避免”的思路与第1个原则中“避免”的思路相同，须针对具体计算问题来讨论。(3)要防止“大数吃小数”什么是“大数吃小数”？我们用一个例子为说明。n计算 8 7

17、5 6 2 9 4 8 7 4+,其中 n=l()2。，o a10工i=l此题是一个很大的数与很多很小的数相加，若采用将大数依次与a1,a2,厮相加，由于计算机字长有限，因此在与为相加时会进行四舍五入将证舍去，这样，最后的结果仍是大数，这就是大数将ai.a2,a。吃掉了。为什么要“避免”?尽管每个小数都很小，但它们很多，可能它们的和比大数还大，而最后计算工结果为大数，显然误差可能很大。怎 样“避免”？有的同学提出先将小数相加，然后再与大数相加，这个思路是对的，但有一个漏洞，因为小数相加到一定程度也会变成大数，它也开始吃小数了。可以采取分部相加的方法解决。第 2章 非 线 性 方 程（组）的近似

18、解法2.1 引言方程f（x）=O 的解称为方程的根。也叫做函数f（x）的零点。方程求根大致包括三个问题（1）方程有没有根？如果有根，有几个根？（2）哪里有根？求有根的区间，区间内的任意一点作为根的近似值。（3）根的精确化，已知一个根的近似值后设法逐步把根精确化，直到足够精确为止。本课程主要研究问题（2）和（3）。2.2根的隔离求方程f(x尸0 的解的近似值时，首先要确定若干个区间，使每个区间内只有的一个根，这个步骤称为根的隔离。对一般的方程，根的隔离有两种方法(1)试值法。求出f(x)在若干点上的函数值，观察函数值符号变化的情况，从而确定隔根区间。(2)作图法。画出尸f(x)的草图，观察曲线产

19、f(x)与 x 轴交点的大致位置，从而确定隔根区间。例 1.2.1讨论方程f(x尸2x?-4x2+4x+2=0 的根的位置。fl=inline(2*xA3-4*xA2+4*x+2),fplot(fl,-1,1),f2=inline(log(x)-l/x),fplot(f2,l,2)例 1.2.2将方程xlog(x)=1 的根进行隔离。2.3对分法设有方程f(x)=O在(a b)内有且仅有个根a,这时有f(a)f(b)0可用对分法求a的近似值，方法如下(1)准备：计算区间(a b)两个端点的函数值f(a),f(b)(2)对分：取c=(a+b)/2为(a b)的中点,计算f(c)(3)判 断:如

20、果f=0,则c为f(x)=0的根，否则检验：若f(c)f(a)0,则方程的根位于 a c内，用c代替b,若f(c)f(b)0,则方程的根位于 c b 内，用c代替a。(4)检验：若|b-a|ep1.25001.5000c=(a+b)/2;1.25001.3750if f(c)*f(a)01.31251.3750a=c;1.31251.3438else1.32811.3438b=c;1.32811.3359end1.32811.3320a,b,abs(b-a),pause1.32811.3301end1.32811.3291fplot(f,l 2)方程的解x=1.32862.4 迭代法设有方程f

21、(x)=O 在 a b 上有且仅有一个根a,可用迭代法求a的近似值，方法如下(1)将方程f(x)=O 写成迭代形式x=(p(x)(2)在 a b 上任取一个初始值x o。(3)计算 x i=(p(x()(4)若|x x o|e(e为精度要求)，此时计算结束a=x“否则令x 0=X|转(3)。定理2 4 1(收敛定理)设函数(p(x)在 a b 上连续，在(a b)内可导，且满足(1)当 xe a b 时,(p(x)6 a b 当 xG a b 时，|(p(x)|Wm ),771 771(3)成立误差估计式l a -x jW;|x,-x0|a-x|1 称为超线性收敛，P=2 称为平方收敛，显然P

22、越大，迭代过程收敛的越快。可以证明当a是方程f(x)=O 的单根时，牛顿法是平方收敛的。当 a是方程f(x)=O 的重根时，牛顿法仅为线性收敛。对分法：收敛速度与公比为1/2 的等比级数相同。收敛速度最慢，但简单有效，不存在发散问题。弦截法：弦截法的收敛阶P=L 6 1 8。收敛速度次之，不需要计算f(x)的导函数，有发散问题。牛顿法：牛顿法是平方收敛，收敛速度最快，但要计算f(x)的导函数，有发散问题。第 3章线性方程组的解法3.1 引言在科学实验和工程设计中，经常用到解线性方程组的问题。本章讨论用计算机求解线性方程组的两类主要方法：I 接法和迭代法。解线性方程组的般表达式al l X 1+

23、a1 2x2+-+al nxn=匕a21Xl-a22X2*a2n*Xn=b2根据矩阵的运算的性质有am X1+an2x2+-+annx=bnail ai2ain-X1笥记为A x=b 其 中 A =a21 a22a 2n.X X2_anl an2 ann_Xn方程组Ax=b有唯一解的充分必要条件是d e t(A)O o理论上，可以用克莱姆法则x=Ak/A,(k=l,2.n)其中A=d e t(A),是A 中第k 列换成向量所得到的矩阵的行列式。计算需要的乘法次数为(n-l)(n+l)!,当 n 较大时,计算量很大。这种方法效率低，在实际应用中很少使用。解线性方程组的方法可以分为两类：一类是直接

24、法，其特点是只包含有限次的四则运算，在每次运算都无舍入误差的情况下，所得到的是方程组的准确解。由于实际计算中总是有舍入误差，所以实际得到的也是近似解。令一类是迭代法，它首先选择一组初始值，再运用同样的计算步骤，重复计算，得到近似解。由于这类方法中出现了极限过程，必须研究迭代过程的收敛性。本章主要介绍：直接法中的高斯消去法和主元高斯消去法。迭代法中的简单迭代法和塞德尔单迭代法。3.2高斯消去法3.2.1 顺序高斯消去法以 n=4为例说明高斯消去法的计算过程，设有线性方程组a“X|+a1 2x2+al3x,+a1 4x4=ba2iX1+a2 2x2+a2 3x3+a2 4x4=b2a3iX,+a3

25、 2x2+a3 3x3+a3 4x4=b3a4 1X +a4 2x2+a4 3x3+a4 4x4=b4a“X|+al2x2+a1 3x3+a1 4x4=b.a，；)X 2 +a，；*+a)?X 4 =b?a。；%+a*x3+a；?X 4 =b?a4 2)X2 +a4 3，X3 +a4 4)X4 =b4 )a“X +a1 2x2+a1 3x3+a1 4x4=b分(I)Y+A(1)Y +分a)、_ U(DCL2 2 八 2 1 a 2 2 人 3 a 2 2 4 u 2aa X-h n3 3 X3 十 d3 4 X4 -D3义4-A(2)Y 一 人 4 3 X3 十 d4 4 A4 -U4a1 1

26、x1+aI 2x2+a1 3x3+a1 4x4=b,a分 202)八X 2 -+A(，)Y +分(】)X -h(,)。2 2、3 a 2 2、4 u 2a3 3)X3+aMX4=2)4 4 X 4 =b)经过3 次消元步骤，得到以上形式。从最后一个方程中解出次依次回代得到方程组的全部解。计算过程见教材(P37)算法3.2,13.2.2主元消去法例 3.2.2解线性方程组0.0003X1+3.0000 x2=2.00011.0000+1.00002=1.0000解：按 4 位小数计算，得到刈=0.6667,工 2=0.0000,准确解出=1/3,必=2/3),误差很大。如果将方程组的顺序对换，得

27、到1.0000.x,+1.0000 x2=1.00000.0003X)+3.0000X2=2.0001按 4 位小数计算，得至lJxi=0.3334,孙=0.6667,准确解。产1/3,必=2/3),误差很小。在顺序主元消去法中，如 果 遇 到 方 程 组 中 4 的主对角线元素为零时，计算过程不能进行。如果4 的主对角线元素的绝对值很小，也会产生较大的舍人误差，使得最后得到的解与准确解有较大的误差。工程中使用较多的是列主元高斯消去法，计算过程见教材(P42)算法3.4f 6X+3XZ+2X3=6例 2 2 3 用顺序消去法解方程组 10X1+5X2+6X3=01 8XI+5X2+3X3=0方

28、程组的增广矩阵A|b6 32610 5608 5消元306.00003.00002.0000 6.0000002.6667-10.000001.00000.3333-8.0000方程组系数矩阵主对角线元素为零，消元过程无法进行!例 2 2 4 用主元高斯消去法解例2 2 3 中的方程组。方程组的增广矩阵A|b6326105608530选主元回代得至I 方程组的解1056063268530消元10.00005.00006.0000000-1.60006.000001.0000-1.80000选主元10.00005.00006.0000001.0000-1.8000000-1.60006.0000

29、消元10.00005.00006.0000001.0000-1.8000000-1.60006.00005.6250-6.7500-3.75003.3矩阵的LU分解定理3.3.1设矩阵/的 各 阶顺序主子式不等于5翔（k=l,2,n）,则A有唯一的LU分解，其中L为单位下三角矩阵，U为上三角矩阵。对于线性方程组4x=b如果已经得到了的LU分解，方程组的解可以通过以下方法得到LUx=b，令U x可，则有U=b,所以，求解Ax=b如的问题等价于求解两的系数矩阵为三角方阵的方程组。X=伉k-=2,3,六1X”=4=（”一 X%七）/%k=n-,n-2-j=k+l求解方程组Ax冲 的计算变得非常简单。

30、例3.3.1解线性方程组4户）PA=LU,LUx=Pb,Ly=Pb,Ux=yA=magic(3),b=l;2;3 ,L,U,P =lu(A),y=L (P*b),x=U y3.4对称矩阵的L D lJ分解设矩阵4 的各阶顺序主子式不等于。k#)(k=l,2,.n),则 A 有唯一的L U分解，其中L为单位下三角矩阵，U 为主对角线元素不为0 的上三角矩阵。U=町00%2,2 2 ,0,2).=u000 0“2 2 00:F1 I2/M1 1%,/知0 1 2./2 2o o：=DV00 0o 0 1从而A=LD匕若为对称矩阵4=力 T,主对角元素不为0 的上三角矩阵，则有A=AT=(LV)T=

31、俨/力，其中为户为单位下三角矩阵，为由L U分解的唯一性得到，心=匕于是4=L D L1.定理3.4.1设对称矩阵4 的各阶顺序主子式不等于小 视(k=l,2,.n),则唯一确定一个单位下三角矩阵L和主对角元素不为0 的对角矩阵。，使4=5 *;例 3.4.1 A=5 10 5-5;10 24-2-6;5-2 44-11;-5-6-11 23,L,P=chol(A),L*L如果线性方程组A x=b系数矩阵是对称正定的，A=lJL,l/Lx=b，令Lx=y,LTy=b例 343b=5 10-1-19,y=Lb,x=Ly3.5线性方程组解的可靠性3.5.1 向量范数和误差向量定义3.5.1设|.|

32、是定义在配 上的实值函数，如果对于陞 中 的 任 意 向量及任意非负实数我,满足(1)(非负性)对任意向量x都有假口0且1叩1=。的充分必要条件是=0。(正齐性)对任意实数k和任意向量x都向收|=川国|。(3)(三角不等式)对任意向量假力后冈出引。称|为向量范数。定理3.5.1对 上 的 任 意 向 量X=(X/,X 2 X )T,记网=闻+同+闻国2=收+片凡=酷闻|x 1 1 1，|x|2，|x|o o都是向量范数。定义3.5.2设 是 定 义 在 刈 上的实值函数，如果对于A 1中的任意矩阵A B及任意非负实数k,满足(1)(非负性)对任意矩阵A都有|以|0且|囿|=0的充分必要条件是A

33、=0。(2)(正齐性)对任意实数k和任意矩阵4都 有|9|=4四|。(3)(三角不等式)对任意矩阵4,5都 有|A+5|W M|+|5|,M A|W M|出II称I I|为矩阵范数。定理3.5.2对 上 的 任 意 矩 阵4记MI,=ZKIJ 1=1HI2=7AU)|g以n=4为例X mH m1 2 m”m1 47阴f;Y(k+1)A2m2 1 m2 2 m2 3 m2 4X?+f2Y3 DX 3m3 I m3 2 m3 3 m3 4X,Y(k+1)LA4_ m41 m42 m43 m44_.f4.TTTTx(k+l)Mx(k,f写成分量形式X产）=m1 1AY(1k)4-m x f)+m1

34、3x*k+ml 4x*k)+f.Xk+,)=m2 1+m2 2X 2k)+m 2 3 X 然+m2 4X 4k)+f2XK)=m3 1X，+m3 2x+L+U,其中。，L,U分别取A的主对角线，下三角和上三角部分的元素。由(+L+U)x=Z,Zx=-(L+U)x+瓦(L+U)x+O6,由此可以得到迭代形式x(k+,=-/)(+t/)x(k)+Db(k=0,l,2 )(3-6 7)雅可比迭代法的迭代矩阵M=-D XL+U).写成分量形式x fa=(一出戏)一心婢)一一%染+4)/知X,+l)=(_。2必)一的3工？i-a2nXn（）+4”a22（3-6 8）X”=（f,2 球）3 炉 一。,-1

35、蜷：+2）/ann3.7.2 高斯-塞德尔迭代法在计算(3-6 8)式时，用已经计算出的司进行后续的计算，可以得到=(-2石一3-anXn+4)/a+=(-%|球+-3 球)-a2nXn)+b2)/“2 2 门 小1.(3-6 9)X =(-35称式(3-6 9)为高斯-塞德尔迭代法。式(3-6 9)的矩阵表达形式为X(k+D _ _p-i Lx.p-uyx+D-b(k=0,l,2.)x(k+1)=-(D +L)-Ux(k)+(D +L)b(k=0,l,2.)(3-7 0)高斯-塞德尔迭代法的迭代矩阵MGS=-(D+L)-U.3.7.3雅可比迭代法和高斯-塞德尔迭代法的收敛性定理3.7.1雅可

36、比迭代法和高斯-塞德尔迭代法收敛的充分必要条件是它们的迭代矩阵的各个特征值的模都小 于lo定理3.7.2若存在某种范数|.|,使 则 雅 可 比 迭 代 法 收 敛。若 存 在 某 种 范 数 使|MG S|L则高斯-塞德尔迭代法收敛。例3.7.1分别用雅可比迭代法和塞德尔迭代法解方程组1 0%,-x2-2X3=7 2-x+1 0 x2-2X3=8 3 误差 e vi o”一%一%+5七=4 2雅可比迭代法迭代公式X(k+I)=O(L+U)?k)+D b高斯塞德尔迭代法迭代公式x(k+1)=.(D +L)“u k)+(0 +为 A=10-1-2;-l 10-2;-1-1 5b=72 83 42

37、1;D=diag(diag(A);U=triu(A,l);L=tril(A,-l);M=-inv(D)*(L+U);b=inv(D)*b;x=b;for k=l:l 0,x=M*x+b,endA=10-1-2;-l 10-2;-l-1 5b=72 83 42,;D=diag(diag(A);U=triu(A,l);L=tril(A,-l);M=-inv(D+L)*U;b=inv(D+L)*b;x=b;for k=l:5,x=M*x+b,end例 3.7.2考察用雅可比迭代法和塞德尔迭代法解方程组的收敛性。2-11 11 1雅可比迭代法迭代公式x +LUxw+(O+LYb例 3.7.3用雅可比迭

38、代法解方程组1 -2-1 1-2 -22 X-1 x21 1X310-2误雅可比迭代法迭代公式x(k+1)=-(L+t/)x(k)+DbA=2-1 1;1 1 l;l 1 -2D=diag(diag(A);U=triu(A,l);L=tril(A,-l);MJ=-inv(D)*(L+U);MS=-inv(D+L)*U;abs(eig(MJ)abs(eig(MS)A=l-2 2;-l 1 -l;-2-2 1b=l 0-2f;D=diag(diag(A);U=triu(A,l);L=tril(A,-l);M=-inv(D)*(L+U);b=inv(D)*b;x=b;x=M*x+b本章小结本章讨论了

39、解线性方程组的直接解法和迭代解法。直接解法比较适用与系数矩阵稠密（既零元素较少）的中、小型线性方程组，但对系数矩阵是带状或近似带状的大型线性方程组也适用。直接解法中的列主元高斯消去法具有精度较高和省时的优点，是计算机中常用的算法。迭代解法中主要介绍了雅可比迭代法、高斯-塞德尔迭代法和松弛法。迭代法具有计算公式简单、程序设计容易、占用计算机内存较少的优点。适用于解大型稀疏矩阵（既零元素较多）线性方程组。高斯-塞德尔迭代法是在雅可比迭代法的基础上改进得到，在很多情况下可以加快收敛速度，但它的收敛域与雅可比迭代法不同，因此不能互相取代。松弛法可以加速迭代过程的收敛速度，但 要 适 当 选 择 松 弛

40、 因 子 在选择迭代法时，要特别注意检验方法的收敛性问题。第4章矩阵特征值与特征向量的计算4.1引言求矩阵的特征值和特征向量，是代数计算中的重要问题。在自然科学和工程中的许多问题，例如电磁振荡、桥梁的振动，机械振动等都可以归结为求矩阵的特征值和特征向量问题。矩阵A 的特征值和特征向量是指，如果数大和非零列向量x满足关系式Ax=2ix,则数人称为A 的特征值非零列向量x 称为A 的与特征值九对应的特征向量。计算n 阶矩阵A 的特征值，就是求特征方程|A-4|=0的 根X,(i=l,2,.,n)o齐次线性方程组(A-Xi l)x=O的非零解x”是无对应的特征向量。本章讨论一些在计算机上计算矩阵的特

41、征值和特征向量的较为稳定的数值算法。4.2 塞法和反暴法1、幕法：计算n 阶矩阵A的模最大的特征值（主特征值）及对应的特征向量。任取n 维列向量x（）,用迭代公式x（k+D=A x（k）计算得到x（）,x（l）,x（2），设 x（=a M+a 2 V 2+anvn,因为 A V j=Z.jV j 所以x（1 =A x=a|X|V i+a 2 A _ 2 V 2+a n vnx =A x =a|X|2 V i+a 2 九 2 2 V 2+anXn2 vn一般地有x（k+i）=A x ）=a 仇 J V|+a 2 1 2 k V 2+anlnk vn=X k a v）+a 2（九 2 九 1 尸

42、V 2+an（Xn/X i）k vn当 k 充分大时X（k+l）=a&k+l v|=A|X（k）向量X（k+D 与 X00向近似地只差一个倍数，这个倍数就是模最大的特征值储。1、反暮法:A x M x,A-A x=A-XX,A-X=VX,即 A的特征值的倒数1 是 A的逆矩阵A 的特征值。用幕法求A-1的模最大的特征值，它的倒数就是A的模最小的特征值。4.3雅可比方法a 1 1 acos 0 s i n0uT（e）u（e）=-1 o-对于2阶方阵A =u（e）=_a21 a22_-s i n0 cos 00 1aH cos U e+a)2 s i n2 0 +a2 1s i n 2 0 J(a

43、“一aJ s i n2 9 +a 2 i cos 2 0UT(O)AU(O)=12一2(、a”-a1111，)s i n2 0 +a7 1 cos 2 0 aH s i n2 0 +a cos2 0-a7 1 s i n2 0Z 1 1 1/L 1 2 a令 一包2 2 -aH)s i n2 0 4-a2 1 cos 2 0 =0 t a n2 0 =-2ai l a2 2UT(0)A U(0)=o-0 x2_all a21 a31-对于n阶 方 阵（以n=3为例）A 二a21 a22 a32a31 a32 a33cos 0 s i n0 0X0X令t a n 2 6 =作变换矩阵u（e）=-

44、s i n0 cos 0 0则有 u（e）Au（e）=0XXa“一a220 01XXX2a一般地说，令tan29=J，可以将A中的元素的a”和却变为0。在实际计算中采用以下公式an-ajjcos 9 0 sinOx x 0令tan 20=二 作变换矩阵 U（0）=0 1 0则有 UT（9）AU（O）=X X Xa”一a3 3一 sinG 0 cos00 x x-1 0 0X X X令tan 20=作变换矩阵 U(0)=0 cosO sin0则有 UT(0)A U(0)=x x 0a22-a330-sin0 cosOx 0 x九=为1 ,、./入(o=sign(|i)曲+Usin 0=V 2(1

45、 +7 1-(O2)cos0=71-sin2 0例4.3.1 用雅可比求对称矩阵A=2-10-102-1-12的特征值和特征向量。（见教材P86）4.4 QR 方法*Q R方法是求般矩阵A 的全部特征值和特征向量的一种迭代方法。其基本思路是利用矩阵A 的 Q R分解,其中，R 是一个上三角矩阵，Q 是正交矩阵。通过迭代格式A.=Q.R.k k k将 A 化为相似的上三角矩阵（或4 句=&2分块上三角矩阵），从而求出A 的全部特征值和特征向量。例 4 4 1 用 Q R方法求矩阵A=的特征值。213123012特征向量-0.8165-0.40820.4082特 征 值 1.0000-0.6215

46、-0.62150.47700.6972-0.6760-0.6760-0.29354.3028a=2 1 3;1 2 3;0 1 2,q,r=qr(a),a=r*q本章小结本章介绍了求矩阵的特征值和对应的特征向量的几种方法。毒法可以求出矩阵的主特征值和对应的特征向量，优点是算法简单，但 当 w=1 时，收敛速度很慢。反基法可以求出矩阵的模最小的特征值和对应的特征向量。雅可比方法是利用一系列正交相似变换（即平面旋转变换）把实对称矩阵A 化为对角阵（近似），从而求出实对称矩阵全部特征值。Q R方法是用镜向反射阵将矩阵A 作 QR分解，是一种求矩阵的全部特征值的有效方法。第 5章插值与拟合5.1 引言

47、已知表格函数y=f(x)X iX oX 1X 2Xn-1Xnf(X i)y oy iY 2Y n-1Y n构造一个公式p(x)近似地表示f(x),解决这个问题的方法有两类：一类是插值法，另一类是拟合法，又称为逼近法。已知函数y=f(x)在互异点X。,xb x2,xn.b xn上的函数值y o,y i,y 2,，y n-i,y(i，构造一个函数p(x)使得p(X i)=y 这样的问题称为插值问题。y=f(x)称为被插值函数，X。xn称为插值区间，p(x)称为插值函数，X。，*1,*2 _.,*向,*1 1称为插值点，在插值区间内部用p(x)代替f(x)称为内插，在插值区间外部用p(x)代替f(x

48、)称为外推，R(x 尸f(x)-p(x)称为插值函数p(x)的误差。5.2插值多项式的存在和唯性定理：给出n+1个插值点及函数值XiX oX1x2Xn-lXnf(Xi)yoyiY2Yn-1Yn求一个 n 次多项式 pn(x)=ao+aix+a2x2+.+a nx n5.3 拉格朗日插值多项式V Y x X1、给出2个插值点(x 0,y o),凶，力)可以得到一次多项式p,(x)=-Ly0+-X。一X|x,-x02、给出3 个插值点(x0,y0),(X|,y D ,(x 2,丫 2)可以得到二次多项式n/Y、一 (x-x,)(x-x2)(x-x0)(x-x2)(X-XO)(X-X1)P 2 (x

49、 j -r y o+7 0 r y i+7 r y 2(x0-x1)(x0-x2)(x,-x0)(x1-x2)(x2-x0)(x2-x.)不难验证P 2(x)满足插值条件P 2(X o尸y o P 2(x j=y i p2(x2)=y23、给出n+1 个插值点(x0,y0)(X,y i),.,(xn,y j 可以得到一个n 次多项式pn(x)=L0(x)y0+Ll(x)y1+-+Ln(x)yn其中 LK(X)=73 x/_ (O n(x)=(x_Xo)(x_X|).(x-xn)(x-xK)a)n(xK)例 5.3.1按下列表格求y(-0.5)和 y(0.5)的值。xl 1 2 3y|7 14

50、23解：插值多项式L(x)=(x_x(x_X2)+(x-XoXx-x?)f (x-XoXx-xJ2(x0-x1)(x0-x2)(X-Xo)(X-X2)(XXQX XJ-XJ)2=(x-2)(x-3)7 (x-lX x-B),(X1)(X2)2 3(l-2)(l-3)(2-l)(2-3)(3-1)(3-2)=X2+4X+2L2(-0.5)=0.2500 L2(0.5)=4.2500例 4.3.2按下列表格求y(2.5)、y(4.5)、y(5.5)的值。x|1 2 3 4 5y|0 2 1 5 3解：插值多项式 L4(X)=-0.7917 x4+9.25 x3-37.21 x2+60.75 x-3