2. Núllstöðvar

Build a man a fire, and he’ll be warm for a day. Set a man on fire, and he’ll be warm for the rest of his life.

- Terry Pratchett, Jingo

2.1. Nálgun á núllstöð

2.1.1. Skilgreining

Munum að talan \(p\in I\) sögð vera núllstöð fallsins \(f:I\to {\mathbb R}\) ef

\[f(p)=0.\]

2.1.2. Dæmi

Það er auðvelt að finna núllstöðvar (rót) annars stigs margliðu \(ax^2+bx+c\), því

\[ax^2+bx+c = 0\]

ef

\[x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}.\]

Svipaðar formúlur eru til fyrir núllstöðvar þriðja og fjórða stigs margliða. Einnig þekkjum við núllstöðvar hornafalla.

2.1.3. Athugasemd

Almennt er hins vegar erfitt að finna núllstöðvar falla. Til dæmis er ekki til almenn formúla fyrir núllstöðvar margliða af stigi 5 og hærra (sjá Abel-Ruffini setningin).

Eins er ekki hægt treysta á það að geta fundið nákvæmlega núllstöðvar almennra falla með því að nota þekkingu okkar á algebru og stærðfræðigreinginu. Hverjar (og hversu margar) eru t.d. núllstöðvar

\[e^x + x^3?\]

Aðferðirnar í þessum kafla ganga út á að finna nálgun á núllstöðvum falla og í sumum tilvikum hjálpa þær okkur einnig að sýna fram á tilvist núllstöðva (sem er ekki alltaf sjálfgefin).

2.2. Helmingunaraðferð

Fyrsta aðferðin til að finna núllstöðvar sem við skoðum kallast helmingunaraðferð (e. bisection method).

2.2.1. Milligildissetningin

Ef \(f\) er samfellt á \([a,b]\) og \(y\) er einhver tala á milli \(f(a)\) og \(f(b)\), þá er til \(c\) þannig að \(a < c < b\) og \(f(c) = y\).

2.2.2. Afleiðing

Svo ef við höfum \(a\) og \(b\) þannig að \(a < b\) og þannig að \(f(a)\) og \(f(b)\) hafi ólík formerki, þá hefur \(f\) núllstöð \(p\) á bilinu \([a,b]\).

Notum okkur þetta til þess að finna rætur.

1. Látum \(x = \frac 12(a+b)\) vera miðpunkt \([a,b]\).

2. Reiknum \(f(x)\), þá geta þrjú tilvik komið upp:

   1. \(f(x) = 0\) og leitinni að rót er lokið.

   2. \(f(a)\) og \(f(x)\) hafa sama formerki, þannig að við leitum að rót á bilinu \([x,b]\).

   3. \(f(x)\) og \(f(b)\) hafa sama formerki, þannig að við leitum að rót á bilinu \([a,x]\).

Í tilviki (ii) segir milligildissetningin að \(f\) hafi rót á bilinu \([x,b]\), og í tilviki (iii) er rótin á bilinu \([a,x]\). Þá getum við farið aftur í skref 1, nema með helmingi minna bil en áður.

Með því að ítreka þetta ferli \(n\) sinnum fáum við minnkandi runu af bilum

\[[a,b]=[a_1,b_1]\supset [a_2,b_2]\supset \cdots\supset [a_n,b_n].\]

Billengdin helmingast í hverju skrefi og milligildissetningin segir okkur að það sé núllstöð á öllum bilunum.

Rununa af bilunum

\[[a,b]= [a_1,b_1]\supset \cdots\supset [a_n,b_n]\supset \cdots\]

skilgreinum við með ítrun og notum til þess rununa \(x_n=\frac 12(a_n+b_n)\).

Setjum \(a_0=a\), \(b_0=b\), og \(x_0=\frac 12(a+b)\).

Gefið er \(x_0,\dots,x_n\). Reiknum \(f(x_n)\).

1. Ef \(f(x_n) = 0\), þá er núllstöð fundin og við hættum.

2. Ef \(f(x_n)\) og \(f(a_n)\) hafa sama formerki, þá setjum við \(a_{n+1}=x_n\), \(b_{n+1}=b_n\), og \(x_{n+1}=\frac 12(a_{n+1}+b_{n+1})\)

3. annars setjum við \(a_{n+1}=a_n\), \(b_{n+1}=x_n\) og \(x_{n+1}=\frac 12(a_{n+1}+b_{n+1})\).

2.2.3. Skekkjumat í helmingunaraðferð

Ef við látum miðpunktinn \(p_n=\frac 12(a_n+b_n)\) vera nálgunargildi okkar fyrir núllstöð fallsins \(f\) í bilinu \([a_n,b_n]\), þá er skekkjan í nálguninni

\[e_n=p-p_n\]

og við höfum skekkjumatið

\[|e_n|\leq \dfrac{b_n - a_n}{2}\ = \frac{b_{n-1}-a_{n-1}}{2^2} = \ldots = \dfrac{b_1-a_1}{2^{n}},\]

það er

\[|e_n| < \dfrac{b-a}{2^{n}}.\]

2.2.4. Fyrirframmat á skekkju

Nú er auðvelt að meta hversu margar ítrekanir þarf að framkvæma til þess að nálgunin lendi innan gefinna skekkjumarka.

Ef \(\varepsilon>0\) er gefið og við viljum að \(|e_n|< \varepsilon\), þá dugir að

\[|e_n|\leq \dfrac{b-a}{2^{n}} <\varepsilon.\]

Seinni ójafnan jafngildir því að

\[n>\dfrac{\ln\big((b-a)/\varepsilon\big)}{\ln 2}.\]

2.3. Fastapunktsaðferð

Næsta aðferð sem við skoðum kallast fastapunktsaðferð (e. fixed point method) og er til að finna fastapunkta en ekki núllstöðvar. Það er hins vegar hægt að nota hana til þess að finna núllstöðvar, sjá athugasemd hér að neðan.

2.3.1. Skilgreining

Látum \(f : [a,b] \to \mathbb R\) vera samfellt fall. Punktur \(r \in [a,b]\) þannig að

\[f(r) = r\]

kallast fastapunktur fallsins \(f\).

Athugasemd

Athugum að í fastapunktum skerast graf fallsins \(y=f(x)\) og línan \(y=x\). Verkefnið að ákvarða fastapunkta fallsins \(r\) er því jafngilt því að athuga hvar graf \(f\) sker línuna \(y=x\).

2.3.2. Tenging við núllstöðvar

Verkefnið að finna fastapunkta fallsins \(g(x)\) er jafngilt því að finna núllstöðvar fallsins \(f(x)=g(x)-x\).

Þannig að ef við viljum t.d. finna núllstöð \(f(x) = e^x + x^3\) þá er nóg að finna fastapunkt fallsins \(g(x) = e^x + x^3 + x\).

2.3.3. Reiknirit

Byrjunarskref: Valin er tala \(x_0\in [a,b]\).

Ítrunarskref: Ef \(x_0,\dots,x_n\) hafa verið valin, þá setjum við

\[x_{n+1}=f(x_n)\]

Athugasemd

Til þess að þetta sé vel skilgreind runa, þá verðum við að gera ráð fyrir að \(f(x)\in [a,b]\) fyrir öll \(x\in [a,b]\). Þetta skilyrði er einnig skrifað

\[f([a,b])\subset [a,b].\]

Athugasemd

Ef \(f\) er samfellt og runan er samleitin með markgildið \(r\), þá er

\[r=\lim_{n\to \infty}x_{n+1}=\lim_{n\to \infty}f(x_{n}) =f(\lim_{n\to \infty}x_{n})=f(r).\]

Þetta segir okkur að ef við getum séð til þess að runan verði samleitin, þá er markgildið fastapunktur.

2.3.4. Skilgreining: Herping

Fall \(f:[a,b]\to {\mathbb R}\) er sagt vera herping ef til er fasti \(\lambda\in [0,1[\) þannig að

\[|f(x)-f(y)|\leq \lambda|x-y| \qquad \text{ fyrir öll } x,y\in [a,b].\]

Athugasemd

Sérhver herping er samfellt fall.

2.3.5. Setning

Ef \(f\) er deildanlegt fall á \(]a,b[\), þá gefur meðalgildissetningin okkur til er \(\xi\) milli \(x\) og \(y\) þannig að

\[f(x)-f(y)=f'(\xi)(x-y).\]

Ef til er \(\lambda\in[0,1[\) þannig að \(|f'(x)|\leq \lambda\) fyrir öll \(x\in [a,b]\), þá er greinilegt að \(f\) er herping.

2.3.6. Fastapunktssetningin

Látum \(f : [a,b] \to [a,b]\) vera herpingu. Þá hefur \(f\) nákvæmlega einn fastapunkt \(r\) á bilinu \([a,b]\) og runan \((x_n)\) þar sem

\[\begin{split}\begin{aligned} x_0 &\in [a,b] \quad \text{ getur verið hvaða tala sem er og } \\ x_{n+1} &= f(x_n), \quad n \geq 0,\end{aligned}\end{split}\]

stefnir á fastapunktinn.

Sönnun

Sönnunina brjótum við upp í nokkur skref.

1. skref, herping hefur í mesta lagi einn fastapunkt

Sönnum þetta með mótsögn.

Gerum ráð fyrir að \(r\) og \(s\) séu tveir ólíkir fastapunktar á \([a,b]\). Þá er

\[|r - s| = |f(r) - f(s)| \leq \lambda |r - s| < |r - s|\]

því \(\lambda < 1\). Þetta fær ekki staðist, þannig að fjöldi fastapunkta er í mesta lagi einn

2. skref, fallið \(f\) hefur fastapunkt:

Látum \(g(x) = f(x) - x\), þá eru núllstöðvar \(g\) nákvæmlega fastapunktar \(f\).

Þar sem \(a \leq f(x) \leq b\) fyrir öll \(x \in [a,b]\) er

\[\begin{split}\left\{ \begin{array}{c} g(a) = f(a) - a \geq 0 \\ g(b) = f(b) - b \leq 0 \end{array} \right.\end{split}\]

Ef annað hvort \(g(a) = 0\) eða \(g(b) = 0\) höfum við fundið fastapunkt fallsins \(f\) og við getum hætt.

Ef hins vegar \(g(a) > 0\) og \(g(b) < 0\) þá hefur \(g\) ólík formerki í endapunktum bilsins \([a,b]\) og hefur því núllstöð \(r\) á bilinu skv. milligildissetninguninni. Þá er \(r\) jafnframt fastapunktur \(f\).

Skref 1 og 2 sýna því að fallið \(f\) hefur nákvæmlega einn fastapunkt á bilinu.

3. skref, runan \((x_n)\) er samleitin

Látum \(r\) vera ótvírætt ákvarðaða fastapunktinn á \([a,b]\).

Við notfærum okkur að \(f\) er herping og að \(r\) er fastapunktur \(f\), þá fæst að fyrir sérhvert \(k\in {\mathbb N}\) þá er

\[|r - x_k| = |f(r) - f(x_{k-1})| \leq \lambda |r - x_{k-1}|\]

það er \(|r - x_k| \leq \lambda |r - x_{k-1}|\).

Með því að nota þetta \(n\)-sinnum þá fæst að

\[\begin{split}\begin{aligned} |r - x_n| &\leq \lambda |r - x_{n-1}| & (k=n)\\ &\leq \lambda^2 |r - x_{n-2}| & (k=n-1)\\ &\vdots & \vdots\\ &\leq \lambda^n |r - x_0| & (k=1). \end{aligned}\end{split}\]

Þar sem \(\lambda < 1\) er því

\[\lim\limits_{n \to +\infty} |r - x_n| \leq \lim\limits_{n \to +\infty} \lambda^n |r - x_0| = 0,\]

það er runan \(x_n\) stefnir á \(r\).

2.3.7. Fastapunktsaðferð er að minnsta kosti línulega samleitin

Af skilgreiningunni á rununni \(x_n\) leiðir beint að

\[|e_{n+1}|=|r-x_{n+1}|=|f(r)-f(x_n)|\leq \lambda|r-x_n|=\lambda|e_n|\]

sem segir okkur að fastapunktsaðferð sé að minnsta kosti línulega samleitin ef \(f\) er herping.

2.4. Sniðilsaðferð

Næst er aðferð til að finna núllstöðvar sem kallast sniðilsaðferð (e. secant method)

Gefið er fallið \(f:[a,b]\to {\mathbb R}\). Við ætlum að ákvarða núllstöð \(f\), þ.e.a.s. \(p\in [a,b]\) þannig að

\[f(p)=0.\]

Rifjum upp að sniðill við graf \(f\) gegnum punktana \((\alpha,f(\alpha))\) og \((\beta,f(\beta))\) er gefinn með jöfnunni

\[y=f(\alpha)+f[\alpha,\beta](x-\alpha)\]

þar sem hallatalan er

\[f[\alpha,\beta]=\dfrac{f(\beta)-f(\alpha)}{\beta-\alpha} =\dfrac{f(\alpha)-f(\beta)}{\alpha -\beta}.\]

Sniðillinn sker \(x\)-ásinn í punkti \(s\) þar sem

\[0=f(\alpha)+f[\alpha,\beta](s-\alpha) \quad \text{sem jafngildir því að } \quad s=\alpha-\dfrac{f(\alpha)}{f[\alpha,\beta]}.\]

2.4.1. Reiknirit

Byrjunarskref: Giskað er á tvö gildi \(x_0\) og \(x_1\).

Ítrunarskref: Fyrir \(n>1\) þá er punkturinn \(x_{n+1}\) skilgreindur sem skurðpunktur sniðilsins gegnum \((x_{n-1},f(x_{n-1}))\) og \((x_n,f(x_n))\) við \(x\)-ás, þ.e.

\[x_{n+1}=x_n-\dfrac{f(x_n)}{f[x_n,x_{n-1}]}.\]

2.4.2. Samleitin runa stefnir á núllstöð \(f\)

Gefum okkur að runan \((x_n)\) sé samleitin að markgildinu \(r\). Meðalgildissetningin segir okkur þá að til sé punktur \(\eta_n\) á milli \(x_{n-1}\) og \(x_n\) þannig að

\[f[x_n,x_{n-1}]=f'(\eta_n),\]

og greinilegt er að \(\eta_n\to r\).

Við fáum því

\[r=\lim_{n\to \infty}x_{n+1}=\lim_{n\to \infty} \bigg(x_n-\dfrac{f(x_n)}{f'(\eta_n)}\bigg) =r-\dfrac{f(r)}{f'(r)}\]

Þessi jafna jafngildir því að \(f(r)=0\).

2.4.3. Skekkjumat í nálgun á \(f(x)\) með \(p_n(x)\)

Sniðilinn sem við notum er graf 1. stigs margliðunnar

\[p_n(x) = f(x_n) + \dfrac{f(x_{n-1})-f(x_n)}{x_{n-1}-x_n}(x-x_n) = f(x_n) + f[x_n,x_{n-1}](x-x_n)\]

Samkvæmt skilgreiningu er \(p_n(x_{n+1}) = 0\) svo \(x_{n+1}\) uppfyllir jöfnuna

\[x_{n+1} = x_n - \frac{f(x_n)}{f[x_n,x_{n-1}]}.\]

Við þurfum að vita hver skekkjan er á því að nálga \(f(x)\) með \(p_n(x)\).

Niðurstaðan er að fyrir sérhvert \(x \in [a,b]\) er til \(\xi_n\) sem liggur í minnsta bilinu sem inniheldur \(x\), \(x_n\) og \(x_{n-1}\) þannig að

\[f(x) - p_n(x) = \frac{1}{2}f''(\xi_n)(x-x_n)(x-x_{n-1})\]

Sönnun

Ljóst er að matið gildir ef \(x=x_{n-1}\) eða \(x=x_n\).

Festum því punktinn \(x\) og gerum ráð fyrir að \(x\neq x_1\) og \(x\neq x_n\).

Skilgreinum fallið

\[g(t)=f(t)-p_n(t)-\lambda(t-x_n)(t-x_{n-1})\]

þar sem \(\lambda\) er valið þannig að \(g(x)=0\).

Látum nú \(\alpha<\beta<\gamma\) vera uppröðun á punktunum \(x_{n-1}\), \(x_n\) og \(x\).

Fallið

\[g(t)=f(t)-p_n(t)-\lambda(t-x_n)(t-x_{n-1})\]

hefur núllstöð í öllum punktunum þremur.

Meðalgildissetningin gefur þá að \(g'(t)\) hefur eina núllstöð í punkti á bilinu \(]\alpha,\beta[\) og aðra í \(]\beta,\gamma[\).

Af því leiðir aftur að \(g''(t)\) hefur núllstöð, \(\xi_n\), í \([\alpha,\gamma]\), sem er minnsta bilið sem inniheldur alla punktana \(x_{n-1}\), \(x_n\) og \(x\).

Af þessu leiðir

\[0=g''(\xi_n)=f''(\xi_n)-2\lambda \quad \text{þþaa} \quad \lambda=\tfrac 12 f''(\xi_n).\]

Nú var \(\lambda\) upprunalega valið þannig að \(g(x)=0\). Þar með er

\[f(x) - p_n(x) = \frac{1}{2}f''(\xi_n)(x-x_n)(x-x_{n-1}).\]

2.4.4. Skekkjumat í sniðilsaðferð

Skoðum hvað af þessu leiðir:

Nú er \(f(r) = 0\) og því

\[-p_n(r) = \frac{1}{2}f''(\xi_n)e_n\cdot e_{n-1}.\]

Eins er

\[-p_n(r) = -f[x_n,x_{n-1}]e_{n+1}=-f'(\eta_n)e_{n+1},\]

þar sem \(\eta_n\) fæst úr meðalgildissetningunni og liggur á milli \(x_n\) og \(x_{n+1}\). Niðurstaðan verður því

\[e_{n+1} = \frac{-\frac{1}{2}f''(\xi_n)} {f[x_n, x_{n+1}]} e_ne_{n-1} = \frac{-\frac{1}{2}f''(\xi_n)} {f'(\eta_n)}e_ne_{n-1}\]

það er

\[\lim_{n\to \infty}\dfrac{e_{n+1}}{e_ne_{n-1}}= \lim_{n \to \infty} \frac{-\frac{1}{2}f''(\xi_n)} {f'(\eta_n)} = \frac{-\frac{1}{2}f''(r)} {f'(r)}.\]

2.4.5. Setning

Ef sniðilsaðferð er samleitin, \(f\in C^2([a,b])\) (tvisvar diffranlegt) og \(f'(r)\neq 0\), þá er sniðilsaðferðin ofurlínuleg.

Sönnun

\[\lim_{n\to \infty}\dfrac{|e_{n+1}|}{|e_n|} = \lim_{n\to \infty}\dfrac{|e_{n+1}e_{n-1}|}{|e_ne_{n-1}|}= \lim_{n \to \infty} \frac{|e_{n-1}\frac{1}{2}f''(r)|} {|f'(r)|} = 0\]

Raunar þá er sniðilsaðferðin samleitin af stigi \(\alpha = (1+\sqrt 5)/2 \approx 1,618\) og með \(\lambda = \left(\frac{f''(r)}{2f'(r)}\right)^{\alpha -1}\).

2.5. Aðferð Newtons

Í sniðilsaðferðinni létum við \(x_{n+1}\) vera skurðpunkt sniðils gegnum \((x_{n-1},f(x_{n-1}))\) og \((x_n,f(x_n))\) við \(x\)-ás og fengum við rakningarformúluna

\[x_{n+1} = x_n - \frac{f(x_n)}{f[x_n,x_{n-1}]}.\]

Aðferð Newtons er nánast eins, nema í stað sniðils tökum við snertil í punktinum \((x_n,f(x_n))\).

Rakningarformúlan er eins, nema hallatalan verður \(f'(x_n)\) í stað \(f[x_n,x_{n-1}]\)

2.5.1. Reiknirit

Byrjunarskref: Giskað er á eitt gildi \(x_0\).

Ítrunarskref: Gefin eru \(x_0,\dots,x_n\). Punkturinn \(x_{n+1}\) er skurðpunktur snertils gegnum \((x_n,f(x_n))\) við \(x\)-ás,

\[x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}.\]

2.5.2. Upprifjun

Munum að snertill við graf \(f\) í punktinum \(x_n\) er

\[y=f(x_n) + f'(x_n)(x-x_n),\]

þessi lína sker \(x\)-ásinn (\(y=0\)) þegar \(x=x_n - \frac{f(x_n)}{f'(x_n)}\).

2.5.3. Samleitin runa stefnir á núllstöð \(f\)

Gefum okkur að runan \((x_n)\) sé samleitin með markgildið \(r\). Við fáum því

\[r=\lim_{n\to \infty}x_{n+1}=\lim_{n\to \infty} \bigg(x_n-\dfrac{f(x_n)}{f'(x_n)}\bigg) =r-\dfrac{f(r)}{f'(r)}\]

Þessi jafna jafngildir því að \(f(r)=0\).

Þannig að ef runan er samleitin þá fáum við núllstöð.

2.5.4. Skekkjumat í nálgun á \(f(x)\) með \(p_n(x)\)

Snertillinn við \(f\) í punktinum \(x_n\) er 1. stigs margliðan

\[p_n(x) = f(x_n) + f'(x_n)(x-x_n)\]

Samkvæmt skilgreiningu er \(p_n(x_{n+1}) = 0\) svo \(x_{n+1}\) uppfyllir jöfnuna

\[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.\]

Athugum að \(p_n\) er fyrsta Taylor nálgunin við fallið \(f\) kringum \(x_n\). Setning Taylors gefur að til er \(\xi_n\) sem liggur á milli \(r\) og \(x_n\) þannig að

\[f(r) - p_n(r) = \frac{1}{2}f''(\xi_n)(r-x_n)^2.\]

2.5.5. Skekkjumat í aðferð Newtons

Nú er \(f(r) = 0\) og því

\[-p_n(r) = \frac{1}{2}f''(\xi_n)e_n^2.\]

Eins er fæst af skilgreiningunni á \(p_n\) að

\[-p_n(r) = -f'(x_n)e_{n+1}\]

Niðurstaðan verður því

\[e_{n+1} = \frac{-\frac{1}{2}f''(\xi_n)} {f'(x_n)}e_n^2\]

2.5.6. Setning

Ef aðferð Newtons fyrir fallið \(f\) er samleitin, \(f\in C^2([a,b])\) og \(f'(r)\neq 0\), þá fáum við:

\[\lim_{n\to \infty}\dfrac{e_{n+1}}{e_n^2}=\frac{-\frac{1}{2}f''(r)} {f'(r)}\]

Það þýðir að aðferð Newtons er ferningssamleitin.

Sönnun

\[\lim_{n\to \infty}\dfrac{e_{n+1}}{e_n^2}= \lim_{n\to \infty}\frac{-\frac{1}{2}f''(\xi_n)}{f'(x_n)} = \frac{-\frac{1}{2}f''(r)}{f'(r)}\]

Athugasemd

Athugið að það er ekki sjálfgefið að aðferð Newtons sé samleitin.

Auðvelt er að finna dæmi þar sem vond upphafságiskun \(x_0\) skilar runu sem er ekki samleitin.

2.6. Samanburður á aðferðum

Aðferð	Samleitni	Stig samleitni
Helmingunaraðferð (e. bisection method)	Já, ef \(f(a)f(b)<0\)	1, línuleg
Fastapunktsaðferð (e. fixed point iteration)	Ekki alltaf. En saml. ef \(f\) er herping	amk 1
Sniðilsaðferð (e. secant method)	Ekki alltaf	\(\approx 1,618\), ef \(f'(r)\neq 0\)
Aðferð Newtons (e. Newtons method)	Ekki alltaf	2, ef \(f'(r)\neq 0\)

Aðvörun

Þó að aðferð Newtons sé samleitin af stigi 2, en sniðilsaðferðin af stigi u.þ.b. 1,618, þá er í vissum tilfellum hagkvæmara að nota sniðilsaðferðina ef það er erfitt að reikna gildin á afleiðunni \(f'\).