《计算方法》课件2第7章

7.1迭代法7.2向量和矩阵的范数

7.3迭代过程的收敛性7.4消去法

7.5追赶法

7.6误差分析7.7实例——小行星轨道问题习题七

7.1迭代法7.1.1雅可比迭代法

例7.1

求解方程组

解分离出x1，x2，x3,得

据此可建立迭代公式

设初值，，迭代得到

以此类推可得

结果如表7-1所示，迭代次数增大时，会越来越逼近方程组的精确解。表7-1雅可比迭代法结果考察一般形式的方程组：

从第i个方程组分离出xi,得

据此建立迭代公式：

(7.1)此公式称为雅可比(Jacobi)公式，展开如下：

(7.2)用相邻两次迭代结果的偏差刻划精度，当偏差e小于给定精度ε时计算终止。为防止发散，设置最大迭代次数N以控制计算量，如达不到精度，则宣告迭代失败。7.1.2高斯-赛德尔迭代法

再考察例7.1，得到近似值，由迭代公式得

所求的新值比老值更准确些，因此在计算时，用

来代替

用同样的方法计算，得

这样充分利用新值建立的迭代公式，称为高斯-赛德尔迭代法

设初值，迭代得到

以此类推，可得

结果如表7-2所列，比雅可比迭代法收敛更快。表7-2雅可比迭代法结果一般形式的方程组高斯-赛德尔公式为

(7.3)其特点是，一旦求出变元xi的某个新值后，将用新值来代替老值进行剩下的计算。偏差小于给定精度ε时，计算终止。

实际应用时，高斯-赛德尔法与雅可比迭代法各有千秋，雅可比迭代法收敛，而高斯-赛德尔法发散。7.1.3超松弛迭代法

迭代法的困难是计算量难以估计，有时迭代虽然收敛，但由于收敛速度缓慢，使计算量变得很大，从而失去使用价值，因此迭代过程要采取加速技术。

所谓松弛法，实质是高斯-赛德尔迭代法的一种加速方法，这种方法将前一步结果与高斯-赛德尔迭代值适当加权平均，期望获得更好的近似值，具体公式为

迭代：加速：

(7.4)

ω称为松弛因子，当ω=1时就是高斯-赛德尔迭代法。可以证明，为保证迭代过程收敛，要求0<ω<2。因为比准确，所以在加速公式中加大的比重，为此取1<ω<2，即为超松弛法，简称SOR方法。ω值由方程组系数结合实践计算来选取。合并：7.1.4迭代公式的矩阵表示

方程组矩阵表示为AX=b，式中

将A分解为

=L+D+U

其中D为对角阵，L和U分别为严格下三角阵和严格上三角阵。

(1)雅可比迭代法矩阵表示为

X

(k+1)=D-1(b-LX

(k)-UX

(k))或

X(k+1)=D-1b-D-1(L+U)X

(k)

X

(k+1)=D-1b+(I-D-1A)X

(k)

(7.5)

(2)高斯-赛德尔迭代法矩阵表示为

X

(k+1)=D-1(b-LX

(k+1)-UX

(k))

即

X

(k+1)=(D+L)-1b-(D+L)-1UX(k)

(7.6)

(3)松弛法矩阵表示为

X

(k+1)=(1-ω)X

(k)+ωD-1(b-LX

(k+1)-UX

(k))

即

X

(k+1)=(D-ωL)-1［(1-ω)D-ωU］X

(k)+ω(D+Lω)-1b

(7.7)上面三种方法均可写成X(k+1)=GX

(k)+d的迭代形式，收敛性与矩阵G的性态有关。7.2.1向量的范数

为研究迭代过程的收敛性，需要对向量的“大小”引进某种度量——向量与矩阵的范数。

对于向量X=(x1,x2,…,xn)T，其范数记为‖X‖，它是一个实数，且满足下列三项条件:

(1)(非负性)对于任意向量X，‖X‖≥0，当且仅当X=0时，‖X‖=0；7.2向量和矩阵的范数

(2)(齐次性)对任意实数λ及任意向量X，有‖λX‖=

‖λ‖·‖X‖；

(3)(三角不等式)对任意向量X和Y，有‖X+Y‖≤

‖X‖+‖Y‖。

常用的向量范数有以下几种：

(1)2—范数

‖X‖2=

(7.8)

(2)∞—范数

‖X‖∞=

(7.9)

(3)1—范数

‖X‖1=

(7.10)

例7.2

计算X=(1,2，-1,2)T的三种范数。

解

‖X‖2=

‖X‖∞=

‖X‖1=

以上三种范数是p-范数的特例，p=1,2时，很显然为1—范数和2—范数，当p→∞时，‖X‖p→‖X‖∞。

定理7.1

任意向量X，。按照不同方式规定的范数，其值一般不相同，但在各种范数下考虑向量序列收敛性时，却表现出明显的一致性，这就是向量范数的等价性。

如果存在正数C1，C2使对任意向量X，均有‖X‖p≤C1‖X‖q，‖X‖q≤C2‖X‖p，则称‖X‖p与‖X‖q等价。可以证明三种常用的范数‖X‖1、‖X‖2和‖X‖∞彼此等价。

向量序列X

(k)收敛到向量X*的充要条件是，对任意给定的p，当K→∞时，‖X(k)-X*‖p→0。7.2.2矩阵的范数

对于给定的n阶方阵，将的上界定义为A的范数‖A‖，即‖A‖=。由定义可知

，即‖AX‖≤‖A‖·‖X‖。因此矩阵范数具有下列基本性质：

(1)对于任意方阵A，‖A‖≥0，当且仅当A=0时，‖A‖=0；

(2)对任意实数及任意方阵A，‖λA‖=|λ|·‖A‖；

(3)对任意两个同阶方阵A和B，有‖A+B‖≤‖A‖+‖B‖，‖AB‖≤‖A‖·‖B‖。因为‖A‖=而，故矩阵范数可以等价定义为‖A‖=，相应的p—范数定义为‖A‖p=

定理7.2

对于n阶方阵，有

(表示方阵ATA的最大特征值的正平方根)

例7.3

计算A=的三种范数。

解

‖A‖1=max(4,6)=6,‖A‖∞=max(3,7)=7

ATA=

|λI-ATA|=

=λ2-30λ+4=0

‖A‖2=7.2.3矩阵的谱半径

设n阶方阵A的特征值为λ1,λ2,…,λn，则称

ρ(A)=

|λi|为A的谱半径。

定理7.3

ρ(A)≤‖A‖

证对于n阶方阵A，设，即ρ(A)=λ1，对应特征向量u1，u1为非零向量，则

λ1u1=Au1两边取范数得到：

|λ1|‖u1‖=‖λ1u1‖=‖Au1‖≤‖A‖·‖u1‖

而‖u1‖>0，所以有

|λ1|≤‖A‖

因此

ρ(A)≤‖A‖7.3.1迭代收敛的充分条件

由7.1节中迭代格式的矩阵形式知，方程组AX=b的雅克比迭代法、高斯-赛德尔迭代法和松驰法的矩阵形式都可以写成

X

(k+1)=GX

(k)+d

(7.11)7.3迭代过程的收敛性当然，不同的迭代法其迭代矩阵G和d的元素也不同。所以我们讨论迭代格式(7.11)的收敛性具有普遍意义。下面我们不加证明地给出迭代格式(7.11)收敛的充分必要条件。

定理7.4

对任意初始向量X

(0)及常向量d，迭代格式(7.11)收敛的充分必要条件是ρ(G)<1。这一结论在理论上是颇为重要的，但实际用起来不甚方便，为此我们着重研究更为实用的判别迭代格式收敛的充分条件。

定理7.5

对于方阵G，若‖G‖<1，则I-G为非奇异。

证明

(反证法)若I-G为奇异阵，则存在非零向量X，使

(I-G)X=0,有X=GX

‖X‖=‖GX‖≤‖G‖·‖X‖由于‖X‖≠0推导出‖G‖≥1与题设‖G‖<1矛盾，所以I-G为非奇异。

对于方程组AX=b的迭代法，先将它改写成X=GX+d的形式，据此迭代公式为X

(k+1)=GX

(k)+d，收敛性与矩阵G的性态有关。

定理7.6

若迭代公式G满足‖G‖<1，则迭代公式X

(k+1)=GX

(k)+d对于任意X(0)均收敛。

证法一由‖G‖<1，根据定理5知I-G为非奇异。因此方程组(I-G)X=d有唯一解

X*=GX*+d

X

(k)=GX(k-1)+d

两式相减

‖X

(k)-X*‖=‖G(X

(k-1)-X*)‖

≤‖G‖·‖X

(k-1)-X*‖

≤‖G‖2·‖X(k-2)-X*‖

≤‖G‖k·‖X(0)-X*‖因为‖G‖<1，当k→∞时，‖X

(k)-X*‖→0，故迭代收敛。证法二根据定理3可知，ρ(G)≤‖G‖<1，由定理4得到，迭代公式X

(k+1)=GX

(k)+d对于任意X

(0)均收敛。

例7.4

A=，b=，用迭代法x

(k+1)=x

(k)-ω(Ax

(k)-b)求解Ax=b，试确定可使迭代收敛的ω取值范围。

解

x

(k+1)=x

(k)-ω(Ax

(k)-b)=(I-ωA)x

(k)+ωb迭代矩阵为

B=I-ωA=

|λI-B|=

所以ρ(B)=max{|1-3ω|,|1-ω|}<1，即

解得

0<ω<

对于例7.1，线性方程组

雅可比迭代法的迭代矩阵为

高斯-赛德尔迭代法的迭代矩阵为

而‖G1‖∞=0.4<1，‖G2‖∞=0.3<1，故雅可比迭代法和高斯-赛德尔迭代法均收敛。7.3.2对角占优方程组

如果矩阵I主对角线元素的绝对值大于同行其他元素绝对值之和，即|aij|<|aii|(i=1,2,…,n),则称A为对角占优矩阵。定理7.7

若A为对角占优矩阵，则它是为非奇异的。

定理7.8

对角占优方程组AX=b的雅可比迭代法X(k+1)=

D-1b+(I-D-1A)X

(k)和高斯-赛德尔迭代法X(k+1)=-(D+L)-1UX

(k)+(D+L)-1b均收敛。

注意，定理7.8是充分条件，不是必要条件。不是对角占优方程组，有时可转化为对角占优方程组，如

交换次序得到：，此时对角占优，两种迭代方法收敛。求解线性方程组的另一类重要方法是直接法，消去法是最基本的一种直接法。消去法的基本思想是，将一个方程乘或除以某个常数，以及将两个方程相加减的这两种方法，逐步减少方程中变元的数目，最终使每个方程仅含一个变元，从而得出所求的解。

消去法有约当消去法和高斯消去法两种。7.4消去法7.4.1约当消去法

例7.5

求解方程组

解将(1)式x1的系数化为1，并消去(2)、(3)式中的x1项，得到

将(5)式的系数化为1，并消去其余两个方程中x2项，得到

在将(9)式中x3系数化为1，并消去其余两个方程中x3项，得到

x1=9,x2=-1,x3=-6

约当消去法的特点是，每一步仅在一个方程组中保留某个变元，从其余的各方程中消去该元，这样反复消元后，方程组最终加工成每个方程仅含一个变元的形式，从而得出所求的解。

约当消去法总的计算量为。流程如图7-1所示。图7-1约当消去法流程7.4.2高斯消去法

高斯消去法是约当消去法的改进，减少了计算量。在上例中，第二步只消去第(3)个方程的x2项，第(1)个方程x2项不改变，第三步只把第(3)方程x2系数变为1，可变为

把x3=-6代入第(2)方程，解出x2=-1，再把x3=-6和x2=-1代入第(1)个方程得到：

x1=9

高斯消去法分消元过程和回代两个环节，计算量为。高斯消去法流程如图7-2所示。图7-2高斯消去法流程

例7.6

求下面方程组的解：

解

7.4.3选主元法

高斯消去法的消元过程，第k步要用做除法，这要求它们全不为0。

定理7.9

假设方程是对角占优的，则(k=1,2,…,n)全不为0。

对于对角占优方程，可以不用考虑，它一定不为0。那么对于其它情形又如何呢？例如

精确解为采用高斯消去法，方程变为

结果严重失真。应将方程组改写为

运用上面技巧，第k步从xk各个系数k,…,的绝对值中挑选最大者为第k步主元素，设，若l≠k，则第l方程与第k方程互换位置，这一过程称做选主元消去法。选主元流程如图7-3所示。例7.7

求解线性方程组：

解图7-3选主元流程

定理7.10

假设方程是对角占优的，则

全是主元素。

从定理7.10可知，对于对角占优的方程，可以不选主元。7.5.1三对角方程组

在数值计算中，比如三次样条插值，或差分方法解微分方程边值问题，都会遇到下列形式的方程组

7.5追赶法用矩阵表示，简记AX=d系数A为

这是一个特殊的稀疏阵，其非零元素集中分布在主对角线及其相邻两条对角线上，故称为三对角矩阵。7.5.2追赶法的计算公式

1.消元过程

采用高斯消去法，先从第(2)个方程中消去x1，然后从第(3)个方程中消去x2，以此类推，可将方程组加工成下列形式其中

2.回代过程

以上就是解方程组的追赶法，它分追和赶的两个环节，追的过程为计算u1→u2→…→un-1和y1→y2→…→yn，赶的过程为按逆序计算xn→xn-1→…→x1。

追赶法原理与高斯消去法相同，但由于它考虑到方程组的具体计算特点，计算时将系数中大量零元素撇开，从而大大节省了计算量，计算量仅为5n次乘除法。7.5.3追赶法的代数基础

追赶法是将A分解为L和U:

定理7.11

设三对角阵A是对角占优，则它可唯一地分解成矩阵L和U，使A=LU，其中U为单位上二对角阵，L为下二对角阵。

计算过程为

计算过程次序为

l1→u1→l2→u2→…→un-1→ln

AX=d

L(UX)=d

可分解成LY=d，UX=Y两个方程组。由LY=d得到

解UX=Y得到

xn=yn,xi=yi-uixi+1(i=n-1,n-2)

这样求解可归结为以下三步：

(1)次序计算：l1→u1→l2→u2→…→un-1→ln。

(2)顺序求y1→y2→…→yn。

(3)逆序求xn→xn-1→…→x1。

追赶法流程如图7-4所示。图7-4追赶法流程

例7.8

用追赶法求解三对角方程

解

所以

x1=0，x2=1，x3=-1，x4=27.6.1方程组的病态

在现实方程组中，其系数往往含有误差，因此必须研究扰动对解的影响问题。

例7.9

考察方程组

7.6误差分析和上述两个方程组仅系数有微小的差别，但两者的解却大不相同。第一方程组x1=1,x2=1；

第二方程组x1=2，x2=0，这类方程组称为病态方程组。

为了定量地刻画方程组的“病态”程度，对一般方程组AX=b进行讨论。

首先考察b的扰动对解的影响，δb表示右端项b的扰动，相应的解X的扰动记为δX

A(X+δX)=b+δb从中消去AX=b，得到AδX=δb，故有δX=A-1δb

‖δX‖=‖A-1δb‖≤‖A-1‖·‖δb‖

另一方面

‖b‖=‖AX‖≤‖A‖·‖X‖，有两式相乘

再考察A的扰动对解的影响，δA表示A的扰动，相应的解X的扰动记为δX

(A+δA)(X+δX)=b

从中消去AX=b，得到AδX+δA(X+δX)=0，故有δX=-A-1δA(X+δX)‖δX‖=‖A-1δA(X+δX)‖≤‖A-1‖·‖

δA‖·(‖X‖+‖δX‖)假设δA足够小，使‖A-1‖·‖δA‖<1，由上式得到

记cond(A)=‖A-1‖·‖A‖为A的条件数，上式变为

cond(A)=‖A-1‖·‖A‖愈大，对扰动解影响愈大，其刻划了方程组的“病态”程度。病态程度是相对的，条件数与所用的范数有关，有时记为

cond(A)p=‖A-1‖p·‖A‖p

考察上例

cond(A)∞=‖A-1‖∞·‖A‖∞=20001×2.0001≈4×104，扰动比较大，因此它是病态的。7.6.2精度分析

求AX=b的一个近似解，希望判断其精度。方法是将

再代回到原方程组去求余量，如果r很小，就认为精确。

若的近似解，余量

，尽管r很小，但与精确解相差很大。说明用余量r来检验近似解对病态方程组是不可靠的。因此有必要研究相对误差。定理7.12

设为AX=b的近似解，AX=b的精确解为X*，

r为的余量，则有

证明由AX=b得到‖b‖=‖AX‖≤‖A‖·‖X‖，故有

(7.12)由得到，故有

(7.13)

由式(7.12)和式(7.13)得到

由得到

(7.14)

由AX*=b得到X*=A-1b，故有‖X*‖=‖A-1b‖≤‖A-1‖·

‖b‖，所以有

(7.15)由式(7.14)和式(7.15)得到

即

所以

需要确定一颗小行星绕太阳运行的轨道，天文学家在轨道平面内建立以太阳为原点的直角坐标系，在两个坐标上取天文测量单位(一天文单位为地球到太阳的平均距离：

1.4959787×1011m)，在5个不同的时间对小行星作了5次观察，测得轨道上5个点的坐标数据，确定小行星轨道，测量数据见下表。7.7实例——小行星轨道问题由开普勒第一定理知，小行星轨道为一椭圆，椭圆的一般方程为

a1x2+2a2xy+a3y2+2a4x+2a5y+1=0

(7.16)把5个坐标代入可得到线性方程组AX=b

解出系数为a1=0.6143，a2=-0.3440，a3=-0.6942，a4=-1.6351，a5=-0.2165。一、填空题

(1)解线性方程组，用雅可比法的迭代格式为：

，

，

=(k=0,1,2,…)；而高斯-塞德尔迭代法迭代格式为：

，

，

(k=0,1,2,…)。习题七

(2)已知，则‖A‖1=

，‖A‖∞=

。

(3)已知X=(3,-1,0,-9)T，则‖X‖1=

，

‖X‖2=

，‖X‖∞=

。

(4)向量X=(x1,x2,x3)T，|x1|+2|x2|+|x3|是不是一种向量范数？(填是或不是)

。

|x1+3x2|+|x3|是不是一种向量范数？(填是或不是)

。二