Interpolatie Met Afgeleiden

Het probleem

Als je een functie wil interpoleren of benaderen zijn er een paar manieren om dit te doen, bijvoorbeeld Lagrange interpolatie. Lagrange interpolatie vindt de polynoom die door n aantal punten gaat met de laagst mogelijke graad (n-1). Lagrange interpolatie heeft ook nadelen, één daarvan is bijvoorbeeld dat de polynoom snel oneindig groot of klein wordt buiten de punten. Een uitbreiding op lagrange interpolatie is Hermite interpolatie. Hermite interpolatie zorgt er niet alleen voor dat de waarden van een functie op de punten overeen komen, maar ook de afgeleiden. Dit lost het probleem deels op. De interpolant bijft langer dicht bij de orginele data/functie, maar de coëfficiënten zijn lastig te vinden.

Stelsel

Als voorbeeld benaderen we de wortel van $x$ tussen $x=9$ en $x=16$. \[p(9) = 3\] \[p(16)=4\] \[p'(9)=\frac{1}{6}\] \[p'(16)=\frac{1}{8}\] Er zijn vier voorwaarden dus hebben we een polynoom van graad 3 nodig. \[p(x)=ax^3+bx^2+cx+d\] Dit geeft een lineair stelsel die met rref op te lossen is. Dit is sloom, voor meer dan 1 afgeleide duurt dit lang.

Snellere techniek

We kunnen een hermite interpolant maken zonder dat we een ingewikkeld stelsel moeten oplossen. Begin met een lineaire interpolant van de afgeleiden: \[l(9)=\frac{1}{6}\] \[l(16)=\frac{1}{8}\] Lagrange interpolatie: \[l(x)=\frac{1}{6} \frac{x-16}{-7} + \frac{1}{8} \frac{x-9}{7} \] Integreer nu deze functie zodat we een functie ($L(x)$) krijgen, met de correcte afgeleiden. \[L(x)=\frac{1}{12} \frac{(x-16)^2}{-7} + \frac{1}{16} \frac{(x-9)^2}{7}+C \] Nu moeten we alleen nog de hoogte van deze functie corrigeren. Dit kan niet door alleen c te veranderen, omdat het ene punt meer gecorrigeerd moet worden dan het andere punt.

Correctie-functie

Om de hoogten van $L(x)$ te veranderen hebben we een functie ($C(x)$) nodig. Deze functie moet een bepaalde hoogte hebben op $x=x_0$ en $x=x_1$, én moet de afgeleide van $L(x)$ niet veranderen. Dit betekent dat: \[C'(x_0), C'(x_1) = 0\] \[C(x_0)=y_0, C(x_1)=y_1\] Deze lossen we met een stelsel symbolisch op. \[C(x)=ax^3+bx^2+cx+d\] $$ \begin{cases} a{x_0}^3+b{x_0}^2+cx_0+d = y_0\\ a{x_1}^3+b{x_1}^2+cx_1+d = y_1\\ 3a{x_0}^2+2b{x_0}+c = 0\\ 3a{x_1}^2+2b{x_1}+c = 0 \end{cases} $$

Uitwerking van het stelsel

$R1-R2$: \[ a{x_0}^3 - a{x_1}^3 +b{x_0}^2 - b{x_1}^2 + cx_0 - cx_1 + d - d = y_0 - y_1 \] \[= a({x_0}^3 - {x_1}^3) +b({x_0}^2 - {x_1}^2) + c(x_0 - x_1) = y_0 - y_1 \] We houden over: $$ \begin{cases} a({x_0}^3 - {x_1}^3) +b({x_0}^2 - {x_1}^2) + c(x_0 - x_1) = y_0 - y_1 \\ 3a{x_0}^2+2b{x_0}+c = 0 \\ 3a{x_1}^2+2b{x_1}+c = 0 \end{cases} $$

$R2-R3$: \[ 3a{x_0}^2 - 3a{x_1}^2 + 2b{x_0} - 2b{x_1} + c - c = 0 \] \[ = 3a({x_0}^2 - {x_1}^2) + 2b({x_0} - {x_1}) = 0 \]
$R1-(x_0 - x_1)R2$: \[a({x_0}^3 - {x_1}^3) - {3a{x_0}^2}(x_0 - x_1) +b({x_0}^2 - {x_1}^2) - 2b{x_0}(x_0 - x_1) + c(x_0 - x_1) - (x_0 - x_1)c = \] \[y_0 - y_1\]
\[= a(({x_0}^3 - {x_1}^3) - {3{x_0}^2}(x_0 - x_1)) +b(({x_0}^2 - {x_1}^2) - 2{x_0}(x_0 - x_1)) = y_0 - y_1 \]

Nieuw stelsel: \[ \begin{cases} 3a({x_0}^2 - {x_1}^2) + 2b({x_0} - {x_1}) = 0 \\ a(({x_0}^3 - {x_1}^3) - {3{x_0}^2}(x_0 - x_1)) +b(({x_0}^2 - {x_1}^2) - 2{x_0}(x_0 - x_1)) = y_0 - y_1 \\ \end{cases} \] $R2- \frac{({x_0}^2 - {x_1}^2) - 2{x_0}(x_0 - x_1)}{2(x_0 - x_1)}R1$ \[a(({x_0}^3 - {x_1}^3) - {3{x_0}^2}(x_0 - x_1)) +b(({x_0}^2 - {x_1}^2) - 2{x_0}(x_0 - x_1)) = y_0 - y_1\] \[-\] \[ 3a({x_0}^2 - {x_1}^2)\frac{({x_0}^2 - {x_1}^2) - 2{x_0}(x_0 - x_1)}{2(x_0 - x_1)} + b(({x_0}^2 - {x_1}^2) - 2{x_0}(x_0 - x_1)) = 0 \] \[= a(({x_0}^3 - {x_1}^3) - {3{x_0}^2}(x_0 - x_1)) - 3a({x_0}^2 - {x_1}^2)\frac{({x_0}^2 - {x_1}^2) - 2{x_0}(x_0 - x_1)}{2(x_0 - x_1)} = y_0 - y_1\] \[= a(({x_0}^3 - {x_1}^3) - {3{x_0}^2}(x_0 - x_1) - 3({x_0}^2 - {x_1}^2)\frac{({x_0}^2 - {x_1}^2) - 2{x_0}(x_0 - x_1)}{2(x_0 - x_1)}) = y_0 - y_1 \] Herleiden: \[ -\frac{a}{2}(x_{0}-x_{1})^{3} = y_0 - y_1 \] Los op voor $a$: \[ a=-2\frac{y_0 - y_1}{(x_{0}-x_{1})^{3}} \] Los op voor $b$: \[3a({x_0}^2 - {x_1}^2) + 2b({x_0} - {x_1}) = 0\] \[b = -\frac{3a({x_0}^2 - {x_1}^2)}{2({x_0} - {x_1})}\] \[b = -\frac{3}{2}a(x_0+x_1)\] Los op voor $c$: \[ 3a{x_0}^2+2b{x_0}+c = 0 \] \[ c = -3a{x_0}^2-2b{x_0} \] En als laatste lossen we op voor $d$: \[ d = y_0-a{x_0}^3-b{x_0}^2-cx_0 \]

Nu kunnen we $L(x)$ corrigeren zodat $p(9)=3, p(16)=4$: \[p(x) = C(x) + L(x) \] Waarbij: \[ x_0=9, y_0=3-L(9), x_1=4, y_1=4-L(16) \] Dit geeft uiteindelijk de polynoom: \[ p(x) = \frac{1}{12}\frac{\left(x-16\right)^{2}}{-7}+\frac{1}{16}\frac{\left(x-9\right)^{2}}{7} + \frac{1}{8232}x^3 -\frac{25}{5488}x^2 + \frac{18}{343}x + \frac{55837}{16464} \]

Iteratief process

Dit hele process (lineaire interpolant maken, deze integreren, correctie-functie berekenen met formules herleid uit het stelsel, samenvoegen van $C(x)$ en $L(x)$) kan herhaaldelijk uitgevoerd worden om een interpolant te maken die op 2 punten meer dan 1 afgeleide "matched". Als je 2 afgeleiden wilt gebruiken, begin je met $l(x)$ die door de tweede afgeleide gaat op $x_0, x_1$. Integreer deze en voeg de correctie-functie toe, en zorg dan dat de hoogten van de functie de eerste afgeleiden zijn. Integreer vervolgens $p(x)$ en voeg een CF toe. ect.

Meer punten

Voor 2 punten werkt deze techniek, alleen het is ingewikkelder met 3 of meer punten. De eerste stap blijft hetzelfde: Interpoleer de afgeleide (1e, 2e, n-ste, afhankelijk van het totaal aantal afgeleiden dat je wil gebruiken in de interpolant) met Lagrange interpolatie, en integreer deze vervolgens. Dan moeten de hoogten van $L(x)$ gecorrigeert worden, en we hebben weer een correctie-functie nodig. Dit keer geld voor de CF dat: \[ C(x_n)=y_n \] \[ C'(x_n)=0 \] In principe kan de CF nu ook gevonden worden door een stelsel symbolisch op te lossen, alleen dit is een hoop werk, en geen elegante oplossing.

Generalisatie van de CF

Om de gegeneraliseerde CF te vinden voor $n$-aantal punten breken we de CF eerst op in stukjes: \[ {C_k}(x_n) = 0, n \neq k \] \[ {C_k}(x_k) = 1 \] \[ {C_k}'(x_n) = 0 \] $ {C_k}(x) $ kan geschreven worden in de vorm: \[ C_k(x)=\frac{(1+{m_k}x)f_k(x)}{(1+{m_k}x_k)f_k(x_k)} \] $ f_k(x_k)= 1$ (zie definitie $f_k(x)$): $ {C_k}(x) $ kan geschreven worden in de vorm: \[ C_k(x)=\frac{(1+{m_k}x)f_k(x)}{1+{m_k}x_k} \] Waarbij \[ f_k(x)=(\prod_{0,n\neq k}^{n-1}{\frac{x-x_n}{x_k-x_n}})^2 \] $f(x)$ zorgt ervoor dat bij alle punten behalve $x_k$ geldt: $f(x_n)$. De factor $ 1+m_k $ word zo gekozen dat ${C_k}'(x_k)=0$. De waarden van $m_k$ kan als volgt gevonden worden: \[ ((1+{m_k}x_k)f_k(x_k))'=0 \] \[ {f_k(x_k)(1+{m_k}x_k)}'=0 \] \[ {f_k}'(x_k)(1+{m_k}x_k)+f_k(x_k)(1+{m_k}x_k)'=0 \] \[ {f_k}'(x_k)+{f_k}'(x_k){m_k}x_k+f_k(x_k)(m_k)=0 \] \[ {f_k}'(x_k)+m_k({f_k}'(x_k) x_k+f_k(x_k))=0 \] \[ m_k=\frac{-{f_k}'(x_k)}{{f_k}'(x_k) x_k+f_k(x_k)} \] $ f_k(x_k)= 1$ \[ m_k=\frac{-{f_k}'(x_k)}{{f_k}'(x_k) x_k+1} \]

$m$ verandert langzaam van 0 naar de berekende waarde. $f_0$ (rood) berekend met: $x_0=9, x_1=16, x_2=25$. De raaklijn van $f_0(x_0)$ is zwart. We delen

Nu kunnen we de volledige gegeneraliseerde CF opbouwen. We kunnen $C_0(x) + C_1(x) + ...$ gebruiken zonder dat dit de afgeleide of hoogten verandert op $x_n$. Sinds alle hoogten op $x_n$ 1 zijn, kunnen we de betreffende $C_n$ vermenigvuldigen met $y_n$. Dit geeft: \[ C(x)=\sum_{k=0}^{k=n-1}y_kC_k(x) \] Of uitgeschreven: \[ C(x)=\sum_{k=0}^{k=n-1}y_k\frac{(1+{m_k}x)f_k(x)}{1+{m_k}x_k} \] \[ m_k=\frac{-{f_k}'(x_k)}{{f_k}'(x_k) x_k+1} \] Door $m_k$ in te vullen in $\frac{(1+{m_k}x)f_k(x)}{1+{m_k}x_k}$ kan de expressie versimpeld worden naar: \[ C(x)=\sum_{k=0}^{k=n-1}y_{k}f_{k}(x)(f_{k}'(x_{k})(x_{k}-x)+1) \]