8.2 Lineær programmering

Likningen uten fasit

En økonom sitter med likningen $x^3 - 2x - 5 = 0$ — kanskje fra en kostnadsmodell — og oppdager noe ubehagelig: ingen av skoleformlene biter på den. Slik er det med mange likninger; $x = \cos x$ har for eksempel ingen analytisk løsning i det hele tatt. Men «uløselig» betyr ikke «ubesvarlig». Numeriske metoder gir tilnærmede løsninger med vilkårlig nøyaktighet — du bestemmer selv hvor mange desimaler du trenger.

Vi skal se på tre metoder: halveringsmetoden (enkel og pålitelig), Newtons metode (rask og kraftig) og numerisk integrasjon (for arealer uten antiderivert).

Halveringsmetoden bygger på skjæringssetningen: er $f$ kontinuerlig på $[a, b]$ og har $f(a)$ og $f(b)$ motsatt fortegn, finnes minst ett nullpunkt i intervallet. Algoritmen er ren jakt med innsnevring: beregn midtpunktet $\displaystyle m = \frac{a+b}{2}$ og $f(m)$; har $f(a)$ og $f(m)$ motsatt fortegn, ligger nullpunktet i $[a, m]$ — ellers i $[m, b]$. Gjenta. For hver runde halveres intervallet, og etter $n$ halveringer er feilgrensen $\displaystyle \frac{b-a}{2^n}$ — en garanti, ikke et håp.

Prøv på økonomens likning. $f(2) = 8 - 4 - 5 = -1 < 0$ og $f(3) = 27 - 6 - 5 = 16 > 0$: motsatt fortegn, så nullpunktet ligger i $[2, 3]$. Halvering 1: $f(2{,}5) = 5{,}625 > 0$, nytt intervall $[2,\ 2{,}5]$. Halvering 2: $f(2{,}25) \approx 1{,}89 > 0$, nytt intervall $[2,\ 2{,}25]$. Halvering 3: $f(2{,}125) \approx 0{,}35 > 0$. Halvering 4: $f(2{,}0625) \approx -0{,}35 < 0$, nytt intervall $[2{,}0625,\ 2{,}125]$. Nullpunktet er cirka $x \approx 2{,}09$, med feilgrense $\displaystyle \frac{1}{2^4} = 0{,}0625$.

Newtons metode — tangentens snarvei

Halveringsmetoden er trygg, men treg. Newtons metode er turboversjonen — til gjengjeld krever den at vi kan derivere $f$.

Ideen er geometrisk vakker: stå i et punkt $x_0$ nær nullpunktet, trekk tangenten til $f$ der, og følg den ned til den krysser $x$-aksen. Krysningspunktet er et nytt og som regel mye bedre estimat $x_1$. Gjenta:

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

Konvergensen er vanligvis lynrask — antall korrekte desimaler omtrent dobles for hvert steg.

Se metoden beregne $\sqrt{2}$, altså nullpunktet til $f(x) = x^2 - 2$ med $f'(x) = 2x$ og startverdi $x_0 = 1$. Steg 1: $\displaystyle x_1 = 1 - \frac{1 - 2}{2} = 1{,}5$. Steg 2: $\displaystyle x_2 = 1{,}5 - \frac{2{,}25 - 2}{3} \approx 1{,}4167$. Steg 3: $\displaystyle x_3 = 1{,}4167 - \frac{2{,}007 - 2}{2{,}833} \approx 1{,}4142$. Etter bare tre steg har vi $\sqrt{2} \approx 1{,}4142$ — korrekt til fire desimaler.

Men kraften har en pris: metoden kan feile. Tre farer truer: startverdien kan ligge for langt fra nullpunktet, $f'(x_n)$ kan bli null (horisontal tangent — formelen deler på null), og har funksjonen flere nullpunkter, kan metoden konvergere mot feil ett. Forutsetningene er altså at $f$ er deriverbar, at $f'(x_n) \neq 0$ underveis, og at starten er god nok.

Praktikerens kompromiss kombinerer det beste fra begge: bruk halveringsmetoden først for å ringe inn et grovt estimat, og la Newtons metode polere det til ønsket presisjon. Trygghet først, fart etterpå.

Trapesmetoden — arealet uten antiderivert

Tredje utfordring: økonomen trenger $\int_0^1 e^{-x^2}\,dx$ — et integral som dukker opp i normalfordelingssammenhenger — men ingen antiderivert finnes i lukket form. Løsningen er numerisk integrasjon: del arealet under kurven i enkle geometriske biter og summer dem.

Trapesmetoden deler $[a, b]$ i $n$ like delintervaller med bredde $\displaystyle h = \frac{b-a}{n}$ og punkter $x_0 = a, x_1, \ldots, x_n = b$, og erstatter kurven med rette linjestykker — hvert delareal blir et trapes:

$$\int_a^b f(x)\,dx \approx \frac{h}{2}\bigl[f(x_0) + 2f(x_1) + 2f(x_2) + \cdots + 2f(x_{n-1}) + f(x_n)\bigr]$$

Endepunktene teller én gang, de indre punktene to (de deles av nabotrapesene). Flere delintervaller gir bedre tilnærming.

For integralet vårt med $n = 4$: $h = 0{,}25$, og funksjonsverdiene er $f(0) = 1$, $f(0{,}25) \approx 0{,}9394$, $f(0{,}5) \approx 0{,}7788$, $f(0{,}75) \approx 0{,}5698$ og $f(1) \approx 0{,}3679$. Da blir

$$I \approx \frac{0{,}25}{2}\bigl[1 + 2(0{,}9394 + 0{,}7788 + 0{,}5698) + 0{,}3679\bigr] \approx 0{,}7430$$

Den eksakte verdien er $\approx 0{,}7468$ — feilen er bare en halv prosent, med fire trapeser og en håndkalkulator.

Et enklere alternativ er rektangelmetoden (midtpunktsregelen), som bruker funksjonsverdien i midtpunktet av hvert delintervall: $\displaystyle \int_a^b f(x)\,dx \approx h \sum f\left(x_{i-1} + \frac{h}{2}\right)$. Trapesmetoden er vanligvis mer nøyaktig for samme $n$. Begge bygger på samme idé som hele kapittelet: når den eksakte veien er stengt, kan en systematisk tilnærming med kjent feilgrense være akkurat like nyttig.

Oppsummering: tilnærming med garanti

Likningen uten fasit fikk sine svar likevel. Halveringsmetoden jakter nullpunkt ved systematisk innsnevring: finn et intervall med fortegnsskifte, halver, behold halvdelen der skiftet bor — og etter $n$ runder er feilen garantert under $\displaystyle \frac{b-a}{2^n}$. Pålitelig, men langsom. Newtons metode $\displaystyle x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ følger tangenten og dobler presisjonen for hvert steg — slik fant tre iterasjoner $\sqrt{2}$ til fire desimaler — men krever deriverbarhet, $f'(x_n) \neq 0$ og en god start. Praktikerens regel: halvering først for trygghet, Newton etterpå for fart.

Trapesmetoden tilnærmer integraler uten antiderivert: $\displaystyle \int_a^b f(x)\,dx \approx \frac{h}{2}(f_0 + 2f_1 + \cdots + 2f_{n-1} + f_n)$, der flere delintervaller gir bedre svar — fire trapeser ga $\int_0^1 e^{-x^2}dx$ med en halv prosents feil. Rektangelmetoden er det enklere søskenet.

Fellesnevneren er kapittelets egentlige lærdom: numerikk er ikke «juks» eller nødløsning, men kontrollert tilnærming med kjent feilgrense — det er nettopp slik datamaskiner, GeoGebra og bankenes risikomodeller regner hele tiden. Når modellene i resten av kapittel 8 møter likninger og arealer uten pen fasit, vet du nå hva som skjer under panseret.