Tốc độ hội tụ

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong giải tích số (một nhánh của toán học), vận tốc mà một dãy hội tụ tiến dần về giới hạn của nó được gọi là tốc độ hội tụ. Đúng ra, một giới hạn không cho ta thông tin gì về phần hữu hạn của dãy số, khái niệm này chỉ có ý nghĩa thực tiễn quan trọng nếu ta xét một dãy các ước lượng liên tiếp bằng phương pháp lặp, khi đó chỉ cần số vòng lặp vừa đủ nhỏ cũng có thể cho ta một ước lượng tốt, nếu tốc độ hội tụ là lớn. Điều này tạo ra sự khác biệt giữa việc dùng chỉ 10 vòng lặp hay một triệu vòng lặp. Nói tóm lại, việc xác định tốc độ hội tụ (phụ thuộc vào số vòng lặp) sẽ giúp ta hạn chế được số vòng lặp trong tính toán một ước lượng.

Định nghĩa tốc độ hội tụ[sửa | sửa mã nguồn]

Giả sử rằng dãy số {xk} hội tụ về số ξ.

Ta nói rằng dãy này hội tụ tuyến tính về ξ, nếu

 \lim_k \frac{|x_{k+1}-\xi|}{|x_k-\xi|} = \mu \mbox{ voi } 0 < \mu < 1. \quad\quad (1)

Số μ được gọi là tốc độ hội tụ.

Nếu (1) đúng với μ = 0, thì dãy được gọi là hội tụ siêu tuyến tính. Ta nói dãy trên hội tụ tuyến tính dưới (converges sublinearly) nếu nó hội tụ, và (1) không đúng với bất kỳ μ < 1 nào.

Định nghĩa sau đây dùng để phân biệt các tốc độ hội tụ siêu tuyến tính. Ta nói rằng dãy hội tụ bậc q với q > 1 về ξ nếu

 \lim_k \frac{|x_{k+1}-\xi|}{|x_k-\xi|^q} = \mu \mbox{ voi } \mu > 0. \quad\quad (2)

Trường hợp đặc biệt, hội tụ bậc 2 được gọi là hội tụ bình phương (quadratic convergence), và hội tụ với bậc là 3 được gọi là hội tụ lập phương (cubic convergence).

Định nghĩa mở rộng của tốc độ hội tụ[sửa | sửa mã nguồn]

Một nhược điểm của các định nghĩa trên, (1) và (2), là nó không tính đến trường hợp có một số dãy hội tụ tương đối nhanh, nhưng tốc độ hội tụ thì luôn biến đổi, chẳng hạn như dãy {bk} dưới đây. Do đó, định nghĩa về tốc độ hội tụ có thể được mở rộng như sau:

Dãy {xk} hội tụ bậc tối thiểu q nếu tồn tại một dãy {εk} sao cho

 |x_k - \xi| \le \varepsilon_k \quad\mbox{voi moi } k,

và dãy {εk} hội tụ bậc q về 0 với khái niệm hội tụ được định nghĩa theo cách đơn giản trên kia.

Ví dụ[sửa | sửa mã nguồn]

Ta xét các dãy sau:

 a_0 = 1,\, a_1 = \frac12,\, a_2 = \frac14,\, a_3 = \frac18,\, a_4 = \frac1{16},\, a_5 = \frac1{32},\, \ldots,\, a_k = \frac1{2^k},\, \ldots
 b_0 = 1,\, b_1 = 1,\, b_2 = \frac14,\, b_3 = \frac14,\, b_4 = \frac1{16},\, b_5 = \frac1{16},\, \ldots,\, b_k = \frac1{4^{\operatorname{floor}(k/2)}},\, \ldots
 c_0 = \frac12,\, c_1 = \frac14,\, c_2 = \frac1{16},\, c_3 = \frac1{256},\, c_4 = \frac1{65536},\, \ldots,\, c_k = \frac1{2^{2^k}},\, \ldots
 d_0 = 1,\, d_1 = \frac12,\, d_2 = \frac13,\, d_3 = \frac14,\, d_4 = \frac15,\, d_5 = \frac16,\, \ldots,\, d_k = \frac1{k+1},\, \ldots

Dãy {ak} hội tụ tuyến tính về 0 với tốc độ 1/2. Một cách tổng quát, dãy k hội tụ tuyến tính với tốc độ μ nếu |μ| < 1.

Dãy {bk} cũng hội tụ tuyến tính về 0 với tốc độ 1/2 theo khái niệm mở rộng, nhưng không hội tụ theo khái niệm đơn giản ban đầu.

Dãy {ck} hội tụ siêu tuyến tính. Nó là hội tụ bình phương.

Cuối cùng, dãy {dk} hội tụ tuyến tính dưới.

Tham khảo[sửa | sửa mã nguồn]

Định nghĩa đơn giản được lấy từ

  • Michelle Schatzman (2002), Numerical analysis: a mathematical introduction, Clarendon Press, Oxford. ISBN 0-19-850279-6.

Định nghĩa mở rộng được lấy từ

  • Kendell A. Atkinson (1988), An introduction to numerical analysis (2nd ed.), John Wiley and Sons. ISBN 0-471-50023-2.
  • Walter Gautschi (1997), Numerical analysis: an introduction, Birkhäuser, Boston.
  • Endre Süli and David Mayers (2003), An introduction to numerical analysis, Cambridge University Press. ISBN 0-521-00794-1.