Método de bissecção - Bisection method

Algumas etapas do método de bissecção aplicada ao longo da faixa inicial [a ₁ ; b ₁ ]. O ponto vermelho maior é a raiz da função.

Em matemática , o método da bissecção é um método para encontrar a raiz que se aplica a quaisquer funções contínuas para as quais se conhece dois valores com sinais opostos. O método consiste em dividir repetidamente o intervalo definido por esses valores e, em seguida, selecionar o subintervalo no qual a função muda de sinal e, portanto, deve conter uma raiz . É um método muito simples e robusto, mas também é relativamente lento. Por causa disso, é frequentemente usado para obter uma aproximação grosseira de uma solução que é então usada como ponto de partida para métodos de convergência mais rápidos. O método também é chamado de método de redução de intervalo , método de pesquisa binária ou método de dicotomia .

Para polinômios , existem métodos mais elaborados para testar a existência de uma raiz em um intervalo ( regra dos sinais de Descartes , o teorema de Sturm , o teorema de Budan ). Eles permitem estender o método de bissecção em algoritmos eficientes para encontrar todas as raízes reais de um polinômio; consulte Isolamento de raiz real .

O método

O método é aplicável para resolver numericamente a equação f ( x ) = 0 para a variável real x , onde f é uma função contínua definida em um intervalo [ a , b ] e onde f ( a ) e f ( b ) têm sinais opostos . Neste caso, um e b são ditos Suporte A raiz desde, pelo teorema valor intermédio , a função contínua f deve ter pelo menos uma raiz no intervalo ( um , b ).

Em cada etapa, o método divide o intervalo em duas partes / metades, calculando o ponto médio c = ( a + b ) / 2 do intervalo e o valor da função f ( c ) nesse ponto. A menos que c seja uma raiz (o que é muito improvável, mas possível), agora existem apenas duas possibilidades: ou f ( a ) e f ( c ) têm sinais opostos e colocam uma raiz entre colchetes, ou f ( c ) e f ( b ) têm sinais opostos e colocam uma raiz entre colchetes. O método seleciona o subintervalo que é garantido como um colchete como o novo intervalo a ser usado na próxima etapa. Desta forma, um intervalo que contém um zero de f é reduzido em largura em 50% a cada passo. O processo continua até que o intervalo seja suficientemente pequeno.

Explicitamente, se f ( a ) ef ( c ) têm sinais opostos, então o método define c como o novo valor para b , e se f ( b ) e f ( c ) têm sinais opostos, então o método define c como o novo a . (Se f ( c ) = 0, então c pode ser tomado como a solução e o processo para.) Em ambos os casos, o novo f ( a ) e f ( b ) têm sinais opostos, então o método é aplicável a este intervalo menor .

Tarefas de iteração

A entrada para o método é uma função contínua f , um intervalo [ a , b ] e os valores da função f ( a ) e f ( b ). Os valores da função são de sinal oposto (há pelo menos um cruzamento de zero dentro do intervalo). Cada iteração executa estas etapas:

Calcule c , o ponto médio do intervalo, c = a + b/2.
Calcule o valor da função no ponto médio, f ( c ).
Se a convergência for satisfatória (ou seja, c - a é suficientemente pequeno, ou | f ( c ) | é suficientemente pequeno), retorne ce pare de iterar.
Examine o sinal de f ( c ) e substitua ( a , f ( a )) ou ( b , f ( b )) por ( c , f ( c )) de modo que haja um cruzamento por zero dentro do novo intervalo.

Ao implementar o método em um computador, pode haver problemas com precisão finita, portanto, geralmente há testes de convergência adicionais ou limites para o número de iterações. Embora f seja contínuo, a precisão finita pode impedir que o valor de uma função seja zero. Por exemplo, considere $f (x) = x - π$ ; nunca haverá uma representação finita de x que dê zero. Além disso, a diferença entre a e b é limitada pela precisão do ponto flutuante; ou seja, conforme a diferença entre a e b diminui, em algum ponto o ponto médio de [ a , b ] será numericamente idêntico a (dentro da precisão de ponto flutuante de) a ou b ..

Algoritmo

O método pode ser escrito em pseudocódigo da seguinte forma:

INPUT: Function f, 
       endpoint values a, b, 
       tolerance TOL, 
       maximum iterations NMAX
CONDITIONS: a < b, 
            either f(a) < 0 and f(b) > 0 or f(a) > 0 and f(b) < 0
OUTPUT: value which differs from a root of f(x) = 0 by less than TOL
 
N ← 1
while N ≤ NMAX do // limit iterations to prevent infinite loop
    c ← (a + b)/2 // new midpoint
    if f(c) = 0 or (b – a)/2 < TOL then // solution found
        Output(c)
        Stop
    end if
    N ← N + 1 // increment step counter
    if sign(f(c)) = sign(f(a)) then a ← c else b ← c // new interval
end while
Output("Method failed.") // max number of steps exceeded

Exemplo: Encontrar a raiz de um polinômio

Suponha que o método de bissecção seja usado para encontrar uma raiz do polinômio

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

Primeiro, dois números e devem ser encontrados de modo que e tenham sinais opostos. Para a função acima, e satisfaça este critério, como ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle f (a)}$ ${\ displaystyle f (b)}$ ${\ displaystyle a = 1}$ ${\ displaystyle b = 2}$

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

e

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

Como a função é contínua, deve haver uma raiz dentro do intervalo [1, 2].

Na primeira iteração, os pontos finais do intervalo que coloca a raiz entre colchetes são e , então o ponto médio é ${\ displaystyle a_ {1} = 1}$ ${\ displaystyle b_ {1} = 2}$

{\ displaystyle c_ {1} = {\ frac {2 + 1} {2}} = 1,5}

O valor da função no ponto médio é . Porque é negativo, é substituído por na próxima iteração para garantir que e tenha sinais opostos. À medida que isso continua, o intervalo entre e se tornará cada vez menor, convergindo para a raiz da função. Veja isso acontecer na tabela abaixo. ${\ displaystyle f (c_ {1}) = (1,5) ^ {3} - (1,5) -2 = -0,125}$ ${\ displaystyle f (c_ {1})}$ ${\ displaystyle a = 1}$ ${\ displaystyle a = 1,5}$ ${\ displaystyle f (a)}$ ${\ displaystyle f (b)}$ ${\ displaystyle a}$ ${\ displaystyle b}$

Iteração	${\ displaystyle a_ {n}}$	${\ displaystyle b_ {n}}$	${\ displaystyle c_ {n}}$	${\ displaystyle f (c_ {n})}$
1	1	2	1,5	-0,125
2	1,5	2	1,75	1.6093750
3	1,5	1,75	1.625	0,6660156
4	1,5	1.625	1,5625	0,2521973
5	1,5	1,5625	1,5312500	0,0591125
6	1,5	1,5312500	1.5156250	-0,0340538
7	1.5156250	1,5312500	1.5234375	0,0122504
8	1.5156250	1.5234375	1.5195313	-0,0109712
9	1.5195313	1.5234375	1,5214844	0,0006222
10	1.5195313	1,5214844	1.5205078	-0,0051789
11	1.5205078	1,5214844	1.5209961	-0,0022794
12	1.5209961	1,5214844	1,5212402	-0.0008289
13	1,5212402	1,5214844	1,5213623	-0.0001034
14	1,5213623	1,5214844	1,5214233	0,0002594
15	1,5213623	1,5214233	1,5213928	0,0000780

Após 13 iterações, torna-se aparente que há uma convergência para cerca de 1,521: uma raiz para o polinômio.

Análise

O método é garantido para convergir para uma raiz de f se f for uma função contínua no intervalo [ a , b ] e f ( a ) e f ( b ) tiverem sinais opostos. O erro absoluto é reduzido à metade em cada etapa, de modo que o método converge linearmente . Especificamente, se c ₁ =a + b/2é o ponto médio do intervalo inicial, e c _n é o ponto médio do intervalo na n- ésima etapa, então a diferença entre c _n e uma solução c é limitada por

{\ displaystyle | c_ {n} -c | \ leq {\ frac {| ba |} {2 ^ {n}}}.}

Esta fórmula pode ser usada para determinar, com antecedência, um limite superior no número de iterações que o método de bissecção precisa para convergir para uma raiz dentro de uma certa tolerância. O número n de iterações necessárias para atingir uma tolerância necessária ε (ou seja, um erro garantido ser no máximo ε), é limitado por

{\ displaystyle n \ leq n_ {1/2} \ equiv \ left \ lceil \ log _ {2} \ left ({\ frac {\ epsilon _ {0}} {\ epsilon}} \ right) \ right \ rceil ,}

onde o tamanho do colchete inicial e o tamanho do colchete necessário A principal motivação para usar o método da bissecção é que sobre o conjunto de funções contínuas, nenhum outro método pode garantir a produção de uma estimativa c _n para a solução c que no pior caso tem um valor absoluto erro com menos de n _1/2 iterações. Isso também é verdadeiro sob várias suposições comuns sobre a função f e o comportamento da função na vizinhança da raiz. ${\ displaystyle \ epsilon _ {0} = | ba |}$ ${\ displaystyle \ epsilon \ leq \ epsilon _ {0}.}$ ${\ displaystyle \ epsilon}$

No entanto, apesar do método de bissecção ser ideal em relação ao desempenho do pior caso sob critérios de erro absoluto, é subótimo em relação ao desempenho médio sob suposições padrão, bem como desempenho assintótico . Alternativas populares para o método de bissecção, como o método secante , método de Ridders ou método de Brent (entre outros), normalmente têm melhor desempenho, pois compensam o desempenho do pior caso para alcançar ordens mais altas de convergência para a raiz. E, uma melhoria estrita no método de bissecção pode ser alcançada com uma ordem mais alta de convergência sem comprometer o desempenho do pior caso com o método ITP .

Veja também

Algoritmo de busca binária
Algoritmo de Lehmer-Schur , generalização do método de bissecção no plano complexo
Intervalos aninhados

Referências

Burden, Richard L .; Faires, J. Douglas (1985), "2.1 The Bisection Algorithm", Numerical Analysis (3rd ed.), PWS Publishers, ISBN 0-87150-857-5

Leitura adicional

Corliss, George (1977), "Which root does the bisection algorithm find?", SIAM Review , 19 (2): 325–327, doi : 10.1137 / 1019044 , ISSN 1095-7200
Kaw, Autar; Kalu, Egwu (2008), Métodos Numéricos com Aplicações (1ª ed.), Arquivado do original em 13/04/2009

links externos

Weisstein, Eric W. "Bisection" . MathWorld .
Bisection Method Notes, PPT, Mathcad, Maple, Matlab, Mathematica do Holistic Numerical Methods Institute

Languages

In other projects