Akima-Interpolation

Die Akima-Interpolation ist ein mathematisches Verfahren der Numerik zur Spline-Interpolation. Ein Spline ist eine Funktion, die stückweise aus Polynomen besteht. Bei der Akima-Interpolation werden die Stützstellen durch Polynome dritten Grades verbunden. An den Stützstellen wird allerdings nicht - wie oft üblich - gefordert, dass die zweite Ableitung des Splines stetig ist. Die Forderung der Stetigkeit erzeugt damit Überschwinger bei starken Gradientänderungen. Die Akima-interpolierte Kurve verläuft durch jeden Stützpunkt und beschreibt von Stützpunkt zu Stützpunkt einen homogenen Kurvenverlauf. Kann auf die Stetigkeit der zweiten Ableitung nicht verzichtet werden, so ist die Akima-Interpolation per definitionem ungeeignet. Soll die zweite Ableitung in einer anderen Form von Interpolation in die Berechnung einfließen, müsste diese fehlertolerant sein. Bei solchen Anwendungen führt auch der Mittelwert aus den zweiten Ableitungen der Polynome links und rechts der Stützstellen zu genügend genauen Ergebnissen. Diese Methode wurde im Jahr 1970 von Hiroshi Akima entwickelt.[1]

Verfahren

Akima ging bei seinem Verfahren auf die Grundüberlegung der Interpolation zurück: Was geschieht, wenn eine Kurve manuell gezeichnet wird? Offensichtlich wird beim Zeichnen nur ein lokales Teilintervall von Punkten berücksichtigt. Dieser Aspekt war es, den er in eine mathematische Form brachte.

Definiert man im i-ten Intervall ein Polynom der Form

${\displaystyle p_{i}(x)=a_{i}+b_{i}(x-x_{i})+c_{i}(x-x_{i})^{2}+d_{i}(x-x_{i})^{3}}$

mit der Bedingung, dass diese Funktion durch die i-te und i+1-te Stützstelle verläuft, also dass gilt:

${\displaystyle p_{i}(x_{i})=y_{i}}$

${\displaystyle p_{i}(x_{i+1})=y_{i+1}}$

und dass der Gradient der Funktion in den Stützstellen eine noch zu bestimmende Steigung aufweist,

${\displaystyle p_{i}'(x_{i})=t_{i}}$

${\displaystyle p_{i}'(x_{i+1})=t_{i+1}}$

so können die Polynomkoeffizienten berechnet werden:

${\displaystyle a_{i}=y_{i}}$

${\displaystyle b_{i}=t_{i}}$

${\displaystyle c_{i}={\frac {3{\frac {y_{i+1}-y_{i}}{x_{i+1}-x_{i}}}-t_{i+1}-2t_{i}}{x_{i+1}-x_{i}}}}$

${\displaystyle d_{i}={\frac {t_{i+1}+t_{i}-2{\frac {y_{i+1}-y_{i}}{x_{i+1}-x_{i}}}}{{(x_{i+1}-x_{i}})^{2}}}}$.

Diese Art der Koeffizientenbestimmung ist als Hermite-Interpolation bekannt. Hiroshi Akima bestimmte die Steigung t_i am i-ten Punkt mit Hilfe von je zwei rechts und links benachbarten Punkten. Das Kernstück der Akima-Interpolation ist die Steigungsformel. Sie liefert aus den Geradensteigungen m_i die Steigung t_i der Interpolation an der Stelle ${\displaystyle x_{i}}$.

${\displaystyle m_{i}={\frac {y_{i+1}-y_{i}}{x_{i+1}-x_{i}}}}$

${\displaystyle t_{i}={\frac {|m_{i+1}-m_{i}|m_{i-1}+|m_{i-1}-m_{i-2}|m_{i}}{|m_{i+1}-m_{i}|+|m_{i-1}-m_{i-2}|}}}$

Zum Verständnis der Wirkungsweise dieses Ausdrucks kann man die vier folgenden Fälle betrachten:

1. t_i = m_i-1 ,wenn m_i-2 = m_i-1 und m_i ≠ m_i+1
2. t_i = m_i ,wenn m_i-2 ≠ m_i-1 und m_i = m_i+1
3. t_i = m_i-1 ,wenn m_i-1 = m_i
4. t_i = ${\textstyle {\frac {1}{2}}}$ (m_{i-1 +} m_i) ,wenn m_i-2 = m_i-1 und m_i = m_i+1

Da n Steigungen berechnet werden müssen, sind zwei extrapolierte Punkte links und rechts vom Wertebereich notwendig. Diese werden durch je ein Polynom zweiten Grades bestimmt, das mit Hilfe der letzten drei Stützstellen ermittelt wird. Dazu gelten für die Stützstellen ${\displaystyle x_{i}}$ die Vorgaben

${\displaystyle x_{3}-x_{1}=x_{2}-x_{1}=x_{1}-x_{2}}$

und

${\displaystyle x_{n}-x_{n-2}=x_{n+1}-x_{n-1}=x_{n+2}-x_{n}}$.

Damit sind die vier Koeffizienten für alle ${\displaystyle n-1}$-Polynome bestimmt.[2]

Einzelnachweise

1. Hiroshi Akima: A new method of interpolation and smooth curve fitting based on local procedures. In: Journal of the ACM. 17. Jahrgang, 1970, S. 589–602 (ufpr.br [PDF]). 
2. Heinz Heise GmbH & Co. KG (Hrsg.): c’t Magazin für Computertechnik. Heft Nr. 6. Hannover 1989.