( k 1) (k ) (k ) x2 (8 x1 x3 ) / 10
( k 1) (k ) (k ) x3 (13 x1 x2 ) / 15
x
x
( k 1) 1
(1 ) x
(1 ) x
(k ) 1
(7 x
(k ) 2
x )/9
(k ) 3
L6 3, L12 3.10582854, L24 3.13262861, L48 3.13935020
4 1 L(1) L n 3 2n 3 Ln (1) (1) L(1) 3.141 10472, L 3.141 56197, L 6 12 24 3.14159073
x M 1 Nx M 1b, 其中A M N
对任意的f 和任意的初始 向量X 迭代法收敛的充 分必要条件是 ( B ) 1和 充分条件是||B|| 1
(0)
中止准则
|x
(k ) *
12:47
|| B || L (k ) (k ) ( k 1) || X ( k ) X ( k 1) || x | |x x | || X X * || 1 || B || 1 L
《数值分析》 10
逐次超松驰迭代法
线性方程组的条件数
12:47
1/33
统一的不动点框架 迭代法构造 x ( x) 收敛条件(局部vs全局)
x *为 ( x )的不动点, ( x ) 在x *的某邻域N (x * )连续 且 | ( x * ) | 1, 则迭代法 对任意x (0) N (x * )收敛
0 a12 a1n 0 a 0 U L 21 0 a n 1, n 0 a n1 a n , n 1 0
12:47
( k 1) 2
(k ) 2
(8 x
( k 1) 1
x ) / 10
(k ) 3
( k 1) (k ) ( k 1) ( k 1) x3 (1 ) x3 (13 x1 x2 ) / 15
12:47
7/33
A=
D
-L
-U
a11 a 22 D a nn
1 ( x ) 0 1 ( x )
加速收敛序列
( ( x )) ( x ) ( x ) ( x) x
2
x n 1
12:47
( ( xn ) xn ) xn ( ( xn )) 2 ( xn ) xn
5/33
12:47
14/33
预备知识:

思路:
i
det( A)
a11
f ( ) det( I A) a n1
a1n ( 1 ) ( n )
ann
上式中令 =0既得结论。
12:47
15/33
定理4.7 SOR方法收敛的必要条件是0< <2 。
松弛技术
xi( k 1)
(1 ) x x
k
( k 1)
(k ) a x ij j ] n
i 1 1 (1 ) xi( k ) [bi aij x (jk 1) aii j 1
j i 1
松弛因子通常的范围是(1,2), 故称为超
12:47
( k 1)
D ( LX
1
( k 1)
UX
(k )
b)
9/33
SOR迭代矩阵
xi( k 1) (1 ) xi( k )

aii
[bi aij x (jk 1)
j 1
i 1
j i 1
(k ) a x ij j ]
n
X
( k 1)
(1 ) X
(k )
D ( LX
1
1
( k 1)
UX
(k )
b)
BSOR ( D L) [(1 ) D U ]
Gauss-Siedel方法是SOR方法的特例。
A M N, M 1

( D L), N
1

[(1 ) D U ]
12:47
6/33
例 1 9 x1 x 2 x 3 7
x1 10 x 2 x 3 8 x x 15 x 13 2 3 1
x1 ( 7 x 2 x 3 ) / 9 x 2 (8 x1 x 3 ) / 10 x (13 x x ) / 15 1 2 3
迭代 格式 谱半径
Jacobi 0.6244
GaussSOR Seidel （w=1.13） 0.4166 0.2600
12/33
%%%triu(X,K) is the elements on and above %%%the K-th diagonal of X D = diag(diag(A));L = -tril(A,-1);U = -triu(A,1);
| det( BSOR ) || 1 | 12
n
n ( ( BSOR )) 1。
n
12:47
16/33
定理4.8 若A是实对称正定矩阵, 则当0< <2时, SOR方法收敛。 证明: 由 A = D – L –
1 T T B ( D L ) ((1 ) D L ) L SOR
11/33
12:47
谱半径的比较 算例
5 1 x 3 1 1 2 2 x 3 1 3 1 2 2 x3 1 1 3 1 1 3 1 x4 1 1 3 1 x5 3 2 1 5 1 3 x6 2 2
k
( k 1)
x )
( k 1) k ( x x ) 适当选取平均化系数 调整校正量
以将xk加工成某个更高精度结果。这种基于校 正量的调整或松动的方法, 称之为松弛技术。
3/33
千古绝技割圆术
祖冲之 3.1415926 3.1415927
内接多边形周长逼近, 需要内接正24576边形
证: 由于SOR方法收敛, 所以 ( BSOR ) 1。
det( BSOR ) det(( D L) ((1 ) D U ))
1
=det(( I D L) D ((1 ) D U ))
1 1 1
=det(( I D 1 L)1 ((1 ) I D 1U )) =(1- )n
(k )
(k ) j
x1 b1 0 ( k 1) b a x2 2 21 ( k 1) ann xn a bn n1
( k 1)
0 an 2
12:47
13/33
%%%Jacobi迭代矩阵D-1(L+U) eig(inv(diag(diag(A)))*(-triu(A,1)-tril(A,-1))) %%%GS迭代矩阵(D+L)-1U eig(inv(diag(diag(A))+tril(A,-1)*(-triu(A,1))) %%%%迭代格式 iD = diag((diag(A)).^(-1)); x = x - iD*(A*x - f); x = (D-L)\(U*x + f); x = (D-w*L)\(w*U*x +(1-w)*D*x+ w*f);
( k 1) (k ) (k ) x1 (7 x2 x3 )/ 9
( k 1) ( k 1) (k ) x2 (8 x1 x3 ) / 10
( k 1) ( k 1) ( k 1) x3 (13 x1 x2 ) / 15
( k 1) (k ) (k ) x1 (7 x2 x3 )/ 9
8/33
回顾高斯赛德尔迭代矩阵表示
aii x
a11 a22
( k 1) i
[bi aij x
j 1
i 1
( k 1) j

j i 1
( k 1)
a
n
ij
x ]
a1n x1 x( k ) 2 an1,n (k ) 0 xn
x1 0 a12 ( k 1) 0 x2 ( k 1) 0 xn
D X(k+1) = LX(k+1) + UX(k) +b
x
( k 1) i
1 ( k 1) (k ) [bi aij x j aij x j ] aii j 1 j i 1
12:47
17/33
x ((1 ) D L ) x (1 ) p a T x ( D L) x p a
2/33
松弛思想
目标值x*有两个精度相当的近似值x和 x ( k 1) , 如果将这两个近似值加工成更高精度的结果呢? 改善精度的一种简便而有效的办法是,取两者的 某种加权平均值作为改进值,即令
x 亦即 x
( k 1) ( k 1)
(1 ) x x
k
( k 1) k
x ( x
10/33
程序片段:
Matlab code : SOR迭代法 function [x,iter]=sor(A,b,x0,nmax,tol,omega) %SOR method [n,m]=size(A); if n~= m, error('Only square systems'); end iter=0; r=b-A*x0; r0=norm(r); err=norm(r); xold=x0; while err > tol && iter < nmax iter = iter + 1; for i=1:n s=0; for j = 1:i-1, s=s+A(i,j)*x(j); end for j = i+1:n, s=s+A(i,j)*xold(j); end x(i,1)= (1-omega)*xold(i)+omega*(b(i)-s)/A(i,i)%% x(i,1)=(b(i)-s)/A(i,i); end xold=x; r=b-A*x; err=norm(r)/r0; end