Við munum aðeins tala um föll \(f(x)\) sem haga sér vel á einhverju bili, þ.e. eru samfelld og óendanlega oft diffranleg.
Rifjum upp skilgreininguna á afleiðunni \(f'(x)\)
\[ f'(x) = \lim_{h\to 0}\frac{f(x+h)-f(x)}{h} \]
Athugið að í markgildinu getur \(h\) verið jákvætt eða neikvætt.
Verkefnið sem við fáum er að fallið \(f\) er gefið, annað hvort sem formúla eða forritsbútur og við þurfum að finna afleiðuna. Ef við vitum ekki hvert fallið er eða það er of flókið, þá þurfum við að diffra tölulega.
Gefið \(x\) þá þurfum við að finna gildið \(f'(x)\). Nokkrar leiðir
Síðasti kosturinn heitir töluleg diffrun
Notum skilgreininguna á \(f'\) og reiknum
\[ f'(x) \approx \frac{f(x+h)-f(x)}{h} \]
fyrir \(h\) nógu nálægt núlli.
Eftir því sem \(h\) verður minna þá eru \(f(x+h)\) og \(f(x)\) mjög líkar tölur og hætta á að markverðir aukastafir tapist.
Notum Taylor margliðuna fyrir \(f(x+h)\) í kringum punktinn \(x\).
\[ f(x+h) = f(x) + f'(x)\cdot h + \frac{f''(t)}{2}h^2 \]
þar sem \(x < t < x+h\). Þá fæst
\[ \frac{f(x+h)-f(x)}{h} = f'(x) + \frac{f''(t)}{2}h \]
Svo villan er \(O(h)\) (þ.e. einhver fasti sinnum \(h\))
Skoðum \(f(x) = xe^x\). \(f'(x) = e^x + xe^x\).
Einfalda aðferðin er ekki nógu góð því villan vex eins og \(h\), helst viljum við fá minni villu.
Skoðum Taylor margliðuna fyrir \(f(x+h)\) og \(f(x-h)\)
\[ \begin{aligned} f(x+h) &= f(x) + f'(x)\cdot h + \frac{f''(x)}{2}\cdot h^2 + \frac{f''(t_1)}{6}h^3\\ f(x-h) &= f(x) - f'(x)\cdot h + \frac{f''(x)}{2}\cdot h^2 - \frac{f''(t_2)}{6}h^3 \end{aligned} \] Þá fæst að
\[ \frac{f(x+h)-f(x-h)}{2h} = f'(x) + O(h^2) \]
sem gefur mun betri nálgun.
Þegar við notum miðju aðferð til að finna tölulega afleiðu þá þurfum við að velja \(h\) mátulega lítið
Þumalputtaregla er að nota
\[ h = \sqrt[3]{\frac{3\varepsilon |f(x)|}{|f'''(x)|}} \]
Þar sem \(\varepsilon \approx 10^{-16}\). Ef gildin á \(f(x)/f'''(x)\) eru ekki þekkt getur verið nóg að nálga þau mjög gróft upp að réttum tug.
Skoðum jöfnuna
\[x^3 - x - 1 = 0\]
Lausnin er
\[ x = 1/3\left(27/2-(3 \sqrt{69})/2\right)^{1/3}+\left(1/2 (9+\sqrt{69})\right)^{1/3}/3^{2/3} \]
Þriðja og fjórða stigs margliður hafa lokaðar lausnir en fimmta stigs margliður hafa engar lokaðar lausnir.
Það er mikilvægt að geta fundið núllstöðvar falla á tölulegan hátt.
Oft er hægt að umrita föll sem lausnir á ólínulegum jöfnum, t.d. er \(\sqrt{5}\) jákvæða lausnin á jöfnunni \(x^2 - 5 = 0\).
Fallið \(f(x) = sin^{-1}(x)\) er skilgreint sem sú tala \(y \in [-\frac{\pi}{2},\frac{\pi}{2}]\) þ.a. \(sin(y) = x\).
Til að reikna út gildið \(f(0.5)\) tölulega þá leysum við jöfnuna \(sin(y) = 0.5\) tölulega.
Í stað þess að skilgreina fallið með formúlu getum við skilgreint það með forriti.
Milligildis setningin segir að ef \(f(x)\) er samfellt fall og \(f(a) > 0\) og \(f(b) < 0\) þá er til a.m.k. ein lausn á jöfnunni \(f(x) = 0\) á bilinu \((a,b)\).
Þetta leiðir strax til einföldustu aðferðarinnar við að leysa jöfnur sem er helmingunarleit.
Við fáum sem inntak \(f(x)\), og tölur \(a,b\) þ.a. \(f(a)\cdot f(b) \le 0\)
Hvenær eigum við að hætta? Hversu margar umferðir tekur þetta?
Hættum þegar \(c\) er annað hvort \(a\) eða \(b\).
Getum hætt fyrr ef við viljum fá minni nákvæmni.
Hver umferð minnkar bilið \(|a-b|\) um helming, 53 umferðir í mesta lagi.
Kostir og ókostir:
Höfum gefið \(f(x),f'(x)\) og viljum finna \(x\) þ.a. \(f(x) = 0\). Byrjum með upphafságiskun \(x_0\) og nálgum \(f(x)\) með 1. stigs Taylor margliðu í kringum punktinn \(x_0\).
\[ f(x) \approx f(x_0) + f'(x_0)\cdot(x-x_0) \]
Leysum hægri hlið jafnt og \(0\) og fáum
\[ x = x_0 - \frac{f(x_0)}{f'(x_0)} \]
Notum þessa lausn sem næstu ágiskun.
Byrjum með \(x_0\)
Við getum hætt þegar (hlutfallsleg) villa í \(x_i\) er orðin nógu lítil eða \(f(x_i)\) er nógu nálægt núlli.
Oft er erfiðast að finna upphafspunkt
\(f(x) = x^3 - x -1\) og \(f'(x) = 3x^2-1\)
Skoðum aftur fallið \(f(t) = \frac{1}{\sqrt{t}}\). \(x=f(c)\) er jákvæða lausnin á jöfnunni
\[ x^2 - \frac{1}{c} = 0 \]
þ.e. \(h(x) = x^2-\frac{1}{c}\) og \(h'(x) = 2x\). Þá fæst Newtons ítrunin
\[ x_{i+1} = x_{i} - \frac{x_{i}^2 - \frac{1}{c}}{2x_i} = \frac{1}{2}\left(\frac{1}{cx_i} - x_i\right) \]
T.d. er \(x_0 = \frac{1}{c}\) góð upphafságiskun
Skoðum \(f(x) = |x|^a\) þar sem \(a > 0\).
Þá er \[f'(x) = a|x|^{a-1}\cdot sgn(x)\]
þar sem \(sgn(x)\) skilar formerkinu á \(x\). Newtons ítrunin verður þá
\[ x_{i+1} = x_i - \frac{|x|^a}{a|x|^{a-1}\cdot sgn(x)} = x_i - \frac{1}{a}|x_i|sgn(x) = (1-\frac{1}{a})x_i \]
Þessi runa er samleitin og stefnir á 0 þegar \(a\ge \frac{1}{2}\) og ósamleitin annars.
Þegar aðferð Newtons er samleitin þá gildir nógu nálægt núll stöðinni að
\[ |\varepsilon_{i+1}| \le C\cdot |\varepsilon_{i}|^{2} \]
þar sem \(\varepsilon_{i}\) er fjarlægð \(i\)-tu ágiskunar frá núllstöð. Þetta þýðir að fjöldi markverðra stafa tvöfaldast með hverju skrefi.
Ókostir við Newtons aðferð er að það getur verið erfitt að tryggja samleitni og val á upphafspunkti getur haft mikil áhrif á niðurstöðu.
Sniðilsaðferðin er einfaldari en Newtons aðferð en að mörgu leiti mjög lík. Hún hefur líka þann kost að þurfa bara á fallinu \(f(x)\) að halda en notar ekki afleiðuna \(f'(x)\).
Við byrjum með tvo upphafspunkta \(x_0,x_1\) og nálgum fallið með beinni línu í gegnum punktana. Þessi lína hefur hallatöluna \[ \alpha = \frac{f(x_1)-f(x_0)}{x_1-x_0} \] og fer í gegnum punktinn \((x_1,f(x_1))\), jafna línunnar verður því
\[ y = f(x_1) + \alpha (x-x_1) \]
og sker því \(x\)-ásinn þegar \(y=0\) í punktinum
\[ x = x_1 - \frac{f(x_1)}{\alpha} = x_1 - \frac{f(x_1)\cdot(x-x_1)}{f(x_1)-f(x_0)} = \frac{f(x_1)x_0 - f(x_0)x_1}{f(x_1)-f(x_0)} \]
Byrjum með \(x_0,x_1\)
Við getum hætt þegar (hlutfallsleg) villa í \(x_i\) er orðin nógu lítil eða \(f(x_i)\) er nógu nálægt núlli.
Gallar: svipuð áhætta í samleitni eins og Newtons aðferð
Kostir: þurfum bara eitt fallakall í hverri ítrun, geymum fyrra fallsgildi í breytu.
Rótaraðferðir eru líka oft notaðar þegar lágmarka þarf fall \(f(x)\) á bili \([a,b]\).
Ef \(x\) er lággildi þá gildir annað hvort að \(f'(x)=0\), eða \(x=a\) eða \(x=b\).
Andstæðan gildir ekki, ef \(f'(x)\) þá getur \(x\) verið hágildi, lággildi eða hvorugt.
Lesið fyrsta kafla í bókinni Vectors, Matrices, and Least Squares eftir S. Boyd og L. Vandenberghe. (er á pdf á heimasíðunni).