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

कांटोरोविच प्रमेय, या न्यूटन-कांटोरोविच प्रमेय, न्यूटन की विधि के अनुक्रम की अर्ध-स्थानीय सीमा पर एक गणितीय कथन है। यह पहली बार 1948 में लियोनिद कांटोरोविच द्वारा कहा गया था। यह बानाच निश्चित-बिंदु प्रमेय के रूप के समान है, हालांकि यह एक निश्चित बिंदु (गणित) के स्थान पर किसी फलन के शून्य के अस्तित्व और विशिष्टता को बताता है। न्यूटन की विधि बिंदुओं का एक अनुक्रम बनाती है जो कुछ स्तिथियों के अंतर्गत समीकरण $f(x)=0$ के विलयन x या समीकरण $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.