Tie koodariksi

Kirjaudu sisään

MAA11 Algoritmit ja lukuteoria

★
Kieli:

Liukuluvuista

Matematiikka sisältää äärettömyyksiä, mutta tietokone on äärellinen laite. Kun tietokone tallentaa lukuja, ne joudutaankin useimmiten pyöristämään.

Kokonaisluvuilla (tyyppi int) laskiessaan Python laskee tarkasti, jos koneen muisti vain riittää. Esimerkiksi luvun $2^{10000}$ laskeminen komennolla 2**10000 ei tuota ongelmia. Desimaalilukujen kanssa ollaan kuitenkin pulassa, sillä esimerkiksi $\sqrt{2}=1{,}4142...$ sisältää jo äärettömästi desimaaleja, eivätkä ne voi mahtua koneen äärelliseen muistiin.

Tyypillinen tapa tallentaa desimaalilukuja tietokoneella on liukuluku (eng. floating point number, tyyppi float). Liukuluvussa desimaalipilkku tulee ensimmäisen merkitsevän numeron jälkeen, eli esimerkiksi luku $12345$ merkittäisiin $$12345 = 1{,}2345\cdot 10^4.$$ Kerrointa $1{,}2345$ kutsutaan nimellä mantissa. Tietokoneen rajat tulevat vastaan siinä, että mantissassa on käytössä vain rajallinen määrä merkitseviä numeroita. Siksi esimerkiksi luku $$1/3 = 0{,}33333{...} = 3{,}3333{...} \cdot 10^{-1}$$ ei voi tallentua tietokoneelle tarkkana, vaan se pyöristetään lähimpään käytössä olevaan lukuun. Lisäksi käytössä on vain rajallisen kokoisia eksponentteja, joten mielivaltaisen suuria lukuja ei voi esittää.

Itse asiassa Python tallentaa luvut 2-järjestelmässä eli binäärilukuina. Käytössä on 53 merkitsevää numeroa 2-järjestelmässä, mikä tarkoittaa 10-järjestelmässä noin $15$ merkitsevää numeroa. Suurin mahdollinen kerroin on $2^{2023}$ ja pienin $2^{-2022}$. Tästä seuraa, että tarkkana tallentuvat vain ne luvut, joiden esitys binäärilukuna on päättyvä. Esimerkiksi kymmenjärjestelmän luvun $0{,}2$ binääriesitys on päättymätön: $0{,}0011001100110011{...}$ Kun tämän pyöristää $53$ merkitsevään numeroon binäärijärjestelmässä, tuloksena on luku, joka vastaa kymmenjärjestelmässä lukua $$0{,}20000000000000001110223024625156{...}$$

Oleellisinta tässä kaikessa on siis se, että desimaaliluvuilla laskettaessa kaikki desimaalit 16. merkitsevästä numerosta lähtien ovat täysin epäluotettavia.

Liukuluvuista Pythonissa löydät lisätietoja Pythonin dokumentaatiosta ja Pythonin käyttämästä liukulukustandardista Wikipediasta.

Tehtävä 1 Ratkaisematon

Koska desimaaliluvut pyöristyvät aina lähimpään liukulukuun, desimaalilukujen vertailut operaattorilla == on huono idea. Kirjoita ohjelma, joka tulostaa peräkkäisille riveille lausekkeiden totuusarvot sekä näiden alle laskujen tulokset.

Kirjoita ohjelma tähän:

Tehtävä 2 Ratkaisematon

Kuten edellisessä tehtävässä nähtiin, desimaalilukuja ei kannata vertailla operaattorilla ==. Parempi tapa lukujen $a$ ja $b$ yhtäsuuruuden testaamiseen on tyytyä tarkistamaan, että $|a-b|$ on riittävän pieni, missä "riittävän pieni" tarkoittaa "monta kokoluokkaa pienempi kuin suurempi luvuista $|a|$ ja $|b|$".

Esimerkiksi voitaisiin tarkistaa, onko $x = 2{,}2360689774$ hyvä likiarvo luvulle $\sqrt{5}$ tutkimalla, päteekö $\left|x-\sqrt{5}\right|<10^{-9}$. Tee koodi, joka tulostaa Likiarvo on oikein! tai Likiarvo on väärin! sen mukaan, toteutuuko tämä ehto vai ei.

Neliöjuuren saa math-paketin funktiolla math.sqrt ja itseisarvon funktiolla abs.

Kirjoita ohjelma tähän:

Tehtävä 3 Ratkaisematon

Matemaattisesti lausekkeen $10^n+1-10^n$ arvo on aina $1$. Kokonaisluvuilla laskettaessa Python on samaa mieltä, mutta jos Pythonin pakottaa käyttämään liukukuja vaikkapa tapauksessa $n=50$, lauseke 10.0**50 + 1 - 10.0**50 antaa tulokseksi 0. Syynä on se, että $10^{50}+1 \approx 10^{50}$, ellei käytössä ole 51 merkitsevää numeroa.

Kirjoita koodi, joka tulostaa peräkkäisille riveille lausekkeen 10.0**n+1-10.0**n arvon, kun $n = 1, 2, 3, \ldots, 20$. Muista kirjoittaa 10.0, ei 10. Mitä huomaat?

Kirjoita ohjelma tähän:

Edellisessä tehtävässä huomattiin, että vähennyslasku on vaarallinen. Vaikka luvuissa $10.0^{50}+1$ ja $10.0^{50}$ on molemmissa runsaasti merkitseviä numeroita oikein, vähennyslaskussa $10.0^{50}+1- 10.0^{50} \approx 0$ jäljellä ei ole yhtään merkitsevää numeroa! Sama ongelma tulee vastaan toisen asteen yhtälöitä ratkaistaessa.

Toisen asteen yhtälö

Toisen asteen yhtälön $ax^2+bx+c=0$ reaaliset ratkaisut saadaan tunnetusti kaavasta $$x = \dfrac{-b\pm\sqrt{b^2-4ac}}{2a}.$$ Likiarvoilla laskettaessa tämä kaava ei valitettavasti aina toimi. Tarkastellaan vaikkapa yhtälöä $$3x^2+10^{20}x+5=0.$$ Python laskee sujuvasti: \begin{align*} x_1 &= \frac{-10^{20} +\sqrt{\left(10^{20} \right)^2-4\cdot 3\cdot 5}}{2\cdot 3}\approx 0{,}000000000000000 \\ &\text{ja} \\ x_2 &= \frac{-10^{20} -\sqrt{\left(10^{20} \right)^2-4\cdot 3\cdot 5}}{2\cdot 3}\approx -3{,}333333333333333\cdot 10^{-19} \end{align*} Tässä $x_1$ ei selvästikään voi olla oikein, eihän $x = 0$ ole yhtälön ratkaisu! Oikea likiarvo on $x_1 \approx -5{,}000\cdot 10^{-20}$. Miksi laskeminen siis epäonnistuu?

Ongelma johtuu siitä, että $b^2$ on paljon suurempi kuin $4ac$. Tällöin pätee $$\sqrt{b^2-4ac} \approx \sqrt{b^2-0} = |b|.$$ Kun merkitsevät numerot loppuvat kesken, lukujen $\sqrt{b^2-4ac}$ ja $b$ likiarvo voi siis olla sama! Ratkaisukaava päätyy muotoon $$x_1\approx \frac{-b + |b|}{2a} \quad \text{ja} \quad x_2\approx \frac{-b - |b|}{2a},$$ jolloin positiivisilla luvuilla $b$ saadaan $x_1\approx 0$ ja vastaavasti negatiivisella luvulla $b$ saadaan $x_2 \approx 0$, eikä vastauksessa ei ole yhtään merkitsevää numeroa oikein. Vähennyslasku on vaarallinen!

Korjattu toisen asteen yhtälön ratkaisukaava

Edellä esitetty ongelma yhtälön $ax^2+bx+c=0$ ratkaisukaavassa voidaan korjata välttämällä vähennyslaskua ja laskemalla ensin yksi juuri kaavalla \begin{align*} x_1 &= \frac{-b-\sqrt{b^2-4ac}}{2a}, \quad \text{jos} \quad b \geq 0 \\ \text{tai}\\ x_1 &= \frac{-b+\sqrt{b^2-4ac}}{2a}, \quad \text{jos} \quad b < 0. \end{align*} Toinen juuri puolestaan lasketaan kaavalla $$x_2 = \frac{c}{ax_1},$$ ja näin yhtälön kumpikin ratkaisu saatiin selvitettyä ilman samaa kokoluokkaa olevien lukujen vähennyslaskua.

Miksi kaava $x_2 =\dfrac{c}{ax_1}$ toimii?

Jos toisen asteen polynomilla $P(x)=ax^2+bx+c$ on nollakohdat $x_1$ ja $x_2$, polynomin voi jakaa tekijöihin: $$ax^2+bx+c=a(x-x_1)(x-x_2).$$ Kun tekijämuotoisen polynomin sulut kerrotaan auki, saadaan $$a(x-x_1)(x-x_2)=a(x^2 -x_1x-x_2x+x_1x_2) = ax^2 \underbrace{-a(x_1+x_2)}_{=b}x+\underbrace{ax_1x_2}_{=c}.$$ Vertaamalla muotoon $ax^2+bx+c$ nähdään, että $$b = -a(x_1+x_2) \quad \text{ja} \quad c =ax_1x_2,$$ joista jälkimmäisestä saadaan $$ x_2 = \frac{c}{ax_1}.$$

Tehtävä 4 Ratkaisematon

Toteuta koodi, joka asettaa muuttujille $a$, $b$ ja $c$ arvot ja tulostaa toisen asteen yhtälön $ax^2+bx+c=0$ reaalilukuratkaisut.

Koodin tulee toimia myös yhtälöille, joissa $b^2$ on paljon suurempi kuin $4ac$, esimerkiksi edellä esitetylle yhtälölle $3x^2+10^{20}x+5=0$ sekä yhtälölle $3x^2-10^{20}x+5=0$.

Voit halutessasi toteuttaa myös tarkistuksen sille, onko reaalisia ratkaisuja ylipäänsä olemassa.

Tätä tehtävää ei arvostella automaattisesti.

Kirjoita ohjelma tähän: