פרק 7: מתמטיקה שימושית ו־AᵀA

מפת הפרק

5 תחנות בדרך

5 יחידות לימוד עצמאיות · כ־6 שעות ו־10 דקות לשיעורים ולתרגול

7.1
יחידת לימוד70 דקות
ריבועים פחותים כהקרנה
שאלה 1: מה ננסה להבין?
כאשר Ax=b אינה פתירה, מחליפים את b בהיטל p=Ax̂ הקרוב ביותר בתוך C(A). השארית e=b−p מאונכת לכל עמודה, ומכאן נובעות המשוואות הנורמליות.
לשיעור
7.2
יחידת לימוד85 דקות
SVD — מארבע תנועות אל אנרגיה
שאלה 2: מה ננסה להבין?
מתחילים ממטריצות מלבניות ומעבר בין ממדים, מפרקים כל פעולה לסיבוב–מתיחה–שינוי ממד–סיבוב, ורק אז מחברים את התמונה ל־AᵀA, לאנרגיה, לדרגה ולרגישות.
לשיעור
7.3
יחידת לימוד70 דקות
תנאי שפה והבדלים סופיים
שאלה 3: מה ננסה להבין?
בבעיית שפה שני ערכים בקצות התחום מחליפים את נתוני ההתחלה. מטריצת הפרשים ראשונים A יוצרת את K=AᵀA, קירוב סימטרי ל־−u″.
לשיעור
7.4
יחידת לימוד70 דקות
משוואת לפלס על רשת
שאלה 4: מה ננסה להבין?
המשוואה uₓₓ+uᵧᵧ=0 הופכת לכלל ממוצע: כל צומת פנימי שווה לממוצע ארבעת שכניו. ערכי השפה הם שמניעים פתרון לא־קבוע.
לשיעור
7.5
יחידת לימוד75 דקות
לפלסיאן, הארקה ורשתות
שאלה 5: מה ננסה להבין?
מטריצת incidence מחשבת הפרשי פוטנציאל; L=AᵀCA מחבר אותם למאזן זרימות. L סינגולרית עד שמקבעים פוטנציאל אחד בכל רכיב קשיר.
לשיעור

ביד, שלב אחר שלב

דוגמת עוגן: מנתונים לא עקביים אל הקרנה

התאימו את הקו C+Dx למדידות (0,4),(1,1),(2,0),(3,1), ופרשו את התוצאה כהקרנה של b על C(A).

1
קו C+Dx היה דורש ארבע משוואות בשני נעלמים. בונים A=[[1,0],[1,1],[1,2],[1,3]] ו־b=(4,1,0,1).
2
המערכת Ax=b אינה עקבית: שום קו ישר אינו עובר דרך ארבע הנקודות. לכן מחפשים p=Ax̂ הקרוב ביותר ל־b.
3
השארית e=b−Ax̂ צריכה להיות מאונכת לשתי עמודות A, ולכן Aᵀe=0.
4
מציבים e=b−Ax̂ ומקבלים את המשוואות הנורמליות AᵀA x̂=Aᵀb.
5
כאן AᵀA=[[4,6],[6,14]] ו־Aᵀb=(6,4). פתרון המערכת נותן x̂=(C,D)=(3,−1).
6
הקו הוא 3−x, ולכן p=(3,2,1,0) והשארית e=(1,−1,−1,1).
7
בודקים: סכום השאריות הוא 0 וגם 0·1+1·(−1)+2·(−1)+3·1=0. אלה בדיוק שני רכיבי Aᵀe.

תוצאהx̂=(3,−1), p=(3,2,1,0), e=(1,−1,−1,1), Aᵀe=0, ‖e‖²=4

ניבוי, ניסוי והסבר

מעבדת חקר: מהתאמה וה־SVD אל תנאי שפה ולפלסיאן של רשת

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

נבאו, בדקו והסבירו: התאמה לנתונים, אנרגיה ו־SVD, תנאי שפה ומשוואת לפלס, ומאזן זרימות בגרף.

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

תחנה 1 מתוך 4

מתי קו הוא באמת הקרוב ביותר?

המטרה: לראות את Aᵀe=0 ולא רק את צורת הקו: השאריות צריכות להיות מאונכות לשני כיווני המודל.
המשימה: נבאו, הזיזו שיפוע וחיתוך, והשוו SSE ואת שני רכיבי Aᵀe לקו האופטימלי.

ערכת נתונים

חיתוך C2

שיפוע D−0.5

Aᵀe=0 ⇔ AᵀA x̂=Aᵀb

SSE נוכחי: 5.5
SSE מינימלי: 4
Aᵀe נוכחי: (1, −1)
(C,D) מיטביים: (3, −1)

הקו y=2+−0.5x. השאריות הן (2, −0.5, −1, 0.5).

עכשיו בקוד

אותו רעיון, כאלגוריתם

הקוד קצר בכוונה: כל שורה מקבילה לצעד בחישוב הידני.

מהרעיון אל הקוד

מימוש חישובי

function fitLine(points) {
  const meanX = points.reduce((sum, [x]) => sum + x, 0) / points.length;
  const meanY = points.reduce((sum, [, y]) => sum + y, 0) / points.length;
  const denominator = points.reduce((sum, [x]) => sum + (x-meanX)**2, 0);
  if (denominator === 0) throw new Error("x values must not all be equal");
  const slope = points.reduce(
    (sum, [x, y]) => sum + (x-meanX)*(y-meanY), 0,
  ) / denominator;
  const intercept = meanY-slope*meanX;
  const predicted = points.map(([x]) => intercept+slope*x);
  const residuals = points.map(([, y], i) => y-predicted[i]);
  const normalResidual = [
    residuals.reduce((sum, value) => sum+value, 0),
    residuals.reduce((sum, value, i) => sum+points[i][0]*value, 0),
  ];
  return { intercept, slope, predicted, residuals, normalResidual,
    sse: residuals.reduce((sum, value) => sum+value**2, 0) };
}

const answer = fitLine([[0,4],[1,1],[2,0],[3,1]]);
console.log(answer);

def fit_line(points):
    mean_x = sum(x for x, _ in points) / len(points)
    mean_y = sum(y for _, y in points) / len(points)
    denominator = sum((x-mean_x)**2 for x, _ in points)
    if denominator == 0:
        raise ValueError("x values must not all be equal")
    slope = sum((x-mean_x)*(y-mean_y) for x, y in points) / denominator
    intercept = mean_y-slope*mean_x
    predicted = [intercept+slope*x for x, _ in points]
    residuals = [y-predicted[i] for i, (_, y) in enumerate(points)]
    normal_residual = [
        sum(residuals),
        sum(points[i][0]*value for i, value in enumerate(residuals)),
    ]
    return {"intercept": intercept, "slope": slope,
            "predicted": predicted, "residuals": residuals,
            "normal_residual": normal_residual,
            "sse": sum(value**2 for value in residuals)}

print(fit_line([(0,4),(1,1),(2,0),(3,1)]))

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

5 תחנות בדרך

ריבועים פחותים כהקרנה

SVD — מארבע תנועות אל אנרגיה

תנאי שפה והבדלים סופיים

משוואת לפלס על רשת

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