Orden de operaciones, algoritmos numéricos

10

He leido eso

(1) Las operaciones mal condicionadas deben realizarse antes que las bien condicionadas.

Como ejemplo, uno debe calcular Xz-yz como (X-y)z ya que la resta está mal condicionada mientras que la multiplicación no.

Sin embargo, un análisis de error de primer orden de ambos algoritmos revela que difieren solo por un factor de tres (*), y no veo por qué uno puede generalizar esto a la declaración (1), ni entiendo intuitivamente la importancia de Orden de operaciones. ¿Crees que la declaración es (1) es una regla aceptada, y tienes otras explicaciones para ello?

*: más específicamente, la primera versión tiene un error relativo delimitado por

eps+3El |XEl |+El |yEl |El |XEl |-El |yEl |eps
mientras que el error relativo de la segunda versión está delimitado por

3eps+El |XEl |+El |yEl |El |XEl |-El |yEl |eps

donde eps es la precisión de la máquina.

Este análisis se basa en la suposición de que el yo -ésimo resultado intermedio se multiplica por (1+εyo) (debido a errores de redondeo), donde εyo es iid variables aleatorias limitadas por eps . "Primer orden" significa que los términos de orden superior, como ϵyoϵjX , se descuidan.

Bananach
fuente
¿Dónde leíste eso?
David Ketcheson
en mis apuntes
Bananach

Respuestas:

8

Denotemos por (era flojo tratando de obtener una versión en círculo del operador de división) los análogos de coma flotante de multiplicación exacta ( × ), suma ( + ) y resta ( - ), respectivamente. Asumiremos (IEEE-754) que para todos ellos [ x y ] = ( x + y ) ( 1 + δ ) ,,,×+- donde ϵ m a c h es la máquina épsilon que da un límite superior al error relativo debido al redondeo. También usaremos el siguiente lema (suponiendo que todos | δ i |ϵ m a c h , ym no es demasiado grande) que se puede probar fácilmente: m i = 1 ( 1 + δ i ) = 1 + θ (

[Xy]=(X+y)(1+δ),El |δEl |ϵmetrounaCh,
ϵmetrounaChEl |δyoEl |ϵmetrounaChmetro
yo=1metro(1+δyo)=1+θ(metro),El |θ(metro)El |metroϵmetrounaCh1-metroϵmetrounaCh

Definamos la verdadera función que opera en números reales x , y , z comoFX,y,z

F(X,y,z)=(X×z)-(y×z)

y dos versiones de la implementación de la función en aritmética de coma flotante compatible con IEEE como y ~ f 2 que operan en representaciones de coma flotante ˜ x = x ( 1 + δ x ) , ˜ y , ˜ z , como sigue:F1~F2~X~=X(1+δX),y~,z~

F1~(X~,y~,z~)=(X~z~)(y~z~),

F2~(X~,y~,z~)=(X~y~)z~.

Análisis de error para :F1~

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).
El |θXz,1El |,El |θyz,1El |4 4ϵmetrounaCh1-4 4ϵmetrounaCh

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).
El |θX,2El |,El |θy,2El |4 4ϵmetrounaCh1-4 4ϵmetrounaCh

F1~F2~F2~F1~

Xy

El |F1~-FEl |El |FEl |=El |Xz+XzθXz,1-yz-yzθyz,1-(Xz-yz)El |El |Xz-yzEl |=El |XθXz,1-yθyz,1El |El |X-yEl |El |XEl |+El |yEl |El |X-yEl |4 4ϵmetrounaCh1-4 4ϵmetrounaCh,
El |F2~-FEl |El |FEl |=El |Xz+XzθX,2-yz-yzθy,2-(Xz-yz)El |El |Xz-yzEl |=El |XθX,2-yθy,2El |El |X-yEl |El |XEl |+El |yEl |El |X-yEl |4 4ϵmetrounaCh1-4 4ϵmetrounaCh.

θX,y,z(X-y)Xy

X,y,z,F(X,y,z)F0 0F0 0

Anton Menshov
fuente