Matematica

Nesta aula. . .

Conteúdo
1

Método de bissecções

1

2

Cadeias de caracteres

5

1

Método de bissecções

Resolução numérica de equações
Problema: encontrar uma solução x∗ da equação x3 − 5x + 2 = 0
Equivalente: encontrar zeros da função f (x) = x3 − 5x + 2
• Polinómio do 3o grau: não tem uma fórmula resolvente simples
• Podemos obter aproximações x1 , x2 , . . . tais que limn→∞ xn = x∗
• Paramos quando o erro |x∗ − xn | for aceitável
Método de bissecções
Pré-condições:
• f contínua em [a, b]
• f (a) × f (b) < 0 (f (a) e f (b) têm sinais opostos)
• f tem uma raiz única em [a, b]
Método recursivo:
1. calculamos o ponto médio m = (a + b)/2
2. se f (a) × f (m) < 0: a raiz está em [a, m]
3. caso contrário: a raiz está em [m, b]
4. repetir com o novo intervalo encontrado

1

Método de bissecções

Método de bissecções recursivo def bissect(f, a, b, n):
"Efectuar n bissecções de f(x)=0 em [a,b]."
# calcula o ponto médio m = (a+b)/2.0
# terminou? if n==0: return m
# ponto médio
# senão, parte o intervalo ao meio if f(a)*f(m) < 0: return bissect(f, a, m, n-1) else: return bissect(f, m, b, n-1)
Execução
# equação x**3-5*x+2==0 def eq(x): return x**3-5*x+2
# zero em [0,1]
>>> bissect(eq,
0.421875
# zero em [0,1]
>>> bissect(eq,
0.41455078125

com 5 iterações
0.0, 1.0, 5) com 10 iterações
0.0, 1.0, 10)

2

# verificação
>>> eq(0.41455078125)
-0.0015123802004382014
Eliminar a recursão
• chamadas recursivas apenas no final da função
• podem ser substituídas por iteração com um ciclo while
• vantagem: reduz o uso de pilha de execução (stack)
Método de bissecções iterativo def bissect(f, a, b, n):
"Efectua n bissecções de f(x)=0 em [a,b]." while n>0: m = (a+b)/2.0 # calcula o ponto médio
# parte o intervalo ao meio if f(a)*f(m) < 0: b = m else: a = m n = n-1
# fim do ciclo
# resultado é o ponto médio final return m
# fim do programa
Exercício
Seja x a raíz exacta e x a aproximação