calculo numerico- Implementação de Algoritmos.pdf

8/17/2019 calculo numerico- Implementação de Algoritmos.pdf

1/56

Índice de conteúdos


Capítulo 1. Implementação de Algoritmos.................................................1

1.Computação Numérica............................................................................1

2.Etapas na resolução de um problema..........................................................2

2.1.Definição do problema..................................................................................2

2.2.Modelação matemática..................................................................................2

2.3.Cálculo da solução numérica...........................................................................2

2.3.1.Elaboração do algoritmo..........................................................................2

2.3.2.Codificação do programa (implementação do algoritmo...................................3

2.3.3.!rocessamento (e"ecução do programa.......................................................3

2.3.#.E"emplo..............................................................................................3

2.#.$nálise dos resultados...................................................................................#.Notação algorítmica...............................................................................!

3.1.Estrutura do algoritmo..................................................................................#

3.2.%ariá&eis e comentários.................................................................................'

3.3.E"presses e comando de atribuição.................................................................'

3.3.1.E"presses aritméticas............................................................................'

3.3.2.E"presses l)gicas..................................................................................*

3.3.3.E"presses literais.................................................................................+

3.#.Comandos de entrada e sa,da..........................................................................+

3.'.Estruturas condicionais..................................................................................+

3.'.1.Estrutura condicional simples....................................................................+

3.'.2.Estrutura condicional composta.................................................................+

3.'.3.Estruturas de repetição...........................................................................-

" i "


2/56


3.*.al/a no algoritmo.......................................................................................03.+.E"emplo de algoritmo...................................................................................0

!.Notação matem#tica.............................................................................1$

%.Comple&idade computacional..................................................................11

'.(epresentação de números.....................................................................1

*.1.epresentação de nmeros em diferentes bases..................................................13

*.1.1.epresentação de nmeros inteiros e con&erses de base................................13

*.1.1.1.epresentação de nmeros inteiros.....................................................1#*.1.1.2.Con&ersão pelo método das di&ises sucessi&as.......................................1#

*.1.2.epresentação de nmeros reais e con&erses de base....................................1'

*.1.2.1.epresentação em formato de ponto fi"o..............................................1'

*.1.2.2.epresentação no formato de ponto flutuante........................................1*

*.1.2.3.$ritmética de ponto flutuante............................................................1+

*.1.3.Con&ersão de nmeros inteiros da base b para a base decimal...........................10

*.1.3.1.$lgoritmo de orner........................................................................24

*.1.3.2.Di&isão de uffini...........................................................................21*.1.#.Con&ersão de nmeros fracionários da base b para a base decimal.....................21

*.1.#.1.$lgoritmo de orner........................................................................22

*.1.#.2.Di&isão de uffini...........................................................................22

*.1.'.5mero binário infinito..........................................................................23

*.2.6peraçes com nmeros binários....................................................................2#

*.2.1.$dição binária.....................................................................................2#

*.2.2.7ubtração binária.................................................................................2'

*.2.3.Multiplicação binária.............................................................................2*

*.2.#.Di&isão binária.....................................................................................2+

*.3.epresentação de nmeros em computadores digitais...........................................2+

*.3.1.epresentação de nmeros inteiros...........................................................2+

*.3.2.epresentação de nmeros reais...............................................................31

" ii "


3/56


).Erros.................................................................................................%+.1.ontes de erros e incerte8as..........................................................................3'

+.2.!recisão e e"atidão.....................................................................................3*

+.3.9ipos de erros...........................................................................................3+

+.3.1.Erro de formulação ou de modelação.........................................................3+

+.3.2.Erros iniciais (incerte8as dos dados do modelo.............................................3+

+.3.3.Erro grosseiro......................................................................................3+

+.3.#.Erro de arredondamento........................................................................3+

+.3.'.Erro de truncatura................................................................................3-

+.#.%alores apro"imados e erros..........................................................................3-

+.#.1.Erro absoluto......................................................................................3-

+.#.2.Erro relati&o.......................................................................................30

+.#.3.)rmula fundamental dos erros................................................................#4

+.#.#.5mero de d,gitos significati&os...............................................................#1

+.'.Erros de arredondamento.............................................................................#2

+.'.1.$rredondamento por defeito (ou corte do nmero........................................#3

+.'.2.$rredondamento simétrico......................................................................##

+.'.3.Erros de arredondamento na álgebra de ponto flutuante..................................#'

+.'.3.1.$dição........................................................................................#*

+.'.3.2.7ubtração....................................................................................#*

+.'.3.3.Multiplicação................................................................................#+

+.'.3.#.Di&isão........................................................................................#+

+.*.Erros de truncatura.....................................................................................#+

+.*.1.Cálculo de &alores de funçes transcendentes..............................................#++.*.2.Discreti8ação......................................................................................#-

+.*.3.Métodos iterati&os................................................................................#-

+.+.Condicionamento e estabilidade.....................................................................'1

+.-.$nálise de erros.........................................................................................'1

+.0.Conclusão................................................................................................'2

" iii "


4/56


" i* "


5/56

Capítulo 1. Implementação de Algoritmos


1. Computação Numérica

:ma etapa intermédia importante durante a resolução de um problema en&ol&e a elaboração de

um algoritmo; o


6/56


2. Etapas na resolução de um problema

Dado um problema1 4; usando apenas as # operaçes aritméticas.

2.2. -odelação matem#tica

6 problema real é transformado no problema original por meio de uma formulação matemática

(denominado modelo matemático. 5o e"emplo;

"=√ a "2 = a f ( ") = "2 − a = 4;

o problema real; calcular √ a ; a > 4; foi transformado no problema original (modelo matemático


7/56


algor,tmica. Desta forma; é poss,&el abstrair>se dos detal/es da linguagem de programação do

computador e concentrar>se apenas nos aspetos matemáticos do método.

$lém do mais; a descrição do método numa notação algor,tmica facilita a sua implementação em

se

retornar fase de elaboração do algoritmo para o corrigir.

2..!. E&emplo

!ara e"emplificar a etapa de determinar a solução numérico do problema do cálculo de √ a; será

utili8ado o método de 5eFton (descrito mais adiante para calcular uma rai8 de f (") = "2 − a = 4B

"G+1

= "G −

f("G)

f H ("G

).

7ubstituindo f(" e fH(" na e"pressão acima; tem>se 3

4 1.4444

1 '.4444 2.44442 3.#444 4.#444

3 3.423' 4.423'# 3.4441 4.4441' 3.4444 4.4444

" "


8/56


$ coluna "G mostra as sucessi&as apro"imaçes de √ 0 a cada iteração G e a coluna "G>3 apresenta a

diferença entre o &alor apro"imado "G e o &alor e"ato 3.

2.!. An#lise dos resultados$ adese construir um no&o problema original (modelo matemático

atra&és de uma no&a formulação matemática e determinar uma no&a solução numérica.

E&emplo !ara o caso anterior (√ a; se for atribu,do o &alor inicial "4 I >1 (ou 1.44441 >'.4444 >-.44442 >3.#444 >*.#4443 >3.423' >*.423'# >3.4441 >*.4441' >3.4444 >*.4444

$lguns modelos matemáticos podem produ8ir soluçes


9/56


onde Jlista>de>&ariá&eisK são os nomes das &ariá&eis; separadas por &,rgulas; contendo os &alores

fornecidos. 5ão é necessário descre&er e"atamente como os &alores dessas &ariá&eis serão

fornecidas ao algoritmo. Compete ao programador decidir durante a codificação do programa se os

dados serão fornecidos interati&amente pelo teclado; lidos de um fic/eiro; passados comoargumentos de um subprograma ou; até mesmo; definidos como constantes dentro do pr)prio

programa.

Da mesma forma; os &alores de interesse calculados pelo algoritmo são disponibili8ados pelo

comando

par4metros de saída

podendo a Jlista>de>&ariá&eisK ser ampliada ou redu8ida pelo programados.

.2. 5ari#*eis e coment#rios:ma &ariá&el corresponde a uma posição de mem)ria do computador onde está; ou poderá estar;

arma8enado um determinado &alor. $s &ariá&eis são representadas por identificadores


10/56


$ tabela seguinte apresenta algumas funçes matemáticas se predefinidas.

7unção +escrição 7unção +escrição

8rigonométricas

sen

tan

seno

tangente

cos

sec

co>seno

secante

E&ponenciais

e"p

loge

e"ponencial

logaritmo natural

log14

rai82

logaritmo decimal

rai8


11/56


... E&press6es literais

:ma e"pressão literal é formada por operadores literais e operandos; os &ariá&eisK está dispon,&el para leitura nalgum dispositi&o

e"terno. !or sua &e8; o comando

escre*a de&e ser utili8ado para indicar onde certos &alores de interesse estão dispon,&eis no programa e

podem ser escritos nalgum dispositi&o e"terno. Compete ao programador decidir pela ampliação da

Jlista>de>&ariá&eisK ou mesmo a omissão do comando escre*a.

.%. Estruturas condicionais

6 uso de uma estrutura condicional torna poss,&el a escol/a dos comandos a serem e"ecutados


12/56


7e a e"pressão l)gica JcondiçãoK ti&er como resultado o &alor *erdadeiro; então a sese>á uma estrutura de repetição com interrupção no in,cio (estrutura en


13/56


será incrementada com o &alor de JdeltaK. 5o&amente; é &erificado se a &ariá&el JcontroleK é

maior do o e elementos do *etor @

par4metros de saída !"dia %esvio&adrão

'oma (

'oma2 (

para i 1 até n ,aça

'oma 'oma ) x*i+

'oma2 'oma2 ) x*i+2

,impara

!"dia 'oma , n

%esvio&adrão rai2 **'oma2 . *'oma2 , n++ , *n-1++

escre*a !"dia %esvio&adrão,imalgoritmo

" B "


14/56


!. Notação matem#tica

Definida a modelação matemática por meio de e"presses aritméticas e l)gicas; o passo seguinte

é passar desta notação matemática para a notação algor,tmica. Esta passagem é ilustrada pelos

e"emplos 2 (norma Euclidiana de um &etor x

de taman/o n; definida pela seguinte e"pressãoB

∥" ∥2

= √∑i=1n

∣"i∣2.

Algoritmo Norma2

? b3eti*os #alc$lar a norma-2 */$clidiana+ de $m vetor @

par4metros de entrada n x

? taman>o e elementos do *etor @

par4metros de saída 02

{ norma-2 do vetor }

'oma (

para i 1 até n ,aça

'oma 'oma ) *abs*x*i+++2

,impara02 rai 2'oma+

escre*a 02

,imalgoritmo

E&emplo 2B implementar um algoritmo para calcular a norma> (norma de má"ima magnitude de

um &etor x de taman/o n; definida pela seguinte e"pressãoB

∥" ∥∞ = ma"1≤i≤n

∣"i∣.

Algoritmo Norman

? b3eti*os #alc$lar a norma- de $m vetor @

par4metros de entrada n x

? taman>o e elementos do *etor @

par4metros de saída 0in

{ norma-

do vetor }

Nin, abs&1//

para i 2 até n ,açase abs&i// ; Nin, então

" 1$ "


15/56


0in abs*x*i++

imse

,impara

escre*a 0in

,inalgoritmo

%. Comple&idade computacional

W usual definir>se uma função de comple"idade para medir o custo de e"ecução de um

algoritmo. Esta função tanto pode ser uma medida do tempo necessário para e"ecutar o algoritmo

se estimati&a do esforço computacional

despendido para resol&er o problema; sendo medido pelo nmero de operaçes aritméticas e

l)gicas efetuadas para resol&er um sistema linear de ordem n.

6s problemas possuem comple"idade computacional; podendo ser en


16/56


cu=o algoritmo é o seguinteB

Algoritmo agrange_/xpressão_1

? b3eti*os nterpolar $sando polinmio de agrange @

par4metros de entrada m4 x4 54

? número de pontos abcissas @

? ordenadas e *alor a interpolar @

par4metros de saída r { valor interpolado }

r (

para i 1 até m ,aça

p 5*i+

para j 1 até m ,aça

se i 3 então

p p 6 * * . x*j++ , *x*i+ . x*j++ +

,imse

,impara

r r ) p

,impara

escre*a r

,imalgoritmo

Considerando


17/56


+ Y1

×(" −"

4) × (" −"

2) × ... × (" −"

n)

("1

−"4

) × ("1

−"2

) × ... × ("1

−"n

)

Z ...

+ Y4

× (" −"4) × (" −"1) × ... × (" −"n−1)

("n

−"4

) × ("n

−"1

) × ... × ("n

−"n−1

)

$o analisar>se a comple"idade computacional do algoritmo desta e"pressão; &erifica>se


18/56


'.1.1.1. (epresentação de números inteiros

á no m,nimo duas formas de se representar um nmero inteiro 5. 6 sistema posicional agrupa

os d,gitos na forma de uma se


19/56


'.1.2. (epresentação de números reais e con*ers6es de base

5este momento; é importante con/ecer como os nmeros reais podem ser arma8enados num

computador. :m nmero pode ser representado de duas formasB

➔ com ponto fi"o; por e"emplo; 12.3#➔ com ponto flutuante (ou &,rgula flutuante; por e"emplo; 4.123#"142.

'.1.2.1. (epresentação em ,ormato de ponto ,i&o

Dado um nmero real ]; este possui uma parte inteira ] i e uma parte fracionaria ]f I ] > ]i.

Desta forma; para se con&erter este nmero ] na base binária utili8a>se o mtodo das divis,es

sucessivas para ]i; en

se ]f por 2; e"traindo>se a parte inteira do resultado (a se o processo até


20/56


'.1.2.2. (epresentação no ,ormato de ponto ,lutuante

$ forma geral de representação de um nmero real de ponto flutuante é semel/ante notação

cient,ficaB

d1d2d3...dp × be;

onde d - (G I 1;2;...;p são os d,gitos da parte fracionária (com 4 P dG P b>1; d1 Q 4; b é o &alor da

base (geralmente 2; 14 ou 1*; p é o nmero de d,gitos e e é um e"poente inteiro. Deste modo; um

nmero de ponto flutuante é composto por tr@s partesB o sinal; a parte fracionária (denominada

também de significando ou mantissa e o e"poente. Estas tr@s partes t@m um comprimento total

fi"o


21/56


!or outro lado; como a forma de representação (nmero de d,gitos da mantissa de um nmero

de ponto flutuante pode ser diferente entre os fabricantes do computadores; um mesmo programa

implementado em computadores 34- 3.3* " 14>#032

d,gitos decimais + 1* 10

'.1.2.. Aritmética de ponto ,lutuante

7e uma operação aritmética resultar num nmero


22/56


E&emplo 2 3+2 > 3+1

6s nmeros são arma8enados no formato especificado; as casas decimais são alin/adas e a

operação de adição é efetuada. 6 resultado é arredondado para dois d,gitos é o seguinteB

3+2 > 3+1 I .3+ " 143

Z .3+ " 143

I .3+ " 143

> .3+ " 143

I .44 " 143

.44 " 144.

6 resultado da subtração é 4 em &e8 de 1. $ perda de precisão 1 I .12 " 14#

" .1* " 14>1

I .4102 " 143

.10 " 142.

6 resultado da multiplicação é 10 em &e8 de 10.+##.

E&emplo % -+' " 31+2

6s nmeros são arma8enados no formato definido e a multiplicação é efetuada utili8ando 2p 4

d,gitos na mantissa. 6 resultado é arredondado; normali8ado e; como o e"poente e I + K ' (má"imo

definido para este /ipotético computador; então ocorre o&erfloFB

-+' " 31+2 I .-- " 143 " .32 " 14# I .-- " 143

" .32 " 14#

I .2-1* " 14+

over%lo. (e L>'; [; '.6 resultado obtido é superior ao maior nmero representá&el por este computador (e L>'; [; '.

" 1= "


23/56


E&emplo ' 4.441-3 #02

6s nmeros são arma8enados no formato definido e a di&isão é efetuada utili8ando 2p 4 d,gitos

na mantissa. 6 resultado é arredondado para dois d,gitos e normali8adoB

4.441-3 #02 I .1- " 14>2 .#0 " 143 I .1- " 14>2 .#0 " 143

I .3*+3 " 14>'

.3+ " 14>'.

6 erro relati&o desse resultado foi de apro"imadamente 4;'2^.

E&emplo ) 4.44*# +312

6s nmeros são arma8enados no formato definido e a di&isão é efetuada utili8ando 2p 4 d,gitos

na mantissa. 6 resultado é arredondado; normali8ado e; sendo o e"poente e I >* J >'; então ocorre

under%lo. B

4.44*# +312 I .*# " 14>2 .+3 " 14# I .*# " 14>2

.+3 " 14#

I .-+*+ " 14>*

under%lo. (e L>'; [; '.

6 resultado da di&isão é um &alor inferior ao menor nmero representá&el por este comutador

(por definição; e L>'; [; '; sem considerar o 8ero;


24/56


'.1..1. Algoritmo de Forner

6 nmero 5 pode ser obtido na base decimal atra&és do cálculo da se1 I am"1 Z 2 " bm

bm>2 I am"2 Z 2 " bm>1

... ...

b1 I a1 Z 2 " b2

b4 I a$ Z 2 " b1

e então;

N D b$

E&emplo se=a o nmero (111412.

$plicando o algoritmo de ornerB

b# I a# I 1

b3 I a3 Z 2 " b# I 1 Z 2 " 1 I 3

b2 I a2 Z 2 " b3 I 1 Z 2 " 3 I +

b1 I a1 Z 2 " b2 I $ Z 2 " + I 1#

b4 I a4 Z 2 " b1 I 1 Z 2 " 1# I 2B

portanto;

111$1/2 D 2B1$

Esta metodologia pode ser generali8ada para con&erter 1 I am"1 Z b " cm

cm>2 I am"2 Z b " cm>1

... ...

c1 I a1 Z b " c2

c4 I a$ Z b " c1

e então;

N D c$

" 2$ "


25/56


'.1..2. +i*isão de (u,,ini

W e1 ... c2 c1 c$e então;

N D c$

'.1.!. Con*ersão de números ,racion#rios da base b para a base decimal

Considere um nmero fracionário com representação finita na base bináriaB

]f I (4.a1a2[an2 .

6 seu &alor na base decimal será dado por

]f I 1 2>1 Z 2 2>2 Z [ Z n 2>n

Esta soma pode ser calculada diretamente ou utili8ando


26/56


'.1.!.1. Algoritmo de Forner

5o caso de um nmero fracionário na base 2; o algoritmo fica

bn I a n

bn>1 I a n"1 Z (1N2 " bn

bn>2 I a n"2 Z (1N2 " bn>1

... ...

b2 I a 2 Z (1N2 " b3

b1 I a 1 Z (1N2 " b2

b4 I (1N2 " b1

e então;

N D b$

E&emplo con&erter o nmero (4.141112.

$plicando o algoritmo; ficaB

b' I a % I 1

b# I a ! Z (1N2 " b' I 1 Z (1N2 I 3N2

b3 I a Z (1N2 " b# I 1 Z (3N# I +N#

b2 I a 2 Z (1N2 " b3 I $ Z (+N- I +N-b1 I a 1 Z (1N2 " b2 I 1 Z (+N1* I 23N1*

b4 I (1N2 " b1 I (1N2 " (23N1* I 23N32

portanto;

$.1$111/2 D 2G2 D $.)1=)%

'.1.!.2. +i*isão de (u,,ini

5o caso de um nmero fracionário na base 2; o algoritmo fica

an a n"1 ... a 2 a 1

1N2 (1N2 " bm ... (1N2 " b3 (1N2 " b2 (1N2 " b1

bn bn>1 ... b2 b1 b$

e então;

N D b$

" 22 "


27/56


E&emplo Con&erter o nmero (4.141112 .

$plicando o algoritmo; ficaB

a% a ! a a 2 a 1

1 1 1 $ 1

1N2(1N2 " b' (1N2 " b# (1N2 " b3 (1N2 " b2 (1N2 " b1(1N2 " 1 (1N2 " (3N2 (1N2 " (3N# (1N2 " (+N- (1N2 " (23N1*

b' b# b3 b2 b1 b$1 3N2 +N# +N- 23N1* 2G2

portanto;

$.1$111/2 D 2G2 D $.)1=)%

'.1.%. Número bin#rio in,inito:ma outra situação se

1 + 2−m

+ 2−2m

+ 2−3m

+ ... =

1

1 −2−m =

2m

2m−1 (fa8endo " I 2>m

;

" 2 "


28/56


obtendo>se

]f=α12−1 + α22

−2 + ... + αn2−n+(β12−1 + β22−2 + ... + βm 2−m) 2

m−n

2m−1

$s duas e"presses entre par@nteses t@m a mesma forma e podem ser calculadas diretamenteusando


29/56


E&emplo 14142 Z 11112 I 114412 (1414 Z 1'14 I 2'14

`1 `1 `11 4 1 4

Z 1 1 1 1

1 1 4 4 1

Tuando um dos operandos são nmeros binários negati&os; o processo a aplicar é o seguinteB

➔ dois operandos negati&osB adicionam>se os dois considerando o &alor absoluto de cada um

deles e atribui>se o sinal de negati&oU

➔ um deles é negati&oB &erifica>se se o menor

&alor absoluto ao maior e; atribui>se o sinal do maior em &alor absoluto.

'.2.2. Hubtração bin#ria

$ subtração é análoga adição; sendo reali8ada de acordo com as seguintes regrasB

4 > 4 I 4

4 > 1 I 1 (e Rpede emprestado 1S para o d,gito de ordem superior

1 > 4 I 1

1 > 1 I 4

Desta forma; a operação 4 > 1 resulta em 1; mas com o transporte de 1 para a coluna es


30/56


'.2.. -ultiplicação bin#ria

!rocede>se como numa multiplicação no sistema decimal; de acordo com as seguintes regrasB

4 " 4 I 4

4 " 1 I 41 " 4 I 4

1 " 1 I 1

:tili8a>se o mesmo método


31/56


'.2.!. +i*isão bin#ria

$ di&isão binária usa o mesmo método 1 1 4 1 1 1

4 1 4 4 1> 1 1 4

4 4 1 1 4> 1 1 4

4 4 4

'.. (epresentação de números em computadores digitais

5esta secção serão apresentadas algumas das representaçes usadas para arma8enar nmeros

inteiros e reais na mem)ria de um computador. $s representaçes de nmeros inteiros e reais

apresentadas na secção anterior não são suficientesU é necessário distinguir>se; por e"emplo; o

sinal do nmero. Como não e"iste a representação de um sinal Z ou > na mem)ria de um

computador; o recurso utili8ado é acrescentar um bit; para computadores binários; ao nmero para

representar o sinalU este bit é denominado bit de sinal.

'..1. (epresentação de números inteiros

$ representação mais direta de nmeros inteiros é a denominada 7inal>M)dulo (também

denominada por 8inal$9agnitude. 5esta representação; o &alor absoluto do nmero inteiro é

obtido diretamente a partir dos algoritmos discutidos na secção anterior; en


32/56


em 12- 123 >' (123>12-

1 1 4 1 4 1 1 1 decimal

>12- -+ >#1 (-+>12-

1 1 1 1 1 1 1 1 decimal>12- 12+ >1 (12+>12-

E"istem outras representaçes de nmeros inteiros em computadores; como por e"emplo as

representaçes em complemento a (b$) e em complemento a b.

$ representação de nmeros positi&os em complemento é id@ntica representação em 7inal>

M)dulo. $ representação dos nmeros inteiros negati&os é obtida efetuando>seB (base > 1 menos

cada algarismo do nmero. !or e"emplo; para calcular o complemento a (base > 1 do nmero

>20+14 (como a base é 14; então 14 > 1 I 0; e o complemento a (base >1 será complemento a 0Ucomo 000 > 20+ I +42; o complemento a 1 do nmero >20+ é +42.

" 2= "


33/56


!ara se obter o complemento a (b 1 de um nmero binário; de&e>se subtrair cada algarismo de

1 (b > 1 I 1U no entanto; como se trata de nmeros binários é se representar os seguintes nmerosB 21 até

um d,gito (4; 1; 22 até dois d,gitos (44; 41; 14; 11; 23 nmeros até tr@s d,gitos (444; 441; 414; 411;

144; 141; 114; 111; [

$ tabela seguinte apresenta a representação em C1 dos nmeros binários de # d,gitos. epare

como o espaço de representação da base 2 com # d,gitos está sendo usado na representação em C1

(note m)dulo

Decimal(negati&o \inário em C1

4 4444 4 11111 4441 >1 11142 4414 >2 11413 4411 >3 1144# 4144 ># 1411' 4141 >' 1414* 4114 >* 1441

+ 4111 >+ 1444

$ representação na base 14 com 3 d,gitos &aria de 444 a 000 (143 representaçes; representando

os nmeros de >#00 a >1 (fai"a negati&a 1B

>#1- é representado por 000 > #1- I '-1

'-1 Z 123 I +4#

000 > +4# I 20'; em 20' (+4# está na fai"a negati&a.

" 2B "


34/56


De notar se numa soma em complementoU isto é; a soma dos complementos do nmero

positi&o com o nmero negati&o. !ortanto; uma subtração pode ser reali8ada simplesmente atra&és

da soma dos nmeros RcomplementadosSB manter o nmero se é positi&o e complementar o nmerose é negati&oU depois; é s) somar.

Desta forma; pode>se constatar 1; edepois somar 1 ao resultado. 6u se=a; encontramos o complemento a (base > 1 do nmero (o m)dulo

Decimal(negati&o

\inário em C2

4 4444 >1 11111 4441 >2 11142 4414 >3 11413 4411 ># 1144# 4144 >' 1411' 4141 >* 1414* 4114 >+ 1441+ 4111 >- 1444

Comparando com a tabela anterior (para C1; nota>se


35/56


$ fai"a de representação em C2 dos nmeros binários de n d,gitos é a seguinteB

➔ menor inteiro negati&oB > 2n>1;

➔ maior inteiro positi&oB 2n>1 1.

5a aritmética em complemento a base; basta somar os nmeros; sendo se ter; no entanto; cuidado com a possibilidade

de acontecer over%lo. . Em 1 #. 4114 Z 1411 (* ' I 1

'. 1411 Z 1414 (>' > * I >11

$ representação de um nmero inteiro num computador é e"ata. 6peraçes aritméticas entre

nmeros inteiros também é e"ata; sob as seguintes condiçesB

1. o resultado não pode encontrar>se fora do inter&alo de nmeros inteiros


36/56


e uma mantissa inteira positi&a -; sendo gitos do sistema e define o taman/o da mantissa 9 I 4. d1d2...dn.

6 &alor 8ero não pode ser normali8ado e tem representação especial; com mantissa nula (todos

d,gitos iguais a 8ero e e"poente o menor poss,&el (m1. 6 con=unto formado pelo 8ero e por todos

os nmeros em notação de ponto flutuante é c/amado 'istema de &onto 8l$t$ante na base b com

n algarismos significati&os; denota>se por 7b n emin ema&/.

Contudo; um computador apenas pode representar os &alores de e e - atra&és de d,gitos na base

b. :m computador digital (b I 2; por e"emplo; dispe sempre de um taman/o de pala&ra finito;

isto é; o nmero total de bits


37/56


número bin#rio base 2/

decimal base 1$/ s e&poente de = bits -antissa de 2 bits

1N2 4 44444444 (4 14444444444444444444444

1N# 4 11111111 (>1 144444444444444444444441 4 44444441 (1 14444444444444444444444

3 4 44444414 (2 11444444444444444444444

$ con&ersão do nmero & a3-

3.#42-23' " 143-

1.1024020 " 14>+

'2>14221423

2.22'4+3-'-'4+241 " 14>34-

1.+0+*0313#-*231* " 1434-

2.224##*4#02'4313 " 14>1*

113>1*3-21*3-3

3.3*21431#3112403'4*... " 14>#032

1.1-0+31#0'3'+231+*'... " 14#032

1.02'0200##3-+23'-'3... " 14>3#

" "


38/56


!ara uma base b


39/56


ou se=a; a região de under%lo. consiste no inter&alo

−1*#

< " < 1*#

➔ 6 maior nmero positi&o poss,&el éB

"ma"

= (4.1111)2

× 2* = 1 − 2−# × 2* = *4U

ou se=a; as regies de o&erfloF consistem nos inter&alos

" < −*4 e " > *4.

➔ 6 maior nmero


40/56


não fa8 sentido a implementação de um modelo numérico e de um método


41/56


).. 8ipos de erros

Durante as etapas de resolução de um problema; surgem erros de &árias origens


42/56


num nmero finito de bits. 6 erro causado por esta imperfeição na representação de um nmero é

denominado de erro de arredondamento. $s causas e conse0 1;2 " 14>12

N- +;- " 14>' 2;0 " 14>+ *;1 " 14>14

N* 3;3 " 14># 2;1 " 14>* -;1 " 14>0

N# 2;' " 14>3 3;* " 14>' 3;1 " 14>+

).!. 5alores apro&imados e erros

$o resol&er um problema numérico no computador obtém>se; em geral; um &alor apro"imado

para a solução e"ata do problema. W assim importante poder a&aliar a


43/56


Como para a maior parte dos problemas ] é descon/ecido; não é poss,&el calcular o erro

absoluto; sendo apenas poss,&el estimar$se o seu &alor. eralmente con/ece>se a # para min;

E$ I 1.2330 " 14># para pma" e;

E$p I 2.+'#* " 14># para a média entre pmin e pma".

!ortanto; $rlo pelo &alor

apro"imado fl(] no denominador da e"pressão para o erro relati&o; como a seguinteB

E]

=E$

]

∣ fl( ])∣ = ∣] − fl(] )fl(]) ∣ ≤

δ]

∣ fl( ])∣.

6 erro relati&o não tem dimensão e; em geral; s) é con/ecido o limite superior do seu &alor; ]; o


44/56


Ep I 3.02*2 14># para pma" e;

Ep I -.+*+# " 14>' para a média.

Em geral; a mel/or medida para se estimar a precisão de uma apro"imação é o erro relati&o;

pois este indica diretamente o nmero de d,gitos significati&os corretos na apro"imação.

).!.. 79rmula ,undamental dos erros

Considere>se um determinado problema de cálculo numérico; I f(]. Mesmo


45/56


5ormalmente∣] f H (])∣∣f (]) ∣

é designado por n9mero de condição de f em ] e nota>se por cond *:+.

Este &alor; cond *x+; é um indicador do efeito da propagação do erro relati&o; no &alor da função

no ponto : ; e permite a&aliar em se se


46/56


onde G é o maior nmero inteiro positi&o para o '; *; o nmero racional

Y I 4.123#'000...

não pode ser e"atamente representado. $ forma de Y na base 2 éBY I 4.123#'000... I (4.444111111441141...2.

!ara escre&er Y de acordo com o sistema (2; #; >'; *; de&e>se primeiro normali8ar de acordo com

as operaçesB

Y2 I 2−# + 2−' + 2−* + 2−+ + 2−- + 2−0 + 2−12 + 2−13 + 2−1' + ...

I 2−3 × (2−1 + 2−2 + 2−3 + 2−# + 2−' + 2−* + 2−0 + 2−14 + 2−12 + ...)

I (4.111111441141...) × 2−3;

o 3 e EY I '.3'2' " 14>2 I '.3'^.

" !2 "


47/56


Este procedimento de apro"imação é denominado de arredondamento por de%eito ou corte do

n=mero.

Considere>se um nmero ] na forma normali8ada


48/56


Corol#rio 7e o erro relati&o do &alor apro"imado de um nmero não e"cede 1G2/ b"; então esse

&alor tem d,gitos significati&os.

!ara o e"emplo anterior; no sistema de representação (2; #; >'. *; pode>se escre&erB

Y2 I (4.1111) 2−3 + g

Y 2−

3−#; sendo gY I (4.11441141...

Então; efetuando o arredondamento por defeito obtém>se fl(Y2.

).%.2. Arredondamento simétrico

5o arredondamento simétrico; e"ecuta>se a seguinte operaçãoB

fl(] ) =

{(4. d1 d2 ...dn) b

e; se ∣g] ∣<

1

2

(4. d

1d

2...(d

n+1)

) b

e; se

∣g

] ∣

1

2

5este caso; o erro absoluto cometido por arredondamento simtrico é

E$]

= {∣g] ∣ be−n

; se ∣g] ∣<1

2

∣g] − 1∣ be−n ; se ∣g] ∣1

2

< 12

be−n ;

de onde se obtém uma estimati&a superior para o erro absoluto.

6 erro relativo cometido por arredondamento simtrico é

E]

=

1

2b

e−n

(4.d 1d2...dn) be

; se ∣g] ∣<1

2

1

2b

e−n

(4.d 1d2...(dn+1)) be ; se ∣g]∣

1

2

<

1

2 b

e−n

(4.1)b be

= 1

2 b

1−n

o se

fl(Y I 4.12';

o


49/56


6s computadores mais recentes modificam ligeiramente o arredondamento em relação f)rmula

apresentada antes. 5esta; o ltimo d,gito significati&o (d n não será alterado se _g]_ J 12 e será

alterado se _g]_ O 12. á; portanto; uma ligeira prefer@ncia para a alteração de dn no processo de

arredondamento; o se


50/56


da pala&ra no computador. !or outro lado; caso fosse solicitado o &alor de f(" para " h ; seria a

segunda e"pressão


51/56


Tuando se subtraem


52/56


Definindo

p+

(" ) = " −"

3

3+

"'

' −

"+

+


53/56


$ sese definida por iteraç7es se f não depende de G. $os &alores "4; "1; "2; [;

c/amam>se iteraçes.

!ara um grande nmero de problemas a sua solução pode colocar>se em termos do limite duma

sese a e


54/56


de arredondamento do sistema de ponto flutuante do computador e do nmero de algarismos

significati&os com


55/56


).). Condicionamento e estabilidade

De&ido e"ist@ncia dos c/amados erros iniciais; os dados e parVmetros do problema matemático

se bem condicionado

(ou matematicamente estável se pe


56/56


5a análise de erros in&ersa o resultado calculado de um problema numérico é interpretado como

o resultado e"ato do problema

Documents

calculo numerico- Implementação de Algoritmos.pdf