Tốc độ hội tụ (Rate of convergence) là đại lượng định lượng trong giải tích số và lý thuyết tối ưu hóa mô tả vận tốc suy giảm sai số của dãy xấp xỉ lặp về nghiệm chính xác của bài toán theo số bước lặp hoặc kích thước lưới tính toán.
Tốc độ hội tụ (rate of convergence) của một dãy số {xn} đến giới hạn x* được định nghĩa qua mối quan hệ giữa sai số tại bước lặp tiếp theo và sai số hiện tại. Gọi en = |xn − x*|, nếu tồn tại hằng số μ>0 và order p>0 sao cho với mọi n đủ lớn,
,
thì nói dãy hội tụ với order p và hằng số hội tụ μ. Order p càng lớn thì tốc độ hội tụ càng nhanh; đặc biệt p=1 gọi là hội tụ tuyến tính, p=2 gọi là hội tụ bậc hai (toàn phương).
Cơ sở toán học và phân loại
Phân loại tốc độ hội tụ dựa trên giá trị p và μ:
- Hội tụ tuyến tính (p = 1): tồn tại 0 ≤ μ < 1 sao cho en+1 ≤ μ en. Ví dụ phương pháp chia đôi (bisection) cho μ=½.
- Hội tụ siêu tuyến tính (1 < p < 2): en+1 giảm nhanh hơn tuyến tính nhưng chậm hơn bậc hai. Ví dụ phương pháp secant có p ≈ 1.618.
- Hội tụ toàn phương (p = 2): en+1 ≤ μ en2. Tiêu biểu là phương pháp Newton–Raphson với μ = |f″(x*)|/(2|f′(x*)|).
- Hội tụ cấp cao hơn (p > 2): các thuật toán cải tiến hoặc extrapolation như Halley’s method đạt bậc ba hoặc cao hơn.
Hằng số và order of convergence
Order p và hằng số μ xác định chính xác tốc độ hội tụ. Có thể ước lượng qua giới hạn:
Khi thực nghiệm, ta ghi nhận sai số en qua các bước và vẽ đồ thị log–log: trục ngang là log(en), trục dọc là log(en+1). Độ dốc đường thẳng xấp xỉ p, hệ số chặn biểu diễn log(μ).
Ví dụ thuật toán số
So sánh tốc độ hội tụ giữa ba thuật toán giải phương trình f(x)=0:
| Thuật toán | Order p | Hằng số μ (đại diện) |
|---|---|---|
| Bisection | 1 (tuyến tính) | 0.5 |
| Secant | ≈1.618 (siêu tuyến tính) | tùy f(x) |
| Newton–Raphson | 2 (toàn phương) |
Ví dụ thực tế với f(x)=x2−2, Newton cho xn+1=½(xn+2/xn) hội tụ bậc hai với μ=1/4 khi x* = √2. Secant không cần đạo hàm, nhưng p≈1.618 chậm hơn Newton.
Ảnh hưởng điều kiện ban đầu và tính chất hàm
Điểm khởi đầu x0 quyết định vùng hội tụ (basin of convergence) của thuật toán. Với phương pháp Newton–Raphson, nếu x0 nằm quá xa nghiệm x*, hàm f′(x) có thể gần bằng 0 gây diverge hoặc nhảy ra ngoài vùng hợp lệ. Do đó, lựa chọn x0 sao cho |x0−x*| đủ nhỏ là yếu tố tiên quyết đảm bảo hội tụ bậc hai.
Tính chất hàm f(x) cũng ảnh hưởng lớn đến tốc độ hội tụ. Độ mượt (smoothness) yêu cầu f∈Cp+1 để đạt hội tụ bậc p; độ lồi lõm của hàm (convexity/concavity) quyết định μ, khi f″(x*) nhỏ μ giảm, tăng tốc hội tụ. Hàm có đạo hàm cao bậc ổn định và không đổi dấu thường cho p đúng giá trị lý thuyết.
Trong thực tế, với hàm nhiều cực trị, thuật toán đơn biến có thể hội tụ tới nghiệm sai hoặc lặp vào chu kỳ hạn. Kỹ thuật đa khởi điểm (multi-start) và khảo sát đồ thị f(x) trước khi lặp giúp xác định vùng hội tụ an toàn và cải thiện độ tin cậy.
Đánh giá tốc độ hội tụ
Đánh giá order p và hằng số μ thường thực hiện qua phân tích sai số thực nghiệm. Ghi nhận en, en+1 và en−1 trong quá trình lặp, sau đó ước tính p bằng công thức log–log. Phương pháp least squares áp dụng cho bộ điểm (log en, log en+1) cho kết quả chính xác hơn.
| Bước lặp n | en | log(en) | log(en+1) |
|---|---|---|---|
| 5 | 1.2×10−4 | −9.03 | −17.21 |
| 6 | 2.4×10−8 | −17.54 | −35.08 |
Phân tích đồ thị giúp trực quan hóa p và μ, đặc biệt khi μ ≪ 1 cho thấy hội tụ rất nhanh. Ngoài ra, phân tích độ nhạy (sensitivity analysis) khảo sát sự thay đổi p khi thay đổi x0 hoặc thông số thuật toán giúp đánh giá tính ổn định.
Ứng dụng trong giải phương trình phi tuyến và tối ưu
Trong giải phương trình f(x)=0, lựa chọn thuật toán dựa trên trade-off giữa p và chi phí tính đạo hàm. Newton–Raphson có p=2 nhưng yêu cầu tính f′, f″; secant có p≈1.618, không cần f′, tiết kiệm chi phí tính toán. Ví dụ, giải phương trình e−x−x=0, Newton hội tụ nhanh trong 4–5 bước, trong khi bisection cần >20 bước.
Trong tối ưu hóa đa biến, thuật toán Newton–Raphson mở rộng dùng Hessian matrix cho bậc hai; quasi-Newton (BFGS) ước tính xấp xỉ Hessian giúp giảm chi phí lưu trữ và tính toán. Gradient descent tuyến tính (p=1) thường chậm, cần điều chỉnh bước nhảy (learning rate) và preconditioning để cải thiện tốc độ.
Trong giải PDE, các lặp Jacobi và Gauss–Seidel tuyến tính (μ gần 1) chậm với condition number lớn. Preconditioning như SOR (Successive Over-Relaxation) và multigrid methods tăng tốc hội tụ, giảm số bước lặp xuống một phần mười so với phương pháp cơ bản.
Tăng tốc hội tụ và kỹ thuật cải tiến
- Aitken’s Δ²: extrapolation tuyến tính dùng ba điểm liên tiếp để loại bỏ thành phần tuyến tính, nâng tốc độ hội tụ tuyến tính lên siêu tuyến tính.
- Anderson acceleration: tổng hợp đa bước lặp trước đó để tính bước mới, cải thiện hội tụ Picard iterations trong giải hệ phi tuyến. Đánh giá kết quả trên SIAM Journal phân tích: Anderson thường tăng p lên ~1.8–2.5.
- Line search & trust region: trong tối ưu hóa, kết hợp Newton với điều chỉnh chiều bước dựa trên mô hình cục bộ (trust region) giúp duy trì tính ổn định và tăng tốc hội tụ.
Thách thức và lưu ý
Ước tính p và μ cần sai số đủ nhỏ, bước lặp ban đầu phải gần đủ với x*. Với dữ liệu nhiễu hoặc lượng tính xác suất, cần thuật toán robust hoặc regularization (như Levenberg–Marquardt) để ngăn hội tụ vào nghiệm giả.
Trade-off giữa độ phức tạp thuật toán và tốc độ hội tụ: thuật toán bậc cao tiêu tốn chi phí tính đạo hàm cao hoặc lưu trữ ma trận lớn; thuật toán đơn giản có p thấp nhưng chi phí mỗi bước nhỏ hơn. Lựa chọn phải cân nhắc tài nguyên và yêu cầu ứng dụng.