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:

• Punkte (mit den Bereichen für den Ausgabewert): $P_1( x_1, (yu_1,yo_1 )), \ldots,$ $P_p( x_p, y_p \in (yu_p,yo_p ))$
• der maximale Grad des Polynoms $n$, mit $n < p$

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)

• mit $a_k$ ist das $a_i$ mit groessten $i$, dessen untere und ober Grenze nicht gleich ist
• $as_{n}$ ist der konstante Faktor, der sich aus den $a_i$ mit jeweils gleicher untere und ober Grenze und dem $x$ Wert der Ungleichung ergibt

$$\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