Comment pouvons-nous approximer efficacement les valeurs du domaine réel à l'aide de la recherche d'approximation ?

Comment fonctionne la recherche d'approximation

Prologue

Cet article vise à fournir une compréhension complète de le fonctionnement interne d'une classe de recherche d'approximation, conçue pour approximer des valeurs et des paramètres dans le domaine réel pour des tâches telles que l'ajustement polynomial et l'équation résolution.

Question

Comment pouvons-nous approximer des valeurs ou des paramètres dans le domaine réel (en utilisant des nombres à virgule flottante double précision) pour des tâches telles que l'ajustement de polynômes, la recherche de paramètres dans des fonctions paramétriques, ou en résolvant des équations (difficiles) (telles que transcendantaux) ?

Restrictions

• Domaine réel (double précision)
• Langage C
• Précision d'approximation configurable
• Intervalle connu pour la recherche
• Valeur ajustée ou Le paramètre n'est pas strictement monotone ou peut ne pas être une fonction du tout

Recherche d'approximation

La recherche d'approximation est analogue à la recherche binaire mais supprime la restriction selon laquelle le paramètre recherché la fonction, la valeur ou le paramètre doit être une fonction strictement monotone. Malgré cet assouplissement, il conserve la même complexité O(log(n)).

Algorithme

Considérons le problème suivant :

Étant donné un fonction y = f(x) et un point souhaité y0, nous visons à trouver x0 tel que y0 = f(x0).

Informations connues

• y = f(x) - fonction d'entrée
• y0 - valeur y du point souhaité
• a0, a1 - solution x intervalle plage

Inconnu :

• x0 - point cible x valeur dans la plage

Algorithme Étapes :

1. Points de sonde x(i) = uniformément espacés le long de la plage avec quelques pas da.

   • Par exemple : x(i) = a0 i * da, où i = 0, 1, 2, ...

2. Pour chaque x(i), calculer la distance/erreur ee entre y = f(x(i)) et y0.

   • Cette erreur peut être calculée à l'aide de métriques telles que ee = fabs(f(x(i)) - y0).
3. Rappelez-vous le point aa = x(i) avec la distance/erreur minimale ee.
4. Arrêtez quand x(i) > a1.

5. Augmenter de manière récursive la précision.

   • Limiter la plage de recherche au voisinage de la solution trouvée :

     • a0' = aa - da
     • a1' = aa da

   • Améliorez la précision de la recherche en diminuant le pas de recherche :

     • da' = 0,1 * da
   • Si da' n'est pas trop petit ou si le nombre maximum de récursions n'a pas été atteint, revenez à l'étape 1.
6. La solution trouvée est stockée dans aa.

Implémentation en C

Le code C fourni démontre l'implémentation de l'algorithme de recherche d'approximation :

#include "approx.h"
int main() {
    // Initialize the approx object with parameters
    approx aa;
    aa.init(0.0, 10.0, 0.1, 6, &ee);

    // Loop until a solution is found
    for (; !aa.done; aa.step()) {
        // Retrieve current x
        x = aa.a;

        // Compute y
        y = f(x);

        // Compute error
        ee = fabs(y - y0);
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!