असतत लाप्लास ऑपरेटर

For लाप्लास परिवर्तन के असतत समकक्ष, see Z- परिवर्तन.

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

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

परिभाषाएँ

आरेख लाप्लासियन्स

आरेखों के लिए विचलित लापलेस के विभिन्न परिभाषाएं होती हैं, जो चिह्न और स्केल फैक्टर से अलग होती हैं (कभी-कभी पड़ोस शीर्ष पर औसत लेते हैं, कभी-कभी सिर्फ जोड़ते हैं; एक नियमित आरेख के लिए इसका कोई अंतर नहीं होता है। आरेख लापलेसियन की पारंपरिक परिभाषा, नीचे दी गई, एक मुक्त सीमा वाले डोमेन पर नकारात्मक अनुच्छेद लापलेसियन के समान होती है।

मान लीजिए $G=(V,E)$ एक आरेख हो जिसमें शीर्ष $V$ और शीर्ष $E$. हो, शीर्ष पर मान लेने वाली एक फलन $\phi \colon V\to R$ के लिए निम्नलिखित विचलित लापलेसियन पर क्रिया करना परिभाषित होता है तब, विचलित लापलेसियन जो Δ पर क्रिया करता है, उसकी परिभाषा निम्नलिखित है:

$(\Delta \phi )(v)=\sum _{w:\,d(w,v)=1}\left[\phi (v)-\phi (w)\right]$

जहाँ $d(w,v)$ शीर्ष w और v के मध्य आरेख की दूरी होती है। इस प्रकार, यह योग v के सबसे निकट पड़ोसी शीर्ष के लिए होता है। एक सीमित संख्या के शीर्ष और सदिश के साथ एक आरेख के लिए, यह परिभाषा लापलेसियन मैट्रिक्स की परिभाषा के समान होती है। संक्षिप्त रूप, $\phi$ स्तम्भ सदिश के रूप में लिखा जा सकता है; इसलिए $\Delta \phi$ स्तंभ वेक्टर और लाप्लासियन मैट्रिक्स का उत्पाद है,जबकि $(\Delta \phi )(v)$ उत्पाद सदिश की मात्र v'वीं प्रविष्टि है।

यदि आरेख में भारित किनारे हैं, जो कि एक भारफलन है $\gamma \colon E\to R$ दिया गया है, तो परिभाषा को सामान्यीकृत किया जा सकता है

$(\Delta _{\gamma }\phi )(v)=\sum _{w:\,d(w,v)=1}\gamma _{wv}\left[\phi (v)-\phi (w)\right]$

जहाँ $\gamma _{wv}$शीर्ष पर $wv\in E$. के भार का मान होता है

असतत लाप्लासियन से निकटता से संबंधित औसत प्रचालक है:

$(M\phi )(v)={\frac {1}{\deg v}}\sum _{w:\,d(w,v)=1}\phi (w).$

मेश लाप्लासियन्स

एक आरेख में नोड्स और किनारों की कनेक्टिविटी पर विचार करने के अतिरिक्त, मेश लैपलेस प्रचालक सतह की ज्यामिति को ध्यान में रखते हैं। द्वि-आयामी कई गुना त्रिकोण जाल के लिए, एक स्केलर फलन का लाप्लास-बेल्ट्रामी प्रचालक $u$ एक शीर्ष पर $i$ के रूप में अनुमानित किया जा सकता है

$(\Delta u)_{i}\equiv {\frac {1}{2A_{i}}}\sum _{j}(\cot \alpha _{ij}+\cot \beta _{ij})(u_{j}-u_{i}),$

जहां योग सभी आसन्न शीर्षों पर है $j$ का $i$, $\alpha _{ij}$ और $\beta _{ij}$ किनारे के विपरीत दो कोण हैं $ij$, और $A_{i}$ का चरम क्षेत्र है $i$; वह है, उदा। त्रिभुजों के सम्‍मिलित क्षेत्रों का एक तिहाई घटना $i$. यह ध्यान रखना महत्वपूर्ण है कि असतत लाप्लास-बेल्ट्रामी प्रचालक का चिन्ह पारंपरिक रूप से साधारण लाप्लास प्रचालक के चिन्ह के विपरीत है। उपरोक्त कॉटैंजेंट सूत्र को कई अलग-अलग तरीकों का उपयोग करके प्राप्त किया जा सकता है जिनमें परिमित तत्व विधि, परिमित आयतन विधि और असतत बाहरी कलन शामिल हैं। (पीडीएफ डाउनलोड: [1])।

संगणना की सुविधा के लिए, लाप्लासियन को मैट्रिक्स में एन्कोड किया गया है $L\in \mathbb {R} ^{|V|\times |V|}$ ऐसा है कि $Lu=(\Delta u)_{i}$. होने देना $C$ प्रविष्टियों के साथ (विरल) कोटैंजेंट मैट्रिक्स बनें

$C_{ij}={\begin{cases}{\frac {1}{2}}(\cot \alpha _{ij}+\cot \beta _{ij})&ij{\text{ is an edge, that is }}j\in N(i),\\-\sum \limits _{k\in N(i)}C_{ik}&i=j,\\0&{\text{otherwise}}\end{cases}}$ कहाँ $N(i)$ के पड़ोस को दर्शाता है $i$.

और जाने $M$ विकर्ण द्रव्यमान मैट्रिक्स बनें $M$ किसका $i$विकर्ण के साथ-साथ प्रवेश शीर्ष क्षेत्र है $A_{i}$. तब $L=M^{-1}C$ लाप्लासियन का वांछित विवेक है।

मेश प्रचालक ों का अधिक सामान्य अवलोकन में दिया गया है।

परिमित अंतर

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

$\Delta f(x,y)\approx {\frac {f(x-h,y)+f(x+h,y)+f(x,y-h)+f(x,y+h)-4f(x,y)}{h^{2}}},$

जहां दोनों आयामों में ग्रिड का आकार h है, ताकि ग्रिड में एक बिंदु (x, y) का पांच-बिंदु स्टैंसिल हो

$\{(x-h,y),(x,y),(x+h,y),(x,y-h),(x,y+h)\}.$

यदि ग्रिड का आकार h = 1 है, तो परिणाम आरेख पर 'ऋणात्मक' असतत लाप्लासियन है, जो कि वर्गाकार जाली है। जाली ग्रिड की सीमा परफलन एफ (एक्स, वाई) के मानों पर यहां कोई बाधा नहीं है, इस प्रकार यह सीमा पर कोई स्रोत नहीं है, यानी नो-फ्लक्स सीमा स्थिति (उर्फ, इन्सुलेशन) , या सजातीय न्यूमैन सीमा स्थिति)। सीमा पर राज्य चर का नियंत्रण, जैसे f(x, y) ग्रिड की सीमा पर दिया गया (उर्फ, डिरिचलेट सीमा स्थिति), आरेख लाप्लासियन के लिए शायद ही कभी उपयोग किया जाता है, लेकिन अन्य अनुप्रयोगों में आम है।

घनाभ पर बहुआयामी असतत लाप्लासियन#आयताकार घनाभ नियमित ग्रिड में बहुत ही विशेष गुण होते हैं, उदाहरण के लिए, वे क्रोनकर उत्पाद हैं#क्रोनेकर राशि और एक-आयामी असतत लाप्लासियन के घातांक, असतत लाप्लासियन का क्रोनकर योग देखें, जिस स्थिति में इसके सभी eigenvalue और egenvectors हो सकते हैं स्पष्ट रूप से गणना।

परिमित-तत्व विधि

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

इमेज प्रोसेसिंग

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

प्रचालक विवेक के माध्यम से कार्यान्वयन

एक-, दो- और त्रि-आयामी संकेतों के लिए, असतत लाप्लासियन को निम्नलिखित गुठली के साथ कनवल्शन के रूप में दिया जा सकता है:

1D फ़िल्टर: ${\vec {D}}_{x}^{2}={\begin{bmatrix}1&-2&1\end{bmatrix}}$,

फ़िल्टर कर सकते हैं: $\mathbf {D} _{xy}^{2}={\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}$.

$\mathbf {D} _{xy}^{2}$ पहले देखे गए (पांच-बिंदु स्टैंसिल) परिमित-अंतर सूत्र से मेल खाता है। यह बहुत सुचारू रूप से भिन्न क्षेत्रों के लिए स्थिर है, लेकिन तेजी से भिन्न समाधानों वाले समीकरणों के लिए लाप्लासियन प्रचालक के अधिक स्थिर और आइसोट्रोपिक रूप की आवश्यकता होती है, जैसे नौ-बिंदु स्टैंसिल, जिसमें विकर्ण शामिल हैं:

2 डी फ़िल्टर: $\mathbf {D} _{xy}^{2}={\begin{bmatrix}0.25&0.5&0.25\\0.5&-3&0.5\\0.25&0.5&0.25\end{bmatrix}}$,

गणना फ़िल्टर: $\mathbf {D} _{xyz}^{2}$ सात-बिंदु स्टैंसिल का उपयोग करके दिया गया है:

पहला विमान = ${\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}$; दूसरा विमान = ${\begin{bmatrix}0&1&0\\1&-6&1\\0&1&0\end{bmatrix}}$; तीसरा विमान = ${\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}$.

और 27-बिंदु स्टैंसिल का उपयोग करके:

पहला विमान = ${\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}$; दूसरा विमान = ${\frac {1}{26}}{\begin{bmatrix}3&6&3\\6&-88&6\\3&6&3\end{bmatrix}}$; तीसरा विमान = ${\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}$.

{{var|n}डी फ़िल्टर: तत्व के लिए $a_{x_{1},x_{2},\dots ,x_{n}}$ कर्नेल का $\mathbf {D} _{x_{1},x_{2},\dots ,x_{n}}^{2},$

$a_{x_{1},x_{2},\dots ,x_{n}}=\left\{{\begin{array}{ll}-2n&{\text{if }}s=n,\\1&{\text{if }}s=n-1,\\0&{\text{otherwise,}}\end{array}}\right.$

कहाँ x_i स्थिति है (या तो −1, 0 या 1) कर्नेल में तत्व का i-वीं दिशा, और s दिशाओं की संख्या है i जिसके लिए x_i = 0.

ध्यान दें कि nD संस्करण, जो लाप्लासियन के आरेख सामान्यीकरण पर आधारित है, सभी पड़ोसियों को समान दूरी पर मानता है, और इसलिए उपरोक्त संस्करण के बजाय विकर्णों के साथ निम्न 2D फ़िल्टर की ओर जाता है:

2 डी फ़िल्टर: $\mathbf {D} _{xy}^{2}={\begin{bmatrix}1&1&1\\1&-8&1\\1&1&1\end{bmatrix}}.$

इन गुठली को असतत विभेदक भागफलों का उपयोग करके घटाया जाता है।

इसे दिखाया जा सकता है अंतर प्रचालक ों के उत्तल संयोजन के रूप में द्वि-आयामी लाप्लासियन प्रचालक के निम्नलिखित असतत सन्निकटन

$\nabla _{\gamma }^{2}=(1-\gamma )\nabla _{5}^{2}+\gamma \nabla _{\times }^{2}=(1-\gamma ){\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}+\gamma {\begin{bmatrix}1/2&0&1/2\\0&-2&0\\1/2&0&1/2\end{bmatrix}}$

γ ∈ [0, 1] के लिए असतत स्केल-स्पेस गुणों के साथ संगत है, जहां विशेष रूप से मान γ = 1/3 घूर्णी समरूपता का सर्वोत्तम सन्निकटन देता है। त्रि-आयामी संकेतों के संबंध में, यह दिखाया गया हैकि लाप्लासियन प्रचालक को अंतर प्रचालक ों के दो-पैरामीटर परिवार द्वारा अनुमानित किया जा सकता है

$\nabla _{\gamma _{1},\gamma _{2}}^{2}=(1-\gamma _{1}-\gamma _{2})\,\nabla _{7}^{2}+\gamma _{1}\,\nabla _{+^{3}}^{2}+\gamma _{2}\,\nabla _{\times ^{3}}^{2}),$

कहाँ

$(\nabla _{7}^{2}f)_{0,0,0}=f_{-1,0,0}+f_{+1,0,0}+f_{0,-1,0}+f_{0,+1,0}+f_{0,0,-1}+f_{0,0,+1}-6f_{0,0,0},$

$(\nabla _{+^{3}}^{2}f)_{0,0,0}={\frac {1}{4}}(f_{-1,-1,0}+f_{-1,+1,0}+f_{+1,-1,0}+f_{+1,+1,0}+f_{-1,0,-1}+f_{-1,0,+1}+f_{+1,0,-1}+f_{+1,0,+1}+f_{0,-1,-1}+f_{0,-1,+1}+f_{0,+1,-1}+f_{0,+1,+1}-12f_{0,0,0}),$

$(\nabla _{\times ^{3}}^{2}f)_{0,0,0}={\frac {1}{4}}(f_{-1,-1,-1}+f_{-1,-1,+1}+f_{-1,+1,-1}+f_{-1,+1,+1}+f_{+1,-1,-1}+f_{+1,-1,+1}+f_{+1,+1,-1}+f_{+1,+1,+1}-8f_{0,0,0}).$

निरंतर पुनर्निर्माण के माध्यम से कार्यान्वयन

एक असतत संकेत, जिसमें छवियां शामिल हैं, को एक सतत कार्य के असतत प्रतिनिधित्व के रूप में देखा जा सकता है $f({\bar {r}})$, जहां समन्वयसदिश ${\bar {r}}\in R^{n}$ और मान डोमेन वास्तविक है $f\in R$. व्युत्पत्ति संचालन इसलिए सीधे निरंतर कार्य पर लागू होता है, $f$. विशेष रूप से कोई असतत छवि, विवेक प्रक्रिया पर उचित अनुमानों के साथ, उदा। बैंड सीमित कार्यों को मानते हुए, या वेवलेट विस्तारणीय कार्यों इत्यादि को पुनर्निर्माण फॉर्मूलेशन के तहत अच्छी तरह से व्यवहार करने वाले इंटरपोलेशन कार्यों के माध्यम से पुनर्निर्मित किया जा सकता है,

$f({\bar {r}})=\sum _{k\in K}f_{k}\mu _{k}({\bar {r}})$

कहाँ $f_{k}\in R$ के असतत प्रतिनिधित्व हैं $f$ ग्रिड पर $K$ और $\mu _{k}$ ग्रिड के लिए विशिष्ट प्रक्षेप कार्य हैं $K$. एक समान ग्रिड पर, जैसे कि चित्र, और बैंडलिमिटेड फ़ंक्शंस के लिए, इंटरपोलेशन फ़ंक्शंस शिफ्ट इनवेरिएंट की राशि होती है $\mu _{k}({\bar {r}})=\mu ({\bar {r}}-{\bar {r}}_{k})$ साथ $\mu$ में परिभाषित एक उचित रूप से फैला हुआ sincफलन है $n$-आयाम यानी ${\bar {r}}=(x_{1},x_{2}...x_{n})^{T}$. के अन्य अनुमान $\mu$ एकसमान ग्रिड पर, उचित रूप से गॉसियन कार्यों को फैलाया जाता है $n$-आयाम। तदनुसार असतत लाप्लासियन निरंतर के लाप्लासियन का असतत संस्करण बन जाता है $f({\bar {r}})$ :$\nabla ^{2}f({\bar {r}}_{k})=\sum _{k'\in K}f_{k'}(\nabla ^{2}\mu ({\bar {r}}-{\bar {r}}_{k'}))|_{{\bar {r}}={\bar {r}}_{k}}$ जो बदले में वर्दी (छवि) ग्रिड पर इंटरपोलेशनफलन के लैपलासीन के साथ एक दृढ़ संकल्प है $K$. प्रक्षेप कार्यों के रूप में गॉसियन का उपयोग करने का एक फायदा यह है कि वे लाप्लासियन सहित रैखिक प्रचालक ों का उत्पादन करते हैं, जो समन्वय फ्रेम के घूर्णी कलाकृतियों से मुक्त होते हैं जिसमें $f$ माध्यम से दर्शाया गया है $f_{k}$, में $n$-आयाम, और परिभाषा के अनुसार आवृत्ति जागरूक हैं। एक रैखिक प्रचालक के पास न केवल एक सीमित सीमा होती है ${\bar {r}}$ डोमेन लेकिन फ़्रीक्वेंसी डोमेन (वैकल्पिक रूप से गॉसियन स्केल स्पेस) में एक प्रभावी रेंज जिसे गॉसियन के विचरण के माध्यम से एक सैद्धांतिक तरीके से स्पष्ट रूप से नियंत्रित किया जा सकता है। परिणामी फ़िल्टरिंग को आगे की कम्प्यूटेशनल दक्षता के लिए वियोज्य फ़िल्टर और डिकिमेशन (सिग्नल प्रोसेसिंग) / पिरामिड (इमेज प्रोसेसिंग) प्रतिनिधित्व द्वारा कार्यान्वित किया जा सकता है। $n$-आयाम। दूसरे शब्दों में, किसी भी आकार के असतत लाप्लासियन फ़िल्टर को गॉसियन के नमूने वाले लाप्लासियन के रूप में आसानी से उत्पन्न किया जा सकता है, जो स्थानिक आकार के साथ किसी विशेष अनुप्रयोग की ज़रूरतों को पूरा करता है, जैसा कि इसके विचरण द्वारा नियंत्रित होता है। मोनोमियल्स जो गैर-रैखिक प्रचालक हैं, उन्हें भी इसी तरह के पुनर्निर्माण और सन्निकटन दृष्टिकोण का उपयोग करके कार्यान्वित किया जा सकता है, बशर्ते सिग्नल पर्याप्त रूप से ओवर-सैंपल हो। इस प्रकार, ऐसे गैर-रैखिक प्रचालक उदा। संरचना टेन्सर, और सामान्यीकृत संरचना टेन्सर जो अभिविन्यास अनुमान में उनके कुल न्यूनतम-स्क्वायर इष्टतमता के लिए पैटर्न मान में उपयोग किए जाते हैं, को महसूस किया जा सकता है।

स्पेक्ट्रम

अनंत ग्रिड पर असतत लाप्लासियन का स्पेक्ट्रम प्रमुख रुचि का है; चूँकि यह एक स्वतः संलग्न संकारक है, इसका वास्तविक स्पेक्ट्रम है। अधिवेशन के लिए $\Delta =I-M$ पर $Z$, स्पेक्ट्रम भीतर है $[0,2]$ (जैसा कि औसत प्रचालक में वर्णक्रमीय मान होते हैं $[-1,1]$). इसे फूरियर रूपांतरण लागू करके भी देखा जा सकता है। ध्यान दें कि एक अनंत ग्रिड पर असतत लाप्लासियन में विशुद्ध रूप से निरंतर स्पेक्ट्रम होता है, और इसलिए, कोई eigenvalues ​​या eigenfunctions नहीं होता है।

प्रमेय

यदि आरेख एक अनंत वर्ग जाली है, तो लाप्लासियन की यह परिभाषा अनंत रूप से ठीक ग्रिड की सीमा में निरंतर लाप्लासियन के अनुरूप दिखाई जा सकती है। इस प्रकार, उदाहरण के लिए, हमारे पास एक आयामी ग्रिड है

${\frac {\partial ^{2}F}{\partial x^{2}}}=\lim _{\epsilon \rightarrow 0}{\frac {[F(x+\epsilon )-F(x)]-[F(x)-F(x-\epsilon )]}{\epsilon ^{2}}}.$

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

असतत गर्मी समीकरण

कल्पना करना ${\textstyle \phi }$ एक आरेख (असतत गणित) में तापमान वितरण का वर्णन करता है, जहां ${\textstyle \phi _{i}}$ शीर्ष पर तापमान है ${\textstyle i}$. न्यूटन के शीतलन के नियम के अनुसार, गर्मी को नोड से स्थानांतरित किया जाता है ${\textstyle i}$ नोड करने के लिए ${\textstyle j}$ के लिए आनुपातिक है ${\textstyle \phi _{i}-\phi _{j}}$ अगर नोड्स ${\textstyle i}$ और ${\textstyle j}$ जुड़े हुए हैं (यदि वे जुड़े नहीं हैं, कोई गर्मी स्थानांतरित नहीं होती है)। फिर, तापीय चालकता के लिए ${\textstyle k}$,

${\begin{aligned}{\frac {d\phi _{i}}{dt}}&=-k\sum _{j}A_{ij}\left(\phi _{i}-\phi _{j}\right)\\&=-k\left(\phi _{i}\sum _{j}A_{ij}-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\left(\phi _{i}\ \deg(v_{i})-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\sum _{j}\left(\delta _{ij}\ \deg(v_{i})-A_{ij}\right)\phi _{j}\\&=-k\sum _{j}\left(L_{ij}\right)\phi _{j}.\end{aligned}}$

मैट्रिक्स-वेक्टर नोटेशन में,

${\begin{aligned}{\frac {d\phi }{dt}}&=-k(D-A)\phi \\&=-kL\phi ,\end{aligned}}$

जो देता है

${\frac {d\phi }{dt}}+kL\phi =0.$

ध्यान दें कि यह समीकरण उष्मा समीकरण के समान रूप लेता है, जहां मैट्रिक्स -L लाप्लासियन प्रचालक की जगह ले रहा है ${\textstyle \nabla ^{2}}$; इसलिए, आरेख लाप्लासियन।

इस अंतर समीकरण का हल खोजने के लिए, पहले क्रम के मैट्रिक्स अंतर समीकरण को हल करने के लिए मानक तकनीकों को लागू करें। यानी लिखो ${\textstyle \phi }$ ईजेनवेक्टरों के एक रैखिक संयोजन के रूप में ${\textstyle \mathbf {v} _{i}}$ एल का (ताकि ${\textstyle L\mathbf {v} _{i}=\lambda _{i}\mathbf {v} _{i}}$) समय-निर्भर गुणांक के साथ, ${\textstyle \phi (t)=\sum _{i}c_{i}(t)\mathbf {v} _{i}.}$ मूल अभिव्यक्ति में प्लगिंग (क्योंकि एल एक सममित मैट्रिक्स है, इसकी इकाई-मानदंड eigenvectors ${\textstyle \mathbf {v} _{i}}$ ओर्थोगोनल हैं):

${\begin{aligned}0={}&{\frac {d\left(\sum _{i}c_{i}(t)\mathbf {v} _{i}\right)}{dt}}+kL\left(\sum _{i}c_{i}(t)\mathbf {v} _{i}\right)\\{}={}&\sum _{i}\left[{\frac {dc_{i}(t)}{dt}}\mathbf {v} _{i}+kc_{i}(t)L\mathbf {v} _{i}\right]\\{}={}&\sum _{i}\left[{\frac {dc_{i}(t)}{dt}}\mathbf {v} _{i}+kc_{i}(t)\lambda _{i}\mathbf {v} _{i}\right]\\\Rightarrow 0={}&{\frac {dc_{i}(t)}{dt}}+k\lambda _{i}c_{i}(t),\\\end{aligned}}$

जिसका समाधान है

$c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}.$

जैसा कि पहले दिखाया गया है, eigenvalues ${\textstyle \lambda _{i}}$ एल के गैर-नकारात्मक हैं, यह दर्शाता है कि प्रसार समीकरण का समाधान एक संतुलन तक पहुंचता है, क्योंकि यह केवल घातीय रूप से घटता है या स्थिर रहता है। इससे यह भी पता चलता है कि दिया ${\textstyle \lambda _{i}}$ और प्रारंभिक स्थिति ${\textstyle c_{i}(0)}$, समाधान किसी भी समय टी पाया जा सकता है। ढूँढ़ने के लिए ${\textstyle c_{i}(0)}$ प्रत्येक के लिए ${\textstyle i}$ समग्र प्रारंभिक स्थिति के संदर्भ में ${\textstyle \phi (0)}$, बस प्रोजेक्ट करें ${\textstyle \phi (0)}$ इकाई-मानक eigenvectors पर ${\textstyle \mathbf {v} _{i}}$;

$c_{i}(0)=\left\langle \phi (0),\mathbf {v} _{i}\right\rangle$.

यह दृष्टिकोण असंरचित ग्रिड पर मात्रात्मक ताप अंतरण मॉडलिंग के लिए लागू किया गया है। अप्रत्यक्ष रेखांकन के मामले में, यह काम करता है क्योंकि ${\textstyle L}$ सममित है, और वर्णक्रमीय प्रमेय द्वारा, इसके ईजेनवेक्टर सभी ऑर्थोगोनल हैं। तो के eigenvectors पर प्रक्षेपण ${\textstyle L}$ निर्देशांक के एक सेट के लिए प्रारंभिक स्थिति का केवल एक ऑर्थोगोनल समन्वय परिवर्तन है जो एक दूसरे से घातीय और स्वतंत्र रूप से क्षय होता है।

संतुलन व्यवहार

समझ में ${\textstyle \lim _{t\to \infty }\phi (t)}$, केवल शर्तें ${\textstyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}}$ जो बचे हैं वे वहीं हैं ${\textstyle \lambda _{i}=0}$, तब से

$\lim _{t\to \infty }e^{-k\lambda _{i}t}={\begin{cases}0,&{\text{if}}&\lambda _{i}>0\\1,&{\text{if}}&\lambda _{i}=0\end{cases}}$

दूसरे शब्दों में, सिस्टम की संतुलन स्थिति पूरी तरह से कर्नेल (रैखिक बीजगणित) द्वारा निर्धारित की जाती है ${\textstyle L}$.

चूंकि परिभाषा के अनुसार, ${\textstyle \sum _{j}L_{ij}=0}$,सदिश ${\textstyle \mathbf {v} ^{1}}$ सभी कर्नेल में हैं। अगर वहाँ ${\textstyle k}$ आरेख ़ में कनेक्टेड कंपोनेंट (आरेख ़ थ्योरी) को डिसाइड करें, फिर सभी के इससदिश को योग में विभाजित किया जा सकता है ${\textstyle k}$ स्वतंत्र ${\textstyle \lambda =0}$ एक और शून्य के eigenvectors, जहां प्रत्येक जुड़ा हुआ घटक एक eigenvector से जुड़ा होता है, जो जुड़े हुए घटक और शून्य में कहीं और के तत्वों के साथ होता है।

इसका परिणाम यह है कि दी गई प्रारंभिक स्थिति के लिए ${\textstyle c(0)}$ के साथ एक आरेख के लिए ${\textstyle N}$ कोने

$\lim _{t\to \infty }\phi (t)=\left\langle c(0),\mathbf {v^{1}} \right\rangle \mathbf {v^{1}}$

कहाँ

$\mathbf {v^{1}} ={\frac {1}{\sqrt {N}}}[1,1,\ldots ,1]$

प्रत्येक तत्व के लिए ${\textstyle \phi _{j}}$ का ${\textstyle \phi }$, यानी प्रत्येक शीर्ष के लिए ${\textstyle j}$ आरेख में, इसे फिर से लिखा जा सकता है

$\lim _{t\to \infty }\phi _{j}(t)={\frac {1}{N}}\sum _{i=1}^{N}c_{i}(0)$.

दूसरे शब्दों में, स्थिर अवस्था में, का मान ${\textstyle \phi }$ आरेख ़ के प्रत्येक शीर्ष पर समान मान पर अभिसरित होता है, जो कि सभी शीर्षों पर प्रारंभिक मानों का औसत होता है। चूँकि यह ऊष्मा प्रसार समीकरण का हल है, यह सहज रूप से सही समझ में आता है। हम उम्मीद करते हैं कि आरेख ़ में पड़ोसी तत्व तब तक ऊर्जा का आदान-प्रदान करेंगे जब तक कि ऊर्जा एक दूसरे से जुड़े सभी तत्वों में समान रूप से फैल न जाए।

ग्रिड पर प्रचालक का उदाहरण

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

यह खंड एकफलन का एक उदाहरण दिखाता है ${\textstyle \phi }$ एक आरेख के माध्यम से समय के साथ प्रसार। इस उदाहरण में आरेख ़ एक 2D असतत ग्रिड पर बनाया गया है, जिसमें उनके आठ पड़ोसियों से जुड़े ग्रिड के बिंदु हैं। तीन प्रारंभिक बिंदुओं को सकारात्मक मान रखने के लिए निर्दिष्ट किया गया है, जबकि ग्रिड में शेष मान शून्य हैं। समय के साथ, घातीय क्षय इन बिंदुओं पर मानों को पूरे ग्रिड में समान रूप से वितरित करने का कार्य करता है।

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

N = 20; % The number of pixels along a dimension of the image
A = zeros(N, N); % The image
Adj = zeros(N * N, N * N); % The adjacency matrix

% Use 8 neighbors, and fill in the adjacency matrix
dx = [- 1, 0, 1, - 1, 1, - 1, 0, 1];
dy = [- 1, - 1, - 1, 0, 0, 1, 1, 1];
for x = 1:N
    for y = 1:N
        index = (x - 1) * N + y;
        for ne = 1:length(dx)
            newx = x + dx(ne);
            newy = y + dy(ne);
            if newx > 0 && newx <= N && newy > 0 && newy <= N
                index2 = (newx - 1) * N + newy;
                Adj(index, index2) = 1;
            end
        end
    end
end

% BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL EQUATION
Deg = diag(sum(Adj, 2)); % Compute the degree matrix
L = Deg - Adj; % Compute the laplacian matrix in terms of the degree and adjacency matrices
[V, D] = eig(L); % Compute the eigenvalues/vectors of the laplacian matrix
D = diag(D);

% Initial condition (place a few large positive values around and
% make everything else zero)
C0 = zeros(N, N);
C0(2:5, 2:5) = 5;
C0(10:15, 10:15) = 10;
C0(2:5, 8:13) = 7;
C0 = C0(:);

C0V = V'*C0; % Transform the initial condition into the coordinate system
% of the eigenvectors
for t = 0:0.05:5
    % Loop through times and decay each initial component
    Phi = C0V .* exp(- D * t); % Exponential decay for each component
    Phi = V * Phi; % Transform from eigenvector coordinate system to original coordinate system
    Phi = reshape(Phi, N, N);
    % Display the results and write to GIF file
    imagesc(Phi);
    caxis([0, 10]);
     title(sprintf('Diffusion t = %3f', t));
    frame = getframe(1);
    im = frame2im(frame);
    [imind, cm] = rgb2ind(im, 256);
    if t == 0
        imwrite(imind, cm, 'out.gif', 'gif', 'Loopcount', inf, 'DelayTime', 0.1);
    else
        imwrite(imind, cm, 'out.gif', 'gif', 'WriteMode', 'append', 'DelayTime', 0.1);
    end
end

असतत श्रोडिंगर प्रचालक

होने देना $P\colon V\rightarrow R$ आरेख पर परिभाषित एक संभावित कार्य हो। ध्यान दें कि P को तिरछे कार्य करने वाला गुणक संकारक माना जा सकता है $\phi$

$(P\phi )(v)=P(v)\phi (v).$

तब $H=\Delta +P$ असतत श्रोडिंगर प्रचालक है, निरंतर श्रोडिंगर समीकरण | श्रोडिंगर प्रचालक का एक एनालॉग।

यदि किसी शीर्ष पर मिलने वाले किनारों की संख्या समान रूप से परिबद्ध है, और विभव परिबद्ध है, तो H परिबद्ध और स्व-संलग्न है।

इस हैमिल्टनियन के एक प्रचालक के स्पेक्ट्रम का अध्ययन स्टोन स्पेस के साथ किया जा सकता है। स्टोन की प्रमेय; यह पॉसेट्स और बूलियन बीजगणित (संरचना) के मध्य द्वंद्व का परिणाम है।

नियमित जाली पर, प्रचालक के पास आमतौर पर ट्रैवलिंग-वेव के साथ-साथ एंडरसन स्थानीयकरण समाधान दोनों होते हैं, यह इस बात पर निर्भर करता है कि संभावित आवधिक या यादृच्छिक है या नहीं।

असतत श्रोडिंगर प्रचालक का ग्रीन का कार्य विलायक औपचारिकता में किसके द्वारा दिया गया है

$G(v,w;\lambda )=\left\langle \delta _{v}\left|{\frac {1}{H-\lambda }}\right|\delta _{w}\right\rangle$

कहाँ $\delta _{w}$ आरेख ़ पर क्रोनकर डेल्टाफलन समझा जाता है: $\delta _{w}(v)=\delta _{wv}$; अर्थात, यह 1 के बराबर है यदि v=w और 0 अन्यथा।

निश्चित के लिए $w\in V$ और $\lambda$ एक सम्मिश्र संख्या, हरे रंग का फलन जिसे v का फलन माना जाता है, का अद्वितीय हल है

$(H-\lambda )G(v,w;\lambda )=\delta _{w}(v).$

एडीई वर्गीकरण

Further information: ADE classification

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

$\Delta \phi =\phi ,$

शब्दों में,

किसी भी लेबल का दुगुना आसन्न शीर्षों पर लेबलों का योग होता है,

विस्तारित (affine) ADE Dynkin आरेख पर हैं, जिनमें से 2 अनंत परिवार (A और D) और 3 अपवाद (E) हैं। परिणामी क्रमांकन पैमाने तक अद्वितीय है, और यदि सबसे छोटा मान 1 पर सेट किया गया है, तो अन्य संख्याएँ पूर्णांक हैं, जो 6 तक हैं।

साधारण ADE आरेख ़ एकमात्र ऐसे आरेख ़ हैं जो निम्नलिखित गुणों के साथ एक सकारात्मक लेबलिंग स्वीकार करते हैं:

किसी भी लेबल माइनस दो का दुगुना सन्निकट शीर्षों पर लेबलों का योग होता है।

लाप्लासियन के संदर्भ में, विषम समीकरण के सकारात्मक समाधान:

$\Delta \phi =\phi -2.$

परिणामी क्रमांकन अद्वितीय है (पैमाना 2 द्वारा निर्दिष्ट किया गया है), और इसमें पूर्णांक शामिल हैं; आगे का₈ वे 58 से 270 तक हैं, और 1968 की शुरुआत में देखे गए हैं।

यह भी देखें

• वर्णक्रमीय आकार विश्लेषण
• विद्युत नेटवर्क
• असतत लाप्लासियन का क्रोनकर योग
• असतत कलन

संदर्भ

• Sunada, T. (2008). "Discrete geometric analysis". Analysis on Graphs and Its Applications. Proceedings of Symposia in Pure Mathematics. Vol. 77. American Mathematical Society. pp. 51–86. ISBN 978-0-8218-9384-5.

बाहरी संबंध

• Ollivier, Yann (2004). "Spectral gap of a graph". Archived from the original on 2007-05-23.