METODOS_NUMERICOS_2014_1_ALIMENTOS.pdf

Prévia do material em texto

UNIVERSIDADE FEDERAL DE UBERLAˆNDIA
CAMPUS AVANC¸ADO DE PATOS DE MINAS
FACULDADE DE MATEMA´TICA
ENGENHARIA DE ALIMENTOS
ME´TODOS NUME´RICOS
PROFa MARTA HELENA DE OLIVEIRA
2016
Suma´rio
1 REVISA˜O DE A´LGEBRA LINEAR 2
2 SISTEMAS LINEARES 10
2.1 Me´todos Diretos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.1 Me´todo de Eliminac¸a˜o de Gauss . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.2 Estrate´gia de Pivoteamento . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.3 Me´todo de Gauss-Jordan . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.4 Fatorac¸a˜o LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.5 Algoritmo de Thomas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Me´todos Iterativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 Crite´rio geral de Convergeˆncia . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.2 Me´todo Iterativo de Gauss-Jacobi . . . . . . . . . . . . . . . . . . . . . . 22
2.2.3 Me´todo Iterativo de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . 23
2.2.4 SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 AJUSTE DE CURVAS 27
3.1 ME´TODO DOS MI´NIMOS QUADRADOS - MMQ . . . . . . . . . . . . . . . . 27
3.1.1 Ajuste linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.2 Ajuste na˜o-linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4 INTERPOLAC¸A˜O POLINOMIAL 33
4.1 Forma de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2 Forma de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Estudo do erro na interpolac¸a˜o polinomial . . . . . . . . . . . . . . . . . . . . . 37
5 EQUAC¸O˜ES NA˜O-LINEARES 42
5.1 Zero de equac¸o˜es na˜o lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.1.1 Isolamento de ra´ızes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.1.2 Crite´rio de Parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.1.3 Me´todo da Bissecc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.1.4 Me´todo da Falsa-Posic¸a˜o (Regula-Falsi) . . . . . . . . . . . . . . . . . . . 46
5.1.5 Me´todo de Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.1.6 Me´todo Iterativo Linear (MIL) . . . . . . . . . . . . . . . . . . . . . . . 47
5.1.7 Me´todo de Newton-Raphson (MNR) . . . . . . . . . . . . . . . . . . . . 48
5.1.8 Ordem de Convergeˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.1.9 Multiplicidade das soluc¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.1.10 Acelerando a convergeˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2 Sistemas de Equac¸o˜es na˜o Lineares . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2.1 Crite´rios de Parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.2.2 Me´todo de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2.3 Me´todos Quase-Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
ii
6 INTEGRAC¸A˜O NUME´RICA 57
6.1 Fo´rmulas de Newton-Cottes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.1.1 Regra do Trape´zio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.1.2 Regra do Trape´zio Repetida . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.1.3 Regra 1/3 de Simpson . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.1.4 Regra 1/3 de Simpson Repetida . . . . . . . . . . . . . . . . . . . . . . . 61
6.2 Fo´rmulas de Quadraturas de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2.1 Quadratura de Gauss-Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2.2 Quadratura de Gauss-Radau . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2.3 Quadratura de Gauss-Lobato . . . . . . . . . . . . . . . . . . . . . . . . 65
7 EQUAC¸O˜ES DIFERENCIAIS ORDINA´RIAS DE PRIMEIRA ORDEM 67
7.1 Me´todos de Passo Simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.1.1 Me´todo de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.1.2 Me´todos da Se´rie de Taylor . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.1.3 Me´todos de Runge-Kutta . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Refereˆncias Bibliogra´ficas 72
Cap´ıtulo 1
REVISA˜O DE A´LGEBRA LINEAR
Definic¸a˜o 1.1 Uma matriz real A e´ dita nula quando todos seus elementos forem iguais a
zero.
Definic¸a˜o 1.2 Uma matriz real A e´ dita quadrada quando o nu´mero de linhas e´ igual ao
nu´mero de colunas.
Se A e´ uma matriz quadrada n× n diz-se que A e´ uma matriz de ordem n.
Definic¸a˜o 1.3 Os elementos de uma matriz quadrada onde i = j formam o que chamamos de
diagonal principal. A outra diagonal e´ chamada de diagonal secunda´ria.
Uma matriz A quadrada e´ uma matriz diagonal se aij = 0 sempre que i 6= j.
Definic¸a˜o 1.4 Uma matriz diagonal A, de ordem n e´ chamada de matriz identidade ou
matriz unidade quando todos os elementos da diagonal principal forem iguais a 1.
Representa-se uma matriz identidade de ordem n por In. Por exemplo, a matriz identidade
de 4a ordem e´ dada por
I4 =

1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

Definic¸a˜o 1.5 Sejam as matrizes Am×n e Bm×n. Dizemos que as matrizes A e B sa˜o iguais
se aij = bij para todo i = 1, 2, · · · ,m e j = 1, 2, · · · , n.
Definic¸a˜o 1.6 Dada uma matriz real A denomina-se como matriz oposta de A a matriz
(−A) cujos elementos sa˜o os elementos opostos dos elementos de A.
Propriedades da adic¸a˜o de matrizes: Dadas as matrizes A,B,C temos:
2
3
1) A+B = B + A Comutativa
2) A+ (B + C) = (A+B) + C Associativa
3) A+ 0 = A Elemento Neutro
4) A+ (−A) = O Elemento Oposto
Propriedades da multiplicac¸a˜o de matrizes: Dadas as matrizes A,B,C temos:
1) A(B + C) = AB + AC Distributiva
2) A(BC) = (AB)C Associativa
3) AIn = A Elemento Neutro
Desde que as operac¸o˜es acima estejam definidas.
Definic¸a˜o 1.7 Se A e´ uma matriz m× n denominamos a matriz transposta de A a matriz At
n×m. A matriz transposta e´ obtida pela troca ordenada das linhas pelas colunas de A.
Definic¸a˜o 1.8 Uma matriz real A, n× n, e´ sime´trica se At = A.
Definic¸a˜o 1.9 Uma matriz real A, n× n, e´ anti-sime´trica se A = −At.
Definic¸a˜o 1.10 Uma matriz real A, de ordem n, possui matriz inversa se existe uma matriz
A−1, de ordem n, tal que
A.A−1 = In
Quando existe a matriz inversa da matriz A dizemos que a matriz A e´ invers´ıvel ou na˜o-
singular.
Definic¸a˜o 1.11 Matriz linha ou vetor linha: e´ uma matriz de uma linha e n colunas, ou
seja, de tamanho 1× n.
Definic¸a˜o 1.12 Matriz coluna ou vetor coluna: e´ uma matriz de uma coluna e n linhas,
ou seja, de tamanho n× 1.
Definic¸a˜o 1.13 Matriz triangular superior e´ uma matriz quadrada de ordem n, onde
todos os elementos abaixo da diagonal principal sa˜o nulos.
Como ilustrac¸a˜o considere a matriz triangular superior de ordem 4.
1 0 −10 20
0 −2 −3 3
0 0 0 4
0 0 0 5

4
Definic¸a˜o 1.14 Matriz triangular inferior e´ uma matriz quadrada de ordem n, onde todos
os elementos acima da diagonal principal sa˜o nulos.
Definic¸a˜o 1.15 Matrizes esparsas sa˜o matrizes de grande porte que possuem grande quan-
tidade de zeros.
Dada uma transformac¸a˜o linear de um espac¸o vetorial T : V → V , deseja-se saber quais
vetores sa˜o levados em um mu´ltiplo de si mesmo; isto e´, procura-se um vetor v ∈ V e um
escalar λ ∈ R tais que
T (v) = λv.
Nesse caso T (v) sera´ um vetor na mesma direc¸a˜o ”direc¸a˜o”que v. Por vetores de mesma
direc¸a˜o supo˜e-se a mesma reta suporte.
Como v = 0 satisfaz a equac¸a˜o para todo λ, deseja-se encontrar vetores v 6= 0satisfazendo
a condic¸a˜o acima. O escalar λ sera´ chamado de autovalor ou valor caracter´ıstico e o vetor
v de autovetor ou vetor caracter´ıstico associado.
Definic¸a˜o 1.16 Seja T : V → V um operador linear. Se existirem v ∈ V , v 6= 0 e λ ∈ R tais
que T (v) = λv, λ e´ um autovalor e v um autovetor associado a λ.
Me´todo Pra´tico para determinar autovalores e autovetores
Dada uma matriz A de ordem n a forma de encontrar seus autovalores e´ determinar as
ra´ızes do polinoˆmio caracter´ıstico de grau n det (A− λI) = 0, onde I e´ a matriz identidade de
ordem n, ou seja In.
Exemplo 1.1 Determine os autovalores da matriz A
A =
 4 2 0−1 1 0
0 1 2

Exerc´ıcio 1.1 Determine os autovalores da matriz A
A =
(
−3 4
−1 2
)
Definic¸a˜o 1.17 Matriz Positiva Definida sa˜o matrizes as quais possuem todos os autova-
lores positivos.
Definic¸a˜o 1.18 Matriz na˜o-singular sa˜o matrizes que possuem matriz inversa, ou seja,
cujo determinante e´ diferente de zero.
5
Definic¸a˜o 1.19 Uma matriz A, de ordem n, e´ dita uma matriz diagonalmente dominante
se o valor absoluto do elemento da diagonal principal e´ maior ou igual a` soma dos valores
absolutos dos elementos restantes da mesma linha. Para todas as linha. Ou seja,
|aii| ≥
n∑
j=1
i6=j
|aij| para i = 1, 2, · · · , n (1.1)
Definic¸a˜o 1.20 Uma matriz A, de ordem n, e´ dita uma matriz estritamente diagonal-
mente dominante se o valor absoluto do elemento da diagonal principal e´ maior do que a
soma dos valores absolutos dos elementos restantes da mesma linha. Para todas as linha. Ou
seja,
|aii| >
n∑
j=1
i6=j
|aij| para i = 1, 2, · · · , n (1.2)
Definic¸a˜o 1.21 Matriz tridiagonal e´ uma matriz quadrada no qual todos os elementos na˜o
nulos se localizam em treˆs diagonais.
As diagonal ditadas na definic¸a˜o anterior sa˜o a diagonal principal e as diagonais imediatamente
superior e inferior a diagonal principal. Po exemplo:
1 −3 0 0 0
−2 −2 −3 0 0
0 −8 7 4 0
0 0 −2 5 0
0 0 0 −2 0

De forma ana´loga a definic¸a˜o (17) tambe´m temos matrizes com 5 diagonais. Por exemplo:

1 3 0 0 3 0 0
2 2 3 0 0 2 0
0 8 7 4 0 0 3
0 0 2 5 0 0 0
1 0 0 2 0 2 0
0 4 0 0 7 8 5
0 0 7 0 0 1 3

Definic¸a˜o 1.22 O fator de condic¸a˜o ou (condition number) para uma matriz na˜o-singular
A e´ definido por
K(A) = ‖A‖ ∥∥A−1∥∥
Outra forma de definir o fator de condic¸a˜o e´ dada por:
K(A) =
λn
λ1
6
onde λn e λ1 sa˜o o maior e o menor autovalor de A respectivamente.
Definic¸a˜o 1.23 O trac¸o de uma matriz quadrada A, de ordem n, e´ definido por
trac¸o(A) =
n∑
i=1
aii
Se λi sa˜o os autovalores de A, para i = 1, 2, · · · , n, pode-se mostrar que
trac¸o(A) =
n∑
i=1
λi
Definic¸a˜o 1.24 O posto ou rank de uma matriz A e´ definido como o maior conjunto de
vetores linearmente independentes (li) dos vetores que compo˜em a matriz A.
Definic¸a˜o 1.25 Uma matriz A e´ dita Matriz ortogonal se At = A−1
Definic¸a˜o 1.26 A norma de uma matriz A ∈ Rn×m e´ um nu´mero real na˜o negativo que satisfaz
as propriedades:
1) ‖A‖ ≥ 0, ∀A ∈ Rn×m
2) ‖αA‖ = |α| ‖A‖, ∀A ∈ Rn×m e ∀α ∈ R
3) ‖A+B‖ ≤ ‖A‖+ ‖B‖, ∀A,B ∈ Rn×m
Norma de matrizes e vetores: Considere a matriz A ∈ Rn×m.
As normas matriciais mais usadas sa˜o:
‖A‖1 = max1≤j≤m
{
n∑
i=1
|aij|
}
Norma do Ma´ximo das Colunas
‖A‖∞ = max1≤i≤n
{
m∑
j=1
|aij|
}
Norma do Ma´ximo das Linhas
‖A‖2 =
(
n∑
i=1
m∑
j=1
|aij|2
)1/2
Norma Euclidiana
A norma vetorial pode ser vista como um caso particular da norma matricial, onde
x e´ um vetor do Rn, ou seja, x e´ uma matriz x × 1. Assim as normas para vetores sa˜o dadas
por
‖x‖1 =
n∑
i=1
|xi| Norma da soma
7
‖x‖∞ = max1≤i≤n |xi| Norma do Ma´ximo
‖x‖2 =
(
n∑
i=1
|xi|2
)1/2
Norma Euclidiana
Sistemas Lineares
Um sistema linear de ordem n se escreve da forma

a11x1 + a12x2 + a13x3 + · · · + a1nxn = b1
a21x1 + a22x2 + a23x3 + · · · + a2nxn = b2
...
...
...
. . .
...
...
an1x1 + an2x2 + an3x3 + · · · + annxn = bn.
(1.3)
onde aij sa˜o os coeficientes, xi sa˜o as inco´gnitas e bj sa˜o os termos independentes. Esse sistema
possui uma representac¸a˜o matricial na forma
Ax = b
com A ∈ Rn×n, x, b ∈ Rn×1, ou seja,
A =

a11 a12 · · · a1n
a21 a22 · · · a2n
...
...
. . .
...
an1 an2 · · · ann
 , x =

x1
x2
...
xn
 e b =

b1
b2
...
bn
 .
Considere o sistema linear abaixo:
−7x1 + 3x2 + 2x3 = −2
x1 + 3x2 − x3 = 3
x1 + x2 − 3x3 = −1
Exerc´ıcio 1.2 Considerando a matriz A, dos coeficientes do sistema acima, responda as se-
guintes questo˜es:
a) verifique se a matriz A e´ diagonalmente dominante;
b) calcule os autovalores da matriz A;
c) verifique se a matriz A e´ positiva definida;
d) calcule o determinante da matriz A;
8
e) calcule todas as normas vistas da matriz A;
f) calcule todas as normas vistas do vetor b.
Exerc´ıcio 1.3 a) A matriz do exerc´ıcio 1 e´ na˜o singular?
b) O sistema linear acima pode ser resolvido pelo me´todo tradicional x = A−1.b?
c) Se a resposta do item anterior for positiva, resolva o sistema.
Aritme´tica de pontos flutuantes
Nesse estudo, os algoritmos e ana´lises sa˜o desenvolvidos com nu´meros reais. Modernos com-
putadores digitais, entretanto, na˜o fazem ca´lculos e armazenamentos com nu´meros reais. Eles
trabalham com um subconjunto conhecido como nu´meros de pontos flutuantes.
As quantidades que sa˜o armazenadas em um computador, ou lidas em um arquivo, ou ob-
tidas em resultados intermedia´rios dos ca´lculos poder ser aproximados por nu´meros de pontos
flutuantes. Em geral, estes nu´meros produzidos na pra´tica computacional diferem daqueles
obtidos por ca´lculos aritme´ticos exatos. Naturalmente, a performance dos computadores de-
pendem de obter estas diferenc¸as (erros) as menores poss´ıveis.
Estabilidade e sistemas mal condicionados
Os termos condicionamento e estabilidade sa˜o frequentemente utilizados em computac¸a˜o
nume´rica. Infelizmente seus significados muitas vezes variam de autor para autor. Mas, as
definic¸o˜es abaixo sa˜o amplamente aceitas e utilizadas.
Condicionamento e´ a propriedade de um problema nume´rico a ser controlado (tanto
pode ser um problema linear, um problema de otimizac¸a˜o, um problema de edo’s,etc). Um
problema e´ dito bem condicionado se sua soluc¸a˜o na˜o e´ fortemente afetada por pequenas
pertubac¸o˜es nos dados que definem o problema. Ou seja, se pequenas alterac¸o˜es nos dados
levam a soluc¸o˜es distintas tem-se um problema mal condicionado.
O condicionamento de um sistema pode ser medido pelo fator de condic¸a˜o:
• fator de condic¸a˜o elevado significa que o problema e´ mal condicionado;
• pequenos valores do fator de condic¸a˜o significa que o sistema e´ bem condicionado.
A estabilidade e´ uma propriedade do algoritmo. Um algoritmo e´ esta´vel se garante a ob-
tenc¸a˜o de respostas precisas para problemas bem condicionados (mesmo utilizando aritme´tica
de ponto flutuante).
9
Algoritmo e´ um procedimento que descreve, sem ambiguidades, uma sequeˆncia finita de
passos a serem feitos em uma ordem espec´ıfica. O objetivo do algoritmo e´ implementar um
procedimento para resolver um problema ou aproximar uma soluc¸a˜o do problema.
Usa-se pseudoco´digos para descric¸a˜o dos algoritmos. Os pseudoco´digos devem ser imple-
mentados em softwares nume´ricos para obter a aproximac¸a˜o nume´rica de problemas estudados.
Entre esses softwares podemos citar MATLAB, SCILAB, MAPLE, MATHEMATICA, C e
FORTRAM.
Exerc´ıcio 1.4 Resolva o sistema linear abaixo. Trace o gra´fico das respectivas retas.{
x1 − 2x2 = −19
0.54x1 −x2 = −9
Exerc´ıcio 1.5 Transformando o sistema linear anteriorno sistema abaixo{
x1 − 2x2 = −19
0.56x1 −x2 = −9
decida se este e´ ou na˜o um sistema mal condicionado.
Cap´ıtulo 2
SISTEMAS LINEARES
Os me´todos nume´ricos teˆm por objetivo resolver sistemas lineares poss´ıveis determina-
dos, tais sistemas sa˜o aqueles onde a matriz dos coeficientes e´ na˜o-singular (possui matriz
inversa), ou seja, seu determinante e´ diferente de zero.
Me´todos nume´ricos, para resoluc¸a˜o de sistemas lineares, sa˜o divididos em 2 grupos:
• me´todos diretos (Exatos): sa˜o aqueles me´todos que permitem obter a soluc¸a˜o exata de
um sistema linear, caso ela exista, com certa precisa˜o apo´s um nu´mero finito de operac¸o˜es.
A soluc¸a˜o e´ obtida a menos de erros de arredondamento.
• me´todos iterativos: sa˜o me´todos que geram uma sequeˆncia de aproximac¸o˜es, para a
soluc¸a˜o, atrave´s de um processo repetitivo de operac¸o˜es. A partir de uma aproximac¸a˜o
inicial os me´todos iterativos aproximam a soluc¸a˜o, caso ela exista.
Ambos sa˜o u´teis e ambos apresentam limitac¸o˜es.
Vantagens e desvantagens: os me´todos diretos apresentam apenas o erro de arredondamento,
ao passo que os me´todos iterativos tambe´m apresentam o erro de truncamento.
Em sistemas lineares de grande porte, os erros de arredondamento podem tornar a soluc¸a˜o
sem significado para os me´todos diretos, enquanto que nos me´todos iterativos os erros de arre-
dondamento na˜o se acumulam.
2.1 Me´todos Diretos
Em geral, nos me´todos diretos transformamos o sistema original num sistema equivalente
(atrave´s de operac¸o˜es elementares) cuja soluc¸a˜o e´ obtida resolvendo sistemas lineares triangu-
lares.
Definic¸a˜o 2.1 Um sistema linear, de ordem n, e´ um sistema triangular superior se tiver
a forma
10
11

a11x1 + a12x2 + · · · + a1nxn = b1
a22x2 + · · · + a2nxn = b2
. . .
...
...
annxn = bn.
(2.1)
onde os coeficientes aii 6= 0, i = 1, 2, · · · , n. Assim a soluc¸a˜o do sistema triangular superior e´
obtida por retro-substituic¸a˜o. Algebricamente podemos resolveˆ-lo pelas fo´rmulas
xn =
bn
ann
...
xi =
(
bi −
n∑
j=i+1
aijxj
)
1
aii
, para i = n− 1, · · · , 2, 1
Definic¸a˜o 2.2 As submatrizes principais Ak, k = 1, 2, · · · , n sa˜o constitu´ıdas pelas k pri-
meiras linhas e k primeiras colunas de A.
Definic¸a˜o 2.3 Os menores principais det(Ak) de ordem k, k = 1, 2, · · · , n da matriz A,
sa˜o definidos pelos determinantes das submatrizes principais de A.
Definic¸a˜o 2.4 Uma matriz real sime´trica A, n×n, e´ positiva definida se para todos os seus
menores principais Ak, k = 1, 2, · · · , n tem-se
det(Ak) > 0 para k = 1, 2, · · · , n.
Para conhecer se uma matriz real sime´trica A, n × n, e´ positiva definida calcula-se seus
autovalores λi e verifica se λi > 0 para i = 1, 2, · · · , n.
Algoritmo 2.1 Resoluc¸a˜o de um sistema triangular superior.
Dado um sistema triangular superior com aii 6= 0 para i = 1, 2, · · · , n as inco´gnitas x1, · · · , xn
sa˜o obtidas por:
xn = bn/ann;
Para k = n− 1, · · · , 1
s = 0;
12
Para j = k + 1, · · · , n
s = s+ akjsj;
xk = (bk − s)/akk;
Definic¸a˜o 2.5 Um sistema linear,de ordem n, e´ triangular inferior se obtiver a forma

a11x1 = b1
a21x1 + a22x2 = b2
a31x1 + a32x2 + a33x3 = b3
...
...
...
. . .
...
an1x1 + an2x2 + an3x3 + · · · + annxn = bn.
(2.2)
onde os coeficientes aii 6= 0, i = 1, 2, · · · , n. A soluc¸a˜o do sistema triangular superior e´ obtida
por substituic¸a˜o direta.
Analogamente ao sistema triangular superior podemos resolveˆ-lo por fo´rmulas.
Exerc´ıcio 2.1 Escreva as fo´rmulas para a resoluc¸a˜o do sistema triangular inferior por substi-
tuic¸a˜o direta.
Exerc´ıcio 2.2 Escreva o algoritmo para a soluc¸a˜o do sistema triangular inferior por substi-
tuic¸a˜o direta.
2.1.1 Me´todo de Eliminac¸a˜o de Gauss
O me´todo de Eliminac¸a˜o de Gauss, ou me´todo de Eliminac¸a˜o de Gaussiana, consiste em
transformar o sistema linear dado em um sistema triangular equivalente ao sistema original.
Atrave´s de operac¸o˜es elementares sobre as linhas ou colunas, obtemos o sistema triangular
superior ou o sistema triangular inferior, respectivamente. Vamos adotar a convenc¸a˜o de traba-
lhar com o sistema triangular superior (trabalhar com o sistema triangular inferior e´ totalmente
semelhante).
Operac¸o˜es Elementares
i multiplicar a i-e´sima linha (Li) por um escalar na˜o-nulo k;
ii permutar a i-e´sima e a j-e´sima linha;
iii Substituir a i-e´sima linha pela i-e´sima linha mais m vezes o oposto da j-e´sima linha
(Li ← Li −mLj).
13
Seja o sistema linear Ax = b, de ordem n, onde A possui todas as submatrizes principais
na˜o-singulares, ou seja, det(Ak) 6= 0, k = 1, 2, · · · , n. Considere a matriz aumentada do sistema
linear e efetue operac¸o˜es elementares sobre as linhas (ou colunas) transformando a matriz A
em uma matriz triangular superior (inferior).
Os elementos da diagonal principal akk sa˜o chamados de pivoˆs e os escalares mik =
a
(k−1)
ik
a
(k−1)
kk
sa˜o chamados de multiplicadores, para k = 1, 2, · · · , n− 1 e i = k + 1, · · · , n.
Exemplo 2.1 Resolva o sistema linear abaixo, usando o me´todo de eliminac¸a˜o de Gauss.

3x1 + 2x2 + 4x3 = 1
x1 + x2 + 2x3 = 2
4x1 + 3x2 − 2x3 = 3.
Algoritmo 2.2 Resoluc¸a˜o de um sistema linear Ax = b usando o me´todo de eliminac¸a˜o de
Gauss.
Dado um sistema linear Ax = b onde An×n, xn×1 e bn×1. Supor que akk 6= 0 na etapa k.
Para k = 1, · · · , n− 1
Para i = k + 1, · · · , n
m = aik
akk
aik = 0
Para j = k + 1, · · · , n
aij = aij −makj
fim
bi = bi −mbk
fim
fim
Retorne A e b.
14
Resolva o sistema triangular superior (Algoritmo 2.1).
Avaliac¸a˜o do res´ıduo/erro
O erro � produzido por uma soluc¸a˜o x do sistema Ax = b pode ser avaliado pela expressa˜o
� = max
1≤i≤n
|ri| (2.3)
sendo ri a i-e´sima componente do vetor res´ıduo R, definido por,
R = b− Ax. (2.4)
Exemplo 2.2 Calcule o res´ıduo para o exemplo 2.1.
Observac¸a˜o 2.1 1) O nu´mero de operac¸o˜es efetuadas na fase de eliminac¸a˜o e´ de (4n3 +
3n2 − 7n)/6 e, para a resoluc¸a˜o do sistema triangular superior o nu´mero de operac¸o˜es
efetuadas e´ de n2. Assim o me´todo de Gauss efetua (4n3+9n2−7n)/6 operac¸o˜es no total.
2) O determinante da matriz A e´ igual ao determinante da matriz resultante An−1.(produto
dos elementos da diagonal principal)
3) O me´todo de Gauss na˜o pode ser aplicado se o pivoˆ for nulo akk = 0.
4) Os erros de arredondamento cometidos durante um passo da obtenc¸a˜o do sistema trian-
gular se propagam para os passos seguintes, podendo comprometer a validade da soluc¸a˜o
obtida.
Para resolver o problema descrito na observac¸a˜o 3 e minimizar o problema descrito na ob-
servac¸a˜o 3 usa-se a estrate´gia do pivoteamento.
2.1.2 Estrate´gia de Pivoteamento
Para o me´todo de eliminac¸a˜o de Gauss e´ imposs´ıvel trabalhar com um pivoˆ nulo (akk = 0)
e para um pivoˆ pro´ximo de zero o me´todo pode conduzir a resultados totalmente imprecisos.
Estrate´gias de pivoteamento e´ o processo de escolha da linha e/ou coluna pivotal, ou seja,
escolher para pivoˆ o elemento de maior mo´dulo.
15
Estrate´gia de Pivoteamento Parcial
Essa estrate´gia se resume em:
a) no in´ıcio da etapa k da fase de eliminac¸a˜o, escolher para pivoˆ o elemento de maior mo´dulo
entre os coeficientes: a
(k−1)
ik , i = k, k + 1, · · · , n.
b) trocar as linhas i e k se for necessa´rio
Exemplo 2.3 Resolva o sistema linear abaixo, usando o me´todo de eliminac¸a˜o de Gauss com
pivoteamento parcial.

3x1 + 3x2 + x3 = 7
2x1 + 2x2 − x3 = 3
x1 − x2 + 5x3 = 5.
Exerc´ıcio 2.3 Resolva o sistema linear abaixo considerando:{
0.0001x1 + x2 = 1
x1 + x2 = 2
a) O me´todo de eliminac¸a˜o de Gauss (utilizando 4 casadecimais)
b) O me´todo de eliminac¸a˜o de Gauss com pivoteamento parcial.
c) analise o res´ıduo para ambos os casos.
Exerc´ıcio 2.4 Aplique as estrate´gias de pivoteamento parcial a` matriz:
A(1)|b(1) =

3 2 1 −1 | 5
0 1 0 3 | 6
0 −3 −5 7 | 7
0 2 4 0 | 15
 ,
Estrate´gia de Pivoteamento Completo
Nessa estrate´gia, no in´ıcio da etapa k e´ escolhido para pivoˆ o elemento de maior mo´dulo,
entre todos os elementos que ainda atuam no processo de eliminac¸a˜o.
max
i,j≥k
∣∣∣a(k−1)ij ∣∣∣
16
Exemplo 2.4 Aplique a estrate´gia de pivoteamento completo a` matriz do exerc´ıcio 2.4:
Exerc´ıcio 2.5 Aplique a estrate´gia de pivoteamento completo a` matriz:
A(0)|b(0) =

3 2 1 −1 | 5
7 1 0 3 | 6
−3 −1 −5 0 | 7
−2 2 4 1 | 15
 ,
A estrate´gia de pivoteamento completo na˜o e´ muito utilizada devido a extensa comparac¸a˜o
entre os elementos a
(k−1)
ij i, j ≥ k. Esse fato acarreta grande esforc¸o computacional.
2.1.3 Me´todo de Gauss-Jordan
O me´todo de Gauss-Jordan e´ uma variac¸a˜o do me´todo de Gaus. O me´todo de Gauss-Jordan
apresenta as seguintes variac¸o˜es:
I) todas as linhas sa˜o normalizadas, pela divisa˜o do pivoˆ
II) e quando uma varia´vel e´ eliminada, no me´todo de Gauss-Jordan, ela e´ eliminada de todas
as outras equac¸o˜es.
O passo de eliminac¸a˜o resulta na matriz identidade e na˜o na matriz triangular superior (ou
inferior), consequentemente na˜o e´ necessa´rio usar substituic¸a˜o regressiva (ou progressiva) para
obter o resultado.
Exemplo 2.5 Resolva o sistema linear abaixo, usando o me´todo de Gauss-Jordan.

2x1 + x2 − x3 = 1
5x1 + 2x2 + 2x3 = −4
3x1 + x2 + x3 = 5
2.1.4 Fatorac¸a˜o LU
O processo de fatorac¸a˜o, para resoluc¸a˜o de sistema linear, consiste em decompor a matriz
dos coeficientes A em um produto de dois ou mais fatores e em seguida resolver uma sequeˆncia
de sistemas lineares (mais simples) que conduzira´ a soluc¸a˜o do sistema original Ax = b.
A fatorac¸a˜o LU e´ um dos processos de fatorac¸a˜o mais empregados a´ resoluc¸a˜o de sistemas
lineares. Nessa fatorac¸a˜o L e´ uma matriz triangular inferior com diagonal unita´ria e U e´ uma
17
matriz triangular superior.
Os fatores L e U podem ser obtidos atrave´s de fo´rmulas ou usando a ide´ia ba´sica do me´todo
de eliminac¸a˜o de Gauss. O primeiro me´todo dificulta a estrate´gia de pivoteamento.
Resoluc¸a˜o do sistema linear Ax = b usando a fatorac¸a˜o LU . Sejam Ax = b um
sitema linear, de ordem n, e a fatorac¸a˜o LU da matriz A assim
Ax = b ⇔ (LU)x = b⇔ L(Ux) = b
seja y = Ux a soluc¸a˜o do sistema triangular superior. A soluc¸a˜o do sistema original e´ obtida
pela resoluc¸a˜o do sistema triangular inferior
Ly = b
e posteriormente pela resoluc¸a˜o do sistema triangular superior
Ux = y.
O fator U e´ a matriz obtida no final do processo de eliminac¸a˜o de Gauss e o fator L e´ a
matriz formada pelos respectivos multiplicadores.
A vantagem do uso do processo de fatorac¸a˜o para resoluc¸a˜o de sistema linear e´ que pode-se
resolver qualquer sistema que tenha A como matriz dos coeficientes sem reiniciar o processo.
Exemplo 2.6 Resolva o sistema linear abaixo, usando a fatorac¸a˜o LU .

3x1 + 2x2 + 4x3 = 1
x1 + x2 + 2x3 = 2
4x1 + 3x2 + 2x3 = 3
Exemplo 2.7 Resolva o sistema linear abaixo, usando a fatorac¸a˜o LU .

3x1 + 2x2 + 4x3 = −3
x1 + x2 + 2x3 = 1
4x1 + 3x2 + 2x3 = 1
As fo´rmulas utilizadas para obter os fatores LU :
18
uij = aij −
i−1∑
k=1
likukj i ≤ j
lij =
(
aij −
j−1∑
k=1
likukj
)
1
ujj
i > j
Para o uso dessas fo´rmulas usa-se a convenc¸a˜o de que
∑k
j=1 ≡ 0 se k < 1.
Exerc´ıcio 2.6 Aplique as fo´rmulas acima para obter a fatorac¸a˜o LU da matriz A.
A =
 2 0 10 2 1
1 1 3

Exerc´ıcio 2.7 Considerando a matriz do exerc´ıcio 2.6 resolva o sistema linear Ax = b onde b
e´ dado por
b = [1 2 3]t
R = [0.125 0.625 0.75]t
Algoritmo 2.3 Fatorac¸a˜o LU .
Para m = 1, 2, · · · , n− 1 fac¸a
Para j = m,m+ 1, · · · , n fac¸a
umj = amj −
m−1∑
k=1
lmkukj
Para i = m+ 1, · · · , n
lim =
(
aim −
m−1∑
k=1
likukm
)
1
umm
lmm = 1
Para m = n fac¸a
19
unn = ann −
n−1∑
k=1
lnkukn
2.1.5 Algoritmo de Thomas
O algoritmo de Thomas e´ um esquema de armazenamento que otimiza a ocupac¸a˜o do espac¸o
na memo´ria do computador. Esse algoritmo e´ aplicado para sistemas que possuem 3 ou 5 dia-
gonais.
O algoritmo de Thomas e´ uma variac¸a˜o do me´todo de Eliminac¸a˜o de Gauss para matrizes
esparsas. Consiste do armazenamento da matriz A em vetores e se resume a eliminar os ele-
mentos das diagonais inferiores a` diagonal principal.
Descric¸a˜o do me´todo para matrizes tridiagonais:

d1 u1
l2 d2 u2
l3 d3 u3
. . . . . . . . .
li di ui
. . . . . . . . .
ln−1 dn−1 un−1
ln dn


x1
x2
x3
...
xi
...
xn−1
xn

=

b1
b2
b3
...
bi
...
bn−1
bn

. (2.5)
Vetor u = [u1, u2, . . . , un−1].
Vetor d = [d1, d2, . . . , dn].
Vetor l = [l2, l3, . . . , ln].
Operac¸o˜es: d¯1 = d1 e b¯1 = b1, para k = 2, 3, . . . , n temos:
d¯k = dk − lk¯dk−1
uk−1
b¯k = bk − lk¯dk−1
¯bk−1.
Os vetor u na˜o se altera e o vetor l se anula. A soluc¸a˜o do sistema e´ obtida por substituic¸a˜o
20
reversa a qual pode ser expressa pelas equac¸o˜es:
xn =
b¯n
d¯n
, xk =
b¯k − ukxk+1
d¯k
para k = n− 1, n− 2, . . . , 1.
Exemplo 2.8 Aplique o Algoritmo de Thomas a matriz:
A =

1 2 0 0 0
2 −2 3 0 0
0 1 −1 2 0
0 0 3 1 2
0 0 0 2 4

Observac¸a˜o 2.2 Se o sistema for diagonalmente dominante o algoritmo de Thomas sempre
encontrara´ a soluc¸a˜o do sistema.
2.2 Me´todos Iterativos
Nesse to´pico vamos estudar me´todos nume´ricos para resoluc¸a˜o de sistemas lineares de ordem
n que sa˜o poss´ıveis determinados. Ou seja,

a11x1 + a12x2 + a13x3 + · · · + a1nxn = b1
a21x1 + a22x2 + a23x3 + · · · + a2nxn = b2
...
...
...
. . .
...
...
an1x1 + an2x2 + an3x3 + · · · + annxn = bn.
(2.6)
onde aij sa˜o os coeficientes, xi sa˜o as inco´gnitas e bj sa˜o os termos independentes. Esse sistema
possui uma representac¸a˜o matricial na forma
Ax = b
com A ∈ Rn×n, x, b ∈ Rn×1, ou seja,
A =

a11 a12 · · · a1n
a21 a22 · · · a2n
...
...
. . .
...
an1 an2 · · · ann
 , x =

x1
x2
...
xn
 e b =

b1
b2
...
bn
 .
Estudaremos treˆs esquemas nume´ricos iterativos, ou seja, dado a aproximac¸a˜o inicial x0
21
os me´todos geram uma sequeˆncia de vetores xk. Sob certas condic¸o˜es essa sequeˆncia converge
para o vetor soluc¸a˜o x∗. Chamaremos de x uma soluc¸a˜o aproximada do sistema 5.4.
Para cada classe de sistema estudados a soluc¸a˜o x∗ pode ser obtida pela resoluc¸a˜o da equac¸a˜o
matricial x∗ = A−1 ∗ b. No entanto para calcular explicitamente a matriz A−1 e´ preciso um
grande nu´mero de operac¸o˜es, o que torna o processo na˜o competitivo com os me´todos iterativos.
Seja o sistema linear Ax = b tal que A ∈ Rn×n, x, b ∈ Rn×1. Os me´todos iterativos
reescrevem esse sistema na forma
x = Cx+ g (2.7)
onde a matriz de iterac¸a˜o C ∈ Rn×n e os vetores x, g ∈ Rn×1. Assim montamos o processo
iterativo: dado x0 calculamos
xk+1 = Cxk + g.
Definic¸a˜o: Dizemos que uma sequeˆncia de vetores xk converge para x∗ se
lim
k−→∞
∥∥xk − x∥∥ = 0 (2.8)
E assim podemos definir outros crite´rios de parada. Dado uma precisa˜o � > 0 temos:
∥∥xk+1 − xk∥∥ < � Erro absoluto
∥∥xk+1 − xk∥∥
‖xk‖ < � Erro Relativo
∥∥b− Axk∥∥ < � Teste do Res´ıduo
2.2.1 Crite´rio geral de Convergeˆncia
A convergeˆncia do processo iterativo depende da forma damatriz C, cujo crite´rio geral e´
definido pelo teorema:
Teorema 2.1 Seja x∗ a soluc¸a˜o do sistema linear Ax = b. O processo iteratico
xk+1 = Cxk + g
gera uma sequeˆncia xk que converge para a soluc¸a˜o x se e somente se ‖C‖ < 1.
Note que o crite´rio de convergeˆncia na˜o depende do valor inicial x0. A escolha de x0 influ-
encia no nu´mero de iterac¸o˜es necessa´rias para atingir a precisa˜o desejada. Quanto menor for
‖x0 − x∗‖ menor sera´ a quantidade de iterac¸o˜es necessa´rias para atingir a precisa˜o desejada.
22
2.2.2 Me´todo Iterativo de Gauss-Jacobi
Vamos considerar o sistema linear Ax = b dado na equac¸a˜o 5.4, para o qual aii 6= 0, i =
1, 2, . . . , n. Em cada equac¸a˜o (i) podemos isolar a inco´gnita xi obtendo as seguintes equac¸o˜es:

x1 =
1
a11
(b1 − a12x2 − a13x3 − · · · − a1nxn)
x2 =
1
a22
(b2 − a21x1 − a23x3 − · · · − a2nxn)
...
...
. . .
...
xn =
1
ann
(
bn − an1x1 − an2x2 − · · · − an,(n−1)xn−1
) (2.9)
Na forma matricial essas equac¸o˜es sa˜o equivalentes a`

x1
x2
...
xn
 =

0 −a12
a11
−a13
a11
· · · −a1n
a11
−a21
a22
0 −a23
a22
· · · −a2n
a22
...
...
...
. . .
...
− a11
ann
− an2
ann
− an3
ann
· · · 0


x1
x2
...
xn
 +

b1
a11
b2
a22
...
bn
ann
 . (2.10)
E assim temos o sistema linear na forma x = Cx + g. Na pra´tica o processo iterativo
conhecido como me´todo de Gauss-Jacobi utiliza a equac¸a˜o 2.9. Dado x0 temos

x
(k+1)
1 =
1
a11
(
b1 − a12x(k)2 − a13x(k)3 − · · · − a1nx(k)n
)
x
(k+1)
2 =
1
a22
(
b2 − a21x(k)1 − a23x(k)3 − · · · − a2nx(k)n
)
...
...
. . .
...
x
(k+1)
n = 1ann
(
bn − an1x(k)1 − an2x(k)2 − · · · − an,(n−1)x(k)n−1
) (2.11)
Crite´rio das linhas: Usando a norma do ma´ximo das linhas na matriz C em 2.11 temos
o seguinte corola´rio:
Corola´rio 2.1 (Crite´rio das linhas para o Me´todo de Gauss-Jacobi)
Dado o sistema linear Ax = b. Seja αk da forma
αk =
1
|akk|
 n∑
j=1
j 6=k
|ak,j|
 < 1 para k = 1, 2, . . . , n.
enta˜o o me´todo de Gauss-Jacobi gera uma sequeˆncia xk que converge para a soluc¸a˜o do sistema.
Esse corola´rio e´ apenas suficiente para a convergeˆncia, ou seja, se este crite´rio for satisfeito
23
o me´todo de Gauss-Jacobi sera´ convergente. Pore´m, pode ser que o me´todo seja convergente e
o crite´rio das linha na˜o seja satisfeito.
Exemplo 2.9 Dado o sistema linear
−7x1 + 3x2 + 2x3 = −2
x1 + 3x2 − x3 = 3
x1 + x2 − 3x3 = −1
e a aproximac¸a˜o inicial x0 = [0.5 0.5 0.5]t, aplique o me´todo de Gauss-Jacobi para � = 0.1.
Utilize o erro absoluto na norma ‖.‖∞.
Corola´rio 2.2 O crite´rio das linhas e´ satisfeito se e somente se a matriz A dos coeficientes
for estritamente diagonalmente dominante.
Algoritmo 2.4 Dados de entrada: matriz A ∈ Rn×n, vetores b, x0 ∈ Rn e a precisa˜o � > 0.
Enquanto
∥∥xk+1 − xk∥∥ > � fac¸a
para s = 1, 2, . . . , n fac¸a
xk+1s =
1
ass
(
bs −
∑n
j=1
j 6=s
as,jx
(k)
j
)
fim
fim
sa´ıda: vetor x ∈ Rn. Aproximac¸a˜o para soluc¸a˜o do sistema.
2.2.3 Me´todo Iterativo de Gauss-Seidel
A cada iterac¸a˜o a sequeˆncia xk se aproxima da soluc¸a˜o do sistema. Baseado nessa informac¸a˜o
vamos modificar o me´todo de Gauss-Jacobi, com o objetivo de acelerar a convergeˆncia do
me´todo. Na iterac¸a˜o k + 1, o me´todo de Gauss-Jacobi calcula o elemento s pela equac¸a˜o
xk+1s =
1
ass
bs − n∑
j=1
j 6=s
as,jx
(k)
j

ou seja
xk+1s =
1
ass
(
bs −
s−1∑
j=1
as,jx
(k)
j −
n∑
j=s+1
as,jx
(k)
j
)
.
24
No ca´lculo de xk+1s os elementos x
k+1
1 , x
k+1
2 , . . . , x
k+1
s−1 ja´ foram calculados e espera-se que
estes estejam mais pro´ximos da soluc¸a˜o do que os elementos xk1, x
k
2, . . . , x
k
s−1. Assim vamos
substtuir os elemento x1, x2, . . . , xs da iterac¸a˜o k pelos respectivos elementos da iterac¸a˜o k+ 1.
Esse procedimento e´ conhecido como me´todo de Gauss-Siedel e e` calculado por
xk+1s =
1
ass
(
bs −
s−1∑
j=1
as,jx
(k+1)
j −
n∑
j=s+1
as,jx
(k)
j
)
(2.12)
Como estamos usando valores mais pro´ximos da soluc¸a˜o, o ca´lculo de xk+1s sera´ mais preciso.
Aplicando a norma do ma´ximo das linhas temos o crite´rio de convergeˆncia para o me´todo de
Gauss-Siedel:
Corola´rio 2.3 (Crite´rio de Sassenfeld) Dado o sistema linear Ax = b. Seja βk da forma
βk =
1
|akk|
(
k−1∑
j=1
|ak,j| βj +
n∑
j=k+1
|ak,j|
)
< 1 para k = 1, 2, . . . , n.
Enta˜o o me´todo de Gauss-Siedel gera uma sequeˆncia xk que converge para a soluc¸a˜o do sistema.
Exemplo 2.10 Dado o sistema linear
−7x1 + 3x2 + 2x3 = −2
x1 + 2x2 − x3 = 2
x1 + x2 − 2x3 = 0
e a aproximac¸a˜o inicial x0 = [0.5 0.5 0.5]t, aplique o me´todo de Gauss-Siedel para � = 0.1.
Utilize o erro absoluto na norma ‖.‖∞.
Observac¸a˜o 2.3 1. Note que se aplicarmos o crite´rio das linhas ao exemplo anterior temos
α2 = α3 = 1, ou seja, o crite´rio das linhas na˜o e´ satisfeito. Esse e´ um exemplo onde na˜o
se tem a garantia de convergeˆncia para o me´todo de Gauss-Jacobi.
2. Em um sistema linear a ordem das equac¸o˜es na˜o altera a soluc¸a˜o exata, pore´m os me´todos
iterativos de Gauss-Jacobi e Gauss-Siedel dependem fundamentalmente da disposic¸a˜o das
linhas e/ou colunas.
Exemplo 2.11 Verifique se o sistema linear abaixo possui convergeˆncia pelos me´todos de
Gauss-Jacobi e Gauss-Siedel 
2x1 + x2 + 3x3 = 9
− x2 + x3 = 1
x1 + 3x3 = 3
Caso a resposta seja negativa, verifique se ha´ alguma permutac¸a˜o de linhas (ou colunas) poss´ıvel
para garantir a convergeˆncia dos me´todos nume´ricos para este sistema.
25
a) Caso a resposta seja negativa, verifique se ha´ alguma permutac¸a˜o de linhas (e/ou de
colunas) poss´ıvel para garantir a convergeˆncia dos me´todos nume´ricos para este sistema.
b) Havendo uma permutac¸a˜o poss´ıvel, resolva o sistema linear com a nova formulac¸a˜o. Uti-
lize o erro relativo na norma ‖‖1. Considere precisa˜o de 8 × 10−2 e o ma´ximo de 5
iterac¸o˜es.
2.2.4 SOR
O relaxamento representa uma pequena modificac¸a˜o no me´todo de Gauss-Siedel. Essa
te´cnica foi criada para melhorar a convergeˆncia do me´todo. Apo´s cada novo valor x calculado,
usando a equac¸a˜o 2.12, esse valor e´ modificado por uma me´dia ponderada dos resultados da
iterac¸a˜o anterior e da iterac¸a˜o atual, ou seja,
xk+1s = (1− ω)xks + ωx̂k+1s . (2.13)
Onde ω e´ o fator de relaxac¸a˜o e x̂ e´ calculado pelo me´todo de Gauss-Siedel, dado na equac¸a˜o
2.12. Usando as equac¸o˜es 2.12 e 2.13 podemos escrever a equac¸a˜o
xk+1s = (1− ω)xks +
ω
ass
(
bs −
s−1∑
j=1
as,jx
(k+1)
j −
n∑
j=s+1
as,jx
(k)
j
)
. (2.14)
a qual e´ conhecida como me´todo SOR, sucessive over-relaxation (ou SRS, sobre-relaxac¸a˜o
sucessiva). Ao se fazer ω > 1 tentamos aumentar a velocidade de um processo com boa con-
vergeˆncia, enquanto que ao se fazer ω < 1 pode-se tornar convergente um processo originalmente
divergente. Dessa forma temos a seguinte classificac¸a˜o:
• 1 < ω < 2: sobre-relaxac¸a˜o;
• 0 < ω < 1: sub-relaxac¸a˜o;
• ω = 1: me´todo de Gauss-Siedel.
O valor de ω na˜o pode ser superior a 2, ou o processo iterativo se tornara´ divergente em algum
ponto pro´ximo a sua soluc¸a˜o.
Exemplo 2.12 Resolva o sistema linear abaixo utilizado o me´todo SOR, para ω = 1.25 e
x0 = [1 1 1]t. Utilize erro absoluto na norma do ma´ximo com precisa˜o de 10−2. Fac¸a no
ma´ximo 4 iterac¸o˜es. 
4x1 + 3x2 = 24
3x1 + 4x2 − x3 = 30
− x2 + 4x3 = −24
Convergeˆncia
26
Teorema 2.2 : Se A e´ uma matriz irredut´ıvel, diagonalmente dominante para pelo menos uma
linha, enta˜o o me´todo SOR converge se 0 < ω ≤ 1.
Teorema2.3 : Se A e´ uma matriz sime´trica positiva definida, enta˜o o me´todo SOR converge
se 0 < ω < 2.
Cap´ıtulo 3
AJUSTE DE CURVAS
Uma forma de trabalhar com uma func¸a˜o definida por uma tabela de valores e´ a interpolac¸a˜o
polinomial. Contudo a interpolac¸a˜o na˜o e´ adequada quando:
1. e´ preciso obter um valor aproximado para a func¸a˜o em um ponto fora do intervalo de
tabelamento;
2. os valores tabelados sa˜o resultados de algum experimento f´ısico, ou alguma pesquisa, pois
nestes casos estes valores podera˜o conter erros.
O ajuste de curvas permite extrapolar (aproximar pontos fora do intervalo utilizado) va-
lores com certa margen de seguranc¸a.
3.1 ME´TODO DOS MI´NIMOS QUADRADOS - MMQ
3.1.1 Ajuste linear
Dado um conjunto de pontos (xk, f(xk)), k = 1, 2, ...,m. O ajuste de curvas consiste em
determinar uma func¸a˜o ϕ(x) tal que o desvio em cada ponto k, definido por
dk = f(xk)− ϕ(xk) (3.1)
seja mı´nimo. Onde ϕ(xk) e´ uma combinac¸a˜o linear de func¸o˜es cont´ınuas gi(x), i = 1, 2, ..., n
escolhidas de acordo com os dados do problema. Isto e´,
ϕ(x) = α1g1(x) + α2g2(x) + . . .+ αngn(x).
Dizemos que a func¸a˜o ϕ(xk) e´ linear nos paraˆmetros αi. A escolha das func¸o˜es gi depende
do gra´fico dos pontos tabelados, chamado de diagrama de dispersa˜o. Atrave´s deste pode-se
visualizar que tipo de curva se ajusta melhor aos dados.
Exemplo 3.1 : Construir o diagrama de dispersa˜o da tabela abaixo:
27
28
x 0.5 0.65 0.7 0.8 0.9 1.1 1.35
f(x) 0.75 0.87 0.91 0.96 0.99 0.99 0.87
A ana´lise do diagrama de dispersa˜o mostra que a func¸a˜o que procuramos se comporta como
uma para´bola. Logo poder´ıamos escolher as func¸o˜es g1(x) = 1, g2(x) = x e g3(x) = x
2, pois
ϕ(x) = α1g1(x) + α2g2(x) + α3g3(x)
representa todas as para´bolas. Com a escolha adequada das constantes αi i = 1, 2, 3 teremos
aquela que melhor se ajusta aos pontos.
No Scilab
x = [0.5 0.65 0.7 0.8 0.9 1.1 1.35];
f = [0.75 0.87 0.91 0.96 0.99 0.99 0.87];
plot(x,f,’.’)
xtitle(’Diagrama de dispersa˜o’)
O me´todo dos mı´nimos quadrados consiste em determinar os coeficientes αi de forma que a
soma dos quadrados dos desvios seja mı´nima. Isto e´, encontrar αi de forma que minimizam a
func¸a˜o
F (α1, α2, ..., αn) =
m∑
k=1
[f(xk)− (α1g1(xk) + α2g2(xk) + . . .+ αngn(xk))]2 (3.2)
A func¸a˜o F e´ uma func¸a˜o que satisfaz F (α) ≥ 0 ∀α ∈ R. Isto e´, uma func¸a˜o limitada
inferiormente e portanto tem ponto de mı´mino. Este ponto pode ser determinado pelo teste da
primeira derivada, sendo
∂F
∂αi
∣∣∣
(α1,...,αn)
= 0,
29
i = 1, 2, ..., n.
Dessa forma temos

α1
m∑
k=1
g1(xk)g1(xk) + α2
m∑
k=1
g1(xk)g2(xk) + . . . + αn
m∑
k=1
g1(xk)gn(xk) =
m∑
k=1
f(xk)g1(xk)
α1
m∑
k=1
g2(xk)g1(xk) + α2
m∑
k=1
g2(xk)g2(xk) + . . . + αn
m∑
k=1
g2(xk)gn(xk) =
m∑
k=1
f(xk)g2(xk)
...
...
. . .
...
...
α1
m∑
k=1
gn(xk)g1(xk) + α2
m∑
k=1
gn(xk)g2(xk) + . . . + αn
m∑
k=1
gn(xk)gn(xk) =
m∑
k=1
f(xk)gn(xk)
Que representa um sistema linear n× n da forma

a11α1 + a12α2 + a13α3 + · · · + a1nαn = b1
a21α1 + a22α2 + a23α3 + · · · + a2nαn = b2
...
...
...
. . .
...
...
an1α1 + an2α2 + an3α3 + · · · + annαn = bn.
(3.3)
onde aij =
m∑
k=1
gi(xk)gj(xk) e bi =
m∑
k=1
f(xk)gi(xk).
Esse sistema tem uma u´nica soluc¸a˜o se os vetores formados por gk = (gk(x1), ..., gk(xn))
sa˜o linearmente independentes. Isso equivale a ter func¸o˜es gi(x) linearmente independentes. A
matriz A associada ao sistema linear e´ uma matriz real sime´trica, ou seja, aij = aji.
Ajustar um conjunto de pontos pelo me´todo dos mı´nimos quadrados significa resolver um
sistema linear semelhante a` 3.3 cujo erro e´ calculado por
Erro =
m∑
k=1
(fk − ϕk)2 . (3.4)
Exemplo 3.2 : Considere a tabela abaixo e:
x -0.6 -0.5 -0.3 0 0.2 o.4 0.5
f(x) 0.45 0.4 0.5 0 0.2 0.6 0.5
a) construa o diagrama de dispersa˜o;
b) ajuste os dados a` func¸a˜o ϕ(x) = αx2
c) calcule o erro cometido na aproximac¸a˜o.
Exerc´ıcio 3.1 : Ajuste os dados da tabela abaixo pelo me´todo dos mı´nimos quadrados utili-
zando:
30
a) uma reta;
b) uma para´bola
c) calcule o erro cometido nas aproximac¸o˜es.
x 1 2 3 4 5 6
f(x) 0.5 0.6 0.9 0.8 1.2 1.5
Trace ambas as curvas no diagrama de dispersa˜o.
3.1.2 Ajuste na˜o-linear
O me´todo dos mı´nimos quadrados consiste em aproximar a func¸a˜o dada f(x) por uma
func¸a˜o ϕ(x) linear em seus paraˆmetros αi, i = 1, 2, ..., n.
Quando a aproximac¸a˜o sugerida for na˜o-linear deve-se fazer a linearizac¸a˜o do problema.
Exemplo 3.3 : Considere a tabela abaixo e:
x -1 -0.7 -0.4 -0.1 0.2 o.5 0.8 1.0
f(x) 36.55 17.264 8.155 3.852 1.820 0.86 0.406 0.246
Figura 3.1: Diagrama de dispersa˜o do exemplo 3
O diagrama de dispersa˜o na figura 3.1 sugere uma func¸a˜o exponencial, ou seja,
f(x) ≈ ϕ(x) = α1e−α2x.
Linearizac¸a˜o de ϕ(x): z = ln(ϕ(x))
31
O exemplo anterior ilustra a aproximac¸a˜o de f(x) por uma func¸a˜o exponencial. Tambe´m sa˜o
comuns problemas que a func¸a˜o f(x) deve ser aproximada por:
2o caso) Aproximar f(x) por uma func¸a˜o geome´trica
f(x) ≈ ϕ(x) = axb.
Aplicando logaritmo natural faz-se a linearizac¸a˜o
F (x) = ln(f(x))
a1 = lna a2 = b g1(x) = 1 g2(x) = lnx
3o caso) Aproximar f(x) por uma func¸a˜o hiperbo´lica
f(x) ≈ ϕ(x) = 1
a+ bx
e´ equivalente a aproximar 1
f(x)
= a+ bx. Assim
F (x) =
1
f(x)
,
a1 = a, a2 = b, g1(x) = 1 e g2(x) = x.
4o caso) Aproximar f(x) por
ϕ(x) =
√
a+ bx
e´ equivalente a aproximar
f 2(x) = a+ bx.
5o caso) Aproximar f(x) por
ϕ(x) = xln(a+ bx)
e´ equivalente a aproximar
e
f(x)
x = a+ bx
Exemplo 3.4 : Aproxime a func¸a˜o tabelada pela func¸a˜o racional ϕ(x) = a+x
2
b+x
e calcule o erro
cometido na aproximac¸a˜o.
x 0 1 2 3
f(x) 1 1 1.7 2.5
Exerc´ıcio 3.2 : Considere a func¸a˜o f(x) dada na tabela e fac¸a os ajustes pedidos abaixo.
x -8 -6 -4 -2 0 2 4
f(x) 30 10 9 6 5 4 4
a) ϕ = 1
a+bx
ou
32
b) ϕ = abx
Decida qual das func¸o˜es se ajusta melhor aos dados?
Cap´ıtulo 4
INTERPOLAC¸A˜O POLINOMIAL
Interpolar uma func¸a˜o f(x) consiste em aproximar essa func¸a˜o por uma outra func¸a˜o g(x),
escolhida entre uma classe de func¸o˜es definidas a priori, que satisfac¸a algumas propriedades.
A func¸a˜o g(x) e´ usada em substituic¸a˜o a func¸a˜o f(x). A interpolac¸a˜o polinomial estuda a
aproximac¸a˜o da func¸a˜o f(x) por polinoˆmios g(x) especialmente nos casos:
• na˜o conhecemos a expressa˜o anal´ıtica para f(x), ou seja, temos pontos tabelados;
• quando a func¸a˜o f(x) possui expressa˜o anal´ıtica de tratamento dif´ıcil (integrac¸a˜o, de-
rivac¸a˜o, ...).
A interpolac¸a˜o polinomial de um conjunto de pontos (xk, fk), k = 0, 1, 2, · · · , n consiste em
encontrar um polinoˆmio pn(x) de forma que
f(xk) = pn(xk) k = 0, 1, 2, · · · , n (4.1)
A igualdade fornecida na equac¸a˜o 4.1 e´ chamada de condic¸a˜o de interpolac¸a˜o e o po-
linoˆmio pn(x) e´ chamado de polinoˆmio interpolador.
Teorema 4.1 (Existeˆncia e Unicidade)
Dado um conjunto de (n+ 1) pontos distintos, isto e´,
(xk, fk) k = 0, 1, 2, · · · , n
com xk 6= xj para k 6= j. Existe um u´nico polinoˆmio interpolador p(x) de grau menor ou igual
a n tal que f(xk) = pn(xk) para k = 0, 1, 2, · · · , n.
Exemplo 4.1 Encontre uma aproximac¸a˜o para x = 0.3 usando o polinoˆmio interpolador para
os dados abaixo
x 0 0.2 0.4
f(x) 4 3.84 3.76
33
34
A determinac¸a˜o do polinoˆmio interpolador atrave´s da resoluc¸a˜o de sistemas lineares e´ uma
te´cnica trabalhosa e pouco eficiente. Estudaremos duas te´cnicas, mais eficientes, de obter o
polinoˆmio interpolador:
• a de Lagrange
• e a de Newton.
4.1 Forma de Lagrange
Considereo conjunto de n + 1 pontos distintos (xk, fk), k = 0, 1, 2, · · · , n. O polinoˆmio
interpolador de Lagrange e´ da forma
pn(x) =
n∑
k=0
fk Lk(x) (4.2)
ou seja, pn(x) = f0L0(x) + f1L1(x) + · · ·+ fnLn(x). Onde Lk sa˜o polinoˆmio de grau menor ou
igual a n que satisfazem a condic¸a˜o
Lk(xj) =
{
0, se k 6= j
1, se k = j.
(4.3)
Assim pn(xj) = f0L0(xj) + f1L1(xj) + · · · + fjLj(xj) + · · · + fnLn(xj). Pela condic¸a˜o 4.3
temos que
pn(xj) = fj.
Isso mostra que pn satisfaz a condic¸a˜o de interpolac¸a˜o 4.1. Os polinoˆmios Lk sa˜o chamados
de polinoˆmios de Lagrange e sa˜o obtidos da forma
Lk(x) =
(x− x0).(x− x1) · · · (x− xk−1).(x− xk+1) · · · (x− xn)
(xk − x0).(xk − x1) · · · (xk − xk−1).(xk − xk+1) · · · (xk − xn) (4.4)
Exemplo 4.2 Determine o polinoˆmio interpolador de Lagrange para os pontos da tabela abaixo
x 0 0.2 0.4
f(x) 4 3.84 3.76
Exerc´ıcio 4.1 Determine o polinoˆmio interpolador de Lagrange para os pontos (−2, 4), (0, 2), (2, 0)
e (4, 3) e calcule p(3).
35
4.2 Forma de Newton
A forma do polinoˆmio interpolador de Newton pn(x) que interpola a func¸a˜o f(x) em
x0, x1, · · · , n, (n+ 1) pontos distintos e´ dada por
pn(x) = do + d1(x− x0) + d2(x− x0)(x− x1) + · · ·+ dn(x− x0)(x− x1) · · · (x− xn−1) (4.5)
onde dk, k = 0, 1, 2, · · · , n sa˜o as diferenc¸as divididas de ordem k entre os pontos (xj, f(xj)),
j = 0, 1, 2, · · · , k
Operador diferenc¸as divididas
O operador diferenc¸as divididas de ordem zero da func¸a˜o f em xk, k = 0, 1, 2, · · · , n e´
definido por
f [x0] = f(x0).
O operador diferenc¸as divididas de ordem um da func¸a˜o f em xk, xk+1, k = 0, 1, 2, · · · , n−1
e´ definido por
f [xk, xk+1] =
f [xk+1]− f [xk]
xk+1 − xk .
O valor dado pela equac¸a˜o acima pode ser visto como uma aproximac¸a˜o para a primeira
derivada da func¸a˜o f(x) em xk.
O operador diferenc¸a dividida de ordem 2 nos pontos xk, xk+1, xk+2, k = 0, 1, 2, · · · , n− 2
e´ definido por
f [xk, xk+1, xk+2] =
f [xk+1, xk+2]− f [xk, xk+1]
xk+2 − xk .
De forma ana´loga, o operador diferenc¸a dividida de ordem n nos pontos x0, x1, · · · , xn e´
definido por
f [x0, x1, · · · , xn] = f [x1, x2, · · · , xn]− f [x0, x1, · · · , xn−1]
xn − x0 .
O ca´lculo desses operadores e´ construtivo, no sentido de que para obter as diferenc¸as divi-
didas de ordem n precisamos das diferenc¸as divididas de ordem n − 1, n − 2, · · · , 2, 1, 0. Por
esse motivo e´ conveniente organizar esses valores em uma tabela.
Tabela de diferenc¸as divididas
36
x Ordem 0 Ordem 1 · · · Ordem n
x0 f [x0] = f0
f [x0, x1] =
f [x1]−f [x0]
x1−x0 · · ·
x1 f [x1] = f1
f [x1, x2] =
f [x2]−f [x1]
x2−x1 · · ·
x2 f [x2] = f2
f [x2, x3] =
f [x3]−f [x2]
x3−x2 · · ·
x3 f [x3] = f3 f [x0, x1, · · · , xn] =
· · · f [x1,x2,··· ,xn]−f [x0,x1,··· ,xn−1]
xn−x0
...
...
...
· · ·
xn−1 f [xn−1] = fn−1
f [xn−1, xn] =
f [xn]−f [xn−1]
xn−xn−1 · · ·
xn f [xn] = fn
Exemplo 4.3 Construa a tabela de diferenc¸as divididas para os pontos da tabela abaixo
x -1 0 1 2
f(x) 1 2 0 -1
Forma do Polinoˆmio interpolador de Newton
Seja f(x) cont´ınua e com tantas derivadas quanto necessa´rias no intervalo [a, b]. Sejam
a = x0 < x1 < x2 < · · · < xn = b
(n+ 1) pontos distintos. A forma de Newton para o polinoˆmio interpolador, de grau menor ou
igual a n, que interpola a func¸a˜o f e´ dada por
pn(x) = f [x0] + f [x0, x1](x− x0) + f [x0, x1, x2](x− x0)(x− x1) + · · ·+ f [x0, x1, x2, · · · , xn](x− x0)(x− x1) · · · (x− xn−1)
(4.6)
Ou seja, d0 = f [x0], d1 = f [x0, x1], d2 = f [x0, x1, x2] e assim sucessivamente ate´ o u´ltimo
termo dn = f [x0, x1, x2, · · · , xn].
Na construc¸a˜o do polinoˆmio de Newton se obtem a expressa˜o para os erro da interpolac¸a˜o
polinomial, a qual e´ dada por
En(x) = f [x0, x1, x2, · · · , xn, x](x− x0)(x− x1) · · · (x− xn−1)(x− xn) (4.7)
37
De fato pn(x) interpola f(x) nos pontos x0 < x1 < x2 < · · · < xn, pois sendo
f(x) = pn(x) + En(x)
enta˜o para todo no´ xk, k = 0, 1, 2, · · · , n temos que En(x) = 0 e
f(xk) = pn(xk)
Exemplo 4.4 Construa o polinoˆmio de Newton para os pontos dados no exemplo 5.11
x -1 0 1 2
f(x) 1 2 0 -1
Observac¸a˜o 4.1 1) O operador diferenc¸as divididas e´ sime´trico em relac¸a˜o aos seus argu-
mentos. Ou seja, esse operador permite a permutac¸a˜o de seus argumentos, por exemplo
f [x0, x1] = f [x1, x0].
(Verifique!)
2) A simetria citada na observac¸a˜o 1 e´ va´lida para quaisquer ordem das diferenc¸as divididas.
3) Observamos ainda que e´ conveniente deixar o polinoˆmio na forma de Newton, sem agru-
par os termos semelhante, pois quando calcularmos o valor nume´rico de pn(x) em x = α
evitaremos o ca´lculo das poteˆncias.
4) O nu´mero de operac¸o˜es pode ser reduzido, um pouco mais se usarmos a forma dos
pareˆnteses encaixados. Por simplicidade de notac¸a˜o fac¸amos para n = 3:
p3(x) = f [x0] + f [x0, x1](x− x0) + f [x0, x1, x2](x− x0)(x− x1) + f [x0, x1, x2, x3](x− x0)(x− x1)(x− x2)
(4.8)
Utilizando a fo´rmula dos pareˆnteses encaixados obtemos
p3(x) = f [x0]+(x−x0)
(
f [x0, x1]+(x−x1)
(
f [x0, x1, x2]+(x−x2)f [x0, x1, x2, x3]
))
(4.9)
4.3 Estudo do erro na interpolac¸a˜o polinomial
Ao interpolar uma func¸a˜o f(x) por um polinoˆmio pn(x) comete-se um erro En(x), ou seja,
38
f(x) = pn(x) + En(x) ∀x ∈ (x0, x1).
O teorema abaixo fornece a expressa˜o exata para o erro na interpolac¸a˜o polinomial
Teorema 4.2 Sejam x0, x1, · · · , xn, n + 1 pontos distintos e pn(x) o polinoˆmio interpolador
sobre os pontos x0, x1, · · · , xn. Se f(x) e´ (n + 1) vezes diferencia´vel em [x0, xn] enta˜o para
x ∈ [x0, xn] o erro e´ dado por
En(x) = f(x)− pn(x) = (x− x0)(x− x1) · · · (x− xn−1)(x− xn)f
n+1(ξx)
(n+ 1)!
(4.10)
com ξx ∈ (x0, xn).
Da expressa˜o do erro para o polinoˆmio de Newton obtemos uma relac¸a˜o entre o operados
diferenc¸as divididas e as derivadas da func¸a˜o
Teorema 4.3
f [x0, x1, , · · · , xn, x] = f
n+1(ξx)
(n+ 1)!
(4.11)
com ξx ∈ (x0, xn) e x ∈ (x0, xn).
Para obter a expressa˜o do teorema 4.3 basta igualar as equac¸o˜es 4.7 e 4.10.
A fo´rmula do erro dada no teorema 4.2 possui uso limitado na pra´tica, pois sa˜o raras as
situac¸o˜es onde se conhece fn+1 e ξx. A importaˆncia da fo´rmula exata e´ teo´rica. Na pra´tica
calcula-se um limitante superior para o erro. Esse limitante e´ fornecido no corola´rio 4.1
Corola´rio 4.1 Ale´m das hipo´teses do teorema 4.2 se fn+1 for cont´ınua em I = [x0, xn] podemos
escrever
|En(x)| ≤ |f(x)− pn(x)| = |(x− x0)(x− x1) · · · (x− xn−1)(x− xn)| Mn+1
(n+ 1)!
(4.12)
onde Mn+1 = maxx∈I |fn+1(x)|.
Corola´rio 4.2 Ale´m das hipo´teses anteriores se os pontos forem igualmente espac¸ados
x1 − x0 = x2 − x1 = · · · = xn − xn−1 = h
enta˜o o limitante superior para o erro e´ dado por
|En(x)| < hn+1 Mn+1
4(n+ 1)
(4.13)
onde Mn+1 = maxx∈I |fn+1(x)|.
39
O corola´rio 4.2 ainda depende do ponto x considerado. Se a func¸a˜o f(x) e´ tabelada o valor
absoluto do erro |En(x)| so´ pode ser estimado, pois na˜o e´ poss´ıvel calcular Mn+1.
Utilizando o teorema 4.3 consegue-se uma estimativa para o erro, pois o mo´dulo da diferenc¸a
dividida de ordem n+ 1 aproxima Mn+1
(n+1)!
no intervalo [x0, xn].
Exemplo 4.5 Considere a func¸a˜o f(x) tabelada abaixo e
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
a) obtenha o polinoˆmio interpolador de grau 2;
b) calcule f(0.47);
c) e estime o erro cometido na aproximac¸a˜o.
Observac¸a˜o 4.2 A medida que aumentamos o nu´mero de pontos no intervalo [a, b] se aumen-
tarmos tambe´m o grau do polinoˆmio ocorre o fenoˆmeno de Runge, que e´ caracterizado em
aumentar o erro nos pontos extremos do intervalo.
Esse fato nos diz que o polinoˆmio interpolador na˜o e´ indicado para encontrar aproximac¸o˜es
para pontos fora do intervalo de interpolac¸a˜o.Para a extrapolac¸a˜o (aproximac¸a˜o de pontos fora
do intervalo) e´ indicado um me´todo de ajuste de cura que na˜o seja interpolac¸a˜o. Na figura 4.1
esta´ ilustrado um exemplo do que ocorre no fenoˆmeno de Runge.
Figura 4.1: Ilustrac¸a˜o do fenoˆmeno de Runge
Exemplo 4.6 Deseja-se interpolar a func¸a˜o f(x) = cos(x) no intervalo [1, 2]. Qual deve ser o
nu´mero de pontos utilizados nessa interpolac¸a˜o para que, utilizando interpolac¸a˜o linear, o erro
seja inferior a 10−6?
Exerc´ıcio 4.2 Construa o polinoˆmio de Newton para os pontos da tabela abaixo
x -1 0 2
f(x) 4 1 -1
40
Exerc´ıcio 4.3 Construa o polinoˆmio de Lagrange para a tabela do exemplo 4.2:
Exerc´ıcio 4.4 Construa o polinoˆmio de Lagrange e o polinoˆmio de Newton para a tabela
x -1 0 2 3
f(x) 4 1 -1 -2
Exerc´ıcio 4.5 Encontre uma aproximac¸a˜o para x = 0.8 utilizando o polinoˆmio interpolador
de Lagrange de grau ma´ximo para os pontos da tabela abaixo e calcule o erro cometido na
interpolac¸a˜o.
x 0 0.5 1.0
f(x) 1.3 2.5 0.9
Exerc´ıcio 4.6 Considere a tabela abaixo e determine:
x 2 3 4 5 6 7
f(x) 0.13 0.19 0.27 0.38 0.51 0.67
a) construa o polinoˆmio interpolador de grau adequado;
b) calcule f(4.5);
c) estime o erro cometido;
Exerc´ıcio 4.7 Dada a func¸a˜o tabelada e determine:
x 0 1 1.5 2.5 3.0
f(x) 1.0 0.5 0.4 0.286 0.25
a) a interpolac¸a˜o linear para todos os pontos;
b) a interpolac¸a˜o quadra´tica para todos os pontos;
Exerc´ıcio 4.8 Considere a tabela abaixo e determine:
x -2 -1 1
f(x) 0 1 -1
a) construa o polinoˆmio interpolador de Newton;
b) construa o polinoˆmio interpolador de Lagrange;
Exerc´ıcio 4.9 Considere a tabela abaixo e determine:
x -2 -1 1 2
f(x) 0 1 -1 0
a) construa o polinoˆmio interpolador de Newton;
41
b) construa o polinoˆmio interpolador de Lagrange;
Exerc´ıcio 4.10 Interpole 3 pontos no intervalo [1, 2] para a func¸a˜o cos(x) e construa o po-
linoˆmio de Newton de grau ma´ximo.
a) Aproxime x = 1.55 e x = 1.98;
b) decida se as aproximac¸o˜es calculadas acima sa˜o boas.
Cap´ıtulo 5
EQUAC¸O˜ES NA˜O-LINEARES
5.1 Zero de equac¸o˜es na˜o lineares
Estudaremos, nessa sec¸a˜o, esquemas nume´ricos para resoluc¸a˜o de equac¸o˜es da forma f(x) =
0. Na maioria dos casos essas equac¸o˜es na˜o possuem soluc¸a˜o alge´brica, no entanto esquemas
nume´ricos podem fornecer uma soluc¸a˜o aproximada satisfato´ria.
5.1.1 Isolamento de ra´ızes
Um nu´mero x que satisfaz a equac¸a˜o f(x) = 0 e´ chamado de raiz ou zero da func¸a˜o
f . O objetivo desse esquema nume´rico e´ encontrar um intervalo [a, b], de pequena amplitude
(b − a <<<<< 1), que contenha a raiz que estamos procurando. Para isso usaremos duas
estrate´gias:
• ana´lise gra´fica;
• tabelamento da func¸a˜o.
A ana´lise gra´fica e´ baseada na ideia de que a partir da equac¸a˜o f(x) = 0 podemos obter
uma equac¸a˜o equivalente g(x)− h(x) = 0, onde g, h sa˜o func¸o˜es mais simples e de fa´cil ana´lise
gra´fica. Esboc¸ando os gra´ficos de g e de h podemos determinar os pontos x onde as respectivas
curvas se interceptam (encontram), pois estes pontos sa˜o as ra´ızes ξ de f(x). Ou seja, se
g(ξ) = h(ξ) enta˜o f(ξ) = 0.
Exemplo 5.1 Utilizando ana´lise gra´fica determine um intervalo de amplitude 1 que contenha
a raiz da func¸a˜o f(x) = e−x − x.
Na pra´tica usa-se algum software matema´tico para esboc¸ar os gra´ficos. Quanto menor for
a amplitude do intervalo que conte´m a raiz, mais eficiente sera´ a fase do refinamento. Para
obtermos um intervalo de menor amplitude usaremos a estrate´gia do tabelamento que e´ baseada
no seguinte teorema.
42
43
Teorema 5.1 seja f(x) uma func¸a˜o cont´ınua em um intervalo [a, b]. Se
f(a).f(b) < 0
enta˜o existe pelo menos uma raiz ξ ∈ [a, b].
Observac¸a˜o 5.1 Se f ′ preserva sinal em [a, b] e f(a).f(b) < 0 enta˜o o intervalo conte´m uma
u´nica raiz. A derivada preservar sinal significa que a func¸a˜o f e´ crescente se f ′ > 0 ou decres-
cente se f ′ < 0.
Observac¸a˜o 5.2 Se f(a).f(b) > 0 nada se pode afirmar.
Exemplo 5.2 Da ana´lise gra´fica do exemplo 5.1 vimos que a func¸a˜o f(x) = e−x − x possui
uma u´nica raiz a qual se encontra no intervalo [0, 1]. Fac¸a o tabelamento para essa func¸a˜o no
intervalo citado com espac¸amento de 0.2. Determine um intervalo de amplitude 0.2 que possua
a raiz utilizando o teorema 1.
O tabelamento e´ uma estrate´gia que completa a ana´lise gra´fica. Somente com ele na˜o con-
seguimos determinar se existe outras ra´ızes no intervalo ou mesmo o intervalo em que devemos
tabelar o gra´fico da func¸a˜o.
Exerc´ıcio 5.1 Determine quantas ra´ızes possui a func¸a˜o f(x) = x3 − 9x + 3. Para cada raiz
determine um intervalo de amplitude 1. Para resoluc¸a˜o do exerc´ıcio determine as func¸o˜es g, h
adequadas.
Refinamento
Estudaremos 5 me´todos de refinamento do intervalo ao qual pertence a raiz da func¸a˜o f .
A forma como se efetua o refinamento e´ o que diferencia oa me´todos. Todos eles pertencem a
44
Figura 5.1: Gra´fico da func¸a˜o do exemplo 1
classe dos me´todos iterativos.
Um me´todo iterativo consiste de uma sequeˆncia de instruc¸o˜es que sa˜o executadas passo
a passo, algumas das quais sa˜o repetidas em ciclos. A execuc¸a˜o de um ciclo recebe o nome de
iterac¸a˜o. Esses me´todos fornecem uma aproximac¸a˜o para a soluc¸a˜o exata.
5.1.2 Crite´rio de Parada
Para evitar que o programa entre em ”looping”(repetic¸a˜o do mesmo ciclo indefinidamente)
usa-se um teste de parada do me´todo a cada iterac¸a˜o. O looping pode ocorrer devido a erros
no programa ou mesmo devido a inadequac¸a˜o do me´todo usado.
Esquemas nume´ricos va˜o gerar uma sequeˆncia de valores xk que converge para a raiz procu-
rada (ξ) apartir de uma aproximac¸a˜o inicial x0. Ou seja, xk → ξ quando k →∞. Dizemos
que x e´ uma aproximac¸a˜o da raiz ξ com precisa˜o � se:
1) |x− ξ| < �1 ou
2) |f(x)| < �2.
O ca´lculo de (1) na˜o e´ poss´ıvel, pois na˜o se conhece ξ. Na pra´tica o que se faz e´ usar uma
aproximac¸a˜o da forma:
I) |xn+1 − xn| ≤ �1 erro absoluto
45
ou
II) |xn+1−xn||xn+1| < �2 erro relativo
Outro procedimento utilizado para evitar o looping e´ o nu´mero ma´ximo de iterac¸o˜es.
5.1.3 Me´todo da Bissecc¸a˜o
Esse me´todo e´ baseado no teorema 5.1. Seja f(x) uma func¸a˜o cont´ınua no intervalo [a, b] tal
que f(a).f(b) < 0 e seja � > 0 um nu´mero real dado. A ideia do me´todo e´ reduzir a amplitude
do intervalo, ate´ atingir a precisa˜o desejada:
b− a < �
usando a divisa˜o sucessiva do intervalo ao meio.
Teorema 5.2 Seja f uma func¸a˜o cont´ınua em [a, b] e f(a).f(b) < 0. Enta˜o o me´todo da
bissecc¸a˜o gera uma sequeˆncia (xk) que converge para a raiz ξ quando k →∞.
O teorema 5.2 garante a convergeˆncia do me´todo, pore´m se a amplitude do intervalo inicial
for grande (b−a) >>> � e se a precisa˜o requerida for pequena enta˜o o me´todo tera´ convergeˆncia
lenta.
Exemplo 5.3 Utilize o me´todo da bissecc¸a˜o para aproximar a raiz da func¸a˜o f(x) = x3−9x+3
no intervalo I = [0, 1], com precisa˜o de � = 7× 10−2.
Algoritmo 5.1 Algoritmo do me´todo da bissecc¸a˜o
1) Dados de entrada
[a, b]: intervalo inicial
�: precisa˜o
n: nu´mero ma´ximo de iterac¸o˜es
2) Lac¸o para calcular o me´todo da bissecc¸a˜o
Se o nu´mero de iterac¸a˜o for menor que n
Enquanto b0 − a0 < �
46
x = a0+b0
2
Calcule f(a0) e f(x)
Se f(x).f(a0) > 0
fac¸a a0 = x;
sena˜o
fac¸a b0 = x;
Calcule o erro: (b0 − a0)
5.1.4 Me´todo da Falsa-Posic¸a˜o (Regula-Falsi)
Seja f(x) uma func¸a˜o cont´ınua no intervalo [a, b] tal que f(a).f(b) < 0. O me´todo da
falsa-posic¸a˜o considera para x a me´dia atirme´tica ponderada entre a e b, com pesos |f(b)| e
|f(a)| respectivamente, dada por
x =
a |f(b)|+ b |f(a)|
|f(b)|+ |f(a)|
como f(a) e f(b) possuem sinais opostostemos que
x =
af(b)− bf(a)
f(b)− f(a)
supondo que f(a) < 0.
Exemplo 5.4 Utilize o me´todo da falsa-posic¸a˜o para aproximar a raiz da func¸a˜o f(x) = x3 −
9x+ 3 no intervalo I = [0, 1], com precisa˜o de 10−1. Fac¸a, no ma´ximo, 5 iterac¸o˜es.
Exerc´ıcio 5.2 Utilize o me´todo da falsa-posic¸a˜o para aproximar a raiz da func¸a˜o f(x) = e−x−x
no intervalo I = [0, 1] com precisa˜o de 10−1.
Exerc´ıcio 5.3 Utilize o me´todo da falsa-posic¸a˜o para aproximar a raiz da func¸a˜o f(x) =
x log(x)-1 no intervalo I = [2, 3] com precisa˜o de 10−2.
5.1.5 Me´todo de Monte Carlo
Seja f(x) uma func¸a˜o cuja raiz se encontra no intervalo [a, b] tal que f(a).f(b) < 0. O
me´todo de Monte Carlo consiste em gerar aleatoriamente valores no intervalo [a, b], para os
quais a func¸a˜o deve ser avaliada. Seleciona-se um novo intervalo, de menor amplitude, ate´ que
a precisa˜o requerida seja obtida.
47
O me´todo de Monte Carlo sempre funciona e e´ de fa´cil implementac¸a˜o no entanto e´ lento
e requer a avaliac¸a˜o da func¸a˜o va´rias vezes. Sua extensa˜o a´ problemas multivaria´veis e´ complexa.
Exemplo 5.5 Utilize o me´todo de Monte Carlo para aproximar a raiz positiva da func¸a˜o
f(x) =
√
x− 5e−x no intervalo [1, 2], com erro inferior a 10−2.
Os me´todos da bissecc¸a˜o, regula-falsi e o de Monte Carlo sa˜o me´todos intervalares, de
convergeˆncia lenta.
5.1.6 Me´todo Iterativo Linear (MIL)
Seja f(x) uma func¸a˜o cont´ınua em [a, b], onde existe uma raiz da equac¸a˜o f(x) = 0. A
estrate´gia desse me´todo e´ reescrever a func¸a˜o f da forma
f(x) = x− ϕ(x).
Se x = ϕ(x) enta˜o f(x) = 0. Ou seja, encontrar as ra´ızes da func¸a˜o f(x) e´ o mesmo que
encontrar os pontos fixos da func¸a˜o ϕ(x).
Atrave´s da equac¸a˜o do ponto fixo montamos o processo iterativo. Dado x0 uma aproximac¸a˜o
inicial o processo iterativo do MIL e´ dado por
xn+1 = ϕ(xn) n = 0, 1, 2, · · · (5.1)
A func¸a˜o ϕ e´ chamada func¸a˜o de iterac¸a˜o e esta na˜o e´ determinada de forma u´nica. Surge
enta˜o uma pergunta: o MIL converge para qualquer func¸a˜o de iterac¸a˜o ϕ ? A resposta e´ dada
no teorema abaixo.
Teorema 5.3 Seja ξ uma raiz da func¸a˜o f isolada no intervalo [a, b]. Se ϕ(x) e´ uma func¸a˜o
de iterac¸a˜o da func¸a˜o f que satisfaz:
(i) ϕ(x) e ϕ′(x) sa˜o func¸o˜es cont´ınuas em [a, b];
(ii) |ϕ′(x)| ≤M < 1 , ∀x ∈ [a, b];
(iii) x0 ∈ [a, b].
enta˜o a sequeˆncia xk gerada pelo MIL atrave´s do processo iterativo xn+1 = ϕ(xn) converge para
a raiz ξ.
Como crite´rio de parada para o me´todo pode-se usar o erro absoluto ou o erro relativo,
descritos anteriormente.
48
Exemplo 5.6 Do exemplo 5.1 temos que a func¸a˜o f(x) = e−x−x possui uma raiz no intervalo
[0.5, 0.75]. Encontre a func¸a˜o de iterac¸a˜o ϕ(x) do MIL que obedec¸a as condic¸o˜es do teorema
5.3. Aplique o MIL com precisa˜o de 10−2. Utilize o erro absoluto.
Exerc´ıcio 5.4 Dada a func¸a˜o f(x) = x2 + x− 6 verifique que:
a) a sequeˆncia xk diverge da raiz x = 2 para a func¸a˜o de iterac¸a˜o ϕ(x) = 6− x2. Por queˆ?
b) a sequeˆncia xk converge para a raiz x = 2 usando a func¸a˜o de iterac¸a˜o ϕ(x) =
√
6− x.
Observac¸a˜o 5.3 1) Esse me´todo tambe´m e´ conhecido como me´todo do ponto fixo ou
me´todo da substituic¸a˜o sucessiva.
2) Esse me´todo possui convergeˆncia mais ra´pida que os me´todo intervalares e usa uma quan-
tidade menor de operac¸o˜es, no entanto possui a dificuldade de encontrar a func¸a˜o de
iterac¸a˜o.
Algoritmo 5.2 Algoritmo do MIL
1) Dados de entrada
x0: aproximac¸a˜o inicial
�: precisa˜o
n: nu´mero ma´ximo de iterac¸o˜es
2) Lac¸o para calcular o MIL
Enquanto |x1 − x0| < � ou k < n
x1 = ϕ(x0)
x0 = x1
k = k + 1
5.1.7 Me´todo de Newton-Raphson (MNR)
No me´todo anterior e´ poss´ıvel mostrar que quanto menor for |ϕ′(x)| mais ra´pida sera´ a
convergeˆncia do me´todo (Ruggiero, pg 66). O me´todo de Newton-Raphson e´ baseado no MIL e
determinado de forma que na˜o tenhamos o trabalho de procurar quem sera´ a func¸a˜o de iterac¸a˜o.
O me´todo de Newton-Raphson possui convergeˆncia mais ra´pida do que o MIL. A func¸a˜o de
iterac¸a˜o ϕ do me´todo de Newton-Raphson e´ dada por
ϕ(x) = x− f(x)
f ′(x)
.
49
Com essa func¸a˜o montamos o processo iterativo conhecido como me´todo de Newton-
Raphson
xn+1 = xn − f(xn)
f ′(xn)
n = 0, 1, 2, · · · (5.2)
Exemplo 5.7 Considere a func¸a˜o f(x) = e−x−x que possui uma raiz no intervalo [0.5, 0.75] e
aplique o me´todo de Newton-Raphson para x0 = 0.625 e � = 0.001. Considere o erro absoluto.
Teorema 5.4 Sejam f, f ′, f ′′ func¸o˜es cont´ınuas num intervalo [a, b] onde existe uma raiz ξ.
Supondo que f ′(x) 6= 0 para todo x ∈ [a, b] enta˜o existe um intervalo [a, b] ⊂ [a, b] contendo a
raiz ξ, tal que se x0 ∈ [a, b]a sequeˆncia xn gerada pelo processo iterativo
xn+1 = xn − f(xn)
f ′(xn)
converge para a raiz ξ.
Algoritmo 5.3 Algoritmo do me´todo de Newton
1) Dados de entrada
x0: aproximac¸a˜o inicial
�: precisa˜o
n: nu´mero ma´ximo de iterac¸o˜es
2) Lac¸o para calcular o Me´todo de Newton- Raphson
Enquanto |x1 − x0| < � ou k < n
x1 = x0 − f(x0)f ′(x0)
x0 = x1
k = k + 1
5.1.8 Ordem de Convergeˆncia
Vimos anteriormente que o me´todo de Newton-Raphson possui convergeˆncia mais ra´pida
do que o me´todo iterativo linear. A ”medida” que permite comparar a convergeˆncia entre os
me´todos e´ o que chamamos de ordem de convergeˆncia.
Definic¸a˜o 5.1 Seja xk uma sequeˆncia que converge para um nu´mero ξ e seja ek = xk − ξ o
erro na iterac¸a˜o k. Se
lim
k→∞
|ek+1|
|ek|p = c,
50
com p ≥ 1 e c > 0, dizemos que o me´todo converge com ordem p.
Considerando a sequeˆncia xk convergente temos que ek → 0 quando k → ∞, portanto
quanto maior for p mais pro´ximo estara´ de zero o valor de |ek|p, o que implica a convergeˆncia
mais ra´pida do me´todo.
Exerc´ıcio 5.5 Mostre que o me´todo iterativo linear possui convergeˆncia de ordem p = 1. Ou
seja, o MIL possui convergeˆncia linear.
Exerc´ıcio 5.6 Mostre que o me´todo de Newton-Raphson possui convergeˆncia de ordem p = 2.
Ou seja, o me´todo de Newton-Raphson possui convergeˆncia quadra´tica.
O me´todo de Newton-Raphson possui convergeˆncia mais ra´pida, quando comparado aos
outros me´todos vistos (da bissecc¸a˜o, da falsa-posic¸a˜o, de Monte Carlo e o MIL) no entanto
necessita da avaliac¸a˜o da func¸a˜o e de sua derivada em cada ponto xn. Para func¸o˜es complica-
das esse fato diminui a velocidade da convergeˆncia, ale´m de que para algumas func¸o˜es existe a
dificuldade adicional de obter a expressa˜o anal´ıtica para suas derivadas f ′.
Uma alternativa para contornar esse problema e´ substituir a derivada f ′(xn) pelo quociente
das diferenc¸as:
f ′(xn) ∼= f(xn)− f(xn−1)
xn − xn−1
onde xn, xn−1 sa˜o duas das aproximac¸o˜es sucessivas para a raiz ξ. Nesse caso a func¸a˜o de
iterac¸a˜o e´ dada por:
ϕ(xn) =
xn−1f(xn)− xnf(xn−1)
f(xn)− f(xn−1) .
Observa-se que, para iniciar o me´todo sa˜o necessa´rias duas aproximac¸o˜es xn e xn−1. Esse
me´todo e´ conhecido como me´todo da secante e pode divergir se f(xn) ≈ f(xn−1).
Exemplo 5.8 Considere a func¸a˜o f(x) = e−x − x que possui uma raiz no intervalo [0.5, 0.75]
e aplique o me´todo da secante para x0 = 0.6, x1 = 0.7 e � = 0.001. Considere o erro absoluto.
5.1.9 Multiplicidade das soluc¸o˜es
Definic¸a˜o 5.2 Uma soluc¸a˜o p de f(x) = 0 e´ um zero de multiplicidade m de f se, para x 6= p
f(x) = (x− p)mq(x) onde limx→p q(x) 6= 0.
Exemplo 5.9 A func¸a˜o f(x) = x3 + 2x2 possui uma raiz (p = 0) de multiplicidade 2. Ou seja,
f(x) = x2(x+ 2) ou ainda f(x) = (x− 0)2(x+ 2) assim limx→p q(x) = limx→0(x+ 2) = 2 6= 0.
Teorema 5.5 A func¸a˜o f ∈ C1[a, b] possui um zero simples em p no intervalo (a, b) se e
somente se f(p) = 0 e f ′(p) 6= 0.
51
Teorema 5.6 A func¸a˜o f ∈ Cn[a, b] possui um zero de multiplicidade m,em p, no intervalo
(a, b) se e somente se 0 = f(p) = f ′(p) = f ′′(p) = . . . = f (m−1) e fm(p) 6= 0.
A multiplicidade de soluc¸o˜es pode reduzir a ordem de convergeˆncia de um me´todo nume´rico.
Se p for um zero de f de multiplicidade m e f(x) = (x− p)mq(x) enta˜o o me´todo nume´rico
pode ser aplicado a func¸a˜o:
g(x) = x− f(x)− f
′(x)
(f ′(x))2 − f(x)f ′′(x) .
Se a func¸a˜o g satisfazer as condic¸o˜es necessa´rias o me´todo tera´ a convergeˆncia garantida
independente da multiplicidade da raiz. Na pra´tica esse me´todo pode causar erros graves de
arredondamento.
5.1.10 Acelerando a convergeˆncia
Na pra´tica e´ raro ter a convergeˆncia quadra´tica, enta˜o exite uma te´cnica denominada me´todo
∆2 de Aitken, que pode ser utilizada para acelerar uma sequeˆncia de convergeˆncia linear.
Seja xn uma sequeˆncia linearmente convergente para p, o me´todo ∆
2 de Aitken consiste em
definir uma nova sequeˆncia x̂n de forma que a convergeˆncia seja acelerada
x̂n = xn − (x
n+1 − xn)2
xn+2 − 2xn+1 + xn . (5.3)
Essa te´cnica pode ser aplicada a qualquer me´todo.
5.2 Sistemas de Equac¸o˜es na˜o Lineares
Considere o problema de determinar as ra´ızes de n equac¸o˜es na˜o lineares simultaˆneas, da
forma:

f1(x1, x2, . . . , xn) = 0
f2(x1, x2, . . . , xn) = 0
...
fn(x1, x2, . . . , xn) = 0
(5.4)
onde fi,para i = 1, 2, . . . , n e´ uma func¸a˜o real de n varia´veis reais. Geometricamente, as ra´ızes
desse sistema sa˜o os pontos (x∗1, x
∗
2, . . . , x
∗
n) onde as curvas (f1, f2, . . . , fn) se encontram.
52
Os me´todos nume´ricos para determinar a soluc¸a˜o dos sistemas na˜o lineares, em sua maioria,
sa˜o extenso˜es dos me´todos iterativos para resoluc¸a˜o de uma u´nica equac¸a˜o na˜o linear.
Usando a notac¸a˜o
X =

x1
x2
x3
...
xn

e F (X) =

f1
f2
f3
...
fn

.
onde cada fi(X) e´ uma func¸a˜o na˜o linear em X, fi : Rn → R para i = 1, 2, . . . , n. Enta˜o F (X)
e´ uma func¸a˜o na˜o linear em X, F : Rn → R.
Suponhamos que F esteja definida num conjunto aberto D ⊂ Rn e com derivadas cont´ınuas
nesse conjunto. Suponhamos ainda que existe pelo menos um X∗ ∈ D tal que F (X∗) = 0.
O vetor de derivadas parciais da func¸a˜o fi(x1, x2, . . . , xn) e´ o vetor gradiente de fi(x)
∇fi(X) =
(
∂fi
∂x1
,
∂fi
∂x2
, . . . ,
∂fi
∂xn
)
, (5.5)
onde i = 1, 2, . . . , n. A matriz das derivadas parciais e´ a matriz Jacobiana
J(X) =

∇f1(X)
∇f2(X)
...
∇fn(X)
 =

∂f1
∂x1
∂f1
∂x2
· · · ∂f1
∂xn
∂f2
∂x1
∂f2
∂x2
· · · ∂f2
∂xn
...
...
. . .
...
∂fn
∂x1
∂fn
∂x2
· · · ∂fn
∂xn
 .
Os me´todos, a serem vistos, para resoluc¸a˜o de sistemas na˜o lineares pertencem a classe dos
me´todos iterativos. Dado uma aproximac¸a˜o inicial X0 gera-se uma sequeˆncia de vetores X(k)
tal que limk→∞X(k) = X∗, onde X∗ e´ a soluc¸a˜o exata do sistema F (X) = 0.
5.2.1 Crite´rios de Parada
a) Nu´mero ma´ximo de iterac¸o˜es;
b)
∥∥F (Xk)∥∥ < �
c)
∥∥Xk+1 −Xk∥∥ < �
53
5.2.2 Me´todo de Newton
Semelhante ao caso de uma equac¸a˜o na˜o linear o me´todo de Newton consiste em transformar
um sistema na˜o linear em um modelo linear. O me´todo de Newton e´ o me´todo mais utilizado
para resolver sistema de equac¸o˜es na˜o-lineares.
Descric¸a˜o do me´todo
Dada a aproximac¸a˜o Xk o passo Sk do me´todo de Newton e´ obtido resolvendo o sistema
linear
J(Xk) ∗ (Sk) = −F (Xk) (5.6)
e a nova aproximac¸a˜o de X∗ e´ calculada por:
Xk+1 = Xk + Sk (5.7)
O me´todo de Newton e´ computacionalmente caro, pois necessita da avaliac¸a˜o e da inversa˜o
da matriz Jacobiana J(Xk) a cada passo, para obter a resoluc¸a˜o do sistma linear J(Xk)∗(Sk) =
−F (Xk).
Exemplo 5.10 Utilize o me´todo de Newton para resolver o sistema
F (X) =
(
x1 + x2 − 3
x21 + x
2
2 − 9
)
para X0 = [1 5]
t e � = 9× 10−2. Considere o erro absoluto na norma do ma´ximo.
Observac¸a˜o 5.4 Dada uma matriz de ordem 2
A =
(
a b
c d
)
.
sua inversa e´ dada por
A−1 =
1
detA
(
d −b
−c a
)
.
5.2.3 Me´todos Quase-Newton
A motivac¸a˜o principal dos me´todos de Quase-Newton e´ gerar uma sequeˆncia X(k), com
boas propriedades de convergeˆncia, sem avaliar a matriz Jacobiana a cada iterac¸a˜o, como ocorre
no me´todo de Newton.
Os me´todos quase-Newton substituem a matriz jacobiana por uma matriz de aproximac¸a˜o
que e´ atualizada a cada iterac¸a˜o. A desvantagem desses me´todos e´ que a convergeˆncia quadra´tica
54
do me´todo de Newton e´ perdida e em seu lugar obte´m-se uma convergeˆncia linear (superli-
near).
Os me´todos quase-Newton na˜o sa˜o autocorretivos, ou seja, na˜o corrigem os erros de arre-
dondamento como ocorre no me´todo de Newton.
Existem va´rios me´todos quase-Newton e a diferenc¸a entre eles e´ a forma de aproximar a
matriz jacobiana. Veremos dois destes me´todos:
• o me´todo de Newton modificado;
• o me´todo de Broyden.
Dado X(0) a aproximac¸a˜o inicial para a soluc¸a˜o X∗ de F (X) = 0. Calculamos X(1) da
mesma forma que no me´todo de Newton original e apartir da segunda iterac¸a˜o e´ que realmente
temos a diferenc¸a nos me´todos quase-Newton.
Me´todo de Newton Modificado
Esse me´todo consiste em tomar, a cada iterac¸a˜o k, a mesma matriz jacobiana calculada no
passo inicial. Assim dada a aproximac¸a˜o Xk o me´todo de Newton Modificado e´ calculado
por
Xk+1 = Xk + Sk
onde o passo Sk e´ atualizado por
Sk = (J(X0))−1[−F (Xk)] (5.8)
Exemplo 5.11 Utilize o me´todo de Newton Modificado para resolver o sistema
F (X) =
(
x1 + x2 − 3
x21 + x
2
2 − 9
)
para X0 = [1 5]
t e � = 2× 10−2. Considere o erro absoluto na norma do ma´ximo.
Observac¸a˜o 5.5 Caso na˜o se tenha definido as derivadas parciais, no ca´lculo da matriz Ja-
cobiana, as devivadas podem ser aproximadas por:
∂G
∂x1
(a, b) =
G(a+ h, b)−G(a, b)
h
(5.9)
∂G
∂x2
(a, b) =
G(a, b+ h)−G(a, b)
h
55
Me´todos de Broyden
Equac¸a˜o da secante Bk+1(Xk+1 −Xk) = F (Xk+1)− F (Xk) ou equivalentemente
Bk+1 =
F (Xk+1)− F (Xk)
(Xk+1 −Xk)
que e´ conhecida como equac¸a˜o da secante.
Os me´todos quase-Newton se diferem pelas diferentes aproximac¸o˜es, para a equac¸a˜o da
secante. O me´todo proposto por Broyden e´ dado por:
Xk+1 = Xk − (Bk)−1F (Xk) (5.10)
Bk = Bk−1 +
(
yk −Bk−1Sk) (Sk)t
(Sk)tSk
(5.11)
onde
yk = F (Xk)− F (Xk−1)
Sk = Xk −Xk−1
B0 = J(X0)
Exemplo 5.12 Resolva o exemplo 5.10 utilizando o me´todo de Broyden. Fac¸a no ma´ximo 3
iterac¸o˜es.
Exemplo 5.13 Fac¸a 3 iterac¸o˜es do me´todo de Newton modificado para o sistema do exemplo
5.11 utilizando aproximac¸o˜es para as derivadas parciais da matriz Jacobiana. Para o ca´lculo
do erro considere
∥∥F (Xk)∥∥ < �. Considere h = 0.25.
Algoritmo 5.4 Algoritmo do me´todo de Newton
Objetivo: aproximar a raiz do sistema na˜o linear F (X) = 0 dado uma aproximac¸a˜o inicial
X0.
Dados de entrada
n ; nu´mero de equac¸o˜es e inco´gnitas
X = (x1, x2, . . . , xn)
t ; aproximac¸a˜o inicial
N ; nu´mero ma´ximo de iterac¸o˜es
� ; precisa˜o.
56
Sa´ıda
Soluc¸a˜o aproximada para X∗ ou mensagem de que o nu´mero ma´ximo de iterac¸o˜es foi atin-
gido.
Passo 1: k=1
Passo 2: Enquanto k ≤ N execute os passos de 3 a 7.
Passo 3: Calcule F (X) e J(X) para 1 ≤ i, j ≤ n
Passo 4: Resolva o sistema linear de ordem n
J(X)S = −F (X)
Passo 5: X = X + S
Passo 6: Se ‖S‖ < � enta˜o a sa´ıda e´ X.
Pare
Passo 7: Sena˜o k = k + 1.
Passo 8: Sa´ıda (O nu´mero ma´ximo de iterac¸o˜es foi atingido’).
Pare
Cap´ıtulo 6
INTEGRAC¸A˜O NUME´RICA
O objetivo desse cap´ıtulo e´ estudar esquemas nume´ricos que aproximem a integral definida,
de uma func¸a˜o f(x), num intervalo [a, b]. A integrac¸a˜o