Phương pháp Euler

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm
Minh họa phương pháp Euler. Đường cong chưa biết có màu xanh da trời và lời giải gần đúng của nó là đường nhiều cạnh màu đỏ.

Trong toán họckhoa 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).[1]

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[sửa | sửa mã nguồn]

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 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 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 Dọc bước nhỏ này, độ dốc không thay đổi quá nhiều, vì vậy sẽ gần với đường cong. Nếu chúng ta coi vẫn còn nằm trên đường cong, cùng một lý luận như đối với điểm có thể tính được độ dốc và tiếp tuyến của đường cong tại . Sau vài bước, một đường cong đa giác đượ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.[2]

Chọn một giá trị cho kích thước của mỗi bước và đặt . Bây giờ, một bước của phương pháp Euler từ tới [3]

Giá trị của là một lời giải gần đúng của phương trình ODE tại thời điểm : . Phương pháp Euler là phương pháp hiện, nghĩa là lời giải là một hàm hiện của với .

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ụ và có được phương trình tương đương

Đây là một hệ bậc nhất với biến 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.[4]

Ví dụ[sửa | sửa mã nguồn]

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ỉ .[5]

Sử dụng kích thước bước bằng 1 (h = 1)[sửa | sửa mã nguồn]

Minh họa tích phân số cho phương trình Màu xanh da trời là phương pháp Euler; màu xanh lá cây làphương pháp điểm giữa; màu đỏ là lời giải chính xác, Kích thước bước là h = 1.0.

Phương pháp Euler là:

vì vậy trước tiên chúng ta phải tính toán . Trong phương trình vi phân đơn giản này, hàm được định nghĩa bởi . 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 .

Nhớ lại rằng độ dốc được định nghĩa là sự thay đổi trong chia cho sự thay đổi trong , tức là .

Bước tiếp theo là nhân giá trị trên với kích thước bước , 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 , 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ị . Giá trị này sau đó sẽ được thêm vào giá trị 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 , .

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.

0 1 0 1 1 1 2
1 2 1 2 1 2 4
2 4 2 4 1 4 8
3 8 3 8 1 8 16

Đáp án cuối cùng là . Lời giải chính xác của phương trình vi phân là , vì vậy . 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[sửa | sửa mã nguồn]

Với cùng minh họa cho trường hợp h = 0.25.

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 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.

step size result of Euler's method error
1 16 38.598
0.25 35.53 19.07
0.1 45.26 9.34
0.05 49.56 5.04
0.025 51.98 2.62
0.0125 53.26 1.34

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 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.[6]

Nguồn gốc[sửa | sửa mã nguồn]

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 around

Phương trình vi phân . 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.[7] 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 . 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ữaphươ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ừ tới 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.[8] 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ộ[sửa | sửa mã nguồn]

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, , và lời giải chính xác tại thời điểm . 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 có một đạo hàm bậc ba bị chặn (bounded).[9]

Điều này cho thấy rằng đối với nhỏ, các sai số cắt cụt cục bộ xấp xỉ tỷ lệ thuận với do đó làm cho phương pháp Euler kém chính xác (đối với 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 có đạo hàm bậc hai liên tục, thì tồn tại một

[10]

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 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 ta có

[11]

Sai số cắt cụt tổng thể[sửa | sửa mã nguồn]

Sai số cắt cụt tổng thể là sai số tại một thời điểm cố định , 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 đó.[12] Số lượng các bước được dễ dàng xác định là , tỷ lệ thuận với , và sai số đã phạm phải trong mỗi bước tỷ lệ thuận với (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 .[13]

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 có đạo hàm bậc hai bị chặn (bounded) và 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 đó là một giới hạn trên cho đạo hàm bậc hai của trên khoảng thời gian nhất định nào đó và là hằng số Lipschitz của .[14]

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.[15] Vì lý do này, phương pháp Euler được cho/ gọi là bậc nhất.[16]

Sự ổn định số của phương pháp Euler[sửa | sửa mã nguồn]

Lời giải của phương trình được tính toán bằng phương pháp Euler với kích thước bước (các hình vuông màu xanh da trời) và (các hình tròn màu đỏ). Đường cong màu đen biểu diễn lời giải chính xác.

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

Hình tròn lớn màu hồng biểu diễn vùng ổn định đối với phương pháp Euler

Lời giải chính xác là , phân rã về không khi . 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 , 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ụ , 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 , thì lời giải số không ổn định nếu tích số 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).[17] Trong ví dụ, bằng -2,3, vì vậy nếu thì 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[sửa | sửa mã nguồ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 εyn 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εy0 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 .[18]

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.[19]

Hiệu chỉnh và mở rộng[sửa | sửa mã nguồn]

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 đượ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ó ở 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.

Xem thêm[sửa | sửa mã nguồn]

Chú ý[sửa | sửa mã nguồn]

  1. ^ Butcher 2003, tr. 45; Hairer, Nørsett & Wanner 1993, tr. 35
  2. ^ Atkinson 1989, tr. 342; Butcher 2003, tr. 60
  3. ^ Butcher 2003, tr. 45; Hairer, Nørsett & Wanner 1993, tr. 36
  4. ^ Butcher 2003, tr. 3; Hairer, Nørsett & Wanner 1993, tr. 2
  5. ^ See also Atkinson 1989, tr. 344
  6. ^ Hairer, Nørsett & Wanner 1993, tr. 40
  7. ^ Atkinson 1989, tr. 342; Hairer, Nørsett & Wanner 1993, tr. 36
  8. ^ Atkinson 1989, tr. 343
  9. ^ Butcher 2003, tr. 60
  10. ^ Atkinson 1989, tr. 342
  11. ^ Stoer & Bulirsch 2002, tr. 474
  12. ^ Atkinson 1989, tr. 344
  13. ^ Butcher 2003, tr. 49
  14. ^ Atkinson 1989, tr. 346; Lakoba 2012, equation (1.16)
  15. ^ Iserles 1996, tr. 7
  16. ^ Butcher 2003, tr. 63
  17. ^ Butcher 2003, tr. 70; Iserles 1996, tr. 57
  18. ^ Butcher 2003, tr. 74–75
  19. ^ Butcher 2003, tr. 75–78

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]

Bản mẫu:Numerical integrators