Considere o método da bisseção para aproximar a raiz quadrada de 2 :
(a) Escolha e , tais que e (por exemplo e ), e seja .
(b) Escolhidos e , defina
e , se
e , se
Prove, matematicamente, que
(a) Para fixo, temos .
(b) .
(c) .
Assim, conseguimos fazer alphak^2 se aproximar arbitrariamente de 2. Para isso, basta escolher valores suficientemente grande de k.
Dicas
(a) Para resolver esse item, primeiro mostre, por indução, que as sequências de números m0, m1, m2, ldots, mr, ldots e M0, M1, M2, ldots, Mr, ldots são não decrescente e não crescente, nesta ordem, ou seja, vale que
mk+1 >= mk e Mk+1 <= Mk
para todo número k >= 0. A partir daí, conclua que
mell >= mk e Mell <= Mk
para ell >= k. Utilize essas relações para concluir o que se pede.
(b) Para resolver esse item, deve-se separar em 2 casos, conforme alphak^2>2 ou alphak^2<2. No primeiro caso, por exemplo, o algoritmo diz para definir
mk+1=mk e Mk+1=alphak=Mk+mk2
Utilize essas relações para estimar a diferença Mk+1-mk+1 em função de Mk-mk. Uma vez feito isso, utilize a hipótese de indução para concluir o que se pede. A análise do segundo caso é praticamente idêntica ao do primeiro. Basta fazer as modificações necessárias.
(c) O ponto chave para responder esse item é localizar os pontos mk, Mk, alphak e 2 na reta real de modo ordenado, ou seja, verificar se alphak^2>Mk^2>2>mk^2, por exemplo (esse não é o caso!). Uma vez feito isso, o caminho para a resposta consiste, essencialmente, em responder a seguinte pergunta:
Sejam u e v dois números reais tais que 3 <= u <= 5 e 3 <= v <= 5. Qual é o máximo valor que |u-v| pode ter? É possível que |u-v|>5-3=2 ?
Passo 1
O enunciado descreve o método da bisseção para aproximar raiz2. Começamos com m0,M0 tais que
m0^2<2<M0^2,
e definimos alphak=(mk+Mk)/2. Depois, ajustamos o intervalo [mk,Mk] de forma que ele contenha sempre raiz2. Precisamos mostrar:
(a) para todo k e todo ell>= k,
para todo k.
Base (k=0): trivially m1>= m0 e M1<= M0 porque ou trocamos M1=alpha0<M0 ou trocamos m1=alpha0>m0.
Passo indutivo: suponha mk>= mk-1 e Mk<= Mk-1. No cálculo de (mk+1,Mk+1) temos duas opções:
Se alphak^2>2 então mk+1=mk e Mk+1=alphak<Mk.
Se alphak^2<2 então mk+1=alphak>mk e Mk+1=Mk.
Em ambas, mk+1>= mk e Mk+1<= Mk.
Passo 3
De mk+1>= mk e Mk+1<= Mk por indução segue que, se ell>= k,
mell>= mk e Mell<= Mk
Como sempre mell<=alphaell<= Mell, concluímos
mk;<=;mell;<=;alphaell;<=;Mell;<=;Mk,
o que prova (a).
Passo 4
Para (b), notamos que em qualquer passo do algoritmo