no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Vorhergehende Überarbeitung | |||
— | analogrechner:tschebyscheffapproximation [2023-02-06 02:11] (aktuell) – tippfehler rainer | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | < | ||
+ | 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 " | ||
+ | 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, | ||
+ | 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..& | ||
+ | |||
+ | |||
+ | |||
+ | 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 ' | ||
+ | |||
+ | Da ein Analogrechner vollständig parallel rechnet, werden bei der Bildung | ||
+ | von `x^n` zwar ' | ||
+ | fallen gleichzeitig mit an. | ||
+ | |||
+ | Damit kann ein Addierer mit ' | ||
+ | so dass nur ' | ||
+ | |||
+ | 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), | ||
+ | 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 " | ||
+ | |||
+ | Weglassen des letzten Gliedes ergibt einen maximalen Fehler von 0.2%permil; (für x ≤ 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 & | ||
+ | `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 & | ||
+ | |||
+ | [img: | ||
+ | |||
+ | 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 " | ||
+ | |||
+ | Der maximale Fehler ist nunmehr 5& | ||
+ | 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& | ||
+ | `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& | ||
+ | |||
+ | [img: | ||
+ | |||
+ | |||
+ | Mit lediglich der (negativen) Kubikfunktion, | ||
+ | kann also die Sinusfunktion sehr genau abgebildet werden; | ||
+ | insbesondere ist die Abbildung flexibel einstellbar, | ||
+ | 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, | ||
+ | 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& | ||
+ | |||
+ | [img: | ||
+ | |||
+ | |||
+ | 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& | ||
+ | |||
+ | [img: | ||
+ | |||
+ | |||
+ | |||
+ | \CSS all blockquote { font-style: | ||
+ | |||
+ | \ASCIIMATHML ./ | ||
+ | |||
+ | </ |