Phương pháp Newton: Tìm nghiệm nhanh với xấp xỉ lặp

Một số phương trình đơn giản là không có lời giải đại số gọn gàng.

Bạn có thể phân tích nhân tử và thay thế thoải mái, nhưng một số phương trình không có dạng đóng. Chẳng hạn, đa thức bậc năm trở lên không có lời giải đại số tổng quát. Các hàm trộn lẫn số mũ với đa thức, như e^x = 3x, cũng thuộc nhóm này. Trong những trường hợp đó, bạn cần một cách tiếp cận khác.

Phương pháp Newton chính là cách tiếp cận đó. Nó tìm nghiệm bằng số thông qua các lần đoán ngày càng thông minh hơn - mỗi lần được dẫn dắt bởi tiếp tuyến của hàm tại ước lượng hiện tại.

Trong bài viết này, tôi sẽ hướng dẫn bạn công thức đứng sau phương pháp Newton, cách nó hoạt động từng bước, khi nào nó hội tụ và khi nào không - kèm các ví dụ cụ thể để lý thuyết trở nên dễ nắm bắt.

Bạn đang tìm thêm các chủ đề toán học cần biết với tư cách nhà khoa học dữ liệu? Hãy đọc bài viết Cấp số nhân: Công thức, hội tụ và ví dụ để xem nó ứng dụng trong tài chính, vật lý và khoa học máy tính như thế nào.

Phương pháp Newton là gì?

Phương pháp Newton là kỹ thuật lặp để tìm nghiệm của một hàm. Nghiệm là các giá trị đầu vào mà tại đó hàm bằng không.

Bạn bắt đầu với một giá trị đoán ban đầu. Sau đó, phương pháp dùng hình học của hàm tại điểm đó để đưa ra một ước lượng tốt hơn. Lặp lại quy trình này, và mỗi vòng lặp đưa bạn tiến gần hơn đến nghiệm thực sự.

Ý tưởng chỉ có vậy. Bạn chỉ cần một quy tắc cập nhật thông minh, có thể lặp lại và hội tụ đến đáp án.

Công thức của phương pháp Newton

Trọng tâm của phương pháp Newton là một quy tắc cập nhật duy nhất được áp dụng lặp đi lặp lại cho đến khi bạn đủ gần nghiệm.

Công thức như sau:

Công thức phương pháp Newton

Mỗi vòng lặp nhận ước lượng hiện tại x_n và tạo ra ước lượng tốt hơn, x_{n+1}. Bạn tiếp tục cập nhật cho đến khi kết quả đủ gần bằng không.

Công thức có ba thành phần:

• x_n - ước lượng hiện tại của bạn về nghiệm

• f(x_n) - giá trị của hàm tại ước lượng đó

• f'(x_n) - đạo hàm của hàm tại ước lượng đó, cho biết độ dốc của tiếp tuyến

Nếu f(x_n) lớn, bạn còn xa nghiệm. Nếu f'(x_n) dốc, hàm thay đổi nhanh nên bạn có thể bước dài hơn. Tỷ số f(x_n) / f'(x_n) cho bạn biết chính xác phải dịch bao xa - và bạn trừ nó khỏi giá trị đoán hiện tại để tiến gần hơn.

Nếu f'(x_n) bằng không hoặc gần không, công thức sẽ không hoạt động. Bạn sẽ chia cho 0, nghĩa là phương pháp không thể tạo ra ước lượng tiếp theo. Tôi sẽ nói kỹ hơn ở phần hạn chế.

Phương pháp Newton hoạt động như thế nào

Phương pháp Newton lặp lại cùng bốn bước ở mỗi vòng.

1. Chọn giá trị đoán ban đầu: Chọn giá trị khởi đầu x_0 gần nghiệm. Bạn không cần chính xác - chỉ cần đủ gần để hàm ứng xử có thể dự đoán quanh điểm đó. Tôi sẽ nói “đủ gần” nghĩa là gì trong phần hội tụ.

2. Tính giá trị hàm: Tính f(x_0). Điều này cho biết hàm cách xa 0 bao nhiêu tại ước lượng hiện tại. Nếu f(x_0) = 0, xong - bạn đã tìm được nghiệm.

3. Tính đạo hàm: Tính f'(x_0). Điều này cho bạn độ dốc của hàm tại x_0, cũng chính là độ dốc của tiếp tuyến tại điểm đó.

4. Cập nhật ước lượng: Áp dụng quy tắc cập nhật theo công thức ở phần trước.

Vậy là xong!

Giá trị mới x_1 là nơi đường tiếp tuyến cắt trục hoành. Về mặt hình học, bạn vẽ một đường thẳng chạm vào đường cong tại x_0 và theo nó xuống đến 0. Điểm giao đó là giá trị đoán tiếp theo, tốt hơn.

Rồi bạn lặp lại. Thế x_1 vào các bước 2 đến 4 để được x_2, rồi x_3, v.v. Mỗi vòng lặp vẽ một tiếp tuyến mới tại điểm đã cập nhật và tìm nơi nó cắt trục hoành.

Quy trình dừng khi f(x_n) đủ gần 0 - thường là khi nó nhỏ hơn một ngưỡng nhỏ bạn đặt trước.

Diễn giải hình học của phương pháp Newton

Hãy hình dung một đường cong trên đồ thị - đó là hàm của bạn f(x). Nghiệm là nơi đường cong cắt trục hoành. Bạn chưa biết điểm cắt ở đâu, nên bắt đầu bằng một giá trị đoán x_0 nào đó trên trục hoành.

Ở mỗi bước, bạn lấy điểm (x_0, f(x_0)) trên đường cong, rồi vẽ tiếp tuyến tại điểm đó - một đường thẳng chạm vào đường cong và có cùng độ dốc. Tiếp tuyến này không nằm ngang. Nó nghiêng, và nếu theo nó xuống, nó sẽ cắt trục hoành tại một điểm nào đó. Điểm cắt đó là ước lượng tiếp theo của bạn, x_1.

Rồi bạn lặp lại. Tại x_1, vẽ tiếp tuyến mới và tìm nơi nó cắt trục hoành. Điều đó cho bạn x_2. Mỗi tiếp tuyến là một xấp xỉ tuyến tính cục bộ của đường cong, và mỗi điểm cắt lại gần hơn nghiệm thực sự.

Biểu đồ dưới đây cho thấy hai vòng lặp của phương pháp Newton áp dụng cho f(x) = x^2 - 2, bắt đầu từ x_0 = 2.5:

Biểu đồ diễn giải hình học

Điều này hiệu quả vì tiếp tuyến là xấp xỉ đường thẳng tốt nhất của đường cong tại mọi điểm. Càng gần nghiệm, tiếp tuyến càng giống chính đường cong - và bước tiếp theo của bạn càng chính xác.

Trong thực tế, các ước lượng không chỉ rón rén tiến đến nghiệm. Chúng nhảy rất nhanh, thường nhân đôi số chữ số thập phân đúng sau mỗi vòng lặp.

Ví dụ từng bước với phương pháp Newton

Hãy áp dụng phương pháp Newton cho f(x) = x^2 - 2. Nghiệm của hàm này là x = sqrt(2) ≈ 1.4142 - nói cách khác, ta đang tính căn bậc hai của 2.

Đạo hàm là f'(x) = 2x, nên quy tắc cập nhật trở thành:

Ví dụ (quy tắc cập nhật)

Hãy bắt đầu với giá trị đoán ban đầu x_0 = 2.5.

Vòng lặp 1:

Ví dụ (vòng lặp 1)

Vòng lặp 2:

Ví dụ (vòng lặp 2)

Vòng lặp 3:

Ví dụ (vòng lặp 3)

Chỉ sau ba vòng lặp, chúng ta đã chính xác đến bốn chữ số thập phân. Sai số giảm từ 1.086 tại x_0 xuống 0.0001 tại x_3 - và tiếp tục giảm sau mỗi bước.

Dưới đây là cách ước lượng và giá trị sai số này thể hiện trực quan:

Tổng quan trực quan về ước lượng và sai số

Khung bên trái cho thấy mỗi ước lượng tiến gần đến sqrt(2) ≈ 1.4142, còn khung bên phải cho thấy sai số nhỏ dần trên thang log - mỗi vòng lặp xấp xỉ bình phương độ chính xác của vòng trước.

Sự hội tụ của phương pháp Newton

Phương pháp Newton có thể hội tụ rất nhanh, nhưng chỉ khi điều kiện phù hợp.

Khi giá trị đoán ban đầu của bạn gần nghiệm và hàm trơn tru trong vùng đó, phương pháp thể hiện hội tụ bậc hai. Đó là thuật ngữ kỹ thuật cho điều bạn thấy trong ví dụ: mỗi vòng lặp xấp xỉ bình phương sai số của vòng trước. Hai chữ số thập phân đúng thành bốn, bốn thành tám, v.v.

Cần thỏa mãn hai điều kiện để điều này hiệu quả:

• Một giá trị đoán tốt: x_0 càng gần nghiệm thực, phương pháp càng hội tụ nhanh. Nếu bắt đầu quá xa, tiếp tuyến tại điểm đó có thể đưa bạn đi sai hướng.
• Một hàm “ngoan ngoãn”: Hàm cần trơn và khả vi gần nghiệm. Chỗ ngoặt gắt hoặc vùng phẳng có thể làm sai lệch xấp xỉ tiếp tuyến.

Tình huống lỗi phổ biến nhất là đạo hàm gần bằng không. 

Nếu f'(x_n) gần bằng không, bạn đang chia cho một số rất nhỏ trong quy tắc cập nhật, khiến ước lượng tiếp theo đi xa nghiệm. Trường hợp xấu nhất, f'(x_n) = 0 và phép tính dừng vì bạn không thể chia cho 0.

Một điểm khởi đầu kém cũng có thể khiến phương pháp dao động hoặc phân kỳ. Thay vì tiến gần nghiệm, các ước lượng nhảy qua lại hoặc trôi xa dần sau mỗi vòng.

Phương pháp Newton “thưởng” cho thiết lập tốt. Chỉ cần một giá trị đoán hợp lý và một hàm trơn, nó sẽ hội tụ - và hội tụ rất nhanh.

Ưu điểm của phương pháp Newton

Khi điều kiện phù hợp, thật khó có phương pháp nào vượt mặt Newton.

Ưu điểm lớn nhất là hội tụ bậc hai. Hầu hết các phương pháp số tiến gần nghiệm với tốc độ tuyến tính, nghĩa là mỗi vòng lặp giảm sai số một lượng cố định. Phương pháp Newton thì bình phương sai số, nên đạt độ chính xác rất nhanh chỉ với vài vòng lặp.

Nó cũng mang tính tổng quát. Bạn có thể áp dụng cho nhiều loại hàm - đa thức, lượng giác, mũ - mà không cần thay đổi gì. Vì vậy, nó xuất hiện trong rất nhiều lĩnh vực, từ mô phỏng kỹ thuật đến huấn luyện mô hình học máy.

Hạn chế của phương pháp Newton

Đổi lại tốc độ đó, phương pháp Newton đòi hỏi khá nhiều. Dưới đây là vài hạn chế cần lưu ý:

• Cần đạo hàm: Bạn cần một biểu thức giải tích cho f'(x) trước khi chạy được một vòng lặp. Với các hàm mà đạo hàm khó tính (hoặc không tồn tại) bạn cần cách tiếp cận khác.

• Nhạy với giá trị đoán ban đầu: Nếu bắt đầu quá xa nghiệm, phương pháp có thể đưa bạn đi sai hướng.

• Có thể không hội tụ: Nếu hàm có vùng phẳng hoặc chỗ uốn gắt, xấp xỉ tiếp tuyến đơn giản là không hiệu quả.

• Có thể phân kỳ hoặc dao động: Trong trường hợp xấu, các ước lượng không hội tụ mà trôi xa nghiệm hoặc nảy qua lại vô thời hạn.

Vì thế, trước khi dùng phương pháp Newton, hãy đảm bảo bạn hiểu rõ hàm của mình.

Phương pháp Newton so với các phương pháp tìm nghiệm khác

Phương pháp Newton không phải là cách duy nhất để tìm nghiệm, và không phải lúc nào cũng là lựa chọn đúng cho bạn.

Hai phương pháp khác thường được nhắc đến: chia đôi (bisection) và dây cung (secant). Tôi sẽ giải thích ngắn gọn.

Phương pháp chia đôi

Phương pháp chia đôi là đơn giản nhất trong ba phương pháp. Bạn bắt đầu với một khoảng [a, b] nơi hàm đổi dấu - tức phải có nghiệm nằm đâu đó bên trong. Rồi bạn lặp lại việc chia đôi khoảng, giữ lại nửa vẫn còn chứa sự đổi dấu.

Nó hoạt động, nhưng chậm. Sai số giảm một nửa sau mỗi vòng lặp, tức hội tụ tuyến tính. Bù lại, nó được đảm bảo hoạt động miễn là hàm liên tục và khoảng ban đầu kẹp một nghiệm. Không cần đạo hàm.

Phương pháp dây cung

Phương pháp dây cung là họ hàng gần của phương pháp Newton. Thay vì tính đạo hàm một cách giải tích, nó xấp xỉ đạo hàm bằng hai ước lượng trước đó:

Công thức phương pháp dây cung

Đây là cách tốt khi đạo hàm khó tính. Đổi lại là tốc độ hội tụ - phương pháp dây cung nhanh hơn chia đôi nhưng chậm hơn Newton.

Ứng dụng của phương pháp Newton

Phương pháp Newton xuất hiện khắp khoa học, kỹ thuật và học máy. Hãy xem cụ thể như thế nào.

Giải phương trình bằng số

Ứng dụng trực tiếp nhất. Khi một hàm không có lời giải dạng đóng, phương pháp Newton tìm nghiệm. Điều này xảy ra liên tục trong tính toán khoa học - như tìm điểm cân bằng trong phản ứng hóa học hoặc giải các phương trình siêu việt trong xử lý tín hiệu.

Tối ưu hóa

Tìm cực tiểu hoặc cực đại của một hàm f(x) đồng nghĩa với việc tìm nơi đạo hàm của nó f'(x) = 0. Đó là một bài toán tìm nghiệm - tức có thể áp dụng phương pháp Newton. Bạn chỉ cần chạy thuật toán trên f'(x) thay vì f(x), dùng đạo hàm bậc hai f''(x) thay cho đạo hàm bậc nhất.

Biến thể này gọi là phương pháp Newton cho tối ưu hóa, và nó hội tụ nhanh hơn gradient descent trên các hàm trơn, “ngoan ngoãn”.

Học máy

Trong học máy, huấn luyện mô hình nghĩa là tối thiểu hóa hàm mất mát. Phương pháp Newton và các biến thể xuất hiện ở vài chỗ.

L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) là một bộ tối ưu quasi-Newton xấp xỉ đạo hàm bậc hai để tránh tính trực tiếp. Nó là lựa chọn tiêu chuẩn cho hồi quy logistic và các bài toán lồi khác. Phương pháp Newton cũng là nền tảng cho các cập nhật Newton-Raphson dùng trong khớp mô hình thống kê, như mô hình tuyến tính tổng quát.

Vật lý và kỹ thuật

Phương pháp Newton hiện diện khắp nơi trong mô phỏng và thiết kế. Kỹ sư dùng nó để giải các hệ phương trình phi tuyến mô tả các hệ vật lý - như phân tích ứng suất kết cấu và động lực học chất lưu. Trong mỗi trường hợp, bài toán cơ bản quy về tìm nơi một tập phương trình bằng không.

Lỗi thường gặp với phương pháp Newton

Hầu hết sai sót với phương pháp Newton quy về bốn lỗi giống nhau. Hãy điểm qua:

• Bắt đầu quá xa nghiệm: Giá trị đoán ban đầu kém là lý do phổ biến nhất khiến phương pháp phân kỳ hoặc dao động. Nếu bạn không có trực giác tốt về vị trí nghiệm, hãy vẽ đồ thị hàm trước. Điều đó sẽ cho bạn biết nên bắt đầu ở đâu.

• Tính sai đạo hàm: Quy tắc cập nhật phụ thuộc vào f'(x). Một đạo hàm sai - do lỗi tính toán hoặc lỗi lập trình - tạo ra các ước lượng sai ngay từ vòng đầu, và sai số cộng dồn qua các vòng.

• Không kiểm tra chia cho 0. Nếu f'(x_n) bằng 0 hoặc rất gần 0, bước cập nhật không thể thực hiện. Hãy thêm điều kiện bảo vệ trong triển khai: nếu đạo hàm xuống dưới một ngưỡng nhỏ nào đó, dừng và báo lỗi thay vì tạo ra kết quả vô nghĩa.

• Dừng quá sớm. Cắt ngắn vòng lặp trước khi ước lượng hội tụ để lại một đáp án có vẻ gần đúng nhưng không phải. Hãy đặt điều kiện dừng dựa trên sai số thực - hoặc |f(x_n)| hoặc |x_{n+1} - x_n| nhỏ hơn một ngưỡng bạn chọn cẩn thận, chứ không chỉ một số vòng lặp cố định.

Kết luận

Phương pháp Newton là một trong những công cụ hữu ích nhất trong tính toán số. Chỉ một quy tắc cập nhật, áp dụng lặp lại, có thể tìm nghiệm với độ chính xác tùy ý chỉ sau vài vòng lặp.

Bạn phải trả giá cho tốc độ đó bằng các điều kiện. Bạn cần một giá trị đoán tốt, một hàm không phẳng, không “gai nhọn”, và đạo hàm khác không để đạt hội tụ nhanh. Chỉ cần hiểu các điều kiện này, bạn sẽ biết khi nào nên dùng phương pháp Newton và khi nào nên dùng thứ khác (như chia đôi hoặc dây cung).

Cách tốt nhất để xây dựng trực giác đó là thực hành với các ví dụ đơn giản. Bắt đầu với f(x) = x^2 - 2, thử các điểm bắt đầu khác nhau và quan sát điều gì xảy ra. Chuyển sang các hàm có nhiều nghiệm hoặc vùng phẳng và xem phương pháp đổ vỡ ở đâu.

Nếu bạn thích khái niệm tối ưu hóa qua lặp, bạn cần biết về gradient descent. Đọc Gradient Descent trong Học máy: Phân tích chuyên sâu để biết cách nó tối ưu hóa các mô hình cho học máy.