6 - אורתוגונליות ואלגוריתם גרם-שמידט — אלגוריתמים נומריים

הגדרה 1 (מכפלה פנימית במקרה שלנו)

\langle \underline{u},\underline{v}\rangle=\underline{u}^t\underline{v}

הגדרה 2 (קבוצה אורתוגונלית)

קבוצת וקטורים $\left\{ \underline{v}_{k} \right\}_{k}$ היא אורתוגונלית אם מתקיים שהם אנכיים זה לזה:

\forall i \neq j:\;\; \langle \underline{v}_{i},\underline{v}_{j}\rangle =\underline{v}_{i}^t\underline{v}_{j}=0

הגדרה 3 (קבוצה אורתונורמלית)

קבוצת וקטורים $\left\{ \underline{v}_{k} \right\}_{k}$ היא אורתונורמלנית אם היא אורתוגונלית ומתקיים:

\forall i:\;\; \langle \underline{v}_{i},\underline{v}_{i}\rangle=\left\lVert \underline{v}_{i} \right\rVert _{2}^2=1

הגדרה 4 (מטריצה אורתונורמלית)

מטריצה $Q$ היא מטריצה אורתונורמלית אם היא ריבועית ועמודותיה מהוות קבוצה אורתונורמלית.

משפט (תכונות מטריצה אורתונורמלית)

ההיפוך הוא השחלוף: $Q^{-1}=Q^t$
גם שורות $Q$ מהוות קבוצה אורתונורמלית: $QQ^t=I$ .
הדטרמיננט של $Q$ הוא $\pm1$ .
מכפלת מטריצות אורתונורמליות היא גם אורתונורמלית.
שימור נורמת $L_{2}$ (תכונת פרסוול) $\left\lVert Q\underline{x} \right\rVert_{2}^2=\left\lVert \underline{x} \right\rVert_{2}^2$

אם $A$ היא מטריצה בגודל $n\times n$ אורתונורמלית אזי למערכת המשוואות $A\underline{x}=\underline{b}$ יש פתרון פשוט:

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

אם $A$ היא מטריצה בגודל $m\times n$ כאשר $m\geq n$ ועמודותיה אורתונורמליות, אזי לבעיית הריבועים הפחותים הבאה יש פתרון פשוט:

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

תרגיל

הוכיחו כי סט של $K$ וקטורים אורתוגונליים במרחב $n$ מימדי הינו בהכרח בת"ל.

תזכורת: (משפט פיטגורס המוכלל) $\left\lVert \underline{v}_{1}+\dots+\underline{v}_{k} \right\rVert^2=\sum_{i=1}^k \left\lVert v_{i} \right\rVert^2$ .

הוכחה:
אם $\alpha_{1}\underline{v}_{1}+\alpha_{2}\underline{v}_{2}+\dots+\alpha_{k}\underline{v}_{k}=\underline{0}$ לכל $i \in \left\{ 1,\dots,k \right\}$ כך ש- $\alpha_{i}\neq 0$ מתקיים כי $\left\{ \alpha_{i}\underline{v}_{i} \right\}_{i}$ אורתוגונליים.
לפי פיתגורס מתקיים:

0=\left\lVert 0 \right\rVert^2 =\left\lVert \alpha_{1}\underline{v}_{1}+\dots+\alpha_{k}\underline{v}_{k} \right\rVert ^2 =\sum_{i=1}^k \left\lVert \alpha_{i}\underline{v}_{i} \right\rVert ^2

\implies \forall i:\;\; \left\lVert \alpha_{i}\underline{v}_{i} \right\rVert ^2 \implies \forall i:\;\; \alpha_{i}\underline{v}_{i}=0 \implies \alpha_{i}=0

לכן, ע"פ הגדרה, הוקטורים בת"ל.
∎

הגדרה 5 (מטריצת

Householder

)

בהינתן וקטור כלשהו $\underline{v}$ באורך יחידה $(\underline{v}^t\underline{v}=1)$ . אזי, מטריצת השיקוף של $Householder$ נתונה ע"י:

H=I-2\underline{v}\;\!\underline{v}^t

משפט (תכונות מטריצת השיקוף)

מטריצה זו סימטרית
מטריצה זו אורתונורמלית
נובע מהנ"ל כי המטריצה זו היא היפוך של עצמה. ( $HH=I$ )
מטריצה זו מייצרת שיקוף בכיוון $\underline{v}$ ולא משפיעה בכיוונים אנכיים לזה.

תרגיל

יהיו $u \neq w \in \mathbb{R}^n$ כך ש- $\left\lVert \underline{u} \right\rVert_{2}^2=\left\lVert \underline{w} \right\rVert_{2}^2$ .
נגדיר $\underline{v}=\frac{1}{\left\lVert \underline{u}-\underline{w} \right\rVert}(\underline{u}-\underline{w})$ ונצור את מטריצת האוסהולדר כך $H=I-2\underline{v}\;\!\underline{v}^t$ .
הוכיחו כי מתקיים $H\underline{u}=\underline{w} \land H\underline{w}=\underline{u}$ .

הוכחה:
מתקיים כי:

H=I-2\underline{v}\;\!\underline{v}^t=I-2 \frac{\underline{u}-\underline{w}}{\left\lVert \underline{u}-\underline{w} \right\rVert } \frac{(\underline{u}-\underline{w})^t}{\left\lVert \underline{u}-\underline{w} \right\rVert }=I-\frac{2}{\left\lVert \underline{u}-\underline{w} \right\rVert^2 }(\underline{u}\;\!\underline{u}^t-\underline{u}\;\!\underline{w}^t-\underline{w}\;\!\underline{u}^t+\underline{w}\;\!\underline{w}^t)

נכפיל ב- $w$ :

\begin{align*} H\underline{w}&=\left( I-\frac{2}{\left\lVert \underline{u}-\underline{w} \right\rVert^2 }(\underline{u}\;\!\underline{u}^t-\underline{u}\;\!\underline{w}^t-\underline{w}\;\!\underline{u}^t+\underline{w}\;\!\underline{w}^t) \right)\underline{w} \\ &=\underline{w}-\frac{2}{\left\lVert \underline{u}-\underline{w} \right\rVert^2 }(\underline{u}\!\;\underline{u}^t\underline{w}-\underline{u}\;\!\underline{w}^t\underline{w}-\underline{w}\;\!\underline{u}^t\underline{w}+\underline{w}\;\!\underline{w}^t\underline{w}) \\ &=\underline{w}-\frac{2}{\left\lVert \underline{u}-\underline{w} \right\rVert^2 }((\underline{u}-\underline{w})\underline{u}^t\underline{w}-(\underline{u}-\underline{w})\underline{w}^t\underline{w}) \\ &=\underline{w}-\frac{2}{\left\lVert \underline{u}-\underline{w} \right\rVert^2 }((\underline{u}-\underline{w})(\underline{u}^t\underline{w}-\underline{w}^t\underline{w})) \\ &\left\lVert \underline{u}-\underline{w} \right\rVert^2=\left\lVert \underline{u} \right\rVert^2-\underline{u}^t\underline{w}-\underline{w}^t\underline{u}+\left\lVert \underline{w} \right\rVert^2\;\;\ \R{\text{נשים לב כי:}} \\ & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\left\lVert \underline{u} \right\rVert^2-2\underline{u}^t\underline{w}+\left\lVert \underline{w} \right\rVert^2=2\left\lVert \underline{w} \right\rVert^2-2\underline{u}^t\underline{w} \\ & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=-2(\underline{u}^t\underline{w}-\left\lVert \underline{w} \right\rVert^2 ) \\ &=\underline{w}+(\underline{u}-\underline{w})=\underline{u} \end{align*}

באותה הדרך עבור $\underline{H}=\underline{w}$ .
∎

הגדרה 6 (מטריצת

Hadamard

)

מטריצה זו מוגדרת באופן רקורסיבי עם תנאי עצירה:

H_{0}=\begin{pmatrix} 1 \end{pmatrix} \quad H_{1}=\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \quad H_{2}=\begin{pmatrix} H_{1} & H_{1} \\ H_{1} & -H_{1} \end{pmatrix} \quad H_{n}=\begin{pmatrix} H_{n-1} & H_{n-1} \\ H_{n-1} & -H_{n-1} \end{pmatrix}

מטריצה $H_{n}$ הינה בגודל $2^n\times 2^n$ .

משפט

מטריצת $H_{n}$ סימטרית.

הוכחה: באינדוקציה.
בסיס: עבור $n=0$ המטריצה אכן סימטרית.
צעד: נניח שהמטריצה $H_{n-1}$ מקיימת $H_{n-1}^t=H_{n-1}$ ונוכיח:

H_{n}^t=\begin{pmatrix} H_{n-1}^t & H_{n-1}^t \\ H_{n-1}^t & -H_{n-1}^t \end{pmatrix}=\begin{pmatrix} H_{n-1} & H_{n-1} \\ H_{n-1} & -H_{n-1} \end{pmatrix}=H_{n}

∎

משפט

מטריצת $H_{n}$ אורתונורמלית (עד כדי הכפלה בקבוע)

הוכחה: באינדוקציה
בסיס: עבור $n=0$ המטריצה $H_{0}$ אכן אורתונורמלית.
צעד: נניח שהמטריצה $H_{n-1}$ מקיימת $H_{n-1}^tH_{n-1}=2^{n-1}I_{2^{n-1}}$ . אזי:

H_{n}^2=H_{n}^tH_{n}=\begin{pmatrix} H_{n-1}^t & H_{n-1}^t \\ H_{n-1}^t & -H_{n-1}^t \end{pmatrix}\begin{pmatrix} H_{n-1} & H_{n-1} \\ H_{n-1} & H_{n-1} \end{pmatrix}=\begin{pmatrix} 2H_{n-1}^tH_{n-1} & 0 \\ 0 & 2H_{n-1}^tH_{n-1} \end{pmatrix}=

=2^n\begin{pmatrix} I_{2^{n-1}} & 0 \\ 0 & I_{2^{n-1}} \end{pmatrix}=2^n \cdot I_{2^n}

∎

הגדרה 1 (מכפלה פנימית במקרה שלנו)

\langle \underline{u},\underline{v}\rangle=\underline{u}^t\underline{v}

הגדרה 2 (קבוצה אורתוגונלית)

קבוצת וקטורים $\left\{ \underline{v}_{k} \right\}_{k}$ היא אורתוגונלית אם מתקיים שהם אנכיים זה לזה:

\forall i \neq j:\;\; \langle \underline{v}_{i},\underline{v}_{j}\rangle =\underline{v}_{i}^t\underline{v}_{j}=0

הגדרה 3 (קבוצה אורתונורמלית)

קבוצת וקטורים $\left\{ \underline{v}_{k} \right\}_{k}$ היא אורתונורמלנית אם היא אורתוגונלית ומתקיים:

\forall i:\;\; \langle \underline{v}_{i},\underline{v}_{i}\rangle=\left\lVert \underline{v}_{i} \right\rVert _{2}^2=1

הגדרה 4 (מטריצה אורתונורמלית)

מטריצה $Q$ היא מטריצה אורתונורמלית אם היא ריבועית ועמודותיה מהוות קבוצה אורתונורמלית.

משפט (תכונות מטריצה אורתונורמלית)

ההיפוך הוא השחלוף: $Q^{-1}=Q^t$
גם שורות $Q$ מהוות קבוצה אורתונורמלית: $QQ^t=I$ .
הדטרמיננט של $Q$ הוא $\pm1$ .
מכפלת מטריצות אורתונורמליות היא גם אורתונורמלית.
שימור נורמת $L_{2}$ (תכונת פרסוול) $\left\lVert Q\underline{x} \right\rVert_{2}^2=\left\lVert \underline{x} \right\rVert_{2}^2$

אם $A$ היא מטריצה בגודל $n\times n$ אורתונורמלית אזי למערכת המשוואות $A\underline{x}=\underline{b}$ יש פתרון פשוט:

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

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

תרגיל

הוכיחו כי סט של $K$ וקטורים אורתוגונליים במרחב $n$ מימדי הינו בהכרח בת"ל.

תזכורת: (משפט פיטגורס המוכלל) $\left\lVert \underline{v}_{1}+\dots+\underline{v}_{k} \right\rVert^2=\sum_{i=1}^k \left\lVert v_{i} \right\rVert^2$ .

0=\left\lVert 0 \right\rVert^2 =\left\lVert \alpha_{1}\underline{v}_{1}+\dots+\alpha_{k}\underline{v}_{k} \right\rVert ^2 =\sum_{i=1}^k \left\lVert \alpha_{i}\underline{v}_{i} \right\rVert ^2

\implies \forall i:\;\; \left\lVert \alpha_{i}\underline{v}_{i} \right\rVert ^2 \implies \forall i:\;\; \alpha_{i}\underline{v}_{i}=0 \implies \alpha_{i}=0

לכן, ע"פ הגדרה, הוקטורים בת"ל.
∎

הגדרה 5 (מטריצת

Householder

)

בהינתן וקטור כלשהו $\underline{v}$ באורך יחידה $(\underline{v}^t\underline{v}=1)$ . אזי, מטריצת השיקוף של $Householder$ נתונה ע"י:

H=I-2\underline{v}\;\!\underline{v}^t

משפט (תכונות מטריצת השיקוף)

מטריצה זו סימטרית
מטריצה זו אורתונורמלית
נובע מהנ"ל כי המטריצה זו היא היפוך של עצמה. ( $HH=I$ )
מטריצה זו מייצרת שיקוף בכיוון $\underline{v}$ ולא משפיעה בכיוונים אנכיים לזה.

תרגיל

הוכחה:
מתקיים כי:

H=I-2\underline{v}\;\!\underline{v}^t=I-2 \frac{\underline{u}-\underline{w}}{\left\lVert \underline{u}-\underline{w} \right\rVert } \frac{(\underline{u}-\underline{w})^t}{\left\lVert \underline{u}-\underline{w} \right\rVert }=I-\frac{2}{\left\lVert \underline{u}-\underline{w} \right\rVert^2 }(\underline{u}\;\!\underline{u}^t-\underline{u}\;\!\underline{w}^t-\underline{w}\;\!\underline{u}^t+\underline{w}\;\!\underline{w}^t)

נכפיל ב- $w$ :

\begin{align*} H\underline{w}&=\left( I-\frac{2}{\left\lVert \underline{u}-\underline{w} \right\rVert^2 }(\underline{u}\;\!\underline{u}^t-\underline{u}\;\!\underline{w}^t-\underline{w}\;\!\underline{u}^t+\underline{w}\;\!\underline{w}^t) \right)\underline{w} \\ &=\underline{w}-\frac{2}{\left\lVert \underline{u}-\underline{w} \right\rVert^2 }(\underline{u}\!\;\underline{u}^t\underline{w}-\underline{u}\;\!\underline{w}^t\underline{w}-\underline{w}\;\!\underline{u}^t\underline{w}+\underline{w}\;\!\underline{w}^t\underline{w}) \\ &=\underline{w}-\frac{2}{\left\lVert \underline{u}-\underline{w} \right\rVert^2 }((\underline{u}-\underline{w})\underline{u}^t\underline{w}-(\underline{u}-\underline{w})\underline{w}^t\underline{w}) \\ &=\underline{w}-\frac{2}{\left\lVert \underline{u}-\underline{w} \right\rVert^2 }((\underline{u}-\underline{w})(\underline{u}^t\underline{w}-\underline{w}^t\underline{w})) \\ &\left\lVert \underline{u}-\underline{w} \right\rVert^2=\left\lVert \underline{u} \right\rVert^2-\underline{u}^t\underline{w}-\underline{w}^t\underline{u}+\left\lVert \underline{w} \right\rVert^2\;\;\ \R{\text{נשים לב כי:}} \\ & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\left\lVert \underline{u} \right\rVert^2-2\underline{u}^t\underline{w}+\left\lVert \underline{w} \right\rVert^2=2\left\lVert \underline{w} \right\rVert^2-2\underline{u}^t\underline{w} \\ & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=-2(\underline{u}^t\underline{w}-\left\lVert \underline{w} \right\rVert^2 ) \\ &=\underline{w}+(\underline{u}-\underline{w})=\underline{u} \end{align*}

באותה הדרך עבור $\underline{H}=\underline{w}$ .
∎

הגדרה 6 (מטריצת

Hadamard

)

מטריצה זו מוגדרת באופן רקורסיבי עם תנאי עצירה:

H_{0}=\begin{pmatrix} 1 \end{pmatrix} \quad H_{1}=\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \quad H_{2}=\begin{pmatrix} H_{1} & H_{1} \\ H_{1} & -H_{1} \end{pmatrix} \quad H_{n}=\begin{pmatrix} H_{n-1} & H_{n-1} \\ H_{n-1} & -H_{n-1} \end{pmatrix}

מטריצה $H_{n}$ הינה בגודל $2^n\times 2^n$ .

משפט

מטריצת $H_{n}$ סימטרית.

הוכחה: באינדוקציה.
בסיס: עבור $n=0$ המטריצה אכן סימטרית.
צעד: נניח שהמטריצה $H_{n-1}$ מקיימת $H_{n-1}^t=H_{n-1}$ ונוכיח:

H_{n}^t=\begin{pmatrix} H_{n-1}^t & H_{n-1}^t \\ H_{n-1}^t & -H_{n-1}^t \end{pmatrix}=\begin{pmatrix} H_{n-1} & H_{n-1} \\ H_{n-1} & -H_{n-1} \end{pmatrix}=H_{n}

∎

משפט

מטריצת $H_{n}$ אורתונורמלית (עד כדי הכפלה בקבוע)

H_{n}^2=H_{n}^tH_{n}=\begin{pmatrix} H_{n-1}^t & H_{n-1}^t \\ H_{n-1}^t & -H_{n-1}^t \end{pmatrix}\begin{pmatrix} H_{n-1} & H_{n-1} \\ H_{n-1} & H_{n-1} \end{pmatrix}=\begin{pmatrix} 2H_{n-1}^tH_{n-1} & 0 \\ 0 & 2H_{n-1}^tH_{n-1} \end{pmatrix}=

=2^n\begin{pmatrix} I_{2^{n-1}} & 0 \\ 0 & I_{2^{n-1}} \end{pmatrix}=2^n \cdot I_{2^n}

∎