אנליזה נומרית/אינטרפולציה: מינימום ריבועים

תבנית:אנליזה נומרית שיטה זו נקראת גם "שיטת הריבועים הפחותים" או "מינימום ריבועים" (Least Squares, Least Mean Squares, Least Squares Fitting), והיא שימושית ביותר עבור מציאת קירוב פונקציונלי לפיזור נקודות. בדרך כלל משתמשים בפולינומים ממעלות שונות, אך ניתן להפעילה עבור קבוצות פונקציות שונות, כגון סינוסים וקוסינוסים. כמו-כן, קיימות שיטות עבור "הפרשים-משולשים", "הפרשים-מרובעים" וכו', אך הם פחות נפוצים ולא נעסוק בהם כאן.

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

עקרונית, בשיטה זו מנסים למזער את ריבועי ההפרשים בין ערכי הפונקציה שרוצים לקרב (f) לבין ערכי הפונקציה המקרבת (F). המרחק מוגדר בתור הדרך הקצרה ביותר בין שתי נקודות, כך שאם מדובר בקירוב לינארי, יש למצוא את אורך הקטע הניצב לישר. מאחר וזה מסובך מדי, נהוג לקחת את המרחק האנכי בלבד.

שימו לב כי לעיתים אין אנו יודעים את f, אך אין אנו זקוקים לה כי כל שמעניין הוא הערך בכל נקודה.

נסמן:

1. הפונקציה (הנקודות) שרוצים לקרב: $y_i=f(x_i)$.
2. הפונקציה המקרבת: $F(x)$.
3. הפרש (מרחק) נקודתי בין הפונקציה המקרבת לפונקציה המקורבת: $d_i=y_i-F(x_i)$.
4. סכום ההפרשים (המרחקים): $S=\sum _{i=0}^n{d}_i^2$.

נקח את הפונקציה המקרבת F להיות סכום סופי של משפחת פונקציות φ כך שמתקבל מעין סוג של פריסה לינארית, כאשר הפונקציות φ הן בסיס:

$F(x)=\sum _{j=0}^N{a}_j{\varphi }_j(x)$

יש לציין כי בדרך כלל נבחר במשפחת פולינומים.

כאמור, אנו מחפשים את הפונקציה אשר תתן את הסכום S המינימלי. לשם כך נדרוש את התאפסות הנגזרות החלקיות (או לחילופין התאפסות הגרדיאנט):

$\frac{\partial S}{\partial a_k}=0,\mathrm{\forall }k=0..N$

לסכום S לא קיים מקסימום ולכן הנקודה שנמצא הינה בהכרח המינימום. נמצא ביטוי כללי עבור נגזרת חלקית בעזרת כלל השרשרת:

$S=\sum _{i=0}^n{(y_i-\sum _{j=0}^N{a}_j{\varphi }_j)}^2\Rightarrow \frac{\partial S}{\partial a_k}=\sum _{i=0}^{n}2(y_i-\sum _{j=0}^N{a}_j{\varphi }_j)\cdot \stackrel{-{\varphi }_k}{\overbrace{\frac{\partial }{\partial a_k}(-\sum _{j=0}^N{a}_j{\varphi }_j)}}=0$

מכיוון שמשווים ל-0 ניתן לצמצם את הקבוע 2 ואת סימן ה"-" (מינוס) של φ_k, כך שנשאר עם:

$\sum _{i=0}^n(y_i{\varphi }_k-\sum _{j=0}^N{a}_j{\varphi }_j{\varphi }_k)=0\Rightarrow \sum _{i=0}^n\sum _{j=0}^N{a}_j{\varphi }_j{\varphi }_k=\sum _{i=0}^n{y}_i{\varphi }_k$

כאן המקום להזכיר כי $\varphi =\varphi (x_i)$ ולכן:

$\sum _{i=0}^n\sum _{j=0}^N{a}_j{\varphi }_j(x_i){\varphi }_k(x_i)=\sum _{j=0}^N{a}_j\sum _{i=0}^n{\varphi }_j(x_i){\varphi }_k(x_i)=a_0\sum _{i=0}^n{\varphi }_0(x_i){\varphi }_k(x_i)+a_1\sum _{i=0}^n{\varphi }_1(x_i){\varphi }_k(x_i)+...=\sum _{i=0}^n{y}_i{\varphi }_k,\mathrm{\forall }k=0..N$

מהמשוואה האחרונה ניתן לבנות את המערכת המטריציונית הבאה:

$\stackrel{\psi }{\overbrace{\left[\begin{array}{cccc}\sum _{i=0}^n{\varphi }_0(x_i){\varphi }_0(x_i)& \sum _{i=0}^n{\varphi }_1(x_i){\varphi }_0(x_i)& \cdots & \sum _{i=0}^n{\varphi }_N(x_i){\varphi }_0(x_i)\\ \sum _{i=0}^n{\varphi }_0(x_i){\varphi }_1(x_i)& \sum _{i=0}^n{\varphi }_1(x_i){\varphi }_1(x_i)& \cdots & \sum _{i=0}^n{\varphi }_N(x_i){\varphi }_1(x_i)\\ ⋮& \ddots & & ⋮\\ ⋮& & \ddots & ⋮\\ \sum _{i=0}^n{\varphi }_0(x_i){\varphi }_N(x_i)& \sum _{i=0}^n{\varphi }_1(x_i){\varphi }_N(x_i)& \cdots & \sum _{i=0}^n{\varphi }_N(x_i){\varphi }_N(x_i)\end{array}\right]}}\stackrel{\overrightarrow{a}}{\overbrace{\left\{\begin{array}{c}{a}_0\\ a_1\\ ⋮\\ a_N\end{array}\right\}}}=\stackrel{\overrightarrow{\mathrm{\Gamma }}}{\overbrace{\left\{\begin{array}{c}\sum _{i=0}^n{y}_i{\varphi }_0\\ \sum _{i=0}^n{y}_i{\varphi }_1\\ ⋮\\ ⋮\\ \sum _{i=0}^n{y}_i{\varphi }_N\end{array}\right\}}}$

ונהוג לסמן:

${\psi }_{lm}=\sum _{i=0}^n{\varphi }_l(x_i){\varphi }_m(x_i),{\mathrm{\Gamma }}_l=\sum _{i=0}^n{y}_i{\varphi }_l(x_i)$

מקרה פרטי: פולינום

במקרה זה:

${\varphi }_k(x)=x^k\Rightarrow \{\begin{array}{c}{\varphi }_0(x)=1\\ {\varphi }_1(x)=x\\ {\varphi }_2(x)=x^2\\ ⋮\\ {\varphi }_N(x)=x^N\end{array}\Rightarrow F(x)=\sum _{j=0}^N{a}_j{x}^j;{\psi }_{lm}=\sum _{i=0}^n{x}_i^{l+m},{\mathrm{\Gamma }}_l=\sum _{i=0}^n{x}_i^l{y}_i$

מקרה פרטי: רגרסיה לינארית

(להשלים)

קישורים חיצוניים

• מינימום ריבועים באתר MathWorld: לינארי, פולינומיאלי.