מתמטיקה שימושית ו־AᵀA
לפלסיאן, הארקה ורשתות
Networks and the Graph Laplacian
מטריצת incidence מחשבת הפרשי פוטנציאל; L=AᵀCA מחבר אותם למאזן זרימות. L סינגולרית עד שמקבעים פוטנציאל אחד בכל רכיב קשיר.
- 1נקודת פתיחהמה כבר ידוע ומה השאלה?
- 2ניבוימה יקרה במקרה הפשוט?
- 3המחשהמה באמת משתנה בתמונה?
- 4ניסוח והצדקהשם, נוסחה ולמה היא נכונה
- 5בדיקהדוגמה, תרגול ומשוב
- 6העברהמקרה חדש והמשך המסלול
שאלה לפני נוסחה
מה אנחנו מנסים לראות?
לבנות לפלסיאן של גרף מ־incidence ומוליכויות, לפרש Lv=b כמאזן זרימות, ולהסביר סינגולריות, הארקה, אנרגיה וחיבוריות.
פוטנציאל הוא כמו גובה, מוליכות היא רוחב צינור, וזרימה נעה מן הגבוה לנמוך. A מודדת הפרשי גובה על הקשתות, C ממירה אותם לזרימות, ו־Aᵀ מחזירה לכל צומת את המאזן של כל הקשתות שנפגשות בו.
לפני ההמחשה: קראו רק את הכותרת “פוטנציאל, הפרש, זרימה ומאזן”. מה לדעתכם ישתנה, מה יישאר קבוע, ואיזה סימן בתמונה יוכל להפריך את הניבוי?
לראות לפני שמחשבים · המקרה הפשוט ביותר
פוטנציאל, הפרש, זרימה ומאזן
האיור מציג ארבעה צמתים וחמש קשתות, עם פוטנציאל בכל צומת וזרימה מחושבת בכל קשת.
מה כדאי לגלות: בצמתים ללא הזרקה סכום הזרימות היוצאות הוא אפס. הצומת המוארק קולט בדיוק את הזרם שהוזרק בצומת המקור.
אחרי שראינו
בסוף השיעור תוכלו
- לבנות A, C ו־L=AᵀCA מגרף משוקלל ולפרש כל איבר.
- לחשב הפרשי פוטנציאל, זרימות ומאזנים עם מוסכמת סימנים עקבית.
- להסביר מדוע L סינגולרית, כיצד הארקה יוצרת מערכת חיובית בהחלט, וכיצד מספר הרכיבים קובע את ממד הגרעין.
נותנים שמות למה שראינו
מושגים שנשתמש בהם
- מטריצת incidence A
- מטריצה עם שורה לכל קשת: −1 בזנב, +1 בראש ואפס בשאר הצמתים.
- מטריצת מוליכויות C
- מטריצה אלכסונית חיובית; cₖ קובעת כמה זרימה נוצרת מהפרש נתון בקשת k.
- לפלסיאן L
- המטריצה L=AᵀCA; האלכסון מכיל סכום מוליכויות והאיברים מחוץ לאלכסון הם מוליכויות שליליות בין שכנים.
- הארקה
- קיבוע פוטנציאל של צומת אחד, בדרך כלל לאפס, כדי להסיר את חופש הוספת הקבוע.
- מאזן b
- וקטור הזרקה נטו בצמתים; Lv=b מבטא שזרימה יוצאת נטו שווה להזרקה.
- התנגדות אפקטיבית
- יחס הפרש הפוטנציאלים לזרם הכולל בין שני צמתים ברשת שלמה.
מהמילים אל הסימנים
כותבים את הפעולה שכבר ראינו
פתחו את הנוסחה רק אחרי שאתם יכולים לומר במילים מה כל פעולה אמורה לעשות. בשלב הבא נצדיק אותה צעד אחר צעד.
להצגת נוסחת המפתח
קראו כל סימן כפעולה, לא כמשהו שצריך לשנןd=Av; q=−Cd; L=AᵀCA; Lv=bמרכיבים את הפעולות
מהתמונה אל הנוסחה — הגזירה, בלי לדלג על הצעדים
בוחרים כיוון חשבונאי
כיוון הקשת קובע רק סימן בשורת A. אם השורה היא −1 בזנב ו־+1 בראש, אז Av הוא פוטנציאל הראש פחות הזנב.
d=Av; dₖ=vhead−vtailממירים הפרש לזרימה פיזיקלית
זרימה חיובית בכיוון החץ עוברת מן פוטנציאל גבוה לנמוך, ולכן היא מינוס המוליכות כפול ההפרש האלגברי.
q=−Cd=−CAvמחזירים מאזן לצמתים
Aᵀq הוא כניסה נטו לפי מוסכמת החץ. לכן −Aᵀq=AᵀCAv הוא יציאה נטו, והיא שווה להזרקה b.
Lv=b; L=AᵀCAקוראים את מבנה L
כל קשת מוסיפה c לשני איברי האלכסון ו־−c לשני המקומות הסימטריים בין קצותיה. לכן סכום כל שורה הוא אפס.
Lii=Σj cij; Lij=−cij; L𝟙=0מפרשים אנרגיה
האנרגיה היא סכום מוליכות כפול ריבוע הפרש בכל קשת. היא אינה שלילית ואפסה בדיוק כאשר הפוטנציאל קבוע בכל רכיב קשיר.
vᵀLv=(Av)ᵀC(Av)=Σcₖdₖ²≥0מבינים סינגולריות וחיבוריות
הוספת קבוע לכל הפוטנציאלים אינה משנה שום הפרש. בגרף עם c רכיבים אפשר לבחור קבוע נפרד בכל רכיב, ולכן dim N(L)=c.
rank(L)=n−cמאריקים ומקבלים יחידות
מסירים שורה ועמודה של צומת מוארק בכל רכיב. בגרף קשיר המטריצה המצומצמת חיובית בהחלט ואפשר לפתור פוטנציאלים יחידים.
Lreduced vred=bred
עכשיו רואים את השיטה בפעולה
דוגמאות פתורות, צעד אחר צעד
רשת חמישה נגדים
בגרף עם הקשתות 1–2,1–3,2–3,1–4,2–4, כל המוליכויות 1. קבעו v₁=1,v₄=0 ומצאו v₂,v₃.
בצומת 2 אין הזרקה, ולכן 3v₂−v₁−v₃−v₄=0.
בצומת 3 אין הזרקה, ולכן 2v₃−v₁−v₂=0.
מציבים v₁=1,v₄=0 ופותרים: 3v₂−v₃=1, −v₂+2v₃=1.
מתקבל v₂=0.6,v₃=0.8.
הזרם היוצא מצומת 1 הוא (1−0.6)+(1−0.8)+(1−0)=1.6.
לכן מוליכות הרשת בין 1 ל־4 היא I/V=1.6, והאנרגיה vᵀLv=IV=1.6.
v=(1,0.6,0.8,0), I=1.6, conductance=1.6.
משולש עם מוליכויות שונות
במשולש עם c₁=1,c₂=4,c₃=9 בנו את L.
כל קשת מוסיפה בלוק c[[1,−1],[−1,1]] במיקומי שני קצותיה.
חיבור שלושת הבלוקים נותן L=[[10,−1,−9],[−1,5,−4],[−9,−4,13]] לפי סדר הקשתות 1–2,2–3,3–1.
סכומי השורות אפס, ולכן L𝟙=0 והמטריצה סינגולרית.
לאחר הארקת צומת 3 מתקבלת [[10,−1],[−1,5]], שהדטרמיננטה שלה 49>0 ולכן היא חיובית בהחלט.
L חיובית למחצה; המטריצה המוארקת חיובית בהחלט.
איפה זה פוגש את העולם
יישום
רשתות חשמל, דירוג קבוצות, consensus, דיפוזיה וניתוח קהילות משתמשים בלפלסיאן. אותה משוואה אומרת פעם שזרם נשמר, פעם שדירוגים מתאימים להפרשי תוצאות ופעם שכל צומת מתקרב לממוצע שכניו.
מלכודת נפוצה
מה כדאי לבדוק
לכתוב q=CAv ולכנות אותו זרם מן הזנב לראש. עם ההגדרה d=vhead−vtail, החוק הפיזיקלי הוא q=−Cd. אפשר לבחור מוסכמה אחרת, אך חייבים לשמור אותה באופן עקבי עד משוואת המאזן.
בודקים שהרעיון יושב
תרגול ומשוב
בדיקת הבנה
בחרו תשובה ורק אז בדקו את עצמכם
בחרו אחת מהאפשרויות כדי להמשיך.
עכשיו אתם
אתגר קצר
בשרשרת של ארבעה צמתים ושלוש מוליכויות שוות 1, האריקו את צומת 4 והזריקו זרם 1 לצומת 1. מצאו את הפוטנציאלים ואת ההתנגדות האפקטיבית.
רמז ראשון
אותו זרם 1 חייב לעבור בכל שלוש הקשתות בטור. כל קשת יוצרת ירידת פוטנציאל 1.
הצגת דרך הפתרון
- מן ההארקה v₄=0 והקשת האחרונה דורשת v₃−v₄=1, לכן v₃=1.
- באופן דומה v₂−v₃=1 ולכן v₂=2, ו־v₁−v₂=1 ולכן v₁=3.
- הפוטנציאלים הם (3,2,1,0).
- הפרש הקצוות הוא 3 עבור זרם 1, לכן ההתנגדות האפקטיבית היא 3 והמוליכות 1/3.
מימוש הנושא
קוד שאפשר לקחת לניסוי
הקוד מיישם את אותו רעיון מתמטי. ב־JavaScript אפשר להריץ אותו כאן; גרסת Python זמינה להשוואה ולהעתקה.
הקוד מרכיב L ישירות מן הקשתות, מסיר את הצומת המוארק, פותר את המערכת ומחשב הפרשים, זרימות ואנרגיה.
ברשת חמש הקשתות יתקבלו הפוטנציאלים (1,0.6,0.8,0), זרם מקור 1.6 ואנרגיה 1.6.
הגדילו את מוליכות הקשת 2–4. כיצד משתנים v₂, הזרם הכולל והמוליכות האפקטיבית?
מהרעיון אל הקוד
מימוש חישובי
function solve(A,b) {
const M=A.map((row,i)=>[...row,b[i]]), n=A.length;
for(let c=0;c<n;c++) { let p=c; for(let r=c+1;r<n;r++) if(Math.abs(M[r][c])>Math.abs(M[p][c])) p=r;
[M[c],M[p]]=[M[p],M[c]]; const d=M[c][c]; for(let j=c;j<=n;j++) M[c][j]/=d;
for(let r=0;r<n;r++) if(r!==c) { const f=M[r][c]; for(let j=c;j<=n;j++) M[r][j]-=f*M[c][j]; } }
return M.map(row=>row[n]);
}
function groundedNetwork(n,edges,weights,ground,injections) {
const L=Array.from({length:n},()=>Array(n).fill(0));
edges.forEach(([a,b],k)=>{const c=weights[k];L[a][a]+=c;L[b][b]+=c;L[a][b]-=c;L[b][a]-=c;});
const active=Array.from({length:n},(_,i)=>i).filter(i=>i!==ground);
const reduced=active.map(i=>active.map(j=>L[i][j]));
const values=solve(reduced,active.map(i=>injections[i]));
const v=Array(n).fill(0);active.forEach((node,i)=>v[node]=values[i]);
const energy=edges.reduce((sum,[a,b],k)=>sum+weights[k]*(v[a]-v[b])**2,0);
return {L,v,energy,balances:L.map(row=>row.reduce((sum,value,j)=>sum+value*v[j],0))};
}
const edges=[[0,1],[0,2],[1,2],[0,3],[1,3]];
console.log(groundedNetwork(4,edges,[1,1,1,1,1],3,[1.6,0,0,0]));def solve(A,b):
M=[row[:] + [b[i]] for i,row in enumerate(A)]
n=len(A)
for c in range(n):
p=max(range(c,n),key=lambda r:abs(M[r][c])); M[c],M[p]=M[p],M[c]
d=M[c][c]; M[c]=[value/d for value in M[c]]
for r in range(n):
if r!=c:
f=M[r][c]; M[r]=[M[r][j]-f*M[c][j] for j in range(n+1)]
return [row[n] for row in M]
def grounded_network(n,edges,weights,ground,injections):
L=[[0]*n for _ in range(n)]
for k,(a,b) in enumerate(edges):
c=weights[k]; L[a][a]+=c; L[b][b]+=c; L[a][b]-=c; L[b][a]-=c
active=[i for i in range(n) if i!=ground]
reduced=[[L[i][j] for j in active] for i in active]
values=solve(reduced,[injections[i] for i in active])
v=[0]*n
for i,node in enumerate(active): v[node]=values[i]
energy=sum(weights[k]*(v[a]-v[b])**2 for k,(a,b) in enumerate(edges))
balances=[sum(value*v[j] for j,value in enumerate(row)) for row in L]
return {"L":L,"v":v,"energy":energy,"balances":balances}
edges=[(0,1),(0,2),(1,2),(0,3),(1,3)]
print(grounded_network(4,edges,[1,1,1,1,1],3,[1.6,0,0,0]))לפני שממשיכים
מה לוקחים מהשיעור
- A מודדת הפרשים, C הופכת אותם לזרימות, ו־Aᵀ מחזירה מאזן לצמתים.
- L=AᵀCA סימטרית וחיובית למחצה, וסכומי שורותיה אפס.
- מספר רכיבי הקשירות הוא ממד N(L); הארקה מסירה את חופש הקבוע.
- האנרגיה vᵀLv מחברת בין אלגברה, פיזיקה ומזעור.
משימת מעבדה לשיעור הזה
תחנה 4 — להאריק ולפתור רשת
בחרו טופולוגיה, שנו מוליכות, ועקבו מהפרשי הפוטנציאל אל הזרימות, המאזנים והאנרגיה.
מקורות להעמקה בלבד — השיעור עומד בפני עצמו
מדריך המרצים: עמ׳ 210–215
ספר הלימוד: עמ׳ 423–431