c++ - sirven - tipos de motores de busqueda

Cómo funciona la búsqueda de aproximación

Question

[Prólogo]

Este Q&A está destinado a explicar más claramente el funcionamiento interno de mi clase de búsqueda de aproximaciones que primero publiqué aquí

• Precisión creciente de la solución de la ecuación trascendental

Ya me pidieron información más detallada sobre esto varias veces (por varias razones), así que decidí escribir un tema de estilo de preguntas y respuestas sobre este que pueda consultar fácilmente en el futuro y no necesite explicarlo una y otra vez.

[Pregunta]

¿Cómo aproximar valores / parámetros en el dominio real ( double ) para lograr el ajuste de polinomios, funciones paramétricas o resolver ecuaciones (difíciles) (como trascendental)?

Restricciones

• dominio real ( double precisión)
• Lenguaje C ++
• precisión de aproximación configurable
• intervalo conocido para búsqueda
• El valor / parámetro ajustado no es estrictamente monótono o no funciona en absoluto

Answer 1

Una combinación de secant y método de bisection es mucho mejor:

encontramos aproximaciones de raíz por secantes, y mantenemos la raíz entre paréntesis como en bisección.

mantenga siempre los dos bordes del intervalo para que el delta en un borde sea negativo y en el otro sea positivo, de modo que se garantice que la raíz esté adentro; y en lugar de reducir a la mitad, use el método secante.

Pseudocódigo:

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

Obviamente, esto reduce a la mitad el intervalo [a,b] , o lo hace aún mejor, en cada iteración; entonces, a menos que la función tenga un comportamiento extremadamente malo (como, por ejemplo, sin(1/x) cerca de x=0 ), esto convergerá muy rápidamente, tomando solo dos evaluaciones de f como máximo, para cada paso de iteración.

Y podemos detectar los casos de mal comportamiento comprobando que ba no se vuelve demasiado pequeño (especialmente si estamos trabajando con precisión finita, como en los dobles).

Answer 2

Búsqueda de aproximación

Esto es una analogía con la búsqueda binaria, pero sin sus restricciones, la función / valor / parámetro buscado debe ser una función estrictamente monotónica al compartir la complejidad O(n.log(n)) .

Por ejemplo, supongamos el siguiente problema

Hemos conocido la función y=f(x) y queremos encontrar x0 tal que y0=f(x0) . Básicamente, esto se puede hacer mediante la función inversa a f pero hay muchas funciones que no sabemos cómo calcular de manera inversa. Entonces, ¿cómo calcular esto en tal caso?

sabe

• y=f(x) - función de entrada
• y0 - valor deseado del punto y
• a0,a1 - solución x intervalo de intervalo

Incógnitas

• x0 : el valor del punto x deseado debe estar en el rango x0=<a0,a1>

Algoritmo

1. sondear algunos puntos x(i)=<a0,a1> dispersos uniformemente a lo largo del rango con algún paso da

   Entonces, por ejemplo x(i)=a0+i*da donde i={ 0,1,2,3... }

2. para cada x(i) calcule la distancia / error ee de y=f(x(i))

   Esto se puede calcular, por ejemplo, de esta manera: ee=fabs(f(x(i))-y0) pero también se puede usar cualquier otra métrica.

3. recuerde el punto aa=x(i) con una distancia mínima / error ee

4. parar cuando x(i)>a1

5. aumentar recursivamente la precisión

   así que primero restrinja el rango para buscar solo alrededor de la solución encontrada, por ejemplo:

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

   luego aumente la precisión de la búsqueda al reducir el paso de búsqueda:

   da''=0.1*da;

   si da'' no es demasiado pequeño o si no se alcanza el recuento máximo de recursiones, vaya al # 1

6. la solución encontrada está en aa

Esto es lo que tengo en mente:

En el lado izquierdo se ilustra la búsqueda inicial (viñetas # 1, # 2, # 3, # 4 ). En el lado derecho, la siguiente búsqueda recursiva (viñeta n. ° 5 ). Esto se repetirá recursivamente hasta que se alcance la precisión deseada (número de recursiones). Cada recursividad aumenta la precisión 10 veces ( 0.1*da ). Las líneas verticales grises representan puntos sondeados x(i) .

Aquí el código fuente de C ++ para esto:

//---------------------------------------------------------------------------
//--- 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
//---------------------------------------------------------------------------

Así es como se usa:

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
    }

en el rem de arriba for (aa.init(... son los operandos nombrados. a0,a1 es el intervalo en el que se for (aa.init(... x(i) , da es el paso inicial entre x(i) n es el número de recursiones. así que si n=6 y da=0.1 el error máximo final de ajuste x será ~0.1/10^6=0.0000001 . El &ee es un puntero a la variable donde se calculará el error real. Elijo el puntero para que no haya colisiones al anidar esto.

[notas]

Esta búsqueda de aproximación se puede anidar a cualquier dimensionalidad (pero en términos generales, debe tener cuidado con la velocidad). Vea algunos ejemplos

• Aproximación de n puntos a la curva con el mejor ajuste
• Ajuste de curva con puntos y en posiciones repetidas x (brazos Galaxy Spiral)
• Precisión creciente de la solución de la ecuación trascendental
• Encuentre elipse de área mínima que encierra un conjunto de puntos en c ++

En caso de que no se ajuste la función y la necesidad de obtener "todas" las soluciones, puede usar la subdivisión recursiva del intervalo de búsqueda después de encontrar la solución para buscar otra solución. Ver ejemplo:

• Dada una coordenada X, ¿cómo calculo la coordenada Y para un punto para que descanse en una curva de Bezier?

¿De qué debes estar enterado?

debe elegir cuidadosamente el intervalo de búsqueda <a0,a1> para que contenga la solución pero no sea demasiado amplia (o sería lenta). También el paso inicial da es muy importante si es demasiado grande, puede perderse las soluciones mínimas / máximas locales o si es demasiado pequeño, la cosa se volverá demasiado lenta (especialmente para ajustes multidimensionales anidados).