解线性方程组的迭代法

收敛条件 迭代格式收敛的充要条件是G的谱半径<1。对于
Jacobi迭代，我们有一些保证收敛的充分条件
an n1xn1 bn )
数学系 University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
x1(
k
1)
x2
(
k
1)
1 a11
(a12
x2
(k
)
1 a22
(a21x1(k )
a1n xn(k ) a23x3(k )
x2[i]=0; for(j=0;j<i;j++) {
x2[i] += A[i][j]*x1[j] } for(j=i+1;j<n;j++) {
x2[i] += A[i][j]*x1[j] } x2[i]=-(x2[i]-b[i])/A[i][i] } } 4、输出解x2
数学系 University of Science and Technology of China
b1) a1n xn(k )
b2 )
xn
(
k
1)
1 ann
(an1
x1(
Biblioteka Baidu
k
)
an
x (k
n1 n1
)
bn )
格式很简单：
x (k1) i
1 aii
(
i 1 j 1
aij
x
j
(k
)
n
aij x j (k )
j i 1
bi )
数学系 University of Science and Technology of China
很多实际问题，往往要我们求解很大的n的矩阵，而且这些矩阵 往往是稀疏矩阵就是这些矩阵含有大量的0元素。对于这类的矩 阵，在用直接法时就会耗费大量的时间和存储单元。因此我们 有必要引入一类新的方法：迭代法。
迭代法具有的特点是速度快。与非线性方程的迭代方法一 样，需要我们构造一个等价的方程，从而构造一个收敛序列， 序列的极限值就是方程组的根
DEPARTMENT OF MATHEMATICS
迭代矩阵
0
x1(k x2(k x3(k
1) 1) 1)
a21
a22 a31
xn(k
1)
a33 an1
ann
a12 a11
0
a32 a33 an2 ann
a13 a11 a23 a22
0
an3 ann
数学系 University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
对方程组 Ax b 做等价变换 x Gx g
如：令 A M N ，则 Ax b (M N )x b Mx b Nx x M 1Nx M 1b
易知，Jacobi迭代有 (D (D A))x b Dx (D A)x b x D1(D A)x D1b
G D1(D A) I D1A , g D1b
数学系 University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
DEPARTMENT OF MATHEMATICS
Jacobi迭代算法
1、输入系数矩阵A和向量b，和误差控制eps 2、x1={0,0,…..,0} , x2={1,1,…..,1} //赋初值 3、while( ||x1-x2||>eps) {
x1=x2; // x1 是第k步，x2是第k+1步 for(i=0;i<n;i++) {
DEPARTMENT OF MATHEMATICS
定义：（收敛矩阵） Gk 0
定理：Gk 0 (G) 1
矩阵G为收敛矩阵，当且仅当G的谱半径<1
由 (G) G
知，若有某种范数 G 1 则，迭代收敛 p
数学系 University of Science and Technology of China
a1n
a11 a2n
a22 a3n
x(k) 1
x(k) 2
x(k) 3
• •
•
a33
xn(k
)
•
0
数学系 University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
0
a21
数学系 University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
第6章 解线性方程组的迭代法
直接法得到的解是理论上准确的，但是我们可以看得出， 它们的计算量都是n3数量级，存储量为n2量级，这在n比较小的
时候还比较合适（n<1000 , 1G/s , 15秒 , 8M），但是对于现在的
则，我们可以构造序列 x(k1) G x(k) g
若 x(k) x * x* G x *g Ax* b 同时：x(k1) x* Gx (k) Gx* G(x(k) x*)
Gk1(x(0) x*)
所以，序列收敛 Gk 0
与初值的选取无关
数学系 University of Science and Technology of China
a21 a31
0 a32
a23 0
1 ann
an1
an2
an3
a1n a2n
a3n
0
a11
0
D
0
ann
D1( A D)
数学系 University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
a22 a31
a33 an1
ann
a12 a11
0
a32 a33 an2 ann
a13 a11 a23 a22
0
an3 ann
a1n a11
1 a11
a2n
a22 a3n
a33
0
1 a22
1
a33
0 a12 a13
DEPARTMENT OF MATHEMATICS
6.1 Jacobi迭代
a11x1
a1n xn
b1
an1x1 ann xn bn
x1
x2
1 a11
(a12 x2
1 a22
(a21x1
a1n xn a23x3
b1) a1n xn
b2 )
xn
1 ann
(an1x1