8.3 Crank–Nicolson og implisitte skjemaer
Det implisitte Crank–Nicolson-skjemaet (trapes i tid), det tridiagonale systemet det gir, og hvorfor det er ubetinget stabilt.
Crank–Nicolson eller trapesregelen i tid har eget belegg i 4 av 13 sett (31 %). Det er nok til at metoden må sitte, og lite nok til at kap. 8.2 har høyere prioritet om du har dårlig tid.
Det som spørres om, er tre ting, og de kommer i denne rekkefølgen:
1. «Sett opp systemet.» Skriv skjemaet for hvert indre punkt og samle det som , med matrisen skrevet ut. Dette er hoveddelen av poengene.
2. «Løs for ett tidssteg.» Et lite tridiagonalt system, som regel med to eller tre ukjente, løst for hånd.
3. «Forklar hvorfor skjemaet er stabilt for enhver .» Kortsvaret som skiller toppsjiktet.
Formelark-merking.
- Crank–Nicolson-formelen står på det utdelte formelarket — tren oppslaget. Den ligger på numerikk-siden, i formen . Ferdigheten er å sette inn riktig og lese av matrisen, ikke å huske formelen.
- Oppsettet av det tridiagonale systemet, randbidragene i høyresiden og stabilitetsargumentet må kunnes. Arket sier ingenting om noen av delene.
Tidsbruk: 55 minutter lesetid, fire løkker à omtrent et kvarter. Naturlig pausepunkt etter løkke 2.
Fra tidligere matematikkemner forutsettes at du kan løse et lite lineært likningssystem med Gauss-eliminasjon eller innsetting, og at du vet hva en matrise er. Ingen kunnskap om numerisk lineær algebra kreves — systemene i dette kapitlet har to eller tre ukjente og løses for hånd.
Kapitlet er nyttig, men ikke nødvendig, før kap. 8.4.
Regningen som gjorde stabilitetskravet uakseptabelt
I kap. 8.2 endte oppgave 4 med et tall som fortjener å bli stående: for å regne fram til på et gitter med tjue romlige punkter, med diffusivitet , trengs 7200 tidssteg. Ikke fordi vi trenger så fin oppløsning i tid — men fordi skjemaet ellers sprenger.
Det er en dårlig handel. Vi betaler tusenvis av tidssteg for en nøyaktighet vi ikke har bruk for, bare for å kjøpe stabilitet.
Ideen som løser det, er nesten frekk: hvis problemet er at høyresiden regnes ut på det gamle tidsnivået, hvorfor ikke regne den ut på det nye? Da får du et skjema der den ukjente står på begge sider — og det er ikke lenger en formel du kan sette inn i, men et likningssystem du må løse.
Prisen er reell, og gevinsten er større. Ett likningssystem per tidssteg, mot fullstendig frihet i valget av . For lange kjøringer er det ikke i nærheten av å være et vanskelig valg.
Crank–Nicolson går ett skritt lenger og tar gjennomsnittet av det gamle og det nye nivået. Det er trapesregelen brukt på tidsaksen, og det gir andre orden i tid — mot det eksplisitte skjemaets første. Du får altså både bedre nøyaktighet og ubetinget stabilitet, for prisen av å løse et lite system.
Kapitlet gjør fire ting: innfører den implisitte ideen i sin enkleste form, setter opp Crank–Nicolson og løser et system for hånd, viser hvorfor skjemaet er stabilt uansett , og drøfter ærlig når det faktisk lønner seg.
Løkke 1 — Den implisitte ideen i sin enkleste form (~13 min)
Før Crank–Nicolson tar vi det enkleste implisitte skjemaet. Det er lettere å forstå, det viser hele mekanismen, og det dukker opp på formelarket under navnet bakover-Euler.
Et skjema der den ukjente verdien på det nye tidsnivået opptrer flere steder i samme likning, slik at den ikke kan isoleres.
Konsekvensen er at alle de indre verdiene på nivå må finnes samtidig, ved å løse et lineært likningssystem. Kontrasten er det eksplisitte skjemaet i kap. 8.2, der hver ny verdi leses rett ut.
Hvorfor gjøre det vanskelig? Fordi implisitte skjemaer ikke har noen stabilitetsgrense. Hele kapitlet er en utveksling: mer arbeid per steg, ingen grense på hvor stort steget kan være.
Ryddet opp, med :
Legg merke til fortegnene: på naboene, på diagonalen. Det er motsatt av det eksplisitte skjemaet, og det er ikke tilfeldig — det er nettopp fortegnsmønsteret som gjør matrisen godt oppført.
Skjemaet er ubetinget stabilt, men bare i tid. Det står på det utdelte formelarket sammen med de andre Euler-variantene — tren oppslaget.
Med identiteten :
Nevneren er alltid minst 1, uansett hvor stor er. Derfor er for enhver og enhver bølgelengde: ingen mode kan vokse.
Intuisjon: i det eksplisitte skjemaet ganges feilen med noe som kan være større enn 1 i tallverdi. I det implisitte deles den på noe som alltid er større enn 1. Divisjon kan aldri forstørre.
Sammenlign med kap. 8.2: der var , som stuper under så snart . Her står den samme størrelsen i nevneren i stedet for i telleren, og hele problemet forsvinner.
(Innstegsoppgave — ren avlesning.) Skriv opp bakover-Euler-skjemaet for med og .
a) Hva er ?
b) Skriv likningen for et indre punkt med tallene satt inn.
c) Hvorfor kan du ikke løse den for alene?
Løkke 2 — Crank–Nicolson og det tridiagonale systemet (~16 min)
Bakover-Euler er stabilt, men bare førsteordens i tid — akkurat som det eksplisitte. Crank–Nicolson fikser det med et grep du kjenner fra kap. 6.2: trapesregelen.
der fra kap. 8.1.
Dette er nøyaktig trapesregelen brukt på integralet av høyresiden over ett tidssteg: gjennomsnittet av endepunktverdiene. Og det er derfra ordenen kommer — trapesregelen er andreordens, så tidsdelen blir i stedet for .
Intuisjon: det eksplisitte skjemaet gjetter framover fra der du står, det implisitte gjetter bakover fra der du havner. Sannheten ligger i midten, og gjennomsnittet treffer den bedre enn begge.
med som før.
Formen er lett å huske fordi den er symmetrisk: venstre og høyre side er speilbilder, bortsett fra at blir og blir .
Formelen står på det utdelte formelarket — tren oppslaget. Å sette den opp som et matrisesystem, med randbidragene på riktig side, må kunnes.
Deler du på 2, får du den andre vanlige formen: . Begge er riktige; bruk den arket har.
Formen kommer direkte av stensilen: hver likning knytter bare et punkt til sine to nærmeste naboer.
Hvorfor det er en god nyhet: et tridiagonalt system med ukjente løses med omtrent regneoperasjoner, mot for en full matrise. Kostnaden per tidssteg er altså proporsjonal med antall punkter, akkurat som for det eksplisitte skjemaet — bare med en større konstant.
Matrisen her er i tillegg diagonaldominant: for alle . Det garanterer at systemet har entydig løsning og at eliminasjonen aldri deler på noe lite.
matrisen er den tridiagonale over, og høyresiden er hele det gamle tidsnivået:
Ett system per tidssteg. Matrisen er den samme hele veien — bare høyresiden endres. Det er verdt å si i en drøftingsoppgave: eliminasjonen kan gjøres én gang og gjenbrukes.
Merk at randverdien opptrer på begge tidsnivåer — det gamle bidraget står allerede i formelen, det nye må flyttes over.
Ved homogene randbetingelser () faller begge bort, og høyresiden er den samme formelen overalt. Det er derfor de fleste eksamensoppgavene har kalde ender: da slipper man dette. Å glemme randbidraget ved ikke-homogen rand er en av de dokumenterte feilene i sjangeren.
med Crank–Nicolson, og . Sett opp , løs, og ta ett skritt til.
Merk hva betyr: det er dobbelt så stort som grensen for det eksplisitte skjemaet. Med Crank–Nicolson er det helt lovlig, og vi skal se i løkke 3 hva som skjer om man prøver det samme eksplisitt.
Steg 2 — sett inn i formelen fra arket. Med er og , så hele det gamle midtleddet faller bort:
Det er en tilfeldighet ved akkurat , og den gjør regningen kort.
Steg 3 — startraden. Gitterpunktene er , så
Steg 4 — høyresiden. For er :
Randbidraget på nytt tidsnivå er og , siden randen er kald. Ingenting å legge til.
Steg 5 — systemet.
Steg 6 — løs. Både data og system er symmetriske om midten, så . Det reduserer systemet til to likninger:
Fra den første: . Sett inn i den andre:
Rad 1: .
Kontroll: sett inn i den midterste likningen: . ✓
Steg 7 — ett skritt til. Ny høyreside fra rad 1:
Samme matrise, samme symmetri:
Steg 8 — kontroll mot fasiten. Den analytiske løsningen fra kap. 5.2 er med for denne hattefunksjonen. Regnet ut ved :
Crank–Nicolson ga — avvik , altså 2 %, på et gitter med bare tre indre punkter og med et tidssteg dobbelt så stort som det eksplisitte skjemaet i det hele tatt har lov til å bruke.
Merk et ærlig forbehold: i punktet er avviket større, mot eksakt . Startdataene har et knekkpunkt i , og et knekkpunkt bryter forutsetningen om at er deriverbar nok ganger til at -argumentet holder. Grovt gitter pluss knekk gir større feil enn ordenen alene lover.
Skriv opp Crank–Nicolson-formelen med tallene satt inn for , og oppgi matrisen for et gitter med tre indre punkter og kalde ender.
a) Regn ut .
b) Sett opp med tall.
c) Løs systemet og sammenlign med den eksakte løsningen .
Løkke 3 — Ubetinget stabilitet, og hva det er verdt (~13 min)
— naturlig pausepunkt —
Nå til kortsvaret som skiller toppsjiktet: hvorfor er Crank–Nicolson stabilt for enhver ? Argumentet er tre linjer og bruker samme grep som i kap. 8.2.
Del alt på 2 og bruk . Sett :
Nå er saken avgjort. For enhver er
fordi telleren alltid er mindre enn nevneren i tallverdi. Ingen mode kan vokse, uansett hvor stor er. Skjemaet er ubetinget stabilt.
Intuisjon: måler hvor «hardt» diffusjonen virker på den aktuelle bølgen. Formelen er en gammel kjenning — den avbilder hele den positive halvaksen inn i intervallet , uansett hvor stor blir. Det er hele hemmeligheten.
Sammenlign de tre skjemaene for samme :
| Skjema | Stabilitet | Orden i tid | |
|---|---|---|---|
| Eksplisitt | krever | ||
| Bakover-Euler | ubetinget | ||
| Crank–Nicolson | ubetinget |
Crank–Nicolson er den eneste som har begge deler.
Et skjema er ubetinget stabilt dersom for alle bølgelengder og alle valg av og — altså uten noen betingelse som knytter de to sammen.
Både bakover-Euler og Crank–Nicolson er ubetinget stabile. Det eksplisitte skjemaet er betinget stabilt, med betingelsen .
Hva det betyr i praksis: du velger tidssteget etter hvor nøyaktig du vil ha svaret, ikke etter hva skjemaet tåler. Det er nettopp den friheten det eksplisitte skjemaet ikke gir.
Stabilitetsargumentet må kunnes — formelarket har ingen stabilitetsanalyse.
altså andre orden i begge retninger.
Sammenlign med det eksplisitte skjemaet, som er . Den ekstra ordenen i tid kommer av at trapesregelen er symmetrisk om midtpunktet — samme symmetriargument som i kap. 8.1: symmetriske formler får en orden gratis.
Konsekvensen er praktisk: for å halvere feilen trenger du bare å redusere med en faktor , ikke med en faktor 2.
Kjør både det eksplisitte skjemaet og Crank–Nicolson på hattefunksjonen fra eksempel 1, med , , altså . Sammenlign fire tidssteg.
Regn radene (alle randverdier er 0):
| maks | ||||
|---|---|---|---|---|
| 0 | 0,25 | 0,50 | 0,25 | 0,50 |
| 1 | 0,25 | 0 | 0,25 | 0,25 |
| 2 | 0,50 | 0,50 | ||
| 3 | 0,75 | 0,75 | 1,00 | |
| 4 | 2,50 | 2,50 |
Regn med: . . … nei, fra rad 2: . Og videre.
Se hva som skjer. Allerede på rad 2 er det negative temperaturer i en oppgave der all starttemperatur var positiv og randen holdes på null. På rad 4 veksler verdiene mellom og , og de vokser. Det er sagtannmoden fra kap. 8.2, og den vokser med faktoren per steg.
Crank–Nicolson med samme , fra eksempel 1:
| eksakt | |||
|---|---|---|---|
| 0 | 0,250000 | 0,500000 | 0,500000 |
| 1 | 0,178571 | 0,214286 | 0,218883 |
| 2 | 0,086735 | 0,132653 | 0,118025 |
| 3 | 0,050292 | 0,068513 | — |
Alt synker, alt er positivt, og verdiene ligger nær fasiten. Samme steglengder, samme regnearbeid per punkt — helt ulikt resultat.
Det er dette som menes med at ubetinget stabilitet er verdt prisen av å løse et system. Prisen er et -system per tidssteg. Gevinsten er at svaret i det hele tatt betyr noe.
En ærlig nyansering du bør ha med i en drøftingsoppgave: Crank–Nicolson er stabilt for enhver , men det er ikke det samme som at store er lurt. Ser du på forsterkningsfaktoren for sagtannmoden (), er
som går mot når blir stor. Ved er : den moden dør knapt ut, og den skifter fortegn hvert steg. Løsningen sprenger ikke, men den kan få små, langlevde svingninger som ikke finnes i virkeligheten — særlig rett etter en brå start. Bakover-Euler har ikke det problemet ( alltid), men er til gjengjeld bare førsteordens. Ingen av metodene er best på alt.
b) Vis at for alle .
c) Hva går mot når for sagtannmoden, og hva betyr det praktisk?
Sammenlign de tre skjemaene for varmelikningen på et bestemt problem: , , og du skal regne fram til med en nøyaktighet i tid som svarer til .
a) Hvor mange tidssteg trenger Crank–Nicolson?
b) Hvor mange trenger det eksplisitte skjemaet, når stabiliteten er tatt hensyn til?
c) Drøft kort hvilket skjema du ville valgt.
Løkke 4 — Å løse systemet, og når det lønner seg (~13 min)
Det siste som gjenstår, er å se på hva «løs systemet» faktisk koster — og på et par ærlige forbehold.
Gauss-eliminasjon som utnytter at bare tre diagonaler er fylt. To gjennomløp:
1. Framover: eliminer under diagonalen, én rad om gangen. Hver rad har bare ett element å eliminere.
2. Bakover: finn fra siste likning, og sett inn oppover.
Kostnaden er omtrent operasjoner for ukjente — lineært, ikke kubisk. En full Gauss-eliminasjon ville krevd .
På eksamen løser du systemet for hånd, med to eller tre ukjente, og da er innsetting raskest. Algoritmen er verdt å kjenne til for drøftingsspørsmål om kostnad, men du blir ikke bedt om å utføre den. Den beslektede metoden LU-faktorisering står på formelarket som beredskap, uten å ha egen kapittelkjede i denne boka.
Regelen er enkel: sammenlign det tidssteget nøyaktigheten krever med det tidssteget stabiliteten tillater.
- Er de omtrent like store, bruk det eksplisitte skjemaet. Det er enklere og billigere per steg.
- Krever stabiliteten et mye mindre tidssteg enn nøyaktigheten, bruk Crank–Nicolson.
Det andre skjer alltid når gitteret forfines, fordi stabilitetsgrensen krymper som mens nøyaktighetskravet bare krymper som eller i én potens av gangen.
Tommelfingerregelen: fint gitter, lang kjøring eller stor diffusivitet implisitt.
Crank–Nicolson er stabilt for enhver , men forsterkningsfaktoren for de korteste bølgene er negativ når , altså når .
Negativ betyr at moden skifter fortegn for hvert tidssteg. Med stor er nær 1, så svingningen dør knapt ut.
Når merkes det? Særlig når startdataene har et sprang eller et knekkpunkt, for da er de korteste bølgene godt representert. Symptomet er små krusninger nær spranget som blir stående.
Botemidlene er å velge et mindre tidssteg, eller å ta de første par stegene med bakover-Euler (som har alltid) og deretter bytte. Det siste kalles Rannacher-oppstart og er utenfor pensum — men det er verdt å vite at fenomenet har et navn og en kur.
I avhenger bare av — og er konstant gjennom kjøringen. Bare høyresiden endres fra steg til steg.
Praktisk konsekvens: eliminasjonen gjøres én gang, og hvert tidssteg koster bare innsetting fram og tilbake. Det halverer omtrent kostnaden per steg.
Dette er et poeng verdt å nevne i en drøftingsoppgave om regnearbeid, og det er en av grunnene til at implisitte metoder er så mye brukt i praksis.
Crank–Nicolson er ikke bundet til varmelikningen. Samme grep — trapesregelen i tid, sentraldifferanse i rom — brukes på
- likninger med et kildeledd , der midles over de to tidsnivåene;
- varierende koeffisient , som gir andre tall på diagonalene;
- ikke-homogene randbetingelser, som gir randbidrag i .
Matrisen forblir tridiagonal i alle tilfellene, fordi stensilen er den samme. Det er derfor metoden er så mye brukt: oppskriften endrer seg ikke, bare tallene.
Gitteret er (to indre punkter) og .
a) Sett opp systemet for det første tidssteget, med randbidragene på riktig plass.
b) Løs det.
c) Hva blir løsningen når , og stemmer retningen på svaret i b) med det?
Vis at bakover-Euler-skjemaet oppfyller et maksimumsprinsipp for enhver : ingen indre verdi på det nye nivået kan være større enn den største verdien blant og randverdiene på nivå .
Å behandle Crank–Nicolson som om det var eksplisitt. Den nye verdien kan ikke isoleres — det er tre ukjente i hver likning. Skriver du «» med bare gamle verdier på høyre side, har du regnet noe helt annet.
Å glemme randbidragene i høyresiden. Ved ikke-homogene randbetingelser opptrer randverdien to ganger i første og siste likning: én gang fra det gamle nivået, som allerede står i formelen, og én gang fra det nye, som må flyttes over fra venstre side. Oppgave 6 viser hvor lett den siste glemmes.
Å bruke det eksplisitte -kravet på Crank–Nicolson. Skriver du «, altså ustabilt» om et implisitt skjema, har du misforstått hele poenget med kapitlet. Crank–Nicolson og bakover-Euler er ubetinget stabile. Si det, og si hvorfor.
Å bruke feil form av formelen. Arket har -formen. Deler du på 2 underveis uten å gjøre det på begge sider, blir alle tallene halve. Skriv opp formelen fra arket først, uendret, og sett så inn.
Å tro at ubetinget stabilt betyr ubetinget nøyaktig. Stort er lovlig, men gir stor avkuttingsfeil og kan gi svingninger som ikke finnes i virkeligheten. Velg etter nøyaktigheten du trenger.
Begrepsbank
Flashcard- og repetisjonsstoff — hopp trygt over ved førstegangslesing. Boksene under samler resten av kapitlets begreper som egne kort.
- : eksplisitt, betinget stabilt, .
- : Crank–Nicolson, ubetinget stabilt, .
- : bakover-Euler, ubetinget stabilt og monotont, .
Det generelle stabilitetskravet er for , og ingen betingelse for . Halvveis er altså nøyaktig der stabilitetsgrensen forsvinner — og det er ikke tilfeldig, det er der skjemaet blir symmetrisk om midtpunktet i tid.
En matrise er diagonaldominant når hvert diagonalelement er større i tallverdi enn summen av tallverdiene til de andre elementene i samme rad.
For Crank–Nicolson-matrisen: , som holder for alle . For bakover-Euler: , samme sak.
Hvorfor det er godt nytt: en diagonaldominant tridiagonal matrise er alltid inverterbar, systemet har entydig løsning, og Gauss-eliminasjon kan kjøres uten radbytte og uten å dele på noe nær null. Det er derfor implisitte varmeskjemaer er så robuste i praksis.
der venstre side er en sentral differanse om med steglengde hver vei — og høyre side er gjennomsnittet av romleddet på de to nivåene, som tilnærmer verdien i midten.
Det er hele forklaringen på andre orden i tid. Symmetri om midtpunktet gir en orden gratis, nøyaktig som for sentraldifferansen i kap. 8.1.
Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.
Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.