Hội tụ cấp bốn khác gì so với hội tụ bậc hai của phương pháp Newton?

Phương pháp Newton có cấp hội tụ bậc hai, nghĩa là sai số bước sau tỷ lệ với bình phương sai số bước trước. Hội tụ cấp bốn làm giảm sai số theo lũy thừa bậc bốn, giúp tăng số chữ số có nghĩa chính xác nhanh gấp đôi sau mỗi bước lặp.

Giả thuyết Kung-Traub quy định điều kiện gì cho phương pháp hội tụ cấp bốn?

Theo giả thuyết Kung-Traub (1974), một phương pháp lặp không nhớ cần ít nhất 3 phép tính hàm hoặc đạo hàm mỗi bước để đạt cấp hội tụ bốn. Các phương pháp đạt cấp bốn chỉ với 3 phép tính được gọi là tối ưu.

Hội tụ cấp bốn có duy trì được khi phương trình có nghiệm bội không?

Không, các phương pháp lặp đa điểm tiêu chuẩn sẽ bị suy giảm cấp hội tụ từ cấp bốn xuống cấp một tuyến tính khi gặp nghiệm bội, trừ khi được tích hợp công thức hiệu chỉnh số bội của nghiệm.

Hội tụ cấp bốn là gì? Cơ chế và phương pháp giải tích số

Hội tụ cấp bốn là đặc tính của một phương pháp lặp giải phương trình phi tuyến trong đó sai số của bước lặp kế tiếp tỷ lệ thuận với lũy thừa bậc bốn của sai số ở bước lặp hiện tại khi dãy điểm lặp tiến dần về nghiệm. Thuộc tính này phản ánh tốc độ suy giảm sai số tiệm cận vượt trội, cho phép thuật toán tính toán đạt độ chính xác cao chỉ sau một lượng rất nhỏ các vòng lặp liên tiếp. Mục từ này phân tích nền tảng giải tích của tốc độ hội tụ siêu bậc cao, cấu trúc giải thuật đa điểm, giả thuyết tối ưu Kung-Traub, họ phương pháp King và các mở rộng hiện đại, cùng những rào cản tính toán thực tế trong giải tích số.

Bản chất toán học và cơ chế sai số của hội tụ cấp bốn

Trong giải tích số cổ điển, bài toán giải phương trình phi tuyến một biến tìm nghiệm $\alpha$ thỏa mãn phương trình $f(x) = 0$ thường được thực hiện thông qua các thuật toán lặp tạo ra dãy xấp xỉ số. Giả sử dãy số $x_k$ hội tụ về nghiệm đúng $\alpha$ khi chỉ số bước lặp $k$ tiến ra vô cùng. Sai số tại mỗi bước tính toán được xác định bởi hiệu số $e_k = x_k - \alpha$ , trong đó $x_k$ là giá trị xấp xỉ tại bước thứ $k$ và đại lượng $\alpha$ là vị trí nghiệm thực của hàm số. Quá trình lặp được xác định là đạt cấp hội tụ bốn nếu tồn tại một hằng số thực dương $C$ thỏa mãn giới hạn tiệm cận sau:

\lim_{k \to \infty} \frac{|e_{k+1}|}{|e_k|^4} = C

Trong biểu thức giới hạn trên, đại lượng $e_{k+1}$ biểu diễn sai số ở bước lặp tiếp theo, đại lượng $e_k$ biểu diễn sai số ở bước lặp hiện tại, và đại lượng $C$ được gọi là hằng số tiệm cận sai số. Về mặt định lượng, nếu sai số tại bước hiện tại có độ lớn vào khoảng một phần trăm, thì ở bước kế tiếp, sai số xấp xỉ sẽ giảm tỷ lệ với lũy thừa bậc bốn, tức là đạt độ lớn vào khoảng một phần trăm triệu. Điều này tạo nên sự nhảy vọt về số chữ số có nghĩa chính xác qua từng chu kỳ lặp đơn lẻ, vượt xa tốc độ hội tụ bậc hai của phương pháp Newton truyền thống.

Khai triển chuỗi Taylor quanh nghiệm $\alpha$ là công cụ tiêu chuẩn để thiết lập phương trình sai số của thuật toán lặp. Giả sử hàm số khả vi liên tục đến cấp cần thiết trong lân cận của nghiệm đơn $\alpha$ , ta đặt các hệ số chuẩn hóa của đạo hàm hàm số như sau:

c_j = \frac{f^{(j)}(\alpha)}{j! f'(\alpha)}

Trong công thức xác định hệ số trên, đại lượng $f^{(j)}(\alpha)$ là đạo hàm cấp $j$ của hàm số tại nghiệm, đại lượng $f'(\alpha)$ là đạo hàm cấp một tại nghiệm, và mẫu số chứa giai thừa biểu thị tích các số nguyên dương. Một thuật toán đạt hội tụ cấp bốn khi và chỉ khi phương trình liên hệ sai số tiệm cận triệt tiêu toàn bộ các số hạng bậc một, bậc hai và bậc ba, đồng thời hệ số bậc bốn $M$ khác không, dẫn đến biểu thức sai số có dạng:

e_{k+1} = M e_k^4 + O(e_k^5)

với đại lượng $M$ là hệ số phụ thuộc vào các hệ số chuẩn hóa $c_j$ và thỏa mãn điều kiện khác không, còn ký hiệu số hạng bậc cao biểu thị phần dư suy giảm nhanh hơn khi sai số tiến dần về không.

Giả thuyết Kung-Traub và tính tối ưu hiệu quả tính toán

Việc nâng cao cấp hội tụ của phương pháp lặp không thể tách rời chi phí đánh giá hàm và đạo hàm tại mỗi vòng lặp. Để chuẩn hóa việc đo lường năng lực tính toán, khái niệm chỉ số hiệu quả tính toán được Ostrowski đề xuất thông qua công thức sau:

E = p^{1/d}

Trong đó đại lượng $E$ là chỉ số hiệu quả tính toán, đại lượng $p$ là cấp hội tụ của phương pháp, và đại lượng $d$ là tổng số lần đánh giá hàm số hoặc đạo hàm trong một bước lặp hoàn chỉnh. Đối với phương pháp Newton kinh điển, cấp hội tụ là bậc hai và đòi hỏi hai phép tính gồm hàm số và đạo hàm cấp một, cho chỉ số hiệu quả xấp xỉ căn bậc hai của hai.

Một bước ngoặt nền tảng trong lý thuyết giải tích số là công trình của Kung và Traub (1974). Các tác giả đã nghiên cứu giới hạn trên của cấp hội tụ cho các thuật toán lặp đa điểm không lưu trữ dữ liệu các bước trước. Kung và Traub (1974) phỏng đoán rằng một phương pháp lặp đa điểm không nhớ sử dụng n phép tính hàm có cấp hội tụ tối đa là 2^{n-1}. Giả thuyết này thiết lập giới hạn lý thuyết nghiêm ngặt: để đạt được hội tụ cấp bốn, một phương pháp không nhớ bắt buộc phải sử dụng tối thiểu 3 phép tính hàm hoặc đạo hàm trong mỗi bước lặp, bởi vì lũy thừa của hai với số mũ hiệu số ba trừ một đúng bằng bốn.

Các phương pháp lặp đa điểm thỏa mãn đúng ngưỡng giới hạn của giả thuyết Kung-Traub (1974) được gọi là các phương pháp tối ưu. Tổng quan của Petković và Petković (2010) hệ thống hóa các họ phương pháp lặp đa điểm tối ưu giải phương trình phi tuyến và khẳng định các phương pháp hai bước đạt cấp hội tụ bốn với 3 phép tính hàm giữ vai trò nền tảng. Trong nghiên cứu của Petković (2010), tác giả chứng minh lớp phương pháp lặp đa điểm đạt cấp hội tụ 2^n chỉ đòi hỏi n+1 phép tính hàm trên mỗi bước lặp dựa trên việc kết hợp một phương pháp cấp bốn tùy ý với các bước kiểu Newton, qua đó tiếp tục ủng hộ giả thuyết Kung-Traub (1974).

Gần đây, nghiên cứu của Tassaddiq và cs. (2025) chỉ ra phương pháp lặp tối ưu cấp bốn dựa trên giả thuyết Kung-Traub chỉ cần 3 phép tính hàm mỗi bước lặp, đạt chỉ số hiệu quả xấp xỉ 1,5874. Chỉ số hiệu quả này vượt trội rõ rệt so với phương pháp Newton cũng như các phương pháp một điểm cấp cao khác, khẳng định vị thế trung tâm của hội tụ cấp bốn trong tối ưu hóa chi phí tính toán.

Các cấu trúc thuật toán tiêu biểu đạt hội tụ cấp bốn

Để đạt được cấp hội tụ bốn mà không phải tính toán đạo hàm cấp hai vốn rất tốn kém tài nguyên máy tính, các nhà giải tích số sử dụng cấu trúc lặp đa bước. Thay vì tính đạo hàm cấp cao tại một điểm duy nhất, thuật toán chia bước lặp thành hai giai đoạn liên tiếp.

Họ phương pháp lặp King

Một trong những đóng góp kinh điển thuộc lĩnh vực này là công trình của King (1973). King (1973) xây dựng một họ phương pháp lặp cấp bốn giải phương trình phi tuyến cần tính hàm và đạo hàm tại điểm đầu của mỗi bước lặp và chỉ tính hàm tại điểm Newton. Cấu trúc lặp hai bước của họ phương pháp King (1973) được thiết lập như sau:

y_k = x_k - \frac{f(x_k)}{f'(x_k)}

Trong bước đầu tiên, điểm trung gian $y_k$ chính là bước lặp chuẩn của phương pháp Newton, với $f(x_k)$ là giá trị hàm số tại điểm xuất phát và $f'(x_k)$ là đạo hàm bậc nhất tương ứng. Sau khi nhận được điểm trung gian $y_k$ , thuật toán tiến hành tính giá trị hàm $f(y_k)$ mà không cần tính thêm đạo hàm mới. Bước hiệu chỉnh thứ hai để sinh ra điểm xấp xỉ tiếp theo có dạng:

x_{k+1} = y_k - \frac{f(x_k) + \beta f(y_k)}{f(x_k) + (\beta - 2) f(y_k)} \frac{f(y_k)}{f'(x_k)}

Trong biểu thức trên, tham số thực $\beta$ đóng vai trò tham số tự do xác định từng thành viên cụ thể trong họ phương pháp. Khi tham số $\beta$ nhận giá trị bằng không, công thức thu hẹp về phương pháp Ostrowski kinh điển. Tổng số phép đánh giá hàm số trong mỗi bước lặp của họ King (1973) đúng bằng ba, gồm giá trị hàm tại điểm xuất phát, đạo hàm tại điểm xuất phát và giá trị hàm tại điểm trung gian, do đó họ phương pháp này hoàn toàn tối ưu theo giả thuyết Kung-Traub (1974).

Phương pháp mở rộng không dùng đạo hàm cấp hai

Việc loại bỏ hoàn toàn đạo hàm cấp cao trong khi vẫn duy trì cấp hội tụ bốn tiếp tục là chủ đề nghiên cứu sâu rộng. Nghiên cứu của Dehghan và Hajarian (2008) giới thiệu phương pháp lặp mở rộng của Newton không dùng đạo hàm cấp hai chỉ yêu cầu tính hàm và đạo hàm cấp một đạt cấp hội tụ bốn cho nghiệm đơn. Thuật toán của Dehghan và Hajarian (2008) kết hợp kỹ thuật xấp xỉ sai phân hữu hạn và trung bình trọng số, giúp giảm thiểu độ nhạy cảm của mẫu số và mở rộng khả năng áp dụng cho các hàm số phi tuyến có biểu thức giải tích phức tạp.

Bảng tổng hợp dưới đây so sánh các đặc tính tính toán cơ bản giữa các lớp phương pháp lặp giải phương trình phi tuyến:

Phương pháp lặp	Cấp hội tụ	Số phép tính hàm mỗi bước	Chỉ số hiệu quả tính toán	Đặc tính tối ưu Kung-Traub
Newton-Raphson	Cấp hai	Hai phép tính	Xấp xỉ căn bậc hai của hai	Tối ưu bậc hai
Halley cổ điển	Cấp ba	Ba phép tính gồm đạo hàm cấp hai	Xấp xỉ căn bậc ba của ba	Không tối ưu
Họ phương pháp King (1973)	Cấp bốn	Ba phép tính	Xấp xỉ căn bậc ba của bốn	Tối ưu bậc bốn
Phương pháp Ostrowski	Cấp bốn	Ba phép tính	Xấp xỉ căn bậc ba của bốn	Tối ưu bậc bốn
Thuật toán Tassaddiq (2025)	Cấp bốn	Ba phép tính	Xấp xỉ 1,5874	Tối ưu bậc bốn

Động lực học phi tuyến và mặt phẳng phức

Bên cạnh tốc độ tiệm cận tại lân cận vô cùng bé của nghiệm, hành vi tổng thể của các phương pháp hội tụ cấp bốn trên toàn bộ không gian biến số là một vấn đề then chốt. Công cụ động lực học phức nghiên cứu quỹ đạo lặp của toán tử hữu tỷ trên mặt phẳng phức, thông qua các khái niệm tập hợp Julia và tập hợp Fatou.

Đối với mỗi phương pháp lặp, lưu vực hút của một nghiệm được định nghĩa là tập hợp tất cả các điểm khởi đầu mà từ đó dãy lặp hội tụ về nghiệm đó. Các đặc điểm động học nổi bật của phương pháp hội tụ cấp bốn gồm:

Ranh giới phân chia giữa các lưu vực hút thường mang cấu trúc phân mảnh tự tương đồng dạng fractal, phản ánh tính nhạy cảm cao với điểm khởi đầu.
Sự xuất hiện của các điểm bất động ngoại lai không phải là nghiệm thực sự của phương trình gốc có thể tạo ra các chu trình tuần hoàn ổn định hoặc hỗn loạn, khiến thuật toán không hội tụ về nghiệm mong muốn nếu điểm xuất phát bị chọn sai lệch.
Ngay cả với phương pháp Newton cấp hai, ranh giới giữa các lưu vực hút đã mang cấu trúc fractal phân mảnh rất phức tạp khi phương trình có từ ba nghiệm trở lên trên mặt phẳng phức; các phương pháp cấp bốn với bậc toán tử hữu tỷ cao hơn và sự hiện diện của các điểm bất động ngoại lai càng khiến hình học lưu vực phân mảnh dày đặc hơn, đòi hỏi kỹ thuật chọn điểm ban đầu thận trọng hơn.

Ứng dụng trong khoa học tính toán và kỹ thuật

Khả năng tăng vọt độ chính xác số học khiến các thuật toán hội tụ cấp bốn trở thành thành phần cốt lõi trong các hệ thống tính toán khoa học đòi hỏi độ chính xác cực cao, chẳng hạn như tính toán số học đa chính xác trong thiên văn học và vật lý hạt nhân.

Trong kỹ thuật hóa học và cơ học tính toán, các hệ phương trình phi tuyến mô tả cân bằng pha và động học phản ứng phức tạp thường đòi hỏi giải lặp số. Theo khảo sát ứng dụng của Tassaddiq và cs. (2025), thuật toán lặp cấp bốn được áp dụng giải quyết thành công các mô hình lò phản ứng khuấy trộn phi đoạn nhiệt và hệ tổng hợp động học hóa chất, mang lại tốc độ thực thi vượt trội và tiết kiệm đáng kể thời gian tính toán so với các thuật toán truyền thống.

Tại Việt Nam, các nghiên cứu lý thuyết giải tích số và mô phỏng toán học tại các viện nghiên cứu và trường đại học lớn thường sử dụng các thuật toán giải phương trình phi tuyến làm công cụ nền tảng giải quyết các bài toán biên phức tạp, trong đó việc tiếp cận các họ phương pháp lặp bậc cao giúp tối ưu hóa quy trình tính toán nghiệm số trong các đề tài nghiên cứu chuyên ngành.

Hạn chế và điều kiện áp dụng nghiêm ngặt

Mặc dù sở hữu những ưu thế vượt trội về mặt lý thuyết, phương pháp hội tụ cấp bốn đi kèm các hạn chế kỹ thuật mà người thực hành giải tích số bắt buộc phải kiểm soát:

Bán kính hội tụ cục bộ hẹp: Định lý hội tụ cấp bốn chỉ đảm bảo khi điểm khởi đầu nằm đủ gần nghiệm thực. Khi điểm khởi đầu nằm ngoài lân cận này, tốc độ hội tụ siêu cao không được phát huy và dãy số có thể phân kỳ mãnh liệt.
Hiện tượng triệt tiêu đạo hàm: Trong công thức cập nhật của họ King (1973) cũng như các thuật toán liên quan, mẫu số chứa đạo hàm cấp một $f'(x_k)$ . Khi giá trị đạo hàm tại điểm lặp tiệm cận giá trị không, phép chia cho số cực nhỏ dẫn đến mất ổn định số học và tràn số.
Vấn đề nghiệm bội: Toàn bộ các chứng minh về cấp hội tụ bốn trong các nghiên cứu kinh điển đều giả định nghiệm là nghiệm đơn. Khi phương trình có nghiệm bội với số nhân lớn hơn một, cấp hội tụ của phương pháp lặp đa điểm tiêu chuẩn sẽ bị suy giảm nghiêm trọng về cấp một tuyến tính, đòi hỏi phải can thiệp bằng các kỹ thuật biến đổi tham số nghiệm bội chuyên biệt.
Chi phí nghịch đảo ma trận trong không gian đa chiều: Khi mở rộng phương pháp lên hệ phương trình phi tuyến nhiều biến, việc tính toán ma trận Jacobi và giải hệ phương trình tuyến tính phụ trợ tại mỗi bước lặp đòi hỏi chi phí tính toán tăng nhanh theo quy mô số ẩn số, đòi hỏi các kỹ thuật phân rã ma trận hoặc xấp xỉ tựa Newton thích hợp.