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

תרגיל 1

תרגיל (1 [א])

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

\underset{m\times n}{A} \otimes \underset{p \times q}{B}=\begin{pmatrix} a_{11}B & \dots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{m1}B & \dots & a_{mn}B \end{pmatrix} \in \mathbb{F}^{mp\times nq}

הוכיחו כי פעולת הכפל מקיימת את חוק הפילוג. כלומר: $A \otimes(B+C)=A\otimes B+A\otimes C$ .

הוכחה:
נסמן: $B+C=K$ ואז:

A \otimes (B+C)=A \otimes K=\begin{pmatrix} a_{11}K & \dots & a_{1n}K \\ \vdots & \ddots & \vdots \\ a_{m1}K & \dots & a_{mn}K \end{pmatrix}=\begin{pmatrix} a_{11}(B+C) & \dots & a_{1n}(B+C) \\ \vdots & \ddots & \vdots \\ a_{m1}(B+C) & \dots & a_{mn}(B+C) \end{pmatrix}

=\begin{pmatrix} a_{11}B & \dots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{m1}B & \dots & a_{mn}B \end{pmatrix}+\begin{pmatrix} a_{11}C & \dots & a_{1n}C \\ \vdots & \ddots & \vdots \\ a_{m1}C & \dots & a_{mn}C \end{pmatrix}=A \otimes B + A \otimes C

∎

תרגיל (1 [ב])

הוכיחו ש: $(A \oplus B)^t=A^t \oplus B^t$

הוכחה:

(A \otimes B)^t=\begin{pmatrix} a_{11}B & \dots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{m1}B & \dots & a_{mn}B \end{pmatrix}^{\!\!t}=\begin{pmatrix} (a_{11}B)^t & \dots & (a_{m1}B)^t \\ \vdots & \ddots & \vdots \\ (a_{1n}B)^t & \dots & (a_{mn}B)^t \end{pmatrix}=\begin{pmatrix} B^ta_{11}^t & \dots & B^ta_{m1}^t \\ \vdots & \ddots & \vdots \\ B^ta_{1n}^t & \dots & B^ta_{mn}^t \end{pmatrix}

כל $a_{i,j}$ הוא סקלר ולכן, $a_{ij}^t=a_{ij}$ ובנוסף מתקיים קומוטטיביות לפי משפט ולכן:

=\begin{pmatrix} a_{11}B^t & \dots & a_{m1}B^t \\ \vdots & \ddots & \vdots \\ a_{1n}B^t & \dots & a_{mn}B^t \end{pmatrix}=A^t \otimes B^t

לכן, מתקיים $(A\otimes B)^t=A^t\otimes B^t$ .
∎

תרגיל (1 [ג])

הוכיחו כי $(A \otimes B)(C \otimes D)=AC\otimes BD$ .

הוכחה:

A \otimes B=\begin{pmatrix} a_{11}B & \dots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{m1}B & \dots & a_{mn}B \end{pmatrix} \qquad \qquad C \oplus D=\begin{pmatrix} c_{11}D & \dots & c_{1q}D \\ \vdots & \ddots & \vdots \\ c_{p1}D & \dots & c_{pq}D \end{pmatrix}

נניח כי $p=n$ ואז מתקיים:

(A \otimes B)(C\otimes D)=\begin{pmatrix} a_{11}Bc_{11}D+\dots+a_{1n}Bc_{n1}D & \dots & a_{11}Bc_{n1}D+\dots+a_{1n}Bc_{nq}D \\ \vdots & \ddots & \vdots \\ a_{m1}Bc_{11}D+\dots+a_{mn}Bc_{n1}D & \dots & a_{m1}Bc_{n1}D+\dots+a_{mn}Bc_{nq}D \end{pmatrix}

במטריצות יש קומוטטיביות עם סקלרים ולכן:

\begin{align*} &=\begin{pmatrix} a_{11}c_{11}BD+\dots+a_{1n}c_{n1}BD & \dots & a_{11}c_{n1}BD+\dots+a_{1n}c_{nq}D \\ \vdots & \ddots & \vdots \\ a_{m1}c_{11}BD+\dots+a_{mn}c_{n1}BD & \dots & a_{m1}c_{n{1}}BD+\dots+a_{nm}c_{nq}BD \end{pmatrix} \\ &=\begin{pmatrix} (a_{11}c_{11}+\dots+a_{1n}c_{n1})BD & \dots & (a_{11}c_{n1}+\dots+a_{1n}c_{nq})BD \\ \vdots & \ddots & \vdots \\ (a_{m1}c_{11}+\dots+a_{nm}c_{n1})BD & \dots & (a_{m1}c_{n1}+\dots+a_{nm}c_{nq})BD \end{pmatrix} \\ &=\begin{pmatrix} a_{11}c_{11}+\dots+a_{1n}c_{n1} & \dots & a_{11}c_{n1}+\dots+a_{1n}c_{nq} \\ \vdots & \ddots & \vdots \\ a_{m1}c_{11}+\dots+a_{nm}c_{n1} & \dots & a_{m1}c_{n1}+\dots+a_{nm}c_{nq} \end{pmatrix}\otimes BD \end{align*}

לפי הגדרת כפל מטריצות מתקיים:

(A\otimes B)(C\otimes D)=AC\otimes BD

∎

תרגיל (1 [ד])

נגדיר מטריצה $H_{2^n}$ באופו הבא:

H_{2^{n}}=\frac{1}{\sqrt{ 2 }}\begin{pmatrix} H_{2^{n-1}}\otimes \begin{pmatrix} 1 & 1 \end{pmatrix} \\ I_{2^{n-1}}\otimes \begin{pmatrix} 1 & -1 \end{pmatrix} \end{pmatrix}

כאשר $I_{2^{n-1}}$ היא מטריצת היחידה בגודל $2^{n-1}$ ו- $H_{2}=\frac{1}{\sqrt{ 2 }}\begin{pmatrix}1 & 1\\ 1 & -1\end{pmatrix}$ .
הוכיחו כי $H_{2^n}$ הינה מטריצה אורתונורמלית.

הוכחה:

I_{k}\otimes \begin{pmatrix} 1 & -1 \end{pmatrix}=\begin{pmatrix} 1\begin{pmatrix} 1 & -1 \end{pmatrix} & 0 & \dots & 0 \\ 0 & 1\begin{pmatrix} 1 & -1 \end{pmatrix} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1\begin{pmatrix} 1 & -1 \end{pmatrix} \end{pmatrix}=\begin{pmatrix} 1 & -1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & -1 \end{pmatrix}

למטריצה $I_{k}\otimes \begin{pmatrix}1 & -1\end{pmatrix}$ גודל של $k\times 2k$ .
נוכיח באינדוקציה עבור $n$ .
בסיס: כאשר $n=1$ מתקיים כי $H_{2}=\frac{1}{\sqrt{ 2 }}\begin{pmatrix}1 & 1 \\ 1 & -1\end{pmatrix}$ . נשים לב כי מתקיים:

\left\langle \begin{pmatrix} 1 \\ 1 \end{pmatrix},\begin{pmatrix} 1 \\ -1 \end{pmatrix} \right\rangle=\begin{pmatrix} 1 & 1 \end{pmatrix}\begin{pmatrix} 1 \\ -1 \end{pmatrix}=1-1=0

\left\lVert \frac{1}{\sqrt{ 2 }}\begin{pmatrix} 1 \\ 1 \end{pmatrix} \right\rVert_{2}^2=\frac{1}{2}\begin{pmatrix} 1 & 1 \end{pmatrix}\begin{pmatrix} 1 \\ 1 \end{pmatrix}=\frac{1}{2}\cdot 2=1 \quad \land \quad \left\lVert \frac{1}{\sqrt{ 2 }}\begin{pmatrix} 1 \\ -1 \end{pmatrix} \right\rVert _{2}^2=\frac{1}{2}\begin{pmatrix} 1 & -1 \end{pmatrix}\begin{pmatrix} 1 \\ -1 \end{pmatrix}=\frac{1}{2}\cdot 2=1

לכן, לפי הגדרה, המטריצה $H_{2}$ אורתונורמלית.
צעד: נניח כי $H_{2^{n-1}}$ אורתונורמלית ונוכיח כי $H_{2^n}$ אורתונורמלית.
נסמן $H_{2^{n-1}}=\begin{pmatrix}\vert & \vert & & \vert \\ \underline{h}_{1} & \underline{h}_{2} & \dots & \underline{h}_{n-1} \\ \vert & \vert & & \vert\end{pmatrix}$ . לפי הנחת האינדוקציה, $H_{2^{n-1}}$ היא אורתונורמלית ולכן, לכל $1\leq i \neq j\leq n-1$ מתקיים: $\langle \underline{h}_{i},\underline{h}_{j}\rangle=\underline{h}^t_{i}\underline{h}_{j}=0$ ו- $\langle \underline{h}_{i},\underline{h}_{i}\rangle=\underline{h}_{i}^t\underline{h}_{i}=1$ .
לפי הגדרת המטריצה מתקיים:

H_{2^n}=\frac{1}{\sqrt{ 2 }}\begin{pmatrix} H_{2^{n-1}}\otimes \begin{pmatrix} 1 & 1 \end{pmatrix} \\ I_{2^{n-1}}\otimes \begin{pmatrix} 1 & -1 \end{pmatrix} \end{pmatrix}=\frac{1}{\sqrt{ 2 }}\begin{pmatrix} \vert & \vert & \vert & \vert & & \vert & \vert \\ \underline{h}_{1} & \underline{h}_{1} & \underline{h}_{2} & \underline{h}_{2} & \dots & \underline{h}_{n} & \underline{h}_{n} \\ \vert & \vert & \vert & \vert & & \vert & \vert \\ 1 & -1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & -1 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \dots & 1 & -1 \end{pmatrix}

נסמן כל עמודה במטריצה $\sqrt{ 2 }H_{2^n}$ ב- $\underline{w}_{i}$ .
נפריד למקרים:

כפל בין שני וקטורים זהים:
כל וקטור $\underline{w}_{i}$ $\underline{w}_{i}$ מורכב משני חלקים: $\underline{h}_{i}$ $\underline{h}_{i}$ ווקטור אפסים אשר באחד מהמקומות בו נמצא $1$ $1$ או $-1$ $- 1$ .
$
\langle\underline{w}{i},\underline{w}{i}\rangle=\underline{w}{i}^t\underline{w}{i}=\begin{pmatrix}
- & \underline{h}{i} & - & 0 & \dots & \pm 1 & \dots & 0
  \end{pmatrix}\begin{pmatrix}
  \vert \
  \underline{h}{i} \
  \vert \
  0 \
  \vdots \
  \pm 1 \
  \vdots \
  0
  \end{pmatrix}=1+1=2
  $ואז מתקיים$ \frac{1}{\sqrt{ 2 }}\cdot 2=1$ כנדרש.
כפל בין שני וקטורים שונים:
$
\langle \underline{w}{i},\underline{w}{j}\rangle =\underline{w}{i}^t\underline{w}{j}=\begin{pmatrix}
- & \underline{h}{i} & - & 0 & \dots & \pm 1 & \dots & 0
  \end{pmatrix}\begin{pmatrix}
  \vert \
  \underline{h}{j} \
  \vert \
  0 \
  \vdots \
  \mp1 \
  \vdots \
  0
  \end{pmatrix}
  $
  נפריד למקרים:
1. אם $\pm1$ באותה השורה, אז נקבל כי הוקטורים $\underline{h}_{i},\underline{h}_{j}$ זהים, שכן המצב הזה קורה רק בשכפול העמודות שנותנת המכפלה החדשה. לכן מתקיים:
  $\langle \underline{w}_{i},\underline{w}_{j}\rangle =1 +(-1)\cdot (1)=0$
2. אם $\pm 1$ לא באותה שורה, אזי בהכרח $\underline{h}_{i}\neq \underline{h}_{j}$ שונים. ולכן:
  $\langle \underline{w}_{i},\underline{w}_{j}\rangle = 0 + 0\cdot (-1)+0 \cdot (1)=0$

לכן, עמודות המטריצה הזאת הינן קבוצה אורתוגונלית. כעת נוכיח כי זוהי קבוצה אורתונורמלית.

\left\lVert \underline{w}_{i} \right\rVert_{2}^2=\underline{w}_{i}^t\underline{w}_{i}=1

לכן, המטריצה הינה אורתונורמלית כנדרש.
∎

תרגיל 2

תרגיל (2 [א])

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

A=\begin{pmatrix} 4 & 0 & 2 \\ 4 & 0 & -7 \\ 4 & 5 & 11 \\ 4 & 5 & 2 \end{pmatrix}

בצעו פירוק $Economy\;QR$ למטריצה. הראו את שלבי החישוב וכתבו במפורש את המטריצות $Q,R$ .

נתחיל מהראשון:

r_{11}^2=\left\lVert \underline{w}_{1} \right\rVert _{2}^2=\underline{w}_{1}^t\underline{w}_{1}=\begin{pmatrix} 4 & 4 & 4 & 4 \end{pmatrix}\begin{pmatrix} 4 \\ 4 \\ 4 \\ 4 \end{pmatrix}=16+16+16+16=64

r_{11}=8 \implies \underline{u}_{1}=\frac{1}{8}\begin{pmatrix} 4 \\ 4 \\ 4 \\ 4 \end{pmatrix}=\begin{pmatrix} \frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \end{pmatrix}

כעת, נעבור לשני:

\underline{u}_{1}^t\underline{w}_{2}=r_{21}\underline{u}_{1}^t\underline{u}_{1}+r_{22}\underline{u}_{1}^t\underline{u}_{2}=r_{21} \implies r_{21}=\begin{pmatrix} \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \end{pmatrix}\begin{pmatrix} 0 \\ 0 \\ 5 \\ 5 \end{pmatrix}=\frac{5}{2}+\frac{5}{2}=5

\left\lVert \underline{w}_{2} \right\rVert _{2}^2=\underline{w}_{2}^t\underline{w}_{2}=\begin{pmatrix} 0 & 0 & 5 & 5 \end{pmatrix}\begin{pmatrix} 0 \\ 0 \\ 5 \\ 5 \end{pmatrix}=25+25=50

r_{22}= \sqrt{ \left\lVert \underline{w}_{2} \right\rVert_{2}^2 -r_{21}^2 }= \sqrt{ 50-25 }=5

\underline{u}_{2}=\frac{1}{r_{22}}(\underline{w}_{2}-r_{21}\underline{u}_{1})=\frac{1}{5 }\left(\begin{pmatrix} 0 \\ 0 \\ 5 \\ 5 \end{pmatrix}-5\begin{pmatrix} \frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \end{pmatrix}\right)=\frac{1}{5}\begin{pmatrix} -\frac{5}{2} \\ -\frac{5}{2} \\ \frac{5}{2} \\ \frac{5}{2} \end{pmatrix}=\frac{1}{10}\begin{pmatrix} -5 \\ -5 \\ 5 \\ 5 \end{pmatrix}=\begin{pmatrix} -\frac{1}{2} \\ -\frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \end{pmatrix}

כעת, נעבור לשלישי:

\left\lVert \underline{w}_{3} \right\rVert _{2}^2=\underline{w}_{3}^t\underline{w}_{3}=\begin{pmatrix} 2 & -7 & 11 & 2 \end{pmatrix}\begin{pmatrix} 2 \\ -7 \\ 11 \\ 2 \end{pmatrix}=4+49+121+4=178

r_{31}=\underline{u}_{1}^t\underline{w}_{3}=\begin{pmatrix} \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \end{pmatrix}\begin{pmatrix} 2 \\ -7 \\ 11 \\ 2 \end{pmatrix}=1-\frac{7}{2}+\frac{11}{2}+1=4

r_{32}=\underline{u}_{2}^t\underline{w}_{3}=\begin{pmatrix} -\frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \end{pmatrix}\begin{pmatrix} 2 \\ -7 \\ 11 \\ 2 \end{pmatrix}=-1+\frac{7}{2}+5.5+1=9

r_{33}= \sqrt{ \left\lVert \underline{w}_{3} \right\rVert_{2}^2-\sum_{j=1}^{2} r_{3j}^2 }=\sqrt{ 178-(16+81) }=\sqrt{ 178-97 }=\sqrt{ 81 }=9

\underline{u}_{3}=\frac{1}{r_{33}}(\underline{w}_{3}-r_{31}\underline{u}_{1}-r_{32}\underline{u}_{2})=\frac{1}{r_{33}}\left(\begin{pmatrix} 2 \\ -7 \\ 11 \\ 2 \end{pmatrix}-4\begin{pmatrix} \frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \end{pmatrix}-9\begin{pmatrix} -\frac{1}{2} \\ -\frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \end{pmatrix}\right)=\frac{1}{9}\begin{pmatrix} 4.5 \\ -4.5 \\ 4.5 \\ -4.5 \end{pmatrix}=\begin{pmatrix} \frac{1}{2} \\ -\frac{1}{2} \\ \frac{1}{2} \\ -\frac{1}{2} \end{pmatrix}

לכן מתקבלות המטריצות:

A=QR=\begin{pmatrix} \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{pmatrix}\begin{pmatrix} 8 & 5 & 4 \\ 0 & 5 & 9 \\ 0 & 0 & 9 \end{pmatrix}

כלומר:

Q=\begin{pmatrix} \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{pmatrix} \qquad \qquad \qquad R=\begin{pmatrix} 8 & 5 & 4 \\ 0 & 5 & 9 \\ 0 & 0 & 9 \end{pmatrix}

תרגיל (2 [ב])

הראו בעזרת פירוק $QR$ שלא קיים פתרון למערכת המשוואות $A\underline{x}=\underline{b}$ עבור המטריצה $A$ והווקטור $\underline{b}=\begin{pmatrix}-2 & -1 & -2 & 1\end{pmatrix}^t$ .

A\underline{x}=QR\underline{x}=\underline{b} \underset{\begin{matrix} \downarrow \\ \R{\text{תכונות מטריצה}} \\ \R{\text{אורתונורמלית}} \end{matrix}}{\implies} R\underline{x}=Q^t\underline{b}=\begin{pmatrix} \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ -\frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{pmatrix}\begin{pmatrix} -2 \\ -1 \\ -2 \\ 1 \end{pmatrix}=\begin{pmatrix} -2 \\ 1 \\ -2 \end{pmatrix}

\underline{b}=QQ^t\underline{b}=Q\begin{pmatrix} -2 \\ 1 \\ -2 \end{pmatrix}=\begin{pmatrix} \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{pmatrix}\begin{pmatrix} -2 \\ 1 \\ -2 \end{pmatrix}=\begin{pmatrix} -1-0.5-1 \\ -1-0.5+1 \\ -1+0.5-1 \\ -1+0.5+1 \end{pmatrix}

\underline{b}=\begin{pmatrix} -2.5 \\ -0.5 \\ -1.5 \\ 0.5 \end{pmatrix}

נשים לב כי הוקטור $\underline{b}$ שקיבלנו לא זהה לוקטור $\underline{b}$ המקורי ולכן:

A\underline{x}=QR\underline{x}=Q(Q^t\underline{b})=\underline{b}

לכן, קיים פתרון אם ורק אם $Q(Q^t\underline{b})=\underline{b}$ ומכיוון שזה לא מתקיים כאן אזי אין פתרון.

תרגיל (2 [ג])

מהו הווקטור $\underline{b}_{1}$ הקרוב ביותר ל- $\underline{b}$ (בנורמת $L_{2}$ ) שיאפשר פתרון למערכת הנ"ל? פרטו.

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

ההטלה של $\underline{b}$ על $colA$ הינה הכפלה במטריצת ההטלה, כלומר, $QQ^t\underline{b}$ . לכן, לפי סעיף קודם:

\underline{b}_{1}=\begin{pmatrix} -2.5 \\ -0.5 \\ -1.5 \\ 0.5 \end{pmatrix}

תרגיל (2 [ד])

ברצונינו לפתור את הבעיה מסעיף ג' עבור המטריצה $A$ ללא עמודתה השלישית.
תארו את דרך הפתרון היעילה ביותר בהינתן שיש בידינו את הפירוק מסעיף א'.

נשים לב כי אלגוריתם גרם-שמידט הוא איטרטיבי ולכן, אם נקח את $Q$ ונוציא ממנה את העמודה האחרונה נקבל בדיוק את המטריצה האורתונורמלית החדשה שמגדירה לנו את תת המרחב $col A$ החדש - נסמנה $\tilde{Q}$ .
לכן, נוכל באותה הדרך מסעיף קודם לקבל $\underline{b}_{1}=\tilde{Q}(\tilde{Q}^t\underline{b})$ .

תרגיל 3

תרגיל (3 [א])

שאלה זו עוסקת ביציבות הנומרית של שיטות גרם-שמידט.
נניח כי נתונה קבות וקטורים בת"ל $\left\{ \underline{w}_{1},\underline{w}_{2},\dots,\underline{w}_{n} \right\}$ וברצונינו לייצר קבוצה אורתונורמלית חלופית $\left\{ \underline{u}_{1},\underline{u}_{2},\dots,\underline{u}_{n} \right\}$ הפורשת את אותו ת"מ באמצעות אלגוריתם גרם-שמידט.

פתחו את הביטויים עבור $\underline{u}_{1},\underline{u}_{2}$ בשיטת גרם-שמידט הקלסית ובשיטה היציבה והראו שמתקבלים ביטויים זהים.

נתחיל מגרם שמידט הרגיל:

\underline{u}_{1}=\frac{1}{\left\lVert \underline{w}_{1} \right\rVert _{2}} \underline{w}_{1}

עבור $\underline{w}_{2}$ נרצה להשיג אורתונורמליות ל- $\underline{u}_{1}$ ובנוסף שהוא עצמו יהיה בעל אורך של 1. לכן:

\underline{u}_{2}^*=\underline{w}_{2}-c\underline{u}_{1}. \qquad \underline{u}_{1}^t(\underline{w}_{2}-c\underline{u}_{1})=0\implies c=\underline{u}_{1}^t \underline{w}_{2}

\underline{u}_{2}=\frac{1}{\left\lVert \underline{u}_{2}^* \right\rVert_{2} }\underline{u}_{2}^*=\frac{\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1}}{\sqrt{ (\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1})^t(\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1}) }}

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

\underline{u}_{1}=\frac{1}{\left\lVert \underline{w}_{1} \right\rVert _{2}} \underline{w}_{1}

כעת, נקלף את $\underline{u}_{1}$ משאר הוקטורים ונקבל:

\underline{w}_{2}^*=\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1}

כעת, נבצע את הנרמול:

\underline{u}_{2}=\frac{1}{\left\lVert \underline{w}_{2}^* \right\rVert_{2} }\underline{w}_{2}^*=\frac{\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1}}{\sqrt{ (\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1})^t(\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1}) }}

ניתן לראות כי הביטויים זהים משני האלגוריתמים.

תרגיל (3 [ב])

פתחו את הביטוי עבור $\underline{u}_{3}$ בשיטת גרם-שמידט הקלאסית ובשיטה היציבה והראו שמתקבלים ביטויים שונים.

תחילה נפתח בשיטה הרגילה:

\underline{u}_{3}^*=\underline{w}_{3}-c_{1}\underline{u}_{1}-c_{2}\underline{u}_{2}\implies \underline{u}_{1}^t\underline{w}_{3}-c_{1}=0 \land \underline{u}_{2}^t\underline{w}_{3}-c_{2}=0 \implies \begin{cases} c_{1}=\underline{u}_{1}^t\underline{w}_{3} \\ c_{2}=\underline{u}_{2}^t\underline{w}_{3} \end{cases}

לכן נקבל: $\underline{u}_{3}^*=\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2}$ .
כעת נוכל לבצע את הנרמול:

\underline{u}_{3}=\frac{1}{\left\lVert \underline{u}_{3}^* \right\rVert_{2} }\underline{u}_{3}^*=\frac{\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2}}{\sqrt{ (\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2})^t(\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2}) }}

כעת, נבצע את הפיתוח לפי האלגוריתם היציב.
תחילה, נקלף מ- $\underline{w}_{3}$ את $\underline{u}_{1},\underline{u}_{2}$ :

\underline{w}_{3}^{*}=\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}

\underline{w}_{3}^{**}\!\!=\!\underline{w}_{3}^*-\underline{u}_{2}^t\underline{w}^*_{3}\underline{u}_{2}=\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t(\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1})\underline{u}_{2}=\underline{w}_{3}\!\!-\!\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}\!-\!(\underline{u}_{2}^t\underline{w}_{3}-\underline{u}_{2}^t(\underline{u}_{1}^t\underline{w}_{3})\underline{u}_{1})\underline{u}_{2}

המכפלה $\underline{u}_{1}^t\underline{w}_{3}$ מולידה סקלר ולכן:

\underline{w}_{3}^{**}=\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-(\underline{u}_{2}^t\underline{w}_{3}-(\underline{u}_{1}^t\underline{w}_{3})(\underline{u}_{2}^t\underline{u}_{1}))\underline{u}_{2}

כעת, נוכל לבצע את הנרמול:

\begin{align*} \underline{u}_{3}&=\frac{1}{\left\lVert \underline{w}_{3}^{**} \right\rVert_{2} }\underline{w}_{3}^{**} \\ &=\frac{\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-(\underline{u}_{2}^t\underline{w}_{3}-(\underline{u}_{1}^t\underline{w}_{3})(\underline{u}_{2}^t\underline{u}_{1}))\underline{u}_{2}}{\sqrt{ (\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-(\underline{u}_{2}^t\underline{w}_{3}-(\underline{u}_{1}^t\underline{w}_{3})(\underline{u}_{2}^t\underline{u}_{1}))\underline{u}_{2})^t(\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-(\underline{u}_{2}^t\underline{w}_{3}-(\underline{u}_{1}^t\underline{w}_{3})(\underline{u}_{2}^t\underline{u}_{1}))\underline{u}_{2}) }} \end{align*}

נשים לב כי קיבלנו ביטויים שונים עבור $\underline{u}_{3}$ בשתי השיטות.

תרגיל (3 [ג])

האם למרות שהתקבלו ביטויים שונים עבור $\underline{u}_{3}$ הם שקולים אנליטית?
כלומר, אם נפעיל את שתי השיטות במחשב שמבצע כל חישוב דיוק מושלם, האם הוקטורים שהתקבלו בשתי השיטות צפויים להיות זהים? הסבירו.

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

תרגיל (3 [ד])

בסעיפים הבאים ננסה להצביע על ההבדל בין השיטות.
כפי שציינו במהלך הקורס, עקב חוסר יציבות נומרית של התהליך קבוצת הוקטורים המתקבלת בסופו אינם בהכרח מהווים קבוצה אורתונורמלית, כלומר, לא תמיד מתקיים $\underline{u}_{i}^t\underline{u}_{j}=0$ לכל $i \neq j$ .
בסעיפים הבאים נעבוד תחת ההנחות הבאות:

הוקטורים $\underline{u}_{1},\underline{u}_{2}$ שמתקבלים בסיום תהליך גרם-שמידט בשתי השיטות הינם מנורמלים. כלומר מתקיים $\underline{u}_{j}^t\underline{u}_{j}=1$ .
לא מובטח כי החישוב מתבצע במדויק אך הוא דטרמיניסטי. כלומר תמיד מתקבלת אותה התוצאה.

פתחו ביטוי כללי עבור המכפלה הפנימית $\underline{u}_{2}^t\underline{u}_{3}$ תחת ההנחות הנ"ל בשיטה הקלאסית והראו כי תוצאת המכפלה הפנימית אינה בהכרח מתאפסת.

נזכר בתוצאת סעיף ב' עבור האלגוריתם הרגיל:

\underline{u}_{3}=\frac{1}{\left\lVert \underline{u}_{3}^* \right\rVert_{2} }\underline{u}_{3}^*=\frac{\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2}}{\sqrt{ (\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2})^t(\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2}) }}

\underline{u}_{2}=\frac{1}{\left\lVert \underline{w}_{2}^* \right\rVert_{2} }\underline{w}_{2}^*=\frac{\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1}}{\sqrt{ (\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1})^t(\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1}) }}

כעת, נבדוק מהי ההמכפלה הפנימית שלהם:

\begin{align*} \underline{u}_{2}^t\underline{u}_{3}&=\underline{u}_{2}^t\frac{\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2}}{\sqrt{ (\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2})^t(\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2}) }} \\ &=\frac{\underline{u}_{2}^t\underline{w}_{3}-\underline{u}_{2}^t(\underline{u}_{1}^t\underline{w}_{3})\underline{u}_{1}-\underline{u}_{2}^t(\underline{u}_{2}^t\underline{w}_{3})\underline{u}_{2}}{\sqrt{ (\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2})^t(\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2}) }} \end{align*}

אנו יודעים כי $\underline{u}_{2}^t\underline{w}_{3}$ הוא סקלר ולכן מתקיים חילוף. (באותו האופן עבור $\underline{u}_{1}^t\underline{w}_{3}$ ) ובנוסף אנו יודעים כי $\underline{u}_{2}^t\underline{u}_{2}=1$ לפי ההנחה. לכן:

\begin{align*} \underline{u}_{2}^t\underline{u}_{3}&=\frac{\underline{u}_{2}^t\underline{w}_{3}-(\underline{u}_{1}^t\underline{w}_{3})(\underline{u}_{2}^t\underline{u}_{1})-\underline{u}_{2}^t\underline{w}_{3}}{\sqrt{ (\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2})^t(\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2}) }} \\ &=\frac{-(\underline{u}_{1}^t\underline{w}_{3})(\underline{u}_{2}^t\underline{u}_{1})}{\sqrt{ (\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2})^t(\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-\underline{u}_{2}^t\underline{w}_{3}\underline{u}_{2}) }} \end{align*}

לאור העובדה שלא בהכרח מתקיים $\underline{u}_{2}^t\underline{u}_{1}=0$ לא בהכרח מתקיים כי $\underline{u}_{2}^t\underline{u}_{3}=0$ כפי שהיינו מצפים מווקטורים אורתונורמליים.
לכן, לא מובטח לנו $\underline{u}_{3}$ המקיים את התנאים.

תרגיל (3 [ה])

פתחו ביטוי כללי עבור המכפלה הפנימית $\underline{u}_{2}^t\underline{u}_{3}$ תחת ההנחות הנ"ל בשיטה היציבה והראו כי מתקיים $\underline{u}_{2}^t\underline{u}_{3}=0$ .
המלצה: על מנת להקל על הפיתוח, מומלץ לעבוד עם $\underline{w}_{3}$ לאחר הקילוף של $\underline{u}_{1},\underline{u}_{2}$ במקום לעבוד עם $\underline{u}_{3}$ .
הערה: ניתן לקצר את הפיתוח בסעיף זה ע"י שימוש בביטוי שהתקבל בסעיף הקודם.

נזכר בביטוי עבור $\underline{w}_{3}^{**}$ שלמען פשוטת נסמנו ב- $\underline{v}_{3}$ .

\underline{v}_{3}=\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-(\underline{u}_{2}^t\underline{w}_{3}-(\underline{u}_{1}^t\underline{w}_{3})(\underline{u}_{2}^t\underline{u}_{1}))

כעת, נבצע את ההכפלה אשר אמורה לתת לנו אפס שכן הקילוף נותן לנו וקטורים המקיימים $\underline{u}_{i}^t\underline{u}_{j}=0$ פשוט שהמכפלה הפנימית שלהם עם עצמם לא מובטחת להיות 1:

\begin{align*} \underline{u}_{2}^t\underline{v}_{3}&=\underline{u}_{2}^t(\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}-(\underline{u}_{2}^t\underline{w}_{3}-(\underline{u}_{1}^t\underline{w}_{3})(\underline{u}_{2}^t\underline{u}_{1}))\underline{u}_{2}) \\ &=\underline{u}_{2}^t\underline{w}_{3}-(\underline{u}_{1}^t\underline{w}_{3})(\underline{u}_{2}^t\underline{u}_{1})-(\underline{u}_{2}^t\underline{w}_{3})+(\underline{u}_{1}^t\underline{w}_{3})(\underline{u}_{2}^t\underline{u}_{1}) \\ &=0+0=0 \end{align*}

לכן, בהכרח מתקיים שבשיטה היציבה $\underline{u}_{2}^t\underline{u}_{3}=0$ .

תרגיל 4

תרגיל (4 [א])

נתונה מטריצה ריבועית $A$ ונניח כי קיים עבורה פירוק $A=Q_{1}R_{1}$ .
הציעו פירוק שונה אפילו במקצת ועם זאת בעל המבנה הנכון. כלומר, $A=Q_{1}R_{1}=Q_{2}R_{2}$ . כאשר $Q_{2}$ אורתונורמית ו- $R_{2}$ משולשת עליונה ושתי אלו שונות מהמטריצות $Q_{1},R_{1}$ בהתאמה.

נגדיר $K=\begin{pmatrix}-1 & 0 & \dots & 0 \\0 & 1 & \dots & 0 \\\vdots & \vdots & \ddots & \vdots \\0 & 0 & \dots & 1\end{pmatrix}$ . נשים לב כי מתקיים $KK=I$ ולכן:

A=Q_{1}R_{1}=Q_{1}KKR_{1}=(Q_{1}K)(KR_{1})

המטריצה $K$ מבצעת ניגוד לווקטור הראשון ובכך בעצם הופכת אותו שכן מתקיים:

(-\underline{u}_{1})^t(\underline{u}_{i})=-\underline{u}_{1}^t\underline{u}_{i}=-0=0

ואורכו נשמר שכן:

(-\underline{u}_{1})^t(-\underline{u}_{1})=\underline{u}_{1}^t\underline{u}_{1}

לכן מתקיים כי $Q_{1}K$ הינה מטריצה אורתונורמלית השונה מ- $Q_{1}$ . נסמנה $Q_{2}$ .
מכיוון ש- $K$ מבצעת ניגוד אך ורק לוקטור הראשון המטריצה $KR_{1}$ הינה משולשת עליונה. נסמנה $R_{2}$ .
אזי מתקיים:

A=Q_{1}R_{1}=Q_{2}R_{2}

כך ש- $Q_{1}\neq Q_{2},R_{1}\neq R_{2}$ .

תרגיל (4 [ב])

נרצה להציע פירוק חדש למטריצה מהצורה $A=LS$ כאשר $L$ משולשת תחתונה ו- $S$ אורתונורמלית.
בהנחה שיש בידיכם את הקוד המיישם את פירוק $QR$ כיצד יהיה ניתן להשתמש בו להשגת הפירוק המיוחל? נמקו

נביט במטריצה $A^t$ . קיימים $\tilde{Q},\tilde{R}$ כך שעבורם מתקיים $A^t=\tilde{Q}\tilde{R}$ לפי משפט.
נמצא אותו לפי האלגוריתם הנתון לנו ואז מתקיים:

(A^t)^t=(\tilde{Q}\tilde{R})^t=\tilde{R}^t\tilde{Q}^t

נסמן $S=\tilde{Q}^t$ שכן $\tilde{Q}$ אורתונורמלית ולכן, לפי משפט, $\tilde{Q}^t$ אורתונורמלית.
המטריצה $\tilde{R}$ הינה משולשת עליונה ולכן $\tilde{R}^t$ היא משולשת תחתונה. נסמנה $L$ .
לכן מתקיים:

A=(A^t)^t=LS

כנדרש.

תרגיל (4 [ג])

באופן דומה, נרצה להציע פירוק חדש למטריצה מהצורה $A=SL$ כאשר $L$ משולשת תחתונה ו- $S$ מטריצה אורתונורמלית.
הציעו שיטה לקבלת פירוק מתאים והסבירו את הצעתכם.

לפי ההרצאה, מטריצת פרמוטציה הינה אורתונורמלית. נגדיר $P=\begin{pmatrix}0 & \dots & 0 & 1\\0 & \dots & 1 & 0\ \\ \vdots & & \vdots & \vdots\\ 1 & \dots & 0 & 0\end{pmatrix}$ . המטריצה אורתונורמלית מהנ"ל ולכן, לפי משפט מקיימת $P^tP=I$ ולכן מתקיים:

A=QR=QP^tPR

מכיוון שהשורות הפוכות ב- $P$ נקבל היפוך של השורות במטריצה ולכן מתקיים כי $PR$ הינה משולשת תחתונה. נסמנה $L$ .
המטריצה $QP^t$ היא אורתונורמלית מכפל של אורתונורמליות. נסמנה $S$ .
אזי:

A=SL

כנדרש.

תרגיל 5

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

לפניכם בעיית ריבועים פחותים עם אילוץ:

\arg \underset{\underline{x}}{\min}\left\lVert Q\underline{x}-\underline{b} \right\rVert _{2}^2, \qquad \lVert \underline{x} \rVert _{0}\leq M

כאשר $Q \in \mathbb{R}^{m\times n}$ מטריצה בעלת עמודות אורתונורמליות ו- $\underline{x} \in \mathbb{R}^n,\underline{b}\in \mathbb{R}^m$ בנוסף לכך $M>0$ מספר שלם ומתקיים:

\left\lVert \underline{x} \right\rVert _{0}:= \sum_{i=1}^{n}1_{x_{i}\neq 0}

כלומר, נורמת אפס של וקטור שווה למספר הכניסות בווקטור ששונות מאפס.

תרגיל (5 [א])

האם נורמת האפס היא אכן נורמה ע"פ ההגדרה? הראו שנורמת האפס עומדת בהגדרה או הראו חלק בהגדרה שאינה עומדת בו.

נשים לב כי נורמת האפס בעצם אינה נורמה על פי ההגדרה שכן היא לא מקיימת הומוגניות.
נקח נניח את הוקטור $\underline{x}=\begin{pmatrix}2\\ 3 \\ 0\end{pmatrix}$ ואת הסקלר $\alpha=2$ . אזי יתקיים:

\left\lVert \alpha \underline{x} \right\rVert _{0}=\left\lVert 2\begin{pmatrix} 2 \\ 3 \\ 0 \end{pmatrix} \right\rVert _{0}=\left\lVert \begin{pmatrix} 4 \\ 6 \\ 0 \end{pmatrix} \right\rVert _{0}=1+1+0=2

אך:

|\alpha|\left\lVert \underline{x} \right\rVert _{0}=2\left\lVert \begin{pmatrix} 2 \\ 3 \\ 0 \end{pmatrix} \right\rVert _{0}=2(1+1+0)=4

מכיוון ש- $4\neq 2$ התכונה אינה מתקיימת ולכן, נורמת האפס אינה נורמה.

תרגיל (5 [ב])

הוכיחו כי: $(Q\underline{x}-QQ^t\underline{b})\perp(QQ^t\underline{b}-\underline{b})$ .

הוכחה:
אנו יודעים כי שני וקטורים מאונכים אם המכפלה הפנימית ביניהם הינה 0.

\begin{align*} \langle Q\underline{x}-QQ^t\underline{b},\; QQ^t\underline{b}-\underline{b}\rangle &= (Q\underline{x}-QQ^t\underline{b})^t(QQ^t\underline{b}-\underline{b})=(\underline{x}^tQ^t-\underline{b}^t(Q^t)^tQ^t)(QQ^t\underline{b}-\underline{b}) \\ &=\underline{x}^tQ^tQQ^t\underline{b}-\underline{x}^tQ^t\underline{b}-\underline{b}^tQQ^tQQ^t\underline{b}+\underline{b}^tQQ^t\underline{b} \\ & \!\!\!\!\underset{\begin{matrix} \downarrow \\ \R{\text{לפי משפט:}} \\ Q^tQ=I \end{matrix}}{=}\!\!\!\!\!\! \underline{x}^tQ^t\underline{b}-\underline{x}^tQ^t\underline{b}+\underline{b}^tQQ^t\underline{b}-\underline{b}^tQQ^t\underline{b}=0+0=0 \end{align*}

לכן, הוקטורים הללו מאונכים.
∎

תרגיל (5 [ג])

נרצה להשתמש בסעיף ב' כדי למצוא נוסחה סגורה לבעיית האופטימיזציה מתחילת השאלה בדרך שונה מזו שראינו בכיתה.
הוכיחו את הפתרון ע"י השלבים הבאים וטיעונים נוספים ע"פ הצורך:

הוספה והחסרה של $QQ^t\underline{b}$ .
שימוש בסעיף ב'.
ניסוח כפל מטריצה בוקטור כצ"ל של עמודות המטריצה.
שימוש בתכונות המטריצה $Q$ .
שימוש בפונקציה $TopM(\underline{v})$ המקבלת וקטור ומחזירה את האינדקסים של $M$ הערכים בגדולים ביותר.

הוכחה:
נסתכל על בעיית האופטימיזציה:

\left\lVert Q\underline{x}-\underline{b} \right\rVert _{2}^2=\left\lVert Q\underline{x}-\underline{b}+QQ^t\underline{b}-QQ^t\underline{b} \right\rVert_{2}^2 \underset{\begin{matrix} \downarrow \\ \R{\text{פיתגרוס}} \end{matrix}}{=}\left\lVert Q\underline{x}-QQ^t\underline{b} \right\rVert _{2}^2+\left\lVert QQ^t\underline{b}-\underline{b} \right\rVert _{2}^2

הנורמה השנייה קבועה ולכן על מנת למזער את התוצאה נדרש רק לדאוג למזער את הנורמה הראשונה.

\left\lVert Q\underline{x}-QQ^t\underline{b} \right\rVert _{2}^2=\left\lVert Q(\underline{x}-Q^t\underline{b}) \right\rVert _{2}^2 \underset{\begin{matrix} \downarrow \\ \underline{c}=\underline{x}-Q^t\underline{b} \end{matrix}}{=}\left\lVert Q\underline{c} \right\rVert _{2}^2=\left\lVert c_{1}\underline{q}_{1}+c_{2}\underline{q}_{2}+\dots+c_{n}\underline{q}_{n} \right\rVert _{2}^2

לפי תכונות הנורמה מתקיים:

=c_{1}\left\lVert \underline{q}_{1} \right\rVert _{2}^2+c_{2}\left\lVert \underline{q}_{2} \right\rVert _{2}^2+\dots+c_{n}\left\lVert \underline{q}_{n} \right\rVert _{2}^2 \underset{\begin{matrix} \downarrow \\ \R{\text{ אורתונורמליות}}Q\R{\text{עמודות }} \end{matrix}}{=}c_{1}+c_{2}+\dots+c_{n}=\sum_{i=1}^n c_{i}

לכן, בעיית האופטימיזיציה הינה על מזעור $\underline{c}$ בלבד ובכך מזעור $\underline{x}$ בלבד.

\left\lVert \underline{x}-Q^t\underline{b} \right\rVert _{2}^2=\sum_{i=1}^n (x_{i}-(Q^t\underline{b})_{i})^2

מכיוון שיש לנו תנאי של $\left\lVert \underline{x} \right\rVert_{0}\leq M$ אזי יש לנו רק $M$ מקומות בוקטור $\underline{x}$ שבהם נוכל למקם ערכים שאינם $0$ .
מכייון שאנו לוקחים את הערך בכל מקום ומחסרים ממנו את האינדק התואם ב- $Q^t\underline{b}$ נרצה לקחת את האיברים הגדולים ביותר ב- $Q^t\underline{b}$ ולאפס אותם תחילה.
לכן, נשתמש בפונקציה $TopM(Q^t\underline{b})$ ובכל אינדקס שניתן לנו נשים בדיוק את הערך של $Q^t\underline{b}$ באינדקס הזה באותו האינדקס ב- $\underline{x}$ .
שאר האינדקסים יהיו כמובן אפסים לפי הגדרת השאלה.
כך, אנו נקטין כמה שיותר את הבעיה שלנו.
∎

תרגיל (5 [ד])

במקרה בו אילוץ הדלילות אינו קיים, מהי קבוצת הוקטורים עבורם ערך המינימום של הבעיה מעלה הוא $0$ ? הסבירו כיצד הדבר משתקף בפיתוח מסעיף 3.

ראינו בסעיף הקודם כי אנו נמזער את ערך המינימום ככל שנקבע ליותר איברים $x_{i}=(Q^t\underline{b})_{i}$ . את זה ניתן לראות במשוואה האחרונה:

\left\lVert \underline{x}-Q^t\underline{b} \right\rVert _{2}^2=\sum_{i=1}^n (x_{i}-(Q^t\underline{b})_{i})^2

לכן, על מנת שהמעלה תהיה אפס נגדיר $\underline{x}=Q^t\underline{b}$ , נוכל לעשות זאת מפאת העובדה שאין אילוץ ולכן כל איבר יכול להיות גדול או קטן כבחירתינו וכך כל רכיב בסכום יתאפס ונקבל סכום של אפס.