שינויים
יצירת דף עם התוכן "[[תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר|חזרה לקישורים לתקצירים]] ==הקדמה== תהי מערכת משוו..."
[[תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר|חזרה לקישורים לתקצירים]]
==הקדמה==
תהי מערכת משוואות <math>Ax=b</math> כאשר <math>A\in M_{n\times k}\left ( \mathbb{R} \right )</math>, <math>x\in\mathbb{R}^k</math> ו־<math>b\in\mathbb{R}^n</math>. אזי:
# למערכת אין פתרון אם <math>b\notin C\left ( A \right )</math>.
# למערכת יש פתרון יחיד אם <math>rank\left ( A \right )=k</math>, כלומר <math>\det\left ( A \right )\neq 0</math>.
# למערכת יש אינסוף פתרונות אם <math>b\in C\left ( A \right )</math>.
במקרים 1 ו־3 מתקיים <math>rank\left ( A \right )<k</math>, <math>\det\left ( A \right )=0</math>.
''הערה: <math>rank\left ( A \right )</math> - מספר העמודות הבת"ל ב־<math>A</math>.''
==מקרה 2: פתרון יחיד==
שלוש אפשרויות לחישוב הפתרון על ידי MATLAB:
# x=inv(A)*b
# x=A\b
# x=pinv(A)*b
אפשרויות 2 ו־3 מתאימה גם אם <math>A</math> אינה הפיכה / ריבועית.
==מקרה 1: אין פתרון==
===התאמת קו ישר לאוסף נקודות===
עבור סדרת N נקודות, <math>\left \{ \left ( x_i,y_i \right ) \right \}_{i=1}^N</math>, ננסה להתאים ישר <math>y=c_1 x+c_2</math> הקרוב להן ביותר (קו מגמה).
נגדיר מטריצה <math>A</math>:
<math>A=\begin{pmatrix}
x_1 & 1 \\
x_2 & 1 \\
\vdots & \vdots \\
x_N & 1
\end{pmatrix}</math>
ו־וקטור <math>y</math>:
<math>y=\begin{pmatrix}
y_1 \\
y_2 \\
\vdots \\
y_N
\end{pmatrix}</math>
ונפתור את מערכת המשוואות <math>Ac=y</math>. הפתרון <math>c</math> שנקבל הינו הווקטור <math>\begin{pmatrix}
c_1 \\
c_2
\end{pmatrix}</math>
'''פתרון המערכת: ניעזר ברגרסיה לינארית'''
נגדיר פונקציה <math>R=\sum_{i=1}^Nd_i^2</math> כאשר <math>d_i</math> הינו המרחק של הנקודה ה־i־ית מהישר (אנך לציר x), שהוא בעצם הפרשי ה־y. כלומר, <math>R\left ( c_1,c_2 \right )=\sum_{i=1}^N \left ( y_i-c_ix_i-c_2 \right )^2</math>. המינימום של הפונקציה הזו ייתן לנו את הפתרון המקורב ביותר לנקודות, כזה שסכום ריבועי המרחקים שלו מהנקודות הנתונות מינימלי - הכי קרוב.
נגזור ונקבל נגזרות חלקיות:
<math>\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</math>
<math>\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</math>
נמשיך לפתור:
<math>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</math>
<math>c_1\sum_{i=1}^{N}x_i+Nc_2=\sum_{i=1}^{N}y_i</math>
בעצם, קיבלנו מערכת משוואות השקולה למערכת <math>A^t A c=A^t y</math> (למי שאינו מאמין, ניתן לבדוק).
נחשב את <math>\det(A^t A)</math> כדי לדעת מתי אין פתרון יחיד למערכת:
<math>\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 ]</math>
למה: <math>\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</math>
הוכחה: נסמן את הממוצע <math>\bar{x}=\frac{\sum_{i=1}^{N}x_i}{N}</math>. אזי:
<math>\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</math>
מסקנה: <math>\det (A^t A)=0</math> אם ורק אם <math>x_1=x_2=...=x_N=\bar{x}</math>. לכן, קיים '''פתרון ריבועים מינימליים (Least squares solution)'''.
==הקדמה==
תהי מערכת משוואות <math>Ax=b</math> כאשר <math>A\in M_{n\times k}\left ( \mathbb{R} \right )</math>, <math>x\in\mathbb{R}^k</math> ו־<math>b\in\mathbb{R}^n</math>. אזי:
# למערכת אין פתרון אם <math>b\notin C\left ( A \right )</math>.
# למערכת יש פתרון יחיד אם <math>rank\left ( A \right )=k</math>, כלומר <math>\det\left ( A \right )\neq 0</math>.
# למערכת יש אינסוף פתרונות אם <math>b\in C\left ( A \right )</math>.
במקרים 1 ו־3 מתקיים <math>rank\left ( A \right )<k</math>, <math>\det\left ( A \right )=0</math>.
''הערה: <math>rank\left ( A \right )</math> - מספר העמודות הבת"ל ב־<math>A</math>.''
==מקרה 2: פתרון יחיד==
שלוש אפשרויות לחישוב הפתרון על ידי MATLAB:
# x=inv(A)*b
# x=A\b
# x=pinv(A)*b
אפשרויות 2 ו־3 מתאימה גם אם <math>A</math> אינה הפיכה / ריבועית.
==מקרה 1: אין פתרון==
===התאמת קו ישר לאוסף נקודות===
עבור סדרת N נקודות, <math>\left \{ \left ( x_i,y_i \right ) \right \}_{i=1}^N</math>, ננסה להתאים ישר <math>y=c_1 x+c_2</math> הקרוב להן ביותר (קו מגמה).
נגדיר מטריצה <math>A</math>:
<math>A=\begin{pmatrix}
x_1 & 1 \\
x_2 & 1 \\
\vdots & \vdots \\
x_N & 1
\end{pmatrix}</math>
ו־וקטור <math>y</math>:
<math>y=\begin{pmatrix}
y_1 \\
y_2 \\
\vdots \\
y_N
\end{pmatrix}</math>
ונפתור את מערכת המשוואות <math>Ac=y</math>. הפתרון <math>c</math> שנקבל הינו הווקטור <math>\begin{pmatrix}
c_1 \\
c_2
\end{pmatrix}</math>
'''פתרון המערכת: ניעזר ברגרסיה לינארית'''
נגדיר פונקציה <math>R=\sum_{i=1}^Nd_i^2</math> כאשר <math>d_i</math> הינו המרחק של הנקודה ה־i־ית מהישר (אנך לציר x), שהוא בעצם הפרשי ה־y. כלומר, <math>R\left ( c_1,c_2 \right )=\sum_{i=1}^N \left ( y_i-c_ix_i-c_2 \right )^2</math>. המינימום של הפונקציה הזו ייתן לנו את הפתרון המקורב ביותר לנקודות, כזה שסכום ריבועי המרחקים שלו מהנקודות הנתונות מינימלי - הכי קרוב.
נגזור ונקבל נגזרות חלקיות:
<math>\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</math>
<math>\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</math>
נמשיך לפתור:
<math>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</math>
<math>c_1\sum_{i=1}^{N}x_i+Nc_2=\sum_{i=1}^{N}y_i</math>
בעצם, קיבלנו מערכת משוואות השקולה למערכת <math>A^t A c=A^t y</math> (למי שאינו מאמין, ניתן לבדוק).
נחשב את <math>\det(A^t A)</math> כדי לדעת מתי אין פתרון יחיד למערכת:
<math>\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 ]</math>
למה: <math>\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</math>
הוכחה: נסמן את הממוצע <math>\bar{x}=\frac{\sum_{i=1}^{N}x_i}{N}</math>. אזי:
<math>\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</math>
מסקנה: <math>\det (A^t A)=0</math> אם ורק אם <math>x_1=x_2=...=x_N=\bar{x}</math>. לכן, קיים '''פתרון ריבועים מינימליים (Least squares solution)'''.
