Chebyshev-Approximationsrechner

 (stuffmatic.com)
2 Punkte von GN⁺ 2024-10-06 | 1 Kommentare | Auf WhatsApp teilen
  • Der Chebyshev approximation calculator ist ein Tool, das im Web Code zur Approximation mathematischer Funktionen erzeugt
  • Nutzer können mit f(x), x min, x max und Terms die zu approximierende Funktion, das Intervall und die Anzahl der Terme festlegen
  • Über die Option Match x min x max und den Bereich Coefficients bietet es einen Ablauf, um Intervallgrenzen und Koeffizientenwerte zu prüfen oder anzupassen
  • Im Bereich Generated code werden die Berechnungsergebnisse in Codeform angezeigt; im Beispielbild sind Koeffizienten von c0 bis c10 zu sehen
  • Ein GitHub-Repository ist verknüpft, sodass sich der Implementierungscode des Web-Tools direkt einsehen lässt

Chebyshev-Approximations-Codegenerator

  • Der Chebyshev approximation calculator erzeugt Code zur effizienten Approximation mathematischer Funktionen
  • In der Web-UI werden die Approximationsbedingungen eingegeben
    • f(x): die zu approximierende Funktion
    • x min: Minimalwert des Intervalls
    • x max: Maximalwert des Intervalls
    • Terms: Anzahl der zu verwendenden Terme
    • Match x min x max: Option in Bezug auf die Intervallgrenzen

Koeffizienten prüfen und Code erzeugen

  • Die Oberfläche ist in die Bereiche Coefficients und Generated code unterteilt
  • Die im Beispiel angezeigten Koeffizienten reichen von c0 bis c10
    • c0 = 0.16793649417016518
    • c1 = -0.12411164956092625
    • c2 = -0.09756341588422193
    • c3 = 0.1800765790518846
    • c4 = -0.06972963647223016
    • c5 = -0.09250127939333941
    • c6 = 0.18076946080324185
    • c7 = 0.15990613621816677
    • c8 = -0.028659588693985123
    • c9 = -0.09494966104347571
    • c10 = -0.04980429834982578
  • Auf dem Bildschirm werden außerdem Koeffizienteneinträge von c11 bis c39 angezeigt

Code-Repository

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-10-06
Hacker-News-Kommentare

  • Sehr schön. Um 1974 herum habe ich einmal eine Funktion zur Berechnung von Quadratwurzeln in IBM-360-Assembler geschrieben und dafür Geld bekommen.
    Ich war im letzten Jahr meines Bachelorstudiums und man hatte mich gebeten, sie so effizient wie möglich zu machen. Ich skalierte die Eingabe auf den Bereich zwischen 0 und 1, verwendete für die Anfangsschätzung eine Tschebyscheff-Approximation und löste das Ganze dann mit zwei oder drei entfalteten Iterationen des Newton-Verfahrens. Das war mein erstes Einkommen fürs Programmieren.

    • Solche Geschichten mag ich. Ich erinnere mich noch daran, wie mir im ersten Numerik-Kurs die Augen aufgingen, als ich zum ersten Mal das Potenzial des Rechnens wirklich begriff.

  • Wirklich gut gemacht. Ich war fasziniert davon, wie effizient solche Approximationen sind, und habe viel besser verstanden, warum trigonometrische und andere mathematische Funktionen auf 8-Bit-Computern genau so implementiert wurden.
    Es gibt auch ein großartiges Originaldokument der BBC Research Department von 1969 darüber, warum diese Methode so gut ist: https://downloads.bbc.co.uk/rd/pubs/reports/1969-10.pdf
    Wenn man bisher nur Taylor-Approximationen kennengelernt hat, kann das anfangs ein wenig wie Magie wirken.

    • Ja. Sowohl mathematisch als auch in der Tatsache, dass es in der Praxis auf ein paar Zeilen Code hinausläuft, fühlt es sich ziemlich magisch an.

  • Ich habe früher mit Sollya gute Ergebnisse erzielt: https://www.sollya.org/
    Die Ergebnisse waren gut, aber die Software selbst ist etwas umständlich zu benutzen.

    • Sollya ist vermutlich eines der besten modernen Werkzeuge für diese Art von Aufgabe. Intern macht es eine Remez-Approximation und quantisiert dann mit LLL auf Gleitkommawerte; Tschebyscheff wird nicht direkt verwendet.

  • Wenn man Math.sin(x)/x, also die sinc-Funktion, im Intervall [-3,3] mit 7 Termen approximiert, werden alle Koeffizienten c0...c6 zu NaN. Ist das ein Bug?
    Als Workaround habe ich für den Fall, dass x nahe 0 liegt, einfach 1.0 erzwungen.
    if(Math.abs(x) > 1e-8 ){ Math.sin(x)/x } else { 1.0 }

    • Es ist schwer, das genau als Bug zu bezeichnen. Der Code wertet die Funktion vermutlich an Gitterpunkten wie x_j = (xmin) + (xmax - xmin)/2(1 + cos(pi[0..j-1]/(j-1)) aus, um die Tschebyscheff-Koeffizienten zu berechnen. Wenn einer davon exakt 0 ist, wird Math.sin(0)/0 berechnet, was NaN ergibt.
      Ein anderer Workaround ist, einen leicht asymmetrischen Bereich wie [-3,+3.0000001] zu verwenden.
    • Das Problem ist hier, dass der erste Ausdruck bei x=0 nicht wohldefiniert ist, und der Approximationscode scheint genau dort zu scheitern. Der Code ist etwas schade.
    • Ja, das ist ein Bug. Wenn die Funktion nicht an allen Tschebyscheff-Knoten definiert ist, sollte die App einen Fehler anzeigen. Wie du schon herausgefunden hast, lässt sich das im Moment leicht umgehen.

  • Tschebyscheff-Polynome sind bei Approximationen so mächtig und vielseitig, dass Leute sie für zu gut halten, um wahr zu sein, und sie deshalb nicht verwenden.
    Die erste Methode, die man ausprobieren sollte, sollte Tschebyscheff sein. Neuronale Netze sollten der letzte Ausweg sein.

  • Hervorragend. Ich wollte so etwas kürzlich machen, und es war überraschend schwer, Code zu finden, der Approximationen berechnet.
    Ich habe es als Lesezeichen gespeichert, um es zu verwenden, wenn ich das nächste Mal schnell eine Funktion approximieren muss.

    • Es war auch für mich überraschend schwierig, tatsächlich funktionierenden Code für Tschebyscheff-Approximationen zu finden. Hoffentlich ändert dieses Projekt das.

  • Tschebyscheff wirkt wie schwarze Magie. Selbst nachdem ich die Herleitung in einem Graduiertenkurs gesehen habe, fühlt es sich so an.

  • Chebfun von Nick Trefethen und anderen sollte unbedingt erwähnt werden. Das ist ein Werkzeug, das dieses Thema in praktisch jede denkbare Richtung erweitert.
    Chebfuns kann man als Gegenstücke zu Funktionen sehen, so wie Gleitkommazahlen Gegenstücke zu tatsächlichen mathematischen Zahlen sind. Eine wirklich beeindruckende Software.
    https://www.chebfun.org

    • Zustimmung. Diese Methoden sind sehr leistungsfähig und schnell. Mit auf Tschebyscheff und ultrasphärischen Funktionen basierenden Verfahren lassen sich die meisten Funktionen sehr schnell bis auf Maschinengenauigkeit approximieren, und danach kann man diese Darstellung leichter weiterverarbeiten.
      Dadurch werden viele Verfahren möglich, etwa Lösungen von differential-algebraischen Gleichungen mit Maschinengenauigkeit zu finden oder globale Minima/Maxima eindimensionaler Funktionen zu bestimmen.
      Soweit ich weiß, verwenden sie inzwischen andere Algorithmen, aber die frühere grundlegende Methodik von Chebfun findet man in Kapitel 6 von Trefethens Buch Spectral Methods in Matlab. Die neuere Methodik mit ultrasphärischen Funktionen wird im SIAM-Review-Artikel A Fast and Well-Conditioned Spectral Method von Olver und Townsend beschrieben.

  • Ich habe eine Frage, bin mir aber nicht sicher, ob sie hierher passt. Ich habe einmal ein Video gesehen, in dem es hieß, dass der Nintendo 64 nicht die Fähigkeit hatte, die Sinusfunktion zu berechnen, und daher eine Lookup-Tabelle von 0 bis 2π verwendete, inklusive cleverer Techniken zur Verkleinerung der Tabelle.
    Wäre es auch möglich gewesen, ein neuronales Netz zu trainieren und seine Gewichte zu speichern, oder eine Funktion zu erstellen und deren Koeffizienten zu speichern, um Sinus und Kosinus zu berechnen?

    • Neuronale Netze verwenden intern oft trigonometrische Funktionen, daher würde das viel mehr Rechenaufwand bedeuten, als nötig ist.
      Wenn ein paar CPU-Zyklen übrig sind, könnte man eine hybride Approximation verwenden, bei der Werte aus einer groben Lookup-Tabelle als Anfangsschätzung dienen und dann einige Iterationen numerischer Approximationsverfahren folgen. Oder man speichert, wie im Originalbeitrag, nur einige der ersten Koeffizienten einer Polynomapproximation.
    • Wenn du damit nicht vertraut bist, schau dir CORDIC an. Früher war das ein gängiger Trick für trigonometrische Funktionen, und im Embedded-Bereich wird es bis heute in gewissem Umfang verwendet.
      Neuronale Netze können nützlich sein, wenn man Samples einer Funktion hat, aber nicht weiß, wie man sie approximieren soll; hier ist das aber nicht der Fall.
    • Natürlich ist es möglich, ein neuronales Netz darauf zu trainieren, eine beliebige Funktion zu berechnen, aber bei einer so gut bekannten Funktion wie Sinus ergibt das überhaupt keinen Sinn.
      Neuronale Netze sind eine großartige Lösung, wenn man etwas auswerten muss, das mathematisch schwer zu analysieren ist, aber für die Berechnung und Approximation trigonometrischer Funktionen gibt es bereits viele bekannte Verfahren.
      Ein neuronales Netz zum Berechnen von Sinus zu trainieren ist wie die mathematische Version davon, ein LLM zum Umkehren eines Strings zu verwenden. Es geht, aber auf die Idee kommt man nur, wenn man nicht weiß, dass das Problem im Kern durch einen direkteren Ansatz gelöst ist.
      Es lohnt sich immer zu prüfen, ob Mathematiker bereits eine Lösung haben, bevor man AI/ML-Verfahren einsetzt. Heutzutage wird wahrscheinlich viel Aufwand darauf verwendet, AI/ML auf Probleme anzuwenden, für die es bereits bekannte, effiziente und sogar optimale Lösungen gibt, die Entwickler nur nicht kennen.
    • Neuronale Netze sind im Wesentlichen Kurvenanpassung, also ist es möglich. Dieses Video könnte hilfreich sein: https://www.youtube.com/watch?v=FBpPjjhJGhk But what is a neural network REALLY?
      Die Hauptstärke neuronaler Netze zeigt sich, wenn es nicht nur wenige, sondern sehr viele Eingaben gibt. Für einen einfachen Fall wie sin(x) gibt es andere Methoden, etwa das hier vorgestellte Tool.
    • Die übliche Spartechnik besteht darin, nur die Werte von 0 bis π/2 in einer Tabelle zu speichern und mit zwei zusätzlichen Index-Bits die übrigen drei Quadranten zu erzeugen.

  • Sehr cool. Aus Spieltrieb wollte ich sehen, wie schnell ich eine Funktion finden kann, die sich schlecht approximieren lässt.
    Bisher war Math.cos(x * Math.exp(Math.cos(x * x))) am besten. Durch die vielen Kompositionen entstehen schnelle Oszillationen und steile Gradienten, wodurch es für Tschebyscheff schwer wird, sie einfach zu approximieren.