Dies ist eine alte Version des Dokuments!

---

Tschebyscheff-Approximation für Analogrechner

Rainer Glaschick, Paderborn
2014-06-27

Die Approximation von Funktionen, die sich nicht als Lösung von Differentialgleichungen anbieten, erfolgt in der Regel durch Funktionsgeber auf der Basis einer Sekantenapproximation.

Eine Approximation durch Polynome erscheint dagegen ungünstig, weil wegen Runges Phänomen die Werte zwischen den Stützstellen heftig oszillieren können und im Analogrechner Multiplikationen als aufwendig und ungenau angesehen werden.

Somit wird in der Regel die Approximation durch Potenzreihen verworfen.

Impliziert wird dabei allerdings, dass die optimale Methode zur Berechnung eines Polynoms das Horner-Schema ist, weil die Potenzen von Variablen ohnehin durch Multiplikation gebildet werden. Im klassischen Analogrechner wird hingegen die Multiplikation durchaus über Quadratfunktionen durchgefüht, weil die Bildung von Quadraten, dritten und evtl. höheren Potenzen durch Sekantenapproximantion vergleichsweise wenig aufwendig ist.

Es wird daher untersucht, wie sich unter Verwendung der Tschebyscheff-Approximation Funktionen gut als Potenzreihe darstellen lassen.

Dies gilt insbesondere für symmetrische Funktionen wie ${\displaystyle sinx}$ etc., die nur gerade oder ungerade Potenzen aufweisen und gut konvergieren.

Die übliche Näherung ${\displaystyle sin\left(\frac{\pi }{2}x\right)\approx 1.5x-0.5x^3}$ hat einen maximalen Fehler von 2%; mit den verbesserten Koeffizienten ${\displaystyle 1.55x-0.55x^3}$ bleibt der Fehler unter 0.8%. Dies ist als ${\displaystyle x+0.55x(1-x^2)}$ mit einer Multiplikation und einer Quadrierung leicht zu erreichen. Für die Näherung ${\displaystyle cos\left(\frac{\pi }{2}x\right)\approx 1.00-1.22x^2+0.22x^4}$ bleibt der Fehler unter 0.2%, jeweils mit der Abbildung von 0..±1 auf 0..±90°.

Berechnung von Potenzreihen

Die Berechnung der Potenzreihe

${\displaystyle f\left(x\right)=a_n{x}^n+...+a_3{x}^3+a_2{x}^2+a_{1}x+a_0}$

durch das Hornerschema erfordert n Multiplikationen und n Additionen.

Da ein Analogrechner vollständig parallel rechnet, werden bei der Bildung von ${\displaystyle x^n}$ zwar n Multiplikationen benötigt, aber alle niedrigeren Potenzen fallen gleichzeitig mit an.

Damit kann ein Addierer mit n Eingängen die Partialsummen direkt aufsummieren, so dass nur 1 anstelle von n Addierern benötigt werden.

Auch wenn heute Steilheitsmultiplizierer preiswert sind, kann es sich lohnen, die Potenzen ${\displaystyle x^2}$ und ${\displaystyle x^3}$ als spezielle Funktionen durch Sekantenapproximation bereitzustellen.

Die Potenzen bis ${\displaystyle x^6}$ können mit 3 Quadrierern und 2 Multiplizierern berechnete werden:

${\displaystyle x^3=x^2\cdot x}$

${\displaystyle x^4={\left(x^2\right)}^2}$

${\displaystyle x^5=x^4\cdot x}$

${\displaystyle x^6={\left(x^3\right)}^2}$

Zwar sind bei direkter Bildung von ${\displaystyle x^6}$ auch 5 Multiplizierer notwendig, aber in dem obigen Schema sind höchstens 3 Elemente in Reihe, so dass Fehler weniger stark akkumulieren.

Tschebyscheff-Approximation

Theorie

Bei der Tschebyscheff-Approximation wird eine Potenzreihe durch Verteilung der Fehler durch eine Potenzreihe mit einer niedrigeren Potenz angenähert. Die Funktion muss zuvor sowohl im Argument als auch in den Funktionswerten in das Intervall ${\displaystyle [-1..+1]}$ skaliert werden, was im Analogrechner ohnehin der Fall sein muss.

Dies soll im folgenden nur für die ersten Potenzen explizit betrachtet werden.

Die ersten Tschebyscheff-Polynome sind:

${\displaystyle T_0\left(x\right)=1}$

${\displaystyle T_1\left(x\right)=x}$

${\displaystyle T_2\left(x\right)=2x^2-1}$

${\displaystyle T_3\left(x\right)=4x^3-3x}$

${\displaystyle T_4\left(x\right)=8x^4-8x^2+1}$

${\displaystyle T_5\left(x\right)=16x^5-20x^3+5x}$

${\displaystyle T_6\left(x\right)=32x^6-48x^4+18x^2-1}$

Als Rekursionsformel:

${\displaystyle T_{n+1}\left(x\right)=2x{T}_n\left(x\right)-T_{n-1}\left(x\right)}$

Ersichtlich ist ${\displaystyle T_n\left(1\right)=1}$; dies kann für die Kontrolle von Rechnungen ausgenutzt werden.

Hier wird die Eigenschaft ausgenutzt, dass die Polynome immer im Wertebereich von ${\displaystyle [-1..+1]}$ verbleiben.

Nunmehr werden die Potenzen von ${\displaystyle x}$ als Ausdrücke von Tschebyscheff-Polynomen dargestellt:

${\displaystyle x=T_1\left(x\right)}$

${\displaystyle x^2=\frac{1}{2}[T_2\left(x\right)+1]}$

${\displaystyle x^3=\frac{1}{4}[T_3\left(x\right)+3T_1\left(x\right)]}$

${\displaystyle x^4=\frac{1}{8}[T_4\left(x\right)+4T_2\left(x\right)+3]}$

${\displaystyle x^5=\frac{1}{16}[T_5\left(x\right)+5T_3\left(x\right)+10T_1\left(x\right)]}$

${\displaystyle x^6=\frac{1}{32}[T_6\left(x\right)+6T_4\left(x\right)+15T_2\left(x\right)+10]}$

${\displaystyle x^7=\frac{1}{64}[T_7\left(x\right)+7T_5\left(x\right)+21T_3\left(x\right)+35T_1\left(x\right)]}$

Allgemein:

${\displaystyle x^n=\frac{1}{2^{n-1}}[T_n+\left(\begin{array}{c}n\\ 1\end{array}\right)T_{n-2}+\left(\begin{array}{c}n\\ 2\end{array}\right)T_{n-4}+...]}$

wobei für das letzte Glied gilt:

${\displaystyle x=\{\begin{array}{ll}\frac{1}{2}\left(\begin{array}{c}n\\ \nu \end{array}\right)T_0\left(x\right)& ifn=2\nu \\ \left(\begin{array}{c}n\\ \nu \end{array}\right)T_1\left(x\right)& ifn=2\nu +1\end{array}}$

Beispiel sin(x)

Beispielsweise gilt:

${\displaystyle sinx=x-\frac{1}{6}{x}^3+\frac{1}{120}{x}^5-\frac{1}{5040}{\epsilon }^7\text{für}0\le \epsilon \le x}$

Weglassen des letzten Gliedes ergibt einen maximalen Fehler von 0.2%permil; (für x ≤ 1); damit wird (mit der abgekürzten Schreibweise ${\displaystyle T_{\iota }}$ für ${\displaystyle T_{\iota }\left(x\right)}$:

${\displaystyle sinx=x-\frac{1}{6}{x}^3+\frac{1}{120}{x}^5}$

${\displaystyle sinx=T_1-\frac{1}{24}{T}_3-\frac{3}{24}{T}_1+\frac{1}{16\cdot 120}{T}_5+\frac{5}{16\cdot 120}{T}_3+\frac{10}{16\cdot 120}{T}_1}$

${\displaystyle sinx=(1-\frac{3}{24}+\frac{1}{16\cdot 12})T_1-(\frac{1}{24}-\frac{1}{16\cdot 24})T_3+\frac{1}{1920}{T}_5}$

Da ${\displaystyle T_5}$ dem Betrag nach nicht größer als eins wird, bedeutet das Weglassen dieses Terms einen weiteren Fehler von 0.5 ‰, so dass die Näherung wird:

${\displaystyle sinx\approx 0.8802T_1-0.0391T_3}$

Rücktransformation ergibt:

${\displaystyle sinx\approx 0.8802x-0.0391(4x^3-3x)=0.9974x-0.1564x^3\approx 1.00x-0.160x^3}$

Probe für ${\displaystyle x=1}$: ${\displaystyle 0.9974-0.1564=0.8410;sin1=0.8415}$

Der maximalen Fehler ist 0.5 ‰; und 1.5‰ für die gerundeten Faktoren:

Für die Genauigkeit des Ergebnisses ist einerseits der — unkritsche — Faktor 1.00, dessen Abweichung voll wirksam ist, und der Koeffizient 0.160, dessen absoluter Fehler sich mit dem Faktor 3 auswirkt (0.1595 ist optimal).

Soll der gesamte Bereich von ${\displaystyle 0}$ bis ${\displaystyle \frac{\pi }{2}}$ abgedeckt werden, dann zunächst der Argumentbereich auf ${\displaystyle [0..1]}$ abzubilden:

${\displaystyle f\left(x\right)=sin\left(\frac{\pi }{2}x\right)=1.5708x-0.6460x^3+0.0797x^5-0.0047{\epsilon }^7\text{für}0\le \epsilon \le 1}$

Der maximale Fehler ist nunmehr 5‰, wenn die Reihe bis zur 5ten Potenz verwendet wird; und es wird:

${\displaystyle sin\left(\frac{\pi }{2}x\right)=1.5708x-0.6460x^3+0.0797x^5}$

${\displaystyle sin\left(\frac{\pi }{2}x\right)=1.5708T_1-0.1615T_3-0.4845T_1+0.005T_5+0.0249T_3+0.0498T_1}$

Weglassen von ${\displaystyle T_5}$ könnte bis zu 0.5‰ Fehler bewirken, und es wird

${\displaystyle sin\left(\frac{\pi }{2}x\right)\approx 1.1362T_1-0.1366T_3=1.1362x-0.5464x^3+0.4098x}$

${\displaystyle sin\left(\frac{\pi }{2}x\right)\approx 1.5460x-0.5464x^3\approx 1.55x-0.55x^3=x+0.55x(1-x^2)}$

Die Abweichung bleibt mit den brechneten wie auch mit den gerundeten Faktoren unter 8‰:

Mit lediglich der (negativen) Kubikfunktion, zwei Koeffizientenpotentiometern und einem Addierer kann also die Sinusfunktion sehr genau abgebildet werden; insbesondere ist die Abbildung flexibel einstellbar, ob das Argument im Bogenmass oder skaliert auf ${\displaystyle 90°\widehat{=}1}$ benötigt wird.

Beispiel cos(x)

Zwar wäre ${\displaystyle cosx=\sqrt{1-{sin}^{2}x}}$ mit einer Wurzel und einem Quadrat leicht berechenbar, aber die Tschebyscheff-Approximation benötigt keine Wurzel, sondern zweimal ein Quadrat, also einen Verstärker weniger.

Taylorentwicklung:

${\displaystyle cosx=1-\frac{1}{2}{x}^2+\frac{1}{24}{x}^4-\frac{1}{720}{x}^6+\frac{1}{40320}{x}^8}$

Abbrechen nach dem 4. Glied ist geboten, also wird:

${\displaystyle cosx\approx 1-\frac{1}{2}{x}^2+\frac{1}{24}{x}^4-\frac{1}{720}{x}^6}$

${\displaystyle c\otimes x\approx 1-\frac{1}{4}{T}_2-\frac{1}{4}+\frac{1}{192}{T}_4+\frac{1}{48}{T}_2+\frac{1}{64}-\frac{1}{23040}{T}_6-\frac{1}{3840}{T}_4-\frac{1}{1536}{T}_2-\frac{1}{2304}}$

${\displaystyle cosx\approx 0.7652-0.2298T_2+0.0049T_4=0.7652-0.4596x^2+0.2298+0.0392x^4-0.0392x^2+0.0049}$

${\displaystyle cosx\approx 0.9999-0.4988x^2+0.0392x^4\approx 1.00-0.50x^2+0.404x^4}$

Die Abweichung ist kleiner als 0.1‰ bzw. 0.15‰ für die gerundeten Koeffizienten:

Für den Bereich bis 90°, also ${\displaystyle cos\left(\frac{\pi }{2}x\right)}$, ergibt sich:

${\displaystyle cos\left(\frac{\pi }{2}x\right)\approx 1-1.2337x^2+0.2537x^4-0.0209x^6}$

${\displaystyle cos\left(\frac{\pi }{2}x\right)\approx 1-0.6169T_2-0.6169+0.0317T_4+0.1269T_2+0.0951-0.0007T_6-0.0039T_4-0.0098T_2-0.0065}$

${\displaystyle cos\left(\frac{\pi }{2}x\right)\approx 0.4717-0.4998T_2+0.0278T4=0.4717-0.9996x^2+0.4998+0.2224x^4-0.2224x^2+0.0278}$

${\displaystyle cos\left(\frac{\pi }{2}x\right)\approx 0.9993-1.2220x^2+0.2224x^4\approx 1.00-1.22x^2+0.22x^4}$

Die Abweichung ist kleiner als 1‰ für die berechneten bzw. 2‰ für die gerundeten Koeffizienten: