第九章

求解线性系统的迭代法

9.1向量和矩阵序列的收敛性

在第七章中，我们讨论了求解线性方程组的一些主要方法。这些方法是直接的方法，因为它们产生精确的解（假设无限精确！）.

求解线性系统的另一类方法包括用迭代法近似解。其基本思想是：给定一个线性系统ax=b（在mn（c）中有一个平方可逆矩阵），求另一个矩阵b∈mn（c）和一个向量c∈cn，这样

1。矩阵i-b是可逆的2。系统的唯一解x ax=b与E系统的唯一解u相同。

u=bu+c，

然后从任意向量u0开始计算

UK+1=Buk+C，K∈N。

在某些条件下（即将澄清），序列（UK）收敛到极限Ue，这是u=bu+c的唯一解，因此ax=b。

因此，找到确保上述序列收敛的条件，并利用工具比较这些序列的收敛速度是非常重要的。因此，我们从一些向量和矩阵序列收敛的一般结果开始。

二百九十五

设（e，k）为赋范向量空间。从第8.7节回忆起，向量u k∈e的序列（uk）收敛到极限u∈e，如果对于每个>0，有一些自然数n，这样对于所有k≥n。

我们写信

U=Lim英国。K7→∞

如果e是一个有限维向量空间，dim（e）=n，我们从定理8.5中知道任意两个范数都是等价的，如果我们选择范数k k∞，我们可以看到，向量序列的收敛性uk等于由分量构成的n个标量序列的收敛性。f这些向量（在任何基础上）。同样的性质也适用于m×n矩阵（k=r或k=c）的有限维向量空间mm，n（k），这意味着矩阵序列的收敛性等于m×n标量序列的收敛性（），其中i，j固定（1≤i≤m，1≤j≤n）。

下面的第一个定理给出了矩阵B的幂序列（bk）收敛到零矩阵的一个充要条件。回想一下，矩阵b的光谱半径ρ（b）是b特征值的模λi_的最大值。

定理9.1。对于任何平方矩阵b，以下条件是等效的：

(1) limk7→∞bk=0，

(2) limk7→∞bkv=0，对于所有向量v，

(3) ρ（b）<1，

(4) Kbk<1，对于某些次矩阵范数k k k。

证据。假设（1），k k是e上的向量范数，k是相应的矩阵范数。对于每一个向量v∈e，因为k k是一个矩阵范数，我们有

Kbkvk≤Kbkkkvk，

也就是说，利芒自limk7→∞k7→∞bbkvk=0=0。这证明（1）假设lim k 7→∞kbkk=0，我们得出lim（2）.k→∞7kbkvk=0，

假设（2）。如果ρ（b）≥1，那么会有一些特征向量u（=0）6和一些特征值λ，这样

bu=λu，λ=ρ（b）≥1，

但序列（bku）不会收敛到0，因为bku=λku且λk=λk≥1。由此可见（2）暗示（3）。

假设（3）成立，即ρ（b）<1。通过命题8.12，我们可以找到大于0的足够小的1，以及一个从属矩阵范数k，这样

9.1。向量和矩阵序列的收敛性

即（4）。

最后，假设（4）。因为k k是矩阵范数，

KBkk≤KBkk，

由于Kbk<1，我们推断（1）成立。

研究迭代法的收敛速度需要以下命题。

提案9.2.对于每一个平方矩阵b∈mn（c）和每一个矩阵范数kk，我们有

lim kbkkk1/k=ρ（b）。

K7→∞

证据。我们从命题8.6中知道，ρ（b）≤k b k，并且由于ρ（b）=（ρ（bk））1/k，我们推导出所有k≥1的ρ（b）≤kbkkk，

如此

ρ（b）≤lim kbkkk1/k。

K7→∞

现在让我们证明，对于每个>0，都有一个整数），这样

对所有人来说，

这证明了

lim kbkkk1/k≤ρ（b），

K7→∞

以及我们的建议。

对于任何给定的矩阵

.

因为1，定理9.1意味着lim=0。因此，有一个整数），这样对于所有人来说

，

这意味着，正如所声称的。

我们现在将上述结果应用于迭代方法的收敛性。

9.2迭代法的收敛性

回想一下，求解线性系统a x=b（a∈mn（c）可逆）的迭代方法包括找到一些矩阵b和一些向量c，这样i-b是可逆的，ax=b的唯一解x等于u=bu+c的唯一解u，然后从任意向量开始eu0，计算由

UK+1=Buk+C，K∈N，

并且说迭代法是收敛的iff

klim7→∞UK=U，E

对于每个初始向量u0。

这里是基于矩阵B的任何迭代方法收敛的基本准则，称为迭代方法的矩阵。

定理9.3.如果系统u=bu+c如上所述，其中i−b是可逆的，则以下陈述是等效的：

(1) 迭代法是收敛的。

(2) ρ（b）<1.

(3) Kbk<1，对于某些次矩阵范数k k k。证明。通过以下方式定义矢量Ek（误差矢量）

Ek=英国-U，E

其中u是系统的唯一解u=bu+c。显然，迭代法是

e

收敛iff

Lim Ek=0.K7→∞

我们声称

Ek=BKE0，K≥0，

其中e0=u0−ue。

通过对k的归纳证明了这一点。基本情况k=0是微不足道的。根据诱导假设，Ek=bke0，由于Uk+1=buk+c，我们得到

UK+1−Ue=Buk+C−U，E

由于Ue=bue+c，Ek=bke0（通过诱导假设），我们得到

UK+1−Ue=b uk−Bue=b（UK−Ue=bek=bbke0=bk+1e0，

验证导入步骤。因此，迭代法收敛于iff

lim bke0=0.K7→∞

因此，我们的定理遵循定理9.1。

9.2。迭代法的收敛性

需要下一个命题来比较迭代方法的收敛速度。结果表明，误差向量Ek=bke0的渐近行为最差为（ρ（b））k。

提案9.4.设k k为任意向量范数，设b∈mn（c）为i−b可逆的矩阵，设u为u=bu+c.e的唯一解。

(1) if（uk）是迭代定义的任何序列

然后

.

(2) 假设b1和b2是两个矩阵，使得i−b1和i−b2是可逆的，假设u=b1u+c1和u=b2u+c2都有相同的唯一解ue，并考虑由

UK+1=B1UK+C1

vk+1=b2vk+c2，

U0=v0。如果ρ（b1）<ρ（b2），那么对于任何一个，都有一个整数，这样

对所有人来说，我们有

.

证据。设k k为次矩阵范数。回想一下

UK−Ue=黑色0，

当e0=u0-ue时。对于每一个k∈n，我们有

，

这意味着

，

陈述（1）来自9.2号提案。因为u0=v0，我们有

Uk−Ue=b1ke0 vk−Ue=b2ke0，e0=u0−Ue=v0−Ue。同样，根据命题9.2，对于每大于0，就有一些自然数），然后

此外，还有一个向量e0=e0（k），这样

ke0k=1和，

这意味着陈述（2）。

综上所述，我们发现在研究新的迭代方法时，我们必须处理以下两个问题：

\1. 给出了矩阵B的迭代方法，确定该方法是否收敛。这涉及到确定是ρ（b）<1，还是等效地确定是否存在子矩阵范数，如kbk<1。根据命题8.11，这意味着i−b是可逆的（因为k−b k=k b k，命题8.11适用）。

\2. 给出了两种收敛迭代方法，并进行了比较。迭代法的速度较快，其矩阵的谱半径较小。

我们现在讨论三种求解线性系统的迭代方法：

\1. 雅可比方法

\2. 高斯-赛德尔方法

\3. 放松法。

9.3 Jacobi、Gauss–Seidel和Relaxy方法说明

本节描述的方法是以下方案的实例：给定一个线性系统ax=b，具有可逆性，假设我们可以将a写成

A=m-n，

其中m是可逆的，并且“易于可逆”，这意味着m接近于一个对角线或三角形矩阵（可能是分块的）。那么au=b等于

mu=nu+b，

也就是说，

U=m−1nu+m−1b。

因此，我们处于前面章节描述的情况中，b=m−1n，c=m−1b。事实上，由于a=m−n，我们有

b=m−1n=m−1（m−a）=i−m−1a，（）

这表明i−b=m−1a是可逆的。与矩阵b=m−1n相关的迭代方法由下式给出：

UK+1=m−1nuk+m−1b，k≥0，（†）

从任意向量u0开始。从实际的角度来看，我们不求m，而是迭代求解系统。

muk+1=nuk+b，k≥0。

不同的方法对应于从a中选择m和n的不同方法。前两种方法选择m和n作为a的不相交子矩阵，但松弛方法允许m和n重叠。

为了描述m和n的各种选择，用三个子量d，e，f，as来写a是很方便的。

A=D−E−F，

如果d中的唯一非零项是a中的对角线项，e中的唯一非零项是对角线下a中的项，f中的唯一非零项是对角线上a中的项。更明确地说，如果

 

0 0 0·····−1N−1 0··

γ

0 0 0 0···0安

M = D

N =e+f，

因此（），

b=m−1n=d−1（e+f）=i−d−1a。

作为一个符号，我们让

j=i−d−1a=d−1（e+f）

这就是雅各比矩阵。相应的方法，雅可比迭代法，使用递推计算序列（uk）。

UK+1=D−1（E+F）UK+D−1b，K≥0。

在实践中，我们迭代求解系统

duk+1=（e+f）uk+b，k≥0。

如果我们写），我们迭代地解决以下系统：

A11UK1+1=−A12UK2−A13U3K·····−A1NUKN+B1 A22UK2+1=−A21UK1−A23U3K···−A2NUKN+B2

…………

a n a−nn1n−1ku+1kn+1−1=−a a n−n111uukk1−a····n2uk2−an−1···n−2ukn−2−ann−1ukn−1−an−1nunk++bbnn−1 un

在Matlab中，雅可比迭代的一个步骤是通过以下函数实现的：

函数v=jacobi2（a，b，u）n=size（a，1）；v=zeros（n，1）；

对于i=1:n v（i，1）=u（i，1）+（-a（i，：）*u+b（i））/a（i，i）；

结束

要运行m迭代步骤，请运行以下函数：

函数u=Jacobi（a，b，u0，m）

u=u0；对于j=1:m

u=雅各比2（a，b，u）；结束

结束

例9.1。考虑线性系统

.

我们立即检查解决方案

x1=11，x2=-3，x3=7，x4=-4.

很容易看出雅可比矩阵是

.

经过10次雅可比迭代，我们找到了近似解。

x1=10.2588，x2=-2.5244，x3=5.8008，x4=-3.7061。

经过20次迭代，我们找到了近似解

x1=10.9110，x2=-2.9429，x3=6.8560，x4=-3.9647。

经过50次迭代，我们找到了近似解

x1=10.9998，x2=-2.9999，x3=6.9998，x4=-3.9999，

经过60次迭代，我们找到了近似解

x1=11.0000，x2=-3.0000，x3=7.0000，x4=-4.0000，

最多可更正四位小数。

可以证明（见问题9.6），j的特征值是

，

所以j=b的光谱半径是

.

根据定理9.3，雅可比方法收敛于这个例子的矩阵。

观察到我们可以尝试使用第二个方程的in-solution的新值来“加速”该方法，更一般地说，在第i个方程的uki+1的求解中使用而不是。这一观察结果导致

网络错误
网络错误 网络错误	网络错误 网络错误 网络错误				网络错误 网络错误	网络错误	网络错误
	网络错误 网络错误		网络错误	网络错误

以矩阵形式写的

duk+1=euk+1+fuk+b。

因为d是可逆的，e是下三角的，所以矩阵d-e是可逆的，所以上面的方程等于

Uk+1=（d−e）−1fuk+（d−e）−1b，k≥0。上述对应于选择m和n为

矩阵b由

b=m−1n=（d−e）−1f。

由于m=d−e是可逆的，我们知道i−b=m−1a也是可逆的。

我们刚才描述的方法是高斯-赛德尔迭代法，矩阵B称为高斯-赛德尔矩阵，用l1表示，l1=（d−e）−1f。

高斯-赛德尔方法的一个优点是只需要雅可比方法使用的一半内存，因为我们只需要

计算Uki+1。我们还表明，在某些重要情况下（例如，如果a是三对角矩阵），高斯-赛德尔方法比雅可比方法收敛得更快（在这种情况下，两者同时收敛或发散）。

在matlab中，高斯-赛德尔迭代的一个步骤是通过以下函数实现的：函数u=gaussseidel3（a，b，u）n=size（a，1）；对于i=1:n u（i，1）=u（i，1）+（-a（i，：）*u+b（i））/a（i，i）；结束

值得注意的是，与Jacobi2的唯一区别是，在赋值的两边使用相同的变量u。要运行m迭代步骤，请运行以下函数：

函数u=GausSeidel1（a，b，u0，m）u=u0；对于j=1:m

U=高斯赛德尔3（A，B，U）；结束

结束

例9.2。考虑相同的线性系统

如例9.1所示，其解决方案是

x1=11，x2=-3，x3=7，x4=-4.

经过10次高斯-赛德尔迭代，我们找到了近似解。

x1=10.9966，x2=-3.0044，x3=6.9964，x4=-4.0018。

经过20次迭代，我们找到了近似解

x1=11.0000，x2=-3.0001，x3=6.9999，x4=-4.0000。

经过25次迭代，我们找到了近似解

x1=11.0000，x2=-3.0000，x3=7.0000，x4=-4.0000，

最多可更正四位小数。我们观察到在这个例子中，高斯-赛德尔方法的收敛速度大约是雅可比方法的两倍。命题9.8将表明，对于三对角矩阵，高斯-赛德尔矩阵l1的光谱半径由下式给出：

ρ（l1）=（ρ（j））2，

所以我们的观察和理论是一致的。

松弛法的新成分是将矩阵d的一部分并入n中：我们用

式中，ω=06是需要适当选择的实际参数。实际上，我们在第9.4节中表明，要使松弛方法收敛，我们必须有ω∈（0,2）。注意，情况ω=1对应于高斯-赛德尔方法。

如果我们假设d的所有对角线项都不为零，那么矩阵m是可逆的。矩阵b用lω表示，称为松弛矩阵，用

.

这个数ω称为松弛参数。

当ω>1时，松弛法称为连续过松弛，简称SOR。

乍一看，松弛矩阵lω似乎比高斯-赛德尔矩阵l1复杂得多，但与松弛方法相关的迭代系统与高斯-赛德尔方法非常相似，并且非常简单。实际上，与弛豫方法相关联的系统由下式给出：

相当于

（d-ωe）uk+1=（1-ω）d+ωf）uk+ωb，

而且可以写

duk+1=duk−ω（duk−euk+1−fuk−b）。

明确地说，这就是系统

A11UK1+1=A11UK1−ω（A11UK1+A12UK2+A13U3K+····+A1N−2UKN−2+A1N−1UNK−1+A1UNK−B1）A22UK2+1=A22UK2−ω（A21UK1+1+A22UK2+A23UK3+····+A2N−2UKN−2+A2N−1UNK−1+A2UNK−B2）

…

annukn+1=annukn−ω（an11uk+1+an2uk2+1+·····+ann−2ukn+1−2+ann−1unk+1−1+annukn−bn）。

在matlab中，松弛迭代的一个步骤是通过以下函数实现的：

函数u=relax3（a，b，u，omega）n=size（a，1）；对于i=1:n u（i，1）=u（i，1）+omega（-a（i，：）u+b（i））/a（i，i）；结束

观察到函数relax3是通过在表达式（−a（i，：）u+b（i））/a（i，i）前面插入ω从函数gausseidel3获得的。要运行m迭代步骤，请运行以下函数：

函数u=松弛（a，b，u0，omega，m）u=u0；对于j=1:m

u=松弛3（a，b，u，omega）；结束

结束

例9.3。考虑与实施例9.1和9.2中相同的线性系统，其解为

x1=11，x2=-3，x3=7，x4=-4.

在ω=1.1的10次松弛迭代后，我们得到了近似解。

x1=11.0026，x2=-2.9968，x3=7.0024，x4=-3.9989。

经过10次ω=1.2的迭代，我们得到了近似解。

x1=11.0014，x2=-2.9985，x3=7.0010，x4=-3.9996。

经过10次ω=1.3的迭代，我们得到了近似解。

x1=10.9996，x2=-3.0001，x3=6.9999，x4=-4.0000.

经过10次ω=1.27的迭代，我们得到了近似解。

x1=11.0000，x2=-3.0000，x3=7.0000，x4=-4.0000，

最多可更正四位小数。我们观察到在这个例子中，ω=1.27的松弛方法比高斯-赛德尔方法收敛得更快。这一观察结果将由提案9.10予以确认。

需要做的是找到确保松弛法（和高斯-赛德尔法）收敛的条件，即：

\1. 求ω的条件，即区间i r，使ω∈i表示ρ（lω）<1；证明ω∈（0,2）是一个必要条件。

\2. 找出ω∈i是否存在某个最优值ω0，以便

ρ（lω0）=infρ（lω）。ωi

我们将在下一节中部分回答上述问题。

也可以通过使用A=D−E−F形式的块分解来扩展本节的方法，其中D、E和F由块组成，D是可逆的块对角矩阵。见图9.1。

图9.1：块分解的示意图a=d−e−f，其中d=4i=1di，e=3i=1ei，f=3i=1fi。

9.4高斯-赛德尔方法和松弛方法的收敛性

我们从与（复）厄米特正定矩阵（a=m−n）相关的迭代方法的收敛性的一般准则开始，然后将此结果应用于松弛方法。

提案9.5。设A为任意厄米特正定矩阵，写为

A=m-n，

其中m是可逆的。那么m+n是厄米提安，如果它是正定的，那么

ρ（m−1n）<1，

使迭代法收敛。

9.4。方法的收敛性

证据。因为m=a+n，a是厄米提安，a=a，所以我们得到

M+N=A+N+N=A+N+N=M+N=（M+N），

这表明M+N确实是赫米特人。因为a是厄米特正定的，函数

V 7→（V AV）1/2

从cn到r是一个向量范数k k，让k k也表示它的从属矩阵范数。我们证明了

km−1nk<1，

定理9.1证明了ρ（m−1n）<1。按定义

，

这导致我们评估kmwv−，ma−1=avak，whenakv=km=1−。如果我们写，我们有w=m−1a v，利用kvk=1，v=a−1的事实。

kv−wk2==（kvk−2 W）v a a w（v−−ww）av+w aw

-

=1−w m w mw+w aw=1−w（m+n）w。

既然我们假设m+n是正定的，如果w 6=0，那么w（m+n）w>0，我们得出结论

如果kvk=1，则kv−m−1avk<1。

最后，函数

V 7→kV−m−1avk

作为连续函数的一个组成部分，它是连续的，因此它在紧子集v∈cn kvk=1上达到最大值，这证明了

，

并完成证明。

现在，和前面的部分一样，我们假设a写为a=d−e−f，d可逆，可能是块形式。下一个定理提供了松弛方法收敛（因此，高斯-赛德尔方法收敛）的充分条件（这也是必要的）。这个定理被称为奥斯托夫斯基-赖希定理。

定理9.6。如果a=d−e−f是厄米特正定的，如果0<ω<2，则松弛法收敛。这也适用于证明的块分解。回想一下，对于松弛法，a=m-n

因为d=d，e=f（因为a是厄米提安的），ω=06是真的，我们有

如果d由a的对角项组成，那么从7.8节我们知道这些项都是正的，并且由于ω∈（0,2），我们看到矩阵（（2−ω）/ω）d是正定的。如果d由a的对角块组成，因为a是正的、确定的，通过选择向量z，通过为d的每一块选择一个非零向量并填充零，我们可以看到d的每一块都是正的，因此d本身是正的。因此，在所有情况下，m+n都是肯定的，我们用命题9.5得出结论。

备注：如果我们允许参数ω为非零复数ω∈c，怎么办？在这种情况下，我们

但是，

，

因此松弛法也收敛于

|ω−1<1.

如果ω为实，则此条件减小到0<ω<2。

不幸的是，定理9.6不适用于雅可比方法，但在特殊情况下，可以用命题9.5证明其收敛性。在正的一面，如果矩阵严格地是对角占优的列（行），那么可以证明雅可比方法和高斯-赛德尔方法都是收敛的。当ω∈（0,1）时，松弛法也收敛，但这不是一个非常有用的结果，因为ω>1的收敛速度通常会加快。

我们现在证明，除了a和d是可逆的之外，在没有假设a=d−e−f的情况下，为了使松弛方法收敛，我们必须有ω∈（0,2）。

9.5。三对角矩阵的收敛方法

提案9.7.给定任意矩阵a=d−e−f，且a和d可逆，对于任何ω=06，我们得到

ρ（lω）≥ω−1，

哪里。因此，松弛法（可能是分块）

除非ω∈（0,2），否则不收敛。如果我们允许ω是复数，那么我们必须

|ω−1<1

使松弛法收敛。

证据。观察Lω特征值的积λ1···········λn等于Det（Lω），由下式得出：

.

由此得出ρ（lω）≥λ1········································

如果ω∈c，证明是相同的。

9.5三对角矩阵的雅可比方法、高斯-赛德尔方法和松弛方法的收敛性

我们现在考虑的情况是，A是一个三对角矩阵，可能是按块划分的。在这种情况下，我们得到了关于j和lω谱半径的精确结果，从而得到了这些方法的收敛性。我们还得到了一些关于这些方法收敛速度的信息。我们从ω=1开始，这在技术上更容易处理。下面的命题给出了雅可比矩阵和高斯-赛德尔矩阵的光谱半径ρ（j）和ρ（l1）之间的精确关系。

提案9.8.设A为三对角矩阵（可能按块）。如果ρ（j）是雅可比矩阵的谱半径，而ρ（l1）是高斯-赛德尔矩阵的谱半径，那么我们得到ρ（l1）=（ρ（j））2。

因此，雅可比方法和高斯-赛德尔方法都是同时收敛或同时发散的（即使当a是由块构成的三对角线）；当它们收敛时，高斯-赛德尔方法比雅可比方法收敛得更快。

证据。我们从一个初步的结果开始。让一个（礹）具有一个三对角矩阵的分块形式

Det（A（μ））=Det（A（1）），μ=06。为了证明这一事实，形成块对角矩阵

p（μ）=diag（μi1，μ2i2，…，μpip）

其中，ij是与AJ块具有相同维度的单位矩阵。那么很容易看出

A（μ）=P（μ）A（1）P（μ）−1，

因此，Det（A（μ））=Det（P（μ）A（1）P（μ）−1）=Det（A（1））。

由于雅可比矩阵是j=d−1（e+f），j的特征值是特征多项式的零。

Pj（λ）=det（λi−d−1（e+f）），

因此，它们也是多项式的零

qj（λ）=det（λd−e−f）=det（d）pj（λ）。

同样，由于高斯-赛德尔矩阵是l1=（d−e）−1f，特征多项式的零点

pl1（λ）=det（λi−（d−e）−1f）

也是多项式的零

ql1（λ）=det（λd−λe−f）=det（d−e）pl1（λ）。

由于a=d−e−f是三对角（或按块划分的三对角），因此λ2d−λ2e−f也是三对角（或按块划分的三对角），并且通过使用我们对μ=λ=06的初步结果，我们得到

ql1（λ2）=det（λ2d−λ2e−f）=det（λ2d−λe−λf）=λnqj（λ）。

通过连续性，上述方程也适用于λ=0。但我们推断：

\1. 对于任何β=06，如果β是l1的特征值，那么β1/2和−β1/2都是j的特征值，其中β1/2是β的复平方根之一。

9.5。三对角矩阵的收敛方法

\2. 对于任何α=06，如果α和−α都是j的特征值，那么α2是l1的特征值。

上面立即暗示了ρ（l1）=（ρ（j））2。

现在我们考虑更一般的情况，其中ω是（0,2）中的任何实数。

提案9.9.假设A是一个三对角矩阵（可能是分块的），并假设雅可比矩阵的特征值都是实的。如果ω∈（0,2），那么雅可比方法和松弛方法都会同时收敛或同时发散（即使当a为三对角块时）。当它们收敛时，函数ω7→ρ（lω）（对于ω∈（0,2））的唯一最小值等于ω0−1

，

其中1<ω0<2，如果ρ（j）>0。我们还有ρ（l1）=（ρ（j））2，如前所述。

证据。这是一个非常技术性的证明，可以在serre[151]和ciarlet[41]中找到。在前面的命题的证明中，我们首先证明矩阵lω的特征值是多项式的零。

，

式中，plω（λ）是lω的特征多项式。然后利用9.8号提案的初步事实，很容易证明

，

对于所有的λ∈c，λ=06。这一次我们不能把上述方程推广到λ=0。这导致我们考虑这个方程

相当于

λ2−αωλ+ω−1=0，

对于所有λ=06。自λ=06以来，上述等价性不适用于ω=1，但这不是问题，因为在前面的命题中已经考虑了ω=1的情况。然后我们可以展示以下内容：

\1. 对于任何β=06，如果β是lω的特征值，那么

是j的特征值。

\2. 对于每个α=06，如果α和−α是j的特征值，那么μ+（α，ω）和μ−（α，ω）是lω的特征值，其中μ+（α，ω）和μ−（α，ω）是方程λ2−αωλ+ω−1=0根的平方。

接下来是

ρ（lω）=maxj max（+（α，ω），−（α，ω），

λp（λ）=0

既然我们假设j有实根，我们就可以研究它的函数。

m（α，ω）=max（α，ω），（α，ω），

其中α∈R和ω∈（0,2）。实际上，因为m（−α，ω）=m（α，ω），只需要考虑α≥0的情况。

注意，对于α=06，方程式的根

是

.

反过来，这会导致考虑方程式的根。

，

哪些是

α=06。既然我们有

和

，

这些根是

.

−−−

注意ω0（α）的表达式正是我们命题中的表达式！其余的证明包括通过考虑α的各种情况来分析函数m（α，ω）的变化。最后，我们发现ω0（ρ（j））得到了ρ（lω）的最小值。细节很冗长，我们省略了。读者将在Serre[151]和Ciarlet[41]中找到完整的证据。

9.6。总结

结合定理9.6和9.9的结果，我们得到了下面的结果，给出了矩阵j、l1和lω的光谱半径的精确信息。

提案9.10。设A是一个三对角矩阵（可能是分块的），它是厄米特正定的。然后，雅可比方法、高斯-赛德尔方法和松弛方法都收敛于ω∈（0,2）。有一个独特的最佳松弛参数

，

这样的话

ρ（lω0）=infρ（lω）=ω0−1。

0＜ω＜2

此外，如果ρ（j）>0，则

ρ（lω0）<ρ（l1）=（ρ（j））2<ρ（j），

如果ρ（j）=0，那么ω0=1，ρ（l1）=ρ（j）=0。

证据。为了应用9.9号命题，我们必须检查j=d−1（e+f）是否具有实特征值。但是，如果α是j的任何特征值，如果u是任何对应的特征向量，那么

d−1（e+f）u=αu

意味着

（e+f）u=αdu，

由于a=d−e−f，上述结果表明（d−a）u=αdu，即，

au=（1−α）du.

因此，u au=（1−α）u du，

由于a和d是厄米特正定的，当u=06时，我们得到u au>0和u du>0，这证明了αr，其余的都符合定理9.6和9.9。

注：当最佳松弛参数未知时，最好高估而不是低估松弛参数。

9.6总结

本章的主要概念和结果如下：

• 迭代法。将a拆分为a=m−n。

• 向量或矩阵序列的收敛性。

• 矩阵b的幂次收敛到零的一个准则（以谱半径ρ（b）.bk为单位）

• 光谱半径ρ（b）作为序列极限（Kbkkk1/k）的特征。

• 迭代法收敛的一个准则。

• 迭代方法的渐近行为。

• 分裂（和索拉）。作为a=d−e−f，以及雅可比、高斯-赛德尔和松弛的方法

• 雅可比矩阵，j=d−1（e+f）。

• 高斯-赛德尔矩阵，l1=（d−e）−1f。

• 松弛矩阵，lω=（d−ωe）−1（（1−ω）d+ωf）。

• 正定迭代法的收敛性：当a=m−n为Hermitian时的一般结果

• 雅可比方法、高斯-赛德尔方法和松弛方法收敛的一个充分条件。奥斯托夫斯基-赖希定理：a是厄米特正定，ω∈（0,2）。

• 雅可比方法、高斯-赛德尔方法和松弛方法收敛的一个必要条件：ω∈（0,2）。

• 三对角矩阵的情况（可能是按块）。Jacobi方法和Gauss-Seidel方法同时收敛或发散，并比较了ρ（j）和ρ（l1）：ρ（l1）=（ρ（j））2的光谱半径。

• 三对角厄米正定矩阵的情况（可能是分块的）。雅各比、高斯-塞德尔和放松的主题方法都在汇聚。

• 在上述情况下，有一个唯一的最佳松弛参数，其中（l1）=（ρ（j））2<ρ（j）（如果ρ（j）=0）.6ρ（lω0）<

9.7问题

问题9.1。考虑矩阵

.

9.7。问题

证明ρ（j）=0和ρ（l1）=2，所以

ρ（j）<1<ρ（l1），

其中j是雅各比矩阵，l1是高斯-赛德尔矩阵。

问题9.2。考虑矩阵

.

证明ρ（j）=√5/2和ρ（l1）=1/2，所以

ρ（l1）<ρ（j），

其中j是雅各比矩阵，l1是高斯-赛德尔矩阵。

问题9.3。考虑以下线性系统：

.

(1) 用高斯消去法求解上述系统。

(2) 利用Jacobi、Gauss–Seidel的方法计算向量10的序列，并松弛ω：ω=1.1,1.2，…，1.9的以下值。在所有情况下，初始向量都是u0=（0,0,0,0）。

问题9.4。回想一下，复数或实数n×n矩阵a严格地是行对角占优的if。

(1) 证明了如果a是严格的行对角占优，则雅可比方法收敛。

(2) 证明了如果A是严格的行对角占优，则高斯-赛德尔方法收敛。

问题9.5。证明9.5号命题的逆命题成立。也就是说，如果a是一个厄米正定矩阵，写为a=m−n，m可逆，如果厄米坦矩阵m+n是正定的，如果ρ（m−1n）<1，则a是正定的。

问题9.6.考虑以下三对角n×n矩阵：

.

（1）证明雅可比矩阵j的特征值由

暗示。首先证明雅可比矩阵是

.

那么j的特征值和特征向量就是方程组的解。

Y0＝0

yk+1+yk−1=2λyk，k=1，…，n yn+1=0。

众所周知，上述复发的一般解决方案如下：

，

（α，β=0）6，其中z1和z2是方程的零。

z2−2λz+1=0.

因此，z2=z1−1和z1+z2=2λ。边界条件y0=0生成α+β=0，所以），边界条件yn+1=0生成

.

我们可以假设z1的n个可能值（z1）k由下式给出：

找到

2λk=（z1）k+（z1）−k 1.

证明与特征值λk相关联的特征向量（）由下式给出：

（2）求谱半径ρ（j）、ρ（l1）和ρ（lω0），作为h=1/（n+1）的函数。