單步法

數值分析裡的單步法（one-step methods）和多步法（multistep methods）是求解初值問題的數值方法的兩種分類。常微分方程和初值問題在自然科學、工程物理學中都很重要，在經濟學和社會科學中的重要性也慢慢提高。

單步法近似初值問題，給定起始值${\displaystyle A_{0}}$，可以找到${\displaystyle A_{1}}$、${\displaystyle A_{2}}$等

單步法背後的基本概念是從給定的起點出發，沿著想要的解，一步一步的計算近似解。單步法只使用最近的資訊計算下一個點的資訊，多步法則不同，多步法還會考慮更早的資訊。單步法粗略可以分為兩類：顯式法是直接計算新的近似值，隱式法是將新的近似值和目前已知的資訊形成方程，需求解方程才能知道新的近似值。後者更適用於剛性方程（stiff equation，其數值分析的解只有在時間間隔很小時才會穩定，只要時間間隔略大，其解就會不穩定）。

最簡單也最古老的單步法，是顯式歐拉法，由萊昂哈德·歐拉在1768年發表。後來，在1883年，出現了許多的多步法。而卡爾·龍格、Karl Heun（英語：Karl Heun）和馬丁·威廉·庫塔在1900年針對歐拉法進行大幅改進，之後出現了許多龍格-庫塔法的算法，也是單步法中最重要的一組算法。二十世紀的發展包括外推的概念、以及考慮步長的控制，也就是在每一步經計算後，選擇下一步的步長。這些概念組成了求解複雜初值問題的基礎，常出現在現有的應用中，利用電腦可以有效率的求解問題，而且可以達到要求的精度。

基本概念

考慮以下初值問題的通式，要找到函數${\displaystyle y}$滿足以下的方程

${\displaystyle y'(t)=f(t,y(t)),\quad y(t_{0})=y_{0}}$

其中${\displaystyle f}$是已知的函數

洛倫茲吸引子微分方程的解，是三維空間中的複雜曲線

若${\displaystyle y'(t)}$和${\displaystyle y(t)}$等比例，則${\displaystyle y(t)}$會指數增長。因此，${\displaystyle y'(t)=\lambda y(t)}$，其成長率是${\displaystyle \lambda }$，也有初始條件${\displaystyle y(0)=y_{0}}$。此時，可以用初等的微積分配合指數函數求得結果：${\displaystyle y(t)=y_{0}e^{\lambda t}}$。

微分方程中所要求的函數${\displaystyle y}$其值也可以是向量，也就是針對每一個${\displaystyle t}$，${\displaystyle y(t)=(y_{1}(t),\dotsc ,y_{d}(t))}$是一個${\displaystyle d}$個元素的向量。這也是${\displaystyle d}$維微分方程的系統。以移動物體為例，${\displaystyle y(t)}$是其d維空間中的位置，而${\displaystyle y'(t)}$是其時間${\displaystyle t}$的速度。因此微分方程標示了物體軌跡上每一點的速度方向和大小。就可以由此計算軌跡。

在上述簡化版的指數成長問題中，可以直接求解。但大多數的微分方程問題更複雜，也無法求得解析解。在特定條件下，可以證明針對函數${\displaystyle f}$，其初始值問題的解存在，但無法用分析的解法求解（例如分離變數法、指數法或是變分法），因此需要利用數值方法，找到其近似解。

初值問題的數值方法要在${\displaystyle t_{0}<t_{1}<t_{2}<\ldots }$各時間，逐步計算待求解函數的值${\displaystyle y(t_{0}),y(t_{1}),y(t_{2}),\dotsc }$。單步法在計算${\displaystyle y_{j+1}}$近似值時，只需要${\displaystyle y_{j}}$的近似值，與其相對的，多步法在計算${\displaystyle y_{j+1}}$近似值時，除了${\displaystyle y_{j}}$近似值以外，還至少需要${\displaystyle y_{j-1}}$，甚至${\displaystyle y_{j-2}}$......的值。

顯式歐拉法的前二步

最簡單也最基本的單步法就是顯式歐拉法，是瑞士數學家和物理學家萊昂哈德·歐拉於1768年提出的^[1]。此方法的概念是由分段線性函數來近似要求的解，而從點${\displaystyle t_{j+1}}$到點${\displaystyle f(t_{j},y_{j})}$的斜率是由${\displaystyle t_{j}}$時的資訊所決定。更深入的說：問題定義只提供了此函數的初值：${\displaystyle y(t_{0})=y_{0}}$，而且，此點的斜率也是已知的，${\displaystyle y'(t_{0})=f(t_{0},y_{0})}$。因此，可以確定函數在此點的切線斜率，並以此近似函數在往後時間的特性。在點${\displaystyle t_{1}>t_{0}}$，可以得到以下的結果，而步長為${\displaystyle h_{0}:=t_{1}-t_{0}}$

${\displaystyle y(t_{1})\approx y_{0}+h_{0}f(t_{0},y_{0})=:y_{1}}$.

此作法可以繼續進行。最後，以下計算的結果就是顯式歐拉法

${\displaystyle y_{j+1}=y_{j}+h_{j}f(t_{j},y_{j}),\quad j=0,1,2,\dotsc }$

其遞增量${\displaystyle h_{j}=t_{j+1}-t_{j}}$.^[2]

顯式歐拉法是許多單步法的基礎，其斜率${\displaystyle f(t_{j},y_{j})}$由其他近似函數在點${\displaystyle t_{j}}$和點${\displaystyle t_{j+1}}$之間行為的運算代替。單步法的另一個概念是來自隱式歐拉法，用${\displaystyle f(t_{j+1},y_{j+1})}$為斜率。初看會認為這作法不一定合適，因為此時${\displaystyle y_{j+1}}$未知，不過，若以此往下計算，就得到以下的方程

${\displaystyle y_{j+1}=y_{j}+h_{j}f(t_{j+1},y_{j+1})}$

可以以此求解${\displaystyle y_{j+1}}$（若有需要的話，也可以用數值方法求解）。例如用顯式歐拉法和隱式歐拉法的算術平均數作為斜率，這就是隱式梯形法。若等式右側未知的${\displaystyle y_{j+1}}$用顯式歐拉法近似，也可以得到另一個顯式法，這稱為Heun方法^[3]。所有方法和擴展都有一步法的基本概念：

${\displaystyle y_{j+1}=y_{j}+h_{j}\Phi }$

其斜率${\displaystyle \Phi }$是由${\displaystyle t_{j}}$ , ${\displaystyle y_{j}}$, ${\displaystyle h_{j}}$以及（針對隱式歐拉法）${\displaystyle y_{j+1}}$所決定。

定義

單步法可以定義如下：令 ${\displaystyle y}$ 是以下初值問題的解

${\displaystyle y'(t)=f(t,y(t))}$, ${\displaystyle \quad y(t_{0})=y_{0}}$.

假設解

${\displaystyle y\colon I\to \mathbb {R} ^{d}}$

存在在一定區間${\displaystyle I=[t_{0},T]}$內，而且其值唯一。以下時間

${\displaystyle t_{0}<t_{1}<t_{2}<\ldots <t_{n}=T}$

是區間${\displaystyle I}$內滿足上述條件的時間點，且${\displaystyle h_{j}=t_{j+1}-t_{j}}$是對應的增量，則以下

${\displaystyle y_{j+1}=y_{j}+h_{j}\Phi (t_{j},y_{j},y_{j+1},h_{j})}$, ${\displaystyle \quad j=0,\dotsc ,n-1}$

就是單步法的公式，其斜率函數為${\displaystyle \Phi }$。若${\displaystyle \Phi }$和${\displaystyle y_{j+1}}$無關，這個單步法就是顯式的，不然，在每一個${\displaystyle j}$都要求解方程，才能得到解在該時間的值，這就是隱式的單步法^[4]。

一致性和收斂性

收斂階數

針對實際使用的單步法，所計算的${\displaystyle y_{j}}$應該是其解${\displaystyle y}$在點${\displaystyle t_{j}}$的值${\displaystyle y(t_{j})}$之良好近似。若其變數是通用的${\displaystyle d}$維向量，此近似的好壞會用向量範${\displaystyle \|y_{j}-y(t_{j})\|}$來量測，也就是在該點${\displaystyle t_{j}}$的誤差。若可以將其步階收斂到零時，會希望針對所有${\displaystyle j}$的誤差都快速的收斂到零。為了考慮非定值步階的情形，會將${\displaystyle h}$準確定義為所使用步階的最大值，在所有點${\displaystyle j}$裡最大誤差的特性會和${\displaystyle h}$的冪次比較。求解給定初值問題的單步法，其收斂階數（Convergence order）為${\displaystyle p\geq 1}$，若以下估測值

${\displaystyle \max _{j=0,\dotsc ,n}\|y_{j}-y(t_{j})\|\leq Ch^{p}}$

適用在所有夠小的${\displaystyle h}$上，其常數${\displaystyle C>0}$，和${\displaystyle h}$無關^[5]。要比較不同的單步法時，收斂階數是最重要的參數^[6]。較高收斂階${\displaystyle p}$的方法，在固定步階下的總誤差較小，若要到給定的精度，需要的步數也比較少。針對${\displaystyle p=1}$的方法，可以預期若步階變一半，其總誤差也只會變成一半。若收斂階數${\displaystyle p=4}$的方法，步階變一半，總誤差會是${\displaystyle {\bigl (}{\tfrac {1}{2}}{\bigr )}^{4}={\tfrac {1}{16}}}$。

全域誤差和局部誤差

收斂階數的${\displaystyle \|y_{j}-y(t_{j})\|}$是由兩個獨立的因素所組成，乍看之下會很複雜。一方面，誤差是由每一步用數值方法近似函數未知梯度的誤差有關，但是，也需要考慮每一步的起始點${\displaystyle (t_{j},y_{j})}$和真正起始點${\displaystyle (t_{j},y(t_{j}))}$之間的誤差，目前這一步的誤差也會和以往各步的誤差有關。因為單步法一致性的定義，不同方式的差異只會在程序函數${\displaystyle \Phi }$的選擇，不過可以證明，在${\displaystyle \Phi }$符合特定條件下，可以從單一步的誤差階數推斷收斂階數，這稱為一致階數（consistency order）。

一致的概念是現代數值分析裡，通用的中心概念。數值分析方式的收斂性和數值近似如何近似其確切解有關，一致性要問的是逆問題的簡化版：其確切解可以多符合其數值方式的規格？在通用理論中，一個方法若是一致和穩定的，就是收斂的。為了簡化說明，以下的說明中假設存在顯式單步法

${\displaystyle y_{j+1}=y_{j}+h\Phi (t_{j},y_{j},h)}$

而且其固定步階為${\displaystyle h}$。其真實解為${\displaystyle t\mapsto y(t)}$，局部截尾誤差（也稱為局部處理誤差）${\displaystyle \eta }$ 定義為^[7]

${\displaystyle \eta (t,h)=y(t)+h\Phi (t,y(t),h)-y(t+h)}$.

因此，假設其確切解已知。從${\displaystyle (t,y(t))}$開始單步法的步階，形成了在${\displaystyle t+h}$和確切解的誤差。接著定義：單步法有一致階數（consistency order）${\displaystyle p\geq 1}$若以下估測值的算式成立

${\displaystyle \|\eta (t,h)\|\leq Ch^{p+1}}$

針對所有夠小的${\displaystyle h}$，其常數${\displaystyle C>0}$和${\displaystyle h}$無關。

一致階數和收斂階數中很大的差異是一致階數是${\displaystyle h^{p+1}}$而不是${\displaystyle h^{p}}$。這可以解釋成在局部誤差轉換到全域誤差時，少了一層步階${\displaystyle h}$的影響。以下定理是單步法的核心：^[8]

若過程函數${\displaystyle \Phi }$為利普希茨連續，且其相關的單步法有一致階數${\displaystyle p}$，則其也有收斂階數${\displaystyle p}$。

過程函數的利普希茨連續是針對穩定性的額外要求，若微分方程本身的${\displaystyle f}$是利普希茨連續，其過程函數多半也會是利普希茨連續。不過在大部份的應用都要假設此要求，以確保其初始值問題有唯一可解性，此時已可以確定單步法的一致階數。理論上，這可以用${\displaystyle \eta (t,h)}$的泰勒級數求得。但實務上，高階的公式很複雜，不易理論，因此需要額外的概念以及表示法來處理此議題^[9]。

相關條目

• 常微分方程數值方法