Resolução de equações não lineares Raiz de uma equação Raiz exata Um número xr é raiz exata de uma equação f(x)=0 se f(xr)=0 Raiz aproximada Um número x’ é raiz aproximada de uma equação f(x)=0 se |x’-xr| e |f(x’)| forem ambos próximos de 0 Comparar o módulo da subtração da raiz é basicamente uma operação teórica, pois não se pode obter a raiz exata Calculando as raízes Para calcular as raízes reais de uma equação f(x)=0 é necessário: 1) delimitar, enumerar e separar as raízes 2) utilizar um método numérico para calculo de cada raiz Equações algébricas polinomiais A) toda equação do tipo anxn+an-1xn-1 +...a1x1+a0 é algébrica e polinomial n é um número natural denominado grau da equação Os coeficientes ai, i=0...n são números reais Equações algébricas polinomiais Toda equação polinomial de grau n tem exatamente n raízes, reais ou complexas, desde que cada raiz seja contada de acordo com seu grau de multiplicidade Multiplicidade de raizes Uma raiz tem grau de multiplicidade m se: anula a função que origina a equação Anula as derivadas até a ordem m-1 Não anula a derivada de ordem m Exemplo A equação f(x)=x3-5x2+8x-4 tem raízes x1=1 x2=2 e x3=2 f(2)=0 f’(2) = 3x2-10x+8 -> f’(2)=0 f’’(2)=6x-10 ->f’’(2)=2 Equações algébricas polinomiais As raízes complexas aparecem sempre em pares conjugados (a+bi e a-bi) Toda equação polinomial de grau impar tem pelo menos uma raiz real Delimitação de raízes reais Limite superior positivo-teorema de Lagrange Seja f(x)=0 uma equação polinomial de grau n, na qual an>0 e a0 ≠ 0 Para limite superior de suas raízes positivas, caso existam pode ser tomado o número L 1 nk M an K= grau do 1º termo negativo M= módulo do menor coeficiente negativo Exemplo Calcule o limite superior para as raízes positivas da equação f(x) = x5+x4-8x3-16x2 +7x+14 =0 Exemplo Calcule o limite superior para as raízes positivas da equação f(x) = x5+x4-8x3-16x2 +7x+14 =0 n=5,k=3,a5=1 e M=16 L 1 53 16 2 1 16 1 4 5 1 Delimitação das raízes reais Limite inferior negativo Obter a equação auxiliar f1(x)=f(-x)=0 usar o teorema de Lagrange em f1(x), obtendo o limite superior de suas raízes positivas L1 O limite inferior das raízes negativas é dado por –L1 Exemplo Calcule o limite inferior para as raízes negativas da equação f(x) = x5+x4-8x3-16x2 +7x+14 =0 Exemplo f(x) = x5+x4-8x3-16x2 +7x+14 =0 f1(x) = -x5+x4+8x3-16x2-7x+14 =0 an<0 logo devemos multiplicar f1 por -1 f1(x) = x5-x4-8x3+16x2+7x-14 =0 n=5,k=4,a5=1 e M=14 L1 1 5 4 14 1 1 14 1 14 15 1 Logo –L1=-15 Enumeração das raízes Regra dos sinais de Descartes – O número de raízes positivas de equações polinomiais é igual ao número de variação de sinais apresentado pelo conjunto de coeficientes ou menor em um número par Exemplo x5+x4-8x3-16x2+7x+14=0 Exemplo x5+x4-8x3-16x2+7x+14=0 x5+x4-8x3-16x2+7x+14=0 Exemplo x5+x4-8x3-16x2+7x+14=0 x5+x4-8x3-16x2+7x+14=0 2 variações -> 2 raízes ou nenhuma raiz Exemplo x5-x4+8x3-16x2+7x-14=0 Quantas raízes? Exemplo x5-x4+8x3-16x2+7x-14=0 Quantas raízes? 5 variações -> 5 raízes ou 3 ou 1 raiz Exemplo 5x5-16x2+7x-14=0 Quantas raízes? Exemplo 5x5-16x2+7x-14=0 Quantas raízes? 3 variações -> 3 raízes ou 1 raiz positiva Enumeração de raízes Para determinar o número de raizes negativas basta trocar x por (-x) na equação e aplicar a regra dos sinais Exemplo x5+x4-8x3-16x2+7x+14=0 f(-x)=-x5+x4+8x3-16x2-7x+14=0 f(-x)=-x5+x4+8x3-16x2-7x+14=0 3 raízes ou 1 raiz negativa Exemplo x5-x4+8x3-16x2+7x-14=0 f(-x)=-x5-x4-8x3-16x2-7x-14=0 Sem variação -> nenhuma raiz negativa Sucessão de Sturm Dada a equação polinomial f(x)=0 a sucessão de Sturm a ela associada é o seguinte conjunto de polinômios: f(x)f1(x)f2(x)... fm(x) f(x) é o polinômio que origina a equação f1(x) é a primeira derivada de f(x) Sucessão de Sturm A partir de f2(x) cada termo é o resto, com o sinal trocado, da divisão dos 2 termos anteriores f(x)/f1(x) = Q1x+R1x -> f2(x)=-R1x f1(x)/f2(x) = Q2x+R2x -> f3(x)=-R2x A sucessão procede até que seja obtido um resto constante Propriedades Se a equação tiver raízes múltiplas então o último termo da sucessão é nulo Para nenhum valor de x, 2 termos consecutivos da sucessão não se anulam Se, para algum x, um termo médio da sucessão se anula, então os termos vizinhos terão valores numéricos de sinais opostos Teorema de Sturm Seja N(alpha) o número de variações de sinal apresentado pela sucessão de sturm. Para x = alpha O número de raízes reais de uma equação polinomial, sem raízes múltiplas, situadas em um intervalo [a,b] é igual a N(a)-N(b) Exemplo Determine o número de raízes reais da equação no intervalo (-15,5) f(x)=x5+x4-8x3-16x2+7x+14 f1(x)=5x4+4x3-24x2-32x+7 f2(x)=3,36x3+8,64x2-6,88x-13,72 f3(x)=-9,06x2+29,72x+29,22 f4(x)=-68,42x-49,69 f5(x)=-2,88 -15 0 5 f(x)=x5+x4-8x3-16x2+7x+14 - + + f1(x)=5x4+4x3-24x2-32x +7 + + + f2(x)=3,36x3+8,64x2-6,88x-13,72 - - + f3(x)=-9,06x2+29,72x+29,22 - + - f4(x)=-68,42x-49,69 + - - f5(x)=-2,88 - - - N(x) Raízes negativas N(15)-N(0) = 4-3 =1 Raízes negativas N(0)-N(5) = 3-1 =2 As outras duas raízes são complexas 4 3 1 Separação de Raízes reais Teorema de Bolzano: seja f(x) uma função continua em um intervalo [a,b] Se f(a).f(b)<0 então a equação f(x)=0 tem um número impar de raízes no intervalo [a,b] Exemplo Exemplo Separação de Raízes reais Se f(a).f(b) >0 então f(x)=0 tem um número par de raízes ou nenhuma raiz no intervalo [a,b] Exemplo Exemplo Exemplo Exemplo Exemplo Separe as raízes positivas da equação f(x)= x5+x4-8x3-16x2+7x+14=0 Sabendo-se que estão situadas no intervalo (0,5) e que o número de raízes positivas é 2 f(0)=14, f(5)=2399, f(2,5)= -56,78 Uma raiz entre 0 e 2,5 e outra entre 2,5 e 5 Equações não polinomiais Duas possibilidades 1) Construir um esboço do gráfico da função com o objetivo de detectar os pontos 2) Transformar a equação f(x)=0 em uma equação equivalente da forma g(x)-h(x)=0 g(x)=h(x) Equações não polinomiais Esboçar os gráficos de g(x) e h(x) em um mesmo sistema de eixos cartesianos As abscissas de cada ponto onde g(x) e h(x) se interceptam é uma raiz de f(x) Exemplo Seja a equação f(x)=x+ x -5=0 x = 5-x (g(x)=h(x)) Pode ser escrita Metodo da Bisseção Seja f(x) uma função continua em um intervalo [a,b] O intervalo contém uma única raiz da equação f(x)=0 sendo assim, f(a).f(b)<0 Este método consiste em dividir de forma sucessiva o intervalo [a,b] ao meio, até que seja obtido (b-a) <= precisão estabelecida Graficamente - + a b Graficamente - a + + b Graficamente - a + b’ + b Graficamente - a - + b’ + b Graficamente - - a a’ + b’ + b Critério de parada O processo para quando o intervalo [a,b] é suficientemente pequeno Assim qualquer ponto no intervalo é tomado como raiz Número máximo de passos – préestabelecido Convergência Sendo f(x) contínua em [a,b] f(a).f(b)<0 O método da bisseção converge se as condições anteriores forem respeitadas Exemplo Utilizando o método da bisseção calcule a maior raiz positiva da equação f(x)= x5+x4-8x3-16x2+7x+14=0 Precisão 0,025, máximo de 10 iterações, intervalo = [2,5;5] f(2,5)=-56,781 e f(5)=2399 k xk 2,5 5 f(xk) -56,781 2399 b-a 2,5 1 2 3 3,75 332,706 1,25 3,125 28,875 0,625 2,813 -32,239 0,312 4 5 6 7 2,969 -7,224 0,156 3,047 9,307 0,078 3,008 0,679 0,039 2,989 -3,26 0,019 Qualquer número no intervalo [2,989;3,008] pode ser tomado como raiz Método da Falsa Posição Seja f(x) uma função contínua em um intervalo [a,b] que contém um e só uma raiz da equação f(x)=0 Este método consiste em dividir o intervalo [a,b] no ponto onde a reta que passa pelos pontos (a,f(a)) e (b,f(b)) intercepta o eixo das abscissas Graficamente Graficamente Critério de parada O processo iterativo é interrompido quando for obtido |f(xk)|, k=1,2,... Menor ou igual à precisão estabelecida e então xk é tomado como raiz Critério de convergência Se f(x) é contínua em [a,b] e f(a).f(b)<0, então o método da falsa posição converge Calculando xk No método da bisseção x é dado pela média aritmética do intervalo x= (a+b)/2 No método da FP o x é dado pela média aritmética ponderada x=(a|f(b)|+b|f(a)|)/(|f(b)|+|f(a)|) x=(af(b)-bf(a))/(f(b)-f(a)) O cálculo de xk Seja a matriz a x1 b f (a) 1 0 1 0 f (b) 1 bf(a) +x1f(b)-af(b)-x1f(a) x1=(af(b)-bf(a))/(f(b)-f(a)) Generalizando xk=(af(b)-bf(a))/(f(b)-f(a)) Desde que a cada passo seja atualizado a ou b O critério utilizado por este método para a divisão do intervalo [a,b] é o da média ponderada Exemplo Utilizando o método da falsa posição com precisão 0.006 e um máximo de 5 iterações encontrar a maior raiz positiva f(x)=x4-14x2+24x-10=0 A) delimitação das raízes reais LSP = 1 n k M a = 4,7 = 5 n LIN – equação auxiliar f(x) = x4 -14x2-24x-10 L1=6 Logo –L1=-6 Enumeração das raízes reais Raízes positivas:+1-14+24-10 3 variações -> 3 ou 1 raiz positiva Raízes negativas:+1-14-24-10 1 variação -> 1 raiz negativa Número de raízes positivas Teorema de Sturm Sucessão de Sturm 0 5 f(x)=x4-14x2+24x-10 - + f1(x)=4x3-28x+24 + + f2(x)=7x2-18x+10 + + f3(x)=7,24x-9,3 - + f4(x)=1,5 + + N(x) 3 0 Número de raízes positivas O número de raízes é dado por: N(0)-N(5)=3-0=3 Separação das raízes positivas Teorema de Bolzano e o método da bisseção - + 0 5 Separação das raízes positivas Teorema de Bolzano e o método da bisseção - + + 0 2,5 5 Separação das raízes positivas Teorema de Bolzano e o método da bisseção - + + + + 0 1,25 2,5 3,75 5 Separação das raízes positivas Teorema de Bolzano e o método da bisseção - 0 - - + 1,25 0,625 1,875 + + + 2,5 3,75 5 Calculando a maior raiz positiva Reduzindo um pouco mais o intervalo f(1,875)<0, f(2,5)>0, f(2,188)<0 Aplicando o método da falsa posição xk=(af(b)-bf(a))/(f(b)-f(a)) k a b f(a) f(b) xk f(xk) 1 2,188 2,5 -1,592 1,563 2,345 -0,467 2 2,345 2,5 -0,467 1,563 2,381 -0,085 3 2,381 2,5 -0,085 1,563 2,387 -0,016 4 2,387 2,5 -0,016 1,563 2,388 -0,005 Para a precisão estabelecida, 2,388 é a maior raiz positiva da equação Método de Newton-Raphson Também conhecido como método das tangentes Seja f(x) uma função contínua em um intervalo [a,b] que contém uma e só uma raiz da equação f(x)=0 Método de Newton-Raphson Dada uma estimativa xk-1, k=1,2,..., para uma raiz de f(x)=0 a estimativa xk é a abscissa do ponto onde a reta tangente f(x) em [xk-1,f(xk-1)] intercepta o eixo das abscissas Método de Newton-Raphson Critério de parada: O processo é interrompido quando for obtido um |xk-xk-1| ou |f(xk)| menor ou igual a uma precisão pré-estabelecida Graficamente x0 x0 x1 Graficamente x0 x1 Graficamente x0 x1 Método de Newton-Raphson Convergência: se f(a)f(b)<0 e f’(x) e f’’(x) forem não nulas e mantiverem o sinal em [a,b], então partindo-se de uma estimativa inicial x0 є[a,b] tal que f(x0)f’’(x)>0 é possível construir, pelo método de Newton-Raphson uma sequência {xk}, k=1,2,..., que converge para a raiz de f(x)=0 Método de Newton-Raphson Seja o cálculo de x1 f ( x0 ) f ( x0 ) tg f ' ( x0 ) x1 x0 x0 x1 f ' ( x0 ) Para x2 f ( x1) f ( x1) tg f ' ( x1) x2 x1 x1 x2 f ' ( x1) Método de Newton-Raphson Generalizando f ( xk 1) xk xk 1 f ' ( xk 1) Exemplo Calcule a raiz negativa de f(x)=x414x2+24x-10=0 utilizando o método de newton-Raphson com precisão 0,001 e um máximo de 5 iterações. Sabe-se que esta raiz está situada no intervalo (-6,0) Exemplo Aplicando o método da Bisseção para diminuir o intervalo f(-6)=638 + - -6 0 f(0)=-10 Exemplo Aplicando o método da Bisseção para diminuir o intervalo f(-6)=638 + - - -6 -3 0 f(-3)=-127 f(0)=-10 Exemplo Aplicando o método da Bisseção para diminuir o intervalo f(-6)=638 + + - - -6 -4,5 -3 0 f(-4,5)=8,562 f(-3)=-127 Exemplo Aplicando o método da Bisseção para diminuir o intervalo + + -6 -4,5 f(-4,5)=8,562 - - - -3 0 -3, 75 f(-3,75)=-99.125 f(-3)=-127 Exemplo Aplicando o método da Bisseção para diminuir o intervalo + + - -6 -4,5 -3, 75 - - -3 0 Exemplo f’(x)=4x3-28x+24 <0 no intervalo [-4,5;-3,75] f’’(x)=12x2-28 >0 no intervalo [-4,5;-3,75] Como f(-4,5)f’’(-4,5)>0 então x0=-4,5 Exemplo k xk f(xk) f'(xk) |xk-xk-1| 0 -4,5 8,562 -214,5 - 1 -4,460 0,153 -205,986 2 -4,459 0,018 0,040 0,001 Notas Com relação à convergência o que se faz na prática é: 1) toma-se uma estimativa inicial próxima da raiz; para isto basta diminuir suficientemente o intervalo que a contém 2) toma-se x0 є [a,b] de forma que seja obtido x1 є [a,b] Comparação - Bisseção Apesar de sempre convergir, tem baixa velocidade de convergência Utilizado de forma isolada quando se deseja um intervalo, tal que qualquer dos pontos pode ser tomado como raiz Normalmente é utilizado para reduzir o tamanho do intervalo que contém a raiz Comparação – F.P. e N.R. Quando se deseja é um intervalo que contém a raiz o método da Falsa Posição não é adequado porquê não converge Quando não houver problemas para trabalhar com a primeira derivada de f(x) deve-se usar o método de NewtonRaphson; caso contrário deve-se usar o método da Falsa Posição Exercício Determine os limites das raízes reais da equação f(x)=x3+4x2-10=0