Numerisk analyse

Numerisk analyseer en gren avmatematikkder en studerer metoder ogalgoritmerfor å utføre beregninger medtall.Algoritmene er ofte konstruert for å finnetilnærmedeløsninger på matematiske problemstillinger som vanskelig lar seg løse eksakt. Utføring av beregninger pådatamaskinermedaritmetikkbasert påflyttaller også et viktig studieområde.

Fagfeltet numerisk analyse er svært viktig i mange praktiske anvendelser av matematikk, for eksempel iøkonomi,fysikk,kjemi,meteorologiogingeniørfag.Metoder som utvikles blir kaltnumeriske metoder.Fagfeltet omtales også somnumerikkognumerisk matematikk.En person som arbeider med fagfeltet kalles ennumeriker.

Introduksjon

Anvendt matematikkhar tradisjonelt arbeidet med å gi fysiske problemstillinger en matematisk formulering, og så forsøkt å uttrykke løsninger i form av kjentefunksjoner.For praktiske problemstillinger laget en enkle beregningsmetoder som var mulig å utføre for hånd. Omfanget av problem som lot seg behandle på denne måten var imidlertid svært begrenset.

Utvikling av datamaskiner har gjort det mulig å gjennomføre et stort antall beregninger på kort tid, samtidig som moderne teknologi og ingeniørkunst har stilt nye og større krav til matematikken. Parallelt med framveksten av datamaskiner har det derfor utviklet seg et stort behov for avanserte beregningsmetoder. Numerisk analyse er utviklet for å dekke dette behovet.

Eksempel: Polynomberegning

En grunnleggende problemstilling i numerisk analyse er å finne effektive metode for beregning av funksjoner. Anta at en i en datamaskin - eller for hånd - har behov for å utføre beregning avpolynomet

$f(x)=x^{3}+3x^{2}+6x+2\,$

Med argumentet x=2,1 vil polynomverdien rett fram kunne regnes ut som

$f(x)=2,1\times 2,1\times 2,1+3\times 2,1\times 2,1+6\times 2,1+2\,$

Denne beregningsmåten krever at en må en utføretreaddisjoner ogfemmultiplikasjoner. Alternativt kan en bruke den følgende funksjonsformen:

$f(x)=((x+3)x+6)x+2\,$

Selv om dette uttrykket er matematisk ekvivalent med det første, vil det ikke være det numerisk. Utregning av funksjonen basert på det alternative uttrykket krever færre operasjoner: tre addisjoner og to multiplikasjoner.

Den siste beregningsformen er basert på den såkalteHorners metode,en effektiv algoritme for beregning av polynom. Metoden er oppkalt etter den britiske matematikerenWilliam Georg Horner.Horners metode eroptimali den forstand at enhver beregning av et polynom må bruke minst like mange operasjoner som denne metoden.

Tilnærmede løsninger

Mange matematiske problem kan være vanskelige å løse eksakt, men det kan likevel være viktig å ha en løsning som er «nesten» riktig, kanskje god nok til praktisk bruk. Et viktig mål i numerisk analyse er å utvikle og studere løsningsmetoder som kan gi slike løsninger. Hva som skal til for å karakterisere løsningen som «nesten rett» vil avhenge av både problemstilling og bruk.

Eksempel: Tilnærming til tallet pi

Forholdet mellom omkretsen og diameteren i en sirkel er liktallet pi eller π.For mange praktiske formål er tilnærmingen 3,14 eller kanskje også 22/7 eller 355/113 nøyaktig nok med mange nok desimaler. Disse tilnærmingene er en aproksimativ løsning til problemstillingen å finne forholdet mellom omkretsen og diameteren i en sirkel. Gjennom historien har man funnet stadig bedre tilnærminger til pi med stadig flere desimaler.

Direkte og iterative metoder

Direkte metoder finner løsningen på et problem i et endelig antall steg. Løsningen av enandregradsligningkan for eksempel uttrykkes i ett enkelt steg, fordi vi kjenner denanalytiskeformen til løsningen. I motsetning til direkte metoder, vil iterative metoder forsøke å finne en tilnærming til løsningen ved å gjenta en likeartet utregning igjen og igjen, inntil løsningen er god nok. En hver gjentaking av utregningen kalles eniterasjon.En velegnet metode vil gi en bedre tilnærming i hver iterasjon.

En iterasjon kan uttrykkes som enfølge{x_n} der hvert ledd er definert som en funksjon av de foregående leddene i følgen, dvs

$x_{n}=f(x_{n-1},x_{n-2},....,x_{0})\,$

Iterative metoder vil kreve en eller flerestartverdier,for å sette iterasjonene i gang. Som regel inngår en gjetning på løsningsverdien blant startverdiene.

En iterativ metode kan værekonvergentellerdivergent,tilsvarende som for generelle følger.

Eksempel: Fikspunktiterasjon

Fikspunktiterasjonkan brukes til å finne en rot i en ligning x = f(x). Metoden er basert på den enklerekursjonsregelen

$x_{n}=f(x_{n-1})\,$

.Metoden kan for eksempel brukes til å løse den følgendeandregradsligningen

$x^{2}-2x+0,75=0\,$

I dette enkle tilfellet er de løsningene kjent, fra teorien for andregradsligninger, nemmeligx= 0,5 ogx=1,5.Dersom vi ønsket å bruke fikspunktiterasjon til å løse ligningen, så kunne rekursjonsformelen skrives på formen

$2x_{n}=x_{n-1}^{2}+0,75\quad n=1,2,....$

Bruker vi startverdien x₀= 0,1 finner vi tilnærmingene

Iterasjon	$x_{n}$
1	0,38
2	0,4472
3	0,475..
4	0,488..
5	0,494..

Med startverdien x₀= 1,6 vil metoden divergere.

Selv om fikspunktiterasjon kan vises å konvergere for svært mange funksjoner f(x), så vil den vanligvis være en lite effektiv metode. Det eksisterer mange mer effektive iterative metoder for å finne røtter i ligninger. En viktig metode erNewtons metode.

Nøyaktighet

Numeriske beregninger vil være påvirket av en rekke feilkilder, og kartlegging av disse er viktig for å kunne kontrollere nøyaktigheten i resultatet.

• Avrundingsfeiler feil som skyldes at datamaskinen ikke kan operere med flere enn et gitt antall siffer i beregningene.IEEE 754er en teknisk standard for beregninger med flyttalsaritmetikk.

• Trunkeringsfeiler feil som skyldes at en uendelig prosess er blitt representert i algoritmen med et endelig antall steg.

• Diskretiseringsfeiler feil som skyldes at en kontinuerlig funksjon av en kontinuerlig variabel er blitt tilnærmet med et endelig antall funksjonsberegninger.

• Modellfeiler idealiseringer og forenklinger i den matematiske modellen, slik at denne ikke eksakt representerer fenomenet som studeres.

Numerisk stabilitet

Skal en numerisk algoritme være velegnet til praktisk bruk, så må den værenumerisk stabil.Dette vil den være dersom små feil som kan opptre underveis ikke påvirker sluttresultatet i nevneverdig grad. I en numerisk ustabil metode vil beregningsfeil eller feil i inngangsdata vokse over tid, og til slutt ødelegge sluttresultatet fullstendig. En slik ustabil metode sies også å væredårlig kondisjonert.

Både den problemformuleringen og løsningsalgoritmen kan hver for seg være dårlig kondisjonerte. Med en dårligkondisjonert problemstilling vil enhver algoritme feile.

Ifeilanalysevil en studere hvordan feil som opptrer underveis kan forplante seg i en beregningsfølge. Feilanalyse er en viktig del av vurderingen av en hver numerisk algoritme.

Underkategorier av numerisk analyse

Numerisk analyse kan deles opp i en lang rekke underkategorier. I studiet av numeriske algoritmer inngår

• Numerisk approksimasjonsteori
• Interpolasjon
• Numerisklineær algebra
• Numerisk løsning av ikke-lineære ligninger
• Numerisk løsning avdifferensialligninger
• Numeriskintegrasjon
• Numeriskoptimering

Historie

Babylonsk leirtavle med tilnærming til kvadratroten av to

Referanser til beregninger med tall finnes i mange av de eldste spor av menneskelig sivilisasjon. Enbabylonskleirtavle gir en tilnærming til kvadrattroten av to, lengden av en diagonal i enlikesidet trekantmed side lik 1. Babylonerne brukte etseksagesimalt tallsystem,det vil si et tallsystem basert på grunntallet 60. Tilnærmingen til kvadratroten av to er gitt som en sum av fire ledd:

$1+(24/60)+(51/60)^{2}+(10/60)^{3}=1,41421296...$

Dette er korrekt med omtrent seks siffer i vårt titallssystem. Tavlen er tidfestet til 1800-1600 f.Kr, og den befinner seg i dag iYale Babylon Collection.

Abacus i bruk. FraGregor Reisch:Margarita Philosophica, 1508

Den persiske matematikerenMuhammad ibn Mūsā al-Khwārizmī,født omkring 780 i dagensUsbekistan,ga mange bidrag til utvikling av matematikk. Et av læreverkene hans, i aritmetikk, bidro vesentlig til innføring avarabiske talli Europa. Fra den latiniserte formen av navnet hans stammer ordetalgoritme- brukt for å betegne en steg for steg prosedyre for å løse et matematisk problem.

Abakusen(kuleramma) var lenge et viktig hjelpemiddel for å utføre praktiske beregninger. Ved innføring avdesimalsystemetble behovet for dette hjelpemiddelet redusert. I Europa skjedde innføring av dette systemet gradvis fra 1300-tallet til slutten av 1600-tallet.

Logaritmerble utviklet av den skotske matematikerenJohn Napier(1550-1617), for å lette utføring av multiplikasjon, divisjon, potens og rot. Dette førte til at man trykte bøker med logaritmetabeller til hjelp i beregninger. Bøkene hadde gjerne også tabeller fortrigonometriskefunksjoner og annet.Regnestavener basert på bruk av logaritmer, og denne var i allmenn bruk blant ingeniører og vitenskapsmenn fram til 1970-tallet da digitale elektroniske verktøy somkalkulatorerog datamaskiner ble billige nok til allmenn bruk.

Isaac Newton(1643-1727) la grunnlaget for moderne matematikk og utviklet også mange metoder for tallberegninger. Hans beskrev metoden for å finne tilnærmede røtter i ligninger i verketDe analysi per aequationes numero terminorum infinitasfra 1669. Metoden går blir i dag ofte referert til somNewton-Raphsonsmetode, også oppkalt etter den engelske matematikerenJoseph Raphson(1648?-1715?).

Etter Newton bidro en rekke av de store matematikeren til utviklingen av numeriske metoder, med viktige bidrag avLeonhard Euler(1707-1783),Joseph Louis Lagrange(1736-1813) ogCarl Friedrich Gauss(1777-1855).Gausseliminasjoner en viktig numerisk metode for løsning av lineære ligningssystem. Denne metoden er en direkte metode som finner løsningen i et endelig antall steg, mensGauss-Seidel-metodener en alternativ iterativ metode. Gauss deler æren for den iterative metoden sammen med den tyske matematikerenPhilipp Ludwig von Seidel(1821-1896).

Rekonstruksjon av Schickards regnemaskin, opprinnelig kun skissert på papiret ca. 1624

På 1700-tallet ble det utviklet flere mekaniske regnemaskiner, blant annet avWilhelm Schickard(1592-1635),Blaise Pascal(1623-1662) ogGottfried Leibniz(1646-1716). Den engelske matematikerenCharles Babbage(1791-1871) er berømt for sine skisser av programmerbare regnemaskiner, og han kan regnes som «far» til dagens datamaskiner. Formålet med Babbages maskiner var å automatisere generering av logaritmetabeller, for å unngå de mange feilene som fulgte manuelle beregninger.

Etter Gauss var det liten utvikling innenfor numeriske metoder, helt fram til andre verdenskrig. Få matematikere var numerisk orientert, og numerisk analyse hadde et heller dårlig omdømme.Ved behov for regnekraft under den andre verdenskrigen brukte en fremdeles grupper av mennesker som sammen gjennomførte kompliserte beregninger, ved hjelp av papir og blyant, tabeller, regnestaver og mekaniske kalkulatorer. Det engelske ordet «computer» ble brukt for å omtale en person, og ikke en maskin.

John von Neumann, 1947

Under andre verdenskrigen varkryptografinaturlig nok et viktige fagområde. Den engelske matematikeren og kryptografenAlan Turing(1912-1954) ledet en periode arbeidet med å knekke tyske kodesystem, og som ledd i dette arbeidet bidro han vesentlig til utvikling av automatiske regnemaskiner. Enturingmaskiner en idealisert og formell beskrivelse av en datamaskin, samt hvilke beregninger eller oppgaver maskinen kan utføre.

Parallelt med framveksten av teknologi for programmerbare regnemaskiner økte også innsatsen innenfor numerisk analyse. Artikkelen «Numerical inverting of matrices of high order» avJohn von Neumann(1903-1957) ogHerman Goldstine(1913-2004), publisert i 1947, kan regnes som den første moderne publikasjon innenfor fagfeltet.Hovedemnet for artikkelen var Gausseliminasjon. Spesielt ble von Neumann en viktig pådriver for utvikling av numerisk analyse.

James H. Wilkinson(1919-1986) ga viktige bidrag til feilanalyse.

Moderne datateknologi har vært pådriver for en eksplosiv utvikling av numerisk analyse. Fagfeltet danner grunnlaget fornumerisk modellering,også kalt beregningsvitenskap. I dette fagfeltet studerer en hvordan en gitt problemstilling, i naturvitenskap, teknologi eller økonomi, kan bli gitt en matematisk formulering - som igjen kan danne grunnlaget for en numerisk beskrivelse av fenomenene.

Litteratur

• Germund Dahlquist, Åke Björck (1974).Numerical methods.New Jersey: Prentice-Hall Inc.ISBN0-13-627315-7.

• Michael L. Overton (2001).Numerical computing with IEEE floating point arithmetic.Philadelphia: Society of Industrial and Applied Mathematics.ISBN0-89871-571-7.