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