Capítulo 2: Resolução Numérica de Equações
2.1. Raiz de uma equação
Em muitos problemas de engenharia há necessidade de determinar um
número ξ para a qual a função f(x) seja zero, ou seja, f(ξ)=0. A ξ
chamamos raiz da equação f(x)=0 ou zero da função f(x).
Equações algébricas (polinómios) do primeiro e segundo grau e certas
classes de equações algébricas do terceiro e quatro grau, bem como
algumas equações transcendentes podem ser resolvidas analiticamente,
i.e., as suas raízes podem ser calculadas exactamente através de métodos
analíticos.
Exemplos:
x2-2x+1=0 ⇔ x=1
sin(x)=0 ⇔ x=kπ, k ∈ Z
Mas para polinómios de grau superior a quatro e para a grande maioria
das equações transcendentes o problema só pode ser resolvido por
métodos numéricos. Embora estes métodos não forneçam raízes exactas,
estas podem ser calculadas com determinada precisão, desde que certas
condições sobre f sejam satisfeitas.
Duas etapas devem ser seguidas para calcular a raiz pretendida:
i) 1ª Etapa: Isolar a raiz, i.é., encontrar um intervalo [a, b], com menor
amplitude possível, que contenha uma e somente uma raiz da equação.
ii) 2ª Etapa: Melhorar o valor da raiz aproximada, i.é., refinar a raiz até
à precisão pretendida.
1
Antes de continuarmos com o nosso estudo vamos definir multiplicidade
de uma raiz.
Definição: Uma raiz, ξ, de uma equação tem multiplicidade m se
f(ξ) = f ’(ξ) = f ’’(ξ) =...= f (m-1)(ξ) = 0 e f (m)(ξ) ≠ 0,
onde f j(ξ) é a derivada de ordem j de f(x) calculada em x = ξ e j=1,...,m.
2.2. Isolamento das raízes
Apresentamos de seguida alguns teoremas que nos permitem contar e
localizar as raízes de uma equação:
Teorema 1: Uma equação algébrica de grau n tem exactamente n raízes,
reais ou complexas, desde que cada raiz seja contada de acordo com a sua
multiplicidade.
Teorema 2: Se f é definida e contínua em [a, b] e se f é tal que f(a)f(b)<0
então f(x)=0 tem no mínimo uma raiz em [a, b], por outras palavras
haverá, no mínimo, um número ξ∈(a, b) tal que f(ξ)=0.
Além disso, a raiz ξ será definida e única se f ’(x) existir e preservar o
sinal no intervalo (a, b), i.é., se f ’(x)>0 ou f ’(x)<0 para a<x<b.
Exemplo:
1
0.5
2.25 2.5 2.75
3
3.25 3.5
0.5
-1
2
Com a=0 e b=3.5, temos que f(a)f(b)<0 mas f ’(x) muda de sinal em ]a,b[,
a função tem três raízes no intervalo [a,b].
Teorema 3- Teorema de Bolzano: Seja P(x)=0 uma equação algébrica
com coeficientes reais e x ∈ (a, b).
i-
Se P(a)P(b)<0 então existe um número ímpar de raízes reais
(contando as suas multiplicidades) no intervalo (a, b).
ii-
Se P(a)P(b)>0 então existe um número par de raízes reais (contando
as suas multiplicidades) ou não existem raízes reais no intervalo (a, b).
O modo mais simples para isolar uma raiz é fazer um esboço do gráfico
da função e verificar em que ponto ou pontos esta “toca” o eixo dos xx.
2.3. Grau de exactidão de uma raiz
Depois de termos isolado a raiz no intervalo [a, b] temos que recorrer ao
uso de métodos numéricos para determinar uma aproximação para essa
raiz. Como vamos ver, os métodos numéricos fornecem-nos uma sucessão
{xn} de aproximações, cujo limite é a raiz exacta ξ, i é,
lim xn = ξ
n→∞
O teorema que se segue dá-nos “uma medida” para verificarmos se
aproximação está longe da solução exacta.
Teorema: Seja ξ uma raiz exacta e xn uma raiz aproximada da equação
f(x)=0, com ξ e xn∈ [a, b] e |f ’(x)|≥m>0 para a≤x≤b onde m= Min f ' ( x) .
a ≤ x ≤b
Então,
x −ξ ≤
n
f ( xn)
m
.
Exemplo: Seja f(x)=x2-8, limitar o erro com xn=2,827 no intervalo [2, 3].
3
Resolução: Tem-se que f ’(x)=2x. Pretende-se m= min | 2 x | =4. Então
2≤ x≤3
|2.827-ξ|≤
2.827 2 − 8
4
=
0.008
=0.002, ou seja, |2.827-ξ|≤0.002.
4
O cálculo de m é por vezes muito difícil. Por essa razão utilizamos um
dos três critérios abaixo para avaliar a precisão da raiz aproximada.
i)
| f ( xn ) | ≤ ε
ii)
| xn − xn −1 | ≤ ε
iii)
| xn − xn −1 |
≤ε
| xn |
onde ε é a tolerância prefixada ou erro admitido.
Vamos agora estudar métodos que nos permitem refinar a raiz.
2.4. Métodos Iterativos para a resolução de equações
Determinado o intervalo onde se encontra a raiz, devemos em seguida
refinar essa raiz, ou seja, determinar uma aproximação para essa raiz tão
exacta quanto o possível.
2.4.1. Método da Bissecção
Seja f uma função definida e contínua em [a, b], onde [a, b] é um
intervalo onde f(x)=0 tem uma raiz ξ, i.é., f(ξ)=0.
Interpretação Geométrica
4
Analiticamente:
1ª Iteração:
I0=[a, b]
x0=
a+b
(ponto médio de [a, b] )
2
i ) f(a)f(x0)<0 ⇒ ξ∈(a, x0)
ii) f(a)f(x0)>0 ⇒ ξ∈(x0, b)
iii) f(a)f(x0)=0⇒ ξ = x0
Suponhamos que ξ∈(a, x0).
2ª Iteração:
I1=(a, x0)
x1=
a + x0
(ponto médio de (a, x0))
2
i ) f(a)f(x1)<0 ⇒ ξ∈(a, x1)
ii) f(a)f(x1)>0 ⇒ ξ∈(x1, x0)
iii) f(a)f(x1)=0⇒ ξ = x1
O processo é repetido até que se obtenha uma aproximação para a raiz
exacta ξ, com a tolerância ε desejada.
Este método gera uma sucessão de intervalos I0 I1, I2,..., In,...com
amplitude decrescente, tendo-se que:
5
I0 ⊃ I1 ⊃ I2 ⊃....⊃ In, ⊃...
e além disso, ξ∈ In, e xn ∈ In, .
Seja W( In, ) a amplitude do intervalo In, , tem-se
W( In )=
1
1 1
1
W( In-1 )=
W( In-2 )=...= n W( I0 ).
2
2 2
2
Como W( I0 )=b-a tem-se que W( In )=
b−a
. Donde
2n
b−a
n = 0.
n→∞ 2
limW ( I n ) = lim
n →∞
Mas ξ e xn ∈ In, logo tem de ser lim x n =ξ. Provamos assim o seguinte
n →∞
teorema:
Teorema: Seja f uma função definida e contínua em [a, b] que satisfaz
f(a)f(b)<0, seja xn o ponto médio de In gerado pelo método da bissecção,
então
∃ ξ ∈ [a, b]: f(ξ)=0 e lim x n =ξ
n →∞
Prova-se ainda que | x n − x n−1 | =
b−a
. Mesmo que o intervalo
+
n
1
2
escolhido não seja ( xn , xn−1 ) ou ( xn−1 , xn ) a igualdade anterior verifica-se
sempre. Se pretendermos que | x n − x n−1 | ≤ ε então temos que ter
b−a
⎛b − a⎞
b−a
n+1
n+1
n+1
≤
ε
⇔
2
ε
≥
b-a
⇔
2
≥
⇔
ln(2
)
≥
ln
⎜
⎟⇔
+
1
n
ε
ε
⎝
⎠
2
ln((b − a) / ε )
⎛b−a⎞
−1
⎟ ⇔n≥
ln(2)
⎝ ε ⎠
⇔ (n+1)ln(2) ≥ ln ⎜
ou seja, para um dado intervalo [a, b] são necessárias, no mínimo, n
iterações para determinar a raiz ξ com uma tolerância ε.
6
Exemplo: Calcule a raiz positiva da equação f(x)=x2-3 com ε ≤ 0.03.
Solução exacta: x2-3=0 ⇔ x =± 3 ⇔ x =±1.7321…
Solução aproximada:
Tem-se que I0=(1, 2) com f(1)=-2 e f(2)=1, i.é., f(1)f(2)<0 ou seja a
solução pertence ao intervalo (1, 2).
n
0
1
2
3
4
5
an
1
1.5
1.5
1.625
1.6875
1.7188
bn
2
2
1.75
1.75
1.75
1.75
xn
1.5
1.75
1.625
1.6875
1.7188
1.7344
f(xn)
-0.75
0.0625
-0.3594
-0.1523
-0.0457
0.0081
erro
0.25
0.125
0.0625
0.0313
0.0156
A solução aproximada é: x5=1.7344.
2.4.2. Método da Secante ou ponto fixo
Como de costume consideremos f(x)=0 tal que f(x) tem uma só raiz - ξ em [a, b] e, além disso, f é contínua e definida em [a, b], e sendo que f ’ e
f ’’ preservam o sinal em [a, b].
O método da secante em vez de dividir o intervalo (a,b) ao meio, o
intervalo é dividido em partes proporcionais á razão f(a)/f(b).
Interpretação geométrica:
i)
Considere a recta que passa pelos pontos (a, f(a)) e (b, f(b)), seja s
essa recta;
ii)
Considere o ponto de intersecção de s com o eixo dos xx, seja x1
esse ponto;
iii) Determine f(x1);
iv) Considere a recta que passa pelos pontos (x1, f(x1)) e (b, f(b)), ou (a,
f(a)) e (x1, f(x1)) seja s’ essa recta;
v)
Determine o ponto de intersecção de s’ com o eixo dos xx;
7
O método anteriormente descrito gera uma sucessão x0, x1, x2, ..., xn,...
que converge para ξ.
Interpretação Geométrica
Analiticamente:
Caso I
f (b) − f ( x0 ) f ( x1 ) − f ( x0 )
x − x0
b − x0
f ( x0 )
=
⇔ 1
=
⇔ x1 = x0 −
( x0 − b)
b − x0
x1 − x0
0 − f ( x0 ) f (b) − f ( x0 )
f ( x0 ) − f (b)
Por indução, xn +1 = xn −
f ( xn )
( x n − b)
f ( xn ) − f (b)
Caso II
f (a) − f ( x0 ) f ( x1 ) − f ( x0 )
x − x0
x0 − a
f ( x0 )
⇔ x1 = x0 −
=
⇔ 1
=
( x0 − a)
a − x0
x1 − x0
0 − f ( x0 ) f ( x0 ) − f (a)
f ( x0 ) − f (a)
Por indução, xn +1 = xn −
f ( xn )
( xn − a)
f ( xn ) − f (a)
8
Caso III
f (a ) − f ( x0 ) f ( x1 ) − f ( x0 )
=
(igual ao caso II)
a − x0
x1 − x0
Caso IV
f (b) − f ( x0 ) f ( x1 ) − f ( x0 )
=
b − x0
x1 − x0
(igual ao caso I)
Conclusão:
O ponto fixo a ou b é aquele no qual o sinal de f coincide com o sinal de
f ’’ e a aproximação sucessiva faz-se do lado do ponto não fixo.
xn+1 = x n −
f ( xn )
( x n − C ) , onde C é o ponto fixo extremo de
f ( x n ) − f (C )
[a,b] onde f (C) f ’’(C) > 0.
Exemplo: Consideremos de novo a função f(x)=x2-3 e ε ≤ 0.03 e
calculemos a sua raiz positiva pelo método da secante.
Vimos que a raiz está no intervalo [1, 2]. Como f(2)f ’’(2)>0, então C=2
e x0=1.
1ª Iteração:
x1 = x0 -
f ( x0 )
−2
( x − 2) ⇔ x1 = 1 (1 − 2)
f ( x0 ) − f (2) 0
− 2 −1
⇔ x1 = 1.6667
O erro cometido é de |x1-x0|=|1.667-1|=0.6667 > 0.03.
2ª Iteração:
x2 = x1 -
f ( x1 )
( x1 − 2) ⇔ x2 = 1.7273
f ( x1 ) − f (2)
O erro cometido é de |x1-x2|= 0.0606> 0.03.
3ª Iteração:
x3 = x2 -
f ( x2 )
( x2 − 2) ⇔ x3 = 1.7317
f ( x2 ) − f (2)
O erro cometido é de |x2-x3|=0.0044<0.03. A solução aproximada é x3 =
1.7317
9
Convergência do método:
Prova-se o seguinte teorema:
Teorema: Seja f∈C2[a, b] (i.é., f, f ’, f ’’ são contínuas em [a, b]) e
estritamente monótona em [a, b], se f(a)f(b) ≤ 0 e se f ’,f ’’ preservar o
sinal em [a, b], então a sucessão produzida pelo método da secante ou
ponto fixo converge monotonamente para o zero de f nesse intervalo.
2.4.3. Método de Newton-Raphson
Seja f∈C2[a, b], i.é., f, f ’ (f ’(x)≠0), f ’’ são contínuas em [a, b], e seja ξ
o único zero da função em [a, b].
Expandindo f(x)=0 em série de Taylor em torno de ξ obtemos:
f(ξ) ≅ f(x0)+(ξ-x0)f ’(x0)
Mas f(ξ)=0, então
f(x0)+(ξ-x0)f ’(x0) ≅ 0 ⇔ ξ-x0 ≅
−
f ( x0 )
f'( x )
0
⇔ ξ ≅ x0
−
f ( x0 )
.
f'( x )
0
A relação anterior é a base da fórmula de recorrência do método de
Newton:
xn+1 = xn −
f ( xn )
, n=0, 1, ...
f ' ( xn)
Interpretação Geométrica:
O ponto xn+1 é a abcissa do ponto de intersecção com o eixo dos xx da
recta tangente à curva de f no ponto (xn ,f(xn)).
10
Escolha de x0 e Convergência:
Teorema: Prova-se que é condição suficiente para que o método de
Newton convirja, que f∈C2[a, b], f ’(x) e f ’’(x) sejam não nulas e
preservem o sinal em [a, b] e que x0 seja tal que f(x0) f ’’(x0)>0.
Exemplo: Consideremos de novo a função f(x)=x2-3 com ε ≤ 0.03. Vimos
que a raiz se encontra no intervalo [1,2]. Tem-se que f ’(x)=2x e f ’’(x)=2.
Como f (2) f ’’(2)>0, tem-se que, x0=2 é uma boa aproximação.
1ª Iteração
x1 = x0 −
f ( x0 )
f ( 2)
1
⇔ x1 = 2 −
⇔ x1 = 2 − ⇔ x1 = 1.75
f ' ( x0 )
f ' ( 2)
4
|1.75-2|=0.25>0.03
2ª Iteração
x2 = x1 −
f (x1 )
0.0625
⇔ x2 = 1.75 −
⇔ x2 = 1.7321
f ' ( x1 )
3 .5
|1.75-1.7321|=0.0179<0.03 . A solução aproximada é: x2 = 1.7321.
2. 5. Comparação e observações sobre os métodos
Comparando os três métodos podemos concluir que o método de Newton
é o mais eficiente pois é o que necessita de menos iterações para “chegar à
solução” com a mesma precisão.
O método da bissecção não exige o conhecimento das derivadas mas é o
que tem uma convergência mais lenta. Deve por isso ser utilizado apenas
para diminuir a amplitude do intervalo que contém a raiz. O método da
secante ou ponto fixo também não requer o conhecimento das derivadas
tendo uma convergência apenas superada pelo método de Newton. O
método de Newton é o que converge mais depressa, precisa de um número
reduzido de iterações para convergir, o único senão deste método reside
no facto de ser necessário o conhecimento da forma analítica de f ’(x).
11
O quadro seguinte mostra o número de iterações que cada método
necessitou para encontrar um zero de g(x)=e0.1x+x2-10 com ε ≤ 10-5 e
f(x)=x2-3 com ε ≤ 0.03
g
f
Bissecção
16
5
Secante
4
3
Newton
3
2
12
Download

zero da função