ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN VĂN ĐẠT

PHƯƠNG TRÌNH TOÁN TỬ J -ĐƠN ĐIỆU
VÀ PHƯƠNG PHÁP NEWTON–KANTOROVICH

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN-2015


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN VĂN ĐẠT

PHƯƠNG TRÌNH TOÁN TỬ J -ĐƠN ĐIỆU
VÀ PHƯƠNG PHÁP NEWTON–KANTOROVICH

Chuyên ngành: TOÁN ỨNG DỤNG
Mã số:

60 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học:
TS. NGUYỄN THỊ THU THỦY


1.1.3 Đạo hàm Fréchet . . . . . . . . . . . . . . . . . . .
Phương trình toán tử phi tuyến . . . . . . . . . . . . . . .

8
9

1.2.1
1.2.2

Phương trình toán tử đặt không chỉnh . . . . . . . . 9
Phương pháp hiệu chỉnh Browder–Tikhonov . . . . . 10

1.2.3

Phương pháp Newton . . . . . . . . . . . . . . . . . 11

2 Phương pháp Newton–Kantorovich
15
2.1 Phương pháp Newton–Kantorovich và định lý hội tụ . . . . 15
2.1.1
2.1.2
2.2

Phương pháp . . . . . . . . . . . . . . . . . . . . . . 15
Định lý hội tụ . . . . . . . . . . . . . . . . . . . . . 16

Phương pháp hiệu chỉnh Newton–Kantorovich . . . . . . . . 30
2.2.1 Mô tả phương pháp . . . . . . . . . . . . . . . . . . 30
2.2.2



Fix(T )

Tập điểm bất động của toán tử T

H

không gian Hilbert

C

tập con lồi đóng của H

I

ánh xạ đơn vị

PC

Phép chiếu mêtrix H lên tập con lồi đóng C của H

xn → x

dãy {xn } hội tụ mạnh tới x

xn

dãy {xn } hội tụ yếu tới x

x

ở đây x+ là một phần tử cho trước và αn là dãy tham số dương đủ bé
thỏa mãn αn → 0 khi n → +∞. Nếu A là một toán tử phi tuyến thì


4

phương trình hiệu chỉnh (0.2) là một bài toán phi tuyến. Để khắc phục
khó khăn khi giải bài toán phi tuyến này, Bakushinskii đề xuất phương
pháp hiệu chỉnh Newton–Kantorovich trong không gian Hilbert H giải
phương trình (0.1) (xem [4]):
x0 ∈ E,

A(xn ) + A (xn )(xn+1 − xn ) + αn xn+1 = fn ,

(0.3)

với A và A là ký hiệu đạo hàm Fréchet cấp một và cấp hai tương ứng
của A, được giả thiết thỏa mãn các điều kiện:
(C1) A liên tục Lipschitz, và
(C2)

A (x) ≤ M,

∀x ∈ H, M là một hằng số dương.

Phương pháp (0.3) được phát triển từ không gian Hilbert lên không gian
Banach bởi Ryazantseva ở dạng (xem [11]):
x0 ∈ E,

A(xn ) + A (xn )(xn+1 − xn ) + αn J s (xn+1 ) = fn ,

hiệu chỉnh Browder–Tikhonov hiệu chỉnh bài toán này. Phần cuối của
chương trình bày phương pháp Newton giải phương trình phi tuyến. Nội
dung của chương được tham khảo trong các tài liệu [1]-[9].
Chương 2 với tiêu đề "Phương pháp Newton–Kantorovich" nhằm giới
thiệu phương pháp Newton–Kantorovich và phương pháp hiệu chỉnh
Newton–Kantorovich giải phương trình toán tử J-đơn điệu. Nội dung
của chương này được viết từ bài báo [5], [8] và [10].
Tôi xin bày tỏ lòng cảm ơn sâu sắc tới người cô kính mến TS. Nguyễn
Thị Thu Thủy đã tận tình hướng dẫn tôi hoàn thành đề tài này. Tôi
cũng vô cùng biết ơn các thầy, cô giáo, đặc biệt là các thầy cô giáo trong
Khoa Toán - Tin, trường Đại học Khoa học - Đại học Thái Nguyên đã
dạy dỗ, đóng góp về nội dung cũng như về cách thức trình bày đề tài
này.
Thái Nguyên, ngày 15 tháng 4 năm 2015
Nguyễn Văn Đạt


6

Chương 1

Phương trình toán tử phi tuyến
Trong chương này, chúng tôi giới thiệu một số khái niệm và tính chất
về không gian Banach phản xạ có chuẩn khả vi Gâteaux đều, toán tử Jđơn điệu, toán tử đối ngẫu. Phần thứ hai của chương giới thiệu về phương
trình toán tử J-đơn điệu và phương pháp hiệu chỉnh Browder–Tikhonov.
Phần cuối của chương trình bày phương pháp Newton giải phương trình
phi tuyến. Nội dung của chương này được tham khảo trong các tài liệu
[1]-[11].
1.1
1.1.1

t→0

x + ty − x
t

tồn tại với mọi x, y ∈ SX ;
(ii) có chuẩn khả vi Gâteaux đều nếu với mỗi y ∈ SX giới hạn trên
tồn tại đều với x ∈ SX .
Các không gian Lp , lp là các ví dụ về không gian trơn đều.
1.1.2

Ánh xạ J -đơn điệu

Mục này trình bày định nghĩa ánh xạ đối ngẫu, ánh xạ J-đơn điệu,
J-đơn điệu mạnh, mối liên hệ với ánh xạ đơn điệu trong không gian
Hilbert và một số ví dụ.
Định nghĩa 1.3. Cho X là một không gian Banach thực và X ∗ là không
gian liên hợp của X. Với s ≥ 2, ánh xạ J s từ X vào X ∗ xác định bởi
J s (y) = {g ∈ X ∗ : y, g = y

g

s−1

, g = y ,

∀y ∈ X},

được gọi là ánh xạ đối ngẫu tổng quát của X. Khi s = 2, J 2 thường
được ký hiệu là J, gọi là ánh xạ đối ngẫu chuẩn tắc của X.

Đạo hàm Fréchet

Cho X, Y là các không gian Banach, điểm x0 ∈ X và r > 0. Hình cầu
mở (tương ứng đóng) tâm tại x0 với bán kính r được ký hiệu là B(x0 ; r)
(tương ứng B(x0 ; r)). Ký hiệu L(X, Y ) là không gian tất cả các toán tử
tuyến tính liên tục từ X vào Y . Cho Ω là một tập con mở của không
gian X. Ánh xạ f : Ω ⊂ X → Y được gọi là khả vi tại điểm a ∈ Ω nếu
có một phần tử f (a) ∈ L(X, Y ) sao cho
f (a + h) = f (a) + f (a)h + δ(h)


9

với lim δ(h)/ h = 0 trong Y . Ánh xạ tuyến tính f (a) ∈ L(X, Y ) xác
h→0

định theo cách này là duy nhất và được gọi là đạo hàm Fréchet (hay đơn
giản là đạo hàm) của ánh xạ f tại điểm a. Nếu ánh xạ f : Ω ⊂ X → Y
khả vi tại tất cả các điểm của tập hợp mở Ω thì f được gọi là khả vi
trong Ω. Nếu ánh xạ f : Ω ⊂ X → L(X, Y ) liên tục, thì ánh xạ f được
gọi là khả vi liên tục trong Ω, hay đơn giản là thuộc lớp C 1 trong Ω.
Không gian của tất cả các ánh xạ khả vi liên tục từ Ω vào Y được biểu
viết là C 1 (Ω; Y ), và C 1 (Ω) nếu Y = R.
1.2
1.2.1

Phương trình toán tử phi tuyến
Phương trình toán tử đặt không chỉnh

Xét phương trình toán tử

x0 − x∗ = min{ x − x∗ : Ax = f },
trong đó S là tập nghiệm của bài toán (1.1), được giả thiết là khác rỗng.
Bằng cách chọn x∗ ta có thể có được nghiệm mà ta muốn xấp xỉ.
1.2.2

Phương pháp hiệu chỉnh Browder–Tikhonov

Tư tưởng của phương pháp hiệu chỉnh do Browder đề xuất năm 1966
cho bài toán bất đẳng thức biến phân (còn gọi là phương pháp hiệu chỉnh
Browder–Tikhonov) là sử dụng một toán tử M : X → X ∗ có tính chất
hemi-liên tục, đơn điệu mạnh làm thành phần hiệu chỉnh. Một dạng của
toán tử M là ánh xạ đối ngẫu tổng quát J s của X. Bằng phương pháp
này, Alber (xem [3]) đã xây dựng nghiệm hiệu chỉnh cho phương trình
toán tử (1.1) trên cơ sở phương trình
A(x) + αJ s (x − x∗ ) = fδ .

(1.2)


11

Sự tồn tại duy nhất nghiệm xδα với mỗi α > 0 và sự hội tụ của dãy
nghiệm xδα về nghiệm của phương trình (1.1) được trình bày trong định
lý dưới đây.
Định lý 1.1. (xem [3]) Cho A : X → X ∗ là một toán tử đơn điệu,
hemi-liên tục. Khi đó, với mỗi α > 0 và fδ ∈ X ∗ , phương trình (1.2)
có duy nhất nghiệm xδα . Ngoài ra nếu α, δ/α → 0 thì {xδα } hội tụ đến
nghiệm có x∗ -chuẩn nhỏ nhất của bài toán (1.1).
1.2.3



(1.5)

Dãy lặp (1.5) được gọi là phương pháp Newton, được Newton đề xuất
năm 1669. Chính xác hơn là Newton đã giải quyết bài toán về đa thức:
trong biểu thức f (x0 + h) ông loại bỏ số hạng bậc lớn hơn h. Phương
pháp được minh họa ở ví dụ sau.
Ví dụ 1.1. Giải phương trình
f (x) = x3 − 2x − 5 = 0.
Chọn xấp xỉ ban đầu x0 = 2, ta có f (2 + h) = h3 + 6h2 + 10h − 1 = 0.
Giữ lại phương trình tuyến tính 10h − 1 = 0, ta được h = 0, 1. Số xấp xỉ
tiếp theo là x1 = 2 + 0, 1 = 2, 1 và quá trình này được lặp lại tại điểm x1
với f (2, 1 + q) = q 3 + 6, 3q 2 + 11, 23q + 0, 061 = 0. Giữ lại phương trình
tuyến tính 11, 23q + 0, 061 = 0, ta được q ≈ −0, 0054. Tiếp tục quá trình
này thêm một bước nữa ta được r ≈ 0, 00004853 và ta nhận được:
x3 = x0 + h + q + r = 2, 09455147.
Sự hội tụ của phương pháp (1.5) được trình bày trong định lý sau
đây:
Định lý 1.2. Giả sử hàm f thỏa mãn các điều kiện:
(1) f ∈ C 2 [a, b], ở đây [a, b] là khoảng phân ly của nghiệm đúng x∗
của phương trình (1.3);
(2) f (x) và f (x) không đổi dấu trên [a, b];
(3) Điểm xấp xỉ ban đầu x0 ∈ [a, b] là điểm Fourier, tức là x0 thỏa
mãn điều kiện f (x0 ).f (x0 ) > 0.


13

Khi đó phương pháp Newton (1.5) giải phương trình phi tuyến (1.1) hội
tụ, đồng thời ta có các công thức đánh giá sai số:

f (ξk )
(xk − xk−1 )2 ,
2

(1.8)

trong đó ξk là điểm trung gian giữa xk và xk−1 . Kết hợp với (1.4) ta suy
ra
f (xk ) =

f (ξk )
(xk − xk−1 )2 > 0.
2

(1.9)

k)
Mặt khác xk+1 − xk = − ff (x
(xk ) < 0, tức là xk+1 < xk .

Như vậy từ (1.5), ta đã xây dựng được một dãy số x0 > x1 > · · · >
xk > xk+1 > . . . đơn điệu giảm. Dãy này bị chặn dưới bởi x∗ . Thật vậy,
giả sử tồn tại xk sao cho xk < x∗ thì do f (x) > 0 nên f (xk ) ≤ f (x∗ ) = 0.
Điều này mâu thuẫn với (1.9). Suy ra tồn tại giới hạn
lim xk = x˜.

k→∞


14

f (xk )δxk = −f (xk ), ở đây f (xk ) biểu diễn ma trận (∂j fi (xk )) cấp n, và
cho phép ta tính toán xk+1 := xk + δxk .


15

Chương 2

Phương pháp Newton–Kantorovich
Chương này trình bày phương pháp Newton–Kantorovich giải phương
trình phi tuyến F (x) = 0 trong không gian Banach. Trong phần đầu của
chương, chúng tôi giới thiệu phương pháp của Kantorovich giải phương
trình phi tuyến và định lý hội tụ Newton–Kantorovich. Phần thứ hai
của chương trình bày phương pháp hiệu chỉnh Newton–Kantorovich giải
phương trình toán tử J-đơn điệu trong không gian Banach. Nội dung
của chương này được viết từ bài báo [5], [8] và [10].
2.1
2.1.1

Phương pháp Newton–Kantorovich và định lý hội tụ
Phương pháp

Vào năm 1948, L.V. Kantorovich [10] đã mở rộng phương pháp Newton
(1.5) cho việc giải các phương trình phi tuyến với không gian các phiếm
hàm và gọi là phương pháp Newton–Kantorovich. Đóng góp này của
Kantorovich là một trong các kỹ thuật căn bản trong giải tích số và giải
tích hàm.
Kantorovich nghiên cứu phương trình giống như (1.3):
F (x) = 0,



√
1
1 − 1 − 2h
h = Kη < , r ≥
η.
2
h
Khi đó, phương trình (2.1) có nghiệm x∗ ∈ B, và quá trình (2.2) xác
định và hội tụ tới x∗ đồng thời ta có công thức đánh giá sai số:
xk − x∗ ≤

η
2k
(2h)
.
h2k

Các giả thiết của định lý rất đơn giản. Đóng góp mới của Kantorovich
là ở việc lập công thức tổng quát của dãy lặp và dùng kỹ thuật phù hợp
của giải tích hàm, mà trước đó người ta không cho rằng giải tích số cần
được xem xét trong khung giải tích hàm. Một nét riêng nữa của định lý
Kantorovich là định lý không giả sử sự tồn tại của nghiệm của phương
trình phi tuyến, nhằm cho định lý không chỉ là kết quả hội tụ đơn thuần
cho một phương pháp cụ thể mà còn chỉ ra sự tồn tại của nghiệm của


17

phương trình phi tuyến. Một nét nổi bật nữa là các giả thiết của định

−1

.

n=0

Khi đó, phương trình (2.1) có nghiệm x∗ ∈ B và quá trình (2.2) hội tụ
tới x∗ , đồng thời ta có đánh giá:
k

xk − x∗

βη(h/2)2 −1
≤
.
1 − (h/2)2k

Định lý này khác biệt với Định lý 2.1 ở chỗ F (x) khả nghịch trên B
(còn Định lý 2.1 lại giả sử F (x0 ) chỉ khả nghịch tại điểm khởi đầu x0 )
và một giả thiết yếu hơn với h < 2 chứ không phải h < 1/2.
Định lý Newton–Kantorovich có vị thế đặc biệt vì nó vừa là kết quả
của phân tích số học, như cung cấp phương pháp lặp cho việc tính toán


18

các không điểm của đa thức vừa là kết quả căn bản của phân tích hàm
phi tuyến, như cho việc chứng minh phương trình phi tuyến trong không
gian hàm có nghiệm.
Chú ý rằng, định lý điểm bất động Banach nổi tiếng cung cấp cách đơn


≤ν x−x

1
µν

≤ λ,
≤ µ,
X

∀x, x ∈ B(x0 ; r).

Khi đó f (x) ∈ L(X; Y ) là ánh xạ một-một và lên và f (x)−1 ∈ L(Y ; X)
tại mỗi x ∈ B(x0 ; r). Dãy {xk } xác định bởi
xk+1 = xk − f (xk )−1 f (xk ),

k ≥ 0,


19

chứa trong hình cầu B(x0 ; r− ) với
√
1 − 1 − 2λµν
r− :=
≤ r,
µν
hội tụ tới a ∈ B(x0 ; r− ) là không điểm của f . Ngoài ra, với mỗi k ≥ 0,
xk − a



f (x) − f (x)

X

L(X;Y )

≤

≤ν x−x

X

∀x, x ∈ B(x0 ; r+ ),

thì điểm a ∈ B(x0 ; r+ ) là không điểm duy nhất của f trong B(x0 ; r+ ).
Nếu λµν =

1
2

(trong trường hợp này r− = r = r+ ), giả thiết thêm rằng
B(x0 ; r) ⊂ Ω,

thì điểm a ∈ B(x0 ; r) là không điểm duy nhất của f trong B(x0 ; r).
Chứng minh. Cho các số tk với t0 := 0, k ≥ 0 là số lần lặp Newton cho
đa thức toàn phương
p : t ∈ R → p(t) :=

µν 2


p(tk )
:= tk −
= tk +
p (tk )

µν 2
2 tk

− tk + λ
,
1 − µνtk

k ≥ 0,

thỏa mãn:
µν(tk − tk−1 )2
, k ≥ 1,
2(1 − µνtk )
µν(r− − tk )2
r− − tk+1 =
, k ≥ 0,
2(1 − µνtk )
λ
tk+1 − tk ≤ k , k ≥ 0,
2
1
1 − µνtk ≥ k , k ≥ 0,
2
1


(trong trường hợp đó µν(r− = 1).

Để thuận tiện, ta ký hiệu tất cả các chuẩn đều là . .
(ii) Phân tích hàm sơ bộ đầu tiên: Ánh xạ f : Ω ∈ X → Y thỏa mãn
f (x) − f (x) − f (x)(x − x) ≤

ν
x−x
2

2

∀x, x ∈ B(x0 ; r).

Cách chứng minh bất đẳng thức này dựa vào định lý giá trị trung bình
cho các hàm của lớp C 1 trong không gian Banach, áp dụng với hàm
f ∈ C 1 (Ω; Y ) giữa hai điểm x và x trong tập con mở B(x0 ; r) của Ω (như
là một tập lồi, hình cầu B(x0 ; r) chứa đoạn đóng [x, x]). Điều này dẫn
tới
1

f (x) − f (x) =

f ((1 − θ)x + θx)(x − x)dθ
0

∀x, x ∈ B(x0 ; r).



(iii) Phân tích hàm sơ bộ thứ hai: Lấy bất kì x ∈ B(x0 ; r). Đạo hàm
f (x) ∈ L(X; Y ) là ánh xạ một-một và lên, và f (x)−1 ∈ L(Y ; X). Bên
cạnh đó,
f (x)−1 ≤

µ
1 − µν x − x0

∀x ∈ B(x0 ; r).

Lưu ý rằng
x − x0

(v) Dãy lặp Newton xk+1 := xk − (f (xk ))−1 f (xk ), k ≥ 0, (f thuộc
hình cầu mở B(x0 ; r− )) thỏa mãn đánh giá
xk+1 − xk ≤ tk+1 − tk

với mọi k ≥ 0,

với tk , k ≥ 0, là lặp Newton của đa thức p : t ∈ R → p(t) =

µν 2
2 t

−t+λ

khi t0 = 0 (xem (i)).
Thật vậy, trước hết ta thấy các đặc tính trên đúng với k = 0 vì
x1 − x0 = f (x0 )−1 f (x0 ) ≤ λ = t1 < r− .
Giả sử chúng đúng với k = 0, . . . , n − 1, với n ≥ 1, sao cho
n−1

xn − x0 ≤

n−1

x +1 − x
=0

≤

(t +1 − t ) = tn − t0 = tn .
=0

xn+1 − x0 ≤

≤ tn+1 < r− .

=0

Do đó các đặc tính trên đúng với k = n.
(vi) Dãy lặp Newton xk ∈ B(x0 ; r− ), k ≥ 0, hội tụ tới không điểm
a ∈ B(x0 ; r− ) của f , và
a − xk ≤

1
k
(µνr− )2 ,
k
µν2

k ≥ 0.

Thật vậy, vì
m−1

xm − xn ≤

xk+1 − xk ≤ tm − tn
k=n

với mọi m > n ≥ 0 và dãy {tk } hội tụ khi k → ∞ (tới r− ), nên dãy {xk }
là dãy Cauchy trong hình cầu đóng B(x0 ; r− ). Do đó, dãy {xk } hội tụ
tới điểm a ∈ B(x0 ; r− ). Ngoài ra,