השינוי האחרון נעשה בֹ־29 ביוני 2013 ב־11:04

תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר, משוואות לינאריות וריבועים מינימליים

גרסה מ־11:04, 29 ביוני 2013 מאת גיא (שיחה | תרומות) (יצירת דף עם התוכן "חזרה לקישורים לתקצירים ==הקדמה== תהי מערכת משוו...")

(הבדל) → הגרסה הקודמת | הגרסה האחרונה (הבדל) | הגרסה הבאה ← (הבדל)

חזרה לקישורים לתקצירים

הקדמה

תהי מערכת משוואות Ax=b כאשר A\in M_{n\times k}\left ( \mathbb{R} \right ), x\in\mathbb{R}^k ו־b\in\mathbb{R}^n. אזי:

  1. למערכת אין פתרון אם b\notin C\left ( A \right ).
  2. למערכת יש פתרון יחיד אם rank\left ( A \right )=k, כלומר \det\left ( A \right )\neq 0.
  3. למערכת יש אינסוף פתרונות אם b\in C\left ( A \right ).

במקרים 1 ו־3 מתקיים rank\left ( A \right )<k, \det\left ( A \right )=0.

הערה: rank\left ( A \right ) - מספר העמודות הבת"ל ב־A.

מקרה 2: פתרון יחיד

שלוש אפשרויות לחישוב הפתרון על ידי MATLAB:

  1. x=inv(A)*b
  2. x=A\b
  3. x=pinv(A)*b

אפשרויות 2 ו־3 מתאימה גם אם A אינה הפיכה / ריבועית.

מקרה 1: אין פתרון

התאמת קו ישר לאוסף נקודות

עבור סדרת N נקודות, \left \{ \left ( x_i,y_i \right ) \right \}_{i=1}^N, ננסה להתאים ישר y=c_1 x+c_2 הקרוב להן ביותר (קו מגמה).

נגדיר מטריצה A: A=\begin{pmatrix}
 x_1 & 1 \\ 
 x_2 & 1 \\ 
 \vdots & \vdots \\ 
 x_N & 1
\end{pmatrix}

ו־וקטור y: y=\begin{pmatrix}
y_1 \\ 
y_2 \\ 
\vdots \\ 
y_N
\end{pmatrix}

ונפתור את מערכת המשוואות Ac=y. הפתרון c שנקבל הינו הווקטור \begin{pmatrix}
c_1 \\ 
c_2
\end{pmatrix}


פתרון המערכת: ניעזר ברגרסיה לינארית

נגדיר פונקציה R=\sum_{i=1}^Nd_i^2 כאשר d_i הינו המרחק של הנקודה ה־i־ית מהישר (אנך לציר x), שהוא בעצם הפרשי ה־y. כלומר, R\left ( c_1,c_2 \right )=\sum_{i=1}^N \left ( y_i-c_ix_i-c_2 \right )^2. המינימום של הפונקציה הזו ייתן לנו את הפתרון המקורב ביותר לנקודות, כזה שסכום ריבועי המרחקים שלו מהנקודות הנתונות מינימלי - הכי קרוב.

נגזור ונקבל נגזרות חלקיות:

\frac{\partial R}{\partial c_1}=\sum_{i=1}^N 2\cdot \left ( y_i-c_ix_i-c_2 \right ) \cdot \left (-x_i  \right )=-\sum_{i=1}^{N}2x_i \left ( y_i-c_ix_i-c_2 \right )=0

\frac{\partial R}{\partial c_2}=\sum_{i=1}^N 2\cdot \left ( y_i-c_ix_i-c_2 \right ) \cdot \left (-1  \right )=-\sum_{i=1}^{N}2 \left ( y_i-c_ix_i-c_2 \right )=0

נמשיך לפתור:

c_1\sum_{i=1}^N x_i^2+c_2 \sum_{i=1}^N x_i=\sum_{i=1}^{N} x_i y_i

c_1\sum_{i=1}^{N}x_i+Nc_2=\sum_{i=1}^{N}y_i

בעצם, קיבלנו מערכת משוואות השקולה למערכת A^t A c=A^t y (למי שאינו מאמין, ניתן לבדוק).

נחשב את \det(A^t A) כדי לדעת מתי אין פתרון יחיד למערכת:

\det\left ( A^t A \right )=N\sum_{i=1}^{N}x_i^2-\left ( \sum_{i=1}^{N}x_i \right )^2=N^2 \left [ \frac{\sum_{i=1}^{N}x_i^2}{N}-\left ( \frac{\sum_{i=1}^{N}x_i}{N} \right )^2 \right ]

למה: \frac{\sum_{i=1}^{N}x_i^2}{N}-\left ( \frac{\sum_{i=1}^{N}x_i}{N} \right )^2=\frac{1}{N}\sum_{i=1}^{N}\left ( x_i-\frac{\sum_{i=1}^{N}x_i}{N} \right )^2

הוכחה: נסמן את הממוצע \bar{x}=\frac{\sum_{i=1}^{N}x_i}{N}. אזי:

\frac{1}{N}\sum_{i=1}^{N}\left ( x_i-\bar{x} \right )^2=\frac{1}{N}\sum_{i=1}^{N} \left (x_i^2-2x_i\bar{x} +\bar{x}^2 \right )=\frac{1}{N}\sum_{i=1}^{N} x_i^2-2\bar{x}\underset{\bar{x}}{\underbrace{\frac{1}{N}\sum_{i=1}^{N}x_i}}+\underset{\bar{x}^2}{\underbrace{\frac{1}{N}\sum_{i=1}^{N}\bar{x}^2}}=\frac{1}{N}\sum_{i=1}^{N} x_i^2-\bar{x}^2


מסקנה: \det (A^t A)=0 אם ורק אם x_1=x_2=...=x_N=\bar{x}. לכן, קיים פתרון ריבועים מינימליים (Least squares solution).