当前位置：文档之家 › 计算方法PPT课件第四章 解线性方程组的迭代法

计算方法PPT课件第四章 解线性方程组的迭代法

  • 格式：pptx
  • 大小：672.63 KB
  • 文档页数：40

下载文档原格式

  / 40

合集下载

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

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

(4 - 1)
简记为：
an1 x1 an2 x2 ann xn bn
n
aij x j bi
j 1
(i 1,2,, n)
其系数矩阵A非奇异，不妨设aii≠ 0 (1,2,…,n)可将上式 改写为等价方程组：
x1 (
a12 x2 a13x3 a1n xn b1) / a11
但在Jacobi迭代过程中, 对已经算出来的信息未 加充分利用,
即在计算x2(k 1)时, x1(k 1)已经算出, 计算xi(k 1)时, x1(k 1) , x2(k 1) ,, xi(k11) 已经算出,这些前面的最新分量未 被利用,从直观上看,在收敛的
情况下, 这些新值x1(k 1) , x2(k 1) ,, xi(k11)应比旧值x1(k) , x2(k) ,, xi(k1)更 好,更准确一些.因此,如果每计算出一个新的 分量便立即用它取代 对应的旧分量进行迭代 ,可能收敛更快并且只需 要存贮一个近 似解向量即可, 据此想法构造的迭代法 称为高斯 塞德尔 (Gauss Seidel)迭代法,其迭代格式为 :

(3 8)
M ( D L) U x(k1) n

1 ann
(an1x1(k 1)
an2 x2(k 1)
1


a x(k 1) nn1 n1
bn )
其分量形式为
x(k 1) i

1 aii
i 1
(
a x(k 1) ij j
j 1

n
n维点列收敛的一种等价描述是其对应坐标序列均
收敛，向量序列也有类似的结论。
定理1
Rn中的向量序列 x(k) 收敛于Rn中的

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

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

其中
0 a2 1 B (I D1 A) a 22 a n1 an n
a1n a1 2 a1 1 a1 1 a2n 0 a2 2 an2 0 an n
在例4.2中,由迭代公式写出雅可比迭代矩阵为
8x1 3x2 2x3 20 4x1 11x2 x3 33 6x 3x 12x 36 2 3 1
( 0 ) ( 0 ) ( 0 ) ( 0 )T T 取初始向量 x ( x , x , x ) ( 0 , 0 , 0 ) 1 2 3
进行迭代, 可以逐步得出一个近似解的序列：
x Gx d( k 0 , 1 , )
( k )
( k 1 )
Gx d 中当 k x x ,则 x 时，
(k) *
* *
, 故 x * 是方程组 Ax b 的解。
对于给定的方程组可以构造各种迭代公式。
并非全部收敛
例4.1
用迭代法求解线性方程组
2x1 x2 3 2x1 5x2 3
3 ( k ) 3 1 ( k ) 25 ( k 1) 0 x 2 x3 x1 8 84 82 4 1 4 (k ) 1 (k ) (k 1 1 ) BI D A 0 x1 x3 3 x2 11 11 11 11 6 1 ( k )3 1 ( k 1) (k ) 0 x x x 3 1 2 3 2 4 12 12
2 x 4 x 3 计算得
( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) x 3 x 3 x 9 x 15 x 33 1 1 1 1 1 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) x 3 , x 3 , x 9 , x 15 , x 33 , 2 2 2 2 2

第四章线性方程组的求解

第四章线性方程组的求解
(行 系 数 i,k ) l
1.2.2
For j=k+1,…, n
aij- aik akj aij(新) bi - aik bk bi (新)
*常用|akk|≤
步骤 2. 步骤 3.
bn /ann xn For k=n-1,…,1 3.1 3.2
(回代)
bk s For j=k+1,…,n
b1( 0 ) (1) b2 (1) bn
注意：若a11（0） ＝0，因为 det（A）0，在A的第1列元素中至 少有某ai1（0） 0将i行与第1行交换，再作第1步 。
(0 a11 ) 假定已完成k－1步消元， ( 0) ( 0) ( A( k 1) , b( k 1) ) ( A ,b ) (0 a12 ) (1 a22)
迭代法：从一个初始向量出发，按照一定的迭代格 式，构造出一个趋向于真解的无穷序列。
举例
x 2 x2 2 x3 2 例：直接法解线性方程组 1 2 x1 3 x2 3 x3 4 4 x1 x2 6 x3 3
1 2 2 2 ( A, b) 2 3 3 4 4 1 6 3 2 2 1 2 0 1 7 8 0 0 61 61
解：
2 2 1 2 0 1 7 8 0 9 2 11
x3 1 x2 8 7 x3 1 x1 2 2x2 2x3 2
第四章 解线性方程组的直接法
a11 x1 a12 x 2 a1n x n b1 a x a x a x b 21 1 22 2 2n n 2 a n1 x1 a n 2 x 2 a nn x n bn

第四章_线形方程组求根

第四章_线形方程组求根

max | aij |
1 i n j 1
n
max表示A ' A的最大特征值
§1
向量范数,矩阵范数,谱半径 及有关性质
2 0 0 A 0 1 0 0 0 1
n 1 j n i 1 n
例子：设有方阵A，求其1-范数,2-范数及-范数。
其中
A 1 max | aij | max(2 ,1 ,1 ) 2 A

max | aij | max(2 ,1 ,1 ) 2
1 i n j 1
§1
向量范数,矩阵范数,谱半径 及有关性质
X BX ( I B ) X 0 X 0, ( I B ) 0 det( I B ) 0 2 0 0 2 0 0 4 0 0 A' A 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 || A ||2 max ( A ' A) 4 2
|| X ||2 x12 x2 2 ... xn 2 ( xi )
i 1
1-范数
1 2 2
i 1 n
2-范数
|| X || max{| x1 |,| x2 |,...,| xn |} max{| xi |}
1i n
其中x1,x2, …,xn分别是X的n个分量 -范数 上述范数都是p范数的特例 || X || p ( xi )
§1
向量范数,矩阵范数,谱半径 及有关性质
|| A ||F
F-范数(Frobenius OR Euclid范数)
i , j 1
a

《解线性方程组的VRP-GMRES(m)迭代法》

《解线性方程组的VRP-GMRES(m)迭代法》

《解线性方程组的VRP-GMRES(m)迭代法》篇一一、引言随着科技的发展，线性方程组的求解在科学计算、工程问题以及数据分析等领域扮演着重要的角色。

其中，VRP-GMRES(m)迭代法是一种高效、准确的求解方法。

本文将详细介绍VRP-GMRES(m)迭代法的原理、步骤及其在解线性方程组中的应用。

二、VRP-GMRES(m)迭代法的基本原理VRP-GMRES(m)迭代法是一种基于Krylov子空间的迭代法，用于求解大型稀疏线性方程组。

该方法通过构造一系列的Krylov 子空间，逐步逼近方程组的解。

GMRES算法在每次迭代中都会寻找一个最佳的方向来逼近解，而VRP（Variable Projection）技术则是在此基础上进行优化，提高了算法的收敛速度和稳定性。

三、VRP-GMRES(m)迭代法的步骤1. 初始化：设定初始向量x0和初始残差r0=b-Ax0。

2. 构建Krylov子空间：根据初始残差r0，通过Arnoldi过程构建Krylov子空间。

3. 求解最小二乘问题：在Krylov子空间中求解最小二乘问题，得到搜索方向。

4. 投影与更新：利用VRP技术对搜索方向进行投影和更新，得到新的近似解和残差。

5. 判断收敛性：根据设定的收敛准则判断是否收敛，若收敛则输出解，否则返回步骤2继续迭代。

四、VRP-GMRES(m)迭代法在解线性方程组中的应用VRP-GMRES(m)迭代法在解线性方程组中具有广泛的应用。

首先，它可以有效地处理大型稀疏线性方程组，提高了计算效率。

其次，该方法在处理病态方程组时具有较好的稳定性和收敛性。

此外，VRP技术的引入进一步提高了算法的收敛速度和精度。

在实际应用中，VRP-GMRES(m)迭代法已被广泛应用于科学计算、工程问题、数据分析等领域。

五、结论VRP-GMRES(m)迭代法是一种高效、准确的求解大型稀疏线性方程组的方法。

该方法通过构造Krylov子空间，逐步逼近方程组的解。

解线性方程组的迭代法

解线性方程组的迭代法
定义2 (向量范数) 如果在 R n 中定义了实值函数，记为 || || ， 对所有 x, y R n 以及 R ，若满足
|| x || 0 (非负性) ； （1）|| x || 0 ，当且仅当 x 0 时，
（2） || x ||| | || x || (齐次性)； （3） || x y |||| x || || y || (三角不等式). 则称 || x || 为向量 x 的范数 (或模).
4.1.2 向量范数和向量序列的极限
常用的向量范数：设 x R n （1）向量的 - 范数 (最大范数)： || x || max | xi |
1 i n
|| x ||1 （2）向量的 1 - 范数 (绝对值范数)：
（3）向量的 2 - 范数：|| x ||2 ( x , x ) (
|| A ||2 3+2 2 , || A ||F 6
4.1.3 矩阵范数和矩阵序列的极限
(k ) ) R nn ，如果存 定义5 (矩阵序列的极限) 设有矩阵序列 Ak (aij
在 A (aij ) R nn，使
k (k ) lim aij aij ,
i, j 1, 2,
（4） || AB |||| A || || B || ； 则称 || A || 为矩阵 A 的范数.
4.1.3 矩阵范数和矩阵序列的极限
相容性： 设有矩阵范数 || ||s 和向量范数 || ||t ，如果对任何向量 x R n 及矩阵 A R nn ，有/2 || A ||F ( aij ) i , j 1 n
它是与向量 2-范数相容的矩阵范数，但不是从属范数.
4.1.3 矩阵范数和矩阵序列的极限

计算方法迭代法PPT课件

计算方法迭代法PPT课件
第8页/共33页
不动点原理(迭代过程收敛)
•定理3.1 (不动点原理) 设映射g(x)在[a,b]上有连 续的一阶导数且满足
1o 封闭性：x [a,b], g(x) [a,b] ,
2o 压缩性： L (0,1)使对x [a,b], |g'(x)|L,
则 在 [a,b] 上 存 在 唯 一 的 不 动 点 x* ， 且 对 x0
1 x j 1
g~mj 0 g~mj 0
x 1
G~
n g~mj
j 1
n g~mj x j
j 1
max
1in
n j 1
g~ij x j
G~x
第27页/共33页
Gauss-Seidel迭代收敛性证明
记 那么 存在k使得
，其中y迭代G矩~阵x y D1(Ly Ux)
G~ (L D)1U
x x(k ) k 0
第19页/共33页
2 Jacobi迭代和Gauss-Seidel迭代
• 例3.7
• 解：变形
1x01x1
x2 2x3 7.2 10x2 2x3 8.3
x1 x2 5x3 4.2
x1 x2
0.72 0.1x2 0.83 0.1x1
0.2x3 0.2x3
第24页/共33页
3 迭代的收敛性
• 定理3.4 设G的某种范数||G||<1，则x=Gx+f存在唯一解，且对任意初值，迭代序列 x(k)= Gx (k-1) + f
收敛于x*，进一步有误差估计式
k
x x G x x G • 证明思路：(1)解的存在唯一(k性) ; (2)解的收敛性;((3k))误差估(k计1式) (习题)。

解线性方程组的迭代法

解线性方程组的迭代法

0.9906
0.0355
5 1.01159 0.9953
1.01159 0.01159
6 1.000251 1.005795 1.000251 0.005795
7 0.9982364 1.0001255 0.9982364 0.0017636
可见,迭代序列逐次收敛于方程组的解, 而且迭代7次得到精确到小数点后两位的近似解.
a11x1 a12x2 a13x3 b1 a21x1 a22x2 a23x3 b2 a31x1 a32x2 a33x3 b3
从而得迭代公式
x1
a12 a11
x2
a13 a11
x3
b1 a11
x2
a21 a22
x1
a23 a22
x3
b2 a22
x3
a31 a33
M 00.8 00..75
但(M)=0.8<1,所以迭代法 x(k+1)=Mx(k)+g 是收敛的.
由(3.5)式可见,‖M‖越小收敛越快,且当‖x (k) -x(k-1) ‖很小时,‖x(k) –x*‖就很小,实际中用‖x (k) x(k-1) ‖<作为
迭代终止的条件。 例如，对例1中的Jacobi迭代计算结果
+‖x(k+1) –x*‖‖M‖‖x(k) –x(k-1)‖+‖M‖‖x(k) –x*‖ 从而得‖x(k) –x*‖‖M‖‖x (k) -x(k-1) ‖/（1- ‖M‖）
(3.5) (3.6)
估计式(3.5)得证。利用(3.5)式和
‖x(k+1) 得到
-x(k)
‖‖M‖‖x
(k)
-x(k-1)
‖
解线性方程组 的迭代法

线性代数方程组迭代法PPT课件

线性代数方程组迭代法PPT课件

超松弛法
收敛速度快
总结词
总结词
计算量较大
ABCD
详细描述
超松弛法具有较快的收敛速度，尤其对于大型线 性方程组，能够显著减少迭代次数。
详细描述
由于超松弛法的计算量较大，因此在实际应用中 可能需要考虑计算效率的问题。
CHAPTER 04
迭代法的实现步骤
初始化
设置初值
为方程组的解向量设定一个初始值。
迭代法的应用场景
当方程组的系数矩阵难以直接求解时 ，迭代法可以作为一种有效的替代方 案。
在科学计算、工程技术和经济领域中 ，许多问题可以转化为线性代数方程 组求解，而迭代法在这些领域有广泛 的应用。
迭代法的优缺点
优点
迭代法通常比直接法更加灵活和通用，对于大规模和高维度的线性代数方程组， 迭代法更加高效。
缺点
迭代法需要选择合适的迭代公式和参数，并且需要满足收敛条件，否则可能无 法得到正确的解。此外，迭代法的计算过程比较复杂，需要较高的计算成本。
CHAPTER 02
迭代法的基本原理
迭代法的数学模型
迭代法是一种求解线性代数方程组的数值方法，通过不断迭代逼近方程的 解。
迭代法的数学模型通常表示为：$x_{n+1} = T(x_n)$，其中$x_n$表示第 $n$次迭代时的近似解，$T(x)$表示迭代函数。
03
非线性方程组的迭代法在求解优化问题、控制问题 等领域有广泛应用。
在优化问题中的应用
01
迭代法在优化问题中也有广泛应用，如求解无约束优化问题、 约束优化问题和多目标优化问题等。
02
常见的优化问题迭代法包括梯度下降法、牛顿法和共轭梯度法
等。
这些方法通过不断迭代来逼近最优解，广泛应用于机器学习、

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

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

第四章解线性方程组的迭代法4.1 迭代法及其收敛性4.1.1 向量序列及矩阵序列的极限定义1.1设中的向量序列，如果存在，使则称向量序列收敛于x,记作同样，矩阵序列，，若有，i,j=1,2,…，n,则称矩阵序列收敛于，记作.概据定义，显然有定理1.1的充分必要条件是(4.1.1)其中两个极限的右端分别指零矩阵与零向量.证明对任一种矩阵从属范数有由,故式(4.1.1)对成立.反之，若取x为第j个坐标向量，则表示第j列元素极限均为零；当j=1,2,…,n时则证明了.证毕.定理1.2的充分必要条件是，其中为谱半径.证明由于，而，当，故有，即，故.反之，当时，由上章定理4.6可知，对任给ε＞0，存在，使，于是从而.证毕.定理1.3设为任一种范数，则(4.1.2) 讲解：及矩阵序列的极限是通过向量分量与矩阵元素极限定义的。

共收敛充要条件是迭代法收敛性要使用的。

为加深理解请看下例：例设，证明，但则不收敛。

解根据定理1.2要证明只要证明，先求的特征值，由，可知，故，故对有得，故，由定理1.2知不收敛。

4.1.2 迭代法的构造设非奇异，用迭代法解方程组(4.1.3)首先要构造迭代序列，通常可将方程改写为(4.1.4)并由此构造迭代法(4.1.5)其中称为迭代矩阵.对任意给定的初始向量，由(4.1.5)可求得向量序列.若，则就是方程(4.1.4)(或(4.1.3))的解.定义1.2若迭代法(4.1.5)生成的序列满足则称迭代法(4.1.5)是收敛的.构造的迭代法(4.1.5)是否收敛，取决于迭代矩阵的性质，先看例题.例4.1给定方程组它的精确解,可构造如下迭代法(4.1.6)若写成式(4.1.5)的形式，则迭代矩阵B及f可表示为：若取,按式(4.1.6)迭代10次可得，误差.它表明迭代序列(4.1.6)收敛.对于方程组(4.1.3)，构造迭代法的一般原则是将A分解为A=M-N (4.1.7) 其中M非奇异且容易求,则由(4.1.3)可得(4.1.8)其中(4.1.9)这样就得到与(4.1.3)等价的(4.1.8)，从而可构造(4.1.5)的迭代法，将A按不同方式分解为(4.1.7)，就可得到不同的迭代矩阵B，从而得到不同的迭代法.通常为使容易计算，可取M为对角矩阵，三角矩阵或三对角矩阵等.在例4.1中，,.式(4.1.6)就是下节将要讨论的Jacobi迭代法.4.1.3迭代法的收敛性与收敛速度下面讨论迭代法(4.1.5)的收敛性.若则即,故即为方程(4.1.3)的解.令,由(4.1.5)减去等式,则得由此递推得(4.1.10) 其中与k无关，所以等价于即.由定理1.2可知，于是有如下定理.定理1.4迭代法(4.1.5)对收敛的充分必要条件是(4.1.11)其中为矩阵B的谱半径.例4.2考察例4.1中迭代法(4.1.6)的收敛性.解由可得.用方程求根方法可解得，故迭代法(4.1.6)收敛.由于计算较困难，通常可利用判断迭代法的收敛性.在本例中由于，故迭代法(4.1.6)收敛.于是，迭代法(4.1.5)收敛的充分条件如下.定理1.5对迭代法(4.1.5)，如果迭代矩阵B的某种范数，则对及，迭代序列均收敛于，且有误差估计(4.1.12)证明由于，故由定理1.4得收敛于.又由(4.1.5)知于是即为(4.1.12)，证毕.注意，定理只给出迭代序列(4.1.5)收敛的充分条件，即使条件‖B‖＜1对任何范数都不成立，迭代序列仍可能收敛.例4.3 设，其中，讨论迭代序列的收敛性.解显然表明B的范数均大于1，但由于，故由定理1.4知此迭代序列是收敛的.下面考察迭代法(4.1.5)的收敛速度.由(4.1.10)得于是(4.1.13)根据算子范数定义可知所以是迭代k次后误差向量的范数与初始误差向量的范数之比的最大值.若要求迭代k次后这里是一个小数，通常ε<< 1，所以，由，两边取对数可得(4.1.14)它表明迭代步数k与成反比，即(4.1.15)愈大，迭代次数k愈少.于是可定义(4.1.15)式中的量为迭代法的平均收敛速度.它依赖于所取的范数，若利用定理1.3的(4.1.2)式则有定义1.3 称为迭代法(4.1.5)的渐近收敛速度.显然，它与B取何种范数无关.由于迭代法(4.1.5)收敛，故，越小，越大，迭代法收敛越快，且当迭代次数k满足时，有.例4.4 对例4.1中的迭代序列(4.1.6)要使相对误差，至少要迭代几次?解因(4.1.6)中迭代矩阵B的谱半径，因此取k=12,即为所求.，，讲解：求解可改为，从而有，为迭代收敛得充分必要条件。

解线性方程组的迭代方法优质课赛课一等奖市公开课获奖课件

解线性方程组的迭代方法优质课赛课一等奖市公开课获奖课件

Lx Ux
第16页
a11
其中
D
a22
,
ann
0
L
a21 a31
an1
0 a32
an 2
0
an,n1
0
0 a12 a13
U
0 a23 0
a1n
a2n
an1,n
0
A D L U , 因D1存在，故Ax b x D1(L U )x D1b
记 BJ D1(L U ) I D1A , fJ D1b 则有迭代格式： x(k1) BJ x(k) fJ
注：怎样判断迭代过程终止？
利用定理2误差预计式能够判断迭代过程是否能够
终止，但这种方法比较麻烦，通常采取方法是经过前
后两次迭代近似值差来判断，即利用：
max
1i n
|
x(k 1) i
x(k) i
|
或 || x(k1) x(k) ||
终止迭代过程。
上述这种求解方程组方法称为Jacobi迭代法。
第14页
a1n xn(k ) b1)
即
x2( k
1)
1 a22
(a21x1(k )
a23 x3(k )
a2n xn(k ) b2 )
xn( k
1)
1 ann
(an1x1(k )
an2 x2(k )
a x(k) n,n1 n1
bn
)
3、判断迭代格式收敛性。取初值 x(0) 带入计算。
第15页
Jacobi 迭代矩阵形式
例1：用迭代法解方程组
82xx11
x2 10
x2
x3
1 x3
4
x1
x2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

的右端可得m 1次近似x(m1)
(
x1(
m1)
,
x
( m1) 2
,
x（3 m1））T，其中
x1(
m1)
1 a11
(b1
a12 x2(m) a13 x3(m) )
x
( m1) 2
1 a22
(b2
a21 x1(m)
a(m) 23
x(m) 3
)
x (m1) 3
1 a33
(b3
a31 x1(m)
于是就得到矩阵形式的 Jacobi迭代公式
x(m1) BJ x(m) f J (m 0,1,)
(4.7)
其中BJ D1(L U )称为Jacobi迭代矩阵，f J D1b。
2020年8月15日星期六
a
7
•3.Jacobi迭代法的缺陷
由Jacobi迭代法的迭代公式(4.3)可以看到, 在计 算机上使用它求线性方 程组Ax b的解时，x(m)的分 量必须保存到x(m1)的分量全部算出之后， 因此，需 要两组存储单元。另外 ，算出的x(m1)的分量的新的 近似值在迭代过程中没 有被利用，例如在算出 x1(m1) 后，再算x2(m1)时，对于第1个分量仍然采用 x1(m) ,而不 是采用x1(m1)。
(比i=迭1ai,代i2,…格0,n式)时为，：类似于(4.3)式的推导，可得雅可
给出初值x(0)
xi(
m1)
1 aii
(bi
(
x(0) 1
,
x(0) 2
,,
xn(0
)
)T
,
i 1
n
aij
x
(m) j
aij
x
(m j
)
)
j 1
j i1
(m 0,1,2,；i 1,2,, n).
(4.4)
2020年8月15日星期六
在假定aii 0(i 1,2,3)的情形，（4.1）式可改写为
x1
1 a11
(b1
a12 x2 a13 x3 )
x2
1 a22
(b2
a21 x1
a23 x3 )
1
x3
a33
(b3
a31 x1
a32 x2
)
2020年8月15日星期六
a
(4.1)
(4.2)
2
设方程组（4.1）的准确解为向量 x* ( x1* , x2* , x3* )T，任取一个
0
， U
0 an1n
an1
an2
ann1
0
0
则系数矩阵A可表示成A D L U
(4.5)
i 1
n
改写(4.4)，有aii
x ( m 1) i
bi
aij
x(m) j
aij
x
(m j
)
j 1
j i1
(i 1,2,, n; m 0,1,)
(4.6)
2020年8月15日星期六
a
a(m) 32
x(m) 2
)
(4.3)
式（4.3）就是求解方程组（4.1）的Jacobi迭代公式。由(4.3)式
可知, 从某一初始近似 x(0)出发，一步一步地进行 迭代就得到了向
量序列x (0) , x (1) ,, x (m) ,。
2020年8月15日星期六
a
3
对于n阶方程组Ax=b,假定系数矩阵A的对角元
6
记向量x(m) (x1(m) , x2(m) ,, xn(m) )T，容易看出上式的左、 右两端分别是向量 Dx(m1)和向量b Lx(m) Ux(m)的第i
个分量，从而有
Dx(m1) b (L U )x(m)。 在假定aii 0(i 1,2,, n)时，D可逆，所以
x(m1) D1(L U )x(m) D1b,
第四章 解线性方程组的迭代法
a
1
4.1 三种基本的迭代法
4.1.1 Jacobi迭代法
(1.公式的推导, 2.Jacobi迭代法的矩阵形式, 3.Jacobi迭代法的缺陷)
•1.公式的推导
考虑3阶方程组
a11 x1 a12 x2 a13 x3 b1 a21 x1 a22 x2 a23 x3 b2 a31 x1 a32 x2 a33 x3 b3
a
4
定义4.1 如果向量序列x(0) , x(1) ,, x(m) ,中的向 量的每个分量，当 m 时都趋向于向量x*的对应分 量，则称x*是该向量序列的极限， 记为
lim x(m) x*
m
在一定条件下，对任意初始向量 x，(0)按迭代公
式(4.4)求出的向量序列的极限存在且等于方程的解。 这种用迭代格式(4.4)求线性代数方程组近似解的方 法称为雅可比迭代法，也称简单迭代法。
1 a33
(b3
a x (m1) 31 1
a32
x (m1) 2
)
2020年8月15日星期六
a
9
•2.用矩阵形式表示
类似于Jacobi迭代法，将上式改写为
i 1
n
a x(m1) ii i
bi
a x(m1) ij jFra bibliotekaij
x
(m j
)
j 1
j i1
(i 1,2,, n; m 0,1,2,)
(4.8)
fG (D L)1b。
2020年8月15日星期六
a
10
例1 用Jacobi迭代法和Gauss Seidel迭代法解线性方程组
利用由(4.5)定义的分解式 A D L U
上式可用矩阵形式表示 为
Dx(m1) b Lx(m1) Ux(m) ,
在假定aii 0(i 1,2,, n)时，就得到了矩阵形式 的Gauss Seidel迭代公式
x(m1) BG x(m) fG
(4.9)
其中：BG (D L)1U称为Gauss Seidel迭代法的迭代矩阵，
2020年8月15日星期六
a
5
•2.Jacobi迭代法的矩阵形式
记D diag(a11, a22 ,, ann )为A的对角线元素组成的对 角阵，L 和U分别为由A的元素组成的严格下三 角阵和严格上三角阵 ,即
0 a21 0
0 a12 0
a13 a23
a1n a2n
L
a31
a32
向量x (0)
(
x10
,
x(0) 2
,
x(0) 3
)
T
作为x
*的初始近似，把
x
(
0
)
代入（4.2）的
右端，求出的结果记为 x(1)
(
x (1) 1
,
x (1) 2
,
x (1) 3
)
T
，称为1次近似。一般
地，当求出了 m次近似 x ( m )
(
x1(
m
)
,
x
(m 2
)
,
x3( m
)
)
T
后，再代入
(4.2)式
2020年8月15日星期六
a
8
4.1.2 高斯－赛德尔(Gauss Seidel)迭代法
•1. 迭代公式（将4.3式作一点改进，得到下式：）
x
(
1
m
1)
1 a11
(b1
a12 x2(m)
a13
x(m) 3
)
x 2( m
1)
1 a22
(b2
a 21 x1(m1)
a23
x(m) 3
)
x3(m1)