Baixe o app para aproveitar ainda mais
Prévia do material em texto
Cálculo Numérico Uma Introdução às Técnicas Elementares Waldir L. Roque Instituto de Matemática Universidade Federal do Rio Grande do Sul Este texto é uma versão preliminar. Direitos autorais reservados ao autor. Sumário Prefácio 9 1 ERROS COMPUTACIONAIS 11 1.1 Sistemas de numeração . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.1 Sistema métrico versus sistema de numeração . . . . . . . 13 1.1.2 Base de numeração . . . . . . . . . . . . . . . . . . . . . . 14 1.1.3 Sistema decimal . . . . . . . . . . . . . . . . . . . . . . . . 14 1.1.4 Sistema binário . . . . . . . . . . . . . . . . . . . . . . . . 15 Conversão de decimal para binário . . . . . . . . . . . . . 16 Parte inteira . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Parte fracionária . . . . . . . . . . . . . . . . . . . . . . . 17 Algoritmo de conversão binário-decimal . . . . . . . . . . . 19 Algoritmo de conversão decimal-binário . . . . . . . . . . . 20 1.1.5 Outros sistemas de numeração . . . . . . . . . . . . . . . . 20 Sistema octal . . . . . . . . . . . . . . . . . . . . . . . . . 20 Sistema hexadecimal . . . . . . . . . . . . . . . . . . . . . 21 1.2 Sistema de ponto �utuante . . . . . . . . . . . . . . . . . . . . . . 22 1.2.1 Representação em ponto �utuante . . . . . . . . . . . . . . 23 1.2.2 Representação compacta de um número . . . . . . . . . . . 24 1.2.3 Operações aritméticas com ponto �utuante . . . . . . . . . 27 Adição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Multiplicação . . . . . . . . . . . . . . . . . . . . . . . . . 28 Divisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.2.4 Distributividade e associatividade . . . . . . . . . . . . . . 30 1.2.5 Precisão e exatidão de máquina . . . . . . . . . . . . . . . 31 1.3 Tipos de erros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.3.1 Erros de dados . . . . . . . . . . . . . . . . . . . . . . . . 32 1.3.2 Erros do modelo . . . . . . . . . . . . . . . . . . . . . . . 32 1.3.3 Erros por truncamento . . . . . . . . . . . . . . . . . . . . 32 1.3.4 Erros por arredondamento . . . . . . . . . . . . . . . . . . 33 1.3.5 Erros absoluto e relativo . . . . . . . . . . . . . . . . . . . 35 3 4 1.4 Propagação de erros . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.4.1 Adição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.4.2 Subtração . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.4.3 Multiplicação . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.4.4 Divisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.4.5 Operação geral . . . . . . . . . . . . . . . . . . . . . . . . 39 1.5 Complexidade computacional . . . . . . . . . . . . . . . . . . . . 40 1.6 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . 41 2 RESOLUÇÃODE EQUAÇÕES ALGÉBRICAS E TRANSCEN- DENTAIS 43 2.1 Isolamento de raízes . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.2 Equações algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.3 Valor numérico de um polinômio . . . . . . . . . . . . . . . . . . . 46 2.3.1 Método de Briot-Ru�ni . . . . . . . . . . . . . . . . . . . 46 2.3.2 Método de Horner . . . . . . . . . . . . . . . . . . . . . . 48 2.4 Limites das raízes polinomiais . . . . . . . . . . . . . . . . . . . . 49 2.5 Número de raízes reais . . . . . . . . . . . . . . . . . . . . . . . . 52 2.6 Regra de sinais de Descartes . . . . . . . . . . . . . . . . . . . . . 52 2.6.1 Raízes imaginárias . . . . . . . . . . . . . . . . . . . . . . 53 2.7 Relações de Girard . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.8 Equações transcendentais . . . . . . . . . . . . . . . . . . . . . . . 55 2.9 Grau de exatidão de uma raiz . . . . . . . . . . . . . . . . . . . . 56 2.10 Raízes complexas . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.11 Métodos iterativos para re�namento de raízes . . . . . . . . . 59 2.11.1 Método da bisseção . . . . . . . . . . . . . . . . . . . . . . 59 Critério da convergência . . . . . . . . . . . . . . . . . . . 60 2.11.2 Método das cordas ou das secantes . . . . . . . . . . . . . 62 Critério da convergência . . . . . . . . . . . . . . . . . . . 65 2.11.3 Método de Newton-Raphson . . . . . . . . . . . . . . . . . 66 Critério da convergência . . . . . . . . . . . . . . . . . . . 68 2.11.4 Método da iteração linear . . . . . . . . . . . . . . . . . . 68 Critério da convergência . . . . . . . . . . . . . . . . . . . 70 2.12 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . 71 3 RESOLUÇÃO DE SISTEMAS DE EQUAÇÕES ALGÉBRI- CAS 75 3.1 Sistemas lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.1.1 Sistemas compatíveis . . . . . . . . . . . . . . . . . . . . . 77 3.1.2 Sistemas triangulares . . . . . . . . . . . . . . . . . . . . . 78 3.2 Transformações elementares . . . . . . . . . . . . . . . . . . . . . 79 5 3.3 Solução numérica de sistemas de equações algébricas lineares . . . 79 3.3.1 Métodos diretos . . . . . . . . . . . . . . . . . . . . . . . . 79 Método de Gauss . . . . . . . . . . . . . . . . . . . . . . . 80 Método da pivotização completa . . . . . . . . . . . . . . . 82 Método de Jordan . . . . . . . . . . . . . . . . . . . . . . 84 3.3.2 Re�namento de soluções . . . . . . . . . . . . . . . . . . . 84 3.3.3 Métodos iterativos . . . . . . . . . . . . . . . . . . . . . . 85 Método de Jacobi . . . . . . . . . . . . . . . . . . . . . . . 86 Método de Gauss-Seidel . . . . . . . . . . . . . . . . . . . 88 Método de Sobre-Relaxação Sucessiva . . . . . . . . . . . . 89 3.4 Sistemas mal-condicionados . . . . . . . . . . . . . . . . . . . . . 89 3.5 Sistemas não lineares . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.5.1 Método do ponto �xo . . . . . . . . . . . . . . . . . . . . . 91 3.5.2 Método de iteração não linear de Seidel . . . . . . . . . . . 96 3.5.3 Método de Newton para sistemas . . . . . . . . . . . . . . 97 3.6 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . 100 4 APROXIMAÇÃO DE AUTOVALORES 105 4.1 Autovalores e autovetores . . . . . . . . . . . . . . . . . . . . . . 105 4.1.1 Método da potência . . . . . . . . . . . . . . . . . . . . . . 107 5 INTERPOLAÇÃO 111 5.1 Interpolação linear . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.2 Interpolação quadrática . . . . . . . . . . . . . . . . . . . . . . . . 115 5.3 Existência e unicidade do polinômio interpolador . . . . . . 116 5.4 Interpolação de Lagrange . . . . . . . . . . . . . . . . . . . . . . . 117 5.5 Erros de truncamento . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.5.1 Erro de truncamento na interpolação linear . . . . . . . . . 120 5.5.2 Erro de truncamento na interpolação quadrática . . . . . . 121 5.5.3 Erro de truncamento na interpolação de Lagrange . . . . . 122 5.6 Interpolação de Newton . . . . . . . . . . . . . . . . . . . . . . . 123 5.6.1 Fórmula de Newton para interpolação com diferenças divididas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.6.2 Comparação dos métodos de Newton e Lagrange . . . . . . 127 5.7 Interpolação com diferenças �nitas . . . . . . . . . . . . . . . . . 129 5.8 Interpolação por Splines . . . . . . . . . . . . . . . . . . . . . . . 130 5.8.1 Spline linear . . . . . . . . . . . . . . . . . . . . . . . . . . 131 5.8.2 Spline cúbica . . . . . . . . . . . . . . . . . . . . . . . . . 132 5.9 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . 137 6 6 AJUSTE DE CURVAS 139 6.1 Critérios para medida da qualidade dos ajustes . . . . . . . . 140 6.2 Método dos mínimos quadrados . . . . . . . . . . . . . . . . . . . 141 6.3 Ajuste polinomial .. . . . . . . . . . . . . . . . . . . . . . . . . . 144 6.3.1 Ajuste por uma reta . . . . . . . . . . . . . . . . . . . . . 144 6.3.2 Ajuste polinomial quadrático . . . . . . . . . . . . . . . . 146 6.3.3 Ajuste polinomial geral . . . . . . . . . . . . . . . . . . . . 148 6.4 Ajuste não linear . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 6.4.1 Casos redutíveis ao linear . . . . . . . . . . . . . . . . . . 149 6.5 Coe�ciente de determinação . . . . . . . . . . . . . . . . . . . . . 151 6.6 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . 151 7 MÉTODOS DE DERIVAÇÃO NUMÉRICA 153 7.1 Aproximação da derivada por diferenças . . . . . . . . . . . . . . 153 7.2 Aproximação por polinômios interpoladores . . . . . . . . . . . . 155 7.3 Derivadas de ordem superior . . . . . . . . . . . . . . . . . . . . . 158 7.4 Extrapolação de Richardson . . . . . . . . . . . . . . . . . . . . . 159 7.5 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . 160 8 MÉTODOS DE INTEGRAÇÃO NUMÉRICA 163 8.1 Regra dos trapézios . . . . . . . . . . . . . . . . . . . . . . . . . . 164 8.1.1 Erro de truncamento . . . . . . . . . . . . . . . . . . . . . 166 8.1.2 Fórmula composta dos trapézios . . . . . . . . . . . . . . . 167 8.2 Regras de Simpson . . . . . . . . . . . . . . . . . . . . . . . . . . 168 8.2.1 Primeira regra de Simpson . . . . . . . . . . . . . . . . . . 168 8.2.2 Primeira regra de Simpson composta . . . . . . . . . . . . 170 8.2.3 Segunda regra de Simpson . . . . . . . . . . . . . . . . . . 171 8.2.4 Segunda regra de Simpson composta . . . . . . . . . . . . 172 8.3 Quadratura Gaussiana . . . . . . . . . . . . . . . . . . . . . . . . 173 8.3.1 Quadratura Gaussiana com n = 1 . . . . . . . . . . . . . . 174 8.3.2 Quadratura gaussiana para n = 2 . . . . . . . . . . . . . . 176 8.3.3 Procedimento geral . . . . . . . . . . . . . . . . . . . . . . 177 8.3.4 Erro de truncamento . . . . . . . . . . . . . . . . . . . . . 178 8.4 Integrais impróprias . . . . . . . . . . . . . . . . . . . . . . . . . . 179 8.5 Integrais múltiplas . . . . . . . . . . . . . . . . . . . . . . . . . . 180 8.5.1 Aplicando a primeira regra de Simpson composta . . . . . 180 8.5.2 Aplicando a quadratura Gaussiana . . . . . . . . . . . . . 186 8.6 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . 189 7 9 RESOLUÇÃO NUMÉRICA DE EDO'S 191 9.1 Resolução do problema do valor inicial . . . . . . . . . . . . . . . 192 9.1.1 Método da série de Taylor . . . . . . . . . . . . . . . . . . 192 9.1.2 Método de Euler . . . . . . . . . . . . . . . . . . . . . . . 195 Erros no método de Euler . . . . . . . . . . . . . . . . . . 197 9.1.3 Métodos de Runge-Kutta . . . . . . . . . . . . . . . . . . . 198 Método de Heun . . . . . . . . . . . . . . . . . . . . . . . 198 Método clássico de Runge-Kutta . . . . . . . . . . . . . . 199 9.2 Métodos de passos múltiplos . . . . . . . . . . . . . . . . . . . . . 201 9.2.1 Método trapezoidal . . . . . . . . . . . . . . . . . . . . . . 201 9.2.2 Método de Simpson . . . . . . . . . . . . . . . . . . . . . . 204 9.2.3 Método de Adams-Basforth-Multon . . . . . . . . . . . . . 204 9.3 Equações de ordens superiores . . . . . . . . . . . . . . . . . . . . 205 9.4 Problema do valor de fronteira . . . . . . . . . . . . . . . . . . . . 210 9.5 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . 213 Bibliogra�a 215 Índice remissivo 217 8 Prefácio Este livro é o resultado da compilação das notas de aula do autor, as quais foram utilizadas para ministrar a disciplina de cálculo numérico em cursos de graduação nas áreas de ciências exatas e engenharias. A proposta deste livro é apresentar um material introdutório sobre técnicas de cálculo numérico. Como um texto introdutório, evitamos a apresentação demasiada de demonstrações de muitos dos resultados mencionados nos teoremas, o quais poderão ser facilmente pesquisados em textos mais avançados sobre o assunto. Os prerequisitos básicos para que o estudante possa estudar por este livro, sem maiores di�culdades, são um curso introdutório de cálculo diferencial e integral, álgebra linear e noções de computação. O conteúdo coberto por este livro é su�ciente para satisfazer os requisitos de um primeiro curso de cálculo numérico para as áreas de ciências exatas e enge- nharias, podendo ser particularmente útil como suporte àquelas disciplinas de noções de cálculo numérico oferecidas para cursos de graduação de outras áreas, as quais tratam apenas de alguns dos tópicos abordados no livro. Ao longo do texto, vários exemplos são apresentados como ilustração do uso da técnica discutida. Ao �nal de cada capítulo exemplos e exercícios adicionais são apresentados e propostos. Deste modo, o livro pode ser utilizado pelos estudantes como se fosse as suas próprias notas de aula. Escrever um texto sobre uma disciplina básica havendo inúmeros outros tex- tos já escritos sobre o assunto, nos leva, muitas vezes, a utilizar alguns exemplos ilustrativos, que pela sua riqueza, já o foram abordados de forma semelhante em outros livros. Como a idéia aqui é sempre ilustrar a aplicação dos métodos com exemplos, a consulta, adicionalmente, a exemplos e exercícios apresentados e propostos em outros livros é importante para enriquecer o aprendizado e a utili- zação dos métodos. Isto permite ao estudante uma maior �exibilidade em leituras complementares, uma vez que a consulta a outros livros amplia o conhecimento. Em muitas instituições de ensino superior do país, os cursos de cálculo nu- mérico nem sempre são ministrados com auxílio de recursos computacionais, em virtude da ausência de equipamentos e software. Por um lado a utilização inte- grada por ser útil, porém muitas vezes há uma grande enfase no aprendizado dos softwares em detrimento do essencial que são as técnicas propriamente ditas. Hoje 9 10 em dia grande parte dos estudantes possuem calculadoras e computadores portá- teis ou mesmo são disponibilizados em laboratórios nas instituições de ensino, o que amplia enormemente a possibilidade de realização de exercícios demandando uma maior experiência computacional. Muitos softwares para computação numé- rica ou mesmo integrados com computação algébrica e grá�ca estão disponíveis tanto comercialmente quanto de domínio público, com uma capacidade enorme de cálculo. Deste modo, este livro está muito mais direcionado ao ensino das técnicas do que às suas implementações computacionais. Uma bibliogra�a complementar é apresentada no �nal do livro, onde os textos citados foram escolhidos com os compromissos de qualidade e acessibilidade, já que a maioria pode ser facilmente encontrada nas bibliotecas, livrarias ou mesmo na internet. Há vários outros bons livros-textos de cálculo numérico que não foram citados na bibliogra�a e que poderão também ser consultados pelos estudantes. Waldir L. Roque, fevereiro de 2013. Capítulo 1 ERROS COMPUTACIONAIS A observação dos fenômenos da natureza é uma grande fonte de inspiração para os pesquisadores. A necessidade de conhecer como e quais são os mecanis- mos associados aos fenômenos da natureza delimitam um conjunto de informa- ções conceituais que dão origem a um problema que, comumente, denominamos de problema físico. O caminho mais imediato e natural para tratarmos e compre- endermos um problema físico é procurando caracterizá-lo e descrevê-lo por meio de um modelo, que em muitas áreas utiliza a matemática como instrumento e linguagem para tal �nalidade. Os modelos matemáticos empregam métodos e técnicas que envolvem, no sen- tido mais amplo, a resolução de equações, cujas soluções subsidiam a comparação dos resultados, por meio de experimentos e/ouobservações, com o fenômeno in- vestigado. Na prática, dizemos que um modelo é tanto mais adequado à descrição do fenômeno quanto menor for o desvio da solução do problema físico com relação ao mundo observável. A Figura 1.1 ilustra a cadeia da pesquisa cientí�ca. Matemática aplicada e computacional é uma área que atua muito fortemente nos vários segmentos da investigação cientí�ca. Particularmente, tem um pa- pel importante na modelagem e resolução dos problemas físicos. A computação tornou-se uma grande aliada nessas etapas, permitindo que a resolução de equa- ções não triviais, e que requerem grande número de cálculos, possam ser realizadas com mais rapidez e e�ciência. A construção de um modelo para um problema físico não é uma tarefa trivial, especialmente quando se deseja levar em consideração muitos detalhes. Portanto, diversas vezes modelos simpli�cados são utilizados, proporcionando uma visão geral do sistema físico em análise, sem contudo ser completo. Os modelos mais simples, por não levarem em consideração algumas variáveis importantes, produ- zem erros inerentes, exclusivamente, devido ao modelo adotado. Um exemplo ilustrativo de erros gerados pela escolha do modelo pode ser visto no caso do movimento de um corpo sujeito a uma aceleração constante. Nesse 12 cálculo numérico Figura 1.1: Cadeia da pesquisa cientí�ca. sistema físico, o modelo pode ser de tal forma que a equação do movimento é dada por: S = s0 + v0t+ 1 2 at2, onde S é o espaço percorrido pelo corpo, partindo de uma posição inicial s0 com velocidade v0 e aceleração a, e t indica o tempo de movimento do objeto. Suponha que desejamos determinar a altura de um penhasco, utilizando esse modelo. Se largarmos uma esfera de aço do alto do penhasco, sua velocidade inicial é nula, v0 = 0. Observando que a esfera levou um tempo t = 5 segundos para atingir o solo, e que a aceleração que atua sobre a esfera é a da gravidade, que podemos considerar como g = 9, 8m/s2, usando a equação anterior, tem-se: S = 0 + 0× 5 + 1 2 × 9.8× 52 = 122, 5m. À primeira vista, podemos achar que esse resultado é con�ável. De certa forma, é razoável, dependendo da exatidão exigida. No entanto, o modelo ado- erros computacionais 13 tado pode ser muito mais re�nado, se considerarmos alguns aspectos importantes que interferem sobre o sistema, como: (i) resistência do ar sobre a esfera, (ii) velocidade e direção do vento, e (iii) constante gravitacional. Assim, um novo modelo, mais so�sticado, pode ser construído, resultando em um modelo mais próximo da realidade do problema físico. Muitas vezes, os modelos conduzem a um conjunto de equações (algébricas, diferenciais ordinárias ou parciais não lineares, tensoriais, etc.) cuja solução é obtida quando tais equações são resolvidas. Na fase de resolução, as equações que descrevem o modelo do sistema físico nem sempre podem ser resolvidas de forma exata, e, portanto, há a necessidade da utilização de métodos numéricos e aproximações de funções, o que conduz a erros. Por �m, a própria medida realizada com aparelhos mecânicos ou eletrônicos apresenta erros em suas medições. Dessa forma, vemos que há muitas etapas no processo de investigação de um problema físico que são passíveis de gerar erros. Neste capítulo, estaremos interessados particularmente nos erros que surgem na fase de resolução do problema. Vamos considerar inicialmente os erros que surgem devido ao sistema de numeração adotado. Para isso, apresentaremos algumas noções sobre os principais sistemas de numeração. 1.1 Sistemas de numeração 1.1.1 Sistema métrico versus sistema de numeração Quando perguntamos a altura de uma pessoa é comum simplesmente ouvirmos um número, por exemplo, 1, 72, que imediatamente assumimos como sendo 1 metro de 72 centimetros. O mesmo ocorre para o peso, 65, que já admitimos como sendo em quilogramas. Aqui temos duas noções postas juntas, um valor numérico 1, 72 e uma indicação do sistema de unidades. Como aprendemos desde a infância o Sistema Métrico Internacional (SI), adotado pelo Brasil e por muitos países, temos uma sensação bastante clara do que signi�ca 1, 72m ou mesmo 65kg. Se perguntassemos a uma pessoa na Inglaterra qual a sua altura poderíamos ouvir algo como 5, 6 pés. Neste caso, notamos imedatamente que temos a noção do que 5, 6 signi�ca, no entanto não temos a sensibilidade do que signi�ca esta medida em pés. Para isso, temos que procurar uma conversor de sistema de unidades para converter pés em metros. O mesmo acontece com peso, dado em libras, ou outras medidas como a temperatura que fomos acostumados com graus centigrados e não em Farenheit. Porém, em qualquer um dos casos, temos a noção clara do valor numérico atribuido à quantidade. Deixando o sistema de unidades à parte, o valor numérico é conhecido já que estamos igualmente empregando o sistema de numeração decimal, ou seja a base escolhida é 10, com os algarísmos sendo representados pelos simbolos 14 cálculo numérico 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Observe que a escolha dos simbolos para representar os elementos que compõem a base do sistema decimal são arbitrários, podendo ser completamente diferentes. Assumindo que os elementos da base são estes, os números em decimal são construídos a partir dos elementos da base. Os sistemas de numeração estão divididos em sistemas posicionais e não posicionais . Nos sistemas posicionais, a posição ocupada pelos algarismos que formam o número é importante e tem um signi�cado especí�co. Por exemplo, no sistema decimal, o número 127, 5 informa-nos que o algarismo 7 corresponde à quantidade de unidades; o algarismo 2 informa o número de dezenas; o algarismo 1, a quantidade de centenas; e o algarismo 5, a parte fracionária referente aos décimos. Assim, a posição de cada algarismo na constituição do número possui um signi�cado próprio. Nos sistemas não posicionais, a posição ocupada pelos algarismos não tem um signi�cado próprio. Um exemplo de sistema não posicional é o sistema romano de numeração. Nesse sistema, temos a unidade representada pela letra I, que ocupa uma posição; o número dois é representado por II, que ocupa duas posições; o número três, por III, ocupando três posições; mas o número quatro é represen- tado por apenas dois algarismos, da forma IV , com duas posições, e o cinco, por V , que possui apenas um algarismo que ocupa uma única posição. Dessa forma, vemos que a posição não é um indicador do valor do número, já que todos estes se refere a unidades. Neste livro, trataremos apenas dos sistemas de numeração que são posicionais. 1.1.2 Base de numeração Seja β um número natural, com β ≥ 2. Um número real r pode ser represen- tado em qualquer base de numeração β, escrito da forma: rβ = (±dndn−1 . . . d2d1d0, d−1d−2 . . . d−m)β, (1.1) onde os di são dígitos inteiros que pertencem à base β, ou seja, são valores entre 0 e β − 1. O valor númerico em decimal do número real escrito em (1.1) é dado por dnβ n + dn−1βn−1 + · · ·+ d1β1 + d0β0 +d−1β−1 + d−2β−2 + · · ·+ d−mβ−m. (1.2) 1.1.3 Sistema decimal O sistema de numeração decimal é um sistema posicional adotado internacio- nalmente para expressar medidas do cotidiano. Não devemos confundir o sistema erros computacionais 15 de numeração com o sistema métrico. O sistema de numeração informa-nos sobre o valor da quantidade, sua magnitude, enquanto o sistema métrico informa-nos sobre a unidade de referência da medida. O sistema decimal é formado pelos números inteiros da base β = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. A partir dessa base, que denotaremos β10, todos os números podem ser expressos neste sistema. De�nição 1.1 Um número no sistema decimal é formado a partir da expressão an10 n + · · ·+ a2102 + a1101 + a0100 + a−110−1 + a−210−2 + · · ·+ a−m10−m, onden,m são números inteiros e os ai são elementos da base decimal. Exemplo 1.1 O número 127, 5 é escrito como: 1× 102 + 2× 101 + 7× 100 + 5× 10−1. A aritmética dos números no sistema decimal é conhecida e não vamos tratá- la aqui. As operações são a adição e subtração (+,−) e a multiplicação e divisão (×,÷). 1.1.4 Sistema binário O sistema de numeração posicional cuja base é composta pelos dois algarismos, β2 = {0, 1}, é chamado de sistema binário de numeração. Nesse sistema, qualquer número pode ser expresso por uma combinação de zeros e uns, de tal forma que seu valor numérico em decimal é obtido por meio da expressão dada na de�nição a seguir: De�nição 1.2 O valor numérico em decimal de um número expresso no sistema binário é obtido tomando-se an2 n + · · ·+ a222 + a121 + a020 + a−12−1 + a−22−2 + · · ·+ a−m2−m, onde n,m são números inteiros e os ai são elementos da base binária. É fácil vermos que os números binários {0, 1, 10, 11, 100, 101, 110} correspon- dem, respectivamente, em decimal aos números {0, 1, 2, 3, 4, 5, 6}. O número bi- nário 1101, 01 corresponde ao valor em decimal dado por: 1× 23 + 1× 22 + 0× 21 + 1× 20 + 0× 2−1 + 1× 2−2, que equivale a 13, 25. 16 cálculo numérico Exercício 1.1 Quais os valores, em decimal, dos números binários 11011 e 101010? A representação dos números por meio do sistema binário tornou-se muito importante com o advento da computação. A razão para isso é bastante simples. Nesse sistema, todos os números podem ser representados por combinações de apenas dois algarismos. Por outro lado, muitos conceitos da Física podem ser representados de forma binária, como, por exemplo, a carga elétrica, positiva ou negativa; a polarização de um meio magnético, que pode estar ou não polarizado etc. Outra vantagem de se representarem os números em binário é que as operações de adição e multiplicação requerem poucas regras para manipulação. As tabelas de adição e multiplicação são extremamente simples. 0 + 0 = 0, 0× 0 = 0, 0 + 1 = 1, 0× 1 = 0, 1 + 0 = 1, 1× 0 = 0, 1 + 1 = 10, 1× 1 = 1. Conversão de decimal para binário A relação da de�nição 1.2 dá-nos um mecanismo para obtermos o valor decimal de um número binário. No entanto, precisamos também conhecer como obter o correspondente número em binário a partir do número em decimal. O processo de passagem do número em decimal para binário é feito em duas etapas: 1. Parte inteira; 2. Parte fracionária. Parte inteira O método das divisões sucessivas é utilizado para obtenção do correspondente valor em binário, partindo-se da parte inteira de um número escrito em decimal. Considerando a parte inteira de um número N em decimal, dividimos este número por dois; em seguida, o resultado da divisão é novamente dividido por dois, se- guindo esse procedimento sucessivas vezes até que o quociente 1 seja encontrado. O número expresso em binário é obtido tomando-se a concatenação do último quociente com os restos das divisões, lendo-se no sentido inverso ao que foram obtidos. Esse procedimento é ilustrado na Figura 1.2. erros computacionais 17 Figura 1.2: Conversão da parte inteira: decimal para binário. O número Nβ=10 em binário é construído da forma: Nβ=2 = 1rnrn−1 · · · r3r2r1. (1.3) Exemplo 1.2 O número 18 é representado na base binária da forma: 18 b2 0 9 b2 1 4 b2 0 2 b2 0 1 Portanto, seguindo o procedimento de concatenação, obtemos 18β=10 = 10010β=2. Exercício 1.2 Encontre a representação binária para os 20 primeiros números inteiros em decimal. Parte fracionária A parte fracionária de um número em decimal é obtida em binário por meio da aplicação do método das multiplicações sucessivas. Nesse caso, devemos con- siderar a parte fracionária do número; então: 1. multiplicamos o número fracionário por dois; 2. do resultado, a parte inteira será considerada o primeiro dígito da represen- tação do número em binário. A parte fracionária é novamente multiplicada por dois; 18 cálculo numérico 3. o procedimento continua sucessivamente até obtermos que a parte fracio- nária do último produto seja igual a zero; 4. em algumas ocasiões, os termos da multiplicação passam a repetir-se, ocor- rendo um ciclo. Nesses casos, a representação é periódica. Vejamos os seguintes exemplos de aplicação para a parte fracionária. Exemplo 1.3 Considere a parte fracionária de um número em decimal dada por 0, 1875. A aplicação no método das divisões sucessivas é vista a seguir: 0, 1875× 2 = 0, 3750, 0, 3750× 2 = 0, 7500, 0, 7500× 2 = 1, 5000, 0, 5000× 2 = 1, 0000. Assim, a representação do número em binário é dada por: 0, 1875β=10 = 0, 0011β=2. Vejamos agora o seguinte caso. O número fracionário em decimal é dado por 0, 6. Aplicando o método, temos: 0, 6× 2 = 1, 2, 0, 2× 2 = 0, 4, 0, 4× 2 = 0, 8, 0, 8× 2 = 1, 6, 0, 6× 2 = 1, 2, . . . Vemos que o processo possui um ciclo. A representação em binário é dada por: 0, 6β=10 = 0, 10011001 . . .β=2 , que é periódica binária. Exercício 1.3 Determine a representação binária para o número 13, 25β=10. Su- gestão: considere as partes inteira e fracionárias separadamente e, no �nal, a re- presentação será dada pela parte inteira, em binário,seguida da parte fracionária em binário, separadas por uma vírgula. erros computacionais 19 Embora o sistema binário tenha uma série de vantagens para utilização em sistemas digitais, também apresenta algumas desvantagens. Uma desvantagem de representarmos os números decimais em binário é que a representação binária requer um número maior de bites para representação. Em outras palavras, requer mais espaço físico para armazenar o mesmo número. Suponha que temos o número em binário 1 000 000 000 000β=2 ≡ 212 = 4096β=10. Vemos que são necessários cerca de 13 dígitos binários para representarmos o número equivalente em decimal, o qual é escrito com apenas quatro dígitos. Em geral, podemos estabelecer a relação entre o número de dígitos, pois 2N = 10N log10 2 = 100,3N , onde N corresponde ao número de dígitos na representação binária. Logo, um número em binário requer aproximadamente 0, 3N dígitos em decimais, que se re�ete na maior necessidade de memória física dos computadores. Algoritmo de conversão binário-decimal Seja N = (anan−1 . . . a1a0)β=2 um inteiro binário. Para determinarmos N na forma decimal, tomamos o seguinte procedimento: bn = an bn−1 = an−1 + 2bn bn−2 = an−2 + 2bn−1 . . . = . . . b1 = a1 + 2b2 b0 = a0 + 2b1, onde b0 corresponde ao número N na forma decimal. Exemplo 1.4 Seja o número 1101β=2. Identi�cando os termos, temos: a0 = 1, a1 = 0, a2 = 1, a3 = 1. Agora, b3 = a3 = 1 b2 = a2 + 2b3 = 1 + 2× 1 = 3 b1 = a1 + 2b2 = 0 + 2× 3 = 6 b0 = a0 + 2b1 = 1 + 2× 6 = 13. Logo, temos a correspondência 1101β=2 = 13β=10. 20 cálculo numérico Algoritmo de conversão decimal-binário Seja N um número inteiro positivo em decimal. Para determinarmos sua representação binária (anan−1 . . . a1a0)β=2, tomamos o seguinte procedimento: b0 = N, b1 = b0 − a0 2 , b2 = b1 − a1 2 , . . . . . . bk = bk−1 − ak−1 2 , onde ak = 1, se bk é um número ímpar; ou ak = 0, se bk é um número par. O procedimento termina quando obtemos bk = 0. O valor em binário é obtido pela concatenação retroativa dos valores obtidos para os ak. Exemplo 1.5 Seja o número 187β=10. Aplicando o algoritmo, temos: k 0 1 2 3 4 5 6 7 bk 187 93 46 23 11 5 2 1 ak 1 1 0 1 1 1 0 1 Então: 187β=10 = 10111011β=2. 1.1.5 Outros sistemas de numeração Outros sistemas de numeração que têm sido empregados em computação são os sistemas octal e o hexadecimal. Sistema octal O sistema de numeracão octal possui a base formada pelos oito dígitos inteiros β8 = {0, 1, 2, 3, 4, 5, 6, 7}. A conversão dosistema octal para o sistema decimal ocorre de forma seme- lhante à apresentada para os binários. Portanto, um número em octal é convertido para decimal usando a relação: an8 n + · · ·+ a282 + a181 + a080 + a−18−1 + a−28−2 + · · ·+ a−m8−m, onde os ai são dígitos pertencentes à base octal. erros computacionais 21 Exemplo 1.6 Seja o número em octal 7634, 152β=8. O valor correspondente em decimal é 7× 83 + 6× 82 + 3× 81 + 4× 80 + 1× 8−1 + 5× 8−2 + 2× 8−3 ≈ 3996, 207031β=10. Observe que 8 = 23; portanto, cada algarismo da base octal requer três alga- rismos da base binária para a conversão octal-binário. A tabela de conversão da base octal-binário é dada por: Octal 0 1 2 3 4 5 6 7 Bina´rio 000 001 010 011 100 101 110 111 Utilizando essa relação de grupo para conversão dos algarismos na base octal pelos correspondentes na base binária, a conversão torna-se bastante simples. O octal 7634, 152β=8 ≡ 111 110 011 100, 001 101 010β=2, pois, lembrando que os sistemas são posicionais, podemos substituir para cada posição do algarismo octal seu correspondente agrupamento em binário. Assim, no caso do algarismo 7, temos: 7 ≡ 7× 83 ≡ 7× 29 ≡ (1× 22 + 1× 21 + 1× 20)× 29 ≡ 1× 211 + 1× 210 + 1× 29 ≡ 111 · · · A conversão de binário para octal ocorre de maneira inversa. Basta consi- derarmos agrupamentos de três dígitos binários, a partir da vírgula, e substituir pelo correspondente algarismo da base octal. Exemplo 1.7 Conversão do binário 11011, 10111 para octal. Formando os gru- pos, temos: 011︸︷︷︸ 011︸︷︷︸ , 101︸︷︷︸ 110︸︷︷︸ 3 3 , 5 6 Assim, 11011, 10111β=2 = 33, 56β=8. Sistema hexadecimal O sistema hexadecimal é formado por uma base que contém 16 elementos, os quais são: β16 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A,B,C,D,E, F}. A conversão entre hexadecimal e decimal é imediata, usando an16 n + · · ·+ a2162 + a1161 + a0160 + a−116−1 + a−216−2 + · · ·+ a−m16−m, onde n,m são números inteiros e os ai são elementos da base hexadecimal. 22 cálculo numérico Exemplo 1.8 Converta o número 6AC,E9β=16 para decimal. Tomando a relação de conversão, obtemos: 6× 162 + 10× 161 + 12× 160 + 14× 16−1 + 9× 16−2 ≈ 1708, 910156 A conversão de hexadecimal para binário segue o mesmo raciocínio usado entre octal e binário. Observe que 16 = 24; assim, cada algarismo em hexadecimal corresponde a um agrupamento de 4 algarismos binários. Exercício 1.4 Construa a tabela de conversão dos algarismos da base hexade- cimal para binário. Em seguida, converta o número 76EA, 0Dβ=16 para binário. Qual o valor em hexadecimal do número 101111.0110111β=2? 1.2 Sistema de ponto �utuante Nos computadores, o processamento da informação é realizado em quantidades �xas, tendo como base uma unidade-padrão. Essa unidade recebe o nome de pa- lavra, e o número de dígitos que compõe uma palavra é chamado de comprimento da palavra do computador. Atualmente, os computadores utilizam diferentes arquiteturas, que empregam palavras de comprimentos distintos. Os microcom- putadores utilizam uma palavra de comprimento 16 bites (dígitos binários), as estações de trabalho usam uma palavra de 32 bites e os supercomputadores usam palavras de comprimento 64 bites, para a representação dos números reais. Em um computador, apenas uma quantidade �nita de números pode ser re- presentada. Os números inteiros podem ser representados de forma exata, desde que o comprimento da palavra seja su�ciente para o armazenamento de todos os seus dígitos. Por outro lado, os números reais não são completamente representados no computador. Dessa forma, erros surgem, em virtude da conversão numérica de um sistema de numeração para outro, em particular, de decimal para binário, como já vimos, ou mesmo devido a arredondamentos, em virtude do comprimento �nito da palavra do computador. As primeiras arquiteturas de computador empregavam uma representação dos números chamada de representação de ponto �xo, em que, para cada operação, o usuário tinha que especi�car quantos dígitos deveriam ser usados em uma palavra, para representar as partes inteiras e fracionárias de um número real. Um dos problemas dessa arquitetura é a representação simultânea de números grandes e pequenos nesse sistema. erros computacionais 23 Por exemplo, se tivermos um computador cujo comprimento da palavra é sete bites, e usarmos quatro dígitos para a parte inteira e três para a parte fracioná- ria, o maior número representado por esse computador no sistema decimal será 9999, 999, e o menor, 0000, 001, respectivamente. Para possibilitar maior representatividade dos números, esse problema foi me- lhorado por meio da representação em ponto �utuante. 1.2.1 Representação em ponto �utuante A representação dos números em ponto �utuante permite expressarmos um número real r na base β em uma forma canônica, como: r = ±0, d1d2 . . . dt × βe = ± ( d1 β1 + d2 β2 + · · ·+ dt βt ) × βe, (1.4) onde β é a base do sistema de numeração adotado, e é o expoente da base, tal que I ≤ e ≤ S, e ∈ Z, com I o limite inferior e S o limite superior para a variação do expoente. De�nição 1.3 Os dígitos d1d2 . . . dt formam a mantissa do número e represen- tam seus dígitos signi�cativos. Cada elemento di da mantissa é um símbolo da base β do sistema de numera- ção. Chamando de q = ± 0.d1 . . . dt a mantissa de um número, é fácil veri�carmos que o valor da mantissa q é limitado. De�nição 1.4 Um número r na representação de ponto �utuante é dito norma- lizado quando o dígito d1 de sua mantissa é tal que d1 6= 0. De�nição 1.5 O número t de dígitos signi�cativos do sistema de ponto �utuante corresponde à precisão da máquina. Exemplo 1.9 Seja a base decimal β = 10. O número r = 25, 87 é representado em ponto �utuante normalizado como: 0, 2587 = ( 2 10 + 5 102 + 8 103 + 9 104 ) × 102. O número 5β=10 é representado em binário na representação de ponto �utuante com 101β=2 = 0, 101× 23 = ( 1 2 + 0 22 + 1 23 ) × 23. 24 cálculo numérico Tabela 1.1: Exemplos de sistemas de ponto �utuante. F (β, t, I, S) β t I S Padrão IEEE 2 23 −126 127 IBM 3090 16 5 −65 62 CRAY X-MP 2 47 −16385 8190 De�nição 1.6 O número zero em ponto �utuante é representado por 0β = 0, 000 . . . 0t × βI. A união de todos os números em ponto �utuante, incluindo o zero, é denomi- nada de sistema de ponto �utuante da máquina e denotado por F (β, t, I, S). Na Tabela 1.1, são apresentados os sistemas de ponto �utuante para algumas máquinas. Em muitas linguagens de programação, como Fortran, é possível operar com uma representação de ponto �utuante com precisão dupla. Nesse caso, o sistema é implementado de tal forma que a máquina passa a utilizar duas palavras para armazenar um número, permitindo maior precisão e um intervalo maior de representatividade dos números. De forma geral, as máquinas possuem precisão simples implementada em hardware, enquanto a precisão dupla é implementada via software. Atualmente, há vários sistemas computacionais disponíveis, tanto para cál- culo numérico especi�camente quanto para cálculo simbólico e algébrico, além de possuirem facilidades grá�cas. Dentre os sistemas para cálculo numérico o MATLAB R© é um excelente sistema comercial, porém o SCILAB é um sistema aberto alternativo de excelente qualidade (http://www.scilab.org/). Os sistemas de computação algébrica (SCA), são capazes de realizar cálculos simbolicamente e com precisão arbitrária, porém na prática a precisão torna-se �nita devido às limitações impostas pelo próprio hardware da máquina. Exemplos de tais SCA comerciais são MAPLE R© e MATHEMATICA R© ; enquanto o MAXIMA é livre e pode facilmente ser baixado da internet (http://maxima.sourceforge.net/). 1.2.2 Representação compacta de um númeroVamos supor que temos um sistema de ponto �utuante dado por F (2, 10,−15, 15). O número inteiro 19 é escrito nesse sistema como: 19β=10 = 10011β=2 = 0, 10011× 25 = 0, 10011× 2101 = ( 1 2 + 0 22 + 0 23 + 1 24 + 1 25 + 0 26 + 0 27 + 0 28 + 0 29 + 0 210 ) × 2101. erros computacionais 25 Observando as expressões anteriores, uma representação compacta pode ser escrita para o número 19. Vemos que podemos tomar a seguinte notação 1 0 0 1 1 0 0 0 0 0 0 1 0 1 Os 10 primeiros algarismos correspondem à mantissa do número e os quatro últimos, após as duas barras, correspondem aos bites necessários para a repre- sentação binária dos números do expoente, que estão no intervalo I ≤ e ≤ S. Vemos que essa notação é su�ciente para expressar um número positivo cujo expoente também é positivo. Para podermos representar, por intermédio dessa mesma notação, qualquer número nesse sistema de ponto �utuante, devemos incluir ainda duas caixas, ou dois bites, para incluirmos os sinais do número e do expoente. Dessa forma, teremos: 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 Na notação estendida, temos o primeiro bite para representar o sinal do nú- mero; se positivo, o dígito é 0; se negativo, o dígito é 1. Na posição 12 da notação, é acrescentado um bite para representar o sinal do expoente. Assim, temos aqui um sistema formado por uma palavra de 16 bites. Supondo ainda o mesmo sistema de ponto �utuante e considerando apenas a notação compacta, podemos perguntar quais seriam o menor e o maior valores numéricos, em termos absolutos, representáveis nesse sistema. As respostas podem ser facilmente encontradas, observando que o maior valor numérico é dado por: 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 De outra forma, esse número corresponde a 0, 1111111111× 21111 = 10∑ k=1 1 2k × 215 = 32736β=10. Como o menor número negativo é obtido nesse caso tomando-se o simétrico, já que o valor mínimo do expoente é I = −15, temos, então, −32736β=10. Por outro lado, o menor número representável em valor absoluto é dado por: 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 Logo, o primeiro número positivo nesse sistema corresponde a 0, 1× 2−1111 = 1 2 × 2−15 = 0, 0000152587β=10. 26 cálculo numérico O primeiro número negativo representável no sistema é −0, 0000152587β=10. Por meio desses exemplos, vemos que os números são representados de forma discreta em um sistema de ponto �utuante. Observamos ainda que, para o sistema em questão, F (2, 10,−15, 15), o intervalo onde estão representados os números, incluindo o zero, é [−32736, 32736]. As regiões compreendidas além desses valores formam o que se chama de região de over�ow, isto é, os intervalos (−∞,−32736) ∪ (32736,+∞). As regiões compreendidas entre o zero e o primeiro número positivo ou nega- tivo são chamadas de regiões de under�ow, ou seja, (−0, 0000152587; 0) ∪ (0; 0, 0000152587). De forma geral, para um sistema de ponto �utuante normalizado F (β, t, I, S), o menor número em valor absoluto é determinado por: m = 0, 1× βI , (1.5) e o maior número representável é determinado por: M = 0, (β − 1)(β − 1) . . . (β − 1)× βS. (1.6) É possível mostrar que a quantidade de números que são representáveis expli- citamente por um sistema de ponto �utuante qualquer é dado pela relação N = 2(S − I + 1)(β − 1)βt−1 + 1. (1.7) Para nosso estudo de caso, F (2, 10,−15, 15), temos N = 31745. Com uma cal- culadora programável ou um sistema de computação algébrica é fácil declararmos uma função para a equação (1.7). Exercício 1.5 Veri�que que a distribuição dos números representados pelo sis- tema de ponto �utuante não é igualmente espaçada. Exercício 1.6 Dado o sistema de ponto �utuante F(2, 3,−1, 2), determine quan- tos e quais são os números representados por esse sistema. erros computacionais 27 1.2.3 Operações aritméticas com ponto �utuante Nessa seção, daremos uma noção de como as operações aritméticas são reali- zadas em um sistema de ponto �utuante. Consideremos dois números escritos em um sistema de ponto �utuante F (β, t, I, S), x = 0, d1d2 . . . dt × βe, y = 0, l1l2 . . . lt × βf . Adição A operação de adição entre dois números é realizada em uma seqüência de passos. 1. Os registros dos números são dispostos da forma a seguir, admitindo-se que x ≥ y. x → d1 d2 · · · dt 0 0 · · · 0 y → l1 l2 · · · lt 0 0 · · · 0 Para determinar o valor de a = x+ y, devemos seguir para o passo 2. 2. Calcule o valor g = e− f . Se g ≥ t, então teremos que a = x, e a operação está concluída. Senão, devemos alinhar o registro do número y de g posições a sua direita, isto é: y → 0 · · · 0 l1 l2 · · · | · · · lt 0 · · · 0 3. Adicione os conteúdos de x e y com g = e. a→ b0 ... b1 b2 · · · bt bt+1 · · · 4. Se tivermos b0 6= 0, então: (i) desloque o registro de a de uma posição à direita; (ii) calcule o valor g → g + 1, e tome o registro a→ 0 ... b1 b2 · · · bt ... bt+1 · · · 28 cálculo numérico 5. Se b1 = 0, então devemos normalizar. (i) desloque à esquerda, até que obtenha b1 6= 0. (ii) calcule g = g − 1 para cada posição deslocada. Teremos: a→ 0 b1 b2 · · · bt bt+1 · · · 6. Se g > S, temos over�ow, e se g < I, temos under�ow. 7. Para arredondamento, cancele os valores de registro de a que estão além da precisão t da máquina. O resultado da operação é dado por: a = x+ y = 0, b1b2 · · · bt × βg. Exemplo 1.10 Sejam x = 0, 1547 × 105 e y = 0, 2748 × 10−1 dois números em decimal com precisão t = 4. Vemos que g = e − f = 5 − (−1) = 6. Então, a = x + y = x = 0, 1547× 105. Na notação de registros, vemos que: x → 1 5 4 7 0 · · · 0 y → 2 7 4 8 0 · · · 0 y′ → 0 0 0 0 0 0 2 7 4 8 a = x + y = x. Exemplo 1.11 Sejam x = 0, 9876×101 e y = 0, 8732×101. Assim, a = x+y = 1, 8608× 101 = 0, 18608× 102 = 0, 1860× 102. Exemplo 1.12 Sejam x = 0, 1012 × 101 e y = −0, 9876 × 10−1. Temos que a = x + y = 0, 1012× 101 − 0, 009876× 101 = 0, 091324× 101 = 0, 91324× 100 = 0, 9132× 100. Multiplicação Sejam dois números x e y em ponto �utuante e seja p = x · y seu produto. A operação de multiplicação realiza-se por meio dos passos: 1. Dispor os números em seus registros x → d1 d2 · · · dt 0 0 · · · 0 y → l1 l2 · · · lt 0 0 · · · 0 erros computacionais 29 2. Calcule p = x · y com expoente g = e+ f . p→ b1 b2 · · · bt bt+1 · · · 3. Se b1 = 0, então normalize, fazendo g → g − 1. p→ b1 b2 · · · bt bt+1 · · · 4. Se g > S, temos over�ow ; se g < I, temos under�ow. 5. Cancele os valores de registro de p que estão além da precisão t. p→ b1 b2 · · · bt 0 · · · 0 Logo, o produto é dado por p = 0, b1b2 · · · bt × βg. Exemplo 1.13 Sejam os números x = 0, 1432 × 101 e y = 0, 4330 × 102. O produto é dado por p = x ·y = 0, 0620056× 103 = 0, 620056× 102 = 0, 6200× 102. Divisão A operação de divisão de dois números em ponto �utuante realiza-se por meio das seguintes etapas. Dados x e y, obtenha o valor q = x y . 1. O primeiro passo é carregar os números em seus registros x → d1 d2 · · · dt 0 0 · · · 0 y → l1 l2 · · · lt 0 0 · · · 0 Se tivermos y = 0, então �m. Senão, 2. Calcule o valor g = e− f e veri�que o registro, q → b0 b1 b2 · · · bt bt+1 · · · 0 3. Se tivermos b0 6= 0, então devemos ajustar q levando em consideração que g → g + 1. 30 cálculo numérico q → 0 ... b1 b2 · · · bt bt+1 · · · 4. Se b1 = 0, então normalize, tomando g → g − 1. q → 0 ... b1 b2 · · · bt bt+1 · · · 5. Se g > S, temos over�ow, e se g < I, temos under�ow. 6. Cancele os valores de q além da precisão t da máquina. Assim, a divisão é dada por: q = x y = 0, b1b2 · · · bt × βg. Exemplo 1.14 Sejam os números x = 0, 5649× 101 e y = 0, 1357× 102. Então, a divisão é dada por: q = x y = 4, 162859× 10−1 = 0, 4162859× 100 = 0, 4162× 100. 1.2.4 Distributividadee associatividade Em sistemas de ponto �utuante, as propriedades de Adição, Subtração, Multi- plicação e Divisão não obedecem necessariamente às mesmas regras da aritmética sobre o conjunto dos números reais <. Para ilustrarmos, vejamos o Exemplo 1.15. Exemplo 1.15 Tomemos x1 = 0, 3491×104 e x2 = 0, 2345×100. Seja a precisão da máquina dada por t = 4. Assim, a1 = (x2 + x1)− x1 = (0, 2345× 100 + 0, 3491× 104)− 0, 3491× 104 = 0, 0000 Agora, tomando-se a2 = x2 + (x1 − x1) = 0, 2345× 100 + (0, 3491× 104 − 0, 3491× 104) = 0, 2345× 100 Vemos, portanto, que a1 6= a2, o que é um absurdo! erros computacionais 31 1.2.5 Precisão e exatidão de máquina Os conceitos de precisão e exatidão são distintos um do outro. A precisão de uma máquina informa sobre o número de dígitos signi�cativos da máquina, sendo este �xo para uma máquina. A exatidão, ao contrário, de�ne a perfeição do resultado, que depende de diversos fatores, entre eles a precisão, a base do sistema de numeração, o compilador etc. Vimos que todas as máquinas operam com um sistema de ponto �utuante F (β, t, I, S), onde t é a precisão da máquina para a base β. É comum desejarmos conhecer qual a precisão de uma máquina com relação ao sistema decimal. Se chamarmos de precisão p o valor da precisão em decimal, temos a seguinte relação, βt = 10p ⇒ p = t ln β ln 10 . (1.8) De�nição 1.7 A exatidão de uma máquina é medida por ε, que é o menor nú- mero em ponto �utuante, tal que temos 1 + ε > 1. Este valor é conhecido como ε de máquina. Exercício 1.7 Escreva um programa simples para determinar o ε de máquina. Note que, nos sistemas de computação algébrica é possível de�nir várias precisões t. Exercício 1.8 Considerando os sistemas de ponto �utuante padrão IEEE F(2, 23,−126, 127), IBM 3090 F(16, 5,−65, 62) e do supercomputador CRAY XM-P F(2, 47,−16385, 8190), determine a precisão destes em decimal. 1.3 Tipos de erros Como vimos anteriormente, nas várias etapas da cadeia da pesquisa cientí- �ca, erros de diversos tipos podem ocorrer. Em geral, os tipos de erros estão classi�cados como: • Erros nos dados de entrada; • Erros gerados pelo modelo; • Erros por truncamento; • Erros por arredondamento. 32 cálculo numérico 1.3.1 Erros de dados A coleta de dados decorrentes de medidas das observações e experimentos, na maioria das vezes, traz consigo erros que são inerentes aos próprios instrumentos de medida. Dependendo do tipo de aparelho utilizado para a coleta de dados, obtemos um melhor ou um pior conjunto de valores observáveis. Neste livro, não vamos tratar especi�camente de erros dessa natureza, por não fazerem parte de nosso objetivo de estudo. 1.3.2 Erros do modelo A fase de modelagem é extremamente importante para a correta descrição de um fenômeno físico. Já vimos, anteriormente, como um modelo pobre pode levar a erros e, por conseguinte, a resultados que estejam longe do observável. Muitos modelos são descartados tendo em vista que os seus resultados não são consistentes com a observação do fenômeno. Como estamos mais interessados na etapa de resolução dos problemas, não vamos discutir aqui os erros devido à modelagem do problema físico, embora a etapa de modelagem seja uma das mais importantes para a solução de um problema físico. 1.3.3 Erros por truncamento Em muitas ocasiões, no tratamento de um problema, é preciso fazermos a substituição de uma expressão ou fórmula in�nita por uma �nita. Nesse caso, a diferença entre a solução encontrada pela substituição da solução exata pela fórmula �nita gera um erro que se chama erro de truncamento. Um exemplo típico é a aproximação de uma função por sua série de Taylor. Seja f(x) uma função de�nida em um certo intervalo, então sua expansão em série de Taylor, na vizinhança de um ponto x = x0, é dada por: f(x) = f(x0) + (x− x0)f ′(x0) + (x− x0) 2 2! f ′′(x0) + (x− x0)3 3! f ′′′(x0) + · · · (1.9) Exemplo 1.16 Seja a função f(x) = sen x. A expansão da função em torno do ponto x = 0, até ordem 5, é dada por p5(x) = x− x3/3 + x5/120. Se considerarmos a aproximação sen x ≈ p5(x), temos que o erro de trun- camento é dado por: ET =| sen x − p5(x) |. Tomando o valor de x = pi/4 na expressão do erro de truncamento, temos erros computacionais 33 ET (pi/4) = sen (pi/4)− p5(pi/4) ' −3, 626459× 10−5. Em geral, deseja-se saber o erro dentro de certa tolerância, ET = |sen x− p(x)| ≤ �, (1.10) onde � é a tolerância desejada. Em geral, a tolerância é estabelecida de acordo com a acurácia desejada para a solução do problema em estudo. Exercício 1.9 Determine a expansão em série de Taylor, até ordem 5, para as funções a seguir. Em todos os casos, veri�que o erro de truncamento, conside- rando alguns valores de x para as funções. f(x) = ex, em torno de x = 0, g(x) = cos x, em torno de x = 0, h(x) = ln x, em torno de x = 1. 1.3.4 Erros por arredondamento Vimos que a conversão de um número, escrito em um sistema de numeração, para outro sistema de numeração pode causar erros, uma vez que considerando um sistema de ponto �utuante, não podemos representar o número com precisão in�nita. Em um sistema de ponto �utuante, os números são representados de forma discreta e com uma precisão limitada, 1 o que causa erros devido a arredon- damentos, como veremos a seguir. Para melhor ilustrar a noção de erro por arredondamento, vejamos o seguinte caso. Suponha que temos a soma das frações 1 3 + 1 3 + 1 3 (1.11) A solução exata dessa operação é 1. Suponha, agora, que estejamos traba- lhando com uma máquina cuja precisão é t = 4. Considere a soma usando a aproximação decimal para cada termo da equação (1.11), ou seja: 0, 3333 + 0, 3333 + 0, 3333 = 0, 9999 (1.12) Vemos, então, que o resultado da soma em (1.12) é diferente do resultado da soma em (1.11). Em ponto �utuante teríamos o erro, 1 Nos sistemas de computação algébrica, a precisão pode ser de�nida pelo usuário, tendo como limite apenas a capacidade de hardware da máquina. Por isso, esses sistemas são conhecidos como sistemas com precisão arbitrária. 34 cálculo numérico E = 0, 1× 10− 0, 09999× 10 = 0, 00001× 10 = 10−5. Por outro lado, como a precisão do sistema é t = 4, se cancelarmos o 1 que está além da precisão, o resultado é E = 0, 0000 × 10 = 0, já que não podemos representar mais que 4 casas decimais. Neste caso, a diferença entre o valor exato e o valor representando em ponto �utuante é nula, muito embora tenhamos desprezado uma contribuição da ordem de 10−5. Considere agora 2 3 + 2 3 + 2 3 = 2, (1.13) Em uma máquina com precisão t = 4, temos: 0, 6666 + 0, 6666 + 0, 6666 = 0, 19998× 10 (1.14) Como o sistema não pode representar além de 4 dígitos signi�cativos, o resultado de (1.14), cancelando o 8, é 0, 1999× 10. Neste caso, vemos que a diferença entre o valor exato e o valor em ponto �utuante não é nulo, pois E = 0, 2 × 10 − 0, 1999× 10 = 0, 0001× 10 = 0, 1× 10−2. Os arredondamentos podem ser de dois tipos: 1. Arredondamento do tipo Corte, também chamado de cancelamento. Nesse caso, os dígitos além da precisão t do sistema de ponto �utuante são auto- maticamente abandonados (desprezados); 2. Arredondamento para o número mais próximo de máquina. Suponha que a precisão de uma máquina é t. Então, analisamos o algarismo de ordem t+ 1: i) Se esse algarismo for maior ou igual a 5, somaremos uma unidade ao algarismo de ordem t; ou seja, dt → dt = dt + 1, ii) Se o algarismo de ordem t + 1 for menor que 5, então o algarismo de ordem t permanecerá inalterado, ou seja, dt → dt. Suponha, agora, que consideremos um arredondamento para número mais próximo de máquina no caso da soma dada em (1.14). Temos a soma (1.14) dada por 0, 2×10, e como consequência, não teríamos erro causado por arredondamentoneste caso. Exemplo 1.17 Se x = 1 3 = 0, 3333333, então x = 0, 3333 × 100 para uma má- quina com precisão t = 4, com arredondamento do tipo corte. Se x = 0, 666666.... Então, com t = 5, temos que x = 0, 66667 × 100, com arredondamento do tipo para número mais próximo de máquina. erros computacionais 35 Se x = −0, 0004235437, com t = 4, temos então que x = −0, 4235 × 10−3, cujo valor do último algarismo permaneceu inalterado. De uma forma geral, se x é um número real, este pode ser escrito, em uma base β, da forma x = q × βe = 0, d1 . . . , dt × βe, com 0 ≤ di < β, i = 1, . . . , t. (1.15) Se x = q × βe, onde q é o valor de q arredondado para o dígito t + 1, temos que: |q − q| ≤ 1 2 β−t, (1.16) e o limite do erro entre os valores é dado por: |x− x| ≤ 1 2 βe−t. (1.17) 1.3.5 Erros absoluto e relativo Sejam os valores x exato e x aproximado para uma grandeza. De�nição 1.8 De�nimos o erro absoluto de uma grande x como: EA = |x− x|. (1.18) O erro relativo é de�nido como: De�nição 1.9 O erro relativo de uma grandeza x é dado por: ER = EA |x| = |x− x| |x| . (1.19) Das expressões (1.17) e (1.19) podemos determinar o limite do erro relativo, pois temos que: ER = |x− x| |x| ≤ 1 2 βe−t |q|βe = β−t 2|q| . (1.20) Aplicando a condição de normalização 0, 1 ≤ |q| < 1, obtemos ER = |x− x| |x| ≤ 1 2 β1−t. (1.21) 36 cálculo numérico De�nição 1.10 De�nimos a unidade de arredondamento de um número em ponto �utuante como sendo a quantidade µ = 1 2 β1−t. (1.22) É importante chamar a atenção para o fato de que a unidade de arredonda- mento é um valor independente da magnitude do número que está sendo apro- ximado. A acurácia do resultado de uma grandeza pode ser estimada por seus erros absoluto e relativo. Exemplo 1.18 Sejam os valores x = 0, 000008 e x = 0, 000006. Então, os erros são dados por: EA = |x− x| = |0, 8× 10−5 − 0, 6× 10−5| = 0, 2× 10−5 ER = EA |x| = 0, 2× 10−5 0, 8× 10−5 = 0, 25 O erro absoluto é muito baixo, mas o erro relativo é de 25%. Exemplo 1.19 Sejam x = 0, 435795× 10−3 e x = 0, 435210× 10−3. Então ER = |x− x| |x| = 5, 85× 10−7 0, 435795× 10−3 = 0, 134237× 10 −2, ER < 0, 5× 10−2 =⇒ t = 3. Logo, a aproximação x possui três dígitos signi�cativos exatos; a saber, o 4, o 3 e o 5. Veja agora que, se aplicarmos o logaritmo na base 10 da expressão (1.21), com β = 10, temos: m ≤ log10 ( 1 2 ) − log10 ( |x− x| |x| ) . (1.23) O maior valor de m na expressão (1.23) representa o número de algarísmos signi�cativos com que o valor x se aproxima do valor x. De forma mais geral, escrevemos o valor de m como: erros computacionais 37 m = − [ 0, 3 + log10 ( µ+ |x− x| |x| )] , (1.24) onde o termo µ representa a unidade de arredondamento de máquina. Quando o arredondamento for para o número mais próximo de máquina, temos que µ = 1 2 × 101−t. (1.25) Na prática, não sabemos o valor exato da grandeza x. Assim, o que fazemos, ao tomar duas medidas consecutivas de x é calcular a grandeza D(xi, xi+1) = − [ 0, 3 + log10 ( µ+ |xi+1 − xi| |xi| )] , (1.26) que nos dá o número de dígitos signi�cativos exatos de xi+1 com relação ao valor xi. 1.4 Propagação de erros Vejamos agora como ocorre a propagação de erros causados nas operações aritméticas com ponto �utuante. 1.4.1 Adição Sejam x e y os valores aproximados de duas grandezas x e y, respectivamente. Sejam Ex e Ey os erros em x e y. Temos então que: S = x+ y, (1.27) S = x+ y, (1.28) Es = S − S = (x+ y)− (x− y) = (x− x) + (y − y). (1.29) Logo, temos que: |Ex+y| ≤ |Ex|+ |Ey|. (1.30) Isto é, o valor absoluto da soma dos erros absolutos é menor que a soma individual do valor absoluto dos erros. 38 cálculo numérico Exercício 1.10 Mostre que, para o erro relativo, a operação de adição resulta em: ER(x + y) = max{(ER(x),ER(y)}, (1.31) para x, y valores com o mesmo sinal. 1.4.2 Subtração O procedimento para subtração é similar ao da adição; temos que: Ex−y = Ex − Ey =⇒ (1.32) |Ex−y| ≤ |Ex|+ |Ey|. (1.33) Exercício 1.11 Mostre que, para o erro relativo, a operação de subtração resulta em: ER(x− y) = ER(x) + ER(y)|x− y| , (1.34) para quaisquer valores de x, y. 1.4.3 Multiplicação Seguindo a mesma construção anterior, vemos que: Ex?y ' xEy + y Ex =⇒ (1.35) |Ex?y| ≤ |x| |Ey|+ |y| |Ex|. (1.36) Exercício 1.12 Mostre que, para o erro relativo, a operação de multiplicação resulta em: ER(x · y) ≈ ER(x) + ER(y), para quaisquer valores de x, y. erros computacionais 39 1.4.4 Divisão Finalmente, seguindo o mesmo procedimento, temos para a divisão: |Ex/y| ≤ |y| |Ex|+ |x| |Ey||y|2. (1.37) Observamos que, na divisão, se dividirmos um número em ponto �utuante por outro número muito pequeno, temos a propagação de um erro muito grande, já que o termo na expressão anterior está dividido pelo quadrado do valor da grandeza aproximada. Exercício 1.13 Mostre que para o erro relativo, a operação de divisão resulta em: ER(x/y) ≈ ER(x) + ER(y), para quaisquer valores de x, y, y 6= 0. Exemplo 1.20 Sejam x = 3, 2548, com |Ex| ≤ 0, 5 × 10−4 e y = 0, 0351, com |Ey| ≤ 0, 5× 10−4. Temos que: Ex/y ≤ 0, 1335 < 0, 5× 100. 1.4.5 Operação geral Se de�nirmos � como uma operação genérica qualquer e �∗ como uma pseu- do-operação, vemos que para: x = x+ Ex, y = y + Ey, x � y − x �∗ y = (x � y − x � y) + (x � y − x �∗ y). (1.38) Assim, observando a equação (1.38), podemos interpretar o primeiro termo do lado direito da equação como correspondendo a um erro introduzido pelos valores numéricos e o segundo termo como correspondendo a um erro introduzido pela máquina. Teorema 1.1 Seja a operação � qualquer uma das operações aritméticas +,−,×,÷. Então, 40 cálculo numérico ∣∣∣∣x� y − x� yx� y ∣∣∣∣ ≤ µ, (1.39) para x� y 6= 0, ou de forma equivalente, x� y = (x� y)(1 + ε), (1.40) para algum ε > 0 satisfazendo à condição |ε| < µ, com µ a unidade de arredon- damento. Uma das conseqüências do Teorema 1.1 é que o resultado da comparação entre dois valores reais, por meio de um teste Booleano de igualdade é, em geral, falso, pois há o erro devido ao ε da máquina. Portanto, um teste Booleano da forma x = y deve ser substituído pelo teste |x− y| < ε. 1.5 Complexidade computacional Ao longo deste livro apresentaremos várias técnicas numéricas para resolu- ção de problemas de diferentes naturezas. Em certas ocasiões veremos mais de uma técnica, as quais podem ser empregadas para a resolução do mesmo tipo de problema. Tais técnicas são convertidas, no formalismo computacional, em procedimentos que chamamos de algorítmos. Assim, podemos ter vários algorít- mos destinados à resolução de um mesmo tipo de problema. Na Ciência da Computação é comum de�nir-se o custo computacional de um algoritmo para a resolução de um problema. Em termos simples, o custo com- putacional de um algoritmo está relacionado a dois fatores: primeiro ao número de passos necessários resolver um problema, que se re�ete em um custo deno- minado temporal e, segundo, na quantidade de memória utilizada para resolver um problema, que é denominado custo espacial. Formalmente, o custo computa- cional re�ete a complexidade do algoritmo. A complexidade de um algoritmo é uma função do tamanho do problema a ser tratado. Mais adiante, na Seção 2.3, veremos que a complexidade dos algoritmos para determinar o valor numérico de um polinômio depende do grau, n, do polinômio, isto é, do tamanho do problema a ser resolvido. Em geral, no cálculo numérico estamos mais interessados na complexidade temporal, relacionando esta ao número de operações que devem ser executadas por um algoritmo para resolver um problema. A complexidade temporal pode ser vista de duas formas: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) +r ⇒ r = P (c). (2.5) Se r = 0, então a constante c é uma raiz da equação polinomial P (x) = 0. O método de Briot-Ru�ni é obtido fazendo, a0 + a1x+ · · ·+ anxn = (x− c) [bnxn−1 + bn−1xn−2 + · · ·+ b2x+ b1]+ r. Realizando a multiplicação do primeiro termo da direita, obtemos: bnx n + (bn−1 − cbn)xn−1 + · · ·+ (b1 − cb2)x− cb1. Igualando os coe�cientes da mesma potência, temos: an = bn, an−1 = bn−1 − cbn ⇒ bn−1 = an−1 + cbn, . . . . . . a0 = r − cb1 ⇒ r = a0 + cb1. As relações anteriores formam um algoritmo para determinação do valor nu- mérico de um polinômio. Esquematicamente, podemos reescrevê-las da forma: an an−1 an−2 · · · a1 a0 c cbn cbn−1 · · · cb2 cb1 bn bn−1 bn−2 · · · b1 r = b0 (2.6) No método de Briot-Ru�ni, o número de operações necessárias para obtermos o valor numérico de um polinômio é de n adições e n multiplicações. Assim, o número total de operações é #Op = 2n, portanto, o custo computacional do algoritmo de Briot-Ru�ni, para a resolução do valor numérico de um polinômio é da ordem de O(n). 48 cálculo numérico Exemplo 2.5 Seja P(x) = x3 − 7x2 + 16x − 10. Determine o valor de P(2). Usando o esquema para o cálculo, temos: 1 −7 16 10 2 2 −10 12 1 −5 6 2 = P(2) (2.7) Pelo algoritmo, temos: bn = an, n = 3⇒ b3 = a3 = 1, c× bn ⇒ 2× 1 = 2, bn−1 = c× bn + an−1 ⇒ b2 = 2 + (−7) = −5, c× bn−1 ⇒ 2× (−5) = −10, bn−2 = c× bn−1 + an−2 ⇒ b1 = 2× (−5) + 16 = 6. Exercício 2.1 Veri�que que, se �zermos o mesmo cálculo para x = 1(c = 1), teremos P(1) = 0, e portanto c = 1 é uma raiz do polinômio P(x). 2.3.2 Método de Horner O método de Horner é muito intuitivo. Seja um polinômio P (x) dado por: P (x) = anx n + an−1xn−1 + · · ·+ a1x+ a0. (2.8) Podemos evidenciar um termo x na expressão do polinômio P (x), de tal forma que �camos com: P (x) = (anx n−1 + an−1xn−2 + · · ·+ a2x+ a1)x+ a0. (2.9) Se evidenciarmos x sucessivamente (n− 1) vezes, teremos: P (x) = ((anx n−2 + an−1xn−3 + · · ·+ a2)x+ a1)x+ a0 (2.10) = ((· · · (anx+ an−1)x+ · · ·+ a2)x+ a1)x+ a0. (2.11) Vemos da expressão anterior que o valor numérico de um polinômio, deter- minado pelo método de Horner, necessita de um total de n operações de adição e n operações de multiplicação, totalizando o número de operações #Op = 2n. Vemos que o custo computacional do algoritmo de Horner é, também, da ordem O(n). resolução de equações algébricas e transcendentais 49 Exemplo 2.6 Seja P(x) = 3x4 − 6x3 − 2x2 + 5x − 8. Utilizando o método de Horner, temos: P(x) = 3x4 − 6x3 − 2x2 + 5x− 8 = (3x3 − 6x2 − 2x + 5)x− 8 = ((3x2 − 6x− 2)x + 5)x− 8 = (((3x− 6)x− 2)x + 5)x− 8. Assim, o valor de P(3) é determinado por: P(3) = (((3 · 3− 6) · 3− 2) · 3 + 5 · 3− 8 = 70. 2.4 Limites das raízes polinomiais Seja P (x) = 0 uma equação polinomial. Teorema 2.4 Sejam an, a0 6= 0 e k (0 ≤ k ≤ n− 1) o maior dos expoentes entre os termos com coe�cientes negativos do polinômio P(x). Então, para o limite superior das raízes positivas da equação P(x) = 0, podemos tomar o valor: L = 1 + n−k √ B an , (2.12) onde B é o máximo dos valores absolutos dos coe�cientes negativos do polinômio P(x). Do teorema acima, podemos concluir que, se chamarmos de λp a maior raiz positiva de P (x) = 0, então λp ≤ L. Corolário 2.2 Se os coe�cientes do polinômio P(x) forem não negativos, então P(x) = 0 não possui raízes positivas. A a�rmação do corolário é bastante simples de ser veri�cada, pois, se não há termos com coe�ciente negativo na equação, não é possível haver compensação entre termos, e por isso não haverá raízes positivas. Claramente, poderá haver raízes negativas, pois termos com expoentes ímpares podem gerar compensações no valor do polinômio, de tal forma que poderá existir raízes negativas. 50 cálculo numérico Exemplo 2.7 Seja P(x) = x4 − 5x3 − 7x2 + 29x + 30 = 0. O polinômio possui quatro raízes λi, i = 1, 2, 3, 4. Pelo teorema, temos k = 3, B = | − 7| = 7, L = 1 + 4−3 √ 7/1 = 1 + 7 = 8. Logo, as raízes positivas possuem um limite λi ≤ 8. De�nição 2.3 Sejam λ1, λ2, · · · , λn as raízes de Pn(x) = 0. O polinômio, em sua forma fatorada, é dado por: Pn(x) = an(x− λ1)(x− λ2) · · · (x− λn). (2.13) Os limites das raízes positivas e negativas de um polinômio Pn(x) podem ser estimados da forma: Seja Pn(x) = 0 em sua forma fatorada an(x − λ1)(x − λ2) · · · (x− λn) = 0. Se chamarmos a expressão anterior de Q1(x) = x nPn(1/x), (2.14) teremos: Q1(x) = anx n(1− xλ1)(1− xλ2) · · · (1− xλn) = 0. (2.15) As raízes de Q1(x) são os valores 1/λ1, 1/λ2, · · · , 1/λn. Seja 1/λp a maior das raízes positivas e L1 o limite superior das raízes positivas de Q1(x) = 0. Então, temos: 1 λp ≤ L1 ⇒ λp ≥ 1 L1 . (2.16) Assim, o valor 1/L1 é o limite inferior das raízes positivas de Pn(x) = 0. De modo análogo, fazendo Q2(x) = Pn(−x) = 0, temos: an(x− λ1)(x− λ2) · · · (x− λn) = 0, an(−x− λ1)(−x− λ2) · · · (−x− λn) = 0, an(x+ λ1)(x+ λ2) · · · (x+ λn) = 0. (2.17) Logo, as raízes de P2(x) = 0 são −λ1,−λ2, · · · ,−λn. Assim, se −λq (λq < 0) é a maior das raízes positivas e L2 é o limite superior das raízes positivas de Q2(x) = 0, temos: resolução de equações algébricas e transcendentais 51 −λq ≤ L2 ⇒ λq ≥ −L2. (2.18) Portanto, −L2 é o limite inferior das raízes negativas de Pn(x) = 0. Considerando agora a construção Q3(x) = x nPn(−1/x) = 0, obtemos anx n(−1 x − λ1)(−1 x − λ2) · · · (−1 x − λn) = 0. (2.19) As raízes desta equação são −1 λ1 , −1 λ2 , · · · , −1 λn . Assim, considerando −1 λq (λq < 0) a maior raiz positiva de Q3(x) e L3 o limite superior das raízes de P3(x) = 0, temos: − 1 λq ≤ L3 ⇒ λq ≤ − 1 L3 . (2.20) Logo, o valor −1/L3 é o limite superior das raízes negativas de Pn(x) = 0. Podemos �nalmente concluir que: • Todas as raízes positivas, λp, de Pn(x) = 0, se existirem, deverão satisfazer à relação: 1 L1 ≤ λp ≤ L; (2.21) • Todas as raízes negativas, λn, de Pn(x) = 0, se existirem, deverão satisfazer à relação: −L2 ≤ λn ≤ − 1 L3 . (2.22) Exemplo 2.8 Seja P4(x) = x 4 − 5x3 + 6x2 + 4x + 8 = 0. Temos n = 4, k = 3,B = | − 5|. Podemos veri�car que o limite superior das raízes positivas é dado por L ' 3, 828427. Exercício 2.2 Sejam as equações polinomiais, P2(x) = x 2 + x− 1 = 0, P3(x) = x 3 − 7x2 + 16x− 10 = 0, P4(x) = x 5 + x4 − 9x3 − x2 + 20x− 12 = 0, P6(x) = 2x 6 − 3x5 − 2x3 + x2 − x+ 1 = 0. Usando uma calculador ou computador, determine os limites das raízes para esses polinômios, desenhe os seus grá�cos e estime os valores das suas raízes. 52 cálculo numérico Figura 2.2: Ilustração do Teorema de Bolzano, f(1) · f(6) > 0 ⇒ número par de raízes. 2.5 Número de raízes reais Na seção anterior vimos um método para identi�car os intervalos onde se en- contram as raízes de um polinômio. Vejamos agora alguns resultados que indicam o número de raízes de um polinômio em um certo intervalo. Teorema 2.5 (Teorema de Bolzano) Seja P(x) = 0 uma equação algébrica com coe�cientes reais e x ∈ [a, b]. Assim, i) se P(a) · P(b) < 0, então existe um número impar de raízes reais (contando suas multiplicidades) no intervalo [a, b]; ii) se P(a) · P(b) > 0, então existe um número par de raízes reais (contando as multiplicidades), ou não existem raízes reais no intervalo [a, b]. A Figura 2.2 ilustra o teorema de Bolzano. 2.6 Regra de sinais de Descartes A regra de sinais de Descartes permite identi�car o número de raízes reais positivas e negativas de uma equação algébrica polinomial. Para isso, seja λ(+) o número de raízes reais positivas de uma equação P (x) = 0. Regra de Descartes O número de raízes reais positivas de uma equação po- liniomial é igual a variação de sinais na seqüência dos coe�cientes do polinômio, ou menor que este por um número inteiro par, sendo uma raiz de multiplicidade m contada como
Compartilhar