גליון 2 — אלגוריתמים נומריים

תרגיל 1

לפניכם 4 שאלות אמריקאיות. עליכם לבחור בתשובה הנכונה ולנמק אותה.

תרגיל (1 [א])

נתונה בעית ריבועים פחותים $\underline{x}^*=\arg\underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2$ שבה המטריצה $A$ ידועה והוקטור $\underline{b}$ לא ידוע.

A=\begin{pmatrix} -4 & 1 & 1 & 1 \\ 1 & -4 & 1 & 1 \\ 1 & 1 & -4 & 1 \\ 1 & 1 & 1 & -4 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix} \qquad \qquad \underline{b}=\begin{pmatrix} ? \\ ? \\ ? \\ ? \\ ? \\ ? \\ ? \\ ? \\ ? \\ ? \end{pmatrix}

מי מהוקטורים הבאים עשוי להיות וקטור השארית של הפתרון האופטימלי $\underline{r}^*=A\underline{x}^*-\underline{b}$ ?
א. $\underline{r}^*=\begin{pmatrix}-4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{pmatrix}^t$
ב. $\underline{r}^*=\begin{pmatrix}2 & -8 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2\end{pmatrix}^t$
ג. $\underline{r}^*=\begin{pmatrix}4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & -16\end{pmatrix}^t$
ד. $\underline{r}^*=\begin{pmatrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{pmatrix}^t$
ה. כל הוקטורים הנ"ל מתאימים להיות $\underline{r}^*$ .

תשובה: ג'
הוכחה:
לפי משפט:

\underline{x}^*=A^{\dagger}\underline{b}=(A^tA)^{-1}A^t\underline{b}

לכן מתקיים:

A^tA\underline{x}^*-A^t\underline{b}=0 \implies A^t(A\underline{x}^*-\underline{b})=0 \implies A^t \underline{r}^*=0

כעת נמצא את $\underline{r}^*$ על פי התנאי הנ"ל:

\begin{pmatrix} -4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & -4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & -4 & 1 & 1 & 1 & 1 & 1 & 1 \end{pmatrix}\begin{pmatrix} r_{1} \\ r_{2} \\ \vdots \\ r_{10} \end{pmatrix}=\begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix}

\begin{pmatrix} -4r_{1}+r_{2}+\dots+r_{10} \\ r_{1}-4r_{2}+r_{3}+\dots+r_{10} \\ r_{1}+r_{2}-4r_{3}+r_{4}+\dots+r_{10} \\ r_{1}+r_{2}+r_{3}-4r_{4}+r_{5}+\dots+r_{10} \end{pmatrix}=\begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}\iff \begin{cases} -4r_{1}+r_{2}+\dots+r_{10}=0 \\ r_{1}-4r_{2}+r_{3}+\dots+r_{10}=0 \\ r_{1}+r_{2}-4r_{3}+r_{4}+\dots+r_{10}=0 \\ r_{1}+r_{2}+r_{3}-4r_{4}+r_{5}+\dots+r_{10}=0 \end{cases}

\iff \begin{cases} r_{1}=\frac{r_{2}+\dots+r_{10}}{4} \\ \frac{r_{2}+\dots+r_{10}}{4}-4r_{2}+r_{3}+\dots+r_{10}=0\implies 15r_{2}=5r_{3}+\dots+5r_{10}\implies r_{2}=\frac{r_{3}+\dots+r_{10}}{3} \\ \implies r_{1}=\frac{\frac{r_{3}+\dots+r_{10}}{3}+r_{3}+\dots +r_{10}}{4}=\frac{4r_{3}+\dots+4r_{10}}{12}=\frac{r_{3}+\dots+r_{10}}{3}=r_{2} \\ \frac{2}{3}(r_{3}+\dots+r_{10})-4r_{3}+r_{4}+\dots+r_{10}=0\implies 10r_{3}=5r_{4}+\dots+5r_{10}\implies r_{3}=\frac{r_{4}+\dots+r_{10}}{2} \\ \implies r_{2}=\frac{\frac{r_{4}+\dots+r_{10}}{2}+r_{4}+\dots+r_{10}}{3}=\frac{3r_{4}+\dots+3r_{10}}{6}=\frac{r_{4}+\dots+r_{10}}{2}=r_{3} \\ \implies r_{1}=r_{2}=\frac{r_{4}+\dots+r_{10}}{2}=r_{3} \\ \frac{3}{2}(r_{4}+\dots+r_{10})-4r_{4}+r_{5}+\dots+r_{10}=0\implies 5r_{4}=5r_{5}+\dots+5r_{10}\implies r_{4}=r_{5}+\dots+r_{10} \\ \implies r_{3}=\frac{r_{5}+\dots+r_{10}+r_{5}+\dots+r_{10}}{2}=\frac{2r_{5}+\dots+2r_{10}}{2}=r_{5}+\dots+r_{10}=r_{4} \\ \implies r_{1}=r_{2}=r_{3}=r_{4}=r_{5}+\dots+r_{10} \end{cases}

\iff \underline{r}^*=\begin{pmatrix} r_{5}+\dots+r_{10} \\ r_{5}+\dots+r_{10} \\ r_{5}+\dots+r_{10} \\ r_{5}+\dots+r_{10} \\ r_{5} \\ r_{6} \\ r_{7} \\ r_{8} \\ r_{9} \\ r_{10} \end{pmatrix}

כעת, לאחר שמצאנו את כל התנאים על $\underline{r}^*$ נרצה לראות אילו מהתשובות מתאימה:
התשובה הראשונה מקיימת $1+1+1+1+1+1=6\neq 1 \neq -4$ ולכן היא לא נכונה.
התשובה השנייה מקיימת $2+2+2+2+2+2=12\neq{2} \neq -8$ ולכן היא לא נכונה.
התשובה השלישית מקיימת: $-16+4+4+4+4+4=4$ ולכן היא התשובה הנכונה
∎

תרגיל (1 [ב])

נתונה לנו המטריצה הבאה:

A=\begin{pmatrix} 1 & 0 & 1 \\ 2 & 1 & 0 \\ 1 & 0 & 1 \\ 2 & 1 & 0 \\ 1 & 0 & 1 \\ 2 & 1 & 0 \\ 1 & 0 & 1 \\ 2 & 1 & 0 \end{pmatrix}

ברצוננו למצוא וקטור $\underline{b}$ שעבורו השגיאה של הפתרון האופטימלי לבעיית הריבועים הפחותים תהיה

\underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2=0

והפתרון יהיה יחיד.
מי מהוקטורים הבאים עונה על שתי הדרישות?
א. $\underline{b}=\begin{pmatrix}0 & 1 & 0 & 1 & 1 & 0 & 1 & 0\end{pmatrix}^t$
ב. $\underline{b}=\begin{pmatrix}0 & 0 & 0 & 0 & 1 & 1 & -1 & -1\end{pmatrix}^t$
ג. $\underline{b}=\begin{pmatrix}1 & 0 & -1 & 0 & 1 & 0 & -1 & 0\end{pmatrix}^t$
ד. $\underline{b}=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\end{pmatrix}^t$
ה. לא קיים וקטור $\underline{b}$ שעונה על שתי הדרישות.

תשובה: ה'
הוכחה:
הפתרון יחיד $\iff$ המטריצה $A^tA$ היא סימטרית וחיובית מוגדרת. נבדוק זאת:

\begin{align*} A^tA&=\begin{pmatrix} 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 0 & 1 \\ 2 & 1 & 0 \\ 1 & 0 & 1 \\ 2 & 1 & 0 \\ 1 & 0 & 1 \\ 2 & 1 & 0 \\ 1 & 0 & 1 \\ 2 & 1 & 0 \end{pmatrix} \\ &=\begin{pmatrix} 1+4+1+4+1+4+1+4 & 2+2+2+2 & 1+1+1+1 \\ 2+2+2+2 & 1+1+1+1 & 0 \\ 1+1+1+1 & 0 & 1+1+1+1 \end{pmatrix} \\ &=\begin{pmatrix} 20 & 8 & 4 \\ 8 & 4 & 0 \\ 4 & 0 & 4 \end{pmatrix} \end{align*}

המטריצה סימטרית.
המטריצה תהיה חיובית מוגדרת $\iff$ עמודותיה בת"ל.
נשים לב כי העמודה הראשונה ניתנת להרכבה מהעמודה השנייה והשלישית ולכן הן לא בת"ל.
לכן, המטריצה לא חיובית מוגדרת ולכן לא קיים וקטור $\underline{b}$ שעונה על שתי הדרישות.
∎

תרגיל (1 [ג])

נתונה בעיית ריבועים פחותים כאשר:

A=\begin{pmatrix} -4 & 1 & 1 & 1 \\ 1 & -4 & 1 & 1 \\ 1 & 1 & -4 & 1 \\ 1 & 1 & 1 & -4 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix} \qquad \qquad \underline{b}=\begin{pmatrix} -3 \\ 2 \\ 2 \\ 2 \\ -3 \\ 2 \\ 2 \\ 2 \\ 2 \\ 2 \end{pmatrix}

חשבו את ערך השגיאה המינימלית.
א. $\underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2=0$
ב. $\underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2=25$
ג. $\underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2=9$
ד. $\underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2=16$
ה. $\underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2=36$

תשובה: ב'
הוכחה:
דבר ראשון, ניתן לראות כי עמודות $A$ בת"ל, שכן לפי משפט, אם $A^tA$ הפיכה, העמודות של $A$ בת"ל.

A^tA=\begin{pmatrix} 25 & 0 & 0 & 0 \\ 0 & 25 & 0 & 0 \\ 0 & 0 & 25 & 0 \\ 0 & 0 & 0 & 25 \end{pmatrix}=25I

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

\underline{x}^*=A^{\dagger}\underline{b}

A^tA=25I \implies (A^tA)^{-1}=\frac{1}{25}(I)^{-1}=\frac{1}{25}I

\begin{align*} A^{\dagger}&=\frac{1}{25}\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} -4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & -4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & -4 & 1 & 1 & 1 & 1 & 1 & 1 \end{pmatrix} \end{align*}

\begin{align*} \underline{x}^*&=A^{\dagger}\underline{b}=\frac{1}{25}\begin{pmatrix} -4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & -4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & -4 & 1 & 1 & 1 & 1 & 1 & 1 \end{pmatrix}\begin{pmatrix} -3 \\ 2 \\ 2 \\ 2 \\ -3 \\ 2 \\ 2 \\ 2 \\ 2 \\ 2 \end{pmatrix}=\frac{1}{25}\begin{pmatrix} 12-3+2\cdot 8 \\ -6-8+2\cdot 7 \\ -6-8+2\cdot 7 \\ -6-8+2\cdot 7 \end{pmatrix} \\ &=\frac{1}{25}\begin{pmatrix} 25 \\ 0 \\ 0 \\ 0 \end{pmatrix}=\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{align*}

כעת נוכל לפתור את המשוואה המקורית:

\begin{align*} \underline{r}^*&=A\underline{x}^*-\underline{b}=\begin{pmatrix} -4 & 1 & 1 & 1 \\ 1 & -4 & 1 & 1 \\ 1 & 1 & -4 & 1 \\ 1 & 1 & 1 & -4 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}-\begin{pmatrix} -3 \\ 2 \\ 2 \\ 2 \\ -3 \\ 2 \\ 2 \\ 2 \\ 2 \\ 2 \end{pmatrix}=\begin{pmatrix} -4 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}-\begin{pmatrix} -3 \\ 2 \\ 2 \\ 2 \\ -3 \\ 2 \\ 2 \\ 2 \\ 2 \\ 2 \end{pmatrix} \\ &=\begin{pmatrix} -1 \\ -1 \\ -1 \\ -1 \\ 4 \\ -1 \\ -1 \\ -1 \\ -1 \\ -1 \end{pmatrix} \end{align*}

כעת נוכל למצוא את הפתרון הסופי:

\begin{align*} \left\lVert A\underline{x}^*-\underline{b} \right\rVert _{2}^2&=\left\lVert \underline{r}^* \right\rVert _{2}^2={\underline{r}^*}^t\underline{r}^*=\begin{pmatrix} -1 & -1 & -1 & -1 & 4 & -1 & -1 & -1 & -1 & -1 \end{pmatrix}\begin{pmatrix} -1 \\ -1 \\ -1 \\ -1 \\ 4 \\ -1 \\ -1 \\ -1 \\ -1 \\ -1 \end{pmatrix} \\ &=1+1+1+1+16+1+1+1+1+1=16+4+5=25 \end{align*}

וזוהי בדיוק התשובה :)
∎

תרגיל (1 [ד])

נתונה בעיית ריבועים פחותים.
נתון שקיים וקטור $\underline{c}$ שעבורו למערכת המשוואות הלא הומגונית $A\underline{x}=\underline{c}$ קיים פתרון יחיד.
בנוסף, נתון ש- $\underline{b}$ אינו שייך למרחב הנפרש מעמודות $A$ .
יהי $\underline{x}^*$ פתרון לבעיית הריבועים הפחותים. נסמן את השארית: $\underline{r}^*=A\underline{x}^*-\underline{b}$ ונסמן את השגיאה: $\underline{e}^*=A^t\underline{r}^*$ .
סמנו את הטענה הנכונה:
א. לבעיית הריבועים הפחותים יש פתרון יחיד ובנוסף מתקיים $\underline{e}^* \neq 0,\underline{r}^* \neq 0$ .
ב. לבעיית הריבועים הפחותים יש פתרון יחיד ובנוסף מתקיים $\underline{e}^* = 0,\underline{r}^* \neq 0$ .
ג. לבעיית הריבועים הפחותים יש פתרון יחיד ובנוסף מתקיים $\underline{e}^* = 0,\underline{r}^* = 0$ .
ד. לבעיית הריבועים הפחותים יש $\infty$ פתרונות ובנוסף מתקיים $\underline{e}^*=0,\underline{r}^*=0$ .
ה. לבעיית הריבועים הפחותים יש $\infty$ פתרונות ובנוסף מתקיים $\underline{e}^*=0,\underline{r}^* \neq0$ .

תשובה: ב'
הוכחה:
נתון כי $\underline{b} \not\in colA$ ולכן, לפי משפט, למערכת $A\underline{x}=\underline{b}$ אין פתרון.
קיים וקטור עבורו למערכת יש פתרון יחיד ולכן בהכרח עמודות $A$ בת"ל.
לכן, לבעיית הריבועים הפחותים עם $A$ ו- $\underline{b}$ יהיה פתרון יחיד אך בו, מכיוון שאין פתרון במקור, $\underline{r}^*\neq 0$ .
אם $A^t\underline{r}^*=0$ אזי וקטור השארית מאונך למרחב הפתרונות. לפי הגדרת בעיית הריבועים הפחותים והפתרון, זה תמיד מתקיים ולכן $\underline{e}^*=0$ תמיד.
∎

תרגיל 2

תרגיל (2 [א])

נתונה פונקציה בשני משתנים:

f(x_{1},x_{2})=(x_{1}+30)^2+(x_{1}+x_{2}-20)^2+(x_{1}+2x_{2}-15)^2+(x_{1}+3x_{2})^2+(x_{1}-6x_{2})^2

מצאו את $x_{1},x_{2}$ שמביאים את הפונקציה למינימום באמצעות הנגזרות החלקיות של $f$ .
תזכורת: $\frac{d}{dt}(at-b)^2=2a(at-b)$ שימו לב גם לסימן של $b$ .

נגזור את הפונקציה ונמצא את ערכי ה- $x_{1},x_{2}$ אשר יהוו מינימום:

\begin{align*} \nabla f(x_{1},x_{2})&=\begin{pmatrix} 2(x_{1}+30)+2(x_{1}+x_{2}-20)+2(x_{1}+2x_{2}-15)+2(x_{1}+3x_{2})+2(x_{1}-6x_{2}) \\ 2(x_{2}+x_{1}-20)+4(x_{1}+2x_{2}-15)+6(x_{1}+3x_{2})-12(x_{1}-6x_{2}) \end{pmatrix} \\ &=\begin{pmatrix} 10x_{1}+60-40-30 \\ 100x_{2}-100 \end{pmatrix}=\begin{pmatrix} 0 \\ 0 \end{pmatrix} \\ \implies & \begin{cases} 10x_{1}=10 \implies x_{1}=1 \\ 100x_{2}=100\implies x_{2}=1 \end{cases} \end{align*}

לכן, כדי להביא את הפונקציה למינימום נדרש ל- $\begin{pmatrix}x_{1}\\ x_{2}\end{pmatrix}=\begin{pmatrix}1\\ 1\end{pmatrix}$ .

תרגיל (2 [ב])

נסחו את הבעית הבאת $f$ למינימום כבעיית ריבועים פחותים.
מהם $A,\underline{x},\underline{b}$ ?

נגדיר:

f_{1}=(x_{1}+30), \quad f_{2}=(x_{1}+x_{2}-20), \quad f_{3}=(x_{1}+2x_{2}-15), \quad f_{4}=(x_{1}+3x_{2}), \quad f_{5}=(x_{1}-6x_{2})

אזי מתקיים:

f(x_{1},x_{2})=f^2_{1}+f^2_{2}+f^2_{3}+f^2_{4}+f^2_{5}

לכל $1\leq i\leq 5$ מתקיים $f_{i}^2(x_{1},x_{2})\geq 0$ לכל $x_{1},x_{2} \in \mathbb{R}$ . לכן, כדי להביא את $f$ למינימום נדרש להביא את כל $f_{i}$ כמה שיותר קרוב ל-0 עם אותם $x_{1},x_{2}$ . כלומר, נרצה לבצע $f_{i}=0$ . נעשה זאת באמצעות ריבועים פחותים. נגדיר יצוג וקטורי לכל פונקציה כזו עם בסיס $B=\left\{ x_{1},x_{2},1 \right\}$ כך:

[f_{1}]_{B}=\begin{pmatrix} 1 \\ 0 \\ 30 \end{pmatrix} \quad [f_{2}]_{B}=\begin{pmatrix} 1 \\ 1 \\ -20 \end{pmatrix} \quad [f_{3}]_{B}=\begin{pmatrix} 1 \\ 2 \\ -15 \end{pmatrix} \quad [f_{4}]_{B}=\begin{pmatrix} 1 \\ 3 \\ 0 \end{pmatrix} \quad [f_{5}]_{B}=\begin{pmatrix} 1 \\ -6 \\ 0 \end{pmatrix}

כעת, נציב את וקטורים האלו במטריצה ליצירת מערכת משוואות הומוגנית - שכן אנו רוצים $x_{1},x_{2}$ יחידים לכל הפונקציות הללו.

(A|\underline{\tilde{b}})=\left(\begin{array}{ccc|c} 1 & 0 & 30 & 0 \\ 1 & 1 & -20 & 0\\ 1 & 2 & -15 & 0 \\ 1 & 3 & 0 & 0 \\ 1 & -6 & 0 & 0 \end{array}\right)

נוכל להעביר את המקדמים של $1$ לצד השני ליצירת $\underline{b}$ כך:

(A|\underline{b})=\left(\begin{array}{cc|c} 1 & 0 & -30 \\ 1 & 1 & 20 \\ 1 & 2 & 15 \\ 1 & 3 & 0 \\ 1 & -6 & 0 \end{array}\right)

נגדיר כעת במדוייק:

A=\begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3 \\ 1 & -6 \end{pmatrix} \quad \quad \underline{b}=\begin{pmatrix} -30 \\ 20 \\ 15 \\ 0 \\ 0 \end{pmatrix} \quad \quad \underline{x}=\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}

כעת נוכל להגדיר את בעיית הריבועים הפחותים שלנו:

p(\underline{x}) =\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2=\left\lVert \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3 \\ 1 & -6 \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}-\begin{pmatrix} -30 \\ 20 \\ 15 \\ 0 \\ 0 \end{pmatrix} \right\rVert_{2}^2

תרגיל (2 [ג])

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

נפתור את הבעייה לפי המשוואה הנורמלית כפי שלמדנו בהרצאה.

A^tA=\begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 & -6 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3 \\ 1 & -6 \end{pmatrix}=\begin{pmatrix} 5 & 0 \\ 0 & 50 \end{pmatrix}=5\begin{pmatrix} 1 & 0 \\ 0 & 10 \end{pmatrix}

\left(\begin{array}{cc|cc} 5 & 0 & 1 & 0\\ 0 & 50 & 0 & 1 \end{array}\right)\overrightarrow{\begin{matrix} R_{1}=\frac{1}{5}R_{1} \\ R_{2}=\frac{1}{50}R_{2} \end{matrix}}\left(\begin{array}{cc|cc} 1 & 0 & \frac{1}{5} & 0 \\ 0 & 1 & 0 & \frac{1}{50} \end{array}\right) \implies (A^tA)^{-1}=\begin{pmatrix} \frac{1}{5} & 0 \\ 0 & \frac{1}{50} \end{pmatrix}=\frac{1}{5}\begin{pmatrix} 1 & 0 \\ 0 & \frac{1}{10} \end{pmatrix}

A^{\dagger}=(A^tA)^{-1}A^t=\frac{1}{5}\begin{pmatrix} 1 & 0 \\ 0 & \frac{1}{10} \end{pmatrix}\begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 & -6 \end{pmatrix}=\frac{1}{5}\begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & \frac{1}{10} & \frac{2}{10} & \frac{3}{10} & -\frac{6}{10} \end{pmatrix}

\underline{x}^*=A^{\dagger}\underline{b}=\frac{1}{5}\begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & \frac{1}{10} & \frac{2}{10} & \frac{3}{10} & -\frac{6}{10} \end{pmatrix}\begin{pmatrix} -30 \\ 20 \\ 15 \\ 0 \\ 0 \end{pmatrix}=\frac{1}{5}\begin{pmatrix} -30+20+15 \\ 2+3 \end{pmatrix}=\frac{1}{5}\begin{pmatrix} 5 \\ 5 \end{pmatrix}

\implies \underline{x}^*=\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}=\begin{pmatrix} 1 \\ 1 \end{pmatrix}

הפתרון זהה לפתרון מסעיף א' שזה טוב כי הם אמורים להיות זהים אם יש מינימום :)

תרגיל (2 [ד])

הוכיחו בעזרת $A$ כי קיים מינימום יחיד לבעיה.

הוכחה:
לפי משפט, יש מינימום יחיד $K \iff$ היא מטריצה סימטרית וחיובית מוגדרת אשר מוגדרת להיות $K=A^tA$ .
נשים לב כי בסעיף קודם קיבלנו:

K=A^tA=\begin{pmatrix} 5 & 0 \\ 0 & 50 \end{pmatrix}

המטריצה הזו היא בהחלט סימטרית וכעת נבדוק אם היא חיובית מוגדרת לפי הגדרה:
יהי $\underline{x} \neq 0$ . אזי:

\begin{align*} \underline{x}^tK\underline{x}&= \begin{pmatrix} x_{1} & x_{2} \end{pmatrix}\begin{pmatrix} 5 & 0 \\ 0 & 50 \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}=\begin{pmatrix} 5x_{1} & 50x_{2} \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}=5x_{1}^2+50x_{2}^2 \geq 0 \end{align*}

נניח בשלילה כי $\underline{x}^tK\underline{x}=0$ אזי $5x_{1}^2+50x_{2}^2=0$ ולכן, $5x_{1}^2=0 \land 50x_{2}^2=0$ ולכן: $x_{1}=0 \land x_{2}=0$ ובכך $\underline{x}=0$ .
לכן, $K \succ 0$ ולכן, לפי המשפט, יש מינימום יחיד לבעיית הריבועים הפחותים בתרגיל.
∎

תרגיל (2 [ה])

האם שינוי $\underline{b}$ היה משנה את יחידות הפתרון? נמקו

המשפט הנ"ל שנלמד בהרצאה מציב תנאי יחיד על $A$ על מנת שיהיה פתרון יחיד.
אם $A^tA$ סימטרית וחיובית מוגדרת אזי יש פתרון יחיד לבעיה.
לכן, לא משנה מה $\underline{b}$ עדיין יהיה פתרון יחיד לבעיית הריבועים הפחותים הנ"ל.

תרגיל 3

תרגיל (3 [א])

נתונות 2 בעיות מינימיזציה ריבועיות עם מטריצות $A,C \in \mathbb{R}^{m\times n}$ ומטריצה אלכסונית בעלת איברים אי שליליים $W \in \mathbb{R}^{m\times m}$ ווקטורים $\underline{b}, \underline{d} \in \mathbb{R}^{m}$ וסקלר $\lambda >0$ .
בעיה א': $\underset{\underline{x} \in \mathbb{R}^n}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2$
בעיה ב': $\underset{\underline{x} \in\mathbb{R}^n}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2+\lambda \left\lVert C\underline{x}-\underline{d} \right\rVert_{W}^2$ . שימו לב ל- $W$ ו- $\lambda$ !

מהי קבוצת הפתרונות של בעיה א'?
מצאו קבוצה שניתן להציג בצורה $\left\{ \underline{x} \in \mathbb{R}^n | K\underline{x}=\underline{f} \right\}$ שוקטור $\underline{x}$ שייך אליה $\iff$ הצבתו בביטוי מבעיה א' נותנת ערך מינימלי לביטוי.

קבוצת הפתרונות של בעיה א' הינה לפי משפט קבוצת הפתרונות של המשוואה הנורמלית:

A^tA\underline{x}=A^t\underline{b}

נסמן $K=A^tA$ ו- $\underline{f}=A^t\underline{b}$ ואז:

K\underline{x}=\underline{f}

תרגיל (3 [ב])

מהי קבוצת הפתרונות של בעיה ב'?
הדרכה: ניתן לגזור את הביטוי בבעיה ב' ולהשוות אותו ל- $0$ . לשם כך ניתן למצוא $K,\underline{f}$ מתאימים (שונים מאלו של הסעיף הקודם) שבאמצעותם ניתן לבטא את הביטוי בבעיה ב' בצורה $\underline{x}^tK\underline{x}-2\underline{x}^t\underline{f}+c$ .

נגדיר:

\begin{align*} p(\underline{x})&=\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2+\lambda \left\lVert C\underline{x}-\underline{d} \right\rVert _{W}^2=(A\underline{x}-\underline{b})^t(A\underline{x}-\underline{b})+\lambda(C\underline{x}-\underline{d})^tW(C\underline{x}-\underline{d}) \\ &=(\underline{x}^tA^t-\underline{b}^t)(A\underline{x}-\underline{b})+\lambda(\underline{x}^tC^t-\underline{d}^t)W(C\underline{x}-\underline{d}) \\ &=\underline{x}^tA^tA\underline{x}-\underline{x}^tA^t\underline{b}-\underline{b}^tA\underline{x}+\underline{b}^t\underline{b}+\lambda(\underline{x}^tC^tWC\underline{x}-\underline{x}^tC^tW\underline{d}-\underline{d}^tWC\underline{x}+\underline{d}^tW\underline{d}) \end{align*}

נשים לב כי $\underline{x}^tA^t\underline{b}$ הוא סקלר שזהה ל- $\underline{b}^tA\underline{x}$ שכן שחלוף סקלר שווה לעצמו. בהתאמה, $\underline{x}^tC^tW\underline{d}=\underline{d}^tWC\underline{x}$ ולכן:

\begin{align*} p(\underline{x})&=\underline{x}^tA^tA\underline{x}-2\underline{x}^tA^t\underline{b}+\underline{b}^t\underline{b}+\lambda \underline{x}^tC^tWC\underline{x}-2\lambda\underline{x}^tC^tW\underline{d}+\lambda\underline{d}^tW\underline{d} \\ &=\underline{x}^t(A^tA+\lambda C^tWC)\underline{x}-2\underline{x}^t(A^t\underline{b}+\lambda C^tW\underline{d})+\underline{b}^t\underline{b}+\lambda\underline{d}^tW\underline{d} \end{align*}

כעת נגדיר:

K=A^tA+\lambda C^tWC, \quad \underline{f}=A^t\underline{b}+\lambda C^tW\underline{d}, \quad c=\underline{b}^t\underline{b}+\lambda\underline{d}^tW\underline{d}

קיבלנו: $p(\underline{x})=\underline{x}^tK\underline{x}-2\underline{x}^t\underline{f}+c$ . נגזור את $p(x)$ כעת למציאת המינמום:

\nabla_{\underline{x}} p(\underline{x})= 2K\underline{x}-2\underline{f}

נשווה לאפס ונקבל:

2K\underline{x}=2\underline{f} \implies K\underline{x}=\underline{f}

לכן, קבוצת הפתרונות של בעיה ב' הינה:

\left\{ \begin{array}{c|c} \underline{x} & (A^tA+\lambda C^tWC)\underline{x}=(A^t\underline{b}+\lambda C^tW\underline{d}) \end{array} \right\}

תרגיל (3 [ג])

מהו התנאי ההכרחי והמספיק ליחידות הפתרון לבעיה א'?

לפי משפט, לבעית ריבועים פחותים $\underset{\underline{x}}{\min}\left\lVert M\underline{x}-\underline{v} \right\rVert_{2}^2$ יש פתרון יחיד $\iff$ המטריצה $K'=M^tM$ הינה חיובית מוגדרת.
לפי משפט אחר, המטריצה $K'$ חיובית מוגדרת $\iff$ עמודות המטריצה $M$ בת"ל.

במקרה של בעיה א', נדרוש שעמודות $A$ יהיו בת"ל וזה יהיה התנאי ההכרחי והמספיק ליחידות הפתרון.

תרגיל (3 [ד])

מהו התנאי ההכרחי והמספיק ליחידות הפתרון לבעיה ב'?

לפי מה שראינו בסעיף הנ"ל, נדרוש גם פה כי המטריצה $K$ תהיה חיובית מוגדרת ונבדוק האם נוכל לפתח את התנאי על המטריצות שמרכיבות את $K$ .

K=A^tA+\lambda C^tWC

נתון כי $\lambda>0$ ובנוסף כי $W$ הינה אלכסונית בעלת איברים אי-שליליים ולכן אם נקח כל איבר באלכסון $W$ ונהפוך אותו לשורש של עצמו נקבל מטריצה חדשה אותה נסמן $W^{\frac{1}{2}}$ המקיימת $W=W^{\frac{1}{2}}W^{\frac{1}{2}}$ ובנוסף, מכיוון שגם $W^{\frac{1}{2}}$ אלכסונית היא מקיימת $W^{\frac{1}{2}}=(W^{\frac{1}{2}})^t$ .
לכן:

K\!=\!\!A^tA\!+\!\!\left( \sqrt{ \lambda }C^tW^{\frac{1}{2}} \right)\!\!\left( \sqrt{ \lambda }W^{\frac{1}{2}}C \right)\!=\!A^tA+\!\!\left( \sqrt{ \lambda }W^{\frac{1}{2}}C \right)^t\!\!\left( \sqrt{ \lambda }W^{\frac{1}{2}}C \right)\!\!=\!\!\begin{pmatrix} A^t & \left( \sqrt{ \lambda }W^{\frac{1}{2}}C \right)^t \end{pmatrix}\!\!\begin{pmatrix} A \\ \sqrt{ \lambda }W^{\frac{1}{2}}C \end{pmatrix}

נסמן: $M=\begin{pmatrix}A\\ \sqrt{ \lambda }W^{\frac{1}{2}}C\end{pmatrix}$ ואז: $K=M^tM$ .
לכן, נוכל לדרוש כי עמודות $M$ יהיו בת"ל. כלומר, לכל סט סקלרים $x_{1},\dots,x_{m}\in \mathbb{R}$ אשר נסמנם יחדיו $\underline{x}=\begin{pmatrix}x_{1}\\ x_{2} \\ \vdots \\ x_{m}\end{pmatrix}$ מקיים:

M\underline{x}=0

(שזהו בדיוק הכפלת עמודות $M$ בכל סקלר ואז סכימתם יחדיו בדיוק כמו בהגדרת צ"ל ובת"ל)
נוכל לחלק זאת למטריצות שהרכיבו את $M$ כך:

M\underline{x}=\begin{pmatrix} A \\ \sqrt{ \lambda }W^{\frac{1}{2}}C \end{pmatrix}\underline{x}=\begin{pmatrix} A\underline{x} \\ \sqrt{ \lambda }W^{\frac{1}{2}}C\underline{x} \end{pmatrix}=\begin{pmatrix} 0 \\ 0 \end{pmatrix}

לכן מתקיים:

\begin{cases} A\underline{x}=0 \iff \underline{x} \in null A \\ \sqrt{ \lambda }W^{\frac{1}{2}}C\underline{x}=0 \iff \underline{x} \in null(\sqrt{ \lambda }W^{\frac{1}{2}}C)\iff \underline{x} \in null(W^{\frac{1}{2}}C) \end{cases}

אם עמודות $M$ בת"ל אז מתקיים כי $\underline{x}$ היחיד המקיים את הדרישות הללו הינו וקטור האפס ולכן:
לבעיית הריבועים הפחותים ב' יש רק פתרון אחד $\iff$ מתקיים:

null A \cap null(W^{\frac{1}{2}}C) =\left\{ 0 \right\}

תרגיל (3 [ה])

מהי קבוצת החיתוך של הקבוצות שמצאתם בסעיפים $1-2$ ?
מצאו מטריצה $K$ ווקטור $\underline{f}$ מתאימים שבאמצעותם ניתן להציג את קבוצת החיתוך בצורה $\left\{ \underline{x} \in \mathbb{R}^n | K\underline{x}=\underline{f} \right\}$ .

הדרכה: כאשר מחפשים וקטור $\underline{x}$ שמקיים 2 מעכרות משוואות ליניאריות בו זמנית, ניתן לאחד אותן למערכת משוואות ליניארית אחת גדולה.
כדאי לפשט את מערכת המשוואות ע"י פעולות שורה בסיסיות, כדי לקבל תשובות פשוטות יותר לסעיפים הבאים.

בעצם נרצה למצוא את קבוצת הוקטורים המקיימת:

A^tA\underline{x}=A^t\underline{b}\;\; {\large \land}\;\; (A^tA+\lambda C^tWC)\underline{x}=(A^t\underline{b}+\lambda C^tW\underline{d})

מכיוון שזה מתקיים לאותו הוקטור נאחד את שתי המשוואות הללו לוקטורים:

\begin{pmatrix} A^tA \\ A^tA+\lambda C^tWC \end{pmatrix}\underline{x}=\begin{pmatrix} A^t\underline{b} \\ A^t\underline{b}+\lambda C^tW\underline{d} \end{pmatrix}

נשתמש בפעולת שורה על שני האגפים של: $R_{2}=R_{2}-R_{1}$ ואז נקבל:

\begin{pmatrix} A^tA \\ \lambda C^tWC \end{pmatrix}\underline{x}=\begin{pmatrix} A^t\underline{b} \\ \lambda C^tW\underline{d} \end{pmatrix}

נשתמש כעת בעוד פעולת שורה בדמות $R_{2}=\frac{1}{\lambda}R_{2}$ . אנו יכולים לעשות זאת כי $\lambda>0$ ובפרט $\lambda \neq 0$ .

\begin{pmatrix} A^tA \\ C^tWC \end{pmatrix}\underline{x}=\begin{pmatrix} A^t\underline{b} \\ C^tW\underline{d} \end{pmatrix}

נגדיר:

K=\begin{pmatrix} A^tA \\ C^tWC \end{pmatrix} \qquad \qquad \underline{f}=\begin{pmatrix} A^t\underline{b} \\ C^tW\underline{d} \end{pmatrix}

קבוצת החיתוך של הקבוצות מסעיף 1 ו-2 הינה:

\left\{ \begin{array}{c|c} \underline{x} & \begin{pmatrix} A^tA \\ C^tWC \end{pmatrix}\underline{x}=\begin{pmatrix} A^t\underline{b} \\ C^tW\underline{d} \end{pmatrix} \end{array} \right\}=\left\{ \underline{x} | K\underline{x}=\underline{f} \right\}

תרגיל (3 [ו])

מהו התנאי ההכרחי והמספיק לכך שקבוצת החיתוך תכיל וקטור אחד לפחות?

נשים לב כי קיבלנו בסעיף קודם מערכת משוואות שכל $\underline{x}$ שפותר אותה נמצא בקבוצת החיתוך. לכן, על מנת שקבוצת החיתוך תכיל וקטור אחד לפחות, נדרש שיהיה וקטור אחד לפחות שפותר את מערכת המשוואות הנ"ל.
לכן, לפי משפט מאלגברה אמ, על מנת שיהיה פתרון למערכת משוואות $A\underline{x}=\underline{b}$ נדרש כי $\underline{b} \in colA$ .
נדרוש את תנאי זה אצלנו:

\begin{pmatrix} A^t\underline{b} \\ C^tW\underline{d} \end{pmatrix} \in col\begin{pmatrix} A^tA \\ C^tWC \end{pmatrix}

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

תרגיל (3 [ז])

מהו התנאי ההכרחי והמספיק לכך שקבוצת החיתוך תכיל וקטור אחד לכל היותר?
הדרכה: נסחו תנאי על מטריצת הבלוקים $\begin{pmatrix}K \\ M\end{pmatrix}$ שמצאתם בסעיף 5.

על מנת שקבוצת החיתוך תכיל וקטור אחד לכל היותר וקטור אחד נדרש כי עמודותיה של המטריצה $V=\begin{pmatrix}A^tA\\ C^tWC\end{pmatrix}$ יהיו בת"ל ולכן, למערכת ההומוגנית יהיה בדיוק פתרון אחד והוא הטריויאלי(לפי הגדרת צ"ל ובת"ל).
לפי משפט, קבוצת הפתרונות של המערכת הלא הומוגנית יהיה הפתרון הכללי של ההומוגנית + הפתרון הפרטי של האי הומוגנית. מכיוון שהפתרון הכללי של ההומוגנית הוא 0, הפתרון הפרטי הוא היחיד שמשנה. אם קיים כזה, אזי יהיה פתרון אחד למערכת המשוואות. אם לא קיים פתרון כזה, אז יהיו אפס פתרונות למערכת המשוואות.
לכן, במצב בו עמודות $V$ בת"ל בקבוצת החיתוך יהיה מקסימום וקטור אחד.

שאלה 4

תרגיל (4 [הקדמה])

עבור מטריצה $A$ בעלת עמודות בת"ל, הגדרנו בשיעור את מטריצת ההטלה $P_{A}=A(A^tA)^{-1}A^t$ . זו המטריצה שעבורה ההיטל של וקטור כלשהו $\underline{b}$ על מרחב העמודות $A$ הוא $P_{A}\underline{b}$ .
שימו לב ש- $A^{-1}$ לא בהכרח מוגדרת.
הוכיחו את הטענות הבאות:

תרגיל (4 [א])

המטריצה $A$ אינוואריאנטית תחת כפל משמאל במטריצת ההטלה שלה, כלומר, $P_{A}A=A$ .

הוכחה:
נשים לב כי $A^tA$ הפיכה לא משנה מה $A$ ולכן $(A^tA)^{-1}(A^tA)=I$ ולכן:

P_{A}A=A(A^tA)^{-1}(A^tA)=A\cdot I=A

∎

תרגיל (4 [ב])

מטריצת ההטלה אידמפוטנטית, כלומר $P_{A}P_{A}=P_{A}$ .

הוכחה:

P_{A}P_{A}=P_{A} A(A^tA)^{-1}A^t =(P_{A}A)(A^tA)^{-1}A^t \underset{\begin{matrix} \downarrow \\ \R{\text{סעיף קודם}} \end{matrix}}{=}A(A^tA)^{-1}A^t=P_{A}

∎

תרגיל (4 [ג])

מטריצת ההטלה סימטרית.

הוכחה:

P_{A}^t=(A(A^tA)^{-1}A^t)^{t}=(A^t)^t((A^tA)^{-1})^{t}A^t=A((A^tA)^t)^{-1}A^t=A(A^tA)^{-1}A^t=P_{A}

לכן, לפי הגדרה, מטריצת ההטלה סימטרית.
∎

תרגיל (4 [ד])

מטריצת ההטלה חיובית חצי מוגדרת.

הוכחה:
יהי $\underline{x} \neq0$ . אזי:

\begin{align*} \underline{x}^tP_{A}\underline{x}&= \underline{x}^tP_{A}P_{A}\underline{x}=\underline{x}^tP_{A}^tP_{A}\underline{x} \underset{\begin{matrix} \downarrow \\ \underline{y}=P_{A}\underline{x} \end{matrix}}{=}\underline{y}^t\underline{y}=\sum_{i=1}^n y_{i}^2 \geq 0 \end{align*}

לכן, לפי הגדרה, מטריצת ההטלה חיובית חצי מוגדרת.
∎

תרגיל (4 [ה])

אם $A$ לא ריבועית, אז מטריצת ההטלה (סינגולרית, כלומר) לא הפיכה.

הוכחה:
מסעיף ב', אנו יודעים כי $P_{A}P_{A}=P_{A}$ . נניח בשלילה ש- $P_{A}$ הפיכה ונכפיל משמאל ב- $P_{A}^{-1}$ ואז:

I\cdot P_{A}=I \implies P_{A}=I \iff A(A^tA)^{-1}A^t=I \iff A((A^tA)^{-1}A^t)=I

לכן, המטריצה $A$ הפיכה בסתירה לכך ש- $A$ לא ריבועית ולכן לא יכולה להיות הפיכה.
לכן, $P_{A}$ אינה הפיכה במידה ו- $A$ אינה ריבועית.
∎

תרגיל (4 [ו])

אם $A$ ריבועית, אז מטריצת ההטלה הפיכה.

הוכחה:
נתון כי $A$ ריבועית. נניח בה"כ כי $A$ בגודל $n \times n$ . נתון כי עמודות $A$ בת"ל ולכן, $\dim colA=n$ . לכן, לפי משפט $r(A)=n$ ולכן, לפי משפט, המטריצה A הפיכה ובנוסף, גם $A^t$ הפיכה.
לכן:

\underline{x}^tP_{A}\underline{x}=\underline{x}^tA(A^tA)^{-1}A^t\underline{x} = \underline{x}^tAA^{-1}(A^t)^{-1}A^t\underline{x} =\underline{x}^t\underline{x}=\left\lVert \underline{x} \right\rVert _{2}^2 \geq0

הנורמה שווה לאפס אך ורק כאשר $\underline{x}=0$ ולכן, לפי הגדרה, $P_{A}\succ 0$ .
בנוסף, המטריצה $P_{A}$ ריבועית, סימטרית(סעיף ג') וחיובית חצי מוגדרת(סעיף ד'). לכן, לפי משפט, $P_{A}$ הפיכה.
∎

תרגיל (4 [ז])

נגדיר את המטריצה $H_{A}=I-P_{A}$ זו מטריצת ההטלה על מרחב הוקטורים הניצבים לעמודות $A$ .
הוכיחו כי $H_{A}$ היא סימטרית ואידמפוטנטית.

הוכחה:

H_{A}^t=(I-P_{A})^t=I-P_{A}^t=I-P_{A}=H_{A}

לכן, המטריצה $H_{A}$ סימטרית.

H_{A}H_{A}=(I-P_{A})(I-P_{A})=I^2-P_{A}-P_{A}+P_{A}^2=I-2P_{A}+P_{A}=I-P_{A}=H_{A}

ולכן המטריצה $H_{A}$ גם אידמפוטנטית.
∎

תרגיל (4 [ח])

הוכיחו כי $A^tH_{A}=0$ .

הוכחה:

A^tH_{A}=A^t(I-P_{A})=A^t-A^tP_{A}=A^t-A^tA(A^tA)^{-1}A^t=A^t-I\cdot A^t=0

∎

תרגיל (4 [ט])

נתון פתרון לבעית ריבועים פחותים $\underline{x}=arg \underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2$ .
בטאו את וקטור השגיאה $\underline{r}^*=A\underline{x}^*-\underline{b}$ באמצעות $H_{A},\underline{b}$ .

לפי המשוואה הנורמלית נקבל כי:

\underline{x}^*=A^{\dagger}\underline{b}=(A^tA)^{-1}A^t\underline{b}

נציב בוקטור השארית ונקבל:

\underline{r}^*=A(A^tA)^{-1}A^t\underline{b}-\underline{b}=P_{A}\underline{b}-\underline{b}=(P_{A}-I)\underline{b}=H_{A}\underline{b}

תרגיל (4 [י])

הוכיחו כי $H_{A}P_{A}=0$ .

הוכחה:

H_{A}P_{A}=(I-P_{A})P_{A}=P_{A}-P_{A}^2=P_{A}-P_{A}=0

∎

תרגיל 5

תרגיל (5 [הקדמה])

בבעיה זו יש לנו $m$ דגימות מהצורה $\left\{ (x_{k},y_{k}) \right\}_{k=1}^m$ כאשר $x_{k}$ זו הנקודה בה התרחשה הדגימה ו- $y_{k}$ זה הערך שנדגם.
כעת, נרצה להתאים פולינום ממעלה $n-1$ שיהיה כמה שיותר קרוב לדגימות שקיבלנו. שימו לב שאם הדגימות באמת התקבלו מפולינום כלשהו, אז אם נגלה אותו נדע גם מה תהיה הדגימה ב- $x$ אחר שלא התקבל בדגימות.

ניתן לנסח את הבעיה בצורה הבאה:
קיבלנו את $m$ הדגימות $\left\{ (x_{k},y_{k}) \right\}_{k=1}^m$ כך ש- $x_{1}<x_{2}<\dots<x_{m}$ .
נרצה למצוא פולינום $p(x)$ ממעה לכל היותר $n-1$ (אם קיים) המקיים כי:

p(x)=arg \underset{q(x) \in \mathbb{R}_{n-1}[x]}{\min} \left( \sum_{k=1}^m |q(x_{k})-y_{k}|^2 \right)

כעכשיו שאנו מבינים את הבעיה, בואו נפתור אותה.

תרגיל (5 [א])

יהיו $x_{1},x_{2},\dots,x_{m}\in \mathbb{R}$ ויהי $n \in \mathbb{N}$ ונגדיר את המטריצה:

V_{n}(x_{1},x_{2},\dots,x_{m})=\begin{pmatrix} 1 & x_{1} & x_{1}^2 & \cdots & x_{1}^{n-1} \\ 1 & x_{2} & x_{2}^2 & \cdots & x_{2}^{n-1} \\ 1 & x_{3} & x_{3}^2 & \cdots & x_{3}^{n-1} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_{m} & x_{m}^2 & \cdots & x_{m}^{n-1} \end{pmatrix}

כאשר $m=n$ והמטריצה נקראת מטריצת ונדרמונד.
נסחו את הבעיה כבעיית $LS$ והוכיחו שקיים פתרון לבעיה שלנו.

נסמן: $\displaystyle f(x)=\sum_{k=1}^m |q(x_{k})-y_{k}|^2$ ואז $p(x)=\arg \min f(x)$ .
נשים לב כי כל מחובר בסכום של $f$ הינו אי שלילי ובריבוע. לכן, כדי להביא את $p$ למינימום נצטרך להקטין כל מחובר עד כמה שאפשר. נוכל להציב זאת במטריצה:

\begin{pmatrix} q(x_{1}) \\ q(x_{2}) \\ \vdots \\ q(x_{m}) \end{pmatrix}=\begin{pmatrix} y_{1} \\ y_{2} \\ \vdots \\ y_{m} \end{pmatrix}

אם נוציא את $x_{k}$ מתוך הפולינום נקבל תבנית של פולינום אליה אנו מכניסים את ה- $x$ -ים שלנו. לכן:

V_{n}(x_{1},x_{2},\dots,x_{m})=\begin{pmatrix} 1 & x_{1} & x_{1}^2 & \dots & x_{1}^{n-1} \\ 1 & x_{2} & x_{2}^2 & \dots & x_{2}^{n-1} \\ 1 & x_{3} & x_{3}^2 & \cdots & x_{3}^{n-1} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_{m} & x_{m}^2 & \cdots & x_{m}^{n-1} \end{pmatrix}=\begin{pmatrix} y_{1} \\ y_{2} \\ \vdots \\ y_{m} \end{pmatrix}=\underline{y}

כעת, נגדיר:

A=V_{n}, \qquad \underline{b}=\underline{y}, \qquad \underline{x}=\begin{pmatrix} c_{1} \\ c_{2} \\ \vdots \\ c_{m} \end{pmatrix}

ואז מתקיים:

p(x)=arg \underset{\underline{c}}{\min}\left\lVert A\underline{c}-\underline{b} \right\rVert _{2}^2

זוהי בעיית הריבועים הפחותים שלנו.
לפי משפט, לבעיית ריבועים פחותים תמיד יש פתרון(או $\infty$ פתרונות) ולכן גם לבעיה זו יש פתרון(או $\infty$ פתרונות).

תרגיל (5 [ב])

הראו כי

|V_{n}(x_{1},x_{2},\dots,x_{n})|=\prod_{1\leq i < j\leq n} (x_{j}-x_{i})

הוכחה:
נמצא את הדרטמיננטה באמצעות אינדוקציה על $n$ .
בסיס: עבור $n=2$ . מתקיים:

V_{2}(x_{1},x_{2})=\begin{pmatrix} 1 & x_{1} \\ 1 & x_{2} \end{pmatrix}

ולכן:

|V_{2}(x_{1},x_{2})|=\begin{vmatrix} 1 & x_{1} \\ 1 & x_{2} \end{vmatrix}=x_{2}-x_{1}

כנדרש.

צעד: נניח כי עבור $n$ מתקיים $|V_{n}(x_{1},x_{2},\dots,x_{n})|=\prod_{1\leq i < j\leq n} (x_{j}-x_{i})$ ונוכיח זאת עבור $n+1$ .

|V_{n+1}(x_{1},\dots,x_{n+1})|=\begin{vmatrix} 1 & x_{1} & x_{1}^2 & \dots & x_{1}^{n} \\ 1 & x_{2} & x_{2}^2 & \dots & x_{2}^{n} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_{n+1} & x_{n+1}^2 & \dots & x_{n+1}^n \end{vmatrix}

נבצע כעת פעולות עמודה אלמנטריות בזה אחר זה אשר יעקבו אחר התבנית: $C_{i}=C_{i}-x_{1}C_{i-1}$ לכל $2\leq i$ כאשר נתחיל מ- $i=n$ ונרד עד $i=2$ .
נקבל לאחר דירוג זה את המטריצה:

\begin{align*} V_{n+1}(x_{1},\dots,x_{n+1})&=\begin{vmatrix} 1 & 0 & 0 & \dots & 0 \\ 1 & x_{2}-x_{1} & x_{2}(x_{2}-x_{1}) & \dots & x_{2}^{n-1}(x_{2}-x_{1}) \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_{n+1}-x_{1} & x_{n+1}(x_{n+1}-x_{1}) & \dots & x_{n+1}^{n-1}(x_{n+1}-x_{1}) \end{vmatrix} \\ &=\begin{vmatrix} 1 & x_{2}-x_{1} & x_{2}(x_{2}-x_{1}) & \dots & x_{2}^{n-1}(x_{2}-x_{1}) \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_{n+1}-x_{1} & x_{n+1}(x_{n+1}-x_{1}) & \dots & x_{n+1}^{n-1}(x_{n+1}-x_{1}) \end{vmatrix} \\ &=(x_{2}-x_{1})(x_{3}-x_{1})\cdots(x_{n+1}-x_{1})\begin{vmatrix} 1 & x_{2} & \dots & x_{2}^{n-1} \\ \vdots & \vdots & & \vdots \\ 1 & x_{n+1} & \dots & x_{n+1}^{n-1} \end{vmatrix} \\ &=(x_{2}-x_{1})(x_{3}-x_{1})\cdots(x_{n+1}-x_{1})|V_{n}(x_{2},\dots,x_{n+1})| \end{align*}

מכיוון ש- $x_{2},\dots,x_{n+1}$ הם $n$ איברים בדיוק, לפי הנחת האינדוקציה מתקיים:

|V_{n+1}(x_{1},\dots,x_{n+1})|=(x_{2}-x_{1})(x_{3}-x_{1})\dots(x_{n+1}-x_{1})\prod_{2\leq i<j<n+1} (x_{j}-x_{i})=\prod_{1\leq i<j\leq n+1}(x_{j}-x_{i})

לכן, לפי ההוכחה באינודקציה, הטענה מתקיימת.
∎

תרגיל (5 [ג])

הוכיחו כי אם $m=n$ אז קיים פולינום יחיד שמביא למינימום את הבעיה שלנו והראו כי המינימום הוא $0$ .

הוכחה:
לפי סעיף קודם, הדטרמיננטה של $V_{n}(x_{1},\dots,x_{n})$ שונה מאפס שכן כל חיסור שונה מאפס( $x_{j}>x_{i}$ ) ו- $\mathbb{R}$ הוא שדה.
לכן, לפי משפט, המטריצה הפיכה ולכן למערכת יש פתרון יחיד.
לפי משפט מתקיים:

\underline{c}^*=A^{-1}\underline{b}

\left\lVert A\underline{c}-\underline{b} \right\rVert _{2}^2=\left\lVert \underline{b}-\underline{b} \right\rVert _{2}^2= \left\lVert \underline{0} \right\rVert _{2}^2=0

∎

תרגיל (5 [ד])

הוכיחו כי אם $n>m$ אז יש $\infty$ פולינומים שמביאים למינימום את הבעיה שלנו.

הוכחה:
כאשר $n>m$ המטריצה $A$ מקבלת דרגה של מקסימום $m$ .
לפי משפט, $r(A^tA)=r(A)\leq m<n$ . אך המטריצה $A^tA$ הינה בגודל $n \times n$ ולכן דרגתה אינה מלאה. לכן היא לא הפיכה ולבעיית הריבועים הפחותים יש $\infty$ פתרונות לפי משפט.
∎