(91) 350-9520 support@omarine.org M-F: 7 AM - 7 PM; Weekends: 9 AM - 5 PM

Ánh xạ co và định lý điểm bất động Banach

Điểm bất động(Fixed point)

Thông thường khi một ánh xạ tác động vào một phần tử sẽ sinh ra giá trị hàm khác với đối số. Nếu lặp ánh xạ ấy một cách đệ qui, nghĩa là lấy giá trị hàm làm đối số cho lần lặp tiếp theo thì chúng ta thấy một cách trực quan rằng ánh xạ nhảy theo các giá trị mới. Nếu có một phần tử mà được ánh xạ tới chính nó sẽ làm ánh xạ không di chuyển được. Phần tử đó được gọi là điểm bất động của ánh xạ.

Điểm x* là một điểm bất động của hàm f(x) nếu và chỉ nếu f(x*) = x*

Để thêm hương vị cho khái niệm, chúng ta phân biệt điểm bất động với điểm cố định(stationary point). Điểm cố định là điểm mà tại đó hàm số không biến thiên, f’(x) = 0. Còn điểm bất động cho thấy tại đó dù lặp ánh xạ bao nhiêu lần đi nữa thì hàm số vẫn bất động

f(f(…f(x*)…)) = x*

Nội dung trên cho chúng ta thấy rằng điểm bất động mang nhiều ý nghĩa thực tiễn trong khoa học máy tính bởi hầu hết các chương trình máy tính đều có các vòng lặp, đặc biệt là đệ qui.

Ánh xạ co(Contraction mapping)

Định nghĩa. Cho (X,d) là một không gian metric. Ánh xạ f : X X được gọi là một ánh xạ co trên X nếu và chỉ nếu tồn tại q ϵ [0, 1) sao cho Ɐ x, y ϵ X,

d(f(x), f(y)) ≤ qd(x, y).

q được gọi là hằng Lipschitz.

Tổng quát hơn, một ánh xạ co có thể được định nghĩa cho ánh xạ giữa hai không gian metric. Nếu (M, dM) và (N, dN) là hai không gian metric, và f : M N, thì có một hằng  q ϵ [0, 1) sao cho

dN(f(x), f(y)) ≤ qdM(x, y)

với mọi x, y ϵ M.

Định lý điểm bất động Banach

Cho (X,d) là một không gian metric đầy đủ không rỗng với một ánh xạ co f : X → X. Thì f có một điểm bất động duy nhất x* ϵ X sao cho Ɐ x0 ϵ X,

anhxaco1

Trong đó f0(x­0) = x­­0 và fn(x­0) = f(fn-1(x­0))

Chứng minh.

a) Dãy (fn(x­0)) hội tụ tới x*

Theo bất đẳng thức tam giác(tính chất 4) của không gian metric thì Ɐ x, y ϵ X,

d(x, y) ≤ d(x, f(x)) + d(f(x), f(y)) + d(f(y), y)

Do d(f(x), f(y)) ≤ qd(x, y) nên

d(x, y) ≤ d(x, f(x)) + qd(x, y) + d(f(y), y) ⇔

d(x, y) – qd(x, y) ≤ d(x, f(x)) + d(f(y), y)  ⇔

(1 – q)d(x, y) ≤ d(x, f(x)) + d(f(y), y)         ⇔

(1 – q)d(x, y) ≤ d(f(x), x) + d(f(y), y)         ⇔

anhxaco2

Thay x bằng fn(x­0) và y bằng fm(x­0) chúng ta có

anhxaco3

d(f2(x­0), f1(x­0)) = d(f(f1(x­0)), f(f0(x­0))) = d(f(f(x­0)), f(x­0)) ≤ qd(f(x­0), x­0)

nên bằng cách qui nạp chúng ta có

anhxaco4

Áp dụng (3) vào (2) cho cả n và m chúng ta được

anhxaco5

Vì q < 1 nên biểu thức cuối của (4) hội tụ về 0 khi n, m → ∞ nên (fn(x­0)) là dãy Cauchy, mặt khác (X,d) là không gian metric đầy đủ do đó (fn(x­0)) hội tụ tới một điểm x* ϵ X, hay

anhxaco1

 

 

b) x* là điểm bất động

Thay fm(x0) bằng x* trong (4),

anhxaco6

Chúng ta có

anhxaco7

Từ (5) và (6) suy ra

anhxaco8

Vế phải của (7) hội tụ về 0 khi n → ∞ nên (fn+1(x­0)) hội tụ tới f(x*). Dãy (fn+1(x­0)) là (fn(x­0)) bỏ đi phần tử đầu tiên nên cũng hội tụ tới x*. Nhưng vì giới hạn của một dãy là duy nhất nên f(x*) = x* hay x* là điểm bất động.

c) x* là điểm bất độngduy nhất

Giả sử có hai điểm bất động x và y. Chúng ta có f(x) = x và f(y) = y. Suy ra d(f(x), x) = 0 và d(f(y), y) = 0. Áp dụng vào bất đẳng thức (1) thì vế phải của (1) bằng 0, do đó d(x, y) ≤ 0 hay d(x, y) = 0, tức là x = y. Vậy hai điểm bất động này phải là một và điểm bất động x* là duy nhất.

d) Tốc độ hội tụ

Chúng ta viết lại bất đẳng thức (5)

anhxaco9

Áp dụng bất đẳng thức (1) với x = fn+1(x­0) và y = x* chúng ta có

anhxaco10

Vì d(f(x*), x*) = 0 và d(fn+2(x­0), fn+1(x­0)) ≤ qd(fn+1(x­0), fn(x­0)) nên

anhxaco12

Bất đẳng thức (6) tương đương với

anhxaco11

Các bất đẳng thức (8), (9), (10) biểu thị tốc độ hội tụ tới điểm bất động của ánh xạ co.

Advertisements

Gửi phản hồi

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: