Đ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, d_M) và (N, d_N) là hai không gian metric, và f : M → N, thì có một hằng  q ϵ [0, 1) sao cho

d_N(f(x), f(y)) ≤ qd_M(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 Ɐ x₀ ϵ X,

Trong đó f⁰(x­₀) = x­­₀ và fⁿ(x­₀) = f(f^n-1(x­₀))

Chứng minh.

a) Dãy (fⁿ(x­₀)) 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)         ⇔

Thay x bằng fⁿ(x­₀) và y bằng f^m(x­₀) chúng ta có

Vì

d(f²(x­₀), f¹(x­₀)) = d(f(f¹(x­₀)), f(f⁰(x­₀))) = d(f(f(x­₀)), f(x­₀)) ≤ qd(f(x­₀), x­₀)

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

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

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

 

 

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

Thay f^m(x₀) bằng x* trong (4),

Chúng ta có

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

Vế phải của (7) hội tụ về 0 khi n → ∞ nên (fⁿ⁺¹(x­₀)) hội tụ tới f(x*). Dãy (fⁿ⁺¹(x­₀)) là (fⁿ(x­₀)) 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)

Áp dụng bất đẳng thức (1) với x = fⁿ⁺¹(x­₀) và y = x* chúng ta có

Vì d(f(x*), x*) = 0 và d(fⁿ⁺²(x­₀), fⁿ⁺¹(x­₀)) ≤ qd(fⁿ⁺¹(x­₀), fⁿ(x­₀)) nên

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

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.