1. Inngangur

He was determined to discover the underlying logic behind the universe. Which was going to be hard, because there wasn’t one.

- Terry Pratchett, Mort

1.1. Hvað er töluleg greining?

1.1.1. Tilraun að svari

• Fagið töluleg greining snýst um að búa til, greina og forrita aðferðir til þess að nálga á lausnum á stærðfræðilegum verkefnum.

• Aðferðirnar eru settar fram með reikniritum sem síðan eru forrituð og það þarf góðan skilning á eiginleikum lausnanna sem verið er að nálga til þess að geta greint hvernig forritin munu virka.

• Greining á reikniritum er aðallega fólgin í skekkjumati og mati á þeim aðgerðafjölda sem þarf til þess að ná að nálga lausn með fyrirfram gefinni nákvæmni, þ.e. hagkvæmni og nákvæmni reikniritsins.

• Líkanagerð í raunvísindum og verkfræði felur yfirleitt í sér eftirfarandi skref:

  1. Greina kerfið sem um ræðir

  2. Smíða líkan sem útskýrir hvernig kerfið hegðar sér, þó yfirleitt með töluverðum einföldunum.

  3. Herma kerfið í tölvu eins vel og hægt er. Hér þarf að ná ásættanlegri námkvæmni á þeim tíma sem útreikningar mega taka.

  4. Túlka niðurstöðurnar og bera saman við upphaflega kerfið.

  Töluleg greining kemur mikið við sögu í lið 3. og einnig í lið 4.

1.2. Dæmi: Eldflaug

Gerum ráð fyrir að við höfum eftirfarandi eldflaug undir höndum:

• Eldsneytið dugir í 18 sek., þ.e. $t\in [0,18]$.

• Loftmótstaðan er $d=0.1v^2$, þar sem $v(t)$ er hraðinn á tíma $t$.

• Krafturinn sem knýr flaugina er $T=5000$ N.

• Massi eldsneytisins er $m=180-10t$ kg.

• Massi flaugarinnar er $M = 120 + m = 300 - 10t$ kg.

Spurningin er: Í hvaða hæð er eldflaugin þegar eldsneytið klárast?

Úr öðru lögmáli Newtons fæst að $F = (Mv)'$. Kraftarnir sem verka á eldflaugina er $T$ upp á við og loftmótstaðan og þyngdarkrafturinn niður á við. Þannig fæst

$$(Mv)' = F = T - Mg - d$$

það er

$$M'v + Mv' = T - Mg -d.$$

Þetta jafngildir því að

$$v' = \frac{T-Mg-d-M'v}{M} = \frac{5000-(300-10t)g-0,1v^2+10v}{300-10t}, \label{eldflaug}$$

og upphafsskilyrðin eru $v(0) =0$.

Þar sem $h' = v$, þá er hæðin á tíma $t$ gefin með $h(t) =\int_0^t v(s)\, ds$. Þegar eldsneytið klárast þá er hæðin $h(18) = \int_0^{18} v(s)\, ds$.

Verkefnið er því að finna $v$, og reikna svo heildið.

Diffurjafnan hér að ofan er ólínuleg og ekki aðgreinanleg þannig að við getum ekki vænst þess finna lausn með þeim aðferðum sem við höfum þegar lært. Eins er ekki víst að við getum auðveldlega fundið stofnfall $h$ fyrir $v$ til þess að reikna heildið, jafnvel þótt við hefðum $v$.

Hins vegar getum við leyst diffurjöfnuna tölulega með aðferðunum úr kafla 6, og heildið reiknum við svo tölulega með aðferðunum úr kafla 5.

1.3. Samleitni runa

1.3.1. Nokkur atriði um samleitni runa

Mörg reiknirit til nálgunar á einhverri rauntölu eru hönnuð þannig að reiknuð er runa $x_0,x_1,x_2,\dots$ sem á að nálgast lausnina okkar.

1.3.2. Skilgreining: Samleitni

Rauntalnaruna $(x_n)$ er sögð vera samleitin (e. convergent) að markgildinu $r$ ef um sérhvert $\varepsilon>0$ gildir að til er $N>0$ þannig að

$$|x_n-r|<\varepsilon, \qquad \text{ ef } \quad n\geq N.$$

Þetta er táknað annað hvort með

$$\lim_{n\to \infty}x_n=r \qquad \text{ eða } \qquad x_n\to r \text{ ef } n\to \infty.$$

Ef runan $(x_n)$ er samleitin að markgildinu $r$ þá segjum við einnig að hún stefni á $r$.

Hugsum okkur nú að $(x_n)$ sé gefin runa sem stefnir á $r$ og táknum skekkjuna með $e_n=r-x_n$.

Runan er sögð vera línulega samleitin (e. linear convergence) ef til er $\lambda\in ]0,1[$ þannig að

$$\lim_{n\to \infty}\dfrac{|e_{n+1}|}{|e_n|}=\lambda,$$

ofurlínulega samleitin (e. superlinear convergence), ef

$$\lim_{n\to \infty}\dfrac{|e_{n+1}|}{|e_n|}=0,$$

ferningssamleitin (e. quadratic convergence) ef til er $\lambda>0$ þannig að

$$\lim_{n\to \infty}\dfrac{|e_{n+1}|}{|e_n|^2}=\lambda,$$

og samleitin af stigi $\alpha$ (e. convergence of order $\alpha$), þar sem $\alpha> 1$, ef til er $\lambda>0$ þannig að

$$\lim_{n\to \infty}\dfrac{|e_{n+1}|}{|e_n|^\alpha}=\lambda.$$

Athugasemd

Runa er ofurlínulega samleitin ef hún er samleitin af stigi $\alpha>1$.

Ferningssamleitin runa er samleitin af stigi 2 þannig að hún er einnig ofurlínulega samleitin.

1.3.3. Skilgreining

Oft eru notuð veikari hugtök til þess að lýsa samleitni runa (t.d. ef við getum ekki fundið $\lambda$ og $\alpha$ nákvæmlega).

Þannig segjum við að runan $(x_n)$ sé að minnsta kosti línulega samleitin ef til er $\lambda\in ]0,1[$ og $N >0$ þannig að

$$|e_{n+1}|\leq \lambda |e_n|, \qquad n\geq N,$$

ef til er $\lambda>0$ og $N>0$ þannig að

$$|e_{n+1}|\leq \lambda |e_n|^2, \qquad n\geq N,$$

og að minnsta kosti samleitin af stigi $\alpha$, þar sem $\alpha> 1$, ef til eru $\lambda>0$ og $N>0$ þannig að

$$|e_{n+1}|\leq \lambda |e_n|^\alpha, \qquad n\geq N.$$

1.4. Setning Taylors

Sometimes it’s better to light a flamethrower than curse the darkness. - Terry Pratchett, Men at Arms: The Play

1.4.1. Ritháttur fyrir diffranleg föll

Látum nú $f : I \to {\mathbb C}$ vera fall á bili $I$ sem tekur gildi í tvinntölunum. Ef $f$ er deildanlegt í sérhverjum punkti í $I$, þá táknum við afleiðuna með $f'$. Ef $f'$ er deildanlegt í sérhverjum punkti í $I$, þá táknum við aðra afleiðu $f$ með $f''$, og svo framvegis.

Við skilgreinum með þrepun $f^{(k)}$ fyrir $k = 0,1,2, \ldots$ þannig að $f^{(0)} = f$ og ef $f^{(k-1)}$ er deildanlegt í sérhverjum punkti í $I$, þá er $f^{(k)} = (f^{(k-1)})'$.

Við látum $C^{k}(I)$ tákna línulega rúmið sem samanstendur af öllum föllum $f : I \to {\mathbb C}$ þannig að $f', \ldots, f^{(k)}$ eru til í sérhverjum punkti í $I$ og $f^{(k)}$ er samfellt fall á $I$.

1.4.2. Nálgun með Taylor-margliðu

Ef $a \in I$, $m$ er jákvæð heiltala og $f \in C^{m}(I)$, þá nefnist margliðan

$$p(x) = f(a) + f'(a)(x-a) + \ldots + \frac{f^{(m)}(a)}{m!}(x-a)^m$$

Taylor-margliða fallsins $f$ í punktinum $a$ af stigi $m$, og er stundum táknuð með $T_m f(x;a)$.

Athugið að stig margliðunnar $p$ er minna eða jafnt og $m$.

1.4.3. Setning Taylors

Látum $I \subseteq {\mathbb R}$ vera bil, $f : I \to {\mathbb C}$ vera fall, $m \geq 0$ vera heiltölu og gerum ráð fyrir að $f \in C^m(I)$ og að $f^{(m+1)}(x)$ sé til í sérhverjum innri punkti bilsins $I$. Þá er til punktur $\xi$ á milli $a$ og $x$ þannig að

$$f(x) - T_mf(x;a)= \frac{f^{(m+1)}(\xi)}{(m+1)!}(x-a)^{m+1}.$$

Hægri hliðin er oft táknuð $R_m(x)$.

Athugasemd

Þetta þýðir að skekkjan í því að nálga fallið $f(x)$ með Taylor-margliðu af stigi $m$ hagar sér eins og $(x-a)^{m+1}$.

1.4.4. Viðbót

Ef $f^{(m+1)}$ er samfellt á lokaða bilinu með endapunkta $a$ og $x$, þá er

$$\begin{split}\begin{aligned} R_m(x) &= f(x) - T_mf(x;a) \\ &= \int\limits_a^x \frac{(x-t)^m}{m!}f^{(m+1)}(t) dt \notag \\ &= (x-a)^{m+1} \int\limits_0^1 \frac{(1-s)^m}{m!} f^{(m+1)}(a + s(x-a)) ds. \end{aligned}\end{split}$$

1.4.5. Sýnidæmi: Nálgun á fallgildum $x-\sin x$

Vitum að $x \approx \sin x$ ef $x$ er lítið. Tökum $x=0.1$ og hugsum okkur að við séum að reikna á vél með 8 stafa nákvæmni. Hún gefur

$$\sin 0.1 = 0.099833417$$

Af því leiðir

$$0.1 - \sin 0.1 = 1.66583\cdot 10^{-4}$$

Við höfum tapað tveimur markverðum stöfum í nákvæmni.

Ef við notum Taylor-nálgunina fyrir $\sin(x)$,

$$\sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} \cdots$$

og tökum fyrstu þrjá liðina, þ.e. skoðum 6. stigs Taylor-margliðu fallsins.

$x-\sin(x)$ er þá u.þ.b.

$$x - \left(x - \frac{x^3}{3!} + \frac{x^5}{5!}\right) = \frac{x^3}{3!} - \frac{x^5}{5!}.$$

Fallgildið er þá

$$\frac {0.1^3}{3!} - \frac{0.1^5}{5!} = 1.6658334 \cdot 10^{-4}.$$

Skekkjan er gefin með

$$|R_6(0.1)| = \left|\frac{\sin^{(7)}(\xi)}{7!}0.1^7\right| = \left|\frac{-\cos(\xi)}{7!}0.1^7\right| \leq \frac{1}{7!}0.1^7 < 0.2\cdot 10^{-10}.$$

Sem þýðir að allir 8 stafir reiknivélarinnar eru markverðir, þ.e. allir stafir $1.6658334 \cdot 10^{-4}$ eru réttir.

$\sin^{(7)}$ hér að ofan táknar 7. afleiðu $\sin$, sem er $-\cos$.

Ef við tökum $x = 0.01$ er þetta enn greinilegra. Reiknivélin gefur

$$\sin(0.01) = 0.0099998333$$

Þannig að

$$0.01 - \sin 0.01 = 0.1667\cdot 10^{-7}$$

og við erum bara með 4 markverða stafi.

Hér dugir að taka aðeins þriðja stigs liðinn í Taylor-formúlunni

$$0.01 - \sin (0.01) \approx \frac{0.01^3}{3!} = 0.16666667 \cdot 10^{-7},$$

því skekkjan er

$$R_4(0.01) \leq \frac{0.01^5}{5!} < 10^{-12}$$

1.5. Skekkjur

Við allar úrlausnir á verkefnum í tölulegri greininingu þarf að fást við skekkjur. Þær eru af ýmsum toga:

• Gögn eru oft niðurstöður mælinga og þá fylgja þeim mæliskekkjur. Eins getum við þurft að notast við nálganir á föstum sem koma fyrir (t.d. $\pi$, Avogadrosar talan, …).

• Við nálganir á lausnum á stærðfræðilegum verkefnum verða til aðferðarskekkjur. Þær verða til þegar reikniritin eru hönnuð og greining á reikniritum snýst fyrst og fremst um mat á aðferðarskekkjum.

• Reikningsskekkjur verða til í tölvum á öllum stigum, jafnvel þegar tölur eru lesnar inn í tugakerfi og þeim snúið yfir í tvíundarkerfi. Þær verða líka til vegna þess að tölvur geta einungis unnið með endanlegt mengi af tölum og allar útkomur þarf að nálga innan þess mengis. Þessar skekkjur nefnast oft afrúningsskekkjur.

• Mannlegar villur eru óumflýjanlegar. Það sem við getum gert er temja okkur vinnubrögð sem lágmarka líkur á þeim og auðvelda okkur að finna villur sem við gerum.

  Real stupidity beats artificial intelligence every time. – Terry Pratchett

1.5.1. Skekkja í nálgun á rauntölu $r$

Við getum stillt upp jöfnunum svona

$$r \text{ (rétt gildi) } = x\text{ (nálgunargildi)} + e \text{ (skekkja)}$$

þar sem talan $x$ er nálgun á tölunni $r$, og þá nefnist

$$e=r-x$$

skekkjan (e. error) í nálgun á $r$ með $x$ eða bara skekkja.

Algildi skekkju (e. absolute error) er tölugildið $|e|=|r-x|$

Ef vitað er að $r\neq 0$, þá nefnist

$$\dfrac{|e|}{|r|}=\dfrac{|r-x|}{|r|}$$

hlutfallsleg skekkja (e. relative error) í nálgun á $r$ með $x$.

Aðvörun

Auðvitað er talan $r$ sem við leitum að óþekkt (annars þyrftum við ekki að framkvæma alla þessa reikninga), sem þýðir að við getum hvergi notað hana í reikningum.

1.5.2. Fyrirframmat á skekkju

Metið er áður en reikningar hefjast hversu umfangsmikla reikninga þarf að framkvæma til þess að nálgunin náist innan fyrirfram gefinna skekkjumarka.

Ef lausnin er fundin með ítrekunaraðferð er yfirleitt metið hversu margar ítrekarnir þarf til þess að nálgun verði innan skekkjumarka.

1.5.3. Eftirámat á skekkju

Um leið og reikningar eru framkvæmdir er lagt mat á skekkju og reikningum er hætt þegar matið segir að nálgun sé innan skekkjumarka. Það gerist yfirleitt þegar gildið sem við reiknum út breytist orðið lítið í hverju skrefi.

Hér þarf að skipta í tvö tilvik, fyrst skoðum við tilvikið þegar runan er ofurlínulega samleitin og seinna tilvikið er þegar við vitum aðeins að runan er línulega samleitin, en þá er matið aðeins flóknara.

1.5.4. Ofurlínuleg samleitni – Eftirámat á skekkju

Hugsum okkur að við séum að nálga töluna $r$ með gildum rununnar $x_n$, að við höfum reiknað út $x_0,\dots,x_n$ og viljum fá mat á skekkjunni $e_n=r-x_n$ í $n$-ta skrefi.

Við reiknum næst út $x_{n+1}$ og skrifum $e_{n+1}=\lambda_ne_n$. Þá er

$$x_{n+1}-x_n = (r-x_n)-(r-x_{n+1}) = e_n-e_{n+1} = (1-\lambda_n)e_n$$

og við fáum

$$e_n = \dfrac{x_{n+1}-x_n}{1-\lambda_n}.$$

Ef við vitum að runan er ofurlínulega samleitin, þá stefnir $\lambda_n$ á $0$ og þar með er

$$e_n\approx x_{n+1}-x_n.$$

Við hættum því útreikningi þegar $|x_{n+1}-x_n|<\varepsilon$ þar sem $\varepsilon$ er fyrirfram gefin tala, sem lýsir þeirri nákvæmni sem við viljum ná.

1.5.5. Línuleg samleitni – Eftirámat á skekkju

Skoðum nú tilvikið ef einu upplýsingarnar sem við höfum er að runan $x_n$ sé að minnsta kosti línulega samleitin, þ.e. $c\in [0,1)$ og $N\in \mathbb N$ þannig að

$$|e_{n+1}|\leq c|e_n|, \qquad \text{fyrir } n \geq N.$$

Þá stefnir $\lambda_n = e_{n+1}/e_n$ á fasta $\lambda \leq c$ og við höfum

$$\lambda_n = \dfrac{e_{n+1}}{e_n} = \dfrac{1-\lambda_n}{1-\lambda_{n+1}} \cdot\dfrac{x_{n+2}-x_{n+1}}{x_{n+1}-x_n}\approx \dfrac{x_{n+2}-x_{n+1}}{x_{n+1}-x_n}$$

Nú þurfum við að átta okkur á því hvernig þetta er nýtt í útreikningum.

Hugsum okkur að við höfum reiknað út $x_0,\dots,x_n$ og viljum fá mat á $e_n$. Við reiknum þá út $x_{n+1}$ og $x_{n+2}$ og síðan hlutfallið $\kappa_n=(x_{n+2} - x_{n+1})/(x_{n+1} - x_n)$ sem við notum sem mat á $\lambda_n$. Eftirámatið á skekkjunni í ítrekunarskrefi númer $n$ verður síðan

$$e_n\approx \dfrac{x_{n+1}-x_n}{1-\kappa_n}.$$

Ef stærðin í hægri hliðinni er komin niður fyrir fyrirfram gefin skekkjumörk $\varepsilon$, þá stöðvum við útreikningana.

1.5.6. Sýnidæmi

Okkur er gefin runa af nálgunum á lausn jöfnunnar

$$f(x) = e^x\sin x-x^2 = 0$$

og eigum að staðfesta hvort nálgunaraðferðin er ferningssamleitin:

$n$	$x_n$	$|x_{n+1}-x_n|$	$\frac{|x_{n+1}-x_n|}{|x_n-x_{n-1}|^2}$
0	3.00000000000000
1	2.73251570951922	0.10052257507862	1.404
2	2.63199313444060	0.01373904283351	1.359
3	2.61825409160709	0.00024006192208	1.273
4	2.61801402968501	0.00000007236005	1.256
5	2.61801395732496	0.00000000000001	1.272

Við metum $e_n\approx |x_{n+1}-x_n|$ og þar af leiðandi er

$$|e_n|/|e_{n-1}|^2\approx |x_{n+1}-x_n|/|x_n-x_{n-1}|^2.$$

Við sjáum að hlutfallið $|x_{n+1}-x_n|/|x_n-x_{n-1}|^2$ helst stöðugt og því ályktum við að aðferðin sé ferningssamleitin.

1.5.7. Útreikningur á samleitnistigi

Skoðum lítið dæmi um útreikninga á samleitnistigi.

Eftirfarandi runa stefnir á $\sqrt 3$.

$n$	$x_n$
0	2.000000000000000
1	1.666666666666667
2	1.727272727272727
3	1.732142857142857
4	1.732050680431722
5	1.732050807565499

Er samleitnistigið $1.618$?

Ef ekki, hvert er þá samleitnistigið?

Lausn

Ef miðað er við að runan $(x_n)$ sé ofurlínulega samleitin, þá er eðlilegt að taka $e_n\approx x_{n+1}-x_n$ sem mat á skekkjunni $e_n=\sqrt 3-x_n$ í $n$-ta ítrekunarskrefinu.

Við byrjum á því að kanna hvernig tilgátan um að samleitnistigið kemur út á þessum tölum með $e_n=x_{n+1}-x_n$:

$n$	$x_n$	$|e_n|$	$|e_n|/|e_{n-1}|^{1.618}$
0	2.000000000000000	3.3333$\cdot 10^{-1}$
1	1.666666666666667	6.0606$\cdot 10^{-2}$	3.5851$\cdot 10^{-1}$
2	1.727272727272727	4.8701$\cdot 10^{-3}$	4.5439$\cdot 10^{-1}$
3	1.732142857142857	9.2177$\cdot 10^{-5}$	5.0837$\cdot 10^{-1}$
4	1.732050680431722	1.2713$\cdot 10^{-7}$	4.3004$\cdot 10^{-1}$
5	1.732050807565499

Tveimur síðustu tölunum í aftasta dálki ber ekki nógu vel saman, svo það er vafasamt hvort talan $1.618$ er rétta samleitnistigið.

Ef $(x_n)$ er samleitin af stigi $\alpha$, þá gildir $\lim_{n\to \infty}|e_{n+1}|/|e_n|^\alpha=\lambda$, þar sem $\lambda>0$. Þar með höfum við nálgunarjöfnu ef $n$ er nógu stórt,

$$\dfrac{|e_{n+1}|}{|e_n|^\alpha} \approx \dfrac{|e_{n+2}|}{|e_{n+1}|^\alpha} \qquad \text{ þá og því aðeins að } \qquad \dfrac{|e_{n+1}|}{|e_{n+2}|} \approx \bigg|\dfrac{e_{n}}{e_{n+1}} \bigg|^\alpha.$$

Ef við lítum á þetta sem jöfnu og leysum út $\alpha$, þá fáum við

$$\alpha_n = \dfrac{\ln(|e_{n+1}|/|e_{n+2}|)}{\ln(|e_{n}|/|e_{n+1}|)}.$$

Við getum reiknað út þrjú gildi á $\alpha$ úr þeim gögnum sem við höfum, $\alpha_0= 1.479$, $\alpha_1 = 1.573$ og $\alpha_2=1.660$.

Ef við endurtökum útreikninga okkar hér að framan með $1.660$ í stað $1.618$, þá fæst

$n$	$p_n$	$|e_n|$	$|e_n|/|e_{n-1}|^{1.660}$
0	2.000000000000000	3.3333$\cdot 10^{-1}$
1	1.666666666666667	6.0606$\cdot 10^{-2}$	3.7551$\cdot 10^{-1}$
2	1.727272727272727	4.8701$\cdot 10^{-3}$	5.1143$\cdot 10^{-1}$
3	1.732142857142857	9.2177$\cdot 10^{-5}$	6.3639$\cdot 10^{-1}$
4	1.732050680431722	1.2713$\cdot 10^{-7}$	6.3639$\cdot 10^{-1}$
5	1.732050807565499

Tölunum neðst í aftasta dálki ber saman með fimm réttum stöfum og því ályktum við að $1.660$ sé nær því að vera rétta samleitnistigið.

1.6. Meira um skekkjur

1.6.1. Skilgreining: Markverðir stafir

Gerum ráð fyrir að $r\neq 0$, þá segjum við að $x$ sé nálgun á $r$ með $t$ markverðum stöfum (e. significant digits) ef

$$\frac{|r-x|}{|r|} \leq 10^{-t}.$$

Getum útfært þetta aðeins ítarlegra. Ef

$$10^{-(t+1)} < \frac{|r-x|}{|r|} \leq 10^{-t}.$$

þá segjum við að nálgunin á $r$ með $x$ sé rétt með að minnsta kosti $t$ markverðum stöfum og að hámarki með $t+1$ markverðum stöfum.

Athugið að ef $e$ er minnsta heila talan þannig að $|r|<10^e$, þá gefur seinni ójafnan matið

$$|r-x| = 0.0\dots 0 a_t a_{t+1}\ldots \ \cdot\ 10^e,$$

þar sem núllin aftan við punkt eru $t$ talsins.

Einnig er hægt að útfæra þetta fyrir aðrar grunntölur en 10.

1.6.2. Úrlausn annars stigs jöfnu

Þegar núllstöðvar annars stigs jöfnunnar $ax^2+bx+c=0$ eru reiknaðar út úr formúlunni

$$x = \dfrac{-b\pm\sqrt{b^2-4ac}}{2a},$$

verður til styttingarskekkja ef $b^2$ er miklu stærra heldur en $4ac$ vegna $|b|\approx\sqrt{b^2-4ac}$. Við komumst hjá þessum vandræðum með því að líta á margliðuna fullþáttaða $a(x-x_1)(x-x_2)$ og notfæra okkur að núllstöðvarnar $x_1$ og $x_2$ uppfylla $x_1x_2=c/a$.

Ef $b>0$, þá reiknum við $x_1$ fyrst út úr formúlunni

$$x_1 = \dfrac{-b-\sqrt{b^2-4ac}}{2a} \quad \text{ og síðan } \quad x_2 = \dfrac{c/a}{x_1}.$$

Ef aftur á móti $b<0$, þá reiknum við fyrst $x_1$ út úr formúlunni

$$x_1 = \dfrac{-b+\sqrt{b^2-4ac}}{2a} \qquad \text{ og síðan } \qquad x_2 = \dfrac{c/a}{x_1}.$$

Ef $b^2\approx 4ac$ þá lendum við í styttingarskekkjum, en við neyðumst til þess að lifa með þeim.

1.6.3. Áhrif gagnaskekkju

Hugsum okkur að við séum að finna nálgun á núllstöð falls $x\mapsto f(x,\alpha)$. Við viljum finna nálgun $x$ á lausninni $r=r(\alpha)$ sem uppfyllir

$$f(r,\alpha) = 0$$

og við lítum á $\alpha$ sem stika (t.d. náttúrulegur fasti).

Gerum ráð fyrir að $\alpha_0$ sé nálgun á $\alpha$ og að við þekkjum nálgun á $r(\alpha_0)$ sem er lausn á jöfnunni $f(x,\alpha_0)=0$.

Við viljum athuga hversu mikil áhrif nálgun á $\alpha$ með $\alpha_0$ hefur á lausnina okkar, þ.e. við þurfum að meta skekkjuna $r(\alpha)-r(\alpha_0)$.

Ef við gefum okkur að $f$ sé samfellt deildanlegt í grennd um punktinn $(x_0,\alpha_0)$, þar sem $x_0=r(\alpha_0)$ og ${\partial}_xf(x_0,\alpha_0)\neq 0$, þá segir setningin um fólgin föll að til sé grennd $I$ um punktinn $\alpha_0$ í ${\mathbb R}$ og samfellt deildanlegt fall $r:I\to {\mathbb R}$, þannig að $r(\alpha_0)=x_0$ og $f(r(\alpha),\alpha)=0$ fyrir öll $\alpha\in I$.

Með öðrum orðum má segja að við getum alltaf leyst jöfnuna $f(x,\alpha)=0$ með tilliti til $x$ þannig að út komi lausn $x=r(\alpha)$ sem er samfellt diffranlegt fall af $\alpha$.

Keðjureglan gefur okkur nú gildi afleiðunnar, því af jöfnunni $f(r(\alpha),\alpha)=0$ leiðir að fallið $I \ni \alpha \mapsto f(r(\alpha),\alpha)$ er fast, þannig að

$$0 =\frac {\partial}{\partial \alpha}f(r(\alpha),\alpha) = f_x'(r(\alpha), \alpha)\cdot r'(\alpha) + f_{\alpha}'(r(\alpha), \alpha).$$

Þetta gefur

$$r'(\alpha) = \frac{-f_{\alpha}'(r(\alpha),\alpha)} {f_x'(r(\alpha),\alpha)}.$$

Nú látum við $e$ tákna skekkjuna í nálguninni á $\alpha$ með $\alpha_0$, $e=\alpha-\alpha_0$. Þá fáum við skekkjumatið

$$r(\alpha) - r(\alpha_0) \approx r'(\alpha_0)\cdot e = \frac{-f_{\alpha}'(r(\alpha_0),\alpha_0)} {f_x'(r(\alpha_0),\alpha_0)}\cdot e$$

og jafnframt mat á hlutfallslegri skekkju

$$\dfrac{|r(\alpha) - r(\alpha_0)|} {|r(\alpha)|} \approx \frac{|f_{\alpha}'(r(\alpha_0),\alpha_0)|} {|r(\alpha_0)f_x'(r(\alpha_0),\alpha_0)|}\cdot |e|.$$

1.6.4. Sýnidæmi

Við skulum nú líta á það verkefni að finna nálgun á minnstu jákvæðu lausn jöfnunnar $\sin(\pi x)=1-e^{-x}$, þar sem við gerum ráð fyrir því að þurfa að nálga $\pi$ með $3.14$.

Okkur eru gefnar niðurstöður úr nálguninni með einhverri aðferð. Við setjum $f(x,\alpha)=1-e^{-x}-\sin(\alpha x)$ og fáum

$n$	$x_n$	$|x_{n+1}-x_n|$	$\frac{|x_{n+1}-x_n|}{|x_n-x_{n-1}|^2}$
0			0.8
1	0.81276894538752	0.00014017936338	0.8597
2	0.81262876602414	0.00000001621651	0.8253
3	0.81262874980763	0.00000000000000	0.8444

Hér er $\alpha=\pi$ og $\alpha_0=3.14$ og þar með $|e|<0.0016$.

Hlutafleiðurnar eru $f'_x(x,\alpha)=e^{-x}-\alpha\cos(\alpha x)$ og $f'_\alpha(x,\alpha)=-x\cos(\alpha x)$.

Við stingum tölunum okkar inn í matið og notum punktinn $(x_3,\alpha_0)=(0.8126,3.14)$. Það gefur

$$\begin{split}\begin{aligned} r(\pi)-r(3.14)&\approx r'(3.14) \cdot e\\ &\approx \dfrac{|0.8126\cdot \cos(0.8126\cdot 3.14)|}{|e^{-0.8126}-3.14 \cdot \cos(0.8126 \cdot 3.14)|}\ 0.0016 \\ &\approx 0.4\cdot 10^{-3}\end{aligned}\end{split}$$

Þetta mat segir okkur að við eigum að gera ráð fyrir að áhrif gagnaskekkjunnar séu þau að við fáum lausn með þremur réttum stöfum, $r(\pi) \approx 0.813$. Nálgun okkar á minnstu jákvæðu lausn jöfnunnar $\sin(\pi x)=1-e^{-x}$ er því $0.813$.

1.6.5. $O$-ritháttur

Látum $f$ og $g$ vera tvö föll sem skilgreind eru á bili $I \subset \mathbb{R}$ og látum $c$ vera tölu á $I$ eða annan hvorn endapunkt $I$.

Við segjum að $f(t)$ sé stórt O af $g(t)$ og skrifum

$$f(t) = O(g(t)), \qquad t \rightarrow c,$$

ef til er fasti $C>0$ þannig að ójafnan

$$|f(t)| \leq C|g(t)|$$

gildi fyrir öll $t$ í einhverri grennd um $c$.

Athugið að grennd um $c=+\infty$ er bil af gerðinni $]\alpha,+\infty[$ og grennd um $c=-\infty$ er bil af gerðinni $]-\infty,\alpha[$.

1.6.6. $O$-ritháttur og skekkja í Taylor-nálgnum

Oft er $O$-ritháttur notaður þegar fjallað er um skekkjur í Taylor-nálgunum,

$$\begin{split}\begin{aligned} f(x) - T_n f(x;c) &= f(x) - f(c) - f'(x-c) - \cdots - \frac{f^{(n)}(c)}{n!}(x-c)^n \\ &= \frac{f^{(n+1)}(\xi)}{(n+1)!}(x-c)^{n+1} = O\big((x-c)^{n+1}\big), \quad x \to c\end{aligned}\end{split}$$

1.6.7. Sýnidæmi

Það eru til haugar af dæmum, sem við þekkjum vel.

Setning Taylors gefur okkur:

$$\begin{split}\begin{gathered} x - \sin x = O(x^3), \quad x \to 0\\ x - \frac{x^3}{3!} - \sin x = O(x^5), \quad x \to 0\end{gathered}\end{split}$$

1.6.8. $O$-ritháttur fyrir runur

Látum nú $(a_n)$ og $(b_n)$ vera tvær talnarunur. Við segjum að $a_n$ sé stórt O af $b_n$ og skrifum

$$a_n = O(b_n),$$

ef til er fasti $C>0$ þannig að ójafnan

$$|a_n| \leq C|b_n|$$

gildi fyrir öll $n=0,1,2,3,\dots$.

1.6.9. Tvö sýnidæmi

• Út frá Taylor-röðinni fyrir $\cos x$ fáum við að

  $$\cos(1/n)-1+1/(2n^2) = O(1/n^4)$$

• Út frá

  $$\sqrt{n+1}-\sqrt n = \dfrac{1}{\sqrt{n+1}+\sqrt n} \leq \frac{1}{2\sqrt n}$$

  sjáum við að

  $$\sqrt{n+1}-\sqrt n = O\big(\dfrac 1{\sqrt n}\big)$$

1.7. Fleytitalnakerfið

1.7.1. Framsetning á tölum

Ef $r$ er rauntala frábrugðin $0$ og $\beta$ er náttúrleg tala, $2$ eða stærri, þá er til einhlýtt ákvörðuð framsetning á $r$ af gerðinni

$$r = \pm (0.d_1d_2\dots d_kd_{k+1}\dots)_\beta\times \beta^e$$

þar sem $e$ er heiltala og $d_j$ eru heiltölur

• $1\leq d_1<\beta$,

• $0\leq d_j<\beta$, $j=2,3,4,\dots$.

Tölvur reikna ýmist í tvíundarkerfi með $\beta=2$ eða í sextánundarkerfi með $\beta=16$, en við mannfólkið með okkar tíu fingur reiknum í tugakerfi með $\beta=10$.

1.7.2. Mantissa

Formerkið og runan

$$\pm(0.d_1d_2\dots d_kd_{k+1}\dots)_\beta = \pm\sum_{j=1}^\infty \dfrac{d_j}{\beta^j}$$

nefnist mantissa tölunnar $r$.

Við skrifum

$$(0.d_1d_2\dots d_k)_\beta = \sum_{j=1}^k \dfrac{d_j}{\beta^j}$$

ef $d_{k+1} = d_{k+2} = \cdots = 0$ og segjum þá að talan $r$ hafi $k$-stafa mantissu.

1.7.3. Markverðir $\beta$-stafir

Ef rauntalan $x$ er nálgun á $r$, þá segjum við að $x$ sé nálgun á $r$ með að minnsta kosti $t$ markverðum $\beta$ -stöfum ef

$$\dfrac{|r-x|}{|r|}\leq \beta^{-t}.$$

Ef við höfum að auki að

$$\beta^{-t-1}<\dfrac{|r-x|}{|r|}\leq \beta^{-t}.$$

þá segjum við að $x$ sé nálgun á $r$ með $t$ markverðum $\beta$ -stöfum.

Athugið að ef $e$ er minnsta heila talan þannig að $|r|<\beta^e$, þá gefur seinni ójafnan matið

$$|r-x| = (0.0\dots 0a_ta_{t+1}\dots)_\beta \times \beta^e,$$

þar sem núllin aftan við punkt eru $t$ talsins.

1.7.4. Afrúningur talna

Ef $r$ er sett fram á stöðluðu $\beta$-fleytitöluformi, þá nefnist talan

$$x = (\pm 0.d_1d_2\dots d_k)_\beta\times \beta^e$$

afskurður tölunnar $r$ við $k$ -ta aukastaf $r$, en talan

$$\begin{split}x = \begin{cases} \pm (0.d_1d_2\dots d_k)_\beta\times \beta^e, & d_{k+1}<\beta/2,\\ \pm ((0.d_1d_2\dots d_k)_\beta+\beta^{-k})\times \beta^e, &d_{k+1}\geq \beta/2. \end{cases}\end{split}$$

nefnist afrúningur tölunnar $r$ við $k$ -ta aukastaf.

Við köllum þessar aðgerðir afskurð (e. chopping) og afrúning (e. rounding).

1.7.5. Fleytitölukerfi

Fleytitölukerfi er endanlegt hlutmengi í ${\mathbb R}$, sem samanstendur af öllum tölum

$$\pm (0.d_1d_2\dots d_k)_\beta\times \beta^e$$

þar sem $d_j$ eru heiltölur eins og áður var lýst, $k$ er föst tala og við höfum mörk á veldisvísinum $m\leq e\leq M$.

Allar tölvur vinna með eitthvert fleytitölukerfi, oftast með grunntölu $\beta=2$ eða $\beta=16$ eins og áður sagði.

Eftir hverja aðgerð í tölvunni þarf að nálga útkomuna með afskurði eða afrúningu.

Ef við förum ekki varlega þá getur þetta magnað upp skekkju.

Sjá Úrlausn annars stigs jöfnu.

1.7.6. IEEE staðlar

• Single: $\beta = 2, k=24, m=-125$ og $M = 128$,

• Double: $\beta = 2, k=53, m=-1021$ og $M = 1024$.

1.7.7. Útreikningur í tugakerfi

Þegar reiknað er í tugakerfi er tölurnar afrúnaðar við $k$-ta aukastaf ef skekkjan í nálgun á þeim er minni en $\frac 12\times 10^{-k}$. Ef

$$\dfrac{|r-x|}{|r|}<10^{-k-1}$$

þá treystum við öllum $k$ stöfum mantissunnar, en ef

$$\dfrac{|r-x|}{|r|}>10^{-k+q},$$

þá eru síðustu $q$ stafir mantissunnar marklausir auk þess sem vænta má nokkurs fráviks í $d_{k-q}$.