Cálculo Numérico - Apostila - Português

- um número em aritmética de ponto flutuante está normalizado se d1 ≠ 0

unesp

CAMPUS DE GUARATINGUETÁ Computação e Cálculo Numérico Prof. G.J. de Sena - Depto. de Matemática – Ed. 2005.

- o número máximo de dígitos da mantissa (t) é definido em termos do comprimento da palavra do computador

CAPÍTULO 1

- dado um número N, sua representação em aritmética de ponto flutuante de t dígitos é efetuada por truncamento ou arredondamento.

ARITMÉTICA DE PONTO FLUTUANTE

- erros decorrentes da impossibilidade de se representar um número dado:

1.1. Representação de Números num Sistema de Aritmética de Ponto Flutuante 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:

"OVERFLOW"

SE

e > M

"UNDERFLOW"

SE

e < m

Preservamos o máximo de exatidão normalizando todos os resultados. Ex.:

± (.d d ...d ) × β e 1 2 t β

t = 3

m= −4

β = 10

M= 4

REPRESENTAÇÃO

onde (. d1d 2 ... d t )

é a mantissa , 0 ≤ dj ≤ β - 1, j = 1, ... t

e é um expoente no intervalo [m, M]

Observações: - m, M dependem da máquina utilizada

1

x

ARREDONDAMENTO

TRUNCAMENTO

1,25 2.71828 -238.15 0.000007 718235.82

0.125 x 10 0.272 x 10 -0.238 x 103 -

0.125 x 10 0.271 x 10 -0.238 x 103 -

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

Ex.:

x = 2112 .9 ⇒ ER x =

1.2. ERROS ABSOLUTOS E RELATIVOS

EAx x

<

01 . ≅ 4,7 x 10 −5 2112.9

EAx < 01 .

ERRO ABSOLUTO: É a diferença entre o valor exato de um número x e seu valor aproximado x :

y = 5. 3 ⇒ ERy =

EA X = x − x

Ex.: π ∈ ( 314 . , 315 . ) , π um valor tomado dentro deste intervalo,

EAy y

<

0.1 ≅ 0.02 5.3

EAy < 0.1

EAπ = π − π < 0.01 (limitante superior p/ o módulo do erro) Ex.: x = 2112 .9

∴ o erro relativo fornece uma indicação do grau de precisão da representação.

⇒ x ∈ ( 2112 .8, 2113)

EAx < 01 . y =5.3 EAy < 0.1

⇒ y

1.3. ERROS DE ARREDONDAMENTO E TRUNCAMENTO EM UM SISTEMA DE ARITMÉTICA DE PONTO FLUTUANTE

∈ (5.2 , 5.4 )

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 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:

ERRO RELATIVO: É o quociente do erro absoluto pelo valor aproximado:

ER x =

EAx x

=

x−x x 2

x = f x ×10e + g x × 10e − t onde 0.1 ≤ f x < 1 e 0 ≤ g x < 1.

1  e  f x ×10 , se g x < 2 x=  f ×10e +10e − t , se g ≥ 1 x x  2

Exemplo: t = 4, x = 234.57 x = 0.2345 × 103 + 0.7 × 10 −1 ⇒ f x = 0.2345 e g x = 0.7

Se g x <

1 : 2

EAx = x − x = g x ×10e − t <

TRUNCAMENTO:

1 x10e − t 2

O termo g x × 10e − t é despreza do

ERx =

∴ x = f x × 10e

EAx

=

g x ×10e − t f x ×10e

x

<

1 2 ×10e − t 1 = ×10 − t +1 e 0.1×10 2

Se g x ≥1 2 :

EAx = x − x = g x × 10e − t < 10e − t (pois | g x |< 1)

(

) (

EAx = x − x = f x ×10e + g x x10e − t − f x ×10e +10e − t

ERx =

EAx x

=

g x ×10e − t f x ×10e

<

10e − t = 10 − t +1 0.1×10e

)

= g x ×10e − t −10e − t

(pois 0.1 é o valor mínimo que f x pode ter)

1 = (g x −1) × x10e − t ≤ ×10e − t 2

ARREDONDAMENTO:

Arredondamento simétrico:

ERx =

3

EAx x

≤

1 2 ×10e − t f x ×10e +10e − t

<

1 2 ×10e − t 1 2 ×10e − t 1 < = ×10− t +1 f x ×10e 0.1×10e 2

RESUMO

Para o caso de arredondamento:

TRUNCAMENTO EAx < 10 e − t ERx

< 10 − t +1

ARREDONDAMENTO 1 EAx < × 10e − t 2 1 ERx < × 10 − t +1 2

( x + y) − ( x + y)

ERx + y =

x+ y

0.938272 − 0.9383 1 = 2.9841x10 − 5 < 10 − t +1 0.9383 2

1 = 10 − 4 + 1 = 5 x10 − 4 2

Exemplo:

Ex.:

x = 0.937 × 104

x1 = 01246 . x 2 = 0.3290

x+ y =? y = 0.1272 ×10

=

x x

10 10 −1

x1 + x2 = .1246 ×101 + .3290 ×10−1 = (.1246 + .003290 ) x101

2

=.1278×101 ∴ x1 + x2 = .1278 ×101 (truncamento)

Solução Exemplo:

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.

x = 0.937 x10 4

x.y = ? Solução:

x. y = (0.937 x104 ) × (0.1272 x10 2 )

y = 0. 001272 x10 4 {

=(0.937 x0.1272) × 106

4−2

= 0.1191864 × 106

4 ∴ x + y = (0.937 + 0.001272) x10 4 = 01 .938272 x10 44244 3 resultado exato

∴ truncamento x. y = 0.1191 × 106

Sistema com t = 4

arredondamento x. y = 0.1192 × 106

truncamento = x + y = 0.9382 x10 arredondamento = x + y = 0.9383x104 4

4

(b) Subtração (x-y)

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.

EAx − y = EAx − EAy

 x   y  ERx − y = ERx   − ER y .  x − y x − y

Exemplo: x = 0.0000 x10 4 y = 01234 . x10 2 ⇒ x + y = ( 0.0000 + 0.001234) x10 4 = 0.001234 x10 4 ⇒ x + y = 0.0012 x10 4

(c) Multiplicação: (x.y)

∴ Exemplo de zero de ponto flutuante: 0.0000 x10 −50

x. y = ( x + EAx ).( y + EAy ) = xy + xEAy + yEAx +

1.4. PROPAGAÇÃO DE ERRO

∴ ERx .y = x . EAy + y . EAx

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.

ER x . y =

x . EAy + y . EAx x. y

=

EAx x

+

EAy y

∴ ERx . y = ERx + ERy (a) Adição (x+y)

x + y = ( x + EAx ) + ( y + EAy ) = ( x + y ) + ( EAx + EAy )

∴EAx + y = EAx + EAy ER x + y =

EAx + y x+y

=

(d) Divisão (x/y)

EAx  x  EAy  y  . +  = x x + y y x + y

EAy  x + EAx  x x + EAx x + EAx 1 = = = . 1 +  EAy   y y + EAy y y y   1 +  y  

 x   y  ⇒ ER x + y = ER x   + ER y .  x + y x + y

5

−1

t=4 β = 10

aproximaç ão do binômio (1 + r ) n ≅ 1 + nr , p / r << 1

∴

EAy  x x + EAx  ≅ .1 −  y y y   =

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

x xEAy EAx − + − y y2 y

Solução de (b)

x x EAx x . EAy ≅ + − y y y y2 EAx x . EAy ∴ EAx / y ≅ − y y2 y . EAx − x . EAy ∴ EAx / y = y2 ∴

ER x / y

w={ x− y−z s1 1 4 24 3 s2

s1 = x − y = (0.7237 − 0.00000002) × 10 4 = 0.72369998 × 10 4 ∴ s1 = 0.7237 × 10 4

y . EAx − xEAy y EAx EAy = . = − y2 x x y

∴ ER x / y =

EAx EAy − x y

x = 0.7237 × 10 4   y = 0.2145 × 10 − 3 nú meros exatamente representados z = 0.2585 × 101 

∴ ERx/ y = ERx − ERy

Exemplo: Sistema de aritmética de ponto flutuante

1 1 × 10 − 4 +1 = × 10 − 3 2 2 s2 = s1 − z = (0.7237 − 0.0002585) × 10 4 = 0.7234415 × 10 4

∴ ERs1 <

∴ s2 = 0.7234 × 10 4 6

 s  ERs 2 = ERs1 . 1  −  s1 − z  ∴ ERs2 <

que o limite do erro relativo de u = 3 x - y é menor que o limite do erro relativo de w= ( x + x + x ) − y .

 z    + RA  s1 − z 

Respostas: ER u < 2 x10− t +1

ER w <

1 0.7237 1 x10 − 3 × + × 10− 4 +1 2 0.7234 2

7 x10− t +1 3

Exemplo:

ERs2 < 1.0002 × 10 −3

Solução do item (d) do exemplo anterior:

∴ x − y − z = 0.7234 × 104

w = ({ x. y ) / z

ERx − y − z < 1.0002 × 10− 3

1s124 3 s2

s1 = x. y = (0.7237 × 0.2145 x10 4 − 3 = 0.152336 × 101

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

∴ s1 = 0.1552 × 101

1 1 1 × 10 − t +1 = 10 − 4 +1 = × 10 − 3 2 2 2 1 ∴ ERs1 < 10 − 3 2 s2 = s1 z = (0.1552 0.2585) × 101−1

∴ 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

= 0.6003868 ∴ s2 = 0.6004

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 7

∴( x. y ) / z = 0.6005 −3 ERx. ( y / z ) < 10 1 1 ∴ ERs2 < 10−3 + 10−3 = 10−3 2 2

Ex.: implementação com dígito de proteção ou dígito de guarda: (imediatamente à direita da mantissa do número de menor expoente).

∴( x. y ) / z = 0.6004 −3 ER( x. y ) / z < 10

x1 = .1064 ×103

Solução do item (e): w = x. ( y / z ) 123 1 12 4 s4 3

x2 = − .3173×10 2 x1 + x2 = (.1064 − .03173)×103 = .07467 ×103

s2

s1 = y z = (0.2145 0.2585) × 10−3−1 = 0.8297872 × 10 4

com dígito de guarda:

x1 + x 2 =.7467 x 10 2

s1 = 0.8298 × 10− 4

sem digito de guarda:

x1 + x 2 =.7460 x 10 2

Exemplo:

x1 = .2631×102 x2 = .1976×102 x1 + x2 =.0655× x102 ∴ x1 + x2 =.6550×101 ↑

s2 = x.s1 = (0.7237 × 0.8298) x104 − 4 = 0.6005262

este zero não é significativo!

∴ s2 = 0.6005 ERs2 =

Exemplo: x1 =.999 × 10 x2 = .999 × 1099 1 424 3

1 1 ERs1 + RA ∴ ERs2 < 10−3 + 10−3 2 2

Supor que é o maior valor possível na representação da máquina:

⇒ ERs2 < 10 −3

8

Optando-se por (a): 0.9375 × 2 =1.875 0.875 × x 2 =1.75   0.75 × 2 =1.50 0.1110  0.5 × 2 =1.0   0× 2 = 0

∴x1 + x 2 = 1 .9998 ×10 99 ⇒ " Overflow " de ponto flutuante (interrupção). 1.5. REPRESENTAÇÕES EM DIFERENTES SISTEMAS DE NUMERAÇÃO a) decimal flutuante

0.1111 →

Notação utilizada:

x = f . 10 e 1 ≤ f < 1 10

 f : mantissa e: característica 

1 1 1 1 + + + = 0.9375 2 4 8 16

Optando-se por (b): 0.467875 x 2 = 0.9375 . 1o dígito = 0

ERx < 10− t +1 truncamento 1 ERx < 10 − t +1 arredondamento 2

ER x < 2 − t arredondamento ER x < 2 − t +1 truncamento

b) máquina binária c) sistema hexadecimal

x = f . 2e 1 ≤ f < 1 2 1 Porquê f ≥ para base 2? 2

x = f . 16 e 1 ≤ f < 1 16

Ex.: Considere-se o decimal 30: 30 = 0.9375 × 25 (a ) ou 30 =0.46875× 26

ERx < 8 x16− t arredondamento ERx < 16 x16− t truncamento

(b) 9

Exercício: obter as expressões dos erros relativos para os sistemas binário e hexadecimal.

Apêndice ao capítulo: breves considerações sobre sistemas de numeração

A tabela a seguir sumariza algumas das características de algumas bases de sistemas de numeração:

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 x16 − th = 16 x16 −6 = 16 −5

2526 10 = 2 x 10 3 + 5 x 10 2 + 2

x

10 1 + 6

x

10 0

∴ 10 − p+1 = 16 −5

(− p + 1)ln 10 = −5 ln16

Mudança de uma base para outra

− 5 ln 16 − p +1 = ln 10 5 ln 16 p = 1+ ⇒ p≅7 ln 10

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.

Exercício: computador binário com 27 bits na mantissa; p = ? (dígitos decimais significativos).

10

Exemplo: Converter 29 10 para os sistema binários, octal e hexadecimal.

29

2

(1)

14

2

(0)

7

2

(1)

3

2

(1)

1

2

(1)

0

Ex.: mostrar como são convertidos as representações 111012 , 358 e 10 16 para base 10

111012 = ( 1x 2 4 + 1x 2 3 + 1x 2 2 + 0 x 2 1 + 1x 2 0 ) 10 = 29 10 358 = ( 3x81 + 5x8 0 ) = 29 10 1016 = ( 1x161 + 13x16 0 ) = 29 10

29 10 = 111012

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

8

(5)

3

8

(3)

0

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. 11

Ex.: obter a representação, na base 2, do número 0.687510

0.6875 0.375 0.75 0.50 0.00

x x x x x

2 2 2 2 2

= = = = =

CAPÍTULO 2 RESOLUÇÃO NUMÉRICA DE EQUAÇÕES

1. 375 0. 75 1. 50 1. 00 0. 00

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: 01011 . = ( 1x 2 −1 + 0 x 2 −2 + 1x 2 −3 + 1x 2 −4 ) 10 = 0.687510 2

Classificação:

Ex.: obter a representação, na base 2, do número 0.110 0.1 x 2 = 0.2 0.2 x 2 = 0.4 0.4 x 2 = 0.8 0.8 x 2 = 1.6 0.6 x 2 = 1.2 0.2 x 2 = 0.4 0.4 x 2 = 0.8 0.8 x 2 = 1.6 0.6 x 2 = 1.2 . 01 . 10 = 0.00011001100...

Etapas no cálculo de uma aproximação para a raiz:

(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

(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

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 0x:

Notar que o número 01 . 10 não tem representação exata na base 2. 12

⇒ g(x0) - h(x0) = F(x0) = 0 ⇒ ρ = x0

Ex.: seja y = F(x) = ex - senx - 2 1

Exemplo: isolar todas as raízes da equação F ( x) = x 2 − sen x − 1

0.5

-2

-1

1

2

3

x 2 − (sen x + 1) = { 1424 3 g ( x) 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

13

-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:

14

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:

15

(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]

16

F ' ( x) < 0, ∀x ∈ [ a, b] .

Algoritmo

Aplicação do método da bisseção: 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=(a+b)/2 Repita 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 Xma=xm Até que |xm-xma| ≤ P Escreva ‘aproximação ‘, (xm+xma)/2 Fim

  ( 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

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

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

ε i = x i − x i −1

ε = x − x = 0.25 1

i

0

ε = x − x = 013 . 2

2

1

ε = x − x = 0.06 3

3

2.1.4 MÉTODO DA ITERAÇÃO LINEAR (MIL)

2

ε = x − x = 0.03 ε = x − x = 0.01

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.

Assume-se para aproximação da raiz o último valor obtido para xi, ou seja, ρ = 1.44 .

Suponha que xo corresponda a uma primeira aproximação de ρ; geramos uma seqüência do seguinte modo:

4

4

3

ε = x − x = 0.02 5

6

5

6

4

5

17

xo

(c ) x 2 − sen x = 0

x1 = ϕ (xo) x2= ϕ (x1)

x/ 2 − sen x − x/ 2 = − x 2

xn+1= ϕ (xn)

sen x = x 2 x = arc sen x 2

Se {xn} é uma seq. convergente, então ∃ ρ tal que

∴ϕ 3 ( x ) = arc sen x 2

lim x n = ρ

n →∞

Como ϕ é contínua:

ρ = lim x n = lim ϕ ( x n −1 ) = ϕ (lim x n−1 ) = ϕ ( ρ )

Exemplo: Determinar

Portanto, quando n → ∞, x n +1 = ϕ ( x n ) → ρ = ϕ ( ρ ). Ou seja, ρ = ρ .

F ( x ) = x 2 − sen x − 1 = 0

n →∞

n →∞

n→∞

uma

aproximação para a raiz da equação no intervalo [1.0, 1.5], com grau de exatidão

∈≤ 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.

Solução:

Função de iteração: F ( x ) = x 2 − sen x − 1 = 0

Solução: (a) x2 - sen x = 0

⇒ x 2 = sen x + 1 ⇒ x = sen x + 1

x + x2 - 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

xo = 1.3

x 2 − sen x + sen x = sen x

x1 = ϕ ( xo ) = sen (1.3) + 1 = 1.4013

x = ± senx

ε1 = x1 − xo = 1.4013 − 1.3 = 0.1013 > 0.001

∴ϕ 2 (x ) = sen x 18

x2 = ϕ ( x1 ) = sen (1.4013) + 1 = 1.4091

ε 2 = x2 − x1 = 1.4091 − 14013 = 0.0078 > 0.001 x3 = ϕ ( x2 ) = sen (1.4091) + 1 = 1.4096

∴ xn +1

ε 3 = x3 − x2 = 1.4096 − 14091 = 0.0005 < 0.001

F(x ) = x 2 − a = 0

∴ ρ = 14096 .

(b) tentativa com uma função de iteração mais trabalhada: a x2 − a = 0 ⇒ x2 = a ⇒ x = x a a 1 x + x = + x ∴x =  x +  x 2 x 1 a xn +1 = ϕ ( xn ) ∴ xn +1 =  xn +  2 xn 

com grau de exatidão ≤ 10 −3 2 Obs.: F ρ = (1.4096 ) − sen (1.4096 ) − 1 = −6.38 x10 −5 .

()

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.4 xn +1 = ϕ ( xn )

a = 5   x0 = 1.5

x2 = ϕ ( x1 ) =

1 a xn +1 =  xn +  2 xn 

TOLERÂNCIA : ε ≤ 10-3 a cada passo : ε n = xn − xn −1

x0 = 1.5  1 5  1 5   = 2.417  x1 = ϕ ( x0 ) =  x0 +  = 1.5 + 2 x0  2  1.5    ε1 = 2.417 − 1.5 = 0.917

∴x0 = 1.5 x1 =ϕ ( x0 ) = ϕ (1.5) =

5 = 3.333 1.5 5 = ϕ ( xn ) = não converge para a raiz da equação xn

x3 = ϕ ( x2 ) =

5 = 3.333 1.5

5 = 1.5 3.333 19

 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

 5  1  = 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 )

Convergência no M.I.L.

5 x 1 2

pela direita

y = g (x ) é bissetriz!

(g ' (x ) = 1)

∴ ϕ '( x ) < 1 numa vizinhança de ρ.

Para o caso da equação x = 5 , com x o = 1.5, observamos que:

ϕ1 ( x ) =

xn → ρ

Observe-se agora a situação ilustrada na figura a seguir:

não converge 5 x

ϕ 2 ( x ) =  x +  converge 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:

20

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 − ρ

21

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 xo 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 ) = −

22

a 5 = = 0.555 < 1 2 x0 9

ϕ 3' (x ) =

Aplicação:

1 1 − x4

⋅ 2x

x0 = 3

No ponto x 0 = 0.9 :

5 = 1.667 3 5 x2 = ϕ ( x1 ) = = 2.999 1.667 5 = 1.667 x3 = ϕ (x2 ) = 2.999

ϕ1' ( x0 ) = ϕ1' (0.9 ) = 2 ⋅ (0.9 ) + 1 − cos(0.9) = 2.178 > 1

x1 = ϕ ( x0 ) =

ϕ 2' ( x0 ) = ϕ 2' (0.9 ) = ϕ 2' ( x0 ) = ϕ 2' (0.9 ) =

não converge!

cos(0.9) 0.622 = = 0.351 < 1 2 sen (0.9 ) 2.0885 2.0.9 1 − (0.9)

4

= 3.069 > 1

∴ Somente ϕ 2 (x ) deverá convergir.

Exemplo: estudar a convergência das funções de iterações obtidas anteriormente para a equação

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.

Sol.:

ϕ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 23

ε 〈 10 −3

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 ,

x0 = 0.9 x1 = ϕ ( x0 ) = sen (0.9 ) = 0.885

ε1 = 0.015

ϕ ( x ) = sen x + 1

x2 = ϕ (x1 ) = sen (0.885) = 0.879 ε 2 = 0.006 x3 = ϕ ( x2 ) = sen (0.879) = 0.878 ε 3 = 0.001

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 *)

x4 = ϕ ( x3 ) = sen (0.878) = 0.877 ε 4 = 0.001 x5 = ϕ ( x4 ) = sen (0.877 ) = 0.877 ε 5 〈 10-3

ρ = 0.877 é uma aproximação para ρ Obs.:

()

F ρ = F (0.877 ) = (0.877 ) − sen (0.877 ) = 3.051x10 −4 2

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)

Algoritmo:

24

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

 (1.3) 2 − sen(1.3) − 1   − 0.2736   = 1.3 −   = 1.4173  2.3325   2(1.3) − cos(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 = 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

25

−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 26

ϕ ′( 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 ∴ se x 0 estiver suficientemente próximo da raiz, a aplicação do

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 .

método deverá ser convergente. 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 . 27

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 " ( x0 ) = F " (0.9) = 2 + sen(0.9) = 2.783 F ( x0 ).F " ( x0 ) > 0

Resolução: F ( xn ) xn + 1 = xn − F ′( xn )

 x 2 − sen xn xn +1 = xn −  n  2 xn − cos xn

2

F ( x) = x − sen x F ′( x) = 2 x − cos x



x0 = 0.9

2

⇒ xn + 1

   

( x − sen xn ) = xn − n 2 xn − cos xn

[

]

2 0.0267 (0.9) − sen(0.9) x1 = 0.9 − = 0.9 − = 0.8773 2.(0.9) − cos( 0.9) 1.1784

ε1 = 0.8773 − 0.9 = 0.0227

Condições para convergência:

x2 = 0.8773 −

(a) F ′( x) = 2 x − cos x F " ( x) = 2 + sen x

[(0.8773)2 − sen(0.8773] = 0.8773 − 6.395 x10−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. 28

(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

x0 = 0.5 x1 = 0.5 −

(2 x − cos x) ∴ϕ ( x ) = x − 2 + sen x

(2 xn − cos xn ) 2 + sen xn

[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 29

2 + sen(0.4502) = 0.4502

2.4355

2.4355

∴ ε 3 = x3 − x2 < 10 −4 ∴

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 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 *)

ρ = 0.4502

Exercício Dada a função: F(x) = x ln x - 1 = 0 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 (ρ = 4.2748) (a ) − tgx = 0 2 (b)2 cos x = e x / 2 (ρ = 0.754)

(ρ = 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. 30

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

n.(a1 + an ) 2 com a1 = n, an = 1, número de termos = n. P. A. : S 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

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.

⇒ P' (2) = 4.2 3 − 15.2 2 + 12.2 + 4 = 32 − 60 + 24 + 4 = 0

31

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

an x n + an −1 x n −1 + L + a1 x + a0 = n

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

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:

r = c.b1 + a0 Ou, equivalentemente, bn = an

P(x ) = (x − c ) Q (x ) + {r {

resto da divisão

bn − k = c.bn − k +1 + an − k

Q (x ) = bn x n −1 + bn −1.x n − 2 +L + b2 x +b1

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

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 Q (x ) = bn x

+ bn −1 x

n−2

1 ≤ k ≤ n − 1 (algoritmo de Briot - Ruffini)

r = c.b1 + a0

onde Q( x ) é da forma:

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 +

2.2.3 MÉTODO DE BRIOT-RUFFINI

polinômio quociente

n −1

Solução: P( x ) = ( x − 2).Q( x ) + r

+ L + b2 x + b1

Q( x ) = b3 x 2 + b2 x + b1

32

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

Observe-se que: P(− 3) = (− 3) − 7.(− 3) + 16(− 3) − 10 = − 148 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:

x=c

ai 's44444448 644444447

1

2

−7

16

-10

2

− 10

12

1 −5 6 144 42444 3

⇒ 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

−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 33

∴ 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 34

∴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:

( ) = ((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

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 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: 35

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 36

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 + − 1 2 3

− + + 123 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 37

P( x ) = x 4 − 5 x 3 − 7 x 2 + 29 x + 30 . Encontrar um limitante superior para os seus zeros.

1 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=Ks. (b) se n é ímpar, determina-se o limitante superior Ks de y=-P(-x) e toma-se Li=-Ks. Graficamente:

-7

-7 +29 14 49 7 78

∴ LS = 7

30

-7

-5 7 2

Caso (a):

−7 < 0

−1< 0

38

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 = - Ks onde Ks limit sup. para P( -x)

Determinação de Ks: P(− x ) = x 4 + 5 x 3 − 7 x 2 − 29 x + 30 39

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 ⇒

-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

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,

− 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 ⇒ 40

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 41

(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 42

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

43

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)

44

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)

45

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

(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

0. 4 1 1. 4

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) )

46

∴ 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 47

= 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) = ? 48

= 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: Q(x ) = bn x n −1 + bn −1 x n − 2 + L + b2 x + b1

2

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: 49

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. a11x1 + a12 x2 + ... + a1n xn = b1  S n : a21x1 + a22 x2 + ... + a2 n xn = b2 a x + a x + ... + a x = b nn n n  n1 1 n 2 2

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.

50

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 :

51

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. 52

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

(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 )

3.2.1. MÉTODO DE ELIMINAÇÃO DE GAUSS

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. 53

(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 54

(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 (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 x2 + 3x3 + 4 x4 = 10

⇒ 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 ) : 55

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:

56

( 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) =

57

(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

58

(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) : 59

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:

60

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 61

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:

62

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

63

( 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

64

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:

65

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

66

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: 67

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 )

68

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 69

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  α2 = = 1  ⇒ o critério das linhas não é satisfeito. 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. 70

(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:

1 − 1  x1   2  1      S3 =  2 4 2  x2  =  6 − 2 − 1 4  x3  − 3

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

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

71

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. RUGGIERO, M.A.G. & LOPES, V.L.R. Cálculo Numérico Aspectos Teóricos e Computacionais. São Paulo: MAKRON Books, 1996. 2. DORN, W.S. & MAcCRACKEN, D.D. Cálculo Numérico com Estudo de Casos em Fortran IV. Campus, 1978 3. BARROSO, L.C. & outros. Cálculo Numérico (com aplicações). Editora Harbra Ltda, 1987

72