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