Introdução à Matemática Numérica

Prévia do material em texto

Introdução à Matemática Numérica
Introdução à Matemática Numérica
Eduardo Camponogara
Departamento de Automação e Sistemas
Universidade Federal de Santa Catarina
DAS-5103: Cálculo Numérico para Controle e Automação
1 / 35
Introdução à Matemática Numérica
Sumário
Natureza e Objetivos
Algoritmos
Algoritmos Numéricos
Resolução de Problemas
2 / 35
Introdução à Matemática Numérica
Natureza e Objetivos
Sumário
Natureza e Objetivos
Algoritmos
Algoritmos Numéricos
Resolução de Problemas
3 / 35
Introdução à Matemática Numérica
Natureza e Objetivos
Matemática Numérica
Natureza e Objetivos da Matemática Numérica
◮ Máquinas de contagem da IBM no ińıcio do Século XX
◮ Advento das máquinas computacionais nos anos 40
◮ Aplicações em cálculos baĺısticos
◮ Loǵıstica de transporte
◮ Técnicas de proteção contra submarinos
◮ Importância da matemática numérica
◮ 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
4 / 35
Introdução à Matemática Numérica
Natureza e Objetivos
Matemática Numérica
Subdivisões da Matemática Computacional
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 Computacional
2. Matemática Numérica
3. Matemática Simbólica
4. Matemática Gráfica
5. Matemática Intervalar
5 / 35
Introdução à Matemática Numérica
Natureza e Objetivos
Matemática Numérica
Matemática Computacional
Matemática Computacional
◮ Estudo da matemática do ponto de vista computacional
6 / 35
Introdução à Matemática Numérica
Natureza e Objetivos
Matemática Numérica
Matemática Numérica
Matemática Numérica
◮ Parte da matemática computacional que se preocupa com o
desenvolvimento de algoritmos para resolução aproximada de
problemas
◮ Utiliza como sistema de operações o conjunto {+,−, /, ∗} de
operadores matemáticos
7 / 35
Introdução à Matemática Numérica
Natureza e Objetivos
Matemática Numérica
Matemática Simbólica
Matemática Simbólica
◮ Busca a solução anaĺıtica de problemas matemáticos
◮ Por exemplo, a solução anaĺıtica da integral:
∫
x2 · dx =
x3
3
8 / 35
Introdução à Matemática Numérica
Natureza e Objetivos
Matemática Numérica
Matemática Gráfica
Matemática Gráfica
◮ Trabalha com modelos gráficos buscando solução na forma
gráfica
9 / 35
Introdução à Matemática Numérica
Natureza e Objetivos
Matemática Numérica
Matemática Intervalar
Matemática Intervalar
◮ Trata dados na forma de intervalos, buscando controlar os
limites de erro da matemática numérica.
10 / 35
Introdução à Matemática Numérica
Natureza e Objetivos
Matemática Numérica
Área de Concentração
Concentração
◮ Nos concentramos na matemática numérica
◮ Estudamos processos numéricos para a resolução de problemas
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
11 / 35
Introdução à Matemática Numérica
Algoritmos
Sumário
Natureza e Objetivos
Algoritmos
Algoritmos Numéricos
Resolução de Problemas
12 / 35
Introdução à Matemática Numérica
Algoritmos
Problema Computacional
Problema Computacional
Discussão de problemas computacionais em geral e a necessidade
de algoritmos para resolvê-los.
O que é um 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 ∈ A,
computar y = f (x).
◮ Definir um problema computacional é especificar a relação
entre entrada e sáıda.
◮ Exemplo: x codifica um grafo direcionado G = (V ,E ), uma
função w : E → R com os pesos dos arcos, e dois vértices s e
t. f (x) é o caminho mais curto de s a t.
13 / 35
Introdução à Matemática Numérica
Algoritmos
Algoritmo
Algoritmo
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 sáıda um valor (ou
conjunto de valores) com a solução de um problema
computacional.
◮ Um algoritmo é uma sequência de passos computacionais que
transforma entrada em sáıda
◮ Podemos ver um algoritmo como uma ferramenta para
resolver um problema computacional bem definido.
14 / 35
Introdução à Matemática Numérica
Algoritmos
Algoritmo
Algoritmo
ALGORITMO
ENTRADA SAIDA
15 / 35
Introdução à Matemática Numérica
Algoritmos
Problema de Ordenação
Definição Formal: Ordenação
Entrada
Uma sequência (a1, a2, . . . , an) de n números.
Sáıda
Uma permutação (a′1, a
′
2, . . . , a
′
n) da sequência de entrada tal que
a′1 ≤ a′2 ≤ . . . ≤ a′n.
◮ Dada uma sequência de entrada (31, 41, 59, 26, 41, 58) um
algoritmo de ordenação produz a sáı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 sáıda
16 / 35
Introdução à Matemática Numérica
Algoritmos
Problema de Ordenação
Ordenação
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
◮ tipo de memória utilizada (RAM, fita ou disco)
◮ grau de ordenação da entrada
Corretude
◮ Um algoritmo é dito correto se, para toda a instância, o
algoritmo termina com a sáıda correta.
◮ Neste caso, dizemos que o algoritmo resolve o problema.
17 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Sumário
Natureza e Objetivos
Algoritmos
Algoritmos Numéricos
Resolução de Problemas
18 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Introdução
Introdução
Introdução a Algoritmos Numéricos
◮ Algoritmos 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.
◮ Abaixo discutiremos caracteŕıticas desejadas de algoritmos
numéricos
19 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
Caracteŕısticas Desejáveis
Caracteŕısticas Desejáveis
◮ 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
20 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
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
21 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
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 posśı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”.
22 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
Inexistência de ErroOperacional
◮ Considere o problema computacional no qual procuramos
‖z‖ =
√
x2 + y2
◮ Se implementarmos diretamente a fórmula acima dependendo
dos valores x ou y , podemos ter:
◮ overflow em x2 ou
◮ overflow em y2, embora valha
√
x2 + y2 < t2.
23 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
Inexistência de Erro Operacional
Algoritmo Alternativo
O algoritmo abaixo procura contornar o problema de“overflow”.
Algoritmo
Se x = y = 0, então z = 0
Caso contrário
Se |x | ≥ |y |, então
z = |x |
√
1 +
(
y
x
)2
Caso contrário,
z = |y |
√
1 +
(
x
y
)2
24 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
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.
◮ Considere o problema de determinar, pelo método de Newton,
uma raiz da equação f (x) = sign(x) ·
√
|x | = 0, onde:



sign(x) = 1 se x > 0
sign(x) = 0 se x = 0
sign(x) = −1 se x < 0
25 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
Quantidade Finita de Cálculos
Algoritmo Problemático
Um algoritmo problemático é dado por:
Algoritmo
Entrada {x0, γ}
j ← 0
Enquanto |f (xj)| > γ faça
Se f ′(xj) 6= 0 então xj+1 = xj −
f (xj )
f ′(xj )
j ← j + 1
Fim-enquanto
Sáıda {j , xj}
Pare
26 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
Existência de um Critério de Exatidão
◮ É fundamental que o algoritmo forneça, de antemão, um
critério de exatidão em função das limitações de precisão das
máquinas.
◮ Se deseja que o algoritmo forneça:
Resultado = Valor Aproximado+ Erro
27 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
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.
28 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
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 R e a solução de máquina.
◮ Considere o problema de determinar sin(α) = x dado α ∈ R.
29 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
Precisão Infinita
Condição de erro nulo não satisfeita com precisão infinita
Algoritmo: calcula sin(α) = x
Entrada {α}
x = 0± 1
Sáıda {α, x}
30 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
Eficiência
◮ Quando se deseja encontrar a solução para um problema,
sempre visamos obter economia de rescursos envolvidos.
◮ Alguns fatores relevantes são:
1. tempo de execução;
2. exatidão;
3. volume de dados;
4. dificuldade de representação; e
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.
31 / 35
Introdução à Matemática Numérica
Algoritmos Numéricos
Caracteŕısticas Desejáveis
Eficiência
◮ Outro exemplo se refere ao algoritmo de Cramer para a
solução de sistemas de equações lineares: Ax = b, com
A ∈ R
n×n.
Passos do algoritmo
1) calcule o determinante ∆ da matriz dos coeficientes;
2) calcule os n determinantes ∆xj resultantes da substituição da
coluna 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
◮ O algoritmo de Gauss termina após n3 operações.
32 / 35
Introdução à Matemática Numérica
Resolução de Problemas
Sumário
Natureza e Objetivos
Algoritmos
Algoritmos Numéricos
Resolução de Problemas
33 / 35
Introdução à Matemática Numérica
Resolução de Problemas
Passos para Resolução
Comentários Finais
Passos para Resolução
a) Modelo matemático do problema
b) Necessidade de simplificação
c) Uso de valores já conhecidos
d) Parâmetros de equações termodinâmicas
e) Escolha ou desenvolvimento do algoritmo
f) Definição de parâmetros do algoritmo
g) Como a maioria dos problemas não tem solução direta e
precisa, faz-se o uso de métodos iterativos.
34 / 35
Introdução à Matemática Numérica
Resolução de Problemas
Passos para Resolução
Comentários Finais
◮ Fim!
◮ Obrigado pela presença
35 / 35