解线性方程组的迭代法收敛速度

k
lim Ak 0 .
k
(2.27)
由定理 2.5 知，
( A k ) Ak ，
即
( A)
由(2.27) 和(2.28)可得
k
Ak .
(2.28)
lim ( A) 0
k k
再由矩阵谱半径的定义可知一定有 ( A) 1 . （必要性） 若 ( A) 1 ，则有定理 2.5 的推论可知至少存在一个 0 使得一种范数
若有
lim x ( k ) x* , 即 lim xi( k ) xi* ,
k k
则有 lim x ( k ) x*
k 2
0.
常见的向量范数有： ① 1-范数
x 1 xi ；
i 1
n
② ∞-范数
x

max xi ；
1 i n
③ 2-范数
x 2 ( x ) ；
lim x x* lim G k x x* 0 ，
k
0
k


k


再由向量范数的定义可知
lim x k x* 0 ，
k
即迭代过程收敛. （必要性） 若迭代公式(2.20)收敛，即满足
lim x x* 0
k k


由此推论可知当 ( A) 1 时，至少存在一种范数 A 1 .
定 理 2.6 设 A R nn ， 则 lim Ak 0 的 充 要 条 件 为 ( A) 1 . （ 其 中
k
Ak AA A）
k
证明： （充分性） 若 lim Ak 0 ，则由矩阵范数的定义可知

第二章解线性代数方程组的迭代法2. 1 引言在许多实际问题中，常常需要求解这样的线性代数方程组，它的系数矩阵数很高，但非零元素很少，人们称其为大型稀疏线性代数方程组，对于这类方程组，如果它乂不具有带状性，那么，再用直接法求解就不太有效，因为用直接法进行消元或矩阵的三角分解时，没有考虑到系数矩阵的稀疏性，破坏了系数矩阵的形状，导致了计算量的增加和存储单元的浪费，于是，人们常用迭代法求解大型稀疏线性代数方程组。

迭代法只需要存储系数矩阵的非零元素，这样，占用内存在单元较少，能解高阶线性代数方程组。

山于迭代法是通过逐次迭代来逼近方程组的解，因此，收敛性和收敛速度是构造迭代法时要注意的问题。

那么，是否可以构造一种适用于一般情况的迭代法呢？回答是否定的，这是因为不同的系数矩阵具有不同的性态，一般地，每一种迭代法都具有一定的适用范围，在本章的学习中将会看到，有时，某种方法对一类方程组迭代收敛，而对另一类方程组进行迭代时就会发散。

因此，我们应该学会针对具有不同性质的线性代数方程组，构造合适的迭代方法。

本章主要介绍一些基本的迭代法，并在一定的范围内讨论其中儿种方法的收敛法。

2. 2 基本迭代法考虑线性方程组如坷+如勺+…+气兀”二勺a2t x i+a22x2 + - + a2…x n =b2■•••••••••••(2. 1)采用矩阵和向量记号，我们可以把(2.1)式写成Ax = h(2.2)其中，为非奇异矩阵，设下面我们介绍雅可比(Jacobi)迭代，高斯-塞德尔(Gauss-Seidel)迭代与S0R迭代以及SS0R迭代的基本思想和算法。

为了方便地给出矩阵表示式，我们引进下列矩阵分裂：4SD-U,(2.3)其中-a2\-a n\(1)雅可比迭代的基本思想从式(2.1)的第i个方程中解出X t=(/ = 1,2,•••,«)我们把迭代前面的值代入上式右边，山计算得到等式左边的值作为一次迭代的新值，然后再把这个新值代入右边，再从左边得到一个新值，如此反复，就得到了雅可比迭代公式。

Gauss-Seidel迭代法是一种用于求解线性方程组的迭代算法，该算法在科学计算和工程领域被广泛应用。

在使用该算法时，我们需要考虑其收敛性，以确保结果的准确性和可靠性。

下面我们将介绍Gauss-Seidel迭代法收敛判断的相关内容。

1. 收敛性定义在使用迭代法求解线性方程组时，迭代算法的收敛性是一个非常重要的问题。

一个迭代算法如果能够在有限步内得到一个接近于真实解的近似解，就称为收敛。

否则，如果迭代算法无法收敛或者收敛速度非常慢，就需要考虑改进算法或者选择其他更适合的算法。

2. Gauss-Seidel迭代法Gauss-Seidel迭代法是一种逐次逼近法，它通过不断地逼近线性方程组的解来求得近似解。

这种迭代算法的优点是简单易行，适用于各种情况。

然而，它的收敛性需要进行严格的判断。

3. 收敛条件对于Gauss-Seidel迭代法，我们可以使用以下收敛条件来进行判断：a) 对角占优条件：如果线性方程组的系数矩阵是严格对角占优的，那么Gauss-Seidel迭代法一定收敛。

b) 正定条件：如果线性方程组的系数矩阵是正定的，即所有的特征值都是正的，那么Gauss-Seidel迭代法也一定收敛。

c) 非奇异条件：如果线性方程组的系数矩阵是非奇异的，即行列式不为0，那么Gauss-Seidel迭代法也一定收敛。

4. 不收敛的情况尽管Gauss-Seidel迭代法在很多情况下能够收敛，但也存在一些情况下它不收敛的情况。

当线性方程组的系数矩阵不满足对角占优条件、正定条件或者非奇异条件时，Gauss-Seidel迭代法就可能不收敛。

此时，我们需要考虑改进算法或者选择其他更适合的迭代算法。

5. 收敛速度除了考虑Gauss-Seidel迭代法的收敛性外，还需要关注其收敛速度。

一般来说，Gauss-Seidel迭代法的收敛速度相对较快，特别是在满足对角占优条件、正定条件或非奇异条件的情况下。

然而，如果在实际使用中发现收敛速度较慢，也可以考虑使用加速方法如SOR方法等来提高收敛速度。

x(k) x q x(k) x(k1) 1q
x(k) x qk x(1) x(0) 1q
证 因 (B)||B||=q<1, 所以迭代格式收敛, 且有 设 lim x (k) =x*，由 x(k+1) = Bx(k) + f ， 得 x* = Bx* + f ，则
数学学院 信息与计算科学系
又 || Bk|| ||B||k ，有 lim||Bk||=0 ， 故 lim B k =0，由1）知，迭代格式收敛。
数学学院 信息与计算科学系
三、迭代法的收敛速度
考察误差向量
e(k) =x(k) -x＊=Bk ·e(0)
设B有n个线性无关的特征向量及相应的特征值为
1 ,2 , ,n ,
1 , 2 , , n
数学学院 信息与计算科学系
2） 由1)知，迭代格式收敛 lim Bk=O ， 即lim||Bk||=0 ，从而存在 k ，使 || B k || <1，由谱半径 的性质有
[( B )]k = (B k ) ||B k ||<1，
故得
( B )<1，
因(B)=inf{||B||}且(B)<1，存在 >0及使 || B || ( B )+ <1，
取对数得 定义3 称
k s ln10
ln (B)
R(B) ln (B)
为迭代法 x(k+1) = Bx(k) + f 的收敛速度。 由此看出，当(B)<1愈小，速度R(B)就愈大，
所需要的迭代次数也就愈少。
数学学院 信息与计算科学系
定理 2 若 ||B||=q<1，则对任意x(0) 迭代格式 x(k+1) = Bx(k) + f 收敛 ，且有误差估计式