Runge-Kutta法

喺數值分析當中， Runge-Kutta法（德文：Runge-Kutta-Verfahren，英文：Runge-Kutta methods）、又可以叫龍俄-厥他法（粵拼：lung4 ngo4 - kyut3 taa1 faat3），簡稱RK法，查實係一系列隱式同顯式迭代方法，其中包括眾所周知嘅喊做Euler法嘅例程，呢個例程用於幫常微分方程嘅近似解做時間離散化。 啲方法係由德國數學家Carl Runge跟Wilhelm Kutta於1900年左右開發出嚟嘅。
微分方程y'= sin（t）^ 2 * y嘅Runge-Kutta法嘅比較（橙色為精確解）

經典RK法
經典Runge-Kutta法使用嘅斜率
Runge-Kutta系列裏便最廣為人知嘅一種通常着喊做「 RK4」、「經典Runge-Kutta法」抑或直程「 Runge-Kutta法」，「4」係因爲有四階。
指定一個初值問題：
其中係時間嘅未知函數（標量抑或向量）  ，有待逼近；已知嘅變化值係跟本身嘅函數。喺初始時間，個值係 。畀有函數跟初始條件 ，。
而今揀一個𨂾長h > 0並定義埋：
對於n = 0、1、2、3，...，使用
（注意：以上等式喺唔同嘅文本裏便具有唔同但等效嘅定義）。
呢度嘅係嘅RK4近似值 ，同埋下一個值（  ）由當前值（  ）加埋四個增量嘅加權平均值嚟決定，其中每個增量都係一個乘積、由間隔大細h乘埋一個估出嘅斜率得出嘅，個斜率k由微分方程右側嘅函數 f 指定。
係區間開頭嘅斜率，用到 （歐拉法）;
係區間中點嘅斜率，用到跟 ;
又係中點度嘅斜率，之用到跟 ;
係區間孻尾嘅斜率，用到跟 。
喺對四個斜率求平均值陣時，對中點度嘅斜率賦予大啲嘅權重。若果獨立於 ，即微分方程相當於一個簡單嘅積分，係噉RK4就係Simpson法則（英文：Simpson's rule）。
種RK4方法係四階方法，噉樣代表局部截尾誤差同階於 ，而總累積誤差同階於 。
喺許多實際應用裏便，隻函數獨立於 （所謂嘅自治系統（autonomous system）抑或時唔變系統，特別係喺物理學裏便），而且佢哋嘅增量根本唔會得到計算，亦都唔會傳遞畀函數 ，只有對個最終公式用到。

顯式RK法
顯式Runge-Kutta法家族係上述RK4方法嘅概括，之係噉樣得出：
其中
（注意：以上公式喺某些文本裏便可能具有唔同但等效嘅定義）。
要指定一個特定嘅方法，就要提供整數s（級數）、係數aij（對於 1 ≤ j < i ≤ s）、bi（對於i = 1，2，...， s ）同埋ci （對於i = 2，3，...， s ）。矩陣[aij]着喊做Runge-Kutta矩陣，而 bi 、ci着喊做權重、節點。 啲數據通常係攞一套助記手段喊做Butcher表（Butcher tableau ）嘅形式嚟排列（根據返John C. Butcher個名）：
泰勒級數展開表明，Runge-Kutta法相容（consistent）若且唯若有：
若果要求呢個方法有返一定階數p ，噉亦都有相應嘅要求，噉樣意味住局部截尾誤差為O(hp+1)。啲可以從截尾誤差本身嘅定義裏便得出。譬如，若果b1 + b2 = 1， b2c2 = 1/2， b2a21 = 1/2，噉兩級方法嘅階數為2。 請注意，確定係數嘅常用條件係：
之不過，僅衹呢個條件唔夠保持相容性。
一般嚟講，若果階龍格-庫塔方法有階，噉就證明得到級數必須滿足 ， 而若果 ， 就有 。 但係，仲唔知道喺所有情況下啲界限係唔係都咁清晰（sharp）。譬如，所有啲已知嘅8階方法至少有11級，即使有可能存在啲方法少啲級嘅。 （上便個範圍表明到可能係有9級嘅方法；但亦都可能係個範圍根本唔清晰。 ）實質上，確切嘅最細級數仲係一個開放問題（open problem）、對於一個顯式階Runge-Kutta法嚟講，因爲仲未發現啲方法、滿足得上述啲範圍入便啲等號嘅。一些已知嘅值係：
上便啲證明得嘅範圍就意味住搵唔到階數嘅方法，所需級數少過目前搵到嘅同階方法嘅。但係，可以想像到，搵得到一種階數之只有8級嘅方法，之不過如表所示而今已知嘅方法至少要到9級。

例子
RK4法屬於呢個框架。佢個Butcher表係：
0

1/6
1/3
1/3
1/6
種Runge-Kutta法嘅其中一種熹微變體亦都歸功於1901年Kutta，喊做3/8規則。呢個方法嘅主要優點係，幾乎所有啲誤差係數都細過啲流行方法入便嘅誤差係數，但每一𨂾時間需要稍爲多啲嘅FLOP（浮點運算）。佢個Butcher表係：
0

1/8
3/8
3/8
1/8
但係，最簡單嘅Runge-Kutta法梗係（正向）歐拉法，公式係 。呢個係唯一相容（consistent）嘅一級顯式Runge-Kutta法。個相應圖表係：
0



0
1
中點法唔係唯一嘅兩級二階Runge-Kutta法。有一系列噉樣嘅方法，由α參數設定並由以下公式畀出：
個Butcher表係：
0
喺噉樣嘅方法族入便，嗰陣畀出中點法，而嗰陣係Heun法。

使法
譬如，考慮α= 2/3嘅兩級二階Runge-Kutta法，之亦都喊做Ralston方法。佢由表格畀出：
0


1/4
3/4
用到相應嘅方程式
呢個方法用於解決初值問題
其中𨂾長h = 0.025，因此呢個方法需要執行四𨂾。
呢個方法進行如下：
數值解對應於帶下劃線啲值。

自適應RK法
自適應方法旨喺產生單個Runge-Kutta𨂾步嘅局部截尾誤差嘅估計。噉樣可以通過兩種方法來完成，一種係有序嘅還有一個訂單 。啲方法係交織嘅，即佢哋有共同嘅中間𨂾步。因此，戥採用高階方法嘅一𨂾相比，估計誤差嘅計算成本好細抑或可忽略唔計。
喺積分期間，𨂾長會着調整，嚟令估計嘅誤差保持喺用戶定義嘅閾值以下：若果誤差太大，噉攞細啲嘅𨂾長重複執行過一𨂾；若果誤差細得多，就增加𨂾長嚟慳時間。噉樣（幾乎）可以畀出最佳𨂾長，同時慳返計算時間。而且，用戶唔使嘥時間來搵返啱嘅𨂾長。
低階𨂾步由以下式得出：
其中戥高階方法相同。然之後個誤差係：
噉樣係 。幫呢種方法擴展Butcher表，嚟畀出 ：
0
Runge-Kutta-Fehlberg法具有5跟4階兩種方法。佢嘅擴展後嘅Butcher表係：
0


25/216
0
1408/2565
2197/4104
−1/5
0
但係，最簡單嘅自適應Runge-Kutta法涉及Heun法（階數2）佮Euler法（階數1）嘅組合。佢嘅擴展後嘅Butcher表係：
0


1
0
其他啲自適應嘅Runge-Kutta法有Bogacki-Shampine法（3、2階）同埋Cash-Karp法跟Dormand-Prince法（5、4階）。

非融合RK法
若果互相之間唔同，噉Runge-Kutta法就着認爲係非融合嘅（nonconfluent）。

隱式RK法
到目前為止，所有啲提到嘅Runge-Kutta法都係顯式方法。顯式嘅Runge-Kutta法通常唔適合於攞嚟求解啲剛性方程（Stiff equations），因為佢哋嘅絕對穩定域好細。特別係佢係有界嘅。 噉樣個問題喺偏微分方程求解裏便尤為重要。
顯式Runge-Kutta法個唔穩定性激唨啲隱式方法嘅發展。隱式Runge-Kutta法具有以下形式：
其中
顯式方法嘅區別喺於，喺顯式方法裏便， j嘅總和僅衹等於i -1。呢個亦都顯示喺張Butcher表裏便，當中顯式方法個係數矩陣係下三角形式。喺隱式方法裏便， j度嘅總和上升到s而且係數矩陣唔係三角形，係噉畀出對應嘅Butcher表形式：
請參閱返上方嘅自適應Runge-Kutta法嚟獲取有關排嘅介紹。
呢種差異導致，每一𨂾都必須求解代數方程組。噉樣大大增加唨計算成本。若果使用s級嘅方法求解m個分量嘅微分方程，噉個代數方程組將具有ms個分量。噉樣可以戥隱式線性多步法（ODE嘅另一種大方法系列）形成對比：隱式s𨂾線性多步方法需要求解只有m個分量嘅代數方程組，因此系統嘅大細唔會隨住𨂾數增加而增加。

例子
隱式Runge-Kutta法嘅最簡單示例係後褪Euler法：
張Butcher表好簡單：
呢張Butcher表戥以下公式相對應
可以重新排列嚟獲得上便列出嘅後褪Euler法嘅公式。
隱式Runge-Kutta法嘅另一個示例係梯形規則。佢個Butcher表為：
梯形規則係一種選點法（似文中所述）。所有選點法都係隱式Runge-Kutta法，但並非所有隱式Runge-Kutta法都係選點法。
Gauss-Legendre法構成唨一系列基於Gauss正交嘅搭配方法。s級嘅Gauss-Legendre法嘅階數為2 s （因此，可以構造任意高階嘅方法）。 兩級（即有四階）嘅方法會有噉樣嘅Butcher表：

穩定
戥顯式方法相比，隱式Runge-Kutta法嘅優勢喺於其更大嘅穩定性，尤其係喺應用於剛性方程嗰陣。考慮線性測試方程y' = λy。應用到呢條方程嘅Runge-Kutta法簡化成迭代式 ，其中r由下式得出：
其中e代表1嘅向量。函數r喊做穩定性函數。 從公式可以得出，若果呢個方法有s級，噉r係兩個次數為s嘅多項式個商。顯式方法有嚴格意義上嘅下三角矩陣A ，噉樣意味住det（ I - zA ）= 1而且穩定性函數係多項式。
若果|r(z)| < 1，z = hλ ，線性測試方程嘅數值解將衰減到零。噉樣嘅z嘅集合喊做絕對穩定性域。特別嚟講，若果啲Re(z) < 0嘅z係喺嗮絕對穩定域，呢個方法就着認為係絕對穩定嘅。顯式Runge-Kutta法嘅穩定性函數係多項式，因此顯式Runge-Kutta法永遠唔會係A穩定嘅。
若果方法嘅階數為p ，噉穩定性函數滿足陣時 。因此，研究畀定次數嘅多項式個商、之逼近指數函數嘅，會好有趣。啲喊做Padé近似值。若且唯若'm≤N≤M' + 2嗰陣，一個Padé近似值有m次嘅分子同埋n次嘅分母嘅先係A穩定嘅。
s級嘅Gauss-Legendre法嘅階數為2 s ，因此佢個穩定性函數為m = n = s嘅Padé近似值。因此，呢個方法係A穩定嘅。 噉樣表明A穩定嘅Runge-Kutta可以有任意高嘅階。相反，A穩定線性多步法嘅階數唔超得過2。

B穩定性
微分方程解嘅A穩定性概念同線性自治方程有關 。 Dahlquist進行唨一項研究針對啲數值方案嘅穩定性、啲應用於滿足單調性條件嘅非線性系統嘅。相應嘅概念被定義為：G穩定性同埋B穩定性（Butcher，1975），分別對應多步方法（同埋戥佢相關嘅啲單腿方法（one-leg methods））同埋Runge-Kutta法。 Runge-Kutta法應用於非線性系統 ，有；若果呢種情況意味住兩個數值解，噉就喊做B穩定。
設 ， ，係三個矩陣，定義爲：
若果跟矩陣都係非負定嘅，噉呢個Runge-Kutta法就可以講係代數穩定嘅 。 B穩定性嘅充分條件係： 跟係非負定嘅。

四階RK法嘅推導
一般來講，階Runge-Kutta法寫得成：
其中：
係通過評估喺第 階嘅導數嚟獲得嘅增量。
如前所述，喺任一間隔嘅起點、中間點、末點進行求值，捉代入通用公式可以得到四階Runge-Kutta方法。因此，揀：
否則。首先定義以下數量：
其中跟 。若果定義：
對於先前嘅關係，可以證明以下等式滿足得 ：
其中：
係對應時間嘅個總導數（total derivative）。
若果而今使用啱啱導出嘅內容來表達通用公式，噉會得到：
並捉佢戥附近嘅泰勒級數比較，有 ：
獲有一個係數約束系統：
個系統解出陣時畀出，似之前噉。