So funktioniert die Annäherungssuche

Lesezeit: 9 Minuten

So funktioniert die Annaherungssuche
Gespenst

[Prologue]

Dies Fragen und Antworten soll das Innenleben meiner Näherungssuchklasse, die ich hier zuerst veröffentlicht habe, deutlicher erklären

  • Erhöhung der Genauigkeit der Lösung der transzendenten Gleichung

Ich wurde bereits einige Male um genauere Informationen dazu gebeten (aus verschiedenen Gründen), also beschloss ich, zu schreiben Fragen und Antworten Stilthema dazu, auf das ich in Zukunft leicht zurückgreifen kann und es nicht immer wieder erklären muss.

[Question]

So approximieren Sie Werte/Parameter im Realbereich (double) um die Anpassung von Polynomen, parametrischen Funktionen zu erreichen oder (schwierige) Gleichungen (wie transzendentale) zu lösen?

Einschränkungen

  • echte Domäne (double Präzision)
  • C++ Sprache
  • konfigurierbare Näherungsgenauigkeit
  • bekanntes Suchintervall
  • Angepasster Wert/Parameter ist nicht streng monoton oder funktioniert überhaupt nicht

  • Dippy-Frage: Warum sind Runge-Kutta- oder Newton-Raphson-Methoden hier nicht anwendbar?

    – scooter me fecit

    22. März 2016 um 20:12 Uhr

  • @ScottM sind sie nicht nur auf Funktionen beschränkt?

    – Spektre

    22. März 2016 um 20:17 Uhr

  • @Spektre: Wenn Sie die erste Ableitung (Delta y’s) berechnen, ist die Integration über Runge-Kutta oder die Annäherung über Newton-Raphson möglicherweise die bessere Wahl. Es gibt auch adaptive Schrittweitenvarianten.

    – scooter me fecit

    22. März 2016 um 21:41 Uhr

  • Ich stimme dafür, diese Frage als nicht zum Thema gehörend zu schließen, da SO für Fragen und Antworten und nicht für Diskussionen gedacht ist.

    – Duffymo

    22. März 2016 um 23:50 Uhr

  • “nicht monoton” ist vollkommen in Ordnung; “keine Funktion” macht keinen Sinn. Wenn es keine Funktion ist, was nähern wir uns hier an? Ich nehme an, Sie meinten eine nicht monotone, kontinuierliche Funktion, die nicht unbedingt eine Definition in geschlossener Form hat.

    – Will Ness

    2. April 2016 um 9:10 Uhr

So funktioniert die Annaherungssuche
Gespenst

Näherungssuche

Dies ist eine Analogie zur binären Suche, jedoch ohne deren Einschränkungen, dass gesuchte Funktion/Wert/Parameter streng monotone Funktionen sein müssen, während sie gemeinsam genutzt werden O(log(n)) Komplexität.

Nehmen wir zum Beispiel folgendes Problem an

Wir haben bekannte Funktion y=f(x) und finden wollen x0 so dass y0=f(x0). Dies kann grundsätzlich per Umkehrfunktion erfolgen f aber es gibt viele Funktionen, von denen wir nicht wissen, wie man sie invers berechnet. Wie berechnet man das in einem solchen Fall?

bekannt

  • y=f(x) – Eingabefunktion
  • y0 – Gesuchter Punkt y Wert
  • a0,a1 – Lösung x Intervallbereich

Unbekannte

  • x0 – Gesuchter Punkt x Der Wert muss im Bereich liegen x0=<a0,a1>

Algorithmus

  1. prüfe einige Punkte x(i)=<a0,a1> gleichmäßig verteilt entlang der Strecke mit einigen Schritten da

    Also zum Beispiel x(i)=a0+i*da wo i={ 0,1,2,3... }

  2. für jeden x(i) Berechnen Sie den Abstand / Fehler ee des y=f(x(i))

    Das lässt sich zum Beispiel so berechnen: ee=fabs(f(x(i))-y0) es können aber auch beliebige andere Metriken verwendet werden.

  3. Punkt erinnern aa=x(i) mit minimalem Abstand/Fehler ee

  4. hör auf wann x(i)>a1

  5. Genauigkeit rekursiv erhöhen

    Beschränken Sie also zuerst den Bereich, um beispielsweise nur um die gefundene Lösung herum zu suchen:

    a0'=aa-da;
    a1'=aa+da;
    

    Erhöhen Sie dann die Genauigkeit der Suche, indem Sie den Suchschritt verringern:

    da'=0.1*da;
    

    wenn da' nicht zu klein ist oder wenn die maximale Rekursionsanzahl nicht erreicht ist, dann gehe zu #1

  6. gefundene Lösung ist drin aa

Das habe ich im Sinn:

Bild1

Auf der linken Seite ist die anfängliche Suche dargestellt (Aufzählungszeichen #1, #2, #3, #4). Auf der rechten Seite die nächste rekursive Suche (bullet #5). Dies wird eine rekursive Schleife durchlaufen, bis die gewünschte Genauigkeit erreicht ist (Anzahl der Rekursionen). Jede Rekursion erhöht die Genauigkeit 10 mal (0.1*da). Die grauen vertikalen Linien stellen Sonden dar x(i) Punkte.

Hier der C++ Quellcode dazu:

//---------------------------------------------------------------------------
//--- approx ver: 1.01 ------------------------------------------------------
//---------------------------------------------------------------------------
#ifndef _approx_h
#define _approx_h
#include <math.h>
//---------------------------------------------------------------------------
class approx
    {
public:
    double a,aa,a0,a1,da,*e,e0;
    int i,n;
    bool done,stop;

    approx()            { a=0.0; aa=0.0; a0=0.0; a1=1.0; da=0.1; e=NULL; e0=NULL; i=0; n=5; done=true; }
    approx(approx& a)   { *this=a; }
    ~approx()           {}
    approx* operator = (const approx *a) { *this=*a; return this; }
    //approx* operator = (const approx &a) { ...copy... return this; }

    void init(double _a0,double _a1,double _da,int _n,double *_e)
        {
        if (_a0<=_a1) { a0=_a0; a1=_a1; }
        else          { a0=_a1; a1=_a0; }
        da=fabs(_da);
        n =_n ;
        e =_e ;
        e0=-1.0;
        i=0; a=a0; aa=a0;
        done=false; stop=false;
        }
    void step()
        {
        if ((e0<0.0)||(e0>*e)) { e0=*e; aa=a; }         // better solution
        if (stop)                                       // increase accuracy
            {
            i++; if (i>=n) { done=true; a=aa; return; } // final solution
            a0=aa-fabs(da);
            a1=aa+fabs(da);
            a=a0; da*=0.1;
            a0+=da; a1-=da;
            stop=false;
            }
        else{
            a+=da; if (a>a1) { a=a1; stop=true; }       // next point
            }
        }
    };
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------

So verwenden Sie es:

approx aa;
double ee,x,y,x0,y0=here_your_known_value;
//            a0,  a1, da,n, ee  
for (aa.init(0.0,10.0,0.1,6,&ee); !aa.done; aa.step())
    {
    x = aa.a;        // this is x(i)
    y = f(x)         // here compute the y value for whatever you want to fit
    ee = fabs(y-y0); // compute error of solution for the approximation search
    }

in der rem oben for (aa.init(... sind die genannten Operanden. Die a0,a1 ist das Intervall, in dem die x(i) wird sondiert, da ist der erste Schritt zwischen x(i) und n ist die Anzahl der Rekursionen. also wenn n=6 und da=0.1 der endgültige maximale Fehler von x passen wird ~0.1/10^6=0.0000001. Die &ee ist ein Zeiger auf eine Variable, in der der tatsächliche Fehler berechnet wird. Ich wähle Zeiger, damit es beim Verschachteln nicht zu Kollisionen kommt, und auch aus Geschwindigkeitsgründen, da das Übergeben von Parametern an stark genutzte Funktionen zu Heap-Trashing führt.

[notes]

Diese Annäherungssuche kann in jede Dimensionalität verschachtelt werden (aber grob muss man auf die Geschwindigkeit achten), siehe einige Beispiele

  • Annäherung von n Punkten an die Kurve mit der besten Anpassung
  • Kurvenanpassung mit y-Punkten an wiederholten x-Positionen (Galaxie-Spiralarme)
  • Erhöhung der Genauigkeit der Lösung der transzendenten Gleichung
  • Finden Sie eine Ellipse mit minimaler Fläche, die eine Reihe von Punkten in C++ umschließt
  • 2D TDoA Zeitdifferenz der Ankunft
  • 3D TDoA Zeitdifferenz der Ankunft

Im Falle einer Nichtfunktionsanpassung und der Notwendigkeit, “alle” Lösungen zu erhalten, können Sie die rekursive Unterteilung des Suchintervalls nach der gefundenen Lösung verwenden, um nach einer anderen Lösung zu suchen. Siehe Beispiel:

  • Wie berechne ich bei gegebener X-Koordinate die Y-Koordinate für einen Punkt, sodass er auf einer Bezier-Kurve ruht?

Was sollten Sie beachten?

Sie müssen das Suchintervall sorgfältig wählen <a0,a1> es enthält also die Lösung, ist aber nicht zu breit (sonst wäre es langsam). Auch erster Schritt da ist sehr wichtig, wenn es zu groß ist, können Sie lokale Min/Max-Lösungen verpassen, oder wenn es zu klein ist, wird das Ding zu langsam (insbesondere für verschachtelte mehrdimensionale Anpassungen).

1647128411 841 So funktioniert die Annaherungssuche
Will Ness

eine Kombination aus Sekante (mit Belichtungsreiheaber siehe Korrektur unten) und Halbierung Methode ist viel besser:

Geben Sie hier die Bildbeschreibung ein

Wir finden Wurzelnäherungen durch Sekanten und halten die Wurzel wie in der Halbierung eingeklammert.

Geben Sie hier die Bildbeschreibung ein

Halten Sie die beiden Kanten des Intervalls immer so, dass das Delta an einer Kante negativ und an der anderen positiv ist, sodass die Wurzel garantiert innen liegt. und anstatt zu halbieren, verwenden Sie die Sekantenmethode.

Pseudocode:

given a function f
given two points a, b, such that a < b and sign(f(a)) /= sign(f(b))
given tolerance tol
find root z of f such that abs(f(z)) < tol     -- stop_condition

DO:
    x = root of f by linear interpolation of f between a and b
    m = midpoint between a and b

    if stop_condition holds at x or m, set z and STOP

    [a,b] := [a,x,m,b].sort.choose_shortest_interval_with_
                                   _opposite_signs_at_its_ends

Dies halbiert offensichtlich das Intervall [a,b], oder sogar besser, bei jeder Iteration; es sei denn, die Funktion verhält sich extrem schlecht (wie zum Beispiel sin(1/x) in der Nähe von x=0), wird dies sehr schnell konvergieren, da nur zwei Auswertungen erforderlich sind f höchstens für jeden Iterationsschritt.

Und wir können die Fälle von schlechtem Benehmen erkennen, indem wir das überprüfen b-a nicht zu klein wird (insbesondere wenn wir mit endlicher Genauigkeit arbeiten, wie bei Dubletten).

aktualisieren: offenbar das ist eigentlich doppelt falsche Position -Methode, die Sekanten mit Klammern ist, wie durch den obigen Pseudocode beschrieben. Die Erweiterung um den Mittelpunkt wie bei der Halbierung gewährleistet die Konvergenz selbst in den pathologischsten Fällen.

  • Anerkennung für die Originalgrafiken ist natürlich dem Benutzer Spektre in seiner obigen Antwort zu verdanken.

    – Will Ness

    16. April 2017 um 18:51 Uhr

  • Könnte (wie?) Dies auf die gleiche Weise verschachtelt werden wie die Lösung von Spektre? Zum Beispiel verwende ich diese Lösung (oder jedenfalls etwas sehr Ähnliches), um ein dreidimensionales Lokalisierungsproblem zu lösen. Wie würde man so etwas verschachteln (hier ist ein Beispiel für eine 2-D-Verschachtelung von Spektres Lösung zur Lösung dieses Lokalisierungsproblems, die ich auf 3-D erweitert habe: pastebin.com/nQpX2hrX)

    – 10GeV

    22. Oktober 2020 um 13:28 Uhr

  • en.wikipedia.org/wiki/Secant_method#Generalizations

    – Will Ness

    22. Oktober 2020 um 16:44 Uhr

  • @KeithMadison für höhere Dimensionen ist die einfachste Methode die Halbierung. wie bei 1d klammern wir eine Wurzel mit zwei Punkten ein f(x +- delta)für 2d sind es 4 Punkte f(x +- delta, y +- delta)für 3d – 8 Punkte f(x +- delta, y +- delta, z +- delta)etc. dann berechnen wir f(x,y) und wähle die Unterteilung mit entgegengesetzten Fehlerzeichen so, dass die wahre Wurzel darin liegt. Dies kann verbessert werden, indem ein Analogon der Sekante hinzugefügt wird, z. B. Gradientenabstieg. und anscheinend ist dies tatsächlich eine doppelte falsche Positionsmethode, keine Sekante. Ich habe die Antwort aktualisiert.

    – Will Ness

    23. Oktober 2020 um 11:19 Uhr


  • Entschuldigung, könnten Sie das etwas erläutern? Ich bin mir nicht ganz sicher, ob ich dem folgen kann (ich denke, ich finde so etwas schwer vorstellbar). Oder zumindest verstehe ich die große Idee, bin mir aber bei den Details nicht sicher. Also bei OP’s ca. Klasse kann ich ein Lokalisierungsproblem der Ankunftszeit in 2d/3d lösen, indem ich ein Suchintervall wähle, den Fehler bei jedem Schritt berechne, indem ich die Ankunftszeit für den aktuellen “besten Punkt” berechne und diese wieder in den Algorithmus einfüge. Es ist mir nicht ganz klar, wie sich so etwas auf diese Methode übertragen lässt. Es ist wahrscheinlich einfach – ich kann einfach keine Verbindung herstellen.

    – 10GeV

    14. November 2020 um 4:35 Uhr

995420cookie-checkSo funktioniert die Annäherungssuche

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy