查看“欧拉方法”的源代码

{{Expand |time=2010-02-26T11:49:32+00:00 }}

在[[数学]]和[[计算机科学]]中，'''欧拉方法'''，命名自它的发明者[[萊昂哈德·歐拉]]，是一种一阶[[数值分析|数值]]方法，用以对给定初值的[[常微分方程]]（即[[初值問題]]）求解。它是一种解决[[数值常微分方程]]的最基本的一类[[显型方法]]（Explicit method）。

== 非正式的几何描述 ==
[[File:Euler method.png|right|thumb|欧拉方法的图示。待求的曲线为蓝色，它的折線近似为红色。]]

考虑计算這樣的一个未知曲線的形状：它具有给定的起点并且满足一个给定的微分方程。 这里，所谓“微分方程”可以看作能够通过曲线上任意点的位置而计算出这一点的[[切线]][[斜率]]的公式。

思路是，一开始只知道曲線的起点（假设为<math>A_0</math>），曲線其他部份是未知的，不過通过微分方程，<math>A_0</math>的斜率可以被计算出来，也就得到了切线。

顺着切线向前走一小步到点<math>A_1</math>。如果我们假设<math>A_1</math>是曲线上的一点（实际上通常不是），那么同样的道理就可以确定下一条切线，依此类推。在经过几步之后，一条[[折线]]<math>A_0A_1A_2A_3\dots</math>就被计算出来了。一般情况下，这条折线与原先的未知曲线偏离不远，并且任意小的误差都可以通过减少步长来得到（虽然对于[[刚性方程]]而言会比较复杂<!--下文将提到-->）。

== 欧拉方法的推导 ==
[[File:Numerical integration illustration, h=1.png|right|thumb|图示为方程<math>y'=y, y(0)=1</math>的数值积分。蓝色为欧拉法，绿色为[[中点法]]，红色为精确解<math>y=e^t</math>。所用步长為<math>h=1.0</math>。]]
[[File:Numerical integration illustration, h=0.25.png|right|thumb|图示为同一个方程在步长<math>h=0.25</math>时的结果。可以看出中点法比欧拉法收敛更快。]]</div>

以以下微分方程為例
:<math>y'(t) = f(t,y(t)), \qquad y(t_0)=y_0, </math> 

希望用 ''y'' 在點 (t<sub>0</sub>,y(t<sub>0</sub>)) 附近的線性近似來得到其近似解（也就是  ''y'' 的[[泰勒展開式]]的前二項）。利用時間 ''t''<sub>n</sub> 時的數值，若用單步的欧拉方法，可得到時間 ''t''<sub>n+1</sub>&nbsp;=&nbsp;''t''<sub>n</sub>&nbsp;+&nbsp;''h'' 時的近似值如下：

:<math> y_{n+1} = y_n + hf(t_n,y_n).  \qquad \qquad</math>

欧拉方法是一種顯型方法，也就是說 <math>y_{n+1}</math> 的解是 <math>y_i</math>,  <math>i \leq n</math> 的顯函數。

欧拉方法可以求解一階的微分方程，而任何<math>N</math>階的微分方程都可以表示成一階的微分方程。

對於微分方程

:<math> y^{(N)}(t) = f(t, y(t), y'(t), \ldots, y^{(N-1)}(t)) </math>

可以通過新設輔助變量 <math>z_1(t)=y(t), z_2(t)=y'(t),\ldots, z_N(t)=y^{(N-1)}(t)</math>，得到以下的等價方程

:<math> \mathbf{z}'(t)
  = \begin{pmatrix} z_1'(t)\\ \vdots\\ z_{N-1}'(t)\\ z_N'(t) \end{pmatrix}
  = \begin{pmatrix} y'(t)\\ \vdots\\ y^{(N-1)}(t)\\ y^{(N)}(t) \end{pmatrix}
  = \begin{pmatrix} z_2(t)\\ \vdots\\ z_N(t)\\ f(t,z_1(t),\ldots,z_N(t)) \end{pmatrix} </math>

這是一個以<math>\mathbf{z}(t)</math>為變量的一階系統，因此可以用歐拉法求解，也可以使用其他的一階數值方法。<ref>{{harvnb|Butcher|2003|p=3}}；{{harvnb|Hairer|Nørsett|Wanner|1993|p=2}}</ref>

==应用例题==
设微分方程为 <math>y'=y</math> ，初始值为 <math>y(0)=1</math>，试用欧拉方法求 <math>y_3</math>的近似值，步长为 <math>h=1</math>。

欧拉法為：

:<math> y_{n+1} = y_n + hf(t_n,y_n).</math>

首先求<math>f(t_0, y_0)</math>（当<math>n = 0</math>），<math>f</math>的定義為<math>f(t,y)=y</math>，因此有

:<math> f(t_0,y_0)=f(0,1)=1.</math>

透過以上步驟，求得解曲線在点<math>(0,1)</math>的切线斜率。回顾直線斜率的定义：<math>y</math>变化量和<math>t</math>变化量的比值，亦記作<math> \Delta y/ \Delta t</math>。 

接著是

:<math> h \cdot f(y_0) = 1 \cdot 1 = 1.</math>

:<math> y_0 + hf(y_0) = y_1 = 1 + 1 \cdot 1 = 2.</math>
 
重复以上步骤求出<math> y_2</math> 和 <math>y_3 </math>的值。

:<math> y_2 = y_1 + hf(y_1) = 2 + 1 \cdot 2 = 4</math>
:<math> y_3 = y_2 + hf(y_2) = 4 + 1 \cdot 4 = 8</math>

由于欧拉法属于递归算法，把運算整理成表格也許有助於避免計算錯誤。

{| class="wikitable"
|-
! <math>y_n</math> !! <math>t_n</math> !!<math>y'(t)</math> !! <math>h</math> !! <math>dy</math> !! <math>y_{n+1}</math>
|-
| 1 || 0 || 1 || 1 || 1 || 2
|-
| 2 || 1 || 2 || 1 || 2 || 4
|-
| 4|| 2 || 4 || 1 || 4 || 8
|}

== 局部截尾误差 ==
欧拉法的局部截尾误差（Local truncation error, LTE）是指在实施一次欧拉法所产生的误差，是指经过一步的数值解<math>y_1</math>与在<math>t_1 = t_0+h</math>时精确解的误差。数值解<math>y_1</math>由以下给出：

:<math> y_1 = y_0 + h f(t_0, y_0). \quad</math>

对于精确解，我们使用泰勒级数展开给出：

:<math> y(t_0 + h) = y(t_0) + h y'(t_0) + \frac{1}{2}h^2 y''(t_0) + O(h^3). </math>

欧拉法的局部截尾误差为：

:<math> \mathrm{LTE} = y(t_0 + h) - y_1 = \frac{1}{2} h^2 y''(t_0) + O(h^3). </math>

当<math>y</math>拥有三阶有界导数时，这个结果是成立的。<ref>{{harvnb|Butcher|2003|p=60}}</ref>

结果显示：当步长<math>h</math>很小时，局部截尾误差近似与 <math>h^2</math> 成比例。也就是说，欧拉法没有其他的高阶方法如[[龙格－库塔法]]和[[线性多步法]]精确，这些方法的局部截尾误差与<math>h^p</math>（''p''>2）成比例。

== 全局截尾误差 ==

全局截尾误差（Global truncation error, GTE）是指在一个固定时间<math>t</math>时的误差，但是很多步之后该方法需要以从初始时间到达该时间来计算。全局截尾误差可以看做是一个每一步的局部截尾误差的累积效应。<ref>{{harvnb|Atkinson|1989|p=344}}</ref> 经过的步骤數為<math>(t-t_0)/h</math>，而每步的误差则正比于<math>h^2</math>。因此，可以预期全局截尾误差是正比于<math>h</math>的。<ref>{{harvnb|Butcher|2003|p=49}}</ref> 

这个直观的推测可以被嚴謹地證明。如果解<math>y</math>存在二阶有界导数，并且<math>f</math>關於<math>y</math>是[[利普希茨连续]]的，那么全局截尾误差是有界的：

:<math> |\text{GTE}| \le \frac{hM}{2L}(e^{L(t-t_0)}-1) \qquad \qquad </math>

其中 <math>M</math> 是在给定区间内<math>y</math>的二阶导数的上界，<math>L</math> 是<math>f</math>的利普希茨常数。<ref>{{harvnb|Atkinson|1989|p=346}}；{{harvnb|Lakoba|2012|loc=公式 (1.16)}}</ref> 

这种精确的形式其实是没有什么意义的，通常情况下这个上界都會嚴重高估了欧拉法所造成的实际误差。<ref>{{harvnb|Iserles|1996|p=7}}</ref>重要的是，这顯示了全局截尾误差是近似正比于<math>h</math>的，所以欧拉法被稱为是一阶的。<ref>{{harvnb|Butcher|2003|p=63}}</ref>

== 註腳 ==
{{reflist}}

== 参考文献 ==
* {{Citation | last1=Atkinson | first1=Kendall A. | title=An Introduction to Numerical Analysis | publisher=[[約翰威立|John Wiley & Sons]] | location=New York | edition=2nd | isbn=978-0-471-50023-0 | year=1989}}.
* {{Citation | last1=Ascher | first1=Uri M. | last2=Petzold | first2=Linda R.|author2-link=Linda Petzold | title=Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations | publisher=[[工業與應用數學會|Society for Industrial and Applied Mathematics]] | location=Philadelphia | isbn=978-0-89871-412-8 | year=1998}}.
* {{Citation | last1=Butcher | first1=John C. | author1-link=John C. Butcher | title=Numerical Methods for Ordinary Differential Equations | publisher=[[約翰威立|John Wiley & Sons]] | location=New York | isbn=978-0-471-96758-3 | year=2003}}.
* {{Citation | last1=Hairer | first1=Ernst | last2=Nørsett | first2=Syvert Paul | last3=Wanner | first3=Gerhard | title=Solving ordinary differential equations I: Nonstiff problems | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-3-540-56670-0 | year=1993}}.
* {{Citation | last1=Iserles | first1=Arieh | author1-link=Arieh Iserles | title=A First Course in the Numerical Analysis of Differential Equations | publisher=[[劍橋大學出版社|Cambridge University Press]] | isbn=978-0-521-55655-2 | year=1996}}.
* {{Citation | last1=Lakoba | first1=Taras I. | title=Simple Euler method and its modifications | type=Lecture notes for MATH334, University of Vermont | year=2012 | url=http://www.cems.uvm.edu/~lakobati/math337/notes_1.pdf | accessdate=2016-01-02}}.

[[Category:数值微分方程]]