数值分析-3

i = 1,2, L n k = 0,1,2, L (3.9)
Seidel 迭代法的矩阵迭代形式： 迭代法的矩阵迭代形式：
（推导） 推导）
x ( k +1) = B s x ( k ) + f s 其中 B s = − ( D + L ) −1 U ,
7
f s = ( D + L ) −1 b
( 3 .12 )
或改写为
x
( k +1) i
= 1 − ω）x （
+
bi − ∑ a x aii j =1
ω
i −1
( k +1) ij j
− ∑a x j =i +1
n (k ) ij j
(3.13)
称此公式为逐次超松弛法(SOR法). 法 称此公式为逐次超松弛法 式不难推出SOR方法的矩阵迭代形式： 方法的矩阵迭代形式： 从(3.13)式不难推出 式不难推出 方法的矩阵迭代形式
由表３-３和表３-４可见，达到同样的精度 由表３ ３和表３ ４可见，达到同样的精度Seidel迭代法要 迭代法要 72步，而取 的逐次超松弛法只要25步 步 而取ω=1.45的逐次超松弛法只要 步，可见当松弛 的逐次超松弛法只要 因子选择适当时，逐次超松弛法有明显加速收敛作用， 因子选择适当时，逐次超松弛法有明显加速收敛作用，它 常用于求解大型线性方程组。 常用于求解大型线性方程组。
( 一般地， 用 x1 k +1) 代替 x1( k ) ，一般地，计算
x i( k +1) (n≥i≥2)时，使 时
(k ) 用 x (pk +1) 代替 x p
(i >p≥1)，这样可能收敛会快一些，这就 ，这样可能收敛会快一些，
形成一种新的迭代法，称为塞德尔迭代法。 形成一种新的迭代法，称为塞德尔迭代法。 用塞德尔迭代法计算例1并作比较 并作比较. 例2 用塞德尔迭代法计算例 并作比较 解 迭代公式为： 迭代公式为：
雅可比迭代法的矩阵迭代形式 推导) 雅可比迭代法的矩阵迭代形式: (推导 的矩阵迭代形式 推导
x ( k +1) = B J x ( k ) + f J 其中， B J = − D − 1 ( L + U ), f J = D −1b
5
结束
3.2.2 塞德尔 (Seidel) 迭代法 ( x2k+1) 在简单迭代法的迭代形式(3.6)中，可以看出，在计算 在简单迭代法的迭代形式 中 可以看出， (k ) 已计算出来.看来此时可提前使 时，要使用 x1 .但此时 x1( k +1) 已计算出来 看来此时可提前使 但此时
x ( k +1) = Bω x ( k ) + f ω 其中 Bω = ( D + ω L ) −1[(1 − ω ) D − ω U ] , f ω = ω ( D + ω L ) −1 b
下面定理3.8可以看到，必须取 下面定理 可以看到，必须取0<ω<2，当ω=1时，就是 可以看到 ， 时 就是Seidel 迭代法.当 取得适当时 对塞德尔迭代法有加速效果. 取得适当时， 迭代法 当ω取得适当时，对塞德尔迭代法有加速效果 9
结束
用塞德尔迭代法和取ω=1.45的逐次超松弛法计算下列方程 例3 用塞德尔迭代法和取 的逐次超松弛法计算下列方程 ( k +1) (k ) max | xi − xi |< 10 −7 组的解， 组的解，当 时退出迭代，初值取x 时退出迭代，初值取 (0)=(1,1,1)T 。
4 x1 − 2 x 2 − x 3 = 0 − 2 x1 + 4 x 2 − 2 x 3 = − 2 − x − 2 x + 3x = 3 1 2 3
( ( x1( k +1) = 0.2 x2k ) + 0.1x3k ) + 0.3 ( k +1) ( k +1) ( + 0.1x3k ) + 1.5 x2 = 0.2 x1 x ( k +1) = 0.2 x ( k +1) + 0.4 x ( k +1) +2 1 2 3
(k=0,1,2, L)
结束
任取一初始向量， 例如x 得到迭代序列{x 任取一初始向量 ， 例如 (0)=(0,0,0)T ， 得到迭代序列 (k)} (k=0,1,2,L)，列表如下表 。 L ，列表如下表3-1。
k x1 x2 x3 0
0 0 0
1
2
3
4
5
6
7
8
0.3000 0.8000 0.9180 0.9716 0.9804 0.9962 0.9985 0.9998 1.5000 1.7600 1.9260 1.9700 1.9897 1.9961 1.9986 1.9998 2.0000 2.6600 2.9540 2.9540 2.9823 2.9938 2.9977 2.9997
2
结束
先看一个算例： 先看一个算例： 例1 10 x 1 − 2 x 2 − x 3 = 3 − 2 x 1 + 10 x 2 − x 3 = 15 − x − 2 x + 5 x = 10 1 2 3 从以上三个方程中分别解出x 从以上三个方程中分别解出 1, x2, x3。 x1 = 0.2 x2 + 0.1x3 + 0.3 + 0.1x3 + 1.5 x2 = 0.2 x1 x = 0.2 x + 0.4 x +2 1 2 3 按下式进行迭代 ( ( x ( k +1) = 0.2 x2k ) + 0.1x3k ) + 0.3 1 ( k +1) ( x2 = 0.2 x1( k ) + 0.1x3k ) + 1.5 x ( k +1) = 0.2 x ( k ) + 0.4 x ( k ) +2 1 2 3 3
容易验证， 容易验证，原方程组的精确解为 x = (1,2,3) T，从上面的计 算可看出， 收敛于精确解. 算可看出，{x(k)}收敛于精确解 收敛于精确解 一般说来，对方程组： 一般说来，对方程组： n a ij x j = bi i=1,2,L，n (3.4) L j =1 并设a 个方程解出x 并设 ii≠0(i=1,2,L,n)，从第 个方程解出 i，得等价的方程组 L ，从第i个方程解出 ： 4 结束
10
结束
3.3 迭代法的一般形式的收敛条件
可见它对这一方程组比简单迭代法收敛快一些。 可见它对这一方程组比简单迭代法收敛快一些。 塞德尔迭代法的公式如下： 塞德尔迭代法的公式如下： 1 i −1 bi ( k +1) ∑ aij x (j k +1) + xi = − aii aii j =1
j = i +1
∑a
n
ij
x
(k ) j
(k=0,1,2, L)
6
结束
用它计算得到的序列{x 列表如表 列表如表3-2： 用它计算得到的序列 (k)}列表如表 ：
k x1 x2 x3 0 0 0 0 1 0.3000 1.5000 2.6840 2 0.8804 1.9448 2.9539 3 0.9843 1.9922 2.9938 4 0.9978 1.9989 2.9991 5 0.9997 1.9998 2.9999 6 1.0000 2.0000 3.0000
8
结束
为加快收敛， 为加快收敛，在增量 ri( k ) 前加一个因子 ω
x
( k +1 ) i
(0 < ω < 2) ，得
n (k ) j
=x
(k ) i
+
bi − ∑ a ij x a ii j =1
(k ) i
ω
i −1
( k +1 ) j
− ∑ a ij x
j =i

j = i +1
∑a
n
ij
x
(k ) j

改写为
xi( k +1)
1 = xi( k ) + aii
ri
(k )
i −1 n ( k +1) (k ) bi − ∑ aij x j − ∑ aij x j j =1 j =i
记
=x
( k +1 ) i
−x
(k ) i
任取一个向量x 作为x的近似解 的近似解， 任取一个向量 (0)作为 的近似解，用迭代公式 (3.3) x(k+1)=Bx(k)+f, (k=0,1,2,L) L (k ) = x 产生一个向量序列{x ， lim 产生一个向量序列 (k)}，若→ ∞ x k 的解， 也就是Ax=b的解 的解. 则有 x=Bx +f，即x是(3.2)的解，当然 也就是 ， 是 的解 当然x也就是 的解 从以上的讨论中，可以看出，迭代法的关键有： 从以上的讨论中，可以看出，迭代法的关键有： 1如何构造迭代公式 (k+1)=Bx(k)+f ？这样的构造形式不止 如何构造迭代公式x 一种，它们各对应一种迭代法. 一种，它们各对应一种迭代法 2 迭代法产生的向量序列 (k)}的收敛条件是什么 ， 收敛 的收敛条件是什么， 迭代法产生的向量序列{x 的收敛条件是什么 速度如何.后面将进行讨论 后面将进行讨论. 速度如何 后面将进行讨论 3.2 几种常用的迭代法公式 3.2.1 简单迭代法
第三章 线性方程组的迭代解法
线性方程组的直接法， 线性方程组的直接法，用于阶数不太高的线性方程组效 果较好.实际工作中有的线性方程组阶数很高， 果较好.实际工作中有的线性方程组阶数很高，但其中的大 多数系数为0 这一类的线性方程组的系数阵 多数系数为0，这一类的线性方程组的系数阵称为稀疏矩 稀疏矩阵的存贮和计算有一套技术处理， 阵.稀疏矩阵的存贮和计算有一套技术处理，可以节约大量 的存贮空间和计算工作量.用直接法计算时， 的存贮空间和计算工作量.用直接法计算时，因一次消元就 可以使系数阵丧失其稀疏性，不能有效利用其稀疏的特点. 可以使系数阵丧失其稀疏性，不能有效利用其稀疏的特点. 下文介绍的迭代法就有保持系数阵稀疏的优点 迭代法就有保持系数阵稀疏的优点， 下文介绍的迭代法就有保持系数阵稀疏的优点，此外迭代法 也常用来提高已知近似解的精度. 也常用来提高已知近似解的精度 迭代法的一般形式 3.1 迭代法的一般形式 Ax=b 线性方程组 (3.1) 其中A非奇异 非奇异， ≠ 因而它有唯一非零解. 其中 非奇异，b≠0，因而它有唯一非零解. 构造与(3.1)等价的方程组 = + 构造与(3.1)等价的方程组 x=Bx+f (3.1) (3.2) (3.2) 即使得(3.2)与(3.1)同解，其中B是n×n矩阵，f是n维向量 即使得(3.2)与(3.1)同解，其中 是 × 矩阵， 是 维向量. (3.2) 同解 矩阵 维向量 1 结束