Tilbake
6.5
Alle fag for Høyskole

6.5 Kontraksjon, fikspunkt og Newtons metode i flere variable

Vis kontraksjon via norm/egenverdi < 1, iterér mot fikspunktet, og kjør Newtons metode for systemer — teoritunge innslag fra 2018 og 2021.

45 min
11 oppgaver
KontraksjonfikspunktNewtons metode i flere variable
Din fremgang i kapitlet
0 / 11 oppgaver
Kapitlets plass i kurset
Forkunnskaper. Dette kapitlet knytter sammen to tidligere tema: egenverdier fra kap. 6.1 (vi bruker at ∣λ∣<1|\lambda|<1 gir kontraksjon) og Jacobi-matrisen fra kap. 2.2 (Newton-steget bruker (F′(x))−1(F'(x))^{-1}). Inversregning fra kap. 1.3 trengs for Newton-steget.

Sist du var her: egenverdiene løses fra det⁡(λI−A)=0\det(\lambda I - A)=0 (kap. 6.1); Jacobi-matrisen F′F' har rad ii lik ∇Fi\nabla F_i (kap. 2.2). Formelsamlingen gir Newtons metode xn+1=xn−(F′(xn))−1F(xn)x_{n+1} = x_n - (F'(x_n))^{-1}F(x_n).

Mange likninger kan ikke løses eksakt, men de kan løses iterativt: gjett en løsning, forbedre gjetningen, gjenta. To slike metoder står i pensum. Fikspunkt-iterasjon skriver likningen som x=F(x)x = F(x) og gjentar zn+1=F(zn)z_{n+1} = F(z_n) — den konvergerer dersom FF er en kontraksjon (trekker punkter nærmere hverandre). Newtons metode lineariserer med Jacobi-matrisen og konvergerer raskt nær en løsning.

Den sentrale teoretiske ideen er kontraksjonsprinsippet: en kontraksjon har nøyaktig ett fikspunkt, og iterasjonen finner det uansett startpunkt. Vi bygger dette i tre løkker: (1) kontraksjon og hvordan man beviser den via norm/egenverdi; (2) fikspunktprinsippet og iterasjon; (3) Newtons metode for systemer, ett steg for hånd.

Løkke 1 — Kontraksjon og kontraksjonsbeviset (~14 min)

Kontraksjon
En avbildning FF er en kontraksjon hvis den trekker alle punktpar nærmere hverandre med en fast faktor K<1K<1:

∣F(x)−F(y)∣≤K ∣x−y∣for alle x,y,0≤K<1.|F(x) - F(y)| \le K\,|x - y| \quad\text{for alle } x,y,\qquad 0\le K<1.

Tallet KK er kontraksjonsfaktoren. Kravet K<1K<1 er strengt: K=1K=1 (bevarer avstand) er ikke nok. Kontraksjoner «klemmer» rommet sammen, og det er derfor de har et entydig fikspunkt.

Spektralradius
Spektralradiusen til en matrise AA er den største tallverdien blant egenverdiene, ρ(A)=max⁡i∣λi∣\rho(A) = \max_i |\lambda_i|. For en lineær avbildning F(x)=AxF(x)=Ax styrer spektralradiusen langtidsoppførselen: er ρ(A)<1\rho(A)<1, krymper AnA^n mot null, og FF er (i en passende norm) en kontraksjon.
Indusert matrisenorm (operatornorm)

En operatornorm ∥A∥\|A\| måler hvor mye AA maksimalt strekker en vektor: ∥A∥=max⁡x≠0∣Ax∣∣x∣\|A\| = \max_{x\ne 0}\dfrac{|Ax|}{|x|}. Da er ∣Ax∣≤∥A∥ ∣x∣|Ax|\le \|A\|\,|x|. Er ∥A∥<1\|A\|<1 for en slik norm, er F(x)=AxF(x)=Ax en kontraksjon med K=∥A∥K=\|A\|. Radsum- og søylesumnormene er lette å regne og gir ofte ∥A∥<1\|A\|<1 direkte.

📜Kontraksjonsbeviset for en lineær avbildning

For F(x)=AxF(x)=Ax er ∣F(x)−F(y)∣=∣A(x−y)∣≤∥A∥ ∣x−y∣|F(x)-F(y)| = |A(x-y)| \le \|A\|\,|x-y|. Altså:

- finner du én matrisenorm med ∥A∥<1\|A\|<1, er FF en kontraksjon med K=∥A∥K=\|A\|; eller
- er spektralradiusen ρ(A)<1\rho(A)<1 (alle ∣λi∣<1|\lambda_i|<1), er FF en kontraksjon i en passende norm.

To gyldige normvalg. Feiler det ene (en norm gir ∥A∥≥1\|A\|\ge 1), prøv det andre — egenverdiene avgjør til slutt.

✏️Eksempel 1: Vis at en lineæravbildning er en kontraksjon

Vis at F(x)=AxF(x) = Ax med A=(0,50,20,10,4)A=\begin{pmatrix} 0{,}5 & 0{,}2 \\ 0{,}1 & 0{,}4\end{pmatrix} er en kontraksjon.

Vi bruker egenverdikriteriet. Egenverdier: tr⁡A=0,9\operatorname{tr}A = 0{,}9, det⁡A=0,5⋅0,4−0,2⋅0,1=0,2−0,02=0,18\det A = 0{,}5\cdot0{,}4 - 0{,}2\cdot0{,}1 = 0{,}2 - 0{,}02 = 0{,}18, så
λ2−0,9λ+0,18=0⇒λ=0,9±0,81−0,722=0,9±0,32,\lambda^2 - 0{,}9\lambda + 0{,}18 = 0 \Rightarrow \lambda = \frac{0{,}9\pm\sqrt{0{,}81-0{,}72}}{2} = \frac{0{,}9\pm 0{,}3}{2},
altså λ1=0,6\lambda_1 = 0{,}6 og λ2=0,3\lambda_2 = 0{,}3.

Begge oppfyller ∣λ∣<1|\lambda|<1, så spektralradiusen er ρ(A)=0,6<1\rho(A) = 0{,}6 < 1. Da er F(x)=AxF(x)=Ax en kontraksjon (i en passende norm): ∣F(x)−F(y)∣=∣A(x−y)∣|F(x)-F(y)| = |A(x-y)| krymper med faktor <1<1.

Konklusjon: FF er en kontraksjon fordi begge egenverdier har tallverdi <1<1. (Bekreftelse med søylesumnormen: største søylesum er 0,5+0,1=0,6<10{,}5+0{,}1 = 0{,}6 < 1, så ∥A∥1=0,6\|A\|_1 = 0{,}6 — samme faktor.)

📝Oppgave 1

Vis at F(x)=AxF(x)=Ax med A=(0,30,30,20,4)A=\begin{pmatrix} 0{,}3 & 0{,}3 \\ 0{,}2 & 0{,}4\end{pmatrix} er en kontraksjon, og oppgi en kontraksjonsfaktor.

Løkke 2 — Fikspunkt og fikspunktiterasjon (~14 min)

Fikspunkt

Et fikspunkt for FF er et punkt x∗x^* som avbildes på seg selv: F(x∗)=x∗F(x^*) = x^*. Å løse likningen x=F(x)x = F(x) er nettopp å finne et fikspunkt. Mange likninger g(x)=0g(x)=0 kan skrives om til fikspunktform x=F(x)x = F(x) på flere måter, og valget av FF avgjør om iterasjonen konvergerer.

Fikspunktiterasjon
Fikspunktiterasjonen starter med en gjetning z0z_0 og gjentar

zn+1=F(zn).z_{n+1} = F(z_n).

Hvis FF er en kontraksjon, konvergerer følgen z0,z1,z2,…z_0, z_1, z_2,\dots mot fikspunktet uansett startpunkt. Hvert steg reduserer avstanden til fikspunktet med (minst) faktoren KK, så konvergensen er geometrisk rask.

📜Fikspunktprinsippet (kontraksjonsprinsippet)

En kontraksjon FF på et fullstendig rom har nøyaktig ett fikspunkt x∗x^*, og fikspunktiterasjonen zn+1=F(zn)z_{n+1}=F(z_n) konvergerer mot x∗x^* fra ethvert startpunkt. Feilen avtar geometrisk: ∣zn−x∗∣≤Kn ∣z0−x∗∣|z_n - x^*| \le K^n\,|z_0 - x^*|. Dette er hele grunnen til at kontraksjon er verdt å vise — det garanterer både eksistens, entydighet og en konvergent metode.

✏️Eksempel 2: Fikspunkt og iterasjon
F(x,y)=(0,5x+0,5, 0,5y+1)F(x,y) = (0{,}5x + 0{,}5,\ 0{,}5y + 1). Vis at FF er en kontraksjon, finn fikspunktet, og forklar at iterasjonen konvergerer mot det.
Kontraksjon. FF er affin med lineærdel A=(0,5000,5)A = \begin{pmatrix} 0{,}5 & 0 \\ 0 & 0{,}5\end{pmatrix}. Egenverdiene er 0,50{,}5 og 0,50{,}5 (diagonal), så ρ(A)=0,5<1\rho(A) = 0{,}5 < 1 — FF er en kontraksjon med K=0,5K = 0{,}5.

Fikspunkt. Løs F(x,y)=(x,y)F(x,y) = (x,y) komponentvis:
x=0,5x+0,5⇒0,5x=0,5⇒x=1,y=0,5y+1⇒0,5y=1⇒y=2.x = 0{,}5x + 0{,}5 \Rightarrow 0{,}5x = 0{,}5 \Rightarrow x = 1,\qquad y = 0{,}5y + 1 \Rightarrow 0{,}5y = 1 \Rightarrow y = 2.
Altså fikspunkt (x∗,y∗)=(1,2)(x^*,y^*) = (1,2).

Konvergens. Ved fikspunktprinsippet er (1,2)(1,2) det entydige fikspunktet, og iterasjonen zn+1=F(zn)z_{n+1} = F(z_n) konvergerer mot det uansett start. (Kontroll fra z0=(0,0)z_0=(0,0): z1=(0,5, 1)z_1 = (0{,}5,\ 1), z2=(0,75, 1,5)z_2 = (0{,}75,\ 1{,}5), z3=(0,875, 1,75)z_3 = (0{,}875,\ 1{,}75) — på vei mot (1,2)(1,2), avstanden halveres hvert steg.)

Konklusjon: entydig fikspunkt (1,2)(1,2), og iterasjonen konvergerer dit.

📝Oppgave 2
F(x,y)=(0,25x+3, 0,25y−6)F(x,y) = (0{,}25x + 3,\ 0{,}25y - 6). Vis at FF er en kontraksjon og finn det entydige fikspunktet.

Løkke 3 — Newtons metode for systemer (~14 min)

Newtons metode for system
For å løse F(x)=0F(x) = 0 der F:Rn→RnF:\mathbb{R}^n\to\mathbb{R}^n, lineariserer Newtons metode med Jacobi-matrisen F′F' og iterer:

xn+1=xn−(F′(xn))−1F(xn)x_{n+1} = x_n - \bigl(F'(x_n)\bigr)^{-1} F(x_n)

(formelen er utdelt). I hvert steg løser man egentlig det lineære systemet F′(xn) Δ=−F(xn)F'(x_n)\,\Delta = -F(x_n) og setter xn+1=xn+Δx_{n+1} = x_n + \Delta. Nær en løsning konvergerer metoden svært raskt.

Jacobi-matrisen i Newton-steget

Newton-steget krever Jacobi-matrisen F′(x)F'(x) (rad ii = ∇Fi\nabla F_i, fra kap. 2.2), evaluert i det aktuelle punktet xnx_n, og deretter dens invers. For 2×22\times2-systemer regnes inversen med den vanlige formelen 1det⁡(d−b−ca)\tfrac{1}{\det}\begin{pmatrix} d & -b \\ -c & a\end{pmatrix}. Er F′(xn)F'(x_n) singulær, stopper metoden — velg da et annet startpunkt.

📜Konvergens av Newtons metode (kjennskap)

Nær en enkel løsning (der F′F' er inverterbar) konvergerer Newtons metode kvadratisk: antall korrekte siffer omtrent dobles for hvert steg. Til gjengjeld kan et dårlig startpunkt gi divergens — metoden er lokal. I praksis holder ett–to steg for å komme nær løsningen når startpunktet er rimelig.

✏️Eksempel 3: Ett Newton-steg for et system

Utfør ett steg av Newtons metode på systemet F(x,y)=(x2+y2−4, x−y)F(x,y) = (x^2 + y^2 - 4,\ x - y) fra startpunktet (x0,y0)=(32,32)(x_0,y_0) = \left(\tfrac32,\tfrac32\right).

Jacobi-matrisen: F′(x,y)=(2x2y1−1)F'(x,y) = \begin{pmatrix} 2x & 2y \\ 1 & -1\end{pmatrix}.

Evaluer i (32,32)(\tfrac32,\tfrac32): F(32,32)=(94+94−4, 0)=(12, 0)F(\tfrac32,\tfrac32) = \left(\tfrac94 + \tfrac94 - 4,\ 0\right) = \left(\tfrac12,\ 0\right) og F′(32,32)=(331−1)F'(\tfrac32,\tfrac32) = \begin{pmatrix} 3 & 3 \\ 1 & -1\end{pmatrix}.

Invers: det⁡=3⋅(−1)−3⋅1=−6\det = 3\cdot(-1) - 3\cdot1 = -6, så (F′)−1=1−6(−1−3−13)=(161216−12)\bigl(F'\bigr)^{-1} = \tfrac{1}{-6}\begin{pmatrix} -1 & -3 \\ -1 & 3\end{pmatrix} = \begin{pmatrix} \tfrac16 & \tfrac12 \\ \tfrac16 & -\tfrac12\end{pmatrix}.

Newton-steget:
(x1y1)=(3232)−(161216−12)(120)=(3232)−(112112)=(17121712).\begin{pmatrix} x_1 \\ y_1\end{pmatrix} = \begin{pmatrix} \tfrac32 \\ \tfrac32\end{pmatrix} - \begin{pmatrix} \tfrac16 & \tfrac12 \\ \tfrac16 & -\tfrac12\end{pmatrix}\begin{pmatrix} \tfrac12 \\ 0\end{pmatrix} = \begin{pmatrix} \tfrac32 \\ \tfrac32\end{pmatrix} - \begin{pmatrix} \tfrac{1}{12} \\ \tfrac{1}{12}\end{pmatrix} = \begin{pmatrix} \tfrac{17}{12} \\ \tfrac{17}{12}\end{pmatrix}.

Konklusjon: (x1,y1)=(1712,1712)≈(1,417, 1,417)(x_1,y_1) = \left(\tfrac{17}{12},\tfrac{17}{12}\right) \approx (1{,}417,\ 1{,}417) — nærmere den eksakte løsningen (2,2)≈(1,414, 1,414)(\sqrt2,\sqrt2) \approx (1{,}414,\ 1{,}414).

📝Oppgave 3

Utfør ett steg av Newtons metode på F(x,y)=(x2−y, x+y2−3)F(x,y) = (x^2 - y,\ x + y^2 - 3) fra startpunktet (1,1)(1,1). Oppgi svaret eksakt.

Eksamensrettet oppgavepulje

Stigende vanskegrad. Begrunn kontraksjon med norm/egenverdi, og før Newton-steget med eksakt invers.

📝Oppgave 4

Avgjør om F(x)=AxF(x)=Ax er en kontraksjon når A=(0,4000,6)A=\begin{pmatrix} 0{,}4 & 0 \\ 0 & 0{,}6\end{pmatrix}.

📝Oppgave 5

Finn fikspunktet til F(x)=0,5x+3F(x)=0{,}5x + 3 (én variabel) og forklar hvorfor iterasjonen konvergerer.

📝Oppgave 6
F(x)=AxF(x)=Ax med A=(0,20,50,10,2)A=\begin{pmatrix} 0{,}2 & 0{,}5 \\ 0{,}1 & 0{,}2\end{pmatrix}. Vis at FF er en kontraksjon ved å bruke en matrisenorm.
📝Oppgave 7
F(x,y)=(0,5y+1, 0,5x+1)F(x,y) = (0{,}5y + 1,\ 0{,}5x + 1).

a) Vis at FF er en kontraksjon.

b) Finn det entydige fikspunktet.

📝Oppgave 8

Utfør ett Newton-steg på F(x,y)=(x2+y−3, xy−2)F(x,y) = (x^2 + y - 3,\ xy - 2) fra startpunktet (1,2)(1,2). Oppgi svaret eksakt.

Begrepsbank

Kjernebegrepene fra kapitlet samlet som oppslag og flashcards.

Begrepsbanken er flashcard-/repetisjonsstoff — den gjentar det du nettopp har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder kjernestoffet.

Kontraksjonsfaktor KK

Tallet 0≤K<10\le K<1 i kontraksjonsulikheten ∣F(x)−F(y)∣≤K∣x−y∣|F(x)-F(y)|\le K|x-y|. Jo mindre KK, desto raskere konvergerer fikspunktiterasjonen (∣zn−x∗∣≤Kn∣z0−x∗∣|z_n-x^*|\le K^n|z_0-x^*|). For en lineær avbildning kan KK tas lik en matrisenorm ∥A∥<1\|A\|<1 eller lik spektralradiusen.

Fullstendig rom

Et rom er fullstendig når enhver «konvergent-aktig» følge (Cauchy-følge) faktisk har en grense i rommet. Rn\mathbb{R}^n er fullstendig, så kontraksjonsprinsippet gjelder alltid der. Fullstendigheten er det som garanterer at fikspunktiterasjonens grense virkelig eksisterer i rommet.

Rad- og søylesumnorm

To lettregnede operatornormer: radsumnormen ∥A∥∞\|A\|_\infty er den største summen av tallverdiene i en rad, og søylesumnormen ∥A∥1\|A\|_1 er den største slike søylesummen. Begge oppfyller ∣Ax∣≤∥A∥ ∣x∣|Ax|\le\|A\|\,|x| i sin norm, så er en av dem <1<1, har du vist kontraksjon uten å regne egenverdier.

Repetisjon
Din fremgang
0 / 3 oppgaver
Symbol- og formelliste

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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.