Phương pháp Euler

Trong toán học và khoa học máy tính, phương pháp Euler là một phương pháp số bậc một để giải các phương trình vi phân thường (ODEs) với giá trị ban đầu cho trước. Nó là phương pháp hiện (explicit) cơ bản nhất cho việc tính tích phân số của các phương trình vi phân thường và là phương pháp Runge-Kutta đơn giản nhất. Phương pháp Euler được đặt theo tên của Leonhard Euler, người đã đề cập đến phương pháp này trong cuốn sách "Institutionum calculi integralis" của ông (xuất bản 1768-1770).
Phương pháp Euler là một phương pháp bậc một, có nghĩa là sai số cục bộ (sai số mỗi bước) tỷ lệ thuận với bình phương của kích thước bước, và sai số tổng thể (sai số tại một thời điểm nào đó) tỷ lệ thuận với kích thước bước. Phương pháp Euler thường phục vụ như là cơ sở để xây dựng các phương pháp phức tạp hơn, ví dụ như, phương pháp Dự đoán- Hiệu chỉnh.
Mô tả hình học phi chính thức.
Xem xét bài toán tính toán hình dạng của một đường cong chưa biết bắt đầu tại một điểm cho trước và thỏa mãn một phương trình vi phân nào đó. Ở đây, phương trình vi phân có thể được coi như là một công thức mà nhờ nó độ dốc của đường tiếp tuyến với đường cong có thể được tính toán tại điểm bất kỳ nào trên đường cong, một khi vị trí của điểm đó đã được tính toán.
Ý tưởng là trong khi đường cong ban đầu chưa biết, điểm khởi đầu của nó được biểu thị bởi formula_1 là đã biết (xem hình phía trên bên phải). Thì, từ phương trình vi phân, độ dốc của đường cong tại formula_2 có thể được tính toán, và vì vậy, có thể tìm được đường tiếp tuyến.
Đi một bước nhỏ dọc theo đường tiếp tuyến đến một điểm formula_3 Dọc bước nhỏ này, độ dốc không thay đổi quá nhiều, vì vậy formula_4 sẽ gần với đường cong. Nếu chúng ta coi formula_4 vẫn còn nằm trên đường cong, cùng một lý luận như đối với điểm formula_2 có thể tính được độ dốc và tiếp tuyến của đường cong tại formula_4. Sau vài bước, một đường cong đa giác formula_8 được tìm ra. Nói chung, đường cong này không phân kỳ quá xa khỏi đường cong chưa biết ban đầu, và sai số giữa hai đường cong có thể được làm nhỏ nếu kích thước bước là đủ nhỏ và khoảng thời gian tính toán là hữu hạn.
Chọn một giá trị formula_10 cho kích thước của mỗi bước và đặt formula_11. Bây giờ, một bước của phương pháp Euler từ formula_12 tới formula_13 là
Giá trị của formula_15 là một lời giải gần đúng của phương trình ODE tại thời điểm formula_12: formula_17. Phương pháp Euler là phương pháp hiện, nghĩa là lời giải formula_18 là một hàm hiện của formula_19 với formula_20.
Trong khi phương pháp Euler tích phân một ODE bậc nhất, ODE bất kỳ bậc N có thể được biểu diễn như là một ODE bậc nhất:
để xử lý phương trình
chúng ta giới thiệu các biến phụ formula_22 và có được 
phương trình tương đương
Đây là một hệ bậc nhất với biến formula_24 và có thể được giải bằng phương pháp Euler hoặc bằng bất kỳ lược đồ nào được sử dụng để giải các hệ bậc nhất.
Ví dụ.
Cho bài toán giá trị ban đầu
chúng ta muốn sử dụng phương pháp Euler để xấp xỉ formula_26.
Sử dụng kích thước bước bằng 1 ("h" = 1).
Phương pháp Euler là:
vì vậy trước tiên chúng ta phải tính toán formula_28. Trong phương trình vi phân đơn giản này, hàm formula_29 được định nghĩa bởi formula_30. Chúng ta có
Bằng cách thực hiện bước trên, chúng ta đã tìm được độ dốc của đường thẳng tiếp tuyến với đường cong lời giải tại điểm formula_32.
Nhớ lại rằng độ dốc được định nghĩa là sự thay đổi trong formula_33 chia cho sự thay đổi trong formula_34, tức là formula_35.
Bước tiếp theo là nhân giá trị trên với kích thước bước formula_10, cái chúng ta lấy bằng một ở đây: 
Bởi vì kích thước bước là sự thay đổi trong formula_34, khi chúng ta nhân kích thước bước và độ dốc của tiếp tuyến, chúng ta có được sự thay đổi trong giá trị formula_33. Giá trị này sau đó sẽ được thêm vào giá trị formula_33 ban đầu để có được giá trị tiếp theo được sử dụng để tính toán.
Các bước trên sẽ được lặp đi lặp lại để tìm ra formula_42, formula_43 và formula_44.
Do tính chất lặp đi lặp lại của thuật toán này, nên tổ chức các bước tính toán dưới dạng biểu đồ, như thấy bên dưới, để tránh tạo ra các sai sót.
Đáp án cuối cùng là formula_46. Lời giải chính xác của phương trình vi phân là formula_47, vì vậy formula_48. Như vậy, lời giải gần đúng của phương pháp Euler không thật sự tốt trong trường hợp này. Tuy nhiên, như hình vẽ cho thấy, ứng xử của nó là đúng về mặt định tính.
Sử dụng các kích thước bước khác.
Như đã nói trong phần giới thiệu, phương pháp Euler sẽ chính xác hơn nếu kích thước bước formula_10 nhỏ hơn. Bảng dưới đây cho thấy kết quả với các kích thước bước khác nhau. Hàng trên cùng tương ứng với ví dụ trong phần trước, và hàng thứ hai được minh họa trong hình.
Sai số được ghi ở cột cuối cùng của bảng là sự khác biệt giữa lời giải chính xác tại formula_50 và lời giải gần đúng Euler. Ở dưới cùng của bảng, kích thước bước bằng một nửa kích thước bước ở hàng trên nó, và sai số cũng bằng khoảng một nửa sai số trong dòng trên nó. Điều này cho thấy rằng sai số gần như là tỷ lệ với kích thước bước, ít nhất là đối với các giá trị kích thước bước tương đối nhỏ. Điều này nói chung, cũng đúng cho các phương trình khác; xem phần Sai số cắt cụt tổng thể để biết thêm chi tiết.
Các phương pháp khác, chẳng hạn như phương pháp điểm giữa cũng được minh họa trên các hình, và có vẻ chính xác hơn: sai số của phương pháp điểm giữa gần như tỷ lệ thuận với bình phương của kích thước bước. Vì lý do này, phương pháp Euler được gọi là một phương pháp bậc nhất, trong khi phương pháp điểm giữa là phương pháp bậc hai.
Chúng ta có thể ngoại suy từ bảng trên rằng kích thước bước cần thiết để có được một đáp án chính xác đến ba chữ số thập phân là khoảng 0,00001, có nghĩa là chúng ta cần 400.000 bước. Con số bước rất lớn này đòi hỏi một chi phí tính toán cao. Vì lý do này, người ta thường sử dụng các phương pháp bậc cao, thay thế cho phương pháp Euler, như là các phương pháp Runge-Kutta hoặc các phương pháp đa bước tuyến tính, đặc biệt là nếu muốn đạt được độ chính xác cao.
Nguồn gốc.
Phương pháp Euler có thể được rút ra theo một số cách. Cách thứ nhất, đó là mô tả hình học đã được đề cập ở trên.
Một khả năng khác là xem xét mở rộng Taylor của hàm formula_33 around formula_52: 
Phương trình vi phân formula_54. Nếu phương trình vi phân này thay vào trong mở rộng Taylor và các số hạng bậc hai và bậc cao hơn bị bỏ qua, thì sẽ có được phương pháp Euler. Mở rộng Taylor được sử dụng dưới đây để phân tích sai số của phương pháp Euler, và nó có thể được mở rộng để đạt được các phương pháp Runge-Kutta.
Một cách khác là để thay thế công thức sai phân hữu hạn tiếp tới cho đạo hàm,
trong phương trình vi phân formula_56. Một lần nữa, điều này đem lại phương pháp Euler.[8] Theo cách tương tự sẽ dẫn đến quy tắc điểm giữa và phương pháp Euler lùi lại.
Cuối cùng, ta có thể tích phân phương trình vi phân từ formula_52 tới formula_58 và áp dụng các định lý cơ bản của tích phân và vi phân để có được:
Bây giờ xấp xỉ tích phân bằng phương pháp hình chữ nhật bên trái:
Kết hợp cả hai phương trình, ta lại tìm thấy phương pháp Euler một lần nữa. Cách tiếp cận này có thể được tiếp tục để đi đến nhiều phương pháp đa bước tuyến tính khác.
Sai số cắt cụt cục bộ.
Sai số cắt cụt cục bộ của phương pháp Euler là sai số trong một bước duy nhất. Đó là sự khác biệt giữa lời giải số sau một bước, formula_61, và lời giải chính xác tại thời điểm formula_62. Lời giải số được cho bởi
Đối với lời giải chính xác, chúng ta sử dụng mở rộng Taylor được đề cập trong phần Nguồn gốc phía trên:
Sai số cắt cụt cục bộ (LTE) của phương pháp Euler được cho bởi sự khác biệt giữa các phương trình này:
Kết quả này là hợp lý nếu formula_33 có một đạo hàm bậc ba bị chặn (bounded).
Điều này cho thấy rằng đối với formula_10 nhỏ, các sai số cắt cụt cục bộ xấp xỉ tỷ lệ thuận với formula_68 do đó làm cho phương pháp Euler kém chính xác (đối với formula_10 nhỏ) hơn so với các phương pháp bậc cao khác như các phương pháp Runge-Kutta và các phương pháp đa bước tuyến tính, mà sai số cắt cụt cục bộ tỷ lệ thuận với một số mũ cao hơn của kích thước bước.
Một cách xây dựng công thức hơi khác cho sai số cắt cụt cục bộ là sử dụng dạng thức Lagrange cho số hạng còn lại trong định lý Taylor. Nếu formula_33 có đạo hàm bậc hai liên tục, thì tồn tại một formula_71 mà
Trong các biểu thức sai số trên, đạo hàm bậc hai của lời giải chính xác chưa biết formula_33 có thể được thay thế bằng một biểu thức ở phía bên phải của phương trình vi phân. Thật vậy, từ phương trình formula_54 ta có
Sai số cắt cụt tổng thể.
Sai số cắt cụt tổng thể là sai số tại một thời điểm cố định formula_34, sau nhiều bước nhiều phương pháp cần phải thực hiện để đạt được thời điểm đó từ thời điểm ban đầu. Sai số cắt cụt tổng thể là tích lũy của các sai số cắt cụt cục bộ đã phạm phải trong mỗi bước trước đó. Số lượng các bước được dễ dàng xác định là formula_77, tỷ lệ thuận với formula_78, và sai số đã phạm phải trong mỗi bước tỷ lệ thuận với formula_68(xem phần trước). Vì vậy, mong đợi rằng sai số cắt cụt tổng thể sẽ tỷ lệ thuận với formula_10.
Lý luận trực quan này có thể được chứng minh là chính xác. Nếu lời giải formula_33 có đạo hàm bậc hai bị chặn (bounded) và formula_29 là Lipschitz liên tục trong đối số thứ hai của nó, thì sai số cắt cụt tổng thể (GTE) được bao (bounded) bởi:
trong đó formula_84 là một giới hạn trên cho đạo hàm bậc hai của formula_33 trên khoảng thời gian nhất định nào đó và formula_86 là hằng số Lipschitz của formula_29.
Dạng thức chính xác của giới hạn này ít quan trọng trong thực tế, trong hầu hết các trường hợp, giới hạn này quá lớn so với sai số thực sự phạm phải bởi phương pháp Euler.[16] Điều quan trọng là nó cho thấy rằng sai số cắt cụt tổng thể (một cách gần đúng) tỷ lệ thuận với. Vì lý do này, phương pháp Euler được cho/ gọi là bậc nhất.
Sự ổn định số của phương pháp Euler.
Phương pháp Euler cũng có thể không ổn định về mặt phương pháp số, đặc biệt là đối với các phương trình cứng, có nghĩa là lời giải số tăng rất nhanh trong khi lời giải chính xác không (tăng). Điều này có thể được minh họa bằng cách sử dụng phương trình tuyến tính
Lời giải chính xác là formula_89, phân rã về không khi formula_90. Tuy nhiên, nếu phương pháp Euler được áp dụng cho phương trình này với kích thước bước formula_91, thì lời giải số là sai về mặt định tính: nó dao động và tăng (xem hình). Đây là những gì có nghĩa là không ổn định. Nếu kích thước bước nhỏ hơn được sử dụng, ví dụ formula_92, thì lời giải số không phân rã về không.
Nếu phương pháp Euler được áp dụng cho phương trình tuyến tính formula_93, thì lời giải số không ổn định nếu tích số formula_94 nằm bên ngoài vùng
được minh họa ở phía bên phải. Vùng này được gọi là vùng không ổn định (tuyến tính). Trong ví dụ, formula_96 bằng -2,3, vì vậy nếu formula_91 thì formula_98 tức là nằm bên ngoài vùng ổn định, và do đó lời giải số là không ổn định.
Sự hạn chế này —cùng với việc hội tụ sai số chậm với "h"— làm cho phương pháp Euler không được sử dụng thường xuyên, ngoại trừ như một ví dụ đơn giản của tích phân số.
Các sai số làm tròn.
Thảo luận từ trên đến giờ đã bỏ qua những hậu quả của sai số làm tròn. Trong bước "n" của phương pháp Euler, sai số làm tròn là xấp xỉ độ lớn ε"y""n" trong đó ε là Machine epsilon (giới hạn trên của sai số tương đối do làm tròn trong số học điểm nổi). Giả sử rằng các sai số làm tròn tất cả có kích thước xấp xỉ như nhau, sai số làm tròn tổng hợp trong "N" bước là xấp xỉ "N"ε"y"0 nếu tất cả các sai số chỉ về cùng hướng. Bởi vì số lượng bước tỉ lệ nghịch với kích thước bước "h", tổng sai số làm tròn tỷ lệ thuận với ε / "h". Trong thực tế, tuy nhiên, vô cùng khó xảy ra trường hợp tất cả các sai số làm tròn chỉ về cùng một hướng. Nếu thay vào đó giả định rằng các sai số làm tròn là các biến làm tròn độc lập, thì tổng sai số làm tròn tỷ lệ thuận với formula_99.
Vì vậy, đối với những giá trị kích thước bước cực nhỏ, sai số cắt cụt sẽ nhỏ nhưng tác động của sai số làm tròn có thể lớn. Hầu hết các tác động của sai số làm tròn có thể dễ dàng tránh được nếu phép tổng đền bù (compensated summation) được sử dụng trong việc xây dựng công thức cho phương pháp Euler.
Hiệu chỉnh và mở rộng.
Một hiệu chỉnh đơn giản của phương pháp Euler loại bỏ các vấn đề ổn định đã lưu ý trong phần trước là phương pháp Euler lùi lại (backward):
Phương pháp này khác với phương pháp Euler (tiêu chuẩn, hoặc tiếp tới) là hàm formula_29 được đánh giá tại điểm cuối của bước, thay vì điểm xuất phát. Phương pháp Euler lùi lại là một phương pháp ẩn, có nghĩa là công thức của phương pháp Euler lùi lại có formula_102 ở cả hai bên, vì vậy khi áp dụng phương pháp Euler lùi lại chúng ta phải giải một phương trình. Điều này làm cho việc thực hiện tốn kém (thời gian...) hơn.
Những hiệu chỉnh khác của phương pháp Euler đối với sự ổn định đã đưa đến phương pháp Euler mũ hoặc phương pháp Euler bán ẩn.
Các phương pháp phức tạp hơn có thể đạt được bậc cao hơn (và chính xác hơn). Một khả năng đó là sử dụng nhiều hơn các đánh giá hàm. Điều này được minh họa bằng phương pháp điểm giữa đã được đề cập trong bài viết này:
Điều này dẫn đến họ của các phương pháp Runge-Kutta.
Một khả năng khác là sử dụng nhiều hơn các giá trị quá khứ, như được minh họa bằng phương pháp Adams-Bashforth hai bước: 
Điều này dẫn họ của các phương pháp đa bước tuyến tính.