线性方程组迭代解法平均收敛速度收敛阶的定量估计

刘宇民

(太原师范学院数学系，山西太原030012)

在自然科学和工程技术中,很多问题的解决常常归结为求解线性代数方程组,迭代法就是用某种极限过程去逼近线性方程组精确解的方法,该方法具有对计算机的存贮单元需求少,程序计算简单,原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法。常用的迭代法有Jacobi迭代法、Gauss-seidel迭代法等。

1 迭代法原理和性质

1.1 Jacobi迭代原理

设有方程组

其中，A∈Rn×n，x，b∈Rn。

A为非奇异矩阵,可分裂为A＝D－L－U,其中:

将式(1)用矩阵形式表示为

令

由此可构造迭代公式:

故迭代公式的形式为

这种方法称为Jacobi迭代法,其中BJ称为Jacobi迭代矩阵。

1.2 Gauss-Seidel迭代原理[1]

对式(1)中的系数矩阵A分裂为A＝D－L－U,其中D，L，U与式(2)相同。

将式(1)可写成矩阵形式Dx＝b＋Lx＋Ux，进而（D－L）x＝b＋Ux,若设（D－L）－1存在,则

其中,BG＝（D－L）－1U,f＝（D－L）－1b，于是 Gauss-Seidel迭代公式的矩阵形式为

BG称为式(1)的Gauss-Seidel迭代法的迭代矩阵。

通过实例分析,我们可以得出:由于Gauss－Seidel迭代充分利用了迭代过程的新信息,一般来说,它的迭代效果要比Jacobi迭代好[1],当然也有例外的情形。文中讨论Gauss－Seidel和Jacobi迭代法的平均收敛速度与渐进收敛速度的关系。

1.3 这两种迭代方法收敛性与Bk→0是否成立有关，且敛速与Bk→0的速度有关[1]

当 ρ（B）＜1 时,Bk趋于零矩阵的速度有赖于 ρ（B）的大小:一般说来,ρ（B）愈小,则Bk趋于零矩阵的愈快,反之就愈慢。通常,当 ρ(B)＜1时,可以用正数－1nρ(B)的大小作为迭代法渐进收敛速度的度量。这时ρ（B）愈小,迭代法的收敛速度愈大。

1.4 平均收敛速度与渐进收敛速度之间的联系

对于收敛的迭代法xk＋1＝Bxk＋f（k＝0，1，2，…）,Rk＝－ln（‖Bk‖1/k） 称为平均收敛速度(它与所用的范数以及 k 有关);R∞＝－lnρ（B）称为渐进收敛速度。……