• संभाव्यता सिद्धांत पर शैक्षिक कार्यक्रम (परिचयात्मक लेख, वैकल्पिक)
  
• समीकरणों के रैखिक प्रणालियों का परिचय
  
• परिमित तत्व विधियाँ
  
• द्विघात रूपों का न्यूनतमकरण और ओएलएस समस्याओं के उदाहरण
  
• लेस्टर स्क्वेयर से लेकर न्यूरल नेटवर्क तक
  

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

तो चलिए शुरू करते हैं। आइए कल्पना करें कि मेरे चेहरे की एक स्कैन (बाईं ओर की तस्वीर में) के साथ एक त्रिकोणीय सतह है। सुविधाओं को बढ़ाने के लिए मुझे क्या करने की आवश्यकता है, इस सतह को एक गॉकेटेक मास्क में बदल दें?



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

वास्तव में, कोड की बीस लाइनें एक सॉल्वर के लिए पर्याप्त हैं। यदि आप 3 डी मॉडल फ़ाइल के पार्सर सहित सब कुछ, सब कुछ के साथ गणना करते हैं, तो दो सौ लाइनों के भीतर रखें - बस थूक।

उदाहरण 1: डेटा चौरसाई

आइए बात करते हैं कि यह कैसे काम करता है। आइए दूर से शुरू करते हैं, कल्पना करें कि हमारे पास एक नियमित सरणी f है, उदाहरण के लिए, 32 तत्वों की, निम्नानुसार प्रारंभ की गई है:



और फिर हम निम्नलिखित प्रक्रिया को एक हजार बार करेंगे: प्रत्येक सेल f [i] के लिए हम इसमें पड़ोसी कोशिकाओं का औसत मूल्य लिखते हैं: f [i] = (f [i-1] + f [i + 1]) / 2। इसे स्पष्ट करने के लिए, यहाँ पूर्ण कोड है:

import matplotlib.pyplot as plt f = [0.] * 32 f[0] = f[-1] = 1. f[18] = 2. plt.plot(f, drawstyle='steps-mid') for iter in range(1000): f[0] = f[1] for i in range(1, len(f)-1): f[i] = (f[i-1]+f[i+1])/2. f[-1] = f[-2] plt.plot(f, drawstyle='steps-mid') plt.show() 

प्रत्येक पुनरावृत्ति हमारे सरणी के डेटा को सुचारू करेगा, और एक हजार पुनरावृत्तियों के बाद हमें सभी कक्षों में एक निरंतर मूल्य मिलेगा। यहाँ पहले एक सौ पचास पुनरावृत्तियों का एक एनीमेशन है:



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



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

उदाहरण 2: सुविधाओं को बढ़ाना / बदलना

पूरा कोड जीथब पर उपलब्ध है , लेकिन यहां मैं सबसे महत्वपूर्ण हिस्सा दूंगा, केवल 3 डी मॉडल के पढ़ने और लिखने के लिए। इसलिए, मेरे लिए त्रिभुजित मॉडल को दो सरणियों द्वारा दर्शाया गया है: क्रिया और चेहरे। Verts array सिर्फ तीन-आयामी बिंदुओं का एक सेट है, वे बहुभुज जाल के कोने हैं। चेहरों का सरणी त्रिभुजों का एक समूह है (त्रिकोणों की संख्या face.size ()) के बराबर है, प्रत्येक त्रिकोण के लिए शीर्ष सरणी से सूचक सरणी में संग्रहीत होते हैं। डेटा प्रारूप और इसके साथ काम मैंने कंप्यूटर ग्राफिक्स पर अपने व्याख्यान के पाठ्यक्रम में विस्तार से वर्णित किया है। एक तीसरा सरणी भी है, जिसे मैं पहले दो (अधिक सटीक रूप से, केवल चेहरे के सरणी से) से सुनाता हूं - vvadj। यह एक ऐसा सरणी है जो प्रत्येक शीर्ष के लिए (द्वि-आयामी सरणी का पहला सूचकांक) अपने पड़ोसियों (दूसरे सूचकांक) के सूचकांकों को संग्रहीत करता है।

 std::vector<Vec3f> verts; std::vector<std::vector<int> > faces; std::vector<std::vector<int> > vvadj; 

पहली बात यह है कि मेरी सतह के प्रत्येक शीर्ष के लिए मैं वक्रता वेक्टर पर विचार करता हूं। आइए स्पष्ट करें: वर्तमान शीर्ष v के लिए, मैं अपने सभी पड़ोसियों के n1-n4 पर पुनरावृति करता हूं; फिर मैंने उनके द्रव्यमान b = (n1 + n2 + n3 + n4) / 4 का केंद्र गिना। खैर, अंतिम वक्रता वेक्टर की गणना c = vb के रूप में की जा सकती है, यह दूसरी व्युत्पन्न के लिए साधारण परिमित अंतर जैसा कुछ नहीं है।



सीधे कोड में, यह इस तरह दिखता है:

  std::vector<Vec3f> curvature(verts.size(), Vec3f(0,0,0)); for (int i=0; i<(int)verts.size(); i++) { for (int j=0; j<(int)vvadj[i].size(); j++) { curvature[i] = curvature[i] - verts[vvadj[i][j]]; } curvature[i] = verts[i] + curvature[i] / (float)vvadj[i].size(); } 

ठीक है, तो हम निम्न कार्य कई बार करते हैं (पिछली तस्वीर देखें): हम शीर्ष v को v: = b + const * c पर ले जाते हैं। कृपया ध्यान दें कि यदि स्थिर एक के बराबर है, तो हमारा शीर्ष कहीं भी नहीं जाएगा! यदि निरंतर शून्य है, तो शीर्ष को पड़ोसी छोरों के द्रव्यमान के केंद्र से बदल दिया जाता है, जो हमारी सतह को चिकना कर देगा। यदि निरंतरता एकता से अधिक है (शीर्षक चित्र const = 2.1 का उपयोग करके बनाया गया था), तो सतह को वक्रता वेक्टर की दिशा में स्थानांतरित कर दिया जाएगा, विवरण को मजबूत करेगा। यह कोड में कैसा दिखता है:

  for (int it=0; it<100; it++) { for (int i=0; i<(int)verts.size(); i++) { Vec3f bary(0,0,0); for (int j=0; j<(int)vvadj[i].size(); j++) { bary = bary + verts[vvadj[i][j]]; } bary = bary / (float)vvadj[i].size(); verts[i] = bary + curvature[i]*2.1; // play with the coeff here } } 

वैसे, अगर यह एकता से कम है, तो विवरण इसके विपरीत (const = 0.5) कमजोर होगा, लेकिन यह सरल चौरसाई के बराबर नहीं होगा, "चित्र विपरीत" रहेगा:



कृपया ध्यान दें कि मेरा कोड Wavefront .obj प्रारूप में एक 3D मॉडल फ़ाइल बनाता है, मैंने तीसरे पक्ष के कार्यक्रम में प्रस्तुत किया। आप परिणामी मॉडल देख सकते हैं, उदाहरण के लिए, ऑनलाइन दर्शक में । यदि आप मॉडल बनाने के बजाय रेंडर करने के तरीकों में रुचि रखते हैं, तो कंप्यूटर ग्राफिक्स पर मेरा कोर्स पढ़ें।

उदाहरण 3: बाधाओं को जोड़ना

आइए बहुत पहले उदाहरण पर वापस जाएं, और ठीक वैसा ही काम करें, लेकिन संख्या 0, 18 और 31 के तहत सरणी के तत्वों को फिर से लिखना नहीं होगा:

 import matplotlib.pyplot as plt x = [0.] * 32 x[0] = x[31] = 1. x[18] = 2. plt.plot(x, drawstyle='steps-mid') for iter in range(1000): for i in range(len(x)): if i in [0,18,31]: continue x[i] = (x[i-1]+x[i+1])/2. plt.plot(x, drawstyle='steps-mid') plt.show() 

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



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

लयात्मक विषयांतर: रैखिक समीकरणों की प्रणालियों का संख्यात्मक समाधान।

हमें रैखिक समीकरणों की सामान्य प्रणाली दी जाए:



इसे फिर से लिखा जा सकता है, समान चिन्ह x_i के एक तरफ के प्रत्येक समीकरण को छोड़ते हुए:



हमें एक मनमाना वेक्टर दिया जाए समीकरणों की एक प्रणाली के समाधान का अनुमान लगाना (उदाहरण के लिए, शून्य)।

फिर, इसे हमारे सिस्टम के दाईं ओर चिपकाते हुए, हम एक अद्यतन समाधान सन्निकटन वेक्टर प्राप्त कर सकते हैं ।

इसे स्पष्ट करने के लिए, X0 को x0 से निम्नानुसार प्राप्त किया जाता है:



प्रक्रिया के समय को दोहराते हुए, समाधान वेक्टर द्वारा अनुमानित किया जाएगा

चलो बस मामले में, एक पुनरावर्तन सूत्र लिखें:



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

उदाहरण 3 फिर से, लेकिन दूसरी ओर

और अब चलो उदाहरण 3 से मुख्य लूप पर करीब से नज़र डालें:

 for iter in range(1000): for i in range(len(x)): if i in [0,18,31]: continue x[i] = (x[i-1]+x[i+1])/2. 

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



थोड़ा समय लें, सुनिश्चित करें कि मेरे पायथन कोड में प्रत्येक पुनरावृत्ति कड़ाई से समीकरणों की इस प्रणाली के लिए जैकोबी विधि का एक अद्यतन है। मूल्य x [0], x [18] और x [31] क्रमशः मेरे लिए तय किए गए हैं, वे चर के सेट में शामिल नहीं हैं, इसलिए उन्हें दाईं ओर स्थानांतरित किया जाता है।

कुल मिलाकर, हमारे सिस्टम के सभी समीकरण जैसे दिखते हैं - x [i-1] + 2 x [i] - x [i + 1] = 0. यह अभिव्यक्ति दूसरी व्युत्पन्न के लिए साधारण परिमित अंतर से अधिक कुछ नहीं है। यही है, समीकरणों की हमारी प्रणाली केवल यह बताती है कि दूसरी व्युत्पत्ति शून्य के बराबर होनी चाहिए (अच्छी तरह से, बिंदु x [18] को छोड़कर)। याद रखें, मैंने कहा कि यह स्पष्ट है कि पुनरावृत्तियों को रैखिक रैंप में परिवर्तित करना चाहिए? यही कारण है कि दूसरी व्युत्पन्न का रैखिक व्युत्पन्न शून्य है।

क्या आप जानते हैं कि हमने अभी लाप्लास समीकरण के लिए डिरिचलेट समस्या को हल किया है ?

वैसे, एक चौकस पाठक को देखा जाना चाहिए कि, मेरे कोड में कड़ाई से बोलते हुए, रैखिक समीकरणों के सिस्टम को जैकोबी विधि द्वारा नहीं बल्कि गॉस-सीडेल विधि द्वारा हल किया जाता है, जो कि जैकोबी विधि का एक प्रकार का अनुकूलन है।

उदाहरण 4: पॉइसन समीकरण

और चलो तीसरे उदाहरण को थोड़ा बदल दें: प्रत्येक कोशिका को न केवल पड़ोसी कोशिकाओं के द्रव्यमान के केंद्र में रखा जाता है, बल्कि द्रव्यमान के केंद्र में भी कुछ (मनमाना) स्थिर होता है:

 import matplotlib.pyplot as plt x = [0.] * 32 x[0] = x[31] = 1. x[18] = 2. plt.plot(x, drawstyle='steps-mid') for iter in range(1000): for i in range(len(x)): if i in [0,18,31]: continue x[i] = (x[i-1]+x[i+1] +11./32**2 )/2. plt.plot(x, drawstyle='steps-mid') plt.show() 

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



32 तत्वों की एक सरणी लंबाई के साथ, हमारा सिस्टम सौ पुनरावृत्तियों के एक जोड़े में एक समाधान में परिवर्तित होता है। लेकिन क्या होगा अगर हम 128 तत्वों की एक सरणी की कोशिश करें? यहां सब कुछ बहुत दुखद है, पुनरावृत्तियों की संख्या पहले से ही हजारों में गणना की जानी चाहिए:



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



और आप बंद नहीं दिखा सकते हैं, और समीकरणों के सिस्टम के वास्तविक सॉल्वर का उपयोग कर सकते हैं। इसलिए मैं मैट्रिक्स ए और कॉलम बी का निर्माण करके एक ही उदाहरण को हल करता हूं, फिर मैट्रिक्स समीकरण एक्स = बी को हल कर रहा हूं:

 import numpy as np import matplotlib.pyplot as plt n=1000 x = [0.] * n x[0] = x[-1] = 1. m = n*57//100 x[m] = 2. A = np.matrix(np.zeros((n, n))) for i in range(1,n-2): A[i, i-1] = -1. A[i, i] = 2. A[i, i+1] = -1. A = A[1:-2,1:-2] A[m-2,m-1] = 0 A[m-1,m-2] = 0 b = np.matrix(np.zeros((n-3, 1))) b[0,0] = x[0] b[m-2,0] = x[m] b[m-1,0] = x[m] b[-1,0] = x[-1] for i in range(n-3): b[i,0] += 11./n**2 x2 = ((np.linalg.inv(A)*b).transpose().tolist()[0]) x2.insert(0, x[0]) x2.insert(m, x[m]) x2.append(x[-1]) plt.plot(x2, drawstyle='steps-mid') plt.show() 

और यहां इस कार्यक्रम के काम का परिणाम है, ध्यान दें कि समाधान तुरंत निकला:



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

अपडेट: होमवर्क के रूप में एक और खिलौना

SquareRootOfZero द्वारा सुझाए गए विचार को विकसित करना, इस कोड के साथ खेलना:



यह डिफ़ॉल्ट परिणाम है, लाल लेनिन प्रारंभिक डेटा है, नीला वक्र उनका विकास है, अनंत पर परिणाम एक बिंदु पर परिवर्तित होता है:



और यहाँ गुणांक 2 के साथ परिणाम है।



गृहकार्य: क्यों दूसरे मामले में, लेनिन पहले दोज़रिन्स्की में बदल जाता है, और फिर फिर लेनिन में परिवर्तित हो जाता है, लेकिन एक बड़े आकार का?

निष्कर्ष

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

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



अधिक के लिए बने रहें!