Differensligninger14

Differensligninger

  • Innledende begreper

    • Kapittel 2: Om følger og rekker (aritmetiske, geometriske, og andre mønstre).

    • Fokuset i dette kapittelet: Finne formler for tallfølger ved hjelp av differensligninger.

    • Differensligning: Rekursiv definisjon av en tallfølge.

Rekursiv Definisjon

  • En tallfølge: a0, a1, a2, … an…

  • Hvis an er definert ved forrige ledd(er): rekursivt.

  • Eksempel: an = an-1 + an-2 for n ≥ 2, der a0 = 0, a1 = 1.

    • Anvendelse: Finn an ved å bruke an-1 og an-2, start med a0 og a1.

    • Utfordring med store indekser: Effektiviteten ved direkte metode.

  • Løsning av differensligninger: Gir en formel for n’te ledd uten tidligere ledd.

Fibonacci-tallene

  • Rekursiv definisjon: an = an-1 + an-2, a0 = 0, a1 = 1

  • Tallfølgen: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …


Generell Form for Lineær Differensligning

  • En lineær differensligning av k’te orden:

    • an = c1an-1 + c2an-2 + c3an-3 + … + ckan-k

    • c1, c2, c3,…, ck = reelle tall (koeffisienter).

  • Fibonacci-ligning: 2. orden (c1 = 1, c2 = 1).

Typer Differensligninger

  1. 1. ordens differensligning

    • an = c*an-1 + d

    • Eksempel: Hanois tårn: Hn = 2Hn-1 + 1.

  2. 2. ordens differensligning

    • an = c1an-1 + c2an-2

    • Krever to startebetingelser.

Løsning av 2. ordens Differensligning

  • Gitt: an = c1an-1 + c2an-2 (c2 ≠ 0)

  • Karakteristisk polynom:

    • r2 = c1*r + c2

    • Kan omformes til: r2 - c1*r - c2 = 0

Eksempler på Karakteristiske Polynom

  • Eksempel 1: an = 5an-1 - 6an-2

    • r2 - 5r + 6 = 0

  • Eksempel 2: an = 2an-1 + 3an-2

    • r2 - 2r - 3 = 0

Løsning av 2. Gradsligning

  • Løsningene (røttene):

    • r1 = -b ± √(b2 - 4ac) / 2a

  • Eksempel: an = -an-1 + 6an-2, a0 = 1, a1 = 3.

    • Karakteristisk polynom: r2 + r - 6 = 0

    • Løsning gir røttene: r1 = 2, r2 = -3

Generell Løsning ved Ulike Røtter

  • Hvis differensligningen har to reelle løsninger:

    • an = αr1^n + βr2^n

  • Eksempel:

    • an = -an-1 + 6an-2

      • Røtter: r1 = 2, r2 = -3

      • Ligning: α + β = a0, αr1 + βr2 = a1

Løsning av Differensligninger med Sammenfallende Røtter

  • Hvis r1 = r2, så:

    • Generell løsning: an = αrn + βn*rn

  • Sett opp ligningssett for å løse for α og β ved kjente startbetingelser.

Differensligning i Java

  • Rekursiv metode for Fibonacci:

    • public static int fib(int n)

  • Rekursiv metode for Hanois tårn:

    • public static int hanoi(int n)