Erros e Instabilidade Numérica em Represen tação de Números em Máquinas, Notas de aula de Engenharia Elétrica

Baixe Erros e Instabilidade Numérica em Represen tação de Números em Máquinas e outras Notas de aula em PDF para Engenharia Elétrica, somente na Docsity! Erros Instabilidade Numérica Representação de números em máquinas Leonardo F. Guidi DMPA – IM UFRGS Cálculo Numérico Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Índice 1 Erros 2 Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Conceitos iniciais Notação: Com x  y (x  y) queremos dizer que x é muito menor (muito maior) do que y . O termo “muito menor” (ou “muito maior”)depende do contexto. Com x ≈ y queremos dizer que x é aproximadamente igual a y , ou dito de outra forma, |x−y |  ε, onde ε depende do contexto. Com x / y (x ' y) queremos dizer que x é menor (maior) ou aproximadamente igual a y e possui o mesmo significado da expressão “x ≤ y e x ≈ y ”. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Propagação de erros Vamos assumir que x̃ é uma aproximação de um número x , sem perda de generalidade, vamos supor que x > x̃ . Se quisermos encontrar o valor da função f calculada em x mas só dispor- mos de x̃ devemos aproximar f (x) por f (x̃). Para f diferenciável, o teorema do valor médio garante que existe um ε ∈ (x̃ ,x): f (x)− f (x̃) = f ′(ε)(x− x̃). Mas e ε? Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Propagação de erros Supondo que f ′ é limitada no intervalo de valores entre x e x̃ , então podemos limitar em valor absoluto : |f (x)− f (x̃)| ≤M |x− x̃ | , onde M = supy∈(x ,x̃) |f ′(y)|. Se o erro em valor absoluto for pequeno (o suficiente para que f ′ não varia apreciavelmente) então é razoável estimar |f (x)− f (x̃)| ≈ ∣∣f ′(x̃)∣∣ |x− x̃ | . Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Instabilidade numérica Alguns problemas matemáticos e algoritmos numéricos possuem a propri- edade de ampliar drasticamente os erros presentes nos dados de entrada e assim invalidar a saída ou resposta. No contexto do cálculo numérico, esse fenômeno é denominado instabili- dade numérica. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Instabilidade numérica Alguns problemas matemáticos e algoritmos numéricos possuem a propri- edade de ampliar drasticamente os erros presentes nos dados de entrada e assim invalidar a saída ou resposta. No contexto do cálculo numérico, esse fenômeno é denominado instabili- dade numérica. A instabilidade se manifesta devido à natureza do algoritmo ou do próprio problema (nessa caso, dizemos que o problema é mal-condicionado). Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Instabilidade numérica Alguns problemas matemáticos e algoritmos numéricos possuem a propri- edade de ampliar drasticamente os erros presentes nos dados de entrada e assim invalidar a saída ou resposta. No contexto do cálculo numérico, esse fenômeno é denominado instabili- dade numérica. A instabilidade se manifesta devido à natureza do algoritmo ou do próprio problema (nessa caso, dizemos que o problema é mal-condicionado). Vamos analisar a instabilidade numérica se manifestando em um algoritmo: Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Instabilidade numérica A integral pode ser resolvida utilizando-se sucessivamente a integração por partes. A partir dela, podemos verificar que In satisfaz uma “relação de recorrência”. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Instabilidade numérica A integral pode ser resolvida utilizando-se sucessivamente a integração por partes. A partir dela, podemos verificar que In satisfaz uma “relação de recorrência”. Se n ≥ 1, então In = xnex−1 ∣∣x=1 x=0−n ∫ 1 0 xn−1ex−1 In = 1−nIn−1 para n = 1,2, . . . Veremos que um algoritmo baseado na utilização direta da relação de recorrência para In é numericamente instável. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Cancelamento catastrófico É um efeito presente nas operações em ponto flutuante, caracterizado pelo aumento significativo do erro relativo no resultado da operação. O cancelamento catastrófico pode ser verificado principalmente na operação de subtração de dois pontos flutuantes muito próximos. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Cancelamento catastrófico É um efeito presente nas operações em ponto flutuante, caracterizado pelo aumento significativo do erro relativo no resultado da operação. O cancelamento catastrófico pode ser verificado principalmente na operação de subtração de dois pontos flutuantes muito próximos. Vamos considerar a operação em ponto flutuante associada à subtração dos números racionais 0,9876543210423456789 e 0,9876543209. Se os registros forem de 10 dígitos, a representação dos dois números será respectivamente 0,9876543210 e 0,9876543209. A diferença exata entre os dois números é de 0,1423456789×10−10 enquanto que o resultado da operação de diferença em ponto flutuante é 0,100000000×10−10. O erro relativo é aproximadamente 0,3. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Cancelamento catastrófico Um outro exemplo clássico é o das raízes de uma equação polinomial de segundo grau. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Cancelamento catastrófico Um outro exemplo clássico é o das raízes de uma equação polinomial de segundo grau. Seja a equação de segundo grau x2 +400x−0.00004617 = 0. Essa equação possui duas raízes reais, uma próxima a−400 e outra próxima a 0. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Cancelamento catastrófico Substituindo os valores e realizando as operações, obtemos (−b sqrt((b⊗b) (4⊗ c))) 2 = ( −0,4000000000×103 sqrt ( 0,1600000000×106⊕0,1846800000×10−3 )) 2 = ( −0,4000000000×103 sqrt ( 0,1600000002×106 )) 2 = ( −0,4000000000×103 0,4000000002×103 ) 2 = −0,4000000001×103, Realizando as operações para a outra raiz, obtemos o valor 0,1000000000× 10−6. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Cancelamento catastrófico O valor da primeira raiz com os dezesseis primeiros dígitos exatos é −400,0000001154249 . . . e há concordância com os dez primeiros dígi- tos obtidos na operação em ponto flutuante. O mesmo não ocorre com a segunda raiz. Neste caso, o valor com dezesseis dígitos exatos é 0,1154249999666926 . . .×10−6 e, à exceção do primeiro dígito, todos os seguintes diferem, o que caracteriza o cancelamento catastrófico. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Cancelamento catastrófico O valor da primeira raiz com os dezesseis primeiros dígitos exatos é −400,0000001154249 . . . e há concordância com os dez primeiros dígi- tos obtidos na operação em ponto flutuante. O mesmo não ocorre com a segunda raiz. Neste caso, o valor com dezesseis dígitos exatos é 0,1154249999666926 . . .×10−6 e, à exceção do primeiro dígito, todos os seguintes diferem, o que caracteriza o cancelamento catastrófico. A inexatidão no cálculo da segunda raiz pode ser diminuída consideravel- mente se manipularmos a expressão de maneira a evitar a subtração de dois pontos flutuantes muito próximos. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Cancelamento catastrófico Evitamos o cancelamento catastrófico em ponto flutuante realizando o cancelamento na própria expressão, antes de realizarmos as operações em ponto flutuante: −b + √ b2−4c = = −b + |b| √ 1− 4c b2 = −b + |b| ( 1− 2c b2 + . . . ) ≈ −b + |b| ( 1− 2c b2 ) Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Cancelamento catastrófico Como b > 0, a segunda raiz pode ser calculada a partir da aproximação −b + √ b2−4c 2 ≈−c b . Substituindo os valores das constantes b, c e realizando as operações em ponto flutuante, obtemos a aproximação 0,1154250000×10−6 que possui um erro muitas vezes menor. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Instabilidade relacionada ao canc. catastr. Vamos estudar agora um exemplo no qual o cancelamento catastrófico leva à instabilidade numérica: Fórmula de recorrência de Arquimedes (ou algoritmo Borchardt-Pfaff) para aproximar o valor de π. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Instabilidade numérica – condicionamento Um outro exemplo clássico é o das raízes de uma equação polinomial de segundo grau. Nesse caso, a instabilidade está relacionada à propria natureza do problema. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Instabilidade numérica – condicionamento Um outro exemplo clássico é o das raízes de uma equação polinomial de segundo grau. Nesse caso, a instabilidade está relacionada à propria natureza do problema. Seja o polinômio P(x) = (x−1)(x−2) . . .(x−20) = x20−210x19 + . . .+20! Ou seja, P é um polinômio em x com raízes inteiras 1,2,3, . . . ,20. Leonardo F. Guidi Representação de números em máquinas Erros Instabilidade Numérica Algoritmos instáveis Cancelamento catastrófico Condicionamento Instabilidade numérica – condicionamento Um outro exemplo clássico é o das raízes de uma equação polinomial de segundo grau. Nesse caso, a instabilidade está relacionada à propria natureza do problema. Seja o polinômio P(x) = (x−1)(x−2) . . .(x−20) = x20−210x19 + . . .+20! Ou seja, P é um polinômio em x com raízes inteiras 1,2,3, . . . ,20. Vamos considerar agora o polinômio P̃: P̃(x) = P(x)−2−23 x19. Ou seja, P̃ é igual P a menos de um erro relativo de 5,7 ·10−10 no coefi- ciente do termo x9. Leonardo F. Guidi Representação de números em máquinas