בפרק זה אנו הולכים להכיר את בעיית הריבועים הפחותים. בעיה זו מכלילה את הרעיון של פתרון ממ"ל לקבלת פתרון מקורב.
∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 ⟶ min ||A\underline{x}-\underline{b}||_{2}^2 \longrightarrow \min ∣∣ A x − b ∣ ∣ 2 2 ⟶ min נלמד את תכונותיה של בעיה זו, את הדרכים לפתרונה ונקשור זאת לפירוק L U LU LU
הגדרת הבעיה
נניח כי בידינו סדרה בת m m m n n n
f 1 ( x ‾ ) = 0 , f 2 ( x ‾ ) = 0 , … , f m ( x ‾ ) = 0 f_{1}(\underline{x})=0,f_{2}(\underline{x})=0,\dots,f_{m}(\underline{x})=0 f 1 ( x ) = 0 , f 2 ( x ) = 0 , … , f m ( x ) = 0 כאשר x ‾ = ( x 1 x 2 … x n ) \underline{x}=\begin{pmatrix}x_{1} & x_{2} & \dots & x_{n}\end{pmatrix} x = ( x 1 x 2 … x n )
נוכל להגדיר את אותה הבעיה בתצורה שמשלבת את כל הפונקציות לפונקציה אחת כך:
p ( x ‾ ) = [ f 1 ( x ‾ ) ] 2 + [ f 2 ( x ‾ ) ] 2 + ⋯ + [ f m ( x ‾ ) ] 2 = ∣ ∣ f ‾ ( x ‾ ) ∣ ∣ 2 2 p(\underline{x})=\left[f_{1}(\underline{x})\right]^2+\left[f_{2}(\underline{x})\right]^2+\dots+\left[f_{m}(\underline{x})\right]^2=\left| \left| \underline{f}(\underline{x}) \right| \right|_{2}^2 p ( x ) = [ f 1 ( x ) ] 2 + [ f 2 ( x ) ] 2 + ⋯ + [ f m ( x ) ] 2 = f ( x ) 2 2 הגובה המינימלי של הפונקציה הזו הוא 0 0 0 x x x 0 0 0
אם יש פתרון למערכת המקורית, ערך הפונקציה במינימום יהיה זהותית אפס ולכן הבעיות הנ"ל שקולות.
אם אין פתרון למערכת המקורית, עדיין יתכן שמינימיזציה של p ( x ‾ ) p(\underline{x}) p ( x ) מינימום שגיאה ריבועית של המשוואות המקוריות.
נסמן כעת:
f ‾ ( x ‾ ) = 0 ‾ ⟹ min x ‾ ∣ ∣ f ‾ ( x ‾ ) ∣ ∣ 2 2 \underline{f}(\underline{x})=\underline{0}\implies \underset{\underline{x}}{\min}\left| \left| \underline{f}(\underline{x}) \right| \right|_{2}^2 f ( x ) = 0 ⟹ x min f ( x ) 2 2 מעבר למשוואות ליניאריות
כעת, נקטין את סט הבעיות שאנו רוצים לפתור לפונקציות ליניאריות בלבד:
{ a ‾ 1 x ‾ − b 1 = 0 a ‾ 2 x ‾ − b 2 = 0 ⋮ a ‾ m x ‾ − b m = 0 } ⟹ ( − a ‾ 1 − − a ‾ 2 − ⋮ − a ‾ m − ) x ‾ − ( b 1 b 2 ⋮ b m ) = A x ‾ − b ‾ = 0 \left\{ \begin{matrix}
\underline{a}_{1}\underline{x}-b_{1}=0 \\
\underline{a}_{2}\underline{x}-b_{2}=0 \\
\vdots \\
\underline{a}_{m}\underline{x}-b_{m}=0
\end{matrix} \right\} \implies \begin{pmatrix}
-\underline{a}_{1}- \\
-\underline{a}_{2}- \\
\vdots \\
-\underline{a}_{m}-
\end{pmatrix}\underline{x}-\begin{pmatrix}
b_{1} \\
b_{2} \\
\vdots \\
b_{m}
\end{pmatrix}=A\underline{x}-\underline{b}=0 ⎩ ⎨ ⎧ a 1 x − b 1 = 0 a 2 x − b 2 = 0 ⋮ a m x − b m = 0 ⎭ ⎬ ⎫ ⟹ − a 1 − − a 2 − ⋮ − a m − x − b 1 b 2 ⋮ b m = A x − b = 0 הגדרה 1 (פונקציית המחיר המשולבת)
הפונקציה מבעיית הריבועים הפחותים שמשלבת את כל הפונקציות שראינו קודם -p ( x ) p(x) p ( x )
בבעיה זו נקבל:
p ( x ) = ∑ k = 1 m ( a ‾ k x ‾ − b k ) 2 = ( A x ‾ − b ‾ ) t ( A x ‾ − b ‾ ) ⏟ r ‾ = ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 = ∣ ∣ r ‾ ∣ ∣ 2 2 p(x)=\sum_{k=1}^m (\underline{a}_{k}\underline{x}-b_{k})^2=(A\underline{x}-\underline{b})^t \underbrace{(A\underline{x}-\underline{b})}_{\underline{r}}=||A\underline{x}-\underline{b}||_{2}^2=||\underline{r}||_{2}^2 p ( x ) = k = 1 ∑ m ( a k x − b k ) 2 = ( A x − b ) t r ( A x − b ) = ∣∣ A x − b ∣ ∣ 2 2 = ∣∣ r ∣ ∣ 2 2 זהו הביטוי שנרצה להביא למינימום.
דרך הסתכלות שונה על אותה הבעיה
נניח כי בידינו סדרה בת n < m n<m n < m
{ v ‾ 1 , v ‾ 2 , … , v ‾ n } ∈ F m \left\{ \underline{v}_{1},\underline{v}_{2},\dots,\underline{v}_{n} \right\} \in \mathbb{F}^{m} { v 1 , v 2 , … , v n } ∈ F m ברור כי וקטורים אלו פורשים תת-מרחב במימד קטן או שווה ל-n n n
∑ k = 1 n x k v ‾ k = ( ∣ ∣ v ‾ 1 … v ‾ n ∣ ∣ ) ( x 1 ⋮ x n ) = ↓ סימון A x ‾ \sum_{k=1}^n x_{k}\underline{v}_{k}=\begin{pmatrix}
\vert & & \vert \\
\underline{v}_{1} & \dots & \underline{v}_{n} \\
\vert & & \vert
\end{pmatrix}\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}
\end{pmatrix} \underset{\begin{matrix}
\downarrow \\
\R{\text{סימון}}
\end{matrix}}{=} A\underline{x} k = 1 ∑ n x k v k = ∣ v 1 ∣ … ∣ v n ∣ x 1 ⋮ x n ↓ סימון = A x כעת, נניח כי נתון לנו וקטור שרירותי b ‾ \underline{b} b m m m V V V b ‾ \underline{b} b
min x ‾ ∣ ∣ ∑ k = 1 n x k v ‾ k − b ‾ ∣ ∣ 2 2 = min x ‾ ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 \underset{\underline{x}}{\min}\left| \left| \sum_{k=1}^n x_{k}\underline{v}_{k}-\underline{b} \right| \right|_{2}^2=\underset{\underline{x}}{\min}||A\underline{x}-\underline{b}||_{2}^2 x min k = 1 ∑ n x k v k − b 2 2 = x min ∣∣ A x − b ∣ ∣ 2 2 כל בעית ריבועים פחותים ניתנת להתייחסות כבעיית הטלה למרחב העמודות של המטריצה A A A A x ‾ ∗ A\underline{x}^* A x ∗
פתרון הבעיה
נזכר מה אנו רוצים להביא למינימום:
p ( x ) = ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 = ( A x ‾ − b ‾ ) t ( A x ‾ − b ‾ ) = ( x ‾ t A t − b ‾ t ) ( A x ‾ − b ‾ ) = x ‾ t A t A x ‾ − x ‾ t A t b ‾ − b ‾ t A x ‾ + b ‾ t b ‾ p(x)=\left| \left| A\underline{x}-\underline{b} \right| \right|_{2}^2=(A\underline{x}-\underline{b})^t(A\underline{x}-\underline{b})=(\underline{x}^tA^t-\underline{b}^t)(A\underline{x}-\underline{b})=\underline{x}^tA^tA\underline{x}-\underline{x}^tA^t\underline{b}-\underline{b}^tA\underline{x}+\underline{b}^t\underline{b} p ( x ) = ∣ ∣ A x − b ∣ ∣ 2 2 = ( A x − b ) t ( A x − b ) = ( x t A t − b t ) ( A x − b ) = x t A t A x − x t A t b − b t A x + b t b נשים לב כי כל האיברים הינם סקלים. בנוסף נשים לב כי שני האיברים האמצעיים הם הטרנספוז של אחד של השני ולכן, מכיוון שזה סקלר זה זהה ולכן:
= x ‾ t A t A x ‾ − 2 x ‾ t A t b ‾ + b ‾ t b ‾ = ↓ סימון x ‾ t K x ‾ − 2 x ‾ t f ‾ + c =\underline{x}^tA^tA\underline{x}-2\underline{x}^tA^t\underline{b}+\underline{b}^t\underline{b} \underset{\begin{matrix}
\downarrow \\
\R{\text{סימון}}
\end{matrix}}{=}\underline{x}^tK\underline{x}-2\underline{x}^t\underline{f}+c = x t A t A x − 2 x t A t b + b t b ↓ סימון = x t K x − 2 x t f + c נשים לב כי המטריצה K K K x ‾ \underline{x} x n n n פרבולה רב מימדית כי היא מכילה את איברי x ‾ \underline{x} x 0 , 1 , 2 0,1,2 0 , 1 , 2 הבעיה הריבועית .
בהינתן הבעיה הריבועית: p ( x ‾ ) = x ‾ t K x ‾ − 2 x ‾ t f ‾ + c p(\underline{x})=\underline{x}^tK\underline{x}-2\underline{x}^t\underline{f}+c p ( x ) = x t K x − 2 x t f + c { K , f ‾ , c } \left\{ K,\underline{f},c \right\} { K , f , c } K K K p ( x ‾ ) p(\underline{x}) p ( x )
x ‾ ∗ = K − 1 f ‾ \underline{x}^*=K^{-1}\underline{f} x ∗ = K − 1 f וערך הפונקציה בנקודה הזו הוא:
p ( x ‾ ∗ ) = c − ( x ‾ ∗ ) t K ( x ‾ ∗ ) p(\underline{x}^*)=c-(\underline{x}^*)^tK(\underline{x}^*) p ( x ∗ ) = c − ( x ∗ ) t K ( x ∗ )
בנוסחת הפתרון אנו נדרשים להפוך את K K K
הוכחה: x ‾ ∗ = K − 1 f ‾ ⟺ K x ‾ ∗ = f ‾ \underline{x}^*=K^{-1}\underline{f}\iff K\underline{x}^*=\underline{f} x ∗ = K − 1 f ⟺ K x ∗ = f p ( x ‾ ) p(\underline{x}) p ( x )
p ( x ‾ ) = x ‾ t K x ‾ − 2 x ‾ t f ‾ + c = x ‾ t K x ‾ − 2 x ‾ t K x ‾ ∗ + c = ( x ‾ − x ‾ ∗ ) t K ( x ‾ − x ‾ ∗ ) + c − ( x ‾ ∗ ) t K ( x ‾ ∗ ) \begin{align*}
p(\underline{x}) & =\underline{x}^tK\underline{x}-2\underline{x}^t\underline{f}+c=\underline{x}^tK\underline{x}-2\underline{x}^tK\underline{x}^*+c \\
& =(\underline{x}-\underline{x}^*)^tK(\underline{x}-\underline{x}^*)+c-(\underline{x}^*)^tK(\underline{x}^*)
\end{align*} p ( x ) = x t K x − 2 x t f + c = x t K x − 2 x t K x ∗ + c = ( x − x ∗ ) t K ( x − x ∗ ) + c − ( x ∗ ) t K ( x ∗ ) בתבנית שהתקבלה, בשל היות K K K ( x ‾ − x ‾ ∗ ) t K ( x ‾ − x ‾ ∗ ) ≥ 0 (\underline{x}-\underline{x}^*)^tK(\underline{x}-\underline{x}^*)\geq0 ( x − x ∗ ) t K ( x − x ∗ ) ≥ 0 0 0 0 x ‾ = x ‾ ∗ \underline{x}=\underline{x}^* x = x ∗ ∎
נשים לב כי ניצלנו במעברים את היות K K K
אם נחזור לבעיה המקורית p ( x ‾ ) = ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 p(\underline{x})=||A\underline{x}-\underline{b}||_{2}^2 p ( x ) = ∣∣ A x − b ∣ ∣ 2 2 x ‾ ∗ = K − 1 f ‾ = ( A t A ) − 1 A t b ‾ \underline{x}^*=K^{-1}\underline{f}=(A^tA)^{-1}A^t\underline{b} x ∗ = K − 1 f = ( A t A ) − 1 A t b רק אם עמודותיה של A A A A t A A^tA A t A
הגדרה 2 (המשוואה הנורמלית)
( A t A ) x ‾ ∗ = A t b ‾ ⟹ A t ( A x ‾ ∗ − b ‾ ) = A t r ‾ ∗ = 0 (A^tA)\underline{x}^*=A^t\underline{b} \implies A^t(A\underline{x}^*-\underline{b})=A^t\underline{r}^*=0 ( A t A ) x ∗ = A t b ⟹ A t ( A x ∗ − b ) = A t r ∗ = 0 בפתרון האופטימלי מתקבל כי השארית אנכית לעמודות המטריצה A A A
מה קורה כאשר A A A
מחד, הממ"ל A x ‾ = b ‾ A\underline{x}=\underline{b} A x = b x ‾ ∗ = A − 1 b ‾ \underline{x}^*=A^{-1}\underline{b} x ∗ = A − 1 b p ( x ‾ ∗ ) = 0 p(\underline{x}^*)=0 p ( x ∗ ) = 0
נרצה לבצע בדיקת שפיות, כלומר, לראות ששני הפתרונות שיש לנו שקולים:
x ‾ ∗ = ( A t A ) − 1 A t b ‾ = A − 1 ( A t ) − 1 A t b ‾ = A − 1 b ‾ \underline{x}^*=(A^tA)^{-1}A^t\underline{b}=A^{-1}(A^t)^{-1}A^t \underline{b}=A^{-1}\underline{b} x ∗ = ( A t A ) − 1 A t b = A − 1 ( A t ) − 1 A t b = A − 1 b ולכן, שני הפתרונות שקולים ולכן זה באמת עובד ונכון.
במקרה ש-A A A x ‾ ∗ = ( A t A ) − 1 A t b ‾ = A † b ‾ \underline{x}^*=(A^tA)^{-1}A^t\underline{b}=A^{\dagger}\underline{b} x ∗ = ( A t A ) − 1 A t b = A † b
מטריצת פסודו אינברס תסומן A † A^{^{\dagger}} A †
A † = ( A t A ) − 1 A t A^{^{\dagger}}=(A^tA)^{-1}A^t A † = ( A t A ) − 1 A t
A † A = ( A t A ) − 1 A t A = I A^{\dagger}A=(A^tA)^{-1}A^tA=I A † A = ( A t A ) − 1 A t A = I A A † ≠ I AA^{\dagger} \neq I A A † = I אנו מתחילים בבעיית ריבועים פחותים מתצורה:
p ( x ‾ ) = ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 = ( A x ‾ − b ‾ ) t ( A x ‾ − b ‾ ) p(\underline{x})=||A\underline{x}-\underline{b}||_{2}^2=(A\underline{x}-\underline{b})^t(A\underline{x}-\underline{b}) p ( x ) = ∣∣ A x − b ∣ ∣ 2 2 = ( A x − b ) t ( A x − b ) הפתרון הנדרש יהיה למעשה פתרון מערכת המשוואות:
( A t A ) x ‾ ∗ = A t b ‾ (A^tA)\underline{x}^*=A^t\underline{b} ( A t A ) x ∗ = A t b את פתרון זה נשיג ע"י פירוק L U LU LU או ליתר דיוק, מכיוון שאנו מניחים כי המטריצה A t A A^tA A t A פירוק C h o l e s k y Cholesky C h o l es k y .
פירוק L U LU LU
הכללת הפתרון
מה קורה כאשר A t A A^tA A t A
p ( x ‾ ) = x ‾ t K x ‾ − 2 x ‾ t f ‾ + c p(\underline{x})=\underline{x}^tK\underline{x}-2\underline{x}^t\underline{f}+c p ( x ) = x t K x − 2 x t f + c { K , f ‾ , c } \left\{ K,\underline{f},c \right\} { K , f , c } K K K K x ‾ ∗ = f ‾ K\underline{x}^*=\underline{f} K x ∗ = f
p ( x ‾ ∗ ) = c − ( x ‾ ∗ ) t K ( x ‾ ∗ ) p(\underline{x}^*)=c-(\underline{x}^*)^tK(\underline{x}^*) p ( x ∗ ) = c − ( x ∗ ) t K ( x ∗ ) הוכחה: x ‾ ∗ \underline{x}^* x ∗ K x ‾ ∗ = f ‾ K\underline{x}^*=\underline{f} K x ∗ = f
p ( x ) = x ‾ t K x ‾ − 2 x ‾ t f ‾ + c = x ‾ t K x ‾ − 2 x ‾ t K x ‾ ∗ + c = ( x ‾ − x ‾ ∗ ) t K ( x ‾ − x ‾ ∗ ) + c − ( x ‾ ∗ ) t K ( x ‾ ∗ ) \begin{align*}
p(x) & =\underline{x}^tK\underline{x}-2\underline{x}^t\underline{f}+c=\underline{x}^tK\underline{x}-2\underline{x}^tK\underline{x}^*+c \\
& =(\underline{x}-\underline{x}^*)^tK(\underline{x}-\underline{x}^*)+c-(\underline{x}^*)^tK(\underline{x}^*)
\end{align*} p ( x ) = x t K x − 2 x t f + c = x t K x − 2 x t K x ∗ + c = ( x − x ∗ ) t K ( x − x ∗ ) + c − ( x ∗ ) t K ( x ∗ ) בתבנית שהתקבלה, בשל היות K K K
( x ‾ − x ‾ ∗ ) t K ( x ‾ − x ‾ ∗ ) ≥ 0 (\underline{x}-\underline{x}^*)^tK(\underline{x}-\underline{x}^*)\geq 0 ( x − x ∗ ) t K ( x − x ∗ ) ≥ 0 ביטוי זה מובא לערכו המינימלי - 0, כאשר K ( x ‾ − x ‾ ∗ ) = 0 K(\underline{x}-\underline{x}^*)=0 K ( x − x ∗ ) = 0 K x ‾ = K x ‾ ∗ = f ‾ K\underline{x}=K\underline{x}^*=\underline{f} K x = K x ∗ = f ∎
מיהם כל אותם הפתרונות?K d ‾ = 0 K\underline{d}=0 K d = 0 x ‾ ∗ \underline{x}^* x ∗ x ‾ ∗ + d ‾ \underline{x}^*+\underline{d} x ∗ + d K ( x ‾ ∗ + d ) = K x ‾ ∗ = f ‾ K(\underline{x}^*+d)=K\underline{x}^*=\underline{f} K ( x ∗ + d ) = K x ∗ = f K K K k e r K kerK k erK
בחזרה להתחלה
נחזור לפרשנות לבעיית הריבועים הפחותים כבעיית הטלה. נתון לנו וקטור b ‾ \underline{b} b A A A
min x ‾ ∣ ∣ ∑ k = 1 n x k v ‾ k − b ‾ ∣ ∣ 2 2 = min x ‾ ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 \underset{\underline{x}}{\min}\left| \left| \sum_{k=1}^n x_{k}\underline{v}_{k}-\underline{b} \right| \right|_{2}^2=\underset{\underline{x}}{\min}||A\underline{x}-\underline{b}||_{2}^2 x min k = 1 ∑ n x k v k − b 2 2 = x min ∣∣ A x − b ∣ ∣ 2 2 אם עמודות A A A ∞ \infty ∞ x ‾ \underline{x} x A x ‾ ∗ A\underline{x}^* A x ∗ הסבר: אם A d ‾ = 0 A\underline{d}=0 A d = 0 x ‾ ∗ \underline{x}^* x ∗ x ‾ ∗ + d ‾ \underline{x}^*+\underline{d} x ∗ + d A ( x ‾ ∗ + d ‾ ) = A x ‾ ∗ A(\underline{x}^*+\underline{d})=A\underline{x}^* A ( x ∗ + d ) = A x ∗
הסתכלות אחרת על הפתרון
נסתכל על בעיה ספציפית:
min x ‾ ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 = min x ‾ ∣ ∣ ( 7 10 5 − 4 0 2 ) ( x 1 x 2 ) − ( 10 − 12 3 ) ∣ ∣ 2 2 \underset{\underline{x}}{\min}||A\underline{x}-\underline{b}||_{2}^2=\underset{\underline{x}}{\min}\left| \left| \begin{pmatrix}
7 & 10 \\
5 & -4 \\
0 & 2
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}-\begin{pmatrix}
10 \\
-12 \\
3
\end{pmatrix}\right| \right|_{2}^2 x min ∣∣ A x − b ∣ ∣ 2 2 = x min 7 5 0 10 − 4 2 ( x 1 x 2 ) − 10 − 12 3 2 2 הפתרון התקבל ע"י נוסחה "שנפלה עלינו משמיים":
x ‾ ∗ = ( A t A ) − 1 A t b ‾ = ( ( 7 5 0 10 − 4 2 ) ( 7 10 5 4 0 2 ) ) − 1 ( 7 5 0 10 4 2 ) ( 10 12 3 ) = ( 74 50 50 120 ) − 1 ( 10 154 ) = ( 1.0188 1.7078 ) \underline{x}^*=(A^tA)^{-1}A^t\underline{b}=\left(\begin{pmatrix}
7 & 5 & 0 \\
10 & -4 & 2
\end{pmatrix}\begin{pmatrix}
7 & 10 \\
5 & 4 \\
0 & 2
\end{pmatrix}\right)^{-1}\begin{pmatrix}
7 & 5 & 0 \\
10 & 4 & 2
\end{pmatrix}\begin{pmatrix}
10 \\
12 \\
3
\end{pmatrix}=\begin{pmatrix}
74 & 50 \\
50 & 120
\end{pmatrix}^{-1}\begin{pmatrix}
10 \\
154
\end{pmatrix}=\begin{pmatrix}
1.0188 \\
1.7078
\end{pmatrix} x ∗ = ( A t A ) − 1 A t b = ( 7 10 5 − 4 0 2 ) 7 5 0 10 4 2 − 1 ( 7 10 5 4 0 2 ) 10 12 3 = ( 74 50 50 120 ) − 1 ( 10 154 ) = ( 1.0188 1.7078 ) לו פתחנו את הסוגריים היינו מקבלים את p ( x ‾ ) p(\underline{x}) p ( x )
p ( x 1 , x 2 ) = ( 7 x 1 + 10 x 2 − 10 ) 2 + ( 5 x 1 − x 2 + 12 ) 2 + ( 2 x 2 − 3 ) 2 = 74 x 1 2 + 120 x 2 2 + 100 x 1 x 2 − 20 x 1 − 308 x 2 + 253 \begin{align*}
p(x_{1},x_{2})&=(7x_{1}+10x_{2}-10)^2+(5x_{1}-x_{2}+12)^2+(2x_{2}-3)^2 \\
&=74x_{1}^2+120x_{2}^2+100x_{1}x_{2}-20x_{1}-308x_{2}+253
\end{align*} p ( x 1 , x 2 ) = ( 7 x 1 + 10 x 2 − 10 ) 2 + ( 5 x 1 − x 2 + 12 ) 2 + ( 2 x 2 − 3 ) 2 = 74 x 1 2 + 120 x 2 2 + 100 x 1 x 2 − 20 x 1 − 308 x 2 + 253 אם לא היינו בהרצאה היום, כדי למצוא את המינימום היינו מנסים לגזור ולהשוות ל-0 0 0
∂ p ( x 1 , x 2 ) ∂ x 1 = 2 ⋅ 74 x 1 + 100 x 2 − 20 = 0 \frac{\partial p(x_{1},x_{2})}{\partial x_{1}}=2\cdot74x_{1}+100x_{2}-20=0 ∂ x 1 ∂ p ( x 1 , x 2 ) = 2 ⋅ 74 x 1 + 100 x 2 − 20 = 0 ∂ p ( x 1 , x 2 ) ∂ x 2 = 100 x 1 + 2 ⋅ 120 x 2 − 308 = 0 \frac{\partial p(x_{1},x_{2})}{\partial x_{2}}=100x_{1}+2\cdot 120x_{2}-308=0 ∂ x 2 ∂ p ( x 1 , x 2 ) = 100 x 1 + 2 ⋅ 120 x 2 − 308 = 0 ברישום אחר:
x ‾ ∗ = ( x 1 x 2 ) O P T = ( 74 50 50 120 ) − 1 ( 10 154 ) = ( 1.0188 1.7078 ) \underline{x}^*=\begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}_{OPT}=\begin{pmatrix}
74 & 50 \\
50 & 120
\end{pmatrix}^{-1}\begin{pmatrix}
10 \\
154
\end{pmatrix}=\begin{pmatrix}
1.0188 \\
1.7078
\end{pmatrix} x ∗ = ( x 1 x 2 ) OPT = ( 74 50 50 120 ) − 1 ( 10 154 ) = ( 1.0188 1.7078 ) קיבלנו את אותו הפתרון וזו הנקודה! .
גזירת ביטויים מטריציים-וקטוריים
הפונקציה בה אנו עוסקים היא p ( x ‾ ) : F n → F + p(\underline{x}):\mathbb{F}^n\to \mathbb{F}^+ p ( x ) : F n → F +
p ( x ‾ ) = ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 = ( A x ‾ − b ‾ ) t ( A x ‾ − b ‾ ) p(\underline{x})=||A\underline{x}-\underline{b}||_{2}^2=(A\underline{x}-\underline{b})^t(A\underline{x}-\underline{b}) p ( x ) = ∣∣ A x − b ∣ ∣ 2 2 = ( A x − b ) t ( A x − b ) מהו וקטור הגרדיאנט של פונקציה זו ∇ p ( x ‾ ) = [ ∂ p ( x ‾ ) ∂ x ‾ 1 ∂ p ( x ‾ ) ∂ x ‾ 2 ⋮ ∂ p ( x ‾ ) ∂ x ‾ n ] \nabla p(\underline{x})=\left[\begin{matrix}\frac{\partial p(\underline{x})}{\partial \underline{x}_{1}}\\\frac{\partial p(\underline{x})}{\partial \underline{x}_{2}}\\\vdots\\\frac{\partial p(\underline{x})}{\partial \underline{x}_{n}}\end{matrix}\right] ∇ p ( x ) = ∂ x 1 ∂ p ( x ) ∂ x 2 ∂ p ( x ) ⋮ ∂ x n ∂ p ( x )
למה זה נמצא במומלצת בסמסטר ב'? רק עכשיו אני לומד אינפי 2
אנחנו עכשיו הולכים למצוא את הפתרון ונתחיל ממקרה פשוט - נניח כי הפונקציה בנויה ממשוואה אחת, כלומר:
p ( x ‾ ) = ( a ‾ x ‾ − b ) 2 = ( ∑ k = 1 n a k x k − b ) 2 p(\underline{x})=(\underline{a}\ \underline{x}-b)^2=\left(\sum_{k=1}^n a_{k}x_{k}-b\right)^2 p ( x ) = ( a x − b ) 2 = ( k = 1 ∑ n a k x k − b ) 2 במקרה זה הגרדיאנט יהיה:
∇ p ( x ‾ ) = [ ∂ p ( x ‾ ) ∂ x ‾ 1 ∂ p ( x ‾ ) ∂ x ‾ 2 ⋮ ∂ p ( x ‾ ) ∂ x ‾ n ] = [ 2 ( ∑ k = 1 n a k x k − b ) a 1 2 ( ∑ k = 1 n a k x k − b ) a 2 ⋮ 2 ( ∑ k = 1 n a k x k − b ) a n ] = 2 ( ∑ k = 1 n a k x k − b ) ( a 1 a 2 ⋮ a n ) \nabla p(\underline{x})=\left[\begin{matrix}\frac{\partial p(\underline{x})}{\partial \underline{x}_{1}}\\\frac{\partial p(\underline{x})}{\partial \underline{x}_{2}}\\\vdots\\\frac{\partial p(\underline{x})}{\partial \underline{x}_{n}}\end{matrix}\right]=\left[\begin{matrix}
2\left( \sum_{k=1}^n a_{k}x_{k}-b \right)a_{1} \\
2\left( \sum_{k=1}^na_{k}x_{k}-b \right)a_{2} \\
\vdots \\
2\left( \sum_{k=1}^na_{k}x_{k}-b \right)a_{n}
\end{matrix}\right]=2\left( \sum_{k=1}^na_{k}x_{k}-b \right)\begin{pmatrix}
a_{1} \\
a_{2} \\
\vdots \\
a_{n}
\end{pmatrix} ∇ p ( x ) = ∂ x 1 ∂ p ( x ) ∂ x 2 ∂ p ( x ) ⋮ ∂ x n ∂ p ( x ) = 2 ( ∑ k = 1 n a k x k − b ) a 1 2 ( ∑ k = 1 n a k x k − b ) a 2 ⋮ 2 ( ∑ k = 1 n a k x k − b ) a n = 2 ( k = 1 ∑ n a k x k − b ) a 1 a 2 ⋮ a n ⇓ \Downarrow ⇓ ∇ p ( x ‾ ) = 2 a ‾ t ( a ‾ x ‾ − b ) \nabla p(\underline{x})=2\underline{a}^t(\underline{a}\ \underline{x}-b) ∇ p ( x ) = 2 a t ( a x − b ) כעת, נעבור למקרה מעט יותר מסובך עם הפונקציה הזו:
p ( x ‾ ) = ( a ‾ 1 x ‾ − b 1 ) 2 + ( a ‾ 2 x ‾ − b 2 ) 2 p(\underline{x})=(\underline{a}_{1}\underline{x}-b_{1})^2+(\underline{a}_{2}\underline{x}-b_{2})^2 p ( x ) = ( a 1 x − b 1 ) 2 + ( a 2 x − b 2 ) 2 גזירה היא פעולה לניארית ולכן זה יהיה חיבור של שני הגרדיאנטים:
p ( x ‾ ) = ∣ ∣ ( a ‾ 1 x ‾ − b 1 a ‾ 2 x ‾ − b 2 ) ∣ ∣ 2 2 = ∣ ∣ ( − a ‾ 1 − − a ‾ 2 − ) x ‾ − ( b 1 b 2 ) ∣ ∣ 2 2 = ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 p(\underline{x})=\left| \left| \begin{pmatrix}
\underline{a}_{1}\underline{x}-b_{1} \\
\underline{a}_{2}\underline{x}-b_{2}
\end{pmatrix} \right| \right|^2_{2}=\left| \left| \begin{pmatrix}
-\underline{a}_{1}- \\
-\underline{a}_{2}-
\end{pmatrix}\underline{x}-\begin{pmatrix}
b_{1} \\
b_{2}
\end{pmatrix} \right| \right|_{2}^2=\left| \left| A\underline{x}-\underline{b} \right| \right|_{2}^2 p ( x ) = ( a 1 x − b 1 a 2 x − b 2 ) 2 2 = ( − a 1 − − a 2 − ) x − ( b 1 b 2 ) 2 2 = ∣ ∣ A x − b ∣ ∣ 2 2 כעת, אנו יכולים לבצע את הגרדיאנט:
∇ p ( x ‾ ) = 2 a ‾ 1 t ( a ‾ 1 x ‾ − b 1 ) + 2 a ‾ 2 t ( a ‾ 2 x ‾ − b 2 ) = 2 ( ∣ ∣ a ‾ 1 t a ‾ 2 t ∣ ∣ ) ( a ‾ 1 x ‾ − b 1 a ‾ 2 x ‾ − b 2 ) = 2 A t ( A x ‾ − b ‾ ) \nabla p(\underline{x})=2\underline{a}_{1}^t(\underline{a}_{1}\underline{x}-b_{1})+2\underline{a}_{2}^t(\underline{a}_{2}\underline{x}-b_{2})=2\begin{pmatrix}
\vert & \vert \\
\underline{a}_{1}^t & \underline{a}_{2}^t \\
\vert & \vert
\end{pmatrix}\begin{pmatrix}
\underline{a}_{1}\underline{x}-b_{1} \\
\underline{a}_{2}\underline{x}-b_{2}
\end{pmatrix}=2A^t(A\underline{x}-\underline{b}) ∇ p ( x ) = 2 a 1 t ( a 1 x − b 1 ) + 2 a 2 t ( a 2 x − b 2 ) = 2 ∣ a 1 t ∣ ∣ a 2 t ∣ ( a 1 x − b 1 a 2 x − b 2 ) = 2 A t ( A x − b ) במקרה הכללי:
p ( x ‾ ) = ∑ k = 1 m ( a ‾ k x ‾ − b k ) 2 = ∣ ∣ ( − a 1 − ⋮ − a m − ) x ‾ − ( b 1 ⋮ b m ) ∣ ∣ 2 2 = ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 p(\underline{x})=\sum_{k=1}^m(\underline{a}_{k}\underline{x}-b_{k})^2=\left| \left| \begin{pmatrix}
- & a_{1} & - \\
& \vdots \\
- & a_{m} & -
\end{pmatrix}\underline{x}-\begin{pmatrix}
b_{1} \\
\vdots \\
b_{m}
\end{pmatrix} \right| \right|_{2}^2=\left| \left| A\underline{x}-\underline{b} \right| \right|_{2}^2 p ( x ) = k = 1 ∑ m ( a k x − b k ) 2 = − − a 1 ⋮ a m − − x − b 1 ⋮ b m 2 2 = ∣ ∣ A x − b ∣ ∣ 2 2 ∇ p ( x ‾ ) = 2 ∑ k = 1 m a ‾ k t ( a ‾ k x ‾ − b k ) = 2 ( ∣ ∣ a ‾ 1 t … a ‾ m t ∣ ∣ ) ( a ‾ 1 x ‾ − b 1 ⋮ a ‾ m x ‾ − b m ) = 2 A t ( A x ‾ − b ‾ ) \nabla p(\underline{x})=2\sum_{k=1}^m \underline{a}_{k}^t(\underline{a}_{k}\underline{x}-b_{k})=2\begin{pmatrix}
\vert & & \vert \\
\underline{a}_{1}^t & \dots & \underline{a}_{m}^t \\
\vert & & \vert
\end{pmatrix}\begin{pmatrix}
\underline{a}_{1}\underline{x}-b_{1} \\
\vdots \\
\underline{a}_{m}\underline{x}-b_{m}
\end{pmatrix}=2A^t(A\underline{x}-\underline{b}) ∇ p ( x ) = 2 k = 1 ∑ m a k t ( a k x − b k ) = 2 ∣ a 1 t ∣ … ∣ a m t ∣ a 1 x − b 1 ⋮ a m x − b m = 2 A t ( A x − b ) זוהי נוסחת הנגזרת הכללית של תבנית הריבועים הפחותים.
עבור הפונקציה: p ( x ‾ ) = ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 p(\underline{x})=||A\underline{x}-\underline{b}||_{2}^2 p ( x ) = ∣∣ A x − b ∣ ∣ 2 2
∇ p ( x ‾ ) = 2 A t ( A x ‾ − b ‾ ) \nabla p(\underline{x})=2A^t(A\underline{x}-\underline{b}) ∇ p ( x ) = 2 A t ( A x − b ) איפוס הגרדיאנט מוביל משוואה הנורמלית A t A x ‾ = A t b ‾ A^tA\underline{x}=A^t\underline{b} A t A x = A t b A t A A^tA A t A
עוד מקרה
מה באשר לפונקציה במבנה: p ( x ‾ ) = x ‾ t K x ‾ − 2 x ‾ t f ‾ + c p(\underline{x})=\underline{x}^tK\underline{x}-2\underline{x}^t\underline{f}+c p ( x ) = x t K x − 2 x t f + c
p ( x ‾ ) = ( x 1 x 2 ) ( k 11 k 12 k 21 k 22 ) ( x 1 x 2 ) − 2 ( x 1 x 2 ) ( f 1 f 2 ) + c = k 11 x 1 2 + k 12 x 1 x 2 + k 21 x 1 x 2 + k 22 x 2 2 − 2 f 1 x 1 − 2 f 2 x 2 + c \begin{align*}
p(\underline{x})&=\begin{pmatrix}
x_{1} & x_{2}
\end{pmatrix}\begin{pmatrix}
k_{11} & k_{12} \\
k_{21} & k_{22}
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}-2\begin{pmatrix}
x_{1} & x_{2}
\end{pmatrix}\begin{pmatrix}
f_{1} \\
f_{2}
\end{pmatrix}+c \\
&=k_{11}x_{1}^2+k_{12}x_{1}x_{2}+k_{21}x_{1}x_{2}+k_{22}x_{2}^2-2f_{1}x_{1}-2f_{2}x_{2}+c
\end{align*} p ( x ) = ( x 1 x 2 ) ( k 11 k 21 k 12 k 22 ) ( x 1 x 2 ) − 2 ( x 1 x 2 ) ( f 1 f 2 ) + c = k 11 x 1 2 + k 12 x 1 x 2 + k 21 x 1 x 2 + k 22 x 2 2 − 2 f 1 x 1 − 2 f 2 x 2 + c נגזור אותו ונקבל:
∇ ( x ‾ ) = p ( 2 k 11 x 1 + k 12 x 2 + k 21 x 2 − 2 f 1 2 k 22 x 2 + k 12 x 1 + k 21 x 1 − 2 f 2 ) = 2 ( k 11 k 12 + k 21 2 k 12 + k 21 2 k 22 ) ( x 1 x 2 ) − 2 ( f 1 f 2 ) \begin{align*}
\nabla (\underline{x})&=p\begin{pmatrix}
2k_{11}x_{1}+k_{12}x_{2}+k_{21}x_{2}-2f_{1} \\
2k_{22}x_{2}+k_{12}x_{1}+k_{21}x_{1}-2f_{2}
\end{pmatrix} \\
&=2\begin{pmatrix}
k_{11} & \frac{k_{12}+k_{21}}{2} \\
\frac{k_{12}+k_{21}}{2} & k_{22}
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}-2\begin{pmatrix}
f_{1} \\
f_{2}
\end{pmatrix}
\end{align*} ∇ ( x ) = p ( 2 k 11 x 1 + k 12 x 2 + k 21 x 2 − 2 f 1 2 k 22 x 2 + k 12 x 1 + k 21 x 1 − 2 f 2 ) = 2 ( k 11 2 k 12 + k 21 2 k 12 + k 21 k 22 ) ( x 1 x 2 ) − 2 ( f 1 f 2 ) בשל סימטריות K K K ∇ p ( x ‾ ) = 2 ( K x ‾ − f ‾ ) \nabla p(\underline{x})=2(K\underline{x}-\underline{f}) ∇ p ( x ) = 2 ( K x − f )
ישנם שפע של נוסחאות של גזירה של ביטויים מטריציים-וקטוריים
פתרון בעיות באמצעות ריבועים פחותים
התאמת עקומים לנתונים
נניח כי נתון לנו אוסף צימדי נתונים { t i , b i } i = 1 m \left\{ t_{i},b_{i} \right\}_{i=1}^m { t i , b i } i = 1 m נרצה למצוא את הישר b = α t + β b=\alpha t+\beta b = α t + β
הבעיה שלפנינו הינה בעיית ריבועים פחותים קלאסית. המשימה בעצם הינה
min α , β ∑ k = 1 m ( α t k + β − b k ) 2 \underset{\alpha,\beta}{\min}\sum_{k=1}^m (\alpha t_{k}+\beta-b_{k})^2 α , β min k = 1 ∑ m ( α t k + β − b k ) 2 איך רואים שהיא ריבועים פחותים? נבנה מטריצה שעמודתה הראשונה היא אחדים והעמודה השנייה היא ערכי t t t b b b
( 1 t 1 1 t 2 1 t 3 ⋮ ⋮ 1 t m ) ( β α ) − ( b 1 b 2 b 3 ⋮ b m ) = A x ‾ − b ‾ \begin{pmatrix}
1 & t_{1} \\
1 & t_{2} \\
1 & t_{3} \\
\vdots & \vdots \\
1 & t_{m}
\end{pmatrix}\begin{pmatrix}
\beta \\
\alpha
\end{pmatrix}-\begin{pmatrix}
b_{1} \\
b_{2} \\
b_{3} \\
\vdots \\
b_{m}
\end{pmatrix}=A\underline{x}-\underline{b} 1 1 1 ⋮ 1 t 1 t 2 t 3 ⋮ t m ( β α ) − b 1 b 2 b 3 ⋮ b m = A x − b נקרא את השורה הראשונה והיא בדיוק אומרת: β + t 1 α − b 1 \beta+t_{1}\alpha-b_{1} β + t 1 α − b 1 min x ‾ ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 \underset{\underline{x}}{\min}\left| \left| A\underline{x}-\underline{b} \right| \right|_{2}^2 x min ∣ ∣ A x − b ∣ ∣ 2 2
מהי המשמעות הגיאומטרית של מה שראינו זה עתה? כל פתרון שיוצא ייצור סטיות בין הנקודות לבין הקו המוצע. נסמנו r k r_{k} r k
r k = α t k + β − b k r_{k}=\alpha t_{k}+\beta-b_{k} r k = α t k + β − b k סכום ריבועי המרחקים האלו הוא מה שאנחנו מנסים למזער בפתרון בעיית הריבועים הפחותים.
כעת נפתור זאת פרקטית :
min x ‾ ∣ ∣ ( 1 t 1 1 t 2 1 t 3 ⋮ ⋮ 1 t m ) ( β α ) ( b 1 b 2 b 3 ⋮ b m ) ∣ ∣ 2 2 = min x ‾ ∣ ∣ A x ‾ − b ‾ ∣ ∣ 2 2 \underset{\underline{x}}{\min}\left| \left| \begin{pmatrix}
1 & t_{1} \\
1 & t_{2} \\
1 & t_{3} \\
\vdots & \vdots \\
1 & t_{m}
\end{pmatrix}\begin{pmatrix}
\beta \\
\alpha
\end{pmatrix}\begin{pmatrix}
b_{1} \\
b_{2} \\
b_{3} \\
\vdots \\
b_{m}
\end{pmatrix} \right| \right|_{2}^2=\underset{\underline{x}}{\min}\left| \left| A\underline{x}-\underline{b} \right| \right|_{2}^2 x min 1 1 1 ⋮ 1 t 1 t 2 t 3 ⋮ t m ( β α ) b 1 b 2 b 3 ⋮ b m 2 2 = x min ∣ ∣ A x − b ∣ ∣ 2 2 הפתרון האופטימלי נתון לנו ע"י הנוסחה ממקודם:
( A t A ) − 1 A t ⋅ b = x ‾ ∗ = ( β ∗ α ∗ ) (A^tA)^{-1}A^t\cdot b=\underline{x}^*=\begin{pmatrix}
\beta^* \\
\alpha^*
\end{pmatrix} ( A t A ) − 1 A t ⋅ b = x ∗ = ( β ∗ α ∗ ) נסתכל מה זה A t A A^tA A t A
A t A = ( 1 1 … 1 t 1 t 2 … t m ) ( 1 t 1 1 t 2 ⋮ ⋮ 1 t m ) = ( m ∑ i = 1 m t i ∑ i = 1 m t i ∑ i = 1 m t i 2 ) A^tA=\begin{pmatrix}
1 & 1 & \dots & 1 \\
t_{1} & t_{2} & \dots & t_{m}
\end{pmatrix}\begin{pmatrix}
1 & t_{1} \\
1 & t_{2} \\
\vdots & \vdots \\
1 & t_{m}
\end{pmatrix}=\begin{pmatrix}
m & \sum_{i=1}^m t_{i} \\
\sum_{i=1}^m t_{i} & \sum_{i=1}^m t_{i}^2
\end{pmatrix} A t A = ( 1 t 1 1 t 2 … … 1 t m ) 1 1 ⋮ 1 t 1 t 2 ⋮ t m = ( m ∑ i = 1 m t i ∑ i = 1 m t i ∑ i = 1 m t i 2 ) נסתכל מה זה A t b ‾ A^t\underline{b} A t b
( 1 1 … 1 t 1 t 2 … t m ) ( b 1 b 2 ⋮ b m ) = ( ∑ i = 1 m b i ∑ i = 1 m t i b i ) \begin{pmatrix}
1 & 1 & \dots & 1 \\
t_{1} & t_{2} & \dots & t_{m}
\end{pmatrix}\begin{pmatrix}
b_{1} \\
b_{2} \\
\vdots \\
b_{m}
\end{pmatrix}=\begin{pmatrix}
\sum_{i=1}^m b_{i} \\
\sum_{i=1}^m t_{i}b_{i}
\end{pmatrix} ( 1 t 1 1 t 2 … … 1 t m ) b 1 b 2 ⋮ b m = ( ∑ i = 1 m b i ∑ i = 1 m t i b i )
יש פתרון יחיד לבעיית ריבועים פחותים רק כש-A A A ∞ \infty ∞ t t t
לכן מתקיים:
( β ∗ α ∗ ) = x ‾ ∗ = ( m ∑ i = 1 m t i ∑ i = 1 m t i ∑ i = 1 m t i 2 ) − 1 ( ∑ i = 1 m b i ∑ i = 1 m t i b i ) \begin{pmatrix}
\beta^* \\
\alpha^*
\end{pmatrix}=\underline{x}^*=\begin{pmatrix}
m & \sum_{i=1}^m t_{i} \\
\sum_{i=1}^m t_{i} & \sum_{i=1}^m t_{i}^2
\end{pmatrix}^{-1}\begin{pmatrix}
\sum_{i=1}^m b_{i} \\
\sum_{i=1}^m t_{i}b_{i}
\end{pmatrix} ( β ∗ α ∗ ) = x ∗ = ( m ∑ i = 1 m t i ∑ i = 1 m t i ∑ i = 1 m t i 2 ) − 1 ( ∑ i = 1 m b i ∑ i = 1 m t i b i ) הסתכלות אחרת על בעיית העקומים
נבחר שתי פונקציות מעל הממשיים:
ϕ 1 ( t ) = 1 ϕ 2 ( t ) = t \phi_{1}(t)=1 \qquad \qquad \phi_{2}(t)=t ϕ 1 ( t ) = 1 ϕ 2 ( t ) = t הקירוב שאנו מציעים הוא צירוף של שתי פונקציות אלה מהצורה:
f ( t ) = β ϕ 1 ( t ) + α ϕ 2 ( t ) = α t + β f(t)=\beta \phi_{1}(t)+\alpha \phi_{2}(t)=\alpha t+\beta f ( t ) = β ϕ 1 ( t ) + α ϕ 2 ( t ) = α t + β הקירוב שהצענו ממקודם של הריבועים הפחותים מציב את הנקודות הנתונות ומבקש שגיאה מינימלית
p ( α , β ) = ∑ i = 1 m ( β ϕ 1 ( t k ) + α ϕ 2 ( t k ) − b k ) 2 ⟶ α , β min p(\alpha,\beta)=\sum_{i=1}^m(\beta \phi_{1}(t_{k})+\alpha \phi_{2}(t_{k})-b_{k})^2 \underset{\alpha,\beta}{\longrightarrow} \min p ( α , β ) = i = 1 ∑ m ( β ϕ 1 ( t k ) + α ϕ 2 ( t k ) − b k ) 2 α , β ⟶ min זה העקום שלנו ואנו נרצה שכשנציב את t k t_{k} t k b k b_{k} b k
∥ ( ϕ 1 ( t 1 ) ϕ 2 ( t t ) ϕ 1 ( t 2 ) ϕ 2 ( t 2 ) ϕ 1 ( t 3 ) ϕ 2 ( t 3 ) ⋮ ⋮ ϕ 1 ( t m ) ϕ 2 ( t m ) ) ( β α ) − ( b 1 b 2 b 3 ⋮ b m ) ∥ 2 2 = ∥ A x ‾ − b ‾ ∥ 2 2 ⟶ x ‾ min \left\lVert \begin{pmatrix}
\phi_{1}(t_{1}) & \phi_{2}(t_{t}) \\
\phi_{1}(t_{2}) & \phi_{2}(t_{2}) \\
\phi_{1}(t_{3}) & \phi_{2}(t_{3}) \\
\vdots & \vdots \\
\phi_{1}(t_{m}) & \phi_{2}(t_{m})
\end{pmatrix}\begin{pmatrix}
\beta \\
\alpha
\end{pmatrix}-\begin{pmatrix}
b_{1} \\
b_{2} \\
b_{3} \\
\vdots \\
b_{m}
\end{pmatrix}\right\rVert_{2}^2=\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2 \underset{\underline{x}}{\longrightarrow}\min ϕ 1 ( t 1 ) ϕ 1 ( t 2 ) ϕ 1 ( t 3 ) ⋮ ϕ 1 ( t m ) ϕ 2 ( t t ) ϕ 2 ( t 2 ) ϕ 2 ( t 3 ) ⋮ ϕ 2 ( t m ) ( β α ) − b 1 b 2 b 3 ⋮ b m 2 2 = ∥ A x − b ∥ 2 2 x ⟶ min כעת, נוכל להשתמש באותה הנוסחה ממקודם ולפתור ריבועים פחותים כרגיל.
שימוש בהסתכלות האחרת בתצורה מעניינת
נניח שוב כי נתון סט נקודות במישור { t i , b i } i = 1 m \left\{ t_{i},b_{i} \right\}_{i=1}^m { t i , b i } i = 1 m
f ( t ) = x 1 sin ( 3 t ) + x 2 ln ( ∣ t + 40 ∣ + 3 ) + x 3 ⋅ t 3.5 f(t)=x_{1}\sin(3t)+x_{2}\ln (|t+40|+3)+x_{3}\cdot t^{3.5} f ( t ) = x 1 sin ( 3 t ) + x 2 ln ( ∣ t + 40∣ + 3 ) + x 3 ⋅ t 3.5 כעת אנו נשאל את עצמנו מיהם x 1 , x 2 , x 3 x_{1},x_{2},x_{3} x 1 , x 2 , x 3
A r g min x 1 , x 2 , x 3 ∑ i = 1 m ( f ( t i ) − b i ) 2 = A r g min x 1 , x 2 , x 3 ∑ i = 1 m ( x 1 sin ( 3 t i ) + x 2 ln ( ∣ t i + 40 ∣ + 3 ) + x 3 t i 3.5 − b i ) 2 \underset{x_{1},x_{2},x_{3}}{Arg \min}\sum_{i=1}^m(f(t_{i})-b_{i})^2=\underset{x_{1},x_{2},x_{3}}{Arg \min}\sum_{i=1}^m (x_{1}\sin(3t_{i})+x_{2}\ln(|t_{i}+40|+3)+x_{3}t_{i}^{3.5}-b_{i})^2 x 1 , x 2 , x 3 A r g min i = 1 ∑ m ( f ( t i ) − b i ) 2 = x 1 , x 2 , x 3 A r g min i = 1 ∑ m ( x 1 sin ( 3 t i ) + x 2 ln ( ∣ t i + 40∣ + 3 ) + x 3 t i 3.5 − b i ) 2 נכתוב אותה בתצורה מטריצית-וקטורית ונראה כי היא בעיית ריבועים פחותים:
∥ ( sin ( 3 t 1 ) ln ( ∣ t 1 + 40 ∣ + 3 ) t 1 3.5 sin ( 3 t 2 ) ln ( ∣ t 2 + 40 ∣ + 3 ) t 2 3.5 ⋮ ⋮ ⋮ sin ( 3 t m ) ln ( ∣ t m + 40 ∣ + 3 ) t m 3.5 ) ( x 1 x 2 x 3 ) − ( b 1 b 2 ⋮ b m ) ∥ 2 2 = ∥ A x ‾ − b ‾ ∥ 2 2 ⟶ x ‾ min \left\lVert \begin{pmatrix}
\sin(3t_{1}) & \ln(|t_{1}+40|+3) & t_{1}^{3.5} \\
\sin(3t_{2}) & \ln(|t_{2}+40|+3) & t_{2}^{3.5} \\
\vdots & \vdots & \vdots \\
\sin(3t_{m}) & \ln(|t_{m}+40|+3) & t_{m}^{3.5}
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2} \\
x_{3}
\end{pmatrix}-\begin{pmatrix}
b_{1} \\
b_{2} \\
\vdots \\
b_{m}
\end{pmatrix} \right\rVert _{2}^2=\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2 \underset{\underline{x}}{\longrightarrow} \min sin ( 3 t 1 ) sin ( 3 t 2 ) ⋮ sin ( 3 t m ) ln ( ∣ t 1 + 40∣ + 3 ) ln ( ∣ t 2 + 40∣ + 3 ) ⋮ ln ( ∣ t m + 40∣ + 3 ) t 1 3.5 t 2 3.5 ⋮ t m 3.5 x 1 x 2 x 3 − b 1 b 2 ⋮ b m 2 2 = ∥ A x − b ∥ 2 2 x ⟶ min נשים לב כי אם נשווה את זה למקרה הכללי ממקודם, נקבל:
ϕ 1 ( t ) = sin ( 3 t ) ϕ 2 ( t ) = ln ( ∣ t + 40 ∣ + 3 ) ϕ 3 ( t ) = t 3.5 \phi_{1}(t)=\sin(3t) \qquad \phi_{2}(t)=\ln(|t+40|+3) \qquad \phi_{3}(t)=t^{3.5} ϕ 1 ( t ) = sin ( 3 t ) ϕ 2 ( t ) = ln ( ∣ t + 40∣ + 3 ) ϕ 3 ( t ) = t 3.5 וזה בדיוק אותו הדבר.
הכללת הרעיון
בהינתן סט נתונים { t i , b i } i = 1 m \left\{ t_{i},b_{i} \right\}_{i=1}^m { t i , b i } i = 1 m { ϕ k ( t ) } k = 1 P \large \left\{ \phi_{k}(t) \right\}_{k=1}^P { ϕ k ( t ) } k = 1 P
f ( t ) = ∑ k = 1 P x k ϕ k ( t ) f(t)=\sum_{k=1}^P x_{k}\phi_{k}(t) f ( t ) = k = 1 ∑ P x k ϕ k ( t ) הנעלמים בסיפור הזה הינם: x 1 , x 2 , … , x P x_{1},x_{2},\dots,x_{P} x 1 , x 2 , … , x P
{ x ^ i } i = 1 P = A r g min { x i } i = 1 P ∑ i = 1 m ( ∑ k = 1 P x k ϕ k ( t i ) − b i ) 2 \left\{ \hat{x}_{i} \right\}_{i=1}^P =\underset{\left\{ {x}_{i} \right\}_{i=1}^P}{Arg \min}\sum_{i=1}^m\left( \sum_{k=1}^P x_{k}\phi_{k}(t_{i})-b_{i} \right)^2 { x ^ i } i = 1 P = { x i } i = 1 P A r g min i = 1 ∑ m ( k = 1 ∑ P x k ϕ k ( t i ) − b i ) 2 ונוכל גם לראות זאת בתצורה מטריצית-וקטורית:
∥ ( ϕ 1 ( t 1 ) ϕ 2 ( t 1 ) ⋯ ϕ P ( t 1 ) ϕ 1 ( t 2 ) ϕ 2 ( t 2 ) ⋯ ϕ P ( t 2 ) ϕ 1 ( t 3 ) ϕ 2 ( t 3 ) ⋯ ϕ P ( t 3 ) ⋮ ⋮ ⋮ ϕ 1 ( t m ) ϕ 2 ( t m ) ⋯ ϕ P ( t m ) ) ( x 1 x 2 x 3 ⋮ x p ) − ( b 1 b 2 b 3 ⋮ b m ) ∥ 2 2 = ∥ A x ‾ − b ‾ ∥ 2 2 ⟶ x ‾ min \left\lVert \begin{pmatrix}
\phi_{1}(t_{1}) & \phi_{2}(t_{1}) & \cdots & \phi_{P}(t_{1}) \\
\phi_{1}(t_{2}) & \phi_{2}(t_{2}) & \cdots & \phi_{P}(t_{2}) \\
\phi_{1}(t_{3}) & \phi_{2}(t_{3}) & \cdots & \phi_{P}(t_{3}) \\
\vdots & \vdots & & \vdots \\
\phi_{1}(t_{m}) & \phi_{2}(t_{m}) & \cdots & \phi_{P}(t_{m})
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2} \\
x_{3} \\
\vdots \\
x_{p}
\end{pmatrix}-\begin{pmatrix}
b_{1} \\
b_{2} \\
b_{3} \\
\vdots \\
b_{m}
\end{pmatrix} \right\rVert_{2}^2=\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2 \underset{\underline{x}}{\longrightarrow} \min ϕ 1 ( t 1 ) ϕ 1 ( t 2 ) ϕ 1 ( t 3 ) ⋮ ϕ 1 ( t m ) ϕ 2 ( t 1 ) ϕ 2 ( t 2 ) ϕ 2 ( t 3 ) ⋮ ϕ 2 ( t m ) ⋯ ⋯ ⋯ ⋯ ϕ P ( t 1 ) ϕ P ( t 2 ) ϕ P ( t 3 ) ⋮ ϕ P ( t m ) x 1 x 2 x 3 ⋮ x p − b 1 b 2 b 3 ⋮ b m 2 2 = ∥ A x − b ∥ 2 2 x ⟶ min כעת, נקבל את המקדמים האופטימליים ע"י:
A t ( A x ‾ − b ‾ ) = 0 ‾ ⟹ x ‾ ^ = ( A t A ) − 1 A t b ‾ A^t(A\underline{x}-\underline{b})=\underline{0} \implies \hat{\underline{x}}=(A^tA)^{-1}A^t\underline{b} A t ( A x − b ) = 0 ⟹ x ^ = ( A t A ) − 1 A t b כעת קיבלנו את ה-x x x x x x
f ^ ( t ) = ∑ k = 1 P x ^ k ϕ k ( t ) \hat{f}(t)=\sum_{k=1}^P \hat{x}_{k}\phi_{k}(t) f ^ ( t ) = k = 1 ∑ P x ^ k ϕ k ( t ) וזה כל הסיפור.
על בחירת הפונקציות ϕ t \phi_{t} ϕ t
ישנו חופש מוחלט בבחירת הפונקציות והיא נעשית מתוך הבנת המשימה.
{ ϕ k ( t ) } k = { t k } k = 0 p \left\{ \phi_{k}(t) \right\}_{k}=\left\{ t^k \right\}_{k=0}^p { ϕ k ( t ) } k = { t k } k = 0 p במקרה זה המטריצה A A A ונדרמונדה .
( 1 t 1 t 2 2 … t 1 p 1 t 2 t 2 2 … t 2 p ⋮ ⋮ ⋮ ⋮ 1 t m t m 2 … t m p ) \begin{pmatrix}
1 & t_{1} & t_{2}^2 & \dots & t_{1}^p \\
1 & t_{2} & t_{2}^2 & \dots & t_{2}^p \\
\vdots & \vdots & \vdots & & \vdots \\
1 & t_{m} & t_{m}^2 & \dots & t_{m}^p
\end{pmatrix} 1 1 ⋮ 1 t 1 t 2 ⋮ t m t 2 2 t 2 2 ⋮ t m 2 … … … t 1 p t 2 p ⋮ t m p המטריצה אומרת שהבעיה היא לקחת m m m m − 1 m-1 m − 1 t i t_{i} t i p + 1 = m p+1=m p + 1 = m t k t_{k} t k קיים פתרון יחיד .
דוגמה (פונקציות הרמוניות)
{ ϕ k ( t ) } k = { cos 2 π k t M , sin 2 π k t M } k = 0 P \left\{ \phi_{k}(t) \right\}_{k}=\left\{ \cos \frac{2\pi kt}{M},\sin \frac{2\pi kt}{M} \right\}_{k=0}^P { ϕ k ( t ) } k = { cos M 2 πk t , sin M 2 πk t } k = 0 P נושא זה קשור להתמרות פורייה עליו נדבר לקראת סוף הקורס.
ריבועים פחותים ממושקלים
נניח עכשיו כי במקום שני נתונים אנו מקבלים שלושה כאשר הנתון השלישי הוא אי שלילי והוא מדד לאמינותה של הנקודה(ערך גבוה לאמינות גבוהה)
{ t i , b i , w i } i = 1 m \left\{ t_{i},b_{i},w_{i} \right\}_{i=1}^m { t i , b i , w i } i = 1 m אנו רוצים, כמו ממקודם, להתאים לנתונים אלו קירוב מהצורה הכללית f ( t ) = ∑ k = 1 p x k ϕ k ( t ) f(t)=\sum_{k=1}^px_{k}\phi_{k}(t) f ( t ) = ∑ k = 1 p x k ϕ k ( t ) w i w_{i} w i
{ x ^ i } i = 1 p = A r g min { x i } i = 1 p ∑ i = 1 m w i ( ∑ k = 1 p x k ϕ k ( t i ) − b i ) 2 \left\{ \hat{x}_{i} \right\}_{i=1}^p =\underset{\left\{ {x}_{i} \right\}_{i=1}^p}{Arg \min}\sum_{i=1}^m {\color{red}w_{i}}\left( \sum_{k=1}^px_{k}\phi_{k}(t_{i})-b_{i} \right)^2 { x ^ i } i = 1 p = { x i } i = 1 p A r g min i = 1 ∑ m w i ( k = 1 ∑ p x k ϕ k ( t i ) − b i ) 2 נשים לב כי עכשיו אנחנו עושים סוג של ממוצע משוקלל של כל הנקודות שלנו. נוכל גם לרשום זאת כך:
{ x ^ i } i = 1 p = A r g min { x i } i = 1 p ∑ i = 1 m w i r i 2 ( x ‾ ) \left\{ \hat{x}_{i} \right\}_{i=1}^p =\underset{\left\{ {x}_{i} \right\}_{i=1}^p}{Arg \min}\sum_{i=1}^m w_{i}r_{i}^2(\underline{x}) { x ^ i } i = 1 p = { x i } i = 1 p A r g min i = 1 ∑ m w i r i 2 ( x ) כאשר r i ( x ‾ ) = ∑ k = 1 p x k ϕ k ( t i ) − b i r_{i}(\underline{x})=\sum_{k=1}^px_{k}\phi_{k}(t_{i})-b_{i} r i ( x ) = ∑ k = 1 p x k ϕ k ( t i ) − b i
( A x ‾ − b ‾ ) t W ( A x ‾ − b ‾ ) = ∥ A x ‾ − b ‾ ∥ W 2 ⟶ x ‾ min (A\underline{x}-\underline{b})^tW(A\underline{x}-\underline{b})=\left\lVert A\underline{x}-\underline{b} \right\rVert _{W}^2 \underset{\underline{x}}{\longrightarrow} \min ( A x − b ) t W ( A x − b ) = ∥ A x − b ∥ W 2 x ⟶ min
ה-W W W
נתחיל לפרק כדי למצוא פתרון:
( A x ‾ − b ‾ ) t W ( A x ‾ − b ‾ ) = x ‾ t A t W A x ‾ − 2 x ‾ t A t W b ‾ + b ‾ t W b ‾ (A\underline{x}-\underline{b})^tW(A\underline{x}-\underline{b})=\underline{x}^tA^tWA\underline{x}-2\underline{x}^tA^tW\underline{b}+\underline{b}^tW\underline{b} ( A x − b ) t W ( A x − b ) = x t A t W A x − 2 x t A t W b + b t W b מכאן נובע כי הפתרון לבעיית הריבועים הפחותים במקרה זה חייבת לקיים:
A t W A x ‾ ∗ = A t W b ‾ A^tWA\underline{x}^*=A^tW\underline{b} A t W A x ∗ = A t W b
נרצה שב-W W W A t W A A^tWA A t W A A A A
רגולריזציה
נרצה להציע תיקון או הרחבה לבעיית הריבועים הפחותים על מנת להימנע ממצב של ∞ \infty ∞ רגולריזציה .A t A A^tA A t A A t A + λ I A^tA+\lambda I A t A + λ I λ > 0 \lambda>0 λ > 0 חיובית מוגדרת .הוכחה:
∀ x ‾ ≠ 0 x ‾ t ( A t A + λ I ) x ‾ = x ‾ t A t A x ‾ + λ x ‾ t x ‾ = ∥ A x ‾ ∥ 2 2 + λ ∥ x ‾ ∥ 2 2 ≥ λ ∥ x ‾ ∥ 2 2 > 0 \begin{align*}
\forall \underline{x} \neq 0 \qquad & \underline{x}^t(A^tA+\lambda I)\underline{x}=\underline{x}^tA^tA\underline{x}+\lambda \underline{x}^t\underline{x}=\left\lVert A\underline{x} \right\rVert _{2}^2
\end{align*}+\lambda \left\lVert \underline{x} \right\rVert _{2}^2\geq \lambda \left\lVert \underline{x} \right\rVert _{2}^2 >0 ∀ x = 0 x t ( A t A + λ I ) x = x t A t A x + λ x t x = ∥ A x ∥ 2 2 + λ ∥ x ∥ 2 2 ≥ λ ∥ x ∥ 2 2 > 0 ∎
נבצע שינוי לבעיית הריבועים הפחותים שלנו כך שהמשוואה הנורמלית החדשה תהיה:
( A t A + λ I ) x ‾ ∗ = A t b ‾ (A^tA+\lambda I)\underline{x}^*=A^t\underline{b} ( A t A + λ I ) x ∗ = A t b בהתאם, נקבל את המשפט הבא:
לבעיה הריבועית הבאה עם λ > 0 \lambda>0 λ > 0
min x ‾ ( ∥ A x ‾ − b ‾ ∥ 2 2 + λ ∥ x ‾ ∥ 2 2 ) \underset{\underline{x}}{\min}\left(\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2+\lambda \left\lVert \underline{x} \right\rVert _{2}^2\right) x min ( ∥ A x − b ∥ 2 2 + λ ∥ x ∥ 2 2 ) יש פתרון יחיד הנתון ע"י:
x ‾ ∗ = ( A t A + λ I ) − 1 A t b ‾ \underline{x}^*=(A^tA+\lambda I)^{-1}A^t\underline{b} x ∗ = ( A t A + λ I ) − 1 A t b הביטוי שהתווסף הוא הרגולריזציה והוא נקרא כך כי הוא הופך את הבעיה לרגולרית(מיוצבת)הוכחה:
p ( x ) = ∥ A x ‾ − b ‾ ∥ 2 2 + λ ∥ I x ‾ − 0 ‾ ∥ 2 2 p(x)=\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2+\lambda \left\lVert I\underline{x}-\underline{0} \right\rVert _{2}^2 p ( x ) = ∥ A x − b ∥ 2 2 + λ ∥ I x − 0 ∥ 2 2 ∇ x p ( x ) = 2 A t ( A x ‾ − b ‾ ) + 2 λ I t ( I x ‾ − 0 ) = 2 A t ( A x ‾ − b ‾ ) + 2 λ x ‾ = 0 \nabla_{x}p(x)=2A^t(A\underline{x}-\underline{b})+2\lambda I^t(I\underline{x}-0)=2A^t(A\underline{x}-\underline{b})+2\lambda \underline{x}=0 ∇ x p ( x ) = 2 A t ( A x − b ) + 2 λ I t ( I x − 0 ) = 2 A t ( A x − b ) + 2 λ x = 0 נקבל:
( A t A + λ I ) x ‾ = A t b ‾ (A^tA+\lambda I)\underline{x}=A^t\underline{b} ( A t A + λ I ) x = A t b ∎
הרגולריזציה מתעדפת פתרונות קצרים ב-L 2 L_{2} L 2 ארוך .
הכללת הרגולריזציה
ניתן להציע רגולריזציה כללית יותר מהתצורה:
min x ‾ ( ∥ A x ‾ − b ‾ ∥ 2 2 + λ ∥ C x ‾ ∥ 2 2 ) \underset{\underline{x}}{\min}\left(\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2+\lambda \left\lVert C\underline{x} \right\rVert_{2}^2 \right) x min ( ∥ A x − b ∥ 2 2 + λ ∥ C x ∥ 2 2 ) במקרה זה, אם C t C C^tC C t C
p ( x ‾ ) = ∥ A x ‾ − b ‾ ∥ 2 2 + λ ∥ C x ‾ ∥ 2 2 p(\underline{x})=\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2+\lambda \left\lVert C\underline{x} \right\rVert_{2}^2 p ( x ) = ∥ A x − b ∥ 2 2 + λ ∥ C x ∥ 2 2 2 A t ( A x ‾ − b ‾ ) + 2 C t C x ‾ = 0 ⟺ ( A t A + λ C t C ) − 1 ⋅ A t b ‾ = x ‾ 2A^t(A\underline{x}-\underline{b})+2C^tC\underline{x}=0 \iff (A^tA+\lambda C^tC)^{-1}\cdot A^t\underline{b}=\underline{x} 2 A t ( A x − b ) + 2 C t C x = 0 ⟺ ( A t A + λ C t C ) − 1 ⋅ A t b = x
אם בעיית הריבועים הפחותים בעלת אינסוף פתרונות, הרגולריזציה תמיר זאת לבעיה חדשה בעלת פתרון יחיד, אבל הפתרון שייווצר אינו אחד מ-∞ \infty ∞