Métodos Computacionais II

Introdução a Métodos Computacionais

Antonio Mendes da Silva Filho

2007.2

Natureza e Objetivos da Matemática Numérica

Máquinas de contagem da IBM no início do Século XX Advento das máquinas computacionais nos anos 40

Aplicações em cálculos balísticos Logística de transporte

Importância dos métodos computacionais Propriedades da matemática real são perdidas em máquinas

computacionais Representação aproximada de números perda de precisão Erros, propagação e amplificação de erros

Matemática Computacional

Estudo da matemática do ponto de vista computacional

Divisões da Matemática Computacional A matemática computacional é a área da

matemática que se preocupa com o desenvolvimento, emprego e estudo de métodos numéricos, podendo ser subdivida em:

1. Matemática Numérica

2. Matemática Simbólica

3. Matemática Gráfica

4. Matemática Intervalar

* maior ênfase prática

Matemática Numérica

Parte da matemática computacional que se preocupa com o desenvolvimento de algoritmos para resolução aproximada de problemas representada por um modelo matemático.

Utiliza como sistema de operações o conjunto {+,., /, .} de operadores matemáticos

Matemática Simbólica

Busca a solução analítica de problemas matemáticos Por exemplo, a solução analítica da integral:

Matemática Gráfica

Trabalha com de forma gráfica (i.e. modelos gráficos) buscando representar a solução dos problemas também na forma gráfica.

Matemática Intervalar

Trata dados na forma de intervalos numéricos, buscando controlar os limites de erro dos processos da matemática numérica.

Foco de Atuação

Nosso foco recai sobre a matemática numérica

Estudamos processos numéricos para a

resolução de problemas (algoritmos) visando a

máxima economia e confiabilidade em termos de

fatores envolvidos, tais como:

1. tempo de execução

2. memória utilizada

3. erros de arredondamento

O que é Problema Computacional Consiste em computar o valor de uma função para uma

entrada que satisfaça as especificações. Ou seja, dada uma função f : A → B e uma entrada x que

pertence a A, computar y = f (x). Definir um problema computacional é especificar a

relação entre entrada e saída. Exemplo: x codifica um grafo direcionado G = (V , E), uma

função w : E → RR com os pesos dos arcos, e dois vértices s e t. f (x) é o caminho mais curto de s a t.

Necessidade de algoritmo para resolvê-lo

O que é um Algoritmo ?

Informalmente, um algoritmo é um procedimento computacional bem-definido que toma como entrada um valor (ou conjunto de valores) e produz como saída um valor (ou conjunto de valores) com a solução de um problema computacional.

Um algoritmo é uma seqüência de passos computacionais que transforma entrada em saída.

Podemos ver um algoritmo como uma ferramenta para resolver um problema computacional bem definido.

O que é um Algoritmo ?

Problema de Ordenação

Entrada Uma seqüência (a1, a2, . . . , an) de n números.

Saída Uma permutação (a1’, a2’, ..., an’) da seqüência de entrada tal que

a1’ ≤ a2’ ≤ ... ≤ an’

Dada uma seqüência de entrada (31, 41, 59, 26, 41, 58), um algoritmo de ordenação produz a saída (26, 31, 41, 41, 58, 59).

A entrada (31, 41, 59, 26, 41, 58) é dita instância do problema.

Em geral, uma instância consiste de todas as entradas satisfazendo quaisquer restrições impostas na especificação do problema, necessárias para computar a saída.

Problema de Ordenação (cont.)

Aplicações do problema de ordenação Operação de ordenação é fundamental em ciência da

computação. O melhor algoritmo para uma certa aplicação

depende: tamanho da entrada grau de ordenação da entrada

Corretude Um algoritmo é dito correto se, para toda a instância,

o algoritmo termina com a saída correta. Neste caso, dizemos que o algoritmo resolve o

problema.

Algoritmos Numéricos

Algoritmo numéricos são fundamentais ao

processamento numérico

Algoritmos numéricos são tão importantes ao

processamento numérico, quanto a solução numérica

de sistemas de equações lineares a não-lineares.

A seguir, características desejadas de algoritmos

numéricos são apresentadas

Características Desejáveis dos Algoritmos Numéricos

Inexistência de erro lógico

Inexistência de erro operacional

Quantidade finita de cálculos

Existência de um critério de exatidão

Independência de máquina

Precisão infinita

Eficiência

Inexistência de Erro Lógico

Um algoritmo não apresenta erro lógico se este sempre produz

o resultado correto. Considere o exemplo abaixo.

Problema: procura-se a solução x* de ax = b

Algoritmo ingênuo: x* = b/a

Algoritmo correto:Se a = 0, então se b = 0 imprima “identidade”Senão imprima “contradição”Caso contrário x* = b/a

Inexistência de Erro Operacional

O algoritmo pode falhar por violar restrições físicas da máquina.

Seja T o conjunto de números possíveis de serem

representados por uma máquina onde:

a) x T, - x T

b) t1 = inf{x : x T x > 0}

c) t2 = sup{x : x T x > 0}

Se temos valores y tais que |y| < t1 dizemos que ocorreu

“underflow”.

Se |y| > t2 dizemos que ocorreu “overflow”.

Quantidade Finita de Cálculos

Em algoritmos iterativos, é necessário que se

estabeleça um critério de parada e se prove

convergência.

Um algoritmo não pode executar indefinidamente e

quando ele pára se espera que este tenha produzido o

resultado esperado.

Existência de um Critério de Exatidão

É fundamental que o algoritmo possua um critério de

exatidão em função das limitações de precisão das

máquinas.

Deseja-se que o algoritmo forneça um resultado

aceitável da forma:

Resultado = Valor Aproximado + Erro

Independência de Máquina

É desejável que o algoritmo produza o mesmo resultado

quando executado em diferentes máquinas.

A constante de Euler e = 2.718281828 . . ., por exemplo,

terá representação distinta em diferentes máquinas.

Assim, não se deve utilizar o valor, mas sim a

representação e = exp(1) que corresponde ao valor

adotado pelo compilador.

Precisão Infinita

Com precisão infinita, os limites de erro devem convergir

para zero.

Esta exigência estabelece a dependência entre a

solução ideal em RR e a solução de máquina.

Considere o problema de determinar

sen(a) = x , dado a RR.

Precisão Infinita Algoritmo: calcula sen(a) = x

Entrada {a}x = 0 ± 1Saída {a, x}

Este algoritmo satisfaz as exigências: Não ter erro lógico Não tem erro operacional O algoritmo é finito Os dados não dependem da máquina Temos o resultado dentro dos limites de erro MAS, para satisfazer o critério de precisão infinita, deve haver

condição adequada de truncamento. Se satisfeita, haverá convergência numérica.

Eficiência

Quando se deseja encontrar a solução para um problema,

sempre visamos obter economia de rescursos envolvidos.

Um conjunto de fatores relevantes compreende:

1. tempo de execução

2. exatidão;

3. volume de dados

4. dificuldade de representação

5. eficácia.

Fazer contas com os dedos da mão, por exemplo, é eficaz

mas não é eficiente para cálculos aritméticos não triviais.

Eficiência Um exemplo compreende o algoritmo de Cramer para a solução

de sistemas de equações lineares: Ax = b, com A RRn×n.

Passos do algoritmo1) calcule o determinante Δ da matriz dos coeficientes;

2) calcule os n determinantes Δxj resultantes da substituição dacoluna j da matriz dos coeficientes pelo vetor b; e

3) a solução x = (x1, x2, . . . , xn) é dada por Δxj = Δxj/Δ , j = 1, . . . , n.

O algoritmo de Cramer acima executará (n + 1)!(n + 1) operações aritméticas

Já o algoritmo de Gauss termina após n3 operações.

Passos para Resolução de um Problema Criação do modelo matemático do problema

Necessidade de simplificação

Uso de valores já conhecidos

Parâmetros de equações similares

Escolha ou desenvolvimento do algoritmo

Definição de parâmetros do algoritmo

Como a maioria dos problemas não tem solução direta e

precisa, é comum fazer uso de métodos iterativos.

Exemplo 1: Falha no lançamento de mísseis(25/02/1991 – Guerra do Golfo – míssil Patriot)

Erro de 0,34 s no cálculo do tempo de lançamento

Limitação na representação numérica (24 bits)

Influência da Computação Numérica

Exemplo 2: Explosão de foguetes(04/06/1996 – Guiana Francesa – foguete Ariane 5)

Erro de trajetória 36,7 sapós o lançamento

Limitação na representação numérica (64 bits/ 16 bits)

Prejuízo: U$ 7,5 bilhões

Influência da Computação Numérica

Links

Desastres Causados por Erros de Computação Numérica

http://www.ima.umn.edu/~arnold/disasters/

Coletânea de Bugs de Software

http://wwwzenger.informatik.tu-muenchen.de/persons/huckle/bugse.html

Referências

Ruggiero, M. A. G., Lopes, V. L. R., Cálculo Numérico – Aspectos

Teóricos e Computacionais, Markron Books.

Cláudio, D. M. e Martins, J. M., Cálculo Numérico Computacional,

Ed. Atlas, 1987.

Barroso, L, Barroso, M.M.A., Campos Filho, F. F., Cálculo Numérico

com Aplicações, Ed. Harbra, 1987.