कांटोरोविच प्रमेय

कांटोरोविच प्रमेय, या न्यूटन-कांटोरोविच प्रमेय, न्यूटन की विधि के अनुक्रम की अर्ध-स्थानीय सीमा पर एक गणितीय कथन है। यह पहली बार 1948 में लियोनिद कांटोरोविच द्वारा कहा गया था। यह बानाच निश्चित-बिंदु प्रमेय के रूप के समान है, हालांकि यह एक निश्चित बिंदु (गणित) के बजाय किसी फ़ंक्शन के शून्य के अस्तित्व और विशिष्टता को बताता है। न्यूटन की विधि बिंदुओं का एक क्रम बनाती है जो कुछ शर्तों के तहत एक समाधान में परिवर्तित हो जाएगी $x$ एक समीकरण का $f(x)=0$ या समीकरण की प्रणाली का एक सदिश समाधान $F(x)=0$. कांटोरोविच प्रमेय इस अनुक्रम के प्रारंभिक बिंदु पर स्थितियाँ देता है। यदि वे शर्तें पूरी हो जाती हैं तो प्रारंभिक बिंदु के करीब एक समाधान मौजूद होता है और अनुक्रम उस बिंदु पर परिवर्तित हो जाता है।

धारणाएं

होने देना $X\subset \mathbb {R} ^{n}$ एक खुला उपसमुच्चय बनें और $F:X\subset \mathbb {R} ^{n}\to \mathbb {R} ^{n}$ जैकोबियन मैट्रिक्स और निर्धारक के साथ एक अवकलनीय फलन $F^{\prime }(\mathbf {x} )$ यह स्थानीय रूप से लिप्सचिट्ज़ निरंतर है (उदाहरण के लिए यदि $F$ दो बार भिन्न है)। यानी यह मान लिया गया है कि किसी के लिए भी $x\in X$ एक खुला उपसमुच्चय है $U\subset X$ ऐसा है कि $x\in U$ और वहां एक स्थिरांक मौजूद है $L>0$ ऐसा कि किसी के लिए भी $\mathbf {x} ,\mathbf {y} \in U$

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

धारण करता है. बाईं ओर का मानदंड कुछ ऑपरेटर मानदंड है जो दाईं ओर के वेक्टर मानदंड के साथ संगत है। इस असमानता को केवल वेक्टर मानदंड का उपयोग करने के लिए फिर से लिखा जा सकता है। फिर किसी भी वेक्टर के लिए $\mathbf {v} \in \mathbb {R} ^{n}$ असमानता

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

अवश्य होल्ड करें।

अब कोई भी प्रारंभिक बिंदु चुनें $\mathbf {x} _{0}\in X$. ये मान लीजिए $F'(\mathbf {x} _{0})$ उलटा है और न्यूटन चरण का निर्माण करता है $\mathbf {h} _{0}=-F'(\mathbf {x} _{0})^{-1}F(\mathbf {x} _{0}).$ अगली धारणा यह है कि केवल अगला बिंदु ही नहीं $\mathbf {x} _{1}=\mathbf {x} _{0}+\mathbf {h} _{0}$ लेकिन पूरी गेंद $B(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)$ सेट के अंदर समाहित है $X$. होने देना $M$ इस गेंद पर जैकोबियन के लिए लिप्सचिट्ज़ स्थिरांक बनें (यह मानते हुए कि यह मौजूद है)।

अंतिम तैयारी के रूप में, जब तक संभव हो, अनुक्रमों का पुनरावर्ती निर्माण करें $(\mathbf {x} _{k})_{k}$, $(\mathbf {h} _{k})_{k}$, $(\alpha _{k})_{k}$ के अनुसार

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

कथन

अब अगर $\alpha _{0}\leq {\tfrac {1}{2}}$ तब

1. एक समाधान $\mathbf {x} ^{*}$ का $F(\mathbf {x} ^{*})=0$ बंद गेंद के अंदर मौजूद है ${\bar {B}}(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)$ और
2. न्यूटन पुनरावृत्ति शुरू हो रही है $\mathbf {x} _{0}$ में एकत्रित हो जाता है $\mathbf {x} ^{*}$ अभिसरण के कम से कम रैखिक क्रम के साथ।

एक कथन जो अधिक सटीक है लेकिन साबित करना थोड़ा अधिक कठिन है, वह जड़ों का उपयोग करता है $t^{\ast }\leq t^{**}$ द्विघात बहुपद का

$p(t)=\left({\tfrac {1}{2}}L\|F'(\mathbf {x} _{0})^{-1}\|^{-1}\right)t^{2}-t+\|\mathbf {h} _{0}\|$,

$t^{\ast /**}={\frac {2\|\mathbf {h} _{0}\|}{1\pm {\sqrt {1-2\alpha _{0}}}}}$

और उनका अनुपात

$\theta ={\frac {t^{*}}{t^{**}}}={\frac {1-{\sqrt {1-2\alpha _{0}}}}{1+{\sqrt {1-2\alpha _{0}}}}}.$

तब

1. एक समाधान $\mathbf {x} ^{*}$ बंद गेंद के अंदर मौजूद है ${\bar {B}}(\mathbf {x} _{1},\theta \|\mathbf {h} _{0}\|)\subset {\bar {B}}(\mathbf {x} _{0},t^{*})$
2. बड़ी गेंद के अंदर यह अनोखा है $B(\mathbf {x} _{0},t^{*\ast })$
3. और समाधान के लिए अभिसरण $F$ द्विघात बहुपद के न्यूटन पुनरावृत्ति के अभिसरण का प्रभुत्व है $p(t)$ अपनी सबसे छोटी जड़ की ओर $t^{\ast }$, अगर $t_{0}=0,\,t_{k+1}=t_{k}-{\tfrac {p(t_{k})}{p'(t_{k})}}$, तब

   $\|\mathbf {x} _{k+p}-\mathbf {x} _{k}\|\leq t_{k+p}-t_{k}.$

4. त्रुटि अनुमान से द्विघात अभिसरण प्राप्त होता है #:$\|\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}\|.$

परिणाम

1986 में, यामामोटो ने साबित किया कि डोरिंग (1969), ओस्ट्रोव्स्की (1971, 1973) जैसे न्यूटन पद्धति के त्रुटि मूल्यांकन, ग्रैग-तापिया (1974), पोट्रा-बर्ड (1980), हनी (1981), पोट्रा (1984), कांटोरोविच प्रमेय से प्राप्त किया जा सकता है।

सामान्यीकरण

कांटोरोविच प्रमेय के लिए एक q-एनालॉग|q-एनालॉग है। अन्य सामान्यीकरणों/विविधताओं के लिए, ओर्टेगा और रीनबोल्ड्ट (1970) देखें।

अनुप्रयोग

ओशी और तानबे ने दावा किया कि कांटोरोविच प्रमेय को रैखिक प्रोग्रामिंग के विश्वसनीय समाधान प्राप्त करने के लिए लागू किया जा सकता है।

अग्रिम पठन

• John H. Hubbard and Barbara Burke Hubbard: Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach, Matrix Editions, ISBN 978-0-9715766-3-6 (preview of 3. edition and sample material including Kant.-thm.)
• Yamamoto, Tetsuro (2001). "Historical Developments in Convergence Analysis for Newton's and Newton-like Methods". In Brezinski, C.; Wuytack, L. (eds.). Numerical Analysis : Historical Developments in the 20th Century. North-Holland. pp. 241–263. ISBN 0-444-50617-9.