Baixe o app para aproveitar ainda mais
Prévia do material em texto
Edson Luiz França Senne (elfsenne@feg.unesp.br) DEPARTAMENTO DE MATEMÁTICA Universidade Estadual Paulista - Unesp Campus de Guaratinguetá Faculdade de Engenharia 2000 ii C Á L C U L O N U M É R I C O S U M Á R I O Apresentação Referências Bibliográficas 1. Aritmética Computacional 1.1 - Números de Ponto Flutuante ........................................................................................ 1 1.2 - Sistemas de Ponto Flutuante ........................................................................................ 2 1.3 - Aritmética de Ponto Flutuante....................................................................................... 5 1.4 - Dígitos Significativos Exatos ......................................................................................... 7 1.5 - Mal-Condicionamento e Instabilidade Numérica ........................................................... 9 Exercícios Resolvidos ......................................................................................................... 11 Exercícios Propostos........................................................................................................... 13 Exercícios de Programação ................................................................................................ 14 2. Solução de Equações 2.1 - Introdução ................................................................................................................... 17 2.2 - Estimativa de Raízes de Equações Polinomiais ......................................................... 18 Enumeração das Raízes............................................................................................. 19 Localização das Raízes Reais .................................................................................... 21 Localização das Raízes Complexas............................................................................ 22 2.3 - Separação das Raízes................................................................................................ 23 2.4 - Métodos Iterativos de Solução de Equações .............................................................. 25 Ordem de Convergência de um Método Iterativo........................................................ 26 Métodos de Quebra .................................................................................................... 26 Métodos de Ponto Fixo ............................................................................................... 29 Método de Aitken ........................................................................................................ 31 Método de Newton-Raphson....................................................................................... 32 Método das Secantes (ou das Cordas)....................................................................... 35 Método de Müller......................................................................................................... 36 2.5 - Resolução de Sistemas de Equações Não-Lineares .................................................. 37 Exercícios Resolvidos ......................................................................................................... 40 Exercícios Propostos........................................................................................................... 43 Exercícios de Programação ................................................................................................ 44 3. Solução de Sistemas de Equações Lineares 3.1 - Introdução ................................................................................................................... 45 Matrizes Especiais ...................................................................................................... 46 3.2 - Métodos Diretos .......................................................................................................... 47 Método da Eliminação de Gauss ................................................................................ 48 Determinação de Inversa de Matriz............................................................................. 53 Método de Gauss-Jordan............................................................................................ 54 Refinamento Iterativo da Solução ............................................................................... 56 3.3 - Métodos Iterativos....................................................................................................... 58 iii Método de Gauss-Jacobi ............................................................................................ 61 Método de Gauss-Seidel............................................................................................. 61 Estudo da Convergência dos Métodos Iterativos ........................................................ 64 3.4 - Métodos de Fatoração ................................................................................................ 67 Exercícios Resolvidos ......................................................................................................... 74 Exercícios Propostos........................................................................................................... 78 Exercícios de Programação ................................................................................................ 80 4. Interpolação 4.1 - Introdução ................................................................................................................... 81 4.2 - Interpolação Polinomial ............................................................................................... 82 4.3 - Polinômios de Lagrange ............................................................................................. 87 4.4 - O Erro na Interpolação................................................................................................ 89 4.5 - Diferenças Divididas ................................................................................................... 89 4.6 - Diferenças Simples ..................................................................................................... 92 4.7 - Interpolação de Hermite .............................................................................................. 93 4.8 - Interpolação por "Spline"............................................................................................. 97 Exercícios Resolvidos ....................................................................................................... 102 Exercícios Propostos......................................................................................................... 104 Exercícios de Programação .............................................................................................. 105 5. Aproximação de Funções 5.1 - Introdução ................................................................................................................. 107 5.2 - Método dos Quadrados Mínimos .............................................................................. 107 5.3 - Aproximação de Funções Contínuas ........................................................................ 112 5.4 - Polinômios Ortogonais .............................................................................................. 117 5.5 - Método dos Quadrados Mínimos Generalizado ........................................................ 124 Exercícios Resolvidos ....................................................................................................... 130 Exercícios Propostos......................................................................................................... 131 Exercícios de Programação .............................................................................................. 132 6. Integração Numérica 6.1 - Introdução .................................................................................................................135 6.2 - Métodos de Newton-Cotes........................................................................................ 137 Regra dos Retângulos .............................................................................................. 137 Regra dos Trapézios................................................................................................. 139 Regra de Simpson .................................................................................................... 140 Fórmula Geral das Quadraturas Newtonianas .......................................................... 142 6.3 - Métodos de Extrapolação ......................................................................................... 146 6.4 - Quadratura de Gauss................................................................................................ 149 6.5 - Quadraturas Adaptativas .......................................................................................... 153 Exercícios Resolvidos ....................................................................................................... 158 Exercícios Propostos......................................................................................................... 160 Exercícios de Programação .............................................................................................. 162 iv 7. Resolução Numérica de Equações Diferenciais Ordinárias 7.1 - Introdução ................................................................................................................. 165 7.2 - Método de Euler........................................................................................................ 167 7.3 - Métodos Baseados na Série de Taylor ..................................................................... 169 7.4 - Métodos Baseados em Regras de Quadratura......................................................... 171 7.5 - Métodos de Runge-Kutta .......................................................................................... 173 7.6 - Métodos de Passo Múltiplo ....................................................................................... 178 Métodos Explícitos de Passo Múltiplo ....................................................................... 179 Métodos Implícitos de Passo Múltiplo ....................................................................... 180 7.7 - Métodos de Previsão e Correção.............................................................................. 181 7.8 - Método das Diferenças Finitas.................................................................................. 182 Exercícios Resolvidos ....................................................................................................... 185 Exercícios Propostos......................................................................................................... 187 Exercícios de Programação .............................................................................................. 188 v C Á L C U L O N U M É R I C O A P R E S E N T A Ç Ã O Cálculo Numérico foi escrito para servir como material de apoio para a segunda parte da disciplina Computação e Cálculo Numérico, oferecida aos alunos da Faculdade de Engenharia do Campus de Guaratinguetá, da Unesp - Universidade Estadual Paulista. Seu objetivo é apresentar os fundamentos do cálculo numérico, ilustrando a aplicação dos métodos e algoritmos discutidos com programas de computador escritos na linguagem de programação apresentada na primeira parte da disciplina. O Capítulo 1 discute a aritmética dos computadores, chamando a atenção para o fato de que, como os números representados em um computador não obedecem à mesma estrutura algébrica dos números reais (dada a finitude da máquina), a ocorrência de erros é, por vezes, inevitável. No Capítulo 2 discute-se a busca de raízes de equações não- lineares, dando especial atenção aos polinômios, para os quais muitos resultados teóricos são conhecidos. No Capítulo 3 discute-se a solução de sistemas de equações lineares, um assunto importante porque a solução de várias classes de problemas (como é visto nos capítulos seguintes) recaem em sistemas lineares. O Capítulo 4 discute como aproximar uma função, conhecida apenas em alguns pontos discretos, a um polinômio, através da técnica de interpolação. O assunto do Capítulo 5 também é a aproximação de funções, mas com o emprego da técnica dos mínimos quadrados. Neste caso, não se restringe a discussão ao caso discreto e tampouco às aproximações polinomiais, podendo a função de aproximação ser definida como uma combinação linear qualquer de funções conhecidas. No Capítulo 6 estuda-se o problema de como calcular o valor de integrais definidas, para funções conhecidas discretamente ou para as quais não é possível, ou não é desejável, a aplicação de uma forma analítica de resolver o problema. Finalmente, o Capítulo 7 discute a resolução numérica de equações diferenciais ordinárias, apresentando diversos métodos para a solução de problemas de valor inicial e de problemas de valor de contorno. Este volume apresenta ainda, ao final de cada capítulo, vários exercícios resolvidos e exercícios propostos. Propõe também exercícios de programação e, neste particular, recomenda-se a leitura do volume Introdução à Programação de Computadores para rever os conceitos e construções relativas à linguagem de programação discutida na primeira parte dessa disciplina. ELFS vi REFERÊNCIAS BIBLIOGRÁFICAS Cláudio, D.M.; Marins, J.M. Cálculo Numérico Computacional - Teoria e Prática. São Paulo, SP, Atlas, 1994. Dahlquist, G.; Björck, A. Numerical Methods. Englewood Cliffs, NJ, Prentice-Hall, 1974. Phillips, C.; Cornelius, B. Computational Numerical Methods. New York, NY, John Wiley & Sons, 1986. Ralston, A.; Rabinowitz, P. A First Course in Numerical Analysis. Tokyo, Japan, McGraw- Hill, 1978. Ruggiero, M.A.G.; Lopes, V.L.R. Cálculo Numérico: Aspectos Teóricos e Computacionais. São Paulo, SP, Makron Books, 1998. Vandergraft, J.S. Introduction to Numerical Computations. New York, NY, Academic Press, 1978. Cálculo Numérico 1. ARITMÉTICA COMPUTACIONAL 1.1 – Números de Ponto Flutuante Os números representados em um computador não obedecem à mesma estrutura algébrica dos números reais, isto porque a máquina tem recursos finitos. Os números reais representáveis em um computador são denominados números de ponto flutuante. Um número de ponto flutuante é representado como: x m be= . , onde: · x - número de ponto flutuante · m - mantissa · b - base de numeração · e - expoente Se b m- £ <1 1, então tem-se um número de ponto flutuante normalizado. Exemplo: a) b = 10 x = 721.5438 Existem várias formas não normalizadas para representar x como um valor de ponto flutuante. Por exemplo: x = 721.5438 x 100 ou x = 72.15438 x 101. Existe, entretanto, apenas uma forma normalizada: x = 0.7215438 x 103. b) b = 2 x = 1101.01 Neste caso x corresponde ao valor decimal: 25.13212021202121 210123 ==´´++´´++´´++´´++´´++´´ ---- Forma normalizada: x = 0.110101 x 24 No computador os valores de ponto flutuante são representados (na base binária) sempre na forma normalizada. Representação de Números de Ponto Flutuante sinal mantissa expoente espaço de armazenamento (palavra) Cálculo Numérico 1 – Aritmética Computacional 2 Exemplo: Considere um computador com o seguinte espaço de armazenamento: palavra = 8 bits espaço para mantissa = 4 bits espaço para expoente = 3 bits ou seja: s m e Neste caso, tem-se: Valores Possíveis da Mantissa Valores Possíveis do Expoente Binário Decimal Binário Decimal0.1111 0.9375 000 -4 0.1110 0.8750 001 -3 0.1101 0.8125 010 -2 0.1100 0.7500 011 -1 0.1011 0.6875 100 0 0.1010 0.6250 101 1 0.1001 0.5625 110 2 0.1000 0.5000 111 3 Notar que a representação do expoente corresponde à representação binária de: e + 2 1n - , onde n é o espaço disponível para o expoente. Por exemplo: expoente = -2. Neste caso, a representação do expoente -2 será a representação binária de: -2 + 23 1- = -2 + 4 = 2 ou seja: 010 Observe que neste caso: · o maior número representável (em notação decimal) será: x = 0.9375 x 23 = 7.5 · o total de números representáveis é dado por: 2 (+,-) x 8 (mantissas) x 8 (expoentes) + 1 (zero) = 129 1.2 – Sistemas de Ponto Flutuante Um sistema de ponto flutuante corresponde à união de todos os números de ponto flutuante representáveis e é escrito como F(b,m,n), onde: · b - base de numeração · m - número de dígitos na mantissa · n - número de dígitos para a representação do expoente (incluindo o sinal) Cálculo Numérico 1 – Aritmética Computacional 3 No exemplo anterior, o sistema de ponto flutuante pode ser representado por: F(2,4,3). Dado um sistema de ponto flutuante F(b,m,n) tem-se: 1. Para qualquer mantissa a, b a- £ <1 1 2. " Î Þ - Îx F b m n x F b m n( , , ) ( , , ) 3. A cardinalidade de F (total de números representáveis) é dado por: 2 ´ (b-1).( )bm-1 ´ ( )bn + 1 onde: · 2 vezes corresponde a positivo e negativo; · (b-1) são os dígitos possíveis na primeira posição da mantissa; · ( )bm-1 são os dígitos restantes da mantissa; · ( )bn é o total de expoentes possíveis; · mais 1 corresponde ao valor zero. Seja, por exemplo, F(2,3,2). Logo, as mantissas possíveis são: 0.100, 0.101, 0.110, 0.111 e os expoentes representáveis são: -2, -1, 0, 1. Neste caso, os números positivos representáveis são: ( . ) ( . ) ( . ) ( . ) ( . ) ( . ) ( . ) ( . ) 0100 2 0 00100 0 2 0 2 0 2 1 2 0 2 0 2 1 8 0101 2 0 00101 0 2 0 2 0 2 1 2 0 2 1 2 5 32 0110 2 0 00110 0 2 0 2 0 2 1 2 1 2 0 2 3 16 0111 2 0 00111 2 2 0 1 2 3 4 5 2 2 0 1 2 3 4 5 2 2 0 1 2 3 4 5 2 2 ´ = = ´ + ´ + ´ + ´ + ´ + ´ = ´ = = ´ + ´ + ´ + ´ + ´ + ´ = ´ = = ´ + ´ + ´ + ´ + ´ + ´ = ´ = = - - - - - - - - - - - - - - - - - - - 0 2 0 2 0 2 1 2 1 2 1 2 7 32 0 1 2 3 4 5´ + ´ + ´ + ´ + ´ + ´ =- - - - - e assim por diante, até: ( . ) ( . )0111 2 111 1 2 1 2 1 2 7 4 1 2 0 1 2´ = = ´ + ´ + ´ =- - A tabela a seguir resume os números positivos representáveis neste sistema de ponto flutuante: mantissa expoente 0.100 0.101 0.110 0.111 -2 1/8 5/32 3/16 7/32 -1 1/4 5/16 3/8 7/16 0 1/2 5/8 3/4 7/8 1 1 5/4 3/2 7/4 Esquematicamente: Cálculo Numérico 1 – Aritmética Computacional 4 0 1/41/8 5/32 3/16 5/16 3/8 7/32 7/16 1/2 3/45/8 7/8 1 5/4 3/2 região de overflow 7/4 Da figura acima pode-se ver que os números de ponto flutuante representáveis não estão uniformemente distribuídos no intervalo [-7/4, 7/4]. Nota-se também que entre potências sucessivas da base, o número de valores representáveis é uma constante, dada por: c = (b-1)( )bm-1 (cardinalidade da mantissa) No exemplo acima: · entre 2 2- e 2 1- existem 4 valores: 1/8, 5/32, 3/16 e 7/32 · entre 2 1- e 20 existem 4 valores: 1/4, 5/16, 3/8 e 7/16 · entre 20 e 21 existem 4 valores: 1/2, 5/8, 3/4 e 7/8 Portanto, pode-se definir a densidade de números representáveis entre potências sucessivas da base como: densidade = ( )( )b b b b m k k - - - - 1 1 1 , com k = ..., -1, 0, 1, ... Para o exemplo acima tem-se: k densidade -1 4 1 2 1 4 16 / /- = 0 4 1 1 2 8 - = / 1 4 2 1 4 - = ou seja, a distância entre dois números de ponto flutuante representáveis consecutivos vai aumentanto. Portanto, ao se comparar números de ponto flutuante próximos (por exemplo, para verificar a convergência de um processo iterativo) é conveniente comparar a diferença em relação ao tamanho dos números. Para ilustrar, considere os seguintes conceitos: Erro Absoluto: E x xA = - * , onde: x é o valor verdadeiro e x* é o valor aproximado. Erro Relativo: E x x x E x R A= - = * * * Cálculo Numérico 1 – Aritmética Computacional 5 No caso de números de ponto flutuante, o erro relativo é mais significativo do que o erro absoluto porque, como comentado acima, a comparação de valores de ponto flutuante deve ser feita em relação ao tamanho dos números. Por exemplo: a) Um erro absoluto 6A 10E == em um valor 1510*x == é significativo? Neste caso, ER = = -10 10 10 6 15 9, ou seja, um erro de 106 numa quantidade de 1015 não é significativo (pois 10 9- é um valor pequeno). b) Um erro absoluto 00001.0EA == em um valor x* = 0.00005 é significativo? Neste caso, 2.0 00005.0 00001.0 ER ==== , ou seja, o erro da aproximação é de 20% e portanto, significativo. 1.3 – Aritmética de Ponto Flutuante Algumas leis da aritmética que valem em R (conjunto dos números reais) não valem para a aritmética em F (conjunto dos números de ponto flutuante). Seja, por exemplo, F(2,3,2). a) x = 5/4 y = 3/8 · x + y = 5/4 + 3/8 = 13/8 Ï F (notar que a representação normalizada de 13/8 = ( . )01101 21 2x Ï F, porque requer 4 dígitos na mantissa). b) x = 5/8 y = 3/8 z = 3/4 · (x + y) + z = (( . ) ( . )) ( . )0101 2 0 110 2 0110 20 1 0x x x+ +- = (0.101 + 0.011) + 0.110 = 1.00 + 0.110 = ( . )111 2 · x + (y + z) = ( . ) (( . ) ( . ))0101 2 0 110 2 0 110 20 1 0x x x+ +- = 0.101 + (0.011 + 0.110) = 0.101 + 1.001 = 1.101 = ( . )110 2 (observe que os dígitos assinalados acima precisam ser descartados pois não podem ser representados em F) Logo: (x + y) + z ¹ x + (y + z) Estes exemplos mostram que na aritmética de ponto flutuante, quando um número, para ser representado, precisa de mais dígitos na mantissa do que o máximo permitido, é preciso fazer uma aproximação, o que irá resultar em um erro de arredondamento. Exemplo: Seja F(2,3,2) Cálculo Numérico 1 – Aritmética Computacional 6 x = 9/8 Ï F pois 9/8 = ( . )01001 21 2x e portanto possui um dígito a mais na mantissa do que o máximo permitido. Assim, ( . )01001 21 2x precisa ser arredondado para: ( . )0100 2 1 1x = . ou para: ( . )0101 2 5 4 1x = valor aproximação erro de arredondamento 9/8 = 1.125 1 = 1.00 5/4 = 1.25 1.00 - 1.125 = -0.125 (erro por falta) 1.25 - 1.125 = 0.125 (erro por excesso) Sejam: v1, v2 - valores verdadeiros de dois números positivos. a1, a2 - valores aproximados de v1 e v2, respectivamente. Ei = | vi – ai | - erro absoluto (i = 1,2) Ri = Ei/ai - erro relativo (i = 1,2) Então, tem-se que: ai - Ei £ vi £ ai + Ei (i = 1,2) a) SOMA (a1 - E1) + (a2 - E2) £ v1 + v2 £ (a1 + E1) + (a2 + E2) (a1 + a2) - (E1 + E2) £ v1 + v2 £ (a1 + a2) + (E1 + E2) e portanto: | (v1 + v2) - (a1 + a2) | £ (E1 + E2) ou seja: o erro absoluto da soma é menor ou igual à soma dos erros absolutos das parcelas. Para o erro relativo tem-se: r v v a a a a E E a a E a a E a a a a a E a a a a E a = + - + + £ + + = + + + = + ´ + + ´ ( ) ( )1 2 1 2 1 2 1 2 1 2 1 1 2 2 1 2 1 1 2 1 1 2 1 2 2 2 Seja a = + a a a 1 1 2 . Então: ( ) ( ) 1 1 1 1 2 1 2 1 1 2 2 1 2 - = - + = + - + = + a a a a a a a a a aa a . Logo: r r r£ + -a a. ( ).1 21 ou seja: o erro relativo da soma é menor ou igual a um valor intermediário entre os erros relativos das parcelas. b) SUBTRAÇÃO O maior valor de (v1 - v2) ocorre quando: v1 = a1 + E1 e v2 = a2 - E2. Analogamente, o menor valor de (v1 - v2) ocorre quando: v1 = a1 - E1 e v2 = a2 + E2. Portanto, pode-se afirmar que: (a1 - E1) - (a2 + E2) £ v1 - v2 £ (a1 + E1) - (a2 - E2) Cálculo Numérico 1 – Aritmética Computacional 7 (a1 - a2) - (E1 + E2) £ v1 - v2 £ (a1 - a2) + (E1 + E2) e portanto: | (v1 - v2) - (a1 - a2) | £ (E1 + E2) ou seja: o erro absoluto da subtração é menor ou igual à soma dos erros absolutos das parcelas. Para o erro relativo tem-se: r v v a a a a E E a a E a a E a a a a a E a a a a E a = - - - - £ + - = - + - = - ´ + - ´ ( ) ( )1 2 1 2 1 2 1 2 1 2 1 1 2 2 1 2 1 1 2 1 1 2 1 2 2 2 Logo: r a a a r a a a r a a a a a a a r a a a r erro relativo da soma £ - ´ + - ´ = + - ´ + ´ + + ´ é ëê ù ûú 1 1 2 2 1 2 1 2 1 2 1 1 2 2 1 21 2 1 21 244444 344444 ou seja: o erro relativo da subtração é igual ao produto de um fator = a a a a 1 2 1 2 + - > 1 pelo erro relativo da soma (que é um valor intermediário entre os erros relativos das parcelas). Além disso, quando a1 » a2, o fator a a a a 1 2 1 2 + - pode ser muito grande. Ou seja, a subtração de números muito próximos resulta em um erro relativo muito maior do que os erros relativos das parcelas. Este fenômeno é conhecido como cancelamento subtrativo. Exercício: Mostre que as relações a seguir, são válidas para as operações de multiplicação e divisão. 2. MULTIPLICAÇÃO E a E a E r r1 r £ + £ + 1 2 2 1 2 d) DIVISÃO E a a E a E a r r1 r £ + £ + 1 2 1 1 2 2 2 ( ) 1.4 – Dígitos Significativos Exatos Os resultados numéricos obtidos através do computador são, em geral, valores aproximados. A questão é: Qual é o valor exato? Esta questão, geralmente, não pode ser respondida, e dessa forma fica impossível calcular o valor do erro absoluto e, consequentemente, o valor do erro relativo. Entretanto, é possível avaliar o resultado, ou seja, saber o quão exato é o valor aproximado. Seja x um número de ponto flutuante normalizado. Define-se o número de dígitos significativos de x como sendo o número de dígitos após o ponto decimal. Cálculo Numérico 1 – Aritmética Computacional 8 Exemplos: a) 0.00000014 Þ forma normalizada = 0.14 x 10 6- Þ 2 dígitos significativos b) 30457 Þ forma normalizada = 0.30457 x 105 Þ 5 dígitos significativos c) 231000 Þ forma normalizada = 0.231 x 106 Þ 3 dígitos significativos A questão agora é saber: Todos os dígitos significativos são exatos? Para responder a esta questão tem-se o seguinte teorema: Teorema. Se o erro relativo de um número for menor ou igual a 0 5 10. ´ -k , então este número possui k dígitos significativos exatos. Exemplos: a) v = 2/3 a = 0.6667 ER = - = < = ´ - 2 3 0 6667 0 6667 0 0000499 0 00005 0 5 10 4 . . . . . Logo: a = 0.6667 tem os 4 dígitos significativos exatos. b) v = 2/3 a = 0.66998 ER = - = < = ´ - 2 3 0 66988 0 66998 0 00494 0 005 0 5 10 2 . . . . . Logo: a = 0.66998 tem apenas os 2 primeiros dígitos significativos como exatos. Na prática, com a impossibilidade de calcular o erro relativo exatamente, o teorema é utilizado para determinar o número de dígitos significativos exatos de um valor aproximado obtido iterativamente, em relação ao valor aproximado disponível na iteração anterior. Ou seja, o número m de dígitos significativos exatos é calculado aproximadamente como: x x x i i i m+ - - £ ´ 1 0 5 10. ou seja: log log( . ) log( . ) log x x x m m x x x i i i i i i + + -æ è ç ç ö ø ÷ ÷ £ - £ - -æ è ç ö ø ÷ 1 1 0 5 0 5 1.5 - Mal-Condicionamento e Instabilidade Numérica Cálculo Numérico 1 – Aritmética Computacional 9 Um problema é mal-condicionado se, pequenas alterações nos seus dados (ou parâmetros), resultam em grandes modificações em sua solução. Exemplo. O sistema de equações 10 7 8 7 32 7 5 6 5 23 8 6 10 9 33 7 5 9 10 31 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 x x x x x x x x x x x x x x x x + + + = + + + = + + + = + + + = ì í ïï î ï ï tem como solução: x1 = x2 = x3 = x4 = 1. Entretanto, se os valores do lado direito das equações forem modificados para: 32.1, 22.9, 32.9, 31.1, a solução do sistema irá se alterar para: x1 = 6, x2 = -7.2, x3 = 2.9, x4 = -0.1 Neste caso, pode-se notar que pequenas alterações no sistema modificaram radicalmente sua solução. Este é, portanto, um problema mal-condicionado. É importante ressaltar que o mal- condicionamento é uma propriedade do problema em si, e não do método numérico usado para resolvê-lo. Uma outra situação, é quando o método numérico usado para resolver o problema leva a resultados não confiáveis. Neste caso diz-se que existe um fenômeno de instabilidade numérica. Portanto: · método estável - o erro final de arredondamento é pequeno; · método instável - os erros de arredondamento individuais se propagam com efeito crescente, comprometendo o resultado final. Exemplo. Um método iterativo para calcular os valores de: I x x dx nn n = + > =ò a a0 1 0 0 1 2( ; , , ,...) é dado por: I I n I nn n 0 1 1 1 1 2 = +æ è ç ö ø ÷ = - =- ln ( , ,...) a a a Considere que existe um erro (de arredondamento) e no valor I0. Neste caso, as próximas aproximações serão: Cálculo Numérico 1 – Aritmética Computacional 10 I I I I I I I n In n n 1 0 0 2 1 1 2 1 1 1 1 1 1 2 1 2 1 = - + = - - = - - = - + = - + -- a e a ae a ae a a e a a e ( ) [ ] ( ) [ ] ... [ ] ( ) Nota-se, portanto, que se a > 1, o erro vai crescendo a cada iteração, levando a resultados absurdos. O método iterativo acima é portanto instável. Por vezes é possível reformular o método de maneira a evitar a instabilidade numérica. Para o problema acima, por exemplo, pode-se escrever: I n I nn n- = - æ è ç ö ø ÷ =1 1 1 2 1 a ( ..., , ) Como à medida que n aumenta, In diminui, para n suficientemente grande (por exemplo: n = 20) pode-se fazer In @ 0. Assim, se existir um erro e no valor I20 , tem-se: I I I I I I 19 20 20 18 19 19 2 1 1 20 1 1 20 1 1 1 19 1 1 1 19 1 = - + æ è ç ö ø ÷ = - æ è ç ö ø ÷ + = - + æ è ç ö ø ÷ = - æ è ç ö ø ÷ + a e a a e a a e a a e ( ) ( ) e assim por diante. Portanto, com este outro método, o erro vai diminuindo a cada iteração. Logo, este método iterativo é estável. Cálculo Numérico 1 – Aritmética Computacional 11 EXERCÍCIOS RESOLVIDOS 1. Um cilindro tem base com raio R = 1.0 ± 0.05 e altura H = 2.0 ± EH , onde EH é o erro absoluto em H. Com que erro absoluto deve-se determinar H para que o volume do cilindro V R H= p 2 seja calculado com erro absoluto menor ou igual a 0.5? Considere p = 3.1416 como valor exato. Solução: R = 1.0 ± 0.05 Þ E R = 0.05 H = 1.2 ± EH VR H= p( )2 Þ E E R H EV R H£ +p p2 2( ) . Mas como Ep = 0, E EV R H£ p 2 . Por outro lado, E R E HE R H H R2 2 2£ + . Mas: E RE RE RE R R R R2 2£ + = Logo: E R E H REV H R£ +p( ( )) 2 2 . Portanto, se p( ( )) .R E H REH R 2 2 0 5+ = então EV £ 0 5. Assim, deve-se ter: 0 5 2 31416 10 12 2 10 0 052 2. ( ( )) . (( . ) ( . )( . . ))= + = ´ + ´ ´p R E H RE EH R H . Portanto: EH = - ´ @ 0 5 31416 0 12 31416 0 04 . . . . . 2. Pelo teorema de Taylor pode-se escrever: f b f a b a f a b a f a b a n f a b a n f n n n n( ) ( ) ( ) ! ( ) ( ) ! ( ) ... ( ) ! ( ) ( ) ( )! ( )( ) ( ) ( ) ( )= + - + - + + - + - + + + 1 2 1 1 2 2 1 1 x onde: f(x) é uma função definida no intervalo [a, b] f(i)(x) é a i-ésima derivada de f(x) x Î (a, b) Fazendo f(x) = ex e considerando o intervalo [a, b] como [0, 1], é possível usar o teorema de Taylor para estimar o valor de e (base do logaritmo natural). Obtenha esta estimativa para n = 4, trabalhando com 3 casas decimais. Quais os erros cometidos neste processo? O resultado obtido é confiável com quantas casas decimais? Solução: Fazendo f(x) = ex e considerando a = 0 e b = 1 tem-se: e e e e e e1 0 0 2 0 3 0 4 01 0 1 1 0 2 1 0 3 1 0 4 = + - + - + - + - ! ( ) ! ( ) ! ( ) ! Cálculo Numérico 1 – Aritmética Computacional 12 ou seja: e = + + + + = + + + + =1 1 1 2 1 6 1 24 1000 1000 0 500 0 167 0 042 2 709. . . . . . Os erros cometidos no processo são: · erro de truncamento, por não considerar o termo ( ) ! 1 0 5 5- ex, para 0 1< <x . · erro de arredondamento, por trabalhar com 3 casas decimais. Para determinar quantas casas decimais são confiáveis é necessário calcular um limitante o erro relativo correspondente. Para isto, em primeiro lugar deve-se calcular um limitante para o erro absoluto, ou seja: E e ET T< - Þ < ( ) ! . 1 0 5 0 023 5 1 Logo: E E R T= < = < ´ - 2 709 0 023 2 709 0 008 0 5 10 1 . . . . . . Portanto, como o erro relativo é menor do que 0 5 10 1. ´ - pode-se confiar no resultado até a 1a. casa decimal. 3. Considere um sistema de ponto flutuante com base b = 10, espaço de armazenamento de dígitos da mantissa m = 1, e apenas os expoentes -1, 0 e 1. Quantos números de ponto flutuante podem ser representados neste sistema? Apresente todos os números positivos representáveis neste sistema. Calcule a densidade de números representáveis entre potências sucessivas da base para este sistema de ponto flutuante. Quais são os resultados, neste sistema, das seguintes operações: a) 7/4 + 3/8 b) 1/60 - 3/5 Solução: Os números positivos representáveis neste sistema de ponto flutuante podem ser mostrados na tabela a seguir: mantissa expoente 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 -1 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 6 7 8 9 Portanto, podem ser representados neste sistema: (zero) + (27 números positivos) + (27 números negativos) = 55 números representáveis As densidades de números positivos representáveis entre potências sucessivas da base são dadas por: Cálculo Numérico 1 – Aritmética Computacional 13 Entre 10 1- e 100 existem 9 números representáveis Þ d = - = - = = 9 10 10 9 1 01 9 0 9 10 0 1 . . Entre 100 e 101 existem 9 números representáveis Þ d = - = - = = 9 10 10 9 10 1 9 9 1 1 0 Para as operações tem-se: a) { { 7 4 3 8 1 666 0 375 2 4 7 4 3 8 2 2 0 4 2 + = + = Þ + =. . . . 123 b) 1 60 3 5 0 0166 0 6 0 58 1 60 3 5 0 6 0 02 0 6 - = - = - Þ - = - - . . . . . . 123 123 EXERCÍCIOS PROPOSTOS 1. Uma corrente flui através de uma resistência de 10 ohms que tem exatidão de 10% (erro relativo). A corrente é medida como 2.0 A com tolerância de ± 0.1 A. Pela lei de Ohm, a queda de tensão através da resistência é o produto da resistência pela corrente. Quais são os erros absoluto e relativo na tensão computada? 2. Considere um sistema de ponto flutuante com base b = 10, espaço de armazenamento de dígitos da mantissa m = 4, e com apenas os expoentes -3, -2, -1, 0, 1, 2, 3, 4. Quantos números de ponto flutuante podem ser representados neste sistema? Considerando x = 0.7237 ´ 104, y = 0.2145 ´ 10 3- , z = 0.2585 ´ 101, quais são os resultados, neste sistema, das seguintes operações: a) x + y - z b) x y z ´ 3. Considere o sistema de ponto flutuante F(2,4,3). Quais são os números positivos representáveis neste sistema? Quais são os resultados, neste sistema, das operações: a) 5.4 + 3.8 b) 3.4 + 5.8 4. Seja xn n= - 1 3 1 Mostre que: x x xn n n= -- -( ) /3001 1000 31 2 . Trabalhando com 6 casas decimais, gere os valores de x2, x3, x4 e x5 usando esta relação de recorrência e os valores iniciais x0 = 3 e x1 = 1. Comente sobre os resultados obtidos. 5. A equação polinomial x x3 3 2 0- + = tem raízes x = 1 (raiz dupla) e x = -2. Começando com x0 = 0.9, encontre x1, x2, ..., x7 usando a equação de recorrência: ( )( ) ( )x x x x x n n n n n = - - + + æ è ç ö ø ÷- - - - 1 1 1 1 1 3 1 2 1 . Compare os resultados obtidos com os resultados Cálculo Numérico 1 – Aritmética Computacional 14 que se obtêm quando se usa a equação de recorrência ( )( ) ( )x x x x x n n n n n = - - + + æ è ç ö ø ÷- - - - 1 1 1 1 2 3 1 2 1 . Cálculo Numérico 1 – Aritmética Computacional 15 EXERCÍCIOS DE PROGRAMAÇÃO 1. Para demonstrar o efeito de erros de arredondamento considere os seguintes cálculos: H = 1/2 X = 2/3 - H Y = 3/5 - H A = (X+X+X) - H B = (Y+Y+Y+Y+Y) - H C = B/A Procure prever o valor de C. Em seguida implemente estes cálculos num programa e verifique o resultado. 2. Para determinar a precisão de um computador em representar números "reais", pode-se calcular o valor conhecido como Epsilon da Máquina, definido como sendo o maior número E tal que 1 + E = 1. Para o cálculo do Epsilon da Máquina pode-se começar com E igual a 1 e dividir o valor de E ao meio até que 1 + E = 1. Implemente um programa para isto. 3. A equação f(x) = x + ln(x) = 0 possui uma raiz x* próxima a x = 0.55. Considere a seguinte equação de recorrência: x kx e kn n x n = + + - - -1 1 1 Implemente um programa para encontrar o valor da raiz usando este método iterativo. Considere como critério de parada o seguinte: x xn n- <-1 e para e = 10-5. Sugira um valor (real) de k de forma a alcançar uma convergência rápida. Mostre o valor de k, o número de iterações, o valor de x* obtido e o valor de f(x*). 4. Implementar o método iterativo: I I n I nn n 0 1 1 1 1 2 = +æ è ç ö ø ÷ = - =- ln ( , ,...) a a a para calcular os valores de: dx x x I 1 0 n n ò a+= com a > 0 e n = 0, 1, 2, ..., e verificar que para a > 1, o método é instável. Em seguida, implementar o método na forma: I n I nn n- = - æ è ç ö ø ÷ =1 1 1 2 1 a ( ..., , ) e, considerando 30I = 0, verificar que este método iterativo é estável. 17 Cálculo Numérico 2. SOLUÇÃO DE EQUAÇÕES 2.1 - Introdução Neste capítulo estuda-se como encontrar uma ou mais raízes da equação f(x) = 0,ou, em outras palavras, como encontrar os zeros da função f(x). Exemplo: 0.5 1 1.5 x -0.4 -0.2 0.2 0.4 y raiz isolada y = f(x) -0.4 -0.2 1 y 2 4 6 8 10 0.2 0.4 0.6 0.8 x y = f(x) múltiplas raizes A solução de equações por um método iterativo requer: · uma estimativa inicial para o valor da raiz; · uma equação de recorrência para a geração de uma sequência de valores que, espera-se, convirja para a raiz. São ainda importantes para um método iterativo de solução de equações: a) estabelecer sob que condições a sequência de iterações converge para a raiz; b) sabendo-se que a iteração é convergente, estabelecer um critério de parada para o processo iterativo, o que irá depender da precisão que se deseja alcançar. Além disto, no caso de haver vários esquemas iterativos, é preciso ter uma medida da eficiência computacional para escolher o melhor. Neste capítulo serão estudados alguns métodos iterativos de solução de equações. Para a determinação da estimativa inicial para o valor da raiz, pode-se empregar um método gráfico. Exemplo. Estimar o valor de uma raiz positiva de sin x x ( ) - 2 = 0. Através do gráfico da função (ver página seguinte) pode-se concluir que a raiz Î [1.5, 2.0]. Este método para estimativa da raiz é muito conveniente, principalmente quando se dispõe de ferramentas computacionais para a construção do gráfico da função (como, por exemplo, o programa Mathematica). Entretanto, para uma classe especial de funções - os polinômios - muitos resultados são conhecidos e através destes resultados pode-se chegar também a uma estimativa para o intervalo que contém uma raiz. Cálculo Numérico 2 – Solução de Equações 18 0.5 1 1.5 2 2.5 3 x -0.6 -0.4 -0.2 0.2 y 2.2 – Estimativa de Raízes de Equações Polinomiais Uma equação polinomial é da forma: f x a x a x a x a a xn n n n i i i n ( ) ...= + + + + = =- - = å1 1 1 0 0 0 onde n é o grau e ai (i = 0,1,...,n) são os coeficientes (reais) do polinômio. Uma equação polinomial do grau n tem n raízes (reais ou complexas). Um polinômio f(x) = a xi i i n = å 0 pode ser escrito na forma: ((...(( ) ) . ..) )a x a x a x x a x an n n+ + + + +- -1 2 1 0 e esta maneira de escrever o polinômio facilita sua avaliação e a de sua derivada f'(x), pois minimiza o número de operações aritméticas necessárias. Escrito desta forma, a avaliação de f(a) pode ser escrita como: b a b a b i n n f a b n n i i i - + + = = + = - - = + 1 1 1 0 0 2 3 0a a a ( , ,..., ) ( ) Exemplo. Avaliar f(x) = x x x x5 3 26 7 4- + + - no ponto a = 2. Neste caso, pode-se escrever: x5 x4 x3 x2 x1 x0 1 0 -6 1 7 -4 a = 2 2 4 -4 -6 2 1 2 -2 -3 1 -2 b4 b3 b2 b1 b0 f(2) Teorema. f x x b x fi i i n ( ) ( ) ( )= - + = åa a 0 Cálculo Numérico 2 – Solução de Equações 19 Exemplo. Seja f x x x x x( ) = - + + -5 3 26 7 4 e a = 2. Neste caso, pode-se escrever: f x x x x x x( ) ( )( ) ( )= - + - - + + -2 2 2 3 1 24 3 2 Se a é uma raiz de f(x) = 0, então f(a) = 0. Neste caso, pelo teorema anterior, pode-se escrever: f x x b xi i i n ( ) ( )= - = = - åa 0 0 1 e portanto, g x b xi i i n ( ) = = - å 0 1 corresponde a um polinômio de grau n-1 (polinômio reduzido). Assim, pode-se ter o seguinte esquema para resolver f(x) = 0, equação polinomial de grau n: · determinar x = a, uma raiz de f(x) = 0; · determinar coeficientes bi (i = n-1, n-2, ..., 0); · repetir o processo para g(x) = 0. Este processo pode ser muito insatisfatório devido ao efeito acumulativo dos erros introduzidos a cada vez que f(x) é reduzida para g(x). Avaliação de f'(x): f x x b x f x g x fi i i n ( ) ( ) ( ) ( ) ( ) ( )= - + = - + = åa a a a 0 Logo: f x x g x g x f g' ( ) ( ) ' ( ) ( ) ' ( ) ( )= - + Þ =a a a Exemplo. Seja f x x x x x( ) = - + + -5 3 26 7 4 e a = 2. Neste caso, pode-se escrever: x4 x3 x2 x 1 1 2 -2 -3 1 a = 2 2 8 12 18 1 4 6 9 19 b3 b2 b1 b0 g(2) = f'(2) ENUMERAÇÃO DAS RAÍZES a) Enumeração das Raizes Reais Teorema (Descartes). O número de raízes reais positivas de uma equação polinomial p(x)=0 não é maior que o número de trocas de sinal na sequência de seus coeficientes não nulos, e se for menor, então é sempre por um número par. Exemplo. Seja p x x x x( ) = + - -3 22 3 5 Sequência de sinais: + + - - Þ 1 troca. Logo: p(x) tem 1 raiz real positiva. Cálculo Numérico 2 – Solução de Equações 20 O Teorema de Descartes pode ser usado para enumerar também as raízes reais negativas, calculando-se p(-x) p x x x x( )- = - + + -3 22 3 5 Sequência de sinais: - + + - Þ 2 trocas. Logo: p(x) tem 2 ou 0 raizes reais negativas (se tiver 0 raízes reais negativas, terá 2 raízes complexas). b) Enumeração das Raizes Complexas Teorema (Huat). Dada uma equação polinomial p(x)=0 de grau n, se para algum k (1 £ k £ n) tem-se: a a ak k k 2 1 1£ + -. então p(x) = 0 terá raízes complexas. Exemplos: a) p x x x x x x( ) = + + + - +2 3 2 5 35 4 3 2 Descartes: p(x) + + + + - + 2 trocas p(-x) - + - + + + 3 trocas Portanto, os seguintes casos são possíveis: Raizes Reais Positivas Reais Negativas Complexas Total 0 1 4 5 0 3 2 5 2 1 2 5 2 3 0 5 Mas, pelo teorema de Huat: a a a a a a 2 3 3 2 2 4 4 2 1 1 6 3 = = Þ = £ ´ = = ou seja, p(x) possui raizes complexas, o que descarta a última linha da tabela acima. b) p x x x x x x( ) = - - + - +2 3 2 16 5 3 2 Descartes: p(x) + - - + - + 4 trocas p(-x) + + + + + + 0 trocas Huat: Cálculo Numérico 2 – Solução de Equações 21 a a a a a a 3 4 4 2 3 5 5 2 0 0 6 3 = - = Þ = £ ´ = = - ou seja, p(x) possui raizes complexas. Portanto, as possibilidades são as seguintes: Raizes Reais Positivas Complexas Total 0 6 6 2 4 6 4 2 6 LOCALIZAÇÃO DAS RAÍZES REAIS Para dar início a um processo iterativo é preciso uma estimativa para a raiz. Para isto é necessário conhecer onde as raízes estão localizadas. ·· localização das raízes reais: determinação dos limites a (inferior) e b (superior) de um intervalo que contenha todas as raízes. ·· localização das raízes complexas: determinação dos raios a (interno) e b (externo) de um anel que contenha as raízes complexas. Região das Raízes Reais a b Região das Raízes Complexas b a Teorema (Laguerre). Dado um polinômio p(x) e um número a, seja: p(x) = (x - a)q(x) + R Se os coeficientes de q(x) e R forem todos positivos ou nulos, então as raízes reais positivas xi de p(x) são tais que xi < a. Exemplo: p x x x x x x( ) = + - - + -5 4 3 29 20 12 Localização das raízes reais positivas de p(x) = 0 1 1 -9 -1 20 -12 a = 1 1 2 1 2 -7 Cálculo Numérico 2 – Solução de Equações 22 1 1 -9 -1 20 -12 a = 2 2 6 1 3 -3 1 1 -9 -1 20 -12 a = 3 3 12 9 24 132 1 4 3 8 44 120 Logo, pelo teorema de Laguerre, todas as raízes reais positivas de p(x) = 0 são menores que 3, ou seja, 3 é um limite superior do intervalo das raizes. Localização das raízes reais negativas Basta considerar o polinômio p x x x x x x( )- = - + + - - -5 4 3 29 20 12 . Multiplicando-se por – 1 (para que o coeficiente do termo de maior grau seja positivo), tem-se:1 -1 -9 1 20 12 a = 1 1 0 1 0 -9 1 -1 -9 1 20 12 a = 2 2 2 1 1 -7 1 -1 -9 1 20 12 a = 3 3 6 1 2 -3 1 -1 -9 1 20 12 a = 4 4 12 12 52 288 1 3 3 13 72 300 Logo: todas as raízes reais negativas de p(x) = 0 são maiores que -4, ou seja, -4 é um limite inferior para as raizes reais. Portanto, as raízes reais de p(x) = 0 pertencem ao intervalo [-4, 3]. LOCALIZAÇÃO DAS RAÍZES COMPLEXAS Teorema (Kojima). Dado o polinômio p x a x a x a x an n n n( ) ...= + + + +- - 1 1 1 0 , toda raiz a, real ou complexa, de p(x) = 0 é tal que: | a | £ q1 + q2, onde q1 e q2 são os dois maiores valores de: a a i n n i 1 - ì í ï î ï ü ý ï þ ï (i = n-1, ..., 0) Exemplo: p x x x x x x( ) = + - - + -5 4 3 29 20 12 Neste caso tem-se: Cálculo Numérico 2 – Solução de Equações 23 1 1 9 1 1 1 20 1 12 1 1 9 1 20 12 1 1 1 2 1 3 1 4 1 5 1 2 1 4 1 5, , , , , , , , - - ì í ï î ï ü ý ï þ ï = ì í ï îï ü ý ï þï ={1, 3, 1, 2.1147, 1.6437} Logo: q1 = 3 e q2 = 2.1147. Portanto, toda raiz a de p(x) é tal que: | a | £ 5.1147. Desta forma, b = 5.1147 corresponde à cota superior da região que contém as raízes. Para determinar a cota inferior basta considerar o polinômio: p x x x x x x 1 1 1 9 1 20 125 4 3 2 æ è ç ö ø ÷ = + - - + - Multiplicando por x5 tem-se: p x x x x x x x x x x x 1 1 9 20 12 12 20 9 12 3 4 5 5 4 3 2 æ è ç ö ø ÷ = + - - + - = - + - - + + Assim, tem-se: 20 12 1 12 9 12 1 12 1 12 1 1 1 2 1 3 1 4 1 5 - - - - - - - ì í ï î ï ü ý ï þ ï , , , , = {1.6667, 0.2886, 0.9085, 0.5372, 0.6083} ou seja: q1 = 1.6667 e q2 = 0.9085. Portanto a = 1/(1.6667 + 0.9085) = 0.3883. Então, as raízes a (reais ou complexas) de p x x x x x x( ) = + - - + -5 4 3 29 20 12 são tais que: 0.3883 £ | a | £ 5.1147 2.3 – Separação das Raízes A separação das raízes de uma equação corresponde a encontrar uma sequência de subintervalos tais que: - cada subintervalo contém exatamente uma raiz real; - cada raiz real está contida em um subintervalo. Teorema (Bolzano). Se f(x) é uma função contínua num intervalo [a, b] e trocar de sinal nos extremos deste intervalo, então existe pelo menos uma raiz real de f(x) = 0 no intervalo [a, b]. Exemplos: x y = f(x)f(a) a b f(b) x y = f(x) a b f(a) f(b) Cálculo Numérico 2 – Solução de Equações 24 Teorema de Bolzano não se aplica: função descontínua x y a b Teorema (Budan). Seja p(x) um polinômio de grau n e p k( ) ( )a , o valor da derivada de ordem k de p(x), calculada para x = a. Seja Va o número de variações de sinal da sequência: p(a), p'(a), p"(a), ..., p n( ) ( )a Então, o número de raízes de p(x) = 0 no intervalo (a, b) é igual ou menor que V Va b- por um múltiplo de 2. Exemplo: p x x x x( ) = - - +3 22 2 Descartes: + - - + Þ 2 ou 0 raízes reais positivas. Laguerre: 1 -2 -1 2 1 1 1 -1 1 -2 -1 2 2 1 1 0 -1 1 -2 -1 2 3 3 3 6 1 1 2 8 Portanto: cota superior = 3. Seja o intervalo (0,3). Derivadas de p(x): p x x x p x x p x ' ( ) "( ) '"( ) = - - = - = 3 4 1 6 4 6 2 Então: Cálculo Numérico 2 – Solução de Equações 25 p(0) = 2 p'(0) = -1 p"(0) = -4 p'"(0) = 6 p(3) = 8 p'(3) = 14 p"(3) = 14 p'"(3) = 6 Portanto: V V V V0 3 0 32 0 2= = Þ - = . Logo tem-se 2 ou 0 raízes reais em (0, 3). Bisseccionando o intervalo (0, 3) nos intervalos (0, 1.5) e (1.5, 3) e calculando V15. tem-se que V15. = 1. Pode-se concluir, então, que os intervalos (0, 1.5) e (1.5, 3) contém, cada um, uma raiz real. Assim, para separar as raízes pelo teorema de Budan, deve-se conseguir um intervalo (a, b) tal que V Va b- = 1. Exercício: Separar as raizes de p x x x x( ) = - + +3 29 20 1 É importante ressaltar que nesta seção os resultados apresentados se aplicam apenas a equações polinomiais. Para funções transcendentes, como comentado anteriormente, é necessário uma avaliação gráfica da função. Exemplo: f x e xx( ) = - =- 0 Avaliação Gráfica: 1 2 x y y = exp(x) y = x 1 0 Þ Raiz Î [0, 1] 2.4 – Métodos Iterativos de Solução de Equações Um método iterativo de solução de equações requer: - uma estimativa inicial para a raiz (o que pode ser obtida pelo estudo de separação de raízes); - uma fórmula de recorrência, que calcula uma estimativa melhor com base em estimativas conhecidas; - um critério de parada; - uma estimativa do erro cometido (precisão do resultado). Existem quatro maneiras básicas para estabelecer o critério de parada de um método iterativo: Cálculo Numérico 2 – Solução de Equações 26 x x x f x m x x k i L i i i i i i + + - < < ³ > 1 1 e e( ) ( , ) onde: e k L tolerância de erro número de dígitos significativos exatos requeridos número máximo de iterações Em geral, o critério de parada combina um ou mais destes critérios básicos. ORDEM DE CONVERGÊNCIA DE UM MÉTODO ITERATIVO Definição. Uma sequência x x x0 1 2, , ,... converge para x*, se dado e > 0, existe um inteiro I tal que, qualquer que seja i > I, x xi - <* e . Neste caso, tem-se que: lim * i ix x ® ¥ = Definição. Seja uma sequência x x x0 1 2, , , ... que converge para x*. Seja e x xi i= - * . Se existe um número r > 1 e uma constante a ¹ 0 tais que: lim i i i e e® ¥ + =1r a , então rr é denominado ordem de convergência e a é conhecida como constante assintótica de erro. Quanto maior for o número rr , mais rápida será a convergência do método iterativo. Quanto menor for a constante a, mais preciso será o resultado obtido pelo método. MÉTODOS DE QUEBRA Os métodos de quebra para solução de equações partem de um intervalo [a, b] que contenha uma raiz e reduz este intervalo a intervalos cada vez menores. Estes tipos de métodos são intuitivos geometricamente, mas convergem lentamente. Os principais métodos de quebra são: o método da bissecção e o método da falsa-posição. a) MÉTODO DA BISSECÇÃO Seja a equação f(x) = 0 e o intervalo [a, b], que contém uma raiz de f(x). Algoritmo: 1. m = (a + b)/2 2. se f(m) ¹ 0 então: se f(a)´f(m) < 0 então fazer b = m caso contrário, fazer a = m 3. repetir os passos 1 e 2 até satisfazer o critério de parada. Cálculo Numérico 2 – Solução de Equações 27 Ilustração Gráfica: x y a b m1 m2 Problemas do Método da Bissecção: · pode ser difícil encontrar um intervalo [a, b] tal que f(a) ´ f(b) < 0; · erros de arredondamento podem levar a um intervalo que efetivamente não contém uma raiz. Pode-se determinar a ordem de convergência e a constante assintótica de erro do método da bissecção. Seja x* uma raiz de f(x) = 0 e seja e x xi i= - * . Como x x x i i i + -= + 1 1 2 , onde f x f xi i( ). ( )- <1 0 tem-se: e x x x x x x x x x x x x ei i i i i i i i i+ + - - -= - = + - = + - = - + - £1 1 1 1 12 2 2 1 2 1 2 * * * ( *) ( *) Logo: e e i i + £1 1 2 e, consequentemente: lim i i i e e® ¥ + =11 1 2 Portanto, para o método da bissecção tem-se: rr = 1, ou seja, o método possui convergência linear; aa= 1/2, ou seja, a cada iteração o erro reduz-se à metade. Pode-se também determinar o número de dígitos significativos exatos obtidos por iteração de um método. Por exemplo, para o método da bissecção tem-se: m x x m x x x x x x x x x x x x x x i i i i i i i i i i i i i i i i ( , ) ( , ) log( . ) log log( . ) log log log + - + + - - + + - = = - -æ è ç ö ø ÷ - + -æ è ç ö ø ÷ = = -æ è ç ö ø ÷ - -æ è ç ö ø ÷ 1 1 1 1 1 1 1 1 0 5 05 Fazendo: r x x x x i i i i ( ) = - -1 , tem-se: m x x m x x r x r xi i i i i i ( , ) ( , ) log ( ) ( )+ - + - = æ è ç ö ø ÷1 1 1 Cálculo Numérico 2 – Solução de Equações 28 Como: e e i i + £1 1 2 tem-se que: m x x m x xi i i i( , ) ( , ) log( ) .+ -- £ =1 1 2 0 33 Portanto, no método da bissecção, consegue-se cerca de um dígito significativo exato a cada 3 iterações. b) MÉTODO DA FALSA-POSIÇÃO A idéia do método da falsa-posição é, ao invés de particionar o intervalo [a, b] ao meio a cada iteração, particionar na interseção da reta que une os pontos (a, f(a)) e (b, f(b)) com o eixo x. Graficamente: x y a bm f(a) f(b) Neste caso, o ponto de quebra (por congruência de triângulos) pode ser escrito como: b a f b f a b m f b m b f b b a f b f a - - = - - Þ = - - -( ) ( ) ( ) ( )( ) ( ) ( )0 Assim, dada uma equação f(x) = 0 e um intervalo [a, b] que contém uma raiz de f(x), pode-se escrever o algoritmo do método da falsa-posição como: Algoritmo: 1. m b f b b a f b f a = - - - ( )( ) ( ) ( ) 2. se f(m) ¹ 0 então: se f(a)´f(m) < 0 então fazer b = m caso contrário, fazer a = m 3. repetir os passos 1 e 2 até satisfazer o critério de parada. É fácil perceber (como mostram as figuras a seguir) que no método da falsa-posição pode ocorrer que um dos extremos do intervalo mantenha-se sempre fixo. Isto irá ocorrer sempre que a função f(x) for côncava ou convexa no intervalo [a, b]. Cálculo Numérico 2 – Solução de Equações 29 x y raiz a=x0 x1 x2 b y = f(x) x y raiz b=x0x1x2 a y = f(x) Exemplo: p x x x x( ) = - + + =3 25 17 21 0 tem uma raiz no intervalo [-1, 0]. A tabela a seguir ilustra os resultados obtidos pelos métodos da bissecção e da falsa-posição para este caso. Método da Bissecção Método da Falsa-Posição i xi f(xi) xi f(xi) 0 -0.5000 11.125 -0.9130 0.549 1 -0.7500 5.015 -0.9318 0.010 2 -0.8750 1.627 -0.9321 0.000 3 -0.9375 -0.156 4 -0.9063 0.743 5 -0.9219 0.295 6 -0.9297 0.070 7 -0.9336 -0.043 8 -0.9316 0.014 9 -0.9326 -0.014 10 -0.9321 0.000 MÉTODOS DE PONTO FIXO Nos métodos de ponto fixo (ou métodos de iteração funcional), para determinar a raiz pertencente ao intervalo [a, b] da equação f(x) = 0, procura-se determinar uma função g(x) tal que: g(x) = x + c(x).f(x) onde c(x) ¹ 0, " x Î [a, b]. Desta maneira, procurar os valores x* para os quais f(x*) = 0, corresponde a procurar os valores x* tais que: x* = g(x*) (ponto fixo) Dependendo da escolha de g(x) tem-se diferentes métodos de ponto fixo. Exemplo. f x x x( ) = - + =3 3 1 0 Neste caso g(x) pode ser escrita como: Cálculo Numérico 2 – Solução de Equações 30 g x x ou g x x ( ) ( )= + = - 3 2 1 3 1 3 O teorema a seguir, estabelece condições para que exista um ponto fixo para uma função g(x). Teorema. Seja I = [a, b] e g(x) uma função tal que: · g é contínua em I · g(I) = { g(a) | a Î I } Í I Então existe pelo menos um x* Î I tal que x* = g(x*). O problema é saber, no caso de haver várias funções g(x) possíveis, qual é a melhor escolha. Isto é importante porque, dependendo desta escolha, podem acontecer os seguintes casos: Convergência Monotônica x0 y = x y = g(x) x y raiz Convergência Oscilante x0 y = x y = g(x) x y raiz Divergência Monotônica y x y = g(x) y = x raiz x0 Divergência Oscilante raiz y y = x y = g(x) x0 Os teoremas a seguir ajudam na escolha da função g(x). Teorema. Seja g(x) uma função definida em I = [a, b], tal que: · g(i) Í I · x Î I, | g'(x) | £ L < 1 Cálculo Numérico 2 – Solução de Equações 31 Então existe exatamente um x* Î I tal que g(x*) = x*. Teorema. Seja g(x) uma função satisfazendo as condições do teorema anterior. Para x0 Î I, a sequência xn+1 = g(xn ), n = 0,1,2, ... converge para x* e o erro de truncamento cometido na n-ésima iteração é tal que: e x x L L x xt n n n= - < - - -* 1 1 Exemplo. f x x x( ) = - -2 2 I = [0, 2] Escolha de g(x): a) g x x( ) = -2 2 g'(x) = 2x Þ ½ g'(x) ½ > 1 para x > 1 2 b) g x x( ) = + 2 g'(x) = 1 2 2x + Þ ½ g'(x) ½ < 1 para x > 0 Portanto, o método iterativo mais conveniente é: x xi i+ = +1 2 (i = 0, 1, 2, ...) Outro exemplo: 03x3x)x(f 3 =+-= raízes positivas em: [1, 2] e [2, 3] raiz negativa em: [-1, 0] Neste caso, podemos ter: )3x( 3 x3)3x(x2 - -±=Þ-=- Portanto, se quizermos a raiz negativa podemos considerar )3x( 3 )x(g - --= e se quizermos a raiz positiva em [1, 2] podemos considerar )3x( 3 )x(g - - += . Observe que 2)3x( )3x( 3 2 3 )x('g - - - = < 1 para x Î[-1,0] ou para x Î [1,2]. MÉTODO DE AITKEN Cálculo Numérico 2 – Solução de Equações 32 Teorema (Aitken). Sejam os métodos iterativos x xi i ( ) ( ) ( ) 1 1 1 1= -f e x xi i ( ) ( ) ( ) 2 2 1 2= -f , i = 1, 2, ..., de ordem p, os quais convergem para x = a. Com as funções f1 e f2 é possível construir a função F dada por: F( ) ( ( )) ( ) ( ) ( ) ( ) ( ( )) x x x x x x x x x = - - - + f f f f f f f f 1 2 1 2 1 2 1 2 Então, o método iterativo xi = F(xi-1), i = 1, 2, ... tem ordem de convergência superior a p, desde que seja satisfeita a condição: (f1(a) - 1)(f2(a) - 1) ¹ 0 A aplicação mais simples do Teorema de Aitken é quando f1 = f2 = f. Neste caso tem-se: F( ) ( ( )) ( ) ( ) ( ) ( ) ( ( )) ( ) ( ) ( ) ( ) x x x x x x x x x x x x x x x x x x x x xi i i i i i i i i i i i i i i i i i i i i = - - - + = - - + = - - + + + + + + + + + f f f f f f f f f f 1 1 2 1 1 2 1 2 1 22 2 Exemplo. Seja f(x) = x - e x- = 0 e I = [0, 1] Método Iterativo: x = e x- (ou seja, f(x) = e x- ). Neste caso f'(x) = - e x- . Portanto | f'(x) | < 1 para x > 0, ou seja, o método converge. A tabela a seguir mostra os valores obtidos diretamente por este método iterativo com x0 = 0.5 e também os valores obtidos através do método de Aitken. i ff (xi) Método de Aitken 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0.50000 0.60653 0.54524 0.57970 0.56006 0.57117 0.56486 0.56844 0.56641 0.56756 0.56691 0.56728 0.56707 0.56719 0.56712 0.56716 0.56714 0.50000 0.60653 0.54524 0.56762 0.56687 0.56730 0.56714 Cálculo Numérico 2 – Solução de Equações 33 MÉTODO DE NEWTON-RAPHSON Teorema (Taylor). Seja f(x) uma função tal que f(x) e suas n derivadas f(n)(x) (n > 0) são contínuas no intervalo [a, b]. Seja f(n+1)(x) definida no intervalo (a, b). Então existe, pelo menos,um valor x Î (a, b) tal que: f b f a b a f a b a f a b a n f a b a n f n n n n( ) ( ) ! '( ) ( ) ! " ( ) ... ( ) ! ( ) ( ) ( )! ( )( ) ( )= + - + - + + - + - + + + 1 2 1 2 1 1 x Seja xi uma aproximação para a raiz a de f(x) = 0 e seja a = xi + h. Então, como f(a) = 0, para o intervalo [xi, xi + h], pelo Teorema de Taylor, pode-se escrever: 0 = f(a) = f(xi + h) = f(xi) + hf'(xi) + ... Ignorando os próximos termos da expansão de Taylor, tem-se: f(xi) + hf'(xi) = 0 ou seja: h f x f x i i = - ( ) '( ) Portanto, como xi + h deve ser uma nova aproximação para a raiz de f(x), tem-se o método de Newton-Raphson: x x f x f x ii i i i + = - =1 0 1 2 ( ) '( ) , , , ... Exemplo. Sejam f x xe x( ) .= -- 0 2 e x0 0= . Neste caso, f x e x x' ( ) ( )= -- 1 . Portanto, pelo método de Newton-Raphson, tem-se: x f f1 0 00000 0 00000 0 00000 0 20000= - =. ( . ) '( . ) . x f f2 0 20000 0 20000 0 20000 0 25535= - =. ( . ) ' ( . ) . x f f3 0 25535 0 25535 0 25535 0 25915= - =. ( . ) '( . ) . x f f4 0 25915 0 25915 0 25915 0 25917= - =. ( . ) '( . ) . x f f5 0 25917 0 25917 0 25917 0 25917= - =. ( . ) ' ( . ) . Nota-se, deste exemplo, que a convergência no método de Newton-Raphson é rápida. Cálculo Numérico 2 – Solução de Equações 34 Interpretação Geométrica xi y = f(x) x y raiz xi+1 f(xi) f(xi+1) a tg a f x f x x x x x f x f xi i i i i i i i ( ) '( ) ( ) ( ) ( ) '( ) = = - Þ = - + + 1 1 Uma questão importante é: O método converge sempre? As figuras a seguir ilustram algumas situações possíveis. x y y = f(x) x0 = x2 x1 = x3 x y raiz y = f(x) x0 x1 Destas figuras percebe-se claramente que, dependendo da escolha do ponto inicial x0, o método de Newton-Raphson pode não convergir. O teorema a seguir estabelece as condições necessárias para que ocorra a convergência do método de Newton-Raphson. Teorema. Seja f(x) uma função definida em I = [a, b], tal que: · f(a).f(b) < 0 · f'(x) ¹ 0, x Î [a, b] · f"(x) ³ 0 ou f"(x) £ 0, " x Î [a, b] · f a f a b a e f b f b b a ( ) ' ( ) ( ) ' ( ) < - < - Então, para qualquer x0 Î [a, b] o método de Newton-Raphson irá convergir para a raiz de f(x) = 0 pertencente ao intervalo [a, b]. Exemplo. f(x) = x x x3 22 3 1+ + - I = [0, 1] Verificando as condições do teorema acima, tem-se: Cálculo Numérico 2 – Solução de Equações 35 f(0) = -1; f(1) = 5 Þ f(0).f(1) < 0 f'(x) = 3 4 32x x+ + Þ f'(x) > 0 para x Î [0, 1] f"(x) = 6x + 4 Þ f"(x) > 0 para x Î [0, 1] f f ( ) ' ( ) 0 0 1 3 1 3 1 0= - = < - f f ( ) ' ( ) 1 1 5 10 1 2 1 0= = < - Logo, para qualquer x0 Î [0, 1] o método irá convergir. Ordem de Convergência do Método de Newton-Raphson 0 2 2 = = + - + - f x f x x x f x x x fi i i i( *) ( ) ( * ) '( ) ( * ) "( )x com x Î (xi, x*). Dividindo-se por f'(xi) tem-se: f x f x x x x x f f x i i i i i ( ) '( ) ( * ) ( * ) " ( ) '( ) + - + - = 2 2 0 x Por outro lado: x x f x f xi i i i + = -1 ( ) ' ( ) . Portanto: f x f x x xi i i i ( ) '( ) = - +11. Logo: ( ) ( * ) ( * ) " ( ) '( ) ( * ) ( * ) "( ) ' ( ) x x x x x x f f x x x x x f f x i i i i i i i i - + - + - = - + - = + + 1 2 1 2 2 0 2 0 x x Portanto, como ei = x* - xi, tem-se: e e k e e k e e ctei i i i i i i + + ® ¥ += - Þ = - Þ =1 2 1 2 1 2 1 2 1 2 lim ou seja: o método de Newton-Raphson tem ordem de convergência quadrática. MÉTODO DAS SECANTES (OU DAS CORDAS) Um problema com o método de Newton-Raphson é o cálculo de derivadas, um problema mal- condicionado. A idéia do método das secantes é, partindo-se de duas aproximações x0 e x1 , substituir a derivada por uma reta que passa pelos pontos (x0, f(x0)) e (x1, f(x1)), como no método da falsa-posição. Cálculo Numérico 2 – Solução de Equações 36 x y raizx0 x1 x2 y = f(x) f(x1) f(x0) Da figura acima (por congruência de triângulos) pode-se escrever: x x f x x x f x f x i i i i i i i + - - - - = - - 1 1 10( ) ( ) ( ) Portanto, o método das secantes pode ser escrito iterativamente como: x x x x f x f x f x ii i i i i i i + - - = - - - =1 1 1 1 2 ( ) ( ) ( ) ( ) , , ... Deve-se observar que o método das secantes não exige que haja troca de sinal da função f(x) no intervalo [xi-1, xi] como no método da falsa-posição. À medida que se aproxima da raiz, f(xi) e f(xi-1) devem ser valores muito próximos e consequentemente, poderá ocorrer o fenômeno do cancelamento subtrativo. Para evitar isto, pode-se escrever o método das secantes como: x x x x f x f x f x f x i i i i i i i i + - - - = - - - 1 1 1 1 1 ( ) ( ) ( ) ( ( ) ( ) ) com | f(xi) | < | f(xi-1) | (do contrário, inverter xi e xi-1). Pode-se mostrar que a ordem de convergência do método das secantes é dada por: r = + @ 1 2 5 1 1618( ) . , ou seja, converge um pouco mais lentamente que o método de Newton- Raphson (para o qual r = 2). MÉTODO DE MÜLLER No método das secantes, consideram-se dois pontos xi-1 e xi e por eles traça-se uma reta para determinar o próximo ponto xi+1 (interpolação linear). O método de Müller considera três pontos: xi-2, xi-1 e xi, e por eles passa uma equação do segundo grau (parábola) a fim de determinar o próximo ponto xi+1. Cálculo Numérico 2 – Solução de Equações 37 Ilustração Gráfica: x y y = f(x) x0 x1 x2 x3 Da figura pode-se ver que g x x x( ) = + +a a a0 2 1 2 é tal que: a a a a a a a a a 0 0 2 1 0 2 0 0 1 2 1 1 2 1 0 2 2 1 2 2 2 x x f x x x f x x x f x + + = + + = + + = ì í ï î ï ( ) ( ) ( ) Resolvendo-se o sistema tem-se: x3 2 1 1 2 0 2 2 4 = - ± - a a a a a , onde o sinal à frente do radical deve ser escolhido de modo que o denominador tenha o maior valor absoluto possível. 2.5 – Resolução de Sistemas de Equações Não-Lineares Considere o seguinte sistema de equações: x y x y + - = + - = ì í î 2 3 0 3 7 02 2 Neste caso, deseja-se saber os valores de x e de y que satisfazem, simultaneamente, as duas equações. Estes valores podem ser vistos no gráfico a seguir, onde as funções y = f1(x) e y = f2(x) são definidas como: f x x1 3 2( ) ( ) /= - e f x x2 27 3( ) = - . -2 -1 1 2 0.5 1 1.5 2 2.5 f1(x) f2(x) y x raiz raiz Cálculo Numérico 2 – Solução de Equações 38 Os métodos de quebra (bissecção e falsa-posição) não podem ser generalizados para sistemas pois as trocas de sinal não caracterizam as raízes de funções de várias variáveis. Entretanto os métodos de ponto fixo e de Newton-Raphson podem ser generalizados facilmente. Seja, por exemplo, o método de ponto fixo: x = f1(x,y) = 3 - 2y y = f2(x,y) = 7 3 2- x Pelas tabelas abaixo pode-se observar que, partindo-se de uma estimativa inicial (x0,y0) = (1.00,1.00) o método converge para a raiz (-1.00, 2.00) (mostrada à esquerda, no gráfico acima). Entretanto, partindo-se da estimativa inicial (x0,y0) = (0.00, 1.00), após 3 iterações, o método diverge. i xi yi i xi yi 0 1.00 1.00 0 0.000 1.000 1 1.00 2.00 1 1.000 2.646 2 -1.00 2.00 2 -2.292 2.000 3 -1.00 2.00 3 -1.000 -8 753. A convergência do método de ponto fixo pode ser estabelecida pela generalização do teorema de convergência para função de uma variável, onde o intervalo I é substituído por uma região circular que contenha a raiz. Para o caso acima, por exemplo, deve-se ter: ¶f ¶ ¶f ¶ ¶f ¶ ¶f ¶ 1 1 2 2 1 2 2 2 2 x y x y L æ è ç ö ø ÷ + æ è ç ö ø ÷ + æ è ç ö ø ÷ + æ è ç ö ø ÷ £ £ para o método convergir. A generalização do método de Newton-Raphson pode ser obtida através da generalização do Teorema de Taylor para funções de várias variáveis. Seja, por exemplo, o caso de funções de duas variáveis. Considere ( )ii y,x a i-ésima aproximação para uma raiz do sistema: ( ) ( )î í ì = = 0y,xf 0y,xf 2 1 Uma nova aproximação para a raiz do sistema pode ser estabelecida como: ii1i ii1i kyy hxx += += + + onde ih e ik são os valores dos passos a serem determinados. Como 1ix + e 1iy + são aproximações para uma raiz do sistema, pode-se escrever: 0)ky,hx(f)y,x(f 0)ky,hx(f)y,x(f iiii21i1i2 iiii11i1i1 @++= @++= ++ ++ Cálculo Numérico 2 – Solução de Equações 39 Pelo Teorema de Taylor pode-se escrever: 0...)y,x( y f k)y,x( x f h)y,x(f)ky,hx(f 0...)y,x( y f k)y,x( x f h)y,x(f)ky,hx(f ii 2 iii 2 iii2iiii2 ii 1 iii 1 iii1iiii1 @+ ¶ ¶ + ¶ ¶ +=++ @+ ¶ ¶ + ¶ ¶ +=++ Ou seja: )y,x(f y )y,x(f k x )y,x(f h )y,x(f y )y,x(f k x )y,x(f h ii2 ii2 i ii2 i ii1 ii1 i ii1 i -= ¶ ¶+ ¶ ¶ -= ¶ ¶ + ¶ ¶ ou então, em notação vetorial: )y,x(f )y,x(f k h y )y,x(f x )y,x(f y )y,x(f x )y,x(f ii2 ii1 i i Jacobiano ii2ii2 ii1ii1 - - =´ ¶ ¶ ¶ ¶ ¶ ¶ ¶ ¶ 4444 34444 21 Portanto, resolvendo o sistema tem-se os valores de ih e ik e portanto, as novas aproximações 1ix + e 1iy + para a solução do sistema de equações. Exemplo. Seja o sistema de equações: f x y e y f x y x y x x y 1 2 4 0 4 0 ( , ) ( , ) cos( ) = - = = + + = ì í î - Para este caso, tem-se: ¶ ¶ ¶ ¶ ¶ ¶ ¶ ¶ f x e f y e f x x y f y x y x y x y1 1 2 2 4 4 = = - - = - + + = - + - - sen( ) sen( ) Considerando como estimativa inicial para a solução o ponto ( )00 y,x = (0.0, 0.0), tem-se: 1 1 k h 04 51 0 0 - - =´ - Resolvendo o sistema de equações lineares acima, tem-se os valores de 0h e 0k . Neste caso: Cálculo Numérico 2 – Solução de Equações 40 20 3 ke 4 1 h 00 = - = Portanto, a nova aproximação para a solução será: 15.015.000.0kyy 25.0)25.0(00.0hxx 001 001 =+=+= -=-+=+= Continuando desta forma, a cada iteração do método de Newton-Raphson, determina-se os novos valores de passo e portanto, novas aproximações para a solução do sistema. Deve-se observar que cada iteração do método de Newton-Raphson aplicado a sistemas de equações não-lineares requer a solução de um sistema de equações lineares (para determinar os passos). A resolução de sistemas de equações lineares é o assunto do capítulo seguinte. EXERCÍCIOS RESOLVIDOS 1. Enumere, localize e separe as raízes reais da equação 2 5 2 03 2x x+ - = . Em seguida utilize o método do ponto fixo para encontrar uma raiz positiva e o método de Newton- Raphson para encontrar uma raiz negativa, caso exista, desta equação. Nos métodos iterativos trabalhe com 3 casas decimais e utilize o critério de parada: x xn n- <-1 0 01. , onde xi corresponde à i-ésima aproximação para o valor da raiz. Solução: p(x) = 2 5 23 2x x+ - Þ p(-x) = - + -2 5 23 2x x = 2 5 23 2x x- + Enumeração: p(x) + + - 1 troca Þ 1 raiz real positiva p(-x) + - + 2 trocas Þ 0 ou 2 raízes reais negativas Localização: - Raiz positiva: 2 5 0 -2 1 ¯ 2 7 7 raiz Î [0, 1] 2 7 7 5 - Raízes negativas: 2 -5 0 2 1 ¯ 2 2 -3 2 -5 0 2 2 ¯ 4 2 -1 Cálculo Numérico 2 – Solução de Equações 41 2 -5 0 2 3 ¯ 6 3 9 raízes Î [-3, 0] 2 1 3 11 Separação das raízes negativas: p x x x( ) = + -2 5 23 2 p x x x p x x p x ' ( ) "( ) "'( ) = + = + = 6 10 12 10 12 2 Seja o intervalo [-3, -2]: p(-3) = -11 p(-2) = 2 p'(-3) = 24 V-3 = 3 trocas de sinal p'(-2) = 4 V-2 = 2 trocas de sinal p"(-3) = -26 p"(-2) = -14 p'"(-3) = 12 p'"(-2) = 12 Logo, como V V- -- =3 2 1, existe uma raiz no intervalo [-3, -2]. Portanto a outra raiz negativa está no intervalo [-2, 0]. Cálculo da raiz positiva - Método do ponto fixo: 5x2 2 x2)5x2(x02x5x2 223 + =Þ=+Þ=-+ Assim: ÞÎ<Þ + + -=Þ + = ]1,0[x1)x('g )5x2( 5x2 1 2 )x('g 5x2 2 )x(g 2 método converge. Seja 000.0x0 = 632.0 502 2 x1 =+´ = 571.0 5565.02 2 x3 =+´ = 565.0 5632.02 2 x2 =+´ = 571.0 5571.02 2 x4 =+´ = Cálculo de raiz negativa - Método de Newton-Raphson: p x x x p x x x( ) '( )= + - = +2 5 2 6 103 2 2 x x p x p xi i i i + = -1 ( ) '( ) . Seja x0 3= - Cálculo Numérico 2 – Solução de Equações 42 x p p1 3 3 3 2 542= - - - - = - ( ) '( ) . x p p2 2 542 2 542 2 542 2 352= - - - - = -. ( . ) '( . ) . x p p3 2 352 2 352 2 352 2 315= - - - - = -. ( . ) '( . ) . x p p4 2 315 2 315 2 315 2 313= - - - - = -. ( . ) '( . ) . 2. Enumere, localize e separe as raízes reais da equação x x3 3 1 0- + = . Em seguida utilize o método do ponto fixo para encontrar uma raiz positiva, caso exista, e o método de Newton-Raphson para encontrar uma raiz negativa desta equação. Nos métodos iterativos trabalhe com 4 casas decimais e utilize o critério de parada: x xn n- <-1 0 01. , onde xi corresponde à i-ésima aproximação para o valor da raiz. Solução: p(x) = x x3 3 1- + Þ p(-x) = - + +x x3 3 1 = x x3 3 1- - Enumeração: p(x) + - + 2 trocas Þ 0 ou 2 raízes reais positivas p(-x) - + + 1 troca Þ 1 raiz real negativa Localização: - Raízes positivas: 1 0 -3 1 1 ¯ 1 1 1 1 -2 1 0 -3 1 2 ¯ 2 4 2 raiz Î [0, 2] 1 2 1 3 - Raiz negativa: 1 0 -3 -1 2 ¯ 2 4 2 raiz Î [-2, 0] 1 2 1 1 Separação das raízes positivas: p x x x p x x p x x p x ( ) ' ( ) "( ) "'( ) = - + = - = = 3 2 3 1 3 3 6 6 Cálculo Numérico 2 – Solução de Equações 43 Seja o intervalo [0, 1]: p(0) = 1 p'(0) = -3 Þ V0 = 2 trocas de sinal p"(0) = 0 p'"(0) = 6 p(1) = -1 p'(1) = 0 Þ V1 = 1 troca de sinal p"(1) = 6 p'"(1) = 6 Logo, como V V0 1 1- = , existe uma raiz no intervalo [0, 1]. Portanto, o intervalo [0, 2] deve conter duas raízes (e não zero raízes). Conclui-se então que a outra raiz positiva está no intervalo [1, 2]. Cálculo da raiz positiva - Método do ponto fixo: x x x x3 3 3 1
Compartilhar