Dykstras proektsiyalash algoritmi - Dykstras projection algorithm

Dykstra algoritmi ning kesishgan nuqtasini hisoblaydigan usul qavariq to'plamlar, va ning bir variantidir o'zgaruvchan proektsiya usuli (shuningdek qavariq to'plamlarga proektsiyalar usul). Eng sodda shaklda, har bir qavariq to'plamga takroriy proektsiyalash orqali usul ikkita qavariq to'plamlar kesishmasida nuqta topadi; u o'zgaruvchan proyeksiya usulidan farq qiladi, chunki u oraliq qadamlardir. Algoritmning parallel versiyasi Gaffke va Mathar tomonidan ishlab chiqilgan.

Usul 1980-yillarda taklif qilgan Richard L. Dyukstra nomidan olingan.

Dykstra algoritmi va standart o'zgaruvchan proektsiya usuli o'rtasidagi asosiy farq ikki to'plam kesishmasida bir nechta nuqta bo'lganda sodir bo'ladi. Bu holda o'zgaruvchan proyeksiya usuli bu kesishishda o'zboshimchalik bilan nuqta beradi, Dyukstra algoritmi esa ma'lum bir nuqtani beradi: r chorrahaga, qaerda r algoritmda ishlatiladigan dastlabki nuqta,

Algoritm

Dykstra algoritmi har biri uchun topadi ${ displaystyle r}$ faqat ${ displaystyle { bar {x}} in C cap D}$ shu kabi:

${ displaystyle | { bar {x}} - r | ^ {2} leq | x-r | ^ {2}, { text {all for}} x in C cap D,}$

qayerda ${ displaystyle C, D}$ bor qavariq to'plamlar. Bu muammo topishga tengdir proektsiya ning ${ displaystyle r}$ to'plamga ${ displaystyle C cap D}$buni biz belgilaymiz ${ displaystyle { mathcal {P}} _ {C cap D}}$.

Dykstra algoritmidan foydalanish uchun to'plamlarga qanday qilib proektsiya qilishni bilish kerak ${ displaystyle C}$ va ${ displaystyle D}$ alohida-alohida.

Birinchidan, asosiy narsani ko'rib chiqing o'zgaruvchan proektsiya (aka POCS) usuli (avval o'rganilgan, agar to'plamlar bo'lsa ${ displaystyle C, D}$ tomonidan chiziqli pastki bo'shliqlar bo'lgan Jon fon Neyman^[1]) boshlanadigan ${ displaystyle x_ {0} = r}$ va keyin ketma-ketlikni hosil qiladi

${ displaystyle x_ {k + 1} = { mathcal {P}} _ {C} left ({ mathcal {P}} _ {D} (x_ {k}) right)}$.

Dykstra algoritmi xuddi shunday shaklda, lekin qo'shimcha yordamchi o'zgaruvchilardan foydalanadi. Bilan boshlang ${ displaystyle x_ {0} = r, p_ {0} = q_ {0} = 0}$ va yangilash

${ displaystyle y_ {k} = { mathcal {P}} _ {D} (x_ {k} + p_ {k})}$

${ displaystyle p_ {k + 1} = x_ {k} + p_ {k} -y_ {k}}$

${ displaystyle x_ {k + 1} = { mathcal {P}} _ {C} (y_ {k} + q_ {k})}$

${ displaystyle q_ {k + 1} = y_ {k} + q_ {k} -x_ {k + 1}.}$

Keyin ketma-ketlik ${ displaystyle (x_ {k})}$ asl muammoning echimiga yaqinlashadi. Uyg'unlik natijalari va adabiyotga zamonaviy nuqtai nazar uchun qarang ^[2]

Adabiyotlar

• Boyl, J. P .; Dykstra, R. L. (1986). Hilbert fazosidagi qavariq to'plamlar kesishmasiga proektsiyalarni topish usuli. Statistikadan ma'ruza yozuvlari. 37. 28-47 betlar. doi:10.1007/978-1-4613-9940-7_3. ISBN  978-0-387-96419-5.
• Gaffke, N .; Mathar, R. (1989). "Ikkilik orqali proektsion tsiklik algoritm". Metrika. 36: 29–54. doi:10.1007 / bf02614077.

Iqtiboslar