- Trang Chủ
- Toán học
- Thuật toán trung bình thành phần giải phương trình thưa, kích thước lớn
Xem mẫu
- KHOA HỌC CÔNG NGHỆ
THUẬT TOÁN TRUNG BÌNH THÀNH PHẦN
GIẢI PHƯƠNG TRÌNH THƯA, KÍCH THƯỚC LỚN
Phạm Kim Phượng*
ABSTRACT
This study is a literature review of parallel iterative algorithms, with emphasis on the component
averaging (CAV) algorithm as well as its numerical testing. The results show that: i) Instead of
orthogonal projections and scalar weights are used in Cimino algorithm by oblique projection and
diagonal weight matrix system. ii) The convergence of the component mean method does not depend
on whether the system is compatible or not. iii) A numerical test illustrating the convergence of CAV
using Matlab software.
Keywords: The Cimmino Algorithm, the CAV Algorithm.
Received: 8/11/2021; Accepted: 23/11/2021; Published: 12/12/2021
1. Đặt vấn đề bình thành phần
Ta đã biết bài toán chấp nhận lồi: “Tìm một Trong thuật toán song song, Cimmino là
điểm thuộc tương giao của các tập lồi đóng trong phương pháp cơ bản nhất. Trước hết, ta xét thuật
không gian Hilbert, biết rằng giao của chúng là toán Cimmino sau.
khác rỗng” là bài toán có nhiều ứng dụng trong Thuật toán Cimmino
lý thuyết tối ưu, xử lý ảnh, lý thuyết trò chơi… Chiếu x k ∈ R n lên các tập Ci , ta thu được các
Khi các tập lồi đóng là siêu phẳng, Kaczmarz điểm trung gian
(1937) và Cimmino (1938) đã đề xuất các thuật
x k +1,i = Pi ( x k ) , với i = 1,2,3,..., m . (1.1)
toán chiếu tuần tự và song song kinh điển để giải
Công thức lặp thu được là
bài toán nói trên. Von Neumann (1933) xét bài
toán tìm giao của hai không gian con đóng bằng m
x k + λk ∑ w i x k +1,i − x k
x k +1 = (1.2)
phương pháp chiếu xoay vòng. Censor (2000) đề i =1
xuất phương pháp chiếu tổng quát cho bài toán Trong trường hợp hệ phương trình tuyến tính,
chấp nhận lồi với các siêu phẳng. Giải hệ phương
với bất kì z ∈ R n , phép chiếu trực giao của z lên
trình đại số tuyến tính là trường hợp đặc biệt
của bài toán chấp nhận lồi. Nếu số phương trình Hi là
bằng số ẩn, các phương pháp lặp truyền thống bi − a i , z
Pi ( z )= z + ai
như Jacobi, Gauss-Seidel, lặp giảm dư, vv.... tỏ ra ai
2
2
khá hữu hiệu trong việc tìm gần đúng nghiệm của
hệ phương trình. Phương pháp trung bình thành Ở thuật toán Cimmino, ta xét với w i = 1/ m ,
phần (CAV) là một kỹ thuật lặp song song mới để bước lặp x k +1 là trung bình các phép chiếu của x k
giải hệ này. lên tập lồi Ci . Các bước thuật toán như sau
2. Nội dung nghiên cứu Bước 0 : Cho x 0 ∈ R n bất kỳ .
2.1. Tổng quan lý thuyết về thuật toán trung Bước thứ k+1 : Cho x k ta thu được
m 1
* ThS Bộ môn Toán, Khoa Cơ sở-Cơ bản, Đại Học Hàng x k + λk ∑ x k +1,i − x k
x k +1 =
Hải Việt Nam i =1 m
TẠP CHÍ QUẢN LÝ VÀ CÔNG NGHỆ - Số 19 Quý 4/2021 55
- KHOA HỌC CÔNG NGHỆ
m 1 Để chứng minh sự hội tụ của (1.5), phần tiếp
x k + λk ∑ Pi x k − x k
= ( ) theo, ta thay phép chiếu trực giao lên siêu phẳng
i =1 m
bởi phép chiếu xiên theo ma trận trọng số.
m k b − ai , x k Phép chiếu xiên tổng quát lên siêu phẳng
x k
x k + λk ∑ i
i
= + a − x Giả sử G là ma trân n×n, đối xứng, xác định
2
i =1 m m ai
2 dương, ta đặt x G = x,Gx .Phép chiếu xiên của
2
m b − a ,x
i k
m xk k một phần tử z lên H ứng với ma trận G là điểm
=x + λk ∑ − x + λk ∑
k i
ai
= m
i 1= i 1 m a i 2
z ) argmin { x − z G / x ∈ H }
PHG ( z ) ∈ H với PHG (=
2
Nhận xét
m bi − a , x
i k
= x + λk ∑ k
2
a i
Ta thấy rằng thuật toán Cimmino với phép
i =1 m ai chiếu xiên theo ma trận đối xứng, xác định
2
Vậy dương G với hệ Ax = b tương đương với thuật
toán Cimmino với phép chiếu trực giao trong hệ
λk m bi − a , x i
i k
x= x + ∑
k +1 k
a A G −1/ 2 x ’ = b . (với x ’ = G1/ 2 x )
m i =1 m a i 2
2 Thật vậy
Với j = 1,2,.., m Phương trình của siêu phẳng H ≡ Hi đối với hệ
λk m bi − a , x i
i k
tọa độ ( x1, x2 ,..., xn ) là a i , x = bi
+1
x kj = x kj + ∑
m i =1 m a i 2
aj
Phép chiếu trực giao của z’ lên hệ tọa độ
2
Viết dưới dạng ma trận, ta thu được ( x , x ,..., x )
'
1
'
2
'
n là
( ),
1
x k +1
x + λk A D b − x
= k T k −
bi − G 2 a i , z ' 1
( )
−
với
=b ( bi ) ∈ R m và P z' = z' +
1 2
G 2 ai
−
G 2 ai
1 1 1 1
D= diag
, ,..., (1.3)
m a 1 2
a 2 2
a m 2
2 2 2 Mà z 0 = G1/ 2 z nên
1
Trong trường hợp A là ma trận thưa tức là −
bi − G 2 a i , z '
số phần tử a1 j , a 2 j ,..., a m j khác 0 rất nhỏ, m lại 1
1
−
1
2 i
P G 2= z G2z + 2
G a
1
là số rất lớn nên ta thay thế 1/ m bởi thừa số −
G a2 i
chỉ phụ thuộc vào các phần tử khác 0 trong tập
{a1j ,a2j ,..., amj } Với mỗi j = 1,2,..., n , s j là số phần 1 bi − a i , z ' − 1 i
tử khác 0 trong cột j của ma trận A , thay thế 1/ m = G z + G 2a
2
2
ai
ở công thức (1.3) ta được G −1
m b − a ,x
i k
λ Do đó
x kj + k ∑
+1 i
x kj = a ij (1.4)
s j i =1 m a i 2
−
1 1
−
1
21 bi − a i , z −1 i
2 G 2
PG 2
( z ) = G 2
P G z =z +
i 2
G a PHG ( z )
=
a
Phép lặp trong công thức (1.3) là trường hợp G −1
đặc biệt của m Suy ra
1 1
m bi − a , x i k −
G 2 PG 2 = PHG
x = x + λk ∑ w i
k +1 k
a i
2 (1.5)
i =1 ai
2
Vậy PHG và P tương đương nhau.
với các trọng số {w i }i =1 với mọi i và ∑w = 1.
m
i =1
i Với ma trận đường chéo G = diag {g1, g 2 ,..., g n }
56 TẠP CHÍ QUẢN LÝ VÀ CÔNG NGHỆ - Số 19 Quý 4/2021
- KHOA HỌC CÔNG NGHỆ
,với các phần tử đường chéo có thể bằng 0, ta xét Khi đó
phép chiếu xiên lên H theo G. Nếu có phần tử x k + λk AT DS b − Ax k (1.7)
x k +1 = ( )
đường chéo bằng 0 thì sẽ không thỏa điều kiện
Sự hội tụ trong thuật toán CAV
của công thức (1.4). Vì thế, ta có định nghĩa sau
Định nghĩa 2.1 Ta đã chứng minh với λk = 1; ∀k > 0 , thì dãy
Cho G = diag {g1, g 2 ,..., g n } với {x } k
hội tụ không phụ thuộc vào giá trị ban đầu
k ≥0
g j > 0∀j =1,2,..., n . H = b} là x , hệ tương thích hay không tương thích.
{ x ∈ R | ha, x i = n
0
siêu phẳng với a =( a j ) ∈ R n , b ∈ R . Giả sử g j = 0 Ta lần lượt xét các bổ đề sau.
Bổ đề 2.1 Nếu {Gi }i =1 là SPO theo ma trận A
m
khi và chỉ khi a j = 0 . Khi đó, phép chiếu xiên
tổng quát của z ∈ R n lên H theo ma trận G được thì ∀x, z ∈ R m ta có
định nghĩa như sau
m m
2 2 2
∑ PHGi i ( z ) −=
x
Gi
∑ PHGi i ( z ) − T ( z ) + T ( z ) − x
Gi 2
b − a, z aj
( )
=i 1=i 1
PHG ( z )= z j + m . m nếu gj = 0,
j g Chứng minh
∑
=l 1,g j ≠ 0
al2 / g j j
Xét biểu thức
( )
m
Thuật toán CAV ∑
2
PHG ( z ) − x − PHG ( z ) − T ( z )
2
i i
Thuật toán CAV được đề xuất bởi Y. Censor; i =1
G G i
i
i
i
D. Gordon và R. Gordon (2001), có ba đặc điểm
= ∑ { P ( z ) − x,G ( P ( z ) − x ) − P ( z ) − T ( z ) ,G ( P ( z ) − T ( z ) ) }
m
Gi Gi Gi Gi
Hi i Hi Hi i Hi
sau: i =1
∑{ x }
m
2
− T ( z ) G + 2 Gi PHGi i ( z ) ,T ( z ) − x
2
Mỗi phép chiếu trực giao lên Hi t) được thay thế = Gi i
i =1
bằng phép chiếu xiên theo ma trận Gi . m m m
=
Các trọng số vô hướng {wi} được thay thế bởi các ma
=i 1=i 1
∑ x,Gi x −∑ T ( z ) ,Gi PHGi i − + 2∑ Gi PHGi i ( z ) ,T ( z ) − x
=i 1
trận đường chéo có trọng số {Gi } . x, x
=− T ( z ) ,T ( z ) + T ( z ) ,T ( z ) − x + T ( z ) ,T ( z ) − x
Các trọng số tỷ lệ nghịch với số phần tử khác 0 trong x, x
=− T ( z ) ,T ( z ) + T ( z ) ,T ( z ) − x
mỗi cột
Các bước cơ bản của thuật toán trung bình = x − T ( z ) , x + T ( z ) ,T ( z ) − x
thành phần: 2
Bước 0 : Cho x o ∈ R n bất kỳ. = T ( z ) − x,T ( z ) − x= T ( z ) − x 2
Suy ra
Bước thứ k+1 : Khi đó x k +1 được tính theo m 2 m 2 2
công thức ∑ PHG ( z ) − = x
G
=i 1=i
∑
i 1
PHG ( z ) − T ( z ) + T ( z ) − x 2
i
i
G i
i
i
nbi − a i , x k i
x k +1
j x + λk ∑ n
= k
j a j ≠ 0 (1.6) Bổ đề 2.2 Với mọi dãy {x k }k ≥0 trong thuật toán
( )
2
i =1
∑ aj s j
i
1.3.1 với λk =1∀k > 0 , thì dãy F ( x k ) { }
m
là dãy
l =1,g il ≠0
{λk }k > 0 là
i =1
trong đó các tham số giảm dư,
không tăng và lim x k +1 − x k= 0, x → ∞
{s j }
n 2
l =1
đã định nghĩa ở trên. Chứng minh
Ta đặt Ta có m
( ) ∑ P (x ) − x ( )
2 2
S = diag ( s1, s2 ,..., sn ) , xk
F= Gi
Hi
k k
+ T xk − xk
Gi 2
i =1
1 1 1 Lại có
Ds = diag , ,...,
1 2 2 2 2 m m
x k + λk ∑ Gi PHGi i x k −∑ Gi x k λk = ( ) ( )
m
a a a x k +1 = T x k +1
s s s
=i 1=i 1
TẠP CHÍ QUẢN LÝ VÀ CÔNG NGHỆ - Số 19 Quý 4/2021 57
- KHOA HỌC CÔNG NGHỆ
Ta kí hiệu tập các giá trị cực tiểu của hàm F là
(vì
m
∑G i =I)
Φ= {x ∈ F ( x ) ≤ F ( x ) ∀x ∈ } n
i =1
Định lý 2.1 Nếu hàm F đạt các giá trị cực tiểu,
Từ PHG = argmin x − x k + 1
i
| ∀x ∈ Hi o ta có
i G Φ6 =ϕ thì dãy {x k } với λk = 1∀k > 0 hội tụ
m k ≥0
( ) ≥ ∑ P (x ) − x
2 2
k +1 k +1
F x k Gi
Hi + x k +1 − x k đến một giá trị cực tiểu của F.
Gi 2
i =1
Chứng minh
( ) ( )
2
= F x k +1 + x k +1 − x k ≥ F x k +1
2 Vì {x k }k ≥0 bị chặn nên nó có các điểm hội
Suy ra {F ( x k )} là dãy không tăng, bị chặn. Do tụ.Ta sẽ chỉ ra rằng mọi điểm hội tụ của {x } k
k ≥0
đó F ( x k
) → F (k → ∞ ) . * là điểm cực tiểu.
Giả sử x* là một điểm hội tụ của. Lấy x ∈ Φ . Áp
Khi đó, lim x k +! − x k 0 .
=
k →∞ 2
dụng bổ đề 3.1 với
= *
y x= ,G G=
i ,H i ,z
H= PHG ( x ) i
i
Bổ đề 2.3 Giả sử H ∈ R n là siêu phẳng. G là ta có
ma trận đường chéo, không âm. Cho z là một ( )
PHGi i x * − x *
2
≤ PHGi i ( x ) − x *
2
+ PHGi i ( x ) − PHGi i x *( )
2
Gi Gi Gi
điểm thuộc H. Khi đó, với mọi y ∈ R n ta có
2 2 Suy ra
PHG ( y ) − y ≤ z − y G + z − PHG ( y )
2
m m m
∑ P (x ) − x ( )
2 2 2
≤∑P (x) − x + ∑ PHGi i ( x ) − PHGi i x *
G G Gi * * Gi *
Hi Hi Gi
Gi Gi
Chứng minh =i 1 = i 1= i 1
2
Xét hàm E ( u ) = u − y G + u − PH G ( y ) G
2 Nên
m
2 m
( ) ( )
2 2
F x * ≤ ∑ PHGi i ( x ) − T ( x ) − ∑ PHGi i ( x ) − PHGi i x * + T ( x ) − x*
Khi đó E ( u ) sẽ được viết dưới dạng =i 1=
Gi
,
i 1
Gi 2
E ( u ) =hu,α i + β với α ∈ R , β ∈ R Do đó
n
( ) ( )
2
Nên E ( u ) là hàm lồi. F x* ≤ F ( x ) + T ( x ) − x* − T x*
2
Đặt uλ = λ z + (1 − λ ) PHG ( y ) . Vậy
Theo bất đẳng thức Jensen
( ) ( )
2
F x* + T x* ≤ F ( x ) + T ( x ) − x*
2
( 2
E ( uλ ) ≤ λ z − y G − z − PHG ( y ) + (1 − λ )
G ) PHG ( y ) − y
2
G
Vì lim x k =x * ,T ( x k ) =x k +1 ⇒ T ( x * ) =x * .
2
Suy ra k →∞
Suy ra F ( x * ) ≤ F ( x ) .
2 2
z − y G z − PHG ( y ) − PHG ( y ) − y
2
G G
Vậy dãy {x k }k ≥0 với hội tụ đến một giá trị cực
tiểu của F.
≥
λ(
1
u λ − y G − PHG ( y − y )
2 2
G ) − λ1 u λ − PHG ( y )
2
G
. Thử nghiệm số
1
(vì vế phải của bất đẳng thức trên → 0 khi Bài toán: Tính ∫ K ( t,s ) x ( s ) ds = y ( t )
λ → +0 . ) 0
Suy ra 1 t+s
Với K (t ; s ) =+ + ts
3 2
2 2
(y ) − y G (y ) G
G 2 G
PH ≤ z−y G + z−P H
Định nghĩa 2.2 Dãy {x k }k ≥0 là dãy Fejér theo 1 t 1
Suy ra y (t ) = + a + + t b với
tập Ω, Ω ⊆ R n nếu với mọi x ∈ Ω , ta có 3 2 2
1 1
x − x k +1 6 x − x k với k > 0 (1.8) a = ∫ x( s )ds và b = ∫ sx( s )ds
2 2
Khi đó, dãy Fejér {x k
} bị chặn. 0 0
k ≥0
Phương pháp: Ta chia đoạn [0;1] thành N
58 TẠP CHÍ QUẢN LÝ VÀ CÔNG NGHỆ - Số 19 Quý 4/2021
- KHOA HỌC CÔNG NGHỆ
phần và sử dụng phương pháp trùng khớp. là khá lớn.
1
3. Kết luận
∫0 K ( ti ,s ) x ( s ) ds = y ( ti ) Bài báo trình bày một cách có hệ thống phương
Tính tích phân trên bằng công thức hình thang, pháp trung bình thành phần để giải hệ phương
ta có trình tuyến tính thưa, kích thước lớn. Kết quả cho
1 thấy phương pháp trung bình thành phần và các
2N
{ K ( ti ; t0 ) x0 + 2 K ( ti ; t1 ) x1 + ... + 2 K ( ti ; t N −1 ) xNkết K ( tihội
−1 +quả }=
; t N )tụxNcủa yi không phụ thuộc vào hệ
nó
tương thích hay không tương thích. Ví dụ minh
( ti ; t1 ) x1 + ... + 2 K ( ti ; t N −1 ) xN −1 + K ( ti ; t N ) xN } = yi họa phép lặp song song được thử nghiệm số trong
môi trường Matlab. Trong tương lai, tác giả sẽ tập
Ta viết phương trình trên dưới dạng sau trung vào nghiên cứu, tính toán, thử nghiệm một
N số phương pháp song song để giải bài toán đại số
∑ aij x j = 2 Nyi
j =0 tuyến tính kích thước lớn và điều kiện xấu.
i = 0,1,..., N
Tài liệu tham khảo
K ij ; j = 0; N 1. Y.Censor, D.Gordon, R.Gordon (2001),
Với aij =
An efficient iterative parallel algorithm for
2 K ij ;1 ≤ j ≤ N − 1
large sparse unstructured problems, Parallel
1 1 ij i j
Và K ij = + ( i + j ) + 2 ; ti = ; t j = Computing 777-808
3 2N N N N 2. Y.Censor, T.Elfving (2002), Block - iterative
Thử nghiệm số với algorithms with diagonally scaled oblique
1 projections for the linear feasibility problem,
x ( t ) = sin ( 2π t ) a = 0, b = −
*
2π . SIAM.
Suy ra 3. P.P.B. Eggermont, G.T.Herman, A.Lent
* 2t + 1 (1981), Iterative algorithms for large partitioned
y = −
4π . linear systems, with applications to image
Áp dụng thuật toán CAV, ta thu được bảng kết reconstruction, Linear Algebra Appl 37-67.
quả sai số của nghiệm gần đúng của hệ phương 4. H.H.Bauschke, J.M.Borwein (1996),
trình tuyến tính và nghiệm đúng của tích phân On projection algorithms for solving convex
sau đây. feasibility problems, SIAM 367-426.
Thử nghiệm số= với λ = 1.00, x 0 0 , sai số 5. E.John (2005), Handbook of parallel
của phép lặp CAV là 10 , tức là phép lặp dừng computing and statistics, 199 - 220.
−4
nếu x ( k +1) − x ( k ) ≤ 10−4 . 6. T. T. Vo, N. T. Luong, and D. Hoang,
“MLAMAN: a novel multi-level authentication
Bảng: Kết quả thử nghiệm số
model and protocol for preventing wormhole
N 100 300 500 1000 1500
attack in mobile ad hoc network,” Wireless
Sai số 7.0342 12.2262 15.7949 22.3491 27.3766 Networks, vol. 25, no. 7, pp. 4115–4132, 2019.
Nhận xét: Bài toán tính tích phân trên là bài 7. L. Sánchez-Casado, G. Maciá-Fernández,
toán đặt không chỉnh. Đây là bài toán khó. Trong P. García-Teodoro, and N. Aschenbruck,
việc tính toán các ví dụ trên đều có sai số rời rạc “Identification of contamination zones for
hóa và sai số của phép lặp. Vì vậy kết quả tính Sinkhole detection in MANETs,” Journal of
sai số giữa nghiệm gần đúng của hệ đại số tuyến Network and Computer Applications, vol. 54, pp.
tính và nghiệm đúng của phương trình tích phân 62–77, 2015.
TẠP CHÍ QUẢN LÝ VÀ CÔNG NGHỆ - Số 19 Quý 4/2021 59
nguon tai.lieu . vn
