next up previous contents index
Next: Die Fib-Operatoren Up: Polynom Approximation Previous: Polynom Approximation   Contents   Index

Eindimensionale Polynome mit Y-Bereichen

In Fib gibt es die Problemstellung, dass ein Polynom ($f(x)=y$) interpoliert werden soll, das eine feste Zahl für die Eingabe $x$ hat, aber deren Ausgabewerte $y$ in einem Bereich liegen können. Beispielsweise ist bei Funktionen auf Ganzzahlen die Eingabe eine Ganzzahl und die Ausgabe wird auf eine Ganzzahl $y$ gerundet, wenn sie im Bereich $(y-0.5, y+0.5)$ liegt. Dies kommt in Fib unter anderen vor, wenn die Helligkeit eines Punktes in Abhängigkeit von seiner Position berechnet werden soll ( z. B. mit "$for($ $x, [1, 20],$ $fun( y$ $,mult(x,0.5),$ $pr($ $(y)_{colorGrayscale},$ $p(x,1) ) ) )$" ). Wird in diesen Fällen nicht der Freiheitsgrad für die Ausgabe ausgenutzt, sondern nur ein fester Wert aus dem möglichen Ausgabewert zur Polynominterpolation gewählt (so dass ein übliches Verfahren angewendet werden kann), kann es zu starken Schwingungen des Polynoms kommen. Dann hat das Polynom viele unnötige Faktoren, die den Speicherplatzverbrach für ein Fib-Object nur unnötig erhöhen.

Deshalb wird im Nachfolgenden ein Verfahren vorgestellt, dass dies Freiheitsgraden berücksichtigt.


gegeben:


Gesucht wird das Polynom $f(x) = \sum_{i=0}^{n} (a_i( x )^i)$; bzw. dessen Faktoren: $a_i$ mit $i=0, \ldots, n$ .


Lösung:

setze untere Grenze $a_n$ auf $-inf$ und die obere auf $+inf$


1. Lösungschema aufbauen:

\begin{eqnarray*}
yu_1 &<= a_0 + a_1( x_1 ) + \ldots + a_n( x_1 )^n &<= yo_1\\ ...
...
yu_p &<= a_0 + a_1( x_p ) + \ldots + a_n( x_p )^n &<= yo_p\\
\end{eqnarray*}


2. in Dreiecksform bringen: ( $<?>$ : Vergleich wird entsprechend gedreht wenn durch negative $x_i$ geteilt wird)

\begin{eqnarray*}
&&yu_1 <= a_0 + a_1( x_1 ) + \ldots + a_n( x_1 )^n <= yo_1\\ ...
... / x_p^n + g_p( yo_1, \ldots, yo_{n}, x_1, \ldots, x_n, x_p)\\
\end{eqnarray*}


2.b So Umformen, dass in jeder Ungleichung ein $a_i$ ($b_i$ Faktor fuer die $a_i$)

\begin{eqnarray*}
&& g_0( yu_1, \ldots, yu_{n}, x_1, \ldots, x_n, x_p) <?> b_0 ...
... / x_p^n + g_p( yo_1, \ldots, yo_{n}, x_1, \ldots, x_n, x_p)\\
\end{eqnarray*}


3. Lösungsschema umformen (zu $0 <= p$)


4. Faktoren Eingrenzen:

  1. Fuer jede Ungleichung mit maximal einen Faktor mit einer Grenze im Unendlichen:
    1. Passe Faktoren an; für jeden Faktor $f = a_i (mit i = 1, \ldots n )$ und y*; (enthaelt die Ungleichung einen inf Faktor kann nur dieser gewaehlt werden):
      1. setze anderen nicht $f$ Faktoren so (auf jeweils ihre Ober- oder Untergrenze), dass sie Formel maximieren; bestimme dann $f$ neu
  2. wenn sich in 4. Aenderungen ergeben haben zurück zu 4.
  3. beginne dann mit diesem Wert Schritt 1. "Lösungschema aufbauen" erneut solange für ein $a_i$ sich zuletzt Aenderungen ergeben haben oder es noch nicht eingegrenzt wurde
  4. Wenn alle $a_i$ mit Grenzen belegt und keine Änderungen, wähle jeweils einen Wert (den Mittelwert) fuer $a_i$ aus seinen Bereich aus; beginne mit $a_i$ mit kleinsten $i$ dessen Grenzen noch nicht gleich sind und gehe dann jeweils wieder zum Schritt 4


next up previous contents index
Next: Die Fib-Operatoren Up: Polynom Approximation Previous: Polynom Approximation   Contents   Index
Betti Österholz 2013-02-13