7.5

מתמטיקה שימושית ו־AᵀA

לפלסיאן, הארקה ורשתות

Networks and the Graph Laplacian

מטריצת incidence מחשבת הפרשי פוטנציאל; L=AᵀCA מחבר אותם למאזן זרימות. L סינגולרית עד שמקבעים פוטנציאל אחד בכל רכיב קשיר.

יחידת לימוד עצמאיתשיעור 5 מתוך 5כ־75 דקות כולל תרגול3 מטרות למידה
  1. 1
    נקודת פתיחהמה כבר ידוע ומה השאלה?
  2. 2
    ניבוימה יקרה במקרה הפשוט?
  3. 3
    המחשהמה באמת משתנה בתמונה?
  4. 4
    ניסוח והצדקהשם, נוסחה ולמה היא נכונה
  5. 5
    בדיקהדוגמה, תרגול ומשוב
  6. 6
    העברהמקרה חדש והמשך המסלול

שאלה לפני נוסחה

מה אנחנו מנסים לראות?

לבנות לפלסיאן של גרף מ־incidence ומוליכויות, לפרש Lv=b כמאזן זרימות, ולהסביר סינגולריות, הארקה, אנרגיה וחיבוריות.

פוטנציאל הוא כמו גובה, מוליכות היא רוחב צינור, וזרימה נעה מן הגבוה לנמוך. A מודדת הפרשי גובה על הקשתות, C ממירה אותם לזרימות, ו־Aᵀ מחזירה לכל צומת את המאזן של כל הקשתות שנפגשות בו.

לפני ההמחשה: קראו רק את הכותרת “פוטנציאל, הפרש, זרימה ומאזן”. מה לדעתכם ישתנה, מה יישאר קבוע, ואיזה סימן בתמונה יוכל להפריך את הניבוי?

לראות לפני שמחשבים · המקרה הפשוט ביותר

פוטנציאל, הפרש, זרימה ומאזן

לפלסיאן של גרף מעביר פוטנציאלים להפרשי קשתות, זרימות ומאזני צמתיםv11v20.6v30.8v40groundd=Av · q=−Cd · Lv=AᵀCAv=bv=(1,0.6,0.8,0) · I=1.6L𝟙=0; הארקה מסירה את חופש הוספת הקבוע
עקבו מהצורה הראשונית אל התוצאה

האיור מציג ארבעה צמתים וחמש קשתות, עם פוטנציאל בכל צומת וזרימה מחושבת בכל קשת.

מה כדאי לגלות: בצמתים ללא הזרקה סכום הזרימות היוצאות הוא אפס. הצומת המוארק קולט בדיוק את הזרם שהוזרק בצומת המקור.

אחרי שראינו

בסוף השיעור תוכלו

  • לבנות 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

מרכיבים את הפעולות

מהתמונה אל הנוסחה — הגזירה, בלי לדלג על הצעדים

  1. בוחרים כיוון חשבונאי

    כיוון הקשת קובע רק סימן בשורת A. אם השורה היא −1 בזנב ו־+1 בראש, אז Av הוא פוטנציאל הראש פחות הזנב.

    d=Av; dₖ=vhead−vtail
  2. ממירים הפרש לזרימה פיזיקלית

    זרימה חיובית בכיוון החץ עוברת מן פוטנציאל גבוה לנמוך, ולכן היא מינוס המוליכות כפול ההפרש האלגברי.

    q=−Cd=−CAv
  3. מחזירים מאזן לצמתים

    Aᵀq הוא כניסה נטו לפי מוסכמת החץ. לכן −Aᵀq=AᵀCAv הוא יציאה נטו, והיא שווה להזרקה b.

    Lv=b; L=AᵀCA
  4. קוראים את מבנה L

    כל קשת מוסיפה c לשני איברי האלכסון ו־−c לשני המקומות הסימטריים בין קצותיה. לכן סכום כל שורה הוא אפס.

    Lii=Σj cij; Lij=−cij; L𝟙=0
  5. מפרשים אנרגיה

    האנרגיה היא סכום מוליכות כפול ריבוע הפרש בכל קשת. היא אינה שלילית ואפסה בדיוק כאשר הפוטנציאל קבוע בכל רכיב קשיר.

    vᵀLv=(Av)ᵀC(Av)=Σcₖdₖ²≥0
  6. מבינים סינגולריות וחיבוריות

    הוספת קבוע לכל הפוטנציאלים אינה משנה שום הפרש. בגרף עם c רכיבים אפשר לבחור קבוע נפרד בכל רכיב, ולכן dim N(L)=c.

    rank(L)=n−c
  7. מאריקים ומקבלים יחידות

    מסירים שורה ועמודה של צומת מוארק בכל רכיב. בגרף קשיר המטריצה המצומצמת חיובית בהחלט ואפשר לפתור פוטנציאלים יחידים.

    Lreduced vred=bred

עכשיו רואים את השיטה בפעולה

דוגמאות פתורות, צעד אחר צעד

דוגמה 1

רשת חמישה נגדים

בגרף עם הקשתות 1–2,1–3,2–3,1–4,2–4, כל המוליכויות 1. קבעו v₁=1,v₄=0 ומצאו v₂,v₃.

  1. בצומת 2 אין הזרקה, ולכן 3v₂−v₁−v₃−v₄=0.

  2. בצומת 3 אין הזרקה, ולכן 2v₃−v₁−v₂=0.

  3. מציבים v₁=1,v₄=0 ופותרים: 3v₂−v₃=1,‏ −v₂+2v₃=1.

  4. מתקבל v₂=0.6,v₃=0.8.

  5. הזרם היוצא מצומת 1 הוא (1−0.6)+(1−0.8)+(1−0)=1.6.

  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.

דוגמה 2

משולש עם מוליכויות שונות

במשולש עם c₁=1,c₂=4,c₃=9 בנו את L.

  1. כל קשת מוסיפה בלוק c[[1,−1],[−1,1]] במיקומי שני קצותיה.

  2. חיבור שלושת הבלוקים נותן L=[[10,−1,−9],[−1,5,−4],[−9,−4,13]] לפי סדר הקשתות 1–2,2–3,3–1.

  3. סכומי השורות אפס, ולכן L𝟙=0 והמטריצה סינגולרית.

  4. לאחר הארקת צומת 3 מתקבלת [[10,−1],[−1,5]], שהדטרמיננטה שלה 49>0 ולכן היא חיובית בהחלט.

התוצאה ומה היא אומרת

L חיובית למחצה; המטריצה המוארקת חיובית בהחלט.

איפה זה פוגש את העולם

יישום

רשתות חשמל, דירוג קבוצות, consensus, דיפוזיה וניתוח קהילות משתמשים בלפלסיאן. אותה משוואה אומרת פעם שזרם נשמר, פעם שדירוגים מתאימים להפרשי תוצאות ופעם שכל צומת מתקרב לממוצע שכניו.

מלכודת נפוצה

מה כדאי לבדוק

לכתוב q=CAv ולכנות אותו זרם מן הזנב לראש. עם ההגדרה d=vhead−vtail, החוק הפיזיקלי הוא q=−Cd. אפשר לבחור מוסכמה אחרת, אך חייבים לשמור אותה באופן עקבי עד משוואת המאזן.

בודקים שהרעיון יושב

תרגול ומשוב

בדיקת הבנה

בחרו תשובה ורק אז בדקו את עצמכם

מה משתנה ב־L אם הופכים את כיוון אחת הקשתות ב־A?

בחרו אחת מהאפשרויות כדי להמשיך.

עכשיו אתם

אתגר קצר

בשרשרת של ארבעה צמתים ושלוש מוליכויות שוות 1, האריקו את צומת 4 והזריקו זרם 1 לצומת 1. מצאו את הפוטנציאלים ואת ההתנגדות האפקטיבית.

רמז ראשון

אותו זרם 1 חייב לעבור בכל שלוש הקשתות בטור. כל קשת יוצרת ירידת פוטנציאל 1.

הצגת דרך הפתרון
  1. מן ההארקה v₄=0 והקשת האחרונה דורשת v₃−v₄=1, לכן v₃=1.
  2. באופן דומה v₂−v₃=1 ולכן v₂=2, ו־v₁−v₂=1 ולכן v₁=3.
  3. הפוטנציאלים הם (3,2,1,0).
  4. הפרש הקצוות הוא 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]));

לפני שממשיכים

מה לוקחים מהשיעור

  • A מודדת הפרשים, C הופכת אותם לזרימות, ו־Aᵀ מחזירה מאזן לצמתים.
  • L=AᵀCA סימטרית וחיובית למחצה, וסכומי שורותיה אפס.
  • מספר רכיבי הקשירות הוא ממד N(L); הארקה מסירה את חופש הקבוע.
  • האנרגיה vᵀLv מחברת בין אלגברה, פיזיקה ומזעור.

משימת מעבדה לשיעור הזה

תחנה 4 — להאריק ולפתור רשת

בחרו טופולוגיה, שנו מוליכות, ועקבו מהפרשי הפוטנציאל אל הזרימות, המאזנים והאנרגיה.

לפתיחת התחנה
מקורות להעמקה בלבד — השיעור עומד בפני עצמו

מדריך המרצים: עמ׳ 210–215

ספר הלימוד: עמ׳ 423–431