Kantorovich teoremasi - Kantorovich theorem - Wikipedia

The Kantorovich teoremasiyoki Nyuton-Kantorovich teoremasi - bu yarim mahalliy matematik bayon yaqinlashish ning Nyuton usuli. Bu birinchi tomonidan aytilgan Leonid Kantorovich 1948 yilda.^[1]^[2] Ning shakliga o'xshaydi Banax sobit nuqta teoremasi, garchi u a ning mavjudligi va o'ziga xosligini bildiradi nol a o'rniga sobit nuqta.^[3]

Nyuton usuli ma'lum sharoitlarda yechimga yaqinlashadigan nuqtalar ketma-ketligini tuzadi ${ displaystyle x}$ tenglama ${ displaystyle f (x) = 0}$ yoki tenglama tizimining vektorli echimi ${ displaystyle F (x) = 0}$ . Kantorovich teoremasi ushbu ketma-ketlikning dastlabki nuqtasida shartlarni beradi. Agar ushbu shartlar bajarilsa, unda dastlabki nuqtaga yaqin echim mavjud va ketma-ketlik shu nuqtaga yaqinlashadi.^[1]^[2]

Taxminlar

Ruxsat bering ${ displaystyle X subset mathbb {R} ^ {n}}$ ochiq pastki qism bo'lishi va ${ displaystyle F: X subset mathbb {R} ^ {n} to mathbb {R} ^ {n}}$ a farqlanadigan funktsiya bilan Jacobian ${ displaystyle F ^ { prime} ( mathbf {x})}$ bu mahalliy Lipschitz doimiy (masalan, agar ${ displaystyle F}$ ikki marta farqlanadi). Ya'ni, har qanday ochiq to'plam uchun deb taxmin qilinadi ${ displaystyle U subset X}$ doimiy mavjud ${ displaystyle L> 0}$ har qanday kishi uchun ${} displaystyle mathbf {x}, mathbf {y} U}$

{ displaystyle | F '( mathbf {x}) -F' ( mathbf {y}) | leq L ; | mathbf {x} - mathbf {y} |}

ushlab turadi. Chapdagi norma - bu o'ngdagi vektor normasiga mos keladigan ba'zi operator normalari. Ushbu tengsizlikni faqat vektor normasidan foydalanish uchun qayta yozish mumkin. Keyin har qanday vektor uchun ${ displaystyle mathbf {v} in mathbb {R} ^ {n}}$ tengsizlik

{ displaystyle | F '( mathbf {x}) ( mathbf {v}) -F' ( mathbf {y}) ( mathbf {v}) | leq L ; | mathbf { x} - mathbf {y} | , | mathbf {v} |}

ushlab turishi kerak.

Endi har qanday dastlabki fikrni tanlang ${ displaystyle mathbf {x} _ {0} in X}$ . Buni taxmin qiling ${ displaystyle F '( mathbf {x} _ {0})}$ o'zgaruvchan va Nyuton qadamini qurish ${ displaystyle mathbf {h} _ {0} = - F '( mathbf {x} _ {0}) ^ {- 1} F ( mathbf {x} _ {0}).}$

Keyingi taxmin - bu nafaqat keyingi nuqta ${ displaystyle mathbf {x} _ {1} = mathbf {x} _ {0} + mathbf {h} _ {0}}$ lekin butun to'p ${ displaystyle B ( mathbf {x} _ {1}, | mathbf {h} _ {0} |)}$ to'plam ichida joylashgan ${ displaystyle X}$ . Ruxsat bering ${ displaystyle M leq L}$ Jacobs uchun bu to'p ustidan Lipschitz doimiysi bo'ling.

Oxirgi tayyorgarlik sifatida, iloji boricha ketma-ketliklarni rekursiv ravishda tuzing ${ displaystyle ( mathbf {x} _ {k}) _ {k}}$ , ${ displaystyle ( mathbf {h} _ {k}) _ {k}}$ , ${ displaystyle ( alfa _ {k}) _ {k}}$ ga binoan

{ displaystyle { begin {alignedat} {2} mathbf {h} _ {k} & = - F '( mathbf {x} _ {k}) ^ {- 1} F ( mathbf {x} _) {k}) [0.4em] alfa _ {k} & = M , | F '( mathbf {x} _ {k}) ^ {- 1} | , | mathbf { h} _ {k} | [0.4em] mathbf {x} _ {k + 1} & = mathbf {x} _ {k} + mathbf {h} _ {k}. end { alignedat}}}

Bayonot

Endi agar ${ displaystyle alpha _ {0} leq { tfrac {1} {2}}}$ keyin

yechim ${ displaystyle mathbf {x} ^ {*}}$ ning ${ displaystyle F ( mathbf {x} ^ {*}) = 0}$ yopiq to'p ichida mavjud ${ displaystyle { bar {B}} ( mathbf {x} _ {1}, | mathbf {h} _ {0} |)}$ va
dan boshlanadigan Nyuton iteratsiyasi ${ displaystyle mathbf {x} _ {0}}$ ga yaqinlashadi ${ displaystyle mathbf {x} ^ {*}}$ yaqinlashuvning hech bo'lmaganda chiziqli tartibi bilan.

Aniqroq, ammo isbotlash biroz qiyinroq bo'lgan bayonot ildizlardan foydalanadi ${ displaystyle t ^ { ast} leq t ^ {**}}$ kvadratik polinomning

{ displaystyle p (t) = chap ({ tfrac {1} {2}} L | F '( mathbf {x} _ {0}) ^ {- 1} | ^ {- 1} o'ng) t ^ {2} -t + | mathbf {h} _ {0} |}

,

{ displaystyle t ^ { ast / **} = { frac {2 | mathbf {h} _ {0} |} {1 pm { sqrt {1-2 alfa}}}}}}

va ularning nisbati

{ displaystyle theta = { frac {t ^ {*}} {t ^ {**}}} = { frac {1 - { sqrt {1-2 alpha}}} {1 + { sqrt {1-2 alfa}}}}.}

Keyin

yechim ${ displaystyle mathbf {x} ^ {*}}$ yopiq to'p ichida mavjud ${ displaystyle { bar {B}} ( mathbf {x} _ {1}, theta | mathbf {h} _ {0} |) subset { bar {B}} ( mathbf { x} _ {0}, t ^ {*})}$
u kattaroq to'p ichida noyobdir ${ displaystyle B ( mathbf {x} _ {0}, t ^ {* ast})}$
va ning echimiga yaqinlashish ${ displaystyle F}$ kvadratik polinomning Nyuton takrorlanishining yaqinlashuvi ustunlik qiladi ${ displaystyle p (t)}$ uning eng kichik ildiziga qarab ${ displaystyle t ^ { ast}}$ ,^[4] agar ${ displaystyle t_ {0} = 0, , t_ {k + 1} = t_ {k} - { tfrac {p (t_ {k})} {p '(t_ {k})}}}$ , keyin
${ displaystyle | mathbf {x} _ {k + p} - mathbf {x} _ {k} | leq t_ {k + p} -t_ {k}.}$
Kvadratik yaqinlashuv xatolarni baholashdan olinadi^[5]
${ displaystyle | mathbf {x} _ {n + 1} - mathbf {x} ^ {*} | leq theta ^ {2 ^ {n}} | mathbf {x} _ {n +1} - mathbf {x} _ {n} | leq { frac { theta ^ {2 ^ {n}}} {2 ^ {n}}} | mathbf {h} _ {0 } |.}$

Xulosa

1986 yilda Yamamoto Nyuton uslubidagi xatolarni baholash, masalan Doring (1969), Ostrowski (1971, 1973),^[6]^[7] Gragg-Tapia (1974), Potra-Ptak (1980),^[8] Miel (1981),^[9] Potra (1984),^[10] Kantorovich teoremasidan kelib chiqishi mumkin.^[11]

Umumlashtirish

Bor q-analog Kantorovich teoremasi uchun.^[12]^[13] Boshqa umumlashmalar / tafovutlar uchun qarang: Ortega & Rheinboldt (1970).^[14]

Ilovalar

Oishi va Tanabe ishonchli echimlarni olish uchun Kantorovich teoremasini qo'llash mumkin deb da'vo qildilar chiziqli dasturlash.^[15]

Adabiyotlar

^ ^a ^b Deuflhard, P. (2004). Lineer bo'lmagan muammolar uchun Nyuton usullari. Afinaviy o'zgaruvchanlik va adaptiv algoritmlar. Hisoblash matematikasida Springer seriyasi. Vol. 35. Berlin: Springer. ISBN 3-540-21099-7.
^ ^a ^b Zeidler, E. (1985). Lineer bo'lmagan funktsional tahlil va uning qo'llanilishi: 1-qism: Ruxsat etilgan teoremalar. Nyu-York: Springer. ISBN 0-387-96499-1.
^ Dennis, Jon E.; Shnabel, Robert B. (1983). "Kantorovich va shartnomaviy xaritalash teoremalari". Cheklanmagan optimallashtirish va nochiziqli tenglamalar uchun sonli usullar. Englewood qoyalari: Prentice-Hall. 92-94 betlar. ISBN 0-13-627216-9.
^ Ortega, J. M. (1968). "Nyuton-Kantorovich teoremasi". Amer. Matematika. Oylik. 75 (6): 658–660. doi:10.2307/2313800. JSTOR 2313800.
^ Gragg, V.B.; Tapia, R. A. (1974). "Nyuton-Kantorovich teoremasi uchun xatoning optimal chegaralari". Raqamli tahlil bo'yicha SIAM jurnali. 11 (1): 10–13. Bibcode:1974SJNA ... 11 ... 10G. doi:10.1137/0711002. JSTOR 2156425.
^ Ostrowski, A. M. (1971). "La metod de Newton dans les espaces de Banach". C. R. Akad. Ilmiy ish. Parij. 27 (A): 1251-1253.
^ Ostrowski, A. M. (1973). Evklid va banax bo'shliqlarida tenglamalarni echish. Nyu-York: Academic Press. ISBN 0-12-530260-6.
^ Potra, F. A .; Ptak, V. (1980). "Nyuton jarayonida keskin xato chegaralari". Raqam. Matematika. 34: 63–72. doi:10.1007 / BF01463998.
^ Miel, G. J. (1981). "Nyuton usuli uchun Kantorovich teoremasining yangilangan versiyasi". Hisoblash. 27 (3): 237–244. doi:10.1007 / BF02237981.
^ Potra, F. A. (1984). "Nyuton usuli uchun posteriori xato taxminlari to'g'risida". Beiträge zur Numerische Mathematik. 12: 125–138.
^ Yamamoto, T. (1986). "Kantorovich taxminlari bo'yicha Nyuton usuli uchun aniq xato chegaralarini topish usuli". Numerische Mathematik. 49 (2–3): 203–220. doi:10.1007 / BF01389624.
^ Rajkovich, P. M.; Stankovich, M. S .; Marinkovich, S. D. (2003). "Tenglama va tizimlarni echishning q-takroriy usullari to'g'risida". Novi Sad J. Matematikasi. 33 (2): 127–137.
^ Rajkovich, P. M.; Marinkovich, S. D .; Stankovich, M. S. (2005). "Tenglama tizimlarini echishning q-Nyuton-Kantorovich usuli to'g'risida". Amaliy matematika va hisoblash. 168 (2): 1432–1448. doi:10.1016 / j.amc.2004.10.035.
^ Ortega, J. M .; Rheinboldt, W. C. (1970). Lineer bo'lmagan tenglamalarni bir nechta o'zgaruvchilardagi takroriy echimi. SIAM. OCLC 95021.
^ Oishi, S .; Tanabe, K. (2009). "Lineer dasturlash uchun optimal nuqtani raqamli kiritish". JSIAM xatlari. 1: 5–8. doi:10.14495 / jsiaml.1.5.

Qo'shimcha o'qish

John H. Hubbard va Barbara Burke Hubbard: Vektorli hisoblash, chiziqli algebra va differentsial shakllar: yagona yondashuv, Matrix Editions, ISBN 978-0-9715766-3-6 (3. nashrni va Kant.-thm, shu jumladan namunaviy materialni oldindan ko'rish )
Yamamoto, Tetsuro (2001). "Nyuton va Nyutonga o'xshash usullar uchun konvergentsiya tahlilidagi tarixiy o'zgarishlar". Brezinskida, C .; Vuytak, L. (tahrir). Raqamli tahlil: 20-asrdagi tarixiy o'zgarishlar. Shimoliy-Gollandiya. 241-263 betlar. ISBN 0-444-50617-9.

[Deuflhard-1] Deuflhard, P. (2004). Lineer bo'lmagan muammolar uchun Nyuton usullari. Afinaviy o'zgaruvchanlik va adaptiv algoritmlar. Hisoblash matematikasida Springer seriyasi. Vol. 35. Berlin: Springer. ISBN 3-540-21099-7.

[Zeidler-2] Zeidler, E. (1985). Lineer bo'lmagan funktsional tahlil va uning qo'llanilishi: 1-qism: Ruxsat etilgan teoremalar. Nyu-York: Springer. ISBN 0-387-96499-1.

[3] Dennis, Jon E.; Shnabel, Robert B. (1983). "Kantorovich va shartnomaviy xaritalash teoremalari". Cheklanmagan optimallashtirish va nochiziqli tenglamalar uchun sonli usullar. Englewood qoyalari: Prentice-Hall. 92-94 betlar. ISBN 0-13-627216-9.

[4] Ortega, J. M. (1968). "Nyuton-Kantorovich teoremasi". Amer. Matematika. Oylik. 75 (6): 658–660. doi:10.2307/2313800. JSTOR 2313800.

[5] Gragg, V.B.; Tapia, R. A. (1974). "Nyuton-Kantorovich teoremasi uchun xatoning optimal chegaralari". Raqamli tahlil bo'yicha SIAM jurnali. 11 (1): 10–13. Bibcode:1974SJNA ... 11 ... 10G. doi:10.1137/0711002. JSTOR 2156425.

[6] Ostrowski, A. M. (1971). "La metod de Newton dans les espaces de Banach". C. R. Akad. Ilmiy ish. Parij. 27 (A): 1251-1253.

[7] Ostrowski, A. M. (1973). Evklid va banax bo'shliqlarida tenglamalarni echish. Nyu-York: Academic Press. ISBN 0-12-530260-6.

[8] Potra, F. A .; Ptak, V. (1980). "Nyuton jarayonida keskin xato chegaralari". Raqam. Matematika. 34: 63–72. doi:10.1007 / BF01463998.

[9] Miel, G. J. (1981). "Nyuton usuli uchun Kantorovich teoremasining yangilangan versiyasi". Hisoblash. 27 (3): 237–244. doi:10.1007 / BF02237981.

[10] Potra, F. A. (1984). "Nyuton usuli uchun posteriori xato taxminlari to'g'risida". Beiträge zur Numerische Mathematik. 12: 125–138.

[11] Yamamoto, T. (1986). "Kantorovich taxminlari bo'yicha Nyuton usuli uchun aniq xato chegaralarini topish usuli". Numerische Mathematik. 49 (2–3): 203–220. doi:10.1007 / BF01389624.

[12] Rajkovich, P. M.; Stankovich, M. S .; Marinkovich, S. D. (2003). "Tenglama va tizimlarni echishning q-takroriy usullari to'g'risida". Novi Sad J. Matematikasi. 33 (2): 127–137.

[13] Rajkovich, P. M.; Marinkovich, S. D .; Stankovich, M. S. (2005). "Tenglama tizimlarini echishning q-Nyuton-Kantorovich usuli to'g'risida". Amaliy matematika va hisoblash. 168 (2): 1432–1448. doi:10.1016 / j.amc.2004.10.035.

[14] Ortega, J. M .; Rheinboldt, W. C. (1970). Lineer bo'lmagan tenglamalarni bir nechta o'zgaruvchilardagi takroriy echimi. SIAM. OCLC 95021.

[15] Oishi, S .; Tanabe, K. (2009). "Lineer dasturlash uchun optimal nuqtani raqamli kiritish". JSIAM xatlari. 1: 5–8. doi:10.14495 / jsiaml.1.5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]