当前位置：文档之家 › 解线性方程组的迭代法

解线性方程组的迭代法

  • 格式：doc
  • 大小：200.00 KB
  • 文档页数：7

第四章 解线性方程组的迭代法对于阶数不高的方程组，直接法非常有效，对于阶数高，而系数矩阵稀疏的线性方程组却存在着困难，在这类矩阵中，非零元素较少，若用直接法求解，就要存贮大量零元素。

为减少运算量、节约内存，使用迭代法更有利。

本章介绍迭代法的初步内容。

§1 雅克比法、赛得尔法、超松驰法 1．雅克比（Jacobi ）迭代法 设有n 阶方程组⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++nn nn n n n n n n b x a x a x a b x a x a x a b x a x a x a 22112222212111212111 （4.1）若系数矩阵非奇异，且0≠ii a (i = 1, 2,…, n )，将方程组（4.1）改写成()()()⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧----=----=----=--11,221112323122221213132121111111n n n n n n nn n n n n n x ax a x a b a x x a x a x a b a x x a x a x a b a x 然后写成迭代格式()()()⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧----=----=----=--+++)(11,)(22)(11)1()(2)(323)(121122)1(2)(1)(313)(212111)1(1111k n n n k n k n n nn k n k n n k k k k n n k k k x a x a x a b a x x a x a x a b a x x a x a x a b a x （4.2）（4.2）式也可以简单地写为),,2,1(1)(1)1(n i x a b a x k j n i j j ij i iik i =⎪⎪⎪⎭⎫ ⎝⎛-=∑≠=+（4.3）对（4.2）或（4.3）给定一组初值Tn x x x X),,()0()0(2)0(1)0( =后，经反复迭代可得到一向量序列Tk n k k x x X ),()()(1)( =，如果X (k )收敛于Tn x x x X ),,(**2*1*=，则),,2,1(*n i x i =就是方程组（4.1）的解。

这一方法称为雅克比（Jacobi ）迭代法或简单迭代法，（4.2）或（4.3）称为Jacobi 迭代格式。

下面介绍迭代格式的矩阵表示： 设D = diag (a 11, a 22, …, a nn )，将AX = b 改写为： AX = (D – (D - A )) x = b DX = (D - A ) x + b X = (I – D -1A ) x + D -1b记 B = I – D -1A F = D -1 b 则迭代格式的向量表示为F BX X k k +=+)()1( Ｂ称为雅克比迭代矩阵。

2．高斯――赛得尔（Gauss-Seidel ）迭代法显然，如果迭代收敛，)1(+k i x 应该比)(k i x 更接近于原方程的解*i x （i = 1, 2,…, n ），因此在迭代过程中及时地以)1(+k i x 代替)(k i x （i = 1, 2,…, n -1），可望收到更好的效果。

这样（4.2）式可写成：()()()⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧---=---=---=+--++++++)1(11,)1(22)1(11)1()(2)(323)1(121222)1(2)(1)(313)(212111)1(1111k n n n k n k n n nn k nk n n k k k k n n k k k x a x a x a b a x x a x a x a b a x x a x a x a b a x （4.5）（4.5）式可简写成⎪⎪⎭⎫⎝⎛--=∑∑+=+-=+)(1)1(11)1(1k jni j ijk j i j ij i iik ixax a b a x（i = 1, 2,…, n ） 此为G －S 迭代格式。

G －S 迭代格式的矩阵表示： Jacob 方法的迭代格式为F Bx x k k +=+)()1(其中 B = I-D -1A F = D -1b 将B 写成 B = L + U L 是下三角阵，U 是上三角阵 从而 F Ux Lx x k k k ++=++)()1()1(F Ux x L I k k +=-+)()1()(F L I Ux L I x k k 1)(1)1()()(--+-+-=（4.6）此时迭代矩阵为 (I - L )-1U 关于上述迭代法的误差控制，可按类似于第二章非线性方程求根的迭代法处理，设ε为允许的绝对误差限，可以检验ε<-+≤≤)()1(1max k i k i ni x x是否成立，以决定计算是否终止，进一步的讨论稍后进行。

实际计算时，如果线性方程组的阶数不高，建立迭代格式也可以不从矩阵形式出发，以避免求逆矩阵的计算。

3．超松驰法 使用迭代法的困难是计算量难以估计，有些方程组的迭代格式虽然收敛，但收敛速度慢而使计算量变得很大。

松驰法是一种线性加速方法。

这种方法将前一步的结果)(k i x 与高斯――赛得尔方法的迭代值)1(~+k i x 适当进行线性组合，以构成一个收敛速度较快的近似解序列。

改进后的迭代方案是： 迭代⎪⎪⎭⎫ ⎝⎛--=∑∑+=+-=+)(1)1(11)1(1~k j ni j ij k j i j ij i ii k i x a x a b a x加速),,2,1(~)1(1)()1(n i x x x k i k i k i =+-=++ωω所以⎪⎪⎭⎫⎝⎛--+-=∑∑+=+-=+)(1)1(11)()1()1(k j ni j ij k ji j ij i ii k ik ix a x a b a xxωω（4.7）这种加速法就是松驰法。

其中系数ω称松驰因子。

可以证明，要保证迭代格式（4.7）收敛必须要求 20<<ω 松驰法的矩阵形式的迭代格式为：ωωF x B x k k +=+)()1(其中 ()U I L I B ωωωω+--=-)1()(1b L I F 1)(--=ωωω当ω = 1时，即为高斯――赛得尔迭代法，为使收敛速度加快，通常取1>ω，即为超松驰法。

松驰因子的选取对迭代格式（4.7）的收敛速度影响极大。

实际计算时，可以根据系数矩阵的性质，结合经验通过反复计算来确定松驰因子ω。

§2 迭代法的收敛条件 由§1中迭代格式的矩阵形式知，方程组AX = b 的雅克比迭代法、高斯――赛得尔迭代法和松驰法的矩阵形式都可以写成下式：F BX X k k +=+)1(（4.8）当然，不同的迭代法其迭代矩阵B 和F 的元素是不同的。

所以我们讨论迭代格式（4.8）的收敛性，就具有普遍意义。

下面，我们不加证明地给出迭代格式（4.8）收敛的充分必要条件。

定理1：对任意初始向量X (0)及常向量F ，迭代格式（4.8）收敛的充分必要条件是迭代矩阵B 的谱半径ρ(B ) < 1。

这一结论在理论上是颇为重要的，但实际用起来不甚方便，为此我们着重研究更为实用的判别迭代格式收敛的充分条件。

考虑迭代向量序列{X (k )}的收敛问题： 若 *)(lim X X k k =∞→F BX X +=**于是()())(*)0(*)2(2*)1(*)(X X B X X B X X B X X k k k k -==-=-=---收敛的意思是：()()0lim lim *)0(*)(=-=-∞→∞→X X B X X k k k k依范数收敛是0*)0(*)(→-≤-X X BX X mk 当k →∞，从而得以下定理：定理2：若迭代矩阵Ｂ的某种范数1<B 则（4.8）确定的迭代法对任意初值X (0)均收敛于方程组X = BX + F 的唯一解x *。

下面给出直接计算)1(+k i x 时的收敛性定理。

为给出这个定理，先介绍对角占优的概念。

定义1：如果矩阵的每一行中，不在主对角线上的所有元素绝对值之和小于主对角线上元素的绝对值，即n i a aiinij j ij,,2,11 =<∑≠=则称矩阵A 按行严格对角占优，类似地，也有按列严格对角占优。

定理3：若线性方程组AX = b 的系数矩阵A 按行严格对角占优，则雅克比迭代法和高斯――赛得尔迭代法对任意给定初值均收敛。

证明：记*)(1max j k jnj k x x e -=≤≤为第k 次近似值()Tk nk k x x x )()(2)(1,,, 的误差，（1）由雅克比迭代法()*)(1*)(1*)1(j k j nij j iiijjk jnij j iiijik i x x aa xxa a x x-≤-=∑∑≠=≠=+记∑≠==nij j iiij a a L 1则有*)(1*)1(max j k j nj i k i x x L x x -⋅≤-≤≤+上式对 i = 1, 2,…, n 成立，故有e L Le e k k k 11++≤≤≤因为A 严格对角占优，故L < 1，从而有0lim lim *)0(1*)1(=-≤-+∞→+∞→i i k k i k i k x x L x x即雅克比方法收敛。

（2）高斯――赛得尔迭代法 考虑高斯――赛得尔方法的误差()iini j j k j ijiij k j i j ijiini j jk j jk ji j ij i k i a x x aa x x aa x xx xa x x ∑∑∑∑+=+==+=+==+-+-≤-+-=-1*)(*)1(111*)(*)1(11*)1(记∑∑+=====ni j iiiji j iiij aa S a a L 111则*)(1*)1(11*)1(max j k j nj i j k j i j i k i x x mas S x x L x x -⋅+-⋅≤-≤≤++-≤≤+从而k k k Se Le e +≤++1101111e L S e L S e k k k ⋅⎪⎭⎫ ⎝⎛-≤≤-≤++而11111111=---<---+=-+-=⎪⎭⎫ ⎝⎛-L L L L L L LS L L L S L S 所以0lim *)1(=-+∞→i k i k x x即：高斯――赛得尔迭代法收敛。

证完例：用雅克比迭代法和高斯――赛得尔迭代法解线性方程组⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎭⎫ ⎝⎛----877901081119321x x x 解：所给线性方程组的系数矩阵按行严格对角占优，故雅克比迭代法和高斯――赛得尔迭代法都收敛。

合集下载

第2章解线性代数方程组的迭代法

第2章解线性代数方程组的迭代法

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

第五章 解线性方程组的迭代解法

第五章 解线性方程组的迭代解法

i 1 n 1 xi = [bi ∑ aij x j ∑ aij x j ] , i = 1, 2,, n. （*） ） aii j =1 j = i +1
定义迭代法为： 定义迭代法为：
x ( k + 1) = G J x ( k ) + g
其中Jacobi迭代矩阵：GJ = D1 ( L + U ) 迭代矩阵： 其中 迭代矩阵
g = D 1b = (7.2, 8.3, 8.4)T 取 x ( 0 ) = (0, 0, 0)T , 代入迭代式，得x(1) = Bx ( 0 ) + g = (7.2, 8.3, 8.4)T x ( 2 ) = Bx (1) + g = (9.71,10.70,11.5)T x (9 ) = (10.9994,11.9994,12.9992) 精确解为 x = (11,12,13)T .
记
A = D L U
其中 D = diag (a11 ,, ann ) , L, U 分别为 A 的 严格下、上三角形部分元素构成的三角阵 严格下、上三角形部分元素构成的三角阵. Gauss-Seidel方法的矩阵形式为 方法的矩阵形式为
x ( k +1) = D1 ( Lx ( k +1) + Ux ( k ) + b)
或者
x ( k +1) = ( D L)1Ux ( k ) + ( D L)1 b
( 这说明Gauss-Seidel方法的迭代矩阵为 D L)1U 方法的迭代矩阵为 这说明
从而有
定理5.2 定理5.2 Gauss-Seidel方法收敛的充分必要条件为 方法收敛的充分必要条件为
ρ (GG ) < 1 或
计算方法3_线性方程组迭代解法

计算方法3_线性方程组迭代解法

计算方法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 。