مؤثر لابلاس المنفصل

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 117 صور
الموسوعة الحرة

في الرياضيات، يُعدّ مُؤثر لابلاس المتقطع نظيرًا لمؤثر لابلاس المتصل ، وهو مُعرّف بحيث يكون له معنى على الرسم البياني أو الشبكة المتقطعة . في حالة الرسم البياني ذي الأبعاد المحدودة (الذي يحتوي على عدد محدود من الحواف والرؤوس)، يُطلق على مُؤثر لابلاس المتقطع اسم مصفوفة لابلاس .

يُستخدم مُؤثر لابلاس المتقطع في مسائل فيزيائية مثل نموذج إيزينغ ونظرية الجاذبية الكمومية الحلقية ، وكذلك في دراسة الأنظمة الديناميكية المتقطعة . كما يُستخدم في التحليل العددي كبديل لمُؤثر لابلاس المستمر. تشمل تطبيقاته الشائعة معالجة الصور [ 1 ] ، حيث يُعرف باسم مُرشِّح لابلاس ، وفي التعلّم الآلي للتجميع والتعلّم شبه الموجّه على الرسوم البيانية المجاورة.

التعريفات

رسم بياني لابلاس

توجد تعريفات متعددة لمؤثر لابلاس المنفصل للرسوم البيانية ، وتختلف هذه التعريفات باختلاف الإشارة ومعامل المقياس (أحيانًا يتم حساب المتوسط ​​على الرؤوس المجاورة، وأحيانًا أخرى يتم الجمع فقط؛ وهذا لا يُحدث فرقًا بالنسبة للرسم البياني المنتظم ). التعريف التقليدي لمؤثر لابلاس للرسوم البيانية، الموضح أدناه، يُطابق مؤثر لابلاس السالب المستمر على نطاق ذي حدود حرة.

يتركجي=(V،هـ){\displaystyle G=(V,E)}ليكن رسمًا بيانيًا برؤوسV{\displaystyle V}والحوافهـ{\displaystyle E}. يتركϕ:V→R{\displaystyle \phi \colon V\to \mathbb {R} }لتكن دالة للرؤوس تأخذ قيمًا في حلقة . عندئذٍ، يكون لابلاس المنفصلΔ{\displaystyle \Delta }العمل علىϕ{\displaystyle \phi }يتم تعريفها بواسطة

(Δϕ)(v)=∑w:د(w،v)=1[ϕ(v)-ϕ(w)]{\displaystyle (\Delta \phi )(v)=\sum _{w:\,d(w,v)=1}\left[\phi (v)-\phi (w)\right]}

أيند(w،v){\displaystyle d(w,v)}يمثل المسافة بين الرأسين w و v في الرسم البياني. وبالتالي، فإن هذا المجموع يشمل أقرب الجيران للرأس v . بالنسبة للرسم البياني ذي عدد محدود من الحواف والرؤوس، فإن هذا التعريف مطابق لتعريف مصفوفة لابلاس . أي،ϕ{\displaystyle \phi }يمكن كتابتها كمتجه عمودي ؛ وهكذاΔϕ{\displaystyle \Delta \phi }هو حاصل ضرب متجه العمود ومصفوفة لابلاس، بينما(Δϕ)(v){\displaystyle (\Delta \phi )(v)}هو مجردv{\displaystyle v}المدخل رقم 1 من متجه المنتج.

إذا كان للرسم البياني حواف مرجحة، أي دالة ترجيحγ:هـ→R{\displaystyle \gamma \colon E\to \mathbb {R} }إذا تم إعطاء التعريف، فيمكن تعميمه على

(Δγϕ)(v)=∑w:د(w،v)=1γwv[ϕ(v)-ϕ(w)]{\displaystyle (\Delta _{\gamma }\phi )(v)=\sum _{w:\,d(w,v)=1}\gamma _{wv}\left[\phi (v)-\phi (w)\right]}

أينγwv{\displaystyle \gamma _{wv}}هل قيمة الوزن على الحافةwv∈هـ{\displaystyle wv\in E}.

يرتبط عامل المتوسط ​​ارتباطًا وثيقًا بعامل لابلاس المنفصل :

(مϕ)(v)=1درجة⁡v∑w:د(w،v)=1ϕ(w).{\displaystyle (M\phi )(v)={\frac {1}{\deg v}}\sum _{w:\,d(w,v)=1}\phi (w).}

لابلاس الشبكي

إضافةً إلى مراعاة ترابط العقد والحواف في الرسم البياني، تأخذ معاملات لابلاس للشبكات في الحسبان هندسة السطح (مثل الزوايا عند العقد). بالنسبة لشبكة مثلثات متعددة الأبعاد، فإن معامل لابلاس-بيلترامي لدالة قياسيةu{\displaystyle u}عند رأسأنا{\displaystyle i}يمكن تقريبها على النحو التالي

(Δu)أنا≡12أأنا∑ج∈شمال(أنا)(سرير أطفال⁡αأناج+سرير أطفال⁡βأناج)(uج-uأنا)،{\displaystyle (\Delta u)_{i}\equiv {\frac {1}{2A_{i}}}\sum _{j\in N(i)}(\cot \alpha _{ij}+\cot \beta _{ij})(u_{j}-u_{i}),}

أينشمال(أنا){\displaystyle N(i)}يشير إلى جوارأنا{\displaystyle i}(باستثناءأنا{\displaystyle i})αأناج{\displaystyle \alpha _{ij}}وβأناج{\displaystyle \beta _{ij}}هما الزاويتان المقابلتان للحافةأناج{\displaystyle ij}، وأأنا{\displaystyle A_{i}}هي مساحة رأسأنا{\displaystyle i}أي، على سبيل المثال، ثلث مجموع مساحات المثلثات الواقعة علىأنا{\displaystyle i}عادةً ما تكون إشارة مؤثر لابلاس-بيلترامي المتقطع معاكسة لإشارة مؤثر لابلاس العادي . ويمكن اشتقاق صيغة ظل التمام المذكورة أعلاه باستخدام العديد من الطرق المختلفة، من بينها العناصر المحدودة الخطية القطعية ، والحجوم المحدودة ، وحساب التفاضل والتكامل الخارجي المتقطع . [ 2 ]

لتسهيل الحساب، يتم ترميز لابلاس في مصفوفةل∈R|V|×|V|{\displaystyle L\in \mathbb {R} ^{|V|\times |V|}}بحيثلu=(Δu)أنا{\displaystyle Lu=(\Delta u)_{i}}. يتركج{\displaystyle C}لتكن مصفوفة الظل التمام (المتفرقة) ذات العناصر

جأناج={12(سرير أطفال⁡αأناج+سرير أطفال⁡βأناج)أناج هذا يمثل ميزة، أي ج∈شمال(أنا)،-∑ك∈شمال(أنا)جأناكأنا=ج،0خلاف ذلك{\displaystyle 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}}}

أينشمال(أنا){\displaystyle N(i)}يشير إلى جوارأنا{\displaystyle i}ودعم{\displaystyle M}لتكن مصفوفة الكتلة القطريةم{\displaystyle M}لمنأنا{\displaystyle i}المدخل رقم - على طول القطر هو مساحة الرأسأأنا{\displaystyle A_{i}}. ثمل=م-1ج{\displaystyle L=M^{-1}C}هو التقطيع المطلوب لمؤثر لابلاس.

يتم تقديم نظرة عامة أكثر شمولاً عن عوامل الشبكة في [ 3 ] .

الفروق المحدودة

يمكن أيضًا تسمية تقريبات لابلاس ، التي يتم الحصول عليها باستخدام طريقة الفروق المحدودة أو طريقة العناصر المحدودة ، بـ "لابلاس المنفصلة" . على سبيل المثال، يمكن تقريب لابلاس في بعدين باستخدام طريقة الفروق المحدودة ذات الخمس نقاط ، مما ينتج عنه:

Δو(x،y)≈و(x-ح،y)+و(x+ح،y)+و(x،y-ح)+و(x،y+ح)-4و(x،y)ح2،{\displaystyle \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-ح،y)،(x،y)،(x+ح،y)،(x،y-ح)،(x،y+ح)}.{\displaystyle \{(x-h,y),(x,y),(x+h,y),(x,y-h),(x,y+h)\}.}

إذا كان حجم الشبكة h = 1، فإن النتيجة هي لابلاس منفصل سالب على الرسم البياني، وهو ما يُعرف بشبكة المربعات . لا توجد قيود هنا على قيم الدالة f ( x , y ) على حدود شبكة المربعات، وبالتالي فإن هذه الحالة هي حالة انعدام المصدر عند الحدود، أي شرط حدودي بدون تدفق (يُعرف أيضًا بالعزل أو شرط نيومان الحدودي المتجانس ). نادرًا ما يُستخدم التحكم في متغير الحالة عند الحدود، كما هو الحال مع f ( x , y ) المعطاة على حدود الشبكة (يُعرف أيضًا بشرط ديريشليه الحدودي )، في لابلاس الرسوم البيانية، ولكنه شائع في تطبيقات أخرى.

تتمتع لابلاس المنفصلة متعددة الأبعاد على الشبكات المنتظمة المستطيلة المكعبة بخصائص خاصة جدًا، على سبيل المثال، هي عبارة عن مجموعات كرونكر من لابلاس المنفصلة أحادية البعد، انظر مجموع كرونكر للابلاس المنفصلة ، ​​وفي هذه الحالة يمكن حساب جميع قيمها الذاتية ومتجهاتها الذاتية بشكل صريح.

طريقة العناصر المحدودة

في هذا النهج، تُقسّم المجال إلى عناصر أصغر، غالبًا ما تكون مثلثات أو رباعيات أوجه، ولكن يمكن استخدام عناصر أخرى مثل المستطيلات أو متوازيات المستطيلات. ثم يُقرّب فضاء الحل باستخدام ما يُسمى بدوال الشكل ذات درجة مُحددة مسبقًا. بعد ذلك، تُحوّل المعادلة التفاضلية التي تحتوي على مُؤثر لابلاس إلى صيغة حسابية، ويُبنى نظام من المعادلات (مسائل خطية أو مسائل القيم الذاتية). عادةً ما تكون المصفوفات الناتجة متفرقة جدًا ويمكن حلها باستخدام الطرق التكرارية.

معالجة الصور

يُستخدم مُعامل لابلاس المتقطع بكثرة في معالجة الصور، مثل تطبيقات كشف الحواف وتقدير الحركة. [ 4 ] يُعرَّف لابلاس المتقطع بأنه مجموع المشتقات الثانية ، ويُحسب كمجموع الفروق بين أقرب جيران البكسل المركزي. ولأن مرشحات المشتقات غالبًا ما تتأثر بالتشويش في الصورة، يُسبق مُعامل لابلاس عادةً بمرشح تنعيم (مثل مرشح غاوسي ) لإزالة التشويش قبل حساب المشتق. وغالبًا ما يُدمج مرشح التنعيم ومرشح لابلاس في مرشح واحد. [ 5 ]

التنفيذ عبر تجزئة المؤثرات

بالنسبة للإشارات أحادية وثنائية وثلاثية الأبعاد، يمكن التعبير عن لابلاس المنفصل على أنه التفاف مع النوى التالية:

مرشح أحادي البعد:د→x2=[1-21]{\displaystyle {\vec {D}}_{x}^{2}={\begin{bmatrix}1&-2&1\end{bmatrix}}}،
فلتر ثنائي الأبعاد:دxy2=[0101-41010]{\displaystyle \mathbf {D} _{xy}^{2}={\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}}.

دxy2{\displaystyle \mathbf {D} _{xy}^{2}}يتوافق هذا مع صيغة الفروق المحدودة ( النموذج الخماسي النقاط ) التي سبق ذكرها. وهي مستقرة للحقول المتغيرة بسلاسة شديدة، ولكن بالنسبة للمعادلات ذات الحلول المتغيرة بسرعة، يلزم شكل أكثر استقرارًا وتجانسًا لمؤثر لابلاس، [ 6 ] مثل النموذج التساعي النقاط ، الذي يتضمن الأقطار:

فلتر ثنائي الأبعاد:دxy2=[0.250.50.250.5-30.50.250.50.25]{\displaystyle \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}}}،
فلتر ثلاثي الأبعاد:دxyz2{\displaystyle \mathbf {D} _{xyz}^{2}}يتم استخدام قالب النقاط السبع كما يلي:
الطائرة الأولى =[000010000]{\displaystyle {\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}}الطائرة الثانية =[0101-61010]{\displaystyle {\begin{bmatrix}0&1&0\\1&-6&1\\0&1&0\end{bmatrix}}}المستوى الثالث =[000010000]{\displaystyle {\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}}.
وباستخدام قالب مكون من 27 نقطة بواسطة: [ 7 ]
الطائرة الأولى =126[232363232]{\displaystyle {\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}}الطائرة الثانية =126[3636-886363]{\displaystyle {\frac {1}{26}}{\begin{bmatrix}3&6&3\\6&-88&6\\3&6&3\end{bmatrix}}}المستوى الثالث =126[232363232]{\displaystyle {\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}}.
مرشح n -D : للعنصرأx1،x2،...،xن{\displaystyle a_{x_{1},x_{2},\dots ,x_{n}}}من النواةدx1،x2،...،xن2،{\displaystyle \mathbf {D} _{x_{1},x_{2},\dots ,x_{n}}^{2},}
أx1،x2،...،xن={-2نلو s=ن،1لو s=ن-1،0خلاف ذلك،{\displaystyle 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 .

لاحظ أن النسخة ذات الأبعاد n ، والتي تستند إلى تعميم الرسم البياني لمؤثر لابلاس، تفترض أن جميع الجيران على مسافة متساوية، وبالتالي تؤدي إلى مرشح ثنائي الأبعاد التالي مع تضمين الأقطار، بدلاً من النسخة المذكورة أعلاه:

فلتر ثنائي الأبعاد:دxy2=[1111-81111].{\displaystyle \mathbf {D} _{xy}^{2}={\begin{bmatrix}1&1&1\\1&-8&1\\1&1&1\end{bmatrix}}.}

يتم استنتاج هذه النوى باستخدام النسب التفاضلية المنفصلة.

يمكن إثبات [ 8 ] [ 9 ] أن التقريب المنفصل التالي لمؤثر لابلاس ثنائي الأبعاد هو عبارة عن توليفة محدبة من مؤثرات الفرق

∇γ2=(1-γ)∇52+γ∇×2=(1-γ)[0101-41010]+γ[1/201/20-201/201/2]{\displaystyle \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 تحديدًا أفضل تقريب للتناظر الدوراني . [ 8 ] [ 9 ] [ 10 ] وفيما يتعلق بالإشارات ثلاثية الأبعاد، فقد ثبت [ 9 ] أنه يمكن تقريب مؤثر لابلاس بواسطة عائلة مؤثرات الفرق ذات المعلمتين.

∇γ1،γ22=(1-γ1-γ2)∇72+γ1∇+32+γ2∇×32)،{\displaystyle \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}),}

أين

(∇72و)0،0،0=و-1،0،0+و+1،0،0+و0،-1،0+و0،+1،0+و0،0،-1+و0،0،+1-6و0،0،0،{\displaystyle (\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},}
(∇+32و)0،0،0=14(و-1،-1،0+و-1،+1،0+و+1،-1،0+و+1،+1،0+و-1،0،-1+و-1،0،+1+و+1،0،-1+و+1،0،+1+و0،-1،-1+و0،-1،+1+و0،+1،-1+و0،+1،+1-12و0،0،0)،{\displaystyle (\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}),}
(∇×32و)0،0،0=14(و-1،-1،-1+و-1،-1،+1+و-1،+1،-1+و-1،+1،+1+و+1،-1،-1+و+1،-1،+1+و+1،+1،-1+و+1،+1،+1-8و0،0،0).{\displaystyle (\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}).}

يمكن إثبات ذلك من خلال تحليل متسلسلة تايلور، حيث أن مجموعات قيمγ1{\displaystyle \gamma _{1}}وγ2{\displaystyle \gamma _{2}}والتي3γ1+6γ2=2{\displaystyle 3\gamma _{1}+6\gamma _{2}=2}تقديم أفضل التقريبات للتناظر الدوراني.

التنفيذ من خلال إعادة البناء المستمر

يمكن اعتبار الإشارة المنفصلة، ​​التي تتكون من صور، تمثيلاً منفصلاً لدالة متصلةو(ر¯){\displaystyle f({\bar {r}})}، حيث متجه الإحداثياتر¯∈Rن{\displaystyle {\bar {r}}\in R^{n}}ومجال القيمة حقيقيو∈R{\displaystyle f\in R}وبالتالي، فإن عملية الاشتقاق قابلة للتطبيق مباشرة على الدالة المتصلة.و{\displaystyle f}. على وجه الخصوص، يمكن إعادة بناء أي صورة منفصلة، ​​مع افتراضات معقولة حول عملية التقطيع، على سبيل المثال بافتراض وظائف محدودة النطاق، أو وظائف قابلة للتوسيع بالمويجات، وما إلى ذلك، عن طريق وظائف الاستيفاء ذات السلوك الجيد التي تقوم عليها صياغة إعادة البناء، [ 11 ]

و(ر¯)=∑ك∈كوكμك(ر¯){\displaystyle f({\bar {r}})=\sum _{k\in K}f_{k}\mu _{k}({\bar {r}})}

أينوك∈R{\displaystyle f_{k}\in R}هي تمثيلات منفصلة لـو{\displaystyle f}على الشبكةك{\displaystyle K}وμك{\displaystyle \mu _{k}}هي دوال استيفاء خاصة بالشبكةك{\displaystyle K}على شبكة منتظمة، مثل الصور، وبالنسبة للدوال محدودة النطاق، تكون دوال الاستيفاء ثابتة عند الإزاحة، مما يؤدي إلى μك(ر¯)=μ(ر¯-ر¯ك){\displaystyle \mu _{k}({\bar {r}})=\mu ({\bar {r}}-{\bar {r}}_{k})}معμ{\displaystyle \mu }كونها دالة sinc ممتدة بشكل مناسب معرفة فين{\displaystyle n}-الأبعاد أير¯=(x1،x2...xن)تي{\displaystyle {\bar {r}}=(x_{1},x_{2}...x_{n})^{T}}. تقديرات أخرى لـμ{\displaystyle \mu }على الشبكات المنتظمة، تكون دوال غاوسية متمددة بشكل مناسب فين{\displaystyle n}-الأبعاد. وبناءً على ذلك، يصبح لابلاس المتقطع نسخة متقطعة من لابلاس المستمرو(ر¯){\displaystyle f({\bar {r}})}

∇2و(ر¯ك)=∑ك′∈كوك′(∇2μ(ر¯-ر¯ك′))|ر¯=ر¯ك{\displaystyle \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}}}

وهو بدوره عبارة عن عملية التفاف مع لابلاس دالة الاستيفاء على الشبكة المنتظمة (الصورة).ك{\displaystyle K}تتمثل إحدى مزايا استخدام الدوال الغاوسية كدوال استيفاء في أنها تُنتج مؤثرات خطية، بما في ذلك مؤثرات لابلاس، خالية من التشوهات الدورانية لنظام الإحداثيات الذي يتم فيهو{\displaystyle f}يتم تمثيلها عبروك{\displaystyle f_{k}}، فين{\displaystyle n}الأبعاد، وهي حساسة للتردد بحكم تعريفها. لا يقتصر نطاق المؤثر الخطي على نطاق محدود فير¯{\displaystyle {\bar {r}}}ليس فقط في المجال، بل أيضًا في نطاق فعال في مجال التردد (أو فضاء المقياس الغاوسي) والذي يمكن التحكم فيه بشكل صريح من خلال تباين التوزيع الغاوسي بطريقة منهجية. يمكن تنفيذ الترشيح الناتج بواسطة مرشحات قابلة للفصل وتمثيلات التخفيف (معالجة الإشارات) / الهرم (معالجة الصور) لمزيد من الكفاءة الحسابية.ن{\displaystyle n}-الأبعاد. بعبارة أخرى، يمكن توليد مرشح لابلاس المنفصل بأي حجم بسهولة باستخدام لابلاس غاوسي مُعَيَّن، بحجم مكاني يُناسب احتياجات تطبيق مُحدد، ويتم التحكم فيه بواسطة تباينه. كما يمكن تطبيق أحاديات الحدود، وهي عوامل غير خطية، باستخدام أسلوب إعادة بناء وتقريب مُشابه، شريطة أن تكون الإشارة مُعَيَّنة بشكل كافٍ. وبالتالي، يُمكن تحقيق عوامل غير خطية مثل مُوتر البنية ومُوتر البنية المُعمَّم ، والتي تُستخدم في التعرف على الأنماط لتحقيقها الأمثلية الكلية للمربعات الصغرى في تقدير الاتجاه.

نطاق

يُعد طيف لابلاس المنفصل على شبكة لانهائية ذا أهمية بالغة؛ لأنه مؤثر ذاتي الترافق ، وبالتالي فإن له طيفًا حقيقيًا. للاتفاقيةΔ=أنا-م{\displaystyle \Delta =I-M}علىZ{\displaystyle Z}، يقع الطيف ضمن[0،2]{\displaystyle [0,2]}(حيث أن عامل المتوسط ​​له قيم طيفية في[-1،1]{\displaystyle [-1,1]}ويمكن ملاحظة ذلك أيضًا بتطبيق تحويل فورييه. تجدر الإشارة إلى أن لابلاس المتقطع على شبكة لانهائية له طيف متصل تمامًا، وبالتالي، لا توجد له قيم ذاتية أو دوال ذاتية.

النظريات

إذا كان الرسم البياني عبارة عن شبكة مربعة لانهائية ، فيمكن إثبات أن هذا التعريف لمؤثر لابلاس يطابق مؤثر لابلاس المتصل في حالة الشبكة الدقيقة للغاية. وبالتالي، على سبيل المثال، على شبكة أحادية البعد لدينا

∂2F∂x2=ليمϵ→0[F(x+ϵ)-F(x)]-[F(x)-F(x-ϵ)]ϵ2.{\displaystyle {\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}،

دϕأنادت=-ك∑جأأناج(ϕأنا-ϕج)=-ك(ϕأنا∑جأأناج-∑جأأناجϕج)=-ك(ϕأنا درجة⁡(vأنا)-∑جأأناجϕج)=-ك∑ج(دلتاأناج درجة⁡(vأنا)-أأناج)ϕج=-ك∑ج(لأناج)ϕج.{\displaystyle {\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}}}

في تدوين المصفوفة والمتجه،

دϕدت=-ك(د-أ)ϕ=-كلϕ،{\displaystyle {\begin{aligned}{\frac {d\phi }{dt}}&=-k(D-A)\phi \\&=-kL\phi ,\end{aligned}}}

مما يعطي

دϕدت+كلϕ=0.{\displaystyle {\frac {d\phi }{dt}}+kL\phi =0.}

لاحظ أن هذه المعادلة تأخذ نفس شكل معادلة الحرارة ، حيث تحل المصفوفة − L محل مؤثر لابلاس∇2{\textstyle \nabla ^{2}}ومن ثم، "مؤثر لابلاس البياني".

لإيجاد حل لهذه المعادلة التفاضلية، نطبق التقنيات القياسية لحل المعادلات التفاضلية المصفوفية من الرتبة الأولى . أي نكتبϕ{\textstyle \phi }كمزيج خطي من المتجهات الذاتيةvأنا{\textstyle \mathbf {v} _{i}}من L (بحيثلvأنا=λأناvأنا{\textstyle L\mathbf {v} _{i}=\lambda _{i}\mathbf {v} _{i}}) بمعاملات تعتمد على الزمن،ϕ(ت)=∑أناجأنا(ت)vأنا.{\textstyle \phi (t)=\sum _{i}c_{i}(t)\mathbf {v} _{i}.}

بالتعويض في التعبير الأصلي (لأن L مصفوفة متناظرة)، فإن متجهاتها الذاتية ذات المعيار الواحدvأنا{\textstyle \mathbf {v} _{i}}(متعامدة):

0=د(∑أناجأنا(ت)vأنا)دت+كل(∑أناجأنا(ت)vأنا)=∑أنا[دجأنا(ت)دتvأنا+كجأنا(ت)لvأنا]=∑أنا[دجأنا(ت)دتvأنا+كجأنا(ت)λأناvأنا]⇒0=دجأنا(ت)دت+كλأناجأنا(ت)،{\displaystyle {\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}}}

حلها هو

جأنا(ت)=جأنا(0)هـ-كλأنات.{\displaystyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}.}

كما هو موضح سابقًا، القيم الذاتيةλأنا{\textstyle \lambda _{i}}إذا كانت قيم L غير سالبة، فهذا يدل على أن حل معادلة الانتشار يقترب من حالة التوازن، لأنه إما يتناقص أُسّيًا أو يبقى ثابتًا. وهذا يدل أيضًا على أنه بالنظر إلىλأنا{\textstyle \lambda _{i}}والشرط الأوليجأنا(0){\textstyle c_{i}(0)}يمكن إيجاد الحل في أي وقت t . [ 12 ]

للعثور علىجأنا(0){\textstyle c_{i}(0)}لكلأنا{\textstyle i}من حيث الحالة الأولية العامةϕ(0){\textstyle \phi (0)}ببساطة قم بالإسقاطϕ(0){\textstyle \phi (0)}على المتجهات الذاتية ذات المعيار الواحدvأنا{\textstyle \mathbf {v} _{i}}؛

جأنا(0)=⟨ϕ(0)،vأنا⟩.{\displaystyle c_{i}(0)=\left\langle \phi (0),\mathbf {v} _{i}\right\rangle .}

وقد طُبّق هذا النهج على نمذجة انتقال الحرارة الكمية على الشبكات غير المنتظمة. [ 13 ] [ 14 ]

في حالة الرسوم البيانية غير الموجهة، ينجح هذا الأمر لأنل{\textstyle L}المصفوفة متناظرة، وبحسب نظرية الطيف ، فإن متجهاتها الذاتية جميعها متعامدة. لذا فإن الإسقاط على المتجهات الذاتية لـل{\textstyle L}هو ببساطة تحويل إحداثيات متعامدة للحالة الأولية إلى مجموعة من الإحداثيات التي تتلاشى بشكل أسي وبشكل مستقل عن بعضها البعض.

سلوك التوازن

لفهمليمت→∞ϕ(ت){\textstyle \lim _{t\to \infty }\phi (t)}الشروط الوحيدةجأنا(ت)=جأنا(0)هـ-كλأنات{\textstyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}}أما الباقي فهو حيثλأنا=0{\textstyle \lambda _{i}=0}، منذ

ليمت→∞هـ-كλأنات={0،لوλأنا>01،لوλأنا=0{\displaystyle \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}.

لأن بحكم التعريف،∑جلأناج=0{\textstyle \sum _{j}L_{ij}=0}، المتجهv1{\textstyle \mathbf {v} ^{1}}أحدها موجود في النواة. إذا كان هناكك{\textstyle k}إذا كانت المكونات المتصلة منفصلة في الرسم البياني، فيمكن تقسيم هذا المتجه الذي يحتوي على جميع القيم 1 إلى مجموعك{\textstyle k}مستقلλ=0{\textstyle \lambda =0}المتجهات الذاتية المكونة من واحدات وأصفار، حيث يتوافق كل مكون متصل مع متجه ذاتي يحتوي على واحدات في العناصر الموجودة في المكون المتصل وأصفار في أي مكان آخر.

نتيجة لذلك، بالنسبة لشرط ابتدائي معينϕ(0){\textstyle \phi (0)}بالنسبة للرسم البياني معشمال{\textstyle N}الرؤوس

ليمت→∞ϕ(ت)=⟨ϕ(0)،v1⟩v1{\displaystyle \lim _{t\to \infty }\phi (t)=\left\langle \phi (0),\mathbf {v^{1}} \right\rangle \mathbf {v^{1}} }

أين

v1=1شمال[1،1،...،1]{\displaystyle \mathbf {v^{1}} ={\frac {1}{\sqrt {N}}}[1,1,\ldots ,1]}

لكل عنصرϕج{\textstyle \phi _{j}}لϕ{\textstyle \phi }أي لكل رأسج{\textstyle j}في الرسم البياني، يمكن إعادة كتابتها على النحو التالي

ليمت→∞ϕج(ت)=1شمال∑أنا=1شمالϕأنا(0).{\displaystyle \lim _{t\to \infty }\phi _{j}(t)={\frac {1}{N}}\sum _{i=1}^{N}\phi _{i}(0).}

بمعنى آخر، في حالة الاستقرار، تكون قيمةϕ{\textstyle \phi }يتقارب الناتج إلى القيمة نفسها عند كل رأس من رؤوس الرسم البياني، وهي متوسط ​​القيم الابتدائية عند جميع الرؤوس. وبما أن هذا هو حل معادلة انتشار الحرارة، فإن هذا الأمر منطقي تمامًا. نتوقع أن تتبادل العناصر المتجاورة في الرسم البياني الطاقة حتى تتوزع هذه الطاقة بالتساوي بين جميع العناصر المتصلة ببعضها.

مثال على عامل التشغيل على شبكة

تُظهر هذه الصورة المتحركة (GIF) تطور الانتشار، كما تم حله باستخدام تقنية لابلاس البيانية. يتم إنشاء رسم بياني على شبكة، حيث يرتبط كل بكسل في الرسم البياني بثمانية بكسلات مجاورة له. تنتشر القيم في الصورة بسلاسة إلى جيرانها بمرور الوقت عبر هذه الروابط. تبدأ هذه الصورة تحديدًا بثلاث قيم نقطية قوية تنتشر ببطء إلى جيرانها. في النهاية، يستقر النظام بأكمله عند نفس القيمة عند حالة التوازن.

يُظهر هذا القسم مثالاً على دالةϕ{\textstyle \phi }ينتشر هذا التوزيع بمرور الوقت عبر رسم بياني. في هذا المثال، تم إنشاء الرسم البياني على شبكة ثنائية الأبعاد منفصلة، ​​حيث ترتبط كل نقطة على الشبكة بنقاطها الثمانية المجاورة. تم تحديد ثلاث نقاط أولية بقيمة موجبة، بينما بقية القيم في الشبكة تساوي صفرًا. بمرور الوقت، يعمل التضاؤل ​​الأسي على توزيع القيم عند هذه النقاط بالتساوي في جميع أنحاء الشبكة.

يُقدَّم أدناه كود المصدر الكامل لبرنامج Matlab الذي استُخدم لإنشاء هذا الرسم المتحرك. يُظهر الكود عملية تحديد الشروط الابتدائية، وإسقاط هذه الشروط الابتدائية على المتجهات الذاتية لمصفوفة لابلاس، ومحاكاة التضاؤل ​​الأسي لهذه الشروط الابتدائية المُسقطة.

N = 20 ; % عدد البكسلات على طول بُعد من أبعاد الصورة A = zeros ( N , N ); % الصورة Adj = zeros ( N * N , N * N ); % مصفوفة التجاوراستخدم 8 جيران، واملأ مصفوفة التجاور 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% فيما يلي الكود الرئيسي الذي يحسب حل المعادلة التفاضلية Deg = diag ( sum ( Adj , 2 )); % حساب مصفوفة الدرجة L = Deg - Adj ; % حساب مصفوفة لابلاس بدلالة مصفوفات الدرجة والتجاور [ V , D ] = eig ( L ); % حساب القيم الذاتية/المتجهات الذاتية لمصفوفة لابلاس D = diag ( D );% الشروط الابتدائية (ضع بعض القيم الموجبة الكبيرة حول القيم الأخرى، و % اجعل كل شيء آخر أصفارًا) 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 ; % تحويل الحالة الابتدائية إلى نظام إحداثيات % المتجهات الذاتية لـ t = 0 : 0.05 : 5 % التكرار عبر الأوقات وتضاؤل ​​كل مكون ابتدائي Phi = C0V.*exp(-D * t); % التضاؤل ​​الأسي لكل مكون Phi = V * Phi ; % التحويل من نظام إحداثيات المتجهات الذاتية إلى نظام الإحداثيات الأصلي Phi = reshape ( Phi , N , N ) ; % عرض النتائج وكتابتها في ملف GIF imagesc ( Phi ); caxis ([ 0 , 10 ]); title ( sprintf ( 'Diffusion t = %3f' , t )); frame = getframe ( 1 ); im = frame2im ( frame ); [ imind , cm ] = rgb2ind ( im , 256 ); إذا كان t يساوي 0، فاكتب ( imind ، cm ، 'out.gif' ، 'gif' ، 'Loopcount' ، inf ، 'DelayTime' ، 0.1 )؛ وإلا فاكتب ( imind ، cm ، 'out.gif' ، 'gif' ، ' WriteMode' ، 'append' ، 'DelayTime' ، 0.1 ) .

مؤثر شرودنغر المنفصل

يتركP:V→R{\displaystyle P\colon V\rightarrow R}لتكن دالة جهد معرفة على الرسم البياني. لاحظ أنه يمكن اعتبار P عامل ضرب يعمل قطريًا علىϕ{\displaystyle \phi }

(Pϕ)(v)=P(v)ϕ(v).{\displaystyle (P\phi )(v)=P(v)\phi (v).}

ثمح=Δ+P{\displaystyle H=\Delta +P}هو عامل شرودنغر المنفصل ، وهو نظير لعامل شرودنغر المستمر .

إذا كان عدد الحواف التي تلتقي عند رأس ما محدودًا بشكل منتظم، وكان الجهد محدودًا، فإن H يكون محدودًا وذاتيًا .

يمكن دراسة الخصائص الطيفية لهذا الهاميلتوني باستخدام نظرية ستون ؛ وهذا نتيجة للازدواجية بين المجموعات المرتبة جزئياً والجبر البولياني .

في الشبكات المنتظمة، يمتلك المشغل عادةً حلولًا للموجات المتنقلة بالإضافة إلى حلول تحديد موقع أندرسون ، اعتمادًا على ما إذا كان الجهد دوريًا أم عشوائيًا.

تُعطى دالة غرين لمؤثر شرودنغر المنفصل في صيغة المُحلِّل بواسطة

جي(v،w؛λ)=⟨دلتاv|1ح-λ|دلتاw⟩{\displaystyle G(v,w;\lambda )=\left\langle \delta _{v}\left|{\frac {1}{H-\lambda }}\right|\delta _{w}\right\rangle }

أيندلتاw{\displaystyle \delta _{w}}من المفهوم أن دالة دلتا كرونكر موجودة على الرسم البياني:دلتاw(v)=دلتاwv{\displaystyle \delta _{w}(v)=\delta _{wv}}أي أن قيمتها تساوي 1 إذا كانت v = w و 0 خلاف ذلك.

للثابتw∈V{\displaystyle w\in V}وλ{\displaystyle \lambda }عدد مركب، دالة غرين التي تُعتبر دالة لـ v هي الحل الوحيد لـ

(ح-λ)جي(v،w؛λ)=دلتاw(v).{\displaystyle (H-\lambda )G(v,w;\lambda )=\delta _{w}(v).}

تصنيف ADE

بعض المعادلات التي تتضمن لابلاس المنفصل لا تملك حلولاً إلا على مخططات دينكين البسيطة (جميع الحواف من الرتبة 1)، وهي مثال على تصنيف ADE . وبالتحديد، الحلول الموجبة الوحيدة للمعادلة المتجانسة هي:

Δϕ=ϕ،{\displaystyle \Delta \phi =\phi ,}

بالكلمات،

"ضعف أي تسمية يساوي مجموع التسميات الموجودة على الرؤوس المجاورة."

تُعرض هذه البيانات على مخططات دينكين الموسعة (الخطية) ADE، والتي تتضمن عائلتين لانهائيتين (A وD) وثلاثة استثناءات (E). ويكون الترقيم الناتج فريدًا ضمن المقياس، وإذا تم تحديد أصغر قيمة عند 1، فإن الأرقام الأخرى تكون أعدادًا صحيحة، تصل إلى 6.

تُعدّ الرسوم البيانية العادية من نوع ADE هي الرسوم البيانية الوحيدة التي تسمح بتسمية موجبة بالخاصية التالية:

ضعف أي تسمية مطروحًا منها اثنان يساوي مجموع التسميات الموجودة على الرؤوس المتجاورة.

من حيث لابلاس، الحلول الموجبة للمعادلة غير المتجانسة:

Δϕ=ϕ-2.{\displaystyle \Delta \phi =\phi -2.}

الترقيم الناتج فريد (يتم تحديد المقياس بواسطة "2")، ويتكون من أعداد صحيحة؛ بالنسبة لـ E 8 تتراوح من 58 إلى 270، وقد لوحظت في وقت مبكر من عام 1968. [ 15 ]

انظر أيضاً

مراجع

  1. ↑ ليفينثال، دانيال (خريف 2011). "معالجة الصور" (ملف PDF) . جامعة واشنطن . تاريخ الاسترجاع: 1 ديسمبر 2019 .
  2. ↑ كرين، ك.؛ دي غويس، ف.؛ ديسبرون، م.؛ شرودر، ب. (2013). "معالجة الهندسة الرقمية باستخدام حساب التفاضل والتكامل الخارجي المنفصل" . دورات ACM SIGGRAPH 2013. SIGGRAPH '13. المجلد 7. الصفحات 1-126. doi : 10.1145 / 2504435.2504442 .  
  3. ↑ رويتر، م.؛ بياسوتي، س.؛ جيورجي، د.؛ باتاني، ج.؛ سبانيولو، م. (2009). "مؤثرات لابلاس-بيلترامي المنفصلة لتحليل الأشكال وتجزئتها". الحوسبة والرسومات . 33 (3): 381-390. CiteSeerX 10.1.1.157.757 . doi : 10.1016/j.cag.2009.03.005 . 
  4. ↑ فورسيث، د.أ.؛ بونس، ج. (2003). "رؤية الحاسوب". الحواسيب والرسومات . 33 (3): 381-390 . CiteSeerX 10.1.1.157.757 . doi : 10.1016/j.cag.2009.03.005 . 
  5. ↑ ماثيس، دون (14 فبراير 2001). "مرشح لوغاريتمي" . جامعة ماركيت . تم الاسترجاع في 1 ديسمبر 2019 .
  6. ↑ بروفاتاس، نيكولاس؛ إلدر، كين (13-10-2010). أساليب مجال الطور في علوم وهندسة المواد (ملف PDF) . فاينهايم، ألمانيا: Wiley-VCH Verlag GmbH & Co. KGaA. ص 219. doi : 10.1002/9783527631520 . ISBN  978-3-527-63152-0.
  7. ↑ أورايلي، هـ.؛ بيك، جيفري م. (2006). "عائلة من تقريبات لابلاس المنفصلة ذات الاستنسل الكبير في ثلاثة أبعاد" (ملف PDF) . المجلة الدولية للطرق العددية في الهندسة : 1-16 .
  8. 1 2 ليندبيرج، تي، "مساحة المقياس للإشارات المنفصلة"، PAMI(12)، العدد 3، مارس 1990، ص 234-254.
  9. 1 2 3 ليندبيرغ، ت.، نظرية فضاء المقياس في رؤية الحاسوب، دار نشر كلوير الأكاديمية، 1994 ، رقم ISBN 0-7923-9418-6.
  10. ↑ باترا، مايكل؛ كارتونين، ميكو (2006). "قوالب ذات خطأ تجزئة متساوي الخواص للمؤثرات التفاضلية". الطرق العددية للمعادلات التفاضلية الجزئية . 22 (4): 936-953 . doi : 10.1002/num.20129 . ISSN 0749-159X . S2CID 123145969 .  
  11. ↑ بيغون، ج. (2006). الرؤية مع التوجيه . سبرينغر. doi : 10.1007/b138918 . ISBN 978-3-540-27322-6.
  12. ↑ نيومان، مارك (2010). الشبكات: مقدمة . مطبعة جامعة أكسفورد. ISBN 978-0-19-920665-0.
  13. ↑ يافاري، ر.؛ كول، ك.د.؛ راو، ب.ك. (2020). "نقل الحرارة الحسابي باستخدام نظرية الرسم البياني الطيفي: التحقق الكمي" . المجلة الدولية للعلوم الحرارية . 153 106383. Bibcode : 2020IJTS..15306383C . doi : 10.1016/j.ijthermalsci.2020.106383 .
  14. ↑ كول، ك.د.؛ رينش، أ.؛ راو، ب.ك. (2022). "دوال غرين المنفصلة ونظرية الرسم البياني الطيفي لنمذجة حرارية فعالة حسابيًا" . المجلة الدولية لانتقال الحرارة والكتلة . 183 122112. Bibcode : 2022IJHMT.18322112C . doi : 10.1016/j.ijheatmasstransfer.2021.122112 . S2CID 244652819 . 
  15. ↑ بورباكي، نيكولاس (2002) [1968]، الزمر وجبر لي: الفصول 4-6 ، عناصر الرياضيات، ترجمة أندرو بريسلي، سبرينغر، ISBN 978-3-540-69171-6
  • أوليفييه، يان (2004). "الفجوة الطيفية للرسم البياني" . مؤرشف من الأصل بتاريخ 23-05-2007.