Apostila Metodos Numericos

UNIVERSIDADE FEDERAL DE PELOTASINSTITUTO DE FISICA E MATEMATICA

DEPARTAMENTO DE MATEMATICA E ESTATISTICA

APOSTILA DE CALCULO NUMERICO

pelo

Prof. Dr. German Ramon Canahualpa Suazo

Apostila da disciplina de Calculo Numerico

Pelotas, setembro de 2004

APOSTILA DE CALCULO NUMERICO

por

German Ramon Canahualpa Suazo

Apostila de Aula para a disciplina Calculo Numerico ministrada no semestre 2004-2.

Autor: Prof. Dr. German Ramon Canahualpa Suazo

Pelotas, setembro de 2004

RESUMO

O proposito deste trabalho e fornecer ao aluno da disciplina de Calculo Numerico,

um complemento teorico e pratico sobre os conceitos, definicoes e metodos ministrados em aula,

bem como detalhar as provas das proposicoes e dos teoremas para um melhor entendimento e

aproveitamento.

i

ABSTRACT

TITLE: “LESSONS OF NUMERICAL CALCULUS”

ii

INDICE

1 INTRODUCAO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 Natureza e Objetivos da Analise Numerica . . . . . . . . . . . . . . . . . . . 1

1.2 Analise Numerica no contexto da Matematica Computacional . . . . . . 1

1.3 Calculo Numerico no contexto da Analise Numerica . . . . . . . . . . . . . 2

1.4 Calculo Numerico no contexto da Modelagem Matematica . . . . . . . . . 2

2 ALGORITMOS NUMERICOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 A Estrutura dos Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.3 Alguns Exemplos de Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.4 Introducao a Analise de Algoritmos . . . . . . . . . . . . . . . . . . . . . . . 7

3 INTRODUCAO A ANALISE DE ERROS . . . . . . . . . . . . . . . . . . . . . . 9

3.1 Erros na Fase da Modelagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.2 Erros na Fase da Resolucao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.3 Conversao de Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.3.1 Conversao de Inteiros da Base Decimal para a Base Binaria . . . . . . . . . 11

3.3.2 Conversao de Numeros Fracionarios da Base Decimal para a Base Binaria . 12

3.3.3 Conversao de Inteiros da Base Binaria para a Base Decimal . . . . . . . . . 13

3.3.4 Conversao de Numeros Fracionarios da Base Binaria para a Base Decimal . 15

3.4 Aritmetica de Ponto Flutuante . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.5 Erros Absolutos e Relativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.6 Erros de Arredondamento e Truncamento em um Sistema de Aritmetica

de Ponto Flutuante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

iii

3.7 Erros nas Operacoes Aritmeticas de Ponto Flutuante . . . . . . . . . . . . 23

3.8 Problemas Propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4 EQUACOES TRANSCENDENTES E ALGEBRICAS . . . . . . . . . . . . . . 29

4.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.2 Aproximacoes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.3 Criterios de Parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.4 O Metodo da Bissecao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.5 O Metodo da Falsa Posicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.6 O Metodo das Cordas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.7 O Metodo de Newton-Raphson . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.8 A Velocidade de Convergencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.9 Eficiencia de um Metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.10 Equacoes Polinomiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.11 O Metodo de Birge-Vieta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.12 O Metodo de Bairstow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.13 Problemas Propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5 SISTEMAS DE EQUACOES ALGEBRICAS LINEARES . . . . . . . . . . . . 56

5.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.2 Metodos Diretos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.2.1 A Regra de Cramer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.2.2 Eliminacao Gaussiana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.2.3 Metodo de Decomposicao LU . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.3 Metodos Iterativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

iv

5.3.1 Metodo de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.3.2 Metodo de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.3.3 Convergencia dos Metodos Iterativos . . . . . . . . . . . . . . . . . . . . . . 69

6 INTERPOLACAO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.2 Interpolacao de Lagrange e de Newton . . . . . . . . . . . . . . . . . . . . . 73

6.2.1 Interpolacao Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.2.2 Interpolacao de n+ 1 pontos . . . . . . . . . . . . . . . . . . . . . . . . . . 77

6.2.3 Erro na Interpolacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6.2.4 Forma de Gregory-Newton para o Polinomio Interpolador . . . . . . . . . . 84

6.2.5 Interpolacao Inversa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

6.3 Polinomios de Taylor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7 AJUSTE DE CURVAS PELO METODO DOS QUADRADOS MINIMOS . 92

7.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

7.2 Caso Linear Discreto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

7.2.1 Ajuste de uma Reta por Quadrados Mınimos . . . . . . . . . . . . . . . . . 95

7.3 Caso Linear Contınuo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

7.4 Caso Nao Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

8 INTEGRACAO NUMERICA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

8.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

8.2 As Formulas de Newton-Cotes . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

8.2.1 Regra dos Trapezios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

8.2.2 Regra dos Trapezios Repetida . . . . . . . . . . . . . . . . . . . . . . . . . . 105

v

8.2.3 Regra de Simpson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

8.2.4 Regra de Simpson Repetida . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

8.2.5 Regra dos Tres Oitavos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

8.2.6 Regra dos Tres Oitavos Repetida . . . . . . . . . . . . . . . . . . . . . . . . 108

8.3 Quadratura Gaussiana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

9 RESOLUCAO NUMERICA DE EQUACOES DIFERENCIAIS ORDINARIAS112

9.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

9.2 Erros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

9.3 Metodo de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

9.4 Metodos de Taylor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

9.5 Metodos de Runge-Kutta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

9.6 Metodos de Passo Multiplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

9.6.1 Metodos Explıcitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

9.6.2 Metodos Implıcitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

9.7 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

vi

INDICE DE FIGURAS

Figura 3.1 Fases da resolucao de um problema . . . . . . . . . . . . . . . . . . . . . . . . . 9

Figura 4.1 Uma intersecao do eixo x com o grafico da funcao fornece uma raiz de f(x) = 0. 32

Figura 4.2 Uma intersecao dos graficos de duas funcoes, y = x e y = e−x cos(x) fornece

uma raiz de f(x) = 0. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Figura 4.3 Se f(a)f(b) < 0 entao existe pelo menos uma raiz no intervalo ]a, b[. No primeiro

grafico, existe exatamente uma raiz, no segundo, tres raızes e no terceiro, duas

raızes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Figura 4.4 Se f(a)f(b) < 0 e f ′(x) preservar o sinal em (a, b), entao existe uma unica raiz

no intervalo ]a, b[. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Figura 4.5 Escolha da aproximacao inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Figura 7.1 Ajuste de uma curva ϕ(x) = α1x2 aos dados da tabela. . . . . . . . . . . . . . . 94

Figura 7.2 Ajuste de uma curva ϕ(x) = α1x2 + α2x aos dados da tabela. . . . . . . . . . . 95

Figura 7.3 Ajuste de uma curva ϕ(x) = α1x+ α2 aos dados da tabela. . . . . . . . . . . . 97

Figura 7.4 Ajuste de uma curva ϕ(x) = α1x+ α2 a funcao f(x) = 4x3. . . . . . . . . . . . 99

Figura 7.5 Ajuste de uma curva ψ(x) = β2eβ1x aos dados da tabela. . . . . . . . . . . . . . 100

vii

1 INTRODUCAO

1.1 Natureza e Objetivos da Analise Numerica

A analise numerica e uma area da matematica destinada ao estudo analıtico das diver-

sas metodologias e abordagens numericas utilizadas na resolucao de problemas reais. Os diversos

problemas reais que se originam nas ciencias exatas envolvem quase sempre a resolucao de proble-

mas de valor inicial ou problemas de valor de contorno, isto e, equacoes diferenciais ordinarias ou

parciais junto com condicoes iniciais (isto e, uma certa configuracao inicial do modelo) ou condicoes

de contorno (isto e, uma configuracao na fronteira geometrico do modelo), respectivamente.

A analise numerica esta, desse modo, envolvida no estudo dos diversos metodos para a

resolucao numerica dos problemas de valor inicial ou de contorno, pois, em geral, tais problemas nao

podem ser resolvidos de maneira exata. Os metodos numericos sao sempre iterativos, isto e, os va-

lores aproximados seguintes dependem dos valores aproximados atuais e/ou anteriores, e devem ser

realizados um numero finito de vezes. Os tres aspectos fundamentais estudados sao: a eficiencia, a

convergencia e a estabilidade de um metodo numerico. As diversas tecnicas matematicas utilizadas

para a resolucao dos problemas envolvem com frequencia a resolucao de equacoes algebricas, de

sistemas de equacoes lineares, interpolacao, ajuste, e diferenciacao e integracao numerica.

Um conceito importante estudado na analise numerica e o erro, que pode originar-se

a partir das medicoes ou do tipo de instrumento de calculo que esta sendo utilizado.

1.2 Analise Numerica no contexto da Matematica Computacional

A analise numerica e uma area da matematica envolvida com o estudo da resolucao

numerica de problemas reais das ciencias exatas. Neste sentido, ela pode ser enquadrada como

uma area da matematica computacional, por estar diretamente relacionada com a elaboracao de

algoritmos bem como o estudo analıtico destes.

A matematica computacional esta relacionada com a resolucao de problemas matema-

ticos utilizando computadores.

Antigamente, existiam dois aspectos da investigacao cientıfica: a teoria e o experi-

mento. Atualmente, tem aparecido um terceiro aspecto: a computacao.

1

1.3 Calculo Numerico no contexto da Analise Numerica 2

Os modelos matematicos aparecem a partir de diversas areas cientıficas, incluındo a

previsao do tempo, angenharia, comercio e financas, ciencia e medicina. A utilizacao do computa-

dor para resolver modelos tem revolucionado estas areas.

Desenvolver e analisar tais modelos de modo que as simulacoes por computador se-

jam realizadas de maneira eficiente e precisa, envolve mais do que a matematica classica e a

ciencia da computacao elementar. Inclui ıtens tais como as implicacoes da imprecisao e os erros de

aproximacao, a eficiencia, a precisao e a estabilidade dos calculos numericos, o desenvolvimento e

manutencao de software matematico, e os efeitos de desenvolvimentos modernos em arquiteturas

e redes de computacao.

Ate pouco tempo atras, os modelos e as ferramentas de software correspondentes eram

basicamente desenvolvidos por especialistas na area. Mas devido a complexidade crescente dos

modelos e a facilidade do calculo por computador, faz-se necessario o entendimento dos conceitos

envolvidos na matematica computacional.

1.3 Calculo Numerico no contexto da Analise Numerica

O calculo numerico e a parte pratica da analise numerica, pois consiste na aplicacao

direta de resultados teoricos e fechados da analise numerica em problemas especıficos. A funda-

mentacao teorica desses resultados nao e o principal objetivo mas ela nao pode ser deixada de lado.

Nesta apostila, sempre que possıvel, serao feitas as demonstracoes dos resultados teoricos.

1.4 Calculo Numerico no contexto da Modelagem Matematica

O calculo numerico e uma ferramenta pratica poderosa para resolver problemas prove-

nientes das ciencias exatas. Ele e aproveitado ao resolver numericamente modelos matematicos de

sistemas reais mediante a tecnica denominada simulacao de sistemas. A modelagem matematica

e geralmente desenvolvida por especialistas da area especıfica sendo investigada, mas a tendencia

atual e a insercao de especialistas da matematica computacional pois o modelo matematico pode

envolver um comprometimento com aspectos tais como a complexidade computacional.

2 ALGORITMOS NUMERICOS

2.1 Introducao

Dizer que um problema e resolvıvel algoritmicamente significa, de modo informal que

pode ser escrito um programa de computador que produzira o resposta correta para qualquer en-

trada se e permitida a execucao do programa o tempo que for necessario utilizando o espaco de

armazenamento necessario. Na decada de 30, antes da aparicao dos computadores, os matematicos

trabalharam ativamente para formalizar e estudar a nocao de um algoritmo, que foi entao inter-

pretado informalmente como um conjunto de instrucoes simples a serem seguidas para resolver um

problema. Foi criada uma area especıfica da ciencia denominada teoria da computabilidade cujo ob-

jetivo era descrever e caracterizar aqueles problemas que podiam ser resolvidos algoritmicamente

e mostrar aqueles que nao podiam. Um dos resultados negativos importantes, estabelecido por

Alan Turing, foi a prova da insolubilidade do problema da parada. O problema da parada consiste

em determinar se um algoritmo arbitrario (ou um programa de computador) parara alguma vez

enquanto trabalha com uma entrada dada. Nao existe um programa de computador que resolva

este problema.

Embora a teoria da computabilidade tem implicacoes obvias e fundamentais para a

ciencia da computacao, o conhecimento que um problema pode ser teoricamente resolvido em um

computador nao basta para afirmar que tal resolucao e pratica. Por exemplo, um programa de

jogar xadrez de maneira perfeita pode ser escrito. Esta nao seria uma tarefa muito difıcil. Existe

so um numero finito de maneiras de arranjar as pecas no tabuleiro, e sob certas regras um jogo

deve terminar apos um numero finito de movimentos. O programa poderia considerar cada um dos

possıveis movimentos de um oponente e as possıveis respostas do outro, cada uma das respostas a

esses movimentos e assim por diante, ate que cada sequencia de movimentos chegue ao fim. Entao

como o ultimo resultado e conhecido, o computador pode escolher o melhor movimento. O numero

de arranjos diferentes das pecas sobre o tabuleiro que e razoavel considerar (muito menor que o

numero de sequencias de movimentos) e mais ou menos 1050. Um programa que examinasse todos

eles levaria varios milhares de anos. Assim, tal programa nao pode ser executado.

Existem diversos problemas com aplicacoes praticas que podem ser resolvidos - isto

e, para os quais podem ser escritos programas - mas para os quais os requerimentos de tempo e

armazenamento sao demasiado grandes para que estes programas sejam de uso pratico. E claro

que os requerimentos de tempo e armazenagem de um programa sao de importancia pratica. Estes

3

2.2 A Linguagem dos Algoritmos 4

aspectos tem-se convertido no tema de estudo teorico na area da ciencia da computacao denominada

complexidade computacional.

2.2 A Estrutura dos Algoritmos

Basicamente, todo algoritmo deve estar munido das seguintes partes:

1. Nome: que deve lembrar o procedimento ou o resultado do algoritmo.

2. Entrada: que deve enumerar de maneira completa todas as variaveis a serem uti-

lizadas pelo algoritmo, assim como a sua natureza. Por exemplo: numero real ou

inteiro, funcao, vetor, matriz (junto com a ordem), etc.

3. Saıda: que deve enumerar de maneira completa todas as variaveis a serem obtidas

atraves do procedimento.

4. Procedimento: que deve enumerar as possıveis variaveis locais, e o processo ao que

deve ser submetida a entrada do algoritmo, enumerado sequencialmente.

Por sua vez, o procedimento do algoritmo tem diversas ferramentas basicas, que sao

enumeradas a seguir:

1. Dar valor a uma variavel: associa o nome da variavel com certo valor calculado.

A sintaxe representativa dessa acao tem a forma:

variavel← valor

2. Ler o valor de uma variavel: realiza uma operacao de leitura, isto e, recebe o valor

de uma variavel e associa a ela o nome de uma variavel. A sintaxe representativa dessa

acao tem a forma:

read valor

3. Escrever uma mensagem ou o valor de uma variavel: realiza uma operacao

de escritura, isto e, escreve uma mensagem e/ou o valor de uma variavel em algum

dispositivo tal como a memoria ou a tela do computador. A sintaxe representativa

dessa acao tem a forma:

write valor

2.2 A Linguagem dos Algoritmos 5

4. Parar o procedimento: para o procedimento antes do final do algoritmo. A sintaxe

representativa dessa acao tem a forma:

return

5. O laco for: e utilizado para repetir instrucoes similares varias vezes. A sintaxe


for variavel ← valor inicial to valor final by tamanho do salto{

instrucoes

end

6. O laco while: e utilizado para repetir instrucoes similares varias vezes enquanto

certa condicao seja satisfeita. A sintaxe representativa dessa acao tem a forma:

while condicao do{

instrucoes

end

7. O condicional if: e utilizado para realizar uma certa acao se alguma condicao e

satisfeita, e, opcionalmente, outra acao se a condicao nao e satisfeita. A sintaxe


if condicao then{

instrucoes

end

ou,

if condicao

then instrucoes

else instrucoes

end

Tambem e utilizada uma terceira alternativa, denominada condicional aninhado que

nao e outra coisa que um condicional dentro de um outro.

2.3 Alguns Exemplos de Algoritmos 6

2.3 Alguns Exemplos de Algoritmos

1. Apresenta-se um algoritmo que calcula as raızes reais ou complexas, simples ou duplas,

de uma equacao quadratica com coeficientes reais

ax2 + bx+ c = 0, a 6= 0.

A tecnica matematica neste caso e a formula de Bhaskara. Lembre que os valores

das raızes dependem basicamente do discriminante b2 − 4ac: se o discriminante for

positivo, a equacao tem duas raızes reais diferentes, se for zero, a equacao tem uma

raiz real dupla, e se for negativo, a equacao tem duas raızes complexas conjugadas.

Um algoritmo que realiza este procedimento e

Algoritmo raızes

A. Entrada: a, b, c, numeros reais

B. Saıda: x1, x2, raızes reais ou complexas da equacao quadratica ax2 + bx+ c = 0, a 6= 0

C. Procedimento:

if a = 0 then

1. write ‘nao e uma equacao quadratica’

else if b2 − 4ac = 0 then

2. write ‘raiz real dupla, x1 = x2 =’,-b/(2a)

else if b2 − 4ac > 0 then

3. write ‘raızes reais simples, x1 =’,−b+√b2 − 4ac

2a ,‘x2 =’,−b−√b2 − 4ac

2a

else

4. write ‘raizes complexas conjugadas, x1 = x2 =’, b2a ± i√

4ac− b22a

end

end

end

2.4 Introducao a Analise de Algoritmos 7

2. Agora, apresenta-se um algoritmo que o produto de duas matrizes reais de ordem

m× n e p× q, respectivamente. Lembre que a multiplicacao so e possıvel se n = p.

Algoritmo prod mat

A. Entrada: A = [aij ]m×n, B = [bkl]p×q matrizes reais

B. Saıda: C = [cil]m×q matriz real, produto das matrizes A e B

C. Procedimento:

if n 6= p then

1. write ‘a multiplicacao nao e possıvel’

else

for i← 1 to m by 1 do

for l ← 1 to q by 1 do

2. cil ← 0

for j ← 1 to n by 1 do

3. cil ← cil + aijbjl

end

end

end

end

2.4 Introducao a Analise de Algoritmos

Os algoritmos sao analisados visando melhora-los, se possıvel, e para escolhe-lo como

apropriado para um determinado problema. Utilizam-se os seguintes criterios:

1. Correcao: Existem tres etapas envolvidas para estabelecer a correcao de um al-

goritmo. Primeiro, antes de determinar se um algoritmo e correto, deve-se ter um

entendimento claro do que significa “correto”. Precisa-se de uma lista de quais sao

as entradas e as saıdas. O metodo de solucao precisa ter as formulas corretas e/ou

previamente validadas analiticamente por lemas e teoremas. Segundo, implementar o

algoritmo na forma de um programa. Finalmente, verificar a validade do algoritmo

mediante tecnicas elementares ou sofisticadas (tais como a invariancia para lacos).

2. Quantidade de trabalho realizado: esta relacionado com o numero de operacoes

basicas realizadas. Quanto menor tal numero, mais eficiente sera o algoritmo.

2.4 Introducao a Analise de Algoritmos 8

3. Analise do pior caso e do caso medio: A quantidade de operacoes basicas nao e

o mesma para entradas diferentes. Por exemplo, o trabalho realizado nao e o mesmo

se, tratando-se de um algoritmo que ordena alfabeticamente, uma lista de palavras

tem poucas palavras fora de ordem.

4. Quantidade de espaco utilizado: esta relacionado com o requerimento de memoria

de um algoritmo. Quanto menos memoria requerida mais eficiente sera o algoritmo.

5. Simplicidade: Com frequencia, acontece que a maneira mais simples e mais direta de

resolver um problema nao e a mais eficiente. Ainda a simplicidade em um algoritmo e

uma caracterıstica desejavel. Pode fazer com que as outras caracterısticas do algoritmo

sejam mais faceis de medir.

6. Complexidade do problema: Existem basicamente duas tarefas a serem realizadas

para encontrar um bom algoritmo, ou, desde outro ponto de vista, para responder a

pergunta: Quanto trabalho e necessario e suficiente para resolver um problema?

(a) Monte o que parece ser um algoritmo eficiente. Encontre uma funcao W tal que,

para entradas de tamanho n, o algoritmo efetua como maximo W (n) passos no

pior caso.

(b) Para alguma funcao F , prove que para qualquer algoritmo em uma classe sob

consideracao, existe alguma entrada de tamanho n para a qual o algoritmo deve

realizar pelo menos F (n) passos.

Se as funcoes W e F sao iguais, entao o algoritmo e otimo, senao poderia existir um

algoritmo melhor.

3 INTRODUCAO A ANALISE DE ERROS

O objetivo maior e a resolucao de problemas que surgem das mais diversas areas da

ciencia. Este objetivo pode ser atingido atraves de varias fases. Estas podem ser resumidas, de

maneira geral, no seguinte esquema:

- -

problema modelagem modelo resolucaosolucao

matematicoreal

Figura 3.1 Fases da resolucao de um problema

De maneira bastante geral, um erro e e diferenca entre o valor real e o valor obtido

como solucao de um problema. E de interesse conhecer as possıveis fontes de erros para que se

possa controla-los ou evita-los. As duas fases, modelagem e resolucao, sao as maiores fontes de

erros na resolucao de um problema.

3.1 Erros na Fase da Modelagem

O objetivo da fase da modelagem e obter um modelo matematico que descreve

o comportamento do fenomeno que origina o problema real.

Nesta fase, os erros podem ser classificados basicamente em dois tipos:

• erros inerentes ao modelo: decorrem das simplificacoes feitas no ambiente do

fenomeno, aplicadas no modelo. Por exemplo: considere a equacao de queda livre de

um corpo

h = H − v0t−1

2gt2 (3.1)

sendo

– h : altura do corpo com relacao ao solo no instante t (m),

– H : altura inicial (t = 0) do corpo com relacao ao solo (m),

– v0 : velocidade inicial (t = 0) do corpo (m/s),

– g : aceleracao da gravidade (m/s2) e

– t : tempo (s).

A equacao (3.1) tem simplificacoes tais como a nao inclusao da resistencia do ar, a

velocidade e direcao do vento, etc.

9

3.2 Erros na Fase da Resolucao 10

• erros no levantamento dos dados: sao os erros introduzidos atraves dos in-

strumentos de medicao. Por exemplo, suponha que quer-se determinar a altura de

um predio mediante um cronometro e uma bolinha de metal, utilizando a formula da

queda livre (3.1). Sobe-se no topo do edifıcio e larga-se a bolinha, medindo o tempo

que a bolinha gasta para tocar o solo. Se o cronometro marcou tres (3) segundos,

entao, como no solo h = 0,

H = v0t+1

2gt2 = 0 +

1

2· 9, 8 · 32 = 44, 1 m

Mas este resultado nao e confiavel, pois para 3, 1 segundos a altura resulta H = 47, 1

m. A diferenca entre as medicoes pode ser devido a percepcao do observador bem

como a imprecisoes proprias do instrumento.

3.2 Erros na Fase da Resolucao

O objetivo da fase da resolucao e obter a solucao do modelo matematico

junto com a informacao dos dados, mediante a aplicacao de metodos numericos.

Nesta fase, tem-se as seguintes fontes de erros:

• erros de conversao numerica: originam-se quando a informacao dos dados numericos

na base decimal e transferida para a calculadora ou computador, ou quando o resul-

tado numerico obtido no computador e transferido para o usuario. Estes erros podem

ser de arredondamento ou de truncamento.

• erros de aritmetica de ponto flutuante: que se originam quando os dados

sao processados no computador mediante operacoes aritmeticas. Cabe ressaltar que

acontece um fenomeno chamado propagacao de erros, que e um processo em que os

erros cometidos em um calculo influenciam nos calculos subsequentes.

Nas secoes seguintes, estudam-se estes processos.

3.3 Conversao de Bases 11

3.3 Conversao de Bases

3.3.1 Conversao de Inteiros da Base Decimal para a Base Binaria

Aplica-se o metodo das divisoes sucessivas, que consiste em dividir o numero por 2 e

os sucessivos quocientes por 2 ate que o ultimo quociente seja 1. Esquematicamente:

N | 2

r1 q1 | 2

r2 q2 | 2

r3 q3. . .

qn−1 | 2

rn−1 1

(3.2)

A representacao binaria do numero N esta dada por

N = 1rn−1 . . . r3r2r1(2) (3.3)

Este metodo pode ser utilizado para converter qualquer numero inteiro da base decimal

para uma base qualquer β : divide-se o numero por β e os sucessivos quocientes por β ate que o

ultimo quociente seja um inteiro 1 ≤ qn < β. Esquematicamente:

N | β

r1 q1 | β

r2 q2 | β

r3 q3. . .

qn−1 | β

rn−1 qn

(3.4)

A representacao do numero N na base β esta dada por

N = qnrn−1 . . . r3r2r1(β) (3.5)


Exemplo 3.1.

18 | 2

0 9 | 2

1 4 | 2

0 2 | 2

0 1

1810 = 100102

Exemplo 3.2.

11 | 2

1 5 | 2

1 2 | 2

0 1

1110 = 10112

3.3.2 Conversao de Numeros Fracionarios da Base Decimal para a Base Binaria

Aplica-se o metodo das multiplicacoes sucessivas, que consiste em multiplicar o numero

por 2 e extrair a parte inteira (podendo ser 0). O resto fracionario e multiplicado novamente por 2

e a parte inteira e extraıda. Este processo deve-se repetir ate ter um resto fracionario igual a 0 ou

ate observar um padrao repetitivo, em cujo caso tratar-se-a de um numero fracionario periodico

(puro ou misto).

Exemplo 3.3.

0, 3125 0, 625 0, 25 0, 50

×2 ×2 ×2 ×2

0, 6250 1, 250 0, 50 1, 00

0, 312510 = 0, 01012

Exemplo 3.4.

0, 8 0, 6 0, 2 0, 4 0.8

×2 ×2 ×2 ×2 ×2

1, 6 1, 2 0, 4 0, 8 1, 6

. . . os produtos estao se repetindo

0, 810 = 0, 11002


Exemplo 3.5. Considere o numero 12, 12510 = 1210 + 0, 12510

12 | 2

0 6 | 2

0 3 | 2

1 1

0, 125 0, 25 0, 5

×2 ×2 ×2

0, 250 0, 50 1, 0

1210 = 11002 0, 12510 = 0, 0012

Portanto, 12, 12510 = 11002 + 0, 0012 = 1100, 0012

Para converter um numero fracionario da base decimal para uma base β, tambem

aplica-se o metodo das multiplicacoes sucessivas, que, neste caso, consiste em multiplicar o numero

por β e extrair a parte inteira (podendo ser 0). O resto fracionario e multiplicado novamente por

β e a parte inteira e extraıda. Este processo deve-se repetir ate ter um resto fracionario igual a 0

ou ate observar um padrao repetitivo.

3.3.3 Conversao de Inteiros da Base Binaria para a Base Decimal

O numero representado por

am . . . a2a1a0(2)

tem o valor decimal igual a

am2m + · · ·+ a222 + a12 + a0. (3.6)

Portanto, para conhecer o valor decimal do numero am . . . a2a1a0(2) basta calcular a soma em (3.6).

Esta soma pode ser calculada diretamente ou utilizando dois metodos equivalentes

1. o esquema de Horner que consiste em calcular a sequencia

bm = am,

bm−1 = am−1 + 2bm,

bm−2 = am−2 + 2bm−1,

...

b1 = a1 + 2b2,

b0 = a0 + 2b1.

(3.7)


O valor decimal do numero am . . . a2a1a0(2) e entao, simplesmente, b0.

2. a divisao de Ruffini que e equivalente ao primeiro metodo e so difere na disposicao

dos coeficientes aj e bj ,

am am−1 · · · a2 a1 a0

2 2bm · · · 2b3 2b2 2b1

bm bm−1 · · · b2 b1 b0

Exemplo 3.6. O numero 111012 forma a sequencia de Horner

b4 = a4 = 1,

b3 = a3 + 2b4 = 1 + 2 · 1 = 3,

b2 = a2 + 2b3 = 1 + 2 · 3 = 7,

b1 = a1 + 2b2 = 0 + 2 · 7 = 14,

b0 = a0 + 2b1 = 1 + 2 · 14 = 29;

isto e, 111012 = 29.

Exemplo 3.7. O numero 1011002 forma o esquema de Ruffini

1 0 1 1 0 0

2 2 4 10 22 44

1 2 5 11 22 44

Portanto, 1011002 = 44

A metodologia anterior pode ser generalizada para converter qualquer numero inteiro

na base β para a base decimal. Considere o numero O numero representado por

am . . . a2a1a0(β)

1. o esquema de Horner consiste em calcular a sequencia

bm = am,

bm−1 = am−1 + βbm,

bm−2 = am−2 + βbm−1,

...

b1 = a1 + βb2,

b0 = a0 + βb1.

(3.8)

O valor decimal do numero am . . . a2a1a0(β) e entao, simplesmente, b0.


2. a divisao de Ruffini,

am am−1 · · · a2 a1 a0

β βbm · · · βb3 βb2 βb1

bm bm−1 · · · b2 b1 b0

3.3.4 Conversao de Numeros Fracionarios da Base Binaria para a Base Decimal

Considere o numero fracionario na base binaria

0, a1a2 . . . an(2).

Este numero tem representacao finita e o valor decimal e

a12−1 + a22

−2 + · · ·+ an2−n. (3.9)

Esta soma pode ser calculada diretamente ou utilizando qualquer um dos dois metodos ja enunci-

ados na subsecao anterior com algumas modificacoes

1. o esquema de Horner,

bn = an,

bn−1 = an−2 +1

2bn,

bn−2 = an−3 +1

2bn−1,

...

b2 = a2 +1

2b3,

b1 = a1 +1

2b2,

b0 =1

2b1.

(3.10)

O valor decimal do numero 0, a1a2 . . . an(2) e entao, simplesmente, b0.

2. a divisao de Ruffini,

an an−1 · · · a2 a1 0

12

12bn · · · 1

2b312b2

12b1

bn bn−1 · · · b2 b1 b0


Exemplo 3.8. O numero 0, 101112 origina a sequencia de Horner

b5 = a5 = 1,

b4 = a4 +1

2b5 = 1 +

1

2· 1 =

3

2,

b3 = a3 +1

2b4 = 1 +

1

2· 32

=7

4,

b2 = a2 +1

2b3 = 0 +

1

2· 74

=7

8,

b1 = a1 +1

2b2 = 1 +

1

2· 78

=23

16,

b0 =1

2b1 =

1

2· 23

16=

23

32= 0, 71875.

Portanto, 0, 101112 = 0, 71875

Exemplo 3.9. O numero 0, 001112 origina a divisao de Ruffini

1 1 1 0 0 0

12

12

34

78

716

732

1 32

74

78

716

7

32

Portanto, 0, 001112 = 732 = 0, 21875.

Se o numero fracionario tem representacao binaria infinita

0, a1a2 . . . anb1b2 . . . bm(2),

entao o valor decimal e

a12−1 + a22

−2 + · · ·+ an2−n + b12−n−1 + b22

−n−2 + · · ·+ bm2−n−m

+ b12−n−m−1 + b22

−2n−2 + · · ·+ bm2−n−2m

+ b12−n−2m−1 + b22

−n−2m−2 + · · ·+ bm2−n−3m + · · ·

(3.11)

que pode ser escrito como

(

a12−1 + a22

−2 + · · ·+ an2−n)

+(

b12−1 + b22

−2 + · · ·+ bm2−m)

· 2m−n

2m − 1(3.12)

onde as duas expressoes entre parenteses tem a mesma forma que a soma na equacao (3.9) e podem

ser calculadas diretamente ou utilizando qualquer dos metodos descritos anteriormente.

Exemplo 3.10. O numero fracionario 0, 110102 tem valor decimal

(

1 · 2−1 + 1 · 2−2)

+(

0 · 2−1 + 1 · 2−2 + 0 · 2−3)

· 1

23 − 1=

(

1

2+

1

4

)

+1

4· 17

=11

14

3.4 Aritmetica de Ponto Flutuante 17

Portanto,

0, 110102 =11

14= 0, 7857142

Em geral, se o numero fracionario tem representacao infinita na base β,

0, a1a2 . . . anb1b2 . . . bm(β),

entao o valor decimal e

(

a1β−1 + a2β

−2 + · · ·+ anβ−n

)

+(

b1β−1 + b2β

−2 + · · ·+ bmβ−m

)

· βm−n

βm − 1(3.13)

onde as duas expressoes entre parenteses podem ser calculadas diretamente ou utilizando qualquer

dos metodos descritos anteriormente (divisao de Ruffini ou metodo de Horner).

3.4 Aritmetica de Ponto Flutuante

As calculadoras e computadores possuem um numero finito de dıgitos para representar

os numeros. Formaliza-se esta afirmacao na seguinte definicao:

Definicao 3.1. Um sistema normalizado de aritmetica de ponto flutuante consiste de

0 e todos os numeros que podem ser representados na forma

±(

0, d1d2 . . . dt

)

β× βexp

onde β e um inteiro maior ou igual que 2 denominado base do sistema, t e um inteiro maior ou

igual que 1 denominado numero de dıgitos do sistema, dj sao inteiros tais que 0 ≤ dj ≤ β−1,

∀j = 2, . . . t, e 0 < d1 ≤ β − 1, e exp e um inteiro tal que m ≤ exp ≤ M sendo m ≤ M dois

inteiros, exp e denominado expoente do numero. Tal sistema e denotado por F(

β, t,m,M)

.

Em um sistema normalizado de aritmetica de ponto flutuante, a parte fracionaria de

um numero na base β,(

d1d2 . . . dt

)

e denominada mantissa.

Os parametros β, t, m e M dependem exclusivamente do computador

3.4 Aritmetica de Ponto Flutuante 18

Maquina β t m M

Burroughs 5500 8 13 -51 77

Burroughs 6700 8 13 -63 63

HP 45 10 10 -98 100

Texas SR-5X 10 12 -98 100

PDP-11 2 24 -128 127

IBM/360 16 6 -64 63

IBM/370 16 14 -64 63

Quartzil QI 800 2 24 -127 127

No sistema F(

β, t,m,M)

podem ser observadas as seguintes caracterısticas:

1. O menor numero positivo possıvel de ser representado neste sistema e

xMIN = 0, 10 . . .0β × βm = βm−1

2. A regiao de “underflow” e definida como o intervalo

(

−xMIN , xMIN

)

,

isto e, qualquer numero real cujo valor verdadeiro esta nesse intervalo, sera considerado

0 neste sistema.

3. O maior numero positivo possıvel de ser representado neste sistema e

xMAX =(

0, (β − 1)(β − 1) . . . (β − 1))

β× βM =

βt − 1

βt · βM

4. A regiao de “overflow” e definida como a uniao de dois intervalos

(

−∞,−xMAX

)

∪(

xMAX ,∞)

,

isto e, qualquer numero real cujo valor verdadeiro esta nessa uniao de intervalos, sera

considerado −∞ ou +∞, dependendo de se o numero esta no primeiro ou no segundo

intervalo, respectivamente.

5. O numero total de elementos do sistema e

2(

β − 1)(

M −m+ 1)

βt−1 + 1 (3.14)

3.5 Erros Absolutos e Relativos 19

Exemplo 3.11. Considere o sistema F(

2, 3,−1, 2)

. O menor elemento positivo deste sistema e

xMIN = (0, 100)2 × 2−1 = 2−1−1 =1

4,

portanto, a regiao de “underflow” e o intervalo

(

−1

4,1

4

)

.

O maior elemento positivo deste sistema e

xMAX = (0, 111)2 × 22 =23 − 1

23 · 22 =7

2,

portanto, a regiao de “overflow” deste sistema e

(

−∞,−7

2

)

∪(

7

2,+∞

)

.

Mais ainda, como os valores dos parametros do sistema sao pequenos, os valores na base decimal

dos elementos positivos podem ser enumerados em um arranjo

mantissa ↓ exp=-1 exp=0 exp=1 exp = 2

100 14

12 1 2

101 516

58

54

52

110 38

34

32 3

111 716

78

74

72

O numero de elementos do sistema F(

2, 3,−1, 2)

e

2(

β − 1)(

M −m+ 1)

βt−1 + 1 = 2 · (2− 1) · (2 + 1 + 1) · 23−1 + 1 = 33.

3.5 Erros Absolutos e Relativos

Nesta secao, formaliza-se o conceito de erro absoluto e relativo.

Definicao 3.2. Seja x o valor exato de um numero e x o seu valor aproximado. O erro absoluto

e definido como a diferenca entre o valor exato e o valor aproximado do numero, isto e,

EAx = x− x

3.5 Erros Absolutos e Relativos 20

Em geral, apenas o valor x e conhecido, e neste caso, e impossıvel obter o valor exato

do erro absoluto. Mas uma alternativa e calcular uma estimativa ou cota superior do valor absoluto

do erro absoluto.

Por exemplo, sabe-se que o valor exato de π ∈(

3, 14 , 3, 15)

, e para um valor aproxi-

mado, π dentro deste intervalo, tem-se

∣

∣EAπ

∣

∣ = |π − π| < 0, 01.

Por outro lado, seja x o numero aproximado por x = 1234, 5 de modo que∣

∣EAx

∣

∣ < 0, 1,

ou seja, x ∈(

1234, 4 , 1234, 6)

e seja y o numero aproximado por y = 2, 3 de modo que∣

∣EAy

∣

∣ < 0, 1,

ou seja, y ∈(

2, 2 , 2, 4)

. As cotas superiores para os erros absolutos sao os mesmos, mas os numeros

x e y nao estao representados com a mesma precisao. Neste caso, e necessario comparar a ordem

de grandeza de x e y. Fazendo isto, pode-se concluir que o primeiro resultado e mais preciso que

o segundo, pois a ordem de grandeza de x e maior que a ordem de grandeza de y.

Observa-se, entao, que o erro absoluto nao e suficiente para descrever a precisao de

uma aproximacao. Precisa-se de uma outra ferramenta, o erro relativo.

Definicao 3.3. Seja x o valor exato de um numero e x o seu valor aproximado. O erro relativo

e definido como o erro absoluto dividido por x, isto e,

ERx =EAx

x=x− xx

.

Voltando ao exemplo anterior, tem-se

∣

∣ERx

∣

∣ =

∣

∣EAx

∣

∣

|x| <0, 1

1234, 5≈ 0, 8× 10−4

e∣

∣ERy

∣

∣ =

∣

∣EAy

∣

∣

|y| <0, 1

2, 3≈ 0, 4× 10−1,

que confirma, portanto, que o numero x e representado com maior precisao que o numero y.

3.6 Erros de Arredondamento e Truncamento em um Sistema de Aritmetica de Ponto Flutuante 21

3.6 Erros de Arredondamento e Truncamento em um Sistema de Aritmetica dePonto Flutuante

Na secao 3.4, viu-se que a representacao de um numero depende da maquina uti-

lizada, isto e, cada maquina possui um sistema F(

β, t,m,M)

, que determina a base numerica, o

comprimento de palavra, etc.

Se um numero x nao tem uma representacao finita na base β ou se o comprimento

de palavra da maquina nao comporta tal representacao, sera considerada uma aproximacao por

arredondamento ou por truncamento.

Exemplo 3.12. Considere o sistema F(

10, 4,m,M)

, com m e M muito grandes em modulo. O

numero x = 62, 378 pode ser expresso como

x = 0, 6237× 102 + 0, 8× 10−2.

Pode-se observar que a ultima parcela, 0, 8×10−2, desta soma nao pode ser incorporada totalmente

a mantissa. Entao, aparece a questao de como considerar esta parcela e determinar o erro absoluto

ou relativo maximo cometido.

Um problema semelhante aparece quando tenta-se representar o numero y = 16 = 0, 16.

Observa-se que

y = 0, 1666× 100 + 0, 6× 10−4.

Dado o sistema F(

β, t,m,M)

, se um numero x positivo, nao esta na regiao de “un-

derflow” ou “overflow”, entao pode ser escrito como

x =(

0, d1d2 . . . dt

)

β× βexp + gx × βexp−t, d1 6= 0,

onde 0 ≤ gx < 1. Para tratar o problema de considerar a parcela gx × βexp−t , podem-se adotar

dois criterios:

1. truncamento: a parcela gx × βexp−t e desprezada e

x =(

0, d1d2 . . . dt

)

β× βexp ∈ F

(

β, t,m,M)

.

Neste caso,

∣

∣EAx

∣

∣ = |x− x| =∣

∣gx

∣

∣× βexp−t < βexp−t, pois∣

∣gx

∣

∣ < 1

3.6 Erros de Arredondamento e Truncamento em um Sistema de Aritmetica de Ponto Flutuante 22

e∣

∣ERx

∣

∣ =

∣

∣EAx

∣

∣

|x| =

∣

∣gx

∣

∣× βexp−t

(

0, d1d2 . . . dt

)

β× βexp

<βexp−t

0, 1β × βexp = β−t+1,

pois(

0, d1d2 . . . dt

)

β≥ 0, 1β = β−1.

2. arredondamento: a forma mais comum e o arredondamento simetrico, isto e,

x =

(

0, d1d2 . . . dt

)

β× βexp se

∣

∣gx

∣

∣ < 12 ,

(

0, d1d2 . . . (dt + 1))

β× βexp se

∣

∣gx

∣

∣ ≥ 12 .

O erro absoluto esta dado por

∣

∣EAx

∣

∣ = |x− x| =

∣

∣gx

∣

∣× βexp−t, se∣

∣gx

∣

∣ < 12 ,

∣

∣gx − 1∣

∣× βexp−t, se∣

∣gx

∣

∣ ≥ 12 ,

<1

2× βexp−t;

e o erro relativo pode ser calculado como

∣

∣ERx

∣

∣ =

∣

∣EAx

∣

∣

|x| <

12 × β

exp−t

(

0, d1d2 . . . dt

)

β× βexp se

∣

∣gx

∣

∣ < 12 ,

12 × β

exp−t

(

0, d1d2 . . . (dt + 1))

β× βexp se

∣

∣gx

∣

∣ ≥ 12 ,

<12 × β

exp−t

0, 1β × βexp =1

2β−t+1.

Portanto, os erros cometidos no arredondamento simetrico tem as seguintes cotas

superiores∣

∣EAx

∣

∣ <1

2× βexp−t; (3.15)

e∣

∣ERx

∣

∣ <1

2β−t+1. (3.16)

Uma ferramenta muito utilizada para medir quanto um numero aproxima outro e o

numero de dıgitos significativos exatos.

3.7 Erros nas Operacoes Aritmeticas de Ponto Flutuante 23

Definicao 3.4. Sejam x e x dois numeros. O numero x e dito uma aproximacao de x em k dıgitos

significativos exatos, se∣

∣x− x∣

∣

|x| ≤ 1

2β−k+1

Exemplo 3.13. Se x = 1/3 e x = 0.333, entao

∣

∣x− x∣

∣

|x| ≤ 0, 1× 10−2 = 0, 1× 10−3+1

e x e uma aproximacao de x em 3 dıgitos significativos exatos.

3.7 Erros nas Operacoes Aritmeticas de Ponto Flutuante

Sejam x e y dois numeros reais e x e y dois valores aproximados dos primeiros, re-

spectivamente. Entao

x = x+ EAx (3.17)

e

y = y + EAy . (3.18)

Serao obtidas as formulas para os erros absolutos e relativos nas quatro operacoes

aritmeticas principais:

1. adicao: tem-se que

x+ y =(

x+ EAx

)

+(

y + EAy

)

=(

x+ y)

+(

EAx + EAy

)

;

portanto, o erro absoluto na soma, denotado por EAx+y e a soma dos erros absolutos

das parcelas,

EAx+y = EAx + EAy. (3.19)

O erro relativo pode ser calculado como

ERx+y =EAx+y

x+ y

=EAx

x· x

x+ y+EAy

y· y

x+ y

= ERx ·x

x+ y+ ERy ·

y

x+ y.

(3.20)


2. subtracao: similarmente ao caso anterior, tem-se que

EAx−y = EAx − EAy (3.21)

e

ERx−y = ERx ·x

x− y − ERy ·y

x− y . (3.22)

3. multiplicacao: tem-se que

x · y =(

x+ EAx

)

·(

y + EAy

)

= x · y + y · EAx + x · EAy + EAx · EAy

e considerando que o produto EAx · EAy e muito pequeno, pode ser desprezado na

expressao acima, conseguindo a seguinte equacao para o erro absoluto no produto

EAx·y = x ·EAy + y · EAx. (3.23)

O erro relativo pode ser calculado como

ERx·y =EAx·y

x · y

=x ·EAy + y ·EAx

x · y

=EAx

x+EAy

y

= ERx + ERy.

(3.24)

4. divisao: tem-se que

x

y=x+ EAx

y + EAy=x+ EAx

y·

1

1 +EAy

y

.

O ultimo fator,1

1 +EAy

y

, pode ser representado mediante uma serie

1

1 +EAy

y

= 1− EAy

y+

(

EAy

y

)2

−(

EAy

y

)3

+ · · · (3.25)


e desprezando os termos com potencias maiores que 1, tem-se que

x

y≈ x+ EAx

y·

1−EAy

y

=x

y+EAx

y− x ·EAy

y2− EAx · EAy

y2;

novamente, considerando que o produto EAx · EAy e muito pequeno, pode ser de-

sprezado na expressao acima, e entao

x

y≈ x

y+EAx

y− x · EAy

y2.

Assim, consegue-se a seguinte expressao para o erro absoluto da divisao:

EAx/y =EAx

y− x · EAy

y2=y ·EAx − x ·EAy

y2(3.26)

e para o erro relativo tem-se

ERx/y =y ·EAx − x ·EAy

y2· yx

=EAx

x− EAy

y,

portanto

ERx/y = ERx − ERy. (3.27)

Exemplo 3.14. Suponha que x, y, z e v estao representados de maneira exata. Quer-se encontrar

uma cota superior do erro relativo total cometido ao calcular

u = (x + y) · z − v

no sistema de aritmetica de ponto flutuante F(

10, t,m,M)

. O erro relativo de arredondamento e

denotado por ǫa.

Tem-se que

ERtotalx+y = ERx ·

x

x+ y+ ERy ·

y

x+ y+ ǫa = ǫa

e entao∣

∣ERtotalx+y

∣

∣ =∣

∣ǫa∣

∣ <1

2× 10−t+1.

Seja s = x+ y. Ao calcular s · z, o erro relativo total desse produto e

ERtotals·z = ERs + ERz + ǫa = ERx+y + 0 + ǫa

3.8 Problemas Propostos 26

e, portanto,∣

∣ERtotals·z

∣

∣ ≤ 2∣

∣ǫa∣

∣ < 10−t+1

Seja m = s · z. Ao calcular u = m− v, o erro relativo total dessa diferenca e

ERtotalm−v = ERm

m

m− v − ERv ·v

m− v + ǫa = ERm ·m

m− v + ǫa

e, portanto,

∣

∣ERtotalm−v

∣

∣ ≤∣

∣ERm

∣

∣ ·∣

∣

∣

∣

m

m− v

∣

∣

∣

∣

+∣

∣ǫa∣

∣ < 10−t+1 ·∣

∣

∣

∣

m

m− v

∣

∣

∣

∣

+1

2× 10−t+1.

Enfim,∣

∣ERtotalm−v

∣

∣ <

(

m

u− 1

2

)

× 10−t+1.

3.8 Problemas Propostos

1. Converter os seguintes numeros decimais para sua forma binaria

(a) 321

(b) 32, 15

(c) 0, 025

(d) 3, 17

2. Converter os seguintes numeros binarios para sua forma decimal

(a) 10101012

(b) 0, 0112

(c) 0, 011102

(d) 1101, 00101102

3. Efetuar as seguintes operacoes (sem converter para a base decimal):

(a) 1, 0012 + 0, 12 + 0, 01112

(b) 1534, 236 + 54, 4456 + 44, 126

(c) 754, 568 − 552, 77778

(d) 4332, 25 × 23, 225

(e) A1B,A16 × 7CE,D16


4. Considere o sistema F(

10, 4,m,M)

. Dados os numeros x = 0, 7273×104, y = 0, 3323×10−1 e z = 0, 8382× 101, efetuar as operacoes abaixo e obter o erro relativo total no

resultado:

(a) x+ y + z

(b) x− y − z

(c) x/y

(d) (x · y)/z

(e) x · (y/z)

5. Seja x um numero real e x a sua aproximacao por arredondamento. Obter cotas

superiores para os erros relativos de u = 2x e w = x+ x.

6. Sejam x e y numeros reais aproximados por arredondamento por x e y, respectiva-

mente. Compare os erros relativos de u = 3 · x · y e w = (x + x+ x) · y

7. Sejam x e y dois numeros reais aproximados por x = 0, 178693×101 e y = 0, 178439×101 no sistema F

(

10, 6,m,M)

. Quantos dıgitos significativos exatos tem estas aprox-

imacoes? Se a diferenca z = x − y e aproximada mediante z = x − y, qual e o erro

relativo total cometido? Quantos dıgitos significativos exatos possui z?

8. Considere o sistema aritmetico de ponto flutuante F(

2, 4,−2, 1)

.

(a) Encontre o menor e maior elementos positivos de tal sistema e determine a regiao

de “underflow” e “overflow”;

(b) Enumere, mediante uma tabela, todos os elementos positivos de tal sistema e

encontre o numero de elementos.

9. Em um sistema F(

10, 3,m,M)

, onde a aproximacao e feita por truncamento, calcule

a media dos numeros x = 4, 45 e y = 6, 76 de duas maneiras, primeiro, mediante a

formula

c =x+ y

2

e depois pela formula

d = x+y − x

2.

Calcule a media verdadeira, compare os resultados e explique a diferenca.

10. Encontre as raızes da equacao

x2 − 400x+ 1 = 0


utilizando a formula

x =−b±

√b2 − 4ac

2a

em um sistema aritmetico decimal flutuante de quatro dıgitos. Calcule a verdadeira

raiz e compare. Compare os resultados anteriores, se no mesmo sistema aritmetico

(de quatro dıgitos), a raiz e calculada pela formula

x =2c

−b±√b2 − 4ac

.

Explique a diferenca destes resultados.

11. Em um sistema F(

10, 4,m,M)

, calcule a media dos numeros x = 4, 568 e y = 6, 762

de duas maneiras, primeiro, mediante a formula

c =x+ y

2

e depois pela formula

d = x+y − x

2.

Calcule a media verdadeira, compare os resultados e explique a diferenca.

4 EQUACOES TRANSCENDENTES E ALGEBRICAS

4.1 Introducao

Um problema de grande importancia na matematica aplicada e na engenharia e de-

terminar as solucoes de uma equacao da forma

f(x) = 0. (4.1)

Definicao 4.1. Se na equacao

f(x) = 0,

a funcao f(x) e dada explicitamente por

f(x) = pn(x) = xn + an−1xn + · · ·+ a1x+ a0, (4.2)

isto e, f(x) e um polinomio de grau n em x, entao a equacao (4.1) e denominada uma equacao

polinomial.

Se f(x) pode ser conhecida so de maneira implıcita mediante uma funcao transcen-

dente, entao a equacao (4.1) e denominada uma equacao transcendente. �

Definicao 4.2. Um numero ξ e uma solucao de f(x) = 0 se f(ξ) = 0. Essa solucao ξ e denomi-

nada uma raiz ou um zero de f(x) = 0. �

Definicao 4.3. Uma raiz ξ de f(x) = 0 e dita uma raiz multipla de multiplicidade m, onde

m ∈ N, se e somente se,

1. dk

dxk f(ξ) = 0 para k = 0, . . .m− 1, onde d0

dx0 f(ξ) denota f(ξ); e

2. dm

dxm f(ξ) 6= 0.

Uma raiz de multiplicidade 1 denomina-se uma raiz simples. �

Em geral, existem dois tipos de metodos utilizados para encontrar as raızes da equacao

(4.1).

(i) Metodos Diretos: Estes metodos fornecem o valor exato das raızes em um numero

finito de passos. Alem do mais, os metodos dao todas as raızes ao mesmo tempo. Por

29

4.1 Introducao 30

exemplo, um metodo direto da a raiz de uma equacao linear ou de primeiro grau

a1x+ a0 = 0, a1 6= 0 (4.3)

como

x = −a0

a1. (4.4)

Similarmente, as raızes da equacao quadratica ou de segunda ordem

a2x2 + a1x+ a0 = 0, a2 6= 0 (4.5)

estao dadas por

x =−a1 ±

√

a21 − 4a2a0

2a2. (4.6)

(ii) Metodos Iterativos: Estes metodos estao baseados na ideia de aproximacao sucessiva,

isto e, comecar com uma ou mais aproximacoes da raiz e obter uma sequencia de

aproximantes ou iteradas{

xk

}

, que, no limite quando k −→ ∞, converge a raiz. Os

metodos podem fornecer so uma raiz por vez. Por exemplo, para resolver a equacao

quadratica (4.5) pode-se escolher qualquer um dos seguintes metodos iterativos:

(a) xk+1 = −a0 + a2x2k

a1, k = 0, 1, 2, . . .;

(b) xk+1 = − a0a2xk + a1

, k = 0, 1, 2, . . .; e

(c) xk+1 = −a0 + a1xka0xk

, k = 0, 1, 2, . . ..

A convergencia da sequencia{

xk

}

para um numero ξ, a raiz da equacao (4.5) de-

pende da escolha de uma formula recursiva, (a), (b) ou (c), e da escolha de uma

aproximacao inicial x0.

Definicao 4.4. Uma sequencia de aproximantes{

xk

}

converge a raiz ξ, se e somente se,

limk−→∞

∣

∣xk − ξ∣

∣ = 0.

�

Definicao 4.5. Se xk, xk−1, . . . , xk−m+1 sao m aproximantes da raiz, entao define-se um

metodo iterativo de m pontos como

xk+1 = φ(

xk, xk−1, . . . , xk−m+1

)

.

A funcao φ e denominada funcao iterativa do metodo.

4.2 Aproximacoes Iniciais 31

Cada aplicacao da metodo iterativo para obter determinado xk e denominada uma

iteracao.

Para m = 1, consegue-se o metodo iterativo de um ponto

xk+1 = φ(

xk

)

.

�

O processo de encontrar uma raiz da equacao ξ da equacao f(x) = 0 pode ser dividido

em duas etapas:

1. determinacao de uma aproximacao inicial que consiste em obter um intervalo

onde se encontra a raiz ξ; e

2. refinamento que consiste na escolha de um metodo iterativo para obter uma aprox-

imacao da raiz com algum grau de precisao.

A seguinte secao trata o tema da determinacao de uma aproximacao inicial.

4.2 Aproximacoes Iniciais

Com frequencia, as aproximacoes iniciais da raiz ξ sao tomadas a partir de consid-

eracoes fısicas do problema. Caso contrario, quase sempre sao utilizados metodos graficos, baseados

no calculo, para obter aproximacoes iniciais da raiz.

Como o valor de x, em que o grafico da equacao y = f(x) intersecta o eixo x, fornece

a raiz de f(x) = 0, qualquer valor em uma vizinhanca deste ponto pode ser tomado como uma

aproximacao da raiz. Por exemplo, veja os graficos da figura 4.1,

Se a equacao f(x) = 0 pode ser escrita na forma f1(x) = f2(x), entao o ponto de

intersecao dos graficos das equacoes y = f1(x) e y = f2(x) fornece a raiz de f(x) = 0 e portanto

qualquer valor na vizinhanca deste ponto pode ser tomado como uma aproximacao inicial da raiz.

Veja, por exemplo, a figura 4.2.

Outro metodo muito comum utilizado para obter uma aproximacao inicial de uma

raiz esta baseado no Teorema do Valor Intermediario, que afirma


Figura 4.1 Uma intersecao do eixo x com o grafico da funcao fornece uma raiz de f(x) = 0.

Figura 4.2 Uma intersecao dos graficos de duas funcoes, y = x e y = e−x cos(x) fornece uma raizde f(x) = 0.

Teorema 4.1. Se f(x) e uma funcao contınua sobre algum intervalo [a, b] e e satisfeita a de-

sigualdade f(a)f(b) < 0, entao a equacao f(x) = 0 tem pelo menos uma raiz real no intervalo

]a, b[.

Observacoes: Sob as hipoteses do teorema anterior, outro resultado importante e que a equacao

f(x) = 0 possui pelo menos uma raiz real ou um numero ımpar de raızes incluindo a multiplicidade

no intervalo ]a, b[.

Graficamente, alguns dos casos que podem acontecer sao os mostrados na figura 4.3.


Figura 4.3 Se f(a)f(b) < 0 entao existe pelo menos uma raiz no intervalo ]a, b[. No primeiro

grafico, existe exatamente uma raiz, no segundo, tres raızes e no terceiro, duas raızes.

Observacao: Sob as hipoteses do teorema anterior, se f ′(x) existir e preservar o sinal em ]a, b[,

entao este intervalo contem um unico zero de f(x). Veja a figura 4.4

f ′(x) > 0, ∀ x ∈ [a, b] f ′(x) < 0, ∀ x ∈ [a, b]

Figura 4.4 Se f(a)f(b) < 0 e f ′(x) preservar o sinal em (a, b), entao existe uma unica raiz nointervalo ]a, b[.

Tambem pode-se construir uma tabela dos valores da funcao f(x) para varios valores

de x e obter uma aproximacao inicial de uma raiz da equacao.

Exemplo 4.1. Para obter uma aproximacao inicial de uma raiz da equacao

f(x) = cos(x)− xex = 0,

pode-se construir uma tabela dos valores da funcao f(x) para varios valores de x. Consegue-se

4.3 Criterios de Parada 34

x f(x)

0 1

0,5 0,0532

1,0 -2,1780

1,5 -6,6518

2,0 -15,1942

A partir da tabela, encontra-se que a equacao f(x) = 0 tem pelo menos uma raiz

no intervalo ]0, 5 , 1, 0[. Entao, as escolhas possıveis para uma aproximacao inicial podem ser

x0 = 0, 5, x0 = 1, 0 ou x0 =0, 5 + 1, 0

2 = 0, 75. �

4.3 Criterios de Parada

A partir de uma aproximacao inicial x0, qualquer metodo iterativo gera uma sequencia

de aproximantes{

xk

}

={

x1, x2, x3, . . . , xk, . . .}

de uma raiz da equacao. Devido a limitacoes

fısicas, tal sequencia nao pode ser infinita.

Portanto, existe a necessidade de estabelecer criterios de parada para construir

uma sequencia finita de aproximantes{

x1, x2, x3, . . . , xk

}

. Os criterios mais comuns sao enumer-

ados a seguir

1. numero fixo de iteracoes, isto e, a formula do metodo iterativo deve ser utilizada

um numero prescrito, N , de vezes;

2. parada baseada no erro absoluto do aproximante: dada uma tolerancia

de erro prescrita, ε, deve-se parar se

∣

∣xk − xk−1

∣

∣ < ε.

3. parada baseada no erro relativo do aproximante: dada uma tolerancia

de erro prescrita, ε, deve-se parar se

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

< ε.

4. parada baseada em um numero de dıgitos significativos exatos do aprox-

imante: se deseja-se obter um aproximante xk com M dıgitos significativos exatos

4.4 O Metodo da Bissecao 35

(com relacao ao valor exato da raiz), deve-se parar quando

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

< 0, 5× 10−M+1.

4.4 O Metodo da Bissecao

Este metodo esta baseado na aplicacao repetida do teorema do valor intermediario.

Se e sabido que uma raiz de f(x) = 0 encontra-se no intervalo I0 =]a0, b0[, entao bisseca-se I0 no

ponto x0 = a0 + b02 . Define-se o intervalo I1 com uma aquela metade do intervalo I0 que ainda

contem a raiz, para isto deve-se ter que

I1 =]a1, b1[=

]a0, x0[, se f(a0)f(x0) < 0,

]x0, b0[, se f(a0)f(x0) > 0.

Ja que o intervalo I1 contem a raiz, entao procede-se a bissecar este intervalo novamente para obter

um intervalo I2, e assim por diante.

O k-esimo passo deste metodo pode ser descrito da seguinte maneira: Dado o intervalo

Ik−1 =]ak−1, bk−1[, que contem a raiz da equacao f(x) = 0, bisseca-se tal intervalo no ponto

xk−1 =ak−1 + bk−1

2 e escolhe-se aquela metade do intervalo que ainda contem a raiz, mediante o

seguinte teste

Ik =]ak, bk[=

]ak−1, xk−1[, se f(ak−1)f(xk−1) < 0,

]xk−1, bk−1[, se f(ak−1)f(xk−1) > 0.

No caso que f(xk−1) = 0, entao xk−1 e uma raiz de f(x) = 0.

Cada passo deste metodo, requer uma avaliacao da funcao f(x): f(xk−1).

Os resultados obtidos a partir do metodo da bissecao podem ser arranjados em uma

tabela com o seguinte formato:

4.4 O Metodo da Bissecao 36

k ak bk xk = ak + bk2 Erro:

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

Sinal de f(ak) Sinal de f(xk)

0 a0 b0 x0 - < 0 ou > 0 < 0 ou > 0

1 a1 b1 x1

∣

∣x1 − x0

∣

∣

∣

∣x1

∣

∣

< 0 ou > 0 < 0 ou > 0

2 a2 b2 x2

∣

∣x2 − x1

∣

∣

∣

∣x2

∣

∣

< 0 ou > 0 < 0 ou > 0

......

......

......

...

Este metodo, constroi uma sequencia de intervalos I0 ⊃ I1 ⊃ I2 ⊃ . . . tal que cada

intervalo contem a raiz. Depois de repetir o procedimento N vezes, ou a raiz e achada ou obtem-se

um intervalo IN de comprimento bN − aN = b0 − a0

2N que contem a raiz. A aproximacao desejada

da raiz e tomada como xN = aN + bN2 .

Este metodo e simples e a sequencia de aproximantes{

xk

}

sempre converge a raiz ξ.

Se e permitido um erro ε entao o numero aproximado de iteracoes requeridas pode ser determinado

a partir da seguinte relacao

b0 − a0

2n< ε ou n >

ln(b0 − a0)− ln(ε)

ln(2)(4.7)

O mınimo numero de iteracoes requerido para aproximar uma raiz no intervalo ]0, 1[

para um ε dado e dado na tabela a seguir

ε n

10−2 7

10−3 10

10−4 14

10−5 17

10−6 20

10−7 24

Assim, o metodo da bissecao requer um grande numero de iteracoes para atingir um

grau razoavel de precisao para a raiz.

Exemplo 4.2. Efetuar seis iteracoes do metodo da bissecao para obter uma aproximacao da raiz

da equacao

f(x) = x3 − 5x+ 1 = 0

no intervalo ]0, 1[ e determinar quantos dıgitos significativos exatos possui o aproximante da raiz.

4.5 O Metodo da Falsa Posicao 37

Tem-se que f(0) = 1 > 0 e f(1) = −5 < 0. Agora, monta-se a tabela

k ak bk xk = ak + bk2 Erro:

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

f(ak) f(xk)

0 0 1 0, 5 - 1 −1.375

1 0 0, 5 0, 25 1 1 −0, 234375

2 0 0, 25 0, 125 1 1 0.376953125

3 0, 125 0, 25 0, 1875 0, 3 0.376953125 0, 0690917969

4 0, 1875 0, 25 0, 21875 0, 1428571429 0, 0690917969 −0, 083282471

5 0, 1875 0, 21875 0, 203125 0, 07692307692

Entao a aproximacao da raiz ξ e x5 = 0.203125 e o erro relativo e

∣

∣x5 − x4

∣

∣

∣

∣x5

∣

∣

= 0, 07692307692< 0, 5× 100 = 0, 5× 10−1+1

o que indica que o aproximante tem 1 dıgito significativo exato.

4.5 O Metodo da Falsa Posicao

O metodo da falsa posicao tem uma abordagem analoga a do metodo da bissecao.

Quando f(a0)f(b0) < 0 a raiz encontra-se no intervalo [a0, b0] se a0 < b0, ou, no intervalo [b0, a0]

se b0 < a0. No metodo da bissecao, o aproximante x0 e calculado como a media entre a0 e

b0, x0 = a0 + b02 . No metodo da bissecao, calcula-se o aproximante seguinte, x0, como a media

ponderada entre a0 e b0 com pesos |f(b0)| e |f(a0)|, respectivamente. Tem-se, entao

x0 =a0|f(a0)|+ b0|f(b0)||f(b0)|+ |f(b0)|

=a0f(b0)− b0f(a0)

f(b0)− f(a0), (4.8)

devendo-se a ultima igualdade ao fato que f(a0)f(b0) < 0. A seguir, se f(a0)f(x0) < 0, escolhe-se

a1 = a0 e b1 = x0, e se f(a0)f(x0) > 0, escolhe-se a1 = x0 e b1 = b0. O processo e continuado

sabendo que f(a1)f(b1) < 0.

Os resultados obtidos a partir do metodo da falsa posicao podem ser arranjados em

uma tabela com o seguinte formato:

4.5 O Metodo da Falsa Posicao 38

k ak bk f(ak) f(bk) xk =akf(bk)− bkf(ak)f(bk)− f(ak)

Erro:

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

f(xk)

0 a0 b0 f(a0) f(b0) x0 - f(x0)

1 a1 b1 f(a1) f(b1) x1

∣

∣x1 − x0

∣

∣

∣

∣x1

∣

∣

f(x1)

2 a2 b2 f(a2) f(b2) x2

∣

∣x2 − x1

∣

∣

∣

∣x2

∣

∣

f(x2)

......

......

......

......

Exemplo 4.3. Efetuar tres iteracoes do metodo da falsa posicao para obter uma aproximacao da

raiz da equacao

f(x) = x3 − 5x+ 1 = 0

no intervalo ]0, 1[ e determinar quantos dıgitos significativos exatos possui o aproximante da raiz.

Tem-se que f(0) = 1 > 0 e f(1) = −5 < 0. Agora, monta-se a tabela


Erro:

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

f(xk)

0 0 1 1 −3 0, 25 - −0, 234375

1 0 0, 25 1 −0, 234375 0, 202532 0, 234375 −0, 004351

2 0 0, 202532 1 −0, 004351 0, 201654 0, 004351 -

Entao a aproximacao da raiz ξ e x5 = 0.202532 e o erro relativo e

∣

∣x2 − x1

∣

∣

∣

∣x2

∣

∣

= 0, 004351 < 0, 5× 10−2 = 0, 5× 10−3+1

o que indica que o aproximante tem 3 dıgitos significativos exatos.

Observe que, na verdade, efetua-se uma so avaliacao funcional por iteracao. Por

exemplo, f(a1) = f(a0) e f(b1) = f(x0).

A seguir, mostra-se um exemplo onde a velocidade de convergencia e menor que no

caso anterior.

Exemplo 4.4. Utilizando o metodo da falsa posicao, obtenha uma aproximacao da raiz da equacao

f(x) = cos(x) − xex = 0

no intervalo ]0, 1[ com dois dıgitos significativos exatos.

Para se ter uma aproximacao com dois dıgitos significativos exatos, o erro relativo

deve ser menor que 0, 5× 10−2+1 = 0, 5× 10−1 = 0, 05.

4.6 O Metodo das Cordas 39

Tem-se que f(0) = 1 > 0 e f(1) = −2.177980 < 0. Agora, monta-se a tabela


Erro:

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

f(xk)

0 0 1 1 −2, 177980 0, 314665 - 0, 519871

1 0, 314665 1 0, 519871 −2, 177980 0, 446728 0, 295622 0, 203545

2 0, 446728 1 0, 203545 −2, 177980 0, 494015 0, 095720 0, 070802

3 0, 494015 1 0, 070802 −2, 177980 0, 509946 0, 031240 -

Entao a aproximacao da raiz ξ e x3 = 0, 509946 e o erro relativo e

∣

∣x3 − x2

∣

∣

∣

∣x3

∣

∣

= 0, 031240 < 0, 5× 10−1 = 0, 5× 10−2+1

o que indica que o aproximante tem 2 dıgitos significativos exatos.

4.6 O Metodo das Cordas

Sabe-se que se f(x) = 0 e uma equacao de primeiro grau em x entao pode ser resolvida

facilmente. O metodo das cordas produz resultados exatos se f(x) = 0 e uma equacao de primeiro

grau.

A ideia do metodo esta baseada na seguinte condicao: Se xk−1 e xk sao dois aproxi-

mantes consecutivos da raiz da equacao f(x) = 0, entao, denotando por

fk−1 ≡ f(xk−1) e fk ≡ f(xk),

substitui-se a funcao f(x) pela reta (ou corda) que passa pelos pontos (xk−1, fk−1) e (xk, fk) e

toma-se o ponto de intersecao dessa reta com o eixo x como o aproximante xk+1 da raiz.

Assim, se f(x) e aproximada por uma funcao de primeiro grau, entao

f(x) = a1x+ a0. (4.9)

Para obter a0 e a1, tem-se que impor as condicoes que os pontos (xk−1, fk−1) e (xk, fk)

satisfazem a equacao (4.9):

fk−1 = a1xk−1 + a0, (4.10)

4.6 O Metodo das Cordas 40

e

fk = a1xk + a0, (4.11)

Resolvendo as equacoes (4.10) e (4.11), obtem-se

a1 =fk − fk−1

xk − xk−1(4.12)

e

a0 =xkfk−1 − xk−1fk

xk − xk−1. (4.13)

A solucao da equacao

a1x+ a0 = 0 (4.14)

esta dada por

x = −a0

a1, (4.15)

e utilizando as equacoes (4.12) e (4.13), o aproximante xk+1 esta dado por

xk+1 =xk−1fk − xkfk−1

fk − fk−1, (4.16)

que tambem pode ser escrito como

xk+1 = xk −xk − xk−1

fk − fk−1fk. (4.17)

Os resultados podem ser organizados de acordo com o formato a seguir

k xk Erro:

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

fk xk − xk−1 fk − fk−1

0 x0 - f0 - -

1 x1

∣

∣x1 − x0

∣

∣

∣

∣x1

∣

∣

f1 x1 − x0 f1 − f0

2 x2

∣

∣x2 − x1

∣

∣

∣

∣x2

∣

∣

f2 x2 − x1 f2 − f1...

......

......

...

Exemplo 4.5. Utilize o metodo das cordas para determinar uma raiz da equacao

f(x) = cos(x) − xex = 0

com 3 dıgitos significativos exatos.

4.7 O Metodo de Newton-Raphson 41

Considere as aproximacoes iniciais x0 = 0 e x1 = 1. O metodo tem que ser aplicado

ate conseguir um erro relativo

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

< 0, 5× 10−3+1 = 0, 005.

Entao

k xk Erro:

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

fk xk − xk−1 fk − fk−1

0 0 - 1 - -

1 1 1 −2.177980 1 −3.177980

2 0, 314665 2, 177980 0, 519871 −0, 685335 2, 697851

3 0, 446728 0, 295622 0, 203545 0, 132063 −0, 316326

4 0, 531706 0, 159821 −0, 042931 0, 084978 −0, 246476

5 0, 516904 0, 028635 0, 002593 −0, 014801 0, 045524

6 0, 517747 0, 001628 - - -

Entao o aproximante x6 = 0, 517747 tem 3 dıgitos significativos exatos. �

4.7 O Metodo de Newton-Raphson

O metodo de Newton-Raphson tambem esta baseada na ideia de substituir f(x) = 0

por uma equacao de primeiro grau.

A ideia do metodo esta baseada na seguinte condicao: Se xk e um aproximante da

raiz da equacao f(x) = 0, entao substitui-se a funcao f(x) pela reta que passa pelo ponto (xk, fk)

e cujo coeficiente angular tem o mesmo valor que a derivada da funcao no ponto xk, denotado por

f ′k ≡ f ′(xk). O aproximante xk+1 da raiz e tomado como o ponto de intersecao dessa reta com o

eixo x.

Assim, se f(x) e aproximada por uma funcao de primeiro grau, entao

f(x) = a1x+ a0. (4.18)

Para obter a0 e a1, tem-se que impor as condicoes que o ponto (xk, fk) satisfaz a

equacao (4.18):

fk = a1xk + a0, (4.19)


e que

f ′k = a1. (4.20)

Resolvendo as equacoes (4.19) e (4.20), obtem-se

a1 = f ′k (4.21)

a0 = fk − xkf′k. (4.22)

A solucao da equacao

a1x+ a0 = 0 (4.23)

esta dada por

x = −a0

a1, (4.24)

e utilizando as equacoes (4.21) e (4.22), o aproximante xk+1 esta dado por

xk+1 = xk −fk

f ′k

. (4.25)

Pode-se dizer que este metodo e o caso limite do metodo das cordas quando xk−1 −→xk.

Os resultados podem ser arranjados de acordo com o formato a seguir

k xk Erro:

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

fk f ′k

0 x0 - f0 f ′0

1 x1

∣

∣x1 − x0

∣

∣

∣

∣x1

∣

∣

f1 f ′1

2 x2

∣

∣x2 − x1

∣

∣

∣

∣x2

∣

∣

f2 f ′2

......

......

...

Exemplo 4.6. Utilize o metodo de Newton-Raphson para determinar uma raiz da equacao

f(x) = cos(x) − xex = 0

com 3 dıgitos significativos exatos.


A derivada da funcao f(x) esta dada por

f ′(x) = −sen(x) − (x+ 1)ex

Considere a aproximacao inicial x0 = 0. O metodo tem que ser aplicado ate conseguir

um erro relativo∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

< 0, 5× 10−3+1 = 0, 005.

Entao

k xk Erro:

∣

∣xk − xk−1

∣

∣

∣

∣xk

∣

∣

fk f ′k

0 0 - 1 −1

1 1 1 −2.177980 −6, 278034

2 0, 653079 0, 531207 −0, 460642 −3, 783942

3 0, 531343 0, 229110 −0, 041803 −3.111838

4 0, 517910 0, 025938 −0, 000464 −3.042901

5 0, 517757 0, 000295 - -

Entao o aproximante x5 = 0, 517757 tem 4 dıgitos significativos exatos. �

Exemplo 4.7. Encontre a aproximacao inicial x0 para encontrar 1N , onde e um numero inteiro

positivo, mediante o metodo de Newton de maneira que seja atingida a convergencia.

A equacao a ser resolvida pode ser escrita como

f(x) =1

x−N = 0.

A equacao iterativa de Newton fica

xk+1 = xk −f(xk)

f ′(xk)= xk −

1xk−N− 1x2

k

= xk + x2k

(

1

xk−N

)

= 2xk −Nx2k

Desenhe os graficos de y = x e y = 2x−Nx2. A segunda curva e a parabola

(

x− 1

N

)2

= − 1

N

(

y − 1

N

)

.

Os graficos estao dados na figura 4.5. O ponto de intersecao destas duas curvas e o valor requerido,

1N . A partir da figura 4.5, encontra-se que qualquer aproximacao inicial fora do intervalo 0 < x0 <

4.8 A Velocidade de Convergencia 44

2N diverge. Se x0 = 0, a iteracao nao converge a 1

N mas permanece sempre zero. Isto mostra a

importancia da escolha de uma aproximacao inicial adequada.

Figura 4.5 Escolha da aproximacao inicial

�

4.8 A Velocidade de Convergencia

Agora, estuda-se a velocidade a qual o metodo iterativo converge se a aproximacao

inicial a raiz esta suficientemente proximo a raiz desejada.

Definicao 4.6. Um metodo iterativo e dito de ordem p ou tem a velocidade de convergencia

p, se p e o maior numero real positivo para o qual existe uma constante finita C 6= 0 tal que

∣

∣ǫk+1

∣

∣ ≤ C∣

∣ǫk∣

∣

p(4.26)

onde ǫk = xk − ξ e o erro absoluto na k-esima iterada. A constante C e chamada a constante

assintotica de erro e geralmente depende das derivadas de f(x) em x = ξ.

Agora, enunciam-se os resultados correspondentes para os metodos da bissecao, das

cordas e de Newton:

Teorema 4.2. A velocidade de convergencia do metodo da bissecao e p = 1 e a constante

assintotica de erro e C = 12 .

4.9 Eficiencia de um Metodo 45

Teorema 4.3. A velocidade de convergencia do metodo das cordas e p = 1 +√

52 e a constante

assintotica de erro e C =f ′′(ξ)2f ′(ξ)

.

Teorema 4.4. A velocidade de convergencia do metodo de Newton e p = 2 e a constante assintotica

de erro e C =f ′′(ξ)2f ′(ξ)

.

4.9 Eficiencia de um Metodo

Definicao 4.7. O ındice de eficiencia de um metodo iterativo no sentido de Traub define-se

pela equacao

E∗ = p1/n (4.27)

onde p e a ordem do metodo e n e o numero total de avaliacoes da funcao f(x) e suas derivadas

em cada passo da iteracao.

Obviamente, se o valor do ındice e maior, entao o metodo e mais eficiente. A tabela

a seguir da o ındice de eficiencia dos metodos discutidos nas secoes previas.

Metodo n p E∗

Bissecao 1 1 1

Cordas 1 1,62 1,62

Newton 2 2 1,41

4.10 Equacoes Polinomiais

Os metodos discutidos nas secoes previas podem ser aplicados diretamente para obter

as raızes de uma equacao polinomial de grau n

pn(x) = anxn + an−1x

n−1 + · · ·+ a1x+ a0 = 0 (4.28)

onde an 6= 0, an−1, . . . , a1, a0 sao numeros reais. Porem, se o objetivo e determinar todas as raızes

(reais e complexas) de uma equacao polinomial, entao e vantajoso do ponto de vista computacional

utilizar os metodos diretos de solucao.

E util saber a seguinte informacao com relacao as raızes:

(i) O numero exato de raızes reais e complexas junto com as respectivas multiplicidades.

4.10 Equacoes Polinomiais 46

(ii) Um intervalo em que cada raiz se encontre.

Para determinar intervalos onde as raızes reais estao localizadas, pode-se utilizar o

seguinte teorema

Teorema 4.5. (Teorema de Lagrange) Seja a equacao polinomial


n−1 + · · ·+ a1x+ a0 = 0

onde an > 0. Entao uma cota superior para as raızes positivas da equacao polinomial esta dada

por

L = 1 + n−k

√

B

an(4.29)

onde

B =

0, se aj ≥ 0, ∀j = 0, 1, . . . , n− 1

max{

|aj | : aj < 0}

, se aj < 0, para algum j = 0, 1, . . . , n− 1

e k e a maior potencia de x correspondente a um coeficiente aj negativo.

Para estabelecer as outras cotas superiores das raızes, positivas e negativas, o teorema

de Lagrange pode ser aplicado nos polinomios

xnpn(1/x) resultando a cota de Lagrange L1; (4.30)

pn(−x) resultando a cota de Lagrange L2; (4.31)

e

xnpn(−1/x) resultando a cota de Lagrange L3. (4.32)

Entao, todas as raızes positivas do polinomio encontram-se no intervalo

[

1

L1, L

]

,

e as raızes negativas encontram-se no intervalo

[

−L2,−1

L3

]

.

Exemplo 4.8. Seja a equacao polinomial

pn(x) = x4 − 7x3 − 9x2 + 30x+ 31 = 0


entao

xnpn(1/x) = 31x4 + 30x3 − 9x2 − 7x+ 1

pn(−x) = x4 + 7x3 − 9x2 − 30x+ 31

xnpn(−1/x) = 31x4 − 30x3 − 9x2 + 7x+ 1

Entao

L = 1 +4−3

√

9

1= 10

L1 = 1 +4−2

√

9

31= 1, 5388 =⇒ 1

L1= 0, 6498

L2 = 1 +4−2

√

30

1= 6, 4772 =⇒ −L2 = −6, 4772

L3 = 1 +4−3

√

30

31= 1, 9677 =⇒ − 1

L3= −0, 5081

As raızes positivas, se existirem, encontram-se no intervalo

[

1

L1, L

]

= [0, 6498 , 10]

e as raızes negativas, se existirem, encontram-se no intervalo,

[

−L2,−1

L3

]

= [−6, 4772 , −0, 5081].

Definicao 4.8. Quando em um polinomio (os termos escritos em ordem decrescente) um sinal +

segue a um sinal + ou um sinal − segue a um sinal −, diz-se que ocorreu uma continuacao ou

permanencia de sinais. Mas se um sinal + segue a um sinal − ou um sinal − segue a um sinal

de +, diz-se que ocorreu uma mudanca de sinais.

Exemplo 4.9. O polinomio

p5(x) = 8x5 + 12x4 − 10x3 + 17x2 − 18x+ 5

tem quatro mudancas de sinais e uma continuacao de sinais.

Teorema 4.6. (Regra de sinais de Descartes) O numero de raızes reais positivas da equacao

polinomial pn(x) = 0 e igual ao numero de mudancas de sinais em pn(x) ou este numero menos

um numero par. O numero de raızes reais negativas da equacao polinomial pn(x) = 0 e igual ao

numero de mudancas de sinais em pn(−x) ou este numero menos um numero par.


Exemplo 4.10. A equacao polinomial

p5(x) = 8x5 + 12x4 − 10x3 + 17x2 − 18x+ 5 = 0

tem quatro mudancas de sinais, e portanto, tem 4, 2 ou 0 raızes reais positivas. O polinomio

p5(−x) = −8x5 + 12x4 + 10x3 + 17x2 + 18x+ 5

tem uma mudanca de sinais e portanto, 1 raiz real negativa.

Em geral, o teorema 4.6 nao fornece o numero exato de raızes reais. O numero exato

de raızes reais de uma equacao polinomial pode ser encontrado mediante o teorema de Sturm.

Definicao 4.9. Seja p(x) = 0 uma equacao polinomial de grau n com as n raızes simples. Denote

por s0(x) = p(x) e s1(x) = p′(x). Denote por s2(x) o negativo do resto de dividir s0(x) por s1(x),

s3(x) o negativo do resto de dividir s1(x) por s2(x), e assim por diante, ate chegar em sk(x) = c 6= 0

onde c e uma constante. Obtem-se uma sequencia de funcoes

s0(x), s1(x), . . . , sk(x)

denominada as funcoes de Sturm ou a sequencia de Sturm.

Se p(x) = 0 e uma equacao polinomial de grau n com raiz multipla, obtem-se como

antes, t0(x) = p(x) e t1(x) = p′(x), t2(x) o negativo do resto de dividir t0(x) por t1(x), t3(x) o

negativo do resto de dividir t1(x) por t2(x), e assim por diante, ate chegar em tk(x) que, neste

caso, nao sera constante, mas o maior divisor comum de t0(x) e t1(x). Agora, a sequencia de

Sturm e obtida dividindo cada tj(x) por tk(x):

s0(x) =t0(x)

tk(x), s1(x) =

t1(x)

tk(x), . . . , sk−1(x) =

tk−1(x)

tk(x), sk(x) = 1

Teorema 4.7. (Teorema de Sturm) O numero de raızes reais da equacao polinomial pn(x) = 0

no intervalo [a, b] e igual a diferenca entre o numero de mudancas de sinal na sequencia de Sturm

em x = a e x = b, sempre que f(a) 6= 0 e f(b) 6= 0.

Outro teorema importante e enunciado a seguir.

Teorema 4.8. (Teorema Fundamental da Algebra) A equacao polinomial


n−1 + · · ·+ a1x+ a0 = 0


onde an 6= 0, an−1, . . .a1, a0 sao numeros reais, tem exatamente n raızes reais e/ou complexas

incluindo a multiplicidade.

Exemplo 4.11. Considere a equacao polinomial

p(x) = x4 − 7x3 − 9x2 + 30x+ 31 = 0.

A seguir, aplica-se a regra de Descartes.

O numero de mudancas de sinal para p(x) e 2. Portanto, a equacao polinomial p(x) =

0 tem 2 ou 0 raızes positivas.

Tem-se que p(−x) = p(x) = x4 + 7x3 − 9x2 − 30x + 31. O numero de mudancas de

sinal para p(−x) e 2. Portanto, a equacao polinomial p(x) = 0 tem 2 ou 0 raızes negativas.

Exemplo 4.12. Considere a equacao polinomial

p(x) = x4 − 7x3 − 9x2 + 30x+ 31 = 0.

A sequencia de Sturm e

s0(x) = x4 − 7x3 − 9x2 + 30x+ 31;

s1(x) = 4x3 − 21x2 − 18x+ 30;

s2(x) = 13, 6875x2 − 14, 625x− 44, 125;

s3(x) = 22, 97666854x+ 23, 92043535;

s4(x) = 14, 06425678.

Os sinais da sequencias de Sturm que acontecem nas cotas de Lagrange sao mostradas

na seguinte tabela

−L2 = −6, 4772 − 1L3

= −0, 5081 1L1

= 0, 6498 L = 10

s0(x) > 0 > 0 > 0 > 0

s1(x) < 0 > 0 > 0 > 0

s2(x) > 0 < 0 < 0 > 0

s3(x) < 0 > 0 > 0 > 0

s4(x) > 0 > 0 > 0 > 0

A diferenca entre o numero de mudancas de sinal na sequencia de Sturm em x = −L2

e x = − 1L3

e 4-2 = 2. Portanto, existem duas raızes negativas.

4.11 O Metodo de Birge-Vieta 50

A diferenca entre o numero de mudancas de sinal na sequencia de Sturm em x = 1L1

e x = L e e 2-0 = 2. Portanto, existem duas raızes positivas.

De acordo com o Teorema Fundamental da Algebra, a equacao polinomial proposta

tem quatro raızes reais e nenhuma raiz complexa.

O metodo de Newton pode ser adaptado para encontrar raızes reais de uma equacao

polinomial. Este e o tema das proximas secoes.

4.11 O Metodo de Birge-Vieta

Dada a equacao polinomial


n−1 + · · ·+ a1x+ a0 = 0,

o metodo de Newton pode ser escrito como

xk+1 = xk −pn(xk)

p′n(xk), k = 0, 1, 2, . . . (4.33)

onde x0 e uma aproximacao inicial da raiz requerida. O calculo dos valores pn(xk) e p′n(xk) em

cada iteracao pode ser efetuado mediante o esquema de Ruffini. Esta e a ideia basica do metodo

de Birge-Vieta.

O esquema pratico para calcular os valores de pn(xk) e p′n(xk) e como segue. Dispoem-

se os coeficientes de pn(x) de acordo com a ordem crescente dos termos e e feita a divisao por (x−xk)

duas vezes consecutivas:

an an−1 · · · a2 a1 a0

xk xkbn · · · xkb3 xkb2 xkb1

bn bn−1 · · · b2 b1 b0

xk xkcn · · · xkc3 xkc2

cn cn−1 · · · c2 c1

e o metodo pode ser escrito como

xk+1 = xk −b0c1, k = 0, 1, 2, . . . (4.34)

onde em cada iteracao sao calculados os valores b0 e c1.

4.12 O Metodo de Bairstow 51

Exemplo 4.13. Efetuar duas iteracoes do metodo de Birge-Vieta para encontrar a menor raiz

positiva da equacao

p(x) = x4 − 3x3 + 3x2 − 3x+ 2 = 0

Considere a aproximacao inicial x0 = 0, 5. Efetua-se uma iteracao do metodo

1 −3 3 −3 2

0, 5 0, 5 −1, 25 0, 875 −1, 0625

1 −2, 5 1, 75 −2, 125 0, 9375

0, 5 0, 5 −1, 0 0, 375

1 −2, 0 0, 75 −1, 75

obtem-se entao

x1 = x0 −b0c1

= 0, 5 +0, 9375

1, 75= 1, 0356

Mais uma vez, efetua-se uma iteracao do metodo

1 −3 3 −3 2

1, 0356 1, 0356 −2, 0343 1, 0001 −2, 0711

1 −1, 9644 0, 9657 −1, 9999 −0, 0711

1, 0356 1, 0356 −0, 9619 0, 0039

1 −0, 9288 0, 0038 −1, 9960

logo,

x2 = x1 −b0c1

= 1, 0356− 0, 0711

1, 9960= 0, 999979

A raiz exata e 1, 0.

4.12 O Metodo de Bairstow

O metodo de Bairstow extrai um fator quadratico da forma x2 +αx+β do polinomio


n−1 + · · ·+ a1x+ a0,

gerando uma sequencia de polinomios quadraticos x2 +α0x+β0, x2 +α1x+ β1, . . .x2 +αkx+βk.

4.12 O Metodo de Bairstow 52

Para dividir o polinomio pn(x) por

x2 + αkx+ βk

pode-se utilizar uma variante do metodo de Ruffini

an an−1 an−2 · · · a2 a1 a0

−αk −αkbn −αkbn−1 · · · αkb3 −αkb2 −αkb1

−βk −βkbn · · · −βkb4 −βkb3 −βkb2

bn bn−1 bn−2 · · · b2 b1 b0

Entao, o quociente e o polinomio

qn(x) = bnxn−2 + bn−1x

n−3 + · · ·+ b3x+ b2

e o resto e

r(x) = b1x+ (b0 + αkb1)

Exemplo 4.14. Divida o polinomio p(x) = x5 + 2x4 − 3x + 2 pelo polinomio quadratico q(x) =

x2 + 3x− 1.

O esquema de divisao seria

1 2 0 0 −3 2

−3 −3 3 −12 39 −120

1 1 −1 4 −13

1 −1 4 −13 40 −131

Entao, o quociente e o polinomio q(x) = x3 − x2 + 4x− 13 e o resto e r(x) = 40x− 11.

O metodo de Bairstow utiliza o esquema de divisao para gerar um polinomio quadratico

x2 + αk+1x+ βk+1 que aproxima o verdadeiro fator x2 + νx+ ξ do polinomio pn(x); isto e feito a


partir de um polinomio quadratico x2 + αkx+ βk mediante o esquema

an an−1 an−2 · · · a2 a1 a0

−αk −αkbn −αkbn−1 · · · αkb3 −αkb2 −αkb1

−βk −βkbn · · · −βkb4 −βkb3 −βkb2

bn bn−1 bn−2 · · · b2 b1 b0

−αk −αkcn−1 −αkcn−2 · · · αkc2 −αkc1

−βk −βkcn−1 · · · −βkc3 −βkc2

cn−1 cn−2 cn−3 · · · c1 c0

Logo, considere

∆αk = − b0c2 − b1c1c21 − c2(c0 − b1)

. (4.35)

e

∆βk = −b1(c0 − b1)− b0c1c21 − c2(c0 − b1)

. (4.36)

Os valores melhorados αk+1 e βk+1 estao dados por

αk+1 = αk + ∆αk (4.37)

e

βk+1 = βk + ∆βk. (4.38)

4.13 Problemas Propostos

1. Calcular pelo menos uma raiz real das equacoes com um erro relativo menor que 10−1

pelo metodo da bissecao

(a) x+ ln(x) = 0

(b) 3x− cos(x) = 0

(c) x+ 2 cos(x) = 0


pelo metodo das cordas

(a) x2 − ln(x) − 5 = 0

(b) x3 − e2x + 3 = 0

(c) sen(x)− ln(x) = 0



pelo metodo de Newton

(a) 0, 1x3 − e2x + 2 = 0

(b) sen(x)− ln(x) = 0

(c) ecos(x) + x3 − 3 = 0

4. Faca uma tabela de valores para a funcao f(x) = cos(x) + 2ex−1 − 3 para os valores

x = 1, 0 1, 1 1, 2 1, 6 1, 4 1, 5. Utilizando esta tabela,

(a) Aplique o metodo da bissecao para encontrar a unica raiz real da equacao

f(x) = cos(x) + 2ex−1 − 3 = 0

com 3 dıgitos significativos exatos;

(b) Aplique o metodo das cordas para encontrar a unica raiz real da mesma equacao

com 3 dıgitos significativos exatos, utilizando como aproximacoes iniciais os val-

ores onde a funcao muda de sinal na tabela;

(c) Aplique o metodo de Newton para encontrar a unica real renl da equacao com 3

dıgitos significativos exatos, utilizando x0 = 1, 4.

5. Desenhe aproximadamente a funcao iterativa y = φ(x) junto com a reta y = x para

estudar a convergencia do metodo de Newton xk+1 = φ(

xk

)

para as seguintes equacoes

(a) f(x) = x2 −N ,

(b) f(x) = x− Nx

onde N e um inteiro positivo.

6. Desenhe aproximadamente a funcao iterativa y = φ(x) junto com a reta y = x para

estudar a convergencia do metodo iterativo xk+1 = φ(

xk

)

para as seguintes funcoes

iterativas

(a) φ(x) = 23x+ N

3x2

(b) φ(x) = x+ Nx

7. Calcule as cotas de Lagrange para as raızes reais negativas e positivas das seguintes

equacoes polinomiais:

(a) p(x) = x5 − 3x+ 1 = 0


(b) p(x) = x5 − 3x− 1 = 0

(c) p(x) = 2x4− 20x3 + 70x2

− 100x + 47 = 0

(d) p(x) = 4x4 − 16x3 − 28x2 + 88x+ 95 = 0

8. Calcule a sequencia de Sturm para os polinomios da parte (a) e determine de maneira

exata quantas raızes positivas e negativas possui cada equacao polinomial.

9. Utilize o metodo de Birge-Vieta para calcular, com dois dıgitos significativos exatos, a

menor raiz positiva, se existir, das equacoes polinomiais da parte (a), utilizando como

aproximacao inicial x0 a menor cota positiva de Lagrange.

10. Divida os seguintes polinomios pela tecnica de divisao do metodo de Bairstow:

(a) p(x) = x6 − x5 + 7x3 + 8, d(x) = x2 + 2x− 1

(b) p(x) = x6 + 3x5 − x4 + 8x, d(x) = x2 + x+ 3

5 SISTEMAS DE EQUACOES ALGEBRICAS LINEARES

5.1 Introducao

Considere um sistema de m equacoes lineares algebricas com n incognitas

a11x1 + a12x2 + · · ·+ a1nxn = b1

a21x1 + a22x2 + · · ·+ a2nxn = b2

...

am1x1 + am2x2 + · · ·+ amnxn = bm

(5.1)

onde aij sao valores escalares conhecidos, bi, i = 1, . . . ,m sao valores conhecidos e xi, i = 1, . . . , n

sao as incognitas a serem determinadas.

Introduz-se a seguinte notacao e definicoes

A matriz de ordem m× naij elemento na i-esima linha e j-esima coluna da matriz A

A−1 inversa de A

AT transposta de A

det(A) = |A| determinante de A

Mij menor de aij em A

Cij cofator de aij em A

0 matriz nula

I matriz identidade

D matriz diagonal de ordem n

L matriz triangular inferior de ordem n

U matriz triangular superior de ordem n

P matriz de permutacao

x vetor coluna com elementos xi, i = 1, . . . , n

O sistema de equacoes (5.1) pode ser escrito de maneira matricial como

Ax = b, (5.2)

56

5.2 Metodos Diretos 57

onde

A =

a11 a12 . . . a1n

a21 a22 . . . a2n

......

. . ....

am1 am2 . . . amn

, x =

x1

x2

...

xn

e b =

b1

b2...

bm

.

Os metodos de solucao de um sistema de equacoes algebricas lineares (5.1) podem ser

classificados de maneira ampla em dois tipos:

(i) Metodos Diretos: Estes metodos produzem a solucao exata apos um numero finito de

passos (sem levar em conta os erros de arredondamento).

(ii) Metodos Iterativos: Estes metodos originam uma sequencia de solucoes aproximadas,

que converge quando o numero de passos tende a infinito.

Os metodos diretos e iterativos estudados aqui serao aplicados para sistemas quadra-

dos, isto e, no caso que m = n, ou seja, o numero de equacoes coincide com o numero de incognitas.

5.2 Metodos Diretos

O sistema de equacoes (5.1) pode ser resolvido diretamente pela regra de Cramer.

5.2.1 A Regra de Cramer

Tem-se que

xi =|Bi||A| , i = 1, 2, . . . , n, (5.3)

onde |Bi| e o determinante da matrix obtida por substituir a i-esima coluna de A pelo vetor b.

O vetor x esta dado por

x =1

|A|

C11 C21 . . . Cn1

C12 C22 . . . Cn2

......

. . ....

C1n C2n . . . Cnn

b1

b2...

bn

=1

|A|adj(A)b = A−1b. (5.4)

onde Cij e o cofator correspondente ao elemento aij da matriz A. Esta expressao e equivalente a

equacao (5.3). A regra de Cramer fornece um metodo de obter a solucao imediatamente, mas estas


solucoes envolvem n + 1 determinantes de ordem n. Esta caracterıstica torna a regra de Cramer

impraticavel na resolucao de sistemas.

Exemplo 5.1. Resolva o sistema

x1 + 2x2 − x3 = 2

3x1 + 6x2 + x3 = 1

3x1 + 3x2 + 2x3 = 3

utilizando a regra de Cramer.

A solucao das equacoes podem ser escritas como

xi =|Bi||A| , i = 1, 2, 3,

onde

|B1| =

∣

∣

∣

∣

∣

∣

∣

∣

∣

2 2 −1

1 6 1

3 3 2

∣

∣

∣

∣

∣

∣

∣

∣

∣

, |B2| =

∣

∣

∣

∣

∣

∣

∣

∣

∣

1 2 −1

3 1 1

3 3 2

∣

∣

∣

∣

∣

∣

∣

∣

∣

, |B3| =

∣

∣

∣

∣

∣

∣

∣

∣

∣

1 2 2

3 6 1

3 3 3

∣

∣

∣

∣

∣

∣

∣

∣

∣

, |A| =

∣

∣

∣

∣

∣

∣

∣

∣

∣

1 2 −1

3 6 1

3 3 2

∣

∣

∣

∣

∣

∣

∣

∣

∣

ou

|B1| = 35, |B2| = −13, |B3| = −15, |A| = 12

que fornece a solucao

x1 =35

12, x2 = −13

12, x3 = −15

12.

Exemplo 5.2. Resolva o sistema

x1 + 2x2 + 2x3 = 6

x1 + 2x2 + x3 = 1

2x1 + x2 + x3 = 4

utilizando a equacao (5.4).

Tem-se que

|A| =

∣

∣

∣

∣

∣

∣

∣

∣

∣

1 2 2

1 2 1

2 1 1

∣

∣

∣

∣

∣

∣

∣

∣

∣

= −3.


e

adj (A) =

1 0 −2

1 −3 1

−3 3 0

.

Assim, utilizando a equacao (5.4), obtem-se

x =1

−3

1 0 −2

1 −3 1

−3 3 0

6

1

4

=

23

−73

5

.

5.2.2 Eliminacao Gaussiana

Outro metodo direto e o metodo de eliminacao gaussiana. A ideia principal consiste

em transformar o sistema Ax = b em um sistema equivalente cuja matriz associada e do tipo

triangular superior. Isto pode ser feito mediante algumas operacoes elementares de matrizes:

troca de linhas e soma de uma linha com um multiplo escalar de outra linha. Se acontecer troca

de linhas, o processo de eliminacao denomina-se com pivoteamento parcial e se nao acontecer, o

processo denomina-se sem pivoteamento.

A ideia do metodo e transformar a matriz aumentada

(

A...b

)

=

a11 a12 . . . a1n

... b1

a21 a22 . . . a2n

... b2...

.... . .

......

...

an1 an2 . . . ann

... bn

na matriz

(

A(n)...b(n)

)

=

a(n)11 a

(n)12 . . . a

(n)1n

... b(n)1

0 a(n)22 . . . a

(n)2n

... b(n)2

......

. . ....

......

0 0 . . . a(n)nn

... b(n)n

mediante a troca de linhas e soma de uma linha com um multiplo escalar de outra linha. A

ultima matriz representa um sistema triangular superior de equacoes lineares que pode ser resolvido

facilmente mediante a tecnica denominada retro-substituicao.


Exemplo 5.3. Resolver o sistema de equacoes lineares

10x1 + x2 − 5x3 = 1

−20x1 + 3x2 + 20x3 = 2

5x1 + 3x2 + 5x3 = 6

mediante a eliminacao gaussiana sem pivoteamento.

A matriz aumentada do sistema e transformada na forma triangular superior:

10 1 −5 1

−20 3 20 2

5 3 5 6

l2−−20

10l1−−−−−−→

l3−510

l1

10 1 −5 1

0 5 10 4

0 5/2 15/2 11/2

l3−5/2

5l2−−−−−→

10 1 −5 1

0 5 10 4

0 0 5/2 7/2

(5.5)

e isto significa que o sistema original e equivalente ao sistema triangular superior

10x1 + x2 − 5x3 = 1

5x2 + 10x3 = 4

5/2x3 = 7/2

que, utilizando a retro-substituicao, fornece a solucao

x3 = (7/2)/(5/2) = 7/5

x2 = (−10x3 + 4)/5 = −2

x1 = (−x2 + 5x3 + 1)/10 = 1.

Os elementos 10 na primeira matriz e 5 na segunda matriz sao denominados os pivos da matriz

correspondente.

Quando e utilizado o procedimento de pivoteamento parcial, e recomendavel, por

questoes de minimizar o erro cometido, fazer uma troca de equacoes de maneira que o pivo seja

aquele com o maior valor absoluto entre o elemento diagonal aii e os elementos correspondentes

da mesma coluna aij com j > i.


10x1 + x2 − 5x3 = 1

−20x1 + 3x2 + 20x3 = 2

5x1 + 3x2 + 5x3 = 6


mediante a eliminacao gaussiana com pivoteamento parcial.

A matriz aumentada do sistema e transformada na forma triangular superior:

10 1 −5 1

−20 3 20 2

5 3 5 6

l1↔l2−−−→

−20 3 20 2

10 1 −5 1

5 3 5 6

l2−10

−20l1−−−−−−→

l3−5

−20l1

−20 3 20 2

0 5/2 5 2

0 15/4 10 13/2

l2↔l3−−−→

−20 3 20 2

0 15/4 10 13/2

0 5/2 5 2

l3−5/2

15/4l2

−−−−−−→

−20 3 20 2

0 15/4 10 13/2

0 0 −5/3 −7/3

e isto significa que o sistema original e equivalente ao sistema triangular superior

−20x1 + 3x2 + 20x3 = 1

15/4x2 + 10x3 = 13/2

−5/3x3 = −7/3

que, utilizando a retro-substituicao, fornece a solucao

x3 = (−7/3)/(−5/3) = 7/5

x2 = (−10x3 + 13/2)/(15/4) = −2

x1 = (−3x2 − 20x3 + 1)/(−20) = 1.

5.2.3 Metodo de Decomposicao LU

A ideia deste metodo consiste em conseguir uma fatoracao da matriz A como A = LU

onde L e uma matriz triangular inferior e U, uma matriz triangular superior. Entao, neste caso,

o sistema

Ax = b

e equivalente a dois sistemas triangulares

Ly = b

Ux = y

O primeiro sistema pode ser resolvido pela tecnica denominada substituicao para frente e o segundo

sistema, como antes, pode ser resolvido por retro-substituicao.


O metodo de decomposicao LU tambem pode utilizar o pivoteamento parcial. Neste

caso, a montagem das matrizes L e U e feita utilizando as matrizes de permutacao, mas isto nao

sera visto aqui.

A tecnica de fatoracao da matriz A e similar ao processo de eliminacao. Isto pode ser

ilustrado no exemplo a seguir.


10x1 + x2 − 5x3 = 1

−20x1 + 3x2 + 20x3 = 2

5x1 + 3x2 + 5x3 = 6

mediante a decomposicao LU sem pivoteamento.

A matriz do sistema e transformada na forma triangular superior:

10 1 −5

−20 3 20

5 3 5

l2−−20

10l1−−−−−−→

l3−510

l1

10 1 −5

0 5 10

0 5/2 15/2

l3−5/2

5l2−−−−−→

10 1 −5

0 5 10

0 0 5/2

(5.6)

Entao, a matriz U e a ultima matriz obtida

U =

10 1 −5

0 5 10

0 0 5/2

e a matriz L esta formada por elementos diagonais unitarios e os elementos restantes pelos mul-

tiplicadores, l21 = −2010 = −2, l31 = 5

10 = 12 e l32 =

5/25 = 1

2 , ou seja,

L =

1 0 0

−2 1 0

1/2 1/2 1

.

O sistema Ly = b pode ser escrito como

y1 = 1

− 2y1 + y2 = 2

1/2y1 + 1/2y2 + y3 = 6

5.3 Metodos Iterativos 63

cuja solucao e

y1 = 1

y2 = 2y1 + 2 = 4

y3 = −1/2y1 − 1/2y2 + 6 = 7/2.

O sistema Ux = y pode ser escrito como

10x1 + x2 − 5x3 = 1

5x2 + 10x3 = 4

5/2x3 = 7/2

que fornece a solucao

x3 = (7/2)/(5/2) = 7/5

x2 = (−10x3 + 4)/5 = −2

x1 = (−x2 + 5x3 + 1)/(−10) = 1.

5.3 Metodos Iterativos

O sistema

Ax = b

pode ser resolvido numericamente mediante a construcao de um metodo iterativo. Suponha que

a matriz A pode ser escrita como a diferenca de duas outras matrizes A = S −T. Neste caso, o

sistema original pode ser escrito como

Sx = Tx + b

que origina o metodo iterativo

Sx(k+1) = Tx(k) + b (5.7)

onde em cada iteracao e gerado o vetor x(k+1) a partir do vetor x(k) mediante a equacao recursiva

(5.7) comecando com um vetor inicial x(0).

A equacao recursiva (5.7), no caso que S seja uma matriz nao singular, pode ser escrita

como

x(k+1) = S−1Tx(k) + S−1b. (5.8)


5.3.1 Metodo de Jacobi

Quando a matriz S e a parte diagonal de A, o metodo recursivo (5.7) e denominado

metodo de Jacobi.

Exemplo 5.6. Resolver o sistema

3x1 + 2x2 = 5

2x2 + x3 = 3

x1 + 2x3 = 3

mediante o metodo de Jacobi.

Neste caso,

A =

3 2 0

0 2 1

1 0 2

, S =

3 0 0

0 2 0

0 0 2

, T =

0 −2 0

0 0 −1

−1 0 0

.

Logo,

S−1 =

1/3 0 0

0 1/2 0

0 0 1/2

, S−1T =

0 −2/3 0

0 0 −1/2

−1/2 0 0

,S−1b =

5/3

3/2

3/2

e portanto a equacao iterativa (5.8) fica

x(k+1)1

x(k+1)2

x(k+1)3

=

0 −2/3 0

0 0 −1/2

−1/2 0 0

x(k)1

x(k)2

x(k)3

+

5/3

3/2

3/2

ou,

x(k+1)1 =

−2x(k)2 + 5

3

x(k+1)2 =

−x(k)3 + 3

2

x(k+1)3 =

−x(k)1 + 3

2.

Estas ultimas tres equacoes recursivas podem ser obtidas diretamente do sistema original, botando

em evidencia x1 da primeira equacao, x2 da primeira equacao e x3 da primeira equacao. Este

procedimento e muito pratico e evita o tratamento matricial da equacao (5.8).


Os criterios de parada mais comumente utilizados sao a determinacao do maior erro

absoluto ‖x(k+1) − x(k)‖, a determinacao do maior erro relativo‖x(k+1) − x(k)‖‖x(k+1)‖ e o numero pre-

determinado de iteracoes. Neste caso, ‖a‖ e qualquer norma vetorial.

A seguinte tabela mostra os resultados das primeiras cinco iteracoes para x(0) =

0

0

0

j x(j)1 x

(j)2 x

(j)3

0 0 0 0

1 5/3 3/2 3/2

2 2/3 3/4 2/3

3 7/6 7/6 7/6

4 8/9 11/12 11/12

5 19/18 25/24 19/18...

......

...

e pode-se observar que a solucao vai convergindo para o vetor

1

1

1

que e a solucao exata do

sistema.


3x1 + 2x2 + x3 = 6

2x2 + 3x3 = 5

2x1 + 2x3 = 4

mediante o metodo de Jacobi.

Neste caso,

A =

3 2 1

0 2 3

2 0 2

, S =

3 0 0

0 2 0

0 0 2

, T =

0 −2 −1

0 0 −3

−2 0 0

.


Logo,

S−1 =

1/3 0 0

0 1/2 0

0 0 1/2

, S−1T =

0 −2/3 −1/3

0 0 −3/2

−1 0 0

,S−1b =

2

5/2

2


x(k+1)1

x(k+1)2

x(k+1)3

=

0 −2/3 −1/3

0 0 −3/2

−1 0 0

x(k)1

x(k)2

x(k)3

+

2

5/2

2

ou,

x(k+1)1 =

−2x(k)2 + x

(k)3 + 6

3

x(k+1)2 =

−3x(k)3 + 5

2

x(k+1)3 =

−2x(k)1 + 4

2.


0

0

0

j x(j)1 x

(j)2 x

(j)3

0 0 0 0

1 2 5/2 2

2 -1/3 -1/2 0

3 7/3 5/2 7/3

4 -4/9 -1 -1/3

5 25/9 3 22/9

......

......

e pode-se observar que as iteradas nao convergem para solucao exata

1

1

1

do sistema.


5.3.2 Metodo de Gauss-Seidel

Quando a matriz S e a parte triangular inferior de A, o metodo recursivo (5.7) e

denominado metodo de Gauss-Seidel.


3x1 + 2x2 = 5

2x2 = 3

x1 + 2x3 = 3

mediante o metodo de Gauss-Seidel.

Neste caso,

A =

3 2 0

0 2 1

1 0 2

, S =

3 0 0

0 2 0

1 0 2

, T =

0 −2 0

0 0 −1

0 0 0

.

Logo,

S−1 =

1/3 0 0

0 1/2 0

−1/6 0 1/2

, S−1T =

0 −2/3 0

0 0 −1/2

0 1/3 0

,S−1b =

5/3

3/2

2/3


x(k+1)1

x(k+1)2

x(k+1)3

=

0 −2/3 0

0 0 −1/2

0 1/3 0

x(k)1

x(k)2

x(k)3

+

5/3

3/2

2/3

ou,

x(k+1)1 =

−2x(k)2 + 5

3

x(k+1)2 =

−x(k)3 + 3

2

x(k+1)3 =

−x(k+1)1 + 3

2.

Pode-se observar que o metodo de Gauss-Seidel utiliza os valores de x(k+1)i que foram calculados

na mesma iteracao. Isto aumenta a rapidez de convergencia do metodo.



0

0

0

j x(j)1 x

(j)2 x

(j)3

0 0 0 0

1 5/3 3/2 2/3

2 2/3 7/6 7/6

3 8/9 11/12 19/18

4 19/18 35/36 35/36

5 55/54 73/72 107/108...

......

...

e pode-se observar que a solucao vai convergindo para o vetor

1

1

1

que e a solucao exata do

sistema.


3x1 + 2x2 + x3 = 6

2x2 + 3x3 = 5

2x1 + 2x3 = 4

mediante o metodo de Gauss-Seidel.

Neste caso,

A =

3 2 1

0 2 3

2 0 2

, S =

3 0 0

0 2 0

0 0 2

, T =

0 −2 −1

0 0 −3

−2 0 0

.

Logo,

S−1 =

1/3 0 0

0 1/2 0

−1/3 0 1/2

, S−1T =

0 −2/3 −1/3

0 0 −3/2

0 2/3 1/3

,S−1b =

2

5/2

0



x(k+1)1

x(k+1)2

x(k+1)3

=

0 −2/3 −1/3

0 0 −3/2

0 2/3 1/3

x(k)1

x(k)2

x(k)3

+

2

5/2

0

ou,

x(k+1)1 =

−2x(k)2 + x

(k)3 + 6

3

x(k+1)2 =

−3x(k)3 + 5

2

x(k+1)3 =

−2x(k+1)1 + 4

2.


0

0

0

j x(j)1 x

(j)2 x

(j)3

0 0 0 0

1 2 5/2 0

2 1/3 5/2 5/3

3 -2/9 0 20/9

4 34/27 -5/6 20/27

5 187/81 25/18 -25/81

......

......

e pode-se observar que os aproximantes calculados nao convergem para solucao exata

1

1

1

do

sistema.

5.3.3 Convergencia dos Metodos Iterativos

Uma condicao necessaria e suficiente para a convergencia do metodo iterativo (5.8)

x(k+1) = S−1Tx(k) + S−1b

e que todos os autovalores da matriz S−1T sejam, em valor absoluto, menores que 1.


Uma condicao suficiente para a convergencia do metodo e que a matriz A seja diago-

nalmente dominante, isto e, que para cada i,

|aii| >∑

j 6=i

|aij |

.

Exercıcios Propostos:

1. Resolva os seguintes sistemas de equacoes utilizando a regra de Cramer e o metodo

da matriz adjunta

(a)

x1 + x2 = 2

2x1 − x2 = 1

(b)

x1 − x2 + x3 = 1

x1 − x2 − x3 = −1

−3x1 + 3x2 = 0

2. Resolva os seguintes sistemas de equacoes mediante o metodo de eliminacao gaussiana,

utilizando o pivoteamento parcial

(a)

x1 + 2x2 + 3x3 + 4x4 = 10

x1 − x2 + x3 − x4 = 0

x1 + 4x2 + x3 − x4 = 5

4x1 + 3x2 + 2x3 + x4 = 10

(b)

x1 + 2x2 + 3x3 + 4x4 = 10

2x1 + x2 + 2x3 + 3x4 = 8

3x1 + 2x2 + x3 + 2x4 = 8

4x1 + 3x2 + 2x3 + x4 = 10

3. Resolva os sistemas lineares do exercıcio anterior mediante a decomposicao LU sem

pivoteamento.

4. Resolva os seguintes sistemas de equacoes pelos metodos de Jacobi e Gauss-Seidel,

verificando previamente se havera convergencia. Efetue cinco iteracoes de cada metodo

e estime o erro relativo cometido.

(a)

2x1 + x2 = 3

x1 − 2x2 = −1


(b)

2x1 − x2 = 7

−x1 + 2x2 − x3 = 1

− x2 + 2x3 = 1

5. Qual e a condicao necessaria e suficiente sobre o escalar b para que o metodo de

Jacobi seja convergente ao ser aplicado ao sistema

2x1 + bx2 = 3

x1 − 2x2 = −1. E qual

e a condicao para que o metodo de Gauss-Seidel seja convergente?

6 INTERPOLACAO

6.1 Introducao

Neste capıtulo, considera-se o problema de aproximar uma funcao dada por uma classe

de funcoes mais simples, principalmente polinomios. Existem dois motivos principais para utilizar

a interpolacao:

(i) Reconstruir a funcao f(x) quande esta nao e dada de maneira explıcita e so sao

conhecidos os valores de f(x) e/ou suas derivadas de certa ordem em um conjunto de

pontos, denominados nos, pontos tabulares ou argumentos;

(ii) Substituir a funcao f(x) por um polinomio p(x) denominado polinomio interpo-

lador, de maneira que muitas operacoes comuns tais como a determinacao de raızes,

diferenciacao e integracao, etc., que devem ser feitas sobre f(x), possam ser efetuadas

utilizando p(x).

Primeiro, discutem-se os metodos para construir os polinomios interpoladores p(x)

para uma funcao dada f(x).

Definicao 6.1. Um polinomio p(x) e denominado um polinomio interpolador se os valores

de p(x) e/ou suas derivadas de certas ordens coincidem com os de f(x) e/ou as derivadas das

mesmas ordens em um ou mais pontos tabulares.

Em geral, se existem n+ 1 pontos distintos

a0 ≤ x0 < x1 < . . . < xn ≤ b

entao o problema de interpolacao e obter p(x) que satisfaz as condicoes

p(xi) = f(xi), i = 0, 1, . . . , n (6.1)

ou

p(xi) = f(xi), i = 0, 1, . . . , n

p′(xi) = f ′(xi), i = 0, 1, . . . , n(6.2)

As condicoes sobre as derivadas em (6.2) podem ser substituıdas por condicoes mais gerais envol-

vendo derivadas de ordem superior. A condicao (6.1) origina o polinomio interpolador de

Lagrange e a condicao (6.2) origina o polinomio interpolador de Hermite.

72

6.2 Interpolacao de Lagrange e de Newton 73

6.2 Interpolacao de Lagrange e de Newton

Supoe-se que sao dados n+ 1 pontos distintos

a0 ≤ x0 < x1 < . . . < xn ≤ b

no intervalo [a, b] e certos valores yi = f(xi), i = 0, 1, . . . , n associados a uma certa funcao f(x)

conhecida ou nao. Quer-se determinar o polinomio

p(x) = anxn + an−1x

n−1 + · · ·+ a1x+ a0 (6.3)

que satisfaz as condicoes (6.1), isto e,

p(xi) = f(xi), i = 0, 1, . . . , n.

Tal polinomio e unico, pois se existe um outro polinomio p∗(x) tal que

p∗(xi) = f(xi), i = 0, 1, . . . , n

entao o polinomio

q(x) = p(x)− p∗(x)

tem grau ≤ n e

q(xi) = p(xi)− p∗(xi) = 0, i = 0, 1, . . . , n,

isto e, q(x) e um polinomio de grau ≤ n com n + 1 raızes distintas. Necessariamente, q(x) =

0, ∀x ∈ [a, b] e

p∗(x) = p(x), ∀x ∈ [a, b].

6.2.1 Interpolacao Linear

Considere o conjunto de dados

i xi yi

0 x0 y0

1 x1 y1


quer-se determinar um polinomio

p1(x) = a1x+ a0 (6.4)

tal que

p1(x0) = y0 e p1(x1) = y1.

Entao, tem-se o sistema de equacoes:

a1x0 + a0 = y0

a1x1 + a0 = y1

(6.5)

Obtem-se

a0 =x1y0 − x0y1x1 − x0

a1 =y0 − y1x0 − x1

(6.6)

e substituindo em (6.4) resulta

p1(x) =y0 − y1x0 − x1

x+x1y0 − x0y1x1 − x0

, (6.7)

que pode ser escrito na forma de Lagrange

p1(x) =x− x1

x0 − x1y0 +

x− x0

x1 − x0y1 (6.8)

ou

p1(x) = l0(x)y0 + l1(x)y1 (6.9)

onde

l0(x) =x− x1

x0 − x1e l1(x) =

x− x0

x1 − x0(6.10)

Os polinomios l0(x) e l1(x), definidos em (6.10) sao denominados polinomios fundamentais de

Lagrange e satisfazem as condicoes

l0(x) + l1(x) = 1 (6.11)

e

l0(x0) = 1, l0(x1) = 0,

l1(x0) = 0, l1(x1) = 1,(6.12)


ou

li(xj) = δij =

1, se i = j

0, se i 6= j

(6.13)

A equacao (6.9) e o polinomio interpolador de Lagrange. Desta maneira, para

obter o polinomio interpolador de Lagrange, determinam-se primeiro os polinomios fundamentais

de Lagrange, li(x), multiplicam-se por yi, respectivamente, e somam-se tais produtos.

A equacao (6.7)

p1(x) =y0 − y1x0 − x1

x+x1y0 − x0y1x1 − x0

,

tambem pode ser escrita na forma de Newton

p1(x) = y0 +y1 − y0x1 − x0

(

x− x0

)

(6.14)

e se os dados estao associados a uma certa funcao f(x), x ∈ [a, b], ou seja,

i xi f(xi)

0 x0 f(x0)

1 x1 f(x1)

a equacao (6.14) pode ser escrita como

p1(x) = f(x0) + f [x0, x1](

x− x0

)

(6.15)

onde

f [x0, x1] =f(x1)− f(x0)

x1 − x0,

que e denominada a diferenca dividida de f(x) de primeira ordem com relacao a x0 e

x1.

O erro cometido ao interpolar os pontos (xi, f(xi), i = 0, 1 mediante o polinomio p1(x)

e

E1(x) = f(x)− p1(x), ∀x ∈ [a, b]. (6.16)

Uma expressao geral para o erro e mostrada no teorema 6.1. Para n = 1, tem-se

E1(x) =1

2!f ′′(ξ)

(

x− x0

)(

x− x1

)

, ∀x ∈ [x0, x1] (6.17)


para algum ξ ∈ [x0, x1]. Pode-se observar facilmente que uma estimativa deste erro e

∣

∣E1(x)∣

∣ ≤ (x1 − x0)2

8max

{∣

∣f ′′(x)∣

∣/x ∈ [x0, x1]}

(6.18)

Exemplo 6.1. Dada a tabela de dados

i xi sen(xi)

0 0, 1 0, 09983

1 0, 2 0, 19867

determine o polinomio interpolador de Lagrange e de Newton, calcule o valor aproximado de

sen(0, 15) e estime o erro cometido.

De acordo com (6.9), o polinomio interpolador de Lagrange esta dado por

p1(x) = y0x− x1

x0 − x1+ y1

x− x0

x1 − x0

= 0, 09983x− 0, 2

0, 1− 0, 2+ 0, 19867

x− 0, 1

0, 2− 0, 1

= −0, 9983(

x− 0, 2)

+ 1, 9867(

x− 0, 1)

e o polinomio interpolador de Newton esta dado por

p1(x) = y0 +y1 − y0x1 − x0

(

x− x0

)

= 0, 09983 +0, 19867− 0, 09983

0, 2− 0, 1

(

x− 0, 1)

= 0, 09983 + 0, 9884(

x− 0, 1)

.

O polinomio de Lagrange em x = 0, 15 vale

p1(0, 15) = −0, 9983(

0, 15− 0, 2)

+ 1, 9867(

0, 15− 0, 1)

= 0, 049915 + 0, 099335 = 0, 14925,

e o polinomio de Newton em x = 0, 15 vale

p1(0, 15) = 0, 09983 + 0, 9884(

0, 15− 0, 1)

= 0, 09983 + 0, 04942 = 0, 14925.


A estimativa do erro esta dada por (6.18)

∣

∣E1(x)∣

∣ ≤ (x1 + x0)2

8max

{∣

∣f ′′(x)∣

∣/x ∈ [x0, x1]}

=(0, 2 + 0, 1)2

8sen(0, 2) = 0, 01125 · 0, 19867 = 0, 00223.

6.2.2 Interpolacao de n+ 1 pontos

Considere o conjunto de dados

i xi yi

0 x0 y0

1 x1 y1...

......

n xn yn

quer-se determinar um polinomio


n−1 + · · ·+ a1x+ a0 (6.19)

tal que

pn(xi) = yi, ∀i = 0, 1, . . . , n

O polinomio interpolador na forma de Lagrange esta dado por

pn(x) = l0(x)y0 + l1(x)y1 + · · ·+ ln(x)yn (6.20)

onde

l0(x) =(x− x1)(x− x2) . . . (x− xn)

(x0 − x1)(x0 − x2) . . . (x0 − xn), (6.21)

li(x) =(x− x1)(x − x2) . . . (x − xi−1)(x− xi+1) . . . (x− xn)

(x0 − x1)(x0 − x2) . . . (x0 − xi−1)(x0 − xi+1) . . . (x0 − xn), i = 1, 2, . . . , n− 1 (6.22)

e

ln(x) =(x− x0)(x− x1) . . . (x− xn−1)

(xn − x0)(xn − x1) . . . (xn − xn−1), (6.23)


Os polinomios li(x), i = 0, 1, . . . , n definidos em (6.21) - (6.23) sao denominados

polinomios fundamentais de Lagrange e satisfazem as condicoes

l0(x) + l1(x) + · · ·+ ln(x) = 1 (6.24)

e

li(xj) = δij =

1, se i = j

0, se i 6= j

(6.25)

Se os valores de yi, i = 0, 1, . . . , n correspondem aos de certa funcao f(x) nos pontos

x0 < x1 < . . . < xn, o polinomio interpolador na forma de Newton associado a tabela de dados

i xi f(xi)

0 x0 f(x0)

1 x1 f(x1)...

......

n xn f(xn)

e escrito como

pn(x) =f(x0) + f [x0, x1](

x− x0

)

+ f [x0, x1, x2](

x− x0

)(

x− x1

)

+ · · ·

+ f [x0, x1, . . . , xn−1](

x− x0

)

(x − x1

)

. . . (x− xn−1

)

(6.26)

onde

f [x0, x1, . . . , xi] =f [x1 . . . , xi]− f [x0, . . . , xi−1]

xi − x0, i = 1, 2, . . . , n− 1 (6.27)

que e denominada a diferenca dividida de f(x) de i-esima ordem com relacao a x0, x1,

. . .xi. Deve-se observar que f [xi] = f(xi), ∀i = 0, 1, . . . , n

As diferencas divididas podem ser construıdas de acordo com a tabela a seguir


x Ordem 0 Ordem 1 Ordem 2 Ordem 3 . . . Ordem n

x0 f [x0]

f [x0, x1]

x1 f [x1] f [x0, x1, x2]

f [x1, x2] f [x0, x1, x2, x3]

x2 f [x2] f [x1, x2, x3]. . .

f [x2, x3] f [x1, x2, x3, x4]

x3 f [x3] f [x2, x3, x4] f [x0, x1, x2, . . . , xn]

f [x3, x4]...

x4 f [x4]... f [xn−3, xn−2, xn−1, xn]

... f [xn−2, xn−1, xn]

... f [xn−1, xn]

xn f [xn]

Exemplo 6.2. Dada a tabela

i xi f(xi)

0 −1 4

1 0 1

2 2 −1

determine os polinomios interpoladores de Lagrange e de Newton, p2(x).

A forma de Lagrange para o polinomio interpolador esta dada por

p2(x) = y0l0(x) + y1li(x) + y2l2(x),

onde

l0(x) =(x− x1)(x− x2)

(x0 − x1)(x0 − x2)=

(x− 0)(x− 2)

(−1− 0)(−1− 2)=

1

3(x2 − 2x),

l1(x) =(x− x0)(x− x2)

(x1 − x0)(x1 − x2)=

(x+ 1)(x− 2)

(0 + 1)(0− 2)= −1

2(x2 − x− 2),

l2(x) =(x − x0)(x − x1)

(x2 − x0)(x2 − x1)=

(x+ 1)(x− 0)

(2 + 1)(2− 0)=

1

6(x2 + x).

Entao

p2(x) = 4 · 13(x2 − 2x) + 1 · −1

2(x2 − x− 2) + (−1) · 1

6(x2 + x) =

2

3x2 − 7

3x+ 1.

Para conseguir a forma de Newton, faz-se a tabela de diferencas divididas:


x Ordem 0 Ordem 1 Ordem 2

−1 4

−3

0 1 23

−1

2 −1

Portanto, a forma de Newton do polinomio interpolador e

p2(x) = f [x0] + f [x0, x1](x− x0) + f [x0, x1, x2](x − x0)(x − x1)

= 4 + (−3)(x+ 1) +2

3(x+ 1)(x− 0)

=2

3x2 − 7

3x+ 1,

como foi obtido anteriormente.

6.2.3 Erro na Interpolacao

A seguir, estabelece-se um resultado para o erro

Teorema 6.1. Considere-se n+ 1 pontos,

x0 < x1 < x2 < . . . < xn.

Seja f(x) com derivadas ate de ordem n + 1, ∀x ∈ [x0, xn]. Seja pn(x) o polinomio interpolador

de Lagrange de f(x) nos pontos x0, x1, . . . , xn. Entao, para cada x ∈ [x0, xn], o erro e dado por

En(x) = f(x)− pn(x) =(

x− x0

)(

x− x1

)

. . .(

x− xn

)f (n+1)(ξx)

(n+ 1)!,

para algum ξx ∈ [x0, xn].

Prova: Seja

w(x) =(

x− x0

)(

x− x1

)

. . .(

x− xn

)

, ∀x ∈ [x0, xn].

Lembrando que

En(x) = f(x)− pn(x), ∀x ∈ [x0, xn];

para cada x ∈ [x0, xn], defina

H(t) = En(x)w(t) − En(t)w(x), ∀t ∈ [x0, xn].


Se x = xi, para algum i = 0, 1, . . . , n, entao En(x) = 0 e o resultado e obvio.

Considere, entao, que x 6= xi, ∀i = 0, 1, . . . , n. Observe que x ∈]xi − 1, xi[, para um unico

i0 = 1, 2, . . . , n. As derivadas f (k)(t) e p(k)n (t), k = 0, 1, . . . , n + 1, existem, e assim, E

(k)n (t),

k = 0, 1, . . . , n + 1, existem. A funcao w(t) e um polinomio de grau n + 1, e tambem w(k)(t),

k = 0, 1, . . . , n+ 1, existem. Portanto, as derivadas H(k)(t),k = 0, 1, . . . , n+ 1, tambem existem.

Tem-se que H(xi) = 0, ∀i = 0, 1, . . . , n e tambem H(x) = 0. Aplica-se o teorema de

Rolle a funcao H(t) restrita a cada um dos subintervalos seguintes:

[x0, x1], . . . , [xi0−2, xi0−1], [xi0−1, x], [x, xi0 ], [xi0 , xi0+1], . . . , [xn−1, xn],

e consegue-se uma sequencia ξ0,1 < ξ1,1 < · · · < ξn,1 de valores tais que H ′(ξi,1) = 0, ∀i =

0, 1, . . . , n. Aplica-se o teorema de Rolle a funcao H ′(t) restrita a cada um dos subintervalos

seguintes:

[ξ0,1, ξ1,1], [ξ1,1, ξ2,1], . . . , [ξn−1,1, ξn,1],

e consegue-se uma sequencia ξ0,2 < ξ1,2 < · · · < ξn−1,2 de valores tais que H ′′(ξi,2) = 0, ∀i =

0, 1, . . . , n− 1. Procedendo dessa maneira, ate aplicar o teorema de Rolle a H(n)(t), consegue-se o

valor ξ0,n+1 ∈ [x0, xn] tal que H(n+1)(ξ0,n+1) = 0.

Mas, E(n+1)n (t) = f (n+1)(t)−p(n+1)

n (t) = f (n+1)(t), pois pn(t) e um polinomio de grau

n. Por outro lado, w(n+1)(t) = (n + 1)!, pois w(t) e um polinomio de grau n+ 1 com coeficiente

principal 1.

Entao

0 = H(n+1(ξ0, n+ 1 = En(x)(n + 1)!− f (n+1)(ξ0,n+1)w(x).

Portanto,

En(x) = w(x)f (n+1)(ξ0,n+1)

(n+ 1)!.

Basta escolher ξx = ξ0,n+1. �

Prova-se, agora, uma propriedade das diferencas divididas:

Lema 6.1. Para cada k ∈ N e satisfeita a propriedade

f [x0, x1, . . . , xk] = f [xj0 , xj1 , . . . , xjk]

onde(

xj0 , xj1 , . . . , xjk

)

e qualquer permutacao de(

x0, x1, . . . , xk

)

.


Prova: Utiliza-se a inducao matematica. �

Teorema 6.2. Considere-se n+ 1 pontos,

x0 < x1 < x2 < . . . < xn.

Seja f(x) com derivadas ate de ordem n + 1, ∀x ∈ [x0, xn]. Seja pn(x) o polinomio interpolador

de Newton de f(x) nos pontos x0, x1, . . . , xn. Entao, para cada x ∈ [x0, xn], o erro e dado por

En(x) = f(x) − pn(x) =(

x− x0

)(

x− x1

)

. . .(

x− xn

)

f [x0, x1, . . . , xn, x].

Prova: Por inducao matematica. �

Corolario 6.1. Sob as hipoteses do teorema 6.1 ou as do teorema 6.2 e se f (n+1)(x) e contınua

em [x0, xn], entao

|En(x)| = |f(x)− pn(x)| ≤∣

∣

(

x− x0

)(

x− x1

)

. . .(

x− xn

)∣

∣

Mn+1

(n+ 1)!

onde Mn+1 = max{∣

∣f (n+1)(x)∣

∣ : x ∈ [x0, xn]}

Corolario 6.2. Se alem das hipoteses teorema 6.1 ou teorema 6.2 e as do corolario 6.1, os pontos

xi sao igualmente espacados, isto e,

xi − xi−1 = h, ∀i = 1, 2, . . . , n,

entao

|En(x)| = |f(x)− pn(x)| ≤ hn+1Mn+1

4(n+ 1)

Exemplo 6.3. Seja f(x) = ex + x− 1 tabelada a seguir.

x 0, 0 0, 5 1, 0 1, 5 2, 0

f(x) 0, 0 1, 1487 2, 7183 4, 9811 8, 3890

Obter f(0, 7) por interpolacao linear e obter o erro exato e as estimativas do erro de acordo com

os corolarios 6.1 e 6.2.


O polinomio interpolador e p1(x) = f(x0) +(

x − x0

)

f [x0, x1] e como x = 0, 7 ∈[0, 5 , 1], entao escolhe-se x0 = 0, 5 e x1 = 1, 0. Entao

p1(x) = 1, 1487 + (x− 0, 5)2, 7183− 1, 1487

1− 0, 5= 1, 1487 + 3, 1392(x− 0, 5)

e assim p(0, 7) = 1, 7765.

Neste caso, o erro exato e dado por

|E1(0, 7)| = |f(0, 7)− p1(0, 7)| = |1, 7137− 1, 7765| = 0, 0628.

O corolario 6.1 fornece a estimativa

|E1(0, 7)| = |(0, 7− 0, 5)(0, 7− 1, 0)|M2

2= 0, 0815

pois M2 = max{

|f ′′(x)| : x ∈ [0, 5 , 1, 0]}

= max{

ex : x ∈ [0, 5 , 1, 0]}

= 2, 7183.

O corolario 6.2 fornece a estimativa

|E1(x)| =h2M2

2= 0, 0850

pois h = 0, 5.

Se a funcao f(x) nao e conhecida, o valor absoluto do erro, |Ek(x)|, so pode ser

estimado, porque nao e possıvel calcular f (k+1)(x) e portanto, Mk+1. Mas, a partir da tabela de

diferencas divididas, o valorMn+1

(n+ 1)!pode ser aproximado mediante o maior valor absoluto das

diferencas divididas de ordem k + 1:

|Ek(x)| ≈ |(x− x0)(x− x1) · · · (x− xk)| ·max{|f [xj0 , xj1 , . . . , xjk]|/j0 < j1 < . . . < jk}


x 0, 2 0, 34 0, 4 0, 52 0, 6 0, 72

f(x) 0, 16 0, 22 0, 27 0, 29 0, 32 0, 37

obter f(0, 47) utilizando um polinomio quadratico e fornecer uma estimativa para o erro cometido.

Constroi-se a tabela de diferencas divididas


x Ordem 0 Ordem 1 Ordem 2 Ordem 3

0, 2 0, 16

0, 4286

0, 34 0, 22 2, 0235

0, 8333 −17, 8963

x0 = 0, 4 0, 27 −3, 7033

0, 1667 18, 2494

x1 = 0, 52 0, 29 1, 0415

0, 375 −2, 6031

x2 = 0, 6 0, 32 0, 2085

0, 4167

0, 72 0, 37

Para ter um polinomio quadratico sao necessarios tres pontos, e como 0, 47 ∈ [0, 4 , 0, 52]

entao escolhem-se: x0 = 0, 4, x1 = 0, 52, x2 = 0, 6. Outra possıvel escolha poderia ter sido

x0 = 0, 34, x1 = 0, 4, x2 = 0, 52.

O polinomio interpolador na forma de Newton e

p2(x) = f [x0] + f [x0, x1](x− x0) + f [x0, x1, x2](x − x0)(x − x1)

= 0, 27 + 0, 1667(x− 0, 4) + 1, 0415(x− 0, 4)(x− 0, 52)

Entao, p2(0, 47) = 0, 2780 ≈ f(0, 47).

A estimativa do erro cometido esta dada por

E2(0, 47) ≈ |(0, 47− 0, 4)(0, 47− 0, 52)(0, 47− 0, 06)| · 18, 2492 = 0, 8303 · 10−2.

6.2.4 Forma de Gregory-Newton para o Polinomio Interpolador

Considere, agora, o caso que os pontos xi, i = 0, 1, . . . , n sao igualmente espacados,

isto e, xi − xi−1 = h, ∀i = 1, 2, . . . , n, onde h e uma constante. Entao a forma de Newton do

polinomio interpolador pn(x) pode ser tratada de modo mais simplificado.


Definicao 6.2. A diferenca finita (para frente) de j-esima ordem e definida recursivamente

como

△jf(x) =

f(x), se j = 0,

△j−1f(x+ h)−△j−1f(x), se j = 1, 2, . . .

As diferencas finitas e as diferencas divididas estao relacionadas como segue

Lema 6.2. Para todo j = 0, 1, . . . , n, tem-se que

f [x0, x1, . . . , xj ] =△jf(x0)

hnn!.

Prova: Utilize inducao matematica. �

De maneira similar as diferencas divididas, as diferencas finitas tambem podem ser

escritas em uma tabela, a tabela de diferencas finitas:

x Ordem 0 Ordem 1 Ordem 2 Ordem 3 . . . Ordem n

x0 f(x0)

△f(x0)

x1 f(x1) △2f(x0)

△f(x1) △3f(x0)

x2 f(x2) △2f(x1). . .

△f(x2) △3f(x1)

x3 f(x3) △2f(x2) △nf(x0)

△f(x3)...

x4 f(x4)... △3f(xn−3)

... △2f(xn−2)

... △f(xn−1)

xn f(xn)

A forma de Newton para o polinomio interpolador pn(x) pode ser escrita como

pn(x) =f(x0) +△f(x0)

h(x− x0) +

△2f(x0)

2h2(x − x0)(x − x1) + · · ·

+△nf(x0)

n!hn(x− x0)(x − x1) . . . (x− xn−1).

(6.28)


A equacao (6.28) e denominada a forma de Gregory-Newton do polinomio inter-

polador pn(x).

Fazendo a mudanca de variaveis s = x− x0h

, e observando que xj = x0 + jh, j =

0, 1, . . . , n, tem-se que x − xj = (s − j)h, j = 0, 1, . . .. Com isto, o polinomio interpolador pn(x)

na equacao (6.28) pode ser escrito em termos da variavel s como

pn(s) = f(x0) + s△f(x0) +△2f(x0)s(s− 1)

2!+ · · ·+△nf(x0)

s(s− 1) . . . (s− (n− 1))

n!. (6.29)


x −1 0 1 2 3

f(x) 2 1 2 5 10

determinar, mediante o melhor polinomio interpolador na forma de Gregory-Newton (6.28) e

(6.29), o valor de f(0, 5).

A tabela de diferencas finitas para estes dados e

x f(x) △f(x) △2f(x) △3f(x)

−1 2

−1

0 1 2

1 0

1 2 2

3 0

2 5 2

5

3 10

Neste caso, o melhor polinomio interpolador e quadratico pois △jf(x) = 0, ∀j ≥ 3.

De acordo com (6.28), tem-se que

p2(x) =f(x0) +△f(x0)

h(x− x0) +

△2f(x0)

2h2(x− x0)(x − x1)

=2− (x+ 1) +2

2(x+ 1)(x− 0)

=x2 + 1.

Portanto, f(0, 5) ≈ p2(0, 5) = (0, 5)2 + 1 = 1, 25.


De acordo com (6.29), tem-se que

p2(s) =f(x0) + s△f(x0) +△2f(x0)s(s− 1)

2

=2− s+2

2(s2 − s)

=s2 − 2s+ 2.

Se x = 0, 5, entao s = x− x0h

=0, 5− (−1)

1 = 1, 5 e assim

p2(s)∣

∣

s=1,5= (1, 5)2 − 2(1, 5) + 2 = 1, 25.

6.2.5 Interpolacao Inversa

Considerando a tabela de dados

x x0 x1 x2 . . . xn

f(x) f(x0) f(x1) f(x2) . . . f(xn)

e dado y ∈ [min{f(xi},max{f(xi)}], o problema da interpolacao inversa consiste em obter x tal

que f(x) = y,

Basicamente, existem duas maneiras de abordar este problema:

1. Obter pn(x) que interpola f(x) e resolver a equacao pn(x) = y. Aqui, o valor de x

nao e necessariamente unico e o erro cometido nao pode ser estimado.

Exemplo 6.6. Considere os dados do exemplo 6.5

x −1 0 1 2 3

f(x) 2 1 2 5 10

Pede-se obter x tal que f(x) = 1, 25.

Neste caso, o polinomio interpolador e p2(x) = x2+1, e ao resolver a equacao x2+1 =

1, 25 obtem-se duas solucoes: x1 = −0, 5 e x2 = 0, 5

2. Se a existencia da funcao inversa x = f−1(y) e garantida, entao pode-se aplicar as

tecnicas de interpolacao aos dados

f(x) f(xj0) f(xj1 ) f(xj2) . . . f(xjn)

x xj0 xj1 xj2 . . . xjn


onde f(xj0 ) < f(xj1 ) < . . . < f(xjn). Tal arranjo e possıvel se a funcao inversa

x = f−1(y) existe, pois nesse caso, tal funcao e estritamente monotona no seu domınio.

Exemplo 6.7. Considerando a tabela para os valores de f(x) = ex

x 0 0, 1 0, 2 0, 3 0, 4 0, 5

f(x) 1 1, 1052 1, 2214 1, 3499 1, 4918 1, 6487

obter x tal que ex = 1, 3165 mediante interpolacao quadratica inversa.

E construıda a tabela de diferencas divididas para os dados

y Ordem 0 Ordem 1 Ordem 2 Ordem 3

1 0

0, 9506

1, 1052 0, 1 −0, 4065

0, 8606 0, 1994

y0 = 1, 2214 0, 2 −0, 3367

0, 7782 0, 1679

y1 = 1, 3499 0, 3 −0, 2718

0, 7047 0, 1081

y2 = 1, 4918 0, 4 −0, 2256

0, 6373

1, 6478 0, 5

O polinomio quadratico que interpola a funcao inversa g(y) e

p2(y) = g(y0) + g[g0, y1](y − y0) + g[y0, y1, y2](y − y0)(y − y1)

= 0, 2 + 0, 7782(y− 1, 2214) + (−0, 2718)(y− 1, 2214)(y− 1, 3499).

Portanto, p2(1, 3165) = 0, 27494. A estimativa do erro pode ser encontrada facilmente:

|E2(x)| ≤ |(y − y0)(y − y1)|M3

3!

onde M3 = max{|g′′(y)| : y ∈ [y0, y2]}. Aqui, g(y) = ln(y) e g′′′(y) = 2y3 . Entao

M3 = 2(1, 2214)3

= 1, 0976

Assim,

|E2(x)| ≤ 0, 1019× 10−3.

6.3 Introducao 89

6.3 Polinomios de Taylor

Os polinomios de Taylor sao tambem uma ferramenta de interpolacao, que aproximam

uma certa funcao f(x) ao redor de um ponto escolhido x0, com a condicao

p(k)(x0) = f (k)(x0), k = 0, 1, . . . , n.

Definicao 6.3. Seja uma funcao f(x) tal que as primeiras n + 1 derivadas de f(x) existem. O

polinomio p(x)

p(x) = f(x0) + (x− x0)f′(x0) +

1

2!(x − x0)

2f ′′(x0) + · · ·+ 1

n!(x− x0)

nf (n)(x0) (6.30)

e denominado o polinomio de Taylor de grau n para a funcao f(x) no ponto x0, x0 ∈ [a, b] e

pode ser considerado como um polinomio interpolador de grau n da funcao f(x), que satisfaz as

condicoes

p(k)(x0) = f (k)(x0), k = 0, 1, . . . , n. (6.31)

O termo

Rn =1

(n+ 1)!(x− x0)

n+1f (n+1)(ξ), x0 < ξ < x (6.32)

que tem sido desprezado em (6.30), e denominado o resto ou o erro de truncamento.

O numero de termos a serem incluıdos em (6.30) pode ser determinado pelo erro

aceitavel. Se este erro e ε > 0 e a serie e truncada no termo f (n)(x0), entao

1

(n+ 1)!|x− x0|n+1

∣

∣f (n+1)(ξ)∣

∣ < ε, x0 < ξ < x (6.33)

ou1

(n+ 1)!|x− x0|n+1Mn+1(x) < ε, (6.34)

onde Mn+1(x) = maxa≤t≤x

∣

∣f (n+1)(t)∣

∣.

Exemplo 6.8. Obtenha uma aproximacao polinomial p(x) para f(x) = e−x utilizando a expansao

de Taylor ao redor de x0 = 0 e determine

(i) x para que a aproximacao p(x) com quatro termos tenha erro absoluto menor que

0, 5× 10−6;

6.3 Introducao 90

(ii) o numero de termos na aproximacao para encontrar resultados corretos ate 0, 5×10−10

para 0 ≤ x ≤ 1.

Para (i), tem-se que se f(x) = e−x, entao

f (r)(x) = (−1)re−x =⇒ f (r(0) = (−1)r, r = 0, 1, . . . .

A partir de (6.30) obtem-se

p(x) = 1− x+x2

2− x3

6

e de (6.34)x4

4!M4 < 0, 5× 10−6

onde M4(x) = max0≤t≤x

∣

∣f (4)(t)∣

∣ = max0≤t≤x

∣

∣e−t∣

∣ = 1 e

x4 < 0, 12× 10−4

ou

x < 0, 0589

Para (ii), de (6.34) tem-se que

1

(n+ 1)!< 0, 5× 10−10

que resulta em

n ≥ 14.

Exercıcios:

1. Obtenha uma aproximacao polinomial p(x) para

(a) f(x) = 11 + x2

(b) f(x) = e−2x

(c) f(x) = 11 +√x

utilizando a expansao de Taylor ao redor de x0 = 0 e determine

(i) x para que a aproximacao p(x) com quatro termos tenha erro absoluto menor

que 0, 5× 10−4;

6.3 Introducao 91

(ii) o numero de termos na aproximacao para encontrar resultados corretos ate 0, 5×10−10 para 0 ≤ x ≤ 1.

2. Dada a tabela abaixo,

x 2, 4 2, 6 2, 8 3, 0 3, 2 3, 4 3, 6 3, 8

f(x) 11, 02 13, 46 16, 44 20, 08 24, 53 29, 96 36, 59 44, 70

(a) Calcule e3,1 utilizando um polinomio de interpolacao sobre tres pontos.

(b) Faca uma estimativa do erro cometido.

3. Prove os lemas 6.1, 6.2 e o teorema 6.2 utilizando a inducao matematica.

4. Prove os corolarios 6.1 e 6.2.

5. Quer-se construir uma tabela que contenha valores de sen(x) para pontos igualmente

espacados no intervalo [0, 1]. Qual deve ser o menor numero de pontos na tabela para se

obter, a partir dela, o sen(x), utilizando a interpolacao linear com erro |E(x)| ≤ 10−6,

∀x ∈ [0, 1].

6. Sabendo-se que a equacao x− e−x = 0 admite uma raiz no intervalo [0, 1], determine

o valor desta raiz utilizando um polinomio de interpolacao sobre tres pontos. Estime

o erro cometido.

7. Construa a tabela de diferencas divididas com os dados

x 0, 0 0, 5 1, 0 1, 5 2, 0 2, 5

f(x) −2, 78 −2, 241 −1, 65 −0, 594 1, 34 4, 564

(a) Estime o valor de f(1, 23) da melhor maneira possıvel, de forma que se possa

estimar o erro cometido.

(b) Justifique a escolha do grau do polinomio.

8. Seja a tabela

x 0, 15 0, 20 0, 25 0, 30 0, 35 0, 40

f(x) 0, 12 0, 16 0, 19 0, 22 0, 25 0, 27

Utilizando um polinomio interpolador quadratico, encontre o valor de x para o qual

f(x) = 0, 23.

9. Construa uma tabela para a funcao f(x) = cos(x) utilizando os pontos 0, 8; 0, 9; 1, 0; 1, 1; 1, 2; 1, 3.

Obtenha um polinomio cubico para estimar cos(1, 07) e forneca uma estimativa do erro

cometido.

7 AJUSTE DE CURVAS PELO METODO DOS QUADRADOS MINIMOS

7.1 Introducao

No capıtulo anterior, tratou-se o problema de aproximar e interpolar uma funcao f(x)

ou um conjunto de dados tabulares mediante polinomios de grau n, pn(x). Mas, as vezes, isto nao

aconselhavel pois os dados obtidos podem ser resultados de algum experimento fısico possivelmente

governados por alguma lei fısica. Entao tem-se a necessidade de criar heuristicamente uma funcao

ϕ(x) que aproxime f(x) fora do intervalo [x0, xn] e que seja uma “boa” aproximacao.

7.2 Caso Linear Discreto

Seja a tabela de dados

x x1 x2 x3 . . . xn

f(x) f(x1) f(x2) f(x3) . . . f(xn)

com x1 ≤ x2 ≤ x3 ≤ . . . ≤ xn e sejam escolhidas certas funcoes g1(x), g2(x), . . ., gm(x), (m ∈ N)

contınuas em [x1, xn]. O problema de ajuste pelo metodo dos quadrados mınimos consiste

em obter certos coeficientes αi, i = 1, 2, . . . ,m, tais que a funcao

ϕ(x) = α1g1(x) + α2g2(x) + · · ·+ αmgm(x)

se aproxime a f(x) satisfazendo a condicao que

n∑

i=1

(

f(xi)− ϕ(xi))2

seja a menor possıvel.

Observe que a funcao ϕ(x) e uma combinacao linear das funcoes gi(x), i = 1, 2, . . . ,m.

Por este motivo, o ajuste e dito linear. Por outro lado, os dados disponıveis sobre a funcao f(x)

sao aqueles listados na tabela. Por essa razao, o ajuste e dito discreto.

Seja definida a funcao

F (α1, α2, . . . , αm) =n

∑

i=1

[

f(xi)−ϕ(xi)]2

=n

∑

i=1

[

f(xi)−α1g1(xi)−α2g2(xi)−· · ·−αmgm(xi)]2

(7.1)

92

7.2 Caso Linear Discreto 93

Para minimizar a funcao F (α1, α2, . . . , αm), tem de ser encontrados os seus pontos crıticos, isto e,

tem que ser resolvida o sistema de equacoes

∂F

∂αj

∣

∣

∣

∣

(α1,α2,...,αm)

= 0, j = 1, 2, . . . ,m. (7.2)

Calculando estas derivadas parciais, tem-se, para cada j = 1, 2, . . . ,m,

∂F

∂αj

∣

∣

∣

∣

(α1,α2,...,αm)

= 2

n∑

i=1

[

f(xi)− α1g1(xi)− α2g2(xi)− · · · − αmgm(xi)][

−gj(xi)]

. (7.3)

De (7.2) e (7.3), tem-se que

n∑

i=1

[

f(xi)− α1g1(xi)− α2g2(xi)− · · · − αmgm(xi)][

gj(xi)]

= 0, j = 1, 2, . . . ,m. (7.4)

A partir de (7.4), forma-se o sistema de equacoes lineares

[

n∑

i=1

g1(xi)g1(xi)

]

α1 + · · ·+[

n∑

i=1

gm(xi)g1(xi)

]

αm =

n∑

i=1

f(xi)g1(xi)

[

n∑

i=1

g1(xi)g2(xi)

]

α1 + · · ·+[

n∑

i=1

gm(xi)g2(xi)

]

αm =n

∑

i=1

f(xi)g2(xi)

...[

n∑

i=1

g1(xi)gm(xi)

]

α1 + · · ·+[

n∑

i=1

gm(xi)gm(xi)

]

αm =

n∑

i=1

f(xi)gm(xi)

(7.5)

que pode ser escrito da forma

n∑

i=1g1(xi)g1(xi)

n∑

i=1g2(xi)g1(xi) · · ·

n∑

i=1gm(xi)g1(xi)

n∑

i=1g1(xi)g2(xi)

n∑

i=1g2(xi)g2(xi) · · ·

n∑

i=1gm(xi)g2(xi)

......

. . ....

n∑

i=1g1(xi)gm(xi)

n∑

i=1g2(xi)gm(xi) · · ·

n∑

i=1gm(xi)gm(xi)

α1

α2

...

αm

=

n∑

i=1f(xi)g1(xi)

n∑

i=1f(xi)g2(xi)

...n∑

i=1f(xi)gm(xi)

(7.6)

Exemplo 7.1. Dada a tabela

x −1, 0 −0, 75 −0, 6 −0, 5 −0, 3 0 0, 2 0, 4 0, 5 0, 7 1, 0

f(x) 2, 05 1, 153 0, 45 0, 4 0, 5 0 0, 2 0, 6 0, 512 1, 2 2, 05

ajustar a curva ϕ(x) = α1x2 a estes dados.


Figura 7.1 Ajuste de uma curva ϕ(x) = α1x2 aos dados da tabela.

Neste caso, m = 1, g1(x) = x2. Entao a unica equacao e

[

11∑

i=1g1(xi)g1(xi)

]

α1 =11∑

i=1f(xi)g1(xi)

ou[

11∑

i=1(x2

i )2]

α1 =11∑

i=1x2

i f(xi),

α1 =

11∑

i=1x2

i f(xi)

11∑

i=1x4

i

=5, 8756

2, 8464= 2, 0642.

Portanto, a curva ϕ = 2, 0642x2 e a que melhor ajusta esses dados no sentido de

quadrados mınimos. Veja a figura 7.1

Exemplo 7.2. Considerando os dados da tabela anterior, ajustar a curva ϕ(x) = α1x2 + α2x.

Neste caso, m = 2, g1(x) = x2, g2(x) = x. Entao as equacoes sao

[

11∑

i=1g1(xi)g1(xi)

]

α1 +

[

11∑

i=1g2(xi)g1(xi)

]

α2 =11∑

i=1f(xi)g1(xi)

[

11∑

i=1g1(xi)g2(xi)

]

α1 +

[

11∑

i=1g2(xi)g2(xi)

]

α2 =11∑

i=1f(xi)g2(xi)


ou,[

11∑

i=1x4

i

]

α1 +

[

11∑

i=1x3

i

]

α2 =11∑

i=1x2

i f(xi)

[

11∑

i=1x3

i

]

α1 +

[

11∑

i=1x2

i

]

α2 =11∑

i=1xif(xi).

Tem-se que11∑

i=1x4

i = 2, 8464,11∑

i=1x3

i = −0.2499,11∑

i=1x2

i = 4, 2025,11∑

i=1x2

i f(xi) = 5, 8756,11∑

i=1xif(xi) =

−0, 1087, e o sistema de equacoes fica

2, 8464α1 − 0, 2499α2 = 5, 8756

−0, 2499α1 + 4.2025α2 = −0, 1087.

Resolvendo este sistema, consegue-se α1 = 2, 0728 e α2 = 0, 0974. Veja a figura 7.2. Pode-se

apreciar a semelhanca entre os graficos conseguidos nas figuras 7.1 e 7.2.

Figura 7.2 Ajuste de uma curva ϕ(x) = α1x2 + α2x aos dados da tabela.

7.2.1 Ajuste de uma Reta por Quadrados Mınimos

Dada a tabela de dados

x x1 x2 x3 . . . xn

f(x) f(x1) f(x2) f(x3) . . . f(xn)

com x1 ≤ x2 ≤ x3 ≤ . . . ≤ xn, quer-se ajustar uma reta ϕ(x) = α1x + α2 a estes dados mediante

o metodo de quadrados mınimos.

7.3 Caso Linear Contınuo 96

Neste caso, m = 2, g1(x) = x, g2(x) = 1. Substituindo no sistema de equacoes (7.5),

obtem-se o sistema[

n∑

i=1x2

i

]

α1 +

[

n∑

i=1xi

]

α2 =n∑

i=1xif(xi)

[

n∑

i=1xi

]

α1 + nα2 =n∑

i=1f(xi)

(7.7)

A solucao do sistema (7.7) pode ser encontrada facilmente:

α1 =

n

[

n∑

i=1xif(xi)

]

−[

n∑

i=1xi

] [

n∑

i=1f(xi)

]

n

[

n∑

i=1x2

i

]

−[

n∑

i=1xi

]2 ,

α2 =

[

n∑

i=1f(xi)

]

−[

n∑

i=1xi

]

α1

n.

(7.8)


x 1, 3 3, 4 5, 1 6, 8 8, 0

f(x) 2, 0 5, 2 3, 8 6, 1 5, 8

ajustar uma reta ϕ(x) = α1x+ α2.

Calculando previamente os valores necessarios para o sistema de equacoes:5∑

i=1x2

i =

149, 5,5∑

i=1xi = 24, 6,

5∑

i=1f(xi) = 22, 9,

5∑

i=1xif(xi) = 127, 54; tem-se que:

α1 =5 · 127, 54− 24, 6 · 22, 9

5 · 149, 5− (24, 6)2= 0, 5224,

α2 =22, 9− 24, 6 · 0, 5224

5= 2, 0097.

Veja a figura 7.3 para apreciar geometricamente o ajuste.

7.3 Caso Linear Contınuo

Seja uma funcao f(x) definida e contınua sobre um intervalo [a, b] e sejam escolhidas

certas funcoes g1(x), g2(x), . . ., gm(x), (m ∈ N) contınuas em [a, b]. O problema de ajuste

pelo metodo dos quadrados mınimos consiste em obter certos coeficientes αi, i = 1, 2, . . . ,m,


Figura 7.3 Ajuste de uma curva ϕ(x) = α1x+ α2 aos dados da tabela.

tais que a funcao

ϕ(x) = α1g1(x) + α2g2(x) + · · ·+ αmgm(x)

se aproxime a f(x) satisfazendo a condicao que

∫ b

a

(

f(x)− ϕ(x))2dx

seja a menor possıvel.

Como na secao 7.2, observe que a funcao ϕ(x) e uma combinacao linear das funcoes

gi(x), i = 1, 2, . . . ,m. Por este motivo, o ajuste e dito linear. Por outro lado, o conhecimento da

funcao f(x) sobre o intervalo [a, b], o ajuste e dito contınuo.

Seja definida a funcao

F (α1, α2, . . . , αm) =

∫ b

a

[

f(x)−ϕ(x)]2dx =

∫ b

a

[

f(x)−α1g1(x)−α2g2(x)−· · ·−αmgm(x)]2

(7.9)

Para minimizar a funcao F (α1, α2, . . . , αm), tem de ser encontrados os seus pontos crıticos, isto e,

tem que ser resolvida o sistema de equacoes

∂F

∂αj

∣

∣

∣

∣

(α1,α2,...,αm)

= 0, j = 1, 2, . . . ,m. (7.10)

Calculando estas derivadas parciais, tem-se, para cada j = 1, 2, . . . ,m,

∂F

∂αj

∣

∣

∣

∣

(α1,α2,...,αm)

= 2

∫ b

a

[

f(x)− α1g1(x)− α2g2(x)− · · · − αmgm(x)][

−gj(x)]

dx. (7.11)


De (7.10) e (7.11), tem-se que

∫ b

a

[

f(x) − α1g1(x)− α2g2(x) − · · · − αmgm(x)][

gj(x)]

dx = 0, j = 1, 2, . . . ,m. (7.12)

A partir de (7.12), forma-se o sistema de equacoes lineares

[

∫ b

a

g1(x)g1(x)dx

]

α1 + · · ·+[

∫ b

a

gm(x)g1(x)dx

]

αm =

∫ b

a

f(x)g1(x)dx

[

∫ b

a

g1(x)g2(x)dx

]

α1 + · · ·+[

∫ b

a

gm(x)g2(x)dx

]

αm =

∫ b

a

f(x)g2(x)dx

...[

∫ b

a

g1(x)gm(x)dx

]

α1 + · · ·+[

∫ b

a

gm(x)gm(x)dx

]

αm =

∫ b

a

f(x)gm(x)dx

(7.13)

que pode ser escrito da forma

∫ b

a g1(x)g1(x)dx∫ b

a g2(x)g1(x)dx · · ·∫ b

a gm(x)g1(x)dx∫ b

ag1(x)g2(x)dx

∫ b

ag2(x)g2(x)dx · · ·

∫ b

agm(x)g2(x)dx

......

. . ....

∫ b

ag1(x)gm(x)dx

∫ b

ag2(x)gm(x)dx · · ·

∫ b

agm(x)gm(x)dx

α1

α2

...

αm

=

∫ b

a f(x)g1(x)dx∫ b

af(x)g2(x)dx

...∫ b

af(x)gm(x)dx

,

(7.14)

Os coeficientes αi, i = 1, 2, . . . ,m, podem ser obtidos resolvendo o sistema de equacoes

(7.13) ou (7.14).

Exemplo 7.4. Ajustar por mınimos quadrados um polinomio de primeiro grau, ϕ(x) = α1x+α2,

a funcao f(x) = 4x3, x ∈ [0, 1].

Aqui, m = 2, g1(x) = x, g2(x) = 1. Entao o sistema (7.13) pode ser escrito como

[∫ 1

0

x2dx

]

α1 +

[∫ 1

0

xdx

]

α2 =

∫ 1

0

4x4dx

[∫ 1

0

xdx

]

α1 +

[∫ 1

0

dx

]

α2 =

∫ b

a

4x3dx

ou1

3α1 +

1

2α2 =

4

51

2α1 + α2 = 1,

donde α1 = 185 , α2 = −4

5 . Para apreciar graficamente tal ajuste veja a figura

7.4 Caso Nao Linear 99

Figura 7.4 Ajuste de uma curva ϕ(x) = α1x+ α2 a funcao f(x) = 4x3.

7.4 Caso Nao Linear

As vezes, quer-se ajustar uma funcao ψ(x) que nao uma combinacao linear das funcoes

gi(x), i = 1, 2, . . . ,m. Neste caso, com frequencia, e possıvel realizar uma “linearizacao” dos dados,

tanto no caso discreto como no caso contınuo, de maneira que pode-se ajustar como anteriormente.

No caso discreto, os casos mais comuns e sua respectiva linearizacao sao mostrados na

seguinte tabela

Funcao ψ(x) Linearizacao Ajuste

ψ(x) = β2eβ1x ln(ψ(x)) = β1x+ ln(β2) ϕ(x) = α1x+ α2, β1 = α1, β2 = eα2

ψ(x) = β2βx1 ln(ψ(x)) =

[

ln(β1)]

x+ ln(β2) ϕ(x) = α1x+ α2, β1 = eα1 , β2 = eα2

ψ(x) = β2xβ1 ln(ψ(x)) = β1 ln(x) + ln(β2) ϕ(x) = α1 ln(x) + α2, β1 = α1, β2 = eα2

ψ(x) = eβ1x+β2 ln(ψ(x)) = β1x+ β2 ϕ(x) = α1x+ α2, β1 = α1, β2 = α2

ψ(x) = 1β1x+ β2

1ψ(x)

= β1x+ β2 ϕ(x) = α1x+ α2, β1 = α1, β2 = α2

Tabela 7.1 Casos mais frequentes de ajuste nao linear e sua respectiva linearizacao

Exemplo 7.5. Ajustar uma funcao ψ(x) = β2eβ1x aos dados da tabela


x 0, 1 1, 5 3, 3 4, 5 5, 0

f(x) 5, 9 8, 8 12, 0 19, 8 21, 5

Neste caso, ajusta-se uma reta ϕ(x) = α1x+ α2 aos dados

x 0, 1 1, 5 3, 3 4, 5 5, 0

g(x) = ln(f(x)) 1.7750 2.1748 2.4849 2.9857 3.0681

Aqui, m = 2, g1(x) = x, g2(x) = 1, e

α1 =

5

[

5∑

i=1xig(xi)

]

−[

5∑

i=1xi

] [

5∑

i=1g(xi)

]

5

[

5∑

i=1x2

i

]

−[

5∑

i=1xi

]2 =5 · 40, 4156− 14, 4 · 12, 4883

5 · 58, 4− (14, 4)2= 0, 2628,

α2 =

[

5∑

i=1g(xi)

]

−[

5∑

i=1xi

]

α1

5=

12, 4883− 14, 4 · 0, 2628

5= 1, 7407.

Portanto, β1 = α1 = 0, 2628 e β2 = eα2 = 5, 7014, e a funcao que ajusta os dados e

ψ(x) = 5, 7014 · e0,2628x.

Veja a figura 7.5.

Figura 7.5 Ajuste de uma curva ψ(x) = β2eβ1x aos dados da tabela.

Exercıcios


1. Tem-se a seguinte tabela de dados que correspondem as alturas e pesos de nove in-

divıduos de sexo masculino com idades entre 25 e 29 anos

Altura (m) 1, 83 1, 73 1, 68 1, 88 1, 58 1, 63 1, 93 1, 63 1, 78

Peso (kg) 79 69 70 81 61 63 79 71 73

(a) Ajuste, por quadrados mınimos, uma reta a esses dados de maneira que o peso

seja uma funcao linear da altura.

(b) Estime o peso de um indivıduo com 1, 75 de acordo com o resultado obtido no

ıtem anterior.

2. A tabela a seguir mostra o numero de habitantes do Brasil (em milhoes) desde 1872:

Ano 1872 1890 1900 1920 1940 1950 1960 1970 1980

Habitantes 9, 9 14, 3 17, 4 30, 6 41, 2 51, 9 70, 9 93, 1 130

Ajuste uma reta por quadrados mınimos a estes dados e obtenha uma estimativa da

populacao em 2004. A populacao verdadeira em 2004 e ao redor de 175 milhoes de

habitantes. Comente os resultados.

3. Ajuste por quadrados mınimos um polinomio quadratico a funcao f(x) = sen(x),

x ∈ [0, π].

4. Mediante quadrados mınimos, ajuste os dados

x −8 −6 −4 −2 0 2 4

f(x) 30 10 9 6 5 4 4

(a) por uma funcao ψ(x) = 1β1x+ β2

;

(b) por uma funcao ψ(x) = β2 · (β1)x.

(c) Que criterio ou procedimento utilizaria para afirmar qual funcao ψ(x) produz o

melhor ajuste.

5. A seguinte tabela de dados mostra o tempo (s), t de uma reacao quımica junto com a

concentracao (M), C

t 0, 05 0, 10 0, 15 0, 20 0, 25 0, 30

C 0, 86 0, 68 0, 59 0, 47 0, 43 0, 38

(a) Sabe-se que uma reacao quımica de primeira ordem esta governada pela equacao

C = C0ekt


onde C0 e a concentracao inicial e k e a constante de velocidade da reacao quımica.

Por mınimos quadrados, determine o valor de k.

(b) Sabe-se que uma reacao quımica de segunda ordem esta governada pela equacao

1

C=

1

C0+ kt.

Por mınimos quadrados determine o valor de k.

(c) Os dados da tabela correspondem mais provavelmente a qual tipo de reacao

quımica?

8 INTEGRACAO NUMERICA

8.1 Introducao

O objetivo central deste capıtulo e o calculo da integral

I =

∫ b

a

f(x)dx (8.1)

mediante uma solucao numerica. Tal tecnica de calculo recebe o nome de quadratura.

Especificamente, seja uma funcao integravel, f(x) definida sobre o intervalo [a, b]. A

ideia basica da quadratura e aproximar a integral mediante

∫ b

a

f(x)dx = A0f(x0) +A1f(x1) + · · ·+ Anf(xn), xi ∈ [a, b], i = 0, 1, . . . , n, (8.2)

onde os Ai sao certos coeficientes a serem determinados, bem como os pontos xi.

Os metodos mais comumente utilizados podem ser classificados em dois grupos:

1. As formulas de Newton-Cotes que utilizam a interpolacao, e

2. A quadratura gaussiana que esta baseada no fato em que a soma em (8.2) e o valor

exato da integral para polinomios de certos graus.

8.2 As Formulas de Newton-Cotes

A ideia basica e aproximar f(x) por um polinomio pn(x) que interpole f(x) em n+ 1

pontos, a = x0 < x1 < . . . < xn = b, igualmente espacados do intervalo [a, b] e realizar a integracao

sobre tal polinomio.

8.2.1 Regra dos Trapezios

Considere n = 1, a = x0 < x1 = b. Denote h = x1 − x0. O polinomio interpolador de

f(x) e

p1(x) = f(x0) +△f(x0)

h· (x− x0) ≈ f(x), (8.3)

103

8.2 As Formulas de Newton-Cotes 104

e integrando (8.3) tem-se

∫ x1

x0

f(x)dx ≈∫ x1

x0

p1(x)dx = f(x0) · (x1 − x0) +f(x1)− f(x0)

h· (x− x0)

2

2

∣

∣

∣

∣

x1

x0

= hf(x0) +h

2

(

f(x1)− f(x0))

(8.4)

e assim, a regra dos trapezios fica

∫ x1

x0

f(x)dx ≈∫ x1

x0

p1(x)dx =h

2

(

f(x0) + f(x1))

. (8.5)

O erro na integracao pela regra dos trapezios e obtido integrando o erro na inter-

polacao, isto e,

ET =

∫ x1

x0

w(x)f ′′(ξx)

2dx, (8.6)

onde, ξx ∈ [x0, x1], para cada x ∈ [x0, x1], e

w(x) = (x− x0)(x− x1). (8.7)

Observe que w(x) < 0, ∀x ∈ [x0, x1]. Se f ′′(x) e contınua sobre [x0, x1], entao ela

atinge seus valores mınimo e maximo nesse intervalo, isto e, existem constantes m e M tais que

m ≤ f ′′(ξx) ≤M, ∀x ∈ [x0, x1] (8.8)

entao

mw(x) ≥ w(x)f ′′(ξx) ≥Mw(x), ∀x ∈ [x0, x1], (8.9)

resultando que

m

∫ x1

x0

w(x)dx ≥∫ x1

x0

w(x)f ′′(ξx)dx ≥M∫ x1

x0

w(x)dx (8.10)

e levando em conta que∫ x1

x0w(x)dx < 0,

m ≤∫ x1

x0w(x)f ′′(ξx)dx∫ x1

x0w(x)dx

≤M. (8.11)

E pelo teorema do valor medio para integrais com peso w(x), existe c ∈ [x0, x1] tal que

∫ x1

x0

w(x)f ′′(ξx)dx = f ′′(c)

∫ x1

x0

w(x)dx. (8.12)


Da equacao (8.6), tem-se que

ET =1

2

∫ x1

x0

w(x)f ′′(ξx)dx =1

2f ′′(c)

∫ x1

x0

w(x)dx, c ∈ [x0, x1], (8.13)

mas∫ x1

x0

w(x)dx = −h3

6, (8.14)

e entao

ET = −h3

12f ′′(c), c ∈ [x0, x1], (8.15)

ou, em termos de estimativa,

∣

∣ET

∣

∣ ≤ h3

12M2, (8.16)

onde

M2 = max{|f ′′(x)| : x ∈ [x0, x1]}. (8.17)

8.2.2 Regra dos Trapezios Repetida

Pode-se observar que o erro (8.15) nao e pequeno quando o intervalo de integracao

e grande. Isto significa que o valor aproximado da integral nao e muito preciso. O que pode

ser feito neste caso e subdividir o intervalo de integracao [a, b] em pontos igualmente espacados

a = x0 < x1 < . . . < xn = b, onde h = xi+1 − xi, i = 0, 1, . . . , n− 1, a aplicar a regra dos trapezios

repetidamente a cada subintervalo [xi, xi+1], i = 0, 1, . . . , n− 1.

Entao

∫ b

a

f(x)dx =

n−1∑

i=0

∫ xi+1

xi

f(x)dx ≈n−1∑

i=0

[

h

2

(

f(xi) + f(xi+1))

]

(8.18)

sendo o erro cometido

ETR = −h3

12

n−1∑

i=0

f ′′(ci) = −nh3

12f ′′(ξ), (8.19)

para algum ξ ∈ [a, b]. A existencia de ξ esta garantida por uma generalizacao do Teorema do Valor

Intermediario.

Portanto,

∫ b

a

f(x)dx ≈ h

2

{

f(x0) + 2[

f(x1) + f(x2) + · · ·+ f(xn−1)]

+ f(xn)}

, (8.20)


e o erro cometido e

ETR = −nh3

12f ′′(ξ) (8.21)

com ξ ∈ [a, b], ou em termos de estimativa,

∣

∣ETR

∣

∣ ≤ nh3

12M2 (8.22)

onde

M2 = max{|f ′′(x)| : x ∈ [a, b]}. (8.23)

8.2.3 Regra de Simpson

Considere n = 2, a = x0 < x1 < x2 = b. Denote h = x1 − x0 = x2 − x1. O polinomio

interpolador de f(x) e

p2(x) = f(x0) +△f(x0)

h· (x− x0) +

△2f(x0)

2h2· (x − x0)(x − x1) ≈ f(x), (8.24)

e integrando (8.24) tem-se a regra de Simpson,

∫ x2

x0

f(x)dx ≈∫ x2

x0

p2(x)dx =h

3

(

f(x0) + 4f(x1) + f(x2))

. (8.25)

O erro na integracao pela regra de Simpson e obtido integrando o erro na interpolacao,

e pode-se mostrar que e

ES = −h5

90f (iv)(c), c ∈ [x0, x2], (8.26)


∣

∣ES

∣

∣ ≤ h5

90M4, (8.27)

onde

M4 = max{|f (iv)(x)| : x ∈ [x0, x2]}. (8.28)

8.2.4 Regra de Simpson Repetida

Similarmente ao caso da regra dos trapezios repetida, o intervalo de integracao [a, b]

pode ser dividido em pontos igualmente espacados a = x0 < x1 < . . . < xn = b, onde h = xi+1−xi,


i = 0, 1, . . . , n − 1, a aplicar a regra de Simpson repetidamente a cada subintervalo [xi, xi+2],

i = 0, 1, . . . , n− 2. Uma condicao para poder fazer isto e que n deve ser um numero par, n = 2k.

Entao

∫ b

a

f(x)dx =

k−1∑

i=0

∫ x2i+2

x2i

f(x)dx ≈k−1∑

i=0

[

h

3

(

f(x2i) + 4f(x2i+1) + f(x2i+2))

]

. (8.29)

Portanto,

∫ b

a

f(x)dx ≈h3

{

f(x0) + f(xn) + 4[

f(x1) + f(x3) + · · ·+ f(x2k−1)]

+ 2[

f(x2) + f(x4) + · · ·+ f(x2k−2)]}

,

(8.30)

e o erro cometido e

ESR = −nh5

180f (iv)(ξ) (8.31)


∣

∣ETR

∣

∣ ≤ nh5

180M4 (8.32)

onde

M4 = max{|f (iv)(x)| : x ∈ [a, b]}. (8.33)

8.2.5 Regra dos Tres Oitavos

Considere n = 3, a = x0 < x1 < x2 < x3 = b. Denote h = x1−x0 = x2−x1 = x3−x2.

O polinomio interpolador de f(x) e

p3(x) =f(x0) +△f(x0)

h· (x− x0) +

△2f(x0)

2h2· (x− x0)(x − x1)

+△3f(x0)

6h3· (x − x0)(x − x1)(x− x2) ≈ f(x),

(8.34)

e integrando (8.34) tem-se a regra dos tres oitavos,

∫ x3

x0

f(x)dx ≈∫ x3

x0

p3(x)dx =3h

8

(

f(x0) + 3f(x1) + 3f(x2) + f(x3))

. (8.35)


O erro na integracao pela regra dos tres oitavos e obtido integrando o erro na inter-

polacao, e pode-se mostrar que e

EO = −3h5

80f (iv)(c), c ∈ [x0, x2], (8.36)


∣

∣EO

∣

∣ ≤ 3h5

80M4, (8.37)

onde, como antes,

M4 = max{|f (iv)(x)| : x ∈ [x0, x3]}. (8.38)

8.2.6 Regra dos Tres Oitavos Repetida

O intervalo de integracao [a, b] pode ser dividido em pontos igualmente espacados

a = x0 < x1 < . . . < xn = b, onde h = xi+1 − xi, i = 0, 1, . . . , n − 1, a aplicar a regra dos tres

oitavos repetidamente a cada subintervalo [xi, xi+3], i = 0, 1, . . . , n− 2. Uma condicao para poder

fazer isto e que n deve ser um numero multiplo de 3, n = 3k.

Entao

∫ b

a

f(x)dx =k−1∑

i=0

∫ x3i+3

x3i

f(x)dx ≈k−1∑

i=0

[

3h

8

(

f(x3i) + 3f(x3i+1) + 3f(x3i+2) + f(x3i+3))

]

. (8.39)

Portanto,

∫ b

a

f(x)dx ≈3h

8

{

f(x0) + 3f(xn−2) + 3f(xn−1) + f(xn)

+

k−2∑

i=0

[

3f(x3i+1) + 3f(x3i+2) + 2f(x3i+3))}

,

(8.40)

e o erro cometido e

EOR = −nh5

80f (iv)(ξ) (8.41)


∣

∣ETR

∣

∣ ≤ nh5

80M4 (8.42)

onde

M4 = max{|f (iv)(x)| : x ∈ [a, b]}. (8.43)

8.3 Quadratura Gaussiana 109

Os erros das formulas de Newton-Cotes estao dados pelo seguinte teorema

Teorema 8.1. Se f(x) e uma funcao definida sobre o intervalo [a, b] e e de classe Cn+2 (funcoes

com as derivadas ate de ordem n+ 2 contınuas), entao o erro das formulas de Newton-Cotes sao

1. se n e impar,

En =hn+2

(n+ 1)!f (n+1)(ξ)

∫ n

0

u(u− 1) . . . (u − n)du, ξ ∈ [a, b] (8.44)

2. se n e par,

En =hn+3

(n+ 2)!f (n+2)(ξ)

∫ n

0

(

u− n

2

)

u(u− 1) . . . (u− n)du, ξ ∈ [a, b] (8.45)

8.3 Quadratura Gaussiana

Seja uma funcao integravel, f(x) definida sobre o intervalo [a, b]. Sempre e possıvel

expressar∫ b

a

f(x)dx =

∫ 1

−1

g(t)dt (8.46)

mediante a mudanca de variaveis

x =1

2

[

(b− a)t+ a+ b]

, (8.47)

e entao

g(t) =1

2(b− a) · f

(

1

2

[

(b − a)t+ a+ b]

)

(8.48)

A ideia basica da quadratura gaussiana e aproximar a integral mediante

∫ 1

−1

g(t)dt = A0g(t0) +A1g(t1) + · · ·+Ang(tn), ti ∈ [−1, 1], i = 0, 1, . . . , n, (8.49)

onde os Ai sao certos coeficientes a serem determinados, bem como os pontos ti, de maneira que

a formula (8.49) seja exata para todos os polinomios ate de grau 2n+ 1.

Para isto acontecer, basta considerar os polinomios 1, t, t2, . . . , t2n+1, formando o

seguinte sistema de equacoes

∫ 1

−1

tkdt = A0tk0 +A1t

k1 + · · ·+Ant

kn, k = 0, 1, . . . , 2n+ 1. (8.50)


Por exemplo, para n = 1, tem-se o sistema de equacoes

2 =

∫ 1

−1

t0dt =A0t00 +A1t

01 = A0 +A1

0 =

∫ 1

−1

t1dt =A0t10 +A1t

11 = A0t1 +A1t1

2

3=

∫ 1

−1

t2dt =A0t20 +A1t

21

0 =

∫ 1

−1

t3dt =A0t30 +A1t

31

(8.51)

Resolvendo tal sistema, tem-se

A0 = A1 = 1, t0 = −t1 =1√3. (8.52)

Utilizando os polinomios de Legendre, e possıvel demonstrar que o erro cometido pode

ser avaliado de maneira exata mediante

En =22n+1 · (n!)4

(2n+ 1) ·(

(2n)!)3 g

(2n)(ξ), ξ ∈ [−1, 1]. (8.53)

Os valores de Ai e ti sao apresentados na seguinte tabela ate n = 4:

n i ti Ai

1 0 0 2

2 1; 0 ±1/√

3 1

3 0; 1 ±0, 77459667 5/9

2 0 8/9

4 0; 1 ±0, 86113631 0, 34785484

2; 3 ±0, 33998104 0, 65214516

Exercıcios

1. Calcule as integrais pela regra repetida dos trapezios, de Simpson utilizando quatro e

seis divisoes de [a, b]. Compare com os resultados exatos.

(a)∫ 2

1

exdx


(b)∫ 4

1

√xdx

(c)∫ 14

2

1√xdx

2. Calcule as integrais do exercıcio anterior pela regra dos tres oitavos utilizando tres e

seis divisoes de [a, b]. Compare com os resultados exatos.

3. Considerando as integrais do exercıcio 1., quantas divisoes tem que ser feitas no in-

tervalo [a, b] para obter um erro menor que 10−5, quando sao utilizados as regras do

trapezio, de Simpson e dos tres oitavos?

4. Calcule o valor aproximado de∫ 0,6

0

1

1 + xdx

com tres digitos significativos exatos utilizando as regras repetidas dos trapezios, de

Simpson e dos tres oitavos. Em que sentido a regra de Simpson e melhor do que as

outras?

5. Determine h para poder avaliar

∫ π/2

0

cos(x)dx

com erro inferior a 10−3 utilizando a regra de Simpson e dos tres oitavos.

6. Calcule as integrais do exercıcio 1. mediante as formulas de quadratura gaussiana com

2 e 3 pontos e compare com os resultados exatos.

9 RESOLUCAO NUMERICA DE EQUACOES DIFERENCIAIS ORDINARIAS

9.1 Introducao

As equacoes diferenciais sao da mais notavel importancia no desenvolvimento cientıfico

atual pois elas aparecem sempre nas diversas areas da ciencia e da engenharia.

Em geral, uma equacao diferencial e uma equacao envolvendo uma funcao junto

com as suas variaveis independentes bem como as suas derivadas parciais ate de alguma ordem.

Tal ordem de diferenciacao determina a ordem da equacao diferencial.

Se uma equacao diferencial tem uma variavel independente, entao ela e denominada

uma equacao diferencial ordinaria que sera estudado neste capıtulo.

Se uma equacao diferencial tem mais de uma variavel independente, entao ela e de-

nominada uma equacao diferencial parcial. A resolucao numerica das equacoes diferenciais

parciais requer metodologias mais elaboradas e mais especıficas.

Uma solucao de uma equacao diferencial ordinaria e uma funcao que satisfaz a

equacao.

Se, dada uma equacao diferencial de ordemm, e a funcao, assim como as suas derivadas

sao especificadas em um mesmo ponto, x0, entao tem-se um problema de valor inicial.

Dada uma equacao diferencial escalar de ordem m, e facil transformar esta equacao

em um sistema de m equacoes de primeira ordem. Assim, seja a equacao diferencial

y(m) = F (x, y, y′, . . . , y(m−1)) (9.1)

faz-se

z1 = y entao:

z′1 = y′ = z2

z′2 = y′′ = z3

...

z′m−1 = y(m−1) = zm

z′m = y(m) = F (x, z1, z2, . . . , zm),

112

9.2 Erros 113

e no caso de equacoes diferenciais lineares, pode ser escrito matricialmente como

z′1

z′2

z′3...

z′m1

z′m

=

0 1 0 0 . . . 0 0

0 0 1 0 . . . 0 0

0 0 0 1 . . . 0 0

...

0 0 0 0 . . . 0 1

a0(x) a1(x) a2(x) a3(x) . . . am−2(x) am−1(x)

z1

z2

z3...

zm1

zm

+

0

0

0

...

0

f(x)

(9.2)

Neste capıtulo, considerar-se-ao metodos numericos para resolver o problema de valor

inicial

y′ = f(x, y)

y(x0) = y0.(9.3)

Os metodos estudados aqui baseiam-se na seguinte abordagem: dado o problema de

valor inicial (9.3), escolhem-se pontos x1 < x2 < x3 < . . . igualmente espacados, isto e, xi+1−xi =

h, ∀i = 0, 1, . . . e calculam-se as aproximacoes yi ≈ y(xi) da solucao exata utilizando informacao

sobre os pontos anteriores. Se para calcular yi utiliza-se apenas yi−1, o metodo e dito de passo

simples ou passo um. Se sao utilizados mais valores, o metodo e dito de passo multiplo.

9.2 Erros

Tem-se basicamente duas fontes de erro na resolucao numerica das equacoes diferen-

ciais ordinarias.

1. Erros de arredondamento: que dependem da aritmetica de ponto flutuante que esta

sendo utilizada pelo computador.

2. Erros de discretizacao: que podem ser de dois tipos

(a) Erro global: ǫg(xk+1), e a diferenca yk+1 − y(xk+1) onde y(x) e a solucao exata

do problema de valor inicial;

(b) Erro local: ǫl(xk+1), e a diferenca entre yk+1 e o valor, em xk+1, da solucao da

equacao diferencial que passa pelo ponto (xk, yk).

Um conceito importante para medir a precisaode um metodo numerico e sua ordem,

que e definida em termos do erro local de truncamento, como segue: um metodo numerico e dito

9.3 Metodo de Euler 114

de ordem p se existe um numero c tal que

|ǫl(xi)| ≤ chp+1. (9.4)

9.3 Metodo de Euler

O metodo de Euler esta dado por

yn+1 = yn + hf(xn, yn) (9.5)

e o erro local de dicretizacao esta dado por

ǫl(xn) =h2

2y′′(ξn), ξn ∈ [xn−1, xn]. (9.6)

9.4 Metodos de Taylor

O metodo de Taylor de ordem k esta dado por

yn+1 = yn + hy′n +h2

2y′′n + · · ·+ hk

k!y(k)

n (9.7)

e o erro local de dicretizacao esta dado por

ǫl(xn) =hk+1

(k + 1)!y(k+1)(ξn), ξn ∈ [xn−1, xn]. (9.8)

A principal dificuldade destes metodos e o calculo das derivadas y(i)n . O metodo de

Euler e o metodo de Taylor de ordem 1. O metodo de Taylor de ordem 2 esta dado por

yn+1 = yn + hf(xn, yn) +h2

2

(

fx(xn, yn) + fy(xn, yn)f(xn, yn))

(9.9)

9.5 Metodos de Runge-Kutta

Os metodos de Runge-Kutta estao baseados na ideia de concordar com o polinomio

de Taylor de ordem p mas sem exigir o calculo das derivadas parciais de f(x, y), calculando, porem

tal funcao em varios pontos.

9.5 Metodos de Runge-Kutta 115

O metodo de Runge-Kutta de ordem 1 e o metodo de Taylor.

Os metodos de Runge-Kutta de 2 podem ser escritos da forma

yn+1 = yn + ha1f(xn, yn) + ha2f(xn + b1h, yn + b2hy′n) (9.10)

Para haver concordancia com o polinomio de Taylor de ordem 2, e necessario que

a1 + a2 = 1

a2b1 = 1/2

a2b2 = 1/2.

(9.11)

A escolha a1 = a2 = 1/2, b1 = b2 = 1, determina o metodo de Euler aperfeicoado,

yn+1 = yn +h

2

(

K1 +K2

)

(9.12)

onde K1 = f(xn, yn) e K2 = f(xn + h, yn + hK1).

A escolha a1 = 0, a2 = 1/2, b1 = b2 = 1/2, determina o metodo de Euler modifi-

cado,

yn+1 = yn + hK2 (9.13)

onde K1 = f(xn, yn) e K2 = f(xn + h/2, yn +K1h/2).

Um metodo de Runge-Kutta de ordem 3 esta dado por

yn+1 = yn +h

9

(

2K1 + 3K2 + 4K3

)

(9.14)

onde

K1 = f(xn, yn)

K2 = f(xn + h/2, yn +K1h/2)

K3 = f(xn + 3h/2, yn + 3K2h/4).

Um metodo de Runge-Kutta de ordem 4 esta dado por

yn+1 = yn +h

6

(

K1 + 2K2 + 2K3 +K4

)

(9.15)

9.6 Metodos de Passo Multiplo 116

onde

K1 = f(xn, yn)

K2 = f(xn + h/2, yn +K1h/2)

K3 = f(xn + h/2, yn +K2h/2)

K4 = f(xn + h, yn +K3h).

9.6 Metodos de Passo Multiplo

Os metodos Adams estao baseados na integracao da equacao diferencial mediante

metodos de quadratura.

Como y′ = f(x, y), pode-se integrar entre xn e xn+1:

∫ xn+1

xn

y′(x)dx =

∫ xn+1

xn

f(x, y(x))dx

y(xn+1)− y(xn) =

∫ xn+1

xn

f(x, y(x))dx

y(xn+1) = y(xn) +

∫ xn+1

xn

f(x, y(x))dx

Seja fi = f(xi, yi).

9.6.1 Metodos Explıcitos

Aproxima-se f(x, y(x)) pelo polınomio interpolador pm(x) que passa pelos pontos

(xn, fn), . . . , (xn−m, fn−m).

No caso m = 3, tem-se

yn+1 = yn +h

24

(

55fn − 59fn−1 + 37fn−2 − 9fn−3

)

. (9.16)

9.6.2 Metodos Implıcitos

Aproxima-se f(x, y(x)) pelo polınomio interpolador pm+1(x) que passa pelos pontos

(xn+1, fn+1), (xn, fn), . . . , (xn−m, fn−m).

9.6 Metodos de Passo Multiplo 117

No caso m = 2, tem-se

yn+1 = yn +h

24

(

9fn+1 + 19fn − 5fn−1 + fn−2

)

. (9.17)

9.7 Exercıcios

1. Considere o problema de valor inicial

y′ = −20y

y(0) = 1

(a) Qual e a formula para yn fornecida por qualquer metodo de Runge-Kutta de

ordem 2?

(b) O que acontece com a solucao do item anterior quando h > 0, 1?

2. Considere o problema de valor inicial

y′ = 4− 2x

y(0) = 2

e h = 0, 5, 0, 25, 0, 125, 0, 1

(a) Calcule y(1)

(b) O que acontece com a solucao do item anterior quando h > 0, 1?

3. Qual e metodo de passo multiplo explıcito com m = 1 e qual e o metodo de passo

multiplo implıcito com m = 0? Compare tal metodo com o metodo de Euler?

4. Qual e metodo de passo multiplo explıcito com m = 2 e qual e o metodo de passo

multiplo implıcito com m = 1?

Apostila Metodos Numericos

Documents