Mètode de la bisecció: diferència entre les revisions
Línia 8: | Línia 8: | ||
Algorisme: |
Algorisme: |
||
*Es comprova que <math>f(a)\cdot f(b) <0</math> |
*Es comprova que <math>f(a)\cdot f(b) <0</math> |
||
*Es calcula el [[punt mitjà]] ''m'' de l'interval ''[a,b]'' i s' |
*Es calcula el [[punt mitjà]] ''m'' de l'interval ''[a,b]'' i s'avalua ''f(m)''. |
||
*Si ''f(m)=0'', ''m'' és una arrel. Si no, es comprova que ''f(m)'' té signe contrari que ''f(a)'' ó ''f(b)''. |
*Si ''f(m)=0'', ''m'' és una arrel. Si no, es comprova que ''f(m)'' té signe contrari que ''f(a)'' ó ''f(b)''. |
||
*Es redefineix l'interval ''[a,b]'' com ''[a,m]'' ó ''[m,b]'' segons s'haja determinat en quin d'aquests intervals es produeix un canvi de signe. |
*Es redefineix l'interval ''[a,b]'' com ''[a,m]'' ó ''[m,b]'' segons s'haja determinat en quin d'aquests intervals es produeix un canvi de signe. |
||
*Es repeteix el procés amb l'interval fins arribar a la |
*Es repeteix el procés amb l'interval fins arribar a la precisió desitjada. |
||
Revisió del 11:09, 8 jul 2019
En matemàtiques, el mètode de la bisecció és un algorisme de cerca d'arrels d'una funció contínua en un interval. L'algorisme consisteix en dividir repetidament l'interval en dos subintervals i seleccionar el que conté l'arrel, fins trobar l'arrel o una aproximació de la mateixa.
Introducció
El mètode es basa en el teorema del valor intermedi (TVI), segons el qual, tota funció contínua f en un interval tancat [a,b] s'anul·la en algun punt del interval si els signes de f(a) i f(b) són contraris.
Algorisme:
- Es comprova que
- Es calcula el punt mitjà m de l'interval [a,b] i s'avalua f(m).
- Si f(m)=0, m és una arrel. Si no, es comprova que f(m) té signe contrari que f(a) ó f(b).
- Es redefineix l'interval [a,b] com [a,m] ó [m,b] segons s'haja determinat en quin d'aquests intervals es produeix un canvi de signe.
- Es repeteix el procés amb l'interval fins arribar a la precisió desitjada.
El método de bisección es menos eficiente que el método de Newton, pero es mucho más seguro para garantizar la convergencia. Si f es una función continua en el intervalo [a, b] y f(a)f(b) < 0, entonces este método converge a la raíz de f. De hecho, una cota del error absoluto es: Plantilla:Ecuación en la n-ésima iteración. La bisección converge linealmente, por lo cual es un poco lento. Sin embargo, se garantiza la convergencia si f(a) y f(b) tienen distinto signo.
Si existieran más de una raíz en el intervalo entonces el método sigue siendo convergente pero no resulta tan fácil caracterizar hacia qué raíz converge el método.
Algorisme
Para aplicar el método consideremos tres sucesiones definidas por las siguientes relaciones: Plantilla:Ecuación Donde los valores iniciales vienen dados por: Plantilla:Ecuación Se puede probar que las tres sucesiones convergen al valor de la única raíz del intervalo: Plantilla:Ecuación
Demostración de la convergencia
Suponiendo que se cumplen las condiciones iniciales para la puesta en práctica del algoritmo, definimos r como una raíz dentro del intervalo [a, b]. El intervalo de búsqueda en el n-ésimo paso tiene longitud:
Como , que es la raíz n-ésima calculada, se encuentra siempre dentro del intervalo de búsqueda, tenemos entonces que:
Tomando límites,
Queda demostrado entonces, que si se cumplen las condiciones iniciales del problema, el método de bisección converge al menos, a una de las raíces que se encuentran en el intervalo señalado.
Cota de error
El error cometido tras realizar iteraciones del método de bisección es[1]
Para lograr un error inferior a , el número de iteraciones a realizar debe ser
Bibliografía
- Richard L Burden, J. Douglas Faires (2000), "Numerical Analysis, (7th Ed)", Brooks/Cole. ISBN 0-534-38216-9.
- Corliss, George (1977), "Which root does the bisection algorithm find?", SIAM Review 19 (2): 325–327, ISSN 1095-7200, DOI 10.1137/1019044
Referències
- ↑ «Método de bisección». www.matesfacil.com. [Consulta: 22 febrer 2019].