Métodos Numéricos 2013

Prévia do material em texto

�PAGE �
�PAGE �17�
Métodos Numéricos
Prof. Heinz Arthur Niederheitmann Jr
�
I. Introdução
Cálculo Numérico é a obtenção da solução de um problema pela aplicação de método numérico; a solução do problema será caracterizada, então, por um conjunto de números, exatos ou aproximados.
	Método Numérico é um algoritmo composto por um número finito de operações envolvendo apenas números (operações aritméticas elementares, cálculo de funções, consulta a uma tabela de valores, consulta a um gráfico, arbitramento de um valor, etc.).
Modelagem é a fase de obtenção do modelo matemático que descreve o comportamento do sistema físico.
Resolução é a fase de obtenção da solução através da aplicação de métodos numéricos (este é o objetivo de estudo do Cálculo Numérico).
1 Hipóteses usuais da Matemática
No estudo da matemática, para não complicar a análise, admite-se que :
a)	os números que intervem nas operações são exatos, isto é, tem infinitos algarismos.
 Ex. : 2 = 2,0000...
 1/3 = 0,3333...
 SYMBOL 112 \f "Symbol" = 3,14159255...
 SYMBOL 214 \f "Symbol"2 = 1,41421356...
b)	todos os cálculos são feitos usando os infinitos algarismos de todos os números, o que é possível em operações com inteiros, mas nem sempre quando envolve números reais.
 Ex. : 2,0000....
 +2,0000....
 -----------
 4,0000....
 2 . SYMBOL 112 \f "Symbol" = 6,283185???? 
c)	existem muitos processos infinitos ( séries, limites, integrais, ... ).
 Ex. :
 (0,72)3 (0,72)5 (0,72)7
 sen 0,72 = 0,72 - ------- + ------- - ------- + ...
 3! 5! 7!
2. Métodos Numéricos
a)	Teóricos : 
SYMBOL 183 \f "Symbol" \s 10 \h	usam exclusivamente operações aritméticas;
SYMBOL 183 \f "Symbol" \s 10 \h	processos infinitos são aproximados por processos finitos, ocorrendo erro de truncamento.
 (0,72)3 (0,72)5 (0,72)7
 sen 0,72 = 0,72 - ------- + ------- - ------- = 0,659385
 3! 5! 7!
 
 
 (0,72)9 (0,72)11 (0,72)13
 erro = ------- - ------- + ------- < 0,4 . 10-6
 9! 11! 13!
�
b)Práticos :
	 
SYMBOL 183 \f "Symbol" \s 10 \h	os números que intervem nos processos são representados com um número finito de algarismos, ocorrendo erro de arredondamento.
Ex.: 623,4783 623,4783
 +502,9731 x 502,9731
 --------- ----------------
 1.126,4514 315.592,81333373 
 1.126,451 315.592,8 
c)Definição :
Disciplina que busca :
SYMBOL 183 \f "Symbol" \s 10 \h	desenvolver algoritmos numéricos;
SYMBOL 183 \f "Symbol" \s 10 \h	analisar tais algoritmos; e 
SYMBOL 183 \f "Symbol" \s 10 \h	implementá-los em computadores.
considerando que :
SYMBOL 183 \f "Symbol" \s 10 \h	os números são aproximados, devido a erros; e
SYMBOL 183 \f "Symbol" \s 10 \h	a aritmética utilizada é finita.
procurando soluções corretas :
SYMBOL 183 \f "Symbol" \s 10 \h	dentro da precisão desejada; e
SYMBOL 183 \f "Symbol" \s 10 \h	utilizando algoritmos que demandem um tempo razoável.
Ex. : Resolver o sistema de equações lineares abaixo :
a11 x1 + a12 x2 + ... + a1n xn = b1
a21 x1 + a22 x2 + ... + a2n xn = b2
 .
 .
 .
an1 x1 + an2 x2 + ... + ann xn = bn
pelo método de Cramer :
 xi = SYMBOL 68 \f "Symbol"i / SYMBOL 68 \f "Symbol"
onde :
 SYMBOL 68 \f "Symbol" = determinante da matriz de coeficientes do sistema 
 SYMBOL 68 \f "Symbol"i = determinante da matriz resultante da substituição da coluna i da matriz de coeficientes do sistema pelo vetor b.
Para um sistema de ordem n, será preciso calcular n + 1 determinantes de ordem n e então fazer n divisões. 
Para cada determinante será preciso fazer n! produtos com n - 1 multiplicações cada, os quais devem ser somados, portanto serão :
 n! . ( n - 1 ) + ( n! - 1 ) SYMBOL 64 \f "Symbol" n! . n operações
e para determinar a solução :
 
 ( n + 1 ) . n! . n + n operações
Se o sistema for de ordem :
 3 serão 75 operações
 10 serão 399.168.010 operações 
Se a solução for feita com auxílio de uma calculadora não programável, cada operação leva cerca de 10 segundos, ou 8640 operações por dia, portanto para um sistema de ordem 10 uma pessoa levaria cerca de 127 anos para a solução completa. 
Se a solução for feita com auxílio de um computador, com velocidade de 10 MIPS ( milhões de instruções por segundo ) a solução levaria cerca de 36 segundos.
Para um sistema de ordem :
 20 serão aproximadamente 1021 operações
o que levaria cerca de 3,2 milhões de anos para a solução com o auxílio do computador.
3. Processo de resolução de problemas
Consiste nas seguintes etapas :
a)Identificaçåo da situaçåo
SYMBOL 183 \f "Symbol" \s 10 \h estudo do sistema atual;
SYMBOL 183 \f "Symbol" \s 10 \h levantamento dos problemas e suas causas;
SYMBOL 183 \f "Symbol" \s 10 \h definição da abrangência; e
SYMBOL 183 \f "Symbol" \s 10 \h esboço de soluções alternativas.
b)análise do sistema
Também chamado de projeto lógico do sistema, consiste na definição do "O QUE QUEREMOS" e é composta das seguintes atividades :
SYMBOL 183 \f "Symbol" \s 10 \h definição dos objetivos ( saídas );
SYMBOL 183 \f "Symbol" \s 10 \h descrição das entradas; e 
SYMBOL 183 \f "Symbol" \s 10 \h descrição dos processos.
c)Projeto do sistema
Também chamado de projeto físico do sistema, consiste na definição do "COMO FAZER" e é composta das seguintes atividades :
SYMBOL 183 \f "Symbol" \s 10 \h	definição das saídas;
SYMBOL 183 \f "Symbol" \s 10 \h	descrição das entradas;
SYMBOL 183 \f "Symbol" \s 10 \h	descrição dos processos :
SYMBOL 183 \f "Symbol" \s 10 \h	construção do modelo matemático;
SYMBOL 183 \f "Symbol" \s 10 \h escolha do método numérico adequado; e 
SYMBOL 183 \f "Symbol" \s 10 \h	descrição do fluxo de trabalho.
d)Implementação do sistema
Nesta etapa o que foi projetado é executado.
É feita a implementação computacional do método numérico.
e)ImplAntação do sistema
O sistema é colocado em operação.
É feita a análise dos resultados obtidos.
f)Operação do sistema
g)Documentação do sistema
Esta etapa é realizada ao mesmo tempo que as demais e consiste na documentação dos seguintes elementos :
SYMBOL 183 \f "Symbol" \s 10 \h	- saídas
SYMBOL 183 \f "Symbol" \s 10 \h	- entradas;
SYMBOL 183 \f "Symbol" \s 10 \h	- processos;
SYMBOL 183 \f "Symbol" \s 10 \h	- descrição dos processos.
g)Manutenção do sistema
Esta etapa é executada durante a operação do sistema para a sua correção, melhoria ou expansão.
�
Erros possíveis da solução de problemas
Durante a resolução de problema os erros são principalmente devido :
a)no levantamento de dados:
SYMBOL 183 \f "Symbol" \s 10 \h	a falta de acuracidade nas medidas;
SYMBOL 183 \f "Symbol" \s 10 \h	ao número finito de algarismos para a representação das grandezas;
SYMBOL 183 \f "Symbol" \s 10 \h	a utilização de dados estatísticos; e
SYMBOL 183 \f "Symbol" \s 10 \h	a enganos.
b)na contrução do modelo matemático :
SYMBOL 183 \f "Symbol" \s 10 \h	utilização de hipóteses simplificadoras para tornar mais simples e viável o estudo.
 Ex.: Cálculo da queda de tensão em um circuito elétrico :
 Lei de Ohm : v = R . i
 v = R . i + r . i3
c)na implementação computacional :
SYMBOL 183 \f "Symbol" \s 10 \h	confecção de programas de forma errada.�
II. Representação de Números Reais
1. Representação de números 
Precisão :
SYMBOL 183 \f "Symbol" \s 10 \h	está relacionada com o número de algarismos com que um número é conhecido.
Exatidão :
SYMBOL 183 \f "Symbol" \s 10 \h	está relacionada com quão bem o número representa uma grandeza.
Ex. : SYMBOL 112 \f "Symbol" = 3,1416 é mais preciso e mais exato que 3,14
 4,2735000... = 4,277452 é mais preciso que 4,27,
 mas menos exatoNúmero aproximado :
SYMBOL 183 \f "Symbol" \s 10 \h	é quando ele representa um valor que não é exatamente o seu.
Algarismo significativo :
SYMBOL 183 \f "Symbol" \s 10 \h	são todos os algarismos de um número, a menos dos zeros quando estiverem substituindo algarismos desconhecidos ou fixando a posição da vírgula.
a)Sistemas numéricos não-posicionais
O valor do símbolo independe de sua posição no número.
Ex.: Sistema Romano : LXI, LXXVIII
b)Sistemas númericos posicionais
SYMBOL 183 \f "Symbol" \s 10 \h o valor de cada símbolo depende de sua posição no número;
SYMBOL 183 \f "Symbol" \s 10 \h	o número pode ser escrito na forma polinomial :
N = an SYMBOL 98 \f "Symbol"n + an-1 SYMBOL 98 \f "Symbol"n-1 + ... + a2 SYMBOL 98 \f "Symbol"2 + a1 SYMBOL 98 \f "Symbol"1 + a0 
onde : ai é o algarismo da posição i;
 
 SYMBOL 98 \f "Symbol" é o valor da base.
Ex.: Sistema decimal - base 10
 2347 = 2 . 103 + 3 . 102 + 4 . 10 + 7
 423 = 4 . 102 + 2 . 10 + 3
 Sistema binário - base 2
 11011 = 1 . 24 + 1 . 23 + 0 . 22 + 1 . 2 + 1 = 27
Conversão de números inteiros :
bn = an
bn-1 = an-1 + SYMBOL 98 \f "Symbol" . bn
bn-2 = an-2 + SYMBOL 98 \f "Symbol" . bn-1
.
.
.
b1 = a1 + SYMBOL 98 \f "Symbol" . b2
b0 = a0 + SYMBOL 98 \f "Symbol" . b1
onde :
 ai é o algarismo da posição na base original;
 
 b0 é o número convertido;
 SYMBOL 98 \f "Symbol" é o valor da base original.
Ex. 1.1 : ( 10111 )2 = ( ? )10
 b4 = a4 = 1
 b3 = a3 + SYMBOL 98 \f "Symbol" . b4 = 0 + 2 . 1 = 2
 b2 = a2 + SYMBOL 98 \f "Symbol" . b3 = 1 + 2 . 2 = 5
 b1 = a1 + SYMBOL 98 \f "Symbol" . b2 = 1 + 2 . 5 = 11
 b0 = a0 + SYMBOL 98 \f "Symbol" . b1 = 1 + 2 . 11 = 23
 ( 10111 )2 = ( 23 )10
Ex. 1.2 : ( 347 )10 = ( ? )2
 b2 = a2 = 3 = 11
 b1 = a1 + SYMBOL 98 \f "Symbol" . b2 = (100) + (1010) . (11) = (100010)
 b0 = a0 + SYMBOL 98 \f "Symbol" . b1 = (111) + (1010) . (100010)
 
 = (101011011)
 ( 347 )10 = ( 101011011 )2
Conversão de números fracionários :
 
São separadas as partes inteira e fracionária do número :
 R = I + F
a parte inteira é convertida da maneira já citada, e
a parte fracionária pode ser representada como :
F = d1 SYMBOL 98 \f "Symbol"-1 + d2 SYMBOL 98 \f "Symbol"-2 + ... + dk SYMBOL 98 \f "Symbol"-k 
e os algarismos (ci) da parte fracionária do número convertido podem ser obtidos da seguinte forma :
c0 = F
b1 = ( SYMBOL 98 \f "Symbol" . c0 )i
c1 = ( SYMBOL 98 \f "Symbol" . c0 )f
b2 = ( SYMBOL 98 \f "Symbol" . c1 )i
c2 = ( SYMBOL 98 \f "Symbol" . c1 )f
.
.
.
bn = ( SYMBOL 98 \f "Symbol" . cn-1 )i
cn = ( SYMBOL 98 \f "Symbol" . cn-1 )f
onde : 
 
bi é o algarismo fracionário da posição na base convertida;
c0 é a parte fracionária do número a ser convertido;
Ex. 1.3 : ( 0,6875 )10 = ( ? )2
c0 = I = 0,6875
b1 = ( SYMBOL 98 \f "Symbol" . c0 )i = (2 . 0,6875)i = (1,3750)i = 1
c1 = ( SYMBOL 98 \f "Symbol" . c0 )f = (2 . 0,6875)f = (1,3750)f = 0,375
b2 = ( SYMBOL 98 \f "Symbol" . c1 )i = (2 . 0,375)i = (0,75)i = 0
c2 = ( SYMBOL 98 \f "Symbol" . c1 )f = (2 . 0,375)f = (0,75)f = 0,75
b3 = ( SYMBOL 98 \f "Symbol" . c2 )i = (2 . 0,75)i = (1,5)i = 1
c3 = ( SYMBOL 98 \f "Symbol" . c2 )f = (2 . 0,75)f = (1,5)f = 0,5
b4 = ( SYMBOL 98 \f "Symbol" . c3 )i = (2 . 0,5)i = (1,0)i = 1
c4 = ( SYMBOL 98 \f "Symbol" . c3 )f = (2 . 0,5)f = (1,0)f = 0
 ( 0,6875 )10 = ( 0,1011 )2
Ex. 1.4 : ( 0,1 )10 = ( ? )2
c0 = b0= 0,1
b1 = ( SYMBOL 98 \f "Symbol" . c0 )i = (2 . 0,1)i = (0,2)i = 0
c1 = ( SYMBOL 98 \f "Symbol" . c0 )f = (2 . 0,1)f = (0,2)f = 0,2
b2 = ( SYMBOL 98 \f "Symbol" . c1 )i = (2 . 0,2)i = (0,4)i = 0
c2 = ( SYMBOL 98 \f "Symbol" . c1 )f = (2 . 0,2)f = (0,4)f = 0,4
b3 = ( SYMBOL 98 \f "Symbol" . c2 )i = (2 . 0,4)i = (0,8)i = 0
c3 = ( SYMBOL 98 \f "Symbol" . c2 )f = (2 . 0,4)f = (0,8)f = 0,8
b4 = ( SYMBOL 98 \f "Symbol" . c3 )i = (2 . 0,8)i = (1,6)i = 1
c4 = ( SYMBOL 98 \f "Symbol" . c3 )f = (2 . 0,8)f = (1,6)f = 0,6
b5= ( SYMBOL 98 \f "Symbol" . c4)i = (2 . 0,6)i = (1,2)i = 1
c5= ( SYMBOL 98 \f "Symbol" . c4)f = (2 . 0,8)f = (1,2)f = 0,2
 ( 0,1 )2 = ( 0,000110011 ... )2
2. Aritmética de ponto flutuante
Um número qualquer na base SYMBOL 98 \f "Symbol", em aritmética de ponto flutuante de t algarismos tem a forma :
 R = SYMBOL 177 \f "Symbol" (.d1d2...dt)SYMBOL 98 \f "Symbol" . SYMBOL 98 \f "Symbol"e 
onde : 
 
.d1d2...dt é uma fração na base SYMBOL 98 \f "Symbol", também chamada de mantissa; e
0 SYMBOL 163 \f "Symbol" dj SYMBOL 163 \f "Symbol" SYMBOL 98 \f "Symbol" - 1 SYMBOL 34 \f "Symbol" j = 1,...,t 
e é o expoente, que pode variar no intervalo ( m,M ), sendo normalmente m = -M.
Um número está normalizado em aritmética de ponto flutuante, se d1 SYMBOL 185 \f "Symbol" 0.
Se e > M resulta em "overflow"; e
se e < m resulta em "underflow".
Um número ( R ) com mais algarismos que o permitido ou com representação não finita na base numérica, será aproximado ( R ) por arredondamento ou por truncamneto. Pode-se representá-lo na forma :
 R = Fx . SYMBOL 98 \f "Symbol"e + Gx . SYMBOL 98 \f "Symbol"e-t
onde, se a base é 10 :
 0,1 SYMBOL 163 \f "Symbol" Fx < 1
 
 0 SYMBOL 163 \f "Symbol" Gx < 1
Truncamento :
SYMBOL 183 \f "Symbol" \s 10 \h	é a eliminação dos algarismos de um número, a partir de uma determinada posição, isto é, a parcela Gx . SYMBOL 98 \f "Symbol"e-t é desprezada, e :
 R = Fx . SYMBOL 98 \f "Symbol"e
Arredondamento :
SYMBOL 183 \f "Symbol" \s 10 \h	é a modificação do último algarismo de Fx para levar em consideração a parcela Gx . SYMBOL 98 \f "Symbol"e-t :
se SYMBOL 189 \f "Symbol"Gx SYMBOL 189 \f "Symbol" < 0,5 SYMBOL 174 \f "Symbol" R = Fx . SYMBOL 98 \f "Symbol"e 
se SYMBOL 189 \f "Symbol"Gx SYMBOL 189 \f "Symbol" SYMBOL 179 \f "Symbol" 0,5 SYMBOL 174 \f "Symbol" R = Fx . SYMBOL 98 \f "Symbol"e + SYMBOL 98 \f "Symbol"e-t 
�
III. Erros
Erros na Fase de Modelagem
Ao se tentar representar um fenômeno do mundo físico por meio de um método matemático, raramente se tem uma descrição correta deste fenômeno. Normalmente, são necessárias várias simplificações do mundo físico para que se tenha um modelo.
Exemplo: Estudo do movimento de um corpo sujeito a uma aceleração constante.
	Tem-se a seguinte equação:
		d = do + vo * t + 1/2 *  * t2
onde:
	 d	: distância percorrida
	 do	: distância inicial
	 vo	: velocidade inicial
	 t	: tempo
	 	: aceleração
Determinar a altura de um edifício com uma bolinha de metal e um cronômetro: 3s
		d = 0 + 0 * 3 + 1/2 * 9.8 * 32 = 44.1m
Este resultado é confiável?
Fatores não considerados:
resistência do ar
velocidade do vento, etc.
Precisão dos dados de entrada:
Se o tempo fosse 3,5s  d = 60.025m
Variação de 16,7% no cronômetro  36% na altura.
Erros na Fase de Resolução
	Para a resolução de modelos matemáticos muitas vezes torna-se necessária a utilização de instrumentos de cálculo que necessitam, para o seu funcionamento, que sejam feitas certas aproximações. Tais aproximações podem gerar erros, tais como: conversão de bases, erros de arredondamento e erros de truncamento.
Erro absoluto ( EAx ) :
SYMBOL 183 \f "Symbol" \s 10 \h	é a diferença entre o valor exato ( x ) e o valor aproximado ( x ).
 EAx = x - x
como x normalmente não é conhecido, utiliza-se uma cota superior do erro absoluto (CSEA).
Algarismo significativo correto :
SYMBOL 183 \f "Symbol" \s 10 \h	um algarismo significativo está correto se o arredondamento do número até a sua posição resultar em um erro absoluto menor do que meia unidade na sua posição.
Ex. : 2/3 = 0,66667 todos são corretos
 = 0,6669984253 só os 3 primeiros são corretos 
Erro relativo ( ERx ) :
SYMBOL 183 \f "Symbol" \s 10 \h	é a razão entre o erro absoluto ( EAx ) e o valor aproximado ( x ).
 EAx
 ERx = ----
 x
Teorema 1 :
SYMBOL 183 \f "Symbol"\s 10 \h	Se um número tiver n algarismos significativos corretos, seu erro relativo será menor que 5 . 10-n nos casos de interesse prático.
Teorema 2 :
SYMBOL 183 \f "Symbol" \s 10 \h	Se o erro relativo de um número aproximado for menor que 0,5 . 10-n, o número terá pelo menos n algarismos significativos corretos.
Ex.: 34,152 com 5 algarismos corretos 
 cota superior do erro relativo = 5 . 10-5
 31,54682 com erro relativo menor que 10-5
 tem 4 algarismos significativos corretos
Erro no truncamento :
 EAx = x - x = Gx . SYMBOL 98 \f "Symbol"e-t < SYMBOL 98 \f "Symbol"e-t 
 EAx SYMBOL 189 \f "Symbol"Gx . SYMBOL 98 \f "Symbol"e-t SYMBOL 189 \f "Symbol" 10e-t
 ERx = ---- = ----------- < --------- = 10-t+1
 x SYMBOL 189 \f "Symbol"FxSYMBOL 189 \f "Symbol". SYMBOL 98 \f "Symbol"e 0,1 . 10e 
Erro no arredondamento :
se SYMBOL 189 \f "Symbol"Gx SYMBOL 189 \f "Symbol" < 0,5 :
 EAx = SYMBOL 189 \f "Symbol"x - xSYMBOL 189 \f "Symbol" = Gx . SYMBOL 98 \f "Symbol"e-t < 0,5 . 10e-t 
 EAx SYMBOL 189 \f "Symbol"Gx . SYMBOL 98 \f "Symbol"e-t SYMBOL 189 \f "Symbol" 0,5 . 10e-t
 ERx = ---- = ----------- < ----------- = 0,5 . 10-t+1
 x SYMBOL 189 \f "Symbol"FxSYMBOL 189 \f "Symbol". SYMBOL 98 \f "Symbol"e 0,1 . 10e 
se SYMBOL 189 \f "Symbol"Gx SYMBOL 189 \f "Symbol" SYMBOL 179 \f "Symbol" 0,5 :
 EAx = SYMBOL 189 \f "Symbol"x - xSYMBOL 189 \f "Symbol" 
 
 = SYMBOL 189 \f "Symbol"(Fx . SYMBOL 98 \f "Symbol"e + Gx . SYMBOL 98 \f "Symbol"e-t) - (Fx . SYMBOL 98 \f "Symbol"e + SYMBOL 98 \f "Symbol"e-t)SYMBOL 189 \f "Symbol" 
 = SYMBOL 189 \f "Symbol"Gx . SYMBOL 98 \f "Symbol"e-t - SYMBOL 98 \f "Symbol"e-t)SYMBOL 189 \f "Symbol" 
 = SYMBOL 189 \f "Symbol"Gx - 1SYMBOL 189 \f "Symbol" . SYMBOL 98 \f "Symbol"e-t SYMBOL 163 \f "Symbol" 0,5 . 10e-t 
 EAx 0,5 . 10e-t 0,5 . 10e-t 
 ERx = ---- = --------------- < ------------
 x SYMBOL 189 \f "Symbol"Fx . SYMBOL 98 \f "Symbol"e + SYMBOL 98 \f "Symbol"e-tSYMBOL 189 \f "Symbol" SYMBOL 189 \f "Symbol"Fx SYMBOL 189 \f "Symbol" . 10e
 
 0,5 . 10e-t 
 ERx < ----------- = 0,5 . 10-t+1 
 0,1 . 10e
 
Portanto, em qualquer caso :
 SYMBOL 189 \f "Symbol"EAxSYMBOL 189 \f "Symbol" SYMBOL 163 \f "Symbol" 0,5 . 10e-t 
 SYMBOL 189 \f "Symbol"ERxSYMBOL 189 \f "Symbol" SYMBOL 163 \f "Symbol" 0,5 . 10-t+1 
Análise dos erros nas operações de ponto flutuante :
Considerando aritmética de ponto flutuante de 4 algarismos na base 10 e com acumulador de precisão dupla. 
Ex. 3.1 : x = 0,937 . 104 
 y = 0,1272 . 102
 z = x + y 
 x + y SYMBOL 174 \f "Symbol" 0,937000 . 104 
 + 0,001272 . 104
 --------------
 0,938272 . 104 
z = 0,9383 . 104 por arredondamento
 = 0,9382 . 104 por truncamento
Ex. 3.2 : x = 0,937 . 104 
 y = 0,1272 . 102
 w = x . y 
 x . y = ( 0,937 . 104 ) x ( 0,1272 . 102 )
 = ( 0,937 . 0,1272 ) . 104+2 
 = 0,1191864 . 106
w = 0,1192 . 106 por arredondamento
 = 0,1191 . 106 por truncamento
Erro no resultado de operação :
 SYMBOL 189 \f "Symbol"ERopSYMBOL 189 \f "Symbol" < 10-t+1 no truncamento
 SYMBOL 189 \f "Symbol"ERopSYMBOL 189 \f "Symbol" < 0,5 . 10-t+1 no arredondamento 
Erro nas operações :
a)adição :
 z = x + y
 x = x + EAx
 y = y + EAy
 x + y = x + EAx + y + EAy
 = ( x + y ) + ( EAx + EAy )
 EAx+y = EAx + EAy
 EAx+y EAx x EAy y
 ERx+y = ------ = ------- . ----- + ---- . ------
 x + y x x + y y x + y 
 x y
 ERx+y = ERx . ----- + ERy . ------
 x + y x + y
É aconselhável somar números começando com os de menor valor absoluto, para conservar ao máximo a precisão das parcelas. 
b)subtração :
 z = x - y
 x = x + EAx
 y = y + EAy
 x - y = x + EAx – ( y + Eay )
 = ( x - y ) + ( EAx - EAy )
 EAx-y = EAx - EAy
 x y
 ERx-y = ERx . ----- - ERy . ------
 x - y x - y
É aconselhável, quando possível, evitar as subtrações.
Ex.: Solução de equações do 2. grau usando a formula de Bascara.
 a . x2 + b . x + c = 0
 - b SYMBOL 177 \f "Symbol" ( b2 - 4 . a . c )½
 x1,x2 = -------------------------
 2 . a
se a = 1 
 b = 80
 c = 1, e utilizarmos 3 algarismos significativos 
 x1 = -0,800 . 102
 x2 = 0,000 
esta mesma equação pode ser resolvida da seguinte forma :
 a . x2 + b . x + c = a . ( x - x1 ). ( x - x2 ) 
 
 = a .[x2 - (x1 - x2).x + x1 . x2]
 
 = a . x2 - a.(x1 - x2).x + a.x1.x2
portanto :
 a = a
 b = - a . (x1 - x2) 
 c = a . x1 . x2
e :
 
 x2 = c / ( a . x1 )
 b + ( b2 - 4 . a . c )½
 x1 = - sinal ( b ) . -----------------------
 2 . a
para os mesmos valores de a, b e c, agora resulta :
 x1 = -0,800 . 102
 x2 = 1,0 / [ 1,0 . ( -0,800 . 102 ) ]
 x2 = -0,125 . 10-1
c)multiplicação :
 z = x . y
 x = x + EAx
 y = y + EAy
 x . y = ( x + EAx ) . ( y + EAy )
 = x . y + x . EAy + y . EAx + EAx . EAy 
 EAx.y = x . EAy + y . EAx 
 x .EAy + y . EAx EAx EAy
 ERx.y = ----------------- = --- + ---
 x . y x y
 ERx.y = ERx + ERy 
d)divisão :
 z = x / y
 x = x + EAx
 y = y + EAy
 x / y = ( x + EAx ) / ( y + EAy )
 x x . EAx 1
 --- = ------- . --------- 
 y y EAy 
 1 + ---
 y 
 1 EAy EAy EAy 
 --- = 1 - --- + ( --- )2 - ( --- )3 + ....
 EAy y y y
 EAy EAy 
 1 + --- SYMBOL 64 \f "Symbol" 1 - --- 
 y y 
 
 x x . EAx EAy 
 --- SYMBOL 64 \f "Symbol" ------- . ( 1 - ---- )
 y y y 
 
 x x EAx x . EAy EAx . EAy 
 --- SYMBOL 64 \f "Symbol" - + --- - -------- - ---------
 y y y y2 y2
 x x EAx x . EAy 
 --- SYMBOL 64 \f "Symbol" - + --- - -------- 
 y y y y2 
 EAx x . EAy 
 EAx/y SYMBOL 64 \f "Symbol" --- - ------- 
 y y2 
 EAx x . EAy 
 EAx/y SYMBOL 64 \f "Symbol" --- - ------- 
 y y2 
 y . EAx - x . EAy 
 EAx/y SYMBOL 64 \f "Symbol" ----------------- 
 y2 
 y . EAx - x . EAy y 
 ERx/y SYMBOL 64 \f "Symbol" ----------------- . --- 
 y2 x
 EAx EAy 
 ERx/y SYMBOL 64 \f "Symbol" --- - ---- 
 x y
�
IV. Zeros de funções ( ou raízes de equações ) polinomiais e transcedentes
1. Introdução
No caso particular de equações do segundo grau, onde se aplica a fórmula de Bascara, e de algumas equações do terceiro e quarto grau, e de certos casos particulares de equações transcedentes a solução destas equações pode ser obtida através de métodos diretos.
Mas nas demais equações, a solução deve ser feita utilizando métodos numéricos, quase sempre iterativos.
Um número z é um zero da função f ( x ) ou uma raiz da equação f ( x ) = 0, se f ( z ) = 0.
As raízes de equações podem ser reais ou complexas.
As raízes reais de uma equação f ( x ) = 0, em um gráficao são representadas pelas abcissas dos pontos onde a curva intercepta o eixo x.
 
2. Processo de solução
A soluçãopor meio de métodos iterativos normalmente consiste nos seguintes passos :
SYMBOL 183 \f "Symbol" \s 10 \h localização de uma raiz;
SYMBOL 183 \f "Symbol" \s 10 \h refinamento da raiz.
O processo é feito da seguinte forma :
SYMBOL 183 \f "Symbol" \s 10 \h localizar uma raiz;
SYMBOL 183 \f "Symbol" \s 10 \h inicializar o número de iterações com 1
SYMBOL 183 \f "Symbol" \s 10 \h Enquanto a aproximação não for adequada e
 o número de iterações não ultrapassar o máximo
SYMBOL 183 \f "Symbol" \s 10 \h refinar a aproximação
SYMBOL 183 \f "Symbol" \s 10 \h somar 1 ao número de iterações
3. Localização de raízes		
A localização das raizes é feita através :
SYMBOL 183 \f "Symbol" \s 10 \h	do conhecimento do problema;
SYMBOL 183 \f "Symbol" \s 10 \h	da análise teórica;
SYMBOL 183 \f "Symbol" \s 10 \h	do esboço de gráfico da função; e
SYMBOL 183 \f "Symbol" \s 10 \h	da confecção de tabela com os valores da função.
A existência de raízes no intervalo (a,b), é garantida pelo teorema :
Seja f ( x ) uma função contínua no intervalo (a,b).
Se f ( a ) . f ( b ) < 0, então existe pelo menos uma raiz no intervalo (a,b).
E se existir f'( x ) e não mudar de sinal no intervalo (a,b), então haverá somente uma raiz no intervalo (a,b).
Mas se f ( a ) . f ( b ) > 0, então haverá nenhuma raiz no intervalo (a,b), quando f'( x ) existir e não mudar de sinal no intervalo (a,b), e em caso contrário um número par de raízes. 
4. Refinamento
O refinamento pode ser feito por vários métodos :
SYMBOL 183 \f "Symbol" \s 10 \h	de bissecção;
SYMBOL 183 \f "Symbol" \s 10 \h	das cordas ou da posição falsa;
SYMBOL 183 \f "Symbol" \s 10 \h	da tangente ou de Newton; e
SYMBOL 183 \f "Symbol" \s 10 \h	outros.
Em todos estes métodos, um dos pontos importantes é a definição se a aproximação é adequada ou não, isto é, quando terminar o processo iterativo. Para isto tem-se :
a) Limite na diferença entre aproximações sucessivas da raiz
 | x - x | < erro máximo permitido
 
Neste caso, como x não é conhecido, mas sabe-se que x está no intervalo (a,b), pode-se reduzir o intervalo a tal ponto que | ( a - b ) | < erro máximo permitido. 
b) Limite no valor da função
 | f ( x ) | < erro máximo permitido 
Em alguns casos as duas condições podem ser satisfeitas ao mesmo temo e em outras não, conforme pode ser visto nos exemplos abaixo.
�
5. Método das cordas
Consiste em determinar a nova aproximação como a intercessão do eixo x com a reta que passa pelos pontos ( a, f (a) ) e ( b, f(b) ).
Portanto, está nova aproximação pode ser calculada da seguinte maneira :
 a . f ( b ) - b . f ( a )
x = ------------------------- 
 f ( b ) - f ( a )
Após determinada a aproximação x, deve-se verificar qual intervalo contém a raiz :
 ( a, x ) ou ( x, b )
É um método seguro, mas não muito rápido.
O critério para término do processo iterativo normalmente é o limite do valor da função, pois nem sempre o intervalo (a,b) será suficientemente pequeno.
Se a função tem a segunda derivada e ela mantém o sinal no intervalo ( a, b ), então temos as seguintes situações :
a) f ( a ) > 0 
 f"( a ) > 0 : neste caso x sempre assumirá como ponto b
b) f ( a ) > 0 
 f"( a ) < 0 : neste caso x sempre assumirá como ponto a
c) f ( a ) < 0 
 f"( a ) > 0 : neste caso x sempre assumirá como ponto a
d) f ( a ) < 0 
 f"( a ) < 0 : neste caso x sempre assumirá como ponto b
6. Método da Iteração Linear
	Seja f(x) uma função contínua no intervalo [a, b] e seja ( uma raiz desta função, sendo ( ( (a, b), tal que f(() = 0.
	Por um artifício algébrico, pode-se transformar f(x) = 0 em duas funções que lhe sejam equivalentes.
f(x) = 0  
onde g(x) é chamada de função de iteração.
Interpretação geométrica do método da iteração linear
	Sendo x0 a primeira aproximação da raiz (, calcula-se g(x0). Faz-se então, x1 = g(x0), x2 = g(x1), x3 = g(x2) e assim sucessivamente.
Então, por indução, temos:
Algoritmo:
		para n = 1, 2, 3, ...
Critério de Parada:
| xn ( xn-1 | ( erro
Melhor extremo:
Empiricamente, sabe-se que o método tem sucesso quando | g'(x) | < 1 em todo intervalo.
O extremo mais rápido para iniciar o método é aquele para o qual o módulo da primeira derivada é menor.
Se | g'(a) | < | g'(b) | então x0 = a, senão x0 = b.
Casos de convergência
Seja f(x) = x3 ( 5x + 3. Possíveis g(x):
g(x) = 
				g(x) = 
g(x) = 
				g(x) = 
Como podemos ter várias funções g(x), vamos estabelecer algumas condições para que os resultados sejam satisfatórios.
Vamos observar graficamente o problema e verificar que há funções g(x) que não são indicadas para a escolha.
		Convergência monotônica
		0 < g’(x) < 1
		Convergência oscilante
	 (1 < g’(x) < 0
	
		Divergência monotônica 
		g’(x) > 1
		Divergência oscilante
		g’(x) < (1
	
Convergência no método da iteração linear
 EQ Considerações finais
A maior dificuldade neste método é encontrar uma função de iteração que satisfaça à condição de convergência;
Teste de | g'(x) | < 1 pode levar a um engano se x0 não estiver suficientemente próximo da raiz. A velocidade de convergência dependerá de | g'(() |: quanto menor este valor maior será a convergência;
Devemos observar que o teste de erro ( | xn ( xn-1 | ( erro ) não implica necessariamente que | xn ( ( | ( erro, conforme vemos na figura abaixo:
Exemplos
Exemplo 1: Dada a função f(x) = x2 + 3x ( 40, obter sua raiz contida no intervalo [4.5, 5.5], pelo MIL, com um erro ( 10-4.
Algoritmo: 
Escolha da função de iteração:
y = x
y = 
		y' = 
			divergência oscilante
y = 
		y' = 
			convergência oscilante
y = 
		y' = 
		convergência oscilante
Melhor extremo (valor inicial):
y = 
			y' =
		y'(4.5) = (0.2914	y'(5.5) = (0.3094	(	x0 = 4.5
Valor do erro:
		erro ( 10-4
Iterações:
		x1 = 5.14782
		x2 = 4.95546
		x3 = 5.01335
		x4 = 4.99599
		x5 = 5.00120
		x6 = 4.99964
		x7 = 5.00011
		x8 = 4.99997
		x9 = 5.00000		| x9 – x8 | = 0.00003 < erro
Resposta:
		A raiz desejada é ( = 5.00000
Exemplo 2: Dada a função f(x) = x2 + 3x ( cos(x) ( 2.45, obter sua raiz contida no intervalo [0.5, 1], pelo MIL, com um erro ( 10-2.
Resposta: A raiz desejada é ( = 0.8161
Método das tangentes ( de Newton )
Consiste em determinar a nova aproximação como a intercessão do eixo x com a tangente a curva no ponto da atual aproximação.
Portanto, está nova aproximação pode ser calculada da seguinte maneira :
 f ( xi )
xi+1 = xi - -------- 
 f' ( xi )
É um método rápido, mas que pode divergir.
Para a aplicação deste método, é preciso verificar as condições de convergência :
a)f" ( x ) SYMBOL 185 \f "Symbol" 0, isto é, o sinal da segunda derivada não deve mudar de sinal no intervalo (a,b).
 	 f" ( a ) . f" ( b ) > 0 NÃO
c)o extremo do intervalo (a,b) a ser utilizado como estimativa inicial deve ser aquele onde :
 f ( x ) . f" ( x ) > 0 
 então :
 
 f ( a ) . f" ( a ) > 0 SYMBOL 222 \f "Symbol" x0 = a
 f ( b ) . f" ( b ) > 0 SYMBOL 222 \f "Symbol" x0 = b
Seja f(x) uma função contínua no intervalo [a, b] e seja ( uma raiz desta função, sendo ( ( (a, b), tal que f(() = 0 e f’(x) ( 0.
Interpretação geométrica do método de Newton
Tomemos x0 = b. Então temos:
Se 
, então x1 é a raiz desejada, senão deve-se calcular x2, que é obtido com base no mesmo raciocínio anterior: 
.
Se 
, então x2 é a raiz desejada, senão deve-se calcular x3, ..., xn, até que 
. Então, por indução, temos:
Algoritmo:
,		para n = 1, 2, 3, ...
Critério de Parada:
Restrição:
É necessário conhecer um intervalo que contenha o valor desejado (.
Melhor extremo:
Para decidir qual o melhor extremo do intervalo (a, b) a iniciar o método, basta verificar qual dos extremos possui função e segunda derivada com mesmo sinal:
		f(xi). f''(xi) > 0		Para i = {extremos do intervalo}EQ Considerações finais
Requer o conhecimento da forma analítica de f '(x), mas sua convergência é extraordinária.
Exemplos
Exemplo 1: Calcular a raiz positiva da equação f(x) = 2x ( sen(x) ( 4 = 0, com erro ( 10-3, usando o método de NR.
Algoritmo: 
f(x) = 2x ( sen(x) ( 4
f´(x) = 2 ( cos(x)
f''(x) = sen(x)
Escolha do intervalo:
		f(2) = (0.9093		f(3) = 1.8589
		f(2). f(3) < 0		( ( [2, 3]
Melhor extremo (valor inicial):
		f(2) = (0.9093		f(3) = 1.8589
		f''(2) = 0.9093		f''(3) = 0.1411
		( x0 = 3
Valor do erro:
		erro ( 10-3
Iterações:
		| x1 ( x0 | = | 2.3783 ( 3 | = 0.6217 > erro
		| x2 ( x1 | = | 2.3543 ( 2.3783 | = 0.0240 > erro
		| x3 ( x2 | = | 2.3542 ( 2.3543 | = 0.0001 < erro
Resposta:
A raiz desejada é ( = 2.3542
Exercício 1: Obter a raiz cúbica de 5, usando o método NR sendo o erro ( 10-3.
f(x) = x3 ( 5
f'(x) = 3x2
f''(x) = 6x
Resposta: 	A raiz desejada é ( = 1.7100
Exercício 2: Calcular a raiz negativa de f(x) = x3 ( 5x2 + x + 3, com erro ( 10-4.
f(x) = x3 ( 5x2 + x + 3
f´(x) = 3x2 ( 10x + 1
f''(x) = 6x ( 10
Resposta: A raiz desejada é ( = (0.64575
Exercício 3: Seja a função f(x) = sen(x) ( tg(x). Deseja-se saber uma das raízes desta função, sabendo-se que está contida no intervalo (3, 4). Todos os cálculos devem ser realizados com 4 casas decimais com arredondamento e erro não superior a 0.001.
f(x) = sen(x) ( tg(x)
f'(x) = cos(x) ( sec2(x)
f''(x) = (sen(x) ( 2sec2(x) tg(x)
Resposta: A raiz desejada é ( = 3.1416
Condições de Newton-Raphson-Fourier
	Segundo Newton, para haver a convergência à uma raiz em seu método, bastaria que o intervalo (a, b) em análise fosse suficientemente pequeno. Contudo, Raphson e Fourier concluíram que um intervalo pequeno é aquele que contém uma e somente uma raiz. Com isso, algumas condições foram estabelecidas para que tal exigência fosse válida:
1() Se f(a). f(b) > 0, então existe um número par de raízes reais (contando suas multiplicidades) ou não existe raízes reais no intervalo (a, b) (Teorema de Bolzano);
2() Se f(a).f(b) < 0, então existe um número ímpar de raízes reais (contando suas multiplicidades) no intervalo (a, b) (Teorema de Bolzano);
3() Se f'(a). f'(b) > 0, então o comportamento da função neste intervalo poderá ser apenas crescente ou apenas decrescente, e nunca os dois se alternando;
4() Se f'(a). f'(b) < 0, então a função terá o comportamento de ora crescer ora decrescer;
5() Se f"(a). f"(b) > 0, então a concavidade não muda no intervalo em análise;
6() Se f"(a). f"(b) < 0, então a concavidade muda no intervalo em análise.
	Portanto, haverá convergência à uma raiz no intervalo (a, b) se e somente se:
		f(a). f(b) < 0,		f'(a). f'(b) > 0		e	 f"(a). f"(b) > 0.
Exemplo 2: Seja a função f(x) = x2 ( 9.5x + 8.5, obter a raiz contida no intervalo [8, 9]. Os cálculos devem ser realizados com 4 decimais com arredondamento e erro não superior a 0,001.
Algoritmo : 
f(x) = x2 ( 9.5x + 8.5
f’(x) = 2x ( 9.5
f”(x) = 2
Escolha do intervalo:
f(8) = (3.5;		f(9) = 4
f(8). f(9) < 0	 	 ( ( [8, 9]
Melhor extremo (valor inicial):
		f(8) = (3,5	f(9) = 4		f(8). f(9) < 0
		f'(8) = 6.5	f'(9) = 8.5	f((8). f((9) > 0
		f"(8) = 2	f"(9) = 2	f((8). f((9) > 0
( x0 = 9
Valor do erro:
		erro ( 10-3
Iterações:
| x1 ( x0 | = | 8.5294 ( 9 | = 0.4706 > erro
| x2 ( x1 | = | 8.5001 ( 8.5294 | = 0.0293 > erro
| x3 ( x2 | = | 8.5000 ( 8.5001 | = 0.0001 < erro
f) Resposta:
A raiz desejada é ( = 8.5000
Exercício 4: Calcular a raiz da equação f(x) = x3 ( x + 1 = 0, contida no intervalo [(2, (1], com um erro ( 10-3.
	f(x) = x3 ( x + 1
		f’(x) = 3x2 ( 1
	f”(x) = 6x
Resposta: 	A raiz desejada é ( = (1.3247
Método das Secantes
	Uma grande desvantagem do método de Newton é a necessidade de se obter a derivada f’(x) e calcular o seu valor numérico a cada iteração.
	Para contornar este problema podemos substituir o cálculo da primeira derivada f’(xn) pelo quociente das diferenças, usando assim, um modelo linear baseado nos dois valores calculados mais recentemente:
onde xn e xn-1 são duas aproximações para a raiz.
	Substituindo o valor aproximado da derivada acima, a função de iteração fica:
	
	
, para n = 1, 2, 3, ...
	Para iniciar o método necessitamos de duas aproximações (x0 e x1) para a raiz.
Interpretação geométrica do método da secante
	Neste método partimos das duas aproximações iniciais x0 e x1 e determinamos a reta que passa pelos pontos (x0, f (x0)) e (x1, f (x1)). A intersecção desta reta com o eixo x fornece o ponto x2. Em seguida é calculado uma nova aproximação para a raiz a partir dos pontos (x1, f(x1)) e (x2, f (x2)). O processo se repete até que seja satisfeito o critério de parada.
	Observe que neste método não necessitamos da característica que é fundamental no método da falsa posição que exige que f(xn). f(xn-1) < 0. É importante salientar também que a raiz não necessita estar entre as duas aproximações iniciais (x0 e x1).
	A convergência deste método é mais rápido que o método da bisseção e o da falsa posição, contudo, pode ser mais lento que o método de Newton-Raphson.
	Algoritmo: 
, 	para n = 1, 2, 3, ...
	Critério de parada:
| xn+1 ( xn | ( erro
Exemplos
Exemplo 1: Calcular a raiz da função f(x) = x2 + x ( 6, sendo x0 = 1.5, x1 = 1.7 e o erro ( 10-2.
Algoritmo : 
Valor inicial:
	x0 = 1.5		x1 = 1.7
Valor do erro:
		erro ( 10-2
Iterações:
		| x2 ( x1 | = | 2.0357 ( 1.7 | = 0.3357 > erro
		| x3 ( x2 | = | 1.9977 ( 2.0357 | = 0.038 > erro
		| x4 ( x3 | = | 2.0000 ( 1.9977 | = 0.0023 < erro
Resposta:
		( = 2.0000 é a raiz procurada.
Exercício 1: Calcular a raiz da função f(x) = 3x ( cos(x), sendo x0 = 0, x1 = 0.5 e o erro ( 10-4. Efetue os cálculos com 5 casas decimais com arredondamento.
Resposta: 	( = 0.31675 é a raiz procurada.
Exercício 2: Calcular a raiz da função f(x) = x3 ( 4, sendo x0 = 1, x1 = 2 e o erro ( 0,05.
Resposta: 	( = 1,5914 é a raiz procurada.
7. Deflação de polinômios
Consiste em, após determinar um zero ( xi ) de um polinômio, dividi-lo por ( x - xi ), para reduzir a ordem do polinômio, ficando mais fácil a determinação dos demais zeros.
Normalmente é utilizado o algoritmo de Briot-Rufini para a deflação de polinômio, que é a substituição do polinômio na forma : 
 pn (x) = an xn + an-1 xn-1 + ... + a2 x2 + a1 x + a0
pela forma :
 pn (x) = ((...(an x + an-1 ).x + ... + a2 ).x + a1 ).x + a0
Algoritmo de Briot-Rufini :
1.	Fazer uma tabela com 3 linhas e com tantas colunas quanto a ordem do polinômio + 2;
2.	na primeira linha são colocados em ordem decrescente os coeficientes do polinômio (an), um em cada coluna e a partir da segunda coluna. 
3.	na primeira coluna da segunda linha é colocada o zero do polinômio;
4.	na segunda coluna da terceira linha ( bn ) coloca-se o valor de an.
5.	multiplica-se o zero do polinômio pelo valor que se encontra na segunda coluna da terceira linha, e o resultado coloca-se na terceira coluna da segunda linha.
6.	soma-se o valor que se encontra na terceira coluna da primeira linha com o valor na terceira coluna na segunda linha, obtendo-se o valor na terceira coluna da terceira linha ( bn ).
7.	repetem-se os passos 5 e 6 para determinar os valores das segundas e terceiras linhas de cada coluna, até que se chegue a última coluna.
	
	an
	an-1
	an-2
	...
	a1
	a0
	x
	
	x.bn
	x.bn-1
	
	x.b2
	x.b1
	
	bn
	bn-1
	bn-2
	
	b1
	b0
											
O valor encontrado na última coluna da terceira linha ( b0 ) é o valor de pn (x) para o valor de x colocado na primeira coluna da segunda linha, que deverá ser zero se este valor for um zero do polinômio.
Portanto este algoritmo pode também ser usado para calcular pn (x). 
8. Teoremas úteis para a localização de zeros de polinômios
SYMBOL 183 \f "Symbol" \s 10 \h	Teorema 1 :
Seja um polinômio na forma :
 pn (x) = an xn + an-1 xn-1 + ... + a2 x2 + a1 x + a0
então pn (x) tem pelo menos um zero no interior do círculo centrado na origem e com raio igual aomenor valor entre
 
 e 
SYMBOL 183 \f "Symbol" \s 10 \h	Teorema 2
Seja um polinômio na forma :
 pn (x) = an xn + an-1 xn-1 + ... + a2 x2 + a1 x + a0
se 
 r SYMBOL 187 \f "Symbol" 1 + Máximo ( 
 ) onde 0 SYMBOL 163 \f "Symbol" k SYMBOL 163 \f "Symbol" n
então todos os zeros de pn (x) se localizam no interior do círculo centrado na origem e de raio igual a r.
�
III. Sistemas de Equações lineares e algébricas
1. Introdução
Uma função f (xj) costituída por um polinômio do primeiro grau em xj, é qualificada de linear em relação a xj e tem a forma :
 f (xj) = a1x1 + a2x2 + ... + anxn + b
Esta função linear será dita homogênea ou não homogênea, conforme b seja igual ou diferente de zero.
O conjunto formado por m equações lineares algébricas a n incógnitas é chamado de Sistema de Linear de Equações Algébricas, o qual tem a forma :
 a11x1 + a12x2 + ... + a1nxn = b1
 a21x1 + a22x2 + ... + a2nxn = b2
 .
 . 
 .
 am1x1 + am2x2 + ... + amnxn = bm
Ou na forma matricial :
 A . x = b
onde : aij são chamados de coeficientes das incógnitas;
 bi são chamados de termos independentes; e
 xj são chamados de incógnitas.
Se os termos independentes forem todos nulos o sistema é dito homogêneo, e se pelo menos um deles for diferente de zero o sistema é dito não homogêneo.
O sistema será dito linearmente dependente ou independente conforme suas equações sejam linearmente dependentes ou não.
 
A solução do sistema consiste no conjunto de valores xj que satisfaz simultaneamente as m equações.
�
Em relação a sua solução o sistema pode ser :
SYMBOL 183 \f "Symbol" \s 10 \h	Compatível e determinado :
 quando admite uma única solução;
SYMBOL 183 \f "Symbol" \s 10 \h	Compatível e indeterminado :
 quando admite infinitas soluções;
SYMBOL 183 \f "Symbol" \s 10 \h	Incompatível : quando não tem solução;
O sistema homogêneo é sempre compatível, pois admite pelo menos uma solução, chamada de trivial, onde xj = 0, para todo j.
O sistema será compatível e determinado se o determinante dos coeficientes for não-nulo.
Matriz Extendida ( M )
Chama-se a matriz formada pelos coeficientes das incógnitas ( xj) e pelos termos independentes.
M = 
�
Sistemas equivalentes 
Dois sistemas são equivalentes se e somente se toda solução de um é também solução do outro e, vice-versa.
Transformações Elementares
São transformações que podem ser efetuadas em sistemas de equações lineares com o objetivo de transformá-las em um outro sistema de equações lineares equivalente.
a) Troca de duas equações;
b) Multiplicação ou divisão dos elementos de uma equação por uma constante diferente de zero;
c) Substituição de uma equação pela sua soma com outra equação.
 
�
Sistemas mal condicionados
Os sistemas com determinante não-nulo são ditos definidos, possuindo solução única. 
Mas para a aplicação de métodos numéricos para a sua solução deve-se tomar outros cuidados, como mostra o exemplo abaixo.
 5 x1 + 8 x2 = 6,2
 4 x1 + 6 x2 = 4,8
Neste sistema os coeficientes são exatos, mas os termos independentes são conhecidos com uma casa decimal, podendo ser resultado de arredondamento.
A solução poderia ser obtida por substituição :
 
 x1 = -1,5 x2 + 1,2 
 - 7,5 x2 + 6 + 8 x2 = 6,2
portanto : x2 = 0,4
 x1 = 0,6
Porém, se os valores reais dos termos independentes fossem 6,15 e 4,85 respectivamente, a solução seria :
 x2 = 0,175
 x1 = 0,95
E, se os valores reais dos termos independentes fossem 6,25 e 4,75 respectivamente, a solução seria :
 x2 = 0,625
 x1 = 0,25
A causa deste problema na solução do sistema é o quase paralelismo das retas representativas das duas equações no plano x1 - x2. A solução seria reformular o problema que originou o sistema ou obter os números com maior precisão.
Os sistemas com o problema apresentado são chamados de mal condicionados e na prática não tem solução.
2. Métodos Clássicos		
1.1 Método de Cramer
Consiste em determinar o valor de cada incógnita através da operação :
xi = SYMBOL 68 \f "Symbol"i / SYMBOL 68 \f "Symbol"
onde :
 SYMBOL 68 \f "Symbol" = determinante da matriz de coeficientes do sistema 
 SYMBOL 68 \f "Symbol"i = determinante da matriz resultante da substituição da coluna i da matriz de coeficientes do sistema pelo vetor b.
Este método, conforme já exposto no capítulo I, somente é aplicável em sistemas de ordem baixa.
�
1.2 Método da inversa
Consiste em obter a solução do sistema a partir da pré-multiplicação do vetor independente pela inversa da matriz de coeficientes.
A . x = b
A-1 . A . x = A-1 . b
U . x = A-1 . b
x = A-1 . b
Este método normalmente não é utilizado devido ao processo complexo de determinação da inversa da matriz de coeficientes.
3. Métodos Diretos
3.1 Método da triangularização ( Gauss )
Consiste em transformar o sistema de equações :
 a11 .x1 + a12 .x2 + ... + a1,n-1 .xn-1 + a1n .xn = b1
 a21 .x1 + a22 .x2 + ... + a2,n-1 .xn-1 + a2n .xn = b2
 a31 .x1 + a32 .x2 + ... + a3,n-1 .xn-1 + a3n .xn = b3
 .
 . 
 .
 an-1,1.x1 + an-1,2.x2 + ... + an-1,n-1.xn-1 + an-1,n.xn = bn-1
 an1 .x1 + an2 .x2 + ... + an,n-1 .xn-1 + ann .xn = bn
de maneira que a matriz de coeficientes do sistema transforme-se em uma matriz triangular superior, ficando os sistema na forma :
 c11.x1 + c12.x2 + ... + c1,n-1 .xn-1 + c1n .xn = d1
 c22.x2 + ... + c2,n-1 .xn-1 + c2n .xn = d2
 ... + c3,n-1 .xn-1 + c3n .xn = d3
 .
 . 
 .
 cn-1,n-1.xn-1 + cn-1,n.xn = dn-1
 cnn .xn = dn
A solução do sistema passa então a ser feita da última para a primeira equação, determinando o valor de uma incógnita a cada equação.
Para se conseguir isto, desenvolve-se o processo em m passos, onde em cada passo é definido um pivô, e são eliminados todos os coeficientes de uma incógnita nas equações seguintes.
Portanto, a cada passo, são substituídas as equações seguintes ( i ) pela sua soma com o negativo da equação do pivô multiplicada pela relação entre o coeficiente da incógnita referente ao pivô ( aik ) na equação e o pivô ( akk ) :
 aik 
 k = ---- 
 akk
 
ficando os coeficientes da linha i :
 aik 
 aij = aij - --- . akj 
 akk
 
Exemplo :
 3 x1 + x2 = -2
 -2 x1 + 2 x3 = 1
 x1 + 3 x2 + 4 x3 = 0
1. passo : eliminação dos coeficientes de x1
 
SYMBOL 183 \f "Symbol" \s 10 \h	Multiplica-se a primeira equação por 2/3 e -1/3 e soma-se respectivamente às segunda e terceira equações, obtendo-se :
 3 x1 + x2 = -2
 2/3 x2 + 2 x3 = -1/3
 8/3 x2 + 4 x3 = 2/3
2. passo : eliminação dos coeficientes de x2
 
SYMBOL 183 \f "Symbol" \s 10 \h	Multiplica-se a segunda equação por -4 e soma-se à terceira equação, obtendo-se :
 3 x1 + x2 = -2
 2/3 x2 + 2 x3 = -1/3
 - 4 x3 = 2
A solução do sistema começa pela terceira equação :
 - 4 x3 = 2 SYMBOL 222 \f "Symbol" x3 = - 1/2
em seguida substitui-se x3 na segunda equação e :
 2/3 x2 + 2 . ( - 1/2 ) = -1/3 SYMBOL 222 \f "Symbol" x2 = 1 
em por último substitui-se x2 e x3 na primeira equação e :
 3 x1 + 1 = -2 SYMBOL 222 \f "Symbol" x1 = - 1 
3.2 Método da diagonalização ( Gauss-Jordan )
Consiste em transformar o sistema de equações :
 a11 .x1 + a12 .x2 + ... + a1,n-1 .xn-1 + a1n .xn = b1
 a21 .x1 + a22 .x2 + ... + a2,n-1 .xn-1 + a2n .xn = b2
 a31 .x1 + a32 .x2 + ... + a3,n-1 .xn-1 + a3n .xn = b3
 .
 . 
 .
 an-1,1.x1 + an-1,2.x2 + ... + an-1,n-1.xn-1 + an-1,n.xn = bn-1
 an1 .x1 + an2 .x2 + ... + an,n-1 .xn-1 + ann .xn = bn
de maneiraque a matriz de coeficientes do sistema transforme-se em uma matriz diagonal, ficando o sistema na forma :
 c11.x1 = d1
 c22.x2 = d2
 .
 . 
 .
 cn-1,n-1.xn-1 = dn-1
 cnn.xn = dn
A solução do sistema passa então a ser feita de forma trivial, determinando o valor de cada incógnita em cada equação.
Neste método, a cada passo, são substituídas as demais equações ( i ) pela sua soma com o negativo da equação do pivô multiplicada pela relação entre o coeficiente da incógnita referente ao pivô ( aik ) na equação e o pivô ( akk ) :
 aik 
 k = ---- 
 akk
 
�
ficando os coeficientes da linha i :
 aik 
 aij = aij - --- . akj 
 akk
 
Exemplo :
 3 x1 + x2 = -2
 -2 x1 + 2 x3 = 1
 x1 + 3 x2 + 4 x3 = 0
1. passo : eliminação dos coeficientes de x1
 
SYMBOL 183 \f "Symbol" \s 10 \h	Multiplica-se a primeira equação por 2/3 e -1/3 e soma-se respectivamente às segunda e terceira equações, obtendo-se :
 3 x1 + x2 = -2
 2/3 x2 + 2 x3 = -1/3
 8/3 x2 + 4 x3 = 2/3
2. passo : eliminação dos coeficientes de x2
 
SYMBOL 183 \f "Symbol" \s 10 \h	Multiplica-se a segunda equação por - 1/2 e -4 e soma-se respectivamnete às primeira e terceira equações, obtendo-se :
 3 x1 - 3 x3 = -2
 2/3 x2 + 2 x3 = -1/3
 - 4 x3 = 2
3. passo : eliminação dos coeficientes de x3
 
SYMBOL 183 \f "Symbol" \s 10 \h	Multiplica-se a terceira equação por - 3/4 e 1/2 e soma-se respectivamnete às primeira e segunda equações, obtendo-se :
 3 x1 = -3
 2/3 x2 = 2/3
 - 4 x3 = 2
A solução do sistema fica :
 3 x1 = -3 SYMBOL 222 \f "Symbol" x1 = - 1
 2/3 x2 = -2/3 SYMBOL 222 \f "Symbol" x2 = 1
 - 4 x3 = 2 SYMBOL 222 \f "Symbol" x3 = - 1/2
�
3.3 Método da transformação na matriz unidade ( Gauss-Jordan )
Consiste em transformar o sistema de equações :
 a11 .x1 + a12 .x2 + ... + a1,n-1 .xn-1 + a1n .xn = b1
 a21 .x1 + a22 .x2 + ... + a2,n-1 .xn-1 + a2n .xn = b2
 a31 .x1 + a32 .x2 + ... + a3,n-1 .xn-1 + a3n .xn = b3
 .
 . 
 .
 an-1,1.x1 + an-1,2.x2 + ... + an-1,n-1.xn-1 + an-1,n.xn = bn-1
 an1 .x1 + an2 .x2 + ... + an,n-1 .xn-1 + ann .xn = bn
de maneira que a matriz de coeficientes do sistema transforme-se em uma matriz unidade, ficando o sistema na forma :
 x1 = d1
 x2 = d2
 .
 . 
 .
 xn-1 = dn-1
 xn = dn
A solução do sistema passa então a ser feita de forma trivial, sendo o valor de cada incógnita igual ao termo independente de cada equação.
Neste método, a cada passo, inicialmente a equação do pivô ( k ) é dividida pelo pivô e as demais equações ( i ) são substituídas pela sua soma com o negativo da nova equação do pivô multiplicada pelo coeficiente da incógnita referente ao pivô ( aik ) na equação :
 
 k = aik
 
ficando os coeficientes da linha i :
 aij = aij - aik . akj 
Exemplo :
 3 x1 + x2 = -2
 -2 x1 + 2 x3 = 1
 x1 + 3 x2 + 4 x3 = 0
1. passo : eliminação dos coeficientes de x1
 
SYMBOL 183 \f "Symbol" \s 10 \h	Divide-se a primeira equação por 3, obtendo-se :
 x1 + 1/3 x2 = -2/3
 -2 x1 + 2 x3 = 1
 x1 + 3 x2 + 4 x3 = 0
SYMBOL 183 \f "Symbol" \s 10 \h	Multiplica-se a primeira equação por 2 e -1 e soma-se respectivamente às segunda e terceira equações, obtendo-se :
 x1 + 1/3 x2 = -2/3
 2/3 x2 + 2 x3 = -1/3
 8/3 x2 + 4 x3 = 2/3
2. passo : eliminação dos coeficientes de x2
 
SYMBOL 183 \f "Symbol" \s 10 \h	Multiplica-se a segunda equação por 3/2, obtendo-se :
 x1 + 1/3 x2 = -2/3
 x2 + 3 x3 = -1/2
 8/3 x2 + 4 x3 = 2/3
SYMBOL 183 \f "Symbol" \s 10 \h	Multiplica-se a segunda equação por - 1/3 e -8/3 e soma-se respectivamnete às primeira e terceira equações, obtendo-se :
 x1 - x3 = -1/2
 x2 + 3 x3 = -1/2
 - 4 x3 = 2
3. passo : eliminação dos coeficientes de x3
 
SYMBOL 183 \f "Symbol" \s 10 \h	Divide-se a terceira equação por -4, obtendo-se :
 x1 - x3 = -1/2
 x2 + 3 x3 = -1/2
 x3 = -1/2
SYMBOL 183 \f "Symbol" \s 10 \h	Multiplica-se a terceira equação por 1/2 e -3 e soma-se respectivamnete às primeira e segunda equações, obtendo-se :
 x1 = -1
 x2 = 1 
 x3 = -1/2
A solução é direta.
3.4 Tipos de soluções
O sistema será :
 
a)	incompatível : se todos os coeficientes das incógnitas de uma equação forem nulos e o termo independente não for nulo;
b)	indeterminado : se todos os coeficientes das incógnitas de uma equação forem nulos e o termo independente também;
c)	determinado : caso pelo menos um dos coeficientes das incógnitas de cada equação for não nulo, após o último passo do processo de eliminação.
3.5 Condensação Pivotal
A aplicação dos métodos de eliminação pode levar a erros consideráveis de arredondamento principalmente se os pivôs são muito próximos a zero.
Outro problema é a ocorrência de um pivô nulo.
Para evitar este e minimizar aqueles, pode-se escolher para pivô outros elementos diferentes dos elementos da diagonal principal do sistema original.
Esta técnica é chamada de condensação pivotal, e consiste em rearranjar as equações e / ou incógnitas de maneira que o pivô seja o coeficiente restante do sistema de maior valor absoluto, fazendo com que os multiplicadores fiquem, em módulo, entre 0 e 1, o que evita a propagação de erros de arredondamento.
O pivô deve ser escolhido entre os coeficientes das equações e incógnitas das quais ainda não foi utilizado nenhum coeficiente para pivô.
Exemplo :
 - x1 + 2 x2 + 42 x3 = 83
 72 x1 - 41 x2 - 14 x3 = 44
 35 x1 + 10 x2 - 5x3 = 25
a matriz extendida do sistema fica :
� 
a sequência de eliminação, utilizando o método de diagonalização, trabalhando com 3 algarismos sigmificativos e sem considerar a condensação pivotal :
� 
� 
�
e a solução seria :
 x1 = 1,6
 x2 = 0,68 
 x3 = 1,98
A sequência de eliminação, considerando a condensação pivotal completa, onde antes da primeira eliminação são trocadas as primeira e segunda equações :
� 
 
 
�
Antes da segunda eliminação são trocadas as segunda e terceira incógnitas nas 3 equações :
 
�
 
�
no terceiro passo não é preciso fazer troca de equações e / ou incógnitas porque o único coeficiente que restou para pivô é o coeficiente de x2 na última equação, resultando a matriz extendida :
 
�
e a solução do sistema :
 x1 = 1,00
 x2 = 0,00 
 x3 = 2,00
o que satisfaz as equações originais, com 3 casas decimais.
A condensação pivotal parcial é preferida a condensação pivotal ( ou condensação pivotal completa ) pois esta além de consumir grande esforço para a escolha do pivô a cada passo, ainda pode destruir certas estruturas particulares do sistema ( simetria e esparsidade ).
A condensação parcial consiste em rearranjar equações de maneira que o pivô escolhido seja o coeficiente de maior valor absoluto da variável correspondente a linha.
o que não satisfaz as equações originais.
3.6 Refinamento da solução
Após determinada a solução do sistema, por qualquer um dos métodos, é conveniente a substituição dos valores das incógnitas nas equações originais do sistema, para verificar a adequação do resultado obtido.
Se os resultados não forem adequados dentro de uma precisão pré-estabelecida,pode-se, devido a linearidade do sistema, utilizar os resíduos da equações como termos independentes e resolver o novo sistema, resultado em correções nos resultados obtidos.
As operações, nesta nova solução, consiste na aplicações das operações efetuadas nos termos independentes na solução inicial, pois os coeficientes iriam se alterar na mesma forma já efetuada. 
Exemplo :
 - x1 + 2 x2 + 42 x3 = 83
 72 x1 - 41 x2 - 14 x3 = 44
 35 x1 + 10 x2 - 5x3 = 25
a matriz extendida do sistema fica :
� 
a sequência de eliminação, utilizando o método de transformação na matriz unidade e sem considerar a condensação pivotal :
� 
� 
�
e a solução seria :
 x1 = 1,7
 x2 = 0,9 
 x3 = 1,97
o que não satisfaz as equações originais.
�
o resíduo é : 
 
�
O resíduo é usado como termo independente para a determinação das correções a serem feitas nos valores inicialmente obtidos, novamente usando só 3 algarismos significativos.
 
�
onde são aplicadas as mesmas operações efetuadas na solução inicial nos termos independentes :
 
�
A solução deste sistema :
 
�
e a solução do sistema :
 x1 = 1,00
 x2 = 0,00 
 x3 = 2,00
o que satisfaz as equações originais, com 3 casas decimais.
A sequência de eliminação, considerando a condensação pivotal completa, onde antes da primeira eliminação são trocadas as primeira e segunda equações :
� 
 
 
�
Antes da segunda eliminação são trocadas as segunda e terceira incógnitasnas 3 equações :
 
�
 
�
no terceiro passo não é preciso fazer troca de equações e / ou incógnitas porque o único coeficiente que restou para pivô é o coeficiente de x2 na última equação, resultando a matriz extendida :
 
�
e a solução do sistema :
 x1 = 1,00
 x2 = 0,00 
 x3 = 2,00
o que satisfaz as equações originais, com 3 casas decimais.
3.7 Inversão de matriz
a) Método da adjunta
 adj A
 A-1 = ------ 
 |A|
O processo consiste nos seguintes passos :
SYMBOL 183 \f "Symbol" \s 10 \h	substituir todos os elementos da matriz pelos valores dos determinantes cofatores correspondentes;
SYMBOL 183 \f "Symbol" \s 10 \h	transpor a matriz resultante; e
SYMBOL 183 \f "Symbol" \s 10 \h	multiplicar a matriz pelo inverso do determinante da matriz original.
b) Por eliminação
Considerando que o produto de uma matriz ( A ) por sua inversa ( B ) resulta na matriz unidade :
A . B = B . A = U
se a matriz é de ordem 3, para facilitar a compreensão :
 
�
pode-se determinar os valores dos elementos da matriz inversa ( bij ) separando esta equação matricial em n equações e utilizando o método da transformação da matriz na matriz unidade :
 
�
 
�
 
 
�
e a determinação das n soluções pode ser feita conjuntamente, ficando a matriz extendida na forma :
 
�
Exemplo : Inverter a matriz :
 
 
�
a matriz extendida fica :
 
�
após a primeira eliminação :
 
�
após a segunda eliminação :
 
�
e após a última eliminação :
 
�
c) Método de Shippley-Coleman	
Consiste em fazer para cada elemento da diagonal principal, em qualquer sequência, os seguintes passos :
1.selecionar e modificar o pivô akk;
 
 akk' = -1 / akk
 
2.modificar os demais elementos da coluna do pivô (aik,iSYMBOL 185 \f "Symbol"k) :
 aik' = aik . akk'
 
3.modificar os elementos fora da coluna e linha do pivô (aij,i,jSYMBOL 185 \f "Symbol"k) :
 aij' = aij + aik' . akj
 
4.modificar os demais elementos da linha do pivô (ajk,jSYMBOL 185 \f "Symbol"k) :
 akj' = akj . akk'
 
No final a matriz deve ser multiplicada por -1.
Exemplo : Inverter a matriz :
 
 
�
 escolhendo como primeiro pivô a22, resulta :
 
�
 escolhendo como segundo pivô a22, resulta :
 
�
 
 e escolhendo como terceiro pivô a33, resulta :
 
�
4. Métodos Iterativos
Os métodos iterativos consistem nos seguintes passos :
SYMBOL 183 \f "Symbol" \s 10 \h	fazer uma estimativa inicial para a solução;
SYMBOL 183 \f "Symbol" \s 10 \h	refinar a estimativa até que a solução satisfaça em termos de precisão
Como o processo pode divergir ou demorar a convergir, deve-se prever uma verificação do número de iterações efetuadas.
Esses métodos tem as seguintes características :
SYMBOL 183 \f "Symbol" \s 10 \h	são métodos infinitos;
SYMBOL 183 \f "Symbol" \s 10 \h	podem divergir;
SYMBOL 183 \f "Symbol" \s 10 \h	enganos não impedem a solução;
SYMBOL 183 \f "Symbol" \s 10 \h	não há propagação de erros entre iterações; e
SYMBOL 183 \f "Symbol" \s 10 \h	são fáceis de programar.
Dado o sistema de equações lineares :
 a11.x1 + a12.x2 + ... + a1n.xn = b1
 a21.x1 + a22.x2 + ... + a2n.xn = b2
 .
 . 
 .
 an1.x1 + an2.x2 + ... + ann.xn = bn
consiste em obter em cada equação o valor de uma incógnita, para formar o processo iterativo :
 x1 = ( 1 / a11 ).[ b1 - ( a12.x2 + a13.x3 + ... + a1n.xn )]
 x2 = ( 1 / a22 ).[ b2 - ( a21.x1 + a23.x3 + ... + a2n.xn )]
 .
 . 
 .
 xn = ( 1 / ann ).[ bn - ( an1.x1 + an2.x3 + ... + ann-1.xn-1 )]
4.1 Método de Gauss-Jakobi
Consiste em utilizar nos cálculos os valores das incógnitas na iteração anterior :
 x1i+1 = ( 1 / a11 ).[ b1 - ( a12.x2i + a13.x3i + ... + a1n.xni )]
 x2i+1 = ( 1 / a22 ).[ b2 - ( a21.x1i + a23.x3i + ... + a2n.xni )]
 .
 . 
 .
 xni+1 = ( 1 / ann ).[ bn - ( an1.x1i + an2.x3i + ... + ann-1.xn-1i )]
Baseado no algoritmo anterior, o método consiste na transformação do algoritmo em um sistema de matriz. Portanto, no algoritmo:
a mesma situação pode ser escrita na forma:
Sendo A a matriz dos coeficientes, onde A = D + I + S, no qual D é a matriz diagonal, I a matriz inferior e S a matriz superior, a expressão anterior poderá ser reescrita na forma:
Multiplicando ambos os termos pela matriz inversa da diagonal,
onde
4.2 Método de Gauss-Seidel
Consiste em utilizar nos cálculos os valores já calculados das incógnitas :
 x1i+1 = (1 / a11).[ b1 -(a12.x2i + a13.x3i + ... + a1n.xni )]
 x2i+1 = (1 / a22).[ b2 -(a21.x1i+1 + a23.x3i + ... + a2n.xni )]
 .
 . 
 .
 xni+1 = (1 / ann).[ bn -(an1.x1i+1 + an2.x3i+1 + ... + ann-1.xn-1i+1 )]
Método de Gauss-Seidel ( Matricial )
Seja o sistema abaixo,
que pode ser representado na forma matricial:
Multiplicando ambos os membros pela inversa de ( D + I ), temos:
onde,
4.3 Convergência
A condição suficiente para o processo convergir é que a matriz de coeficientes seja diagonalmente dominante, isto é, que o módulo do elemento da diagonal seja maior que a soma dos módulos dos elementos fora da diagonal, para cada linha da matriz. Este critério é chamado de critério das linhas.
 
 
A convergência será mais rápida quando as equações forem ordenadas segundo os valores crescentes dos ci e quanto maiores estes forem.
Outra condição suficiente que pode ser usada, mas somente para o método de Gauss-Seidel, é o chamado critério de Sassenfeld, que consiste em determinar os valores SYMBOL 98 \f "Symbol"j : 
 
 
Se o maior SYMBOL 98 \f "Symbol"j for menor que 1, então p método de Gauss-Seidel gera uma sequência convergente qualquer que seja a estimativa inicial.
Quanto maiores forem os SYMBOL 98 \f "Symbol"j mais rápida será a convergência, e esta será mais rápida quando as equações forem ordenadas segundo os valores crescentes dos SYMBOL 98 \f "Symbol"j.
Para se alterar os valores dos SYMBOL 98 \f "Symbol"j ou dos ci, pode trocar as equações ou as incógnitas de posição.
4.4 Estimativa inicial
Não influi na convergência e usualmente é feita xi = 0 .
4.5 Condições terminais
Devem ser utilizadas as seguintes :
SYMBOL 183 \f "Symbol" \s 10 \h	a maior diferença, em valor absoluto, entre dois valores sucessivos das incógnitas deve ser menor ou igual a uma tolerância pré-definida. Também pode-se usar esta diferenças divididas pelo último valor de cada incógnita ( errorelativo ). 
SYMBOL 183 \f "Symbol" \s 10 \h	o maior resíduo das equações deve ser menor ou igual a uma tolerância pré-definida. Também pode-se usar estes resíduos divididos pelo termo independente de cada equação ( erro relativo ). 
5. Comparação dos métodos
Quanto a convergência :
SYMBOL 183 \f "Symbol" \s 10 \h	os métodos diretos obtém a solução para qualquer sistema de equações lineares algébricas, desde que a matriz de coeficiente não seja singular;
	
SYMBOL 183 \f "Symbol" \s 10 \h	os métodos iterativos apenas em determinadas condições.
Quanto a esparsidade :
SYMBOL 183 \f "Symbol" \s 10 \h	os métodos diretos normalmente não conservam a esparsidade;
	
SYMBOL 183 \f "Symbol" \s 10 \h	os métodos iterativos conservam a esparsidade.
Quanto ao número de operações :
SYMBOL 183 \f "Symbol" \s 10 \h	nos métodos diretos o número de operações é proporcional a n3;
	
SYMBOL 183 \f "Symbol" \s 10 \h	nos métodos iterativos o número de operações é proporcional a 2 n2 por iteração.
Quanto aos erros de arredondamento :
SYMBOL 183 \f "Symbol" \s 10 \h	os métodos diretos apresentam erros de arredondamento;
	
SYMBOL 183 \f "Symbol" \s 10 \h	os métodos iterativos são menos susceptíveis aos erros de arredondamento e independem da estimativa inicial.
6.Bibliografia
[1] Rugiero, Márcia A. Gomes & Lopes, Vera Lúcia da Rocha - Cálculo Numérico : aspectos teóricos e computacionais -- São Paulo, SP : McGraw-Hill, 1988
[2] Santos, José Abel Royo dos - Computação e Cálculo Numérico - apostila de curso de pos-graduação -- Itajubá, MG - Escola Federal de Engenharia de Itajubá, 1982
[3] Campos, Ladislau Borges - Cálculo Numérico - apostila de curso de graduação -- Curitiba, PR - Universidade Federal do Paraná, 1983
[4] Menezes, Wanda Cristina de - Cálculo Numérico - apostila de curso de graduação -- Curitiba, PR - Universidade Federal do Paraná, 1993
�
Interpolação
Introdução
	A interpolação é outra das técnicas bem antigas e básicas do cálculo numérico. Muitas funções são conhecidas apenas em um conjunto finito e discreto de pontos de um intervalo [a, b], como, por exemplo, a tabela abaixo que relaciona calor específico da água e temperatura:
	Xi
	x0
	x1
	x2
	x3
	x4
	x5
	x6
	x7
	Temperatura ((C)
	20
	25
	30
	35
	40
	45
	50
	55
	Calor específico
	0.99907
	0.99852
	0.99826
	0.99818
	0.99828
	0.99849
	0.99878
	0.99919
Tabela 1 - Calor específico da água.
	A partir desses dados suponhamos que se queira calcular:
	a) o calor específico da água a 32.5( C
	b) a temperatura para a qual o calor específico é 0.99837.
	A interpolação tem o objetivo de nos ajudar na resolução deste tipo de problema, ou em casos em que possuímos um conjunto de valores obtidos através de alguns experimentos.
	Interpolar uma função f(x) consiste em aproximar essa função por uma outra função g(x), escolhida entre uma classe de funções definida a priori e que satisfaça algumas propriedades. A função g(x) é então usada em substituição à função f(x).
	A necessidade de se efetuar esta substituição surge em várias situações, como por exemplo:
	a) quando são conhecidos somente os valores numéricos da função por um conjunto de pontos (não dispondo de sua forma analítica) e é necessário calcular o valor da função em um ponto não tabelado (como é o caso do exemplo anterior).
	b) quando a função em estudo tem uma expressão tal que operações como a diferenciação e a integração são difíceis (ou mesmo impossíveis) de serem realizadas. Neste caso, podemos procurar uma outra função que seja uma aproximação da função dada e cujo manuseio seja bem mais simples.
	As funções que substituem as funções dadas podem ser de tipos variados, tais como: polinomiais, trigonométricas, exponenciais e logarítmicas. Nós iremos considerar apenas o estudo das funções polinomiais.
Conceito de Interpolação
	Seja a função y = f(x), dada pela tabela 1. Deseja-se determinar 
�, sendo:
	a) 
� ( (x0, x7)		e	
� ( xi, i = 0, 1, 2, ..., 7
	b) 
� ( (x0, x7)
	Para resolver (a) tem-se que fazer uma interpolação. E, sendo assim, determina-se o polinômio interpolador, que é uma aproximação da função tabelada. Por outro lado, para resolver (b), deve-se realizar uma extrapolação.
	Consideremos (n + 1) pontos distintos: x0, x1, x2, ..., xn, chamados nós da interpolação, e os valores de f(x) nesses pontos: f(x0), f(x1), f(x2), ..., f(xn).
	A forma de interpolação de f(x) que veremos a seguir consiste em se obter uma determinada função g(x) tal que:
	g(x0) = f(x0)
	g(x1) = f(x1)
	g(x2) = f(x2)
	 
�	 
�
	g(xn) = f(xn)
	Graficamente temos:
Interpretação geométrica para n = 5
Interpolação Linear
Obtenção da Fórmula
	Dados dois pontos distintos de uma função y = f(x) : (x0, y0) e (x1, y1), deseja-se calcular o valor de 
� para um determinado valor de 
� entre x0 e x1, usando a interpolação polinomial.
	O polinômio interpolador é uma unidade menor que o número de pontos conhecidos. Assim sendo, o polinômio interpolador nesse caso terá grau 1, isto é,
P1(x) = a1x + a0
	Para determiná-lo, os coeficientes a0 e a1 devem ser calculados de forma que tenha:
P1(x0) = f(x0) = y0
P1(x1) = f(x1) = y1
ou seja, basta resolver o sistema linear abaixo:
	
�	onde a1 e a0 são as incógnitas e
	
�		é a matriz dos coeficientes.
	O determinante da matriz A é diferente de zero, sempre que x0 ( x1, logo para pontos distintos o sistema tem solução única.
	O polinômio interpolador P1(x) = a1x + a0 tem como imagem geométrica uma reta, portanto estaremos aproximando a função f(x) por uma reta que passa pelos dois pontos conhecidos (x0, y0) e (x1, y1).
	A figura abaixo mostra, geometricamente, os dois pontos, (x0, y0) e (x1, y1), e a reta que passa por eles.
Exemplos
Exemplo 1: Seja a função y = f(x) definida pelos pontos (0.00; 1.35) e (1.00; 2.94). Determinar aproximadamente o valor de f(0.73).
	P1(x) = a1x + a0 é o polinômio interpolador de 1( grau que passa pelos pontos dados. Então teremos:
a) Pontos utilizados:
	(0.00;1.35)	e	(1.00; 2.94)
b) Cálculo dos coeficientes:
	P1(0) = a1 ( 0 + a0 = 1.35	(	a0 = 1.35
	P1(1) = a1 ( 1 + a0 = 2.94	(	a1 = 1.59
c) Polinômio interpolador:
	P1(x) = 1.59x + 1.35 (equação da reta que passa pelos pontos dados)
d) Resposta:
	P1(0.73) = 1.59 ( 0.73 + 1.35
	P1(0.73) = 2.51
	O resultado obtido acima está afetado por dois tipos de erros:
	a) Erro de arredondamento (EA) - é cometido durante a execução das operações e no caso de um resultado ser arredondado.
	b) Erro de truncamento (ET) - é cometido quando a fórmula de interpolação a ser utilizada é escolhida, pois a aproximação de uma função conhecida apenas através de dois pontos dados é feita por um polinômio de 1( grau.
Exemplo 2: Dada a função f(x) = 10x4 + 2x + 1 com os valores de f(0.1) e f(0.2) determinar P1(0.15) e o erro absoluto cometido.
Resposta: P1(0.15) = 1.3085
Erro absoluto: EA = (0.0034375
Exemplo 3: Calcular o calor específico aproximado da água a 32,5( C, usando os valores da tabela 1.
Resposta: P1(32.5) = 0.99822 (Usando as temperaturas 30( C e 35( C).
Interpolação Quadrática
Obtenção da Fórmula
	Se conhecermos três pontos distintos de uma função, então o polinômio interpolador será:
P2(x) = a2x2 + a1x + a0
	O polinômio P2(x) é conhecido como função quadrática cuja imagem geométrica é uma parábola, portanto, estaremos aproximando a função f(x) por uma parábola que passa pelos três pontos conhecidos (x0, y0), (x1, y1) e (x2, y2).
	Para determinarmos os valores de a2, a1 e a0 é necessário resolver o sistema:
		a2
� + a1x0 + a0 = y0
		a2
� + a1x1 + a0 = y1
		a2
� + a1x2 + a0 = y2
onde a2, a1 e a0 são as incógnitas e os pontos (x0, y0), (x1, y1) e (x2, y2) são conhecidos.
	A matriz dos coeficientes é:
	V = 
�
	Como os pontos são distintos, então o sistema terá solução única.
Exemplos
Exemplo 1: Utilizando os valores da função seno, dados pela tabela abaixo, determinar a função quadrática que se aproxima de f(x) = 
�, trabalhando com três casas decimais.
	x
	sen(x)
	f(x)
	0
	00.000
	
�
	
�
	0.328
	
�
	
�
	0.560
a) Pontos utilizados:
	( 0; 0 )		( (/6; 0.328 )		( (/4; 0.560 )
b) Cálculo dos coeficientes:
	P2(x) = a2x2 + a1x + a0 
	Da primeira linha temos que a0 = 0. Logo, o sistema passa a ser:
	Resolvendo o sistema acima encontraremos a solução aproximada:
	a2 = 0.333		a1 = 0.452		a0 = 0
c) Polinômio interpolador:
	P2(x) = 0.333
� + 0.452x
Exemplo 2: Determinar o valor de f(0.2) e o erro absoluto ocasionado pela aplicação da interpolação quadrática, no cálculo deste valor, usando os valores tabelados da função f(x) = x2 ( 2x + 1. Utilizar duas casas decimais.
	x
	f(x)
	0.5
	0.25
	0.3
	0.49
	0.1
	0.81
Resposta: P2(0.2) = 0.64
Erro absoluto: EA = 0
	Podemos observar que o polinômio interpolador é igual a função dada. Isto ocorre porque a função dada é polinomial de 2( grau e, a partir de três pontos da função, consegue-se determiná-la sem erro. Contudo, poderá existir o erro de arredondamento.
Exemplo 3: Usando três pontos da Tabela 1, determinar o calor específico aproximado da água a 31( C
Resposta: P2(31) = 0.99822 (Considerando os pontos (20; 0.99907), (30; 0.99826) e (40; 0.99828))
Interpolação de Lagrange
	As interpolações vistas anteriormente são casos particulares da interpolação de Lagrange. Vamos estudar agora o polinômio interpolador de grau menor ou igual a n, sendo dados n + 1 pontos distintos.
	Teorema: Sejam (xi, yi), i = 0, 1, 2, ..., n, n + 1 pontos distintos, isto é, xi ( xj para i ( j. Existe um único polinômio P(x) de grau menor ou igual a n, tal que P(xi) = yi, para todo i.
	O polinômio P(x) pode ser escrito na forma:
	Pn(x) = a0 + a1x + a2x2 + ... + anxn	ou	Pn(x) = 
�
	P(x) é, no máximo, de grau n, se an ( 0 e, para determiná-lo, deve-se conhecer os valores de a0, a1, ..., an. Como Pn(x) contém os pontos (xi, yi), i = 0, 1, ..., n, pode-se escrever que Pn(xi) = yi.
	Com isso temos:
�
	Resolvendo o sistema acima, determina-se o polinômio Pn(x). Para provar que tal polinômio é único, basta que se mostre que o determinante da matriz A, dos coeficientes das incógnitas do sistema, é diferente de zero. A matriz A é:
A = 
�
	Mas o determinante da matriz A é conhecido como determinante das potências ou de Vandermonde e, da Álgebra Linear, sabe-se que seu valor é dado por:
	det(A) = 
�. Como xi ( xj para i ( j, vem que det(A) ( 0.
	Logo, P(x) é único.
Exemplo 1: Sejam os valores: x0 = 1, x1 = 0, x2 = 3 e x3 = 2. Determinar: 
�.
	
�	= (x1 ( x0) (x2 ( x0) (x2 ( x1) (x3 ( x0) (x3 ( x1) (x3 ( x2) = 
			= ((1)(2)(3)(1)(2)((1) = 12
	Este valor é igual ao determinante da matriz:
		
�
Obtenção da Fórmula
	Será mostrado, agora, a dedução da fórmula de interpolação de Lagrange.
	Sejam x0, x1, x2, ..., xn, (n + 1) pontos distintos e yi = f(xi), i = 0, 1, ..., n.
	Seja Pn(x) o polinômio de grau ( n que interpola f em x0, ..., xn. Podemos representar Pn(x) na forma Pn(x) = y0L0(x) + y1L1(x) + ... + ynLn(x), onde os polinômios Lk(x) são de grau n. Para cada i, queremos que a condição Pn(xi) = yi seja satisfeita, ou seja:
	Pn(xi) = y0L0(xi) + y1L1(xi) + ... + ynLn(xi) = yi
	A forma mais simples de se satisfazer esta condição é impor:
	Lk(xi) = 
� e, para isso, definimos Lk(x) por
	Lk = 
�
	Como o numerador de Lk(x) é um produto de n fatores da forma:
	(x ( xi), i = 0, 1, ..., n, i ( k, então Lk(x) é um polinômio de grau n e, assim, Pn(x) é um polinômio de grau menor ou igual a n.
	Além disso, para x = xi, i = 0, ..., n temos:
	Pn(xi) = 
� = yiLi(xi) = yi
	Então, a interpolação de Lagrange para o polinômio interpolador é:
	Pn(x) = 
�
onde Lk(x) = 
�
Pn(x) = 
�, é a fórmula da interpolação lagrangeana.
Exemplos: 
Exemplo 2: No caso da interpolação linear, visto anteriormente, temos dois pontos distintos: (x0, f(x0)) e (x1, f(x1)) com n igual a 1.
a) Pontos utilizados:
	(0.00; 1.35) e (1.00; 2.94) 
b) Cálculo dos coeficientes:
	P1(x) = y0L0(x) + y1L1(x), onde
	L0(x) = 
�
	L1(x) = 
�
	Assim, P1(x) = y0
� + y1
�
que é exatamente a equação da reta que passa por (x0, f(x0)) e (x1, f(x1)).
c) Polinômio interpolador:
	P1(x) = 1.35
� + 2.94
� = (1.35x + 1.35 + 2.94x = 1.59x + 1.35
que é a mesma expressão obtida no exemplo 1 de interpolação linear.
Exemplo 3: Determinar o polinômio de interpolação de Lagrange para a função conhecida pelos pontos tabelados abaixo e o resultado em P(0.5):
	i
	xi
	yi
	0
	0
	0
	1
	1
	1
	2
	2
	4
Resposta: P2(0.5) = (0.5)2 = 0.25
Exemplo 4: Determinar o polinômio interpolador de Lagrange para a função conhecida pelos pontos da tabela abaixo:
	i
	xi
	yi
	0
	(1
	4
	1
	0
	1
	2
	2
	1
	3
	3
	16
Polinômio interpolador: P3(x) = x3 ( 4x + 1
Interpolação Parabólica Progressiva
	Na interpolação parabólica progressiva precisamos de n + 1 pontos, onde n é o grau do polinômio desejado. Em seguida, tomamos os pontos mais próximos, do ponto que queremos, na hora de montar a tabela.
Polinômio de grau 0:
G0  
P0(x) = a0
Polinômio de grau 1:
G1  
+
P1(x) = a0 + a1.(x ( x0)
Polinômio de grau 2:
G2 
+
+
P2(x) = a0 + a1.(x ( x0) + a2.(x ( x0).(x ( x1)
(
Polinômio de grau n:
	Pn(x) = a0 + a1.(x ( x0) + a2.(x ( x0).(x ( x1) + ... + an.(x ( x0).(x ( x1).(x ( x2) ... (x ( xn-1)
Impondo que Pn(x) passe por todos os n + 1 pontos da tabela, temos que:
Pn(x0) = f(x0)
Pn(x1) = f(x1)
Pn(x2) = f(x2)
(
Pn(xn) = f(xn)
Validade:
��EMBED Equation.2
�
(
Exemplo 1: Dados os pares abaixo, determinar a expressão analítica destes mesmos:
	xi
	(5
	(3
	1
	2
	f(xi)
	(8
	(4
	4
	6
1ª Hipótese:
2ª Hipótese:
3ª Hipótese:
4ª Hipótese:
Logo, a expressão é : P1(x) = 2x + 2
Diferenças Divididas
	Seja f(x) uma função tabelada em n + 1 pontos distintos x0, x1, x2, ... xn. Definimos o operador diferenças divididas por:
f[x0] = f(x0)
f[x0,x1] = 
 = 
f[x0,x1,x2] = 
�
f[x0,x1,x2, ... xn] = 
Dizemos que f[x0,x1,x2,...xk] é a diferença dividida de ordem k da função f(x) sobre os k + 1 pontos.
Conhecidos os valores que f(x) assume nos pontos distintos x0, x1, x2, ... xn, podemos construir a tabela:
	xi
	Ordem 0
	Ordem 1
	Ordem 2
	....
	Ordem n
	x0
	f[x0]
	f[x0,x1]
	f[x0,x1,x2]
	
	f[x0,x1,x2 ... xn]
	x1
	f[x1]
	f[x1,x2]
	f[x1,x2,x3]
	
	(
	x2
	f[x2]
	f[x2,x3]
	f[x2,x3,x4]
	
	(
	...
	...
	...
	...
	
	...
	xn-2
	f[xn-2]
	f[xn-2,xn-1]
	f[xn-2,xn-1,xn]
	
	(
	xn-1
	f[xn-1]
	f[xn-1,xn]
	(
	
	(
	xn
	f[xn]
	(
	(
	
	(
Propriedade do Operador Diferenças Divididas
	Pode-se provar que as diferenças divididas satisfazem a propriedade de ser simétrico nos argumentos.
Exemplo:
f[x0,x1] = 
 = 
= f[x1,x0]
Interpolação de Newton com Diferenças Divididas
Pode-se provar que cada coeficiente an do polinômio interpolador de Newton corresponde ao operador de grau n de diferenças divididas:
f[x0] = c0
f[x0,x1] = c1
f[x0,x1,x2] = c2
(
f[x0,x1,x2,...,xn] = cn
Pn(x) = c0 + c1.(x ( x0) + c2.(x ( x0).(x ( x1) + ... + cn.(x ( x0).(x ( x1).(x ( x2) ... (x ( xn-1)
	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 ( x2) ... (x ( xn-1)
Exemplos
Exemplo 1: Obter f(0.5) usando um polinômio interpolador de Newton do segundo grau (3 pontos). Considere a seguinte tabela:
	xi
	(1
	0
	1
	2
	3
	F(xi)
	2
	1
	2
	5
	10
a) Cálculo dos coeficientes de Pn(x):
	
	X
	Ordem 0
	Ordem 1
	Ordem 2
	Ordem 3
	Ordem 4
	x0
	(1
	2
	(1
	1
	0
	0
	x1
	0
	1
	1
	1
	0
	
	x2
	1
	2
	3
	1
	
	
	x3
	2
	5
	5
	
	
	
	x4
	3
	10
	
	
	
	
onde:
f[x0] = f(x0) = 2
f[x1] = f(x1) = 1
f[x2] = f(x2) = 2
f[x3] = f(x3) = 5
f[x4] = f(x4) = 10
f[x0,x1] = 
 = 
 = 
� = (1
f[x1,x2] = 
� = 
� = 1
f[x2,x3] = 
 = 
 = 3
f[x3,x4] = 
 = 
 = 5
f[x0,x1,x2] = 
 = 
� = 1
f[x1,x2,x3] = 
� = 
� = 1
f[x2,x3,x4] = 
 = 
 = 1
f[x0,x1,x2,x3] = 
� = 
� = 0
f[x1,x2,x3, x4] = 
� = 
� = 0
f[x0,x1,x2,x3,x4] = 
� = 
� = 0
b) Polinômio interpolador:
P2(x) = 2 ( 1(x + 1) + 1(x + 1)(x ( 0) 
P2(x) = 2 ( (x + 1) + x (x + 1)
P2(x) = 2 ( x ( 1 + x2 + x
P2(x) = x2 + 1
c) Resposta: