Skip to main content

Uke 2 – Newtonfraktaler

Newtonfraktaler: Hvilken løsning finner iterasjonen?

Dette prosjektet er laget for omtrent 4–6 timer selvstendig arbeid. Copilot og andre kodeassistenter er tillatt.

Når en likning har flere løsninger, er det ikke nok å spørre om en metode konvergerer. Vi må også spørre hvilken løsning den finner, hvor raskt den kommer dit, og hvor mye svaret avhenger av startverdien. Newtons metode gjør disse spørsmålene synlige på en særlig tydelig måte.

Metoden løser likningen

\[ f(z)=0 \]

ved å gjenta

\[ z_{n+1}=z_n-\frac{f(z_n)}{f'(z_n)}. \]

Dette er en fikspunktiterasjon med oppdateringsregel

\[ g(z)=z-\frac{f(z)}{f'(z)}. \]

Her arbeider vi med komplekse tall \(z=x+iy\). Ved å fargelegge hver startverdi etter nullpunktet den finner, får vi et kart over metodens oppførsel. Noen områder gir raske og forutsigbare iterasjoner. Langs grensene kan to nesten like startverdier få helt forskjellige forløp. Mengden av startverdier som konvergerer mot et bestemt nullpunkt, kalles nullpunktets tiltrekningsområde.

Problemstilling: Hva kjennetegner gode og dårlige startverdier for Newtons metode, og hvordan kan vi undersøke dette numerisk?

TipsHvordan jobbe med prosjektet

Koden for funksjonstildeling, Newton-iterasjon, rutenett, klassifisering og plotting er gitt. Arbeidet ditt er å planlegge numeriske eksperimenter, velge parametere, kontrollere resultatene og forklare det du observerer.

Dette er også en øvelse i å sette seg inn i eksisterende kode for en numerisk metode. Du skal ikke bygge alt fra bunnen av. Les kommentarene, kjør koden, finn parameterne som styrer forsøket, og gjør små endringer du kan kontrollere. Slik arbeider man ofte med vitenskapelig kode: forstå nok til å stille et spørsmål, endre én ting, og undersøke hva som faktisk skjedde.

Endre én størrelse om gangen. Noter alltid startverdi eller plottevindu, toleranse og maxiter sammen med resultatet. Målet er ikke bare å lage et fraktalbilde, men å bruke bildet til å velge og begrunne numeriske forsøk.

1. Du får tildelt en funksjon

Skriv fornavnet ditt i cellen under. Navnet gjøres først om til en standardform (små bokstaver, uten aksenter) og hashes deretter med SHA-256. Samme normaliserte fornavn gir alltid samme funksjon i dette prosjektet. Studenter med samme fornavn kan derfor få samme funksjon.

Tildelingen skjer lokalt i nettleseren. Navnet sendes ikke noe sted.

Alle funksjonene i puljen har grad 3, 4 eller 5 og bare enkle nullpunkter. Det betyr at hvert nullpunkt \(r\) oppfyller både \(f(r)=0\) og \(f'(r)\ne0\); ingen nullpunkter er gjentatt. Skriv ned funksjons-ID, funksjon, nullpunkter og standardvindu. Bruk den tildelte funksjonen i resten av prosjektet.

2. Newtons metode for én startverdi

Før vi lager et kart med tusenvis av startverdier, følger vi noen få iterasjoner trinn for trinn. Da kan vi se hva «rask» og «langsom» konvergens betyr i praksis.

Programmet trenger en regel for å avgjøre når svaret er godt nok. Siden vi prøver å løse \(f(z)=0\), måler vi hvor nær null funksjonsverdien er. Størrelsen

\[ |f(z_n)| \]

kalles residualen. Her stopper vi når

\[ |f(z_n)|<\texttt{tol}, \]

eller når maxiter er nådd. En liten residual betyr at den beregnede verdien nesten oppfyller likningen. Residualen er likevel ikke det samme som avstanden til det eksakte nullpunktet.

Vi registrerer også skrittlengden

\[ |z_{n+1}-z_n|=\left|\frac{f(z_n)}{f'(z_n)}\right|. \]

Skrittlengden forteller hvor mye iteratet flytter seg i ett steg. Den er nyttig når vi skal forstå store hopp, men i dette prosjektet er det residualen som avgjør konvergens. Uttrykket \(|z-f(z)|\) er ikke residualen til likningen \(f(z)=0\).

Kjør først koden med de foreslåtte startverdiene. Legg deretter til minst to egne startverdier.

Velg én startverdi som konvergerer raskt, og én som konvergerer langsomt eller ikke konvergerer. Vis hele historikken og plottet for begge.

Svar kort:

  1. Konvergerer alle startverdiene mot samme nullpunkt?
  2. Avtar residualen i hvert eneste steg?
  3. Avtar residual og skrittlengde i samme takt?
  4. Hvorfor trenger programmet både en residualtoleranse og maxiter?
  5. Hva skjer dersom et iterat kommer nær et punkt der \(f'(z)=0\)?

3. Tiltrekningsområder

Forsøkene med enkeltpunkter viser at startverdien betyr noe, men de sier lite om hvor vanlig rask eller langsom konvergens er. Derfor gjentar vi samme forsøk på et helt rutenett i det komplekse planet. Resultatet blir både et kart og et datasett vi kan stille spørsmål til.

Neste funksjon kjører Newtons metode samtidig for hele rutenettet. Hvert punkt får nummeret til nullpunktet det konvergerte mot, -1 hvis det ikke konvergerte innen maxiter, eller -2 hvis beregningen ble ugyldig.

Kjør standardeksperimentet. Dersom nettleseren arbeider langsomt, kan du først bruke nx=250, ny=250 og øke oppløsningen til slutt.

Figuren til venstre bruker én fast farge for hvert nullpunkt. Den svarer derfor bare på hvilket nullpunkt metoden fant. Figuren til høyre viser antall iterasjoner før residualkravet ble oppfylt. Les iterasjonstallet fra fargeskalaen. Verdier på 20 eller mer får samme endefarge, slik at noen få svært langsomme punkter ikke skjuler forskjellene i resten av kartet.

Mørkegrå punkter i venstre figur nådde maxiter, mens svarte punkter ga en ugyldig beregning. Begge typene punkter er utelatt (maskert) i iterasjonskartet.

For resten av prosjektet bruker vi følgende målbare beskrivelser:

  • En rask startverdi oppfyller residualkravet innen 6 iterasjoner.
  • En langsom startverdi konvergerer, men trenger mer enn 15 iterasjoner.
  • En mislykket startverdi når maxiter eller gir en ugyldig beregning.

Grensene 6 og 15 er arbeidsdefinisjoner for dette forsøket, ikke generelle grenser for Newtons metode. I diskusjonen bruker vi langsomme og mislykkede startverdier som konkrete eksempler på «dårlige» startverdier. Finn ett eksempel i hver kategori som finnes i ditt datasett. Oppgi \(z_0\), funnet nullpunkt, iterasjonstall og siste residual.

Koden under foreslår én startverdi fra hver kategori. Du kan bruke dem eller velge punkter som er lettere å se i figuren.

Svar kort:

  1. Hvilke områder gir konvergens mot hvert nullpunkt?
  2. Hvor ligger startverdiene som krever flest iterasjoner?
  3. Hvordan skiller punkter nær en grense seg fra punkter langt inne i et tiltrekningsområde?
  4. Ser figuren symmetrisk ut? Sammenlign med plasseringen av nullpunktene.
  5. Kan et endelig rutenett bevise at alle startverdier i vinduet konvergerer?

4. Finner metoden alltid nærmeste nullpunkt?

En naturlig gjetning er at Newtons metode finner nullpunktet som ligger nærmest startverdien. Nå kan vi teste denne gjetningen på hele rutenettet. Koden under sammenligner nærmeste nullpunkt til \(z_0\) med nullpunktet iterasjonen faktisk fant.

Velg ett av moteksemplene og vis iterasjonshistorikken med print_trace.

Svar kort:

  1. Hvor stor andel av de konvergerte startverdiene fant ikke nærmeste nullpunkt?
  2. Hva skjer med avstanden til de ulike nullpunktene gjennom ditt valgte forløp?
  3. Hvor i tiltrekningsplottet ligger de fleste moteksemplene?
  4. Hva kan du nå si om påstanden «Newton finner nærmeste nullpunkt»?

5. Hvorfor kan noen startverdier gi store hopp?

I Newton-formelen deler vi på \(f'(z_n)\). Når \(f'(z_n)\) er nær null, kan ett Newton-skritt derfor bli svært stort selv om funksjonsverdien ikke er stor. Punkter som oppfyller \(f'(z)=0\), kalles her kritiske punkter. De er ikke nødvendigvis dårlige startverdier i seg selv, men de er naturlige steder å undersøke nærmere.

Velg ett kritisk punkt \(c\). Kjør newton_trace for \(c\), \(c+10^{-3}\) og \(c+10^{-2}i\). Oppgi stoppårsak, største skrittlengde, funnet nullpunkt og antall iterasjoner. Du kan endre de små tilleggene (perturbasjonene) dersom alle tre forsøkene blir nesten like.

Svar kort:

  1. Hva skjer når startverdien er nøyaktig et kritisk punkt?
  2. Hvordan oppfører de to nærliggende startverdiene seg?
  3. Ligger områder med mange iterasjoner nær noen av de kritiske punktene?
  4. Er liten \(|f'(z_0)|\) alene nok til å forutsi hele iterasjonsforløpet?

6. Hvor følsom er metoden nær en grense?

Tiltrekningsplottet antyder at en svært liten endring i startverdien kan endre resultatet. For å gjøre dette til et kontrollert forsøk trenger vi et konkret grensepunkt og en bestemt perturbasjon, altså en liten, kontrollert endring av startverdien. Funksjonen under foreslår et punkt mellom to nabopiksler med forskjellig farge. Du kan bruke forslaget eller velge et tydeligere punkt i din egen figur.

Hvis alle tre startverdiene gir samme resultat, flytt grensepunktet eller gjør delta mindre. Vis iterasjonshistorikken for to nærliggende startverdier som finner forskjellige nullpunkter.

Svar kort:

  1. Hvor stor var avstanden mellom de to valgte startverdiene?
  2. Når begynte iterasjonsforløpene å bli tydelig forskjellige?
  3. Fant de ulike nullpunkter, eller var forskjellen bare antall iterasjoner?
  4. Er samme følsomhet synlig langt inne i et ensfarget område?

7. Kontroller stoppreglene

Fargene i kartet avhenger også av stoppreglene i programmet. Før du konkluderer, kontroller at hovedresultatet ikke bare skyldes ett tilfeldig valg av toleranse eller maxiter. Bruk et mindre rutenett for å spare tid.

Forklar med konkrete tall hvordan en strengere toleranse og en større maxiter påvirker klassifiseringen. Betyr «nådde maxiter» at den matematiske følgen divergerer? Betyr \(|f(z_n)|<10^{-12}\) nødvendigvis at \(|z_n-r|<10^{-12}\)?

8. Hovedproblemstilling: Følg en grense inn i fraktalen

Tiltrekningskartet har store, rolige fargeområder der resultatet er lett å forutsi. Mellom dem ligger smale og urolige grenser. På avstand kan en slik grense se ut som en vanlig kurve. Men når vi beregner et nytt kart over et mindre område, dukker det ofte opp nye bukter, øyer og striper som ikke var synlige før.

Dette er i grove trekk ideen bak en fraktal: nye detaljer fortsetter å bli synlige når vi undersøker figuren på mindre skalaer. Det betyr ikke at hvert zoom-bilde må være en nøyaktig minikopi av det forrige. Det viktige her er at grensen ikke raskt blir til en enkel, glatt linje.

For Newtons metode har zoomingen også en konkret numerisk betydning. Hvert punkt i bildet er en startverdi \(z_0\). Når vinduet blir ti ganger smalere, men fortsatt tegnes med \(400\times400\) piksler, undersøker vi startverdier som ligger ti ganger tettere. En fraktalzoom er derfor et forsøk som undersøker hvor følsomt Newton-resultatet er for stadig mindre endringer i startverdien.

Begrepene vi trenger

Et numerisk bilde er bygget opp av små fargede ruter. I dette prosjektet kaller vi én slik rute en piksel. Hver piksel representerer resultatet fra én startverdi i rutenettet: fargen for tiltrekningsområdet viser hvilket nullpunkt startverdien fant, mens iterasjonskartet viser hvor mange Newton-steg som ble brukt.

Oppløsningen nx × ny er antall startverdier vi beregner i vannrett og loddrett retning. I et vindu fra xmin til xmax er avstanden mellom to vannrette nabostartverdier

\[ \Delta x=\frac{\texttt{xmax}-\texttt{xmin}}{\texttt{nx}-1}. \]

Tilsvarende får vi \(\Delta y\) i loddrett retning. Når vinduet er kvadratisk og nx = ny, omtaler vi \(\Delta x\) som pikselbredden. Strengt tatt er dette avstanden mellom startverdiene som to nabopiksler representerer.

Plottevinduet er rektangelet av komplekse startverdier som beregnes. Å zoome betyr her å velge et mindre plottevindu og beregne et helt nytt rutenett med samme oppløsning. Det er altså ikke bare en grafisk forstørrelse av det gamle bildet.

Delproblem 1: Hvordan kjenner vi igjen en grense?

Før vi zoomer, trenger vi en enkel måleregel. Vi kaller en piksel en grensepiksel dersom minst én nabo over, under, til venstre eller til høyre konvergerer mot et annet nullpunkt. En indre piksel har samme farge for tiltrekningsområdet som alle disse naboene.

Dette er ikke en eksakt definisjon av den matematiske grensen. Det er en praktisk regel for et endelig bilde. Regelen lar oss koble figuren til spørsmålet vårt: En grensepiksel representerer en startverdi der en endring på omtrent én pikselbredde kan endre hvilket nullpunkt Newton finner.

Kjør oppsummeringen på hovedkartet. Bruk tallene som sammenligningsgrunnlag for zoom-ekspedisjonen – ikke som en konklusjon ennå.

Tenk før du zoomer: Tror du grensen etter hvert blir glatt dersom du bare zoomer langt nok inn? Tror du forskjellen i iterasjonstall mellom grense og indre områder blir større, mindre eller omtrent den samme? Skriv ned hypotesene dine før neste delproblem.

Delproblem 2: Hva betyr det å zoome numerisk?

En vanlig digital zoom ville bare gjort de eksisterende pikslene større. Det skal vi ikke gjøre. For hvert nivå lager newton_grid et nytt \(400\times400\)-rutenett med nye startverdier i et mindre vindu. Derfor kan det nye bildet inneholde strukturer som det gamle rutenettet ikke hadde nok punkter til å se.

Start ved boundary_point fra del 6. Hvis første bilde ikke viser en interessant grense, velger du et nytt sentrum fra hovedfiguren.

Delproblem 3: Fortsetter nye detaljer å dukke opp?

Gjør zoom_width omtrent ti ganger mindre for hvert nivå. Før neste kjøring velger du et nytt sentrum på en synlig grense i det siste bildet. Du kan bruke

zoom_center = suggest_boundary_point(zoom_data)
zoom_width = zoom_width / 10
zoom_data = run_zoom(zoom_center, zoom_width)

som utgangspunkt. Kontroller alltid figuren selv. Den automatiske funksjonen velger bare en fargeovergang i rutenettet; den vet ikke hvilken struktur du synes er interessant.

Lag minst tre nye zoomnivåer. Bruk samme oppløsning, tol og maxiter på alle nivåene. Da svarer én piksel til en stadig mindre endring i startverdien, mens stoppreglene er de samme.

For hvert nivå lagrer du:

  • figuren med tiltrekningsområder og iterasjonstall,
  • sentrum og vindusbredde,
  • bredden som én piksel representerer,
  • antall synlige tiltrekningsområder (farger),
  • andel grensepiksler,
  • gjennomsnittlig iterasjonstall på grensen og i indre områder.

Delproblem 4: Hva forteller fraktalzoomen om Newtons metode?

Fraktalbildet er ikke pynt ved siden av den numeriske metoden. Hver ny detalj forteller at startverdier som er svært nær hverandre, kan følge forskjellige Newton-baner og finne forskjellige nullpunkter. Iterasjonskartet forteller i tillegg om disse områdene er numerisk krevende.

Velg på det siste zoomnivået:

  • to nabostartverdier i forskjellige tiltrekningsområder (ulik farge),
  • én startverdi et stykke inne i et ensfarget område.

Kjør newton_trace for alle tre. Sammenlign de første iteratene, største skrittlengde, antall iterasjoner og siste residual. Målet er å knytte de små fargestrukturene tilbake til faktiske iterative følger.

Fraktalrapporten

Skriv en samlet rapport. Figurene og tabellen er data; svarene under er analysen.

  1. Hva forventet du før du zoomet, og hva viste bildene?
  2. Hvilke nye detaljer dukket opp på hvert nivå? Ble grensen noen gang en enkel, glatt linje?
  3. Så du nøyaktige kopier av tidligere mønstre, eller nye mønstre med lignende kompleksitet? Hvorfor kan begge deler omtales som fraktallignende?
  4. Hvor liten endring i \(z_0\) representerte én piksel på siste nivå?
  5. Fortsatte nabopiksler å finne forskjellige nullpunkter på denne skalaen?
  6. Hvordan skilte iterasjonstallene på grensen seg fra indre områder?
  7. Hva viste de tre newton_trace-forsøkene om hvorfor fargene blir ulike?
  8. Hvordan kan tol, maxiter og flyttallsregning påvirke de minste strukturene du ser?
  9. Hvorfor er flere vellykkede zoomnivåer god numerisk evidens for en fraktallignende grense, men ikke et bevis på detaljer på alle skalaer?

Ekstra nøtt: Kan grensen ha en dimensjon mellom 1 og 2?

Denne delen er frivillig. Den introduserer én idé som ikke er nødvendig for resten av prosjektet.

Fraktalzoomen viste nye detaljer, men kan vi sette ett enkelt tall på hvor komplisert grensen ser ut? Vi begynner uten en formel.

Se for deg at grensen var en vanlig, glatt strek gjennom bildet. Hvis vi går fra 100 til 200 piksler i hver retning, blir pikslene omtrent halvparten så brede. Da trenger vi omtrent dobbelt så mange små piksler for å følge den samme streken:

\[ 100\longrightarrow200 \qquad\text{gir omtrent}\qquad N\longrightarrow2N. \]

Antallet piksler langs en strek vokser altså med omtrent faktor 2 når oppløsningen dobles.

Tenk deretter på et område som er helt fylt med grense. Når vi dobler oppløsningen, får vi dobbelt så mange piksler vannrett og dobbelt så mange loddrett. Antallet blir da omtrent fire ganger så stort:

\[ N\longrightarrow4N. \]

En fraktalgrense kan vokse raskere enn en vanlig strek, men langsommere enn et helt fylt område. Derfor ser vi først på den enkle vekstfaktoren

\[ q=\frac{\text{nytt antall grensepiksler}} {\text{gammelt antall grensepiksler}}. \]

  • \(q\approx2\) ligner veksten til en vanlig linje.
  • \(q\approx4\) ligner veksten til et fylt område.
  • En verdi mellom 2 og 4 tyder på noe mellom disse ytterpunktene.

Hvis vi ønsker å skrive dette som et dimensjonstall, spør vi: Hvilken potens \(D\) må vi opphøye 2 i for å få vekstfaktoren?

\[ 2^D=q. \]

Dermed gir \(q=2\) dimensjonen \(D=1\), mens \(q=4\) gir \(D=2\). For andre vekstfaktorer regner Python ut

\[ D=\log_2(q). \]

Dette er hele ideen bak dimensjonsanslaget i nøtten.

Vi må bruke ett fast plottevindu. Vi gjør pikslene mindre ved å øke oppløsningen fra 100 til 200 og deretter 400, men vi flytter ikke vinduet. Hvis vinduet også flyttes eller krympes, vet vi ikke om endringen skyldes mindre piksler eller at vi har valgt en annen del av grensen.

Les først vekstfaktoren uten å se på \(D\): Ligger den nærmest 2, nærmest 4 eller mellom? Bruk deretter \(D\) som en kort oppsummering av den samme målingen.

Vurder om de to \(D\)-anslagene nærmer seg hverandre. Et tall mellom 1 og 2 er interessant evidens, men ikke et bevis eller en eksakt dimensjon. Resultatet avhenger av vinduet, oppløsningene, grensepikselregelen, tol og maxiter. Forklar også med egne ord hvorfor vi ikke kan bruke tre forskjellige zoomvinduer i samme måling.

9. Konklusjon

Skriv en samlet konklusjon på omtrent 200–300 ord. Den skal svare på:

  • Hvordan påvirker startverdien hvilket nullpunkt Newtons metode finner?
  • Hvor er konvergensen rask, og hvor kreves mange iterasjoner?
  • Finner metoden alltid nullpunktet som ligger nærmest startverdien?
  • Hvilken rolle ser de kritiske punktene ut til å spille?
  • Hva viste perturbasjonsforsøket nær en grense?
  • Hva viste fraktalzoomen om følsomhet for stadig mindre endringer i startverdien?
  • Hvordan påvirker residualtoleransen og maxiter klassifiseringen?
  • Hvilke påstander bygger på numeriske eksperimenter, og hva kan eksperimentene ikke bevise?
  • Når mener du det er forsvarlig å rapportere at metoden har konvergert?

Leveranse

Lever én Quarto-side eller notebook med:

  1. tildelt funksjon og nullpunkter,
  2. analyserte iterasjonshistorikker for raske, langsomme og følsomme startverdier,
  3. hovedfigur med tiltrekningsområder og iterasjonskart,
  4. test av om nærmeste nullpunkt blir funnet,
  5. undersøkelse av ett kritisk punkt,
  6. perturbasjonsforsøk nær en grense,
  7. kontroll av toleranse og maxiter,
  8. minst tre zoomnivåer, grensesammenligning og fraktalrapport,
  9. konkrete parameterverdier og konklusjonen.
AdvarselOm bruk av kodeassistenter

Copilot og andre kodeassistenter er tillatt. Du er likevel ansvarlig for at stoppkriteriet har en matematisk betydning, at ugyldige og ikke-konvergente beregninger behandles separat, at figurene viser det du sier de viser, og at konklusjonene støttes av egne resultater.

Kode som produserer en figur, er ikke i seg selv en analyse.