LIVRO-calc_num

8/7/2019 LIVRO-calc_num

1/236

AN ALISE NUM ERICA

MICHEL P. J. CARPENTIER

Fevereiro 1993

Departamento de Matem atica Instituto Superior Tecnico U. T. L.


2/236

Indice

ndice i

Prefacio v

1 Teoria dos erros 11.1 Representa cao dos numeros no computador . . . . . . . . . . . . . . . . 11.2 Erros na representa cao em vrgula utuante . . . . . . . . . . . . . . . 4

1.3 Operacoes aritmeticas em vrgula utuante . . . . . . . . . . . . . . . . 71.4 Propaga cao dos erros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4.1 Propaga cao dos erros em operacoes elementares . . . . . . . . . 101.4.2 Mau condicionamento e estabilidade . . . . . . . . . . . . . . . 15

1.5 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2 Equacoes nao lineares 252.1 Introdu cao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.2 Metodos da bisseccao e da falsa posicao . . . . . . . . . . . . . . . . . . 27

2.2.1 Metodo da bissec cao . . . . . . . . . . . . . . . . . . . . . . . . 28

2.2.2 Metodo da falsa posi cao . . . . . . . . . . . . . . . . . . . . . . 312.3 Metodos da secante e de Newton . . . . . . . . . . . . . . . . . . . . . 36

2.3.1 Metodo da secante . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.3.2 Metodo de Newton . . . . . . . . . . . . . . . . . . . . . . . . . 392.3.3 Criterio de convergencia para os metodos da secante e de Newton 42

2.4 Itera cao do ponto xo . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.4.1 Convergencia do metodo iterativo do ponto xo . . . . . . . . . 442.4.2 Modicacao do metodo de Newton para zeros m ultiplos . . . . . 51

2.4.3 Criterios de paragem . . . . . . . . . . . . . . . . . . . . . . . . 532.4.4 Aceleracao de Aitken . . . . . . . . . . . . . . . . . . . . . . . . 55

i


3/236

ii Indice

2.5 Zeros de polinomios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582.5.1 Localizacao dos zeros . . . . . . . . . . . . . . . . . . . . . . . . 592.5.2 Metodo de Newton para equacoes algebricas . . . . . . . . . . . 61

2.6 Precisao no calculo de zeros multiplos . . . . . . . . . . . . . . . . . . . 62

2.7 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3 Sistemas de equa coes 693.1 Elimina cao de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693.2 Pesquisa de pivot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 783.3 Variantes da elimina cao de Gauss . . . . . . . . . . . . . . . . . . . . . 82

3.3.1 Metodos compactos . . . . . . . . . . . . . . . . . . . . . . . . . 823.3.2 Metodo de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . 86

3.4 Analise de erros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 883.4.1 Normas de matrizes . . . . . . . . . . . . . . . . . . . . . . . . . 893.4.2 Numero de condicao de uma matriz . . . . . . . . . . . . . . . . 913.4.3 Metodo da correc cao residual . . . . . . . . . . . . . . . . . . . 95

3.5 Metodos iterativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 983.5.1 Metodos de Jacobi e de Gauss-Seidel . . . . . . . . . . . . . . . 98

3.5.1.1 Metodo de Jacobi (substitui coes simultaneas) . . . . . 993.5.1.2 Metodo de Gauss-Seidel (substitui coes sucessivas) . . 100

3.5.2 Criterios de convergencia dos metodos iterativos . . . . . . . . . 1033.5.2.1 Convergencia dos metodos iterativos . . . . . . . . . . 1033.5.2.2 Convergencia dos metodos de Jacobi e Gauss-Seidel . . 105

3.5.3 Metodo de relaxac cao SOR . . . . . . . . . . . . . . . . . . . . 1093.6 Sistemas de equacoes nao l ineares . . . . . . . . . . . . . . . . . . . . . 1133.7 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

4 Interpola cao Polinomial 123

4.1 Introdu cao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1234.2 Formula interpoladora de Lagrange . . . . . . . . . . . . . . . . . . . . 1244.3 Formula de Newton. Diferen cas divididas . . . . . . . . . . . . . . . . . 1274.4 Erro de interpola cao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1314.5 Nos igualmente espa cados . . . . . . . . . . . . . . . . . . . . . . . . . 1404.6 Nos de Chebyshev . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1474.7 Interpola cao inversa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152


4/236

Indice iii

4.8 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

5 Aproxima cao dos mnimos quadrados 1615.1 Introdu cao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

5.2 Sistema de equacoes normais . . . . . . . . . . . . . . . . . . . . . . . . 164

5.2.1 Caso discreto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

5.2.2 Caso contnuo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

5.2.3 Mau condicionamento do sistema normal . . . . . . . . . . . . . 171

5.3 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

6 Integra cao numerica 1756.1 Introdu cao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

6.1.1 Metodo dos coecientes indeterminados . . . . . . . . . . . . . . 177

6.2 Formulas de Newton-Cotes . . . . . . . . . . . . . . . . . . . . . . . . . 1786.2.1 Regra dos trapezios . . . . . . . . . . . . . . . . . . . . . . . . . 178

6.2.2 Regra de Simpson . . . . . . . . . . . . . . . . . . . . . . . . . . 181

6.2.3 Formulas de graus superiores . . . . . . . . . . . . . . . . . . . 184

6.3 Formulas de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

6.3.1 Polinomios de Legendre . . . . . . . . . . . . . . . . . . . . . . 188

6.3.2 Formulas de Gauss-Legendre. Erro de integracao . . . . . . . . 190

6.4 Integra cao adaptat iva . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1946.5 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

7 Equacoes diferenciais 2037.1 Introdu cao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

7.2 Metodo de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

7.2.1 Majoracao do erro e convergencia do metodo de Euler . . . . . . 207

7.3 Metodos de Runge-Kutta . . . . . . . . . . . . . . . . . . . . . . . . . . 209

7.4 Metodos multipasso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2127.4.1 Metodos de Adams-Bashforth . . . . . . . . . . . . . . . . . . . 212

7.4.2 Metodos de Adams-Moulton . . . . . . . . . . . . . . . . . . . . 213

7.4.3 Metodos preditor-corrector . . . . . . . . . . . . . . . . . . . . . 214

7.4.4 Outros metodos multipasso . . . . . . . . . . . . . . . . . . . . 216

7.5 Compara cao dos varios metodos . . . . . . . . . . . . . . . . . . . . . . 217

7.6 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218


5/236

iv Indice

Bibliograa 221

Resolu cao dos problemas 223


6/236

Prefacio

Com estes apontamentos de Analise Numerica pretendemos apresentar umelemento b asico para o estudo das disciplinas de An alise Numerica que s ao actual-mente lecionadas no IST.

Na resolucao de um problema em engenharia e em outras ciencias e geral-mente possvel distinguir tres fases: (1) a formula cao matem atica do problema, (2)a escolha de um metodo ou combina coes de metodos analticos e numericos para re-

solver o problema formulado, e (3) o calculo numerico da solucao. Basicamente ummetodo numerico e um conjunto ordenado de opera coes aritmeticas e l ogicas, funda-mentado em teoremas da analise matem atica, que conduz a solucao de um problemamatem atico. A um metodo numerico est a pois associado um algoritmo. A construcaode metodos numericos e a escolha apropriada destes metodos para a resolu cao de umdeterminado problema constitui o campo da an alise numerica.

O aparecimento dos computadores veio possibilitar calculos numericos ateent ao humanamente impossveis, o que teve como reexo o desenvolvimento de novosmetodos numericos e a adapta cao dos ja existentes a nova realidade. Desde ent ao aanalise numerica desenvolveu-se como ciencia propria contribuindo para a resolucaodos mais variados problemas. Baseada na analise matem atica classica, a analise

numerica desenvolveu por sua vez uma teoria propria: a analise de erros. Ummetodo numerico deve ser acompanhado de um estudo sobre majora coes de erros,convergencia, escolha do passo, estabilidade, etc.; e para cada problema deve-se saberalgo acerca do seu bom ou mau condicionamento.

Dado que a escolha de um metodo numerico se situa entre a formula caomatem atica do problema e a concretiza cao dos calculos, geralmente efectuados comuma maquina, a an alise numerica requere por um lado conhecimentos te oricos sobreo problema a resolver e por outro experiencia computacional. Para escolher dentrode varios metodos numericos o mais indicado `a resolucao de um determinado pro-blema devemos saber como estes se deduzem e por conseguinte os seus domnios deaplica cao e suas limita coes; como ja referimos devemos fazer as respectivas an alises de

erros e devemos, em certos casos, estimar o numero de opera coes a efectuar em cadametodo. Uma vez escolhido um metodo numerico devemos construir um algoritmoassociado a este. Este algoritmo dever a conter os principais passos do metodo epermitir ao programador traduzi-lo num programa inteligvel para o computador.Na hipotese de varios metodos numericos poderem conduzir ` a resolucao do mesmoproblema com a precis ao exigida pode nao ser indiferente a escolha de um deles.Criterios computacionais tais como maior rapidez de execu cao, menor ocupa cao damemoria e menor complexidade computacional podem ser decisivos na escolha.

Vemos assim que, hoje em dia, um metodo numerico e indissoci avel da teoria

v


7/236

vi Pref acio

que conduziu a sua cria cao e da implementa cao da seu algoritmo no computador.Dado que a an alise numerica abarca campos t ao variados n ao e de admirar que estefacto tenha reexos na estrutura de disciplinas introdut orias nesta area.

Com estas disciplinas pretendemos dominar, quer do ponto de vista te oricoquer do ponto de vista pr atico, a maioria dos metodos numericos mais utilizados nasaplica coes. Isto implica, como ja se deixou entender atras, que a apresenta cao dosmetodos devera ser acompanhada dos teoremas que os suportam e ilustrada frequente-mente por algoritmos de modo a permitir uma melhor compreens ao dos metodos euma mais facil passagem para a fase de computa cao. Ao apresentar v arios metodospara resolver o mesmo problema matematico deveremos comparar os seus campos deaplica cao e vantagens e inconvenientes de cada um. Os metodos dever ao ser testa-dos oportunadamente no computador utilizando programas feitos pelos utilizadores esubrotinas pertencentes a bibliotecas instaladas no computador (NAG, CERN, SSP,LINPACK, MINPACK, EISPACK).

Nestes apontamentos sao abordados a maioria dos temas que, na literatura,habitualmente sao includos num curso introdut orio a analise numerica. No entanto,dada a vastidao da an alise numerica nao se incluiu muitos temas, tais como valorese vectores proprios, optimiza cao, equacoes diferenciais ordinarias com condicoes defronteira, e equa coes diferenciais parciais, sob pena de ter de tratar supercialmenteos assuntos e tambem porque alguns dos temas requerem conhecimentos ainda n aoadquiridos pelos alunos.

Entenda-se que para os assuntos escolhidos bastar ao conhecimentos de an a-lise matem atica elementar, algebra linear e pr atica de programacao. Dado a inclus aonesta disciplina de metodos de resolucao numerica de equacoes diferenciais ordinarias,seria conveniente um conhecimento previo da teoria destas equa coes. Visto que, como actual currculo, os alunos s o mais tarde e que adquirem este conhecimento, foinecessario incluir alguns conceitos b asicos de equacoes diferenciais, nomeadamente aexistencia e unicidade das suas solucoes. Penso que a falta de um conhecimento maisaprofundado das equacoes diferenciais, que podera ocasionar algumas diculdades,e largamente compensada pela supress ao de uma lacuna (a resolu cao numerica deequacoes diferenciais) que se fazia sentir na prepara cao dos alunos.

A materia distribui-se por sete captulos. A escolha da teoria dos erros como 1captulo, onde se inclui a aritmetica do computador, justica-se, dado que os metodosnumericos s ao para implementar no computador e que os resultados obtidos por essesmetodos vem afectados de erros que de alguma forma e necess ario controlar. Apesarde algumas nocoes de interpola cao dadas no captulo 4 serem utilizadas em certosmetodos de resolu cao de equacoes nao lineares no captulo 2, optou-se por esta or-dem por varias raz oes. Em primeiro lugar, de todos os metodos numericos os deresolucao de uma equa cao nao linear sao, sem duvida, dos mais atraentes para osalunos, justicando assim a sua localizacao no incio do programa. Leva os alunosa familiarizarem-se desde o incio com metodos iterativos e nocoes relacionadas comestes, tais como: convergencia, criterio de paragem, precis ao dos resultados, ecienciacomputacional, comparacao de metodos, etc. Os metodos iterativos mais elementaressao de facil implementa cao no computador, e portanto, do ponto de vista pedag ogico,e vantajoso ensaia-los no computador o mais cedo possvel. Pelo contrario, comecandopela interpola cao seria mais difcil conseguir de imediato ensaios no computador, dadoque a aproxima cao de funcoes requer previamente uma base teorica relativamenteaprofundada.


8/236

Pref acio vii

Depois desta escolha, a ordena cao dos restantes captulos torna-se relativa-mente simples. Assim, depois do captulo 2, e logico estudar a resolu cao de sistemasde equacoes, primeiro os lineares e depois os nao lineares, que e o objectivo do captulo3. Os captulos 4 e 5 sao dedicados a teoria da aproxima cao; a interpola cao polinomialno captulo 4 e o ajustamento de funcoes utilizando o criterio dos mnimos quadradosno captulo 5. Os captulos 6 e 7 que tratam repectivamente do c alculo de integrais

e integra cao de equacoes diferenciais baseiam-se fundamentalmente na interpola caopolinomial, fazendo tambem uso de assuntos dos restantes captulos.


9/236

Captulo 1

Teoria dos erros

Neste captulo examinaremos o efeito dos erros de dados e de arredondamentono resultado de um c alculo. Os erros de truncatura ou de metodo ser ao tratados em

pormenor nos restantes captulos por altura do estudo de cada metodo.Este captulo destina-se principalmente a fazer sentir a limita cao do computa-

dor e por conseguinte a necessidade de escolher algoritmos numericamente estaveis.Desta forma, e sendo os computadores o principal meio de c alculo em analise numerica,e consequentemente util perceber como eles operam. Nas seccoes seguintes vamos vercomo os numeros sao representados no computador e estudar os erros provenientesdesta representacao.

1.1 Representa cao dos n umeros no computador

Raramente a base usada no computador e decimal. A maioria dos computa-dores utiliza o sistema numerico binario ou algumas das suas variantes, tais como abase 8 ou a base 16. Como exemplo da representacao binaria e da sua convers ao abase decimal, consideremos

(1101.101)2 = 2 3 + 2 2 + 2 0 + 2 1 + 2 3 = (13 .625)10

O primeiro numero e escrito em base bin aria e o ultimo em decimal.A maioria dos computadores possuem uma representa cao para os numeros

inteiros e outra para os n umeros reais. Actualmente, a representa cao dos reais e feita,quase exclusivamente, sob a forma de vrgula utuante, que constitui uma adapta caoda nota cao cientca dos n umeros. A representa cao em vrgula utuante, como ver-emos mais tarde, permite representar n umeros reais com ordens de grandezas muitodiferentes.

A ttulo de exemplo da representa cao dos numeros em nota cao cientca con-sideremos novamente o n umero 13.625 que se pode exprimir sob a forma

0.13625102ou em base binaria

(0.1101101)2 24

1


10/236

2 1 Teoria dos erros

Com generalidade, seja a base do sistema de numeros utilizada (geralmente =2, 8, 10 ou 16), entao um numero x representado em notacao cientca tem a forma

x = m t = 1em que m e um n umero real designado por mantissa e t e um n umero inteiro designado

por expoente. Fixada a base , esta representacao nao e unica pois, por exemplo, x = 1pode ser escrito na base 2 de varias maneiras,

x = 1 20 = 0 .1 21 = 0 .01 210 = 10 2 1 = 100 2 10(os numeros correspondentes s mantissas e aos expoentes estao escritos em base 2).Para resolver esta ambiguidade e usual adoptar a seguinte conven cao: para um numerox = 0 toma-se a mantissa m de modo a que

1 = (0 .1) m < 1Diz-se neste caso que se usa uma representa cao normalizada . Nesta representa cao a

mantissa de um n umero diferente de zero tem a seguinte formam = 0 .a1a2 . . . a1 = 0

em que os a i sao todos algarismos na base (0 a i 1). Assim, p.ex., o numero1 tem a seguinte forma1 = (0.1) 1

E claro que a nota cao cientca, tal como acabamos de apresentar, n ao podeser implementada em computador, pois para cobrir todos os n umeros reais a mantissae o expoente exigiriam um numero innito de algarismos. Assim a notacao cientca emodicada no sentido de se utilizar um numero nito n de algarismos para a mantissam e connar o expoente t a um intervalo [ t1, t2], obtendo-se a representa cao em vrgula utuante .

Para simplicar a exposi cao usaremos a nota cao V F (,n, t 1, t2) para designaro sistema de representa cao em vrgula utuante constitudo por todos os n umeros reaisx da forma

x = m t 1 m 1 n t1 t t2e ainda x = 0. Assim m tem a seguinte forma

m = 0 .a1a2 . . . a n a1 = 0

Por exemplo o numero x = 0 .13625102e tal que x V F (10, 5, 3, 3) mas x V F (10, 4, 3, 3) ou x V F (10, 5, 3, 1).O ultimo caso e conhecido na literatura inglesa por overow, i.e. , o numero edemasiadamente grande para ser representado naquele sistema.

Notando que a1 = 0, vemos que a mantissa pode tomar ( 1) n 1 valoresdiferentes e portanto o sistema V F (,n, t 1, t2) e constitudo pelo conjunto deN = ( t2 t1 + 1)( 1) n 1


11/236

1.1 Representa c ao dos n umeros no computador 3

Figura 1.1: O sistema V F (2, 4, 1, 2)numeros racionais positivos compreendidos entre

L1 = 1 t 1e

L2 = (1 n ) t 2e ainda pelo conjunto dos n umeros simetricos aos anteriores e o numero zero.

Exemplo 1.1 Concretizar V F (2, 4,

1, 2).

V F (2, 4, 1, 2) designa o sistema de vrgula utuante de base = 2, cuja mantissa mpossui n = 4 algarismos e cujo expoente t pode variar entre t1 = 1 e t2 = 2. Assima mantissa pode tomar neste sistema os seguintes valores:(0.1000)2 = 0 .5000(0.1001)2 = 0 .5625(0.1010)2 = 0 .6250(0.1011)2 = 0 .6875(0.1100)2 = 0 .7500(0.1101)2 = 0 .8125(0.1110)2 = 0 .8750(0.1111)2 = 0 .9375

Atendendo que t pode tomar os valores 2 1, 20, 21, 22, vemos que N = 32, L1 = 0 .25,L2 = 3 .75 e portanto V F (2, 4, 1, 2) e constitudo por 65 numeros que representamosna Figura 1.1.

No VAX, em precis ao simples (32 bits), o sistema numerico utilizado e o

V F (2, 24, (27 1), 27 1) = V F (2, 24, 127, 127)Para este sistema os

N = (28

1) 223

= 2 139 095 040numeros racionais positivos est ao compreendidos entre

L1 = 2 1 2 127 0.29 10 38e

L2 = (1 2 24) 2127 1.7 1038Em precisao dupla (64 bits) o sistema numerico e o

V F (2, 56, (27 1), 27 1) = V F (2, 56, 127, 127)


12/236


comN = (2 8 1) 255 0.92 1019

L1 = 2 128 0.29 10 38L2 = (1 2 56) 2127) 1.7 1038

ou, no caso da variante G _ oating (64 bits), o

V F (2, 53, (210 1), 210 1) = V F (2, 53, 1023, 1023)com

N = (2 11 1) 252 0.92 1019L1 = 2 1024 0.56 10 308

L2 = (1 2 53) 21023 0.90 10308Em precisao qu adrupla (128 bits) o sistema e o

V F (2, 113, (214 1), 214 1) = V F (2, 113, 16383, 16383)com

N = (2 15 1) 2112 1.7 1038L1 = 2 16384 0.84 10 4932

L2 = (1 2 113 ) 216383 0.59 104932

1.2 Erros na representa cao em vrgula utuante

Como acabamos de ver, a representacao em vrgula utuante so permite a

representa cao exacta de alguns n umeros reais, o que implica que em geral tenhamosque aceitar representar numeros reais com um certo erro. P oe-se a seguinte quest ao:dado um n umero real x qual o numero em V F 1, que denotaremos por f l (x), que orepresenta? Se xV F ent ao fazemos fl (x) = x. Se xV F ent ao temos que efectuaro arredondamento de x. Ha dois tipos de arredondamento: o arredondamento porcorte que consiste em escolher para f l (x) o numero mais perto de x entre 0 e x e oarredondamento simetrico que consiste em escolher para f l (x) o numero mais pertode x.

Assim, por exemplo, no sistema V F (10, 2, 2, 2) o numerox = 0 .13625102

sera representado porf l (x) = 0 .13 102 ou f l (x) = 0 .14 102

consoante o arredondamento for por corte ou simetrico. Com generalidade, represen-tando x na nota cao cientca

x = (0.a1a2 . . . a n an +1 . . .) t = 1 a1 = 0 (1.1)1Por comodidade passamos a designar V F (,n, t 1 , t2) por V F sempre que n ao seja necess ario

explicitar os argumentos.


13/236

1.2 Erros na representa c ao em vrgula utuante 5

e supondo que a base e par (normalmente =2,8,10 ou16), temos para o arredonda-mento por corte

f l (x) = (0.a1a2 . . . a n ) t (1.2)e para o arredondamento simetrico

f l (x) =

(0.a1a2 . . . a n )

t 0

an +1 < / 2

f l (x) = (0.a1a2 . . . a n + 0 .00 . . . 1) t / 2 an +1 < em que 0.00 . . . 1 = n .

Exemplo 1.2 Achar as representac oes de: (1) em V F (10, 7, 38, 38), (2) (0.4)10em V F (2, 4, 1, 2), e (3) (0.1)10 no VAX.1. Como

= 3 .1415926535. . .temos que

fl () = 0 .314159210ou

fl () = 0 .314159310consoante o arredondamento for por corte ou simetrico.

2. Como(0.4)10 = (0 .01100110011 . . .)2

temos quefl ((0.4)10) = (0 .1100)2 2 1 = (0 .375)10

ouf l ((0.4)10) = (0 .1101)2 2 1 = (0 .40625)10

consoante o arredondamento for por corte ou simetrico.

3. O VAX trabalha em V F (2, 24, 127, 127), como vimos atras, e com arredonda-mento simetrico. Sendo assim, como(0.1)10 = (0 .000110011 . . .)2

temos que

fl ((0.1)10) = (0 .110011001100110011001101)2 2 (11) 2 (0.100000001490116)10

Acabamos de ver que em geral um numero nao e representado exactamente nocomputador sendo afectado de um certo erro. Para ser mais explicto vamos adoptara seguinte nomenclatura. Sendo x o valor exacto de uma grandeza e x um seu valoraproximado, dene-se erro de x (em relacao a x) como sendo o valor:

ex = x x


14/236


Quando x = 0 podemos calcular ex /x que designamos por x . Podemos ent ao escrever

x x = xx x = x(1 x ) (1.3)Ao valor absoluto de ex e de x correspondem respectivamente o erro absoluto e o errorelativo. Assim, dene-se erro absoluto de x como sendo

|ex | = |x x|e dene-se erro relativo de x como sendo

|x | = |x x||x|

Muitas vezes, designaremos tambem por erro relativo a quantidade x , denida por(1.3). Para alem destas no coes convem-nos ainda introduzir a de algarismo signica-tivo. Para isso consideremos x representado na notacao cientca normalizada, dadapor (1.1), na base decimal.

Denicao 1.1 Diz-se que um dos algarismos a i de x e signicativo se

|ex | 12

10t i

Assim se

|ex | 12

10t n

o n umero x tem n algarismos signicativos relativamente a x.

Exemplo 1.3 Determinar os v arios tipos de erros de = 3 .141592 e o n umero dealgarismos signicativos relativamente a = 3 .1415926535. . ..

Temos quee = 0 .6535 10 6 = e / = 0 .2080 10 6

Dado que |e | > 0.510 6 o ultimo algarismo de nao e signicativo, e portanto sopossui 6 algarismos signicativos. Se fosse 3.141593 ja teria todos os seus algarismossignicativos.

Podemos agora ver qual e o erro absoluto cometido num arredondamento porcorte. Atendendo a (1.1) e (1.2) temos que

ear = x f l (x) = (0.00 . . . 0an +1 . . .) t

= (0.an +1 . . .) t nPor conseguinte temos a seguinte majoracao para o erro absoluto de arredondamento

por corte

|ear | = |x f l (x)| t nDe uma forma semelhante, obtem-se para o erro absoluto de arredondamento simetricoa majora cao

|ear | = |x f l (x)| 12

t n (1.4)


15/236

1.3 Opera c oes aritmeticas em vrgula utuante 7

Vemos que na base 10 o arredondamento simetrico garante que todos os n algarismosde fl (x) sejam signicativos relativamente a x.

As majoracoes apresentadas tem o inconveniente de serem fun cao de t , i.e. ,dependerem da ordem de grandeza de x. Para obviar a este inconveniente vamos obtermajora coes para o erro relativo. De (1.4) temos que

|ar | = |ear ||x| 12

t n 1|x|

= 12 t n

(0.a1a2 . . .) t

12 n

(0.1) = 12

n 1

No caso do arredondamento por corte obteramos o mesmo resultado parte o factor1/2. Portanto o erro relativo de arredondamento ar satisfaz a seguinte majoracao

|ar | = |x f l (x)x | u

u = 1 n arredondamento por corte

u = 12 1 n arredondamento sim etrico

(1.5)

Atendendo a (1.3) podemos escrever

ear = x f l (x) = xar f l (x) = x(1 ar ) |ar | uO u so depende da base , do numero de algarismos n utilizados na mantissa e do tipode arredondamento (por corte ou simetrico). Portanto e uma constante caractersticada maquina utilizada e designa-la-emos por unidade de arredondamento da maquina.Temos assim que, no VAX (arredondamento simetrico)

u = 2 24 0.596 10 7em precisao simples e

u = 2 56 0.139 10 16em precisao dupla (u = 2 53 0.111 10 15 na versao G _ oating) e

u = 2 113 0.096 10 33em precisao qu adrupla . Pode-se portanto garantir a f l (x) quase sempre 7 algarismossignicativos (relativamente a x) em precisao simples e sempre 16 algarismos signi-cativos em precisao dupla (15 na versao G _ oating) e 33 em precisao qu adrupla .

1.3 Opera coes aritmeticas em vrgula utuante

Vejamos sumariamente como e efectuada uma opera cao aritmetica no com-putador. Sejam x e y dois numeros pertencentes a V F e portanto f l (x) = x ef l (y) = y. Pretendemos calcular

z = (x, y) = xy


16/236


em que e uma das operacoes aritmeticas + , , , : . Designando por a opera caoefectuada no computador e por z o resultado desta operacao obtemosz = (x, y) = xy

que geralmente n ao coincide com z. Na maioria dos computadores os c alculos saoefectuados de forma a que z = f l (z). Portanto, dado dois numeros x e y com repre-senta cao exacta no computador temos que

(x, y) (x, y) = (x, y) f l ((x, y)) = (x, y)ar |ar | u (1.6)Vamos exemplicar considerando um computador que funciona em base dec-

imal com o sistema V F (10, 7, 38, 38) e com arredondamento simetrico. Sejamx = 99 .91232 y = 0 .2345271 z = x + y

Ent aof l (x) = 0 .9991232

102 f l (y) = 0 .2345271

100

Antes de efectuar a soma temos que exprimir os dois n umeros de forma a que osseus expoentes coincidam; assim, desnormalizamos a mantissa do n umero com menorexpoente de forma a que este expoente se reduza ao outro. Portanto, temos que

y = 0 .002345271102em que a mantisssa passou a ter 9 algarismos em vez de 7; os algarismos adicionais(neste caso 7 e 1) sao designados por algarismos de guarda . Podemos agora somar asmantissas obtendo

z = (0 .9991232 + 0.002345271)102 = 1 .001468471102De notar que agora a mantissa tem 10 algarismos (3 algarismos de guarda). O re-sultado obtido e exacto, e so agora e que se faz o arredondamento. Assim, obtemosnalmente

f l (z) = 0 .1001468103Se nao tivessemos guardados em y os algarismos de guarda 7 e 1, excedentes namantissa depois da desnormalizacao e tivessemos arredondado para

y = 0 .0023453102ent ao obteramos

x+ y = 0 .1001469

103 = fl (x + y)

Vemos com este exemplo que para garantir (1.6) as opera coes deverao ser efectuadasutilizando algarismos de guarda.

Vejamos outro exemplo: calcular

z = x y x = 0 .1004567 y = 0 .09952144Estamos neste caso a subtrair 2 numeros quase iguais o que e conhecido por cancela-mento subtractivo . Obtemos

z = 0 .00093526


17/236

1.3 Opera c oes aritmeticas em vrgula utuante 9

e portantof l (z) = 0 .935260010 3

Vemos que no caso de cancelamento subtractivo, esta operacao no computador eexacta, i.e. , nao ha erro de arredondamento. No entanto, se os numeros x e y estaoafectados de erros provenientes de c alculos anteriores sua determinacao, ent ao ocancelamento e uma operacao extremamente perigosa visto que o erro relativo doresultado pode ser muito superior aos erros associados a x e a y. Suponhamos que osvalores exactos de x e y sao

x = 0 .100456683 y = 0 .0995214437

e que pretendemos calcular

z = x y = 0 .935239310 3Como

x = fl (x) = 0 .1004567e

y = fl (y) = 0 .09952144o valor calculado sera

z = f l (x y) = 0 .935260010 3Vemos assim que os 3 ultimos algarismos n ao sao signicativos.

Ainda com um computador que funciona em base decimal com o sistemaV F (10, 7, 38, 38) e com arredondamento simetrico, calculemos

1 + u 1 + v

em que

u = 1 / 2 101 7

= 0 .5 10 6

e a unidade de arredondamento e

v = 0 .9u = 0 .45 10 6No 1 caso temos

fl (1 + u) = f l ((0.1 + 0 .00000005)101) = f l (0.10000005101) == 0 .1000001101 = 1 .000001No 2 caso temos

fl (1 + v) = fl ((0.1 + 0 .000000045)101) = f l (0.100000045101) == 0 .100000010

1

= 1Deste exemplo podemos facilmente ver que em geral a unidade de arredondamento eo numero u para o qual

f l (1 + x) = 1 se x uf l (1 + x) = 1 se 0 x < uPor outras palavras, u e o menor numero positivo que adicionado a 1 conduz nocomputador a um resultado diferente de 1. Baseado neste facto apresentamos um al-goritmo que permite determinar o u de um computador que trabalha em base bin aria.


18/236


Algoritmo 1.1 (Determinac ao da unidade de arredondamento u)

INICIALIZAC AO:x = 1

CICLO: PARA k = 0 , 1, . . . FAZER

fazer x = x/ 2, y = x + 1SE y = 1 ENT AO fazer u = 2 x, SAIDA

FIM DO CICLO

1.4 Propaga cao dos erros

1.4.1 Propaga cao dos erros em opera coes elementares

Admitimos que, ao efectuar uma operacao aritmetica no computador, arelacao (1.6) e v alida desde que os operandos x e y sejam representados exactamenteno computador. Em geral quando se pretende determinar

z = (x, y) = xyno computador, o que e de facto calculado e

z = (x, y)em que designa a funcao calculada no computador, como vimos anteriormente, ex = fl (x) e y = f l (y) sao valores aproximados de x e y. Isto pode provir de variassitua coes: (1) x nao e representado exactamente no computador, (2) x e o valor deuma grandeza fsica nao sendo possvel a sua medi cao exacta, (3) x e o resultado decalculos anteriores onde os erros se vao propagando. Temos assim que o erro totalcometido e

ez = (x, y) (x, y) = [(x, y) (x, y)] + [(x, y) (x, y)] (1.7)O 2 termo entre parenteses rectos e o erro de arredondamento que temos vindo aestudar e calcula-se usando (1.6), cando

(x, y) (x, y) = (x, y)ar (x, y)ar |ar | u (1.8)em que a aproxima cao (x, y) (x, y) justica-se por desprezarmos no c alculo deerros termos de ordem superior (supoe-se erros relativos pequenos). O 1 termo entreparenteses rectos e o erro propagado , i.e. , a contribui cao dos erros dos operandos parao erro do resultado da opera cao.

Vejamos como se pode determinar o erro propagado. Recorrendo ao teoremade Lagrange podemos escrever

e = (x, y) (x, y)= [(x, y) (x, y)] + [(x, y) (x, y)]= x (x, y)(x x) + y(x, y)(y y)x (x, y)(x x) + y(x, y)(y y)


19/236

1.4 Propaga c ao dos erros 11

em que x(x, x), y(y, y), x e y sao as derivadas parciais de em ordem a xe a y, respectivamente, e as aproximacoes x(x, y) x (x, y) e y(x, y) y(x, y) justicam-se por desprezarmos novamente termos de ordem superior. Podemos ent aoescrever

e = x (x, y)ex + y(x, y)ey (1.9)Este resultado podia obter-se recorrendo ao desenvolvimento em serie de Taylor emtorno de (x, y) e desprezando termos de ordem superior.

Podemos exprimir a rela cao anterior utilizando erros relativos.

=e

(x, y)=

xx (x, y)(x, y)

.exx

+yy(x, y)(x, y)

.eyy

ou ainda = pxx + pyy (1.10)

onde px =

xx (x, y)

(x, y)

py =yy(x, y)

(x, y)

(1.11)

Os pesos px e py sao designados na literatura por n umeros de condic ao e relacionamo erro relativo da funcao respectivamente com o erro relativo x da vari avel x eo erro relativo y da vari avel y.

Para obtermos o erro propagado em cada uma das opera coes aritmeticas bas-tar a determinar os respectivos n umeros de condicao. Assim teremos sucessivamente.

Multiplica cao: (x, y) = xy. Temos que

x (x, y) = y y(x, y) = x

e portanto px = 1 py = 1

Logo = xy = x + y

Divisao: (x, y) = x/y . Temos que

x(x, y) = 1 /y y(x, y) = x/y 2e portanto

px = 1 py = 1Logo

= x/y = x yAdi cao e subtrac cao: (x, y) = x y. Temos quex (x, y) = 1 y(x, y) = 1

e portanto px = x/ (x y) py = y/ (x y)

Logo = x y =

xx y

x y

x yy


20/236


Nota-se que se utilizarmos (1.9) obtem-se a seguinte relacao muito simples

ex y = ex eyque, neste caso, e exacta mesmo quando nao se desprezam termos de ordem superior.

Estamos agora em condi coes de obtermos o erro total cometido numa opera-cao algebrica (x, y). Com efeito, basta atender a (1.7), (1.8) e (1.10) e utilizarmoserros relativos para obtermos o erro relativo total

z =(x, y) (x, y)

(x, y)= + ar = pxx + pyy + ar |ar | u (1.12)

Acabamos de ver que para as 4 opera coes aritmeticas os n umeros de condicaosao:

(x, y) = xy = px = 1 py = 1

(x, y) = x/y = px = 1 py = 1(x, y) = x y = px = x/ (x y) py = y/ (x y)

Vemos que na multiplicacao e na divisao os erros relativos das parcelas n ao sao au-mentados. Se x e y ou x e y tiverem o mesmo sinal respectivamente para a adi caoou subtrac cao, ent ao os pesos sao em valores absolutos inferiores a 1. Nestes casos oserros nao se propagam fortemente no resultado, sendo as operacoes numericamenteest aveis. Se x e y ou x e y tiverem sinais contr arios respectivamente para a adicaoou subtrac cao, ent ao os pesos sao em valores absolutos superiores a 1 podendo nocaso de x y, na adi cao ou x y, na subtrac cao, atingir valores muito elevados; eo caso do cancelamento subtractivo, ja referido atr as. Neste ultimo caso os erros saomuito ampliados sendo a operacao numericamente instavel.

Exemplo 1.4 Determinar o n umero de algarismos signicativos que se pode garantir a xy, x/y , x + y e x y sendo x = 1010 e y = 1000 , sabendo que todos os algarismos(em n umero de 4) de x e y s ao signicativos. Desprezar os erros de arredondamento.Os erros absolutos |ex | e |ey| sao inferiores a 0.5. Portanto os erros relativos tem asmajora coes2

|x | = |ex |/ |x| |ex |/ |x| 0.5/ 1010 = 0.495 10 3|y| = |ey|/ |y| |ey|/ |y| 0.5/ 1000 = 0.5 10 3

Assim temos que

|xy | = |x + y| |x |+ |y| 0.995 10 3e

|x/y | = |x y| |x |+ |y| 0.995 10 3Como

xy = 1 .010 1062Como se desconhece os valores exactos de x e y utiliza-se os seus valores aproximados x e y. Este

procedimento e habitual e equivale a desprezar no c alculo dos erros termos de ordens superiores.


21/236


ex/ y = 1 .010

temos

|exy | = |xy ||xy| |xy ||xy| 0.995 10 3 1.010 106 = 1 .005 103e

|ex/y | = |x/y ||x/y | |x/y ||x/ y| 0.995 10 3 1.010 = 1.005 10 3Portanto xy e x/ y tem pelo menos 3 algarismos signicativos. Por outro lado

|ex y| = |ex ey| |ex |+ |ey| 0.5 + 0 .5 = 1e como

x + y = 2010

e

x y = 10concluimos que x + y tem tambem 3 algarismos signicativos enquanto que x y temapenas 1 algarismo signicativo.Voltemos ao problema do c alculo aproximado de (x, y) atraves de (x, y),

com x = fl (x) e y = f l (y). Ate agora temos considerado como representando umadas 4 operacoes algebricas, para as quais admitimos que se verica (1.6) ou (1.8), i.e. ,

= f l () (1.13)

Neste caso o termo (x, y) (x, y) em (1.7) deve-se a um unico arredondamentoefectuado pelo computador. A uma operacao que satisfaz (1.13) designamos poroperac ao elementar . As funcoes tais como (x) = x, sin x, cos x, exp x, ln x, etcserao tambem consideradas como opera coes elementares, se bem que (1.13) nao sejarigorosamente satisfeita para estas fun coes.

Para podermos utilizar (1.7) no caso destas fun coes necessitamos de deter-minar o erro propagado (x) (x). Como (x) so depende de x as relacoes (1.9),(1.10) e (1.11) obtidas para (x, y) reduzem-se respectivamente a

e = (x) (x) = (x)ex = pxx (1.14)

px = x (x)(x)

em que (x) e uma derivada total e px e o numero de condicao que relaciona o errorelativo da funcao com o erro relativo x da vari avel x. O erro total ser a dadopor

z =(x) (x)(x)

= + ar = pxx + ar |ar | u (1.15)que e um caso particular de (1.12).


22/236


A seguir apresentamos o n umero de condicao para algumas das operacoesconsideradas elementares

(x) = x = px = x1

2xx = 12(x) = sin x = p

x = x cos xsin x = x cot x

(x) = cos x = px = xsin xcos x = x tan x(x) = exp x = px = x

exp xexp x = x

(x) = ln x = px = x1x

ln x =1

ln x

(1.16)

Vemos que reduz sempre o erro relativo; e pois uma operacao bem condicionada.O sin e mal condicionado para x k, k = 0 (com k inteiro) e |x| 1, visto quepara estes valores de x o numero de condicao px atinge em modulo valores elevados.De igual modo o cos e mal condicionado para x (2k + 1) / 2 e |x| 1, o exp para|x| 1 e o ln para x 1.

Exemplo 1.5 Determinar um majorante para o erro absoluto de z = cosx quandox = 1 .5 com um erro relativo de 0.001 e o c alculo de cos e efectuado por uma m aquina usando o sistema V F (10, 4, 10, 10) com arredondamento por corte.

O valor calculado para o coseno e

z = cosx = f l (0.07073720) = 0.07073

Vamos obter sucessivamente majora coes para os erros relativo e absoluto de z. De(1.14) e (1.16) temos

cos = x tan x x x tan x xe de (1.15) temos

|z| = |cos + ar | |cos|+ |ar |Ent ao, das expressoes anteriores e de (1.5) temos a majora cao

|z | | 1.5tan1 .5 0.001|+ |101 4| = 0 .0212 + 0.001 = 0.0222Como

|ez| = |z||z| |z||z|temos nalmente

|ez| 0.070730.0222 = 0.00157


23/236


1.4.2 Mau condicionamento e estabilidade

Ate agora s o consideramos opera coes elementares isoladas. Suponhamosque pretendemos calcular

z = f (a, b) = a2 b2 = ( a + b)(a b)Podemos faze-lo utilizando sucessivas operacoes elementares. A sequencia como eefectuada estas operacoes constitui um algoritmo . Assim para este exemplo podemosutilizar os 2 algoritmos seguintes:

Algoritmo 1 : Algoritmo 2 :z1 = 1(a) = a a z1 = 1(a, b) = a + bz2 = 2(b) = bb z2 = 2(a, b) = a bz3 = 3(z1, z2) = z1 z2 z3 = 3(z1, z2) = z1 z2

(1.17)

Em qualquer destes algoritmos z3 sera o valor z = f (a, b) pretendido supondo quetodos os calculos foram efectuados sem erros. Quando efectuamos os c alculos com umamaquina ser a que e indiferente o algoritmo escolhido? Vamos ver com um exemplonumerico que de facto o resultado depende da forma como sao efectuadas as contas.

Exemplo 1.6 Comparar os 2 algoritmos dados em (1.17) para determinar z = a2b2com a = 0 .3237 e b = 0 .3134, utilizando uma m aquina com V F (10, 4, 10, 10) earredondamento simetrico. O resultado exacto e z = a2 b2 = 0 .65621310 2.

Algoritmo 1 : Algoritmo 2 :z1 = a a = 0 .1048 z1 = a+ b = 0 .6371z2 = b

b = 0 .9822

10 1 z2 = a

b = 0 .1030

10 1

z1 z2 = 0 .658010 2 z1 z2 = 0 .6562 10 2z = 0.2723210 2 z = 0 .0019810 2

Vemos assim que um dos algoritmos conduziu a um resultado bastante maispreciso do que o outro. Para entender o que se passa vamos determinar uma express aopara o erro correspondente a cada algoritmo. Para isso obtem-se sucessivamente oerro de cada opera cao elementar que constitui o algoritmo em estudo. Assim temospara o Algoritmo 1:

z1 = 1(a) = a a = z1 = a + a + ar 1z2 = 2(b) = bb = z2 = b + b + ar 2z3 = 3(z1, z2) = z1 z2 = z3 = z1z3 z1 z2z3 z2 + ar 3

em que ar 1 ,ar 2 e ar 3 sao os erros de arredondamento cometidos em cada operacaoelementar. Portanto

z3 = 2(z1z3

a z2z3

b) +z1z3

ar 1 z2z3

ar 2 + ar 3


24/236


Atendendo que z1 = a2, z2 = b2 e z3 = a2 b2 obtemosz = f + ar

f = 2a2

a2 b2a 2b

2

a2 b2b

ar = a2

a2

b2 ar 1

b2

a2

b2 ar 2 + ar 3

(1.18)

Da mesma forma para o Algoritmo 2:

z1 = 1(a, b) = a + b = z1 =a

a + ba +b

a + bb + ar 1

z2 = 2(a, b) = a b = z2 = aa ba b

a bb + ar 2z3 = 3(z1, z2) = z1 z2 = z3 = z1 + z2 + ar 3Portanto

z3 = (a

a + b+

a

a b)a + (

b

a + b

b

a b)b + ar 1 + ar 2 + ar 3

Obtemos nalmentez = f + ar

f = 2a2

a2 b2a 2b

2

a2 b2b

ar = ar 1 + ar 2 + ar 3

(1.19)

De (1.18) e (1.19) vemos que o erro relativo z e constitudo por dois termosf e ar com caractersticas diferentes. O primeiro, f , depende dos erros relativos dea e b, argumentos de f , mas nao depende dos erros de arredondamento ar 1 , ar 2 e ar 3provenientes das sucessivas operacoes elementares efectuadas pelo computador. Por

isso este termo, f , e independente do algoritmo escolhido e pode obter-se directamenteutilizando (1.10), como facilmente se depreende. Por outro lado o segundo termo, ar ,e explicitamente independente dos erros dos argumentos de f , e depende dos erros dearredondamento e consequentemente do algoritmo escolhido.

Vamos ver que estes dois tipos de erros, f e ar , estao relacionados respec-tivamente com dois conceitos: condicionamento e estabilidade numerica. O conceitode condicionamento intervem sempre quando um problema consiste em obter um re-sultado z a partir de um conjunto de dados x1, x2, . . . , x m .

Denicao 1.2 Um problema diz-se bem condicionado se pequenos erros nos dadosproduzem pequenos erros no resultado ou de forma equivalente, se uma pequena mu-

danca nos dados produz uma pequena mudanca no resultado. Caso contr ario o prob-lema e mal condicionado.

Consideremos o caso em que z R relaciona-se com x1, x2, . . . , x m atraves de umafuncao f duas vezes continuamente diferenciavel tal que z = f (x1, x2, . . . , x m ). Nestecaso podemos, recorrendo ao desenvolvimento em serie de Taylor e desprezando termosde ordem superior, obter

ef = f (x1, x2, . . . , x m ) f (x1, x2, . . . , xm ) =m

i=1f x i (x1, x2, . . . , x m )ex i


25/236


que e uma generaliza cao de (1.9). Escrevendo esta rela cao em termos de erros relativosobtemos

f =m

i=1 px i x i (1.20)

em que

px i = xif x i (x1, x2, . . . , x m )f (x1, x2, . . . , x m )

Como ja referimos atr as os px i sao os numeros de condicao associados s variaveis xi eindicam como o erro relativo em xi afecta o erro relativo em f . Se um desses numerosem valor absoluto for grande entao o problema e mal condicionado. Se forem todospequenos ent ao o problema e bem condicionado.

No exemplo considerado atr as, quer para o Algoritmo 1 quer para o Algoritmo2 , obtivemos a seguinte express ao

f =2a2

a2

b2 a

2b2

a2

b2 b

Notamos que podiamos ter obtido esta express ao utilizando (1.20). Para b a,como 2a2/ |a2 b2| e 2b2/ |a2 b2| podem tomar valores muito elevados, vemos quef (a, b) = a2 b2 e mal condicionada.O calculo da funcao f no computador e efectuado em varios passos; de forma

que a cada passo k corresponde uma opera cao elementar k a que est a associadoum erro de arredondamento ar k . Assim a funcao f e a composi cao destes k , quedependem do algoritmo escolhido. Admitindo que o c alculo de f e efectuado com spassos, ent ao o erro de arredondamento ar acumulado nestes s passos tem a formageral

ar =s

k=1qkar k qs = 1 (1.21)

em que os pesos q1, q2, . . . , qk 1 dependem do algoritmo escolhido. Se para um certopasso t corresponde um t mal condicionado, ent ao os erros de arredondamentoar 1 , ar 2 , . . . , ar t 1 introduzidos nas operacoes elementares anteriores podem contribuirfortemente para o erro nal; geralmente um ou mais dos q1, q2, . . . , qt 1 tomar a valoresabsolutos grandes.

O erro total z da funcao z = f (x1, x2, . . . , x m ) e dado por

z = f + ar

em que f e ar sao dados respectivamente por (1.20) e (1.21). Sendo assim, temosque

z =m

i=1 px i x i +

s

k=1qkar k (1.22)

Denicao 1.3 Um algoritmo diz-se numericamente inst avel se pelo menos um dospesos px i ou qk , em (1.22), for grande em valor absoluto. Caso contr ario, o algoritmodiz-se numericamente est avel.


26/236


Com este denicao, e obvio que num problema mal condicionado qualquer que seja oalgoritmo escolhido ele sera inst avel.

Para b a, o Algoritmo 1 e inst avel devido ao calculo de z3 = z1 z2, sendo|q1| 1 e |q2| 1

comq1 = z1/z 3 e q2 = z2/z 3

e o Algoritmo 2 e inst avel devido ao calculo de z2 = a b, sendo| pa | 1 e | pb| 1

com pa = a/ (a b) + a/ (a + b) e pb = b/ (a b) + b/ (a + b)

No entanto comparando (1.18) com (1.19) podemos dizer que o Algoritmo 1 e maisinst avel do que o Algoritmo 2 visto que |ar | e muito maior para o 1 algoritmo. Ainstabilidade do Algoritmo 2 deve-se ao facto de

|

f | |

a |e

|

f | |

b|.

Recorrendo a (1.18) e (1.19), podemos obter majoracoes para o erro relativode z quando utilizamos respectivamente os Algoritmo 1 e Algoritmo 2 . Atendendoque

|ar i | u i = 1 , 2, 3em que u e a unidade de arredondamento, designando por |d| e r as quantidadesdenidas respectivamente por

|d| = max( |a |, |b|)e

r = a2

+ b2

|a2 b2|obtemos ent ao para o Algoritmo 1

|z| 2r |d|+ ( r + 1) ue para o Algoritmo 2

|z | 2r |d|+ 3 uPara os valores escolhidos no Exemplo 1.6 temos u = 0 .5 10 3 e r = 30 .9352. Sea e b forem nulo, caso em que a e b sao conhecidos exactamente e s ao representadostambem exactamente no computador, ent ao o resultado utilizando o Algoritmo 2 e muito mais preciso do que utilizando o Algoritmo 1. E o caso considerado noExemplo 1.6 em que o majorante de |z| e respectivamente 1 .5967610 2 e 0.15 10 2 (comparar com os valores 0.27232 10 2 e 0.00198 10 2 de z , obtidosanteriormente naquele exemplo). Se a e b sao conhecidos exactamente mas nao saorepresentados exactamente no computador ent ao temos que |d| u e portanto temospara o Algoritmo 1

|z| (3r + 1) ue para o Algoritmo 2

|z| (2r + 3) u


27/236


Conclumos que mesmo para este caso e prefervel o Algoritmo 2 . Finalmente se a e bvem afectados de erros de dados muito superior a u ent ao |f | |ar | e e praticamenteindiferente escolher um ou outro dos algoritmos.

Vamos a seguir dar um exemplo de um algoritmo para o calculo de uma funcaobem condicionada que e numericamente inst avel e apresentar algoritmos alternativosque sejam est aveis.

Exemplo 1.7 Dado um x 0 pretende-se determinar o valor z = f (x) = 1 cos x.Vericar que este problema e bem condicionado mas que o c alculo de z a partir de1 cos x conduz a um algoritmo numericamente inst avel. Apresentar 2 algoritmosalternativos que sejam est aveis.Como o numero de condicao de f e

px = xf (x)/f (x) = x sin x/ (1 cos x)

e que px 2 para x 0 conclumos que o problema e bem condicionado. Comocos x 1 para x 0 vamos ter um cancelamento subtractivo quando efectuarmos1 cos x e portanto e de esperar que o algoritmo seja numericamente inst avel. Defacto temosz1 = 1(x) = cos x = z1 = x tan xx + ar 1z2 = 2(z1) = 1 z1 = z2 = z11 z1 z1 + ar 2

Por conseguinte

z = xsin x

1 cos xx + cos x1 cos x

ar 1 + ar 2

Vemos que o numero de condicao

q1 = cos x1 cos xpode tomar em m odulo valores extremamente elevados quando for x 0 e porcon-seguinte o algoritmo e numericamente inst avel. Notando que

1 cos x =sin2 x

1 + cos x= 2 sin 2(x/ 2)

deixamos ao leitor o trabalho de apresentar 2 algoritmos est aveis e de vericar qualdestes e o mais est avel.

Vejamos agora um exemplo do c alculo de uma fun cao bem condicionadautilizando um algoritmo que e estavel apesar de ter associada a um dos passos (oprimeiro) uma opera cao elementar mal condicionada.

Exemplo 1.8 Dado um x 1 pretende-se determinar o valor z = f (x), com f (x) =exp(1 x). Vericar que este problema e bem condicionado e que o c alculo de z a partir de exp(1 x) conduz a um algoritmo numericamente est avel apesar de z1 =1(x) = 1 x ser mal condicionada quando x 1 (cancelamento subtractivo).


28/236


Temosz1 = 1(x) = 1 x = z1 = xz1 x + ar 1z2 = 2(z1) = exp(z1) = z2 = z1z1 + ar 2

Por conseguintez =

xx + (1

x)ar 1 + ar 2

Dado que | px | 1 ( px = x), f e bem condicionada. Dado que |q1| 0 (q1 = 1 x)e q2 = 1 o algoritmo e estavel apesar do numero de condicao x/ (1 x) associado a1 tomar valores absolutos elevados.

1.5 Problemas

1. Considere o calculo de w = x + 4 2 para |x| 1.(a) Ser a um problema bem condicionado? Justique. Verique que express ao

que dene w corrresponde um algoritmo instavel.(b) Apresente um algoritmo est avel para o calculo de w e mostre que ele e de

facto est avel.

2. As razes z1 e z2 da equa cao de 2 grau x2 + 2 kx + c = 0 s ao dadas por

z1 = k2 c k z2 = k2 c k(a) Obtenha a expressao do erro relativo z1 de z1.

(b) Justique a armacao seguinte: Quando k |c|, o valor que se obtempara z1 e pouco preciso, o que nao se observa com z2 . Escreva umalgoritmo alternativo do dado e que, nas condicoes anteriores, conduza aum valor mais preciso.

3. Na resolucao de equacoes utilizando a acelera cao de Aitken e necess ario calcular

w1 = ( x2 x1) (x1 x0)ou

w2 = ( x2 2x1) + x0A expressao do erro relativo de w2 e

w2 = f + 2 + ar 3

comf = ( x2x2 2x1x1 + x0x0 )/w

2 = ( 2x1ar 1 + ( x2 2x1)ar 2 )/w(a) Determine w1 .(b) Compare w1 com w2 e diga, justicando sucintamente, qual dos 2 algo-

ritmos prefere para determinar w = w1 = w2, supondo que as iteradas j aest ao perto da solu cao z da equa cao a resolver, i.e. , x2 x1 z.


29/236

1.5 Problemas 21

4. Dado um x 0, pretende-se determinar o valor de z = f (x) = x sin x comum computador que funciona em base decimal com 7 algarismos na mantissa earredondamento simetrico.

(a) Obtenha a expressao do erro z = f + ar .(b) Em face desta express ao diga, justicando, se o problema e bem condi-

cionado e se o algoritmo e numericamente estavel. Note que

1 cosx = x2/ 2(1 + O(x2)) z = x3/ 6(1 + O(x2))Obtenha um majorante do erro relativo de z admitindo que x = 0 .01 erepresentado exactamente nesse computador ( z (1./ 6) 10 6).

5. Conhecido y = cos x, sabe-se que sin x pode ser obtido atraves da expressaoz = 1 y2. Obtenha a express ao do erro z de z. Para valores de x proximosde 0, o que pode armar quanto precis ao do resultado? Justique.

6. A expressaoP = (sin a + cos a + 1) h

permite obter o valor do permetro P de um tri angulo rect angulo, sendo h ocomprimento da hipotenusa e a um dos angulos agudos. Obtenha a expressaodo erro P de P .

7. Suponha a seguinte fun cao

z = f (x) =3x

x2 + ln x

Sabe-se que a unidade de arredondamento do computador e de 0 .5 10 7.(a) Indique a express ao que permita calcular o erro z de z.(b) Compare esta expressao com a que se obtem utilizando f = pxx em que

px e o numero de condicao de f . Justique devidamente.

8. Considere a seguinte express ao:

c = a2 + b2 sin Apresente a express ao que lhe permite calcular o erro c de c.

9. Na resolucao da equacao x2 + 2 x 0.0012345 = 0 somos conduzidos ao calculodex1 = 1.00123451

Suponha que utiliza um computador decimal que opera com 6 dgitos na man-tissa e arredondamento simetrico. Obtenha a express ao do erro x 1 de x1 e digaquantos algarismos signicativos pode garantir a x1. Indique uma f ormula quepermita determinar x1 com maior precisao.


30/236


10. Considere a divisao sintetica de um polinomio p3(x) por x z.a3 a2 a1 a0

z za3 zb2 zb1a3 b2 b1 b0 0

Pretende-se determinar o erro dos coecientes b1 e b2 provocados pelo erro daraiz z de p3(x).

(a) Obtenha as expressoes dos erros de b1 e b2.(b) Considerando os ak exactos determine um majorante do erro de b2.

11. E usual no computador determinar c (c > 0) a partir da sucess aoxm +1 = ( xm + c/x m )/ 2 m = 0 , 1, . . . x0 > c

Suponha que o computador opera na base 10 com 7 algarismos na mantissa earredondamento simetrico.

(a) Obtenha a expressao do erro xm +1 em funcao de xm , c e dos erros dearredondamento.

(b) Admitindo que m e sucientemente grande de modo a que xm c, esupondo que c 4 e representado exactamente no computador, determinequantos algarismos signicativos pode garantir a aproxima cao xm +1 de c.12. Sendo x 1, pretende-se calcular z = f (x) = x(x21)1/ 2 com um computadorque funciona em base decimal com 9 algarismos na mantissa e arredondamento

simetrico. Nestas condicoes a expressao do erro e

z

f

x2[ar 1 + ar 2 + 2 ar 3 ] + ar 4

(a) Determine f . Diga se o problema e bem condicionado e se o algoritmo eest avel. Justique.

(b) Supondo que x = 10 3 e representado exactamente nesse computador, de-termine o numero de algarismos signicativos que pode garantir ao valorcalculado z. Apresenta um algoritmo estavel, justicando a sua escolha.

13. Considere o calculo de z = f (x,y,u ) = u(x y) que pode ser feito utilizando 2algoritmos diferentes:w1 = ( x y) u w2 = u x u y

A expressao do erro para o primeiro algoritmo e w1 = f + ar 1 + ar 2 com

f = u +x

x yx

yx y

y

(a) Determine w2 .(b) Supondo agora que u, x e y sao representados exactamente no computador,

encontra condi coes para as quais um (qual?) dos algoritmos e prefervel aooutro. Em que condi coes e indiferente utilizar um ou outro destes algorit-mos.


31/236

1.5 Problemas 23

14. Considere o calculo de z = f (x, y) = x2 y2 que pode ser feito utilizando 3algoritmos diferentes:w1 = x x y y w2 = ( x + y) (x y) w3 = ( x + y) x (x + y) yAs expressoes dos erros para os 2 primeiros algoritmos sao

w1 = f + 1 w2 = f + 2

comf = 2x

2

x2 y2x 2y

2

x2 y2y

1 = x2

x2 y2ar 1 y

2

x2 y2ar 2 + ar 3

2 = ar 1 + ar 2 + ar 3

(a) Determine w3 .(b) Supondo agora que x e y sao representados exactamente no computador,

encontra para cada algoritmo condicoes para as quais este algoritmo emelhor do que os outros.


32/236


33/236

Captulo 2

Equacoes nao lineares

2.1 Introdu cao

Neste captulo apresentamos os principais metodos iterativos para a reso-lucao de equacoes nao lineares a uma vari avel (o estudo de sistemas de equa coesnao lineares e adiado para o Captulo 3). Obter solu coes de uma equacao e um dosproblemas que surge com maior frequencia nas aplicacoes, especialmente quando aequacao e algebrica. Por isso, reservamos a parte nal deste captulo ` a determina caodos zeros de polinomios.

Depois de apresentarmos um exemplo simples e alguns conceitos dos meto-dos iterativos faremos o estudo dos metodos da bissecc ao, falsa posic ao, secante ede Newton . A seguir faremos o estudo geral dos metodos iterativos do ponto xo auma vari avel. Esta generaliza cao tem como objectivos enquadrar os v arios metodos

anteriores e prepararmo-nos para o estudo, no Captulo 3, dos metodos iterativospara a resolu cao de sistemas de equa coes. Aproveitando este contexto mais geralestudaremos uma tecnica de acelera cao dos metodos de convergencia linear, e ap-resentaremos criterios de paragem das itera coes. Finalmente, particularizaremos ometodo de Newton a resolucao de equacoes polinomiais e chamaremos a aten cao dealgumas diculdades levantadas na resolu cao numerica das mesmas.

Se pretendermos obter as solu coes de uma equacao algebrica do segundo grau,ax 2 + bx + c = 0, basta utilizar a conhecida formula resolvente

x = [bb2 4ac]/ (2a)Para equa coes algebricas de grau 3 ou 4 ainda e possvel obter formulas resolventes,se bem que mais complicadas; mas para a equa cao geral de grau n com n > 4 Ga-lois demonstrou em 1832 que e impossvel obter f ormulas resolventes que permitamdeterminar directamente as solu coes da equacao algebrica.

As equacoes algebricas de grau superior a quatro bem como as equacoestranscendentes (p. ex. x = 2 sin x ) sao resolvidas numericamente por metodositerativos. Num metodo iterativo come ca-se com uma aproxima cao inicial x0 da raizz (solucao da equacao) a partir da qual se obtem outra aproxima cao x1, desta obtem-seoutra aproximacao x2 e assim sucessivamente. Um metodo iterativo consiste portantoem obter uma sucess ao de valores x0, x1, x2, . . . que se pretende que tenha como limite

25


34/236

26 2 Equac oes n ao lineares

uma raiz z da equa cao. O processo iterativo prolonga-se ate uma aproxima cao xmsatisfazer a precis ao pretendida a partida.

Uma equa cao nao linear pode genericamente escrever-se sob a forma

f (x) = 0 (2.1)

com f : D R, em que D R e o domnio de f . Para ilustrar o conceito de ummetodo iterativo para a resolu cao de (2.1), comecamos com um exemplo. Considere-mos a resolucao de

f (x) = x2 apara um dado a > 0. Este problema tem uma aplicacao pratica no computador paraa obten cao da raiz quadrada de um numero.

Seja x0 a uma aproxima cao da solucao da equa cao. Ent aox0 a a/x 0 ou a/x 0 a x0

E de admitir entao que

x1 = ( x0 + a/x 0)/ 2constitui uma melhor aproxima cao de a do que x0. Assim, um possvel metodoiterativo para determinar a consiste em utilizar a rela cao anterior indenidamente,i. e., fazer1

xm +1 = ( xm + a/x m )/ 2 m = 0 , 1, 2, . . . (2.2)

Para este metodo ser de alguma utilidade a sucess ao x0, x1, x2, . . . deveraconvergir para o zero z = a de f , i.e. , o erro

em = z xmdevera tender para zero quando m tender para innito. Comecemos por relacionar oerro em duas itera coes sucessivas. Temos que

em +1 = a (xm + a/x m )/ 2 = (2ax m x2m a)/ (2xm )e portanto

em +1 = e2m / (2xm ) (2.3)Se x0 > 0 entao de (2.2) vemos que xm > 0 para qualquer m 0 e portanto de (2.3)concluimos que em 0 para qualquer m > 0, i.e. , xm a para qualquer m > 0.Escrevemos (2.3) na forma

em +1 = em (1 a/x m )/ 2Dado que 0 (1 a/x m ) < 1 para m > 0 vemos que

|em +1 | |em / 2| m = 1 , 2, . . .e portanto em 0. Concluimos assim que a sucessao {xm}dada por (2.2) convergepara z = a se x0(0, ).

Depois de vericar a convergencia de um metodo iterativo temos que exami-nar a sua rapidez de convergencia.

1Mais tarde veremos que este metodo iterativo corresponde ` a aplica cao do metodo de Newton.


35/236

2.2 Metodos da bissec c ao e da falsa posi c ao 27

Denicao 2.1 Seja {xm}uma sucess ao que converge para z e em = z xm . Seexistirem reais p 1 e K > 0 tais quelim

m |em +1 |/ |em | p = K (2.4)ent ao a sucess ao {xm}converge para z com convergencia de ordem p. A K chama-se coeciente assint otico de convergencia. Se p = 1 a convergencia e linear; se p > 1a convergencia e supralinear e no caso de p = 2 a convergencia e quadr atica.

O coeciente assint otico de convergencia K mede a rapidez de convergencia quandom for sucientemente grande, i.e. ,

|em +1 | K |em | p m 1Pode ser difcil determinar K . De (2.4) facilmente se verica que existe K > K tal que

|em +1 | K |em | p m 0 (2.5)A desigualdade (2.5) pode ser util quando se pretende obter uma majora cao do erro

em +1 e e as vezes mais facil de obter do que o coeciente assintotico de convergencia;neste caso K constitui um majorante de K . No entanto K pode tomar valoresbastantes superiores a K e portanto e importante a determina cao do coecienteassint otico de convergencia.

Usando (2.3) e a Denicao 2.1 vemos que o metodo denido por (2.2) ede convergencia quadratica, com K = 1 / (2a). O exemplo considerado ilustra aconstru cao de um metodo iterativo para resolver uma equa cao nao linear e a analiseda sua convergencia. Esta an alise inclui a prova da convergencia sob certas condicoes(no exemplo, x0(0, )) e a determina cao da ordem da convergencia.

2.2 Metodos da bissec cao e da falsa posi caoOs dois metodos apresentados a seguir baseiam-se no seguinte corolario do

teorema do valor intermedio:

Teorema 2.1 Dado um intervalo I = [a, b] e uma func ao f que satisfaz as condic oes:

f contnua em [a,b] (2.6)

f (a)f (b) < 0 (2.7)ent ao a equac ao

f (x) = 0tem pelo menos uma soluc ao z em (a, b).

E facil de ver que (2.7) nao garante por si s o a existencia de uma raiz z. Para aplicaros metodos da bissec cao e da falsa posicao basta que se verique (2.6) e (2.7). Se f satisfazer, alem disso, a condicao:

f existe, e contnua e n ao se anula em (a, b)

conclui-se entao, usando o teorema de Rolle, que a solucao z e unica em (a, b).


36/236


2.2.1 Metodo da bissec cao

Suponhamos que a fun cao f satisfaz as condicoes (2.6) e (2.7), entao estafuncao possui pelo menos um zero z no intervalo I = [a, b]. O metodo da bissecc aoconsiste em construir subintervalos I m = [am , bm ]I = [a, b] por divisoes sucessivasa meio e relativamente aos quais tambem se verica a condicao (2.7). Deste modo

vamos connando um zero da fun cao f a intervalos t ao pequenos quanto desejarmos.Concretizando, ponhamos

I m = [am , bm ] m = 0 , 1, 2, . . .

em que a0 = a e b0 = b e seja xm +1 o ponto medio do intervalo I m , i.e. ,

xm +1 =am + bm

2

Consideremos as tres situa coes seguintes . Se f (xm +1 ) = 0 ent ao xm +1 e um zero e oprocesso iterativo termina. Se f (am ) e f (xm +1 ) tiverem sinais diferentes fa ca-se

am +1 = am e bm +1 = xm +1

de modo a que o novo subintervalo contenha um zero de f . Se pelo contrario foremf (bm ) e f (xm +1 ) a ter sinais diferentes ent ao ponha-se

am +1 = xm +1 e bm +1 = bm

Deste modo garante-se que o novo subintervalo I m +1 = [am +1 , bm +1 ] contem pelomenos um zero de f . Pela forma como foi construdo, este subintervalo tem umcomprimento que e metade do subintervalo que o precedeu. Portanto

bm +1

am +1 =1

2(bm

am ) (2.8)

Por outro lado, sendo z um zero localizado em I m +1 , temos que

|z xm +1 | |xm +1 xm |A Figura 2.1 ilustra esquematicamente a aplica cao do metodo.

Fa camos agora o estudo da convergencia do metodo da bissec cao. Como nointervalo I m est a localizado pelo menos um zero z e xm +1 e o ponto medio desteintervalo ent ao

|em +1 | (bm am )/ 2 m = 0 , 1, 2, . . .em que em = z xm . Aplicando sucessivamente (2.8) obtemos|em | (ba)/ 2m m = 0 , 1, 2, . . . (2.9)em que, para o caso de m = 0, se considera que x0 e um dos extremos de I . Vemosassim que o metodo e convergente. Da Denicao 2.1 nao podemos concluir que ometodo da bisseccao e de convergencia linear. No entanto podemos compara-lo comos metodo de convergencia linear. Vimos da Deni cao 2.1 que se um metodo possuiconvergencia linear entao

|em | K |em 1| m = 1 , 2, . . .


37/236


Figura 2.1: Exemplo do metodo da bisseccao

em que K e um majorante do coeciente assintotico de convergencia K . Aplicandom vezes esta desigualdade obtemos

|em | K m |e0|Notando que |e0| = |z x0| (ba) se x0[a, b] e z[a, b], vemos que quando ummetodo converge linearmente ent ao existe um K tal que

|em

| K m (b

a)

Comparando com (2.9), vemos que o metodo da bisseccao comporta-se de uma formaparecida com metodos de convergencia linear com o coeciente assint otico de con-vergencia igual a 1/2.

Apresentamos a seguir um algoritmo e um exemplo de aplicacao do metododa bisseccao.

Algoritmo 2.1 (Metodo da bissecc ao)

NOTA: Condic ao suciente de convergencia do metodo: f e contnua em

[a, b] e tal que f (a)f (b) < 0.INICIALIZAC AO:

a0 = a , b0 = b , x0 = bCICLO: PARA m = 0 , 1,... FAZER

xm +1 = am + bm2SE |xm +1 xm | OU f (xm +1 ) = 0ENT AO fazer raiz = xm +1 , SAIDA


38/236


SE f (xm +1 )f (am ) < 0ENT AO fazer am +1 = am , bm +1 = xm +1SENAO fazer am +1 = xm +1 , bm +1 = bm

FIM DO CICLO.

Tabela 2.1: Exemplo do metodo da bisseccao para x2 2 = 0m am 1 bm 1 xm f (xm ) em

1 0.000000 2.000000 1.4142140 2.000000 2.000000 0.5857871 x 1 x0 1.000000 1.000000 0.4142142 x1 x0 1.500000 0.250000 0.0857873 x1 x2 1.250000 0.437500 0.1642144 x3 x2 1.375000 0.109375 0.0392145 x4 x2 1.437500 0.066406 0.0232876 x4 x5 1.406250 0.022461 0.0079647 x6 x5 1.421875 0.021729 0.0076628 x6 x7 1.414063 0.000427 0.0001519 x8 x7 1.417969 0.010635 0.00375610 x8 x9 1.416016 0.005100 0.00180311 x8 x10 1.415039 0.002336 0.00082612 x8 x11 1.414551 0.000954 0.00033713 x8 x12 1.414307 0.000263 0.00009314 x8 x13 1.414185 0.000082 0.00002915 x14 x13 1.414246 0.000091

0.000032

16 x14 x15 1.414215 0.000004 0.00000217 x14 x16 1.414200 0.000039 0.00001418 x17 x16 1.414207 0.000017 0.00000619 x18 x16 1.414211 0.000006 0.000002

Exemplo 2.1 Determinar, pelo metodo da bissecc ao (Algoritmo 2.1), a raiz positiva da equac ao f (x) = x2 2 = 0 com um erro inferior a = 5 E 6, usando ocomputador 2 em precis ao simples. Tomar a = 0 , b = 2 .Este exemplo e escolhido pela sua simplicidade e por se conhecer a solucao exactaque e z = 2 = 1.41421356 (com 9 algarismos signicativos). Tomando I = [0, 2]vericamos que f (0)f (2) < 0 e comof e contnua em I temos a garantia que o metodoconverge. Apresenta-se na Tabela 2.1 os resultados. Desta tabela ve-se que x8 e umamelhor aproxima cao de z do que x9, x10 , x11 , x12 . Comparando f (x7) = 0 .021729 comf (x8) = 0.000427 era de esperar que z estivesse muito mais perto de x8 do que dex9 = ( x7 + x8)/ 2. Assim, se alem do sinal utilizarmos o pr oprio valor de f (xm ) e de

2Rede do CIIST constituida por VAXs 750 e 780.


39/236


esperar que obtenhamos metodos com convergencia mais r apida do que a do metododa bisseccao. Um desses metodos e o da falsa posi cao que estudaremos a seguir.

Este exemplo permite real car duas caractersticas importantes do metododa bisseccao. A primeira e a de que a convergencia podera ser bastante lenta. Asegunda e a de que a convergencia e certa quando f satisfaz as condicoes (2.6) e(2.7), i.e. , quando f e contnua num intervalo [ a, b] e f (a)f (b) < 0. Como e frequentevericar-se estas condi coes, o metodo da bissec cao e por vezes utilizado como fasepreparatoria de localizacao de zeros num intervalo mais ou menos pequeno que tornepossvel o arranque de outros metodos mais r apidos mas cuja convergencia pode estarcondicionada a uma relativamente boa aproxima cao inicial do zero.

2.2.2 Metodo da falsa posi cao

Como ja referimos, a unica informa cao sobre a funcao f que o metodo dabisseccao utiliza e o seu sinal, o que e muito pouco. E de esperar que, se recorrermosa mais informa cao sobre o andamento de f , possamos conceber metodos mais r apidos.Tal como para o metodo da bisseccao, consideremos no metodo da falsa posic ao umafuncao f que satisfaz, no intervalo I m = [am , bm ], as condicoes (2.6) e (2.7). Nesseintervalo f (x) e aproximado pela secante

p1(x) = f (bm ) +f (bm ) f (am )

bm am(x bm ) (2.10)

que passa pelos pontos ( am , f (am )) e (bm , f (bm )) (como veremos mais tarde p1 e umpolinomio interpolador de f ). O zero xm +1 de p1 constitui uma aproximacao do zeroz de f . Ent ao, se zermos em (2.10) x = xm +1 obtemos

p1(xm +1 ) = 0 = f (bm ) +f (bm )

f (am )

bm am (xm +1 bm ) (2.11)e portanto

xm +1 = bm f (bm )bm am

f (bm ) f (am )(2.12)

Fazendo am +1 = xm +1 ou bm +1 = xm +1 e mantendo o outro extremo do intervaloinalterado consoante for f (xm +1 )f (bm ) < 0 ou f (am )f (xm +1 ) < 0, e procedendo deigual modo podemos obter nova aproximacao do zero z. Apresentamos a seguir umalgoritmo do metodo.

Algoritmo 2.2 (Metodo da falsa posi c ao)

NOTA: Condic ao suciente de convergencia do metodo: f e contnua em[a, b] e tal que f (a)f (b) < 0.

INICIALIZAC AO:a0 = a , b0 = b , x0 = b

CICLO: PARA m = 0 , 1,... FAZER

xm +1 = bm f (bm ) bm amf (bm ) f (am )


40/236


SE |xm +1 xm | OU f (xm +1 ) = 0ENT AO fazer raiz = xm +1 , SAIDA

SE f (xm +1 )f (am ) < 0ENT AO fazer am +1 = am , bm +1 = xm +1SENAO fazer am +1 = xm +1 , bm +1 = bm

FIM DO CICLO.

Notando que xm +1 e a abcissa do ponto de intersec cao do eixo dos x coma recta que passa pelos pontos ( am , f (am )) e (bm , f (bm )), construimos um esbo co,representado na Figura 2.2, que permite visualizar o metodo da falsa posi cao. Desta

Figura 2.2: Exemplo do metodo da falsa posicao

gura vemos que para o caso nela representado tem-se am +1 = am para m 1.Isto deve-se ao facto de f (x) nao mudar de convexidade em [a1, b1], i.e. , f (x) = 0em (a1, b1). Em geral, sempre que tenhamos f (x) = 0 num intervalo aberto I r comextremos a r e br , sendo r 0, entao verica-se que

f (x)f (a r ) > 0 xI r = am +1 = am m rou

f (x)f (br ) > 0 xI r = bm +1 = bm m rAssim se f (x) = 0 em (a, b) o metodo iterativo da falsa posicao exprime-se por

xm +1 = xm f (xm )xm w0

f (xm ) f (w0)m = 0 , 1, . . . (2.13)

em que w0 = a, x0 = b se f (x)f (a) > 0 e w0 = b, x0 = a se f (x)f (b) > 0 comx(a, b).

Exemplo 2.2 Determinar, pelo metodo da falsa posic ao (Algoritmo 2.2), a raiz pos-itiva da equac ao f (x) = x2 2 = 0 com um erro inferior a = 5 E 6, usando ocomputador em precis ao simples. Tomar a = 0 , b = 2 .


41/236


Este exemplo coincide com o escolhido anteriormente na ilustracao do metodo dabisseccao. Os resultados est ao apresentados na Tabela 2.2. Neste caso bm = 2 , m 0. Notando que a razao |em /e m 1| dos sucessivos erros e praticamente constante,conclui-se da denicao 2.1 que a convergencia e linear com um coeciente assintoticode convergencia K 0.17. Vemos que neste exemplo o metodo da falsa posi caoconduz a uma convergencia linear mais rapida do que o da bisseccao, visto o coecienteassint otico de convergencia ser inferior a 1/ 2. Nem sempre ao metodo da falsa posi caocorresponde uma convergencia mais rapida que ao metodo da bisseccao; se no exemploconsiderado tivessemos escolhidos b = 6 um majorante para o coeciente assint oticode convergencia seria 0 .62 > 0.5.

Tabela 2.2: Exemplo do metodo da falsa posicao para x2 2 = 0m am 1 bm 1 xm f (xm ) em em /e m 1

1 0.000000 2.000000 1.4142140 2.000000 2.000000 0.5857871 x 1 x0 1.000000

1.000000 0.414214

0.7071

2 x1 x0 1.333333 0.222222 0.080880 0.19533 x2 x0 1.400000 0.040000 0.014214 0.17574 x3 x0 1.411765 0.006920 0.002449 0.17235 x4 x0 1.413793 0.001189 0.000420 0.17176 x5 x0 1.414141 0.000204 0.000072 0.17167 x6 x0 1.414201 0.000035 0.000012 0.17228 x7 x0 1.414211 0.000006 0.000002 0.17479 x8 x0 1.414213 0.000001 3.82E 7 0.1760

Para compreender o comportamento da convergencia do metodo da falsaposicao, e necessario uma formula que relacione os erros em itera coes sucessivas.Vimos que o metodo da falsa posi cao baseia-se na aproxima cao da funcao f pelopolinomio interpolador p1 dado por (2.10). No estudo da interpolacao polinomialveremos que

f (x) = p1(x) +12

f (m )(x am )(x bm ) (2.14)em que p1 e dado por (2.10) e m e um real compreendido entre o mnimo de {am , bm , x}e o maximo de {am , bm , x}o que passamos a partir de agora a representar por m int( am , bm , x). Note-se que se zermos tender bm para am , ent ao (2.14) reduz-se aconhecida formula de Taylor

f (x) = f (am ) + f (am )(x am ) + 12f (m )(x am )2em que m int( am , x). Fazendo em (2.14) x = z, sendo z um zero de f , temos

f (z) = 0 = f (bm ) +f (bm ) f (am )

bm am(z bm ) +

12

f (m )(z am )(z bm ) (2.15)em que m int( am , bm , z). Utilizando novamente (2.11)

p1(xm +1 ) = 0 = f (bm ) +f (bm ) f (am )

bm am(xm +1 bm )


42/236


e subtraindo a (2.15), obtemos

f (bm ) f (am )bm am

(z xm +1 ) +12

f (m )(z am )(z bm ) = 0 (2.16)Atendendo ao teorema de Lagrange, temos que

f (bm ) f (am )bm am

= f (m )

em que m (am , bm ). Portanto, de (2.16) temos nalmente que

z xm +1 = f (m )2f (m )

(z am )(z bm ) (2.17)em que m (am , bm ) e m int( am , bm , z).

Como vimos, quando f (x) = 0 em (a, b), um dos extremos am ou bm

imobiliza-se. Tal como em (2.13) designamos este extremo por w0. Assim, com estacondicao, se em (2.17) substituirmos am e bm por w0 e xm , obtemos

em +1 = [f (m )2f (m )

(z w0)]emem que m int( w0, xm ), m int( w0, xm ) e em = z xm . Com a condicao consider-ada, f (x) = 0 em (a, b), o termo entre chavetas e sempre diferente de zero e portantoa convergencia do metodo e s o linear. Como ja referimos atr as, se w0 estiver muitoafastado de z, o coeciente assintotico de convergencia pode ser maior do que 1/2.

Como acabamos de ver, o metodo da falsa posi cao tende a desenvolver uma

convergencia lenta quando um dos extremos am ou bm se imobiliza. Para evitar esteinconveniente pode usar-se a seguinte modicacao. Suponhamos para exemplicarque bm = bm 1. Ent ao, em vez de se empregarem os pontos (am , f (am )) e (bm , f (bm ))para tracar a secante, utilizam-se os pontos ( am , f (am )) e (bm , f (bm )/ 2). A gura 2.3mostra qualitativamente o efeito produzido por esta modica cao. Convem realcar quea secante continua a ser denida por um ponto acima e outro abaixo do eixo dos xtal como na vers ao original. Para melhor compreensao deste metodo apresentamos aseguir um algoritmo e um exemplo.

Algoritmo 2.3 (Metodo da falsa posi c ao modicado)

NOTA: Condic ao suciente de convergencia do metodo: f e contnua em[a, b] e tal que f (a)f (b) < 0.

INICIALIZAC AO:a0 = a , b0 = b , x0 = b , F = f (a0) , G = f (b0)

CICLO: PARA m = 0 , 1,... FAZER

xm +1 = bm G bm amG F SE |xm +1 xm | OU f (xm +1 ) = 0


43/236


44/236


a raiz positiva da equac ao f (x) = x2 2 = 0 com um erro inferior a = 5 E 6,usando o computador em precis ao simples. Tomar a = 0 , b = 2 .Comparando os resultados apresentados na Tabela 2.3, com os anteriormente obtidosquando da utilizacao do metodo da falsa posi cao (Tabela 2.2), notamos um ligeiroaumento na rapidez de convergencia.

2.3 Metodos da secante e de Newton

2.3.1 Metodo da secante

Tal como no metodo da falsa posi cao, no metodo da secante o zero z def e aproximado pelo zero xm +1 da secante p1 que passa pelos pontos ( am , f (am )) e(bm , f (bm )) e cuja equacao e dada por (2.10). O valor de xm +1 e, como vimos, dadopor (2.12). A diferenca deste metodo relativamente ao anterior e que n ao se impoe

que f (am )f (bm ) < 0 e portanto xm +1 pode nao estar contido em ( am , bm ) o que podeter como consequencia que o metodo da secante divirja em certos casos. Fazendo em(2.12) am = xm 1 e bm = xm , obtemos o metodo da secante

xm +1 = xm f (xm )xm xm 1

f (xm ) f (xm 1)m = 0 , 1, . . . (2.18)

em que x 1 e x0 sao dados. Quando converge, o metodo da secante, normalmente,converge mais rapidamente do que o da falsa posi cao devido ao facto de am e bmtenderem ambos para z. Ilustramos o metodo da secante na Figura 2.4.

Figura 2.4: Exemplo do metodo da secante

Para obter uma formula dos erros basta utilizar (2.17) e substituir nessarelacao am e bm por xm 1 e xm . Obtemos

em +1 = f (m )2f (m )

em 1em (2.19)


45/236

2.3 Metodos da secante e de Newton 37

em que m int( xm 1, xm ) e m int( xm 1, xm , z). Com esta f ormula e possvel fazerum estudo da convergencia do metodo da secante.

Teorema 2.2 Seja f uma func ao duas vezes continuamente diferenci avel numa viz-inhan ca de um zero z e tal que f (z) = 0 . Ent ao se os valores iniciais x 1 e x0 s aoescolhidos sucientemente perto de z, a sucess ao

{x

m}denida por (2.18) converge

para z.

Demonstra c ao: Escolhemos uma vizinhan ca I = [z , z + ] ( > 0) de z suciente-mente pequena de modo que

M =maxxI |f (x)|2minxI |f (x)|

existe eM

< 1 (2.20)

Ent ao, atendo a (2.20), para todos os xm 1, xm I temos que

|em +1 | M |em 1||em | (2.21)Notando que |em | quando xm I , de (2.20) e (2.21) temos que

|em +1 | |em | (2.22)e

|em +1 | < e portanto xm +1 I . Concluimos por indu cao que se x 1, x0I e a condicao (2.20)e satisfeita entao: para qualquer m 1, xm I e (2.22) e vericada. Se utilizarmos(2.22) m vezes obtemos

|em | m |e0|donde concluimos que limm |em | = 0, visto que por hip otese < 1.

Teorema 2.3 Nas condic oes do Teorema 2.2 a ordem de convergencia do metodo da secante e p = (1 + 5)/ 2 1.618.

Teorema 2.4 Se f C k([a, b]), z (a, b) e f (z) = f (z) = = f (k 1) (z) =0 e f (k)(z) = 0 , i.e., se f tiver um zero de multiplicidade k, ent ao o metodo da

secante converge linearmente desde que x 1 e x0 estejam sucientemente perto de ze localizados ambos de um mesmo lado dez.

Podemos agora apresentar um algoritmo para o metodo em estudo.

Algoritmo 2.4 (Metodo da secante)


46/236


47/236

2.3 Metodos da secante e de Newton 39

2.3.2 Metodo de Newton

Tal como nos metodos precedentes, aproximamos o gr aco de y = f (x) navizinhan ca de xm por uma fun cao linear (recta), mas agora utilizando uma tangenteem vez de uma secante. Tomamos o zero xm +1 da funcao linear para aproximacao dozero z da funcao dada f . Obtem-se assim o metodo iterativo de Newton (Figura 2.5)

xm +1 = xm f (xm )f (xm )

m = 0 , 1, . . . (2.23)

De notar que o metodo da secante esta relacionado com o de Newton visto que

Figura 2.5: Metodo de Newton

f (xm ) f (xm ) f (xm 1)

xm xm 1quando xm 1 xm .

O metodo de Newton e o mais conhecido para determinar as raizes de umaequacao. Nao e sempre o melhor metodo para um determinado problema, mas a suaformula simples e a sua grande rapidez de convergencia fazem dele o metodo quegeralmente se utiliza em primeiro lugar para resolver uma equa cao.

Uma outra maneira de obter (2.23), e utilizar a f ormula de Taylor. Desen-volvemos f (x) em torno de xm ,

f (x) = f (xm ) + f (xm )(x xm ) +12

f (m )(x xm )2

com m int( x, x m ). Fazendo x = z, com f (z) = 0, e resolvendo em ordem a zobtemosz = xm

f (xm )f (xm )

f (m )2f (xm )

(z xm )2 (2.24)


48/236


com m int( z, xm ). Desprezando o ultimo termo, vamos obter a aproxima cao xm +1dada por (2.23). Entao, subtraindo (2.23) a (2.24), chegamos `a seguinte formula doserros

em +1 = f (m )2f (xm )

e2m (2.25)

com m

int( z, xm ), em que se pode notar a semelhan ca com a formula dos erros dometodo da secante (2.19). A formula (2.25) vai ser usada para concluir que o metodode Newton, sob certas condi coes, tem uma convergencia quadratica, p = 2.

Teorema 2.5 Seja f uma func ao duas vezes continuamente diferenci avel numa viz-inhan ca de um zero z e tal que f (z) = 0 . Ent ao se o valor inicial x0 e escolhidosucientemente perto de z, a sucess ao {xm} denida por (2.23) converge para z.Alem disso,

limm

z xm +1(z xm )2

= f (z)2f (z)

(2.26)

e portanto o metodo de Newton tem convergencia quadr atica.

Demonstra c ao: Escolhemos uma vizinhan ca I = [z , z + ] ( > 0) de z suciente-mente pequena de modo queK =

maxxI |f (x)|2minxI |f (x)|

existe eK < 1 (2.27)

Ent ao, atendo a (2.25), para todo o xm

I temos que

|em +1 | Ke 2m (2.28)Notando que |em | quando xm I , de (2.27) e (2.28) temos que

|em +1 | |em | (2.29)e

|em +1 | < e portanto xm +1 I . Concluimos por indu cao que se x0 I e a condicao (2.27) esatisfeita entao: para qualquer m

0, xm

I e (2.29) e vericada. Se utilizarmos(2.29) m vezes obtemos

|em | m |e0|donde concluimos que limm |em | = 0, visto que por hip otese < 1. Em (2.25) mest a entre z e xm e portanto m z quando m . Logo

limm

z xm +1(z xm )2

= limm f (m )2f (xm )

= f (z)2f (z)

e portanto (2.26) ca provada.


49/236


50/236


2.3.3 Criterio de convergencia para os metodos da secante ede Newton

Dado que os Teoremas 2.2 e 2.5 sao de difcil aplica cao, vamos apresentarum conjunto de condic oes sucientes para a convergencia dos metodos da secante ede Newton que sao de vericacao mais simples.

Teorema 2.7 Seja x0[a, b] e f uma func ao duas vezes continuamente diferenci avel no intervalo [a, b] que satisfaz as seguintes condic oes:

1. f (a)f (b) < 0

2. f (x) = 0 , x[a, b]

3. f (x) n ao muda de sinal em [a, b], i.e., f (x) 0 ou f (x) 0 com x[a, b]4. (a)

|f (a)/f (a)

| 0 com x(a, b).

Exemplo 2.6 Considerar a equa c ao x2 a = 0 com a > 0. Utilizando o metodo doponto xo e usando o computador em precis ao simples, efectuar 4 itera c oes com asseguintes escolhas para a func ao iteradora g e para o valor inicial x0:


52/236


1. g(x) = x (x2 a) e x0 = 1 .52. g(x) = x 0.6(x2 a) e x0 = 43. g(x) = x 0.6(x2 a) e x0 = 24. g(x) = ( x + a/x )/ 2 e x0 = 2

Tomar a = 2 (neste caso z = 2 = 1.414214).Dos resultados obtidos, que apresentamos na Tabela 2.6, depreendemos que a con-vergencia e sua rapidez dependem da funcao iteradora g e do valor inicial x0 escolhidos(nos casos 1 e 2 o metodo diverge, no caso 3 o metodo converge lentamente, no caso4 o metodo converge rapidamente).

Tabela 2.6: Exemplo do metodo do ponto xo para x2 2 = 0

Caso1 Caso2 Caso3 Caso4m xm xm xm xm0 1.500000 4.000000 2.000000 2.0000001 1.250000 4.400001 0.800000 1.5000002 1.687500 14.81600 1.616000 1.4166673 0.839844 145.3244 1.249126 1.4142164 2.134506 12815.63 1.512936 1.414214

2.4.1 Convergencia do metodo iterativo do ponto xoVamos a seguir apresentar alguns teoremas que nos esclarecem sobre a con-

vergencia do metodo iterativo do ponto xo. Antes porem vamos introduzir a seguintedenicao

Denicao 2.2 Uma func ao g diz-se Lipschitziana no intervalo I = [a, b] se existir uma constante L > 0 tal que

|g(y) g(x)| L|y x|, y, xI (2.34)No caso em que L < 1 a func ao diz-se contractiva.

Nota-se que uma fun cao Lipschitziana e contnua. Por outro lado, se g for continua-mente diferenci avel em I , pelo teorema de Lagrange temos que, para y, xI ,

g(y) g(x) = g ()(y x) int( y, x )e portanto se |g ()| < 1 para todo o I , a funcao g e contractiva. Neste caso, aconstante de Lipschitz L em (2.34) pode ser dada por

L = maxxI |g (x)| (2.35)


53/236

2.4 Iterac ao do ponto xo 45

O teorema seguinte e uma das versoes mais simples do teorema conhecido naliteratura pelo do ponto xo.

Teorema 2.9 Se existir um intervalo I = [a, b] no qual a func ao g e contractiva eg(I )I , i.e., a g(x) b, ent ao:

1. g possui pelo menos um ponto xoz em I 2. z e o unico ponto xo em I

3. para qualquer x0 em I a sucess ao {xm}gerada por (2.33) converge para z4. |z xm | 11 L |xm +1 xm | , |z xm +1 |

L1 L |xm +1 xm |

5. |z xm | Lm |z x0| Lm

1 L |x1 x0|Demonstra c ao: (1) Se g(a) = a ou g(b) = b ent ao g tem um ponto xo em I .Suponhamos ent ao que g(a) = a e g(b) = b e consideremos a funcao contnua h(x) =g(x) x. Por termos suposto que g(I )I , tem-se que h(a) > 0 e h(b) < 0 e portantodo teorema do valor intermedio concluimos que h tem que possuir um zero em (a, b).Fica provado que g possui pelo menos um ponto xo z em I . (2) Suponhamos que we um ponto xo em I . Ent ao por ser g contractiva de (2.34) temos

|z w| = |g(z) g(w)| L|z w|(1 L)|z w| 0

Como 1 L > 0, conclui-se que w = z (unicidade). ( 3) Comecamos por notarque se xm

I ent ao xm +1 = g(xm )

I , visto que g(I )

I . Para mostrar quelimm xm = z atendemos a que |z xm +1 | = |g(z) g(xm )|, por (2.32) e (2.33),|g(z) g(xm )| L|z xm |, por (2.34). Ent ao se x0I , temos

|z xm +1 | L|z xm | xm I (2.36)De (2.36) temos |z xm | L|z xm 1| e por inducao segue

Documents

LIVRO-calc_num