7.2 Butcher-tabeller og ordensbetingelser

Eksplisitt Euler. Ett steg, ingen forskyvning, vekt 1:

$$\begin{array}{c|c}0 & 0\\ \hline & 1\end{array}$$

Les den: $c_1=0$ gir $k_1=f\left(t_n,y_n\right)$, og $b_1=1$ gir $y_{n+1}=y_n+hk_1$ ✔.

Heun (forbedret Euler). To steg:

$$\begin{array}{c|cc}0 & 0 & 0\\ 1 & 1 & 0\\ \hline & \tfrac12 & \tfrac12\end{array}$$

Les den rad for rad:

- Rad 1: $c_1=0$, ingen $a$-er $\Rightarrow k_1=f\left(t_n,y_n\right)$.
- Rad 2: $c_2=1$ og $a_{21}=1$ $\Rightarrow k_2=f\left(t_n+h,\ y_n+hk_1\right)$.
- Vektrad: $y_{n+1}=y_n+h\left(\tfrac12 k_1+\tfrac12 k_2\right)=y_n+\tfrac h2\left(k_1+k_2\right)$ ✔

Klassisk RK4. Fire steg:

$$\begin{array}{c|cccc} 0 & 0 & 0 & 0 & 0\\ \tfrac12 & \tfrac12 & 0 & 0 & 0\\ \tfrac12 & 0 & \tfrac12 & 0 & 0\\ 1 & 0 & 0 & 1 & 0\\ \hline & \tfrac16 & \tfrac13 & \tfrac13 & \tfrac16 \end{array}$$

Les den:

- Rad 2: $k_2=f\left(t_n+\tfrac h2,\ y_n+\tfrac h2 k_1\right)$ ✔
- Rad 3: $k_3=f\left(t_n+\tfrac h2,\ y_n+\tfrac h2 k_2\right)$ ✔ — merk at det er $k_2$, ikke $k_1$, fordi ettallet står i kolonne 2.
- Rad 4: $k_4=f\left(t_n+h,\ y_n+hk_3\right)$ ✔
- Vektrad: $y_{n+1}=y_n+h\left(\tfrac16k_1+\tfrac13k_2+\tfrac13k_3+\tfrac16k_4\right)=y_n+\tfrac h6\left(k_1+2k_2+2k_3+k_4\right)$ ✔

Tre kontroller på alle tre tabellene:

1. Vektsummen er 1. Euler: $1$. Heun: $\tfrac12+\tfrac12=1$. RK4: $\tfrac16+\tfrac13+\tfrac13+\tfrac16=1$ ✔
2. Radsummene stemmer med $c_i$. RK4 rad 3: $0+\tfrac12=\tfrac12=c_3$ ✔
3. $A$ er strengt nedre triangulær, så alle tre er eksplisitte ✔

Poenget med eksempelet. Tabellen inneholder nøyaktig den samme informasjonen som formlene — hverken mer eller mindre. Har du en tabell, kan du regne et skritt; har du et skritt, kan du skrive tabellen. Det er den ferdigheten oppgavene tester.

Tabellen: $\mathbf c=\left(0,\tfrac12,\tfrac12,1\right)$, $\mathbf b=\left(\tfrac16,\tfrac13,\tfrac13,\tfrac16\right)$, og de eneste $a_{ij}$ ulik null er

$$a_{21}=\tfrac12,\qquad a_{32}=\tfrac12,\qquad a_{43}=1.$$

Nivå 1.

$$\sum b_i=\frac16+\frac13+\frac13+\frac16=\frac{1+2+2+1}{6}=1.\qquad ✔$$

Nivå 2.

$$\sum b_ic_i=\frac16\cdot 0+\frac13\cdot\frac12+\frac13\cdot\frac12+\frac16\cdot 1=\frac16+\frac16=\frac13+\frac16.$$

Regn nøye: $\displaystyle \frac13\cdot\frac12=\frac16$ (to ganger) og $\displaystyle \frac16\cdot 1=\frac16$, altså

$$\sum b_ic_i=\frac16+\frac16+\frac16=\frac36=\frac12.\qquad ✔$$

Nivå 3, første betingelse.

$$\sum b_ic_i^{2}=\frac13\cdot\frac14+\frac13\cdot\frac14+\frac16\cdot 1=\frac{1}{12}+\frac{1}{12}+\frac16=\frac{1+1+2}{12}=\frac{4}{12}=\frac13.\qquad ✔$$

Nivå 3, andre betingelse. Gå rad for rad. Bare radene 2, 3 og 4 har $a$-er ulik null:

- $i=2$: $\displaystyle b_2a_{21}c_1=\frac13\cdot\frac12\cdot 0=0$
- $i=3$: $\displaystyle b_3a_{32}c_2=\frac13\cdot\frac12\cdot\frac12=\frac{1}{12}$
- $i=4$: $\displaystyle b_4a_{43}c_3=\frac16\cdot 1\cdot\frac12=\frac{1}{12}$

$$\sum b_ia_{ij}c_j=0+\frac1{12}+\frac1{12}=\frac16.\qquad ✔$$

Metoden har minst orden 3. Videre til nivå 4.

Nivå 4, betingelse 1.

$$\sum b_ic_i^{3}=\frac13\cdot\frac18+\frac13\cdot\frac18+\frac16\cdot 1=\frac{1}{24}+\frac{1}{24}+\frac16=\frac{1+1+4}{24}=\frac{6}{24}=\frac14.\qquad ✔$$

Nivå 4, betingelse 2.

- $i=3$: $\displaystyle b_3c_3a_{32}c_2=\frac13\cdot\frac12\cdot\frac12\cdot\frac12=\frac{1}{24}$
- $i=4$: $\displaystyle b_4c_4a_{43}c_3=\frac16\cdot 1\cdot 1\cdot\frac12=\frac{1}{12}$

$$\sum=\frac{1}{24}+\frac{2}{24}=\frac{3}{24}=\frac18.\qquad ✔$$

Nivå 4, betingelse 3.

- $i=3$: $\displaystyle b_3a_{32}c_2^{2}=\frac13\cdot\frac12\cdot\frac14=\frac{1}{24}$
- $i=4$: $\displaystyle b_4a_{43}c_3^{2}=\frac16\cdot 1\cdot\frac14=\frac{1}{24}$

$$\sum=\frac{2}{24}=\frac{1}{12}.\qquad ✔$$

Nivå 4, betingelse 4 (trippel sum). Det eneste leddet med tre ikke-null faktorer er $i=4$, $j=3$, $k=2$:

$$b_4a_{43}a_{32}c_2=\frac16\cdot 1\cdot\frac12\cdot\frac12=\frac{1}{24}.\qquad ✔$$

Alle åtte betingelsene holder.

$$\boxed{\text{Klassisk RK4 har orden 4.}}$$

Merk hvor systematisk regningen er. Hver betingelse er en liten sum over de radene der $b_i\ne 0$ og de kolonnene der $a_{ij}\ne 0$. For en eksplisitt metode er det få ledd, og de fleste er null.

Tidsbruk på eksamen: en oppgave ber sjelden om alle åtte. Ber den om «bestem ordenen», stopper du ved den første som feiler — og for de fleste oppgavemetodene skjer det på nivå 3.

a) Avlesningen.

Nodene fra tidsargumentene: f(t, y) gir $c_1=0$; f(t + h/2, ...) gir $c_2=\tfrac12$; f(t + h, ...) gir $c_3=1$.

Koeffisientene fra $y$-argumentene:

- k2: y + h*0.5*k1 gir $a_{21}=\tfrac12$.
- k3: y + h*(0.0*k1 + 1.0*k2) gir $a_{31}=0$ og $a_{32}=1$.

Vektene fra returlinja: h*(k1 + 4*k2 + k3)/6 gir $b_1=\tfrac16$, $b_2=\tfrac46=\tfrac23$, $b_3=\tfrac16$.

$$\begin{array}{c|ccc}0 & 0 & 0 & 0\\ \tfrac12 & \tfrac12 & 0 & 0\\ 1 & 0 & 1 & 0\\ \hline & \tfrac16 & \tfrac23 & \tfrac16\end{array}$$

Kontroller: vektsum $\tfrac16+\tfrac23+\tfrac16=1$ ✔. Radsummer: $\tfrac12=c_2$ ✔ og $0+1=1=c_3$ ✔. Strengt nedre triangulær ✔.

Alt ser riktig ut så langt. Det er nettopp det som gjør oppgaven vanskelig.

b) Ordenen.

Nivå 1: $\sum b_i=1$ ✔

Nivå 2:

$$\sum b_ic_i=\frac16\cdot 0+\frac23\cdot\frac12+\frac16\cdot 1=\frac13+\frac16=\frac12.\qquad ✔$$

Nivå 3, første betingelse:

$$\sum b_ic_i^{2}=\frac23\cdot\frac14+\frac16\cdot 1=\frac16+\frac16=\frac13.\qquad ✔$$

Her ville en forhastet besvarelse stoppet og svart «orden 3». Men vi er ikke ferdige med nivå 3.

Nivå 3, andre betingelse:

- $i=2$: $\displaystyle b_2a_{21}c_1=\frac23\cdot\frac12\cdot 0=0$
- $i=3$: $\displaystyle b_3a_{32}c_2=\frac16\cdot 1\cdot\frac12=\frac{1}{12}$

$$\sum b_ia_{ij}c_j=0+\frac1{12}=\frac1{12}.$$

Kravet er $\tfrac16=\tfrac2{12}$, og

$$\frac1{12}\ne\frac2{12}.\qquad ✘$$

$$\boxed{\text{Metoden har orden 2.}}$$

c) Hva er endret. Den klassiske Kuttas tredjeordens metode har samme $\mathbf c$ og samme $\mathbf b$, men tredje rad i $A$ er

$$a_{31}=-1,\qquad a_{32}=2$$

i stedet for $0$ og $1$. Legg merke til at begge tabellene har radsum $1$ i rad 3 ($-1+2=1$ og $0+1=1$) — så radsum-kontrollen avslører ingenting.

Med de riktige tallene blir den andre nivå-3-betingelsen

$$b_3\left(a_{31}c_1+a_{32}c_2\right)=\frac16\left((-1)\cdot 0+2\cdot\frac12\right)=\frac16\cdot 1=\frac16,\qquad ✔$$

altså riktig, og metoden har orden 3.

Konsekvensen i tall. Kjører vi begge metodene på $y'=t-2y$, $y(0)=1$, fram til $t=1$ (eksakt $y(1)\approx 0{,}4191691$), får vi

$n$	Feil, koden over	forhold	Feil, Kuttas RK3	forhold
10	$1{,}25\cdot 10^{-3}$	—	$1{,}32\cdot 10^{-4}$	—
20	$2{,}97\cdot 10^{-4}$	$4{,}21$	$1{,}53\cdot 10^{-5}$	$8{,}67$
40	$7{,}23\cdot 10^{-5}$	$4{,}10$	$1{,}83\cdot 10^{-6}$	$8{,}33$
80	$1{,}78\cdot 10^{-5}$	$4{,}05$	$2{,}25\cdot 10^{-7}$	$8{,}16$

Forholdet 4 mot 8 bekrefter orden 2 mot orden 3, helt uavhengig av tabellregningen.
Lærdommen. Én oppføring i $A$ er endret, radsummen stemmer fortsatt, den første nivå-3-betingelsen holder fortsatt — og likevel har metoden mistet en hel orden. Det er derfor du må sjekke begge betingelsene på nivå 3, og det er nøyaktig denne fella sjangeren er bygd rundt.

a) Avlesningen.

- k1 = f(t, y): $c_1=0$.
- k2 = f(t + h/2, y + h*k1/2): $c_2=\tfrac12$, $a_{21}=\tfrac12$.
- k3 = f(t + h, y + h*(2.0*k2 - k1)): $c_3=1$, og parentesen gir $a_{31}=-1$, $a_{32}=2$.
- Returlinja h*(k1 + 4*k2 + k3)/6: $b_1=\tfrac16$, $b_2=\tfrac46=\tfrac23$, $b_3=\tfrac16$.

$$\begin{array}{c|ccc}0 & 0 & 0 & 0\\ \tfrac12 & \tfrac12 & 0 & 0\\ 1 & -1 & 2 & 0\\ \hline & \tfrac16 & \tfrac23 & \tfrac16\end{array}$$

Kontroller.

- Vektsum: $\tfrac16+\tfrac23+\tfrac16=\tfrac{1+4+1}{6}=1$ ✔
- Radsummer: rad 2: $\tfrac12=c_2$ ✔. Rad 3: $-1+2=1=c_3$ ✔
- Eksplisitt: $A$ er strengt nedre triangulær ✔

Merk det negative tallet $a_{31}=-1$. Negative koeffisienter er helt vanlige i Runge–Kutta-tabeller og er ikke et tegn på feil.

b) Ordenen.

Nivå 1: $\sum b_i=1$ ✔

Nivå 2:

$$\sum b_ic_i=\frac16\cdot 0+\frac23\cdot\frac12+\frac16\cdot 1=\frac13+\frac16=\frac12.\qquad ✔$$

Nivå 3, første betingelse:

$$\sum b_ic_i^{2}=\frac23\cdot\frac14+\frac16\cdot 1=\frac16+\frac16=\frac13.\qquad ✔$$

Nivå 3, andre betingelse:

- $i=2$: $\displaystyle b_2a_{21}c_1=\frac23\cdot\frac12\cdot 0=0$
- $i=3$: $\displaystyle b_3\left(a_{31}c_1+a_{32}c_2\right)=\frac16\left((-1)\cdot 0+2\cdot\frac12\right)=\frac16\cdot 1=\frac16$

$$\sum b_ia_{ij}c_j=0+\frac16=\frac16.\qquad ✔$$

Begge nivå-3-betingelsene holder — metoden har minst orden 3. Videre til nivå 4.

Nivå 4, første betingelse:

$$\sum b_ic_i^{3}=\frac23\cdot\frac18+\frac16\cdot 1=\frac1{12}+\frac16=\frac{1+2}{12}=\frac14.\qquad ✔$$

Overraskende — den gikk gjennom. Vi må videre.

Nivå 4, andre betingelse:

- $i=2$: $\displaystyle b_2c_2a_{21}c_1=\frac23\cdot\frac12\cdot\frac12\cdot 0=0$
- $i=3$: $\displaystyle b_3c_3\left(a_{31}c_1+a_{32}c_2\right)=\frac16\cdot 1\cdot 1=\frac16$

$$\sum b_ic_ia_{ij}c_j=\frac16.$$

Kravet er $\tfrac18$, og

$$\frac16\approx 0{,}1667\ne 0{,}125=\frac18.\qquad ✘$$

$$\boxed{\text{Metoden har orden 3.}}$$

Dette er Kuttas tredjeordens metode, den korrekte utgaven av metoden i eksempel 3.

Merk at nivå 4 krevde to forsøk. Den første betingelsen på nivå 4 gikk gjennom — helt tilfeldig — og hadde vi stoppet der, ville vi påstått orden 4. Regelen om å sjekke alle betingelsene på hvert nivå gjelder også på nivå 4.

c) Numerisk eksperiment.

Oppsett: velg et problem med kjent løsning, for eksempel $y'=t-2y$ med $y(0)=1$, som har

$$y(t)=\tfrac54 e^{-2t}+\tfrac t2-\tfrac14,\qquad y(1)\approx 0{,}4191691.$$

Kjør metoden fra $t=0$ til $t=1$ med $n=10,20,40,80$ skritt, altså med $h$ halvert hver gang, og regn feilen $\left|y_n-y(1)\right|$.

Forventet resultat: forholdet mellom to påfølgende feil skal nærme seg

$$2^{p}=2^{3}=8.$$

Faktisk resultat når eksperimentet kjøres:

$n$	$y_n$	Feil	Forhold
10	$0{,}4190367$	$1{,}32\cdot 10^{-4}$	—
20	$0{,}4191538$	$1{,}53\cdot 10^{-5}$	$8{,}67$
40	$0{,}4191673$	$1{,}83\cdot 10^{-6}$	$8{,}33$
80	$0{,}4191689$	$2{,}25\cdot 10^{-7}$	$8{,}16$

Forholdet nærmer seg 8 nedenfra ✔ — eksperimentet bekrefter orden 3, uavhengig av tabellregningen.
Hvorfor eksperimentet er verdt å beskrive. Ordensbetingelsene er lette å regne feil i, særlig de doble summene. Et eksperiment som gir forhold 8 når du har regnet deg fram til orden 3, er en sterk bekreftelse. Gir det 4 når du har regnet 3, vet du at du har en feil å lete etter.
Tidsbruk på eksamen: a) 5 min, b) 12 min, c) 5 min — omtrent 22 minutter for en oppgave på 10 poeng.