Iteration

• Problemet
• Newton iteration
• f(x) = x
• Iteration af f(x) = –x² + a
• Iteration af f(x) = a · xⁿ + c
• Kompleks iteration c = c² – 1

Problemet

I matematik er man ofte ude for at skulle løse "uløselige" ligninger. F. eks. har ligningen cos(x) = x selvfølgelig en løsning. Men vi kan ikke bestemme den præsist. I stedet kan man angribe ligningen med en teknik, der kaldes iteration.

Newton iteration

Allerede Isaac Newton fandt på at anvende differentialregning til at finde tilnærmende løsninger til vanskelige ligninger af typen f(x) = 0. Hans metode går ud på at erstatte grafen for f lokalt med dens tangent y = f(x0) + f '(x0) · (x – x0).

Tangenten skærer 1 -aksen: 0 = f(x₀) + f '(x₀) · (x – x₀), eller

x – x0 =

–f(x0) f '(x0)

eller

x = x0 –

f(x0) f '(x0)

.

Newtons algoritme er som følger

1. Vælg et passende udgangspunkt x₀
2. Beregn x af x = x₀ – f(x₀)/f '(x₀)
3. Sæt x₀ = x og gå til 2.
4. Fortsæt, indtil f(x) er tilstrækkelig tæt ved 0.

Metodens svaghed er, at dens succes ofte afhænger af den valgte startværdi.

Newton iteration af ax³ + bx² + cx + d = 0

f(x) = x

Lad ligningen være g(x) = 0.

1. Først omformer vi ligningen til f(x) = x.
2. Ideen er nu, at vi vælger et "tilfældigt" udgangspunkt x₁.
3. Så beregnes x₂ = f(x₁).
4. Så beregnes x₃ = f(x₂). O.s.v.
5. Hvis rækken x₁, x₂, x₃, ... , x_n, ... er konvergent med grænseværdien x₀ for n → ∞ er x₀ en løsning til ligningen.

Metoden kan illustreres grafisk ved at tegne graferne for y = f(x) og y = x i et koordinatsystem og

1. start på 1 - aksen i x
2. gå lodret til skæring med f - grafen
3. gå vandret til skæring med y = x. Skæringspunktets førstekoordinat er den nye x-værdi
4. gå lodret til skæring med f - grafen
5. o. s. v.
6. (den fremkomne kurve kaldes et spind).

Det gode spørgsmål er nu: Hvad skal der til, for at rækken x₁, x₂, x₃, ... , x_n, ... konvergerer ? Der gælder følgende sætning:

Hvis f(x) er differentiabel i et interval I omkring løsningen x₀, og der findes et K så
|f '(x)| ≤ K < 1 i I, så konvergerer rækken x₁, x₂, ... , x_n, ...

Bevis
Ved hjælp af middelværdisætningen har vi

|x_n – x₀| = |f(x_n–1) – f(x₀)| = |f '(t)| |x_n–1 – x₀| ≤ K |x_n–1 – x₀| = K |f(x_n–2) – f(x₀)|
≤ K² |x_n–2 – x₀| ... ≤ Kⁿ |x₁ – x₀|.
Da 0 ≤ K < 1 giver, at kⁿ → 0 for n → ∞, ser vi, at |x_n – x₀| → 0 for n → ∞.

[ Hovedmenu ] [ Ordliste ]

Iteration af f(x) = –x² + a

[ Hovedmenu ] [ Ordliste ]

Iteration af f(x) = a·xⁿ + c

[ Hovedmenu ] [ Ordliste ]

Kompleks iteration z = z² + a

	I de senere år har den komplekse ligning z = z2 + a haft stor interesse, fordi den ligger til grund for Mandelbrots fraktal.

Sætter vi z = z₁ + iz₂ og a = x + iy, er z² + a = z₁² – z₂² + x + i (2 z₁z₂ + y) ifølge regneregler for komplekse tal..

Ideen er nu med udgangspunktet z = a = x + iy at udføre transformationen

(z₁² – z₂² + x , 2z₁z₂ + y) → (z₁, z₂)

et antal gange. Der sker ét af to:

1. (z₁, z₂) holder sig i nærheden af (0, 0). Punktet kaldes Tiltrækkende
2. (z₁, z₂) stikker af. Punktet kaldes Frastødende.

Mandelbrots fraktal er grænsekurven for området af tiltrækkende punkter.

Denne regnemaskine itererer z = z² + a .
Indtast x, y og klik uden for boksen.

x : y : giver
z₁: z₂: afstand =

Denne regnemaskine itererer z = z² + a højest n = 200 gange.
Indtast x og y og klik uden for boksen.

x : y : er af type = Antal iterationer :

Mandelbrots fraktal

Fastsæt vinduet og tryk på Ok

[ Toppen af siden ] [ Ordliste ] [ Tilbage til hovedsiden ]