Análise Numérica (1)
Introdução e Sistemas de Numeração
V1.0, Victor Lobo, 2004
Objectivo da cadeira
Introdução
Introdução
Introdução
Introdução
z
Finalidade (Pescolnav 101):
– Proporcionar aos alunos conhecimentos sobre a introduçao
aos métodos numéricos básicos, tendo em vista o
desenvolvimento da capacidade de raciocínio lógico e futura
aplicação a problemas da vida corrente.
Análise Numérica
z
Objectivos (Pescolnav 101):
– Conhecer os métodos numéricos básicos e compreender o seu
funcionamento.
– Saber avaliar das possibilidades e vantagens/desvantagens da
sua utilização.
– Ser capaz de os utilizar com critério e escrever programas de
computador que os implementem com eficácia adequada.
– Ser capaz de detectar oportunidades de aplicação destes
métodos e ficar sensibilizado para estas técnicas.
Doutor Victor Sousa Lobo
Escola Naval
11
V.Lobo @ EN
22
V.Lobo @ EN
Programa da cadeira (1/2)
Programa da cadeira (2/2)
Introdução
Introdução
z
Introdução
z
Números
Introdução
Introdução
z
z
Capacidade de um tanque
Computadores
Erros
z
Sistemas de equações lineares
z
Navegação astronómica
Equações não lineares
Integração Numérica
Cinemática (em Naveg.)
z
Equações diferenciais
Deslocamento de um navio
– Euler, Runge-Kutta, Adams-Bashford
– Multiplicidade de raízes, métodos da bissecção, falsa posição,
ponto fixo, Newton-Raphson, secante
Baixas em combate
Estabilitade, circ.c/díodos
33
V.Lobo @ EN
Manutenção preditiva / Astronomia
– Newton-Cotes (trapézios, simpson), Romberg, diferenciação
numérica
– Métodos directos (Gauss), e iteractivos (Jacobi e Gauss-Seidel)
z
Aproximação de funções
– Mínimos quadrados, regressão linear, regressão polinomial
– Definições, algarismos significativos, erros de arredontamento,
propagação de erros
z
Interpolação Polinomial
– Polinómio interpolador de Lagrange, Newton (dif. Divididas e
progressivas), interpolação inversa, splines
– Representações, sistemas de numeração, vírgula fixa vs.
flutuante
44
V.Lobo @ EN
Avaliação
Introdução à Análise Numérica
Introdução
Introdução
z
Introdução
Introdução
z
2 Repetições escritas
–
–
–
–
– Datas ?
z
Trabalhos de casa
– Curtos, de uma aula para a seguinte
z
z
Trabalho final
Resolver problemas numericamente
Analisar os problemas dessa resolução
Métodos Numéricos vs Análise Numérica
Análise Matemática resolve problemas “em abstracto”, aqui
resolvemo-los “na prática”...
Passos para resolver um problema:
– Desenvolver um ALGORITMO: passos ou método de cálculo que
conduz à solução do problema
– Individual ou grupos de 2 alunos. Todos os trabalhos são
diferentes. Aceitam-se sugestões...
– Pode ser feito^:
→“à mão” ...
→Em Delphi (pascal)
→Em MATLAB
→Noutra linguagem de programação que o prof. conheça ...
V.Lobo @ EN
Objectivo:
– Análise desse algoritmo quanto a:
→Eficiência de cálculo (complexidade do algoritmo, tempo e
espaço necessários)
→Exactidão da solução (melhor ou pior aproximação à resposta)
55
– Implementar o algoritmo num computador
V.Lobo @ EN
66
1
Análise Numérica (1)
Introdução e Sistemas de Numeração
V1.0, Victor Lobo, 2004
História e exemplos
Programas de computador
Introdução
Introdução
z
Matemática Grega, chinesa, etc, etc, etc,
z
Probelmas famosos no séc XIX e XX
z
Advento dos computadores
z
Algoritmos para multiplicação e divisão
€19 a dividir por 3 amigos ?
MATLAB
– Fácil programação de problemas numéricos, fácil visualização
dos dados, muitas bibliotecas de rotinas dedicadas a
problemas deste tipo
z
MATCAD
– Folha de cálculo “livre”, com muitas bibiotecas dedicadas
WHILE A>B DO
BEGIN
A:=A-B;
C:=C+1;
END;
C:= A/B;
WRITELN(C);
Linguagem de uso genérico
– Permitem fazer tudo !
A:=3162;
B:=834;
C:=0;
A:=3162;
B:=834;
√29 ?
z
z
– Directo
– Somas (ou subtrações) sucessivas
Contas de cabeça:
Introdução
Introdução
z
MATEMÁTICA, EXCEL, SPSS, SAS, SAP-R3 (!), etc,etc,etc
– Implementam muitos destes métodos
– Há que perceber que por vezes são aproximações
WRITELN(C);
77
V.Lobo @ EN
88
V.Lobo @ EN
Bibliografia
Sistema de Numeração Decimal
Introdução
Introdução
z
Números
Números
Fundamentos de Análise Numérica, F. Correia dos
Santos, Sílabo 2002
z
Numerical Methods for Scientists and Engineers, R.
Hamming, Dover 1987.
z
Métodos Numéricos, Heitor Pina, McGraw-Hill 1995
z
Numerical Recepies (in C & in Pascal),
Cambridge University Press 1988
z
Applied Numerical Analysis using Matlab, Laurene
Fausett, Prentice-Hall 1999
z
Quantidade vs representação dessa quantidade
z
Significado dos números decimais:
– 1842 ⇒
2x100 + 4x101 + 8x10 2 + 1x103
– 10 símbolos: 0,1,2,3 ... 8,9
– Peso (ordem) de cada dígito dado pela posição
A posição é que dá importância ou peso ao dígito.
Os pesos são todos potências de uma dada base
O dígito mais significativo é o que está mais à esquerda (MSB)
O dígito menos significativo é o que está mais à direita (LSB)
z
99
V.Lobo @ EN
Outras bases muito usadas: base 2,8,16
10
10
V.Lobo @ EN
Conversão Binário/Decimal e v.v.
Sistemas de Numeração de potencias de 2
Números
Números
z
Números
Números
OCTAL
z
– SÍMBOLOS 0..7
– 1634 ⇒ 1x83 +6x82 + 3x81 + 4x80
z
– Escrever o peso de cada dígito, e somar
1 0 1 0 0 1 1 0b = 166d
HEXADECIMAL
1
0
128 64
– SÍMBOLOS 0.. 9,A,B,C,D,E,F
– 5F1A0 ⇒ 5x164 + 15x163 + 1x162 + 10x161 + 0x160
z
BINÁRIO
– SÍMBOLOS 0,1
– 10110 ⇒ 1x24 + 0x23 + 1x22 + 1x21 + 0x20
z
Binário → decimal
1
32
0
16
+
Computadores usam
o sistema binário
z
0
8
1
4
+
– É fácil construir máquinas que trabalham com apenas 2 símbolos
(ligado/desligado)
z
– São fácilmente convertidos em binário (e vice-versa) e são fácilmente
entendidos por humanos.
V.Lobo @ EN
LSB
Sistema octal / hexadecimal
11
11
V.Lobo @ EN
0
1
128+32+4+2=166
+
26 d = 11010 b
Decimal → binário
– Divisões sucessivas
Sistema Binário:
1
2
26d 2
0
13 2
1 6
0
2
3
1
2
1
MSB
12
12
2
Análise Numérica (1)
Introdução e Sistemas de Numeração
V1.0, Victor Lobo, 2004
Conversões para Hexadecimal e Octal
Aritmética binária
Números
Números
z
Números
Números
z
As bases que são potências de 2 são facilmente
convertidas em binário e vice-versa
– Octal
– Hexadecimal
Basicamente as mesmas regras que a aritmética
decimal !
– Somam-se os números dígito a dígito
– De um dígito para o seguinte (mais significativo), pode “ir um”, ou
seja pode haver “CARRY”
– 1 e 1 são dois ( ou seja 10b)
– Exemplo:
1 dígito octal = 3 dígitos binários
1 dígito hexa = 4 dígitos binários
2
D
3
1 0 1 1 0 1 0 0 1 1
1
z
3
2
3
– Usam menos dígitos para representar um dado número
– São mais facilmente entendidas por humanos
– São muito usadas
Multiplicação
13
13
V.Lobo @ EN
(647)10
+ (537)10
(1184)10
1101
101
1101
0000
1101
1000001
152
× 231
152
456
304
35012
×
2D3H = 1011010011b = 1323 Oct.
Vantagens
(11011) 2
+ (10011) 2
(101110) 2
Adição
São apenas
deslocamentos
e somas !!!
14
14
V.Lobo @ EN
Outras bases, partes fraccionárias
Representações com número fixo de dígitos
Números
Números
z
z
Numa máquina, o número de dígitos é FINITO
– Não posso usar todos os dígitos que quiser
– Há um número MÁXIMO que se pode representar:
Podemos usar qualquer base:
– An An-1 ...A1 A0 na base B = An ×Bn + An-1 ×Bn-1 … A1 ×B + A0
z
00
01
10
11
00
01
Podemos usar partes fraccionarias:
– 12,74 = 1×101 + 2×100 + 7×10-1 + 4×10-2
z
Probelma para casa:
z
– Representar o nº de aluno em binário, octal , e hexa
00
00 01 10 11 00 01
01
11
10
Consequência da representação com um número
FINITO de dígitos
– Os números não são representados por uma recta, mas sim por
uma circunferência !
15
15
V.Lobo @ EN
16
16
V.Lobo @ EN
REPRESENTAÇÃO DE NÚMEROS NEGATIVOS
z
COMPLEMENTO PARA 2
Problema:
– Como indicar que um número é negativo, sem usar o símbolo “-”
(usando apenas 0 e 1)
– Solução: usar uma das posições para representar o sinal
z
Ideia Base
– Facilitar somas
e subtrações
Ide
ia b
ase
:
O bit mais significativo representa o sinal, e os restantes a magnitude
Sinal = 0 => Positivo
(representação normal)
Sinal = 1 => Negativo
Exemplos:
0100 = 4
-7
1100 = -4
0010 = 2
1011 = -3
-6
0110
MAGNITUDE
SINAL
3
-4 1100
0100 4
-3
-1 1000
0
7
2
0100 4
-5
NÚMERO ‘N’
-6
-7
1000
-8
7
6
5
NÚMERO ‘N’ EM COMPLEMENTO PARA 2
-5
-2
1
3
N(2) = M - N
2
0
0000
-4 1100
MÓDULO (MÁX Nº DE 1+1)
0
1
0000
-1
-2
-3
SINAL E MÓDULO
–
–
–
–
V.Lobo @ EN
z
6
Regra para fazer as conversões:
COMPLEMENTAR TODOS OS DÍGITOS A PARTIR DO 1º ‘1’
5
17
17
00110 (610) ⇒ 11010 (-610)
V.Lobo @ EN
100000
-00110
111010
18
18
3
Análise Numérica (1)
Introdução e Sistemas de Numeração
V1.0, Victor Lobo, 2004
COMPLEMENTO PARA 2
z
Complemento para 2
– Usa o bit mais significativo para representar o sinal (tal como
anteriormente)
– Os restantes bits são calculados de acordo com o algoritmo
apresentado
– Vantagens
→Permite ver rapidamente se um número é positivo ou negativo
→Não existem números repetidos (com 2 representações)
→O número -1 está imediatamente antes do 0
→As operações se doma e subtracção podem ser feitas usando os
algoritmos usuais
z
V.Lobo @ EN
Algoritmos para a conversão positivo/negativo em
complemento p/2
→Subtrair o número positivo ao número 1000.... (2N)
→Começar do lado direito, e deixar na mesma todos os dígitos até
ao primeiro 1 (inclusive). Complementar todos os dígitos a partir
desse ponto.
19
19
4