$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Méthode de dichotomie

  La méthode de dichotomie est une méthode pour trouver une solution approchée à une équation $f(x)=0$. Précisément, supposons que la fonction $f$ est continue sur l'intervalle $[a,b]$, avec $f(a)\leq 0$ et $f(b)\geq 0$. On sait donc qu'il existe au moins un réel $c$ dans l'intervalle $[a,b]$ tel que $f( c)=0$.

  L'idée est alors d'évaluer ce que vaut $f$ au milieu de $[a,b]$, et de distinguer les deux cas suivants :
  • si $f\left(\frac{a+b}2\right)\leq 0$, alors on sait qu'on a une racine dans l'intervalle $\left[\frac{a+b}2,b\right]$.
  • sinon, $f\left(\frac{a+b}2\right)> 0$ et on sait qu'on a une racine dans l'intervalle $\left[a,\frac{a+b}2\right]$.
Ainsi, dans les deux cas, on a trouvé un intervalle de longueur moitié dans lequel est située une racine de l'équation $f(x)=0$. On recommence alors avec cet intervalle, et ainsi de suite jusqu'à ce qu'on trouve une approximation qui nous convienne.

  Formellement, on définit les suites $(a_n)$ et $(b_n)$ en posant
  • $a_0=a$ et $b_0=b$.
  • si $f\left(\frac{a_n+b_n}2\right)\leq 0$, alors $a_{n+1}=\frac{a_n+b_n}2$ et $b_{n+1}=b_n$.
  • sinon, $a_{n+1}=a_n$ et $b_{n+1}=\frac{a_n+b_n}2$.
On a toujours une solution à l'équation $f(x)=0$ dans l'intervalle $[a_n,b_n]$, qui est de longueur $(b_n-a_n)/2^n$.

  Il existe des méthodes plus efficaces que la dichotomie pour rechercher pratiquement les solutions d'une équation f(x)=0. La plus connue est sans doute la méthode de Newton.

Autrefois, chaque fois que les chirugiens opéraient un patient, ils versaient une certaine somme au médecin généraliste qui le lui avait envoyé. Cette pratique faisait que les généralistes envoyaient leurs patients non pas vers le meilleur chirurgien, mais vers celui qui leur reversait le plus. Elle portait le nom de dichotomie.

Consulter aussi...