Cálculo Numérico

Cálculo Numérico

(Parte 1 de 3)

Edson Luiz França Senne elfsenne@feg.unesp.br

DEPARTAMENTO DE MATEMÁTICA Universidade Estadual Paulista - Unesp

Campus de Guaratinguetá Faculdade de Engenharia

Apresentação Referências Bibliográficas

1.1 - Números de Ponto Flutuante1
1.2 - Sistemas de Ponto Flutuante2
1.3 - Aritmética de Ponto Flutuante5
1.4 - Dígitos Significativos Exatos7
1.5 - Mal-Condicionamento e Instabilidade Numérica9
Exercícios Resolvidos1
Exercícios Propostos13
Exercícios de Programação14

1. Aritmética Computacional

2.1 - Introdução17
2.2 - Estimativa de Raízes de Equações Polinomiais18
Enumeração das Raízes19
Localização das Raízes Reais21
Localização das Raízes Complexas2
2.3 - Separação das Raízes23
2.4 - Métodos Iterativos de Solução de Equações25
Ordem de Convergência de um Método Iterativo26
Métodos de Quebra26
Métodos de Ponto Fixo29
Método de Aitken31
Método de Newton-Raphson32
Método das Secantes (ou das Cordas)35
Método de Müller36
2.5 - Resolução de Sistemas de Equações Não-Lineares37
Exercícios Resolvidos40
Exercícios Propostos43
Exercícios de Programação4

2. Solução de Equações

3.1 - Introdução45
Matrizes Especiais46
3.2 - Métodos Diretos47
Método da Eliminação de Gauss48
Determinação de Inversa de Matriz53
Método de Gauss-Jordan54
Refinamento Iterativo da Solução56
Método de Gauss-Jacobi61
Método de Gauss-Seidel61
Estudo da Convergência dos Métodos Iterativos64
3.4 - Métodos de Fatoração67
Exercícios Resolvidos74
Exercícios Propostos78
Exercícios de Programação80
4.1 - Introdução81
4.2 - Interpolação Polinomial82
4.3 - Polinômios de Lagrange87
4.4 - O Erro na Interpolação89
4.5 - Diferenças Divididas89
4.6 - Diferenças Simples92
4.7 - Interpolação de Hermite93
4.8 - Interpolação por "Spline"97
Exercícios Resolvidos102
Exercícios Propostos104
Exercícios de Programação105

4. Interpolação

5.1 - Introdução107
5.2 - Método dos Quadrados Mínimos107
5.3 - Aproximação de Funções Contínuas112
5.4 - Polinômios Ortogonais117
5.5 - Método dos Quadrados Mínimos Generalizado124
Exercícios Resolvidos130
Exercícios Propostos131
Exercícios de Programação132

5. Aproximação de Funções

6.1 - Introdução135
6.2 - Métodos de Newton-Cotes137
Regra dos Retângulos137
Regra dos Trapézios139
Regra de Simpson140
Fórmula Geral das Quadraturas Newtonianas142
6.3 - Métodos de Extrapolação146
6.4 - Quadratura de Gauss149
6.5 - Quadraturas Adaptativas153
Exercícios Resolvidos158
Exercícios Propostos160
7.1 - Introdução165
7.2 - Método de Euler167
7.3 - Métodos Baseados na Série de Taylor169
7.4 - Métodos Baseados em Regras de Quadratura171
7.5 - Métodos de Runge-Kutta173
7.6 - Métodos de Passo Múltiplo178
Métodos Explícitos de Passo Múltiplo179
Métodos Implícitos de Passo Múltiplo180
7.7 - Métodos de Previsão e Correção181
7.8 - Método das Diferenças Finitas182
Exercícios Resolvidos185
Exercícios Propostos187

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.

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: xmbe=., onde:

a) b = 10x = 721.5438

Existem várias formas não normalizadas para representar x como um valor de ponto flutuante. Por exemplo:

b) b = 2x = 1101.01

Neste caso x corresponde ao valor decimal:

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

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 Decimal

-2 + 231- = -2 + 4 = 2ou seja: 010

Observe que neste caso:

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:

• n - número de dígitos para a representação do expoente (incluindo o sinal)

Cálculo Numérico 1 – Aritmética Computacional

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:

• 2 vezes corresponde a positivo e negativo; • (b-1) são os dígitos possíveis na primeira posição da mantissa;

Seja, por exemplo, F(2,3,2).

Logo, as mantissas possíveis são: 0.100, 0.101, 0.110, 0.1 e os expoentes representáveis são: -2, -1, 0, 1. Neste caso, os números positivos representáveis são:

e assim por diante, até:

A tabela a seguir resume os números positivos representáveis neste sistema de ponto flutuante:

Esquematicamente:

Cálculo Numérico 1 – Aritmética Computacional região de overflow

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:

Portanto, pode-se definir a densidade de números representáveis entre potências sucessivas da base como:

,com k = ..., -1, 0, 1, ...

Para o exemplo acima tem-se: k densidade

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: ExxA=-*, onde: x é o valor verdadeiro e x* é o valor aproximado.

x x E x

Cálculo Numérico 1 – Aritmética Computacional

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:

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/4y = 3/8
b) x = 5/8y = 3/8 z = 3/4

(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

valor aproximação erro de arredondamento

9/8 = 1.125 1 = 1.0

5/4 = 1.25 1.0 - 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)

(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

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:

Cálculo Numérico 1 – Aritmética Computacional

(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

Logo: r a a a r a a r a a r erro relativo da soma ºŒ ø ßœ1 ou seja: o erro relativo da subtração é igual ao produto de um fator = a a

> 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 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 £ +

d) DIVISÃO

r r1 r

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 a) 0.00000014 Þ forma normalizada = 0.14 x 106- Þ 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:

a) v = 2/3a = 0.6667
b) v = 2/3a = 0.66998

Logo: a = 0.6667 tem os 4 dígitos significativos exatos.

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 i i ou seja:

log log( . )

log( . ) log x x x m m x x i i i

Cálculo Numérico 1 – Aritmética Computacional

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 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, 2.9, 32.9, 31.1, a solução do sistema irá se alterar para:

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 n n

é dado por:

I n

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

I n In n n 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:

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:

a e a a

a ae a a 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

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

VRH=p2 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 Þ ER = 0.05 H = 1.2 – EH

VRH=p()2 ÞEERHEVRH
£+p2()Mas como Ep=0, EEVRH
Logo: EREHREVHR£+p(())2Portanto, se p(()).REHREHR205+= então

Assim, deve-se ter:

05 2 31416 10 12 2 10 0052 2. ( ( )) . (( . ) ( . )())= + = · + · ·p R E H RE EH R H . Portanto:

2. Pelo teorema de Taylor pode-se escrever:

f b f a b a f a b a f a b a f a b a

( )

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:

Cálculo Numérico 1 – Aritmética Computacional

1000 1000 0500 0167 0 042 2 709

Os erros cometidos no processo são:

• 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:

Portanto, como o erro relativo é menor do que

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:

Portanto, podem ser representados neste sistema:

(zero) + (27 números positivos) + (27 números negativos) = 5 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

0 1

Para as operações tem-se:

+ = + = Þ + =

b)

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? 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 =

(Parte 1 de 3)

Comentários