·
Engenharia de Alimentos ·
Outros
Send your question to AI and receive an answer instantly
Preview text
Método da Bissecção Cálculo Numérico Profa Dra Ana Paula Mazzini Lima anamazziniifspedubr Engenharia de Alimentos Engenharia de Energias Renováveis Baseado nos livros Análise Numérica de R L Burden e J D Faires Cálculo Numérico de Neide B Franco e nas notas de aula de Marina Andretta Franklina Toledo 3 de agosto de 2022 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 1 20 Sumário 1 Determinação de raízes de funções 2 Método da Bissecção 3 Algoritmo 4 Exemplo 5 Convergência Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 2 20 Determinação de raízes de funções Vamos agora nos concentrar em resolver um dos problemas mais importantes de aproximação numérica a determinação de raízes de funções Este problema consiste em encontrar uma raiz ou uma solução de uma equação da forma fx 0 para uma dada função f R R Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 3 20 Determinação de raízes de funções O problema de determinação de raízes de funções data de pelo menos 1700 aC Uma tábua babilônica que data deste período fornece um número em base 60 equivalente a 1414222 como aproximação de 2 um resultado com precisão 105 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 4 20 Método da Bissecção O primeiro método que veremos para resolução deste problema baseado no Teorema do Valor Intermediário é o Método da Bissecção Suponha que f seja uma função contínua definida no intervalo a b com fa e fb com sinais opostos Pelo Teorema do Valor Intermediário existe um ponto p a b tal que fp 0 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 5 20 Método da Bissecção 1425 Localização gráfica de raízes Teorema 31 Franco Se uma função contínua fx assume valores de sinais opostos nos pontos extremos do intervalo ab isto é se fafb 0 então existe ao menos um ponto x ab tal que fx 0 a fa b fb x Figura Fonte aula prof Alysson Costa Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 6 20 Método da Bissecção Ideia 1453 Idéia da bisseção 175451 655 05 09 1 64 43855 fx 3 2 1 0 1 2 3 x f15 ou Figura Fonte aula prof Alysson Costa Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 7 20 Método da Bissecção O Método da Bissecção consiste em dividir os subintervalos de a b ao meio sucessivas vezes localizando o subintervalo que contém p Inicialmente defina a1 a b1 b e considere p1 o ponto médio do intervalo a b ou seja p1 a1 b1 a1 2 a1 b1 2 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 8 20 Método da Bissecção Se fp1 0 então p p1 e resolvemos o problema Se fp1 0 então fp1 tem o mesmo sinal de fa1 ou de fb1 Quando fp1 tem o mesmo sinal de fa1 temos que p p1 b1 e definimos a2 p1 e b2 b1 Quando fp1 tem o mesmo sinal de fb1 temos que p a1 p1 e definimos a2 a1 e b2 p1 Depois de redefinido o intervalo executamos o mesmo procedimento ao intervalo a2 b2 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 9 20 Algoritmo Método da Bissecção dados os extremos de um intervalo a b tais que fafb 0 uma tolerância TOL 0 e o número máximo de iterações MAXIT devolve a solução aproximada p ou uma mensagem de erro Passo 1 Faça k 1 Passo 2 Enquanto k MAXIT execute os passos 3 a 6 Passo 3 Faça p a b2 Passo 4 Se b a2 TOL ou fp TOL então devolva p como solução e pare Passo 5 Se fa fp 0 então faça a p Senão faça b p Passo 6 Faça k k 1 Passo 7 Escreva o método falhou após MAXIT iterações e pare Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 10 20 Método da Bissecção Note que para aplicarmos o Método da Bissecção precisamos de um intervalo a b com fafb 0 A cada iteração o tamanho do intervalo é dividido por dois Assim quanto menor o tamanho do intervalo a b que contém p mais rápida deverá ser a convergência do método Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 11 20 Exemplo Por exemplo para a função fx 2x3 x2 x 1 temos que f4f4 149 115 0 e f0f1 1 1 0 Assim poderíamos aplicar o Método da Bissecção usando o intervalo 4 4 ou o intervalo 0 1 No entanto a escolha do intervalo 0 1 reduz em três o número de iterações necessárias para se calcular p com uma determinada precisão Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 12 20 Exemplo Considere a função fx x3 4x2 10 Como f1 5 e f2 14 sabemos que há alguma raiz de f no intervalo 1 2 A tabela a seguir mostra os valores obtidos na aplicação do Método da Bissecção para encontrar uma raiz de f no intervalo 1 2 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 13 20 Exemplo k ak bk pk fpk 1 1000000000 2000000000 1500000000 2375000 2 1000000000 1500000000 1250000000 1796870 3 1250000000 1500000000 1375000000 0162110 4 1250000000 1375000000 1312500000 0848390 5 1312500000 1375000000 1343750000 0350980 6 1343750000 1375000000 1359375000 0096410 7 1359375000 1375000000 1367187500 0032360 8 1359375000 1367187500 1363281250 0032150 9 1363281250 1367187500 1365234375 0000072 10 1363281250 1365234375 1364257813 0016050 11 1364257813 1365234375 1364746094 0007990 12 1364746094 1365234375 1364990235 0003960 13 1364990235 1365234375 1365112305 0001940 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 14 20 Exemplo Após 13 iterações p13 1365112305 se aproxima de uma raiz p com erro p p13 b14 a14 1365234375 1365112305 0000122070 Como a14 p p p13 p b14 a14 a14 9 105 o que significa que a aproximação está correta em pelo menos 4 dígitos significativos Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 15 20 Exemplo O valor correto de p com nove casas decimais é p 1365230013 Note que p9 está mais próximo de p do que p13 Uma evidência deste fato é que fp9 fp13 Mas esta evidência pode ser enganosa e só é possível fazer esta constatação sabendo qual o verdadeiro valor de p Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 16 20 Método da Bissecção O Método da Bissecção tem a propriedade de sempre convergir para uma solução além de ter a vantagem de ser muito claro e simples de ser implementado Entretanto o Método da Bissecção tem a convergência muito lenta e uma aproximação intermediária boa pode ser descartada inadvertidamente Por estas razões o Método da Bissecção é muito usado no início da aplicação de outros métodos mais eficientes que veremos mais adiante Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 17 20 Convergência Teorema 1 Suponha que f Ca b e fafb 0 O Método da Bissecção gera uma sequência pk k1 que se aproxima de uma raiz p de f com pk p b a 2k para k 1 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 18 20 Método da Bissecgao Como ba Pk pl oR a sequéncia px 72 Converge para p com uma taxa de convergéncia O sr ou seja 1 Método da Bissecção O Teorema 1 fornece um limitante para o erro da aproximação obtida em cada iteração mas este limitante pode ser muito conservador No exemplo anterior o limitante garante apenas que p p9 2 1 29 2 103 No entanto o erro real é p p9 1365230013 1365234375 44 106 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 20 20
Send your question to AI and receive an answer instantly
Preview text
Método da Bissecção Cálculo Numérico Profa Dra Ana Paula Mazzini Lima anamazziniifspedubr Engenharia de Alimentos Engenharia de Energias Renováveis Baseado nos livros Análise Numérica de R L Burden e J D Faires Cálculo Numérico de Neide B Franco e nas notas de aula de Marina Andretta Franklina Toledo 3 de agosto de 2022 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 1 20 Sumário 1 Determinação de raízes de funções 2 Método da Bissecção 3 Algoritmo 4 Exemplo 5 Convergência Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 2 20 Determinação de raízes de funções Vamos agora nos concentrar em resolver um dos problemas mais importantes de aproximação numérica a determinação de raízes de funções Este problema consiste em encontrar uma raiz ou uma solução de uma equação da forma fx 0 para uma dada função f R R Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 3 20 Determinação de raízes de funções O problema de determinação de raízes de funções data de pelo menos 1700 aC Uma tábua babilônica que data deste período fornece um número em base 60 equivalente a 1414222 como aproximação de 2 um resultado com precisão 105 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 4 20 Método da Bissecção O primeiro método que veremos para resolução deste problema baseado no Teorema do Valor Intermediário é o Método da Bissecção Suponha que f seja uma função contínua definida no intervalo a b com fa e fb com sinais opostos Pelo Teorema do Valor Intermediário existe um ponto p a b tal que fp 0 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 5 20 Método da Bissecção 1425 Localização gráfica de raízes Teorema 31 Franco Se uma função contínua fx assume valores de sinais opostos nos pontos extremos do intervalo ab isto é se fafb 0 então existe ao menos um ponto x ab tal que fx 0 a fa b fb x Figura Fonte aula prof Alysson Costa Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 6 20 Método da Bissecção Ideia 1453 Idéia da bisseção 175451 655 05 09 1 64 43855 fx 3 2 1 0 1 2 3 x f15 ou Figura Fonte aula prof Alysson Costa Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 7 20 Método da Bissecção O Método da Bissecção consiste em dividir os subintervalos de a b ao meio sucessivas vezes localizando o subintervalo que contém p Inicialmente defina a1 a b1 b e considere p1 o ponto médio do intervalo a b ou seja p1 a1 b1 a1 2 a1 b1 2 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 8 20 Método da Bissecção Se fp1 0 então p p1 e resolvemos o problema Se fp1 0 então fp1 tem o mesmo sinal de fa1 ou de fb1 Quando fp1 tem o mesmo sinal de fa1 temos que p p1 b1 e definimos a2 p1 e b2 b1 Quando fp1 tem o mesmo sinal de fb1 temos que p a1 p1 e definimos a2 a1 e b2 p1 Depois de redefinido o intervalo executamos o mesmo procedimento ao intervalo a2 b2 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 9 20 Algoritmo Método da Bissecção dados os extremos de um intervalo a b tais que fafb 0 uma tolerância TOL 0 e o número máximo de iterações MAXIT devolve a solução aproximada p ou uma mensagem de erro Passo 1 Faça k 1 Passo 2 Enquanto k MAXIT execute os passos 3 a 6 Passo 3 Faça p a b2 Passo 4 Se b a2 TOL ou fp TOL então devolva p como solução e pare Passo 5 Se fa fp 0 então faça a p Senão faça b p Passo 6 Faça k k 1 Passo 7 Escreva o método falhou após MAXIT iterações e pare Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 10 20 Método da Bissecção Note que para aplicarmos o Método da Bissecção precisamos de um intervalo a b com fafb 0 A cada iteração o tamanho do intervalo é dividido por dois Assim quanto menor o tamanho do intervalo a b que contém p mais rápida deverá ser a convergência do método Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 11 20 Exemplo Por exemplo para a função fx 2x3 x2 x 1 temos que f4f4 149 115 0 e f0f1 1 1 0 Assim poderíamos aplicar o Método da Bissecção usando o intervalo 4 4 ou o intervalo 0 1 No entanto a escolha do intervalo 0 1 reduz em três o número de iterações necessárias para se calcular p com uma determinada precisão Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 12 20 Exemplo Considere a função fx x3 4x2 10 Como f1 5 e f2 14 sabemos que há alguma raiz de f no intervalo 1 2 A tabela a seguir mostra os valores obtidos na aplicação do Método da Bissecção para encontrar uma raiz de f no intervalo 1 2 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 13 20 Exemplo k ak bk pk fpk 1 1000000000 2000000000 1500000000 2375000 2 1000000000 1500000000 1250000000 1796870 3 1250000000 1500000000 1375000000 0162110 4 1250000000 1375000000 1312500000 0848390 5 1312500000 1375000000 1343750000 0350980 6 1343750000 1375000000 1359375000 0096410 7 1359375000 1375000000 1367187500 0032360 8 1359375000 1367187500 1363281250 0032150 9 1363281250 1367187500 1365234375 0000072 10 1363281250 1365234375 1364257813 0016050 11 1364257813 1365234375 1364746094 0007990 12 1364746094 1365234375 1364990235 0003960 13 1364990235 1365234375 1365112305 0001940 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 14 20 Exemplo Após 13 iterações p13 1365112305 se aproxima de uma raiz p com erro p p13 b14 a14 1365234375 1365112305 0000122070 Como a14 p p p13 p b14 a14 a14 9 105 o que significa que a aproximação está correta em pelo menos 4 dígitos significativos Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 15 20 Exemplo O valor correto de p com nove casas decimais é p 1365230013 Note que p9 está mais próximo de p do que p13 Uma evidência deste fato é que fp9 fp13 Mas esta evidência pode ser enganosa e só é possível fazer esta constatação sabendo qual o verdadeiro valor de p Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 16 20 Método da Bissecção O Método da Bissecção tem a propriedade de sempre convergir para uma solução além de ter a vantagem de ser muito claro e simples de ser implementado Entretanto o Método da Bissecção tem a convergência muito lenta e uma aproximação intermediária boa pode ser descartada inadvertidamente Por estas razões o Método da Bissecção é muito usado no início da aplicação de outros métodos mais eficientes que veremos mais adiante Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 17 20 Convergência Teorema 1 Suponha que f Ca b e fafb 0 O Método da Bissecção gera uma sequência pk k1 que se aproxima de uma raiz p de f com pk p b a 2k para k 1 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 18 20 Método da Bissecgao Como ba Pk pl oR a sequéncia px 72 Converge para p com uma taxa de convergéncia O sr ou seja 1 Método da Bissecção O Teorema 1 fornece um limitante para o erro da aproximação obtida em cada iteração mas este limitante pode ser muito conservador No exemplo anterior o limitante garante apenas que p p9 2 1 29 2 103 No entanto o erro real é p p9 1365230013 1365234375 44 106 Cálculo Numérico Representação e erros numéricos 3 de agosto de 2022 20 20