Comment utiliser la méthode de dichotomie pour le calcul numérique

Utilisation de la méthode de dichotomie en calcul numérique

Comprendre la méthode de recherche de racine par la méthode de la bissection et son fonctionnement

NOUS POUVONS NOUS CONNECTER SUR 😐 LINKEDIN | TWITTER | VoAGI | SUBSTACK |

Un sous-domaine de l’informatique et des mathématiques, connu sous le nom de calcul numérique, se concentre sur l’utilisation de méthodes et d’algorithmes numériques implémentés par ordinateur pour résoudre des problèmes mathématiques. Il s’agit d’exécuter des simulations et des calculs pour obtenir des approximations de réponses à des énigmes mathématiques qui pourraient être difficiles ou impossibles à résoudre analytiquement.

Nous avons de nombreuses équations en mathématiques. Pour utiliser ces équations dans la vie réelle, nous devons résoudre ces équations. Nous disons “L’ÉQUATION EST RÉSOLUE” lorsque nous trouvons ses racines.f(x) = 0 où f(x) est une fonction continue, et nous voulons trouver la ou les valeurs de ‘x’ qui rendent la fonction égale à zéro. Lorsque nous mettons les racines dans l’équation, l’équation devient zéro. Voyons un exemple simple :

f(x) = x * x — 1

• Découvrez AnyLoc La dernière méthode universelle pour la reconnaissance visuelle des lieux (VPR)
• Couche de métriques Une seule source de vérité pour toutes les définitions de KPI
• RecList 2.0 Test Systématique Open-Source des Modèles d’Apprentissage Automatique

x * x — 1 = 0

f(1) = (1) * (1) –1 = 0

f(-1) = (-1) * (-1) –1=0

Ainsi, 1 et –1 sont les racines des équations ci-dessus.

Comment avons-nous compris cela ?

Nous avons remplacé 1 à la place de x dans l’équation. C’est ainsi que nous pouvons résoudre ces équations. Mais malheureusement, dans la vie réelle, les équations ne sont pas aussi simples à résoudre.

Pour résoudre des équations de la vie réelle, nous avons de nombreuses méthodes connues sous le nom de “MÉTHODES DE RECHERCHE DE RACINES”. Ces méthodes sont très utiles pour le calcul numérique, l’optimisation, l’interpolation, le lissage de courbes, l’analyse numérique et bien d’autres domaines encore.

Si nous commencions à parler d’évolution, cela prendrait tout un blog, mais commençons directement par la mise en œuvre des techniques.

Méthode de la bissection

La méthode de la bissection en mathématiques est une approche simple pour localiser les racines numériques d’une équation à une seule inconnue. La méthode de la bissection est la méthode numérique la plus simple pour résoudre le problème transcendantal. Nous aborderons en détail l’approche de la bissection avec des problèmes résolus dans cet article.

Pour déterminer les racines d’un problème polynomial, utilisez la méthode de la bissection. Elle divise et sépare l’intervalle dans lequel se trouve la racine de l’équation. Le théorème des valeurs intermédiaires pour les fonctions continues sert de principe directeur à cette méthode. Elle fonctionne en réduisant la distance entre les intervalles positifs et négatifs jusqu’à ce qu’elle se rapproche de la bonne réponse. En moyennant les intervalles positifs et négatifs, cette technique réduit la distance entre les variables.

Bien qu’il s’agisse d’un processus simple, il est lent. La méthode de la bissection est parfois appelée méthode de la dichotomie, méthode de recherche binaire, méthode de demi-intervalle et méthode de recherche de racines.

Algorithme de la méthode de la bissection

Pour toute fonction continue f(x), [Source]

Trouver deux points, disons a et b tels que a < b et f(a)* f(b) < 0

Trouver le milieu de a et b, disons “c”

t est la racine de la fonction donnée si f(c) = 0 ; sinon, suivre l’étape suivante

Diviser l’intervalle [a, b] — Si f(c)*f(a) <0, il existe une racine entre c et a– sinon, si f(c) *f (b) < 0, il existe une racine entre c et b

Répéter les trois étapes ci-dessus jusqu’à ce que f(c) = 0.

La méthode de la dichotomie est une méthode d’approximation pour trouver les racines de l’équation donnée en divisant l’intervalle de manière répétée. Cette méthode va diviser l’intervalle jusqu’à ce que l’intervalle résultant soit extrêmement petit.

CODE :

Avertissement : Ce code sert uniquement à montrer comment créer un code de dichotomie de base en Python. Je ne revendique aucune optimisation dans le code et des améliorations supplémentaires sont nécessaires en fonction de l’énoncé du problème spécifique.

Prenons une fonction simple.

F(x) = x * x — 3

def fun(x):    return x * x - 3

Écrivons un code très basique pour créer un pipeline simple pour le code de la méthode de dichotomie.

a = 1    #Approximation de la première racineb = 2    #Approximation de la deuxième racine #Déclaration de la fonctiondef fun(x):    return x*x - 3a_original = fun(a)b_original = fun(b)i = 0while i < 50 :        #Faire cela 50 fois     c = (a + b)/2    c_original = fun(c)    if c_original < 0:        a = c    else:        b = c#     plt.plot(a)    print("L'a est {}".format(a))    print("Le b est {}".format(b))    i+=1

Le code ci-dessus est très basique mais un code de base qui représente la méthode de dichotomie à un niveau de force brute.

Voyons sa sortie

L'a est 1.5Le b est 2L'a est 1.5Le b est 1.75L'a est 1.625Le b est 1.75L'a est 1.6875Le b est 1.75L'a est 1.71875Le b est 1.75L'a est 1.71875Le b est 1.734375L'a est 1.7265625Le b est 1.734375L'a est 1.73046875Le b est 1.734375L'a est 1.73046875Le b est 1.732421875L'a est 1.7314453125Le b est 1.732421875L'a est 1.73193359375Le b est 1.732421875L'a est 1.73193359375Le b est 1.732177734375L'a est 1.73193359375Le b est 1.7320556640625L'a est 1.73199462890625Le b est 1.7320556640625L'a est 1.732025146484375Le b est 1.7320556640625L'a est 1.7320404052734375Le b est 1.7320556640625L'a est 1.7320480346679688Le b est 1.7320556640625L'a est 1.7320480346679688Le b est 1.7320518493652344L'a est 1.7320499420166016Le b est 1.7320518493652344L'a est 1.7320499420166016Le b est 1.732050895690918L'a est 1.7320504188537598Le b est 1.732050895690918L'a est 1.7320506572723389Le b est 1.732050895690918L'a est 1.7320507764816284Le b est 1.732050895690918L'a est 1.7320507764816284Le b est 1.7320508360862732L'a est 1.7320508062839508Le b est 1.7320508360862732L'a est 1.7320508062839508Le b est 1.732050821185112L'a est 1.7320508062839508Le b est 1.7320508137345314L'a est 1.7320508062839508Le b est 1.732050810009241L'a est 1.7320508062839508Le b est 1.732050808146596L'a est 1.7320508072152734Le b est 1.732050808146596L'a est 1.7320508072152734Le b est 1.7320508076809347L'a est 1.732050807448104Le b est 1.7320508076809347L'a est 1.7320508075645193Le b est 1.7320508076809347L'a est 1.7320508075645193Le b est 1.732050807622727L'a est 1.7320508075645193Le b est 1.7320508075936232L'a est 1.7320508075645193Le b est 1.7320508075790713L'a est 1.7320508075645193Le b est 1.7320508075717953L'a est 1.7320508075681573Le b est 1.7320508075717953L'a est 1.7320508075681573Le b est 1.7320508075699763L'a est 1.7320508075681573Le b est 1.7320508075690668L'a est 1.732050807568612Le b est 1.7320508075690668L'a est 1.7320508075688394Le b est 1.7320508075690668L'a est 1.7320508075688394Le b est 1.7320508075689531L'a est 1.7320508075688394Le b est 1.7320508075688963L'a est 1.7320508075688679Le b est 1.7320508075688963L'a est 1.7320508075688679Le b est 1.732050807568882L'a est 1.732050807568875Le b est 1.732050807568882L'a est 1.732050807568875Le b est 1.7320508075688785L'a est 1.7320508075688767Le b est 1.7320508075688785L'a est 1.7320508075688767Le b est 1.7320508075688776

La sortie ci-dessus est le résultat de jouer avec a et b pendant 50 itérations. Le système aura des problèmes pour traiter des nombres supérieurs à 16 chiffres en raison de limitations. Mais nous pouvons voir que les valeurs des racines se rapprochent de plus en plus.

Le dernier a est 1.73205080

Le dernier b est 1.73205080

En substituant ces dernières valeurs dans l’équation, vous obtiendrez :

F(a) = -0.000176000…

F(b) = 0.000176000…

Très proche de 0 !!!

Maintenant, nous savons que cette logique fonctionne. Optimisons le code et visualisons la sortie afin de mieux la comprendre.

import matplotlib.pyplot as pltdef Bisection_method(a, b, iterations):    def fun(x):        return x * x - 3    # Créez une figure et un axe pour le graphique    plt.figure()    plt.xlabel('x')    plt.ylabel('y')    plt.title('Visualisation de l'équation y = x^2 - 3')    # Tracez l'équation y = x^2 - 3 pour la plage [a, b]    x_values = [x / 100.0 for x in range(int(a * 100), int(b * 100) + 1)]    y_values = [fun(x) for x in x_values]    plt.plot(x_values, y_values, color='orange', label='y = x^2 - 3')    # Tracez les points initiaux a et b sur le graphique    plt.plot(a, fun(a), 'ro', label='f(a)')    plt.plot(b, fun(b), 'go', label='f(b)')    # Tracez la ligne de l'axe des x    plt.axhline(linewidth=2, y=0, color='brown', linestyle='dashdot')    plt.axhline(y=fun(a), color='blue', linestyle='dashdot')    plt.axhline(y=fun(b), color='blue', linestyle='dashdot')    plt.legend()    plt.grid()    # Mettez à jour le graphique et affichez-le    plt.pause(1)    a_vals = [a]    b_vals = [b]    i = 0    while i < iterations:        c = (a + b) / 2        c_original = fun(c)        if c_original < 0:            a = c        else:            b = c        i += 1        a_vals.append(a)        b_vals.append(b)    # Tracez toutes les valeurs de a et b dans différentes couleurs    plt.plot([fun(a_val) for a_val in a_vals], 'mo', label='f(a)',color='orange')    plt.axhline(y=0, color='brown', linestyle='dashdot')    plt.plot([fun(b_val) for b_val in b_vals], 'co', label='f(b)')    plt.axhline(y=0, color='brown', linestyle='dashdot')    plt.legend()    plt.grid()    # Mettez à jour le graphique et affichez-le#     plt.pause(1)    plt.show()

#Appelez la fonction avec les valeurs initiales de a, b et le nombre d'itérationsa_initial = 1b_initial = 2iterations = 50Bisection_method(a_initial, b_initial, iterations)

J’ai modifié ce code de manière à ce qu’il prenne des entrées et qu’il affiche le graphe des racines.

Dans la figure ci-dessus, nous pouvons voir nos points de départ et leurs valeurs F(x). La ligne en rouge est ce que nous voulons atteindre avec ces racines initiales.

Dans la figure ci-dessus, j’ai tracé les sorties des 10 derniers points sur 50. Vous pouvez voir que les valeurs convergent vers 0 et les derniers points sont presque égales à 0. C’est un signe que nous avons obtenu nos racines. Les itérations sont la limite que vous pouvez définir pour contrôler l’ensemble de l’exécution. Le paramètre pourrait être la valeur seuil de la fonction. Ainsi, vous devez soit arrêter après avoir effectué un certain nombre d’itérations, soit si vous atteignez une certaine valeur seuil.

Vous pouvez modifier la fonction et utiliser ce code pour trouver les racines de votre propre équation, ou vous pouvez utiliser directement le lien ci-dessous, qui vous conduira vers la calculatrice en ligne de la méthode de la dichotomie.

Calculatrice en ligne de la méthode de la dichotomie

La calculatrice en ligne de la méthode de la dichotomie est un outil simple et fiable pour trouver la vraie racine des équations non linéaires en utilisant…

www.codesansar.com

Avantages de la méthode de la dichotomie :

Convergence : la fiabilité garantit que l’approche trouvera une solution tant qu’un intervalle contenant une racine est donné.

Simplicité : la méthode est simple en théorie et facile à utiliser.

Résistance : comparée à certaines autres techniques de recherche de racines, la méthode de la dichotomie est moins sensible à la supposition initiale.

Amélioration de l’intervalle : chaque amélioration garantit qu’à chaque itération, la solution est plus précise.

Aucune condition de dérivée : cela la rend appropriée pour les fonctions pour lesquelles les dérivées sont soit indisponibles, soit difficiles à calculer.

Convergence globale : cette approche finira par localiser une racine si elle est présente à l’intérieur de l’intervalle.

Limitations de la méthode de la dichotomie :

Convergence lente : la méthode peut être lente par rapport à d’autres algorithmes de recherche de racines avec des taux de convergence plus rapides, surtout pour les fonctions avec des pentes raides, bien qu’elle garantisse la convergence.

Exigence d’intervalle : la procédure peut ne pas être appropriée si un tel intervalle est inconnu ou difficile à déterminer.

Seule une racine peut être trouvée : la méthode de la dichotomie est conçue pour ne trouver qu’une seule racine dans l’intervalle fourni [a, b]. La procédure aboutira à l’une des racines de la fonction s’il y en a plus d’une dans cet intervalle.

Applicabilité limitée aux équations complexes : la méthode de la dichotomie est la plus adaptée aux équations avec une seule racine réelle dans l’intervalle spécifié.

Pour surmonter ces limitations, nous avons de nombreuses autres méthodes qui sont de niveau avancé pour la recherche de racines avec des mécanismes différents. Nous les aborderons dans la prochaine série d’articles.

Si vous avez trouvé cet article instructif

Il est prouvé que “la générosité vous rend plus heureux”; donc, donnez des applaudissements à l’article si vous l’avez aimé. Si vous avez trouvé cet article instructif, suivez-moi sur Linkedin et VoAGI. Vous pouvez également vous abonner pour être informé lorsque je publie des articles. Créons une communauté ! Merci pour votre soutien !

Vous pouvez cliquer ici pour m’offrir un café.

Comprendre LangChain 🦜️🔗: PARTIE 1

Compréhension théorique des chaînes, des invites et des autres modules importants dans LangChain

pub.towardsai.net

Guide pratique pour choisir des architectures de CNN pour les applications de vision par ordinateur

De LeNet à EfficientNet : choisir la meilleure architecture de CNN pour votre projet

levelup.gitconnected.com

Guide complet : les meilleures ressources en vision par ordinateur dans un seul blog

Enregistrez ce blog pour des ressources complètes en vision par ordinateur

VoAGI.com

Boostez vos projets de science des données, d’apprentissage automatique et de vision par ordinateur : outils essentiels pour une gestion de projet efficace

Accélérez vos constructions et projets avec ces outils

pub.towardsai.net

Déconnexion,

Chinmay

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!