NotasdeAula_CN

algoritmos que tem um comportamento polinomial
e algoritmos que tem um comportamento exponencial. Quando um algoritmo
apresenta uma complexidade polinomial dizemos que a complexidade é do tipo
erros computacionais 41
O(np), onde n indica o tamanho do problema e p a ordem do polinômio. Quando
a complexidade é exponencial, ela pode ser expressa da forma O(en).
Exemplo 1.21 Na Seção 2.3 mostraremos que o algoritmo direto para determi-
nar o valor numérico de um polinômio de grau n precisa realizar um número total
de
n2+3n
2
operações, o que corresponde a uma complexidade quadrática, O(n2).
Por outro lado, o algoritmo de Horner necessita apenas de um número total de
2n operações, isto é, a sua complexidade é linear O(n).
1.6 Exercícios propostos
1. Com o desenvolvimento de microcomputadores, tornou-se necessária a pa-
dronização da aritmética com ponto �utuante. Pesquise sobre o padrão
IEEE para a aritmética em ponto �utuante.
2. O sistema de ponto �utuante do supercomputador CRAY T-94 (Cesup-
UFRGS) é dado por: F (2, 51,−1022, 1023). Determine quantos números
são representados nesse sistema e quais as regiões de over�ow e under�ow
do sistema.
3. Escreva um programa, para determinar o menor número positivo n para o
qual a expressão 1 + 2−n−1 = 1 é verdadeira na máquina que está sendo
utilizada.
4. Sejam x1 = 10, 44 e x2 = 2, 15 dois valores aproximados de x e y, res-
pectivamente, até o número de dígitos signi�cativos. Sabendo que Ex =
Ey = 0, 005, determine os limites do erro absoluto e do erro relativo para
as seguintes quantidades:
a) x+ x y
b)
√
x y
c) cos (2x− y) + sen (2x− y)
d)
x
y
− y
x
42 cálculo numérico
Capítulo 2
RESOLUÇÃO DE EQUAÇÕES
ALGÉBRICAS E
TRANSCENDENTAIS
A solução de muitos problemas de engenharia e ciências requer a resolução de
diversos tipos de equações. Dentre estas, há o interesse particular na determina-
ção da solução de equações da forma f(x) = 0, onde f(x) é uma função de�nida
em um certo intervalo.
De�nição 2.1 Um número x0 é dito uma raiz ou zero da função f, quando temos
f(x0) = 0, para a equação f(x) = 0.
Exemplo 2.1 Seja a função f(x) = 2x + 1, x0 = −12 é uma raiz da equação
f(x) = 0.
O problema que surge é como determinar as raízes de uma equação da forma
f(x) = 0. Veremos, nesta seção, alguns métodos para determinação das raízes de
equações algébricas e transcendentais.
As equações algébricas são classi�cadas como equações algébricas polinomiais,
ou que podem ser reduzidas à forma polinomial, e as equações transcendentais,
que são aquelas que não podem ser reduzidas a uma forma polinomial. Tais
equações envolvem, geralmente, funções do tipo exponencial, logarítmica, trigo-
nométrica etc.
As equações algébricas de primeiro, segundo e terceiro graus, além de algumas
de quarto grau e transcendentais, podem ter suas raízes determinadas de forma
analítica. No entanto, em geral, para polinômios de grau superior a ≥ 4, e para
a maioria das equações transcendentais, o problema só pode ser resolvido via
métodos numéricos que aproximam a solução da raiz.
Para encontrarmos numericamente a raiz de uma equação, duas etapas devem
ser seguidas:
44 cálculo numérico
Isolamento: Achar um intervalo [a, b], o menor possível, tal que este contenha
uma e somente uma raiz da equação f(x) = 0.
Re�namento: Melhorar o valor inicial da raiz aproximada até que o grau de
exatidão desejado seja alcançado.
2.1 Isolamento de raízes
O seguinte teorema da álgebra ajuda-nos a encontrar um intervalo onde a raiz
se encontra.
Teorema 2.1 Seja f uma função contínua que assume valores de sinais opostos
nos extremos do intervalo [a, b], isto é, temos que f(a)·f(b) < 0. Então, o intervalo
[a, b] conterá no mínimo uma raiz da equação f(x) = 0. Haverá no mínimo um
número x0 ∈ (a, b), tal que f(x0) = 0.
O Teorema 2.1 pode ser interpretado gra�camente, conforme ilustra a Figura
2.1.
Figura 2.1: Isolamento da raíz λ no intervalo [a, b].
O Teorema 2.1 garante a existência de raizes, no entanto não garante a unici-
dade. Assim, uma raiz x0 bem de�nida será única no intervalo [a, b] se a derivada
f ′(x) existir e preservar o sinal em todo o intervalo.
Observe que, se no intervalo [a, b] tivermos f ′(x) > 0, então a função f(x)
é crescente no intervalo, e se f ′(x) < 0 no intervalo, então a função f(x) é
decrescente, o que restringe a unicidade da raiz no intervalo.
resolução de equações algébricas e transcendentais 45
2.2 Equações algébricas
Seja uma equação algébrica de grau n, n ≥ 1, da forma:
P (x) = anx
n + an−1xn−1 + . . .+ a1x+ a0 = 0, (2.1)
onde os coe�cientes ai são números reais e an 6= 0.
Teorema 2.2 (Teorema Fundamental da Álgebra) Uma equação algébri-
ca de grau n tem exatamente n raízes, reais ou complexas, desde que cada raiz
seja contada levando em consideração sua multiplicidade.
De�nição 2.2 Uma raiz x0 da equação P(x) = 0 tem multiplicidade m se:
P(x0) = P
′(x0) = P′′(x0) = . . . = Pm−1(x0) = 0 e
Pm(x0) 6= 0,
onde Pi(x0) =
diP(x)
dxi
|x=x0 , i = 1, 2, . . . ,m.
Exemplo 2.2 Seja a equação polinomial P(x) = x4 − 5x3 + 6x2 + 4x − 8 = 0 e
considere a raiz x0 = 2. Temos que: P(2) = 0.
P′(x) = 4x3 − 15x2 + 12x + 4⇒ P′(2) = 0,
P′′(x) = 12x2 − 30x + 12⇒ P′′(2) = 0,
P′′′(x) = 24x− 30⇒ P′′′(2) = 18 6= 0.
Portanto, a multiplicidade da raiz x0 = 2 é m = 3. De fato, fatorando a equação,
podemos ver que P(x) = (x + 1)(x− 2)3.
O problema do exemplo 2.2 pode ser facilmente resolvido com a utilização de
um sistema de computação algébrica.
Teorema 2.3 Se os coe�cientes da equação algébrica P(x) = 0 são todos reais,
então as raízes complexas dessa equação são complexos conjugados em pares. Isto
é, se a + b i é uma raiz de P(x) = 0, com multiplicidade m, então o complexo
conjugado a− b i também é uma raiz de P(x) = 0 com multiplicidade m.
Exemplo 2.3 Seja a equação P(x) = x2 − 6x + 10 = 0. Temos como raízes
z = 3 + i e o conjugado z = 3− i.
Corolário 2.1 Uma equação algébrica de grau ímpar com coe�cientes reais tem,
no mínimo, uma raiz real.
A a�rmação desse corolário é bastante intuitiva, pois as raízes complexas
ocorrem sempre ao pares, e, assim, para uma ordem ímpar do polinômio, pelo
menos uma raiz deverá ser real.
46 cálculo numérico
2.3 Valor numérico de um polinômio
Dado um polinômio P (x), o valor numérico de P (x) para um valor x0 é o
valor dado por P (x0). Observe que temos:
Pn(x) = a0 + a1x+ · · ·+ anxn,
Pn(x0) = a0 + a1x0 + · · ·+ anxn0 ,
Pn(x0) = a0 + a1 · x0 + a2 · x0 · x0 + · · ·+ an · x0 · . . . · x0. (2.2)
Assim, de (2.2) vemos que o cálculo do valor numérico P (x0) requer o seguinte
número de operações:
• Número de adições: n;
• Número de multiplicações: n(n+1)
2
.
O número total de operações para obtenção de Pn(x0) é dado pela soma das
operações de adição e multiplicação. Temos, portanto,
#Op = n+
n(n+ 1)
2
=
n2 + 3n
2
. (2.3)
O custo computacional para cálculo do valor numérico de um polinômio é da
ordem de O(n2), onde n da re�ete o tamanho do problema a ser resolvido.
Exemplo 2.4 Um polinômio de grau 9 requer um total de 54 operações para
determinar o valor numérico, pois necessitamos de 9 adições e 45 multiplicações.
Veremos a seguir dois métodos que permitem simpli�car o número de opera-
ções a serem executadas para obtermos o valor numérico de um polinômio.
2.3.1 Método de Briot-Ru�ni
Sejam os polinômios P (x) e Q(x) dados por:
P (x) = a0 + a1x+ · · ·+ anxn,
Q(x) = b1 + b2 + · · ·+ bnxn−1.
Dividindo o polinômio P (x) pelo binômio (x− c), temos:
resolução de equações algébricas e transcendentais 47
P (x) = (x− c)Q(x) + r, (2.4)
onde Q(x) é o polinômio quociente de grau (n− 1) e r é uma constante, resto da
operação. O resto r é o número dado pelo valor numérico P (c), pois temos:
P (c) = (c− c)Q(c) +