Phương pháp số: Newton-Raphson, Euler và Runge-Kutta

Phương pháp số là các thuật toán để tìm lời giải gần đúng. Newton-Raphson được dùng để tìm nghiệm của phương trình như $f(x)=0$, còn Euler và Runge-Kutta được dùng để xấp xỉ nghiệm của phương trình vi phân.

Nếu bạn chỉ cần phân biệt nhanh, thì là thế này: Newton-Raphson cập nhật một giá trị đoán cho $x$; Euler và Runge-Kutta đẩy nghiệm tiến dần theo thời gian. Việc chúng có hoạt động tốt hay không phụ thuộc vào các điều kiện như giá trị đoán ban đầu hợp lý, đạo hàm dùng được, hoặc kích thước bước $h$ đủ nhỏ cho bài toán.

Mỗi phương pháp số dùng để làm gì

Newton-Raphson: tìm nghiệm

Nếu bạn muốn tìm một giá trị $x$ sao cho $f(x)=0$, Newton-Raphson cập nhật giá trị đoán bằng cách đi theo tiếp tuyến:

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

Ý tưởng trực quan rất đơn giản: nếu đồ thị trơn gần nghiệm, thì tiếp tuyến là một mô hình tuyến tính cục bộ, và giao điểm của nó có thể là một giá trị đoán tốt hơn điểm hiện tại.

Phương pháp này thường hoạt động tốt khi $f$ khả vi, $f'(x_n) \ne 0$, và giá trị đoán ban đầu đã khá gần một nghiệm đơn. Nếu các điều kiện đó không thỏa, phương pháp có thể bị khựng lại, nhảy ra xa nghiệm hoặc phân kỳ.

Ví dụ, với $f(x)=x^2-2$ và $x_0=1.5$,

$$x_1 = 1.5 - \frac{1.5^2 - 2}{2(1.5)} = 1.4167$$

và thêm một bước nữa cho khoảng $1.4142$, đã khá gần với $\sqrt{2}$.

Phương pháp Euler: một độ dốc, một bước

Với bài toán giá trị ban đầu

$$y' = f(t,y), \qquad y(t_0)=y_0,$$

phương pháp Euler dùng độ dốc hiện tại để tiến một bước:

$$y_{n+1} = y_n + h f(t_n, y_n)$$

Đây là cách xấp xỉ đơn giản nhất: tiến lên với kích thước bước $h$ bằng độ dốc bạn biết ngay lúc này. Điều đó khiến Euler dễ học và dễ cài đặt, nhưng sai số có thể tăng nhanh nếu $h$ quá lớn hoặc nghiệm thay đổi nhanh.

Phương pháp Runge-Kutta: kiểm tra nhiều độ dốc trong một bước

Các phương pháp Runge-Kutta cải thiện Euler bằng cách lấy thông tin độ dốc nhiều hơn một lần trong cùng một bước. Trong các môn nhập môn, "Runge-Kutta" thường có nghĩa là phương pháp bậc bốn cổ điển RK4:

$$k_1 = f(t_n, y_n), \qquad k_2 = f\left(t_n + \frac{h}{2}, y_n + \frac{h}{2}k_1\right),$$ $$k_3 = f\left(t_n + \frac{h}{2}, y_n + \frac{h}{2}k_2\right), \qquad k_4 = f(t_n + h, y_n + hk_3)$$ $$y_{n+1} = y_n + \frac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4)$$

RK4 lấy trung bình có trọng số của nhiều ước lượng độ dốc, nên thường bám theo đường cong tốt hơn Euler rất nhiều với cùng kích thước bước.

Ví dụ có lời giải: Euler so với Runge-Kutta trên cùng một ODE

Xét

$$y' = y, \qquad y(0)=1$$

và dùng một bước có kích thước $h=0.1$ để ước lượng $y(0.1)$.

Bước Euler

Tại $t=0$, giá trị hiện tại là $y_0=1$, nên độ dốc là

$$f(0,1)=1$$

Euler cho

$$y_1 = 1 + 0.1(1) = 1.1$$

Bước RK4

Bây giờ dùng cùng bài toán với RK4:

$$k_1 = 1$$ $$k_2 = 1 + \frac{0.1}{2}(1) = 1.05$$ $$k_3 = 1 + \frac{0.1}{2}(1.05) = 1.0525$$ $$k_4 = 1 + 0.1(1.0525) = 1.10525$$

Vậy

$$y_1 = 1 + \frac{0.1}{6}(1 + 2(1.05) + 2(1.0525) + 1.10525)$$ $$y_1 \approx 1.105170833$$

Với phương trình này, giá trị chính xác là $e^{0.1} \approx 1.105170918$, nên bước RK4 gần hơn rất nhiều so với bước Euler.

Đó là bài học chính. Euler chỉ dùng độ dốc tại đầu mút bên trái. RK4 lấy mẫu cách độ dốc thay đổi trong suốt bước, nên thường cho bức tranh cục bộ tốt hơn.

Khi nào nên dùng Newton-Raphson, Euler hoặc Runge-Kutta

Dùng Newton-Raphson khi nhiệm vụ là giải một phương trình phi tuyến và bạn có thể tính hoặc xấp xỉ đạo hàm. Dùng Euler khi bạn muốn nắm ý tưởng cơ bản của việc tiến từng bước qua một ODE hoặc cần một mốc so sánh nhanh.

Dùng Runge-Kutta, đặc biệt là RK4, khi bạn muốn tăng độ chính xác một cách thực tế mà không cần thay đổi cách thiết lập bài toán. Tuy nhiên, nếu ODE là bài toán cứng, thì cả Euler lẫn RK4 cổ điển đều không phải lúc nào cũng là lựa chọn tốt; phương pháp phải phù hợp với phương trình.

Những lỗi thường gặp trong phương pháp số

Nhầm lẫn loại bài toán

Newton-Raphson dùng cho bài toán tìm nghiệm phương trình. Euler và Runge-Kutta dùng cho phương trình vi phân. Nếu bạn chọn sai họ phương pháp, thì cách thiết lập đã sai ngay từ trước khi tính toán.

Cho rằng phương pháp lúc nào cũng hội tụ

Newton-Raphson có thể thất bại nếu giá trị đoán ban đầu kém hoặc nếu $f'(x)$ rất nhỏ gần điểm lặp. Các phương pháp Euler và RK có thể cho kết quả xấu nếu kích thước bước quá lớn so với bài toán.

Xem kích thước bước là chi tiết nhỏ

Với các phương pháp giải ODE, kích thước bước $h$ là một phần của phương pháp chứ không phải chi tiết phụ. Một $h$ nhỏ hơn thường cải thiện độ chính xác, nhưng cũng làm tăng chi phí tính toán, và với một số bài toán khó bạn có thể cần các phương pháp được thiết kế cho bài toán cứng thay vì chỉ giảm bước.

Quên rằng đáp án chỉ là gần đúng

Một kết quả số có nhiều chữ số không tự động đáng tin hơn. Câu hỏi hữu ích là phép xấp xỉ đó có ổn định, có hội tụ và có đủ chính xác cho mục đích đang xét hay không.

Phương pháp số được dùng ở đâu

Phương pháp số xuất hiện bất cứ khi nào mô hình đã rõ nhưng lời giải ký hiệu chính xác lại bất tiện hoặc không có sẵn. Điều đó bao gồm vật lý, kỹ thuật, tối ưu hóa, tài chính và tính toán khoa học.

Mẫu hình chung ở đây mang tính thực hành hơn là lý thuyết: bạn cần một câu trả lời đủ chính xác cho quyết định mình phải đưa ra. Đó là lý do việc kiểm tra sự hội tụ, ảnh hưởng của kích thước bước hoặc độ nhạy với giá trị đoán ban đầu quan trọng không kém việc viết ra công thức.

Hãy thử một bài tương tự

Hãy thử lại ví dụ ODE ở trên với $h=0.05$ thay vì $0.1$ và so sánh lại kết quả Euler với kết quả RK4. Sau đó thử Newton-Raphson với $f(x)=x^2-3$ bắt đầu từ $x_0=2$ và xem các điểm lặp tiến về $\sqrt{3}$ nhanh đến mức nào.