计算方法 第八章 解线性方程组的迭代法 高斯迭代法 迭代法的收敛

计算方法第八章 线性方程组的解法计算方法课程组

§8.0

引 言

重要性：解线性代数方程组的有效方法在计算数学和

科学计算中具有特殊的地位和作用。如弹性力学、电路分析、热传导和振动、以及社会科学及定量分析商 业经济中的各种问题。 求解线性方程组 Ax b 的求解方法，其中A Rn n

,x, b R n 。* * * x* ( x1 , x2 , , xn )T

假设 A 非奇异，则方程组有唯一解.2

§8.0

引 言

分类： 线性方程组的解法可分为直接法和迭代法两种方法。(a)

直接法： 对于给定的方程组，在没有舍入误差的假设下，能在预定的运算次数内求得精确解。最基本的直接法是 Gauss消去法，重要的直接法全都受到Gauss消去法的启发。

计算代价高.(b)

迭代法：基于一定的递推格式，产生逼近方程组精确解的

近似序列.收敛性是其为迭代法的前提，此外，存在收敛速度与误差估计问题。简单实用, 诱人。

§8.1 雅可比Jacobi迭代法 (AX=b) 一、迭代法的基本思想 二、例题分析 三、 Jacobi迭代公式

§8.1 雅可比Jacobi迭代法 (AX=b)迭代法的基本思想 与解f (x)=0 的不动点迭代相类似，将AX=b改写

为X=BX+f 的形式，建立雅可比方法的迭代格式：

x( k 1) Bx( k ) f其中，B称为迭代矩阵。其计算精度可控，特别 适用于求解系数为大型稀疏矩阵(sparse matrices)的 方程组。5

AX b

x( k 1) Bx( k ) f问题:

(a) 如何建立迭代格式？(b) 向量序列{ x(k) }是否收敛以及收敛条件?

3.1Jacobi迭代法

2 例题分析:考虑解方程组

10 x1 x2 2 x3 7.2 x1 10 x2 2 x3 8.3 x x 5 x3 4.2 2 1其准确解为X*={ 1.1, 1.2, 1.3 }。

(1)

3.1Jacobi迭代法

2 例题分析:考虑解方程组

10 x1 x2 2 x3 7.2 x1 10 x2 2 x3 8.3 x x 5 x3 4.2 2 1其准确解为X*={1.1, 1.2, 1.3}。 建立与式(1)相等价的形式：

(1)

x1 0.1 x2 0.2 x3 0.72 x2 0.1 x1 0.2 x3 0.83 x 0.2 x 0.2 x 0.84 1 2 3

(2)

2 例题分析:考虑解方程组 建立与式(1)相等价的形式：

10 x1 x2 2 x3 7.2 x1 10 x2 2 x3 8.3 x x 5 x3 4.2 2 1其准确解为X*={1.1, 1.2, 1.3}。

x1 0.1 x2 0.2 x3 0.72 x2 0.1 x1 0.2 x3 0.83 x 0.2 x 0.2 x 0.84 1 2 3

据此建立迭代公式：

( ( x1(k +1) =0.1x2k ) +0.2x3k ) +0.72 (k +1) (k ) (k ) x2 =0.1x1 +0.2x3 +0.83 (k +1) ( x3 =0.2x1(k ) +0.2x2k ) +0.84

取迭代初值

( ( x1(0) x20) x30) 0

迭代结果如下表：迭 代 次数 0 1 2 3 4 5 6 7 8 9 1 0 11 1 2 1 3 1 4 1 5 x 0. 7 0 . 97 1 . 05 08 53 95 09 98 33 99

44 9 9 81 99 93 99 97 9 9 99 99 99 99 99 1. 1.1

x 0. 8 1. 0 1 5 7 8 5 3 50 9 83 3 94 4 9 8 1 99 3 99 7 9 9 9 99 9 99 9 1 . 1 .

2

x 0 . 8 1 . 1 24 8 82 8 41 3 80 3 93 3 97 7 99 2 99 7 99 9 99 9 99 9 1 . 1 .

3

1 1 1 1 1 1 1 1 1

1 . . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0

0 2 1 7 5 8 8 2 1 6 9 3 8 9 1 1

1 1 1 1 1 1 1 1 1

1 . 1. 1 . 1 9 . 1 9 . 1 9 . 1 9 . 1 9 . 1 9 . 1 9 . 1 9 . 1 9

0 3 7 1 4 9 7 2 1 6 9 3 8 9 2 2

1 1 1 1 1 1 1 1 1

1 . 1 . 2 . 29 . 29 . 29 . 2 9 . 29 . 29 . 2 9 . 29 . 29

0 4 5 2 2 8 9 5 7 4 5 1 7 9 3 3

§8.1 Jacobi迭代公式设方程组 AX=b , 通过分离变量的过程建立 Jacobi迭代公式，即

ai 1

n

ij

xj b , a 0 i i

( i 1,2, )n , ( i 1,2, )n ,

1 xi (bi aii

aj 1 j i

n

ij

x) j

由此我们可以得到 Jacobi 迭代公式：xi( k 1)n 1 (bi aij xik ) aii j 1 j i

( i 1,2, )n ,

雅可比迭代法的矩阵表示 a11 x1 a12 x2 ... a1n xn b1 a21 x1 a22 x2 ... a2 n xn b2 ... ... ... ... an1 x1 an 2 x2 ... ann xn bn 写成矩阵形式：aii 0 x 1 a x ... a x b 12 2 1n n 1 1 a11 1 a x ... a x b x2 21 1 2n n 2 a22 ... ... ... ... 1 xn a an1 x1 ... a nn 1 xn 1 bn nn

A=

D

U

Ax b ( D L U ) x b Dx ( L U ) x b x D 1 ( L U ) x D 1b

LJacobi 迭代阵

B

f

x( k 1) D 1 (L U ) x( k ) D 1b

§8.2 高斯-塞德尔迭代法 (AX=b)注意到利用Jacobi迭代公式计算xi( k 1) 时，已经计算好了( ( k x1k 1) , x2k 1) , , xi( 1 1)

的值，而Jacobi迭代公式并不利用这些最新的近似值计算， 仍用 (k ) (k ) (k )

x1 , x2 , , xi 1

这启发我们可以对其加以改进,即在每个分量的计算中尽量利用最新的迭代值，得到

xi( k 1)

i 1 n 1 (bi aij x (jk 1) aij x k ) (i 1, 2, , n) j aii j 1 j i 1

上式称为 Gauss-Seidel 迭代法. 13

§8.2 高斯-塞德尔迭代法( ( ( ( ( x1 k 1) 1 ( a12 x 2k ) a13 x 3k ) a14 x4k ) a1n x nk ) b1 ) a11 ( ( ( ( ( x 2k 1) 1 ( a 21 x1 k 1) a 23 x 3k ) a 24 x4k ) a 2 n x nk ) b2 ) a 22 ( ( ( ( ( x 3k 1) 1 ( a 31 x1 k 1) a 32 x 2k 1) a 34 x4k ) a 3 n x nk ) b3 ) a 33

… … …

…

( ( ( ( ( x nk 1) 1 ( a n1 x1 k 1) a n 2 x 2k 1) a n 3 x 3k 1) a nn 1 x nk 1) bn ) 1 a nn

写成矩阵形式： x( k 1) D 1 ( Lx( k 1) Ux( k ) ) D 1b ( D L) x( k 1) Ux( k ) b

x( k 1) ( D L) 1Ux( k ) ( D L) 1 b

Gauss-Seidel 迭代阵

B

f

高斯-塞德尔迭代法算例

考虑解方程组

10 x1 x2 2 x3 7.2 x1 10 x2 2 x3 8.3 x x 5 x3 4.2 2 1其准确解为X*={1.1, 1.2, 1.3}。

高斯-塞德尔迭代格式k k x1k 1 0.1x 2 0.2 x 3 0.72 k 1 k x 2 0.1x1k 1 0.2 x 3 0.83 k 1 k x 3 0.2 x1k 1 0.2 x 2 1 0.84

迭代次数 0 1 2 3 4 5 6 7 8

x1 0 0.72 1.04308 1.09313 1.099126 1.09989 1.099986 1.099998 1.1

x2 0 0.902 1.167188 1.195724 1.199467 1.199933 1.199992 1.199999 1.2

x3 0 1.1644 1.282054 1.297771 1.299719 1.299965 1.299996 1.299999 1.3