Algoritmos Numéricos - Métodos Computacionais

Prévia do material em texto

Josué Abranti
Métodos computacionais
Algoritmos Numéricos
Brasil
Porto Alegre 12 de Abril de 2020
Josué Abranti
Métodos computacionais
Algoritmos Numéricos
Trabalho acadêmico apresentado à disci-
plina de Métodos Computacionais da insti-
tuição Pontíficia Universidade Católica do
Rio Grande do Sul como parte dos requisi-
tos necessários para obtenção do título de
Engenheiro de Computação.
Pontifícia Universidade Católica do Rio Grande do Sul - PUCRS
Escola Politécnica
Engenharia de Computação
Brasil
Porto Alegre 12 de Abril de 2020
Josué Abranti
Métodos computacionais
Algoritmos Numéricos/ Josué Abranti. – Brasil, Porto Alegre 12 de Abril de 2020-
Pontifícia Universidade Católica do Rio Grande do Sul - PUCRS
Escola Politécnica
Engenharia de Computação, Porto Alegre 12 de Abril de 2020.
1. Métodos Computacionais. 2. Computação Científica. I. Beatriz Franciosi. II.
Pontifícia Universidade Católica do Rio Grande do Sul.
“ A Matemática apresenta invenções tão sutis
que poderão servir não só para satisfazer os curiosos como,
também para auxiliar as artes e poupar trabalho aos homens ”
(René Descartes, Século 17)
Lista de ilustrações
Sumário
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1 ALGORITMOS NUMÉRICOS . . . . . . . . . . . . . . . . . . . . . 9
2 QUALIDADE DOS ALGORITMOS NUMÉRICOS . . . . . . . . . . 11
2.1 Inexistência de erro lógico . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Inexistência de erro operacional (overflow/underflow) . . . . . . . . 11
2.3 Quantidade finita de cálculos (critério de parada) . . . . . . . . . . . 11
2.4 Existência de um critério de exatidão . . . . . . . . . . . . . . . . . . 12
2.5 Independência da máquina . . . . . . . . . . . . . . . . . . . . . . . . 12
2.6 Com precisão infinita, os limites do erro devem convergir a zero
(convergência numérica) . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.7 Eficiência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 PASSOS PARA A RESOLUÇÃO DE UM PROBLEMA . . . . . . . 15
Introdução
O campo da análise numérica antecede a invenção do computador em séculos.
Interpolação linear é usada há mais de 2000 anos. Grandes matemáticos no passado
trabalharam com análise numérica, o que é obviamente percebido pelo nome de importantes
algoritmos como: Método de Newton, Polinômio de Lagrange, Eliminação Gaussiana, ou
Método de Euler.
Para facilitar os cálculos manuais, grandes livros foram produzidos, com fórmulas
e tabelas de dados como pontos de interpolação e coeficientes de funções. Utilizando estas
tabelas, freqüentemente calculadas até a 16a casa decimal ou além, qualquer um poderia
olhar os valores e inseri-los nas fórmulas e encontrar estimações numéricas aproximadas
para algumas funções. Este trabalho culminou em uma publicação do NIST em 1964,
de um livro de mais de 1000 páginas editado por Abramowitz e Stegun com um grande
número de formulas e funções comumente utilizadas e seus valores em diversos pontos. Os
valores das funções não são mais de grande utilidade quando temos um computador à
disposição, mas as diversas fórmulas podem ainda ser bastante úteis.
As calculadoras mecânicas também foram desenvolvidas como uma ferramenta para
cálculos a mão. Estas calculadoras evoluíram para computadores eletrônicos nos anos 40,
quando então se percebeu que estes computadores seriam úteis para fins administrativos.
Mas a invenção do computador também influenciou campo da análise numérica, uma vez
que cálculos maiores e mais complexos poderiam ser resolvidos.
9
1 Algoritmos numéricos
Os algoritmos são cada vez mais utilizados no nosso dia-a-dia, principalmente por
profissionais que trabalham com desenvolvimento de softwares, sites, games, etc. Sua
compreensão nem sempre é fácil, mas, entendendo seu princípio, fica mais fácil resolver
exercícios e problemas que parecem difíceis.
Os algoritmos numéricos podem ser definidos como, algoritmos voltados ao pro-
cessamento numérico, isto é, as operações aritméticas formam o cerne do algoritmo e
seu objetivo é obter um ou mais resultados numéricos. Um algoritmo numérico de boa
qualidade tem as seguintes características:
Sua principal utilização consiste na modelagem de problemas reais em forma
matemática de maneira coesa e otimizada para um menor custo computacional. Para criação
destes algoritmos faz-se necessário a utilização de modelagem computacional, afim de trazer
a transcrição do mundo real a linguagem matemática utilizada computacionalmente.
11
2 Qualidade dos Algoritmos numéricos
Um algoritmo numérico de boa qualidade deve possuir as seguintes características:
2.1 Inexistência de erro lógico
Previsão completa de todas as tendências do processo, levando em conta as caracte-
rísticas das operações aritméticas e dos modelos matemáticos. O algoritmo deve identificar
todas as etapas do modelo.
2.2 Inexistência de erro operacional (overflow/underflow)
O algoritmo pode falhar por violar restrições físicas da máquina, e então os erros
são detectados em tempo de execução. y =>
|y| < limite inferior (underflow)|y| > imite superior (overflow)
Exemplo:
Seja z = x + iy ∈ C; x e y ∈ R. Queremos calcular |z| =
√
x2 + y2.
Se num algoritmo implementarmos diretamente |z| =
√
x2 + y2, dependendo dos
valores de x e y podemos ter overflow em x2 ou y2, embora valha
√
x2 + y2 < limite
superior. Então devemos fazer:
|z| =
√
x2 + y2 =
√
x2
(
1 + y2
x2
)
= |x|
√
1 +
(
y
x
)2
, ∀ |x| > |y|
E assim,
|z| = |x|
√
1 +
(
y
x
)2
, ∀ |x| > |y|
2.3 Quantidade finita de cálculos (critério de parada)
Como muitos problemas numéricos são resolvidos por métodos iterativos (um
método é dito iterativo quando o mesmo procedimento é repetido diversas vezes gerando
uma sequencia de aproximações da solução procurada.), é necessário estabelecer um critério
de parada, para que o algoritmo possa terminar após um número finito de operações.
Ainda é aconselhável estabelecer um número máximo de iterações a serem executadas pelo
algoritmo.
12 Capítulo 2. Qualidade dos Algoritmos numéricos
2.4 Existência de um critério de exatidão
Em virtude das limitações de precisão e exatidão da máquina e do método, todo
resultado obtido do computador deverá enquadrar-se em um critério de exatidão fornecido
de antemão.
resultado = valor aproximado ± limite do erro (precisão)
2.5 Independência da máquina
Nos algoritmos numéricos não deve haver dados dependentes da máquina. O
problema gerado pelo algoritmo deve ser executado em diferentes máquinas, visando à
máxima portabilidade.
Exemplo:
e = exp(1) e não e = 2.71828182
2.6 Com precisão infinita, os limites do erro devem convergir a zero
(convergência numérica)
Esta exigência estabelece a dependência entre a solução ideal em R e a solução
da máquina. Sem essa condição de convergência a solução da máquina não precisará
necessariamente estar relacionada com a solução verdadeira.
Exemplo: Dado a ∈ R, calcular x = sin(a)
Início
ler (a)
x ← 0± 1
imprimir (x)
Fim
Este algoritmo satisfaz todas as exigências vistas até o momento:
• Não há erro lógico nem operacional
• Os dados não dependem da máquina
• Resultado dentro dos limites de erro
Porém não há convergência numérica.
2.7. Eficiência 13
2.7 Eficiência
Encontrar a solução de um problema visando obter economia de recursos envolvidos
(tempo, exatidão, volume de dados de referência, dificuldades de representação, espaço de
memória).
As exigências (1) e (2) dizem respeito à eficácia.
Eficácia: qualidade de produzir uma resposta correta ao problema dado.
Eficiência: eficácia + economia.
15
3 Passos para a resolução de um problema
Dado um problema técnico, para chegarmos a um resultado numérico, faz-se
necessário percorrer uma seqüência preestabelecida de passos isolados. Em cada um desses
passos pode existir uma parcela de erro que se acumula ao montante final do processo.
Passos:
• Modelamento: O problema técnico precisa ser associado a um modelo matemático
paraser possível a interpretação e a conseqüente solução.
• Simplificação: Acontece, de modo freqüente, que o modelo usado para certa solução
numérica necessita de simplificações. A essa etapa também pertence a aproximação
de valores de contorno.
• Resultados de Ciências Vizinhas e Medição: Nas equações ocorrem coeficientes,
os quais foram obtidos de ciências vizinhas, como por exemplo, Termodinâmica,
Ecologia, Física, ou de medidas e, por isso, já providos de erros. Neste ponto, já
dispomos das equações a serem resolvidas pelas máquinas digitais.
• Escolha de Métodos: É preciso escolher o método numérico para obter a solução,
sempre levando em conta em que recurso vamos procurar maios eficiência.
• Escolha de Parâmetros: No método de solução devem ser escolhidos certos parâmetros
de cálculo, como, por exemplo, a escolha de um “passo” num método de diferenças,
ou a escolha do tamanho do subintervalo para um método para integração.
• Truncamento das Iterações: Como a maioria dos problemas não tem solução direta e
precisa, por isso, ser resolvida iterativamente, é necessário que se escolha um critério
de parada.
Todos esses passos causam erros no resultado final. Intuitivamente temos: se a
passagem da teoria para a aproximação induz a certo erro na solução, então uma iteração
com certa precisão pode não melhorar o erro e o tempo de cálculo é mero desperdício.
Portanto, se quisermos melhorar o tempo de cálculo de modo efetivo, devemos fazer uma
análise cuidadosa da nossa seqüência de erros. É, freqüentemente, difícil dizer algo sobre
os erros que ocorrem Modelamento e Simplificação. No caso de Simplificação pode-se fazer
uma análise a posteriori, isto é, substituir o resultado aproximado nas equações iniciais e
assim obter-se uma idéia sobre a grandeza do erro.
	Folha de rosto
	Epígrafe
	Lista de ilustrações
	Sumário
	Introdução
	Algoritmos numéricos
	Qualidade dos Algoritmos numéricos
	Inexistência de erro lógico
	Inexistência de erro operacional (overflow/underflow)
	Quantidade finita de cálculos (critério de parada)
	Existência de um critério de exatidão
	Independência da máquina
	Com precisão infinita, os limites do erro devem convergir a zero (convergência numérica)
	Eficiência
	Passos para a resolução de um problema