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

计算方法3_线性方程组迭代解法线性方程组的迭代解法是解决线性方程组的一种常见方法，常用于大规模的线性方程组求解。

该方法通过不断迭代更新解的近似值，直到满足一定的收敛准则为止。

线性方程组的迭代解法有很多种，其中最经典的是雅可比迭代法、高斯-赛德尔迭代法和超松弛迭代法。

本文将分别介绍这三种迭代解法及其计算方法。

雅可比迭代法是一种比较简单的线性方程组迭代解法，它的基本思想是先将线性方程组转化为对角占优的形式，然后通过迭代求解逐渐接近精确解。

雅可比迭代法的迭代公式为：其中，x^(k+1)是第k+1次迭代的近似解，n是未知数的个数，a_ij 是系数矩阵A的元素，f_i是方程组的右端向量的元素。

雅可比迭代法的计算步骤如下：1.将线性方程组转化为对角占优的形式，即保证矩阵A的对角元素绝对值大于其它元素的绝对值。

2.初始化向量x^(0)，设定迭代终止准则。

3.根据雅可比迭代公式，计算x^(k+1)。

4.判断迭代终止准则是否满足，如果满足，则停止迭代，返回近似解x^(k+1)；否则，继续进行下一次迭代。

高斯-赛德尔迭代法是雅可比迭代法的改进方法，它的基本思想是在每次迭代计算x^(k+1)时，利用已经计算出的近似解作为x的一部分。

高斯-赛德尔迭代法的迭代公式为：其中，x^(k+1)_i是第k+1次迭代的近似解中第i个未知数的值，x^(k)_i是第k次迭代的近似解中第i个未知数的值。

高斯-赛德尔迭代法的计算步骤如下：1.将线性方程组转化为对角占优的形式。

2.初始化向量x^(0)，设定迭代终止准则。

3.根据高斯-赛德尔迭代公式，计算x^(k+1)。

4.判断迭代终止准则是否满足，如果满足，则停止迭代，返回近似解x^(k+1)；否则，继续进行下一次迭代。

超松弛迭代法是对高斯-赛德尔迭代法的一种改进方法，它引入了松弛因子ω，通过调整参数ω的值，可以加快迭代的收敛速度。

超松弛迭代法的迭代公式为：其中，0<ω<2，x^(k+1)_i是第k+1次迭代的近似解中第i个未知数的值，x^(k)_i是第k次迭代的近似解中第i个未知数的值。

线性方程组的迭代式求解方法迭代法解方程的基本原理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来判别迭代法的收敛性外，还可根据方程组系数矩阵的特点给出一些收敛性的判别条件。