कांटोरोविच प्रमेय: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|About the convergence of Newton's method}} कांटोरोविच प्रमेय, या न्यूटन-कांटोरोविच प...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|About the convergence of Newton's method}} | {{Short description|About the convergence of Newton's method}} | ||
कांटोरोविच प्रमेय, या न्यूटन-कांटोरोविच प्रमेय, न्यूटन की विधि के अनुक्रम की अर्ध-स्थानीय सीमा पर एक गणितीय कथन है। यह पहली बार 1948 में [[लियोनिद कांटोरोविच]] द्वारा कहा गया था।<ref name="Deuflhard">{{cite book |first=P. |last=Deuflhard |title=अरेखीय समस्याओं के लिए न्यूटन विधियाँ। एफ़िन इनवेरिएंस और अनुकूली एल्गोरिदम|publisher=Springer |location=Berlin |year=2004 |isbn=3-540-21099-7 |series=Springer Series in Computational Mathematics |volume=35 }}</ref><ref name="Zeidler">{{cite book |last=Zeidler |first=E. |year=1985 |title=Nonlinear Functional Analysis and its Applications: Part 1: Fixed-Point Theorems |location=New York |publisher=Springer |isbn=0-387-96499-1 }}</ref> यह [[बानाच निश्चित-बिंदु प्रमेय]] के रूप के समान है, हालांकि यह एक [[निश्चित बिंदु (गणित)]] के | '''कांटोरोविच प्रमेय''', या न्यूटन-कांटोरोविच प्रमेय, न्यूटन की विधि के अनुक्रम की अर्ध-स्थानीय सीमा पर एक गणितीय कथन है। यह पहली बार 1948 में [[लियोनिद कांटोरोविच]] द्वारा कहा गया था। <ref name="Deuflhard">{{cite book |first=P. |last=Deuflhard |title=अरेखीय समस्याओं के लिए न्यूटन विधियाँ। एफ़िन इनवेरिएंस और अनुकूली एल्गोरिदम|publisher=Springer |location=Berlin |year=2004 |isbn=3-540-21099-7 |series=Springer Series in Computational Mathematics |volume=35 }}</ref><ref name="Zeidler">{{cite book |last=Zeidler |first=E. |year=1985 |title=Nonlinear Functional Analysis and its Applications: Part 1: Fixed-Point Theorems |location=New York |publisher=Springer |isbn=0-387-96499-1 }}</ref> यह [[बानाच निश्चित-बिंदु प्रमेय]] के रूप के समान है, हालांकि यह एक [[निश्चित बिंदु (गणित)]] के स्थान पर किसी फलन के शून्य के अस्तित्व और विशिष्टता को बताता है। <ref>{{cite book |first1=John E. |last1=Dennis |author-link=John E. Dennis |first2=Robert B. |last2=Schnabel |author-link2=Robert B. Schnabel |chapter=The Kantorovich and Contractive Mapping Theorems |title=अप्रतिबंधित अनुकूलन और अरेखीय समीकरणों के लिए संख्यात्मक तरीके|location=Englewood Cliffs |publisher=Prentice-Hall |year=1983 |pages=92–94 |isbn=0-13-627216-9 |chapter-url=https://books.google.com/books?id=ksvJTtJCx9cC&pg=PA92 }}</ref> न्यूटन की विधि बिंदुओं का एक अनुक्रम बनाती है जो कुछ स्तिथियों के अंतर्गत समीकरण <math>f(x)=0</math> के विलयन x या समीकरण <math>F(x)=0</math> की प्रणाली के सदिश विलयन में परिवर्तित हो जाएगी। कांटोरोविच प्रमेय इस अनुक्रम के प्रारंभिक बिंदु पर स्थितियाँ देता है। यदि वे स्थितियाँ पूरी हो जाती हैं तो प्रारंभिक बिंदु के करीब एक विलयन सदिश होता है और अनुक्रम उस बिंदु पर परिवर्तित हो जाता है। <ref name="Deuflhard"/><ref name="Zeidler"/> | ||
न्यूटन की विधि बिंदुओं का एक | |||
== | ==पुर्वानुमान == | ||
मान लीजिये <math>X\subset\R^n</math> एक विवृत उपसमुच्चय है और <math>F:X \subset \R^n \to\R^n</math> [[जैकोबियन मैट्रिक्स और निर्धारक]] के साथ एक अवकलनीय फलन <math>F^{\prime}(\mathbf x)</math> स्थानीय रूप से [[लिप्सचिट्ज़ निरंतर]] है (उदाहरण के लिए यदि <math>F</math> दो बार भिन्न है)। यानी यह मान लिया गया है कि किसी <math>x \in X</math> के लिए भी एक विवृत उपसमुच्चय <math>U\subset X</math> इस प्रकार है कि <math>x \in U</math> और वहां एक स्थिरांक सदिश <math>L>0</math> इस प्रकार है कि किसी <math>\mathbf x,\mathbf y\in U</math> के लिए निम्न | |||
:<math>\|F'(\mathbf x)-F'(\mathbf y)\|\le L\;\|\mathbf x-\mathbf y\|</math> | :<math>\|F'(\mathbf x)-F'(\mathbf y)\|\le L\;\|\mathbf x-\mathbf y\|</math> | ||
धारण करता | धारण करता है। बाईं ओर का मानदंड कुछ संचालक मानदंड है जो दाईं ओर के सदिश मानदंड के साथ संगत है। इस असमानता को केवल सदिश मानदंड का उपयोग करने के लिए फिर से लिखा जा सकता है। फिर किसी भी सदिश के लिए <math>\mathbf v\in\R^n</math> असमता | ||
:<math>\|F'(\mathbf x)(\mathbf v)-F'(\mathbf y)(\mathbf v)\|\le L\;\|\mathbf x-\mathbf y\|\,\|\mathbf v\|</math> | :<math>\|F'(\mathbf x)(\mathbf v)-F'(\mathbf y)(\mathbf v)\|\le L\;\|\mathbf x-\mathbf y\|\,\|\mathbf v\|</math> | ||
अवश्य | अवश्य धारण करता है। | ||
अब कोई भी प्रारंभिक बिंदु | अब कोई भी प्रारंभिक बिंदु <math>\mathbf x_0\in X</math> चुनें। मान लीजिए <math>F'(\mathbf x_0)</math> उलटा है और न्यूटन चरण <math>\mathbf h_0=-F'(\mathbf x_0)^{-1}F(\mathbf x_0)</math> का निर्माण करता है। | ||
अंतिम तैयारी के रूप में, जब तक संभव हो, अनुक्रमों का पुनरावर्ती निर्माण | अगली धारणा यह है कि केवल अगला बिंदु <math>\mathbf x_1=\mathbf x_0+\mathbf h_0</math> ही नहीं लेकिन पूरी गोलक <math>B(\mathbf x_1,\|\mathbf h_0\|)</math> सम्मुच्चय <math>X</math> के अंदर समाहित है। मान लीजिये <math>M</math> इस गोलक पर जैकोबियन के लिए लिप्सचिट्ज़ स्थिरांक बनें (यह मानते हुए कि यह सदिश है)। | ||
अंतिम तैयारी के रूप में, जब तक संभव हो, अनुक्रमों का पुनरावर्ती निर्माण <math>(\mathbf x_k)_k</math>, <math>(\mathbf h_k)_k</math>, <math>(\alpha_k)_k</math> के अनुसार करें | |||
:<math>\begin{alignat}{2} | :<math>\begin{alignat}{2} | ||
\mathbf h_k&=-F'(\mathbf x_k)^{-1}F(\mathbf x_k)\\[0.4em] | \mathbf h_k&=-F'(\mathbf x_k)^{-1}F(\mathbf x_k)\\[0.4em] | ||
| Line 25: | Line 25: | ||
== कथन == | == कथन == | ||
अब अगर <math>\alpha_0\le\tfrac12</math> तब | अब अगर <math>\alpha_0\le\tfrac12</math> तब | ||
#एक | #एक विलयन <math>\mathbf x^*</math> का <math>F(\mathbf x^*)=0</math> सवृत गोलक के अंदर सदिश <math>\bar B(\mathbf x_1,\|\mathbf h_0\|)</math> है और | ||
#न्यूटन पुनरावृत्ति शुरू हो रही है <math>\mathbf x_0</math> में एकत्रित हो जाता है <math>\mathbf x^*</math> अभिसरण के कम से कम रैखिक क्रम के साथ। | #'''न्यूटन पुनरावृत्ति''' शुरू हो रही है <math>\mathbf x_0</math> में एकत्रित हो जाता है <math>\mathbf x^*</math> अभिसरण के कम से कम रैखिक क्रम के साथ। | ||
एक कथन जो अधिक सटीक है लेकिन साबित करना थोड़ा अधिक कठिन है, वह जड़ों का उपयोग करता है <math>t^\ast\le t^{**}</math> द्विघात बहुपद का | एक कथन जो अधिक सटीक है लेकिन साबित करना थोड़ा अधिक कठिन है, वह जड़ों का उपयोग करता है <math>t^\ast\le t^{**}</math> द्विघात बहुपद का | ||
| Line 42: | Line 42: | ||
</math> | </math> | ||
तब | तब | ||
#एक | #एक विलयन <math>\mathbf x^*</math> सवृत गोलक के अंदर सदिश है <math>\bar B(\mathbf x_1,\theta\|\mathbf h_0\|)\subset\bar B(\mathbf x_0,t^*)</math> | ||
#बड़ी | #बड़ी गोलक के अंदर यह अनोखा है <math>B(\mathbf x_0,t^{*\ast})</math> | ||
#और | #और विलयन के लिए अभिसरण <math>F</math> द्विघात बहुपद के न्यूटन पुनरावृत्ति के अभिसरण का प्रभुत्व है <math>p(t)</math> अपनी सबसे छोटी जड़ की ओर <math>t^\ast</math>,<ref>{{cite journal |first=J. M. |last=Ortega |title=न्यूटन-कैंटोरोविच प्रमेय|journal=Amer. Math. Monthly |volume=75 |year=1968 |issue=6 |pages=658–660 |jstor=2313800 |doi=10.2307/2313800}}</ref> अगर <math>t_0=0,\,t_{k+1}=t_k-\tfrac{p(t_k)}{p'(t_k)}</math>, तब | ||
#:<math>\|\mathbf x_{k+p}-\mathbf x_k\|\le t_{k+p}-t_k.</math> | #:<math>\|\mathbf x_{k+p}-\mathbf x_k\|\le t_{k+p}-t_k.</math> | ||
#त्रुटि अनुमान से द्विघात अभिसरण प्राप्त होता है<ref>{{cite journal |first1=W. B. |last1=Gragg |first2=R. A. |last2=Tapia |year=1974 |title=न्यूटन-कैंटोरोविच प्रमेय के लिए इष्टतम त्रुटि सीमाएं|journal=SIAM Journal on Numerical Analysis |volume=11 |issue=1 |pages=10–13 |jstor=2156425 |doi=10.1137/0711002|bibcode=1974SJNA...11...10G }}</ref> #:<math> | #त्रुटि अनुमान से द्विघात अभिसरण प्राप्त होता है<ref>{{cite journal |first1=W. B. |last1=Gragg |first2=R. A. |last2=Tapia |year=1974 |title=न्यूटन-कैंटोरोविच प्रमेय के लिए इष्टतम त्रुटि सीमाएं|journal=SIAM Journal on Numerical Analysis |volume=11 |issue=1 |pages=10–13 |jstor=2156425 |doi=10.1137/0711002|bibcode=1974SJNA...11...10G }}</ref> #:<math> | ||
| Line 62: | Line 62: | ||
==अनुप्रयोग== | ==अनुप्रयोग== | ||
ओशी और तानबे ने दावा किया कि कांटोरोविच प्रमेय को [[रैखिक प्रोग्रामिंग]] के विश्वसनीय | ओशी और तानबे ने दावा किया कि कांटोरोविच प्रमेय को [[रैखिक प्रोग्रामिंग]] के विश्वसनीय विलयन प्राप्त करने के लिए लागू किया जा सकता है।<ref>{{cite journal |last1=Oishi |first1=S. |last2=Tanabe |first2=K. |year=2009 |title=रैखिक प्रोग्रामिंग के लिए इष्टतम बिंदु का संख्यात्मक समावेशन|journal=JSIAM Letters |volume=1 |pages=5–8 |doi=10.14495/jsiaml.1.5 |doi-access=free }}</ref> | ||
Revision as of 00:10, 29 July 2023
कांटोरोविच प्रमेय, या न्यूटन-कांटोरोविच प्रमेय, न्यूटन की विधि के अनुक्रम की अर्ध-स्थानीय सीमा पर एक गणितीय कथन है। यह पहली बार 1948 में लियोनिद कांटोरोविच द्वारा कहा गया था। [1][2] यह बानाच निश्चित-बिंदु प्रमेय के रूप के समान है, हालांकि यह एक निश्चित बिंदु (गणित) के स्थान पर किसी फलन के शून्य के अस्तित्व और विशिष्टता को बताता है। [3] न्यूटन की विधि बिंदुओं का एक अनुक्रम बनाती है जो कुछ स्तिथियों के अंतर्गत समीकरण के विलयन x या समीकरण की प्रणाली के सदिश विलयन में परिवर्तित हो जाएगी। कांटोरोविच प्रमेय इस अनुक्रम के प्रारंभिक बिंदु पर स्थितियाँ देता है। यदि वे स्थितियाँ पूरी हो जाती हैं तो प्रारंभिक बिंदु के करीब एक विलयन सदिश होता है और अनुक्रम उस बिंदु पर परिवर्तित हो जाता है। [1][2]
पुर्वानुमान
मान लीजिये एक विवृत उपसमुच्चय है और जैकोबियन मैट्रिक्स और निर्धारक के साथ एक अवकलनीय फलन स्थानीय रूप से लिप्सचिट्ज़ निरंतर है (उदाहरण के लिए यदि दो बार भिन्न है)। यानी यह मान लिया गया है कि किसी के लिए भी एक विवृत उपसमुच्चय इस प्रकार है कि और वहां एक स्थिरांक सदिश इस प्रकार है कि किसी के लिए निम्न
धारण करता है। बाईं ओर का मानदंड कुछ संचालक मानदंड है जो दाईं ओर के सदिश मानदंड के साथ संगत है। इस असमानता को केवल सदिश मानदंड का उपयोग करने के लिए फिर से लिखा जा सकता है। फिर किसी भी सदिश के लिए असमता
अवश्य धारण करता है।
अब कोई भी प्रारंभिक बिंदु चुनें। मान लीजिए उलटा है और न्यूटन चरण का निर्माण करता है।
अगली धारणा यह है कि केवल अगला बिंदु ही नहीं लेकिन पूरी गोलक सम्मुच्चय के अंदर समाहित है। मान लीजिये इस गोलक पर जैकोबियन के लिए लिप्सचिट्ज़ स्थिरांक बनें (यह मानते हुए कि यह सदिश है)।
अंतिम तैयारी के रूप में, जब तक संभव हो, अनुक्रमों का पुनरावर्ती निर्माण , , के अनुसार करें
कथन
अब अगर तब
- एक विलयन का सवृत गोलक के अंदर सदिश है और
- न्यूटन पुनरावृत्ति शुरू हो रही है में एकत्रित हो जाता है अभिसरण के कम से कम रैखिक क्रम के साथ।
एक कथन जो अधिक सटीक है लेकिन साबित करना थोड़ा अधिक कठिन है, वह जड़ों का उपयोग करता है द्विघात बहुपद का
- ,
और उनका अनुपात
तब
- एक विलयन सवृत गोलक के अंदर सदिश है
- बड़ी गोलक के अंदर यह अनोखा है
- और विलयन के लिए अभिसरण द्विघात बहुपद के न्यूटन पुनरावृत्ति के अभिसरण का प्रभुत्व है अपनी सबसे छोटी जड़ की ओर ,[4] अगर , तब
- त्रुटि अनुमान से द्विघात अभिसरण प्राप्त होता है[5] #:
परिणाम
1986 में, यामामोटो ने साबित किया कि डोरिंग (1969), ओस्ट्रोव्स्की (1971, 1973) जैसे न्यूटन पद्धति के त्रुटि मूल्यांकन,[6][7] ग्रैग-तापिया (1974), पोट्रा-बर्ड (1980),[8] हनी (1981),[9] पोट्रा (1984),[10] कांटोरोविच प्रमेय से प्राप्त किया जा सकता है।[11]
सामान्यीकरण
कांटोरोविच प्रमेय के लिए एक q-एनालॉग|q-एनालॉग है।[12][13] अन्य सामान्यीकरणों/विविधताओं के लिए, ओर्टेगा और रीनबोल्ड्ट (1970) देखें।[14]
अनुप्रयोग
ओशी और तानबे ने दावा किया कि कांटोरोविच प्रमेय को रैखिक प्रोग्रामिंग के विश्वसनीय विलयन प्राप्त करने के लिए लागू किया जा सकता है।[15]
संदर्भ
- ↑ 1.0 1.1 Deuflhard, P. (2004). अरेखीय समस्याओं के लिए न्यूटन विधियाँ। एफ़िन इनवेरिएंस और अनुकूली एल्गोरिदम. Springer Series in Computational Mathematics. Vol. 35. Berlin: Springer. ISBN 3-540-21099-7.
- ↑ 2.0 2.1 Zeidler, E. (1985). Nonlinear Functional Analysis and its Applications: Part 1: Fixed-Point Theorems. New York: Springer. ISBN 0-387-96499-1.
- ↑ Dennis, John E.; Schnabel, Robert B. (1983). "The Kantorovich and Contractive Mapping Theorems". अप्रतिबंधित अनुकूलन और अरेखीय समीकरणों के लिए संख्यात्मक तरीके. Englewood Cliffs: Prentice-Hall. pp. 92–94. ISBN 0-13-627216-9.
- ↑ Ortega, J. M. (1968). "न्यूटन-कैंटोरोविच प्रमेय". Amer. Math. Monthly. 75 (6): 658–660. doi:10.2307/2313800. JSTOR 2313800.
- ↑ Gragg, W. B.; Tapia, R. A. (1974). "न्यूटन-कैंटोरोविच प्रमेय के लिए इष्टतम त्रुटि सीमाएं". SIAM Journal on Numerical Analysis. 11 (1): 10–13. Bibcode:1974SJNA...11...10G. doi:10.1137/0711002. JSTOR 2156425.
- ↑ Ostrowski, A. M. (1971). "बानाच स्थानों में न्यूटन की विधि". C. R. Acad. Sci. Paris. 27 (A): 1251–1253.
- ↑ Ostrowski, A. M. (1973). यूक्लिडियन और बानाच स्पेस में समीकरणों का समाधान. New York: Academic Press. ISBN 0-12-530260-6.
- ↑ Potra, F. A.; Ptak, V. (1980). "न्यूटन की प्रक्रिया के लिए तीव्र त्रुटि सीमाएँ". Numer. Math. 34: 63–72. doi:10.1007/BF01463998.
- ↑ Miel, G. J. (1981). "न्यूटन की विधि के लिए कांटोरोविच प्रमेय का एक अद्यतन संस्करण". Computing. 27 (3): 237–244. doi:10.1007/BF02237981.
- ↑ Potra, F. A. (1984). "न्यूटन की विधि के लिए पश्चवर्ती त्रुटि अनुमान पर". Beiträge zur Numerische Mathematik. 12: 125–138.
- ↑ Yamamoto, T. (1986). "कांटोरोविच मान्यताओं के तहत न्यूटन की विधि के लिए तीव्र त्रुटि सीमाएं खोजने की एक विधि". Numerische Mathematik. 49 (2–3): 203–220. doi:10.1007/BF01389624.
- ↑ Rajkovic, P. M.; Stankovic, M. S.; Marinkovic, S. D. (2003). "समीकरणों और प्रणालियों को हल करने के लिए q-पुनरावृत्तीय तरीकों पर". Novi Sad J. Math. 33 (2): 127–137.
- ↑ Rajković, P. M.; Marinković, S. D.; Stanković, M. S. (2005). "On q-Newton–Kantorovich method for solving systems of equations". Applied Mathematics and Computation. 168 (2): 1432–1448. doi:10.1016/j.amc.2004.10.035.
- ↑ Ortega, J. M.; Rheinboldt, W. C. (1970). अनेक चरों में अरेखीय समीकरणों का पुनरावृत्तीय समाधान. SIAM. OCLC 95021.
- ↑ Oishi, S.; Tanabe, K. (2009). "रैखिक प्रोग्रामिंग के लिए इष्टतम बिंदु का संख्यात्मक समावेशन". JSIAM Letters. 1: 5–8. doi:10.14495/jsiaml.1.5.
अग्रिम पठन
- 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.
