IN-KJM1900 - H?st 2018

Diskret kalkulus

IN-KJM1900, Tredje forelesning, 30.oktober

Mål for økta:

  • Praktisk info
  • Fortsettelse fra forrige gang:
    • Newtons metode
    • Sekantmetoden
  • Ny teori: diskret kalkulus
    • Diskretisering
    • Numerisk derivasjon
    • Numerisk integrasjon
    • Differensialligninger

Orakeltjeneste, uke 44

Orakelhjelp tilbys ved Kjemisk Institutt p? f?lgende tidspunkter denne uka

Tirsdag 30/10 14.00-16.00
Onsdag 31/10 13.00-15.00
Torsdag 1/11 11.00-13.00

Ellers g?r gruppeundervisning og samretting som normalt.

Se ogs? nettressurser.

Innlevering av deloppgave 1

  • Fristen for ? levere deloppgave 1 av prosjektet er s?ndag 4. november klokka 23.59.
  • Oppgaven leveres p? Devilry.?
    • ?
  • Vi oppfordrer til ? benytte samrettinga p? torsdag klokka 10.15-12.00
  • Gruppetimene g?r som normalt
  • Sp?rsm?l om prosjektet?

Newtons metode

R?tter

Newtons metode er en fremgangsm?te som for en hvilken som helst jevn funksjon $f(x)$ lar oss finne en $x_*$ slik at

$$f(x_*) = 0$$

Disse punktene kalles r?ttene til funksjonen $f(x)$.
I et hvilket som helst punkt $x_0$ kan vi beregne en tangent $t_f(x_0)$. Analytisk har vi

$$ t_f(x) = f(x_0) - f'(x_0)(x-x_0) $$

I et gitt punkt $x_n$ kan vi finne tangentens rot som vi her kaller $x_{n+1}$ (slik at $t_f(x_{n+1})=0$) ved ? l?se ligningen

$$ t_f(x_{n+1}) = f(x_{n}) - f'(x_{n})(x_{n+1}-x_{n}) = 0$$

L?ser vi ligningen over for $x_{n+1}$ finner vi med enkel algebra at roten er

$$ x_{n+1} = x_{n} - \frac{f(x_n)}{f'(x_n)}$$

Beskrivelse av Newtons metode

Newtons metode er en fremgangsm?te som for en hvilken som helst jevn funksjon $f(x)$ lar oss finne en $x_*$ slik at $$f(x_*) = 0$$ Den formelle beskrivelsen er at vi f?rst gjetter p? en $x_0$, og deretter gjentar f?lgende operasjon $$ x_{n+1} = x_{n} - \frac{f(x_n)}{f'(x_{n})}$$ Vi gjentar frem til enten et maksimalt antall interasjoner er n?dd, eller at funksjonsverdien i punktet er tilstrekkelig n?rt null: $$\vert f(x_{n+1}) \vert \le \epsilon$$

Dette kalles en konvergensbetingelse. En annen konvergensbetingelse kan v?re at forskjellen mellom $x_n$ og $x_{n+1}$ er mindre enn en grenseverdi: $$ \vert x_n - x_{n+1} \vert \le \epsilon$$

Sekantmetoden

Om vi erstatter den deriverte i Newtons metode med en numerisk differanse f?r vi en variasjon av Newtons metode som kalles sekantmetoden:

$$ x_{n+1} \approx x_{n} - \frac{f(x_n)}{\mathbf{D}^+f(x_n)} = x_{n} - \frac{f(x_n)}{f(x_n + \Delta x) - f(x_n)}\Delta x $$

Live-koding, Newtons metode

Vi skal n? se et eksempel p? Newtons metode.

Det vil best? av:

  1. Definisjon av funksjon og dens deriverte.
  2. Visuell deteksjon av r?ttene.
  3. Implementasjon av Newtons metode.
  4. Eksempel p? patologiske tilfeller (hvor metoden feiler)

Diskretisering

Diskretisering

Diskret kalkulus = "opstykket"/numerisk kalkulus.

I diskret kalkulus har vi approksimasjoner p? variabler, funksjoner, operasjoner og modeller som svarer til kontinuerlige ("sammenhengende") st?rrelser i klassisk kalkulus:
Kontinuerlig Diskret
$x$ $x_i = i\cdot\Delta x$
$f(x)$ $f_i = f(x_i) = f(i\cdot\Delta x)$
$\frac{d}{dx}$ $D^+$
$\int$ $\sum$

Med approksimasjon menes her at vi gj?r en feil. Vi antar ofte at denne er s? liten at den er neglisjerbar.

Diskretisering av variabler

I klassisk kalkulus benytter vi gjerne kontinuerlige variabler:

\begin{equation} x \in \mathbb{R} \end{equation}

Disse kan diskretiseres ved ? velge en endelig oppl?sning p? $\mathbb{R}$, slik at

\begin{equation} x \rightarrow x_i = i\cdot\Delta x, i \in \mathbb{Z} \end{equation}

(Det siste betyr at i er et heltall)

Dette er ofte f?rste trinn n?r man klargj?r et problem for numerisk l?sning.

Diskretisering av funksjoner

N?r vi har diskretisert variablene, f?lger det at ogs? funksjoner n? kun er definert i diskrete punkter. Hvor vi i klassisk kalkulus har

\begin{equation} f(x) \end{equation}

har vi n? i steden

\begin{equation} f(x) \rightarrow f_i = f(x_i) = f(i\cdot\Delta x) \end{equation}

Diskretisering av derivasjon

Vi har allerede introdusert mulige diskretiseringer av differensialoperatoren $\frac{d}{dx}$ som brukes i derivasjon. I klassisk kalkulus har vi

$$ \frac{d}{dx} f(x) := \lim_{\Delta x \rightarrow 0} \frac{f(x + \Delta x) - f(x)}{\Delta x}$$

Analogt har vi i diskret kalkulus en av flere mulige approksimasjoner:

$$ \mathbf{D}^+ f_i := \frac{f_{i+1} - f_i}{\Delta x}$$

(Vi vil kun benytte denne i dette kurset)

Diskretisering av integrasjon

I l?pet av forelesningene vil vi se at diskret integrasjon kan gj?res som summasjoner, for eksempel med trapesregelen:

\begin{equation} \int_a^b f(x) dx \approx \sum_{i=1}^{N-1} \left(x_{i+1}-x_i\right)\frac{f(x_i) + f(x_{i+1})}{2} = \frac{\Delta x}{2} \sum_{i=1}^{N-1} \left(f_{i+1}+f_i\right) \end{equation}

Vi kommer tilbake til dette i en annen forelesning, men tar det med her for kompletthet.

Differensialligninger

I dette kurset m?ter vi differensialligninger p? formen

$$\frac{d}{dt} y(t) = f(y(t), t)$$

  • Den ukjente i ligninga er en funksjon: $y(t)$
  • Ligninga over er en 1. ordens ordin?r "diffligning".
    • Enkeltderivert $\rightarrow$ "f?rste orden"
    • Kun derivert med hensyn p? en variabel $\rightarrow$ "ordin?r"
  • Diffligninger brukes gjennomg?ende i vitenskap; b?lger, diffusjon, osv.
  • I kjemi, for eksempel for:
    • Reaksjonskinetikk
    • Kvantekjemi (Schr?dingerligningen)
    • Radioaktivitet

Eksempel på en differensialligning

Vi ser p? ligningen:

\begin{equation} \frac{d}{dt}y(t) = -ky(t) \end{equation}

Hvor $k \in \mathbb{R}$ er en konstant.

Den ukjente her er $y(t)$. L?ser vi ligningen (se for eksempel denne lenken for en analytisk l?sning), finner vi at en mulig funksjon for $y$ er

\begin{equation} y(t) = A_0e^{-kt} \end{equation}

ettersom vi kan sette inn i ligningen slik at

\begin{equation} \frac{d}{dt}y(t) = \frac{d}{dt}A_0e^{-kt} =-k A_0e^{-kt} = -ky(t) \end{equation}

Differensialligninger: initialverdiproblemer

Du skal ikke l?se differensialligninger analytisk i dette kurset.

Derimot vil funksjonene vi ser p? ha en kjent initialverdi

$$\frac{d}{dt} y(t) = f(y(t), t)$$ $$y(0) = a$$

Dette kalles et initialverdiproblem, og har i v?rt tilfelle en rett-frem l?sning

$$ y(t) = ae^{-kt}$$

Vi l?ser det numerisk med de verkt?yene vi har gjennomg?tt s? langt.

Numerisk l?sning av differensialligninger

Initialverdiproblem:

$$\frac{d}{dt} y(t) = f(y(t), t)$$ $$y(0) = a$$

F?lgende fremgangsm?te vil alltid virke i dette kurset, samt i mange andre tilfeller:

  1. Diskretiser problemet (variabler, funksjoner). (la $t \rightarrow t_n = n \cdot \Delta t$).
  2. Diskretiser differensialoperatoren ($\frac{d}{dt} \rightarrow \mathbf{D}^+$ ).
  3. L?s algebraisk for neste funksjonsverdi $f_{n+1} = ...$
  4. Skriv en kode som iterativt l?ser for neste funksjonsverdi.
  5. Presenter og fortolk resultatene.

$\rightarrow$ Live kodeeksempel: reaksjonskinetikk

Oppsummering av dagen

  • Praktisk info
  • Fortsettelse fra forrige gang:
    • Newtons metode
    • Sekantmetoden
  • Ny teori: diskret kalkulus
    • Diskretisering
    • Numerisk derivasjon
    • Numerisk integrasjon
    • Differensialligninger

Veien videre?