Tie koodariksi

MAA11 Algoritmer och talteori

Språk:

Flyttal

Matematik innehåller oändligheter, men datorn är en ändlig maskin. När datorn sparar tal måste de vanligtvis avrundas.

När det räknar med heltal (int), räknar Python exakt, om maskinens minne räcker till. Till exempel kan talet $2^{10000}$ beräknas med kommandot 2**10000 utan problem. Med decimaltal får man emellertid problem, eftersom till exempel $\sqrt{2}=1{,}4142...$ redan innehåller oändligt med decimaler och inte ryms i datorns ändliga minne.

Ett typiskt sätt att spara decimaltal på datorn är flyttal (eng. floating point number, float). I ett flyttal kommer decimalkommat efter den första värdesiffran, dvs. till exempel skulle talet $12345$ betecknas som $$12345 = 1{,}2345\cdot 10^4.$$ Koefficienten $1{,}2345$ kallas mantissa. Datorns gränser kommer emot eftersom mantissan enbart har tillgång till ett begränsat antal siffror. Därför kan till exempel talet $$1/3 = 0{,}33333... = 3{,}3333...\cdot 10^{-1}$$ inte sparas exakt, utan det avrundas till närmaste tillgängliga tal. Därtill används enbart exponenter av begränsad storlek, så godtyckligt stora tal kan inte presenteras.

I själva verket sparar Python talen som binära tal. Det finns 53 värdesiffror i det binära talsystemet, vilket innebär att det finns cirka $15$ värdesiffror i det decimala talsystemet. Den största möjliga koefficienten är $2^{2023}$ och den minsta är $2^{-2022}$. Härav följer att endast de tal vars presentation som binära tal är ändlig sparas exakt. Till exempel är den binära talrepresentationen hos decimalsystemets tal $0,2$ oändlig: $0{,}0011001100110011...$ När denna avrundas till $53$ värdesiffror i den binära talsystemet, är resultatet ett tal, som motsvarar talet $$0{,}20000000000000001110223024625156...$$ i decimalsystemet.

Det väsentliga i allt detta är alltså att när man räknar med decimaltal är alla decimaler från och med 16 värdesiffror helt opålitliga.

Mer information om flyttal i Python hittar du i Pythons dokumentation och Pythons flyttalsstandard i Wikipedia.


Uppgift 1 Olöst

Eftersom decimaltalen alltid avrundas till närmaste flyttal, är det en dålig idé att jämföra decimaltal med operatorn ==. Skriv ett program som matar ut sanningsvärdena för uttrycken på raderna efter varandra samt under dem resultaten av beräkningarna.

Skriv ditt program här:


Uppgift 2 Olöst

Såsom vi såg i föregående uppgift lönar det sig inte att jämföra decimaltal med operatorn ==. Ett bättre sätt att testa likheten hos talen $a$ och $b$ är att nöja sig med att kontrollera att $|a-b|$ är tillräckligt litet, där ”tillräckligt litet” betyder ”många storleksklasser mindre än det större av talen $|a|$ och $|b|$”.

Till exempel kan vi kontrollera om $x = 2{,}2360689774$ är ett bra närmevärde för talet $\sqrt{5}$ genom att kontrollera, om $\left|x-\sqrt{5}\right|<10^{-9}$ gäller. Gör en kod, som skriver ut Närmevärdet är korrekt! eller Närmevärdet är fel! i enlighet med om detta villkor uppfylls eller inte.

Kvadratroten fås med math-paketets funktion math.sqrt och absoluta värdet med funktionen abs.

Skriv ditt program här:


Uppgift 3 Olöst

Matematiskt sett är värdet för uttrycket $10^n+1-10^n$ alltid $1$. När man räknar med heltal är Python av samma åsikt, men om man tvingar Python att använda flyttal exempelvis i fallet $n=50$, ger uttrycket 10.0**50 + 1 - 10.0**50 resultatet 0. Orsaken är att $10^{50}+1 \approx 10^{50}$, om man inte använder 51 värdesiffror.

Skriv en kod som på raderna efter varandra skriver ut värdet för uttrycket 10.0**n+1-10.0**n när $n = 1, 2, 3, \ldots, 20$. Kom ihåg att skriva 10.0, inte 10. Vad upptäcker du?

Skriv ditt program här:


I föregående uppgift upptäckte vi att subtraktion är farligt. Trots att talen $10.0^{50}+1$ och $10.0^{50}$ båda har gott om värdesiffror, vid subtraktion $10.0^{50}+1- 10.0^{50} \approx 0$ finns inga värdesiffror kvar! Samma problem kommer emot när man löser andragradsekvationer.

Andragradsekvation

Reella resultat för andragradsekvationen $ax^2+bx+c=0$ fås som bekant med formeln $$x = \dfrac{-b\pm\sqrt{b^2-4ac}}{2a}.$$ När man räknar med närmevärden fungerar denna formel tyvärr inte alltid. Vi kan exempelvis kontrollera ekvationen $$3x^2+10^{20}x+5=0.$$ Python räknar smidigt: \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{och} \\ 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*} Här kan $x_1$ helt klart inte vara rätt, $x = 0$ är inte lösningen på ekvationen! Det korrekta närmevärdet är $x_1 \approx -5{,}000\cdot 10^{-20}$. Varför misslyckas alltså beräkningen?

Problemet beror på att $b^2$ är mycket större än $4ac$. Då gäller $$\sqrt{b^2-4ac} \approx \sqrt{b^2-0} = |b|.$$ När värdesiffrorna tar slut kan närmevärdet för talen $\sqrt{b^2-4ac}$ och $b$ alltså vara samma! Lösningsformeln slutar i formen $$x_1\approx \frac{-b + |b|}{2a} \quad \text{och} \quad x_2\approx \frac{-b - |b|}{2a},$$ varpå man får $x_1\approx 0$ med de positiva talen $b$ och motsvarande får man $x_2 \approx 0$ med det negativa talet $b$, och inga värdetal är korrekta i svaret. Subtraktion är farligt!

Korrigerad lösningsformel för andragradsekvation

Det tidigare presenterade problemet i lösningsformeln för ekvationen $ax^2+bx+c=0$ kan korrigeras genom att undvika subtraktion och först räkna en rot med ekvationen \begin{align*} x_1 &= \frac{-b-\sqrt{b^2-4ac}}{2a}, \quad \text{och} \quad b \geq 0 \\ \text{eller}\\ x_1 &= \frac{-b+\sqrt{b^2-4ac}}{2a}, \quad \text{om} \quad b < 0. \end{align*} Den andra roten däremot räknas med formeln $$x_2 = \frac{c}{ax_1},$$ och på så sätt kan ekvationens båda lösningar redas ut utan subtraktion av tal i samma storleksklass.

Varför fungerar formeln $x_2 =\dfrac{c}{ax_1}$?

Om andragradspolynomet $P(x)=ax^2+bx+c$ har nollpunkterna $x_1$ och $x_2$, kan polynomet delas upp i faktorer: $$ax^2+bx+c=a(x-x_1)(x-x_2).$$ När polynomets parenteser multipliceras får man $$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}.$$ Genom att jämföra med formen $ax^2+bx+c$ ser man att $$b = -a(x_1+x_2) \quad \text{och} \quad c =ax_1x_2,$$ varav den senare ger $$ x_2 = \frac{c}{ax_1}.$$

Uppgift 4 Olöst

Gör en kod som ger variablerna $a$, $b$ och $c$ värden och skriver ut reella lösningar till andragradsekvationen $ax^2+bx+c=0$.

Koden ska även fungera för ekvationer där $b^2$ är mycket större än $4ac$, till exempel den tidigare presenterade ekvationen $3x^2+10^{20}x+5=0$ samt ekvationen $3x^2-10^{20}x+5=0$.

Om du vill kan du även kontrollera om det över huvud taget finns reella lösningar.

Denna uppgift bedöms inte automatiskt.

Skriv ditt program här: