Ordem das operações, algoritmos numéricos

10

Eu li isso

(1) Operações mal condicionadas devem ser realizadas antes das bem condicionadas.

Como exemplo, deve-se calcular xzyz como (xy)z pois a subtração está mal condicionada enquanto a multiplicação não.

Entretanto, uma análise de erro de primeira ordem de ambos os algoritmos revela que eles diferem apenas por um fator de três (*), e não vejo por que se pode generalizar isso na afirmação (1), nem compreendo intuitivamente a importância de ordem de operações. Você acha que a afirmação é (1) é uma regra aceita e você tem outras explicações para isso?

*: mais especificamente, a primeira versão possui um erro relativo delimitado por

enquanto o erro relativo da segunda versão é delimitado por

eps+3|x|+|y||x||y|eps

3eps+|x|+|y||x||y|eps

onde é a precisão da máquina.eps

Essa análise baseia-se no pressuposto de que o ésimo resultado intermediário é multiplicado por ( 1 + ε i ) (devido a erros de arredondamento), em que ε i são variáveis ​​aleatórias delimitadas por eps . Meios "de primeira ordem" que os termos de ordem superior, como ε i ε j x , são negligenciadas.i(1+εi)εiepsϵiϵjx

Bananach
fonte
Onde você leu isso?
David Ketcheson
nas minhas anotações de aula
Bananach

Respostas:

8

Vamos denotar por (eu estava com preguiça de tentar obter uma versão circulada do operador de divisão) os análogos de ponto flutuante da multiplicação exata ( × ), adição ( + ) e subtração ( - ), respectivamente. Vamos assumir (IEEE-754) que, para todos eles [ x y ] = ( x + y ) ( 1 + δ ) ,,,×+- onde ε m um c h é a epsilon máquina que dá um limite superior sobre o erro relativo devido ao arredondamento. Também usaremos o seguinte lema (assumindo que todos | δ i |ϵ

[xy]=(x+y)(1 1+δ),|δ|ϵmumach,
ϵmumach emnão é muito grande) que pode ser facilmente comprovada: m Π i = 1 (1+ δ i )=1+θ(|δEu|ϵmumachm
i=1m(1+δi)=1+θ(m),|θ(m)|mϵmach1mϵmach

Vamos definir a verdadeira função que opera nos números reais x , y , z comofx,y,z

f(x,y,z)=(x×z)-(y×z)

e duas versões da implementação da função na aritmética de ponto flutuante compatível com IEEE como e ~ f 2 que operam nas representações de ponto flutuante ˜ xf1 1~f2~ , como se segue:x~=x(1 1+δx),y~,z~

f1 1~(x~,y~,z~)=(x~z~)(y~z~),

f2~(x~,y~,z~)=(x~y~)z~.

Análise de erro para :f1 1~

f1~=((x(1+δx)×z(1+δz))(1+δxz)(x~z~)(y(1+δy)×z(1+δz))(1+δyz)(y~z~))(1+δ)=xz(1+δx)(1+δz)(1+δxz)(1+δ)yz(1+δy)(1+δz)(1+δyz)(1+δ)=xz(1+θxz,1)yz(1+θyz,1).
|θxz,1|,|θyz,1|4ϵmach14ϵmach

f2~

f2~=(((x(1+δx)y(1+δy)(1+δxy))×(z(1+δz)))(1+δ)=xz(1+δx)(1+δz)(1+δxy)(1+δ)yz(1+δy)(1+δz)(1+δxy)(1+δ)=xz(1+θx,2)yz(1+θy,2).
|θx,2|,|θy,2|4ϵmach14ϵmach

f1~f2~f2~f1~

xy

|f1~f||f|=|xz+xzθxz,1yzyzθyz,1(xzyz)||xzyz|=|xθxz,1yθyz,1||xy||x|+|y||xy|4ϵmach14ϵmach,
|f2~f||f|=|xz+xzθx,2yzyzθy,2(xzyz)||xzyz|=|xθx,2yθy,2||xy||x|+|y||xy|4ϵmach14ϵmach.

θx,y,z(xy)xy

x,y,z,f(x,y,z)F0F0

Anton Menshov
fonte