Numeeriset menetelmät

Tämän tekstin on tarkoitus toimia yhteenvetona Lapissa käydystä Numeeristen menetelmien kurssista. Tästä voi siis kertailla seuraavassa matematiikan yössä pidettävää koetta varten. Teksin on kirjoittanut Ville.

Teksti on valitettavasti hyvin niukka. Kirjoita rohkeasti selvityspyyntöjä epäselviin paikkoihin, lisään sitten materiaalia. -- Ville

Tekstiä saavat tietysti myös muut paikkailla ja lisäillä vapaasti.

Osaa nämä:

• Polynomien jakokulma
• Karsinointi
• Suhteellinen ja absoluuttinen virhe eri laskutoimituksissa
• 10-kantaisten lukujen muuntaminen kaksikantaisiksi ja kaksikantaisilla luvuilla peruslaskutoimitusten tekeminen (kertominen, jakaminen, yhteen- ja vähennyslasku)
• Liukuluvut ja niiden käytöstä aiheutuva virhe
• Funktion kulun tutkiminen derivoimalla, nollakohtien lukumäärä
• Yhtälön ratkaisu numeerisesti
  • Brute Force
  • Puolitushaku
  • Sekantti ja regula falsi
  • Kiintopisteiteraatio
  • Newtonin menetelmä
• Tarkkuuden osoitus

Polynomien jakokulma

Polunomeja voi jakaa jakokulmassa samoin kuin tavallisia lukuja. Samat potenssit asetetaan päällekkäin, mahdollisille puuttuville termeille jätetään tilaa. (Siis esimerkiksi $ x^5-1 $ kirjoitetaan niin, että x:n potensseille 1-4 on tilaa.)

Tässä esimerkisi jaetaan $ \frac{x^2-5x+6}{x-2} = x-3 $. En onnistunut valitettavasti piirtämään jakokulman viivoja.

		$ x $	$ -3 $
$ x-2 $	$ x^2 $	$ -5x $	$ + 6 $
	$ - (x^2 $	$ -2x ) $
		$ -(-3x $	$ +6 ) $
			0

Karsinointi

Polynomeista on syytä muistaa:

• n. asteen polynomilla on korkeintaan n nollakohtaa. (Paitsi nollapolynomilla P(x)=0, jolla on äärettömän monta nollakohtaa)

• Jos P(b) = 0, niin P(x) on jaollinen x-b:llä.

Näillä työkaluilla ratkomme kätevästi epäyhtälöitä.

Algoritmi polynomi- tai rationaaliepäyhtälön ratkaisuun:

• Siirrä kaikki tavara toiselle puolelle yhtälöä. Älä kerro tai jaa puolittain.
• Lavenna tarvittaessa samannimisiksi
• Nyt pitäisi olla tilanteessa P(x)>0, missä P on polynomi tai polynomien osamäärä.
• Kirjoita polynomi tulomuotoon. Jos kysessä on rationaalilauseke, muokkaa nimittäjää ja osoittajaa erikseen.
• Piirrä taulukko, josta näkyy kunkin tulontekijän merkki eri x:n arvoilla.
• Käytä tulon merkkisääntöä ja lue vastaus.

Kirjoita tähän HEP jos haluat esimerkin:

Virhe

Tietomme maailmasta (ja matematiikasta) on usein likimääräistä. Eroa todellisuuden ja arviomme välillä kutsutaan virheeksi:

Virhe = Oikea - Arvio

eli

Oikea = Arvio + Virhe

Tarkemmin ottaen edellämainittu virhe on absoluuttinen virhe.

Suhteellinen virhe määritellään:

Suhteellinen virhe = (Absoluuttinen virhe)/Oikea = (Oikea - Arvio)/Oikea

Koska oikeaa vastausta ei yleensä tiedetä, käytetään likimääräistystä

Suhteellinen virhe = Virhe / Arvio

Laskutoimituksissa virhe käyttäytyy seuraavasti:

• yhteen- ja vähennyslaskussa absoluuttisen virheen kokoluokka pysyy samana
• kerto- ja jakolaskussa suhteellisen virheen kokoluokka pysyy samana

(Tämän takia fysiikassa vastaukseen annetaan suunnilleen saman verran merkitseviä numeroita kuin lähtöarvoissa - fysiikan kaavoissa kun lähinnä kerrotaan)

Näiden nyrkkisääntöjen lisäksi tulee muistaa tärkeä asia:

Vähennyslaskussa suhteellinen virhe voi kasvaa todella suureksi! Vältä vähennyslaskua!

Esim: Vaa'an mukaan ukko painaa 98kg. Juotuaan pullon limonaatia hän painaa 99kg. Paljonko nestettä puollossa oli? 1kg on epätarkka vastaus, menetimme kokonaisen merkiksevän numeron.

Vielä pahempaa: 0.25895 m - 0.25899 m = -0.00004 m. Viidestä merkisevästä numerosta yhteen.

Parijärjestelmä

Vaihdetaan kotoisan kympin tilalle kantaluvuksemme kaksi. Laskento menee näin:

Parijärjestemässä	Sanotaan	Kymmenjärjestelmässä
1	yksi	1
10	pari	2
11	pariyksi	3
100	neli	4
101	neliyksi	5
110	nelipari	6
111	nelipariyksi	7
1000	kasi	8
10 000	parikasia	16
100 000	nelikasia	32
1000 000	kune	64

jne.

lähes kaikki tietokoneet käyttävät laskuissansa parijärjestelmää, sillä sen laskutoimitukset on helppo koodata.

Liukuluvut

Tietokoneet ja laskimet ovat äärellisen kokoisiä mötiköitä, joten ne voivat tallentaa muistiinsa vain äärellisen monta eri lukua. Näin ollen useimmat koneen suorittamat laskut ovat likiarvoisia.

Koneet tallentavat lukuja yleensä muodossa

$ m*k^e $

missä

• m on luku väliltä -1...1, nimeltään mantissa
• k on kantaluku (yleensä 2)
• e on kokonaisluku (plus tai miinus), nimeltään eksponentti

Tällaisia lukuja kutsutaan liukuluvuiksi (floating point numbers).

Koska mantissa ja eksponetti tallennetaan parijärjestelmän lukuina, mantissassa olevien numeroiden (bittien) määrä kertoo laskennan tarkkuuden. Eksponentin bittien lukumäärä ei ole niin kriittinen, koska yleensä emme tarvitse tavattoman pieniä tai suuria lukuja.

Esimerkki: mantissassa on vain neljä bittiä. Luku 5.4 tallentuu muodossa

$ 0.1011*10^{11} = 101.1 = 5.5 $

Luku siis pyöristyy lähimpään likulukuun. Tarkkuus riippuu bittien määrästä. Voit testata oman laskimesi bittien määrää tarkistamalla, millä n:n arvolla

$ (2^n+1)-2^n $

on laskimesi mielestä nolla.

Yhtälön ratkaisu

Yhtälön numeerinen ratkaisu käy näin:

• Selvitä, kuinka monta ratkaisua yhtälöllä on
• Etsi kaikkien ratkaisujen likiarvot haluamallasi menetelmällä ja tarkkuudella
• Tarkista, että likiarvot ovat oikein (halutun tarkkuuden rajoissa)

Älä unohda.

Ratkaisujen lukumäärä

Näin selvität, kuinka monta ratkaisua yhtälöllä on:

• Kirjoita yhtälö muotoon f(x) = 0. Tämän voi tehdä äärettömän monella eri tavalla, valitse jatkoa ajatellen helpoin.
• Tutki, kuinka monta nollakohtaa funktiolla f(x) on
• Jos edellinen ei suoraan onnistu, laadi kulkukaavio
• Jos edellinen ei suoraan onnistu, derivoi f(x) ja tutki derivaatan merkkiä (f' positiivinen, niin f kasvava; f' negatiivinen, niin f vähenevä)

Tässä auttaa, jos osaa derivoida.

Eri iteraatiot

Kaikki nämä vaativat jatkuvan funktion toimiakseen lainkaan. Jos funktiolla on epäjatkuvuuskohta, tutki jokainen jatkuva pätkä erikseen.

Brute Force

Laske tiheään funktion arvoja ja tarkkaile, milloin arvo positiivinen ja milloin negatiivinen. Positiivisen ja negatiivisen arvon välistä löytyy nollakohta.

Menetelmä on laskennallisesti raskas. Varsinkin, jos aikoo tutkia koko reaaliakselin :)

Puolitushaku

Lähdetään siitä, että f(a) > 0 ja f(b) < 0. Nyt siis välillä [a,b] on nollakohta. Lasketaan f:n arvo välin puolivälissä. Valitaan uudeksi väliksi se puolikas, jonka päissä f saa erimerkkiset arvot. Toistetaan.

Joka askeleella välin pituus puolittuu, joten myös virhe puolittuu. Jos välin pituus on alussa 1, kymmenen askeleen jälkeen virhe on enää $ 1/2^{10} $ eli noin $ 10^{-6} $. Vastauksessa on silloin jo viisi desimaalia oikein.

Sekantti

Lähtökohta: valitaan kaksi alkuarvoa, $ x_1 $ ja $ x_2 $. Piirretään pisteiden $ (x_1, f(x_1)) $ ja $ (x_2,f(x_2)) $ kautta suora. Selvitetään, missä kyseinen suora leikkaa x-akselin. Tämä on uusi arvaus $ x_3 $.

Homma toistetaan alkuarvoilla $ x_3 $ ja toinen vanhoista. Vanhoista pisteistä valitaan joko

• Järjestysnumeroltaan suurempi (kutakin pistettä käytetään siis kahdesti). Tämä on varsinainen sekantti
• Uuden luvun kanssa erimerkkinen. Tämä on nimeltään regula falsi. (Alunperinkin on syytä olla erimerkkiset $ x_1 $ ja $ x_2 $, jotta valinta voidaan tehdä.)

Kaava seuraavan arvon laskemiseksi on

$ x_3 = x_1-f(x_1)*\frac{x_2-x_1}{f(x_2)-f(x_1)} $

Kaavan voi palauttaa mieleen piirtämällä kuvan ja ratkaisemalla nollakohdan $ x_3 $.

Newton

Newton on sekantin hienostuneempi versio.

Graafisesti homma menee näin:

• valitaan alkuarvo $ x_1 $.
• piirretään funktiolle tangentti pisteeseen $ (x_1,f(x_1)) $
• valitaan tangentin nollakohta seuraavan askeleen alkuarvoksi

Algebrallisesti asiaa voidaan ajatella niin, että

$ f'(x_1) \approx \frac{f(x)-f(x_1)}{x-x_1} $

Kun nyt halutaan, että $ f(x)=0 $, saadaan ratkaistua

$ x = x_1 - \frac{f(x_1)}{f'(x_1)} $

Yleinen iterointikaava on siis

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

Newtonin iteraatio suppenee alueella, jossa

$ |\frac{f*f''}{(f')^2}|<1 $

Tämä todistetaan lähtien kiintopisteiteraation vastaavasta kaavasta.

Kiintopiste

Kiintopisteiteraatio poikeaa muista tässä esitellyistä siinä, että yhtälö muokataan muotoon

$ x = g(x) $.

Iterointikaavana käytetään

$ x_{n+1}=g(x_n) $.

Kiintopisteiteraatio suppenee alueella, jossa

$ |g'(x)|<1 $.

Suppeneminen riippuu siis paljon siitä, miten alkuperäisen yhtälön kirjoittaa haluttuun muotoon. Kannattaa kokeilla eri muotoja.

Esimerkki: Yhtälö $ x^3-2x^2 -x+1 $ voidaan kirjoittaa mm. muotoihin

$ x = \sqrt[3]{2x^2+x-1} $

$ x = x^3-2x^2+1 $

$ x = -x^4 +2x^3+x^2 $ jne.

Tarkkuden osoitus

Kun laskimesta on saatu jollakin tavalla arvio nollakohdaksi, se pitää tarkistaa. Tämä on tärkeää, koska iteraatio saattaa supeta arvoon, joka ei ole alkuperäisen yhtälön ratkaisu.

Näin se toimii:

Halutaan selvittää yhtälön $ f(x)=0 $ ratkaisu neljän merkitsevän numeron tarkkuudella.

Ollaan saatu laskimesta $ x= 0.5426738 $. Arvauksemme neljän merkitsevän numeron tarkkuudella on siis $ x = 0.5427 $

Testataan funktion arvot oletetun nollakohdan lähistöltä:

$ f(0.54274) $ ja $ f(0.54266) $

Jos arvot ovat erimerkkiset, välillä [0.54274, 0.54266] on nollakohta ja homma kotona. Jos arvot ovat samanmerkkiset, jokin on voinut mennä pieleen - tarkista laskut.

Tässä valittiin arvot $ 0.5427 \pm 0.00004 $, koska välin [0.54274, 0.54266] kaikki arvot pyöristyvät arvoon 0.5427.

Huomatus: suomeksi desimaalipilkku on todellakin pilkku, ei piste. Tässä käytin kuitenkin pistettä, koska anglisissa maissa tehdyt laskimemme käyttävät niitä.

Linkkejä

Joitakin poimintoja Wikipediasta:

Wikipedian artikkeli aiheesta "Numeeriset menetelmät", ei kovin hyvä tarpeisiimme

Newtonin metodista englanniksi

Hyvä pätkä liukuluvuista (englanniksi)