nunesp
CAMPUS DE GUARATINGUETÁ
Computação e Cálculo Numérico
Prof. G.J. de Sena - Depto. de Matemática – Ed. 2008
CAPÍTULO 1
ARITMÉTICA DE PONTO FLUTUANTE
1.1. Representação de Números num Sistema de Aritmética de
Ponto Flutuante
β
O número máximo de dígitos da mantissa (t) é definido em
termos do comprimento da palavra do computador.
•
Dado um número N, sua representação em aritmética de ponto
flutuante de t dígitos é efetuada por truncamento ou
arredondamento.
•
Erros decorrentes da impossibilidade de se representar um
número dado:
onde
•
e é um expoente num intervalo [m, M].
e > M
"Underflow"
SE
e < m
β =10, t = 3, M = 4, m = −4
x
(.d1d 2 ...d t ) é a mantissa, 0 ≤ d j
SE
Exemplo: Considere o sistema de aritmética de ponto flutuante:
×βe
•
"Overflow"
Preservamos o máximo de exatidão normalizando todos os resultados.
O Sistema Computacional de Aritmética de Ponto Flutuante é
utilizado por calculadoras e computadores na representação dos
números e execução das operações. Um número qualquer na base β
em aritmética de ponto flutuante de t dígitos tem a forma:
± (.d1 d 2 ...d t )
•
1,25
2.71828
-238.15
0.000007
718235.82
≤ β − 1 , j = 1, K t ;
REPRESENTAÇÃO
ARREDONDAMENTO
TRUNCAMENTO
0.125 × 10
0.272 × 10
-0.238 × 103
-
0.125 × 10
0.271 × 10
-0.238 × 103
-
Observações:
•
Os parâmetros m, M dependem da máquina utilizada.
•
Um número em aritmética de ponto flutuante está normalizado
se d 1 ≠ 0 .
Uma representação com t dígitos na mantissa é dada estar em precisão
simples. Um sistema de precisão dupla é um sistema de aritmética de
ponto flutuante com aproximadamente o dobro de dígitos disponíveis
para a mantissa.
1
Exemplo [FRANCO, 2006]:
Exemplo:
Seja um sistema de aritmética de ponto flutuante com as seguintes
características:
Representar, no sistema de aritmética de ponto flutuante anterior, os
seguintes números:
β = 2, t = 3, m = -1, M = 2
x1 = 0.38 , x 2 = 5.3 e x3 = 0.15 (números na base 10)
Quantos números podem ser representados neste sistema? Quais são
estes números?
Resolução:
a) x1 = 0.38
Resolução:
Como a base do sistema é 2, é preciso converter os números para esta
base1.
Os números abaixo de cada elemento da representação indicam o
número de possibilidades na respectiva posição:
0.3810 = 0.011000010K2
e
±
{ 0.d{{{
1 d 2 d3 × β
{
2
1
2
2
∴ x1 = +0.110 × 2 −1
4
Assim, a quantidade de números que pode ser representada é dada por:
b) x 2 = 5.3
2 × 1 × 2 × 2 × 4 = 32 + Representação do zero = 33 números. A tabela
a seguir apresenta os números positivos possíveis neste sistema e a
representação do zero.
510 = 1012
0.310 = 0.0100110011K2
⇒ 5.310 = 101.0100110011K2
∴ x 2 = 0.101 × 2 3 (não pode ser representado: overflow).
0.100 × 2 −1
0.101 × 2 −1
0.110 × 2 −1
0.111 × 2 −1
0.100 × 2 0
0.101 × 2 0
0.110 × 2 0
0.111 × 2 0
c) x3 = 0.15
0.100 × 21
0.101 × 21
0.110 × 21
0.111 × 21
0.1510 = 0.00100110011K2
0.100 × 2 2
0.101 × 2 2
0.110 × 2 2
0.111 × 2 2
∴ x3 = 0.100 × 2 −2 (não pode ser representado: underflow).
ZERO = 0.000 × 2 −1
1
Para maiores detalhes sobre o processo de conversão, veja o apêndice no final do
capítulo.
2
Exercícios [FRANCO, 2006]:
a) Calcular P (1.61) usando uma calculadora.
1) Considere o sistema de aritmética de ponto flutuante:
b) Calcular P (1.61) considerando o sistema:
β = 10, t = 3, m = -5, M = 5
β = 10, t = 3, m = -4, M = 3 (arredondamento)
Efetue as operações indicadas:
a) (1.386 – 0.987) + 7.6485
1.2. ERROS ABSOLUTOS E RELATIVOS
b) 1.386 – (0.987 – 7.6485)
c)
1.338 − 2.038
4.577
ERRO ABSOLUTO: É a diferença entre o valor exato de um número
x e seu valor aproximado x :
1.338 2.038
d)
−
4.577 4.577
EA X = x − x
Exemplo: π ∈ ( 314
. , 315
. ), π
intervalo,
2) Para a expressão a seguir:
x=
um valor tomado dentro deste
EAπ = π − π < 0.01 (limitante superior p/ o módulo do erro)
17.678
9.617 2
, pede-se:
+
3.471 3.716 × 1.85
a) Calcular x diretamente com o auxílio de uma calculadora (ou
seja, sem utilizar um sistema de aritmética de ponto flutuante
específico).
Exemplo:
x = 2112 .9
b) Calcular x considerando o sistema:
⇒ x ∈ ( 2112 .8, 2113)
EAx < 01
.
β = 10, t = 3, m = -4, M = 3 (arredondamento)
y = 5.3
⇒
3) Considere o polinômio a seguir:
EAy < 0.1
P( x) = 2.3 x 2 − 0.6 x 2 + 1.8 x − 2.2
Seja calcular o valor numérico de P ( x) para x = 1.61 . Ped-se:
3
y
∈
(5.2, 5.4)
ERRO RELATIVO: É o quociente do erro absoluto pelo valor
aproximado:
ER x =
EAx
x
=
comporta x, uma aproximação será obtida por arredondamento ou por
truncamento. Seja um sistema de aritmética de ponto flutuante de t
dígitos (base 10); x pode ser escrito na forma:
x−x
x
x = f x ×10e + g x × 10e − t onde 0.1 ≤ f x < 1 e 0 ≤ g x < 1.
Exemplo:
Exemplo:
t = 4, x = 234.57
x = 2112.9
⇒ ERx =
EAx
x
x = 0.2345 × 103 + 0.7 × 10 −1
⇒ f x = 0.2345 e g x = 0.7
0. 1
<
≅ 4,7 ×10 − 5
2112.9
EAx < 0.1
TRUNCAMENTO:
y = 5. 3
⇒ ERy =
EAy
y
<
O termo g x ×10 e −t é despreza do . Portanto, x = f x ×10 e
0.1
≅ 0.02
5.3
EAx = x − x = g x ×10 e−t < 10 e −t (pois | g x |< 1)
EAy < 0.1
ER x =
EAx
x
=
g x ×10 e−t
f x ×10 e
<
10 e −t
= 10 −t +1
0.1×10 e
(pois 0.1 é o valor mínimo que f x pode ter)
∴ o erro relativo fornece uma indicação do grau de precisão da
representação.
ARREDONDAMENTO:
Arredondamento simétrico:
1
e
f x ×10 , se g x < 2
x=
f ×10 e +10 e−t , se g ≥ 1
x
x
2
1.3. ERROS DE ARREDONDAMENTO E TRUNCAMENTO
EM UM SISTEMA DE ARITMÉTICA DE PONTO
FLUTUANTE
Se um dado número x não tem representação finita na base numérica
empregada numa máquina, ou se o comprimento da palavra não
4
Se g x <
Exemplo:
1
:
2
x = 0.937 × 104
1
EAx = x − x = g x ×10 e −t < ×10 e−t
2
e −t
EAx
g x ×10
1 2×10 e−t 1
ER x =
=
<
= ×10 −t +1
e
e
2
f
×
10
0
.
1
×
10
x
x
x+ y =?
y = 0.1272 ×10
2
Resolução:
Se g x ≥1 2 :
(
) (
EAx = x − x = f x ×10 e + g x x10 e−t − f x ×10 e +10 e −t
A mantissa do número de menor expoente deve ser deslocada para a
direita de um número de casas igual à diferença entre os dois
expoentes.
)
= g x ×10 e−t −10 e −t
= (g x −1)× x10
ER x =
EAx
≤
x
e −t
4
x = 0.937 × 10 4 y = 0.00
{1272 × 10
1
≤ ×10 e −t
2
1 2×10 e−t
f x ×10 e +10 e−t
<
4−2
4
∴ x + y = (0.937 + 0.001272) × 10 4 = 01
.938272
×4
10
4424
3
1 2×10 e−t 1 2×10 e−t 1
<
= ×10 −t +1
f x ×10 e
0.1×10 e 2
resultado exato
Para um sistema com t = 4:
RESUMO
TRUNCAMENTO
EAx < 10 e − t
ERx
< 10 − t +1
x + y = 0.9382 x10 4
(truncamento)
x + y = 0.9383 x10 4
(arredondamento)
Para o caso de arredondamento:
ARREDONDAMENTO
1
EAx < × 10e − t
2
1
ERx < × 10 − t +1
2
ER x + y =
( x + y ) − ( x + y ) 0.938272 − 0.9383
=
= 2.9841 × 10 −5
0.9383
x+ y
1
1
< 10 −t +1 = 10 − 4 +1 = 5 × 10 − 4
2
2
5
Exemplo:
x = 0.0000 × 104
x1 = 0.1246 × 10
y = 0.1234 × 102
x2 = 0.3290 × 10−1
⇒ x + y = (0.0000 + 0.001234) × 10 4 = 0.001234 x10 4
x1 + x2 = .1246 ×101 + .3290 ×10−1 = (.1246 + .003290 ) ×101
⇒ x + y = 0.0012 × 104
=.1278×101 ∴ x1 + x2 = .1278 ×101 (truncamento)
∴ Exemplo de zero de ponto flutuante: 0.0000 × 10−50 .
Exemplo:
1.4. PROPAGAÇÃO DE ERRO
x.y = ?
Resolução:
1.4.1. Expressões de Erros para as Operações Aritméticas
4
2
x. y = (0.937 × 10 ) × (0.1272 × 10 )
=(0.937 × 0.1272) × 10 6
= 0.1191864 × 10
Obtenção de expressões para os erros absoluto e relativo no resultado
de cada uma das quatro operações aritméticas, como funções de seus
operandos e de seus erros.
6
∴ x. y = 0.1191 × 10 6 (truncamento).
(a) Adição (x+y)
6
x. y = 0.1192 × 10 (arredondamento).
x + y = ( x + EAx ) + ( y + EAy ) = ( x + y ) + ( EAx + EAy )
∴EAx + y = EAx + EAy
O zero em ponto flutuante é, em geral, representado com o menor
expoente possível da máquina. O exemplo a seguir ilustra a razão
desta necessidade.
ER x + y =
EAx + y
x+y
=
EAx x EAy y
.
+
=
x x + y
y x + y
x
y
⇒ ER x + y = ER x
+ ER y .
x + y
x + y
Exemplo:
6
(b) Subtração (x-y)
EAx − y = EAx − EAy
∴
x
y
ERx − y = ERx
− ER y .
x − y
x − y
EAy
x x + EAx
≅
.1 −
y
y
y
=
x xEAy EAx
−
+
−
y
y2
y
(c) Multiplicação: (x.y)
x x EAx x . EAy
≅ +
−
y y
y
y2
EAx x . EAy
∴ EAx / y ≅
−
y
y2
y . EAx − x . EAy
∴ EAx / y =
y2
∴
x. y = ( x + EAx ).( y + EAy ) = xy + xEAy + yEAx +
∴ ERx .y = x . EAy + y . EAx
ER x . y =
x . EAy + y . EAx
x. y
=
EAx
x
+
EAy
ER x / y =
y
∴ ER x / y
∴ ERx . y = ERx + ERy
y . EAx − xEAy y EAx EAy
. =
−
y2
x
x
y
EAx EAy
=
−
∴ ERx/ y = ERx − ERy
x
y
(d) Divisão (x/y)
EAy
x + EAx
1
x x + EAx x + EAx
=
=
.
=
1 +
EAy
y y + EAy
y
y
y
1 +
y
Exemplo:
Sistema de aritmética de ponto flutuante
−1
t=4
β = 10
aproximaç ão do binômio
(1 + r ) n ≅ 1 + nr , p / r << 1
7
x = 0.7237 × 10 4
y = 0.2145 × 10 −3 números representados exatamente.
z = 0.2585 × 101
Efetuar as operações e obter o erro relativo no resultado
(arredondamento)
(a) x + y + z
(d) (x y)/z
(b) x - y -z
(e) x . (y/z)
(c) x/y
s
ERs 2 = ERs1 . 1 −
s1 − z
∴ ERs2 <
Resolução de (b):
w={
x− y−z
s1
1
4
24
3
1
0.7237 1
x10 − 3 ×
+ × 10− 4 +1
2
0.7234 2
ERs2 < 1.0002 × 10 −3
s2
s1 = x − y = (0.7237 − 0.00000002) × 10
= 0.72369998 × 10
z
+ RA
s1 − z
∴ x − y − z = 0.7234 × 104
4
ERx − y − z < 1.0002 × 10− 3
4
∴ s1 = 0.7237 × 10 4
Exercício:
Supondo que x é representado num computador por x , onde x é
obtido por arredondamento, obtenha os limites superiores para os
erros relativos de u=2 x e w= x + x .
Respostas:
ERu < 10 − t +1
ERw < 10 − t +1
1
1
× 10 − 4 +1 = × 10 − 3
2
2
s2 = s1 − z = (0.7237 − 0.0002585) × 10 4 = 0.7234415 × 10 4
∴ ERs1 <
Exercício:
Idem para u=3 x e w = x + x + x
Respostas:
4
ERu < 10 − t +1 e ERw < x10 − t +1
3
∴ s2 = 0.7234 × 10 4
Exercício:
Sejam x e y as representações de x e y obtidas por arredondamento
em um computador. Deduza expressões de limite de erro para mostrar
8
que o limite do erro relativo de u = 3 x y é menor que o limite do erro
relativo de w= ( x + x + x ) y.
Respostas:
ER u < 2 x10− t +1
ER w
1
1
∴ ERs2 < 10−3 + 10−3 = 10−3
2
2
7
< x10− t +1
3
∴( x. y ) / z = 0.6004
−3
ER( x. y ) / z < 10
Exemplo:
Resolução do item (e):
w = x. ( y / z )
123
1
12
4 s4
3
Resolução do item (d) do exemplo anterior:
w = ({
x. y ) / z
s2
1s124
3
s1 = y z = (0.2145 0.2585) × 10−3−1 = 0.8297872 × 10 4
s2
s1 = x. y = (0.7237 × 0.2145 x10
4−3
1
= 0.152336 × 10
s1 = 0.8298 × 10− 4
1
∴ s1 = 0.1552 × 10
1
1
1
× 10 − t +1 = 10 − 4 +1 = × 10 − 3
2
2
2
1 −3
∴ ERs1 < 10
2
s2 = s1 z = (0.1552 0.2585) × 101−1
∴ ERs1 <
s2 = x.s1 = (0.7237 × 0.8298) x104 − 4 = 0.6005262
∴ s2 = 0.6005
ERs2 =
= 0.6003868
∴ s2 = 0.6004
ERs1 + RA ∴ ERs2 <
⇒ ERs2 < 10 −3
9
1 −3 1 −3
10 + 10
2
2
∴x1 + x 2 = 1 .9998 ×10 99 ⇒ " Overflow " de ponto flutuante
(interrupção).
∴( x. y ) / z = 0.6005
−3
ERx. ( y / z ) < 10
1.4.2. Cálculo de Erros por Diferenciação de Funções Compostas
Exemplo:
Implementação com dígito de proteção ou dígito de guarda:
(imediatamente à direita da mantissa do número de menor expoente).
Suponha que uma grandeza z dependa de duas outras, x e y, por uma
determinada “lei”, ou seja:
x1 = .1064 ×103
z = f ( x, y )
x2 = − .3173×10 2
O erro incorrido em um cálculo de z, EAz , será expresso como uma
função dos erros EAx e EAy , das grandezas x e y respectivamente, de
x1 + x2 = (.1064 − .03173)×103 = .07467 ×103
com dígito de guarda:
x1 + x 2 =.7467 x 10 2
sem digito de guarda:
x1 + x 2 =.7460 x 10 2
acordo com a equação:
EAz = f ( x + EAx , y + EAy ) − f ( x, y )
que pode assumir a forma [Maurer, 1968]:
Exemplo:
x1 = .2631×102 x2 =.1976×102
2
x1 + x2 =.0655× x10 ∴ x1 + x2 =.655
0{
EAz =
1
×10
zero
não
significativo
∂f
∂f
EAx +
EAy + η1 EAx + η 2 EAy
∂x
∂y
onde o binômio η1 EAx + η 2 EAy corresponde a um infinitésimo de
ordem superior em relação a EAx e EAy . De uma forma geral, o erro
Exemplo:
x1 =.999 × 10 x2 = .999 × 1099
1
424
3
absoluto de z, EAz , será obtido com uma aproximação suficiente pela
diferencial total da função f, ou seja:
Supor que é o maior valor possível na representação da máquina:
EAz =
10
∂f
∂f
EAx +
EAy
∂y
∂x
No caso geral, se z é uma função de n variáveis, x1 , x 2 , K , x n ,
segundo uma determinada “lei”, ou seja:
EAg =
z = f ( x1 , x 2 , K x n )
Substituindo os valores de l e T , e dos respectivos erros absolutos,
considerando a situação de máximo erro possível, obtém-se:
com os erros absolutos das variáveis x1 , x 2 , K , x n sendo dados por
EAx1 , EAx2 , K , EAxn , o erro absoluto no cálculo de z, EAz , será
EAg =
obtido a partir da diferencial total:
EAz =
g=
EAg = 10,363
4π 2 l 4π 2 100
=
= 986,961 cm 2 = 9,86961 m 2
s
s
T2
22
EAg
10,363
ER g =
=
= 0,0105
g
986,961
ou ER g = 1,05%
Exercício:
Considere o problema de cálculo do seno de um ângulo de um
triângulo retângulo. Obter uma expressão para o erro absoluto
incorrido no cálculo do seno, a partir dos valores das medidas da
hipotenusa e do cateto oposto e dos respectivos erros absolutos.
Aplicar para os seguintes valores de medidas: 5 cm (hipotenusa) e
Resolução:
⇒
⇒
g=
a partir dos valores medidos para l e T . Considerar l = 100 cm , com
EAl ≤ 0,05cm , e T = 2 s , com EAT ≤ 0,01s [Maurer, 1968].
l
g
4π 2
8π 2 100
×
0
.
05
−
× (− 0.01)
22
23
O erro relativo para o valor aproximado de g pode ser calculado
facilmente a partir da definição de erro relativo. Inicialmente calculase o valor aproximado2 de g para os valores de l e T dados:
∂f
∂f
∂f
EAx1 +
EAx2 + K +
EAxn
∂x1
∂x 2
∂x n
Exemplo: determinar o valor de g a partir da fórmula do pêndulo
simples, que é dada por:
l
T = 2π
g
T = 2π
∂ 4π 2 l
∂ 4π 2 l
4π 2
8π 2 l
2 EAl +
2 EAT = 2 EAl − 3 EAT
∂l T
∂T T
T
T
4π 2 l
T2
Como g é função de l e T , diferenciando-se em relação a estas
variáveis, obtém-se:
2
O cálculo apresentado aqui não considera um sistema de aritmética de ponto
flutuante específico, dado que a ênfase é obter os valores dos erros envolvidos.
11
1.5. EFEITOS NUMÉRICOS
4 cm (cateto oposto), admitindo um erro absoluto nas medidas de
0,5 mm (em módulo).
Resp.: 0.018
(Adaptado de [Maurer, 1968]).
Nos processos em que métodos numéricos são aplicados, o seguintes
efeitos podem ser observados [FRANCO, 2006]:
•
Exercício:
Considere o problema de se determinar a distância c entre dois pontos
A e B, a partir de um ponto de observação C, como mostra a figura a
seguir:
•
•
•
Cancelamento subtrativo
Propagação de erros
Instabilidade Numérica
Mal condicionamento
Os efeitos da propagação de erros nas operações foram estudados na
seção anterior. Nesta seção consideramos os outros efeitos, conforme
discutidos em [FRANCO, 2006].
B
a
c
a) Cancelamento subtrativo
A
Exemplo:
Seja calcular
b
C
Para o triângulo ABC mostrado medem-se a hipotenusa a, o cateto b e
o ângulo α cujo valor é de 45°. A distância c pode ser calculada por
9876 - 9875 , em um sistema com β = 10 e t = 10.
9876 = 0.9937806599 × 10 2
9875 = 0.9937303457 × 10 2
Portanto,
9876 − 9875 = 0.0000503142 × 10 2
Normalizando:
−2
9876 − 9875 = 0.503142 0000
{ × 10
uma das três fórmulas a seguir: a) c = a 2 − b 2 ; b) c = a sen α ; c)
c = b tg α . Supondo que o processo de medição dos lados está
sujeito a um erro de 1% e a do ângulo, a um erro de 2%, verificar qual
das três fórmulas é a melhor para o cálculo de c.
zeros não
significativos
Observe-se que se os quatro dígitos significativos após a décima casa
decimal não fossem “perdidos”, o resultado seria:
9876 − 9875 = 0.5031418680 × 10 −2
Resp.: Erro no cálculo de c: a) 0.03; b) 0.026; c) 0.041. Portanto a
fórmula (b) é a melhor para o cálculo.
(Adaptado de [Maurer, 1968]).
12
Para este exemplo, em particular, pode-se obter um resultado mais
preciso, utilizando-se da transformação mostrada a seguir [FRANCO,
2006]:
x− y=
∴
(
x−
(
y)
9876 − 9875 =
x+ y
x+ y
)=
Aplicando-se a relação de integração por partes:
produz-se:
I n = e −1 x n e x
[
x− y
x+
9876 − 9875
9876 + 9875
=
∫ udv = uv − ∫ vdu ,
y
1
] − ∫ nx
1
0
0
1
e dx = e −1e − ne −1 ∫ x n −1e x dx = 1 − nI n −1
0
n −1 x
∴ I n = 1 − nI n −1 , n = 1,2,K
1
0,1987511006 × 10 3
1
I0 = e
−1
∫e
x
dx = e −1 (e − 1) = 1 − e −1 = 0.6321
0
∴
9876 − 9875 = 0,5031418680 × 10 -2
Conhecendo-se o valor I 0 , calculam-se os demais valores da
seqüência:
I 1 = 1 − I 0 = 1 − 0.6321 = 0.3679
b) Instabilidade Numérica
I 2 = 1 − 2 I 1 = 1 − 2 × 0.3679 = 0.2642
I 3 = 0.2074 I 4 = 0.1704 I 5 = 0.1480 I 6 = 0.1120 I 7 = 0.2160
Algoritmos estáveis são os algoritmos cujos erros intermediários
ocorridos nos cálculos têm um efeito desprezível no resultado final,
podendo até mesmo, em alguns casos, se cancelarem mutuamente,
pelo menos em parte. Diz-se que uma instabilidade numérica ocorre
se os erros intermediários têm uma influência muito grande no
resultado final.
Observa-se que o valor obtido para I 7 está errado, pois a seqüência
I n é decrescente. Observe-se que:
1
1
1
I n = e −1 ∫ x n e x dx < e −1 max(e x ) ∫ x n dx ⇒ I n <
1
424
3
n +1
0
0
0≤ x ≤1
Exemplo [FRANCO, 2006]:
Seja resolver:
∴ I7 <
1
I n = e −1 ∫ x n e x dx
0
1
= 0.125
7 +1
Diz-se que neste caso ocorreu uma instabilidade numérica. Observese se considerássemos 5 casas decimais nos cálculos, a instabilidade
iria ocorrer no cálculo de I 9 :
Resolução:
Fórmula de recorrência para I n :
13
∴ ε n = (− 1) n!ε 0
n
n
In
n
In
0
0.63212
5
0.14560
1
0.36788
6
0.12640
2
0.26424
7
0.11520
3
0.20728
8
0.07840
4
0.17088
9
0.29440
Observa-se, portanto, que, o crescimento do erro é dado pelo fatorial
do número de passos considerados.
Um relação de recorrência instável na direção crescente de n não é
necessariamente instável também na direção decrescente de n.
Considere-se, por exemplo, a partir da relação para cálculo de I n :
I n = 1 − nI n −1 , obtém-se:
I n −1 =
Vamos supor que I 0 seja afetado por um erro inicial ε 0 e que todas as
operações subseqüentes sejam calculadas exatamente. Assim, o erro
no cálculo de I n pode ser calculado como indicado a seguir:
1 −I n
n
Observe-se que I n → 0 quando n → ∞ . Assumindo I 20 = 0 , obtémse, utilizando a expressão acima:
ε n = I n − I n = 1 − nI n−1 − (1 − nI n −1 ) = − n(I n−1 − I n−1 ) = nε n −1 (−1)
14243
ε n −1
Já o cálculo de ε n −1 é efetuado como indicado a seguir:
ε n −1 = I n −1 − I n −1 = 1 − (n − 1) I n − 2 − [1 − (n − 1)I n − 2 ] = −(n − 1)(I n − 2 − I n − 2 )
14243
ε n− 2
∴ ε n −1 = (n − 1)ε n − 2 (− 1)
De modo análogo, obtém-se para ε n − 2 :
ε n − 2 = (n − 2)ε n −3 (− 1)
n
In
n
In
n
In
n
In
19
0,05000
14
0,06273
9
0,09161
4
0,17089
18
0,05000
13
0,06695
8
0,10093
3
0,20728
17
0,05278
12
0,07177
7
0,11238
2
0,26424
16
0,05572
11
0,07735
6
0,12680
1
0,36788
15
0,05902
10
0,08388
5
0,14553
0
0,63212
c) Mal condicionamento
Ou seja:
ε n = nε n −1 (− 1) = n(n − 1)ε n − 2 (− 1)2 = n(n − 1)(n − 2 )ε n −3 (− 1)3 = L
Problemas mal condicionados ou críticos são problemas que possuem
infinitas soluções ou que não possuem nenhuma solução.
= n(n − 1)(n − 2 )L(2 )(1)ε 0 (− 1)
n
14
Exemplo;
Seja resolver o sistema linear:
x+ y =2
x + 1.01y = 2.01
Solução: x = 1 , y = 1 .
Alterando-se o sistema para:
x+ y =2
x + 1.01y = 2.02
Solução: x = 0 , y = 2 .
Observa-se, portanto, que uma pequena modificação em um dos
coeficientes implica em uma grande mudança na solução do sistema.
Apresenta-se, a seguir, a interpretação geométrica, para o primeiro
sistema. As equações das retas são as seguintes:
y = 2− x
Exemplo:
Seja resolver o problema de valor inicial:
y ′′ = y
a, b: constantes.
y (0) = a
y ′(0) = b
2.01 − x
y=
1.01
Plotando-se as duas retas, obtém-se o gráfico mostrado a seguir;
Resolução:
y ( x) = C1e x + C 2 e − x
y ′( x) = C1e x − C 2 e − x
Para a = 1 e b = −1 , as equações das condições iniciais se tornam:
y (0) = C1 + C 2 = 1
⇒ C1 = 0 e C 2 = 1
y ′(0) = C1 − C 2 = −1
15
∴ y ( x) = e
x = f x × 10 e
−x
1
≤ f x <1
10
Observe-se que y ( x) → 0 quando x → ∞ .
ER x < 10 −t +1 (truncamento)
Para a = 1 e b = −1 + δ , com δ arbitrariamente pequeno, o sistema
1
ER x < 10 −t +1 (arredondamento)
2
para determinação das constantes C1 e C 2 se torna:
1
C1 + C 2 =
C1 − C 2 = − 1 + δ
b) Sistema Binário de ponto flutuante
x = f x × 2e
δ
δ
cuja solução é: C1 =
e C 2 = 1 − . Substituindo na equação de
2
2
y ( x) , obtém-se:
y ( x) =
δ x δ −x
δ
e + 1 − e = e − x + (e x − e − x ) = e − x
2
2
2
e x − e−x
+ δ
2
1
≤ fx <1
2
ER x < 2 −t (arredondamento)
ER x < 2 −t +1 (truncamento)
c) Sistema Hexadecimal de Ponto Flutuante
∴ y ( x) = e − x + δ senh x
x = f x × 16 e
Observe-se que neste caso y ( x) → ∞ quando x → ∞ . Ou seja, houve
uma grande mudança na característica matemática da solução.
1
≤ f x <1
16
ER x < 8 × 16 −t (arredondamento)
ER x < 16 × 16 −t (truncamento)
1.6. REPRESENTAÇÕES EM DIFERENTES SISTEMAS DE
NUMERAÇÃO
Exercício: obter as expressões dos erros relativos para os sistemas
binário e hexadecimal.
a) Sistema decimal flutuante
16
Diz-se que um computador digital tem uma precisão de t dígitos se há
t dígitos na mantissa no número de ponto flutuante. A precisão está
relacionada com o número de algarismos significativos. Também se
diz que um computador tem t dígitos significativos se, quando os
números são truncados, o limite do erro relativo é 10− t +1 .
Exemplo: IBM 360 e 370
mantissa com 6 dígitos hexadecimais
p = ? (dígitos significativos)
BASE
DÍGITOS
2
8
10
16
0,1
0,1,2,...,7
0,1,2,...,7,8,9
0,1,2,...,9,A,B,C,D,E,F,
DENOMINAÇÃO
binário
octal
decimal
hexadecimal
Considere-se inicialmente o número 2526 (base 10), denotado aqui
por 252610 Este número pode ser escrito em termos de potências da
base como:
sist. decimal = 10− td +1 = 10− p +1
sist. hexadecimal = 16 × 16 −th = 16 × 16−6 = 16−5
252610 = 2 ×103 + 5×102 + 2 ×101 + 6 ×100
∴ 10 − p+1 = 16 −5
(− p + 1) ln 10 = −5ln 16
Mudança de uma base para outra
− 5 ln 16
ln 10
5 ln 16
p = 1+
⇒ p≅7
ln 10
− p +1 =
Exercício: computador binário com 27 bits na mantissa; p = ?
(dígitos decimais significativos).
Para conversão de um número da base 10 para qualquer uma das
outras bases, divide-se o número pela base, anotando-se o quociente e
o resto. Caso o quociente seja diferente de zero, este deverá ser
dividido pela base, anotando-se os novos valores de quociente e resto.
O processo deve ser continuado até que se obtenha um quociente igual
a 0. O número, na base de interesse, terá como dígitos os restos
obtidos, justapostos em ordem contrária à de geração.
Apêndice ao capítulo: breves considerações sobre sistemas de
numeração
Exemplo: Converter 29 10 para os sistema binários, octal e
hexadecimal.
A tabela a seguir sumariza algumas das características de algumas
bases de sistemas de numeração:
17
29
(1)
(
111012 = 1 × 24 + 1 × 23 + 1 × 2 2 + 0 × 21 + 1 × 20
2
2
(0)
7
2
(1)
3
2
(1)
1
2
(1)
0
29
8
(5)
3
8
(3)
0
0
)
10
= 2910
)
358 = 3 × 8 + 5 × 8 = 2910
29 10 = 111012
14
(
= (1 × 16
1
1016
1
)
+ 13 × 160 = 2910
Para conversão da representação na base 2 para as bases 8 e 16, basta
agrupar os bits da representação binária em conjuntos de
3 ( 2 3 = 8) e 4 ( 2 4 = 16) bits, respectivamente, como ilustrado no
exemplo a seguir.
Ex.: obter as representações nas bases 8 e 16 para o número 111012
29 10 = 358
011101
{{
22 + 2 0 = 5
21 + 2 0 = 3
0001 1101
123 123
29
16
(13)
1
16
(1)
0
29 10 = 1D16
⇒ 111012 = 358
2 3 + 2 2 + 2 0 = 13
20 = 1
⇒ 111012 = 1D16
Os exemplos a seguir ilustra a conversão de números fracionários, de
base 10 para base 2.
Para conversão da representação nas bases 2, 8 e 16, para a base 10,
basta utilizar a representação do número em termos de potência das
bases, como ilustrado no exemplo a seguir.
Ex.: obter a representação, na base 2, do número 0.687510
Ex.: mostrar como são convertidos as representações 111012 ,
358 e 1016 para base 10
18
0.6875
0.375
0.75
0.50
0.00
×
×
×
×
×
2
2
2
2
2
CAPÍTULO 2
= 1. 375
= 0. 75
= 1. 50
= 1. 00
= 0. 00
RESOLUÇÃO NUMÉRICA DE EQUAÇÕES
INTRODUÇÃO
Em muitos problemas de Ciência e Engenharia há a necessidade de se
determinar um número ρ que anule uma determinada função F(x), isto
é, F(ρ ) = 0. Este número ρ é chamado de raiz da equação F(x) = 0
ou zero da função y = F (x) .
∴ 0.678510 = 01011
.
2
Observar que a conversão para a base 10 segue o mesmo esquema
apresentado para inteiros, ou seja:
0.10112 = (1 × 2−1 + 0 × 2−2 + 1 × 2−3 + 1 × 2−4 )10 = 0.687510
Classificação:
(i) eq. algébricas: Ex.: x 4 − 5x 3 + 6 x 2 + 4 x − 8 = 0
(ii) eq. transcendentes: Ex.: x sen x + ( x 2 + 4)e x = cos x
Ex.: obter a representação, na base 2, do número 0.110
0.1 × 2 = 0.2
0.2 × 2 = 0.4
0.4 × 2 = 0.8
0.8 × 2 = 1.6
0.6 × 2 = 1.2
0.2 × 2 = 0.4
0.4 × 2 = 0.8
0.8 × 2 = 1.6
0.6 × 2 = 1.2
.
01
. 10 = 0.00011001100...
Etapas no cálculo de uma aproximação para a raiz:
(i) isolamento da raiz: determinação de um intervalo [a,b] o menor
possível contendo uma e somente uma raiz da equação F(x) = 0
(ii) melhoramento do valor da raiz aproximada até o grau de exatidão
requerido.
EQUAÇÕES TRANSCENDENTES
2.1.1 ISOLAMENTO DE RAÍZES - MÉTODO GRÁFICO
Notar que o número 01
. 10 não tem representação exata na base 2.
Uma raiz real de uma equação F ( x) = 0 é a abscissa de qualquer
ponto no qual a função y = F (x) intercepta o eixo Ox :
19
⇒ g(x0) - h(x0) = F(x0) = 0
⇒ ρ = x0
Ex.: seja y = F ( x) = e x − sen x − 2
Exemplo: isolar todas as raízes da equação
1
F ( x) = x 2 − sen x − 1
0.5
= {
x 2 − (sen x + 1)
1424
3
g ( x)
-2
-1
1
2
3
h( x)
4
Gráfico de g ( x) = x 2 :
-0.5
4
-1
3
Como se observa, para esta equação, ρ ≅ 1.06 .
2
Pode-se também identificar duas funções g(x) e h(x) a partir da
função F(x), impondo-se a condição de que F(x) = g(x) - h(x).
Constroem-se os gráficos de y1 = g(x) e de y2 = h(x). Estes se
interceptam num ponto cuja abscissa é x = x0:
1
-2
20
-1
1
2
Gráfico de h(x) = sen x + 1:
a)4 cos( x) − e 2 x = 0
b) x 3 − 9 x + 3 = 0
c) x log x − 1 = 0
x
d ) − tg x = 0
2
e) 2 x − 3 x = 0
2
1.5
1
0.5
-2
-1
1
2
2.1.2 GRAU DE EXATIDÃO DA RAIZ
Uma vez isolada uma raiz num intervalo [a,b] passa-se a calculá-la
através de métodos numéricos. Estes métodos fornecem uma
seqüência {xi}de aproximações cujo limite é a raiz exata ρ.
Gráficos de g(x) e h(x) superpostos:
4
3
TEOREMA: Seja ρ uma raiz isolada exata e ρ uma raiz aproximada
da equação F(x)=0, com ρ e ρ pertencentes ao intervalo [a,b] e
F ' ( x) ≥ m > 0, para todo x no intervalo [a, b] .
2
1
-2
-1
Então a seguinte desigualdade se verifica:
1
2
ρ−ρ ≤
Como se observa, há duas raízes reais, localizadas nos seguintes
intervalos:
ρ ∈ ( −1,0) e ρ ∈ (1, 2) .
1
2
F (ρ )
m
Exemplo: Sendo F ( x) = x 2 − sen( x) − 1 , delimitar o erro cometido
com ρ = 1.4 no intervalo [1,0,1,5].
Exercício:
Localize, graficamente, as raízes das equações abaixo:
Resolução:
21
F ( x) = x 2 − sen( x) − 1 ⇒ F ' ( x) = 2 x − cos( x )
( i ) F ( xn ) ≤ L
Designando y1 = 2 x e y2 = cos( x ), sobrepondo-se os gráficos destas
duas funções, obtém-se:
Observações:
(a)
4
3
2
1
0.5
1
1.5
2
Observa-se que o menor valor (m) de F’(x) no intervalo [1,1.5] ocorre
em x = 1.0, ou seja:
m = (2)(1) – cos(1) = 1.460
(b)
F (ρ )
F (1,4) 0,025
=
= 0,017
m
1,460
1,46
∴ ρ − ρ = 1,4 − ρ ≤ 0,017 ⇒ 1.383 ≤ ρ ≤ 1,417
∴ ρ−ρ ≤
=
Observa-se que o cálculo de m é difícil de ser efetuado na maioria dos
casos. Por esta razão, no cálculo de uma aproximação para uma raiz
exata ρ de uma equação F(x) = 0, a cada aproximação obtida, xn,
utiliza-se um dos critérios abaixo para comparação do resultado obtido
com uma tolerância L prefixada:
22
(ii ) xn − xn −1 ≤ L
(iii )
xn − xn −1
≤L
xn
O MÉTODO DA BISSECÇÃO
Seja y = F(x) uma função contínua num intervalo [a,b] e F(a). F(b) < 0
Interpretação geométrica:
Construção de uma seqüência { xi } = x 0 , x1 ,..., x n −1 , x n , tomando-se
ρ = x n quando algum critério escolhido dentre os anteriores, por
exemplo, x n − x n −1 ≤ L , for satisfeito:
Sob as hipóteses do teorema anterior, se h = F ' ( x) existe e preserva o
sinal em (a, b), então este intervalo contém um único zero de y = F(x).
Na aplicação do método, a cada xi obtido, (i ≥ 1), calcula-se
∈i = x i − x i −1 e verifica-se ∈i satisfaz alguma condição especificada.
Teorema:
Seja y = F(x) uma função contínua num intervalo [a,b]. Se
F (a ) × F (b) < 0 então existe pelo menos um ponto x = ρ entre a e b
que é zero de y = F(x).
F ' ( x) > 0, ∀x ∈ [a, b]
23
F ' ( x) < 0, ∀x ∈ [a, b] .
Algoritmo
Adaptado para determinar uma aproximação para a raiz da equação
F ( x ) = x 2 − sen x − 1 = 0 .
Aplicação do método da bisseção:
(a, b)
(a, xi ) se F (a) × F ( xi ) < 0
F (a) × F (b) < 0 ou
xi = ponto médio ( xi , b) se F ( xi ) × F (b) < 0
123
novo
int
ervalo
Início
Defina F(x) = x^2-sen(x)-1
Solicite os extremos do intervalo, a e b
Leia a, b
Solicite a precisão P
Leia P
Xm=0
Repita
Xma=Xm
Xm=(a+b)/2
Se f(a)*f(xm) < 0
Então b=xm
Senão se f(a)*f(xm) > 0
Então a=xm
Senão
Escreva ‘raiz = ‘, xm
Pare
Fim Se
Fim Se
Até que |xm-xma| ≤ P
Escreva “aproximação”, (xm+xma)/2
Fim
Exemplo:
Determinar, usando o método da bisseção uma aproximação para a
raiz da equação
F ( x) = x − 5e − x = 0 no intervalo (1,2), com ε ≤ 0.01
Resolução:
i
a
b
xi
F(a)
F(b)
F(xi)
0
1
2
1.5
-0.8
0.7
0.1
1
1
1.5
1.25
-0.8
0.1
-0.3
2
1.25
1.5
1.38
-0.3
0.1
-0.08
ε i = x i − x i −1
ε = x − x = 0.25
1
i
ε = x − x = 013
.
2
3
1.38
1.5
1.44
-0.08
0.1
0.02
4
1.38
1.44
1.41
-0.08
0.02
-0.03
5
1.41
1.44
1.43
-0.03
0.02
-0.0007
6
1.43
1.44
1.44
-0.0007
0.02
0.02
0
2
1
ε = x − x = 0.06
2.1.4 MÉTODO DA ITERAÇÃO LINEAR (MIL)
ε = x − x = 0.03
O MIL consiste em transformar a equação F(x) = 0 na equação
x = ϕ ( x) , tal que F ( x ) = x − ϕ ( x ) = 0 , onde ϕ ( x ) é chamada de função
de iteração.
3
4
3
4
2
3
ε = x − x = 0.02
5
5
4
ε = x − x = 0.01
6
6
5
Suponha que xo corresponda a uma primeira aproximação de ρ;
geramos uma seqüência do seguinte modo:
Assume-se para aproximação da raiz o último valor obtido para xi, ou
seja, ρ = 1.44 .
24
xo
∴ϕ 2 ( x ) = sen x
x1 = ϕ ( x0 )
(c ) x 2 − sen x = 0
x 2 = ϕ ( x1 )
x/ 2 − sen x − x/ 2 = − x 2
x n +1 = ϕ ( x n )
sen x = x 2
Se {x n } é uma seq. convergente, então ∃ ρ tal que
x = arc sen x 2
lim x n = ρ
∴ϕ 3 ( x ) = arc sen x 2
n→∞
Como ϕ é contínua:
ρ = lim x n = lim ϕ ( x n −1 ) = ϕ (lim x n−1 ) = ϕ ( ρ )
n →∞
n →∞
Exemplo:
Determinar
n→∞
aproximação para a raiz da equação
F ( x ) = x − sen x − 1 = 0 no intervalo [1.0, 1.5], com grau de exatidão
Portanto, quando n → ∞, x n +1 = ϕ ( x n ) → ρ = ϕ ( ρ ). Ou seja, ρ = ρ .
uma
2
∈≤ 10 −3 usando o M.I.L.
Exemplo:
Seja F ( x) = x 2 − sen( x) = 0 . Obter funções de iteração para esta
equação.
Resolução:
Função de iteração:
F ( x ) = x 2 − sen x − 1 = 0
Resolução:
⇒ x 2 = sen x + 1
2
(a) x − sen x = 0
⇒ x = sen x + 1
x + x 2 − sen x = x
∴ϕ (x ) = sen x + 1
∴ϕ1 ( x ) = x + x − sen x
2
Processo Iterativo:
xn +1 = ϕ (xn ) ⇒ xn +1 = sen ( xn ) + 1 ε n = xn − xn −1 ≤ 10 − 3
(b ) x 2 − sen x = 0
x 2 − sen x + sen x = sen x
xo = 1.3
x = ± senx
x1 = ϕ ( xo ) = sen(1.3) + 1 = 1.4013
25
∴x0 = 1.5
ε1 = x1 − xo = 1.4013 − 1.3 = 0.1013 > 0.001
x2 = ϕ ( x1 ) = sen (1.4013) + 1 = 1.4091
x1 =ϕ ( x0 ) = ϕ (1.5) =
ε 2 = x2 − x1 = 1.4091 − 14013 = 0.0078 > 0.001
5
= 3.333
1.5
5
= 1. 5
3.333
5
x3 = ϕ ( x 2 ) =
= 3.333
1. 5
5
∴ x n +1 = ϕ ( x n ) =
não converge para a raiz da equação
xn
x2 = ϕ ( x1 ) =
x3 = ϕ ( x2 ) = sen(1.4091) + 1 = 1.4096
ε 3 = x3 − x2 = 1.4096 − 14091 = 0.0005 < 0.001
∴ ρ = 14096
.
com grau de exatidão ≤ 10 −3
2
Obs.: F ρ = (1.4096) − sen(1.4096) − 1 = −6.38 x10 −5 .
()
F(x ) = x 2 − a = 0
(b) tentativa com uma função de iteração mais trabalhada:
a
x2 − a = 0 ⇒ x2 = a ⇒ x =
x
a
1
a
x + x = + x ∴x = x +
x
2
x
1
a
xn +1 = ϕ ( xn ) ∴ xn +1 = xn +
2
xn
Exemplo:
Seja determinar, iterativamente, uma aproximação para 5 .
(a) tentativa com a função de iteração simplificada:
x2 − a = 0
(função de iteração : x = ϕ (x) )
x2 = a
a
a
ϕ ( x) =
x=
x
x
a = 5
x0 = 1.5
x n +1 = ϕ ( x n )
a = 5
x0 = 1.5
TOLERÂNCIA : ε ≤ 10-3
a cada passo : ε n = xn − xn −1
26
1
a
xn +1 = xn +
2
xn
x0 = 1.5
1
2
5
x
ϕ 2 ( x ) = x+ converge
1
5 1
5
= 2.417
x1 = ϕ ( x0 ) = x0 + = 1.5 +
x0 2
2
1.5
ε1 = 2.417 − 1.5 = 0.917
Por quê? Para concluir sobre isto, basta verificar o comportamento do
M.I.L. geometricamente. Observe-se inicialmente a situação ilustrada
na figura a seguir:
1
5
= 2.243
x2 = ϕ ( x1 ) = 2.417 +
2
2.417
ε = 2.443 − 2.417 = 0.174
2
F (x ) = 0
x = ϕ (x )
x0
M .I .L.
x1 = ϕ ( x0 )
x2 = ϕ (x1 )
x3 = ϕ ( x2 )
1
5
= 2.236
x3 = ϕ ( x2 ) = 2.243 +
2
2.243
ε = 2.236 − 2.243 = 0.007
3
1
5
= 2.236
x4 = ϕ ( x3 ) = 2.236 +
2
2.236
ε = 2.236 − 2.236 < 10− 3
4
∴ ρ = 2.236 ⇒ ρ ≅ 2.236
Obs.:
x = ϕ (x ) ⇒ x − ϕ (x ) = 0
F ( x ) = g ( x ) − h(x ) = 0
5 = 2.2360679 K
onde : g(x ) = x
h (x ) = ϕ ( x )
xn → ρ
pela direita
y = g (x ) é bissetriz!
(g ' (x ) = 1)
Convergência no M.I.L.
∴ ϕ '( x ) < 1 numa vizinhança de ρ.
Para o caso da equação x = 5 , com x o = 1.5 , observamos que:
ϕ1 ( x ) =
5
x
Observe-se agora a situação ilustrada na figura a seguir:
não converge
27
Teorema da Convergência de M.I.L.:
Seja xo uma aproximação para a raiz ρ da equação F(x) = 0 numa
vizinhança I = [ρ − δ , ρ + δ ]. Seja ϕ uma função de iteração para a
equação F(x) = 0 e suponha-se que ϕ e ϕ ' sejam contínuos em I.
Então, se ϕ ' ( x ) < 1, ∀x ∈ I , a sequência gerada por
xn +1 = ϕ ( xn ), n = 0,1,2,3, K converge para ρ.
Observação: como o valor de ρ é desconhecido, substitui-se o valor de
xo na derivada para se concluir sobre a convergência.
Esboço da demonstração:
ϕ ' ( x) > 1 numa vizinhança de ρ .
M.I.L.
xn − ρ = ϕ ( xn − 1 ) − ϕ ( ρ )
A figura a seguir ilustra a situação de “convergência alternada”.
Teorema do valor médio:
ϕ ' ( x) < 1
∴ xn − ρ = ϕ ( xn −1 ) − ϕ ( ρ ) = ϕ ' (ε ) xn −1 − ρ
28
Seja L o valor máximo de ϕ ' ( x ) no intervalo I, ou seja, ϕ ' ( x ) ≤ L no
(b ) ϕ 2 (x ) = 1 x + a
intervalo I.
∴ xn − ρ ≤ L xn −1 − ρ
2
x
1
2
a
x2
ϕ 2' ( x ) = 1 −
Do mesmo modo
ϕ 2' ( x0 ) =
xn −1 − ρ ≤ L xn − 2 − ρ ⇒ xn − ρ ≤ L2 xn − 2 − ρ
continuando
∴ xn − ρ ≤ Ln x0 − ρ
5 1
1
1 −
= (1 − 2.222 ) = 0.611 < 1
2 1.96 2
ϕ 2 converge para ρ
Se L 〈 1 em todo intervalo, ∀ x0 ε I , n aumentando ⇒ xn → ρ
∴ ϕ ' ( x ) < 1 o processo converge
∀ x ε I
ϕ ' ( x ) > 1 o processo diverge
Observações:
(1) A maior dificuldade de M.I.L. está em encontrar uma função
de iteração ϕ satisfazendo o critério de convergência.
(2) O teste ϕ ' ( x0 ) < 1 pode levar a um engano se x0 não estiver
suficientemente próximo da raiz.
(3) A velocidade de convergência dependerá de ϕ ' ( ρ ) : quanto
menor este valor, mais rapidamente o processo convergirá.
Exemplo: estudar a convergência das funções de iteração do exemplo
anterior.
Resolução:
F (x ) = x 2 − a = 0
a=5
x0 = 1.5
Exemplo:
F (x ) = x 2 − a = 0
a
ϕ (x ) =
x
a = 5
(ρ ≅ 2.2360679)
x0 = 3
(a )ϕ1 (x ) = a
x
a
x2
a
5
5
= 2 =
=
= 2.222 > 1
2
x0 (1.5)
2.25
ϕ1 não converge para ρ
ϕ1' (x ) = −
ϕ1' ( x0 )
ϕ ' ( x0 ) = −
29
a
5
= = 0.555 < 1
2
x0
9
ϕ 3' ( x ) =
Aplicação:
x0 = 3
−1
1− x4
× 2x
No ponto x0 = 0.9 :
5
= 1.667
3
5
x2 = ϕ ( x1 ) =
= 2.999
1.667
5
= 1.667
x3 = ϕ (x2 ) =
2.999
x1 = ϕ ( x0 ) =
ϕ1' ( x0 ) = ϕ1' (0.9) = 2 × (0.9) + 1 − cos(0.9) = 2.178 > 1
ϕ 2' (x 0 ) = ϕ 2' (0.9) =
ϕ 3' ( x0 ) = ϕ 3' (0.9) =
não converge!
cos(0.9 )
2 sen (0.9 )
2 × 0.9
1 − (0.9 )
4
=
0.622
= 0.351 < 1
2.0885
= 3.069 > 1
Exemplo: estudar a convergência das funções de iterações obtidas
anteriormente para a equação
∴ Somente ϕ 2 (x ) deverá convergir.
F ( x ) = x 2 − sen x = 0 para x0 = 0.9 ,
Isolamento da raiz:
obter uma aproximação para a raiz da equação.
F ( x ) = x 2 − sen x
= g (x ) − h(x )onde g ( x ) = x 2 e h( x ) = sen x.
Resolução:
ϕ1 ( x ) = x 2 + x − sen x
ϕ 2 ( x ) = sen x
ϕ 3 ( x ) = arc sen x 2
funções de iteração
Derivadas:
ϕ1' ( x ) = 2 x + 1 − cos x
ϕ 2' ( x ) =
1
2 sen x
Aplicação de M.I.L x0 = 0.9 e ϕ ( x ) = ϕ 2 ( x ) = sen x
× cos x
30
ε 〈 10−3
x0 = 0.9
x1 = ϕ ( x0 ) = sen (0.9 ) = 0.885
lim
ε1 = 0.015
k →∞
x2 = ϕ (x1 ) = sen (0.885) = 0.879 ε 2 = 0.006
ε k +1
εk
p
=c
então p será a ordem de convergência do método aplicado.
x3 = ϕ ( x2 ) = sen (0.879) = 0.878 ε 3 = 0.001
x 4 = ϕ (x3 ) = sen (0.878) = 0.877 ε 4 = 0.001
Teorema:
A ordem de convergência do MIL é p = 1 (linear).
x5 = ϕ ( x 4 ) = sen (0.877 ) = 0.877 ε 5 < 10 -3
∴ ρ = 0.877 é uma aproximação para ρ .
Do teorema de convergência:
x k +1 − ρ = ϕ ′ ε xk ( x k − ρ ) , ε xk ∈ ( x k , ρ )
( )
Observação:
2
F (ρ ) = F (0.877 ) = (0.877 ) − sen (0.877 ) = 3.051x10 −4
Assim,
x k +1 − ρ
Ordem de Convergência
xk − ρ
A ordem de convergência de um método fornece um medida da
velocidade com que as iterações produzidas pelo método aproximamse da solução exata. Assim, quanto maior for a ordem de
convergência, mais rapidamente se aproximará da solução exta da
equação [FRANCO, 2006].
( )
≤ ϕ ′ ε xk ≤ M
Logo a definição é satisfeita com p = 1 e c = M .
Observação:
Para k suficientemente grande:
Definição:
Seja {x k } a seqüência gerada por uma aplicação de um método
numérico e ε k = x k − ρ , onde x k representa a aproximação obtida na
k-ésima iteração do método e ρ , a solução exata. Caso existam um
número p ≥ 1 e uma constante c > 0 , tais que:
ε k +1 ≅ c ε k
⇒
31
p
⇒
ε k +1 ε k
≅
εk
ε k −1
ε k ≅ c ε k −1
p
⇒
p
ε
log k +1
εk
p≅
log ε k
ε k −1
Exemplo: Determinar a raiz positiva da equação:
F ( x ) = 4 cos(x ) − e x = 0
Utilizando o MIL. Estimar também a ordem convergência da
aplicação do método a esta equação.
Verificação quanto à convergência:
ϕ ′( x ) =
−1
( 4)
x
1− e
Resolução:
Isolamento da raiz pelo método gráfico:
2
( 4 )′ =
x
×e
− ex
( 4)
x
4 1− e
2
Para x0 = 0,9 , tem-se:
ϕ ′( x0 ) =
− e 0.9
( 4)
0.9
4 1− e
2
=
2.4596
= 0.78 < 1
3.1544
Aplicação do MIL:
x0 = 0,9
( 4 ) = 0.9085
x1 = arc cos e
0.9
∈1 = x1 − x0 = 0.9085 − 0.9 = 0.0085
A tabela a seguir, construída no EXCEL, apresenta o resultado da
aplicação do MIL, com a função de iteração anterior, para uma
precisão ε ≤ 10 −3 . A última coluna da tabela apresenta uma
estimativa da ordem de convergência – valor de p – obtida a partir da
expressão:
ε
log k +1
εk
p≅
log ε k
ε
k −1
Como se vê, há duas raízes ρ1 ∈ (− 2,−1) e ρ 2 ∈ (0,1) . A seguir
obtém-se uma função de iteração para resolução da equação:
4 cos( x ) − e x = 0
⇒
∴
⇒
( 4)
ϕ ( x ) = arc cos(e 4 )
x = arc cos e
4 cos( x ) = e x
⇒
cos( x ) = e
x
4
x
x
32
i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
xi
0,9000
0,9085
0,9018
0,9071
0,9030
0,9062
0,9037
0,9057
0,9041
0,9053
0,9044
0,9051
0,9045
0,9050
0,9046
0,9049
0,9047
0,9049
0,9047
ϕ ( xi )
∈i
0,9085
0,9018
0,9071
0,9030
0,9062
0,9037
0,9057
0,9041
0,9053
0,9044
0,9051
0,9045
0,9050
0,9046
0,9049
0,9047
0,9049
0,9047
0,9048
0,0085
0,0067
0,0053
0,0041
0,0033
0,0026
0,0020
0,0016
0,0012
0,0010
0,0008
0,0006
0,0005
0,0004
0,0003
0,0002
0,0002
0,0001
Algoritmo:
p
Adaptado para determinar uma aproximação para a raiz da equação
usando
a
função
de
iteração:
F ( x ) = x 2 − sen x − 1 = 0 ,
ϕ (x ) = sen x + 1
0,9939
1,0048
0,9962
1,0030
0,9977
1,0018
0,9986
1,0011
0,9991
1,0007
0,9994
1,0004
0,9997
1,0003
0,9998
1,0002
Início (* MIL*)
Defina Fi(x) =
sen x + 1
Solicite a aproximação inicial (x0)
Leia Xv
Solicite a precisão (E)
Leia E
Solicite o limite de iterações (N)
Leia N
Para i de 1 até N
Faça
Xn = Fi(Xv)
Se |Xn – Xv| ≤ E
Então
Escreva “aprox “,Xn,“
com “,i,“ iteracoes”
Saia da repetição
Senão
Xv=Xn
Fim Se
Fim para
Se |Xn – Xv| > E
Então
Escreva “Aplicação não converge ou “
Escreva “grau de exatidão não”,
“ pode ser alcançado com “,
N, “ iterações”
Fim Se
Fim (* MIL *)
Exercícios:
(1) Calcular a raiz da equação F ( x ) = x 2 + ln x = 0 com ε ≤ 0.01.
(
)
(
)
Usar o M.I.L. R : ρ = 0.65
(2) Calcular a raiz da equação F (x ) = x 3 − 10 = 0 com ε ≤ 0.01.
Usar o M.I.L. R : ρ = 2.15
(3) Calcular a raiz da equação
(
F ( x ) = x 2 + e3 x − 3 = 0 ,
)
com ε ≤ 10-3 , usando o M.I.L. R : ρ = 0.3521
33
O MÉTODO DE NEWTON-RAPHSON (N-R)
Resolução:
Descrição
y = F ( x) = x 2 − sen x − 1
y ' = F ' ( x) = 2 x − cos x
Seja I um intervalo contendo a raiz ρ da equação F(x) = 0. Suponha-se
que F'(x) ≠ 0 ∀x ∈ I .
F(x) = 0
⇒−
∴ xn +1 = xn −
Equação para iteração:
F ( x)
F ( x)
F ( x)
=0 ⇒ x−
= x ∴ϕ ( x) = x −
F ' ( x)
F ' ( x)
F ' ( x)
F ( xn )
F ' ( xn )
xk +1
( N − R)
n = 0,1,2,...
x0 = 1.3
Como no M.I.L., o objetivo é gerar uma seqüência {xn} a partir de
uma aproximação inicial xo:
F ( x0 )
x1 = ϕ ( x0 ) = x0 −
F ' ( x0 )
x2 = ϕ ( x1 ) = x1 −
M
xk 2 − sen xk − 1
F ( xk )
= xk −
∴ xk +1 = xk −
F ' ( xk )
2 xk − cos xk
x1 = 1.3 −
(1.3) 2 − sen(1.3) − 1
− 0.2736
= 1.3 −
= 1.4173
2.3325
2(1.3) − cos(1.3)
ε1 = x1 − x0 = 1.4173 − 1.3 = 0.1173 > 10
−3
(1.4173) 2 − sen(1.4173) − 1
0.0205
= 1.4097
= 1.4173 −
2.6817
2.(1.4173) − cos(1.4173)
F ( x1 )
F ' ( x1 )
x2 = 1.4173 −
M
ε 2 = x2 − x1 = 1.4097 − 1.4173 = 0.0076
F ( xn )
xn +1 = ϕ ( xn ) = xn −
F ' ( xn )
Encontra-se portanto uma aproximação xn+1 de ρ.
−4
(1.4097 ) 2 − sen(1.4097 ) − 1
2.02 x10
x3 = 1.4097 −
= 1.4096
= 1.4097 −
2.6590
2.(1.4097 ) − cos(1.4097 )
ε 3 = x3 − x2 = 1.4096 − 1.4097 = 0.0001 < 10
Exemplo:
∴ ρ = 1.4096
Seja calcular uma aproximação para a raiz da eq. F(x) = x2 - senx - 1
= 0 no intervalo [1.0, 1.5], com grau de exatidão ε ≤ 10−3 , utilizando
o método de N-R e adotando x0 = 1.3 .
Interpretação Geométrica
34
−3
Obtenção da fórmula de N-R a partir do desenvolvimento de
y= f(x) em série de Taylor
Fórmula de Taylor :
.( x − x0 ) 2 + ...
f
"
(
x
)
0
f(x) = f(x 0 ) + f ′( x0 )( x − x0 ) +
2!
F ( xn +1 ) = F ( xn ) + F ′( xn )( xn +1 − xn ) = 0 n = 0,1,2...
⇒ F ( xn ) + F ′( xn )( xn +1 − xn ) = 0
tgβ =
F ( x1 ) − 0
x1 − x2
= F ′( x1)
tgα =
F ( x0 ) − 0
x0 − x1
= F ′( x0 )
⇒ F ′( x1 ) ( x1 − x2 ) = F ( x1 )
⇒ F ( x0 ) = F ′( x0 ) ( x0 − ( x1 )
F ( x1 )
⇒ −( x1 − x2 ) = −
F ′( x1 )
⇒−
⇒ x2 = x1 −
F ( x1 )
F ′( x1 )
F ( x0 )
F ′( x0 )
= x1 − x0
⇒
F ( xn )
+ xn +1 − xn = 0
F ′( xn )
⇒
xn +1 = xn −
F ( xn )
F ′( xn )
n = 0,1,2...
SOBRE A CONVERGÊNCIA DO MÉTODO
F ( x0 )
Para que um processo iterativo x = ϕ( x ) seja convergente, devemos ter
ϕ ′( x) < 1, ∀ x ∈ I 0 , onde I0 é uma vizinhança da raiz ρ da equação
⇒ x1 = x0 −
F ′( x0 )
F(x)=0.
O método de N-R é conhecido como método das tangentes.
∴ xn +1
F ( xn )
= xn −
F ' ( xn )
ϕ ( x) = x −
( N − R)
n = 0,1,2,...
F ( x)
F ′( x )
⇒ ϕ ′( x ) = 1 −
=
2
2
[ F ′( x ).F ′( x ) − F ( x ).F " ( x )] ( F ′( x )) − ( F ′( x )) + F ( x ).F " ( x )
=
2
2
( F ′( x ))
( F ′( x ))
F ( x ).F " ( x )
2
( F ′( x))
Portanto, o processo será convergente se
35
ϕ ′( x) =
Resolução:
F ( x).F " ( x)
<1
[ F ′( x)]2
(a) M.I.L
Observe-se que:
ϕ ( x) = sen x + 1 ∴ϕ ′( x) =
x = ρ ⇒ F (ρ) = 0
F ( ρ ).F " ( ρ )
= 0 <1
ϕ ′( ρ ) =
[ F ′( ρ )]2
1
2 sen x + 1
. cos x =
cos x
2 sen x + 1
cos(1.3)
ϕ ′( x0 ) =
= 0.954 < 1
3
2 sen(1.3) + 1 1424
∴ se x 0 estiver suficientemente próximo da raiz, a aplicação do
Se F’ e F’’ são contínuos em I, ϕ’ é contínua em I e, portanto, desde
que ϕ ′ (ρ) = 0 , existe uma vizinhança I′ ⊂ I tal que ϕ ′( x) < 1 ∀x ∈ I '.
método deverá ser convergente.
(b) método de N-R
ϕ ′( x) =
F ( x).F " ( x)
F ′( x) 2
F ( x) = x 2 − sen x − 1, F ′( x) = 2 x − cos x, F " ( x) = 2 + sen x
∴ ϕ ′( x0 ) =
[
]
F ( x0 ).F " ( x0 )
(1.3) 2 − sen(1.3) − 1 [2 + sen(1.3)]
=
F ′( x0 ) 2
2.(1.3) − cos(1.3) 2
[
]
= 0.1490 < 1
14243
Portanto, se x0 estiver suficientemente próximo da raiz, a aplicação do
método deverá ser convergente.
Conclusão: o método de N-R, quando pode ser aplicado, é sempre
convergente. A dificuldade está em determinar este
subintervalo I´ onde seguramente ϕ′ ( x ) < 1 .
APLICABILIDADE DO MÉTODO N-R (Teorema de Fourier)
Exemplo:
Para o problema de se determinar uma aproximação para a raiz da eq.
F( x ) = x 2 − sen x − 1 = 0 no intervalo [1.0, 1.5], com x 0 = 1. 3 , estudar
quanto à convergência as funções de iterações utilizadas nos métodos
M.I.L. e N.R.
É condição suficiente para a convergência do método de N-R que
F´(x) e F"(x) não se anulem e mantenham sinais constantes numa
vizinhança I de uma raiz ρ da equação F(x)=0 e que o processo se
inicie num ponto x0 ∈ I tal que F ( x0 ).F " ( x0 ) > 0 .
36
2
(b ) F ( x0 ) = F ( 0.9) = (0.9) − sen(0.9) = 0.03
Exemplo:
Calcular a raiz da equação F ( x) = x 2 − sen x = 0 usando o método de
N-R ( x0 = 0.9;∈< 10 −3 )
F " ( x 0 ) = F " (0.9) = 2 + sen( 0.9) = 2.783
F ( x 0 ).F " ( x 0 ) > 0
Resolução:
xn + 1 = xn −
F ( xn )
F ′( xn )
x n 2 − sen x n
2 x n − cos x n
x n +1 = x n −
2
F ( x) = x − sen x
F ′( x) = 2 x − cos x
x 0 = 0.9
2
⇒ xn + 1
( x − sen xn )
= xn − n
2 xn − cos xn
[
]
2
(0.9) − sen(0.9)
0.0267
= 0.9 −
= 0.8773
x1 = 0.9 −
2.(0.9) − cos( 0.9)
1.1784
ε 1 = 0.8773 − 0.9 = 0.0227
Condições para convergência:
x 2 = 0.8773 −
(a) F ′( x) = 2 x − cos x
F " ( x) = 2 + sen x
[(0.8773) 2 − sen(0.8773] = 0.8773 − 6.395x10 −4 =
2.(0.8773) − cos( 0.8773)
1.1154
= 0.8767
ε 2 = 0.8767 − 0.8773 = 0.0006 < 10
Conclui-se, pelo método grãfico, que ρ ∈( 0.5,1) com relação a F´(x):
−3
∴ ρ = 0.8767
Exemplo:
Calcular a raiz da equação F(x) = 2x - cos x usando o método de N-R
∈< 10 −4
∴ ∀x ∈ (0.5,1.0)
(
F ′( x) = 21x4
−4cos
x4
>30
24
)
.preserva sinal
.não se anula
Resolução:
Com relação a F"(x):
∀x ∈ (0.5,1.0), F " ( x) = 2 + sen x > 0.
37
(b) F ( x0 ).F " ( x0 ) > 0
x0 = 0
F ( x0 ) = 2.0 − cos 0 = −1 < 0
F " ( x0 ) = cos 0 = 1 > 0
F(x) = g(x)
{ - h(x)
{
2x
⇒ F ( x0 ).F " ( x0 ) < 0
cos x
x0 = 0.5
F ( x0 ) = 2.(05)-cos(0.5) = 1 - 0.878 = 0.12 > 0
∴ ρ ∈ [0,0.5]
F " ( x0 ) = cos(0.5) = 0.878 > 0
⇒ F ( x0 ).F " ( x0 ) > 0
Função de iteração
F ( xn )
xn + 1 = x n −
F ′( xn )
F ( x) = 2 x − cos x
F ′( x) = 2 − sen x
Aplicação do método de N-R
n = 0,1,2...
⇒ xn + 1 = xn −
xn + 1 = x n −
(2 xn − cos xn )
2 + sen xn
(2 xn − cos xn )
2 + sen xn
x0 = 0.5
x1 = 0.5 −
(2 x − cos x)
∴ϕ ( x ) = x −
2 + sen x
[2.(0.5) − cos(0.5)] = 0.5 − 0.1224 = 0.4506
2 + sen 0.5
2.4794
ε1 = x1 − x 0 = 0.4506 − 0.5 = 0.0494
Condições para convergência (suficientes)
x2 = 0.4506 −
[2.(0.4506) − cos(0.4506)] = 0.4506 − 1.014 x10− 3
x3 = 0.4502 −
[2.(0.4502) − cos(0.4502)] = 0.4502 − 3.99 x10 − 5
2 + sen(0.4506)
= 0.4502
ε 2 = x2 − x1 = 0.4502 − 0.4506 = 0.0004
F ′( x) = 2 + sen x
ρ ∈ [0,0.5]
F " ( x) = cos x
∀ x ∈ [0,0.5]
F ′( x) > 0
não se anulam e preservam o sinal na vizinhança.
F " ( x) > 0
38
2 + sen(0.4502)
= 0.4502
2.4355
2.4355
∴ ε 3 = x3 − x2 < 10 −4
∴
x1 = x0 −
ρ = 0.4502
F ( x0 )
4 cos(0.25) − e 0.25
2.5916
= 0.25 −
= 0.25 −
= 1.3899
0.25
F ′(x 0 )
− 2.2736
− 4 sen (0.25) − e
ε 1 = x1 − x0 = 1.3899 − 0.25 = 1.1399
Ordem de Convergência do Método de N-R
Teorema:
Se F , F ′ e F ′′ são contínuas em um intervalo I , centrado em ρ ,
raiz da equação F (x ) = 0 , e se F ′(ρ ) ≠ 0 , então a ordem de
convergência do método de Newton-Raphson é quadrática ( p = 2 ).
A tabela a seguir, construída no EXCEL, apresenta o resultado da
aplicação do método de N-R, para a obtenção de uma aproximação
para a raiz da equação com exatidão até a quarta casa decimal. A
última coluna da tabela apresenta uma estimativa da ordem de
convergência – valor de p – obtida a partir da expressão:
Exemplo: Determinar a raiz positiva da equação:
F ( x ) = 4 cos(x ) − e x = 0
Utilizando o método de N-R. Estimar também a ordem convergência
da aplicação do método a esta equação.
ε
log k +1
εk
p≅
log ε k
ε
k −1
Resolução:
F ( x ) = 4 cos( x ) − e x
⇒
F ′( x ) = −4 sen ( x ) − e
x
Pelo método gráfico, conforme já apresentado na seção relativa ao
MIL, a raiz positiva da equação se encontra no intervalo (0,1) e é
próxima de 1. No entanto, como o objetivo é ilustrar a obtenção de
uma aproximação para p , ordem de convergência, adotaremos
x0 = 0.25 .
i
xi
F ( xi )
F ′( xi )
∈i
p
0
1
2
3
4
5
6
0,2500
1,3899
0,9754
0,9068
0,9048
0,9048
0,9048
2,5916
-3,2945
-0,4089
-0,0115
0,0000
0,0000
0,0000
-2,2736
-7,9490
-5,9640
-5,6267
-5,6166
-5,6166
-5,6166
1,1399
0,4145
0,0686
0,0021
1,851E-06
1,508E-12
1,7784
1,9505
1,9977
2,0000
Exercício
Dada a função:
F(x) = x ln x - 1 = 0
Cálculo de x1 :
39
Solicite o limite de iterações (N)
Leia N
Para i de 1 até N
Faça
Xn = xv – F(xv)/DF(xv)
Se |Xn – Xv| ≤ E
Então
Escreva “aprox “,xn,“
com “,i,“ iteracoes”
Saia da repetição
Senão
Xv=Xn
Fim Se
Fim para
Se |Xn – Xv| > E
Então
Escreva “Aplicação não converge ou “
Escreva “grau de exatidão não”,
” pode ser alcançado com “,
N, “ iterações”
Fim Se
Fim (* N-R *)
pede-se calcular uma aproximação para a sua raiz usando o método de
N-R com ∈≤10 −4
(ρ = 1.763)
Exercício:
Usando o método de N-R determine a menor raiz positiva das
equações abaixo.
x
(a ) − tgx = 0
(ρ = 4.2748)
2
(ρ = 0.754)
(b)2 cos x = e x / 2
(ρ = 1.43097 )
(c ) x 5 − 6 = 0
−4
Considere ε ≤10 .
Exercício:
Seja F(x) = ex - 4x2 . Obter uma aproximação para ρ com ε ≤10 −4
( ρ = 0. 7148 )
usando o método de N-R
Algoritmo:
Adaptado para determinação de uma aproximação para a raiz da eq.
F(x) = 2x - cos(x) = 0 através do método de N-R.
Início (* N-R *)
Defina F(x) = 2x-cos(x)
Defina DF(x) = 2 + sen(x)
Solicite a aproximação inicial (x0)
Leia Xv
Solicite a precisão (E)
Leia E
40
O MÉTODO DAS SECANTES
A discussão a seguir é baseada em [FRANCO, 2006]. Uma série
desvantagem do método de N-R é a necessidade de se ter que obter
F ' ( x) , bem como calcular o seu valor numérico a cada passo. No
método das secantes, a derivada F ' ( x) é substituída pelo quociente
das diferenças :
F ' ( xk ) =
F ( x k ) − F ( x k −1 )
x k − x k −1
onde x k , x k −1 são duas aproximações quaisquer para a raiz ρ .
Substituindo na equação do método de Newton-Raphson, obtém-se:
x k +1 = x k −
x k +1 =
tg (α ) =
F ( xk )
F ( xk )
( x − x k −1 ) F ( x k )
= xk −
= xk − k
F
x
−
F
x
(
)
(
)
F ' ( xk )
F ( x k ) − F ( x k −1 )
k
k −1
x k − x k −1
⇒
x k −1 F ( x k ) − x k F ( x k −1 )
F ( x k ) − F ( x k −1 )
F ( x k ) − F ( x k −1 )
F ( x k −1 )
=
x k − x k −1
x k −1 − x k +1
x k −1 − x k +1
x k − x k −1
=
F ( x k −1 )
F ( x k ) − F ( x k −1 )
⇒ x k +1 = x k −1 −
Observe-se que são necessárias duas aproximações iniciais para que a
equação acima possa ser utilizada.
⇒ x k +1 =
F ( x k −1 )( x k − x k −1 )
F ( x k ) − F ( x k −1 )
x k −1 F ( x k ) − x k F ( x k −1 )
F ( x k ) − F ( x k −1 )
Graficamente:
Exemplo: F ( x) = 4 cos x − e x = 0 , ρ ∈ (0,1) , F ' ( x) ρ ≅ 0.9 (método
gráfico)
Resolução:
41
x0 = 0.9 e x1 = 1.0 (valores arbitrados)
x2 = ? ( k = 1 )
F ( x0 ) = 4 cos(0.9) − e 0.9 = 0.0268
Portanto, ρ = 0.9048 , com ε < 10 −3 .
F ( x1 ) = 4 cos(1) − e1 = −0.5571
x F ( x1 ) − x1 F ( x 0 ) (0.9)(−0.577) − (1)(0.0268)
x2 = 0
=
=
F ( x1 ) − F ( x 0 )
− 0.5771 − 0.0268
Ordem de Convergência – Método das Secantes [FRANCO, 2006]
Teorema:
A ordem de convergência
1+ 5
p=
≅ 1.618.
2
− 0.5282
= 0.9046
− 0.5839
ε 2 = x 2 − x1 = 0.9046 − 1 = 0.0954
(
=
)
do
método
das
secantes
é
Exercício:
Determinar, pelo método das secantes, uma raiz de cada uma das
equações a seguir [FRANCO, 2006]:
a) x = −2.7 ln x
b) e − x − ln x = 0
x3 = ? ( k = 2 )
F ( x1 ) = −0.5771
F ( x 2 ) = 4 cos(0.9046) − e 0.9046 = −0.0011
x F ( x 2 ) − x 2 F ( x1 ) (1)(−0.0011) − (0.9046)(−0.5771)
x3 = 1
=
=
F ( x 2 ) − F ( x1 )
− 0.0011 − (−0.5771)
0.5050
= 0.9048
0.5582
ε 3 = x3 − x 2 = 0.9048 − 0.9046 = 0.0002
=
x4 = ? ( k = 3 )
F ( x 2 ) = −0.0011
F ( x3 ) = 4 cos(0.9048) − e 0.9048 = −0.00004
x F ( x3 ) − x3 F ( x 2 ) (0.9046)(−0.00004) − (0.9048)(−0.0011)
=
x4 = 2
=
− 0.00004 − (−0.0011)
F ( x3 ) − F ( x 2 )
0.0009
= 0.9048
0.0010
ε 4 = x 4 − x3 < 10 −3
=
42
P" ( x ) = 12 x 2 − 30 x + 12
2.2 ESTUDO DAS EQUAÇÕES ALGÉBRICAS
⇒ P" (2) = 12.2 2 − 30.2 + 12 = 48 − 60 + 12 = 0
P' ' ' ( x ) = 24 x − 30
⇒ P' ' ' (2 ) = 48 − 30 = 18 ≠ 0
∴ ρ = 2 é raiz e tem multiplicidade 3.
2.2.1 INTRODUÇÃO
Seja uma equação algébrica (polinomial) de grau n(n ≥ 1) :
P(x ) = an x n + an −1 x n −1 + an − 2 x n − 2 + ... + a1 x + a0 = 0
onde os coeficientes ai são números reais e a n ≠ 0
2.2.2 VALOR NUMÉRICO DE UM POLINÔMIO
Dado um polinómio P( x ) , um problema que se coloca é o de calcular
o valor numérico de P( x ) para x = x0 , ou seja, P( x0 ) . Observe-se que
n(n + 1)
o cálculo de P( x0 ) requer n adições e
multiplicações. De
2
fato:
TEOREMA FUNDAMENTAL DA ÁLGEBRA
Todo eq. algébrica de grau n, n ≥ 1, tem exatamente n raízes, que
podem ser reais ou complexas, e não necessariamente distintas.
Uma raiz ρ da equação P( x ) = 0 é dita ter multiplicidade m se:
P( ρ ) = ρ ' ( ρ ) = P" ( ρ ) = ... = P ( m −1) ( ρ ) = 0 e
P( x0 ) = an x0n + an −1 x0n −1 +...+ a1 x0 + a0
{ 1
{
424
3
P (m ) (ρ ) ≠ 0
Exemplo:
Mostrar que ρ = 2 é raiz da equação algébrica
P(x ) = x 4 − 5 x 3 + 6 x 2 + 4 x − 8 = 0
com multiplicidade m = 3
n
n −1
produtos
produtos
1
produto
n + (n − 1) + (n − 2 ) + ... + 2 + 1 =
n(n + 1)
2
Foi utilizada acima a fórumla da soma dos termos de uma progressão
aritmética.
n.(a1 + an )
Sn =
2
com a1 = n, an = 1, número de termos = n.
Solução:
P(2 ) = 2 4 − 5.2 3 + 6.2 2 + 4.2 − 8 = 16 − 40 + 24 + 8 − 8 = 0
P' (x ) = 4 x 3 − 15 x 2 + 12 x + 4
⇒ P' (2) = 4.2 3 − 15.2 2 + 12.2 + 4 = 32 − 60 + 24 + 4 = 0
Então, se o grau n do polinômio for elevado (digamos, n ≥ 20 ), o
cálculo de P( x0 ) , além de se tornar muito laborioso, é também
ineficiente do ponto de vista computacional.
43
an x n + an −1 x n −1 + L + a1 x + a0 =
Exemplo:
Dado o polinômio
P( x ) = 3 x 9 + 2 x8 − 10 x 7 + 2 x 6 − 15 x 5 − 3 x 4 + 2 x 3 − 16 x 2 + 3 x − 5
seja determinar P(2 ) .
(b x
Resolução:
P(2 ) = 3.29 + 2.28 − 10.27 + 2.26 − 15.25 − 3.2 4 + 2.23 − 16.22 + 3.2 − 5
⇒ P(2 ) = 321
Obtém-se, da redução a termos semelhantes:
bn = an
n
n −1
+ bn −1 x n − 2 + L + b2 x + b1 )( x − c ) + r
= bn x n + (bn −1 − cbn )x n −1 + (bn − 2 − cbn −1 )x n − 2 +
L + (b2 − cb3 )x 2 + (b1 − cb2 )x − cb1 + r
bn −1 = c.bn + an −1
bn − 2 = c.bn −1 + an − 2
M
b1 = c.b2 + a1
2.2.3 MÉTODO DE BRIOT-RUFFINI
r = c.b1 + a0
Dado
o
polinômio
P( x ) = an x n + an −1.x n −1 + K + a1 x + a0 ,
dividindo-se P( x ) pelo binômio (x − c ) , obtém-se a igualdade:
Ou, equivalentemente,
bn = an
P(x ) = (x − c ) Q
(x ) + {r
{
polinômio
quociente
bn − k = c.bn − k +1 + an − k
resto da
divisão
1 ≤ k ≤ n − 1 (algoritmo de Briot - Ruffini)
r = c.b1 + a0
onde Q( x ) é da forma:
EXEMPLO: Seja dividir
P(x ) = x 3 − 7 x 2 + 16 x − 10
pelo binômio (x − 2 ) , usando o método de Briot-Ruffini
Q (x ) = bn x n −1 + bn −1.x n − 2 +L + b2 x +b1
Como determinar os coeficientes bi , i = 1,L,n e o resto r?
P( x ) = Q (x )(x − c ) + r
P( x ) = an x n + an −1 x n −1 + L + a1 x + a0
Solução:
P( x ) = ( x − 2).Q( x ) + r
Q (x ) = bn x n −1 + bn −1 x n − 2 + L + b2 x + b1
Q( x ) = b3 x 2 + b2 x + b1
44
Cálculo dos bi's
b3 = a3 = 1
∴ Q( x ) = x 2 − 10 x + 46
R = −148
i = 1, 2 , 3
b2 = c.b3 + a2 = 2.1 + (− 7 ) = −5
b1 = c.b2 + a1 = 2.(− 5) + 16 = 6
3
Cálculo do resto:
r = cb1 + a0 = 2.6 + (− 10 ) = 2
Teorema: o valor numérico de P( x ) em x = c é igual ao resto da
divisão de P(x ) por (x − c )
Demonstração:
∴ Q (x ) = x − 5 x + 6
r=2
2
P ( x ) = ( x − c )Q ( x ) + r
Usando o dispositivo prático de Briot-Ruffini:
ai 's44444448
644444447
1
2
−7
16
-10
2
− 10
12
1
−5
6
144
42444
3
x=c
⇒ P(c ) = (c − c ).Q (c ) + r
⇒ P(c ) = r
2
{
bi 's
Exemplo:
Dado o polinômio
P( x ) = 3 x 9 + 2 x8 − 10 x 7 + 2 x 6 − 15 x 5 − 3 x 4 + 2 x 3 − 16 x 2 + 3 x − 5, seja
calcular P (2 ) usando o dispositivo prático de Briot-Ruffini.
r
Exemplo: Seja dividir
P(x ) = x 3 − 7 x 2 + 16 x − 10
Pelo binômio (x + 3) , usando o dispositivo prático de Briot-Ruffini.
Resolução:
3
Resolução:
2
1
-3
1
2
Observe-se que: P(− 3) = (− 3) − 7.(− 3) + 16(− 3) − 10 = − 148
−7
−3
− 10
16
30
46
3
-10
-138
-148
2
-10
2
-15
-3
2
-16
3
-5
6
16
12
28
26
46
96
160
326
8
6
14
13
23
48
80
163
321
∴P(2 ) = 321
45
∴ P(2 ) = −10 e P' (2 ) = −16
Teorema: o valor numérico da derivada de P (x ) para x = c é igual ao
resto da divisão de Q( x ) por ( x − c ) , onde Q ( x ) é o polinômio
quociente da divisão de P (x ) por (x − c ) .
Demonstração:
P( x ) = ( x − c ).Q (x ) +
Observe-se que:
P( x ) = x3 − 2 x 2 − 20 x + 30
(
)
⇒ P(x ) = x 2 − 2 x − 20 x + 30 = (( x − 2 )x − 20 )x + 30
∴ P(2 ) = ((2 − 2 ) ⋅ 2 − 20 )2 + 30 = −40 + 30 = −10
P' ( x ) = 3 x 2 − 4 x − 20 = (3x − 4 )x − 20
⇒ P ' (2 ) = (3.2 − 4 ) ⋅ 2 − 20 = 4 − 20 = −16
r
cons tan te
P' (x ) = Q( x ) + Q ' ( x )( x − c )
para x = c, temos :
P' (c )= Q(c )+ Q ' (c ).(c − c )= Q(c )
2.2.4 MÉTODO DE HORNER
⇒ P' (c ) = Q(c )
P( x ) = an x n + an −1 x n −1 + L + a2 x 2 + a1 x + a0
(
= ((a x
Pelo teorema anterior sabemos que Q(c ) é igual ao resto da divisão de
Q( x ) pelo binômio (x − c ) .
)
= an x n −1 + an −1 x n − 2 + L + a2 x + a1 x + a0
n
n−2
+ an −1 x
n −3
)
+ L + a2 x + a1 )x + a0
M
= ({
(L(an x + an −1 ) x + L + a2 )x + a1 )x + a0
Exemplo:
Dado o polinômio P( x ) = x 3 − 2 x 2 − 20 x + 30 = 0
seja calcular P' (2 ) usando o dispositivo prático de Briot-Ruffini.
n −1
Exemplo:
Dado P( x ) = 2 x 4 − 5 x3 − 2 x 2 + 4 x − 8 , calcular P(3) (Horner).
Resolução:
1
1
-2
2
0
-20
0
-20
1
2
2
4
-16
2
2
+30
-40
-10
Resolução:
P(x ) = 2 x 4 − 5 x3 − 2 x 2 + 4 x − 8
(
= ((2 x
)
− 5 x − 2 )x + 4 )x − 8
= 2 x3 − 5x 2 − 2 x + 4 x − 8
2
= (((2 x − 5)x − 2 )x + 4 )x − 8
46
∴P(3) = (((2.3 − 5) ⋅ 3 − 2 ) ⋅ 3 + 4 ) ⋅ 3 − 8 ⇒ P(3) = 13
2.2.5 MÉTODO DE BIRGE-VIETA
O algorítmo obtido quando usamos os resultados dos teoremas
anteriores para aplicar o método de N-R é chamado de método de
Birge-Vieta:
Exemplo:
Dado P( x ) = 3 x 9 + 2 x8 − 10 x 7 + 2 x 6 − 15 x 5 − 3 x 4 + 2 x 3 − 16 x 2 + 3x − 5,
calcular P(2 ) pelo método de Horner.
xn +1 = xn −
Resolução:
P( xn ) é o resto da divisão de P( x ) por (x − xn ) P' (xn ) é o resto da
divisão do quociente obtido quando do cálculo da divisão de P( xn )
pelo binômio (x − xn ) .
(
)
= ((3 x + 2 x − 10 x + 2 x − 15 x − 3x + 2 x − 16 )x + 3)x − 5
= (((3x + 2 x − 10 x + 2 x − 15 x − 3 x + 2 )x − 16 )x + 3)x − 5
= ((((3 x + 2 x − 10 x + 2 x − 15 x − 3)x + 2 )x − 16 )x + 3)x − 5
= (((((3x + 2 x − 10 x + 2 x − 15)x − 3)x + 2 )x − 16 )x + 3)x − 5
= ((((((3 x + 2 x − 10 x + 2 )x − 15)x − 3)x + 2 )x − 16 )x + 3)x − 5
= (((((((3 x + 2 x − 10)x + 2 )x − 15)x − 3)x + 2 )x − 16 )x + 3)x − 5
= 3 x8 + 2 x 7 − 10 x 6 + 2 x 5 − 15 x 4 − 3 x 3 + 2 x 2 − 16 x + 3 x − 5
6
6
5
5
5
4
4
4
3
3
3
3
3
4
n = 0,1,2,...
onde:
P( x ) = 3 x 9 + 2 x 8 − 10 x 7 + 2 x 6 − 15 x 5 − 3 x 4 + 2 x 3 − 16 x 2 + 3 x − 5
7
P( xn )
P' ( xn )
2
2
2
2
Exemplo:
Calcule
uma
aproximação
para
a
raiz
de
ρ
ρ
p( x ) = 3 x3 − 76 x 2 + 163 x − 46 no intervalo (20,25) tal que ε < 10−2 ,
usando o método de Brige-Vieta. Assumir x 0 = 22 . 5 como
aproximação inicial da raiz.
2
2
= ((((((((3 x + 2 )x − 10)x + 2)x − 15)x − 3)x + 2 )x − 16)x + 3)x − 5
∴ P(2 ) = ((((((((3 ⋅ 2 + 2 ) ⋅ 2 − 10 )2 + 2 )2 − 15)2 − 3)2 + 2 )2 − 16)2 + 3)2 − 5 = 321
Resolução:
Observe-se que é possível obter a forma fatorada final diretamente,
em um único “passo”:
Cálculo de x1 :
x1 = x0 −
P( x ) = −5 + 3 x − 16 x 2 + 2 x 3 − 3 x 4 − 15 x 5 + 2 x 6 − 10 x 7 + 2 x8 + 3 x9
= −5 + x(3 + x(− 16 + x(2 + x(− 3 + x(− 15 + x(2 + x(− 10 + x(2 + 3 x ))))))))
P( x0 )
P(22.5)
= 22.5 −
P' ( x0 )
P' (22.5)
Dispositivo prático de Briot-Ruffini:
47
3
22.5
3
22.5
3
-76
67.5
-8.5
67.5
59
+163
-46
-191.25
-635.63
-28.25
-681.63
1.327,5
1.299,25 = P'(22.5)
x3 = x2 −
p ( x2 )
P(23)
= 23 −
p ' ( x2 )
P' (23)
Dispositivo prático de Briot-Ruffini:
3
− 681.63
⇒ x1 = 22.5 −
= 23.02
1.299,25
ε1 = x1 − x0 = 23.02 − 22.5 = 0.52
23
3
-76
69
-7
+163
-161
2
-46
46
0
= p(23)
< 10-2
∴ ρ = ρ = x2 = 23
Cálculo de x2 :
x2 = x1 −
P( x1 )
P(23.02)
= 23.02 −
P' ( x1 )
P' (23.02)
2.2.6 NÚMERO DE ZEROS REAIS DE UM POLINÔMIO COM
COEFICIENTES REAIS
Regras de Sinais de Descartes:
Dispositivo prático de Briot-Ruffini:
3
23.02
3
23.02
3
-76
69.06
-6.94
69.06
61.12
O número de raízes reais posistivas n+ de uma equação algébrica é
igual ao número de variações de sinais na seqüência dos coeficientes,
ou menor que este número por um inteiro, par, não negativo, sendo
que uma raiz de multiplicidade m é contada como m raízes e que
coeficientes iguais a zero não são considerados.
Para se determinar o número e raízes reais negativas, n-, aplica-se a
regra anterior a P(-x).
+163
-46
-159.76
+74.61
+3.24
+28.61
1.430.00
1.433.24 = P'(23.02)
28.61
= 23.00
1433.24
ε 2 = x2 − x1 = 23.00 − 23.02 = 0.02
⇒ x2 = 23.02 −
Exemplos:
(a ) P(x ) = x 4 − 5 x3 + 7 x 2 + 29 x + 30 = 0
+
−
123
Cálculo de x3 :
−
+
123
+
n+ = 2 ou 0 raízes reais positivas
48
P(− x ) = x 4 + 5 x 3 − 7 x 2 − 29 x + 30
+
+
−
123
2.2.7 LIMITAÇÃO DAS RAÍZES REAIS DE UMA EQUAÇÃO
ALGÉBRICA: MÉTODO DE LAGUERRE
−
+
123
n- = 2 ou 0 raízes reais negativas
Limitar as raízes de uma equação F(x)=0 é determinar um intervalo
onde estão todas as raízes da equação.
(b ) P(x ) = 2 x5 − 3x 4 − 4 x3 + x + 1
−
+ +
123
+
−
1
2
3
O MÉTODO DE LAGUERRE
n+ = 2 ou 0 raízes reais positivas
P(− x ) = −2 x 5 − 3 x 4 + 4 x 3 − x + 1
−
Seja determinar um número real Ls tal que, dada a função polinomial
y = P(x), P(x) > 0 ∀ x ≥ L > 0 .Diz-se que Ls é um limitante superior
para as raízes da equação algébrica P(x) = 0.
−
+ 123
− 123
+
123
n- = 3 ou 1 raízes reais negativas
Para se determinar Ls divide-se sucessivamente P(x) por (x - xk), xk
= 1, 2, ... até que para um particular valor de x, digamos xL, tem-se
todos os coeficientes do quociente e o resto da divisão positivos.
(c ) P(x ) = 4 x5 − x3 + 4 x 2 − x − 1
+
− +{
− −
{{
n+ = 3 ou 1 raízes reais positivas
Dividindo-se P(x) pelo binômio (x - Ls) obtém-se:
P(− x ) = −4 x 5 + x 3 + 4 x 2 + x − 1
−
+
123
+
P( x ) = ( x − LS )Q( x ) + R
+
−
123
onde Q( x ) é da forma:
n- = 2 ou 0 raízes reais negativas
(d ) P(x ) = x
7
bn x n −1 + bn −1x n −1 + L + b2 x + b1
+1
+
+
123
Obviamente:
Se x ≥ LS > 0, bi > 0, i = 1,2,L, n, e R > 0 então P( x ) > 0.
n+ = 0 raízes reais positivas
P(− x ) = − x 7 + 1
−
+
123
Exemplo:
Seja o polinômio:
n- = 1 raíz real negativa
49
1
P( x ) = x 4 − 5 x 3 − 7 x 2 + 29 x + 30 .
Encontrar um limitante superior para os seus zeros.
7
1
Resolução:
Dispositivo prático de Briot-Ruffini:
1
-5
1
1
−4 < 0
1
-5
2
1
−3< 0
1
-5
3
1
−2 < 0
1
-5
4
1
−1
1
1
2
3
4
5
1
1
6
1
-7
29
29
30
-7
29
30
29
30
-5
5
0
-7
0
29
30
-5
6
1
-7
6
29
30
+30
546
576
é um limitante superior para os zeros da função
polinomial y = P(x).
Para se determinar um limitante inferior, Li, para as raízes reais não
positivas da eq. algébrica P(x) = 0, procede-se como indicado a seguir.
Seja n o grau da equação algébrica P(x) = 0. Então:
(a) se n é par, determina-se o limitante superior Ks de y = P (− x) e
toma-se Li = − K s .
(b) se n é ímpar, determina-se o limitante superior Ks de y = − P(− x )
e toma-se Li = − K s .
Graficamente:
-7
-7 +29
14
49
7 78
∴ LS = 7
30
-7
-5
7
2
Caso (a):
−7 < 0
−1< 0
50
Caso (b):
Exemplo:
Determinar um limitante inferior para os zeros do polinômio do
exemplo anterior.
Solução:
P( x ) = x 4 − 5 x3 − 7 x 2 + 29 x + 30
n = 4, par ⇒ Li = − K s
onde
Ks limit sup. para y = P(− x)
Determinação de Ks:
P(− x ) = x 4 + 5 x 3 − 7 x 2 − 29 x + 30
51
Dispositivo prático de Briot-Ruffini:
1
1
1
1
2
1
1
3
1
5
1
6
-7 -29
6
-1 < 0
5
2
7
-7 -29
14 14
7 -15 < 0
5
3
8
-7
24
17
-29
51
22
(a ) P(x ) = 3x5 − x 4 − x3 + x + 1 = 0
30
+
−
123
−
+
123
1
1
+
n+ = 2 ou 0 raízes reais positivas
(b )P(− x ) = −3x 5 − x 4 + x 3 − x + 1 = 0
30
−
+ 123 −
+
123
123
−
1
1
1
n- = 1 ou 3 raízes reais negativas
30
66
96
(c)
⇒ ks = 3
3
1
3
∴ Li = −k s = −3 é um limitante inferior para os zeros da função
polinomial y = P(x).
(d) n = 5 ⇒
Observação: as raízes da equação x 4 − 5 x 3 − 7 x 2 + 29 x + 30 = 0 são:
ρ1 = −2, ρ 2 = −1, ρ 3 = 3, ρ 4 = 5,
-1
3
2
-1
2
1
0 1 1
1 1 2
1 2 3
Li = - Ks
⇒ Ls = 1
Ks limitante superior de -P( -x)
P(− x ) = −3 x 5 − x 4 + x 3 − x + 1
− P(− x ) = 3 x 5 + x 4 − x 3
3 1 -1 0
1
3
4 3
3 4
3 3
⇒ Li = - Ks = -1
∴ ρ i ∈ (− 3,7 ) , i = 1,2,3,4
Exemplo completo:
Dada a equação algébrica: P( x ) = 3 x 5 − x 4 − x 3 + x + 1 = 0
pede-se determinar:
(a) o número de raízes reais positivas
(b) o número de raízes reais negativas
(c) um limitante superior para as raízes reais
(d) um limitante inferior para as raízes reais
(e) um intervalo contendo no mínimo uma raiz real.
(f) a raiz isolada usando o método de Birge-Vieta.
+ x −1
1
-1
3
4
4
3
∴ L i = −1
De (c ) e (d ) : ∀ρ ∈ ℜ : P( ρ ) = 0 ⇒ ρ ∈ (− 1,1)
(e) P(xi ) = ? xi ∈(-1, 1)
Do item (c) : P( 1 ) = 3 > 0
P(0) = 1 > 0
P( -1) = ?
Do item (d): - P ( -1) = 3 ⇒
52
P( -1 ) = -3
Separação das raízes
Método de Birge-Vieta:
( i ) raízes positivas (?)
xn +1 = xn −
P( 0 ) = 1 > 0
P( 0.5) = ?
P( 1 ) = 3 > 0
3 -1
-1
0
0.5
1.5 0.25 -0.3753
3 0.5 -0.75 -0.375
⇒ P(0.5) = 1.407 > 0
1
-0.188
0.813
x0 = −0.6 (arbitrado)
Verificação quanto à convergência:
1
0.407
1.407
3
-0.6
3
-0.6
Nada se pode concluir sobre as raízes positivas a partir dos valores
obtidos.
3
-0.6
3
( ii ) raízes negativas (?)
P( 0 ) = 1 > 0
P( -1) = -3 < 0
P( -0,5) = ?
3
- 0.5
-1
-1.5
3 -2.5
ϕ ′( x0 ) =
∃ ρ real ;
P ( xn )
, n = 0,1,2,L
P' ( xn )
ρ ∈ (− 1,0 )
-1
-1.8
-2.8
-1.8
-4.6
-1.8
-6.4
-1
1.68
0.68
2.76
3.44
3.84
7.28
0
-0,41
-0.41
-2.06
-2.47
-4.368
-6.838
1
1
0.25
-0.75
1.25
0.25 = P ( -0.6)
1.48
2.73 = P' ( - 0.6)
⇒
P''(-0.6)=-13.676
P( x0 ).P" ( x0 )
(0.25)(−13.676)
=
= 0.459 < 1
2
P′( x0 )
(2.73) 2
∴ haverá convergência se x 0 estiver suficientemente próximo de ρ .
-1
0
1.25 -0.125
0.25 -0.125
1
0.0625
1.0625
Cálculo de x1 :
1
-0.531
0.469
P(x0 )
P(− 0.6 )
⇒ x1 = −0.6 −
P' ( x0 )
P' (− 0.6 )
0.25
⇒ x1 = −0.6 ⇒ x1 = −0.69
2.73
ε1 = x1 − x0 = − 069 − (− 0.6) = 0.09 > 10−2
x1 = x0 −
⇒ P(-0..5) = 0.469 > 0
∃ ρ real; ρ ∈ (− 1, - 0.5)
(f) determinação da raiz real negativa
53
(d) um limitante inferior para as raízes reais
(e) a forma obtida da aplicação do método de Honer.
(f) o valor numérico de P(x) nos pontos -5 e 4.
Cálculo de x2 :
x2 = x1 −
P( x1 )
P(− 0.69 )
= −0.69 −
P' (x1 )
P' (− 0.69)
3
-1
-2.07
-3.07
-2.07
-5.14
-0.69
3
-0.69
3
-1
2.12
1.12
3.55
4.67
0
-0.77
-0.77
-3.22
-3.99
1
0.53
1.53
2.75
4.28
Exercício:
Dada a equação algébrica:
P( x ) = x 3 − 6 x 2 − x + 30 = 0
pede-se determinar:
(a) o número de raízes reais positivas
(b) o número de raízes reais negativas
(c) um limitante superior para as raízes reais
(d) um limitante inferior para as raízes reais
(e) a forma obtida da aplicação do método de Honer.
(f) o valor numérico de P(x) nos pontos -2 e 99. usando a expressão
obtida no item interior.
1
-1.06
-0.06 = P ( -0.69)
= P' ( - 0.6)
− 0.06
= −0.68
4.28
ε 2 = x2 − x1 = − 0.68 − (− 0.69) = 0.01
⇒ x2 = −0.69 −
∴
ρ = −0.68
Exercício:
Dada a equação algébrica:
P( x ) = x 4 − 6 x 3 + 10 x 2 − 6 x + 9 = 0
pede-se determinar:
(a) o número de raízes reais positivas e negativas.
(b) um limitante superior e um limitante inferior para as raízes reais.
(c) a forma obtida da aplicação do método de Honer.
()
Pρ =?
3
-0.68
3
-1
-2.04
-3.04
-1
2.07
1.07
0
-0.73
-0.73
1
0.50
1.50
1
-1.02
0.02 = P ( -0.68)
Exercício:
Dada a equação algébrica:
P( x ) = x 5 − 9 x 4 + 7 x 3 + 185 x 2 − 792 x + 1040 = 0
pede-se determinar:
(a) o número de raízes reais positivas
(b) o número de raízes reais negativas
(c) um limitante superior para as raízes reais
Exercício:
Dada a equação algébrica:
P(x ) = 2 x 3 + x 2 − 2 = 0
Pede-se determinar:
(a) o número de raízes positivas
(b) o número de raízes negativas
(c) um limitante superior para as raízes reais
54
Resolução:
(d) um limitante inferior para as raízes reais
(e) um intervalo contendo no mínimo uma raiz real positiva
(f) uma raiz real positiva ρ no intervalo identificado no item
anterior (Birge-Vieta)
(g) o valor numérico de P ρ .
()
{g i (x )}
g 0 ( x ) = P( x ) ⇒ g 0 ( x ) = x 4 − 2.4 x 3 + 1.03 x 2 + 0.6 x − 0.32
g1 ( x ) = P' (x ) ⇒ g1 ( x ) = 4 x 3 − 7.2 x 2 + 2.06 x + 0.6 (÷ 4 )
g1 ( x ) = x 3 − 1.8 x 2 + 0.515 x + 0.15
g 2 ( x ) = −resto(g 0 ( x ) g1 ( x ))
(a) seqüência
()
Obs.: tomar ε ≤ 10−3
Resp.: ρ = 0.8581
x 4 − 2.4 x 3 + 1.03 x 2 + 0.6 x − 0.32
− x 4 + 1.8 x 3 − 0.515 x 2 − 0.15 x x − 0.6
2.2.9 MÉTODO DAS SEQÜÊNCIAS DE STURM
Seqüência de funções
seguinte modo:
g o (x ) = P(x )
{gi (x )}: g o (x ), g1 (x ),L, g n (x )
x 3 − 1.8 x 2 + 0.515 x + 0.15
− 0.6 x 3 + 0.515 x 2 + 0.45 x − 0.32
construída do
0.6 x 3 − 1.08 x 2 + 0.309 x + 0.09
− 0.565 x 2 + 0.759 x − 0.23
g1 ( x ) = P' ( x )
g k ( x ), k ≥ 2 , é igual ao simétrico do resto da divisão de g k − 2 por g k −1
∴ g 2 (x ) = +0.565 x 2 − 0.759 x + 0.23 (÷ 0.565)
O número de zeros da função y = P( x ) no intervalo (a,b) é a diferença
entre o número de variações de sinal da seqüência
g 0 , (a ), g1 (a ),L, g n (a ) e da seqüência g 0 (b ), g1 (b ),L, g n (b ) .
g 3 (x ) = −resto( g1 ( x ) g 2 ( x ))
⇒ g 2 (x ) = x 2 − 1.343x + 0.4071
x 3 − 1.8 x 2 + 0.515 x + 0.15 x 2 − 1.343 x + 0.4071
− x 3 + 1.343 x 2 − 0.4071 x − 0.457
Exemplo
Aplicar o método das seqüências de Sturm para localizar todas as
raízes reais de:
− 0.457 x 2 + 0.1079 x + 0.15
P( x ) = x 4 − 2.4 x 3 + 1.03 x 2 + 0.6 x − 0.32 = 0
∴ g 3 ( x ) = 0.5059 x − 0.336 (÷ 0.5059 )
+ 0.457 x 2 − 0.613 x + 0.1860
− 0.5059 x + 0.336
⇒ g 3 (x ) = x − 0.6642
55
g 4 ( x ) = −resto( g 2 ( x ) g 3 (x ))
Tabela:
2
x − 1.343 x + 0.4071 x − 0.6642
x
g0
g1
g2
g3
g4
VARIAÇÃO
− 0.6788 x + 0.4071
-1
+
-
+
-
+
4
+ 0.6788 x − 0.4509
0
-
+
+
-
+
3
1
-
-
+
+
+
1
2
+
+
+
+
+
0
3
+
+
+
+
+
0
− x 2 + 0.6642 x x − 0.6788
− 0.0438
∴ g 4 ( x ) = 0.0438
(b) Tabela de sinais:
Ls = ?
1
3
1
-2.4
1.03
0.6
-0.32
3.0
1.8
8.49
27.27
0.6
2.83
9.09
26.95
∴
Observações sobre a construção da tabela acima:
g0(3) = P(3) = 26.95 > 0
g1(3) = ? g1(x) = x3 - 1.8 x2 + 0.515x + 0.15
g1(3) = 12.495 > 0
g2(3) = ? g2(x) = x2 - 1.343 x + 0.4071
g2(3) = 5.3781
g3(3) = ?
g3(x) = x - 0.6642 ⇒ g3(3) > 0
g4(3) > 0
LS = 3
=P(3)
LI = ?
P( x) = x 4 − 2.4 x 3 + 1.03 x 2 + 0.6 x − 0.32
P(− x) = x 4 + 2.4 x 3 + 1.03 x 2 − 0.6 x − 0.32
1
1
1
2.4
1.03
-0.6
-0.32
1
3.4
4.43
3.83
3.4
4.43
3.83
3.51
(c) Interpretação:
Seja v(xi) o número de variações de sinal da seqüência {gi (x)} em
x = xi.
L I = −1
= P(-1)
56
v(−1) = 4
v ( 0) = 3
Observação quanto às raízes isoladas:
⇒ ρ1 ∈ (−1,0)
(i) verificação dos intervalos:
v ( 0) = 3
⇒ ρ 2 , ρ 3 ∈ (0,1)
v(1) = 1
v(1) = 1
v ( 2) = 0
P(−1) = 3.51 > 0
ρ1 ∈ (−1,0)
P(0) = −0.32 < 0
⇒ ρ 4 ∈ (1,2)
P(1) = −0.09 < 0
ρ 4 ∈ (1,2)
P(2) = 1.8 > 0
(d) continuação da aplicação do método de Sturm:
g0(0.6) = 0.022 > 0
g1(0.6) = ?
g1(0.6) = 0.027
g2(0.6) = ?
g2(0.6) = 0.0387
g3(0.6) = 0.6 - 0.6642 = -0.0642 < 0
g4(0.6) > 0
∴
0
-
+
+
-
+
3
0.6
+
+
-
-
+
2
1
-
-
+
+
+
1
∴ v ( 0) = 3
v(0.6) = 2
v(0.6) = 2
v(1)=1
∴P(−1)>0
P ( 0) < 0
P(0.6)>0
∴ρ 1 ∈ (−1,0)
∴ρ 2 ∈ (0,0.6)
P(1)<0 ∴ρ 3 ∈ (0,6,1)
P(2)>0 ∴ρ 4 ∈ (1,2)
(ii) raízes da equação P (x) = 0:
ρ1 = −0.5, ρ 2 =0.5, ρ 3 = 0.8, ρ 4 = 1.6
Exemplo completo:
⇒ ρ 2 ∈ (0,0.6)
Dada a equação algébrica
P( x ) = x 3 + 0.4 x 2 − 4.45 x + 2 = 0, determinar aproximações para as
suas raízes utilizando o método de Birge-Vieta (ε ≤ 0.01)
⇒ ρ3 ∈ (0.6,1)
57
Resolução:
1
(a) Regra de sinais de Descartes (número de raízes)
P( x ) = x 3 + 0.4 x 2 − 4.45 x + 2
+ +
− −
+
123
1
424
3
1
n+ = 2 ou 0 raízes reais positivas
2
P(− x ) = − x + 0.4 x + 4.45 x + 2
−
+ +
+
123
1
424
3
3
3
1
1
1
1
1
(b) Limitantes para as raízes
1
1
2
1
-2
-0.4
2
1.6
-4.45
3.2
-1.25
-2
-0.4
3
2.6
-4.45
7.8
3.35
-2
10.05
8.05
(c) Isolamento das raízes
Método de Laguerre
Ls = ?
1
-4.45
0.6
-3.85
2
n- = 1 raiz real negativa
1
-0.4
1
0.6
0. 4
1
1. 4
(c.1) Método das seqüências de Sturm:
0.4
2
2.4
(c.1.1) Seqüência {g i (x)}:
2
− 4. 45
1. 4
- 3.05
g 0 ( x) = x 3 + 0.4 x 2 − 4.45 x + 2
-4.45
4.8
0.35
2
0.7
2.7
g1 ( x) = 3x 2 + 0.8 x − 4.45 (÷3)
∴ Ls = 2
g1 ( x) = x 2 + 0.267 x − 1.483
LI= ?
P( x ) = x 3 + 0.4 x 2 − 4.45 x + 2
P(− x ) = − x 3 + 0.4 x 2 + 4.45 x + 2
− P(− x ) = x 3 − 0.4 x 2 − 4.45 x − 2
g 2 ( x) = - resto (g 0 ( x) / g1 ( x) )
58
∴ LI= -3
x
g0
g1
g2
g3
VARIAÇÃO
-3
-2
1
0
1
2
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
3
2
2
2
1
0
x 3 + 0.4 x 2 − 4.45 x + 2| x 2 + 0.267 x − 1.483
− x 3 − 0.267 x 2 +1.483 x x + 0.133
2
/ 0.133 x − 2.967 x + 2
− 0.133 x 2 − 0.036 x +0.197
/ − 3.003x + 2.197
Qρ1 ∈( −3, −2)
ρ 2 ∈ ( 0 , 1)
ρ 3 ∈ ( 1, 2 )
∴g 2 ( x) = 3.003x − 2.197
(c.2) Briot-Ruffini
∴g 2 ( x) = x − 0.732
P( x ) = x 3 + 0.4 x 2 − 4.45 x + 2
1
g 3 ( x) = - resto (g1 ( x) / g 2 ( x) )
1
0.267
0.732
0.999
0.732
1
2.0
1
-1.483
0.731
-0.752
1
1.0
1
∴g3 ( x) = 0.752
-4.45
4.8
0.35
2
0.7
2.7
0.4
1.0
1.4
-4.45
1.4
-3.05
2
-3.05
-1.05
-4.45
+0.6
-3.85
2
3.85
5.85
= P (2.0) > 0
= P (1.0) < 0
∴ ρ1 ∈ (1.0,2.0)
P (0) = 2 > 0 ⇒ ρ 2∈ (0,1)
(c.1.2) Tabela de sinais
LI = -3,
0.4
2.0
2.4
1
Ls = 2
-1.0
1
0.4
-1.0
-0.6
P (−2) = 4.5 > 0
ρ 3 ∈ (−3.0,− 2.0)
P (−3) = −8.05 < 0
59
= P (-1.0) > 0
(d) Verificação quanto à convergência
x0 = 1.5 (arbitrado)
ϕ ' ( x0 ) =
(e.1) Cálculo de ρ1 ( ρ1 ∈ (1.0,2.0))
P( x k )
xk +1 = xk −
P' ( x k )
xo = 1.5
P(1.5)
− 0.4
x1 = 1.5 −
= 1.5 −
= 1.61
P' (1.5)
3.5
ε1 = x1 − x0 = 1.61 − 1.5 = 0.11 > 10−2
P ( x0 ).P" ( x0 )
[P' ( x0 )]2
1
1.5
1
1.5
1
1.5
0.4
-4.45
+2
1.5
2.85
-2.4
1.9
-1.60
-0.4
1.5
5.1
3.4
3.5
x2 = 1.61 −
= P(1.5)
1
= P'(1.5)
1.61
1.5
1
1
4.9 = P" (1.5) / 2 ⇒ P" (1.5) = 9.8
1442443
1.61
O resto da terceira aplicação do método
de Briot-Ruffini é igual à metade da
derivada segunda de P(x) no ponto
considerado.
∴ ϕ ' ( x0 ) =
P(1.61)
P' (1.61)
1
0.4
-4.45
+2
1.61
3.2361
-1.9544
2.01
-1.2139 0.0456
1.61
5.8282
3.62
4.6143
= P'(1.61)
0.0456
= 1.60
4.6143
ε 2 = x2 − x1 = 1.60 − 1.61 = 0.01
∴ x2 = 1.61 −
(−0.4)(9.8)
= 01
.32
<31
4
24
(3.5) 2
∴ ρ1 = 1.60
Portanto, xo suficientemente próximo da raiz implicará na
convergência da aplicação do método.
Verificação:
(e) Cálculo das raízes
P(1.60) = ?
60
= P(1.61)
1
1.60
1
0.4 -4.45
1.60 3.20
2.0 -1.25
2
-2
0.0
P( x ) = an x n + an −1 x n −1 + L + a1 x + a0
= P(1.60)
em x=c (ou seja, P(c)). Deve ser utilizado o esquema a seguir:
Exercício: obter aproximações para as demais raízes usando BirgeVieta
bn = an
bn − k = c.bn − k +1 + an − k
1 ≤ k ≤ n − 1 (algoritmo de Briot - Ruffini)
r = c.b1 + a0
Exercício:
Dada a equação algébrica:
3
através do qual são obtidos os coeficientes do polinômio quociente:
2
Q(x ) = bn x n −1 + bn −1 x n − 2 + L + b2 x + b1
P ( x ) = x + 2 x + 10 x − 20 = 0
pede-se:
A seguir apresenta-se um esquema para o cálculo da derivada de um
polinômio:
(a) o número de raízes reais positivas (n+) e negativas (n-);
(b) os limitantes superior (Ls) e inferior (LI) para as raízes reais;
(c) um intervalo com extremos inteiros contendo exatamente uma raiz
real positiva, usando o método das sequüências de Sturm;
(d) verificar se o ponto médio do intervalo identificado em (c) satisfaz
o critério de convergência do método de Newton;
(e) calcular uma aproximação para a raiz isolada usando o método de
Birge-Vieta com ∈< 10 −2 .
Resposta: ρ = 1.3688
bn
c
bn-1
dn-1*c
bn-2
dn-2*c
bn bn-1+dn-1*c bn-2+dn-2*c
dn-1
dn-2
dn-3
…
…
b2
d2*c
b1
d1*c
b2+d2*c b1+d1*c
d1
resto
∴ dn-1 = bn;
Algoritmo para o cálculo do valor numérico de um polinômio:
dn-k-1 = bn-k + dn-k*c, k =1,2,...n-2;
resto = b1+d1*c
(valor numérico da derivada do polinômio).
Seja o problema de se calcular o valor numérico de um polinômio
P(x) da forma:
61
CAPÍTULO 3
SEJAM
A: VETOR DOS COEFICIENTES DO POLINÔMIO: A(0:N)
B: VETOR DOS COEF. DO POL. QUOCIENTE: B(1:N)
D: VETOR COEF. POL. P/ CÁLC. DE P’(C): D(1:N-1)
!
! INICIO ALGORITMO
! DADOS
SOLICITAR O GRAU DO POLINÔMIO
LER N
SOLICITAR OS COEFICIENTES
LER (A(I),I=0,...,N)
SOLICITAR C
LER C
!
! APLICAÇÃO DO ALGORITMO DE BRIOT-RUFFINI: P(C)
B(N)=A(N)
PARA K DE 1 ATÉ N-1
FAÇA
B(N-K)=C*B(N-K+1)+A(N-K)
FIM PARA
! VALOR NUMÉRICO DO POLINÔMIO
VNP = C*B(1) + A(0)
ESCREVA ‘P(‘,C,’)=’, VNP
!
! APLICAÇÃO DO ALGORITMO BRIOT-RUFFINI: P’(C)
D(N-1)=B(N)
PARA K DE 1 ATÉ N-2
FAÇA
D(N-K-1)=C*D(N-K)+B(N-K)
FIM PARA
! VALOR NUMÉRICO DERIVADA P’(C)
VNDP = C*D(1)+B(1)
ESCREVA ‘D/DX(P(‘,C,’))=’,VNDP
! FIM ALGORITMO
SISTEMAS DE EQUAÇÕES LINEARES
3.1. INTRODUÇÃO
Um problema de grande interesse prático é a resolução numérica de
um sistema S n de n equações lineares com n incógnitas.
a11 x1 + a12 x2 + ... + a1n xn = b1
S n : a21 x1 + a22 x2 + ... + a2 n xn = b2
a x + a x + ... + a x = b
n2 2
nn n
n
n1 1
Onde:
aij : coeficientes ,
x j : var iáveis,
ou
n
S n : ∑ aij x j = bi , i = 1,2,..., n
j =1
bi : cons tan tes (i, j = 1,2,...n).
Sob a forma matricial S n pode ser representado como:
onde:
a11
a
21
⋅ ⋅
A=
⋅ ⋅
⋅ ⋅
an1
a12 ... a1n
a22 ... a2 n
⋅
⋅
⋅
an 2 ... ann
é a matriz dos coeficientes.
62
AX = b
x1
x
2
⋅
X =
⋅
⋅
xn
é o vetor das variáveis
2 x1 + 3x2 − x3 = 5
S3 : 4 x1 + 4 x2 − 3x3 = 3
2 x − 3 x + x = −1
2
3
1
b1
b
2
⋅
e b = é o vetor cons tan te ou vetor dos termos cons tan tes.
⋅
⋅
bn
pede-se:
(a) escrevê-lo sob a forma matricial
(b) identificar a sua matriz completa
(c) mostrar que o vetor
1
x = 2
3
A matriz
a11 a12 ....a1n b1
a11 a12 ....a1n b1
[ A : b] = ⋅ ⋅ ⋅
⋅ ⋅ ⋅
⋅ ⋅ ⋅
an1 an 2 .... ann bn
é o vetor solução para o sistema
Solução
(a) forma matricial
2 3 − 1
4 4 − 3
2 − 3 1
1424
3
é chamada matriz aumentada ou matriz completa do sistema. A
resolução de um sistema linear consiste em calcular os valores de
x j , ( j = 1,..., n ) , caso existam, satisfazendo as n equações
x1
5
x2 = 3 (que é da forma AX = b)
x
− 1
3
{
{
matriz dos coeficientes vetor
de
( A)
var iáveis
(X )
simultaneamente.
(b) matriz completa
Exemplo:
2 3 − 1 5
[A : b] = 4 4 − 3 3
2 − 3 1 − 1
Dado o sistema linear S3 :
63
vetor dos
termos
cons tan tes
(b )
(c)
Exemplo:
Encontrar o vetor solução do sistema linear S 4 :
2 3 − 1 1 2.1+ 3.2 − 1.3 5
AX = 4 4 − 3 2 = 4.1+ 4.2 − 3.3 = 3 = b
2 − 3 1 3 2.1− 3.2 + 1.3 − 1
3x1 + 4 x2 − 5 x3 + x4 = −10 (1)
x2 + x3 − 2 x4 = −1 (2)
S4 :
4 x3 − 5 x4 =3 (3)
2 x4 = 2 (4)
SISTEMAS TRIANGULARES
Um sistema linear S n : AX = b é chamado triangular superior se a matriz
A = (a ij ) é tal que aij = 0 se j < i, (i, j = 1,2,..., n ) , ou seja:
Resolução:
eq. (4):
2 x4 = 2 ⇒
a11 x1 + a12 x2 + ... + a1n xn = b1
a22 x2 + ... + a2 n xn = b2
Sn :
M
ann xn = bn
x4 = 1
substituições retroativas
eq. (3):
4 x3 − 5 x4 = 3 ⇒ 4 x3 − 5 = 3 ⇒
Um sistema linear Sn = AX = b é chamado triangular inferior se a
matriz A = (aij ) é tal que a ij = 0 para j > i, ( j = 1,2,..., n ) , ou seja:
eq. (2):
x2 + x3 − 2 x4 = −1 ⇒
= b1
a11x1
a x + a x
= b2
Sn : 21 1 22 2
M
M
an1 x1 + an 2 x2 + ... + ann xn = bn
x 2 + 2 − 2 = −1 ⇒
x 2 = −1
eq. (1):
3x1 + 4 x2 − 5 x3 + x4 = −10
⇒ 3x1 + 4(− 1) − 5.2 + 1 = −10
⇒ 3x1 = 3 ⇒ x1 = 1
Observe-se que os sistemas triangulares em que aii ≠ 0, (1,..., n ) , são
facilmente resolvidos por substituição retroativa ou progressiva.
64
x3 = 2
1
− 1
∴o vetor solução é X =
2
1
Exemplo:
Seja resolver o sistema:
2 x1 + 3x2 − x3 = 5
S3 : 4 x1 + 4 x2 − 3x3 = 3
2 x1 − 3x2 + x3 = −1
Métodos Numéricos de Resolução:
Métodos diretos:
são métodos que determinam a solução exata (X) de um sistema linear
com um número finito de operações aritméticas elementares.
(1)(0 )
(2)(0 )
(3)(0 )
Resolução:
Triangularização do sistema original:
Métodos iterativos
são métodos que permitem obter uma solução aproximada X para
um sistema linear, utilizando-se de um método iterativo para gerar
uma seqüência de aproximações sucessivas X (1) , X (2 ) ,... a partir de
uma aproximação inicial escolhida X (0 ) . Quando um critério de
parada é satisfeito, o último vetor de aproximação X (k ) da seqüência é
tomado para X .
( )
Passo 1: eliminação de x1 das equações (2 )( 0 ) e (3)( 0 ) :
m2(1) =
(0 )
a21
4
=2
(0 ) =
a11
2
m3(1) =
2 x1 + 3x2 − x3 = 5
S3(1) : − 2 x2 − x3 = −7
− 6 x2 − 2 x3 = −6
3.2. MÉTODOS DIRETOS
3.2.1. MÉTODO DE ELIMINAÇÃO DE GAUSS
(0 )
a31
2
=1
(0 ) =
a11
2
(1)(1) = (1)(0 )
(2)(1) = (2)(0 ) − 2 * (1)(0 )
(3)(1) = (3)(0 ) − 1 * (1)(0 )
Passo 2: eliminação de x 2 da equação (3)(1) :
3.2.1.1. CARACTERIZAÇÃO GERAL
m2( 2 ) =
O método da Eliminação de Gauss consiste em transformar o
sistema linear original num sistema linear equivalente triangular
superior.
65
(1)
a32
−6
=3
(1) =
a22 − 2
2 x1 + 3x2 − x3 = 5
(1)(2 ) = (1)(1)
(2)(2 ) = (2)(1)
S3(2 ) : − 2 x2 − x3 = −7
(2 )
(1)
(1)
5 x3 = 15 (3) = (3) − 3 * (2)
Exemplo:
Resolver o sistema:
Resolução do sistema triangularizado:
determinação do vetor X por substituições retroativas:
(1)(2 )
(2)(2 )
2 x1 + 3x2 − x3 = 5
S3(2 ) : − 2 x2 − x3 = −7
(2 )
5 x3 = 15 (3)
Resolução:
Triangularização do sistema original:
(2 )
eq. (3) : 5 x3 = 15⇒ x3 = 3
(0 )
(2 )
m2(1) =
eq. (1)(2 ) : − 2 x1 + 3x2 − x3 = 5⇒2 x1 = 5 + 3 − 6⇒ x1 = 1
1
∴ X = 2
3
S 4(1) :
Cálculo do determinante de A:
(2 )
A
(0 )
(0 )
Passo 1: eliminação de x1 das equações (2 ) ,(3) e (4 ) :
eq. (2 ) : − 2 x2 − x3 = −7⇒2 x2 = 7 − 3⇒ x2 = 2
2 3 − 1
A = 4 4 − 3
2 − 3 1
(1)(0 )
(2)(0 )
(3)(0 )
(4)(0 )
x1 + 2 x2 + 3 x3 + 4 x4 = 10
2 x + x + 2 x3 + 3 x4 = 7
S4 : 1 2
3 x1 + 2 x2 + x3 + 2 x4 = 6
4 x + 3x + 2 x + x = 5
2
3
4
1
2 3 − 1
= 0 − 2 − 1
0 0
5
(0 )
a21
2
(0 ) =
a11
1
m3(1) =
(0 )
(0 )
a31
3
a41
4
(1)
=
=
3
m
=
=4
4
(0 )
(0 ) =
a11
1
a11
1
x1 + 2 x2 + 3 x3 + 4 x4 = 10
− 3 x2 − 4 x3 − 4 x4 = −13
− 4 x2 − 8 x3 − 10 x4 = −24
− 5 x2 − 10 x3 − 15 x4 = −35
(1)(1)
(2)(1)
(3)(1)
(4)(1)
(0 )
(0 )
(0 )
(0 )
(0 )
(0 )
= (2 ) − (1) * 2
= (3) − (1) * 3
= (4 ) − (1) * 4
Passo 2: eliminação de x 2 das equações (3)(1) e (4)(1)
m2(3) =
det (A (2 ) ) = 2 * (− 2) * 5 = −20
66
(1)
a32
−4 4
= = 1.333
(1) =
a22 − 3 3
m4(2 ) =
(1)
a42
−5
= 1.667
(1) =
a22 − 3
x1 + 2 x2 + 3x3 + 4 x4 = 10
x1 + 2 x2 + 3x3 + 4 x4 = 10
(1)(2 ) = (1)(1)
(2)(2 ) = (2)(1)
(2 ) − 3 x2 − 4 x3 − 5 x4 = −13
S4 :
(2 )
(1)
(1)
2.668 x3 − 3.335 x4 = − 6.671 (3) = (3) − 1.333 * (2)
(2 )
(1)
(1)
− 3.332 x3 − 6.665 x4 = −13.329 (4) = (4) − 1.667 * (2)
⇒ x1 + (2)(0.999) + (3)(0.002) + (4)(1.999) = 10
⇒ x1 = 10 − 7.996 − 0.006 − 1.998 ⇒ x1 = 0
0
0.999
∴x =
0.002
1.999
Passo 3: eliminação de x 3 da equação (4 )(2 ) :
m4(3 ) =
(2 )
a43
− 3.332
= 1.249
(2 ) =
a33
− 2.668
3.2.1.2. ALGORITMO PARA A ELIMINAÇÃO GAUSSIANA
x1 + 2 x2 + 3x3 + 4 x4 = 10
(1)(3 ) = (1)(2 )
(2)(3) = (2)(2 )
(3 ) − 3 x2 − 4 x3 − 5 x4 = −13
S4 :
(3 )
(2 )
− 2.668 x3 − 3.335 x4 = −6.671 (3) = (3)
(3 )
(2 )
(2 )
− 2.500 x4 = −4.997 (4) = (4) − 1.249 * (3)
Seja
S n : AX = b, A = (aij ), b = (bi ),1 ≤ i, j ≤ n , um sistema de n
equações lineares a n incógnitas.
Para k = 1,..., n − 1
/* k − esimo passo * /
Para i = k + 1,..., n
Determinação do vetor solução X por substituições retroativas:
(3 )
eq. (4) : − 2.5 x4 = −4.997 ⇒ x4 = 1.999
mi( k ) =
(3 )
eq. (3) :
− 2.668 x3 − 3.335 x4 = −6.671 ⇒ − 2.668 x3 − (3.335)(1.999) = −6.671
⇒
aik(k −1)
akk(k −1)
bi( k ) = bi(k −1) − mi(k )bk(k −1)
Para j = 1,..., n
x3 0.002
aij( k ) = aij(k −1) − mi(k )akj( k −1)
(3 )
eq. (2) :
− 3x2 − 4 x3 − 5 x4 = −13
fim para
fim para
fim para
⇒ − 3x2 − (4)(0.002) − (5)(1.999) = −13 ⇒ x2 = 0.999
eq. (1)(3 ) :
67
3.2.1.3 ESTRATÉGIAS DE PIVOTEAMENTO - ELIMINAÇÃO
GAUSSIANA:
máx ai1 = 3 = a21 ∴ permutação das linhas 1 e 2
i = 1,2,3 (i ≥ 1)
Estágio k: eliminação de xk das equações (k + 1), ..., n, para
1 ≤ k ≤ ( n − 1) .
PIVÔ DO ESTÁGIO K: akk (k = 1, ..., n - 1)
S3( 0)
(A) PIVOTEAMENTO PARCIAL
Escolhe-se um novo pivô para cada estágio k utilizando o algoritmo:
identifica-se:
máx aik = ark
S3(1)
i≥k
se r = k entao nao ha permutacao
senao
as linhas r e k sao permutadas entre si
fim se
− 3x1 − 5 x2 + 7 x3 = 7 (1)( 0)
: x1 + 0 x2 + 3x3 = 6 (2)( 0)
( 0)
2 x1 + 4 x2 + 0 x3 = 15 (3)
1
1
= − = −0.333
−3
3
2
2
=
= − = −0.667
−3
3
m2(1) =
m3(1)
− 3x1 − 5 x2 + 7 x3 = 7 (1)(1) = (1)( 0 )
: / (−1.665) x2 + 5.331x3 = 8.331 (2)(1) = (2)( 0 ) − (1)( 0) * (−0.333)
(1)
(0 )
( 0)
/ 0.665 x2 + 4.669 x3 = 19.669 (3) = (3) − (1) * (−0.667)
(ii) eliminação de x2 da equação (3)(1):
Estratégia de pivoteamento parcial:
máx ai 2 = 1.665 = a22 ∴ não há permutaçao de linha .
Ex.:
i = 2, 3
x1 + 0 x2 + 3x3 = 6 (1)
S3 : − 3x1 − 5 x2 + 7 x3 = 7 (2)
2 x + 4 x + 0 x = 15 (3)
2
3
1
(2 = 2)
m3( 2 ) =
(i) eliminação de x1 das equações (2) e (3):
∴ S3
Estratégia de pivoteamento parcial:
68
( 2)
0.665
= −0.399
− 1.665
− 3 x1 − 5 x 2 + 7 x 3 = 7 (1) ( 2) = (1) (1)
: − 1.665 x 2 + 5.331x 3 = 8.331 (2) ( 2) = (2) (1) − (1) ( 0) * (−0.333)
6.796 x 3 = 22.993 (3) ( 2 ) = (3) (1) − (2) (1) * (−0.399)
Exemplo
22.993
⇒ x3 = 3.383
6.796
= −1.665 x2 + (5.331)(3.383) = 8.331
eq.(3)( 2) = x3 =
eq(2)
( 2)
⇒
x1 + 0 x2 + 3 x3 = 6 (1)
S3 : − 3 x1 − 5 x2 + 7 x3 = 7 (2)
2 x + 4 x + 0 x = 15 (3)
2
3
1
x2 = 5.528
Resolução:
eq(1) ( 2 ) = −3x1 − (5)(5.828) + (7)(3.383) = 7
⇒
Passo 1: (k = 1)
x1 = −4.153
máx aij = máx aij = 7 = a23
(B) PIVOTEAMENTO COMPLETO
∀i , j ≥ k ∀i , j ≥ 1
De acordo com esta estratégia, no início do estágio k é escolhido para
pivô o elemento de maior módulo dentre todos os elementos que ainda
atuam no processo de eliminação:
permutar linhas (1) e (2);
a11 ← a23 ∴
permutar colunas (1) e (3).
Algoritmo:
identifica-se:
máx aij = ars
7 x3 − 5 x2 − 3 x1 = 7 (1)( 0)
S3 : 3 x3 + 0 x2 + x1 = 6 (2)( 0)
( 0)
0 x3 + 4 x2 + 2 x1 = 15 (3)
∀i , j ≥ k
Eliminação de x3 das equações 2( 0) e 3( 0) :
casos:
r = k e s = k : ok; (não há permutação a efetuar)
r = k e s ≠ k : permutar colunas s e k;
r ≠ k e s = k : permutar linhas r e k;
permutar linhas r e k;
r ≠ k es ≠ k:
permular colunas s e k;
fim casos.
m2(1) =
69
(1)
(1)
a21
3
a31
0
(1)
=
=
0
.
429
m
=
= =0
3
(1)
(1)
a11
7
a11
7
7 x3 − 5 x2 − 3 x1 = 7 (1)(1) = (1)( 0)
S3(1) : 2.145 x2 + 2.287 x1 = 2.997 (2)(1) =(2)( 0) − 0.429 * (1)( 0)
(1)
( 0)
( 0)
4 x2 + 2 x1 = 15 (3) = (3) − 0 * (1)
7 x3 − 5 x2 − 3 x1 = 7 (1)( 2 ) = (1)(1)
∴ S3( 2 ) : 4 x2 + 2 x1 = 15 (2)(2 ) = (2)(1)
1.215 x1 = −5.043 (3)( 2 ) = (3)(1) − 0.536 * (2)(1)
Passo 2: (k = 2)
Determinação do vetor X por substituições retroativas
7 x3 − 5 x2 − 3 x1 = 7
(1)
S3 : 2.145 x2 + 2.287 x1 = 2.997
4 x + 2 x = 15
2
1
eq.(3) ( 2) = x1 = −4.151
eq.(2) ( 2) = x2 = 5.825
eq.(1) ( 2) = x3 = 3.382
max aij = max aij = 4 = a32
Exemplo: [RUGGIERO, LOPES: 1996]
∀i , j ≥ k ∀i , j ≥ 2
0.0002 x1 + 2 x2 = 5
S2 :
2 x1 + 2 x2 = 6
(sistema de aritmética de ponto flutuante de 3 dígitos (t = 3))
a22 ← a32 {permutar linhas 2 e 3
7 x3 − 5 x2 − 3x1 = 7 (1)(1)
∴ S3(1) : 4 x2 − 2 x1 = 15 (2)(1)
(1)
2.145 x2 + 2.287 x1 = 2.997 (3)
Resolução
(A) Sem pivoteamento:
Eliminação de x2 da equação 3(1) :
m3( 2) =
m2(1) =
(1)
a32
2.145
=
= 0.536
(1)
a22
4
S
70
(1)
2
0.2 × 101
= 1 × 104 = 0.1 × 105
−3
0.2 × 10
0.2 × 10−3 x1 + 0.2 × 101 x2 = 0.5 × 101 (1)(1) = (1)(0 )
: − 0.2 × 105 x = − 0.5 × 105 (2)(1) = (2)( 0) − (1)(0 ) * m
2
43 2 14243
14=2
(1)
= ( 2)
=
= 0.2 × 101 − (0.2 × 101 )(0.1 × 105 ) = 0.2 × 101 − 0.2 × 105 =
0.2 × 10 −3 x1 + 0.2 × 101 x2 = 0.5 × 101 (1)
S2 :
0.2 × 101 x1 + 0.2 × 101 x2 = 0.6 × 101 (2)
0.00002 × 105 − 0.2 × 105 = −0.2 × 105
(I) eliminando-se x1 da eq. (2)
=
= 0.6 × 101 − (0.1 × 105 )(0.5 × 101 ) = 0.6 × 101 − 0.5 × 105
5
5
Estratégia de pivoteamento parcial
5
= 0.00006 × 10 − 0.5 × 10 = −0.5 × 10
máx aik = máx aik = 0.2 × 101 = a21
i ≥ k i ≥1
∴ permutar linhas (1) e (2)
Vetor solução:
eq. (2) (1) :
− 0.2 × 105 x2 = −0.5 × 105 ⇒ x2 = 0.25 × 10
0.2 × 101 x1 + 0.2 × 101 x2 = 0.6 × 101 (1)( 0)
∴ S3 :
0.2 × 10 − 3 x1 + 0.2 × 101 x2 = 0.5 × 101 (2)( 0)
eq. (1) (1) :
0.2 × 10−3 x1 + (0.2 × 101 )(0.25 × 101 ) = 0.5 × 10
144424443
m2(1) =
0.05 x10 2
0.5 x10
⇒ x1 = 0
0.2 × 10−3
= 0.1 × 10 − 3
0.2 × 101
0.2 × 101 x1 + 0.2 × 101 x2 = 0.6 × 101 (1)(1) = (1)( 0)
0.2 × 101 x2
= 0.5 × 101 (2)(1) = (2)( 0) − (1)( 0) * m2
∴ S3(1) :
14243
0.2×101 −1 ( 0.2×10 −3 −)2× (0.2×101 ) =
10 − 0.04×10 =
== 00..22××10
1
− 0.000 4×101 = 0.2×101
0
∴X =
2.5
Observação:
Substituindo-se na equação (2) ( 0) , obtém-se:
2 x1 + 2 x2 = 2 × 2.5 = 5 ≠ 6
eq. (2) (1) :
0.2 × 101 x2 = 0.5 × 101 ⇒ x2 =
(B) Com pivoteamento (parcial)
eq. (1) (1) :
71
0.5 × 101
= 0.25 × 10
0.2 × 101
0.2 × 101 x1 + (0.2 × 101 )(0.25 × 101 ) = 0.6 × 101
144424443
0.05×10
0.5×101
⇒ x1 = 0.5
3 − 1
2
5
A = 4
4 − 3 b = 3
− 1
2 − 3
1
2
0.5
∴X =
2.5
Matriz aumentada:
A
I
B 6
48 }
47
4
8
647
2
3 − 1 5 1 0 0 (1)( 0)
[ A : b : I ] = 4
4 − 3 3 0 1 0 (2)( 0)
2 − 3
1 − 1 0 0 1 (3)( 0)
Obs.: Substituindo nas eq. (1) e (2), obtém-se:
(2)2 x1 + 2 x2 = 2.(0.5) + 2.(2.5) = 6
(1)(0.2 x10− 3 )(0.5) + (0.2 x101 )(0.25 x10) =0.1x10 − 3 + 0.05 x102
= 0.05 x10 2 = 0.5 x10 = 5
Passo 1:
3.2.2. O MÉTODO DE ELIMINAÇÃO DE GAUSS-JORDAN
1 1.5 − 0.5 2.5 0.5 0 0 (1) = (1) / 2
0 − 2.0 − 1.0 − 7 − 2.0 1 0 ( 2)(1) = −4 * (1) (1) + ( 2)( 0)
0 − 6.0 2.0 − 6 − 1 0 1 (1)
(1)
(0)
(3) = −2 * (1) + (3)
(1)
(0)
3.2.2.1. CARACTERIZAÇÃO GERAL
Passo 2:
Dada a matriz aumentada
[A : b : I]
( 2)
( 2)
(1)
1 0 − 1.25 − 2.75 − 1.0 0.75 0 (1) = −1.5 * ( 2) + (1)
( 2)
(1)
0 1 0.5
3.5
1 − 0.5 0 ( 2)
= ( 2) /( −2.0)
0 0 5.0
15
5
− 3 1 (3) ( 2) = 6 * ( 2)( 2) + (3)(1)
As transformações elementares para se obter uma matriz identidade a
partir de A quando aplicados a b e a I conduzem, respectivamente, a
X, vetor solução do sistema, e a A-1, inversa de A, ou seja
[A : b : I] transformações → [I : X : A-1]
elementares
Passo 3:
1 0 0
0 1 0
0 0 1
424
3
1
I
Exemplo:
72
1
2
3{
X
0.25 0
0.25 (1) (3) = 1.25 * (3)(3) + (1)( 2)
0.5 − 0.2 − 0.1 ( 2) (3) = −0.5 * (3) (3) + ( 2) ( 2)
(3)
( 2)
1
− 0.6 0.2 (3) = (3) / 5
14442444
3
A−1
0.25
1
0.25 0
−1
∴ X = 2 e A = 0.5 − 0.2 − 0.1
3
1
− 0.6 0.2
w + 2 x − 12 y + 8 z = 27
5w + 4 x + 7 y − 2 z = 4
S4 :
− 3w + 7 x + 9 y + 5 z = 11
6 w − 12 x − 8 y + 3 z = 49
3.2.2.2. ALGORITMO PARA O MÉTODO DE JORDAN
Pede-se:
a) Determinar o seu vetor solução (X) e a inversa da matriz dos
coeficientes (A-1 ) usando o método de Jordan;
b) Determinar o seu vetor solução (X) e o determinante da matriz
dos coeficientes usando o método de eliminação de Gauss;
Resp.:
SEJA C A MATRIZ AUMENTADA [A : b : I]
PARA I DE 1 ATE N FACA
(* PASSO I *)
PIVOT = C(I,I)
(* ELEMENTO DA DIAGONAL PRINCIPAL = 1 *)
PARA J DE 1 ATE (2 * N + 1) FACA
C(I,J) = C(I,J)/PIVOT
FIM PARA
3
− 2 −1
X = A =
1
5
(* DEMAIS ELEMENTOS NA COLUNA I IGUAIS A 0 *)
0.0356 0.1345 − 0.0249 0.0362
0.0590 0.0566 − 0.0289 − 0.0715
− 0.0506 0.0098 0.0652 0.0329
0.0299 − 0.0163 0.1081 0.0626
PARA K DE 1 ATÉ N
SE K <> I ENTAO (* NÃO É LINHA DO PIVOT *)
ENTÃO
FMULT = -C(K,I)
PARA J DE 1 ATE (2 * N + 1) FACA
C(K,J) = C(K,J) + FMULT*C(I,J)
FIM PARA
FIM SE
FIM PARA
FIM PARA
Exercício: determinar a inversa da matriz de Wilson
Exercício:
Dado o sistema linear
Resp.:
10
7
A=
8
7
7
5
6
5
8
6
10
9
7
5
utilizando o método de Jordan
9
10
25 − 41 10 − 6
68 − 17 10
−1 − 41
A =
5 −3
10 − 17
− 6 10 − 3 2
73
10 − 5
5 − 10
− 10
30 − 35
19
−1
A = 10 − 35
46 − 27
19 − 27
17
−5
1 − 4 6 − 4 1
Exercíçio:
determinar o vetor solução e a inversa da matriz dos coeficientes do
sistema abaixo:
x1 + 2 x2 + 3 x3 + 4 x4 = 10
2 x + x + 2 x + 3 x = 7
1
2
3
4
3 x1 + 2 x2 + x3 + 2 x4 = 6
4 x1 + 3 x2 + 2 x3 + x4 = 5
3.3. MÉTODOS ITERATIVOS
3.3.1. GERAL
Resp.:
− 3,28 x 10−7
1.0
X =
−7
2.09 x 10
2.0
Um sistema linear é dito ser esparso quando a matriz A dos
coeficientes possui uma grande porcentagem de elementos nulos. Para
tais sistemas o emprego do método da Eliminação de Gaus para a sua
resolução não é aconselhável, dado que este método não preserva
esparsidade, ou seja, durante o processo de eliminação muitos
elementos nulos poderão se tornar não nulos. Observe-se que sistemas
lineares de grande porte são em geral esparsos.
0
0.1
− 0.4 0.5
0
.
5
−
1
.
0
0
.
5
0
−1
A =
0.5 − 1.0
0.5
0
0
0.5 − 0.4
0.1
Exercício: Inverter a matriz de Pascal
1
1
A = 1
1
1
1
− 4
6
− 4
Os métodos iterativos preservam a esparsidade de A, pois os
elementos desta matriz não são alterados. Apresentam ainda uma
outra vantagem sobre o método da Eliminação de Gauss dada pelo
fato de que são métodos relativamente insensíveis ao crescimento de
erros de arredondamento.
1 1 1 1
2 3 4 5
3 6 10 15
4 10 20 35
5 15 35 70
A idéia central dos métodos iterativos é generalizar o M.I.L. utilizado
na busca de raízes de uma equação, estudado anteriormente.
Resp.:
Considere um sistema linear da forma:
74
Sn : AX=b:
3.3.2 MÉTODO DE GAUSS-JACOBI:
a11 x1 + a12 x2 + ... + a1n xn = b1 (1)
a x + a x + ... + a x = b (2)
22 2
2n n
2
S n : 21 1
M
an1 x1 + an 2 x2 + ... + ann xn = bn (n)
3.3.2.1 CARACTERIZAÇÃO
Suponha-se que:
xi( k ) designa a aproximação de ordem k de xi;
(
Obtém-se a partir de Sn as equações:
1
x1 =
(b1 − a12 x2 − a13 x3 − ... − a1n xn )
a11
x2 =
1
(b2 − a21x1 − a23 x3 − ... − a2 n xn )
a22
xi( k +1) =
1
(bn − an1 x1 − an 2 x2 − ... − an , n −1 xn −1 )
ann
i −1
1
bi − ∑ aij x j −
aii
j =1
n
∑a x
ij
j = i +1
(k )
j
k = 0,1,2,...
Exemplo: (Método Iterativo de Gauss-Jacobi)
1
(bi − ai1 x1 − ... − ai ,i −1 xi −1 − ai ,i +1 xi +1... − ain xn )
aii
⇔ xi =
i −1
1
bi − ∑ aij x (jk ) −
aii
j =1
i = 1,2,..., n
ou, equivalentemente,
xi =
T
Calculam-se os vetores aproximativos X(1), X(2), ..., a partir de um
vetor de aproximação inicial X(0), utilizando-se do esquema:
M
xn =
)
X ( k ) = x1( k ) , x2( k ) ,..., xn( k ) designa o vetor de aproximação de ordem k
do vetor solução do sistema (k = 0, 1, 2,...).
n
∑a x
ij
j = i +1
j
Seja resolver o sistema linear:
, i = 1,2,..., n
10 x1 + 2 x 2 + x3 = 7
x1 + 5 x 2 + x3 = −8
2 x + 3 x + 10 x = 6
2
3
1
Pelo método iterativo de Gauss-Jacobi, com X
75
( 0)
0.7
= − 1.6 e ε ≤ 0.05
0.6
Cálculo de ε1 :
Resolução:
X
Obtenção da forma iterativa:
1
1
(7 − 2 x2 − x3 ) ⇒ x1( k +1) =
7 − 2 x2( k ) − x3( k )
10
10
1
1
x2 = (−8 − x1 − x3 ) ⇒ x2( k +1) = (−8 − x1( k ) − x3( k ) )
5
5
1
1
6 − 2 x1( k ) − 3 x2( k )
x3 = (6 − 2 x1 − 3 x2 ) ⇒ x3( k +1) =
10
10
k = 0,1,2,...
(
x1 =
)
(
(1)
−X
1≤ i ≤ 3
Cálculo de X ( 2 ) :
)
1
1
7 − 2 x2(1) − x3(1) = (7 − 2.(−1.86) − 0.94) = 0.98
10
10
1
1
= − 8 − 2 x1(1) − x3(1) = (−8 − 2 − 0.96 − 0.94) = − 1.98
5
5
1
1
=
6 − 2 x1(1) − 3 x2(1) = (6 − 2.(0.96) − 3(−1.86)) = 0.97
10
10
x2( 2)
x3( 2)
x2(1)
(1)
3
x
1
1
=
7 − 2.x2( 0) − x3( 0) = (7 − 2(−1.6) − 0.6) = 0.96
10
10
1
1
= − 8 − x1(0 ) − x3( 0) = (−8 − 0.7 − 0.6) = −1.86
5
5
1
1
=
6 − 2 x1( 0) − 3 x2( 0) = (6 − 2.(0.7) − 3(−1.6)) = 0.94
10
10
(
(
)
∴X
∴X
)
(
( 2)
)
0.98
= − 1.98
0.97
Cálculo de ε 2
)
X
(1)
)
(
)
(
(
x1( 2) =
Cálculo de X (1) :
x
0.96 −0.70 0.26
= − 1.86 − (−1.6) = − 0.26
0.94 − 0.6
0.34
⇒ max xi(1) − xi(0 ) = 0.34 > 0.05
Aplicação do método:
(1)
1
( 0)
0.96
= − 1.86
0.94
( 2)
−X
(1)
0.98 − 0.96 0.02
= − 1.98 − (−1.86) = − 0.12
0.97 − 0.94 0.03
⇒ max xi( 2) − xi(1) = 0.12 > 0.05
1≤ i ≤ 3
76
Cálculo de X (3) :
1
1
7 − 2 x2( 2) − x3( 2 ) = (7 − 2.(−1.98) − 0.97) = 0.999
10
10
1
1
= − 8 − 2 x1( 2) − x3( 2 ) = (−8 − 0.98 − 0.97) = −1.99
5
5
1
1
6 − 2 x1( 2 ) − 3 x2( 2) = (6 − 2.(0.98) − 3(−1.98)) = 0.998
=
10
10
(
x1(3) =
x2(3)
x3(3)
1
X = − 2
1
)
(
)
(
∴ X ( 3)
3.3.2.2 MÉTODO ITERATIVO DE GAUSS-JACOBI - UM
CRITÉRIO DE CONVERGÊNCIA
)
O teorema a seguir estabelece uma condição suficiente para a
convergência do método iterativo de Gauss-Jacobi.
0.999
= − 1.99
0.998
TEOREMA (critério das linhas)
Cálculo de ε 3 :
X
( 3)
−X
(1)
Seja o sistema linear S n : AX = b e seja
0.999 − 0.98 0.019
= − 1.99 − (−1.98) = − 0.01
0.998 − 0.97 0.028
n
α k = ( ∑ akj ) / akk
j =1
j≠k
⇒ max xi(3) − xi( 2 ) = 0.028 < 0.05
Se α = máx α k < 1 então o método iterativo de Gauss-Jacobi gera uma
1≤ i ≤ 3
1≤ k ≤ n
seqüência {X ( k ) } convergente para a solução do sistema dado,
independentemente da escolha da aproximação inicial, X ( 0) .
0.999 é a solução do sistema linear,
⇒ X = − 1.99 com e ≤ 0.05, obtida pelo
0.998 método iterativo de Gass - Jacobi.
Exemplo:
Estude o sistema do exemplo anterior quanto a convergência.
Observação: a solução exata é o vetor:
Resolução:
77
Matriz dos coeficientes:
1 3 1
A = 5 2 2
0 6 8
10 2 1
A = 1 5 1
2 3 10
Cálculo de α k , k = 1,2,3 :
Cálculo de α k , k = 1,2,3 :
α1 =
2 +1
= 0.3 < 1
10
∴ α = max α k < 1
1≤ k ≤ 3
α2 =
3 +1
= 4 >1
1
α1 =
1+1
2+3
= 0.4 < 1 α 3 =
= 0.5 < 1
5
10
Permutando-se a primeira equação com a segunda obtém-se o sistema
linear equivalente:
⇒ seqüência{X ( k ) }será convergente.
S
(1)
3
Exemplo:
Estudar o sistema
5 x1 + 2 x2 + 2 x3 = 3
: x1 + 3 x2 + x3 = −2
6 x + 8 x = −6
2
3
cuja matriz dos coeficientes é:
x1 + 3 x2 + x3 = −2
S3 : 5 x1 + 2 x2 + 2 x3 = 3
6 x + 8 x = −6
2
3
(1)
A
quanto a convergência.
5 2 2
= 1 3 1
0 6 8
Cálculo de α k , k = 1,2,3 :
Resolução:
α1 =
Matriz dos coeficientes:
2+2
= 0 .8 < 1
5
α2 =
1+1
0+6
= 0 .7 < 1 α 3 =
= 0 .75 < 1
3
8
{ }
∴ α = máx α k = 0.8 < 1 ⇒ seqüência X ( k ) será convergente.
1≤ k ≤ 3
78
3.3.3 MÉTODO DE GAUSS-SEIDEL
Obtenção da forma iterativa
3.3.3.1. CARACTERIZAÇÃO
1
(k +1) 1
(k )
(k )
x1 = (7 − 2 x2 − x3 ) ⇒ x1
= 7 − 2 x2 − x3
10
10
1
(k +1) 1
(k +1)
(k )
x2 = (−8 − x1 − x3 ) ⇒ x2
= − 8 − x1
− x3
5
5
Os vetores aproximativos são obtidos através do esquema:
i −1
n
1
(k +1)
(k +1)
(k )
xi
=
bi − ∑ aij x j
− ∑ aij x j
aii
j =1
j =i +1
i = 1,2,..., n
k = 0,1,2,...
1
(k +1) 1
(k +1)
(k +1)
x3 = (6 − 2 x1 − 3 x2 ) ⇒ x3
= 6 − 2 x1
− 3 x2
,
10
10
Observa-se que, no processo iterativo de Gauss-Seidel, no momento
de se calcular xi( k +1) , são usados os valores de x1( k +1) ,..., xi(−k1+1) , que já
Aplicação do método:
Cálculo de X (1) :
foram calculados, e os valores xi(+k1) ,..., xn( k ) restantes.
1
(1) 1
(0)
(0)
x1 = (7 − 2 x2 − x3 ) = (7 − 2.(−1.6) − 0.6 ) = 0.96
10
10
1
(1) 1
(1)
(0)
x2 = (−8 − x1 − x3 ) = (− 8 − 0.96 − 0.6 ) = −1.912
5
5
1
(1) 1
(1)
(1)
x3 = (6 − 2 x1 − 3 x2 ) = (6 − 2.(0.96) − 3(−1.912)) = 0.9816
10
10
Exemplo: Resolver o sistema linear:
10 x1 + 2 x2 + x3 = 7
x1 + 5 x2 + x3 = −8
2 x + 3 x + 10 x = 6
2
3
1
usando o método iterativo de Gauss-Seidel, com:
X
(0)
∴X
0.7
= − 1.6 e ε ≤ 0.05
0.6
(1)
0.96
= − 1.912
0.9816
Cálculo de ε1 :
Resolução:
79
k = 0,1,2,...
X
(1)
−X
( 0)
1
(3) 1
(2)
(2)
x1 = (7 − 2 x2 − x3 ) = (7 − 2.(−1.9932) − 1.0011) = 0.9985
10
10
1
(3) 1
(3)
( 2)
x2 = (−8 − x1 − x3 ) = (− 8 − 0.9985 − 1.0011) = −1.9999
5
5
1
(3) 1
(3)
(3)
x3 = (6 − 2 x1 − 3x2 ) = (6 − 2.(0.9985) − 3(−1.9999)) = 1.0003
10
10
0.96 − 0.7
0.26
(1)
( 0)
= − 1.912 − ( −1.6) = − 0.31 ⇒ máx xi − xi
= 0.38 > 0.05
0.9816 − 0.6 0.38 1≤i ≤3
Cálculo de X ( 2 ) :
1
(2) 1
(1)
(1)
x1 = (7 − 2 x2 − x3 ) = (7 − 2.(−1.912) − 0.9816) = 0.9842
10
10
1
(2) 1
(2)
(1)
x2 = (−8 − x1 − x3 ) = (− 8 − 0.9842 − 0.9816 ) = −1.9932
5
5
Cálculo de ε 3 :
1
1
( 2)
( 2)
( 2)
x3 = (6 − 2 x1 − 3 x2 ) = (6 − 2.(0.9842 ) − 3(−1.9932)) = 1.0011
10
10
∴X
( 2)
X
0.9842
= − 1.9932
1.0011
−X
(2)
⇒ max xi
1≤i ≤3
Cálculo de ε 2 :
3
0.9985 − 0.9842 0.01
= − 1.9999 − (−1.9932) = 0.0067
1.0003 − 1.0011 0.0008
− xi
2
= 0.01 < 0.05
⇒ a solução X do sistema linear, com ε ≤ 0.05 , obtida pelo método
iterativo de Gauss-Seidel, é dada por:
0.9842 − 0.96
0.02
X
−X
= − 1.9932 − (−1.912) = − 0.08,
1.0011 − 0.9816 0.02
( 2)
(1)
⇒ máx xi − xi = 0.08 > 0.05
1≤i ≤3
( 2)
(3)
(1)
X =X
Cálculo de X (3) :
(3)
0.9985
= − 1.9999
1.0003
(Note-se que, de fato, a solução obtida satisfaz o critério ε ≤ 0.01 )
80
3.3.3.2. ESTUDO DA CONVERGÊNCIA DO MÉTODO DE
GAUSS-SEIDEL
2 x1 + x2 − 0.2 x3 + 0.2 x4 = 0.4
0.6 x1 + 3 x2 − 0.6 x3 − 0.3 x4 = − 7.8
S4 =
− 0.1x1 − 0.2 x2 + x3 + 0.2 x4 = 1.0
0.4 x + 1.2 x + 0.8 x + 4 x = −10.0
1
2
3
4
(A) CRITÉRIO DE SASSENFELD
O "critério de Sassenfeld" propicia uma condição suficiente para a
convergência do método iterativo de Gauss-Seidel.
Teorema:
Seja Sn : AX = b um sistema
aii ≠ 0, i = 1,2,..., n e sejam
1 n
a1 j
∑
a11 j = 2
n
1 i −1
βi =
aij β j + ∑ aij
∑
aii j =1
j =i +1
linear
de
ordem
n
Resolução:
Cálculo dos β k ,1 ≤ k ≤ 4 :
com
β1 =
β2 =
β1 =
i = 2,3,..., n
1
2
1
3
1
(1 + 0.2 + 0.2) = 0.7
β 3 = (0.1x 0.7 + 0.2 x0.44 + 0.2) = 0.358
(0.6 x 0.7 + 0.6 + 0.3) = 0.44
β4 =
1
1
4
( 0.4 x 0.7 + 1.2 x 0.44 + 0.8 x 0.358) = 0.2736
⇒ M = máx β i = 0.7 < 1
1≤ i ≤ 4
{ }
⇒ a seqüência X ( k ) gerada pelo método iterativo de Gauss-Seidel
será convergente.
M = max βi
1≤i ≤ n
{ }
A condição M < 1 é suficiente para que a seqüência X ( k ) gerada
pelo método de Gauss-Seidel seja convergente independentemente da
aproximação inicial X ( 0) . Além disto, quanto menor for β mais rápida
será a convergência.
Exemplo:
estudar o sistema linear seguinte quanto a convergência segundo
critério de Sassenfeld:
Exemplo:
Estudar o sistema linear seguinte quanto à convergência segundo o
"critério de Sassenfeld":
2 x + x + 3 x = 9
3
1 2
S3 − x2 + x3 = 1
+ 3 x3 = 3
x1
81
Resolução:
(B) CRITÉRIO DAS LINHAS
1
β1 = (1 + 3) = 2 > 1
2
O critério das linhas diz que se α = máx α k < 1 , onde
1≤ k ≤ n
n
α k = (∑ akj ) / akk ,
Permutando-se entre si as equações (1) e (3), obtém-se:
j =1
j ≠k
x1 + 3 x3 = 3 (1)'
S = − x2 + x3 = 1 (2)'
2 x + x + 3 x = 9 (3)'
3
1 2
1
β1 = (0 + 3) = 3 > 1
1
Permutando-se entre si a 1a e a 3a colunas de S '3 obtém-se:
então o método de Gauss-Seidel gera uma seqüência convergente.
'
3
Exemplo:
Estudar o sistema linear:
3 x + x = 3
3
1
S3 = x1 − x2 = 1
3 x1 + x2 + 2 x3 = 9
quanto à convergência segundo os critérios de Sassenfeld e das linhas.
3 x3 + x1 = 3
S = x3 − x2 = 1
3 x + x + 2 x = 9
2
1
3
''
3
Resolução:
1
1 1
β1 = (0 + 1) = 1 / 3 β 2 = 1 × + 0 = 1 / 3
3
1 3
1 1
1
β3 = 3 × + 1× = 2 / 3
2 3
3
M = máx β i =
1≤ i ≤ 3
(a) Critérios das linhas:
0 +1 1
=
3
3
1+ 0
= 1 ⇒ o critério das linhas não é satisfeito.
α2 =
1
3 +1
α3 =
= 2 < 1
2
α1 =
2
<1
3
{ }
⇒ a seqüência X ( k ) gerada pelo método iterativo de Gauss-Seidel
para o sistema S''3 será convergente.
82
(b) Critério de Sassenfeld
0 +1 1
β1 =
= <1
3
3
1 × (1 / 3) + 0
β2 =
=
1
1
1
3 × + 1×
3
3=
β3 =
2
Exercício:
Usando o "critério de Sassenfeld", verifique para que valores de k se
tem a garantia de que o método de Gauss-Seidel vai gerar uma
seqüência convergente para a solucão do sistema.
1
< 1 ⇒ o critério de Sassenfeld é satisfeito
3
2
< 1
3
kx + 3 x + x = 1
2
3
1
S3 = kx1 + 6 x2 + x3 = 2
x1 + 6 x2 + 7 x3 = 3
Exercício:
Resolva o sistema abaixo pelo método de Gauss-Seidel. Considere
X ( 0) = (0,0,0)T e uma precisão ε < 10 −3 .
Exercício:
Dado o sistema linear:
0 x1 1
4 −1 0
− 1 4 − 1 0 x 1
2 =
S4
0 − 1 4 − 1 x3 1
0 − 1 4 x4 1
0
Pede-se:
(a) Verificar se o critério de Sassenfeld é satisfeito
(b) Resolver por Gauss-Seidel, se possível,
X (0 ) = (0,0,0,0)T e uma precisão ε < 10 −2 .
Resp.:
(a) M = 0.3821
1 − 1 x1 2
1
S3 = 2
4
2 x2 = 6
− 2 − 1 4 x3 − 3
Resp.:
X = (1.9,0.4,0.3)T
considerando
Algoritmo: Método Iterativo de Gauss-Seidel
(b) X = ( 0. 364 0. 455 0. 455 0. 364 ) T
83
Início (* Gauss-Seidel *)
Solicite o número de equações (N)
Leia N
(* leitura dos elementos: matriz a e vetor b
*)
Para i de 1 até N
Faça
Solicite b(i)
Leia b(i)
Para j de 1 até N
Faça
Solicite a(i,j)
Leia a(i,j)
Então
M=1
Fim se
Fim Para (* k *)
Fim enquanto
Para k de 1 até N
Faça
Escreve “x(“,k,”) = “, x(k)
Fim para
Fim (* Gauss-Seidel *)
Agradecimento:
Fim para
Fim para
Solicite a precisão (E)
Leia E
(* inicialização *)
Para k de 1 até N faça x(k) = 0;
M = 1 (* auxiliar: número de iterações *)
Enquanto M <> 0
Faça
Para k de 1 até N
faça
Tmp = x(k)
S = 0
Para j de 1 até n
Faça
Se (k <> j)
Então
S = S + a(k,j)* x(j)
Fim Se
Fim para (* j *)
X(k) = (b(k)-S)/a(k,k)
Se |x(k) – tmp| > E
Ao Polo Computacional do Campus da UNESP - Guaratinguetá, em
particular à equipe de digitação, cujo apoio foi essencial para a
produção do presente trabalho.
BIBLIOGRAFIA
1.
BARROSO, L.C. & outros.
Editora Harbra Ltda, 1987.
Cálculo Numérico (com aplicações).
2.
DORN, W.S. & MAcCRACKEN, D. D. Cálculo Numérico com
Estudo de Casos em Fortran IV. Campus, 1978.
3.
FRANCO, N. B. Cálculo Numérico. São Paulo: Pearson Prentice
Hall, 2006.
4.
MAURER, W. A. Curso de Cálculo Diferencial e Integral: Funções
de Várias Variáveis e Aplicações. São Paulo: Edgard Blücher Ltda, 1968.
5.
RUGGIERO, M.A.G. & LOPES, V.L.R. Cálculo Numérico Aspectos
Teóricos e Computacionais. São Paulo: MAKRON Books, 1996.
84
Download
