3. Brúun

Over the centuries, mankind has tried many ways of combating the forces of evil… prayer, fasting, good works and so on. Up until Doom, no one seemed to have thought about the double-barrel shotgun. Eat leaden death, demon. – Terry Pratchett

3.1. Inngangur

3.1.1. Markmiðið

Viðfangsefni þessa kafla er að finna ferla sem ganga gegnum fyrirfram gefna brúunarpunkta \((x_0,y_0),\dots,(x_m,y_m)\) í planinu eða liggja nálægt punktunum í einhverjum skilningi.

Fyrst viljum við finna graf margliðu \(p\) sem fer gegnum punktana. Þá þurfum við að gefa okkur að \(x_i\neq x_j\) ef \(i\neq j\).

Við sýnum fram á að það sé alltaf hægt að finna margliðu \(p\) af stigi \(\leq m\) sem uppfyllir \(p(x_i)=y_i\) í öllum punktum og að slík margliða sé ótvírætt ákvörðuð.

Hún nefnist brúunarmargliða fyrir punktana \((x_0,y_0),\dots,(x_m,y_m)\).

Við alhæfum þetta verkefni með því að úthluta sérhverjum punkti jákvæðri heiltölu \(m_i\) og krefjast þess graf margliðunnar fari í gegnum alla punktana og til viðbótar að allar afleiður \(p^{(j)}\) upp að stigi \(m_i-1\) taki einnig fyrirfram gefin gildi \(y^{(j)}_i\).

3.1.2. Brúun

Við tilraunir þá fáum við oft aðeins strjálar mælingar, t.d. ef við mælum hljóðhraða við mismunandi hitastig. Hins vegar þá viljum við vita hvert sambandið er fyrir öll möguleg hitastig. Brúunin er margliða og hún skilgreind er fyrir allar rauntölur og ``brúar`` því gildin milli mælipunktanna.

3.1.3. Afhverju margliður?

• Einfalt að meta fallgildin fyrir margliður (Reiknirit Horners).

• Einfalt að diffra og heilda margliður.

• Margliður eru óendanlega oft diffranlegar.

• Setning Weierstrass: Látum \(f\) vera samfellt fall á bili \([a,b]\). Fyrir sérhvert \({\varepsilon}> 0\) þá er til margliða \(p\) þannig að

  \[\|f-p\|_\infty := \max_{x\in [a,b]} |f(x)-p(x)| < {\varepsilon}.\]

Athugasemd

Setning Weierstrass segir að margliður nægja til að nálga samfelld föll. Það er sama hvað samfellda fall við skoðum það er alltaf til margliða sem nálgar það eins vel og við viljum á lokuðu bili.

3.1.4. Margliður

Fall \(p\) af gerðinni

\[p(x) = a_0 + a_1 x + \ldots + a_m x^m\]

þar sem \(m\) er heiltala og \(a_0, \ldots, a_m\) eru tvinntölur nefnist margliða.

Stærsta talan \(j\) þannig að \(a_j \not= 0\) nefnist stig margliðunnar \(p\).

Ef allir stuðlarnir eru 0 þá nefnist \(p\) núllmargliðan og við segjum að stig hennar sé \(-\infty\).

Munum að stuðullinn \(a_j\) við veldið \(x^j\) er gefinn með formúlunni

\[a_j = \frac{p^{(j)}(0)}{j!}, \quad j = 0,1,2,\ldots,m.\]

3.1.5. Mismunandi leiðir á framsetningu

Hægt er að setja sömu margliðuna fram á marga mismunandi vegu, en við nefnum framsetninguna hér að framan staðalform margliðunnar \(p\).

Ef við veljum okkur einhvern punkt \(x_0 \in {{\mathbb R}}\), þá getum við skrifað

\[p(x) = b_0 + b_1(x-x_0) + \ldots + b_m(x-x_0)^m\]

og stuðlarnir \(b_j\) eru gefnir með

\[b_j = \frac{p^{(j)}(x_0)}{j!}, \quad j = 0,1,2,\ldots,m.\]

Þessi formúla er jafngild þeirri staðreynd að ef \(p\) er margliða af stigi \(m\). Þá er Taylor-röð \(p\) í sérhverjum punkti \(x_0 \in {{\mathbb R}}\) bara margliðan \(p\), og stuðlarnir í Taylor-röðinni eru gefnir með formúlunum fyrir \(b_j\) að ofan.

3.1.6. Newton-form margliðu

Ef við veljum okkur \(m\) punkta \(x_0, \ldots, x_{m-1}\) þá nefnist framsetning af gerðinni

\[p(x) = c_0 + c_1(x-x_0) + c_2(x-x_0)(x-x_1) + \ldots + c_m(x-x_0)\cdots(x-x_{m-1})\]

Newton-form margliðunnar \(p\) miðað við punktana \(x_0, \ldots, x_{m-1}\).

3.1.7. Reiknirit Horners

Við munum mikið fást við margliður á Newton-formi og því er nauðsynlegt að hafa hraðvirkt reiknirit til þess að reikna út fallgildi \(p\) út frá þessari framsetningu.

Eitt slíkt reiknirit er nefnt reiknirit Horners. Það byggir á því að nýta sér að þættirnir \((x-x_j)\) eru endurteknir í liðunum

\[(x-x_0), \quad (x-x_0)(x-x_1), \quad (x-x_0)(x-x_1)(x-x_2), \quad \ldots\]

Þar sem við sleppum við að hefja í veldi þá komumst við af með fáar reikniaðgerðir hér.

Ef \(m = 2\) má skrifa Newton-form \(p\) sem

\[p(x) = c_0 + (x-x_0)(c_1 + (x-x_1) \cdot c_2).\]

Ef \(m = 3\) er það

\[p(x) = c_0 + (x-x_0)(c_1 + (x-x_1)(c_2 + (x-x_2)c_3))\]

og ef \(m = 4\) er það

\[p(x) = c_0 + (x-x_0)(c_1 + (x-x_1)(c_2 + (x-x_2) (c_3 + c_4(x-x_3)))).\]

Reikniritið vinnur á þessari stæðu með því að margfalda upp úr svigunum frá hægri til vinstri.

Skilgreinum tölur \(b_0\), \(b_1\), \(\ldots\) á eftirfarandi hátt. Fyrst setjum við

\[b_n = c_n.\]

Fyrir hvert \(k\) frá \(n-1\) niður í 0 þá setjum við

\[b_k = c_k + (a - x_k) b_{k+1}.\]

Þá er \(b_0 = p(a)\).

\[p(a) = \underbrace{ c_0 + (a-x_0)( \underbrace{ c_1 + (a-x_1)( \underbrace{c_2 + (a-x_2)( \underbrace{c_3 + (a-x_3) \underbrace{c_4}_{b_4} }_{b_3}) }_{b_2}) }_{b_1}) }_{b_0}.\]

3.2. Margliðubrúun: Lagrange-form

3.2.1. Margliðubrúun

Látum nú \((x_0,y_0), \ldots, (x_m,y_m)\) vera gefna punkta í plani. Við höfum áhuga á að finna margliðu \(p\) af lægsta mögulega stigi þannig að

\[p(x_k) = y_k, \quad k = 0, \ldots, m.\]

Slík margliða nefnist brúunarmargliða fyrir punktana \((x_0,y_0), \ldots, (x_m,y_m)\)

eða brúunarmargliða gegnum punktana \((x_0,y_0), \ldots, (x_m,y_m)\).

Augljóslega verðum við að gera ráð fyrir að \(x\)-hnitin séu ólík, það er \(x_j \not= x_k\) ef \(j \not= k\).

Verkefnið að finna margliðuna \(p\) nefnist brúunarverkefni fyrir punktana \((x_0,y_0), \ldots, (x_m,y_m)\).

3.2.2. Setning: Brúunarmargliðan er ótvírætt ákvörðuð

Brúunarmargliðan af stigi \(\leq m\) fyrir \((x_0,y_0),\ldots,(x_m,y_m)\) er ótvírætt ákvörðuð.

Sönnun

Ef \(p(x)\) og \(q(x)\) eru tvær brúunarmargliður af stigi \(\leq m\) fyrir punktana \((x_0,y_0), \ldots, (x_m,y_m)\) þá er mismunurinn \(r(x) = p(x) - q(x)\) margliða af stigi \(\leq m\) með núllstöðvar \(x_0, \ldots, x_m\). Þetta eru \(m+1\) ólíkir punktar og því er \(r(x)\) núllmargliðan samkvæmt undirstöðusetningu algebrunnar. Þar með er \(p(x) - q(x)\) núllmargliðan, þ.e. \(p(x) = q(x)\).

3.2.3. Setning: Brúunarmargliðan er til

Til er margliða \(p\) af stigi \(\leq m\) þannig að

\[p(x_0) = y_0, \quad \ldots \quad p(x_n)=y_n.\]

Sönnun

Við notum þrepun til að sýna fram á tilvistina.

Ef \(m = 0\), þá erum við aðeins með eitt brúunarskilyrði, \(p(x_0) = y_0\), og fastamargliðan \(p(x) = y_0\) er lausn af stigi \(\leq 0\).

G.r.f. að við getum leyst öll brúunarverkefni þar sem fjöldi punkta er \(m\) og sýnum að við getum þá leyst verkefnið fyrir \(m+1\) punkt.

Látum \(q\) vera brúunarmargliðuna af stigi \(\leq m-1\) fyrir punktana \((x_0,y_0), \ldots, (x_{m-1},y_{m-1})\) og \(r\) vera brúunarmargliðuna af stigi \(\leq m-1\) fyrir punktana \((x_1,y_1), \ldots, (x_m,y_m)\) og setjum síðan

\[p(x) = \frac{x-x_m}{x_0-x_m}q(x) + \frac{x-x_0}{x_m-x_0}r(x),\]

\(p(x)\) er greinilega margliða af stigi \(\leq m\). Skoðum nú gildin á \(p\)

\[\begin{split}\begin{aligned} p(x_0) &= 1 \cdot q(x_0) + 0\cdot r(x_0) = y_0, \\ p(x_k) &= \frac{x_k-x_m}{x_0-x_m}y_k + \frac{x_k-x_0}{x_m-x_0}y_k = y_k,\qquad k = 1, \ldots, m-1,\\ p(x_m) &= 0 \cdot q(x_m) + 1 \cdot r(x_m) = y_m.\end{aligned}\end{split}\]

Þar með er \(p\) brúunarmargliðan sem uppfyllir \(p(x_j)=y_j\) fyrir \(j=0,\dots,m\) og við höfum leyst brúunarverkefnið fyrir \(m+1\) punkt.

3.2.4. Lagrange-form brúunarmargliðunnar

Sönnunin á undan er í raun rakningarformúla til þess að reikna út gildi brúunarmargliðunnar \(p\) fyrir punktana \((x_0,y_0),\dots,(x_m,y_m)\).

Hægt er að skrifa lausnina niður beint

\[p(x)=y_0\ell_0(x)+y_1\ell_1(x)+\cdots+y_m\ell_m(x),\]

þar sem \(\ell_0,\dots,\ell_m\) er ákveðinn grunnur fyrir rúm allra margliða \({\cal P}_m\) af stigi \(\leq m\) og nefnast Lagrange-margliður fyrir punktasafnið \((x_0,y_0),\dots,(x_m,y_m)\).

3.2.5. Lagrange-margliður, tilfellin \(m=0,1,2\)

• \(m=0\) Ef \(m = 0\) þá er \(p(x) = y_0\) fastamargliða eins og við höfum séð.

• \(m=1\) Ef \(m = 1\), þá blasir við að lausnin er

  \[p(x) = y_0 \frac{(x-x_1)}{(x_0-x_1)} + y_1 \frac{(x-x_0)}{(x_1-x_0)},\]

  sem er margliða af stigi \(\leq 1\) (þ.e. lína) sem leysir brúunarverkefnið.

• \(m=2\) Á hliðstæðan hátt fáum við fyrir \(m = 2\) að

  \[p(x) = y_0 \frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1 \frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2 \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}\]

  leysir brúunarverkefnið.

3.2.6. Lagrange-margliður almenna tilfellið

Almennt fæst lausnin

\[\label{p} p(x) = y_0 \, \ell_{0}(x) + y_1 \, \ell_{1}(x) + \ldots + y_m \, \ell_{m}(x)\]

þar sem

\[\ell_{k} = \prod\limits_{\stackrel{j=0}{j\not=k}}^m \frac{(x-x_j)}{(x_k-x_j)}\]

Athugasemd

\[\begin{split}\label{l} \ell_{k}(x_i) = \left\{ \begin{array}{cc} 1 & \text{ef } i = k \\ 0 & \text{ef } i \not= k \end{array} \right.\end{split}\]

Allar margliðurnar \(\ell_{k}\) eru af stigi \(m\) og því er \(p\) af stigi \(\leq m\). Nú er augljóst útfrá ([p]) og ([l]) að \(p\) er lausn brúunarverkefnisins.

3.2.7. Sýnidæmi

Finnið brúunarmargliðuna gegnum punktana \((1,1)\), \((2,3)\) og \((3,6)\) með því að nota Lagrange-margliður.

Sönnun

Reiknum fyrst margliðurnar \(\ell_{0}\), \(\ell_{1}\) og \(\ell_{2}\):

\[\begin{split}\begin{aligned} \ell_{0} &= \frac{(x-2)(x-3)}{(1-2)(1-3)} = \frac{(x-2)(x-3)}{2} \\ \ell_{1} &= \frac{(x-1)(x-3)}{(2-1)(2-3)} = -(x-1)(x-3) \\ \ell_{2} &= \frac{(x-1)(x-2)}{(3-1)(3-2)} = \frac{(x-1)(x-2)}{2}\end{aligned}\end{split}\]

Þá fæst að brúunarmargliðan \(p\) er

\[p(x) = 1 \cdot \frac{(x-2)(x-3)}{2} - 3 \cdot (x-1)(x-3) + 6 \cdot \frac{(x-1)(x-2)}{2}\]

Þetta er greinilega annars stigs margliða og auðvelt er að sannfæra sig um að \(p(1) = 1\), \(p(2) = 3\) og \(p(3) = 6\).

3.3. Margliðubrúun: Newton-form

3.3.1. Formúla fyrir \(c_0, \ldots, c_m\)

Nú ætlum við að leiða út formúlu fyrir stuðlunum \(c_0, \ldots, c_m\) í Newton-formi brúunarmargliðunnar \(p\) miðað við röð brúunarpunktanna \(x_0, \ldots, x_{m-1}\).

Athugum að \(c_m = a_m\), þar sem \(a_m\) er stuðullinn við veldið \(x^m\) í staðalframsetningunni á \(p\).

Til þess að reikna út \(c_0, \ldots, c_m\) þurfum við að reikna út með skipulegum hætti stuðulinn við veldið \(x^j\) í brúunarmargliðunni gegnum punktana \((x_i,y_i), \ldots, (x_{i+j},y_{i+j})\), fyrir öll \(i = 0, \ldots, m\) og \(j = 0, \ldots, m-i\). Við táknum þennan stuðul með \(y[x_i, \ldots, x_{i+j}]\).

Aðvörun

Verkefnið er háð röð punktanna, þ.e. framsetningin (Newton-formið) á margliðunni breytist eftir röð punktanna. En auðvitað er margliðan og gildin á henni alltaf þau sömu

Dæmi: Skoðum margliðuna \(p(x) = 2-7x+5x^2\).

Ef \(x_0=0\) og \(x_1=2\) þá er Newton-form hennar

\[p(x) = 3 + 3(x-0) + 5(x-0)(x-2).\]

En ef \(x_0=2\) og \(x_1=0\) þá er Newton-form hennar

\[p(x) = 8 + 3(x-2) + 5(x-2)(x-0).\]

3.3.2. Mismunakvótar

Skilgreinum mismunakvóta \(y[x_i,\ldots,x_{i+j}]\) fyrir punktasafnið \((x_i,y_i),\ldots,(x_{i+j},y_{i+j})\) á eftirfarandi hátt:

• \(j=0\): \(y[x_i] = y_i\).

• \(j=1\): \(y[x_i,x_{i+1}] = \frac{y_{i+1}-y_i}{x_{i+1}-x_i}\)

• \(j=2\): \(y[x_i,x_{i+1},x_{i+2}] = \frac{y[x_{i+1},x_{i+2}] - y[x_i,x_{i+1}]}{x_{i+2}-x_i}\).

• \(j>2\): \(y[x_i,\ldots,x_{i+j}] = \frac{y[x_{i+1},\ldots,x_{i+j}] - y[x_i,\ldots,x_{i+j-1}]}{x_{i+j}-x_i}\).

Athugasemd

Stærðin \(y[x_{n-1},x_n]\) hefur komið fyrir áður hjá okkur þegar við fjölluðum um Sniðilsaðferð, enda er sniðill ekkert annað en brúunarmargliða fyrir tvö punkta í planinu.

3.3.3. Upprifjun á tilvistarsönnuninni

Þrepunarskrefið í tilvistarsönnuninni fyrir brúunarmargliður gefur okkur nú hvernig mismunakvótarnir nýtast okkur.

Látum \(q\) vera brúunarmargliðuna af stigi \(\leq m-1\) fyrir punktana \((x_0,y_0), \ldots, (x_{m-1},y_{m-1})\) og \(r\) vera brúunarmargliðuna af stigi \(\leq m-1\) fyrir punktana \((x_1,y_1), \ldots, (x_m,y_m)\) og setjum síðan

\[p(x) = \frac{x-x_m}{x_0-x_m}q(x) + \frac{x-x_0}{x_m-x_0}r(x)\]

Gerum nú ráð fyrir að stuðullinn við veldið \(x^{m-1}\) í \(q(x)\) sé \(y[x_0, \ldots, x_{m-1}]\) og stuðullinn við veldið \(x^{m-1}\) í \(r(x)\) sé \(y[x_1, \ldots, x_m]\).

Við sjáum þá að stuðullinn við veldið \(x^m\) í \(p(x)\) er

\[\frac{y[x_0, \ldots, x_{m-1}]}{x_0-x_m} + \frac{y[x_1, \ldots, x_m]}{x_m - x_0} = y[x_0, \ldots, x_m]\]

Athugasemd

Fyrir \(m=0\) gildir að \(p(x) = y_0 = y[x_0]\).

3.3.4. Mismunakvótatöflur fyrir \(m=0,1,2,3\)

Mismunakvótar eru venjulega reiknaðir út í svokölluðum mismunakvótatöflum.

Tilfellið \(m=0\)

Ef \(m = 0\) er mismunakvótataflan aðeins ein lína

\[\begin{split}\begin{array}{c|c|c} i & x_i & y[x_i] \\ \hline 0 & x_0 & y[x_0] = y_0 \end{array}\end{split}\]

Tilfellið \(m=1\)

Ef \(m = 1\) er taflan

\[\begin{split}\begin{array}{c|c|cc} i & x_i & y[x_i] & y[x_i,x_{i+1}] \\ \hline 0 & x_0 & y[x_0] = y_0 & y[x_0,x_1] \\ 1 & x_1 & y[x_1] = y_1 & \end{array}\end{split}\]

og margliðan er

\[p(x) = y[x_0] + y[x_0,x_1](x-x_0).\]

Tilfellið \(m=2\)

Ef \(m = 2\) verður taflan

\[\begin{split}\begin{array}{c|c|ccc} i & x_i & y[x_i] & y[x_i,x_{i+1}] & y[x_i,x_{i+1},x_{i+2}] \\ \hline 0 & x_0 & y[x_0] = y_0 & y[x_0,x_1] & y[x_0,x_1,x_2] \\ 1 & x_1 & y[x_1] = y_1 & y[x_1,x_2] & \\ 2 & x_2 & y[x_2] = y_2 & & \end{array}\end{split}\]

og margliðan er

\[p(x) = y[x_0] + y[x_0,x_1](x-x_0) + y[x_0,x_1,x_2](x-x_0)(x-x_1).\]

Tilfellið \(m=3\)

Skoðum loks tilfellið \(m = 3\)

\[\begin{split}\begin{array}{c|c|cccc} i & x_i & y[x_i] & y[x_i,x_{i+1}] & y[x_i,x_{i+1},x_{i+2}] & y[x_i,x_{i+1},x_{i+2},x_{i+3}] \\ \hline 0 & x_0 & y[x_0] = y_0 & y[x_0,x_1] & y[x_0,x_1,x_2] & y[x_0,x_1,x_2,x_3] \\ 1 & x_1 & y[x_1] = y_1 & y[x_1,x_2] & y[x_1,x_2,x_3] & \\ 2 & x_2 & y[x_2] = y_2 & y[x_2,x_3] & & \\ 3 & x_3 & y[x_3] = y_3 & & & \end{array}\end{split}\]

Brúunarmargliðan fæst svo með því að nota stuðlana úr fyrstu línu töflunnar:

\[\begin{split}\begin{aligned} p(x) = &y[x_0] + y[x_0,x_1](x-x_0) + y[x_0,x_1,x_2](x-x_0)(x-x_1) \\ &+ y[x_0,x_1,x_2,x_3](x-x_0)(x-x_1)(x-x_2)\end{aligned}\end{split}\]

3.3.5. Sýnidæmi

Við skulum reikna út aftur brúunarmargliðuna gegnum \((1,1)\), \((2,3)\) og \((3,6)\).

Lausn

Stillum fyrst upp mismunakvótatöflu

\[\begin{split}\begin{array}{cc||ccc} i & x_i & y[x_i] & y[x_i,x_{i+1}] & y[x_i,x_{i+1},x_{i+2}] \\ \hline 0 & 1 & 1 & & \\ 1 & 2 & 3 & & \\ 2 & 3 & 6 & & \end{array}\end{split}\]

Fyllum svo út í hana með að ganga á hvern dálk á fætur öðrum

\[\begin{split}\begin{array}{cc||ccc} i & x_i & y[x_i] & y[x_i,x_{i+1}] & y[x_i,x_{i+1},x_{i+2}] \\ \hline 0 & 1 & 1 & \dfrac{3-1}{2-1} = 2 & \dfrac{3-2}{3-1} = 1/2 \\ 1 & 2 & 3 & \dfrac{6-3}{3-2} = 3 & \\ 2 & 3 & 6 & & \end{array}\end{split}\]

Lesum út brúunarmargliðuna \(p\) með að ganga á efstu línuna:

\[p(x) = 1 + 2 \cdot (x-1) + \frac{1}{2} \cdot (x-1)(x-2).\]

Reiknum út brúunarmargliðuna gegnum \((3,1)\), \((1,-3)\), \((5,2)\) og \((6,4)\). Stillum upp og fyllum út í mismunakvótatöflu:

\[\begin{split}\begin{array}{cc||cccc} i & x_i & y[x_i], & y[x_i,x_{i+1}], & y[x_i,x_{i+1},x_{i+2}], & y[x_i,\ldots,x_{i+3}] \\ \hline 1 & 3 & 1 & \frac{-3-1}{1-3} = 2 & \frac{5/4-2}{5-3} = -3/8 & \frac{3/20-(-3/8)}{6-3} = 7/40 \\ 2 & 1 & -3 & \frac{2-(-3)}{5-1} = 5/4 & \frac{2-5/4}{6-1} = 3/20 & \\ 3 & 5 & 2 & \frac{4-2}{6-5} = 2 & & \\ 4 & 6 & 4 & & & \end{array}\end{split}\]

Nú getum við lesið brúunarmargliðuna okkar úr töflunni með að ganga á efstu línuna, við fáum

\[p(x) = 1 + 2(x-3) - \frac 38 (x-3)(x-1) + \frac 7{40} (x-3)(x-1)(x-5)\]

3.3.6. Samantekt

Ef gefnir eru punktar \((x_0,y_0), \ldots, (x_m,y_m)\) í \({{\mathbb R}}^2\), þar sem \(x_i\neq x_j\) ef \(i\neq j\), þá er til nákvæmlega ein margliða \(p\) af stigi \(\leq m\) þannig að

\[p(x_k) = y_k, \quad k = 0, \ldots, m\]

Newton-form margliðunnar \(p\) með tilliti til punktanna \(x_0,\dots,x_{m-1}\) er

\[p(x)=y[x_0]+y[x_0,x_1](x-x_0)+\cdots+y[x_0,\dots,x_m](x-x_0)\cdots(x-x_m)\]

þar sem mismunakvótarnir eru reiknaðir með rakningarformúlunum \(y[x_i]=y_i\) og

\[y[x_i,\ldots,x_{i+j}] = \frac{y[x_{i+1},\ldots,x_{i+j}] - y[x_i,\ldots,x_{i+j-1}]} {x_{i+j} - x_i}, \qquad i=0,\dots,m, \quad j=0,\dots,m-i.\]

3.3.7. Samantekt – Newton-form

Venja er að setja mismunakvótana upp í töflu og stuðlarnir í Newton-forminu raða sér í fyrstu línu töflunnar:

\[\begin{split}\begin{array}{c|c|cccccc} i & x_i & y[x_i] & y[x_i,x_{i+1}] & y[x_i,x_{i+1},x_{i+2}] & y[x_i,\dots,x_{i+3}] &y[x_i,\dots,x_{i+4}] &\dots \\ \hline 0 & x_0 & y[x_0] = y_0 & y[x_0,x_1] & y[x_0,x_1,x_2] & y[x_0,x_1,x_2,x_3]&y[x_0,x_1,x_2,x_3,x_4]& \dots \\ 1 & x_1 & y[x_1] = y_1 & y[x_1,x_2] & y[x_1,x_2,x_3] & y[x_1,x_2,x_3,x_4]&\dots \\ 2 & x_2 & y[x_2] = y_2 & y[x_2,x_3] &y[x_2,x_3,x_4]&\dots & \\ 3 & x_3 & y[x_3] = y_3 & y[x_3,x_4] &\dots & & \\ 4 & x_4 & y[x_4] = y_4 & \dots & \\ \vdots & \vdots &\vdots \end{array}\end{split}\]

3.3.8. Samantekt – Lagrange-margliður

Lagrange-form brúunarmargliðunnar er

\[p(x)=\sum_{k=0}^m y_k\ell_{k}(x)\]

þar sem \(\ell_{k}\) eru Lagrange-margliðurnar með tilliti til punktanna \(x_0,\dots,x_m\),

\[ \begin{align}\begin{aligned}\begin{split} \ell_{k}(x) = \prod_ {\substack{j=0\\ j\neq k}}^m\dfrac{(x-x_j)}{(x_k-x_j)} = \dfrac{(x-x_0)\cdots(x-x_{k-1}) (x-x_{k+1})\cdots(x-x_m)} {(x_k-x_0)\cdots(x_k-x_{k-1}) (x_k-x_{k+1})\cdots(x_k-x_m)}.\end{split}\\En þær uppfylla\end{aligned}\end{align} \]

\[\begin{split}\ell_{k}(x_i) = \left\{ \begin{array}{cc} 1 & \text{ef } i = k \\ 0 & \text{ef } i \not= k \end{array} \right.\end{split}\]

3.4. Samantekt

3.4.1. Lagrange-margliður

• Auðvelt að finna margliðuna

• Dýrara að reikna fallgildin

3.4.2. Newton-margliður

• Erfiðara að finna margliðuna

• Auðvelt að finna fallgildin (reiknirit Horners)

3.5. Margliðubrúun: Margfaldir punktar

Látum \(a_1, \ldots, a_k\) vera ólíka punkta í \({{\mathbb R}}\), \(m_1, \ldots, m_k\) vera jákvæðar heiltölur og hugsum okkur að gefnar séu rauntölur

\[y_i^{(j)}, \quad j = 0, \ldots, m_i-1, \quad i = 1, \ldots, k.\]

Við viljum finna margliðu \(p\) af lægsta mögulega stigi þannig að margliðan \(p=p^{(0)}\) og afleiður hennar \(p^{(j)}\) uppfylli

\[p^{(j)}(a_i) = y_i^{(j)}, \quad j = 0, \ldots, m_i-1, \quad i = 1, \ldots, k\]

Við nefnum verkefnið að finna slíka margliðu \(p\) alhæft brúunarverkefni, og margliða sem uppfyllir þessi skilyrði nefnist brúunarmargliða fyrir brúunarverkefnið sem lýst er með gefnu skilyrðunum.

3.5.1. Margfeldni punktanna

Við segjum að \(a_i\) sé einfaldur brúunarpunktur ef \(m_i=1\), tvöfaldur brúunarpunktur ef \(m_i=2\) o.s.frv.

Við skilgreinum nú töluna

\[m = m_1 + m_2 + \ldots + m_k - 1.\]

Brúunarmargliðan okkar \(p\) á að vera af stigi \(\leq m\), og fjöldi skilyrða sem við setjum á hana eru \(m+1\).

Athugasemd

Tilfellið \(k=m+1\), \(m_j=1\) er það sem við skoðuðum hér á undan.

3.5.2. Sértilfelli

Tvö sértilfelli þekkjum við nú þegar.

1. Allir punktar eins: Ef allir punktarnir eru einfaldir, þá er alhæfða brúunarverkefnið sama verkefni og brúunarverkefnið sem við leystum í Margliðubrúun: Lagrange-form og Margliðubrúun: Newton-form.

   \[p^{(0)}(a_i) = p(a_i) = y_i^{(0)},\]

   og lausnin var leidd út með

   \[x_0=a_1,\dots,x_m=a_k \quad \text{ og } \quad y_0=y_1^{(0)},\dots,y_m=y_k^{(0)}.\]

2. Einn punktur: Ef aftur á móti \(k = 1\), þá er lausn gefin með Taylor-margliðunni af röð \(m\) í punktinum \(a_1\)

   \[p(x) = y_1^{(0)} + \frac{y'}{1!}(x - a_1) + \frac{y''}{2!}(x - a_1)^2 + \ldots + \frac{y_1^{(m)}}{m!}(x - a_1)^m.\]

3.5.3. Upprifjun

Munum að ef \(p\) er margliða og \(p(a)=0\) þá er \(p\) deilanleg með \((x-a)\). Það er, hægt er að skrifa

\[p(x) = (x-a)q(x),\]

þar sem \(q\) er margliða af stigi sem er einu lægra en stig \(p\) (sjá Undirstöðusetning algebrunnar).

3.5.4. Ótvíræðni lausnarinnar

Nú ætlum við að sýna fram á að til sé nákvæmlega ein margliða \(p(x)\) af stigi \(\leq m\) sem uppfyllir

\[p^{(j)}(a_i) = y_i^{(j)}, \quad j = 0, \ldots, m_i-1, \quad i = 1, \ldots, k\]

Byrjum á að sýna að það er í mesta lagi ein margliða sem uppfyllir þetta.

Sönnun

Gerum ráð fyrir að \(p(x)\) og \(q(x)\) séu tvær margliður af stigi \(\leq m\) sem uppfylla öll þessi skilyrði.

Þá uppfyllir margliðan \(r(x) = p(x) - q(x)\) að

\[r^{(j)}(a_i) = 0, \quad j = 0, \ldots, m_i-1, \quad i = 1, \ldots,k\]

Af þessu leiðir að \(r(x)\) er deilanlegt með \((x-a_i)^{m_i}\) en samanlagt stig þessara þátta er \(m_1 + \ldots + m_k = m + 1\).

Nú er stig \(r(x)\) minna eða jafnt \(m\) svo þetta getur aðeins gerst ef \(r(x)\) er núllmargliðan.

Við höfum því að \(p(x) = q(x)\) og ályktum að við höfum nákvæmlega eina lausn á brúunarverkefninu ef við getum sýnt fram á tilvist á lausn.

3.5.5. Tilvist á lausn

Nú beitum við sams konar röksemdafærslu og í byrjum kaflans til þess að sýna fram á tilvist á lausn, þ.e. við notum þrepun.

Sönnun

Smíðum margliðuna:

Ef \(m = 0\), þá er lausnin fastamargliðan \(p(x) = y_1^{(0)}=y_0\).

Gerum nú ráð fyrir að við getum fundið brúunarmargliðu af stigi \(\leq m-1\) fyrir sérhvert alhæft brúunarverkefni þar sem samanlagður fjöldi skilyrðanna er \(m\).

Lítum nú aftur á upprunalega brúunarverkefnið þar sem fjöldi skilyrðanna er \(m+1\). Skilgreinum tvær runur af punktum

\[(x_0,x_1,\ldots,x_m) = (\underbrace{a_1, \ldots, a_1}_{m_1 \, \text{sinnum}}, \underbrace{a_2, \ldots , a_2}_{m_2 \, \text{sinnum}}, \ldots , \underbrace{a_k, \ldots , a_k}_{m_k \, \text{sinnum}})\]

og

\[(y_0,y_1,\ldots,y_m) = (y_1^{(0)}, \ldots, y_1^{(m_1-1)}, \ldots, y_k^{(0)}, \ldots, y_k^{(m_k-1)})\]

Við höfum séð að í því tilfelli að við höfum einn punkt, \(k=1\), \(x_0 = x_1 = \ldots = x_m = a_1\) er lausnin gefin með Taylor-margliðu í \(a_1\).

Við megum því gera ráð fyrir punktarnir séu a.m.k. tveir, \(k\geq 2\). Það gefur að \(x_0 \not= x_m\).

Látum \(q(x)\) vera margliðuna af stigi \(\leq m-1\) sem uppfyllir sömu skilyrði og \(p\), nema það síðasta um að \(q^{(m_k-1)}(a_k)\) þurfi að vera \(y_k^{(m_k-1)}\) .

og látum \(r(x)\) vera margliðuna sem uppfyllir öll brúunarskilyrðin, nema síðasta skilyrðið í fyrsta punkti um að \(r^{(m_1-1)}(a_1)\) sé jafnt \(y_1^{(m_1-1)}\).

Setjum síðan

\[p(x) = \frac{x-x_m}{x_0-x_m}q(x) + \frac{x-x_0}{x_m-x_0}r(x) = \frac{x-a_k}{a_1-a_k}q(x) + \frac{x-a_1}{a_k-a_1}r(x)\]

Sýnum að gefin fallgildi eru tekin

Nú þurfum við að staðfesta að öll skilyrðin séu uppfyllt.

Við byrjum á því að taka \(j=0\) sem svarar til þess að \(p\) taki fyrirfram gefin fallgildi,

\[\begin{split}\begin{aligned} p(a_1) &= \frac{a_1-a_k}{a_1-a_k}q(a_1) + \frac{a_1-a_1}{a_k-a_1}r(a_1) = q(a_1) = y_1^{(0)}\\ p(a_i) &= \frac{a_i-a_k}{a_1-a_k}q(a_i) + \frac{a_i-a_1}{a_k-a_1}r(a_i) = \left( \frac{a_i-a_k}{a_1-a_k} + \frac{a_i-a_1}{a_k-a_1} \right) y_i^{(0)} \\ &= y_i^{(0)}, \qquad \text{fyrir } i=2,\ldots,k-1,\\ p(a_k) &= \frac{a_k-a_k}{a_1-a_k}q(a_k) + \frac{a_k-a_1}{a_k-a_1}r(a_k) = r(a_k) = y_k^{(0)}.\end{aligned}\end{split}\]

Sýnum svo að gildin á afleiðum \(p\) séu rétt.

Rifjum upp margliðuna \(p\):

\[p(x) = \frac{x-x_m}{x_0-x_m}q(x) + \frac{x-x_0}{x_m-x_0}r(x) = \frac{x-a_k}{a_1-a_k}q(x) + \frac{x-a_1}{a_k-a_1}r(x)\]

Afleiður hennar eru

\[p^{(j)}(x) = \frac{(x-a_k)}{(a_1-a_k)}q^{(j)}(x) + \frac{(x-a_1)}{(a_k-a_1)}r^{(j)}(x) + j \frac{\left( q^{(j-1)}(x)-r^{(j-1)}(x)\right)}{a_k-a_1}\]

Ef nú \(m_i > 1\) þá er \(q^{(j-1)}(a_i) = y^{(j-1)}(a_i) = r^{(j-1)}(a_i)\) fyrir \(j = 1, \ldots, m_i-1\) og því kemur alltaf \(0\) út úr síðasta liðnum ef við setjum inn \(x = a_i\), fyrir öll \(i = 1, \ldots, k\).

Af þessu sést að afleiður \(p\) uppfylla skilyrðin

\[p^{(j)}(a_i) = y^{(j)}_i, \qquad \text{fyrir } j=0,\ldots,m_i-1, \quad i=1,\ldots,k.\]

3.5.6. Samantekt

Við höfum því sannað eftirfarandi:

Ef gefnar eru

• rauntölur \(a_1,\dots,a_k\), með \(a_j\neq a_k\) ef \(j\neq k\),

• jákvæðar heiltölur \(m_1,\dots,m_k\),

• rauntölur \(y_i^{(j)}\), fyrir \(j=0,\dots, m_i-1\), \(i=1,\dots,k\),

og talan \(m\) er skilgreind með \(m=m_1+\cdots+m_k-1\), þá er til nákvæmlega ein margliða \(p\) af stigi \(\leq m\) þannig að

\[p^{(j)}(a_i)=y_i^{(j)}, \qquad j=0,\dots, m_i-1, \quad i=1,\dots,k.\]

3.5.7. Brúunarmargliðan fundin

Ef skilgreindar eru runurnar

\[(x_0,\dots,x_m)=(a_1,\dots,a_1,a_2,\dots,a_2,\dots,a_k,\dots,a_k)\]

þar sem \(a_1\) kemur fyrir \(m_1\) sinnum, \(a_2\) kemur fyrir \(m_2\) sinnum o.s.frv., og

\[(y_0,\dots,y_m)=(y_1^{(0)},\cdot\cdot,y_1^{(m_1-1)},y_2^{(0)},\cdot\cdot,y_2^{(m_2-1)}, \cdots,y_k^{(0)},\cdot\cdot,y_k^{(m_k-1)}),\]

þá er Newton-form margliðunnar \(p\) með tilliti til punktanna \(x_0,\dots,x_{m-1}\) gefið með

\[p(x)=y[x_0]+y[x_0,x_1](x-x_0)+\cdots+y[x_0,\dots,x_m](x-x_0)\cdots(x-x_{m-1})\]

þar sem mismunakvótarnir \(y[x_i,\ldots,x_{i+j}]\) eru reiknaðir með rakningarformúlu þannig að \(y[x_i]=y_i\) og

\[\begin{split}y[x_i,\ldots,x_{i+j}] = \begin{cases}\dfrac{y[x_{i+1},\ldots,x_{i+j}] - y[x_i,\ldots,x_{i+j-1}]} {x_{i+j} - x_i}, &\text{ ef } x_i\neq x_{i+j},\\ \dfrac{y^{(j)}_i}{j!}, &\text{ ef } x_i=x_{i+j}. \end{cases}\end{split}\]

3.6. Skynsamlegir skiptipunktar og Chebyshev margliður

3.6.1. Um val á brúunarpunktum

Látum \((t_0,y_0),\dots,(t_n,y_n)\) vera punkta í plani og gerum ráð fyrir að \(a=t_0<t_1<\cdots<t_n=b\).

Við höfum nú lært að ákvarða margliðu \(p\) af stigi \(\leq n\) sem tekur gildin \(y_i\) í punktunum \(t_i\).

Ef punktarnir liggja á grafi fallsins \(f\) og nota á margliðuna til þess að nálga fallgildi \(f\), þá getur það verið ýmsum erfiðleikum bundið þegar stig hennar stækkar. Til dæmis getur komið fram óstöðugleiki í útreikningum þannig að örlítil frávik í \(x\) geta leitt til mikilla frávika í \(p(x)\), og þá hugsanlega í mikilli skekkju á \(f(x)-p(x)\).

3.6.2. Dæmi um óheppilega skiptipunkta

Skoðum dæmi þar sem við brúum fallið \(f(x) = 1/(25x^2+1)\) í 9 brúnarpunktum sem eru jafndreifðir á bilinu \([-1,1]\).

Hér sjáum við ,,þægilegt“ fall þar sem brúunarmargliðan gefur afskaplega vonda nálgun.

3.6.3. Val á brúunarpunktum

Það er ekki sjálfgefið að við getum valið í hvaða brúunarpunkta við notum, t.d. ef þeir ákvarðast af mælingum. Ef við hins vegar getum valið þá óhindrað, þá vaknar sú spurning hvernig er best að gera það?

3.6.4. Skilgreining

Fyrst þurfum við að útskýra betur hvað við eigum við með ,,best”. Við munum bara notast við tvær leiðir hér til að mæla skekkjuna, en það er \(\ell_\infty\) og \(\ell_2\) staðlarnir, fyrir samfellt fall \(h\) á bilinu \([a,b]\) þá eru þeir skilgreindir með

\[\|h\|_\infty = \max_{x\in[a,b]} |h(x)|,\]

og

\[\|h\|_2 = \left( \int_a^b h(x)^2\, dx \right)^\frac 12\]

Athugasemd

Það má líta þannig á þetta að \(\ell_\infty\) staðallinn mæli hámarksskekkju og \(\ell_2\) mæli einhvers konar,,meðaltalsskekkju“, þar sem meðaltalið er reiknað með heildi.

3.6.5. Verkefnið

Verkefnið er því eftirfarandi: Fyrir gefið fall \(f(x)\) á bili \([a,b]\) og fast \(n\), þá viljum við finna \(x_0,\ldots,x_n\) sem lágmarka annað hvort

\[\|f-p\|_\infty \quad \text{ eða } \quad \|f-p\|_2.\]

Þar sem \(p\) er brúunarmargliðan fyrir brúunarpunktana \((x_i,f(x_i))\).

Byrjum á að skoða \(\ell_\infty\) tilvikið.

3.6.6. Skilgreining: Chebyshev margliður

Fyrir náttúrlega tölu \(n\) þá skilgreinum við Chebyshev margliðuna \(T_n\) á \([-1,1]\) með

\[T_n(x) = \cos(n \arccos(x)).\]

Með því að setja inn \(n=0\) og \(n=1\) þá fæst að

\[T_0(x) = 1 \quad \text{ og } \quad T_1(x) = x,\]

og með hornafallareglunum fæst að

\[T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x), n \geq 1.\]

Af jöfnunni hér á undan þá fæst með þrepun að

• \(T_n(x)\) er margliða af stigi \(n\).

• Forystustuðull \(T_n\) er \(2^{n-1}\).

• \(T_n\) er jafnstæð ef \(n\) er slétt og oddstæð ef \(n\) er oddatala.

3.6.7. Setning

Chebyshev margliðan \(T_n\) hefur \(n\) einfaldar núllstöðvar á bilinu \([-1,1]\) og þær eru gefnar með

\[x_j = \cos\left(\frac{2j+1}{2n}\pi\right),\qquad j=0,1,2,3,\ldots,n-1.\]

Auk þess eru útgildi \(T_n\) á \([-1,1]\) staðsett í

\[z_j = \cos\left( \frac{j\pi}{n}\right),\qquad j=0,1,2,\ldots,n,\]

og fallgildin þar uppfylla \(T_n(z_j) = (-1)^j\)

3.6.8. Staðlaðar Chebyshev margliður

Margliða er kölluð stöðluð ef forystustuðull hennar er 1.

Stöðluðu Chebyshev margliðurnar \(\tilde T\) eru skilgreindar á eftirfarandi hátt

\[\begin{split}\tilde T(x) = \begin{cases} T_0(x) & \text{ef } n = 0 \\ 2^{1-n}T_n(x) & \text{ef } n\geq 1 \end{cases}\end{split}\]

Fyrir sérhverja staðlaða margliðu \(q\) af stigi \(n\) þá er

\[\frac 1{2^{n-1}} = \max_{x\in [-1,1]} T_n(x) \leq \max_{x\in[-1,1]} |q(x)|.\]

Þ.e. af öllum stöðluðum margliðum þá eru stöðluðu Chebyshev margliðurnar ,,minnstar” á bilinu \([-1,1]\).

3.6.9. Skynsamlegir skiptipunktar fyrir bilið \([-1,1]\)

Við vitum að skekkjan í því að nálga fallið \(f\) með brúunarmargliðu \(p\) með brúunarpunkta \(x_0,\ldots,x_n\) er

\[f(x)-p(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\, (x-x_0)(x-x_1)\cdots (x-x_n),\]

þar sem \(\xi\) er á minnsta bilinu sem inniheldur \(x\) og \(x_0,x_1,\ldots,x_n\). Ef við skoðum jöfnuna að ofan þá sjáum við að þar sem \(n\) og \(f\) (og þar með \(f^{(n+1)}\)) er fast þá er stæðan \((x-x_0)\cdots(x-x_n)\) það eina sem við höfum einhverja stjórn á.

Með því að nota Chebyshev margliðurnar þá getum við lágmarkað þennan hluta skekkjunnar.

Athugið að \((x-x_0)\cdots (x-x_n)\) er stöðluð margliða af stigi \(n+1\). Þannig að samkvæmt því sem kom fram hér að ofan þá lágmörkum við framlag hennar til skekkjunnar með \((x-x_0)\cdots (x-x_n) = \tilde T_{n+1}\), þ.e. með því að velja

\[x_i = \cos\left(\frac{2i+1}{2(n+1)}\pi\right), \qquad i=0,1,\ldots,n.\]

Hæsta gildi \(\tilde T_{n+1}\) er \(\frac 1{2^n}\), sem þýðir að við fáum skekkjumatið

\[\|f(x)-p(x)\|_\infty \leq \frac{\|f^{(n+1)}\|_\infty}{2^n(n+1)!}.\]

3.6.10. Dæmi um óheppilega skiptipunkta skoðað aftur

Skoðum aftur fallið \(f(x) = 1/(25x^2+1)\), en í stað þess að taka 9 jafndreifaða brúunarpunkta á bilinu \([-1,1]\), þá skulum við nota Chebyshev margliðurnar til að finna 9 punkta á bilinu.

3.6.11. Skynsamlegir skiptipunktar fyrir bil \([a,b]\)

Hér á undan miðaðist allt við að finna brúunarmargliðu fyrir fallið \(f\) á bilinu \([-1,1]\). Ef við viljum skoða almennt bil \([a,b]\) þá byrjum við á athuga að fallið \(\eta:[-1,1]\to [a,b]\),

\[\eta(t) = \frac{b-a}2 t + \frac{b+a}2\]

skilgreinir línulega vörpun (hliðrun og stríkkun) frá \([-1,1]\) yfir á \([a,b]\). Athugið að vörpunin sendir \(-1\) í \(a\) og \(1\) í \(b\).

Með því að taka rætur stöðluðu Chebyshev margliðunnar \(\tilde T_{n+1}\) og varpa þeim með \(\eta\) yfir á bilið \([a,b]\) þá fáum við þá punkta \(x_0,\ldots,x_n \in [a,b]\) sem lágmarka \((x-x_0)\cdots (x-x_n)\) á bilinu \([a,b]\),

\[x_i = \eta\left(\cos\left(\frac{2i+1}{2(n+1)}\pi\right)\right) = \frac{b-a}2 \cos\left(\frac{2i+1}{2(n+1)}\pi\right) + \frac{b+a}2,\]

\(i=0,1,2,\ldots,n\).

3.6.12. Lágmörkun á skekkju með tilliti til \(\ell_2\)

Nú skulum við skipta um staðal, þannig að í stað þess að lágmarka \(\|f-p\|_\infty\) þá skulum við reyna að lágmarka

\[\|f-p\|_2 = \left(\int_a^b (f-p)^2\, dx\right)^{1/2}\]

Við vitum að skekkjan í því að nálga fallið \(f\) með brúunarmargliðu \(p\) með brúunarpunkta \(x_0,\ldots,x_n\) er

\[f(x)-p(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\, (x-x_0)(x-x_1)\cdots (x-x_n),\]

þar sem \(\xi\) er á minnsta bilinu sem inniheldur \(x\) og \(x_0,x_1,\ldots,x_n\).

Eins og áður þá sjáum við að stæðan \((x-x_0)\cdots(x-x_n)\) það eina sem við getum stjórnað með því að velja brúunarpunktana \(x_j\).

3.6.13. Skilgreining: Legendre margliðurnar

Fyrir náttúrlega tölu \(n\) þá skilgreinum við Legendre margliðurnar svona

\[\begin{split}\begin{aligned} P_0(x) &= 1,\\ P_1(x) &= x,\\ P_n(x) &= \frac{2n-1}n x P_{n-1}(x) - \frac{n-1}n P_{n-2}(x). \end{aligned}\end{split}\]

Af skilgreiningunni hér á undan þá sjáum við að

• \(P_n(x)\) er margliða af stigi \(n\).

• Forystustuðull \(P_n\) er \(\frac {2n-1}n \cdot \frac {2n-3}{n-2} \cdots \frac 32 \cdot 1\).

• \(P_n\) er jafnstæð ef \(n\) er slétt og oddstæð ef \(n\) er oddatala.

3.6.14. Setning

\[\begin{split}\int_{-1}^1 P_j(x) P_k(x)\, dx = \begin{cases} 0, & \text{ef } j\neq k\\ \frac{2}{2j+1}, & \text{ef } j=k. \end{cases}\end{split}\]

Einnig gildir að ef \(q\) er margliða af stigi minna en \(n\) þá er

\[\int_{-1}^1 q(x)P_n(x)\, dx = 0.\]

Þetta segir okkur að Legendre margliðurnar eru hornréttar (með tilliti til innfeldisins sem heildið skilgreinir).

3.6.15. Setning

\(P_n\) hefur \(n\) ólíkar núllstöðvar sem liggja allar á \([-1,1]\).

3.6.16. Skilgreining: Staðlaðar Legendre margliður

Eins og þegar við fengumst við Chebyshev margliðurnar þá skilgreinum við stöðluðu Legendre margliðurnar \(\tilde P_n\) með því að deila upp í \(P_n\) með forrystustuðlunum \(P_n\).

Athugasemd

Setningarnar þrjár hér undan gilda um \(\tilde P\) alveg eins og \(P\).

3.6.17. Setning: Lágmörkun með Legendre margliðunum

Ef \(p\) er stöðluð margliða af stigi \(n+1\) þá er \(\|p\|_2\geq \|\tilde P_{n+1}\|_2\).

Sönnun

Skilgreinum \(q = p-\tilde P_{n+1}\), sem þýðir að \(q\) er margliða af stigi minna en \(n+1\). Nú er

\[\begin{split}\begin{aligned} \|p\|_2^2 &= \|\tilde P_{n+1} + q\|_2^2 \\ &= \int_{-1}^1 (\tilde P_{n+1}(x) + q(x))^2\, dx \\ &= \int_{-1}^1 \tilde P_{n+1}(x)^2 + 2q(x)\tilde P_{n+1}(x) + q(x)^2\, dx\\ &= \|\tilde P_{n+1}\|_2^2 + 2\int_{-1}^1 q(x)\tilde P_{n+1}(x)\, dx + \|q\|_2^2\\ &= \|\tilde P_{n+1}\|_2^2 + \|q\|_2^2 \geq \|\tilde P_{n+1}\|_2^2 \end{aligned}\end{split}\]

því \(\int_{-1}^1 q(x)\tilde P_{n+1}(x)\, dx=0\) og \(\|q\|_2 \geq 0\).

Af síðustu setningu sjáum við að til þess að lágmarka

\[\|f(x)-p(x)\|_2 = \left\|\frac{f^{(n+1)}(\xi)}{(n+1)!}\, (x-x_0)(x-x_1)\cdots (x-x_n) \right\|_2,\]

þá veljum við \(x_1,\ldots,x_n\) þannig að \((x-x_0)(x-x_1)\cdots (x-x_n) = \tilde P_{n+1}\). Þ.e. \(x_j\) þurfa að vera rætur stöðluðu Legendre margliðunnar af stigi \(n+1\).

3.6.18. Núllstöðvar \(P_n\), fyrir \(n=1,\ldots,10\)

Ólíkt Chebyshev margliðunum þá er ekki hlaupið að því að finna rætur \(\tilde P_{n+1}\). Þannig að við þurfum að reikna þær tölulega og geyma í töflu.

3.6.19. Dæmi um óheppilega skiptipunkta skoðað aftur

Skoðum enn einu sinni fallið \(f(x) = 1/(25x^2+1)\), en í stað þess að taka 9 jafndreifaða brúunarpunkta á bilinu \([-1,1]\), þá skulum við nota Legendre margliðurnar til að finna 9 punkta á bilinu.

3.6.20. Athugasemd um \(\ell_\infty\) og \(\ell_2\)

Athugasemd

Það má líta þannig á þetta að \(\ell_\infty\) staðallinn mæli hámarksskekkju og \(\ell_2\) mæli einhvers konar,,heildarskekkju“, þar sem skekkjan er reiknað með heildinu hér á undan og svarar því hér um bil til flatarmálsins á milli fallsins og brúunarmargliðunnar.

• \(\ell_\infty\) staðallinn mælir hámarksskekkju, þannig að með því nota Chebyshev margliðurnar þá erum við að reyna að lágmarka mestu skekkju á bilinu.

• \(\ell_2\) mæli einhvers konar,,heildarskekkju“, þar sem skekkjan er reiknað með heildi. Þannig að með því að nota Legendre margliðurnar þá erum við í einhverjum skilningi að lágmarka flatarmál.

3.7. Skekkjumat

3.7.1. Nálgun á föllum með margliðum

Lítum nú aftur á almenna brúunarverkefnið og gefum okkur að tölurnar \(y_i^{(j)}\) séu af gerðinni \(f^{(j)}(a_i)\) þar sem \(f : I \to {{\mathbb R}}\) er fall á bili \(I\) sem inniheldur alla punktana \(a_1, \ldots, a_k\).

Þá snýst brúunarverkefnið um að finna margliðu af stigi \(\leq m\) sem uppfyllir

\[p^{(j)}(a_i) = f^{(j)}(a_i), \quad j = 0, \ldots, m_i-1, \quad i = 1, \ldots, k.\]

Við vitum að lausn þess er ótvírætt ákvörðuð. Ef við notum Newton form lausnarinnar, þá táknum við mismunakvótana með

\[f[x_i,\ldots,x_{i+j}]\]

í stað

\[y[x_i,\ldots,x_{i+j}]\]

3.7.2. Nálgun á fallgildum

Runurnar \((x_0,\ldots,x_m)\) og \((y_0,\ldots,y_m)\) eru skilgreindar með

\[(x_0,x_1,\ldots,x_m) = (\underbrace{a_1, \ldots, a_1}_{m_1 \, \text{sinnum}}, \underbrace{a_2, \ldots , a_2}_{m_2 \, \text{sinnum}}, \ldots , \underbrace{a_k, \ldots , a_k}_{m_k \, \text{sinnum}})\]

og

\[\begin{split}\begin{gathered} (y_0,y_1,\ldots,y_m) = (f^{(0)}(a_1), \ldots, f^{(m_1-1)}(a_1), f^{(0)}(a_2), \ldots, f^{(m_2-1)}(a_2) \\ \ldots, f^{(0)}(a_k), \ldots, f^{(m_k-1)}(a_k)) \label{bru.margfald.5}\end{gathered}\end{split}\]

3.7.3. Skekkjumat

Nú tökum við punkt \(x \in I\) og spyrjum um skekkjuna \(f(x) - p(x)\) í nálgun á \(f(x)\) með \(p(x)\). Ef \(x\) er einn punktana \(a_1, \ldots, a_k\), þá er \(p(x) = f(x)\) og skekkjan þar með 0, svo við skulum gera ráð fyrir að \(x \not= a_i\), \(i = 1, \ldots, k\).

Við bætum nú \((x,f(x))\) sem einföldum brúunarpunkti við alhæfða brúunar verkefnið og fáum sem lausn \(q(t)\) á þessu aukna verkefni. Margliðan \(q\) er af stigi \(\leq m+1\). Við notum táknið \(t\) fyrir breytu, því \(x\) er frátekið.

Þá uppfyllir \(q(t)\) að \(q(x) = f(x)\) auk allra skilyrðanna

\[q^{(j)}(a_i) = p^{(j)}(a_i) = f^{(j)}(a_i)\]

í verkefninu sem við byrjuðum með.

Við getum þá skrifað (sjá Newton-margliður til hliðsjónar)

\[\begin{split}\begin{aligned} q(t) &= p(t) + f[x_0,\ldots,x_m,x](t-x_0)\cdots(t-x_m) \\ &= p(t) + f[x_0,\ldots,x_m,x](t-a_1)^{m_1}\cdots(t-a_k)^{m_k}.\end{aligned}\end{split}\]

Þegar við gefum breytunni \(t\) gildið \(x\), þá fáum við \(q(x) = f(x)\) og því fæst formúla fyrir skekkjunni

\[f(x) - p(x) = f[x_0,\ldots,x_m,x](x-a_1)^{m_1}\cdots(x-a_k)^{m_k}\]

Nú ætlum við að finna leið til þess að meta skekkjuliðinn. Til þess þurfum við að gefa okkur að \(f\) hafi að minnsta kosti \(m+1\) afleiðu.

3.7.4. Tilfellið þegar við höfum aðeins einn punkt

Munum nú að í tilfellinu þegar við erum bara með einn punkt \(a_1\), þá erum við með \(m+1\) skilyrði

\[p^{(j)}(a_1)=f^{(j)}(a_1), \qquad j=0,\dots,m\]

og við fáum að \(p\) er Taylor-margliða fallsins \(f\) í punktinum \(a_1\). Þá er \(x_0=\cdots=x_m=a_1\) og við fáum

\[f(x) - p(x) = f[x_0,\ldots,x_m,x](x-a_1)^{m+1}\]

Nú segir setning Taylors okkur að til sé punktur \(\xi\) milli \(a_1\) og \(x\) þannig að

\[f(x) - p(x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!}(x-a_1)^{m+1}\]

Við getum því dregið þá ályktun að í þessu sértilfelli er

\[f[x_0,\ldots,x_m,x]=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}\]

Það kemur í ljós að þetta er almenn regla sem gildir fyrir öll alhæfðu brúunarverkefnin.

Tilfellið \(m=1\) er meðalgildisreglan

Munum að tilfellið \(m=1\) er meðalgildisreglan

\[f[a_1,x]=\dfrac{f(x)-f(a_1)}{x-a_1}=f'(\xi).\]

3.7.5. Margfeldni núllstöðva

Samfellt fall \(\varphi\) á bili \(I\) er sagt hafa núllstöð af stigi að minnsta kosti \(m>0\) í punktinum \(a\in I\), ef til er samfellt fall \(\psi\) á \(I\) þannig að

\[\varphi(x)=(x-a)^m\psi(x)\]

Við segjum að \(\varphi\) hafi núllstöð af margfeldni \(m\) ef \(\psi(a)\neq0\).

Athugið að ef \(\varphi\) er deildanlegt \(I\) með samfellda afleiðu, þá er \(\psi\) deildanlegt með samfellda afleiðu í \(I\setminus\{a\}\) og við höfum

\[\begin{split}\begin{aligned} \varphi'(x)&=m(x-a)^{m-1}\psi(x)+(x-a)^m\psi'(x)\\ &= (x-a)^{m-1} \big(m\psi(x)+(x-a)\psi'(x)\big)\end{aligned}\end{split}\]

Ef afleiðan \(\psi'\) er takmörkuð í grennd um \(a\), þá sjáum við á þessari formúlu að \(\varphi'\) hefur núllstöð af stigi að minnsta kosti \(m-1\) í \(a\).

Hugsum okkur nú að við séum með \(a_1,\dots,a_k\) ólíka punkta í bilinu \(I\) og að \(m_1,\dots,m_k\) séu jákvæðar náttúrlegar tölur.

Ef fallið \(\varphi\) hefur núllstöðvar í öllum punktunum \(a_j\) og núllstöðin \(a_j\) er af stigi að minnsta kosti \(m_j\). Við segjum að þá hafi \(\varphi\) að minnsta kosti

\[n=m_1+\cdots+m_k\]

núllstöðvar taldar með margfeldni.

Eins þá segjum við að \(\varphi\) hafi \(n\) núllstöðvar í \(\{a_1,\dots,a_k\}\) taldar með margfeldni ef \(\varphi\) hefur núllstöðvar í öllum punktum \(a_1,\dots,a_k\) og samanlögð margfeldni þeirra er \(n\)

Hugsum okkur nú að fallið \(\varphi\) hafi núllstöð af stigi \(m_j\) í punktunum \(a_j\) fyrir öll \(j=1,\dots,k\) og að \(n=m_1+\cdots+m_k\).

Til einföldunar gerum við ráð fyrir að

\[a_1<a_2<\cdots<a_k.\]

Þá gefur meðalgildissetningin að \(\varphi'\) hefur að minnsta kosti eina núllstöð á sérhverju bilanna

\[]a_1,a_2[, \ ]a_2,a_3[, \ \dots \ ]a_{k-1},a_k[\]

Þau eru samanlagt \(k-1\) talsins. Að auki vitum við að \(\varphi'\) hefur núllstöðvar af stigi að minnsta kosti \(m_j-1\) í punktinum \(a_j\). Ef við leggjum þetta saman, þá fáum við að \(\varphi'\) hefur núllstöðvar af margfeldni að minnsta kosti

\[k-1+(m_1-1)+\cdots+(m_k-1)=n-1\]

í minnsta lokaða bilinu sem inniheldur alla punktana \(a_1,\dots,a_k\).

3.7.6. Setning: Skekkjumat

Nú ætlum við að sýna fram á að fyrir föll \(f\) sem eru \((m+1)\) sinnum samfellt deildanleg að til sé \(\xi\) á minnsta bili sem inniheldur \(a_1, \ldots, a_k\) og \(x\) þannig að

\[f[x_0,\ldots,x_m,x] = \frac{f^{(m+1)}(\xi)}{(m+1)!}\]

Sönnun

Við skilgreinum fallið

\[g(t) = f(t) - p(t) - \lambda w(t),\]

þar sem

\[w(t) = (t-a_1)^{m_1} \cdots (t-a_k)^{m_k}\]

og talan \(\lambda\) er valin þannig að \(g(x) = 0\).

Nú er \(p^{(j)}(a_i)=f^{(j)}(a_i)\) fyrir \(j=0,\dots,m_i-1\), þá gefur setning Taylors okkur að \(g\) hefur núllstöð af stigi \(m_i\) í sérhverjum punktanna \(a_i\). Auk þess hefur \(g\) núllstöð í \(x\). Samanlagt eru þetta að minnsta kosti \(m+2\) núllstöðvar taldar með margfeldni.

Höfum:

• \(g\) hefur að minnsta kosti \(m+2\) núllstöðvar taldar með margfeldni,

• \(g'\) hefur að minnsta kosti \(m+1\) núllstöð talda með margfeldni,

• \(g''\) hefur að minnsta kosti \(m\) núllstöðvar taldar með margfeldni

• og þannig áfram, þar til við ályktum að

• \(g^{(m+1)}\) hefur að minnsta kosti eina núllstöð.

Tökum eina slíka og köllum hana \(\xi\).

Munum að

\[g(t) = f(t) - p(t) - \lambda w(t),\]

þar sem

\[w(t) = (t-a_1)^{m_1} \cdots (t-a_k)^{m_k}=t^{m+1}+b_mt^m+\cdots+b_1t+b_0\]

Margliðan \(p\) hefur stig \(\leq m\) svo \(p^{(m+1)}(x) = 0\) fyrir öll \(x\)

og margliðan \(w\) er af stigi \(m+1\) með stuðul \(1\) við hæsta veldið, svo \(w^{(m+1)}(t) = (m+1)!\). Við höfum því

\[0 = g^{(m+1)}(\xi) = f^{(m+1)}(\xi) - \lambda \cdot (m+1)!\]

sem jafngildir því að

\[\lambda =\dfrac{f^{(m+1)}(\xi)}{(m+1)!}\]

Við setjum nú inn \(t=x\) sem gefur

\[0=g(x) = f(x) - p(x) - \lambda w(x),\]

og við fáum þar með formúlu fyrir skekkjunni á nálgun á \(f(x)\) með alhæfðu brúunarmargliðunni \(p(x)\),

\[f(x) - p(x) =\lambda w(x) = \dfrac{f^{(m+1)}(\xi)}{(m+1)!} (x-a_1)^{m_1} \cdots (x-a_k)^{m_k}\]

3.7.7. Samantekt

Ef gefið er fall \(f:I\to {{\mathbb R}}\) á bili \(I\), \(a_1,\dots,a_k\) í \(I\), með \(a_j\neq a_k\) ef \(j\neq k\), jákvæðar heiltölur \(m_1,\dots,m_k\), talan \(m\) er skilgreind með \(m=m_1+\cdots+m_k-1\), og gert er ráð fyrir að \(f\in C^{m+1}(I)\), þá er til nákvæmlega ein margliða \(p\) af stigi \(\leq m\) þannig að

\[p^{(j)}(a_i)=f^{(j)}(a_i), \qquad j=0,\dots, m_i-1, \quad i=1,\dots,k.\]

Newton-form margliðunnar \(p\) er gefið með

\[p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+f[x_0,\dots,x_m](x-x_0)\cdots(x-x_{m-1})\]

þar sem mismunakvótarnir \(f[x_i,\dots,x_{i+j}]\) eru skilgreindir sem \(y[x_i,\dots,x_{i+j}]\) út frá gögnunum \(y^{(j)}_i\). Fyrir sérhvert \(x\) í \(I\) er skekkjan \(f(x)-p(x)\) í nálgun á \(f(x)\) með \(p(x)\) gefin með

\[f(x)-p(x)=f[x_0,\dots,x_m,x](x-a_1)^{m_1}\cdots(x-a_k)^{m_k}.\]

Fyrir sérhvert \(i=1,\dots,k\) og \(j=0,\dots,m-i\) þá gildir að til er tala \(\xi\) á minnsta bilinu sem inniheldur \(x_i\dots,x_{i+j}\) þannig að

\[f[x_i,\dots,x_{i+j}]=\dfrac{f^{(j)}(\xi)}{j!},\]

því gildir sérstaklega að til er tala \(\xi\) á minnsta bilinu sem inniheldur \(a_1,\dots,a_k\) og \(x\) þannig að

\[f(x)-p(x)=\dfrac{f^{(m+1)}(\xi)}{(m+1)!}(x-a_1)^{m_1}\cdots(x-a_k)^{m_k}.\]

3.7.8. Sýnidæmi

Látum \(f(x)=x^2\ln x\).

1. Setjið upp mismunakvótatöflu til þess að reikna út brúunarmargliðu \(p\) af stigi \(\leq 3\) fyrir fallið \(f\), sem hefur tvo tvöfalda brúunarpunkta \(a_1=1\) og \(a_2=2\). Skrifið upp Newton-form margliðunnar \(p\).

2. Reiknið út \(p(1.3)\). Notið aðferðarskekkju fyrir margliðubrúun til þess að meta skekkjuna \(f(1.3)-p(1.3)\) að ofan og neðan og fáið þannig bil þar sem rétta gildið liggur. Veljið miðpunkt bilsins sem nálgunargildi fyrir \(f(1.3)\) og afrúnið gildið miðað við mörk bilsins.

3. Látum nú \(q\) vera brúnunarmargliðuna af stigi \(\leq 4\) sem uppfyllir sömu skilyrði og gefin eru í fyrsta lið að viðbættu því að \(a_2=2\) á að vera þrefaldur brúunarpunktur. Sýnið hvernig hægt er að ákvarða mismunakvótatöfluna fyrir \(q\) með því að stækka töfluna í a). Ákvarðið síðan \(q\) og reiknið út \(q(1.3)\).

Lausn

1. og 2. Til þess að spara pláss skulum leysa fyrsta og þriðja lið báða í einu með því að reikna strax út mismunakvótatöfluna fyrir fjórða stigs margliðuna í 3. lið. Punktarnir \(x_0,\dots,x_4\) eru þá \(1,1,2,2,2\) og við höfum gefin fallgildin

\[f(1)=f[x_0]=f[x_1]=0 \qquad \text{ og } \qquad f(2)=f[x_2]=f[x_3]=f[x_4].\]

Í 1. lið eru punktarnir tvöfaldir svo við höfum gefin gildi afleiðunnar \(f'(x)=2x\ln x+x\) í punktunum \(1\) og \(2\).

\[f'(1)=f[1,1]=f[x_0,x_1]=1 \ \text{ og } \ f'(2)=f[2,2]=f[x_2,x_3]=4\ln 2+2.\]

Í 3. lið er gildið á 2. afleiðu \(f''(x)=2\ln x +3\) gefið í punktinum \(2\). Það gefur okkur

\[f''(2)/2!=f[2,2,2]=f[x_2,x_3,x_4]=\ln 2+\tfrac 32.\]

Við setjum þessi gildi inn í mismunakvótatöfluna og fyllum hana út með því að taka mismunakvóta milli allra gilda

\[\begin{split}\begin{matrix} i&x_i & f[x_i] &f[x_i,x_{i+1}] & f[x_i,x_{i+1},x_{i+2}] & f[x_i,\dots,x_{i+3}]&f[x_i,\dots,x_{i+4}] \\\hline 0&1&0 &1 &4\ln 2-1 &-4\ln 2+3& 5\ln 2-\tfrac 72\\ 1&1&0 &4\ln 2 &2 &\ln 2-\tfrac 12\\ 2&2&4\ln 2&4\ln 2+2&\ln 2+\tfrac 32\\ 3&2&4\ln 2&4\ln 2+2\\ 4&2&4\ln 2 \end{matrix}\end{split}\]

Margliðan í 1. lið er því

\[p(x)=(x-1)+(4\ln 2-1)(x-1)^2+(-4\ln 2+3)(x-1)^2(x-2).\]

en í 3. lið er hún

\[q(x)=p(x)+(5\ln 2-\tfrac 72)(x-1)^2(x-2)^2\]

2. Við stingum gildinu \(x=1.3\) inn í margliðuna og fáum \(p(1.3)=0.445206074\). Skekkjan er

\[f(x)-p(x)=\dfrac{f^{(4)}(\xi)}{4!}(x-1)^2(x-2)^2\]

þar sem \(\xi\) er einhver punktur á bilinu \([1,2]\).

Við þurfum því að meta fjórðu afleiðuna,

\[\begin{split}\begin{aligned} f(x) &=x^2\ln x, \quad f'(x)=2x\ln x+x, \quad f''(x)=2\ln x+3, \quad \\ f'''(x)& =2/x, \quad f^{(4)}(x)=-2/x^2.\end{aligned}\end{split}\]

Ef \(x\in [1,2]\), þá höfum við matið \(-2\leq f^{(4)}(x)\leq -\tfrac 12\).

Af ójöfnunum \(-2\leq f^{(4)}(x)\leq -\tfrac 12\) leiðir síðan að

\[\alpha=\dfrac{-2\cdot(0.3)^2\cdot(-0.7)^2}{24}\leq f(1.3)-p(1.3) \leq \dfrac{-0.5\cdot(0.3)^2\cdot(-0.7)^2}{24}=\beta.\]

Við reiknum út úr báðum brotunum

\[\alpha=-0.003675 \qquad \text{ og } \qquad \beta=-0.00091875.\]

þar með er \(f(1.3)\) á bilinu milli \(p(1.3)+\alpha=0.441531\) og \(p(1.3)+\beta=0.444287\).

Nálgunargildi okkar á að vera miðpunktur þessa bils og algildi skekkjunnar verður þá hálf billengdin. Það færir okkur nálgunina \(f(1.3) \approx 0.442909\) og skekkjuna \(\pm 0.0014\). Réttur afrúningur er \(f(1.3)=0.44\).

Við eigum aðeins eftir að reikna út gildi margliðunnar \(q\) í punktinum \(1.3\). Út úr mismunakvótatöflunni fáum við

\[q(x)=p(x)+(5\ln 2-\tfrac 72)(x-1)^2(x-2)^2\]

sem gefur okkur gildið

\[q(1.3)=0.445206074-0.001511046=0.4436950278\]

Til samanburðar höfum við rétt gildi

\[f(1.3)=0.443395606950060\ldots.\]

3.8. Splæsibrúun

Látum \((t_0,y_0),\dots,(t_n,y_n)\) vera punkta í plani og gerum ráð fyrir að \(a=t_0<t_1<\cdots<t_n=b\).

Við höfum nú lært að ákvarða margliðu \(p\) af stigi \(\leq n\) sem tekur gildin \(y_i\) í punktunum \(t_i\).

Ef punktarnir liggja á grafi fallsins \(f\) og nota á margliðuna til þess að nálga fallgildi \(f\), þá getur það verið ýmsum erfiðleikum bundið þegar stig hennar stækkar eins og við sáum í byrjun kaflans Skynsamlegir skiptipunktar og Chebyshev margliður. Lausnin þar var að reyna að velja brúunarpunktana skynsamlega. Ef við hins vegar getum ekki valið brúunarpunktana eftir eigin höfði þá erum við í vandræðum og þurfum við að leita annarra leiða.

3.8.1. Almennt um splæsibrúun

Splæsibrúun er leið út úr þessum vandræðum.

Með henni er fundið samfellt fall \(S\) sem brúar gefnu punktana, \(S(t_i)=y_i\), og er þannig að einskorðun þess við hlutbilin \([t_i,t_{i+1}]\) er gefið með margliðu af stigi \(\leq m\), þar sem \(m\) er fyrirfram gefin tala.

Algengast er að nota \(m=3\).

3.8.2. Fyrsta stigs splæsibrúun:

Ef stigið \(m\) er \(1\), þá erum við einfaldlega að draga línustrik milli punktanna og sjáum í hendi okkar að lausnin er

\[\begin{split}S(x) = \begin{cases} S_0(x) = \dfrac {y_1-y_0}{t_1-t_0}(x-t_0)+y_0, & x \in [t_0,t_1],\\ S_1(x) = \dfrac {y_2-y_1}{t_2-t_1}(x-t_1)+y_1, & x \in [t_1,t_2],\\ \vdots & \\ S_{n-1}(x) = \dfrac {y_n-y_{n-1}}{t_n-t_{n-1}} (x-t_{n-1})+y_{n-1}, &x \in [t_{n-1},t_n]. \end{cases}\end{split}\]

Þessi aðferð er ekki mikið notuð því hún er ósannfærandi fyrir deildanleg föll.

3.8.3. Þriðja stigs splæsibrúun

Algengast er að framkvæma splæsibrúun með þriðja stigs margliðum.

Við skulum tákna einskorðun \(S\) við hlutbilið \([t_i,t_{i+1}]\) með \(S_i\) og skrifa

\[S_i(x) = a_i+b_i(x-t_i)+c_i(x-t_i)^2+d_i(x-t_i)^3, \qquad x\in [t_i,t_{i+1}).\]

Við ætlum að leiða út jöfnur fyrir stuðlunum \(a_i, b_i, c_i\) og \(d_i\). Kröfurnar sem við setjum eru:

1. \(S\) er tvisvar sinnum samfellt deildanlegt á öllu bilinu \([a,b]\)

2. \(S\) taki gildin \(y_i\) í punktunum \(t_i\)

Setjum til einföldunar \(h_i = t_{i+1}-t_i\) fyrir \(i = 0, \ldots, n-1\).

Skilyrðin tvö má því skrifa sem eftirfarandi jöfnuhneppi:

Útleiðsla á jöfnuhneppi

Á hverju hlutbili \([t_i,t_{i+1}]\) höfum við:

\[S_i(x) = a_i+b_i(x-t_i)+c_i(x-t_i)^2+d_i(x-t_i)^3, \qquad x\in [t_i,t_{i+1}),\]

sem þýðir að skilyrðin tvö má skrifa sem

\[\begin{split}\begin{aligned} a_i &=& &S_i(t_i)& &=& y_i &, \quad (1) \\ a_i + b_ih_i + c_ih_i^2 + d_ih_i^3 &=& &S_i(t_{i+1}) = S_{i+1}(t_{i+1})& &=& a_{i+1} &, \quad (2) \\ b_i + 2c_ih_i + 3d_ih_i^2 &=& &S_i'(t_{i+1}) = S_{i+1}'(t_{i+1})& &=& b_{i+1} &, \quad (3) \\ 2c_i + 6d_ih_i &=& &S_i''(t_{i+1}) = S_{i+1}''(t_{i+1})& &=& 2c_{i+1} &, \quad (4)\end{aligned}\end{split}\]

Í (1) höfum við \(i = 0,\ldots,n\) og í (2)-(4) höfum við \(i=0,\ldots,n-2\).

Samtals: \((n+1)+3(n-1)=4n-2\) línulegar jöfnur til þess að ákvarða \(4n\) óþekktar stærðir.

Það er því ljóst að okkur vantar tvö skilyrði til þess að geta fengið ótvírætt ákvarðaða lausn.

Fyrstu jöfnurnar gefa strax gildi \(a_i\) og (4) gefur að

\[d_i = \frac{c_{i+1}-c_i}{3h_i}, \quad i=0,\ldots,n-2\]

Ef við setjum þetta inn í (2) og (3) fæst

\[\begin{split}\begin{aligned} a_{i+1} = a_i + b_ih_i + \frac{c_{i+1}+c_i}{3}h_i^2 &, \quad i=0,\ldots,n-2 \\ b_{i+1} = b_i + (c_{i+1} + c_i)h_i &, \quad i=0,\ldots,n-2\end{aligned}\end{split}\]

Þegar við leysum fyrri jöfnuna fyrir \(b_i\) fæst

\[b_i = \frac{a_{i+1}-a_i}{h_i}-\frac{c_i+c_{i+1}}{3}h_i , \quad i=0,\ldots,n-2\]

og ef við setjum þetta inn í seinni jöfnuna fæst á endanum að

\[h_{i-1}c_{i-1} + 2(h_{i-1}+h_i)c_i + h_ic_{i+1} = \frac{3}{h_i}(a_{i+1}-a_i) - \frac{3}{h_{i-1}}(a_i-a_{i-1}) , \quad i=1,\ldots,n-1\]

3.8.4. Jöfnuhneppið

\[\begin{split}\begin{aligned} \left[ \begin{array}{c:cccc:c} .?. & .?. &&&& \\ \hdashline h_0 & 2(h_0+h_1) & h_1 &&&\\ & h_1 & 2(h_1+h_2) & h_2 &&\\ &&&&&\\ & & \ddots & \ddots & \ddots &\\ &&&&&\\ & & & h_{n-2} & 2(h_{n-2} + h_{n-1}) & h_{n-1} \\ \hdashline & & & & .?. & .?. \end{array} \right] \left[ \begin{array}{c} c_0 \\ \hdashline c_1 \\ c_2 \\ \\ \vdots \\ \\ c_{n-1} \\ \hdashline c_n \end{array} \right] \\ = 3\left[ \begin{array}{c} .?. \\ \hdashline \dfrac{a_2-a_1}{h_1} - \dfrac{a_1-a_0}{h_0} \\ \dfrac{a_3-a_2}{h_2} - \dfrac{a_2-a_1}{h_1} \\ \vdots \\ \dfrac{a_n-a_{n-1}}{h_{n-1}} - \dfrac{a_{n-1}-a_{n-2}}{h_{n-2}} \\ \hdashline \end{array} \right]\end{aligned}\end{split}\]

En það vantar í þetta einhver skilyrði á \(c_0\) og \(c_n\).

Þegar þau hafa verið sett inn, þá getum við leyst þetta hneppi, reiknað svo gildi \(b_i\) og \(d_i\) og þá höfum við fundið splæsifallið okkar.

Það eru til margar leiðir til að ákvarða \(c_0\) og \(c_n\), en fjórar eru algengastar.

3.8.5. Tilfelli 1: Ekki-hnúts endaskilyrði

Ef við höfum engar upplýsingar um fallið \(f\) í \(t_1\) og \(t_{n-1}\) liggur beint við að krefjast þess að \(S'''\) sé samfellt þar, sem þýðir að \(d_0 = d_1\) og \(d_{n-2} = d_{n-1}\). Með að nota jöfnurnar fyrir \(d_i\) má skrifa þetta sem

\[\begin{split}\begin{aligned} h_1c_0 - (h_0 + h_1)c_1 + h_0c_2 = 0 \\ h_{n-1}c_{n-2}-(h_{n-2}+h_{n-1})c_{n-1}+h_{n-2}c_n = 0\end{aligned}\end{split}\]

og þessar jöfnur, ásamt hinum, má leysa til að ákvarða \(c_i\)-in.

3.8.6. Tilfelli 2: Þvinguð endaskilyrði

Ef hallatala fallsins \(f\) er þekkt í endapunktum bilsins er eðlilegt að nota þær upplýsingar við ákvörðun splæsifallsins. Gerum því ráð fyrir að \(f'(t_0) = A\) og \(f'(t_n) = B\). Skilyrðið \(S'(t_0) = A\) gefur þá að

\[A = \frac{a_1-a_0}{h_0} - \frac{2c_0+c_1}{3}h_0,\]

eða

\[2h_0c_0 + h_0c_1 = 3 \left( \frac{a_1-a_0}{h_0} - A \right)\]

og \(S'(t_n) = B\) gefur

\[B = b_{n-1} + 2c_{n-1}h_{n-1} + 3d_{n-1}h_{n-1}^2\]

og með að nota formúlurnar fyrir \(b_{n-1}\) og \(d_{n-1}\) fæst

\[c_{n-1}h_{n-1} + 2c_nh_{n-1} = 3 \left( B - \frac{a_n-a_{n-1}}{h_{n-1}} \right).\]

3.8.7. Tilfelli 3: Náttúrleg endaskilyrði

Einfaldasta lausnin er að setja \(c_0 = c_n = 0\), en það jafngildir því að \(S''(t_0) = S''(t_n) = 0\).

3.8.8. Tilfelli 4: Lotubundið endaskilyrði

Hugsum okkur að við viljum framlengja \(S\) í tvisvar samfellt deildanlegt \((b-a)\)-lotubundið fall á \({{\mathbb R}}\). Það setur skilyrðin

\[y_0 = S(t_0) = S_(t_n) = y_n, \quad S'(t_0) = S'(t_n), \quad \text{ og } \quad S''(t_0) = S''(t_n)\]

Fljótséð er að \(S''(t_0) = S''(t_n)\) þýðir að \(c_0 = c_n\), eða

\[c_0 - c_n = 0.\]

Þetta er fyrri jafnan sem við þurfum.

Nú gefur \(S'(t_0) = S'(t_n)\) að

\[b_0 = b_{n-1} + 2c_{n-1}h_{n-1} + 3d_{n-1}h_{n-1}^2\]

og með að setja inn formúlurnar fyrir \(b_0, b_{n-1}, d_{n-1}\) og nota að \(c_0 = c_n\) fæst jafnan

\[h_0c_1 + 2h_{n-1}c_{n-1} + (2h_0 + 2h_{n-1})c_n = 3 \left( \frac{a_1-a_0}{h_0} - \frac{a_n-a_{n-1}}{h_{n-1}} \right).\]

3.8.9. Teikning á ferlum í planinu

Hægt er að nota brúun til þess að nálga ferla í \(\mathbb R^n\). Skoðum tilvikið \(n=2\).

Gerum nú ráð fyrir að við höfum gefna punkta \((x_0,y_0),\dots,(x_n,y_n) \in \mathbb R^2\) og að við viljum finna samfelldan splæsiferil í gegnum þá. Þetta er gert í nokkrum skrefum:

1. Ákveðið er stikabil \([a,b]\) og skiptingu á því

   \[a=t_0<t_1<\cdots<t_n=b\]

   til dæmis \([0,n]\) og skiptinguna

   \[0=t_0<t_1=1<\cdots<t_n=n.\]

2. Ákveðið er hvaða endaskilyrði eiga við.

3. Búin eru til tvö splæsiföll \(R(t)\) fyrir punktasafnið \(x_0,\dots,x_n\) og \(S(t)\) fyrir punktasafnið \(y_0,\dots,y_n\).

4. Stikaferillinn \([a,b]\ni t\mapsto (R(t),S(t))\) er síðan teiknaður, en hann uppfyllir \((R(t_j),S(t_j))=(x_j,y_j)\), \(j=0,\dots,n\).

Aðvörun

Athugið að hér er \(t\) breytan okkar en \(x\) og \(y\) eru gildin sem við viljum að ferillinn taki.

Þetta er frábrugðið því þegar við skoðum graf af einni breytu en þá er \(x\) venjulega breytan og \(y\) gildin sem viljum taka.

3.9. Aðferð minnstu fervika

Látum \((x_1,y_1),\dots,(x_m,y_m)\) vera safn punkta í plani með \(x_j\in [a,b]\) fyrir öll \(j\) og látum \(f_1,\dots,f_n\) vera raungild föll á \([a,b]\).

Við viljum finna það fall \(f\) af gerðinni

\[f(x)=c_1f_1(x) + \cdots + c_nf_n(x)\]

með stuðla \(c_1, \ldots, c_n\) þannig að punktarnir \((x_j,f(x_j))\) nálgi gefna punktasafnið sem best og þá er átt við að ferningssummuna

\[\sum_{i=1}^m\big(y_i-f(x_i)\big)^2\]

verði eins lítil og mögulegt er.

3.9.1. Jafna bestu línu

Flestir hafa heyrt talað um bestu línu gegnum punktasafn, hún fæst með að taka hér \(f_1(x) = 1\) og \(f_2(x) = x\), en lítið mál er að finna einnig besta fleygboga, bestu margliðu af fyrirfram ákveðnu stigi eða einhverja aðra samantekt falla gegnum punktasafnið.

3.9.2. Smávegis línuleg algebra

Til þess að finna þessi gildi á stuðlunum \(c_i\) er heppilegt að notfæra sér nokkrar niðurstöður úr línulegri algebru. Fyrir gefin gildi á \(c_1,\dots,c_n\) setjum við

\[b_i = f(x_i) = c_1f(x_i) + \cdots + c_n f_n(x_i), \qquad i=1,\dots,m,\]

og skilgreinum síðan dálkvigrana

\[b = [b_1,\dots,b_m]^T,\qquad y = [y_1,\dots,y_m]^T,\quad \text{ og } \quad c = [c_1,\dots,c_n]^T,\qquad\]

Þá er \(Ac=b\), þar sem \(A\) er \(m\times n\) fylkið

\[\begin{split}A = \left[\begin{matrix} f_1(x_1)& f_2(x_1) & \dots & f_n(x_1) \\ f_1(x_2)& f_2(x_2) & \dots & f_n(x_2) \\ \vdots &\vdots &\ddots &\vdots \\ f_1(x_m)& f_2(x_m) & \dots & f_n(x_m) \end{matrix}\right].\end{split}\]

Verkefnið snýst nú um að finna þann vigur \(c\in {{\mathbb R}}^n\) sem lágmarkar

\[\sum_{i=1}^m \big(y_i-b_i\big)^2 = \| y - b \|^2 = \| y - Ac \|^2\]

þar sem \(\|\cdot\|\) táknar evklíðska fjarlægðina (staðalinn) á \({{\mathbb R}}^m\).

Vigrar af gerðinni \(b= Ac\) spanna dálkrúm fylkisins \(A\) og þá má skrifa sem línulegar samantektir af gerðinni

\[b = c_1A_1 + \cdots + c_nA_n\]

þar sem \(A_j\) er dálkur númer \(j\).

Verkefnið snýst um að finna þann vigur í dálkrúminu sem næstur er \(y\). Vigurinn \(b\) er næstur \(y\) ef og aðeins ef \(y-b\) er hornréttur á alla vigra dálkrúmsins.

Þessi skilyrði má fá með innfeldi

\[A_j \cdot (y-b) = 0, \qquad j = 1, \ldots , n\]

Með fylkjarithætti fæst ein jafna

\[A^T (y-b) = 0.\]

Setjum nú inn \(b=Ac\). Þá ákvarðast \(c\) af hneppinu

\[A^T(y-Ac) = 0\]

sem jafngildir

\[(A^TA)c = A^Ty\]

Við þurfum því aðeins að leysa þetta jöfnuhneppi

\[(A^TA)c = A^Ty\]

fyrir \(c\) til að finna stuðlana okkar. Ef fylkið \(A^TA\) hefur andhverfu, þá fæst alltaf ótvírætt ákvörðuð lausn \(c\).

Ef fylkið \(A^TA\) hefur ekki andhverfu eða að það hefur ákveðu sem er mjög nálægt \(0\), þá þurfum við að beita flóknari brögðum. Við komum að því síðar.

3.9.3. Jafna bestu línu

Algengt er að menn vilji finna beina línu sem best fellur að punktasafninu \((x_1,y_1,)\dots,(x_m,y_m)\). Þá er \(n=2\) og við tökum lausnagrunninn \(f_1(x)=1\) og \(f_2(x)=x\).

Fylkið er þá

\[\begin{split}A = \left[\begin{matrix} 1& x_1\\ 1& x_2 \\ \vdots &\vdots \\ 1& x_m \end{matrix}\right].\end{split}\]

og þar með

\[\begin{split}A^TA = \left[\begin{matrix} m& \sum_{j=1}^mx_j\\ \sum_{j=1}^mx_j& \sum_{j=1}^mx_j^2 \end{matrix}\right]. \qquad \text{ og } \qquad A^Ty = \left[\begin{matrix} \sum_{j=1}^my_j\\ \sum_{j=1}^mx_jy_j \end{matrix}\right].\end{split}\]

Athugasemd

Það er auðvelt að leysa þetta tilvik því við höfum einfalda formúlu fyrir andhverfum \(2 \times 2\) fylkja (svo lengi sem ákveðan er ekki 0).

Sjá Wikipedia.

3.9.4. Jafna bestu annars stigs margliðu

Ef við viljum finna bestu annars stigs margliðu gegnum punktasafnið, þá er \(n=3\) og við tökum lausnagrunninn \(f_1(x)=1\), \(f_2(x)=x\) og \(f_3(x)=x^2\).

Þetta val gefur fylkið

\[\begin{split}A = \left[\begin{matrix} 1& x_1 & x_1^2\\ 1& x_2 & x_2^2\\ \vdots &\vdots &\vdots\\ 1& x_m& x_m^2 \end{matrix}\right].\end{split}\]

Fylkið \(A^TA\) er þá \(3\times 3\) og vigurinn \(A^Ty\) er dálkvigur með \(3\) hnit.

3.9.5. Sýnidæmi: besta annars stigs margliða

Gefin eru mæligildin

\(x\)	0	1	2	3	4	5	6
\(y\)	2.7	-0.5	-1.7	-1.9	-1.5	0.2	2.3

Beitið aðferð minnstu fervika til þess að finna þá annars stigs margliðu sem best fellur að þessum gögnum Teiknið upp gögnin og graf marliðunnar.

Lausn

Við leitum hér að þremur tölum \(c_1\), \(c_2\) og \(c_3\) þannig að annars stigs margliðan \(f(x)=c_1f_1(x)+c_2f_2(x)+c_3f_3(x)\) falli sem best að gögnunum. Grunnföllin þrjú eru \(f_1(x)=1\), \(f_2(x)=x\) og \(f_3(x)=x^2\).

Í þessu dæmi er fylkið \(A\) gefið með

\[\begin{split}A=\left[\begin{matrix} 1 & 0&0\\ 1 & 1&1\\ 1&2&4\\ 1&3&9\\ 1&4&16\\ 1&5&25\\ 1&6&36 \end{matrix}\right],\end{split}\]

því stak númer \((i,j)\) í A er gefið með \(A_{ij} = f_j(x_i)\).

Nú látum við matlab um afganginn

%  Matlab forrit sem teiknar upp bestu margliðunálgun á gefnum gögnum
x=[0; 1; 2; 3; 4; 5; 6]
y=[2.7; -0.5; -1.7; -1.9; -1.5; 0.2; 2.3 ]
m=length(x);

% Við leitum að bestu margliðu af stigi 2 eða lægri
% og því eru  grunnföllin eru 3 talsins.
n=3;

% Stuðlafylkið er A=(a_{ij}), a_{ij}=x_i^{j-1}
A(1:m,1)=ones(m,1);
A(1:m,2)=x;
for j=3:n
    A(1:m,j)=A(1:m,j-1).*x;
end
% Reiknum úr úr normaljöfnuhneppinu A^TAc=A^Ty:
c=(A'*A)\(A'*y);

% Teikning undirbúin
N=100;
X=linspace(min(x),max(x),N);

% Hliðrun í reikniriti horners er 0
%
hlidrun=zeros(n,1);
for j=1:N
    Y(j)=horner(c, hlidrun, X(j));
end
figure
plot(x,y,'*',X,Y)
xlabel('x'), ylabel('y')
title('Adferd minnstu fervika fyrir marglidu af stigi 2')
print

Hér kemur myndin sem beðið var um: