4.8.25Numerical Methods
Adaptive step-size — RK45, error control
1,829 words8 min readdifficulty · medium2 backlinks
WHAT we are trying to do
WHY two orders? A single method gives you a number , but no way to know how good it is. If you have a 4th-order estimate and a 5th-order estimate from the same stages , then is essentially the local error of the 4th-order result — for almost no extra cost. This is an embedded pair.
HOW the stages work (the "embedded" idea)
A Runge–Kutta method builds from slope samples:
y_{n+1} = y_n + h\sum_{i=1}^{s} b_i k_i$$ An **embedded pair** shares the same $k_i$ but uses two weight rows $b_i$ (order 5) and $b_i^{*}$ (order 4): $$y^{(5)} = y_n + h\sum_i b_i k_i,\qquad y^{(4)} = y_n + h\sum_i b_i^{*} k_i$$ $$\boxed{\;\varepsilon = y^{(5)} - y^{(4)} = h\sum_i (b_i - b_i^{*})\,k_i\;}$$ > [!intuition] Why this is "free" > The expensive part of any RK method is the function evaluations $k_i$. The two answers reuse **all** of them, so the error estimate costs only a cheap dot product, not extra $f$ calls. --- ## DERIVING the step-update formula from scratch We assume the error of the lower-order method scales like the leading term: $$\varepsilon(h) \approx C\,h^{p+1}, \qquad p = 4 \text{ for RK45.}$$ **WHY:** the order-$p$ method's local truncation error is dominated by its first uncancelled Taylor term, $\propto h^{p+1}$. We want a new step $h_{\text{new}}$ whose error equals the tolerance: $$C\,h_{\text{new}}^{\,p+1} = \text{tol}.$$ Divide the two equations to eliminate the unknown constant $C$: $$\frac{\text{tol}}{\varepsilon} = \frac{C h_{\text{new}}^{p+1}}{C h^{p+1}} = \left(\frac{h_{\text{new}}}{h}\right)^{p+1}.$$ Solve for $h_{\text{new}}$: $$\boxed{\,h_{\text{new}} = h \left(\frac{\text{tol}}{\varepsilon}\right)^{1/(p+1)}\,}$$ > [!formula] Practical step controller > $$h_{\text{new}} = h \cdot \min\!\Big(f_{\max},\;\max\big(f_{\min},\; S\,(\text{tol}/\varepsilon)^{1/(p+1)}\big)\Big)$$ > - $S \approx 0.8$–$0.9$ : **safety factor** (don't gamble on hitting tol exactly). > - $f_{\min}\approx 0.2,\; f_{\max}\approx 5$ : clamp so $h$ never jumps wildly. > - $p+1 = 5$ for RK45. > **WHY the safety factor?** $\varepsilon$ is itself an estimate; aim slightly *under* tol so the retried step is likely accepted on the first try. ![[4.8.25-Adaptive-step-size-—-RK45,-error-control.png]] --- ## Worked Example 1 — accept and grow > [!example] One adaptive step > Suppose at a step you used $h = 0.10$, got $\varepsilon = 1\times10^{-7}$, tol $= 1\times10^{-6}$, $S=0.9$, $p=4$. > > **Step 1 — accept?** $\varepsilon < \text{tol}$ ✔ → accept this step. > *Why this step?* Error is under budget, so the answer is good enough. > > **Step 2 — new $h$:** ratio $= \text{tol}/\varepsilon = 10$. > $$h_{\text{new}} = 0.9 \times 0.10 \times 10^{1/5} = 0.09 \times 1.585 = 0.143.$$ > *Why this step?* We had error to spare, so we **grow** $h$ to work faster — but only by $10^{1/5}$, not by 10, because error scales like $h^5$. ## Worked Example 2 — reject and shrink > [!example] A rejected step > Now $h = 0.10$, $\varepsilon = 4\times10^{-6}$, tol $= 1\times10^{-6}$. > > **Step 1 — accept?** $\varepsilon > \text{tol}$ �’ → **reject**, redo the step. > *Why this step?* The step is too inaccurate; we must not advance $t$. > > **Step 2 — new $h$:** ratio $= 0.25$. > $$h_{\text{new}} = 0.9\times0.10\times0.25^{0.2} = 0.09\times0.758 = 0.068.$$ > *Why this step?* Shrink $h$ so the **retried** step's predicted error $\approx C h_{\text{new}}^5 = $ tol. We retry from the *same* $t_n$ with $0.068$. ## Worked Example 3 — clamp in action > [!example] Forecast-then-verify > $h = 0.05$, $\varepsilon = 1\times10^{-12}$, tol $=1\times10^{-6}$, $f_{\max}=5$. > Raw factor $= 0.9\,(10^{6})^{1/5} = 0.9\times 15.8 = 14.2$. > **Forecast:** that would 14×-enlarge $h$ — dangerous! > **Verify:** the controller clamps to $f_{\max}=5$, so $h_{\text{new}} = 0.25$. > *Why this step?* The $h^5$ model is only trustworthy locally; a 14× jump could land in a region the model never saw. Clamping keeps us safe. --- > [!mistake] Steel-manned errors > **Mistake A:** "Error scales like $h^4$ so use exponent $1/4$." > *Why it feels right:* RK45's *result* is order 4 (or 5). **Fix:** the **local** error per step is $\sim h^{p+1}=h^5$, so the exponent is $1/(p+1)=1/5$. Using $1/4$ makes the controller over-react. > > **Mistake B:** "After rejecting, advance $t$ with the smaller $h$." > *Why it feels right:* You "did work," so it seems wasteful to throw it away. **Fix:** a rejected step means $y_{n+1}$ is untrustworthy — you must **stay at $t_n$** and recompute with the new $h$. > > **Mistake C:** Using only absolute tolerance. > *Why it feels right:* simpler. **Fix:** if $|y|$ grows large, a fixed atol is impossibly strict; mix in $\text{rtol}\,|y|$ so tolerance scales with the solution. > > **Mistake D:** "The error estimate is the error of $y^{(5)}$." > *Why it feels right:* you advance with $y^{(5)}$ (local extrapolation). **Fix:** $\varepsilon$ estimates the *4th-order* error; it bounds the worse of the two, which is conservative — that's fine. --- > [!recall]- Feynman: explain to a 12-year-old > Imagine driving a car and you want to stay on a winding road without crashing. On long straight bits you speed up; near sharp turns you slow down. To know how sharp the turn is, you peek with **two cameras** — one rough, one sharp — and see how different their pictures are. If they barely differ, the road is straight: floor it (bigger step). If they disagree a lot, a turn is coming: brake (smaller step). RK45 is exactly this: two answers, compare them, and choose your speed (step size) so you never make a big mistake. > [!mnemonic] Remember the controller > **"Tol Over Error, to the Fifth-root"** → $h_{\text{new}} = h\,(\text{tol}/\varepsilon)^{1/5}$. > And **"Reject → Repeat, Accept → Advance."** --- ## #flashcards/maths Why does RK45 compute two solutions per step? ::: To get a free local-error estimate $\varepsilon = y^{(5)}-y^{(4)}$ from the *same* stage evaluations $k_i$. What is an "embedded" Runge–Kutta pair? ::: Two methods of different order sharing the same $k_i$ but different weight rows $b_i,\,b_i^*$. Local error of an order-$p$ method scales as? ::: $C\,h^{p+1}$. Derive the new step size. ::: From $\varepsilon\approx Ch^{p+1}$ and $\text{tol}=Ch_{\text{new}}^{p+1}$, divide to cancel $C$: $h_{\text{new}}=h(\text{tol}/\varepsilon)^{1/(p+1)}$. For RK45 (order 4 controlled), what exponent updates $h$? ::: $1/(p+1)=1/5$. What do you do after a rejected step? ::: Stay at $t_n$, recompute with the smaller $h_{\text{new}}$; do NOT advance $t$. Purpose of safety factor $S\approx0.9$? ::: Aim slightly under tol so the retried/next step usually passes first time. Why clamp $h_{\text{new}}$ with $f_{\min},f_{\max}$? ::: The $h^{p+1}$ model is only locally valid; clamps prevent wild jumps. Standard tolerance formula? ::: $\text{tol}=\text{atol}+\text{rtol}\,|y_n|$. Why is the error estimate essentially "free"? ::: It reuses all expensive $f$-evaluations; only a cheap weighted sum is added. --- ## Connections - [[Runge–Kutta Methods (RK4)]] — the fixed-step parent of RK45. - [[Local vs Global Truncation Error]] — why $h^{p+1}$ governs the step controller. - [[Order of a Numerical Method]] — defines the $p$ in the exponent. - [[Stiff ODEs and Stability]] — when adaptive explicit methods still struggle. - [[Taylor Series Expansion]] — origin of the leading error term. - [[Dormand–Prince (RK45 used by scipy solve_ivp)]] — the standard coefficient table. ## 🖼️ Concept Map ```mermaid flowchart TD FIXED[Fixed step h wasteful] -->|motivates| ADAPT[Adaptive step-size] ADAPT -->|needs| ESTERR[Free error estimate] RK45[RK45 embedded pair] -->|provides| ESTERR RK45 -->|shares| STAGES[Same slopes k_i] STAGES -->|weighted by| Y4[Order-4 estimate] STAGES -->|weighted by| Y5[Order-5 estimate] Y5 -->|difference| EPS[Error epsilon] Y4 -->|difference| EPS TOL[tol = atol + rtol times y] -->|compare with| DECIDE{epsilon <= tol} EPS -->|compare with| DECIDE DECIDE -->|yes| ACCEPT[Accept step] DECIDE -->|no| REJECT[Reject and shrink h] EPS -->|assume C h^p+1| UPDATE[h_new formula] TOL -->|eliminate C| UPDATE UPDATE -->|with safety S| CTRL[Step controller] ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Dekho, jab hum ODE $y'=f(t,y)$ ko numerically solve karte hain, toh fixed step $h$ lena bekaar hai. Jahan solution smooth hai wahan bade steps le sakte hain, aur jahan curve tezi se mudta hai wahan chhote steps chahiye. **Adaptive step-size** ka matlab hai: algorithm khud measure karta hai ki "main kitna galat hoon" aur uske hisaab se $h$ ko bada ya chhota karta hai. Yahi RK45 (Runge-Kutta-Fehlberg / Dormand-Prince) ka kaam hai. > > Trick yeh hai ki ek hi step mein hum **do** answers nikaalte hain — ek 4th order ($y^{(4)}$), ek 5th order ($y^{(5)}$) — aur dono same slope evaluations $k_i$ use karte hain. Inka difference $\varepsilon = y^{(5)}-y^{(4)}$ hamara **free error estimate** hai, kyunki naye function calls nahi lagte, bas ek cheap weighted sum. > > Ab step kaise badle? Local error scale karta hai $C h^{5}$ ki tarah (order $p=4$, exponent $p+1=5$). Hum chahte hain error = tol. Do equations divide karke $C$ cancel karo, mil jaata hai $h_{new}=h\,(tol/\varepsilon)^{1/5}$. Safety factor $0.9$ lagao taaki thoda neeche aim karein, aur factor ko $0.2$ se $5$ ke beech clamp karo taaki $h$ pagal jump na maare. > > Sabse important yaad rakhne wali baat: agar $\varepsilon > tol$ ho toh step **reject** karo — $t$ ko aage mat badhao, same point se chhote $h$ ke saath dobara karo. Agar $\varepsilon \le tol$ ho toh **accept** karo aur agla $h$ thoda bada le lo. Yahi se solver fast bhi hota hai aur accurate bhi. "Reject → Repeat, Accept → Advance" — bas yeh mantra yaad rakho. ![[audio/4.8.25-Adaptive-step-size-—-RK45,-error-control.mp3]]