Kolejność operacji, algorytmy numeryczne

10

Przeczytałem to

(1) Czynności źle uwarunkowane należy wykonać przed czynnościami dobrze uwarunkowanymi.

Jako przykład należy obliczyć xz-yz jako (x-y)z ponieważ odejmowanie jest źle uwarunkowane, podczas gdy mnożenie nie.

Jednak analiza błędów pierwszego rzędu obu algorytmów ujawnia, że ​​różnią się one tylko trzykrotnie (*) i nie rozumiem, dlaczego można to uogólnić na wyrażenie (1), ani intuicyjnie nie rozumiem znaczenia kolejność operacji. Czy uważasz, że stwierdzenie to (1) jest przyjętą zasadą i czy masz na to inne wyjaśnienia?

*: dokładniej, w pierwszej wersji występuje błąd względny ograniczony

eps+3)|x|+|y||x|-|y|eps
podczas gdy błąd względny drugiej wersji jest ograniczony przez

3)eps+|x|+|y||x|-|y|eps

gdzie eps jest precyzją maszyny.

Analiza ta opiera się na założeniu, że ja ty wynik pośredni jest mnożony przez (1+εja) (z powodu błędów zaokrąglania), gdzie εja są zmiennymi losowymi iid ograniczonymi przez eps . „Pierwszego rzędu” oznacza, że ​​terminy wyższego rzędu, takie jak ϵjaϵjotx , są zaniedbywane.

Bananach
źródło
Gdzie to przeczytałeś?
David Ketcheson
w moich notatkach z wykładów
Bananach

Odpowiedzi:

8

Oznaczmy przez (byłem leniwy, próbując uzyskać wersję operatora dzielenia w kółku) odpowiednio zmiennoprzecinkowe analogi dokładnego mnożenia ( × ), dodawania ( + ) i odejmowania ( - ). Zakładamy (IEEE-754), że dla wszystkich [ x y ] = ( x + y ) ( 1 + δ ) ,,,×+- gdzie ϵ m a c h to epsilon maszyny dający górną granicę błędu względnego z powodu zaokrąglenia. Będzie również użyć następującego lematu (przy założeniu, że wszystkie | δ I |ε m o c h i m nie jest zbyt duży), które mogą być łatwo sprawdzone: m Π i = 1 ( 1 + δ I ) = 1 + θ (

[xy]=(x+y)(1+δ),|δ|ϵmzadoh,
ϵmzadoh|δja|ϵmzadohm
ja=1m(1+δja)=1+θ(m),|θ(m)|mϵmzadoh1-mϵmzadoh

Zdefiniujmy prawdziwą funkcję która działa na liczbach rzeczywistych x , y , z jakfax,y,z

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

oraz dwie wersje implementacji funkcji w arytmetyki zmiennoprzecinkowej zgodnej z IEEE jako i ~ f 2, które działają na reprezentacjach zmiennoprzecinkowych ˜ x = x ( 1 + δ x ) , ˜ y , ˜ z , w następujący sposób:fa1~fa2)~x~=x(1+δx),y~,z~

fa1~(x~,y~,z~)=(x~z~)(y~z~),

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

Analiza błędów dla :fa1~

fa1~=((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ϵmzadoh1-4ϵmzadoh

fa2)~

fa2)~=(((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ϵmzadoh1-4ϵmzadoh

fa1~fa2)~fa2)~fa1~

xy

|fa1~-fa||fa|=|xz+xzθxz,1-yz-yzθyz,1-(xz-yz)||xz-yz|=|xθxz,1-yθyz,1||x-y||x|+|y||x-y|4ϵmzadoh1-4ϵmzadoh,
|fa2)~-fa||fa|=|xz+xzθx,2)-yz-yzθy,2)-(xz-yz)||xz-yz|=|xθx,2)-yθy,2)||x-y||x|+|y||x-y|4ϵmzadoh1-4ϵmzadoh.

θx,y,z(x-y)xy

x,y,z,fa(x,y,z)fa0fa0

Anton Menshov
źródło