Baixe o app para aproveitar ainda mais
Prévia do material em texto
NOTAS DE AULA Cálculo Numérico Universidade Tecnológica Federal do Paraná - UTFPR - Maiko Fernandes Buzzi Cálculo Numérico – (Maiko) ii Índice 1 Noções básicas sobre Erros ........................................................................... 1-1 1.1 Erros ............................................................................................................. 1-1 1.2 Erros Absolutos e Relativos ............................................................................ 1-1 1.2.1 Erro Absoluto.................................................................................................................. 1-1 1.2.2 Erro Relativo ou Taxa de Erro ......................................................................................... 1-2 1.3 Erros de Arredondamento e Truncamento...................................................... 1-2 1.3.1 Erro de Arredondamento ............................................................................................... 1-2 1.3.2 Erro de Truncamento ..................................................................................................... 1-2 1.4 Aritmética de Ponto Flutuante ....................................................................... 1-2 1.5 Conversão de Bases ....................................................................................... 1-3 1.5.1 Conversão da Base para a Decimal (10) ................................................................ 1-3 1.5.2 Conversão da Base Decimal para a (10) ................................................................ 1-4 1.5.3 Exercícios: Conversão de Bases ...................................................................................... 1-6 1.6 Operações de Pontos Flutuantes .................................................................... 1-7 1.6.1 Representações .............................................................................................................. 1-7 1.6.2 Exercícios ........................................................................................................................ 1-7 1.6.3 Exercícios complementares ............................................................................................ 1-8 2 Zeros reais de funções reais ........................................................................ 2-11 2.1 Introdução .................................................................................................. 2-11 2.2 Fase I: Isolamento das raízes ........................................................................ 2-11 2.3 Fase II: Refinamento - Critérios de Parada .................................................... 2-15 2.3.1 Método da Bissecção (ou Método da Dicotomia) ........................................................ 2-15 2.3.2 Método do Ponto Fixo (ou Método da Iteração Linear ou Método das Aproximações sucessivas) 2-18 2.3.3 Método de Newton, Newton-Raphson (ou Método das Tangentes) ........................... 2-26 2.3.4 Método da Secante ...................................................................................................... 2-29 2.3.5 Comparação entre os métodos .................................................................................... 2-32 3 Resolução de sistemas de equações lineares .............................................. 3-34 3.1 Introdução .................................................................................................. 3-34 3.1.1 Forma Algébrica de Sn .................................................................................................. 3-34 3.1.2 Forma Matricial de Sn .................................................................................................. 3-34 3.1.3 Matriz Aumentada ou Matriz Completa do Sistema .................................................... 3-34 3.1.4 Solução do Sistema ...................................................................................................... 3-34 3.1.5 Classificação de um Sistema Linear .............................................................................. 3-34 3.1.6 Classificação quanto ao Determinante de A ................................................................ 3-35 3.2 Métodos diretos .......................................................................................... 3-35 3.2.1 Método de Eliminação de Gauss .................................................................................. 3-35 3.2.2 Estratégia de Pivoteamento Completo ........................................................................ 3-38 3.2.3 Fatoração LU ................................................................................................................ 3-40 3.2.4 Refinamento de Soluções ............................................................................................. 3-46 3.3 Métodos iterativos ...................................................................................... 3-47 3.3.1 Testes de parada .......................................................................................................... 3-47 3.3.2 Método de Gauss-Jacobi .............................................................................................. 3-47 3.3.3 Método de Gauss-Seidel .............................................................................................. 3-50 3.3.4 Comparação entre os métodos .................................................................................... 3-51 3.3.5 Critério de Sassenfeld ................................................................................................... 3-53 4 Interpolação .............................................................................................. 4-55 Cálculo Numérico – (Maiko) iii 4.1 Interpolação polinomial ............................................................................... 4-55 4.1.1 Existência e Unicidade do Polinômio Interpolador Pn(x) .............................................. 4-55 4.1.2 Forma de Lagrange ....................................................................................................... 4-56 4.1.3 Forma de Newton ......................................................................................................... 4-58 4.2 Estudo de erro na interpolação .................................................................... 4-59 4.2.1 Estimativa para o Erro .................................................................................................. 4-60 4.3 Interpolação inversa: casos existentes.......................................................... 4-61 4.3.1 Encontrar x tal que nP )(x ....................................................................................... 4-61 4.3.2 Interpolação inversa ..................................................................................................... 4-62 4.4 Funções spline em interpolação ................................................................... 4-63 4.4.1 Função Spline ............................................................................................................... 4-64 4.4.2 Spline linear interpolante ............................................................................................. 4-64 4.4.3 Spline cúbica interpolante ............................................................................................ 4-65 5 Ajuste de curvas pelo método dos mínimos quadrados ............................... 5-71 5.1 Introdução .................................................................................................. 5-71 5.2 Caso Discreto ............................................................................................... 5-72 5.3 Caso Contínuo ............................................................................................. 5-76 5.4 Família de Funções Não Lineares nos Parâmetros ......................................... 5-796 Integração Numérica ................................................................................. 6-81 6.1 Fórmulas de Newton-Cotes .......................................................................... 6-81 6.1.1 Regra dos Trapézios ..................................................................................................... 6-81 6.1.2 Regra dos Trapézios repetida ....................................................................................... 6-83 6.1.3 Regra 1/3 de Simpson .................................................................................................. 6-84 6.1.4 Regra 1/3 de Simpson repetida .................................................................................... 6-87 7 Solução numérica de equações diferenciais ordinárias ................................ 7-90 7.1 Introdução .................................................................................................. 7-90 7.2 Problema de valor inicial (PVI) ..................................................................... 7-91 7.2.1 Solução numérica de um PVI de primeira ordem......................................................... 7-91 7.2.2 Método de Euler ........................................................................................................... 7-91 7.2.3 Métodos de Runge-Kutta ............................................................................................. 7-94 7.2.4 Método de Euler Aprimorado (Método de Runge-Kutta de Segunda Ordem) ............ 7-96 7.2.5 Fórmulas de Runge-Kutta de Quarta Ordem................................................................ 7-96 8 Referências Bibliográficas .......................................................................... 8-98 Cálculo Numérico Noções básicas sobre Erros Maiko 1-1 1 Noções básicas sobre Erros Fenômenos da natureza podem ser descritos através do uso de modelos matemáticos. • MODELAGEM: é a fase de obtenção de um modelo matemático que descreve o comportamento do problema que se quer estudar. • RESOLUÇÃO: é a fase de obtenção da solução do modelo matemático através da aplicação de métodos numéricos. 1.1 Erros Para se obter a solução do problema através do modelo matemático, erros são cometidos nas fases: MODELAGEM e RESOLUÇÃO. 1. Calcular a área da superfície terrestre usando a formulação 𝐴 = 4𝜋𝑟2. Resolução: Aproximações (ERROS): MODELAGEM: a Terra é modelada como uma esfera, uma idealização de sua forma verdadeira. O raio da Terra é obtido por medidas empíricas e cálculos prévios. RESOLUÇÃO: o valor de requer o truncamento de um processo infinito; os dados de entrada e os resultados de operações aritméticas são arredondados pelo computador. OBS. 1: Características do planeta Terra. • Características Físicas: Diâmetro Equatorial: 12756Km; Diâmetro Polar: 12713Km; Massa: 5,981024Kg; Perímetro de Rotação Sideral: 23h 56min 04seg; Inclinação do Equador Sobre a Órbita: 23o 27’. • Características Orbitais: Raio da Órbita, isto é, 1U.A. (unidade astronômica): 149897570Km; Distância Máxima do Sol: 152100000Km; Distância Mínima do Sol: 147100000Km; Período de Revolução Sideral: 365dias 6h 9min 9,5seg; Velocidade Orbital Média: 29,79Km/seg. 1.2 Erros Absolutos e Relativos 1.2.1 Erro Absoluto É o módulo da diferença entre um valor exato 𝑥 de um número e seu valor aproximado �̅�. 𝐸𝐴𝑥 = |𝑥 − �̅�|, onde 𝑥 é o valor exato e �̅� é o valor aproximado. Geralmente não se conhece o valor exato 𝑥. Assim, o que se faz é obter um limitante superior (𝑘1 majorante) ou uma estimativa para o módulo do erro absoluto. |𝐸𝐴𝑥| ≤ 𝑘1. MODELAGEM MODELO MATEMÁTICO RESOLUÇÃO SOLUÇÃOPROBLEMA Cálculo Numérico Noções básicas sobre Erros Maiko 1-2 1.2.2 Erro Relativo ou Taxa de Erro Erro relativo de 𝑥 é o módulo do quociente entre o erro absoluto 𝐸𝐴𝑥 e o valor exato 𝑥 ou o valor aproximado �̅�, se 𝑥 ou �̅� ≠ 0. 𝐸𝑅𝑥 = | 𝐸𝐴𝑥 𝑥 | = | 𝑥−�̅� 𝑥 | ou 𝐸𝑅𝑥 = | 𝐸𝐴𝑥 �̅� | = | 𝑥−�̅� �̅� |. 2. Calcular os erros absoluto e relativo, nos itens a) e b). a) 𝑥 = 1,5 e �̅� = 1,49; b) 𝑦 = 5,4 e �̅� = 5,39. Resolução: a) 𝐸𝐴𝑥 = 0,01 = 10 −2 b) 𝐸𝐴𝑥 = 0,01 = 10 −2 𝐸𝑅𝑥 = 0.00666667 𝐸𝑅𝑥 = 0.00185185 1.3 Erros de Arredondamento e Truncamento 1.3.1 Erro de Arredondamento Arredondar um número na casa 𝑑𝑖 é desconsiderar as casas 𝑑𝑖+𝑗 (𝑗 = 1,… ,∞) de tal forma que: 𝑑𝑖 seja a última casa se 𝑑𝑖+1 < 5; 𝑑𝑖 + 1 seja a última casa se 𝑑𝑖+1 ≥ 5. 3. Arredondar 𝜋 na quarta casa decimal, sendo que 𝜋 = 3,1415926535… Resolução: 𝑑𝑖 = 5 e 𝑑𝑖+1 = 9 > 5 ⇒ 𝑑𝑖 + 1 = 5 + 1 = 6. Logo: 𝜋 = 3,1416. 1.3.2 Erro de Truncamento Truncar um número na casa 𝑑𝑖 é desconsiderar as casas 𝑑𝑖+𝑗 (𝑗 = 1,… ,∞). 4. Aproximar truncando na quarta casa decimal, sendo que 𝜋 = 3,1415926535… Resolução: 𝑑𝑖 = 5⇒ 𝜋 = 3,1415. 5. Sabendo-se que 𝑒𝑥 pode ser escrito através da fórmula abaixo, faça a aproximação de 𝑒2 através de um truncamento após quatro termos da somatória. 𝑒𝑥 =∑ 𝑥𝑖 𝑖! ∞ 𝑖=0 = 1 + 𝑥 1! + 𝑥2 2! + 𝑥3 3! + ⋯ , −∞ < 𝑥 < ∞ Resolução: Truncando-se após quatro termos, tem-se: 𝑒2 =∑ 2𝑖 𝑖! 3 𝑖=0 = 1 + 21 1! + 22 2! + 23 3! = 1 + 2 + 4 2 + 8 6 = 19 3 1.4 Aritmética de Ponto Flutuante Um número é representado, internamente, na máquina de calcular ou no computador através de uma seqüência de impulsos elétricos que indicam dois estados: 0 ou 1, ou seja, os números são representados na base 2 ou binária. De maneira geral, um número 𝑥 é representado na base por: Cálculo Numérico Noções básicas sobre Erros Maiko 1-3 𝑥 = ± [ 𝑑1 𝛽 + 𝑑2 𝛽2 + 𝑑3 𝛽3 +⋯+ 𝑑𝑡 𝛽𝑡 ] ∗ 𝛽𝑒𝑥𝑝 Onde: • 𝑑𝑖 são números inteiros contidos no intervalo 0 ≤ 𝑑𝑖 < 𝛽; 𝑖 = 1, 2, … , 𝑡; • 𝑒𝑥𝑝 representa o expoente de e assume valores entre 𝐼 ≤ 𝑒𝑥𝑝 ≤ 𝑆; • I, S limite inferior e limite superior, respectivamente, para a variação do expoente; • [ 𝑑1 𝛽 + 𝑑2 𝛽2 + 𝑑3 𝛽3 +⋯+ 𝑑𝑡 𝛽𝑡 ] é chamada de mantissa e é a parte do número que representa seus dígitos significativos; • t número de dígitos do sistema de representação. 6. Considerando no sistema de base 10, =10, represente os seguintes números, em aritmética de ponto flutuante: a) 0,34510; b) 31,41510. Resolução: a) 0,34510 = + + ; b) 31,41510= + + + + . OBS. 2: Os números assim representados estão NORMALIZADOS, isto é, a mantissa é um número entre 0 e 1. 7. Considerando no sistema binário, =2, represente o número 1012 em aritmética de ponto flutuante. Resolução: 1012 = 0,101 = + 22 0 + . 1.5 Conversão de Bases 1.5.1 Conversão da Base para a Decimal (10) Um número na base pode ser escrito, na base decimal, como: = + ++ + + + + ++ + . Onde: • 0 ; • , números inteiros, com 0 e 0. Para a conversão, faz-se a operação entre a mantissa do número normalizado e a base . Nos exercícios a seguir, faça a conversão da base indicada para a decimal, determinando o valor da variável . 10 3 210 4 310 5 010 10 3 210 1 310 4 410 1 510 5 210 32 2 1 32 1 32 = m ni i ia m ma 1 1 − − m ma 2 2a 1a 0a 1 1 − − a 2 2 − − a 1 1 + + n na n na ia ia n m n m exp x Cálculo Numérico Noções básicas sobre Erros Maiko 1-4 8. 10112 = . Resolução: 10112 = 0,1011 = + + + = +2+1=11 10112 = 1110 =11. 9. 11,012 = . Resolução: 11,012 = 0,1101 = + + + =2+1+ =3,25 11,012 = 3,2510 =3,25. 10. 403,125 = . Resolução: 403,125 = 0,40312 = + + + + =4 +0+3+ + =100+3+0,2+0,08=103,28 403,125 = 103,2810 =103,28. 1.5.2 Conversão da Base Decimal para a (10) Aplica-se um processo para a parte inteira e um outro para a parte fracionária. • a) PARTE INTEIRA ( ): • a.1) = . • a.2) Até que =( ) 11. Converta 5910 para a base 2. Resolução: =59 e =2 59 2 1 29 2 1 14 2 0 7 2 1 3 2 1 1 5910 = 1110112 10x 42 2 1 22 0 32 1 42 1 42 32 x 10x 22 2 1 22 1 32 0 42 1 22 22 1 x 10x 35 5 4 25 0 35 3 45 1 55 2 35 25 5 1 25 2 x N N 10N N N N 1r 1q 2r 2q 1−nq nr nq nq 10N nq nr 1−nr 3r 2r 1r N N Cálculo Numérico Noções básicas sobre Erros Maiko 1-5 12. Converta 5910 para a base 3. Resolução: =59 e =3 59 3 2 19 3 1 6 3 0 2 5910 = 20123 • b) PARTE FRACIONÁRIA ( ): Multiplica-se por e toma-se a parte inteira do produto como o primeiro dígito do número na base . Repete-se o processo com a parte fracionária do produto tomando sua parte inteira. Continua-se até que a parte fracionária seja igual a zero. Nos exercícios a seguir, determinar o valor de : 13. 0,187510 = . Resolução: 0,1875 0,375 0,75 0,5 2 2 2 2 0,3750 0,750 1,50 1,0 0,187510 = 0,00112. 14. 0,610 = . Resolução: 0,6 0,2 0,4 0,8 0,6 2 2 2 2 2 1,2 0,4 0,8 1,6 1,2 0,610 = 0,100110012. 15. 13,2510 = . Resolução: • a) 1310 = ? =13 e =2 13 2 1 6 2 0 3 2 1 1 1310 = 11012. • b) 0,2510 = ? 0,25 0,5 2 2 0,50 1,0 0,2510 = 0,012. • Logo: 13,2510 = 1310 + 0,2510 = 11012 + 0,012 = 1101,012. N N F F x 2x 2x 2x N N Cálculo Numérico Noções básicas sobre Erros Maiko 1-6 1.5.3 Exercícios: Conversão de Bases Transforme para a base que se pede (determine o valor de ). 16. 100101,10012 = . Resolução: 100101,10012 = 0,1001011001 = + + + + + + + + + = + +1+ + =32+4+1+0,5+0,0625=37,5625 100101,10012 = 37,562510 =37,5625. 17. 19,3867187510 = . Resolução: • a) 1910 = ? =19 e =4 19 4 3 4 4 0 1 1910 = 1034. • b) 0,3867187510 = ? 0,38671875 0,546875 0,1875 0,75 4 4 4 4 1,54687500 2,187500 0,7500 3,00 0,3867187510 = 0,12034. • Logo: 19,3867187510 = 1910 + 0,3867187510 = 1034 + 0,12034 = 103,12034. 18. Transforme a medida 35 48 18 para minutos. DICA: 35:48,1860 = . Resolução: 35:48,1860 = 0,35:48:18 = + + = 3560 + 48 + = 2100 + 48 + 0,3 = 2148,3 35:48,1860 = 2148,310. 35 48 18 = 2148,3 . 19. Transforme 35,805 horas para horas, minutos e segundos. DICA: 35,80510 = . Resolução: • a) 3510 = ? =35 e =60 3510 = 3560. x 10x 62 2 1 22 0 32 0 42 1 52 0 62 1 72 1 82 0 92 0 102 1 62 52 22 2 1 42 1 x 4x N N h min seg 10x min 260 60 35 260 48 360 18 260 60 18 h min seg min 60x N N Cálculo Numérico Noções básicas sobre Erros Maiko 1-7 • b) 0, 80510 = ? 0,805 0,3 60 60 48,300 18,0 0, 80510 = 0,48:1860. • Logo: 35,80510 = 3510 + 0, 80510 = 3560 + 0,48:1860 = 35,48:1860. 35,805 = 35 48 18 . 1.6 Operações de Pontos Flutuantes 1.6.1 Representações • Precisão dupla: “dobra” a mantissa (2 ); • O zero em ponto flutuante é em geral representado com o menor expoente ( = ) possível na máquina; • Ao converter um número para determinada aritmética de ponto flutuante, emprega-se sempre o arredondamento; • Não é possível representar todos os números reais em determinada aritmética de ponto flutuante (reta furada). OBS. 3: Um exemplo da reta furada é: Considere a aritmética de pontos flutuantes com parâmetros =10 e =3. Tome os números consecutivos 3,57 e 3,58. Existem infinitos números reais entre 3,57 e 3,58 que não podem ser representados nesta aritmética de pontos flutuantes. Por exemplo: 3,571 ou 3,57437. 1.6.2 Exercícios 20. Preencher a tabela a seguir, com base nos parâmetros: =3, =10, =−5, =5 e −5 ≤ exp ≤ 5. Número Truncamento Arredondamento −6,48 −0,64810 −0,64810 0,0002175 0,217 0,218 3498,3 0,349 0,35 −0,00000001452 −0,145 −0,145 UNDERFLOW 2379441,5 0,237 0,238 OVERFLOW OBS. 4: Deve-se converter os valores para a aritmética de ponto flutuante com 3 algarismos significativos. Nos exercícios seguintes, calcular o valor das expressões utilizando aritmética de ponto flutuante com 3 algarismos significativos. 21. (4,26 + 9,24) + 5,04 Resolução: 13,5 + 5,04 = 18,5. h h min seg t exp I t t I S 310− 310− 410 410 710− 710− 710 710 Cálculo Numérico Noções básicas sobre Erros Maiko 1-8 22. 4,26 + (9,24 + 5,04) Resolução: 4,26 + 14,3 = 18,6. 23. (4210 − 4,99) − 0,02 Resolução: 4210 − 0,02 = 4210. 24. 4210 − (4,99 + 0,02) Resolução: 4210 − 5,01 = 4200. 25. (4,0237 − 6,106) Resolução: 0,286(4,02 − 6,11) = 0,286(−2,09) = −0,598. 26. Resolução: = = −0,597. OBS. 5: Em aritmética de ponto flutuante não valem as propriedades associativas nem distributivas. 27. Sendo =10, =4 e [−5,5], calcule: a) 42450 + ; b) + 42450. Resolução: • a) 42450 + = 42450 = 0,4245 ; • b) + 42450 = 30 + 42450 = 42480 = 0,4248 . 1.6.3 Exercícios complementares Nos exercícios seguintes, converter os números para a base decimal, determinando o valor da variável : 28. 11000112 = . Resolução: 11000112 =0, 1100011 = + + + + + + = + +2+1 = 99 11000112 = 9910 =99. 29. 11111112 = . Resolução: 11111112 =0, 1111111 = + + + + + + = + + + + +2+1 = 127 11111112 = 12710 =127. 7 2 7 1066023742 ),,( − 7 0922 ),(− 7 184,− t exp = 10 1 3 i = 10 1 3 i = 10 1 3 i 510 = 10 1 3 i 510 x 10x 72 2 1 22 1 32 0 42 0 52 0 62 1 72 1 72 62 52 x 10x 72 2 1 22 1 32 1 42 1 52 1 62 1 72 1 72 62 52 42 32 22 x Cálculo Numérico Noções básicas sobre Erros Maiko 1-9 30. 10101012 = . Resolução: 10101012 =0, 1010101 = + + + + + + = + + +1 = 85 10101012 = 8510 =85. 31. 101,00112 = . Resolução: 101,00112 = 0, 1010011 = + + + + + + = +1+ + = 5 + 0,125 + 0,0625 = 5 + 0,1875 = 5,1875 101,00112 = 5,187510 =5,1875. 32. 0,01111112 = . Resolução: 0,01111112 = 0, 111111 = + + + + + = + + + + + = 0,25 + 0,125 + 0,0625 + 0,03125 + 0,015625 + 0,0078125 = 0,4921875 0,01111112 = 0,492187510 =0,4921875. 33. 1,0100112 = . Resolução: 1,0100112 = 0, 10100112= + + + + + + 2 =1+ + + = 1 + 0,25 + 0,03125 + 0,015625 = 1,296875 1,0100112 = 1,29687510 =1,296875. Nos exercícios seguintes, converter os números para a base binária, determinando o valor da variável : 34. 3710 = . Resolução: =37 e =2 37 2 1 18 2 0 9 2 1 4 2 0 2 2 0 1 3710 = 1001012 10x 72 2 1 22 0 32 1 42 0 52 1 62 0 72 1 72 62 42 22 x 10x 32 2 1 22 0 32 1 42 0 52 0 62 1 72 1 32 22 32 1 42 1 x 10x 12− 2 1 22 1 32 1 42 1 52 1 62 1 12− 22 1 32 1 42 1 52 1 62 1 72 1 x 10x 2 1 22 0 32 1 42 0 52 0 62 1 72 1 22 1 52 1 62 1 x x 2x N N Cálculo Numérico Noções básicas sobre Erros Maiko 1-10 35. 234510 = . Resolução: =2345 e =2 2345 2 1 1172 2 0 586 2 0 293 2 1 146 2 0 73 2 1 36 2 0 18 2 0 9 2 1 4 2 0 2 2 0 1 234510 = 1001001010012 36. Determine com 36 dígitos: 0,121710 = . Resolução: 0,1217 0,2434 0,4868 0,9736 0,9472 0,8944 0,7888 0,5776 0,1552 0,2434 0,4868 0,9736 1,9472 1,8944 1,7888 1,5776 1,1552 0,3104 0,3104 0,6208 0,2416 0,4832 0,9664 0,9328 0,8656 0,7312 0,4624 0,62081,2416 0,4832 0,9664 1,9328 1,8656 1,7312 1,4624 0,9248 0,9248 0,8496 0,6992 0,3984 0,7968 0,5936 0,1872 0,3744 0,7488 1,8496 1,6992 1,3984 0,7968 1,5936 1,1872 0,3744 0,7488 1,4976 0,4976 0,9952 0,9904 0,9808 0,9616 0,9232 0,8464 0,6928 0,3856 0,9952 1,9904 1,9808 1,9616 1,9232 1,8464 1,6928 1,3856 0,7712 0,121710 = 0,0001111100100111101110110010111111102. 37. Determine com 8 dígitos: 2,4710 = . Resolução: • a) 210 = ? =2 e =2 2 2 210 = 102. 0 1 • b) 0, 4710 = ? 0,47 0,94 0,88 0,76 0,52 0,04 0,08 0,16 0,32 0,94 1,88 1,76 1,52 1,04 0,08 0,16 0,32 0,64 0, 4710 = 0,011110002. Logo: 2,4710 = 210 + 0, 4710 = 102 + 0,011110002 = 10, 011110002. 2x N N x 2x x 2x N N Cálculo Numérico Zeros reais de funções reais Maiko 2-11 2 Zeros reais de funções reais 2.1 Introdução Dada uma função real definida e contínua em um intervalo aberto , chama-se de zero desta função em , a todo , tal que f( ) = 0. Neste capítulo são apresentados alguns processos iterativos para calcular de forma aproximada os zeros reais de uma função real dada. Por um processo iterativo entende-se um processo que calcula uma seqüência de aproximações , , , da solução desejada. O cálculo de uma nova aproximação é feito utilizando aproximações anteriores. Dizemos que a seqüência , , , converge para , se dado 0, ℕ (ℕ números naturais), tal que qualquer que seja , . Neste caso tem-se que = , o que também poderá ser indicado por → . Nos processos iterativos que serão apresentados, a determinação dos zeros de uma função real de variável real será feita em duas etapas: • Fase I: Isolar cada zero que se deseja determinar da função em um intervalo [ , ], sendo que cada intervalo deverá conter um e somente um zero da função . • Fase II: Cálculo dos zeros aproximados utilizando um método iterativo, com precisão prefixada ou não. 2.2 Fase I: Isolamento das raízes Teorema 1 Seja f (x) uma função contínua num intervalo [a, b]. Se 𝑓(𝑎) ∙ 𝑓(𝑏) < 0, então existe pelo menos um zero de f (x) entre a e b. OBS. 1: Sob as hipóteses do teorema 1, o zero x = será definido e único em [ a ,b ] se a derivada 'f ( x ) existir e preservar o sinal dentro do intervalo ] a ,b [, isto é se 'f ( x )0, x ] a ,b [ ou 'f ( x )0, x ] a ,b [. Isto significa dizer que a função f ( x ) é estritamente crescente ou estritamente decrescente, respectivamente, no intervalo ] a ,b [. f I I x I x f 1x 2x 3x 1x 2x 3x x N n N xxn − n n x → lim x nx x f a b f y x y =f x( ) a b y x y =f x( ) a b Cálculo Numérico Zeros reais de funções reais Maiko 2-12 Na pesquisa dos zeros reais de funções reais é muito útil o uso do Teorema 1 (que fornece condições de existência de zeros em um intervalo), bem como da OBS 1. (que garante a unicidade, isto é, garante que no intervalo considerado existe um e somente um zero da função ). Outro recurso bastante empregado é: a partir da equação 𝑓(𝑥) = 0, obter a equação equivalente ( )= ( ) e esboçar os gráficos destas funções obtendo os pontos onde as mesmas se intersectam, pois ()=0 ()= (). 38. Isolar os zeros da função ( )= −9 +3. Resolução: Pode-se construir uma tabela de valores para ( ) e analisar os sinais: x −4 −3 −2 −1 0 1 2 3 ( ) − + + + + − − + Como , e , conclui-se, de acordo com o teorema 1, que existem zeros de nos intervalos [−4,−3], [0,1] e [2,3]. Como 𝑓(𝑥) = 0 tem exatamente 3 raízes, pode-se afirmar que existe exatamente um zero em cada um destes intervalos. Pode-se também chegar às mesmas conclusões partindo da equação ( )= −9 +3=0, obtendo-se a equação equivalente =9 −3. Neste caso, tem-se que e . Traçando os gráficos de e , verifica-se que as abscissas dos pontos de intersecção destas curvas estão nos intervalos [−4,−3], [0,1] e [2,3]. f g x h x f g h f x 3x x f x f x 034 −− )()( ff 010 )()( ff 032 )()( ff )(xf y x y = f x( ) 4321-1-2-3-4 1 2 3 f x 3x x 3x x 3xxg =)( 39 −= xxh )( )(xg )(xh y x 4321-1-2-3-4 1 2 3 g x( ) h x( ) Cálculo Numérico Zeros reais de funções reais Maiko 2-13 Outra forma de se verificar a unicidade de zeros nestes intervalos, é traçar o gráfico da função derivada de , e confirmar que a mesma preserva o sinal em cada um dos intervalos ]−4,−3[, ]0,1[ e ]2,3[, conforme a 2.2. 39. Isolar os zeros da função . Resolução: Pode-se construir uma tabela de valores para e analisar os sinais: x 1 2 3 4 − − + + Como , conclui-se, de acordo com o teorema 1, que existem zeros de no intervalo [2,3]. Pode-se ainda verificar graficamente que a função derivada da função , preserva o sinal no intervalo ]2,3[, neste caso ]2,3[, o que pela Obs. 1 garante que só existe um zero de neste intervalo. )(xf 93 2 −= xxf )(' y x y = f’ x( ) 4321-1-2-3-4 33- 23,ln)( −= xxxf )(xf )(xf 032 )()( ff )(xf x y =f x( ) 0 -0,1 -0,2 -0,3 -0,4 -0,5 -0,6 -0,7 -0,8 -0,9 -1,0 -0,8 2,6 2,8 3,0 3,2 3,4 0,1 0,2 0,3 y )(xf xxf ln)(' +=1 0)(' xf x )(xf Cálculo Numérico Zeros reais de funções reais Maiko 2-14 40. Isolar os zeros da função . Resolução: Pode-se construir uma tabela de valores para e analisar os sinais: X 1 2 3 − + + Como , conclui-se, de acordo com o teorema 1, que existem zeros de no intervalo [1,2]. Pode-se também chegar a esta mesma conclusão partindo da equação =0, obtendo-se a equação equivalente . Neste caso, tem-se que e . Traçando os gráficos de e , verifica-se que a abscissa do único ponto de intersecção destas curvas está no intervalo [1,2]. 41. Isolar os zeros da função . Resolução: Pode-se construir uma tabela de valores para e analisar os sinais: x 0 1 2 3 − − + + Como , conclui-se, de acordo com o teorema 1, que existem zeros de no intervalo [1,2]. Pode-se também chegar a esta mesma conclusão partindo da equação =0, obtendo-se a equação equivalente . Neste caso, tem-se que e . Traçando os gráficos de e , verifica-se que a abscissa do único ponto de intersecção destas curvas está no intervalo [1,2]. y x1 1 x( )f’ xxxf 4025 ,log)( +−= )(xf )(xf 021 )()( ff )(xf xxxf 4025 ,log)( +−= xx 4025 ,log −= xxg log)( 5= xxh 4,02)( −= )(xg )(xh y x x( ) 21 3 2 1 h x( )g xexxf −−= 5)( )(xf )(xf 021 )()( ff )(xf xexxf −−= 5)( xex −= 5 xxg =)( xexh −= 5)( )(xg )(xh Cálculo Numérico Zeros reais de funções reais Maiko 2-15 2.3 Fase II: Refinamento - Critérios de Parada 2.3.1 Método da Bissecção (ou Método da Dicotomia) Este método é normalmente utilizado para diminuir o intervalo que contém o zero da função, para a aplicação de outro método, pois o esforço computacional cresce demasiadamente quando se aumenta a precisão exigida. O processo consiste em dividir o intervalo que contém o zero ao meio e por aplicação do Teorema 1, aplicado aos subintervalos resultantes, determinar qual deles contém o zero. , O processo é repetido para o novo subintervalo até que se obtenha uma precisão prefixada. Desta forma, em cada iteração o zero da função é aproximado pelo ponto médio de cada subintervalo que a contém. Assim, na figura anterior tem-se: , , , Desta forma, o maior erro que se pode cometer na: • 1a iteração ( =1): é • 2a iteração ( =2): é y x x( ) 21 3 2 1 h x( )g + 2 ba a, + b ba , 2 y x 2 1 3 x( )f a bmm m 2 1 ba m + = 2 1 2 ma m + = 2 12 3 mm m + = n 2 )( ab − n 22 )( ab − Cálculo Numérico Zeros reais de funções reais Maiko 2-16 • 3a iteração ( =3): é • a iteração: é Se o problema exige que o erro cometido seja inferior a um parâmetro , determina-sea quantidade n de iterações encontrando o maior inteiro que satisfaz a inequação: que se resolve da seguinte maneira: − − 2 42. Determinar um valor aproximado para , com erro inferior a . Resolução: Determinar é equivalente a obter o zero positivo da função = −5. Sabe-se que o intervalo [2,3] contém este zero e a tolerância neste caso é = . Assim, a quantidade mínima de iterações para se obter a resposta com a precisão exigida é: 6,643856. Como deve ser intero, tem-se =7. ( ) ( ) ( ) ( − )/2 1 2,0 2,5 3,0 − + + 0,5 2 2,0 2,25 2,5 − + + 0,25 3 2,0 2,125 2,25 − − + 0,125 4 2,125 2,1875 2,25 − − + 0,0625 5 2,1875 2,21875 2,25 − − + 0,03125 6 2,21875 2,234375 2,25 − − + 0,015625 7 2,234375 2,2421875 2,25 − + + 0,0078125 Portanto 2,24218750,0078125 43. Um tanque de comprimento tem uma secção transversal no formato de um semicírculo com raio r (veja a figura). Quando cheio de água até uma distância h do topo, o volume V da água é: V= . Supondo que =10 , r=1 ft e V=12,4 , encontre a profundidade da água no tanque com precisão de 0,01 . n 32 )( ab − n n ab 2 )( − n ab 2 )( − n ab 2 )( − log n ab 2 )( − log )log( ab − log n2 log )log( ab − n log log n 2log log)log( −− ab 5 210− 5 )(xf 2x 210− n 2log log)log( −− ab n 2 1023 2 log log)log( −−− n 2 1021 log loglog + n 2 120 log + n n n n a x b f a f x f b b a 5 L −− − )(arcsen, 222250 hrh r h rrL L ft 3ft ft Cálculo Numérico Zeros reais de funções reais Maiko 2-17 Resolução: Para calcular a profundidade r−h da água, substitui-se os valores de , e na expressão anterior para obter a equação + +1,24−0,5=0 cuja raiz é . Assim, deve-se calcular o zero da função + +1,24−0,5, com precisão de = . Para isto, primeiramente isola-se o zero desta função num intervalo da seguinte forma. Pode-se construir uma tabela de valores para e analisar os sinais: H −1 0 1 Como , conclui-se, de acordo com o teorema 1, que existem zeros de no intervalo [0,1]. Para se confirmar a unicidade deste zero neste intervalo, pode-se utilizar a OBS. 1, isto é, calcula-se a derivada de para verificar que a mesma preserva o sinal no intervalo ]0,1[. Assim, obtém-se = + + (−2 ) = , o que significa que é estritamente crescente neste intervalo, o que garante a unicidade do zero de em ]0,1[. Agora determina-se o número de iterações necessárias para se obter a precisão exigida: 6,643856 Logo são necessárias = 7 iterações. (b−a)/2 1 0 0,5 1 − + + 0,5 2 0 0,25 0,5 − + + 0,25 3 0 0,125 0,25 − − + 0,125 4 0,125 0,1875 0,25 − + + 0,0625 5 0,125 0,15625 0,1875 − − + 0,03125 6 0,15625 0,171875 0,1875 − + + 0,015625 7 0,15625 0,1640625 0,171875 − − + 0,0078125 Assim, =0,16406250,0078125 e a profundidade − da água solicitada é aproximadamente 1−(0,1640625) . h h r r L V )(arcsen h h 21 h− h =)(hf )(arcsen h h 21 h− 210− )(hf 010 )()( ff )(hf )( , hf )(hf )( , hf 21 1 h− 21 h− ( ) 2121 2 /− − h h h )( , hf 0 1 12 2 2 − − h h )( [,] 10h )(hf )(hf 2log log)log( −− ab n 2 101 2 log loglog −− n n n n a h b )(af )(hf )(bf h r h ft Cálculo Numérico Zeros reais de funções reais Maiko 2-18 Algoritmo do Método da Bissecção Seja uma função contínua em um intervalo [a,b], com . <0 e a raiz de isolada em [ , ]. • Dados de Entrada: Pontos extremos e do intervalo; precisão ou tolerância () e o número máximo de iterações (ITMAX). • Saída: Solução aproximada ou mensagem de "solução não encontrada" com a precisão desejada no número máximo de iterações. PASSO 1 Faça =1 FA= PASSO 2 Enquanto ITMAX execute os passos de 3 a 6 PASSO 3 Faça = e FX = PASSO 4 Se FX = 0 ou < , então Saída ( ) (Procedimento executado com sucesso) FIM PASSO 5 Faça = +1 PASSO 6 Se FA·FX > 0 então faça = e FA = FX Caso contrário faça = PASSO 7 Saída (Solução não encontrada com a precisão exigida) FIM 2.3.2 Método do Ponto Fixo (ou Método da Iteração Linear ou Método das Aproximações sucessivas) Neste método a seqüência de aproximações do zero de uma função 𝑓(𝑥) (𝑓(𝛼) = 0) é obtida através de uma relação de recorrência da forma: , n 0, 1, 2, O ponto será considerado uma aproximação inicial do zero da função e é uma função que tem como ponto fixo, isto é, = . A primeira pergunta a ser respondida é: dada uma função com zero , como encontrar uma função que tenha como ponto fixo? Isto pode ser feito através de uma série de manipulações algébricas sobre a equação =0, transformando-a em uma equação equivalente da forma . Nestas transformações devem-se tomar os devidos cuidados para que esteja definida em e para que pertença à imagem de . Como o zero é desconhecido, é necessário determinar um intervalo I que contenha e que esteja contido tanto no domínio quanto na imagem de . É necessário que o zero de seja único no intervalo I, caso contrário não será possível discernir qual o zero determinado. )(xf )(af )(bf )(xf a b a b x i )(af i x 2 )( ba + )(xf 2 )( ab − x i i a x b x )(1 nn xx =+ = 0x )(xf )(x )( )(xf )(x )(xf )(xx = )(x )(xf Cálculo Numérico Zeros reais de funções reais Maiko 2-19 44. Obter algumas funções de ponto fixo para a função = . Resolução: Efetuando diferentes manipulações algébricas sobre a equação =0 ou =0, podem-se obter diferentes funções de ponto fixo, como por exemplo: a) =0 , logo . Como =−3 e =2, tem-se que −3 e 2 são pontos fixos de . b) =0 , logo se pode ter e neste caso tem-se que 2 é ponto fixo de , pois , ou e neste caso tem-se que −3 é ponto fixo de , pois . c) =0 , logo . Como =−3 e =2, tem-se que −3 e 2 são pontos fixos de . d) =0 , logo . Como =−3 e =2, tem-se que −3 e 2 são pontos fixos de . No próximo passo algumas destas funções serão utilizadas na tentativa de gerar seqüências aproximadoras dos zeros de . 45. Aproximar o maior zero da função = , utilizando a função , e =1,5. Resolução: Neste caso a fórmula de recorrência , n 0, 1, 2, será: , e pode-se construir a seguinte tabela: n 0 1,5 2,12132 1 2,12132 1,96944 2 1,96944 2,00763 3 2,00763 1,99809 4 1,99809 2,00048 Percebe-se que neste caso a seqüência converge para a raiz =2 da equação 0. y x y x= Ponto fixo de (Zero de ) x( ) x( ) x( )f )(xf 62 −+ xx )(xf 62 −+ xx 62 −+ xx 26 xx −= 2 1 6)( xx −= )3(1 − )2(1 )(1 x 62 −+ xx xx −= 6 xx −= 6)(2 )(2 x 2)2(2 = xx −−= 6)(2 )(2 x 3)3(2 −=− 62 −+ xx 06 =−+ xxx x x x x −= 6 1 6 −= x x = )(3 x 1 6 − x )3(3 − )2(3 )(3 x 62 −+ xx 06 =−+ xxx 06)1( =−+xx 1 6 + = x x 1 6 )(4 + = x x )3(4 − )2(4 )(4 x )(xf )(xf 62 −+ xx xx −= 6)(2 0x )(1 nn xx =+ = nnn xxx −==+ 6)(21 nx nnn xxx −==+ 6)(21 }{ nx 62 −+ xx = Cálculo Numérico Zeros reais de funções reais Maiko 2-20 46. Aproximar o maior zero da função = , utilizando a função , e =1,5. Resolução: Neste caso a fórmula de recorrência , =0, 1, 2, será: , e pode-se construir a seguinte tabela: n 0 1,5 3,75 1 3,75 −8,0625 2 −8,0625 −59,003906 3 −59,003906 −3475,4609 Percebe-se que neste caso a seqüência não converge para a raiz 2 da equação 0. y x x( ) 0 x 1x2 x3 y x= x 6 6 2= 2 )(xf 62 −+ xx 2 1 6)( xx −= 0x )(1 nn xx =+ n 2 11 6 nnn xxx −==+ )( nx 2 11 6)( xxx nn −==+ }{ nx = 62 −+ xx = y x x( ) 0 1 x2 x y x= x 6 2= 1 Cálculo Numérico Zeros reais de funções reais Maiko 2-21 Assim, os dois exercícios anteriores mostram que dependendo da transformação escolhida, a relação de recorrência pode ou não fornecer uma seqüência convergente. Desta forma, como determinar a priori, quais transformaçõesfornecerão seqüências convergentes? As figuras que seguem ilustram alguns casos onde ocorrem convergência e alguns casos onde não ocorre convergência. A seqüência converge para o zero (Convergência do tipo escada). A seqüência converge para o zero (Convergência do tipo caracol). A seqüência não converge para o zero . )(xx = )(1 nn xx =+ }{ nx kx y xx0x1x2x3 y x= x( ) kx y xx0x1 x2x3 y x= x4 x( ) kx y xx0 x1 x2 x3 y x= x( ) Cálculo Numérico Zeros reais de funções reais Maiko 2-22 A seqüência não converge para o zero . O Teorema que segue estabelece condições suficientes para garantir a convergência do processo iterativo. OBS. 2: Como as condições que o teorema que segue são apenas suficientes, dada uma função que não satisfaça estas condições, não se pode garantir que a seqüência gerada diverge. Convergência do Método das Aproximações Sucessivas Teorema 2 Seja um zero de uma função f, isolada em um intervalo I=[a,b], e seja uma função tal que . Se: i) são funções contínuas em I; ii) iii) e , para n = 0, 1, 2, Então a seqüência converge para o zero . OBS. 3: Para se resolver um problema com o método das aproximações sucessivas, utiliza-se o teorema anterior da seguinte forma: inicialmente determina-se um intervalo onde o zero de esteja isolado, e uma função que tenha como ponto fixo. Analisando e , pode-se verificar se as condições i) e ii) do Teorema 2 estão satisfeitas. Estas condições podem não estar satisfeitas pelo fato do intervalo ter sido superdimensionado. Neste caso procura-se por um intervalo ’ satisfazendo as condições do teorema. Na demonstração do Teorema 2 , que pode ser vista em HUMES, Ana Flora C., et al. Noções de Cálculo Numérico. São Paulo: McGraw-Hill, p. 16, 1984, tem-se que as condições i) e ii) garantem que se então < . Entretanto, isto não implica que . Uma maneira simples para garantir que é tomar como valor inicial o extremo de mais próximo do zero . Na seqüência, será mostrado que neste caso : Supondo que a seja o extremo de mais próximo de , tem-se: < = , logo . A demonstração é análoga para o caso em que o extremo de mais próximo de . OBS. 4: A condição iii) do Teorema 2 pode ser substituída por: iii’) o zero é o ponto médio do intervalo . Na verdade, se para o intervalo = , estão satisfeitas as condições i) e ii) do Teorema 2, e se estiver mais próximo de do que de então, denotando por r, tem-se que para qualquer a hipótese iii) do teorema é verificada. Mais kx y x0x 1 x2x3 y x= x x( ) ,,, 321 xxx ( ) = ' e ( ) 1= xk Ix ' max Ix 0 Ixx nn =+ )(1 nx I )(xf ' I I 1−nx I nx− 1−− nx nx I baIxn ,= 0n 0x I Ixx = )( 01 I −1x −0x −a −b 1x I b I I I ba, a b −a 0x ra +, Cálculo Numérico Zeros reais de funções reais Maiko 2-23 ainda, para todo = nas condições do teorema 2, existe ’ tal que qualquer que seja ’ tem-se que ’, 1. OBS. 5: A determinação do extremo de = mais próximo do zero pode ser feito da seguinte maneira: Suponhamos satisfeitas as hipóteses i) e ii) do Teorema 2 . Nestas condições, seja = (ponto médio do intervalo ). Sabe-se que está mais próximo de do que . Se < , então está entre e , ou seja, é o extremo de mais próximo de . Analogamente, se > , então é o extremo de mais próximo de . Se = , então é o zero procurado. Este é o caso em que b é o extremo mais próximo de . OBS. 6: Sejam dados ( ), e = satisfazendo as hipóteses do teorema anterior. Se =( ), então . Desta forma, obtém-se um limitante superior para o erro cometido na -ésima iteração ( ). 47. Verificar as condições i) e ii) do teorema anterior quando do uso da função no exercício número 45. Resolução: Verificação da condição i): • é contínua no conjunto ={ /x 6}. • é contínua no conjunto ={ /x < 6}. Verificação da condição ii): • < 1 < 1 < 5,75 Logo, é possível obter um intervalo , tal que =2 , onde as condições i) e ii) estão satisfeitas. 48. Verificar as condições i) e ii) do teorema anterior quando do uso da função . Resolução: Verificação da condição i): • e são contínuas em . Verificação da condição ii): I ba, I I 0x I nx I n I ba, x̂ 2 )( ba + I )ˆ(x x̂ x̂ )ˆ(x x̂ b b I x̂ )ˆ(x a I x̂ )ˆ(x x̂ xx( ) a b x xx( ) a b x x k ( )x Ix ' max nx 1−nx nx− k k −1 1−− nn xx n nx xx −= 6)(2 xx −= 6)(2 S x x x − − = 62 1 2 )(' T x )(' x2 x− − 62 1 x I I 2 1 6)( xx −= 2 1 6 xx −= )( xx 21 −= )(' Cálculo Numérico Zeros reais de funções reais Maiko 2-24 • < 1 < 1 < < . Logo, não existe um intervalo , com =2 , e tal que < 1, . Algoritmo do Método das aproximações sucessivas Para encontrar uma solução para p = dada uma aproximação inicial . • Dados de Entrada: Aproximação inicial , precisão ou tolerância () e o número máximo de iterações (ITMAX). • Saída: Solução aproximada p ou mensagem de “solução não encontrada”. PASSO 1 Faça i = 1 PASSO 2 Enquanto i ITMAX, execute os passos 3 – 6 PASSO 3 Faça (calcular ) PASSO 4 Se < então Saída ( ) (procedimento efetuado com sucesso) FIM PASSO 5 Faça i = i + 1 PASSO 6 Faça = p (atualize ) PASSO 7 Saída (solução não encontrada após ITMAX iterações) FIM OBS. 7: Outros critérios de parada podem ser utilizados: • • • 49. Encontrar o zero de = com precisão , utilizando o método do ponto fixo. Resolução: Pode-se construir uma tabela de valores para ( ) e analisar os sinais: x −3 −2 −1 − + + Como , conclui-se, de acordo com o Teorema 1, que existem zeros de no intervalo [−3,−2]. Fazendo e , pode-se verificar que os gráficos das mesmas se intersectam em apenas um ponto, o que garante que só existe um zero de neste intervalo. )(' x1 x2− 2 1 − x 2 1 I I )(' x1 x I )( p 0p 0p =p )( p ip 0pp − p 0p 0p − −1nn pp − − n nn p pp 1 )( npf )(xf 42 +− xe x 610−= f x )(xf 023 −− )()( ff )(xf xexh =)( 42 −= xxg )( )(xf Cálculo Numérico Zeros reais de funções reais Maiko 2-25 Assim, o zero de está isolado em [−3,−2]. Procurando uma função de ponto fixo adequada pode-se fazer: =0 Verificando as hipóteses i) e ii) do Teorema 2 : i) são contínuas em [−3,−2], o que garante a primeira condição do Teorema 2 . ii) k = Como é decrescente no intervalo =[−3,−2], k = 0,03328 < 1, o que garante a segunda condição do Teorema 2 . Procura-se agora, o extremo do intervalo =[−3,−2] mais próximo do zero de : Para isto, segue-se o indicado na observação 5, isto é, calcula-se o ponto médio do intervalo =[−3,−2]: = = −2,5 e = = −2,02042. Como < , isto é =−2,5 < = = −2,02042, então está entre =−2,5 e −2, ou seja, −2 é o extremo de mais próximo de . Desta forma, iniciando o processo recursivo pelo ponto −2, garante-se que todos os termos da seqüência aproximadora pertencerão ao intervalo =[−3,−2]. y x x( ) 21 3 2 1 h x( )g -2 -1-3 -2 -3 -4 -1 3 4 5 = e x = x 2 - 4 )(xf 42 +− xe x 442 +−=+= xx exex 4+−= xex)( 42 + −= x x e e x)(' )(')( xex )('max ]2,3[ x x −− 42 + −= x x e e x . )(' 012370 42 3 3 3 , . )(' −= + −=− − − e e 033280 42 2 2 2 , . )(' −= + −=− − − e e )(' x I I )(xf I x̂ 2 23 ))(( −+− )ˆ(x 452 52 +−=− − ,),( e x̂ )ˆ(x x̂ )ˆ(x ),( 52− x̂ I =0x I Cálculo Numérico Zeros reais de funções reais Maiko 2-26 Logo, utilizando a partir de −2, gera-se uma seqüência convergente para o zero de . 0 −2 −2,0335524 0,0335524 > 10 -6 1 −2,0335524 −2,0324541 0,0010983 > 10-6 2 −2,0324541 −2,0324895 0,0000354 > 10-6 3 −2,0324895 −2,0324884 0,0000011> 10 -6 4 −2,0324884 −2,0324884 0 < 10-6 Portanto, = −2,0324884. 2.3.3 Método de Newton, Newton-Raphson (ou Método das Tangentes) Este método é uma particularidade do método das aproximações sucessivas. A idéia é construir uma função para a qual exista um intervalo contendo o zero , onde |𝜙′(𝑥)| < 1. Esta construção é feita impondo . Como deve ser uma função contínua, existe sempre uma vizinhança I de onde <1. Obtenção da função : A forma mais geral de equivalente a =0 é dada por: = + onde é uma função contínua tal que . Escolhe-se de forma que . Derivando-se a equação anterior, obtém-se =1+ . Calculando esta derivada no ponto , obtém-se: =1+ . Supondo que 𝑓′(𝛼) ≠ 0, para que , deve-se ter = . Assim, uma escolha satisfatória para será portanto: = , uma vez que . Substituindo na equação inicial, tem-se: = Assim, o processo iterativo de Newton é definido por: = , 0, 1, 2, OBS. 8: A é válida mesmo que = 0, uma vez que . Interpretação Geométrica do Método de Newton O valor é obtido traçando-se a tangente ao gráfico da função no ponto . A intersecção da reta tangente com o eixo das abscissas fornece a nova aproximação . Esta interpretação justifica o nome de método das tangentes. 4)( +−= xex =0x )(xf n nx 1+nx nn xx −+1 x )(x 0)(' = )(' x )('max x Ix )(x )(xx = )(xf x x =)()( xfxA )(x )(xA 0)( A )(xA 0)(' = )(' x )()(')(')( xfxAxfxA + )(' )(')( fA 0)(' = )(A )(' 1 − f )(xA )(xA )(' 1 xf − x )(xA )(x x )(' )( xf xf − 1+nx nx )(' )( n n xf xf − =n )(x )(' f nx 1+nx )(xf ))(,( nn xfx 1+nx Cálculo Numérico Zeros reais de funções reais Maiko 2-27 Convergência do Método de Newton Teorema 3 Seja , duas vezes diferenciável, com contínua. Suponha que: i) ii) iii) não troca de sinal em Então, a seqüência gerada pelas iterações do método de Newton-Raphson utilizando a função que equivale a converge para o único zero de , isolado em , se for escolhido convenientemente. OBS. 9: Para se escolher o ponto inicial , pode-se, por exemplo, fazer = se ou = caso contrário. Algoritmo do Método de Newton Para encontrar uma solução para =0, dada a derivada de e uma aproximação inicial . • Dados de Entrada: Aproximação inicial , precisão ou tolerância () e o número máximo de iterações (ITMAX). • Saída: Solução aproximada p ou mensagem de “solução não encontrada”. PASSO 1 Faça i =1 PASSO 2: Enquanto i ITMAX, execute os passos 3 – 6 PASSO 3 Faça (calcular ) PASSO 4 Se < então Saída (p) (procedimento efetuado com sucesso) FIM PASSO 5 Faça i = i + 1 y xx( ) 0x1x2x f nx x x( )f n+1 n 1+− == nn n n xx xf xf )( )('tg )(' )( n n nn xf xf xx −=+1 →baf ,: ( )xf " ( ) ( ) 0 bfaf ,)(' 0xf ],[ bax )('' xf ba, ( ) ( ) ( )xf xf xx ' −= ( ) ( )n n nn xf xf xx ' −=+1 f ba, bax ,0 0x 0x a ( ) baa , 0x b )(xf )(xf 0p 0p )('/)( 000 pfpfpp −= ip 0pp − Cálculo Numérico Zeros reais de funções reais Maiko 2-28 PASSO 6 Faça =p (atualize ) Passo 7: Saída (solução não encontrada após ITMAX iterações) FIM OBS. 10: Outros critérios de parada podem ser utilizados: • • • OBS. 11: O Método de Newton irá falhar se para algum n, = 0. 50. Encontrar a solução para a equação x = com precisão . Resolução: Pode-se construir uma tabela de valores para ( ) e analisar os sinais: x 0 + − Como , conclui-se, de acordo com o Teorema 1, que existem zeros de no intervalo [0, ]. Fazendo = x e = , pode-se verificar que os gráficos das mesmas se intersectam em apenas um ponto, o que garante que só existe um zero de neste intervalo. Esta informação também pode ser verificada observando que a função =−sen x – 1, preserva o sinal ]0, [, isto é, tem-se que neste caso ( )0, ]0, [ (e também em [0, ] ). Isto significa dizer que a função ( ) é estritamente decrescente no intervalo ]0, [. Como , também preserva o sinal em [0, ], ( ( )0, ]0, [, tem- se que as condições i), ii) e iii) do teorema 3 são satisfeitas. 0p 0p − −1nn pp − − n nn p pp 1 + )( 1npf )(' 1−npf xcos 610−= xxxfxxxx −==−= cos)(0coscos f x 2 )(xf 0 2 0 )()( ff )(xf 2 )(xg )(xh xcos )(xf )(' xf x 2 'f x x 2 2 f x 2 y x( ) h 2 2 2 3 =cos x x( )g = x -1 1 x xxf cos)('' −= 2 ''f x x 2 Cálculo Numérico Zeros reais de funções reais Maiko 2-29 Assim, a fórmula recursiva de Newton para este caso fica: = − para . Agora deve-se escolher convenientemente: Pode-se verificar que o ponto médio = ou =0,785398163398 e =0,739536133515. Pela observação 5 concluímos que =0, pois < . n 0 0 1 1 > 10-6 1 1 0,750363868 0,249636132 > 10-6 2 0,750363868 0,7391128909 0,011250978 > 10-6 3 0,7391128909 0,7390851333 0,000027757 > 10-6 4 0,7390851333 0, 7390851332 0,0000000001 <10-6 Portanto, = 0,739085133. 2.3.4 Método da Secante Uma grande desvantagem do método de Newton é a necessidade de se obter a derivada 𝑓′(𝑥) e calcular o seu valor numérico a cada iteração. Para contornar este problema podemos substituir o cálculo da primeira derivada 𝑓′(𝑥) pelo quociente das diferenças, usando assim, um modelo linear baseado nos dois valores calculados mais recentemente: 𝑓′(𝑥) = 𝑓(𝑥𝑛) − 𝑓(𝑥𝑛−1) 𝑥𝑛 − 𝑥𝑛−1 onde 𝑥𝑛 e 𝑥𝑛−1 são duas aproximações para a raiz. Substituindo o valor aproximado da derivada acima na fórmula e Newton, obtém-se: 𝑥𝑛+1 = 𝑥𝑛 − 𝑓(𝑥𝑛) 𝑓′(𝑥) 𝑥𝑛+1 = 𝑥𝑛 − 𝑓(𝑥𝑛) 𝑥𝑛 − 𝑥𝑛−1 𝑓(𝑥𝑛) − 𝑓(𝑥𝑛−1) Assim, o processo iterativo do Método da Secante é definido por: 𝑥𝑛+1 = 𝑥𝑛 − 𝑓(𝑥𝑛) ∙ (𝑥𝑛 − 𝑥𝑛−1) 𝑓(𝑥𝑛) − 𝑓(𝑥𝑛−1) ou 𝑥𝑛+1 = 𝑥𝑛−1𝑓(𝑥𝑛) − 𝑥𝑛𝑓(𝑥𝑛−1) 𝑓(𝑥𝑛) − 𝑓(𝑥𝑛−1) , com 𝑛 = 0, 1, 2, … Interpretação Geométrica do Método da Secante Os valores 𝑥0 e 𝑥1 são aproximações iniciais que determinam a reta pelos pontos (𝑥0, 𝑓(𝑥0)) e (𝑥1, 𝑓(𝑥1)). A intersecção da reta secante com o eixo das abscissas fornece a nova aproximação 𝑥2. Então, de dois valores 𝑥𝑛−1 e 𝑥𝑛 é determinada a reta pelos pontos (𝑥𝑛−1, 𝑓(𝑥𝑛−1)) e (𝑥𝑛, 𝑓(𝑥𝑛)). A intersecção desta reta com o eixo das abscissas fornece a aproximação 𝑥𝑛+1. 1+nx nx 1−− − )(sen )cos( n nn x xx 0n 0x x̂ 4 x̂ ( )x̂ 0x ( )x̂ x̂ nx 1+nx nn xx −+1 x Cálculo Numérico Zeros reais de funções reais Maiko 2-30 Para o desenho acima, tome 𝑥𝑛 = 𝑥1. Desta forma, 𝑥𝑛−1 = 𝑥0 e 𝑥𝑛+1 = 𝑥2. Assim, os dois triângulos abaixo são semelhantes e foram tirados da figura acima. Então, por semelhança de triângulos, temos: 𝑓(𝑥𝑛−1) 𝑓(𝑥𝑛) = 𝑥𝑛−1 − 𝑥𝑛+1 𝑥𝑛 − 𝑥𝑛+1 Isolando 𝑥𝑘+1, temos: 𝑓(𝑥𝑛−1) ∙ (𝑥𝑛 − 𝑥𝑛+1) = 𝑓(𝑥𝑛) ∙ (𝑥𝑛−1 − 𝑥𝑛+1) 𝑓(𝑥𝑛−1)𝑥𝑛 − 𝑓(𝑥𝑛−1)𝑥𝑛+1 = 𝑓(𝑥𝑛)𝑥𝑛−1 − 𝑓(𝑥𝑛)𝑥𝑛+1 𝑥𝑛+1 ∙ (𝑓(𝑥𝑛) − 𝑓(𝑥𝑛−1)) = 𝑥𝑛−1 ∙ 𝑓(𝑥𝑛) − 𝑥𝑛 ∙ 𝑓(𝑥𝑛−1) 𝑥𝑛+1 = 𝑥𝑛−1𝑓(𝑥𝑛) − 𝑥𝑛𝑓(𝑥𝑛−1) 𝑓(𝑥𝑛) − 𝑓(𝑥𝑛−1) Convergência do Método da Secante Como o método da secante é uma aproximação para o método de Newton, as condições de convergência são próximas. OBS. 12: O método da secante pode divergir se 𝑓(𝑥𝑘) ≅ 𝑓(𝑥𝑘−1). y x x( ) 0x 1x 2x f 3x 4x ( )f 1x ( )f 0x ( )f 2x ( )f 3x ( )f 4x L aur o Cesa r Ga lvã o n-1x ( )f nx ( )f n-1x n+1xn+1x nx L aur o Cesa r Ga lvã o Cálculo Numérico Zeros reais de funções reais Maiko 2-31 Algoritmo do Método da Secante Para encontrar uma solução para =0, dadas duas aproximações inicial 𝑝0 e 𝑝1. • Dados de Entrada: Aproximações inicial 𝑝0 e 𝑝1, precisão ou tolerância () e o número máximo de iterações (ITMAX). • Saída: Solução aproximada 𝑝 ou mensagem de “solução não encontrada”. PASSO 1 Faça i =1 PASSO 2:Enquanto i ITMAX, execute os passos 3 – 6 PASSO 3 Faça 𝑝 = 𝑝0𝑓(𝑝1)−𝑝1𝑓(𝑝0) 𝑓(𝑝1)−𝑓(𝑝0) (calcular 𝑝𝑖) PASSO 4 Se |𝑝 − 𝑝1| < então Saída (p) (procedimento efetuado com sucesso) FIM PASSO 5 Faça i = i + 1 PASSO 6 Faça 𝑝0 = 𝑝1 e 𝑝1 = 𝑝 (atualize 𝑝0 e 𝑝1) Passo 7: Saída (solução não encontrada após ITMAX iterações) FIM OBS. 13: Outros critérios de parada podem ser utilizados: • • • 51. Considerando o mesmo exercício anterior, encontrar a solução para a equação x = com precisão , usando o método da secante. Considere 𝑥0 = 0 e 𝑥1 = 1, como aproximações iniciais. Resolução: 𝑓(𝑥) = cos(𝑥) − 𝑥 = 0 Assim, a fórmula recursiva do método da secante para este caso fica: 𝑥𝑛+1 = 𝑥𝑛−1𝑓(𝑥𝑛) − 𝑥𝑛𝑓(𝑥𝑛−1) 𝑓(𝑥𝑛) − 𝑓(𝑥𝑛−1) n x(n-1) x(n) x(n+1) |x(n+1) - x(n)| 0 0 1 0,685073357 0,314926643 1 1 0,685073357 0,736298998 0,05122564 2 0,685073357 0,736298998 0,739119362 0,002820364 3 0,736298998 0,739119362 0,739085112 3,42498E-05 4 0,739119362 0,739085112 0,739085133 2,11E-08 Portanto, = 0,739085133. )(xf − −1nn pp − − n nn p pp 1 + )( 1npf xcos 610−= x Cálculo Numérico Zeros reais de funções reais Maiko 2-32 2.3.5 Comparação entre os métodos Nos exercícios seguintes, considerando cada método especificado, determine uma aproximação para o zero da função. 52. Pelo método da Bissecção, determine uma aproximação para (1,2) da função 𝑓(𝑥) = 𝑒−𝑥 2 − cos 𝑥 com aproximação = tal que ( − )/2 . Resolução: f ( a ) f ( x ) f (b ) (b − a )/2 1 1 1,5 2 - + + 0,5 2 1 1,25 1,5 - - + 0,25 3 1,25 1,375 1,5 - - + 0,125 4 1,375 1,4375 1,5 - - + 0,0625 5 1,4375 1,46875 1,5 - + + 0,03125 6 1,4375 1,453125 1,46875 - + + 0,015625 7 1,4375 1,4453125 1,453125 - - + 0,0078125 8 1,4453125 1,44921875 1,453125 - + + 0,00390625 9 1,4453125 1,447265625 1,44921875 - - + 0,001953125 10 1,447265625 1,448242188 1,44921875 - + + 0,000976563 11 1,447265625 1,447753906 1,448242188 - + + 0,000488281 12 1,447265625 1,447509766 1,447753906 - + + 0,000244141 13 1,447265625 1,447387695 1,447509766 - - + 0,00012207 14 1,447387695 1,44744873 1,447509766 - + + 6,10352E-05 Logo, =1,44744873 53. Pelo método do Ponto Fixo ou Aproximações Sucessivas, determine uma aproximação para �̅�(1,2) da função 𝑓(𝑥) = 𝑒−𝑥 2 − cos 𝑥 com aproximação 𝜀1 = 𝜀1 = 10 −4 tal que |𝑓(𝑥𝑛)| < 𝜀1 ou |𝑥𝑛+1 − 𝑥𝑛| < 𝜀2. Utilize 𝑥0=1,5. Resolução: ( )= − ( )=0 − + − =0 1( )=− + + ( )1 em (1,2) 2( )= − + ( )1 em (1,2) 𝜙(𝑥) = cos 𝑥 − 𝑒−𝑥 2 + 𝑥 𝑥𝑛+1 = 𝜙(𝑥𝑛) | − | | ( )| Parada 0 1,5 1,465337977 0,034662023 0,01154599 1 1,465337977 1,453791987 0,01154599 0,004075472 2 1,453791987 1,449716515 0,004075472 0,001466938 3 1,449716515 1,448249577 0,001466938 0,000531683 4 1,448249577 1,447717894 0,000531683 0,000193187 5 1,447717894 1,447524708 0,000193187 7,02578E-05 |𝑓(𝑥𝑛)| < 𝜀1 Logo, =1,447524708. x 1 410− b a 1 n a x b x f x 2xe− xcos f x 2xe− xcos x x x xcos 2xe− x '1 x x xcos 2xe− x '2 x n nx 1+nx 1+nx nx f 1+nx x Cálculo Numérico Zeros reais de funções reais Maiko 2-33 54. Pelo método de Newton-Raphson, determine uma aproximação para �̅�(1,2) da função 𝑓(𝑥) = 𝑒−𝑥 2 − cos 𝑥 com aproximação = = tal que | ( )| ou |𝑥𝑛+1 − 𝑥𝑛| < 𝜀2. Utilize 𝑥0=1,5. Resolução: ( )= − ( )=−2 + ( )= − ( )= − =( ) | − | | ( )| Parada 0 1,5 1,4491235 0,0508765 0,001088623 1 1,4491235 1,447416347 0,001707153 1,32044E-06 |𝑓(𝑥𝑛+1)| < 𝜀1 Logo, =1,447416347. 55. Pelo método da secante, determine uma aproximação para �̅�(1,2) da função 𝑓(𝑥) = 𝑒−𝑥 2 − cos 𝑥 com aproximação = = tal que | ( )| ou |𝑥𝑛+1 − 𝑥𝑛| < 𝜀2. Utilize 𝑥0 = 1,5 e 𝑥1 = 1,2, como aproximações iniciais. Resolução: 𝑥𝑛+1 = 𝑥𝑛−1𝑓(𝑥𝑛) − 𝑥𝑛𝑓(𝑥𝑛−1) 𝑓(𝑥𝑛) − 𝑓(𝑥𝑛−1) n x(n-1) x(n) x(n+1) |x(n+1) - x(n)| 0 1,5 1,2 1,435046063 0,235046063 1 1,2 1,435046063 1,450627163 0,0155811 2 1,435046063 1,450627163 1,447385539 0,003241624 3 1,450627163 1,447385539 1,447414206 2,86668E-05 Logo, =1,447414206. 1 2 410− f 1+nx 1 f x 2xe− xcos 'f x x 2xe− xsen x x )(' )( xf xf x x xxe xe x x sen cos +− − − − 2 2 2 1+nx nx n nx 1+nx 1+nx nx f 1+nx x 1 2 410− f 1+nx 1 x Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-34 3 Resolução de sistemas de equações lineares 3.1 Introdução Vários problemas, como cálculo de estruturas de redes elétricas e solução de equações diferenciais, recorrem a resolução numérica de um sistema linear de equações com incógnitas. 3.1.1 Forma Algébrica de Sn = ou = = , =1, 2, , . 3.1.2 Forma Matricial de Sn = = . Onde: • matriz dos coeficientes; • vetor das incógnitas (ou vetor solução); • vetor dos termos independentes. 3.1.3 Matriz Aumentada ou Matriz Completa do Sistema =[ ]= . 3.1.4 Solução do Sistema =( , , , ) . 3.1.5 Classificação de um Sistema Linear • COMPATÍVEL: apresenta soluções; • INCOMPATÍVEL: caso contrário. nS n n nS =+++ =+++ =+++ nnnnnn nn nn bxaxaxa bxaxaxa bxaxaxa 2211 22222121 11212111 nS = n j jij xa 1 ib i n A x b nnnn n n aaa aaa aaa 21 22221 11211 nx x x 2 1 nb b b 2 1 A x b B A b nnnnn n n baaa baaa baaa 21 222221 111211 x 1x 2x nx T Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-35 3.1.6 Classificação quanto ao Determinante de A • 0 (SPD) sistema linear possível e determinado (SOLUÇÃO ÚNICA); • =0 (SPI) ou (SI): a matriz é SINGULAR. (SPI) Sistema possível e indeterminado, (SI) Sistema impossível. OBS. 1: Se =0, =1, 2, , , isto é, se =0, o sistema é dito HOMOGÊNEO. Todo sistema homogêneo é compatível, pois admite sempre a solução =0. A solução é chamada TRIVIAL. 3.2 Métodos diretos São métodos que determinam a solução de um sistema linear com um número finito de operações. Definição: Dois sistemas lineares são equivalentes quando possuem a mesma solução. 3.2.1 Método de Eliminação de Gauss Com ( −1) passos, o sistema linear = é transformado num sistema triangular superior equivalente. Tome 0 como hipótese. = = , o que se resolve por substituição. [ ] [ ] . 56. Resolver o sistema , com = . Resolução: = [ ] [ ] [ ] = (Matriz aumentada). Seja =[ ] e =[ ] após conjuntos de operações elementares aplicadas sobre . • Etapa 1: em , tome , com =1,2,3, como as linhas de e como pivô e calculam-se os multiplicadores ( =2,3). = − = − = −2; = − = − = −1. Operações elementares nas linhas ( =1,2,3). Adet Adet A ib i n b x n A x b Adet A x b U x c A b U c nnnnn n n baaa baaa baaa 21 222221 111211 nnn n n cu cuu cuuu 00 0 2222 111211 3S 3S −=+− =−+ =−+ 132 3344 532 321 321 321 xxx xxx xxx 3S −=+− =−+ =−+ 132 3344 532 321 321 321 xxx xxx xxx A b U c A b −− − − 1132 3344 5132 0B A b kB U c k 0B 0B )(0 iL i 0B )(0 11a )(0 1im i )(0 21m )( )( 0 11 0 21 a a 2 4 )(0 31m )( )( 0 11 0 31 a a 2 2 )( 10+ iL i Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-36 ; + ; + . Sendo ( =1,2,3) as linhas da matriz . Anulam-se todos os valores abaixo do pivô . = . • Etapa 2: Repete-se o processo para o próximo pivô, situado na diagonal da matriz . Em , tome , com =2,3 e como pivô. = − = − = −3. ; ; + . = =[ ]. Segue que: Resolvendo = por substituição retroativa, tem-se: = = que é, também, solução para o sistema = . • Método compacto para a TRIANGULAÇÃO = : Linha Multiplicador m Matriz Aumentada Transformação (1) 2 3 -1 5 (2) = -( 4 )/( 2 )= -2 4 4 -3 3 (3) = -( 2 )/( 2 )= -1 2 -3 1 -1 (2) 0 -2 -1 -7 -2 + (3) = -( -6 )/( -2 )= -3 0 -6 2 -6 -1 + (3) 0 0 5 15 -3 + As linhas contendo os pivôs formam o sistema = . )(1 1L )(0 1L )(1 2L )(0 21m )(0 1L )(0 2L )(1 3L )(0 31m )(0 1L )(0 3L )(1 iL i 1B )(0 11a 1B −− −−− − 6260 7120 5132 1B 1B )(1 iL i )(1 22a )(1 32m )( )( 1 22 1 32 a a 2 6 − − )(2 1L )(1 1L )(2 2L )(1 2L )(2 3L )(1 32m )(1 2L )(1 3L 2B −−− − 15500 7120 5132 2B U c U x c x T321 3 2 1 A x b U x c 0B )(0 21m )(0 31m 1B )(0 1L )(0 2L )(1 32m )(0 1L )(0 3L 2B )(1 2L )(1 3L U x c Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-37 57. Resolver o sistema com arredondamento em duas casas decimais, na matriz aumentada. = Resolução: Linha Multiplicador m Matriz Aumentada (1) 8,70 3,00 9,30 11,00 16,40 (2) = -( 24,50 )/( 8,70 ) 24,50 -8,80 11,50 -45,10 -49,70 (3) = -( 52,30 )/( 8,70 ) 52,30 -84,00 -23,50 11,40 -80,80 (4) = -( 21,00 )/( 8,70 ) 21,00 -81,00 -13,20 21,50 -106,30 (2) 0,00 -17,25 -14,69 -76,08 -95,88 (3) = -( -102,03 )/( -17,25 ) 0,00 -102,03 -79,41 -54,73 -179,39 (4) = -( -88,24 )/( -17,25 ) 0,00 -88,24 -35,65 -5,05 -145,89 (3) 0,00 0,00 7,48 395,27 387,72 (4) = -( 39,49 )/( 7,48 ) 0,00 0,00 39,49 384,13 344,57 (4) 0,00 0,00 0,00 -1702,66 -1702,36 Então = = [ ] [ ]. = Logo: = . Cálculo do Resíduo Uma medida para avaliar a precisão dos cálculos é o resíduo, que é dado por: = − . 58. Com base no exercício anterior, calcular o resíduo do sistema = . Resolução: = − . = − . = . 4S 4S A x b −=+−− −=+−− −=−+− =+++ 3106521213081021 880411523084352 74914551188524 416011390378 4321 4321 4321 4321 ,,,,, ,,,,, ,,,,, ,,,,, xxxx xxxx xxxx xxxx 0B )(0 21m )(0 31m )(0 41m 1B )(1 32m )(1 42m 2B )(2 43m 3B A x b U x c A b U c U x c −=− =++ −=−−− =+++ 361702661702000 723872739548700 88950876691425170 416011390378 4 43 432 4321 ,, ,,, ,,,, ,,,,, x xx xxx xxxx x T001011012011 ,,,, − r b xA r A x b r b xA r − − − 3106 880 749 416 , , , , −− −− −− 521213081021 411523084352 14551188524 011390378 ,,,, ,,,, ,,,, ,,,, − 001 011 012 011 , , , , r T4680082004200240 ,,,, −− Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-38 Algoritmo de Eliminação de Gauss Seja o sistema = , com , e . Sempre supor que 0 na etapa . TRIANGULARIZAÇÃO: = = . Para =1, 2, , ( −1) Para =( +1), , = =0 Para =( +1), , = − = − FIM FIM FIM RESOLUÇÃO DO SISTEMA = . = Para =( −1), , 2, 1 =0 Para =( +1), , = + FIM = FIM 3.2.2 Estratégia de Pivoteamento Completo No momento de se calcular o multiplicador , se o pivô estiver próximo de zero, o método pode ampliar os erros de arredondamento. Para se contornar estes problemas, escolhe- se como pivô , com , =1, 2, , . Dado = , tome =[ ]. = . Seja = , ( , =1, 2, , ) o pivô da linha . Então, calcula-se o multiplicador = − , em cada linha, com =1, 2, , . Assim, anulam-se os elementos da coluna através da operação: A x b nnA 1nx 1nb kka k A x b U x c k n i k n m kk ik a a ika j k n ija ija m kja ib ib m kb U x c nx nn n a b k n s j k n s s kja jx kx kk k a sb − ikm ijaMAX i j n A x b B A b B nnnnqnn ppnpqpp nq nq baaaa baaaa baaaa baaaa 21 21 2222221 1111211 pqa ijaMAX i j n p )(0 iqm )( )( 0 0 pq iq a a i p i n ija q Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-39 + . Eliminando-se a linha pivotal , repete-se o processo até que se obtenha com conjuntos de operações elementares aplicadas sobre , onde =1, 2, , ( −1). 59. Resolva com arredondamento em duas casas decimais, utilizando eliminação de Gauss com pivoteamento completo. = . Resolução: Linha Multiplicador m Matriz Aumentada (1) = -( 3,00 )/( -84,00 ) 8,70 3,00 9,30 11,00 16,40 (2) = -( -8,80 )/( -84,00 ) 24,50 -8,80 11,50 -45,10 -49,70 (3) 52,30 -84,00 -23,50 11,40 -80,80 (4) = -( -81,00 )/( -84,00 ) 21,00 -81,00 -13,20 21,50 -106,30 (1) = -( 11,41 )/( -46,29 ) 10,57 0,00 8,46 11,41 13,51 (2) 19,02 0,00 13,96 -46,29 -41,24 (4) = -( 10,51 )/( -46,29 ) -29,43 0,00 9,46 10,51 -28,39 (1) = -( 15,26 )/( -25,11 ) 15,26 0,00 11,90 0,00 3,34 (4) -25,11 0,00 12,63 0,00 -37,75 (1) 0,00 0,00 19,58 0,00 -19,60 Então = = [ ] [ ]. = Com o cálculo retroativo de para , obtém-se: = . Considerando-se precisão em duas casas decimais, o processo levou ao exato, em conseqüência o resíduo é nulo. = − = . )(1 iL )(0 iqm )(0 pL )(0 iL p )(k iL k B k n 4S 4S A x b −=+−− −=+−− −=−+− =+++ 3106521213081021 880411523084352 74914551188524 416011390378 4321 4321 4321 4321 ,,,,, ,,,,, ,,,,, ,,,,, xxxx xxxx xxxx xxxx )(0 12m )(0 22m 0B )(0 42m )(1 14m 1B )(1 44m )(2 11m 2B 3B A x b U x c A b U c U x c 3 2 1 0 B B B B −=+++ −=+++− −=−++ −=+−− 60190581900 75370631201125 24412946961300219 880411523084352 3 31 431 4321 ,, ,,, ,,,, ,,,,, x xx xxx xxxx 3B 0B x T 001001002001 ,,,, − x r b xA r T000000000000 ,,,, Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-40 3.2.3 Fatoração LU “Toda matriz não singular admite uma decomposição em duas matrizes triangulares, uma superior e outra inferior”. Quem garante esse resultado é o teorema abaixo. Teorema de Gauss Seja A uma matriz quadrada de ordem n tal que det A ≠ 0. Sejam U uma matriz triangular superior, 𝑈 = { 𝑢𝑖𝑗 , se 𝑖 ≤ 𝑗 0, se 𝑖 > 𝑗 e L uma matriz triangular inferior com diagonal unitária, 𝐿 = { 0, se 𝑖 < 𝑗 1, 𝑠𝑒 𝑖 = 𝑗 𝑙𝑖𝑗, se 𝑖 > 𝑗 Então existe e é única a decomposição A = LU, onde U é a matriz resultante do processo de eliminação gaussiana e 𝑙𝑖𝑗 = 𝑚𝑖𝑗, (multiplicadores de linhas, sem troca de sinal). Apresentamos como exemplo: 𝐴 = ( 2 1 1 4 4 3 6 7 4 ) = ( 1 0 0 2 1 0 3 2 1 ) ⏟ L ( 2 1 1 0 2 1 0 0 −1 ) ⏟ U A base do método de Decomposição LU, também conhecido como método Fatoração, consiste na resolução de sistemas triangulares. Seja o sistema linear Ax = b Supor que seja possível fatorar a matriz A dos coeficientes: A = LU Nestas condições, o sistema Ax = b pode ser reescrito na forma LUx = b, o que permite o desmembramento em dois sistemas triangulares: Ly = b e Ux = y Resolvendo o primeiro sistema, calculamos y que, usado no segundo sistema, fornecerá o vetor procurado x. Dessa maneira, conhecidas L e U, o sistema será resolvido com 2n2 operações (dois sistemas triangulares), o que representa um ganho substancial comparado com as 2𝑛3 3 operações do método da eliminação de Gauss. Cálculo dos Fatores L e U: Os fatores L e U podem ser obtidos através de fórmulas para os elementos 𝑙𝑖𝑗 e 𝑢𝑖𝑗, ou então, podem ser construídos usando a ideia básica do método da Eliminação de Gauss. Veremos a seguir, através de um exemplo, como obter L e U através do processo de Gauss. 60. Decompor a matriz A, usando a DecomposiçãoLU. A = ( 1 2 −1 2 3 −2 1 −2 1 ) Calculando o 𝑚𝑖𝑗 e 𝑢𝑖𝑗, usando o processo de Gauss (𝑚𝑖𝑗 sem troca de sinal), temos: Resolução: Para a Coluna 1 da matriz A(0): A=A (0) = ( 1 2 −1 2 3 −2 1 −2 1 ) Pivô = 𝑎11 (0) = 1 Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-41 Multiplicadores: 𝑚21 (0) = 𝑎21 (0) 𝑎11 (0) = 2 1 = 2 𝑚31 (0) = 𝑎31 (0) 𝑎11 (0) = 1 1 = 1 Então: 𝐿1 (1) ← 𝐿1 (0) ; 𝐿2 (1) ← −𝑚21 (0) ∗ 𝐿1 (0) + 𝐿2 (0) 𝐿3 (1) ← −𝑚31 (0) ∗ 𝐿1 (0) + 𝐿3 (0) A (1) = ( 1 2 −1 0 −1 0 0 −4 2 ) Para a Coluna 2 da matriz A(1): Pivô = 𝑎22 = −1 Multiplicadores: 𝑚32 (1) = 𝑎32 (1) 𝑎22 (1) = −4 −1 = 4 Então: 𝐿1 (2) ← 𝐿1 (1) ; 𝐿2 (2) ← 𝐿2 (1) 𝐿3 (2) ← −𝑚32 (1) ∗ 𝐿2 (1) + 𝐿3 (1) A(2) = ( 1 2 −1 0 −1 0 0 0 2 ) Os fatores L e U são: 𝐿 = ( 1 0 0 𝑚21 1 0 𝑚31 𝑚32 1 )= ( 1 0 0 2 1 0 1 4 1 ) e 𝑈 = ( 1 2 −1 0 −1 0 0 0 2 ) Logo: A = 𝐿 ∗ 𝑈 = ( 1 0 0 2 1 0 1 4 1 ) ∗ ( 1 2 −1 0 −1 0 0 0 2 ) = ( 1 2 −1 2 3 −2 1 −2 1 ) Vamos aproveitar o Exercício acima para resolver um sistema de equações lineares através da Decomposição LU. 61. Resolva o sistema linear a seguir usando a Decomposição LU (Fatoração). { 𝑥1 + 2𝑥2 − 𝑥3 = 2 2𝑥1 + 3𝑥2 − 2𝑥3 = 3 𝑥1 − 2𝑥2 + 𝑥3 = 0 Resolução: Já temos que: A = ( 1 2 −1 2 3 −2 1 −2 1 ) = ( 1 0 0 2 1 0 1 4 1 ) ∗ ( 1 2 −1 0 −1 0 0 0 2 ) = 𝐿𝑈 Para resolvermos o sistema Ax = b, onde b = (2 3 0)𝑡, resolvemos primeiramente Ly=b. ( 1 0 0 2 1 0 1 4 1 ) ∗ ( 𝑦1 𝑦2 𝑦3 ) = ( 2 3 0 ) , ou seja, { 𝑦1 = 2 2𝑦1 + 𝑦2 = 3 𝑦1 + 4𝑦2 + 𝑦3 = 0 Então ( 𝑦1 𝑦2 𝑦3 ) = ( 2 −1 2 ). A seguir calculamos x através da equação Ux = y. ( 1 2 −1 0 −1 0 0 0 2 ) ∗ ( 𝑥1 𝑥2 𝑥3 ) = ( 2 −1 2 ), ou seja, { 𝑥1 + 2𝑥2 − 𝑥3 = 2 −𝑥2 = −1 2𝑥3 = 2 Logo, 𝑥 = ( 𝑥1 𝑥2 𝑥3 ) = ( 1 1 1 ). Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-42 62. Resolva o sistema linear a seguir usando a fatoração LU: { 3𝑥1 + 2𝑥2 + 4𝑥3 = −1 𝑥1 + 𝑥2 + 2𝑥3 = 10 4𝑥1 + 3𝑥2 + 2𝑥3 = 5 Resolução: A = ( 3 2 4 1 1 2 4 3 2 ) e 𝑏 = ( −1 10 5 ) Usando o processo de Gauss para triangular A, tem-se: 1ª coluna Multiplicadores: 𝑚21 (0) = 𝑎21 (0) 𝑎11 (0) = 1 3 e 𝑚31 (0) = 𝑎31 (0) 𝑎11 (0) = 4 3 Aplicando os multiplicadores, obtém-se a matriz A(1): 𝐴(1) = ( 3 2 4 0 1/3 2/3 0 1/3 −10/3 ) 𝐿1 → 𝐿1 𝐿2 → −𝑚21 ∗ 𝐿1 + 𝐿2 𝐿3 → −𝑚31 ∗ 𝐿1 + 𝐿3 2ª coluna Multiplicador: 𝑚32 (1) = 𝑎32 (1) 𝑎22 (1) = 1 Aplicando o multiplicado, obtém-se a matriz A(2): A(2) = ( 3 2 4 0 1/3 2/3 0 0 −4 ) 𝐿1 → 𝐿1 𝐿2 → 𝐿2 𝐿3 → −𝑚32 ∗ 𝐿2 + 𝐿3 Os fatores L e U são: 𝐿 = ( 1 0 0 1/3 1 0 4/3 1 1 ) e 𝑈 = ( 3 2 4 0 1/3 2/3 0 0 −4 ) Resolvendo o sistema L(Ux)=b, tem-se: 𝐿𝑦 = 𝑏 → { 𝑦1 = −1 𝑦1 3 + 𝑦2 = 10 4𝑦1 3 + 𝑦2 + 𝑦3 = 5 𝑦 = ( −1 31/3 −4 ) 𝑈𝑥 = 𝑦 → { 3𝑥1 + 2𝑥2 + 4𝑥3 = −1 𝑥2 3 + 2𝑥3 3 = 31 3 −4𝑥3 = −4 𝑥 = ( −21 29 1 ) 63. Resolva o sistema linear a seguir usando a fatoração LU: { 3𝑥 − 0,1𝑦 − 0,2𝑧 = −1,2 0,1𝑥 + 7𝑦 − 0,3𝑧 = 7,8 0,3𝑥 − 0,2𝑦 + 10𝑧 = 3,5 Resolução: A = ( 3 −0,1 −0,2 0,1 7 −0,3 0,3 −0,2 10 ) e 𝑏 = ( −1,2 7,8 3,5 ) Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-43 Usando o processo de Gauss para triangular A, tem-se: 1ª coluna Multiplicadores: 𝑚21 = 𝑎21 (0) 𝑎11 (0) = 0,0333 e 𝑚31 = 𝑎31 (0) 𝑎11 (0) = 0,1 Aplicando os multiplicadores, obtém-se a matriz A(1): A(1) = ( 3 −0,1 −0,2 0 7,0033 −0,2933 0 −0,19 10,02 ) 𝐿1 → 𝐿1 𝐿2 → −𝑚21 ∗ 𝐿1 + 𝐿2 𝐿3 → −𝑚31 ∗ 𝐿1 + 𝐿3 2ª coluna Multiplicador: 𝑚32 = 𝑎32 (1) 𝑎22 (1) = −0,0271 Aplicando o multiplicado, obtém-se a matriz A(2): A(2) = ( 3 −0,1 −0,2 0 7,0033 −0,2933 0 0 10,0120 ) 𝐿1 → 𝐿1 𝐿2 → 𝐿2 𝐿3 → −𝑚32 ∗ 𝐿2 + 𝐿3 Os fatores L e U são: 𝐿 = ( 1 0 0 0,0333 1 0 0,1 −0,0271 1 ) e 𝑈 = ( 3 −0,1 −0,2 0 7,0033 −0,2933 0 0 10,0120 ) Resolvendo o sistema L(Ux)=b, tem-se: 𝐿𝑦 = 𝑏 → { 𝑦1 = −1,2 0,0333𝑦1 + 𝑦2 = 7,8 0,1𝑦1 − 0,0271𝑦2 + 𝑦3 = 3,5 𝑦 = ( −1,2 7,84 3,8327 ) 𝑈𝑥 = 𝑦 → { 3𝑥1 − 0,1𝑥2 − 0,2𝑥3 = −1,2 7,0033𝑥2 − 0,2933𝑥3 = 7,84 10,0120𝑥3 = 3,8327 𝑥 = ( −0,3366 1,1355 0,3828 ) 64. Considere a matriz. A = ( 1 1 1 2 1 −1 3 2 5 ) a) Calcule a fatoração LU de A. b) Usando a fatoração LU, calcule o determinante de A. Resolução: a) Usando o processo de Gauss para triangular A, tem-se: 1ª coluna Multiplicadores: 𝑚21 = 𝑎21 (0) 𝑎11 (0) = 2 e 𝑚31 = 𝑎31 (0) 𝑎11 (0) = 3 Aplicando os multiplicadores, obtém-se a matriz A(1): Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-44 A(1) = ( 1 1 1 0 −1 −3 0 −1 2 ) 𝐿1 → 𝐿1 𝐿2 → −𝑚21 ∗ 𝐿1 + 𝐿2 𝐿3 → −𝑚31 ∗ 𝐿1 + 𝐿3 2ª coluna Multiplicador: 𝑚32 = 𝑎32 (1) 𝑎22 (1) = 1 Aplicando o multiplicado, obtém-se a matriz A(2): A(2) = ( 1 1 1 0 −1 −3 0 0 5 ) 𝐿1 → 𝐿1 𝐿2 → 𝐿2 𝐿3 → −𝑚32 ∗ 𝐿2 + 𝐿3 Os fatores L e U são: 𝐿 = ( 1 0 0 2 1 0 3 1 1 ) e 𝑈 = ( 1 1 1 0 −1 −3 0 0 5 ) b) Sabe-se que A = LU então: det(A) = det(𝐿𝑈) det(A) = det(𝐿) ∗ det(𝑈) det(A) = (1 ∙ 1 ∙ 1) ∗ (1 ∙ (−1) ∙ 5) det(𝐴) = −5 65. Aplicando-se o método da decomposição LU a matriz: A = ( ? 4 ? −1 3 ? 10 8 ? −3 12 11 0 −2 −5 10 ) Obtiveram-se as matrizes: 𝐿 = ( ? 2 0 ? ? ? ? ? 3 0 0 ? ? 1 0 ? ) e 𝑈 = ( ? ? −1 1 ? 5 ? −2 ? 0 3 −4 0 ? 0 10 ) Preencha os espaços pontilhados com valores adequados. Resolução: Iniciamos completando a matriz L com os elementos da diagonal principal, que são igual a 1, e com os elementos acima da diagonal principal, que são nulos. 𝐿 = ( 1 2 0 1 0 0 0 0 3 0 0 ? 1 1 0 1 ) Também podemos completar alguns elementos da matriz U, abaixo da diagonal principal, que são nulos. 𝑈 = ( ? 0 −1 1 ? 5 ? −2 0 0 3 −4 0 0 0 10 ) Com o multiplicador 𝑚21 = 𝑎21 (0) 𝑎11 (0), podemos calcular os elementos 𝑎11: 𝑚21 = 𝑎21 (0) 𝑎11 (0) Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-45 2 = 4 𝑎11 (0) 𝑎11 (0) = 2 Comparando a primeira linha das matrizes A e U, completamos a primeira linha dessas matrizes: A = ( 2 4 −1 −1 3 10 5 8 ? 0 −3 −2 12 −5 11 10 ) 𝑈 = ( 2 0 −1 1 3 5 ? −2 0 0 3 −4 0 0 0 10 ) Com o multiplicador 𝑚31 = 𝑎31 (0) 𝑎11 (0), podemos calcular os elementos 𝑎31: 𝑚31 = 𝑎31 (0) 𝑎11 (0) 3 = 𝑎31 (0) 2 𝑎31 (0) = 6 Assim, temos: A = ( 2 4 −1 −1 3 10 5 8 6 0 −3 −2 12 −5 11 10 ) Com os dados obtidos da matriz A podemos calcular o elemento 𝑎23 (1) : 𝑎23 (1) = 𝑎23 (0) −𝑚21 ∗ 𝑎13 (0) 𝑎23 (1) = 10 − 2 ∗ 3 𝑎23 (1) = 4 Assim, temos: 𝑈 = ( 2 0 −1 1 3 5 4 −2 0 0 3 −4 0 0 0 10 ) Usando o processo de Gauss para triangular A, tem-se: A(1) = ( 2 0 −1 1 3 4 5 −2 0 0 0 −2 3 −5 −4 10 ) Com os dados dessa matriz podemos calcular o multiplicador 𝑚42: 𝑚42 = 𝑎42 (1) 𝑎22 (1) = −2 Assim, temos: 𝐿 = ( 1 2 0 1 0 0 0 0 3 0 0 −2 1 1 0 1 ) Cálculo Numérico Resolução de sistemas de equações lineares Maiko 3-46 3.2.4 Refinamento de Soluções Seja a solução aproximada para = . Obtém-se a solução melhorada aplicando-se a correção em . = + Se = , então ( + )= + = = − = . Assim, vem de [ ]. Obtido o , calcula-se = + . Repete-se
Compartilhar