ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ QUỲNH GIANG
THUẬT TOÁN ĐIỂM GẦN KỀ QUÁN TÍNH HIỆU
CHỈNH CHO ÁNH XẠ ĐƠN ĐIỆU H-LIÊN TỤC
VÀ NGƯỢC ĐƠN ĐIỆU MẠNH
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ QUỲNH GIANG
THUẬT TOÁN ĐIỂM GẦN KỀ QUÁN TÍNH HIỆU
CHỈNH CHO ÁNH XẠ ĐƠN ĐIỆU H-LIÊN TỤC
VÀ NGƯỢC ĐƠN ĐIỆU MẠNH
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60.46.36
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TS. NGUYỄN BƯỜNG
Thái Nguyên - Năm 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i
Mục lục
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Lời cảm ơn 1
Mở đầu 2
Một số ký hiệu và chữ viết tắt 4
1 Một số khái niệm cơ bản 5
1.1 Không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Ánh xạ đơn điệu . . . . . . . . . . . . . . . . . . . . . . . 6

Tác giả
Nguyễn Thị Quỳnh Giang
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
MỞ ĐẦU
Rất nhiều bài toán của thực tiễn khoa học, công nghệ dẫn đến bài toán
đặt không chỉnh (ill- posed) theo nghĩa Hadamard, nghĩa là bài toán (
khi dữ kiện thay đổi nhỏ) hoặc không tồn tại nghiệm, hoặc nghiệm không
duy nhất, hoặc nghiệm không phụ thuộc liên tục vào dữ kiên ban đầu.
Do tính không ổn định của bài toán đặt không chỉnh nên việc giải số
của nó gặp khó khăn. Lý do là một sai số nhỏ trong dữ kiện của bài toán
có thể dẫn đến một sai số bất kì trong lời giải
Mục đích của bài báo này là giới thiệu một phương án hiệu chỉnh của
thuật toán điểm gần kề quán tính tìm một phần tử chung của các tập
nghiệm của bất đẳng thức biến phân với toán tử đơn điệu và h-liên tục
và một họ hữu hạn các ánh xạ ngược đơn điệu mạnh {A
i
}
N
i=1
từ một tập
đóng lồi K vào không gian Hilbert H.
Thuật toán điểm gần kề quán tính được đề xuất bởi Alvarez [1] cho
bài toán cực trị lồi. Sau đó Attouch và Alvarez xét mở rộng thuật toán
đó cho toán tử đơn điệu cực đại [2]. Mới đây Moudafi sử dụng thuật toán
này để giải bất đẳng thức biến phân [9], Moudafi và Elisabeth [8] nghiên
cứu thuật toán này với việc sử dụng, mở rộng toán tử đơn điệu cực đại và
Moudafi cùng Oliny xét kết hợp thuật toán này với quá trình tách [7]. Kết
quả của nghiên cứu này vẫn là sự hội tụ yếu trong không gian Hillbert.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Miền xác định của toán tử Aký hiệu là D(A)
Ma trận chuyển vị của ma trận Aký hiệu là A
T
Toán tử liên hợp của A ký hiệu là A
∗
Dãy {x
n
} hội tụ mạnh tới x ký hiệu là x
n
→ x
Kí hiệu tập nghiệm của A (u
∗
) , x − u
∗
 ≥ 0 là VI(K,A)
Ngược đơn điệu mạnh là λ
i
Một họ hữu hạn các ánh xạ λ
i
ngược đơn điệu mạnh từ K vào H là
{A
i
}
N
i=1
Tập điểm bất động của ánh xạ T là F(T )
Kí hiệu tập không ánh xạ B là S
B
{C
n

Ví dụ 1.1. L
2
[a,b]
là không gian các hàm bình phương khả tích trên [a,b]
f :
b

a
f
2
(x) dx < +∞ với f ∈ L
2
[a,b]
là một không gian Hilbert với tích vô
hướng
f, g =
b

a
f (x) g (x) dx
và chuẩn
f
L
2
[a,b]
=


b


ngược đơn điệu mạnh nếu
tồn tại một số dương λ
i
sao cho
A
i
(x) − A
i
(y), x − y ≥ λ
i
A
i
(x) − A
i
(y)
2
, (1.2)
với mọi x, y ∈ K. Dễ dàng nhận thấy mọi ánh xạ λ
i
ngược đơn điệu mạnh
A
i
là đơn điệu và Lipschitz liên tục với hằng số 1/λ
i
. Do đó ,ta chỉ xét
trường hợp 0 < λ
i
< 1. Cho {A
i
}

chứa trong lớp bài toán (1.3).
Trường hợp , khi A là λ ngược đơn điệu mạnh A
1
= I − T ở đây T là
không giãn.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
1.4 Bài toán đặt không chỉnh
1.4.1 Khái niệm về bài toán đặt không chỉnh
Định nghĩa 1.3. Cho A là một toán tử từ không gian X vào không
gian Y. Bài toán ở dạng phương trình toán tử
A (x) = f, (1.4)
được gọi là bài toán đặt chỉnh (well-posed) nếu
1. Phương trình A (x) = f có nghiệm với mọi f ∈ Y ;
2. Nghiệm này duy nhất;
3. Nghiệm phụ thuộc liên tục vào dữ kiện ban đầu.
Nếu ít nhất một trong các điều kiện trên không thỏa mãn thì bài toán
(1.4) được gọi là bài toán đặt không chỉnh (ill-posed).
Định nghĩa 1.4. Cho A là một toán tử từ không gian X vào không gian
Y. Bài toán (1.4) được gọi là bài toán đặt không chỉnh nếu nghiệm của
nó không phụ thuộc liên tục vào dữ kiện ban đầu.
Chú ý 1.1. Bài toán tìm nghiệm x phụ thuộc vào dữ kiện ban đầu f,
có nghiệm là x = R(f), được gọi là ổn định trên cặp không gian (X,
Y) nếu với mỗi ε > 0, ∃δ (ε) > 0 sao cho từ ρ
Y
(f
1
, f
2
)  δ (ε) cho ta

δ
, δ) ta cần phải tìm một phần tử x
δ
∈ X
hội tụ đến nghiệm chính xác x
0
của (1.4) khi δ → 0. Phần tử x
δ
có tính
chất như vậy gọi là nghiệm xấp xỉ bài toán đặt không chỉnh (1.4).
Chú ý 1.3. Gọi x (δ)là nghiệm của (1.1) với f thay bởi f
δ
( giả thiết rằng
nghiệm tồn tại ). Khi δ → 0 thì f
δ
→ f nhưng với bài toán đặt không
chỉnh thì x
δ
nói chung không hội tụ đến x.
Ví dụ 1.2. Nếu A là toán tử liên tục mạnh thì bài toán (1.4) (vô hạn
chiều) nói chung là bài toán đặt không chỉnh. Thật vậy, giả sử dãy {x
n
}
chỉ hội tụ yếu, không hội tụ mạnh đến x và y
n
= A(x
n
), A(x). khi đó,
do tính liên tục mạnh của A suy ra y
n

[a, b]
ϕ (x) → f
0
(x) =
b

a
K (x, s) ϕ (s) ds
Sự thay đổi của vế phải được đo bằng độ lệch trong không gian
L
2
[a, b], tức là khoảng cách giữa hai hàm f
0
(x),f
1
(x) trong L
2
[a, b]
được cho bởi
ρ
L
2
[a,b]
(f
0
, f
1
) =



0
(x) + N sin (ωx)
Với N bất kì và ω đủ lớn thì khoảng cách giữa hai hàm f
0
và f
1
trong
không gian L
2
[a, b] là
ρ
L
2
[a,b]
(f
0
, f
1
) = |N|



b

a


b

a

K
max
1
ω
cos (ωs)


b
a

2
dx

1
2
≤
|N|K
max
c
0
ω
ở đâyc
0
là một hằng số dương. Ta chọn N và ω đủ lớn tùy ý nhưng
N/ω lại nhỏ. Trong khi đó
ρ
C[a,b]
(ϕ
0
, ϕ

ρ
L
2
[a,b]
(ϕ
0
, ϕ
1
) =


b

a
|ϕ
0
(x) − ϕ
1
(x)|
2
dx


1
2
= |N|


b


0
, ϕ
1
) lại rất lớn.
Ví dụ 1.4. Xét bài toán cực tiểu hàm ϕ (y) = y trên đoạn thẳng y =
λ
0
x + y
0
nằm trong góc phần tư thứ nhất của mặt phẳng 0xy. Ở đây λ
0
và y
0
là những số cho trước và y
0
> 0. Giả sử λ
0
= 0 và thay cho λ
0
ta
có λ
δ
: |λ
δ
− λ
0
| < δ. Ta xét các trường hợp:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
• Trường hợp 1: λ

δ
< 0. Ta có λ
δ
= λ
2
= λ
0
−
δ
2
. Trong trường hợp
này, thay cho đường thẳng y = y
0
ta có đường thẳng d
2
: y = λ
2
x+y
0
.
Do λ
δ
< 0 cho nên đường thẳng d
2
cắt trục 0x tại một điểm x
2
(δ)
nào đó. Giá trị cực tiểu của phiếm hàm ϕ (y) trên một phần của d
2
nằm trong vùng {x  0, y  0} đạt được tại điểm x

0
> 0,
ở đây y
0
có thể lớn tùy ý, bài toán này không ổn định.
Ví dụ 1.5. Xét phương trình toán tử A(x) = f với A là một ma trận
vuông cấp M = 5 được xác định bởi








1 1 1 1 1
1 1.0001 1 1 1
1 1 1.0001 1 1
1 1 1 1.0001 1
1 1 1 1 1.0001








và vế phải
f =


1 1 1 1 1
1 1.0001 1 1 1
1 1 1.0001 1 1
1 1 1 1.0001 1
1 1 1 1 1








và
f =

5 5.0001 5.0001 5.0001 5

T
∈ R
5
.
thì phương trình có vô số nghiệm.
Nếu
A = A
h
2
=


Ta thấy một thay đổi nhỏ của hệ số trong phương trình ban đầu đã kéo
theo những thay đổi đáng kể của nghiệm.
Vì tính không duy nhất của nghiệm của bài toán A(x) = f, nên người
ta thường có một tiêu chuẩn cho sự lựa chọn của nghiệm. Ta sẽ sử dụng
nghiệm x
0
có x
∗
− chuẩn nhỏ nhất, nghĩa là ta tìm nghiệm x
0
∈ X thỏa
mãn
A(x
0
) = f,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
và
x
0
− x
∗
 = min {x − x
∗
 : A (x) = f} .
Bằng cách chọn x
∗
, ta có thể có được nghiệm mà ta muốn xấp xỉ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15

→ ∞ thì x ∈ S .Khi đó tồn tại
ˆx ∈ S sao cho x
k
 ˆx trong H khi cho k → ∞.
Chứng minh: Theo lập luận của Z. Opial [14]. Lấy ˆx
1
, ˆx
2
∈ S là hai
điểm tụ yếu của dãy

x
k

trong H. Đặt l
i
= lim
k→∞


x
k
− ˆx
i


2
khi cho
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16

1
− ˆx
2
|
2
+ 2ˆx
1
− ˆx
2
, ˆx
2
− x
k

Ta suy ra l
1
− l
2
= − |ˆx
1
− ˆx
2
|
2
.Tương tự lấy k
m
→ ∞ sao cho x
km
→ ˆx
2

λ
k

x
k
+ α
k

x
k
− x
k−1

, k = 1, 2,
Với A : H → P (H) là một toán tử đơn điệu cực đại với S := A
−1
(0) = ∅
và các tham số λ
k
và α
k
thoả mãn:
i)tồn tại λ > 0 sao cho ∀k ∈ N ,λ
k
≥ λ
ii) tồn tại α ∈ [0, 1] sao cho ∀k ∈ N ,0  α
k
 α
Nếu điều kiện sau được thoả mãn thì
∞

k
− z


2
.
Khi đó dễ dàng kiểm tra được ∀k ∈ N
ϕ
k+1
= ϕ
k
+ x
k+1
− x
k
, x
k+1
− z − 1/2


x
k+1
− x
k


2
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17

k


2
(2.2)
Do đó {ϕ
k
} không tăng, vì vậy hội tụ.
Vì z là một phần tử bất kì của S nên điều kiện a) của bổ đề 2.1 được thoả
mãn. Mặt khác, từ (2.2) ta có:
∞

k=1


x
k+1
− x
k


2
 2ϕ =


x
1
− z



x
k+1
− x
k
− α
k
(x
k
− x
k−1
), x
k+1
− z + λA(x
k+1
), x
k+1
− z = 0
Và tính đơn điệu cực đại của A cho ta :
x
k+1
− x
k
− α
k
(x
k
− x
k−1
), x
k+1


x
k+1
− x
k


2
− α
k
x
k
− x
k−1
, x
k+1
− z
Và vì
x
k
− x
k−1
, x
k+1
− z = x
k
− x
k−1
, x
k

k−1
, x
k+1
− x
k

suy ra :
ϕ
k+1
− ϕ
k
− α
k
(ϕ
k
− ϕ
k−1
) 
−
1
2


x
k+1
− x
k


2

− x
k
− α
k

x
k
− x
k−1



2
+
1
2

α
k
+ α
2
k



x
k
− x
k−1


− x
k−1


2
(2.3)
Trong đó: v
k+1
:= x
k+1
− x
k
− α
k

x
k
− x
k−1

Đặt θ
k
:= ϕ
k
− ϕ
k−1
; δ
k
:= α
k

[θ
k+1
]
+
 α [θ
k
]
+
+ δ
k
,
với α ∈ [0, 1] cho bởi :
[θ
k+1
]
+
 α
k
[θ
1
]
+
+
k−1

j=0
α
j
δ
k−j

−
k

j=1
[θ
j
]
+
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19
Từ ϕ
k
≥ 0 và

∞
j=1
[θ
j
]
+
< ∞ suy ra ω
k
giới nội dưới. Nhưng
ω
k+1
= ϕ
k+1
− [θ
k+1

k
} hội tụ và
lim
k→∞
ϕ
k
=
∞

j=1
[θ
j
]
+
+ lim
k→∞
ω
k
,
dẫn đến, ∀z ∈ S ,lim
k→∞


x
k
− z


tồn tại. từ (2.3) ta nhận được đánh
giá sau:



2
 ϕ
1
+
∞

k=1

α [θ
k
]
+
+ δ
k

< ∞.
Như vậy, v
k+1
→ 0 khi k → ∞ và vì v
k+1
+ λ
k
A

x
k+1

,theo (i) của


2
< ∞,
và như vậy tồn tại ˆx ∈ S khi x
k
 ˆx trong H khi k → ∞
Chứng minh: Từ chứng minh của định lí 2.1 ta có :
ϕ
k+1
− ϕ
k
− α
k
(ϕ
k
− ϕ
k−1
) 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
−
1
2


x
k+1
− x
k


k
− α
k
(ϕ
k
− ϕ
k−1
) 
(α
k
− 1)
2


x
k+1
− x
k


2
+ α
k


x
k
− x
k−1


k+1
− µ
k
 −
(1 − 3α)
2


x
k+1
− x
k


2
(2.4).
Từ (ii), 1 − 3α > 0 và ta có dãy [µ
k
] không tăng, trong đó:
ϕ
k
− αϕ
k−1
 µ
k
 µ
1
.
Điều này dẫn đến :
ϕ

j+1
− x
j


2
 µ
1
− µ
k+1
 µ
1
+ αϕ
k
 α
k+1
ϕ
0
+
µ
1
1 − α
.
Điều này dẫn đến:
∞

k=1


x

n
)T P
K
(x
n
− α
n
A(x
n
)),
với mọi n = 0, 1, , ở đây {λ
n
} ⊂ [a, b] với a, b ∈ (0, 2λ) và {α
n
} ⊂ (c, d)
với c, d ∈ (0, 1). Khi đó , {x
n
} hội tụ yếu đến z ∈ V I(K, A) ∩ F (T ), ở
đây
z = lim
n→∞
P
V I(K,A)∩F (T )
(x
n
),
và P
Q
ký hiệu phép chiếu metric lên tập Q.
Để tìm một phần tử thuộc V I(K, A) ∩ F (T ) ta có thể sử dụng phương

n
} là hai dãy số thực. Lưu ý rằng thuật toán điểm gần
kề quán tính được đề xuất đầu tiên bởi Alvarez [1] cho bài toán cực trị
lồi. Sau đó ,Attouch và Alvarez xét mở rộng thuật toán đó cho toán tử
đơn điệu cực đại [2]. Mới đây,Moudafi sử dụng thuật toán này để giải bất
đẳng thức biến phân [9], Moudafi và Elisabeth [8] nghiên cứu thuật toán
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
22
này với việc sử dụng mở rộng toán tử đơn điệu cực đại ,và Moudafi cùng
Oliny xét kết hợp thuật toán này với quá trình tách [7].Kết quả cơ bản
của các nghiên cứu trên vẫn là sự hội tụ yếu trong không gian Hilbert.
Trong mục này, bằng cách đưa vào quá trình hiệu chỉnh Browder-
Tikhonov chúng tôi trình bày rằng với việc cộng thêm thành phần hiệu
chỉnh vào thuật toán điểm gần kề quán tính, ta thu được sự hội tụ mạnh
của thuật toán cho trường hợp tổng quát hơn khi A
i
, i = 1, , N, N > 1,
là các ánh xạ λ
i
ngược đơn điệu mạnh từ K vào H, λ
i
có thể bằng 1/2,
và A là đơn điệu và h-liên tục tại u ∈ K.
Cho F là một song hàm từ K × K vào R, sao cho F (u, u) = 0 với mọi
u ∈ K. Giả thiết thêm F (u, .) lồi và nửa liên tục dưới với mỗi u ∈ K.
Bài toán cân bằng đối với F là tìm u
∗
∈ K sao cho
F (u
∗