Bissection – Wikipedia

Le Bissection , aussi bissection continue ou Intervalle Appelé, est une procédure de mathématiques et d’informatique. La bissection crée enfin de nombreux membres d’une boîte d’intervalle, c’est-à-dire une séquence d’intervalles qui définit exactement un nombre réel. Un intervalle est créé à partir de la précédente par division en deux moitiés; Les composants latins représentent cela avec un (“Deux”) et Sectio (“Cut”) du mot “bissection”.

Fondamentalement, les procédures de bissection s’appliquent toujours lorsqu’un problème peut être résolu en divisé en deux sous-problèmes de sous-problèmes d’environ également grands, qui peuvent ensuite être traités individuellement.

Un exemple simple est la tâche suivante: Nous recherchons un nombre entre 1 et 1000, ce qu’un joueur doit deviner. Comme indice, il ne reçoit que “plus” ou “plus” plus “ou” coups “.

Supposons que le nombre soit 512. Si le joueur utilise la recherche binaire de la recherche binaire, les résultats du dialogue suivant:

1. 500 – plus grand
2. 750 – plus petit
3. 625 – plus petit
4. 562 – plus petit
5. 531 – plus petit
6. 515 – plus petit
7. 507 – plus grand
8. 511 – plus grand
9. 513 – plus petit
10. 512 – Hits

Si le joueur cherchait à la place linéaire et avait commencé à 1, la boîte de dialogue aurait suivi le cours suivant:

1. 1 – plus grand

2. 2 – plus grand

…

511. 511 – plus grand

512. 512 – Hits

Au lieu de dix questions, il aurait eu besoin de 512 questions; La bissection est donc beaucoup plus efficace ici.

Boîtier discret [ Modifier | Modifier le texte source ]]

Dans le cas discret, c’est-à-dire si le problème sous-jacent n’a qu’un nombre fini de solutions à tester, un tel problème peut toujours être compris comme une recherche: par une quantité finie

Devrait un élément

Avec la propriété

être trouvé.

Devrait une fonction ici

${displaystyle pcolon mto mathbb {r}}$

être, bien que

Postuler exactement si la propriété recherchée est respectée, c’est-à-dire

. Afin de résoudre ce problème en utilisant la bissection, ce qui suit doit également s’appliquer:

• 
  ${displayStyle p (y) <0}$

  chutes

  ${displaystyle y$

  

• 
  ${displayStyle p (y)> 0}$

  

  ${displaystyle y> x}$

  

  ${displaystyle p}$

  Donc ne donne pas seulement le coup (à

  ${displayStyle p (x) = 0}$

  ), mais aussi dans l’autre cas la direction dans laquelle vous devez continuer. Bien sûr, on suppose tacitement que

  ${displaystyle m}$

  est ordonné par une relation.

  ${displaystyle m}$

  est divisé en deux moitiés de la même taille que d’abord par

  ${displaystyle p}$

  Pour un élément aussi proche que possible du milieu de

  ${displaystyle m}$

  est évalué. L’affaire qui

  ${displaystyle m}$

  En raison d’un nombre impair d’éléments, ne laisse que deux parties qui ne sont qu’approximativement également grandes, ne peuvent être détournées, elle affecte guère des nombres d’éléments importants. Après chaque étape, la moitié du dernier montant examiné peut être rejetée, la quantité de moitié de moitié avec chaque évaluation de

  ${displaystyle p}$

  . La procédure se termine au plus tard lorsque la foule ne contient qu’un seul élément, ce doit être ce que vous recherchez, à condition qu’il soit inclus dans la quantité initiale. Donc, à beaucoup de taille

  ${displaystyle m}$

  réduire la réduction de moitié continue à 1

  ${displaystyle n}$

  Étapes nécessaires, avec:

  ${displayStyle m <2 ^ {n} journal de droite _ {2} m$

  

  La procédure a donc un terme de O

  ${displayStyle (log (m))}$

  .

  Cas continu [ Modifier | Modifier le texte source ]]

  

  Processus de bissection (animation)

  Dans le cas continu, un intervalle est généralement recherché comme une solution qui est un intervalle partiel d’un autre intervalle donné. Une application importante est la recherche d’un petit intervalle qui contient un point nul d’une fonction donnée:

  Nous recherchons le zéro d’une fonction constante strictement monotone

  ${displaystyle f}$

  à l’intervalle

  ${displayStyle [a, b]}$

  . Cela devrait être avec une précision

  ${displayStyle Varsilon}$

  être spécifié; Ce sera donc un intervalle partiel de

  ${displayStyle [a, b]}$

  recherché qui contient le zéro et tout au plus la longueur

  ${displayStyle Varsilon}$

  a. Puisqu’il y a un nombre infini de tels intervalles, ils ne peuvent pas simplement être essayés. Cependant, cela s’applique:

  • Une fonction strictement strictement monotone
    ${displaystyle f}$

    A dans un intervalle

    ${displayStyle [l, r]}$

    Exactement alors un zéro

    ${displayStyle f (l) <0}$

    et

    ${displayStyle f (r)> 0}$

    
    ${displayStyle l = a}$

    et

    ${displayStyle r = b}$

    .

  • Tester, ob
    ${displayStyle [l, r]}$

    contient un point zéro. Sinon: démolition.

  • Tester, ob
    ${displaystyle r-l$

    est. Si c’est le cas, l’intervalle de solution a été trouvé.

  • Partager autrement
    ${displayStyle [l, r]}$

    au milieu et poursuivre la procédure avec les deux intervalles partiels au 2e.

  Semblable au cas discret, l’algorithme se termine au plus tard lorsque l’intervalle la longueur

  ${displayStyle Varsilon}$

  tombe en dessous de. Donc:

  ${DisplayStyle {frac {b-a} {2 ^ {n}}}$

  

  Il en résulte un terme logarithmique en fonction du rapport de la longueur d’intervalle à la précision souhaitée.

  La monotonie de la fonction n’est pas absolument nécessaire. Une fonction constante a un intervalle

  ${displayStyle [l, r]}$

  Selon la valeur intermédiaire, au moins un endroit zéro si

  ${displayStyle f (l) f (r) <0}$

  .
  L’algorithme est très similaire à ce qui précède, puis ressemble à ceci:

  1. Paramètre
     ${displayStyle l = a}$

     et

     ${displayStyle r = b}$

     .

  2. Tester, ob
     ${displayStyle f (l) f (r) <0}$

     . Sinon: démolition.

  3. Paramètre
     ${displayStyle c = {frac {l + r} {2}}}$

     .

  4. Si
     ${displaystyle f (l) f (c) <0}$

     paramètre

     ${displayStyle r = c}$

     autrement réglé

     ${displaystyle l=c}$

     

  5. Tester, ob
     ${displaystyle r-l$

     est. Si c’est le cas, l’intervalle de solution a été trouvé.

  La bissection convient aux cas suivants:

  • Un changement de signe est dans l’intervalle donné et la fonction est stable
  • Les valeurs de début des procédures classiques (processus Newton, Regula Falsi) ne sont pas suffisamment proches au point zéro, de sorte qu’il n’y a pas de convergence locale là-bas
  • Plusieurs points zéro réduisent la vitesse de convergence des méthodes classiques

  Inconvénients de la bissection:

  • Dans les cas simples (fonction strictement monotone), il est plus lent qu’une procédure convergente carrée
  • Sans modifier le signe dans l’intervalle donné, des examens supplémentaires sont nécessaires pour distinguer un minimum local d’un point zéro

  Il existe un lien étroit entre la bissection et les arbres binaires. Au cours d’une bissection, une décision est prise à chaque étape pour savoir si le sous-ensemble gauche ou droit doit être poursuivi, et lorsqu’un arbre binaire coule de la racine, il faut décider à chaque nœud si le bord gauche ou droit doit être suivi. Il y a exactement un arbre binaire attribué qui décrit tous les cours potentiels de la bissection. L’arbre a autant de feuilles que le problème donné peut fournir des résultats possibles. Étant donné que le nombre de résultats possibles diminue encore avec chaque décision en un nœud, il a à peu près

  ${DisplayStyle Log _ {2} m}$

  

  Les niveaux. Cela correspond à la durée de la bissection, car le nombre de niveaux définit la longueur du chemin de haut en bas, ce qui à son tour est égal au terme. L’arbre résultant de cette affectation correspond à un arbre de recherche binaire équilibré.

  La bissection, par exemple, peut également être utilisée pour déterminer la représentation binaire d’un nombre. Un nombre entre

  ${DisplayStyle 0}$

  et

  ${displayStyle M-1}$

  Peut être identifié par une séquence de décisions “plus ou égales” et “petites”. Devient

  ${displaystyle m}$

  Chosé comme puissance de 2, l’élément “à droite du milieu” peut toujours être tapé car la quantité est juste de taille. Pour

  ${displayStyle m = 8}$

  Par exemple, le montant résulte

  ${displayStyle Left {0, ldots, 7Right}}$

  – la recherche du 2 maintenant s’est épuisé comme suit:

  • 4 – plus petit
  • 2 – plus grand ou le même (un “coup” est distribué)
  • 3 – plus petit

  Donc c’est 2 décrit précisément. Si nous définissons maintenant le 0 pour “plus petit” et pour “plus grand ou égal” 1, cela se traduit par 010. Il s’agit précisément de la représentation binaire du 2 .