217 pág.

Pré-visualização | Página 9 de 38
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) +