Retro Computer Laboratory

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
<nimla>
Tschebyscheff-Approximation für Analogrechner
Autor: Rainer Glaschick, Paderborn
Datum: 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 `sin x` etc.,
die nur gerade oder ungerade Potenzen aufweisen und gut konvergieren.

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



Berechnung von Potenzreihen
===========================

Die Berechnung der Potenzreihe
	`f(x) = 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 `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 `x^2` und `x^3` als spezielle Funktionen
durch Sekantenapproximation bereitzustellen.

Die Potenzen bis `x^6` können mit 3 Quadrierern und 2 Multiplizierern berechnete werden:
	`x^3 = x^2 * x`
	`x^4 = ( x^2 )  ^2
	`x^5 = x^4 * x
  	`x^6 = (x^3)^2

Zwar sind bei direkter Bildung von `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 `[-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:
	`T_0 (x) = 1
	`T_1 (x) = x
	`T_2 (x) = 2 x^2 - 1
	`T_3 (x) = 4 x^3 - 3 x
	`T_4 (x) = 8 x^4 - 8 x^2 + 1
	`T_5 (x) = 16 x^5 - 20 x^3 + 5 x
	`T_6 (x) = 32 x^6 - 48 x^4 +18 x^2 - 1

Als Rekursionsformel:
	`T_(n+1) (x) = 2x T_n (x) - T_(n-1) (x)

Ersichtlich ist `T_n (1) = 1`; dies kann für die Kontrolle von Rechnungen
ausgenutzt werden.


Hier wird die Eigenschaft ausgenutzt, dass die Polynome immer im Wertebereich
von `[-1..+1]` verbleiben.

Nunmehr werden die Potenzen von `x` als Ausdrücke von Tschebyscheff-Polynomen
dargestellt:
	`x = T_1 (x)
	`x^2 = 1/2  [T_2 (x) + 1]
	`x^3 = 1/4  [T_3 (x) + 3 T_1 (x)]
	`x^4 = 1/8  [T_4 (x) + 4 T_2 (x)  + 3]
	`x^5 = 1/16 [T_5 (x) + 5 T_3 (x) + 10 T_1 (x) ]
	`x^6 = 1/32 [T_6 (x) + 6 T_4 (x) + 15 T_2 (x) + 10]
	`x^7 = 1/64 [T_7 (x) + 7 T_5 (x) + 21 T_3 (x) + 35 T_1 (x)]

Allgemein:
	`x^n = 1/2^(n-1) [T_n + ((n),(1))T_(n-2) + ((n),(2))T_(n-4)  + ...]`
wobei für das letzte Glied gilt:
	`x={ (1/2 ((n),(nu)) T_0 (x) , if n = 2nu), ( ((n),(nu)) T_1 (x), if n = 2nu + 1) :}`



Beispiel sin(x)
---------------

Beispielsweise gilt:
	`sin x = x - 1/6 x^3 + 1/120 x^5 - 1/5040 epsilon^7 " " "für "  0 <= epsilon <=x`

Weglassen des letzten Gliedes ergibt einen maximalen Fehler von 0.2%permil; (für x &le; 1);
damit wird (mit der abgekürzten Schreibweise `T_iota` für `T_iota (x)`:
	`sin x = x - 1/6 x^3 + 1/120 x^5
	`sin x = T_1 - 1/24 T_3 - 3/24 T_1 + 1/(16*120) T_5 + 5/(16*120) T_3 + 10/(16*120) T_1
	`sin x = (1 - 3/24 + 1/(16*12)) T_1 - (1/24 - 1/(16*24)) T_3 + 1/1920 T_5

Da `T_5` dem Betrag nach nicht größer als eins wird, bedeutet das Weglassen
dieses Terms einen weiteren Fehler von 0.5 &permil;, so dass die Näherung wird:
	`sin x ~~ 0.8802 T_1 - 0.0391 T_3

Rücktransformation ergibt:
	`sin x ~~ 0.8802 x - 0.0391(4 x^3 - 3 x) = 0.9974 x -0.1564 x^3 ~~ 1.00x - 0.160 x^3

Probe für `x=1`: `0.9974 - 0.1564 = 0.8410; sin 1 = 0.8415`

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

[img:analogrechner/Tschebyscheff-Approximation-graph1.png]

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 `0` bis `pi / 2` abgedeckt werden,
dann zunächst der Argumentbereich auf `[0..1]` abzubilden:
	`f(x) = sin (pi/2 x) = 1.5708 x - 0.6460 x^3 + 0.0797 x^5 - 0.0047 epsilon^7 " " "für "  0 <= epsilon <= 1`

Der maximale Fehler ist nunmehr 5&permil;, wenn die Reihe bis zur 5ten Potenz verwendet wird;
und es wird:
	`sin (pi/2 x) = 1.5708 x - 0.6460 x^3 + 0.0797 x^5
	`sin (pi/2 x) = 1.5708 T_1 - 0.1615 T_3 - 0.4845 T_1 + 0.005 T_5 + 0.0249 T_3 + 0.0498 T_1

Weglassen von `T_5` könnte bis zu 0.5&permil; Fehler bewirken, und es wird
	`sin (pi/2 x) ~~ 1.1362 T_1 - 0.1366 T_3 = 1.1362 x - 0.5464 x^3 + 0.4098 x
	`sin (pi/2 x) ~~ 1.5460 x - 0.5464 x^3 ~~ 1.55 x - 0.55 x^3 = x + 0.55 x (1-x^2)

Die Abweichung bleibt mit den brechneten wie auch mit den gerundeten Faktoren
unter 8&permil;:

[img:analogrechner/Tschebyscheff-Approximation-graph2.png]


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 `90° stackrel (^) (=) 1` benötigt wird.


Beispiel cos(x)
---------------

Zwar wäre `cos x = 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:
	`cos x = 1 - 1/2 x^2 + 1/24 x^4 - 1/720 x^6 + 1/40320 x^8`

Abbrechen nach dem 4. Glied ist geboten, also wird:
	`cos x ~~ 1 - 1/2 x^2 + 1/24 x^4 - 1/720 x^6
	`cos x ~~ 1 - 1/4 T_2 - 1/4 + 1/192 T_4 + 1/48 T_2 + 1/64 - 1/23040 T_6 - 1/3840 T_4 - 1/1536 T_2 - 1/2304
	`cos x ~~ 0.7652 - 0.2298 T_2 + 0.0049 T_4 = 0.7652 - 0.4596 x^2 + 0.2298 + 0.0392 x^4 - 0.0392 x^2 + 0.0049
	`cos x ~~ 0.9999 - 0.4988 x^2 + 0.0392 x^4 ~~ 1.00 - 0.50 x^2 + 0.404 x^4

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

[img:analogrechner/Tschebyscheff-Approximation-graph3.png]


Für den Bereich bis 90°, also `cos (pi / 2 x)`, ergibt sich:
	` cos (pi/2 x) ~~ 1 - 1.2337 x^2 + 0.2537 x^4 - 0.0209 x^6
	` cos (pi/2 x) ~~ 1 - 0.6169 T_2 - 0.6169 + 0.0317 T_4 + 0.1269 T_2 + 0.0951 - 0.0007 T_6 - 0.0039 T_4 - 0.0098 T_2 - 0.0065
	` cos (pi/2 x) ~~ 0.4717 - 0.4998 T_2 + 0.0278 T4 = 0.4717 - 0.9996 x^2 + 0.4998 + 0.2224 x^4 - 0.2224 x^2 + 0.0278
	` cos (pi/2 x) ~~ 0.9993 -1.2220 x^2 + 0.2224 x^4 ~~ 1.00 - 1.22 x^2 + 0.22 x^4

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

[img:analogrechner/Tschebyscheff-Approximation-graph4.png]



\CSS all blockquote { font-style:italic; }

\ASCIIMATHML ./ASCIIMathML.js

</nimla>