क्वासी-न्यूटनियन तरीके, या जब एथोस के लिए बहुत अधिक दूसरी व्युत्पन्नियाँ हैं

अर्ध-न्यूटोनियन विधियों के साथ पहले परिचित पर एक दो बार आश्चर्य हो सकता है। सबसे पहले, सूत्रों पर एक त्वरित नज़र डालने के बाद, संदेह पैदा होता है कि यह बिल्कुल काम कर सकता है। हालांकि, वे काम करते हैं। आगे यह संदिग्ध लगता है कि वे अच्छी तरह से काम करेंगे। और यह सब और अधिक आश्चर्य की बात है कि विशेष रूप से निर्मित कार्यों पर नहीं, बल्कि अभ्यास से लिए गए वास्तविक लोगों पर, विभिन्न प्रकार के ढाल वंश की तुलना में वे कितने तेज हैं। और अगर इसके बाद भी ब्याज के साथ मिश्रित संदेह हैं, तो आपको यह समझने की आवश्यकता है कि यह सब कुछ क्यों काम करता है।

न्यूटन विधि सहित ढाल के तरीकों को चलाने वाले मूल और मूल विचारों पर पहले ही विचार किया जा चुका है । अर्थात्, हम वर्तमान स्थिति के आसपास के क्षेत्र में कार्य के व्यवहार के बारे में जानकारी पर निर्भर थे, जो हमें एक सरल गणितीय विश्लेषण देता है। कम से कम, यह मान लिया गया था कि पहले डेरिवेटिव पर जानकारी हमारे पास उपलब्ध थी। क्या होगा अगर यह सब हमारे लिए उपलब्ध है? क्या क्रमिक वंश हमारी सजा है? बेशक, हां, जब तक आप अचानक याद नहीं करते हैं कि हम एक ऐसी प्रक्रिया से निपट रहे हैं जिसमें उद्देश्य फ़ंक्शन ठीक से संसाधित है। और यदि ऐसा है, तो हम अपनी सतह पर चलने के लिए फ़ंक्शन के व्यवहार के बारे में संचित जानकारी का उपयोग क्यों नहीं करते हैं ताकि इसकी सतह थोड़ी कम अंधा हो?

मार्ग के बारे में जानकारी का उपयोग करने का विचार ज्यादातर तरीकों के दिल में निहित है ताकि वंश के तरीकों को तेज किया जा सके। यह आलेख सबसे प्रभावी में से एक पर चर्चा करता है, हालांकि इस तरह की जानकारी के लिए सबसे सस्ता, लेखांकन का तरीका नहीं है, जिससे क्वैसी-न्यूटोनियन तरीकों का विचार होता है।

यह समझने के लिए कि अर्ध-न्यूटोनियन विधियों के पैर कहाँ बढ़ते हैं और नाम कहाँ से आता है, हमें फिर से स्थिर बिंदु समीकरण के प्रत्यक्ष समाधान के आधार पर न्यूनतमकरण विधि पर लौटना होगा । जिस तरह इस समीकरण के समाधान के लिए लागू न्यूटन पद्धति के विचार ने हमें उसी नाम की अनुकूलन विधि की ओर अग्रसर किया (जो कि इसके पूर्वज के विपरीत, अभिसरण का एक वैश्विक क्षेत्र है), हम उम्मीद कर सकते हैं कि नॉनलाइन समीकरणों के सिस्टम को हल करने के लिए अन्य तरीकों पर विचार करना सार्थक होगा। अन्य अनुकूलन विधियों के निर्माण के लिए विचारों की योजना बनाएं।

सुरक्षित तरीके

आपको याद दिला दूं कि समीकरणों की प्रणाली को हल करने के लिए न्यूटन विधि , समाधान के करीब कुछ बिंदु के पड़ोस में प्रतिस्थापन पर आधारित है कार्यों इसके रैखिक सन्निकटन जहाँ एक रैखिक ऑपरेटर है, जो, जब एक वेक्टर है और प्रत्येक चर के संबंध में आंशिक व्युत्पन्न है, जैकोबी मैट्रिक्स के साथ मेल खाता है । अगला, समीकरण हल हो गया है और बिंदु वांछित समाधान के लिए एक नए सन्निकटन के रूप में लिया गया। यह सरल है और यह काम करता है।

लेकिन क्या होगा अगर हम किसी कारण से जैकोबी मैट्रिक्स की गणना नहीं कर सकते हैं? इस मामले में पहली बात जो दिमाग में आती है वह यह है कि अगर हम आंशिक रूप से डेरिवेटिव की गणना नहीं कर सकते हैं, तो हम उनके लिए एक संख्यात्मक अनुमान प्राप्त कर सकते हैं। इस तरह के सन्निकटन के लिए सबसे सरल (यद्यपि कोई मतलब नहीं है) विकल्प सही परिमित अंतर का सूत्र हो सकता है: जहाँ जेथ बेस वेक्टर है। इस तरह के सन्निकटन से बने मैट्रिक्स को निरूपित किया जाएगा । कितना प्रतिस्थापन का विश्लेषण पर न्यूटन की विधि में, इसका अभिसरण प्रभावित होता है, काफी बड़ी संख्या में कार्य समर्पित होते हैं, लेकिन इस मामले में हम दूसरे पहलू में रुचि रखते हैं। अर्थात्, इस तरह के सन्निकटन के लिए एन अतिरिक्त बिंदुओं पर फ़ंक्शन की गणना की आवश्यकता होती है, और, इसके अलावा, फ़ंक्शन इन बिंदुओं पर फ़ंक्शन को प्रक्षेपित करता है , यानी।



जैकोबी मैट्रिक्स के प्रत्येक सन्निकटन में यह गुण नहीं होता है, लेकिन इस गुण वाले एक अनुकार फ़ंक्शन के प्रत्येक मैट्रिक्स में जैकोबी मैट्रिक्स का एक अनुमान होता है। वास्तव में, यदि और तब पर । यह संपत्ति, अर्थात् प्रक्षेप संपत्ति, हमें न्यूटन विधि को सामान्य बनाने का एक रचनात्मक तरीका देती है।

चलो - आवश्यकता को पूरा करते हुए कार्य करें रैखिक स्वतंत्र वैक्टर की कुछ प्रणाली के लिए । तब इस तरह के फंक्शन को एक सिक्योर फंक्शन कहा जाता है , और समीकरण जो इसे परिभाषित करता है, वह धर्मनिरपेक्ष समीकरण है । अगर वैक्टर की व्यवस्था पूर्ण है (अर्थात, उनमें से बिल्कुल एन हैं और वे अभी भी रैखिक रूप से स्वतंत्र हैं), और, इसके अलावा, वैक्टर की प्रणाली रैखिक तो स्वतंत्र है विशिष्ट रूप से परिभाषित किया गया।

समीकरण के स्थानीय परिवर्तन पर आधारित कोई भी विधि फार्म का समीकरण जहाँ secant समीकरण को संतुष्ट करता है , जिसे secant method कहा जाता है ।

सबसे तर्कसंगत तरीके से किसी फ़ंक्शन के लिए सेकंडक का निर्माण करने के तरीके के बारे में एक निष्पक्ष प्रश्न उठता है। । तर्क की निम्न पंक्ति स्पष्ट प्रतीत होती है: बिंदु x पर एक प्रतिरूप मॉडल का निर्माण करें जो बिंदुओं पर दिए गए फ़ंक्शन को प्रक्षेपित करता है । समीकरण समाधान हमें एक नया बिंदु देता है । फिर एक बिंदु पर एक affine मॉडल बनाने के लिए प्रक्षेप बिंदुओं को चुनना सबसे उचित है ताकि मूल्य पहले से ही ज्ञात - वह है, उन्हें सेट से ले जाना । अलग-अलग विकल्प हैं जिनके लिए पहले से उपयोग किए गए कई में से चुनने के लिए अंक हैं। उदाहरण के लिए, आप प्रक्षेप बिंदु के रूप में ले सकते हैं जिसमें कम से कम या सिर्फ पहली बात अंक। किसी भी मामले में, यह स्पष्ट है कि लगता है नए एफाइन मॉडल के लिए कई प्रक्षेप बिंदुओं में शामिल होना चाहिए। तो परे हमारे सेट में पुनरावृत्ति प्रक्रिया के चरण तक हो सकते हैं पहले पारित बिंदुओं पर निर्मित विस्थापन। यदि इस प्रक्रिया का निर्माण इस तरह से किया जाता है कि नया affine मॉडल उपयोग नहीं करता है पिछले मानों के बाद, फिर ऐसी प्रक्रिया को p-point secant विधि कहा जाता है।

पहली नज़र में, ऐसा लग सकता है कि न्यू-पॉइंट की जगह के लिए एन-पॉइंट सेकेंडरी पद्धति सबसे अच्छा उम्मीदवार है, क्योंकि यह उन सूचनाओं का अधिकतम उपयोग करता है जो हम हल करने की प्रक्रिया में प्राप्त करते हैं, जबकि अतिरिक्त गणनाओं की संख्या को कम करते हैं - हम बाद में फ़ंक्शन के मूल्य का उपयोग करते हैं। एन अंक पारित किया। दुर्भाग्य से, ऐसा नहीं है। बात यह है कि वेक्टर प्रणाली हठपूर्वक पर्याप्त रूप से बड़े एन के साथ रैखिक रूप से स्वतंत्र होने से इंकार करता है। इसके अलावा, भले ही यह स्थिति पूरी हो जाए और संबंधित एफाइन मॉडल अभी भी मौजूद है, तो एक मौका है कि निर्देश यह भी रैखिक स्वतंत्र साबित होता है, यह और भी कम हो जाता है। और यह इस तथ्य पर जोर देता है कि एफाइन मॉडल, हालांकि यह मौजूद है, पतित और व्यावहारिक रूप से अनुपयुक्त है।

सामान्य तौर पर, सबसे स्थिर 2-बिंदु सेकेंड विधि है। यही है, एक विधि जिसमें प्रत्येक पुनरावृत्ति पर हमें फ़ंक्शन के अतिरिक्त एन -1 मूल्यों की गणना करना होगा। यह स्पष्ट रूप से हमारे व्यावहारिक उद्देश्यों के लिए उपयुक्त नहीं है।

फिर सवाल है - यह सब क्या था?

समीकरणों को हल करने के लिए क्वैसी-न्यूटनियन तरीके

बाहर का रास्ता सरल है, हालांकि स्पष्ट नहीं है। यदि हमारे पास तकनीकी क्षमता नहीं है, तो पहले से गणना किए गए मानों के आधार पर, प्रतिध्वनी मॉडल को निर्धारित करने के लिए, जो कि समीकरण को संतुष्ट करता है, तो यह आवश्यक नहीं है। हम एक आधार के रूप में सेकेंडरों के समीकरण को लेते हैं, लेकिन हमें आवश्यकता होगी कि यह केवल वैक्टरों की कुछ अधूरी प्रणाली के लिए संतुष्ट हो । दूसरे शब्दों में, हमें आवश्यकता होगी कि प्रक्षेप की स्थिति केवल ज्ञात मूल्यों की पर्याप्त संख्या के लिए संतुष्ट हो। बेशक, इस मामले में हम अब गारंटी नहीं दे सकते हैं कि इस तरह के मॉडल में प्रयुक्त मैट्रिक्स जैकोबी मैट्रिक्स की ओर बढ़ेगा, लेकिन हमें इसकी आवश्यकता नहीं होगी। इसे जोड़कर, एफाइन मॉडल को वर्तमान बिंदु पर फ़ंक्शन को प्रक्षेपित करना होगा, अर्थात। , हम धर्मनिरपेक्ष विधि के निम्नलिखित सूत्रीकरण प्राप्त करते हैं:



ब्रिडेन ने एम = 1 के लिए इस तरह के तरीकों पर विचार करने वाला पहला था, उन्हें क्वैसी-न्यूटनियन कहा। यह स्पष्ट है कि इस मामले में सुरक्षित स्थिति हमें मैट्रिक्स की विशिष्ट पहचान करने की अनुमति देती है केवल अगर अतिरिक्त शर्तें उस पर थोप दी जाती हैं, और ऐसी प्रत्येक अतिरिक्त स्थिति एक अलग विधि को जन्म देती है। ब्रायडेन ने खुद को इस प्रकार बताया:

दिशा में आंदोलन के रूप में बिंदु से इस बिंदु पर फ़ंक्शन को अन्य के अलावा कैसे बदलता है, इस पर हमें कोई अतिरिक्त जानकारी नहीं देता है निर्देश, फिर वेक्टर पर नए एफाइन फ़ंक्शन का प्रभाव एक ही वेक्टर पर पुराने फ़ंक्शन के प्रभाव से कम अलग होना चाहिए से । अंतिम उपाय के रूप में, जब ओर्थोगोनल नए फ़ंक्शन का व्यवहार पुराने के व्यवहार से अलग नहीं होना चाहिए।

ब्रीडेन का विचार अपनी सादगी में शानदार है। वास्तव में, यदि हमारे पास फ़ंक्शन के व्यवहार के बारे में नई जानकारी नहीं है, तो हम जो सबसे अच्छा कर सकते हैं वह पुराने को बेईमानी से न करने की कोशिश है। फिर अतिरिक्त स्थिति

सभी के लिए ऐसा है

आपको नए परिवर्तन के मैट्रिक्स को विशिष्ट रूप से निर्धारित करने की अनुमति देता है - यह पुराने मैट्रिक्स में रैंक 1 सुधार जोड़कर प्राप्त किया जाता है।



हालांकि, ब्रिडेन द्वारा किए गए निष्कर्षों की सादगी और निरंतरता के बावजूद, वे फुलक्रम प्रदान नहीं करते हैं जो अन्य समान तरीकों के निर्माण के लिए आधार के रूप में काम कर सकते हैं। सौभाग्य से, उनके विचार की एक अधिक औपचारिक अभिव्यक्ति है। अर्थात्, इस तरह से निर्मित मैट्रिक्स निम्नलिखित समस्या का समाधान निकला:



कार्य बाधा कुछ भी नहीं है, लेकिन एकांत समीकरण, और न्यूनता स्थिति मैट्रिक्स में अधिक से अधिक जानकारी को बचाने की हमारी इच्छा को दर्शाती है। । इस मामले में मेट्रिसेस के बीच विसंगति का माप फ्रोबेनियस मानदंड है, जिसमें समस्या का हल एक अस्पष्ट समाधान है। यह सूत्रीकरण अन्य तरीकों के निर्माण के लिए एक प्रारंभिक बिंदु के रूप में अच्छी तरह से काम कर सकता है। अर्थात्, हम दोनों माप को बदल सकते हैं जिसके द्वारा हम शुरू किए गए परिवर्तनों का मूल्यांकन करते हैं और मैट्रिक्स पर लगाए गए शर्तों को कसते हैं। सामान्य तौर पर, कोई पहले से ही इस तरह की विधि के साथ काम कर सकता है।

क्वासी-न्यूटन ऑप्टिमाइज़ेशन मेथड्स

मुख्य विचार को समझने के बाद, हम अंत में अनुकूलन समस्याओं पर लौट सकते हैं और नोटिस कर सकते हैं कि ब्रूडेन फॉर्मूला लागू करने से एफलाइन मॉडल को फिर से जोड़ने के लिए हमारे काम में बहुत अच्छी तरह फिट नहीं होते हैं। वास्तव में, ग्रेडिएंट फ़ंक्शन का पहला व्युत्पन्न हेसियन मैट्रिक्स के अलावा और कुछ नहीं है, जो निर्माण द्वारा सममित है। उसी समय, ब्रुयडेन नियम के अनुसार अद्यतन करने से एक असममित मैट्रिक्स होता है भले ही सममित था। इसका मतलब यह नहीं है कि स्थिर बिंदु समीकरण को हल करने के लिए ब्रूडेन विधि को लागू नहीं किया जा सकता है, लेकिन इस तरह के एक अद्यतन नियम के आधार पर, हम अच्छे अनुकूलन तरीकों का निर्माण करने में सक्षम होने की संभावना नहीं है। सामान्य तौर पर, यह काफी स्पष्ट है कि अर्ध-न्यूटन विधि को बेहतर काम करना चाहिए, समस्या की परिस्थितियों की प्रणाली को अधिक सटीक रूप से एक विशिष्ट जैकोबी मैट्रिक्स की बारीकियों का वर्णन करना चाहिए।

इस खामी को ठीक करने के लिए, हम ब्रुडेन न्यूनीकरण की समस्या के लिए एक अतिरिक्त बाधा जोड़ते हैं, स्पष्ट रूप से आवश्यक है कि नए मैट्रिक्स पुराने के साथ सममित हों:



इस समस्या का हल है



यहां , और मैट्रिक्स पुनर्गणना सूत्र को इसके रचनाकारों के नाम पर रखा गया है - पॉवेल, शन्नो और ब्रुईडेन (पीएसबी)। परिणामी मैट्रिक्स सममित है, लेकिन स्पष्ट रूप से सकारात्मक निश्चित नहीं है, अगर केवल अचानक मिलीभगत नहीं होगी । और हमने देखा कि अनुकूलन विधियों में सकारात्मक निश्चितता अत्यधिक वांछनीय है।

फिर, हम समस्या की स्थिति को ठीक कर देंगे, इस बार मैट्रिक्स डायवर्जन के माप के रूप में स्केलड फ्रोबेनियस मानदंड का उपयोग करें।



प्रश्न के ऐसे कथन की उत्पत्ति एक अलग बड़ा विषय है, लेकिन यह दिलचस्प है कि यदि मैट्रिक्स टी ऐसा है (अर्थात्, जी एक एफाइन ट्रांसफॉर्मेशन मैट्रिक्स भी है जो दिशा p के लिए सेकंड समीकरण को संतुष्ट करता है), तो इस समस्या का समाधान T की पसंद से स्वतंत्र हो जाता है और अपडेट फॉर्मूला की ओर जाता है



डेविडन-फ्लेचर-पॉवेल फॉर्मूला के रूप में जाना जाता है। इस अद्यतन विधि ने व्यवहार में खुद को साबित कर दिया है, क्योंकि इसमें निम्न गुण हैं:

अगर और सकारात्मक निश्चित है सकारात्मक रूप से भी पहचाना गया।

मैं इसके बाद ध्यान देता हूं कि यदि पहली शर्त पूरी नहीं होती है, तो एक सकारात्मक निश्चित मैट्रिक्स के साथ एक एफाइन फ़ंक्शन मौजूद नहीं है जो कि धर्मनिरपेक्ष समीकरण को संतुष्ट करता है।

यदि डीएफपी पद्धति के कारण होने वाली समस्या में, हम एफाइन मॉडल की विसंगति को मापते हैं, तो स्वयं मैट्रिसेस के बीच की दूरी नहीं होती है, लेकिन मैट्रिसेस के विपरीत, हम फॉर्म की समस्या प्राप्त करते हैं।



इसका समाधान एक प्रसिद्ध सूत्र है, जिसकी खोज लगभग एक साथ ब्रीडेन, फ्लेचर, गोल्डफर्ब और शन्नो (बीएफजीएस) ने की है।



आज तक, यह माना जाता है कि इस सूत्र के अनुसार पुनर्गणना एक कम्प्यूटेशनल बिंदु से सबसे अधिक कुशल है और एक ही समय में बड़ी संख्या में पुनरावृत्तियों के साथ मैट्रिक्स के अध: पतन की संभावना कम है। डीएफपी के समान शर्तों के तहत, यह सूत्र सकारात्मक निश्चितता की संपत्ति को संरक्षित करता है।

मैट्रिक्स को अपडेट करने के सभी वर्णित तरीकों को रैंक 2 के सुधार की आवश्यकता है। यह मैट्रिक्स को पलटना आसान और आसान बनाता है शर्मन-मॉरिसन सूत्र और मूल्य का उपयोग करना ।



बशर्ते कि सूत्र का भाजक nonzero हो। मैं सूचीबद्ध तरीकों के व्युत्क्रम मैट्रिसेस को अपडेट करने के लिए विशिष्ट सूत्र नहीं दूंगा, क्योंकि वे स्वतंत्र रूप से खोजना या प्राप्त करना आसान है। इस मामले में केवल एक चीज जिस पर ध्यान दिया जाना चाहिए, वह यह है कि उल्टे मैट्रिक्स को अपडेट करने के तरीकों के वेरिएंट आमतौर पर बहुत कम स्थिर होते हैं (यानी, वे राउंडिंग त्रुटियों से अधिक पीड़ित होते हैं) जो मूल मैट्रिक्स को अपडेट करने का सुझाव देते हैं। यह मैट्रिक्स को स्वयं अपडेट करने के लिए सबसे अधिक कुशल है, लेकिन इसका चोल्स्की अपघटन (जब तक कि निश्चित रूप से, ऐसा अपघटन नहीं होता है), क्योंकि इस तरह के कार्यान्वयन का विकल्प अधिक संख्यात्मक रूप से स्थिर है और इसके अलावा, एक समीकरण को हल करने की लागत को कम करता है जो गति की दिशा निर्धारित करता है।

यह इस सवाल पर विचार करता है कि अर्ध-न्यूटोनियन प्रक्रिया में पहले मैट्रिक्स को कैसे देखना चाहिए। यहां सब कुछ स्पष्ट है - हेसियन मैट्रिक्स के करीब या इसके सही संस्करण के लिए, यदि हेसियन अचानक सकारात्मक निश्चितता के लिए बाहर नहीं निकलता है, तो यह अभिसरण के दृष्टिकोण से बेहतर होगा। हालांकि, सिद्धांत रूप में, कोई भी सकारात्मक निश्चित मैट्रिक्स हमारे लिए उपयुक्त हो सकता है। इस तरह के मैट्रिक्स का सबसे सरल संस्करण एक एकल है, और फिर पहला पुनरावृत्ति ढाल वंश के पुनरावृत्ति के साथ मेल खाता है। फ्लेचर और पॉवेल ने दिखाया (स्वाभाविक रूप से, डीएफपी विधि के लिए) कि अगर द्विघात फ़ंक्शन को कम से कम किया जाता है, जिसकी परवाह किए बिना (सकारात्मक निश्चित) मैट्रिक्स को शुरुआती डीएफपी पुनरावृत्ति के रूप में उपयोग किया जाता है, तो वे वास्तव में एन पुनरावृत्तियों में एक समाधान का नेतृत्व करेंगे, जहां एन है समस्या का आयाम, और अर्ध-न्यूटोनियन मैट्रिक्स न्यूनतम बिंदु पर हेसियन मैट्रिक्स के साथ मेल खाता है। इस तरह की खुशी के सामान्य ग़ैर-कानूनी मामले में, हम निश्चित रूप से इंतजार नहीं करेंगे, लेकिन यह कम से कम शुरुआती मैट्रिक्स के खराब विकल्प के बारे में बहुत अधिक चिंता न करने का कारण देता है।

निष्कर्ष

अर्ध-न्यूटोनियन विधियों के निर्माण के लिए वर्णित दृष्टिकोण एकमात्र संभव नहीं है। कम से कम, वर्णित अर्ध-न्यूटोनियन विधियों के खोजकर्ता और बाद के कई शोधकर्ता पूरी तरह से अलग-अलग विचारों के आधार पर एक ही सूत्र में आए। हालांकि, यह दिलचस्प है कि जैसे ही एक निश्चित अर्ध-न्यूटोनियन पद्धति दिखाई दी, यह एक कम समय के बाद स्पष्ट हो गया कि यह कुछ बहुत आसानी से व्याख्या की गई अनुकूलन समस्या का समाधान था। मेरी राय में, यह उल्लेखनीय है कि इस तरह के विविध तरीकों के लिए कुछ सामान्य भाजक लाना संभव है, क्योंकि यह अन्य तरीकों के निर्माण का आधार प्रदान करता है जो किसी विशेष कार्य की बारीकियों को ध्यान में रखते हैं। विशेष रूप से, विरल मैट्रिस को अद्यतन करने के लिए डिज़ाइन किए गए अर्ध-न्यूटोनियन तरीके हैं, ऐसे तरीके जिनमें संभव के रूप में कुछ तत्वों को बदलने के अधीन हैं, और कई अन्य एक कल्पना होगी।

यह भी ध्यान दिया जाना चाहिए कि चर मैट्रिक्स के तरीके, उनके नाम के बावजूद, हमेशा मेट्रिक्स के निर्माण की ओर नहीं जाते हैं, जो वास्तव में मैट्रिक्स होते हैं, हालांकि वे हर बार ऐसा करते हैं यह बिल्कुल भी संभव है। , , — , - . , , . , . , — .

, . , ( , , N , , ). ( , , ), . , , — . — .