Método de bisección

Para determinar cuándo debe detenerse la iteración, es necesario considerar varias posibles condiciones de parada con respecto a una tolerancia (${\displaystyle \epsilon }$). Burden y Faires (2016) identifican las tres condiciones de parada: ^{[ 7 ]}

• Tolerancia absoluta:${\displaystyle |p_{N}-p_{N-1}|<\epsilon }$
• Tolerancia relativa:${\displaystyle \left|{\frac {p_{N}-p_{N-1}}{p_{N}}}\right|<\epsilon ,}$||${\displaystyle p_{N}\neq 0}$
• ${\displaystyle |f(p_{N})|<\epsilon .}$

${\displaystyle |f(p_{N})|<\epsilon }$no da un resultado preciso dentro${\displaystyle \epsilon }$a menos que${\displaystyle |f'(p_{N})|\geq 1}$Las otras dos posibilidades representan conceptos diferentes: la diferencia absoluta${\displaystyle |c-a|\leq 5\times 10^{-t}}$dice que c y a son lo mismo que${\displaystyle t}$decimales, mientras que la diferencia relativa${\displaystyle \left|{\frac {c-a}{c}}\right|\leq 5\times 10^{-t}}$dice que c y a son lo mismo que${\displaystyle t}$cifras significativas . ^{[ 8 ]} Si no se sabe nada sobre el valor de la raíz, entonces la tolerancia relativa es la mejor condición de parada. ^{[ 9 ]}

La entrada para el método es una función continua.${\displaystyle f}$y un intervalo${\displaystyle [a,b]}$, de tal manera que los valores de la función${\displaystyle f(a)}$y${\displaystyle f(b)}$ son de signo opuesto (hay al menos un cruce por cero dentro del intervalo). Cada iteración realiza estos pasos:

1. Calcular${\displaystyle c}$, el punto medio del intervalo,${\displaystyle c={\frac {a+b}{2}}}$;
2. Calcula el valor de la función en el punto medio,${\displaystyle f(c)}$;
3. Si${\displaystyle f(c)=0}$, devolver c;
4. Si la convergencia es satisfactoria (es decir,${\displaystyle \left|c-a\right|\leq 5\times 10^{-t}|c|}$), devolver${\displaystyle c}$;
5. Examine el signo de${\displaystyle f(c)}$y reemplazar cualquiera de ellos${\displaystyle a}$o${\displaystyle b}$con${\displaystyle c}$de modo que haya un cruce por cero dentro del nuevo intervalo.

Supongamos que se utiliza el método de bisección para encontrar una raíz del polinomio.

${\displaystyle f(x)=x^{3}-x-2\,.}$

Primero, dos números${\displaystyle a}$y${\displaystyle b}$deben encontrarse de tal manera que${\displaystyle f(a)}$y${\displaystyle f(b)}$tienen signos opuestos. Para la función anterior,${\displaystyle a=1}$y${\displaystyle b=2}$satisfacer este criterio, como

${\displaystyle f(1)=(1)^{3}-(1)-2=-2}$

y

${\displaystyle f(2)=(2)^{3}-(2)-2=+4\,.}$

Dado que la función es continua, debe existir una raíz dentro del intervalo [1, 2]. Al iterar el método de bisección en este intervalo, se obtienen aproximaciones cada vez más precisas:

Tras 13 iteraciones, se hace evidente que existe una convergencia hacia aproximadamente 1,521: una raíz del polinomio.

Algunos de estos métodos se basan en el cálculo del grado topológico . ^{[ 12 ]}

El método de bisección característica utiliza únicamente los signos de una función en diferentes puntos. Sea f una función de R ^d a R ^d , para algún entero d ≥ 2. Un poliedro característico ^{[ 13 ]} (también llamado polígono admisible ) ^{[ 14 ]} de f es un poliedro en R ^d , con 2 ^d vértices, tal que en cada vértice v , la combinación de signos de f ( v ) es única. Por ejemplo, para d =2, un poliedro característico de f es un cuadrilátero con vértices (digamos) A,B,C,D, tal que:

• Signo f (A) = ( − , − ), es decir, f ₁ (A)<0, f ₂ (A)<0.
• Signo f (B) = ( − ,+), es decir, f ₁ (B)<0, f ₂ (B)>0.
• Signo f (C) = (+, − ), es decir, f ₁ (C)>0, f ₂ (C)<0.
• Signo f (D) = (+,+), es decir, f ₁ (D)>0, f ₂ (D)>0.

Una arista propia de un polígono característico es una arista entre dos vértices, cuyo vector de signos difiere en un solo signo. En el ejemplo anterior, las aristas propias del cuadrilátero característico son AB, AC, BD y CD. Una diagonal es un par de vértices, cuyo vector de signos difiere en todos los d signos. En el ejemplo anterior, las diagonales son AD y BC.

En cada iteración, el algoritmo elige una arista adecuada del poliedro (por ejemplo, A - B) y calcula los signos de f en su punto medio (por ejemplo, M). Luego procede de la siguiente manera:

• Si Sign f (M) = Sign(A), entonces A se reemplaza por M, y obtenemos un poliedro característico más pequeño.
• Si Sign f (M) = Sign(B), entonces B se reemplaza por M, y obtenemos un poliedro característico más pequeño.
• De lo contrario, elegimos un nuevo borde adecuado e intentamos de nuevo.

Supongamos que el diámetro (= longitud de la arista propia más larga) del poliedro característico original es D. Entonces, al menos${\displaystyle \log _{2}(D/\varepsilon )}$Se requieren bisecciones de los bordes para que el diámetro del polígono restante sea como máximo${\displaystyle \varepsilon }$. ^{[ 14 ] : 11, Lema.4.7}