解线性代数方程组的迭代法

第二章解线性代数方程组的迭代法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,•••,«)我们把迭代前面的值代入上式右边，山计算得到等式左边的值作为一次迭代的新值，然后再把这个新值代入右边，再从左边得到一个新值，如此反复，就得到了雅可比迭代公式。

线性方程组的迭代式求解方法迭代法解方程的基本原理1.概述把 Ax=b 改写成 x=Bx+f ，如果这一迭代格式收敛，对这个式子不断迭代计算就可以得到方程组的解。

道理很简单：对 x^{(k+1)}=bx^{(k)}+f 两边取极限，显然如果收敛，则最终得到的解满足 \lim_{k\rightarrow\infty } x^{(k)}=x^*=Bx^*+f ，从而必然满足原方程 Ax^*=b 。

迭代方法的本质在于这一次的输出可以当作下一次的输入，从而能够实现循环往复的求解，方法收敛时，计算次数越多越接近真实值。

2.收敛条件充要条件：迭代格式 x=Bx+f 收敛的充要条件是 \rho (B)<1充分条件： \Vert B\Vert <1即 \Vert B\Vert <1 \Rightarrow \rho(B)<1\Leftrightarrow 迭代收敛一、Jacobi迭代法怎样改写Ax=b ，从而进行迭代求解呢？一种最简单的迭代方法就是把第i行的 x_i 分离出来(假定 a_{ii} \ne 0 )：\sum_{j=1}^{n}a_{ij}x_j=b_i\Rightarrow x_i=\frac{b_i-\sum_{j=1,j\ne i}^{n}a_{ij}x_j}{a_{ii}}\quad \\这就是Jacobi(雅可比)迭代法。

迭代格式给定x^{(0)}=\left[x_1^{(0)},x_2^{(0)},\cdots,x_n^{(0)}\rig ht]^T ，则Jacobi法的迭代格式（也称分量形式）为x_i^{(k+1)}=\frac{1}{a_{ii}}\left ( {b_i-\sum_{j=1,j\ne i}^{n}a_{ij}x_j^{(k)}}\right),\quadi=1,2,\cdots,n\\矩阵形式设 A=D-L-U。

Jacobi法的矩阵形式（也称向量形式）为x^{(k+1)}=B_Jx^{(k)}+D^{-1}b\\其中迭代矩阵 B_J=D^{-1}(L+U)收敛条件\begin{eqnarray} \left. \begin{array}{lll} \VertB_J\Vert <1 \\ A 严格对角占优\\ A, 2D-A对称正定\end{array} \right \} \end{eqnarray} \Rightarrow \rho (B_J)<1\Leftrightarrow 迭代收敛特别地，若 A 对称正定且为三对角，则 \rho^2(B_J)=\rho (B_G)<1 。

第五章 解线性代数方程组的迭代法迭代法是解线性代数方程组的另一类重要方法，特别适于求解系数矩阵为稀疏阵的大型线性代数方程组．它的基本思想是，从任一初始向量(0)X出发，按某一规则，逐次构造一个向量序列(){}k X ，当()k X 收敛于*X ，使*X 是所给方程组的解．于是，就有下列问题需要讨论：（１）构造迭代格式 （２）收敛性及误差估计本章将介绍几种实用的迭代法，并讨论其收敛条件．§１ Jacobi 迭代法１.１迭代格式的构造设所给方程组为X BX F =+ (1.1)其中，B 是n 阶方阵，F 是已知向量，X 是未知向量．任取(0)n X R ∈，代入(1.1)的右端，算得的结果记为(1)X ，再以(1)X 代入(1.1)的右端，算得的结果记为(2)X，如此进行下去，便得到迭代格式(1)(),0,1,,k k X BX F k +=+= (1.2)此格式称为Jacobi 迭代法，称B 为迭代矩阵．显然，若()*lim k x XX →∞=存在，则有 **X BX F =+(1.3)即*X 为(1.1)的解．注：若方程组由下面形式给出AX b = (1.4)则需要把它改写成便于迭代的形式(1.1)，其方法是多种多样的，最一般的方法是将A 分解为两个矩阵之差A M N =-，(1.5)其中矩阵M 可逆，于是(1.4)成为11X M NX M b --=+(1.6)令1B M N -=，1F M b -=，即得(1.1)．必须指出，(1.5)中的M 应是便于求逆的，M 的最简单选择是把它选为对角阵，通常，当A 的对角元素全不为零时，就把M 选为A 的对角线，于是A D E =-其中D 是具有A 的对角元素的对角阵，而E 在对角线上的元素为零．此时关系式(1.6)成为11X D EX D b --=+式中，1D -是简单的对角阵，它的对角元素是D 的元素的倒数．１.２ Jacobi 迭代法若由迭代法(1.2)所构成的向量序列(){}k X 收敛，则称迭代格式(1.2)收敛，或称Jacobi 迭代法收敛．以(1.2)式减去(1.3)式得(1)*()*()k k X X B X X +-=-2(1)*()k B X X -=- (1)(0)*()k B X X +=-所以，为使()*k X X =（当k →∞时），必要而且只要0k B →，而0kB →（k →∞）的充要条件是矩阵B 的谱半径()1B ρ<．故有定理１ 对任意右端向量F 和初始向量(0)X ，迭代格式(1.2)收敛于(1.1)的解*X 的充要条件是()1B ρ<．由定理１可以看出，迭代是否收敛只与迭代矩阵的谱半径有关，而迭代矩阵B 是由系数矩阵A 演变过来的，所以迭代是否收敛是与系数矩阵A 以及演变的方式有关，与右端向量和初始向量的选择无关．在具体问题中，谱半径是很难计算的，但由于() ||||B B ρ≤，所以可以用||||B 来作为()B ρ的一种估计．当||||1B <时迭代格式一定收敛，不过这只是收敛的充分条件．定理２ 若||||1B <，则迭代格式(1.2)收敛于(1.1)的解*X ，且有误差估计 ()*()(1)||||||||||||1||||k k k B X X X X B --≤--(1.7)或()*(1)(0)||||||||||||1||||kk B X X X X B -≤--(1.8) 证明 因为() ||||1B B ρ≤<，所以迭代格式(1.2)收敛．其次，由关系式()*(1)*()k k X X B X X --=-有()*(1)*|||| ||||||||k k X X B X X --≤⋅-()()* |||| (||||||||)k k B X X X X ≤⋅-+-（k-1） ()()* ||||||||||||||||)k k B X X B X X ≤⋅-+⋅-（k-1）从而有()*()(1)||||(1||||) ||||||||k k k X X B B X X ---≤⋅-因此(1.7)式成立．又从(1.2)式有()(1)(1)(2)1(1)(0)()()k k k k k X X B X X B X X -----=-==-,所以()(1)1(1)(0)|||| ||||||||k k k X X B X X ---≤-．将此式代入(1.7)中，便得到(1.8)式．定理２证完．依定理２可知，当11||||max ||1nij ji B b ==<∑或 1||||max||1nijij B b∞==<∑时，Jacobi 迭代法收敛．除了用定理１、定理2来判别迭代法的收敛性外，还可根据方程组系数矩阵的特点给出一些收敛性的判别条件。

线性方程组求解的迭代算法线性方程组是数学中常见的问题之一，求解线性方程组是很多科学和工程领域中必需的基本任务。

而迭代算法是一种常见的求解线性方程组的方法之一，通过不断逼近线性方程组的解来达到求解的目的。

本文将介绍一些常见的线性方程组迭代算法及其原理。

一、雅可比迭代法雅可比迭代法是最早被提出的线性方程组迭代算法之一。

其思想是通过不断迭代，在每一步都利用先前求得的近似解来逼近方程组的解。

具体算法如下：假设给定的线性方程组为Ax=b，其中A为系数矩阵，b为常数向量，x为未知向量。

1. 首先，将方程组转化为x=D^-1(b-Rx)，其中D为一个对角矩阵，R为矩阵A的剩余部分。

2. 设定一个初始解向量x0。

3. 迭代计算：重复执行以下步骤，直到满足终止条件。

a. 计算下一次迭代的解向量：x_k+1 = D^-1(b-Rx_k)，其中k为当前迭代的次数。

b. 检查终止条件是否被满足，如果是，则停止迭代；否则，返回步骤a。

雅可比迭代法的收敛性与系数矩阵A的特征值有关。

当A是严格对角占优矩阵时，迭代法收敛。

二、高斯-赛德尔迭代法高斯-赛德尔迭代法是雅可比迭代法的一种改进方法。

在每一次迭代中，新的解向量x_k+1的计算会利用到之前已经计算得到的近似解向量的信息，从而加快迭代的速度。

具体算法如下：1. 设定一个初始解向量x0。

2. 迭代计算：重复执行以下步骤，直到满足终止条件。

a. 对于每个方程i，计算下一次迭代的解向量的每个分量：x_k+1[i] = (1/A[i][i]) * (b[i]-Σ(A[i][j]*x_k[j]，其中j为1到i-1之间的所有整数。

b. 检查终止条件是否被满足，如果是，则停止迭代；否则，返回步骤a。

高斯-赛德尔迭代法相比于雅可比迭代法，在每一次迭代中都会利用到之前计算得到的近似解向量的信息，因此收敛速度更快。

三、超松弛迭代法超松弛迭代法是对雅可比迭代法和高斯-赛德尔迭代法的进一步改进。

通过引入松弛因子ω，可以加速迭代的收敛速度。