Verfolgungswurzelwurzel des sich bewegenden Wertes

Question

Ich habe einen Regelkreis, der mit hoher Frequenz läuft und jeden Zyklus eine Quadratwurzel berechnen muss. Typische Quadratwurzelfunktionen funktionieren gut, erfordern jedoch übermäßige Zeit. Da der Wert, den ich der Quadratwurzel nehme, sich nicht zu sehr bei jedem Zyklus ändert, würde ich gerne eine iterative Quadratwurzel finden, die konvergiert und dann das korrekte Ergebnis verfolgt. Auf diese Weise konnte ich bei jedem Zeitschritt eine einzige Iteration durchführen, anstatt viele.

Das Problem ist, dass alle iterativen Quadratwurzel-Methoden, die ich gesehen habe, wahrscheinlich fehlschlagen werden, wenn sich die Eingabe ändert. Insbesondere sieht es so aus, als würde es Probleme geben, wenn die Eingabe auf Null geht und dann wieder zunimmt - die Methoden möchten nicht mit einer Schätzung von Null beginnen.

Mein Eingabebereich ist 0-4,5 und ich brauche eine Genauigkeit von etwa 0,01, also könnte die Verwendung eines Inkrementes/Dekrements von 0,01 viel zu lange dauern - ich möchte, dass es in 10 Zyklen oder weniger konvergiert.

FYI Ich verwende 16/32bit Festpunkt der Eingang ist 16bit q12. Es ist auf einem Mikrocontroller, also bin ich nicht daran interessiert, 1K für eine Nachschlagetabelle zu verwenden. Der Code wird auch aus einem Simulink-Modell generiert, und ihre Tabellen-Lookup-Funktionen sind ziemlich voll mit Overhead.

Gibt es eine schöne Lösung?

Answer 1

Sie können eine Aufnahme der Halley-Methode verwenden. Es hat kubische Konvergenz und sollte daher ganz genau sein, wenn der Wert etwas bewegt:

x_{n+1} = x_n * (x_n^2 + 3Q)/(3 x_n^2 + Q) 

Diese cubcially zu sqrt(Q) konvergiert.

Referenz: http://www.mathpath.org/Algor/squareroot/algor.square.root.halley.htm

Answer 2

der Bereich 0-4,5 ist ziemlich klein. Mit einer Genauigkeit von 0,01 sind das nur 450 mögliche Berechnungen. Sie könnten sie alle zur Kompilierzeit als Konstanten berechnen und nur zur Laufzeit nachschlagen.

Answer 3

Ich würde vorschlagen, dass Sie eine Nachschlagetabelle verwenden, wenn Sie in den Bereichen wissen, mit denen Sie es zu tun haben. Generieren Sie eine Array- oder Hash-Tabelle (abhängig von der Sprache, in der Sie arbeiten) mit der Genauigkeitsstufe, die Sie benötigen, und beziehen Sie sich darauf, wenn Sie Ihre Roots benötigen.

Answer 4

habe ich versucht, eine zweite Ordnung Taylorentwicklung auf sqrt(x) und folgendes Ergebnis

wenn y=sqrt(x) gehe und Sie wissen y_c = sqrt(x_c) schon damals:

t = x-3*x_c; 
y = (12*x_c*x_c-t*t)/(8*y_c*y_c*y_c); 

Je größer x desto besser ist die Annäherung. Für den schlimmsten Fall mit x_c=0.01 und x=0.02 ergibt sich das Ergebnis 0.1375 gegenüber dem realen Ergebnis sqrt(0.02)=0.1414 oder ein Unterschied von 0.0039, der unter 0.01 ist.

Ich testete den Code mit C# und sah eine stetige 33% Beschleunigung vs Math.Sqrt().