Urutan operasi, algoritma numerik

10

Saya sudah membaca itu

(1) Operasi yang terkondisi harus dilakukan sebelum yang terkondisi dengan baik.

Sebagai contoh, seseorang harus menghitung xzyz sebagai(xy)z karena pengurangan tidak dikondisikan sedangkan multiplikasi tidak.

Namun, analisis kesalahan orde pertama dari kedua algoritma mengungkapkan bahwa mereka hanya berbeda oleh faktor tiga (*), dan saya tidak melihat mengapa orang dapat menggeneralisasikan ini ke pernyataan (1), dan saya juga tidak secara intuitif memahami pentingnya urutan operasi. Apakah menurut Anda pernyataan itu (1) adalah aturan yang diterima, dan apakah Anda punya penjelasan lain untuk itu?

*: lebih khusus, versi pertama memiliki kesalahan relatif yang dibatasi oleh

eps+3|x|+|y||x||y|eps
sementara kesalahan relatif dari versi kedua dibatasi oleh

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

dimanaeps adalah presisi mesin.

Analisis ini didasarkan pada asumsi bahwa hasil menengah ke- dikalikan dengan (karena kesalahan pembulatan), di mana adalah variabel acak pertama yang dibatasi oleh . "Urutan pertama" berarti bahwa istilah dengan tingkat lebih tinggi, seperti , diabaikan.i(1+εi)εiepsϵiϵjx

Bananach
sumber
Dimana Anda membaca itu?
David Ketcheson
dalam catatan kuliah saya
Bananach

Jawaban:

8

Mari kita tunjukkan dengan (Saya malas mencoba untuk mendapatkan versi yang dilingkari dari operator divisi) analog floating-point dari perkalian yang tepat (× ), penambahan ( + ), dan pengurangan ( - ), masing-masing. Kami akan menganggap (IEEE-754) bahwa untuk semuanya [ x y ] = ( x + y ) ( 1,,×+ mana ϵ m a c h adalah mesin epsilon yang memberikan batas atas pada kesalahan relatif karena pembulatan. Kami juga akan menggunakan lemma berikut (dengan asumsi semua | δ i |ε m a c h , dan m tidak terlalu besar) yang dapat dengan mudah dibuktikan: m Π i = 1 ( 1 + δ i

[xy]=(x+y)(1+δ),|δ|ϵmach,
ϵmach|δi|ϵmachm
i=1m(1+δi)=1+θ(m),|θ(m)|mϵmach1mϵmach

fx,y,z

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

f1~f2~x~=x(1+δx),y~,z~ , sebagai berikut:

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

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

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).
|θ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 adalah himpunan semua angka floating-point normal.

Anton Menshov
sumber