אנו נעסוק במטריצות אורתונורמליות ונבין את חשיבותן. נציג את פירוק $QR$ למטריצות ואת השימוש בו לפתרון בעיות ריבועים פחותים.
נניח שנתונה לנו המטריצה $A$ בגודל $n\times m$ כאשר $n>m$ מדרגה מלאה ויחד עמה נתון גם וקטור שרירותי $\underline{b}$ .
זוהי בעיית ריבועים פחותים המוגדרת מהצמד $A$ ו- $\underline{b}$ ומציאת הפתרון לפי הנוסחאות הסגורות לוקח הרבה עבודה.
נניח וידוע שהעמודות אורתונורמליות? כלומר, מתקיים $\underline{a}_{j}^t\underline{a}_{k}=\begin{cases}1 & j=k\\ 0 & j \neq k\end{cases}$ (פעולה כזו בין שני וקטורים נקראת מכפלה פנימית) אזי:

\begin{align*} A^tA&=\begin{pmatrix} - & \underline{a}_{1}^t & - \\ - & \underline{a}_{2}^t & - \\ & \vdots \\ - & \underline{a}_{m}^t & - \end{pmatrix}\begin{pmatrix} \vert & \vert & & \vert \\ \underline{a}_{1} & \underline{a}_{2} & \dots & \underline{a}_{m} \\ \vert & \vert & & \vert \end{pmatrix}=\begin{pmatrix} \underline{a}_{1}^t\underline{a}_{1} & \underline{a}_{1}^t\underline{a}_{2} & \underline{a}_{1}^t\underline{a}_{3} & \dots & \underline{a}_{1}^t\underline{a}_{m} \\ \underline{a}_{2}^t\underline{a}_{1} & \underline{a}_{2}^t\underline{a}_{2} & \underline{a}_{2}^t\underline{a}_{3} & \dots & \underline{a}_{2}^t\underline{a}_{m} \\ \underline{a}_{3}^t\underline{a}_{1} & \underline{a}_{3}^t\underline{a}_{2} & \underline{a}_{3}^t\underline{a}_{3} & \dots & \underline{a}_{3}^t\underline{a}_{m} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \underline{a}_{m}^t\underline{a}_{1} & \underline{a}_{m}^t\underline{a}_{2} & \underline{a}_{m}^t\underline{a}_{3} & \dots & \underline{a}_{m}^t\underline{a}_{m} \end{pmatrix} \\ &=\begin{pmatrix} 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 1 \end{pmatrix} \end{align*}

כעת המטריצה $A^tA$ לא צריכה חישוב או היפוך ואז נקבל:

\underline{x}^*=(A^tA)^{-1}A^t\underline{b}=A^t\underline{b}=\begin{pmatrix} \underline{a}_{1}^t\underline{b} \\ \underline{a}_{2}^t\underline{b} \\ \vdots \\ \underline{a}_{m}^t\underline{b} \end{pmatrix}

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

p(\underline{x}^*)=\underline{b}^t\underline{b}-(\underline{x}^*)^t(A^tA)(\underline{x}^*)=\left\lVert \underline{b} \right\rVert _{2}^2-\left\lVert A^t\underline{b} \right\rVert _{2}^2

מסקנה

אם התמזל מזלנו ועמודות $A$ אורתונורמליות, אז חישובי פתרון הריבועים הפחותים וגובה הפונקציה במינימום נעשים קלים יותר לאין שיעור.

משפט

בהינתן סט של $\underline{m}$ וקטורים $\underline{a}_{k}$ אורתונורמליים ממימד $n$ (כך ש- $n>m$ ), הם בכרח בת"ל.

הוכחה:
יהיו סקלרים $c_{1},\dots,c_{m}\in \mathbb{F}$ כך ש:

\sum_{k=1}^m c_{k}\underline{a}_{k}=\underline{0}

נכפיל משוואה זו ב- $\underline{a}_{j}$ משוחלף משמאל עבור $j=1,2,3,\dots,n$ ואז נקבל:

0=\underline{a}_{j}^t\left( \sum_{k=1}^m c_{k}\underline{a}_{k} \right)=\sum_{k=1}^m c_{k}\underline{a}_{j}^t \underline{a}_{k} \underset{\begin{matrix} \downarrow \\ \R{\text{הגדרת אורטונורמליות}} \end{matrix}}{=} c_{j}

לכן מתקיים: $c_{i}=0$ לכל $1\leq i \leq n$ ולכן, לפי הגדרה, הוקטורים בת"ל.
∎

מטריצות אורתונומרליות

הגדרה 1 (וקטורים אורתוגונליים)

יהי $V$ מ"ו מעל שדה $\mathbb{F}$ בעל מכפלה פנימית. יהיו $u\neq v \in V$ .
הוקטורים $u,v$ יקראו אורתוגונליים זה לזה אם $\langle u,v \rangle=0$ .

הגדרה 2 (בסיס אורתונורמלי)

יהי $V$ מ"ו מעל שדה $\mathbb{F}$ בעל מכפלה פנימית ויהי $B=\left\{ \underline{v}_{1},\dots,\underline{v}_{n} \right\}$ בסיס ל- $V$ .
$B$ יקרא בסיס אורתונורמלי אם הוא מקיים את שני התנאים הבאים:

כל שני וקטורים שונים ב- $B$ אורתוגונליים. (כלומר, $\forall i,j \leq n:\; \langle \underline{v}_{i},\underline{v}_{j}\rangle =0$ )
הנורמה של כל וקטור בקבוצה שווה בדיוק ל-1. (כלומר, $\forall i\leq n:\; \langle \underline{v}_{i},\underline{v}_{i}\rangle=1=\left\lVert \underline{v}_{i} \right\rVert$ )

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

מטריצה $Q$ נקראת אורתונורמלית אם היא ריבועית ועמודותיה מהוות בסיס אורתונורמלי למלוא המרחב $\mathbb{R}^n$ .

הערה

מטריצות אורתונורמלייות יכולות להיקרא גם מטריצות יוניטריות. (בסיכום זה לא תראו עוד את המושג הזה)

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

Q^tQ=I_{n}

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

Q^{-1}=Q^t

איזה יופי, הא?

משפט

לכל מטריצה אורתונורמלית $Q$ מתקיים:

$Q$ הפיכה.
ההיפוך שלה הינו השחלוף שלה: $Q^{-1}=Q^t$ .

הוכחה: ראינו הנ"ל. (אפשר לפרמל כמובן)

משפט

תהי $Q$ מטריצה.

Q^tQ=I \iff \R{\text{ אורתונורמלית}} Q

הוכחה:
תהי $Q$ מטריצה ריבועית שהעמודות שלה הן הווקטורים $\underline{q}_{1},\dots ,\underline{q}_{n}$ .

\forall 1\leq i,j \leq n:\; (Q^tQ)_{ij}=\underline{q}_{i}^t\underline{q}_{j}=\langle \underline{q}_{i},\underline{q}_{j}\rangle

$\impliedby$ : ברור
$\implies$ : נתון כי $Q^tQ=I$ . אזי לפי הגדרת מטריצת היחידה מתקיים:

\langle \underline{q}_{i},\underline{q}_{j}\rangle =(Q^tQ)_{ij}=I_{ij}=\begin{cases} 1 & i=j \\ 0 & i\neq j \end{cases}

לכן, לפי הגדרה, הוקטורים $\underline{q}_{i},\underline{q}_{j}$ אורתוגונליים לכל $i,j$ ובנוסף לכל $i$ מתקיים כי $\left\lVert \underline{q}_{i} \right\rVert=1$ ולכן, לפי הגדרה עמודות $Q$ הינן בסיס אורתונורמלי ולכן, לפי הגדרה $Q$ מטריצה אורתונורמלית.
∎

משפט

שורות מטריצה אורתונורמלית $Q$ הינן גם קבוצה אורתונורמלית(קבוצה בה כל שני וקטורים אורתוגונליים)

הוכחה: (אין באמת הוכחות בקורס הזה אבל קל לראות לפי $Q^tQ=I=QQ^t$ )

משפט

תהי $Q$ מטריצה אורתונורמלית.

|Q|=\pm 1

הוכחה:

QQ^t=I \implies |QQ^t|=|I|=1

לפי משפט מאלגברה א', $|Q|=|Q^t|$ ולכן:

|QQ^t|=|Q|^2=|I|=1

|Q|=\pm \sqrt{ 1 }=\pm 1

∎

משפט

יהיו $Q_{1},Q_{2}$ מטריצות אורתונורמליות $\impliedby$ מכפלתן אורתונורמלית.

הוכחה:

(Q_{1}Q_{2})^t(Q_{1}Q_{2})=Q_{2}^tQ_{1}^tQ_{1}Q_{2}=Q_{2}^tQ_{2}=I

לכן, לפי משפט, $Q_{1}Q_{2}$ אורתונורמלית.
∎

משפט

תהי $Q$ מטריצה אורתונורמלית.

\left\lVert Q\underline{x} \right\rVert _{2}^2=\left\lVert \underline{x} \right\rVert _{2}^2

הוכחה:

\left\lVert Q\underline{x} \right\rVert _{2}^2=\underline{x}^tQ^tQ\underline{x}=\underline{x}^t\underline{x}=\left\lVert \underline{x} \right\rVert _{2}^2

∎

הערה

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

דוגמה

Q=\begin{pmatrix} 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}\implies Q^{-1}=Q^t=\begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}

נשים לב כי זוהי לא רק מטריצה אורתונורמלית אלא היא גם מטריצת פרמוטציה לפירוק $LU$ .

דוגמה (מטריצת סיבוב ב-

2D

)

\forall \theta \in[0,2\pi]:\; Q=\begin{pmatrix} \cos \theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}

מה המטריצה הזו עושה בעצם?
מטריצת סיבוב ב-2D - נומריים - אורתונורמליות ופירוק QR.svg

{\color{#DAA520} Q\begin{pmatrix} 1\\0 \end{pmatrix}=\begin{pmatrix} \cos\theta \\ \sin\theta \end{pmatrix}} \qquad \qquad {\color{#00BFFF}Q\begin{pmatrix} 0 \\ 1 \end{pmatrix}=\begin{pmatrix} -\sin\theta \\ \cos\theta \end{pmatrix}}

דוגמה (מטריצת שיקוף של הצירים ב-

2D

)

Q=\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \quad \qquad \quad Q=\begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix}

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

Givens

)

המטריצה מציעה סיבוב בין שני צירים בוקטור במימד גבוה.
נבנה אותה: מתחילים ממטריצת היחידה. אנו באים לשורה $j$ ועמודה $k$ וגם לעמודה $j$ ולשורה $k$ וזה יוצר לנו 4 איברים שבשניים מהם גרו במקור 1 ובשניים האחרים במקור גרו 0. נחליף את הרביעיה הזו ב- $\cos\theta,\sin\theta,-\sin\theta,\cos\theta$ ואז כאשר נכפיל את המטריצה בוקטור בגודל $n$ לרוב הערכים היא לא תעשה דבר, אבל בשני צירים היא תבצע את הסיבוב הזה.

G=\begin{pmatrix} 1 \\ & \ddots \\ & & \cos\theta & & & & -\sin\theta \\ & & & \ddots \\ & & & & 1 \\ & & & & & \ddots \\ & & \sin\theta & & & & \cos\theta \\ & & & & & & & \ddots \\ & & & & & & & & 1 \end{pmatrix}

דוגמה (מטריצת השיקוף של

Householder

)

יהי $\underline{v}$ וקטור כך ש- $\left\lVert \underline{v} \right\rVert=1$ (כלומר, $\underline{v}^t\underline{v}=1$ ). אזי המטריצה הינה:

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

היא אורתונורמלית, ונראה למה:

HH^t=(I-2\underline{v}\;\!\underline{v}^t)(I-2\underline{v}\;\!\underline{v}^t)=I-4\underline{v}\;\!\underline{v}^t+4\underline{v}\;\!\underline{v}^t\underline{v}\;\!\underline{v}^t=I-4I+4I=I

כנדרש.

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

כאשר אנו מכפילים בוקטור כללי $\underline{u}$ המקיים $\underline{v}^t\underline{u}=0$ אזי:

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

תהליך $Gram-Schmidt$

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

נתון סט של וקטורי כניסה כלשהם $\left\{ \underline{w}_{k} \right\}_{k=1}^L \in \mathbb{R}^n$ מהמרחב ה- $n$ מימדי.
תהליך גרם-שמיט( $GS$ ) יבנה מוקטורים אלה סדרת וקטורים אורתונורמלית עם $L$ או פחות וקטורים $\left\{ \underline{u}_{k} \right\}_{k=1}^L \in \mathbb{R}^n$ .
התהליך סדרתי ומקיים בל איטרציה:

sp\left\{ \underline{w}_{1},\dots,\underline{w}_{k} \right\}=sp\left\{ \underline{u}_{1},\dots,\underline{u}_{k} \right\}

משפט

בהינתן סט וקטורים כלשהו בת"ל $\left\{ \underline{w}_{k} \right\}_{k=1}^L \in \mathbb{R}^n$ המגדיר ת"מ, קיים בסיס אורתונורמלי תחליפי $\left\{ \underline{u}_{k} \right\}_{k=1}^L \in \mathbb{R}^n$ אשר יפרוש את אותו ת"מ.

sp\left\{ \underline{w}_{1},\dots,\underline{w}_{k} \right\}=sp\left\{ \underline{u}_{1},\dots,\underline{u}_{k} \right\}

את ההוכחה נראה דרך האלגוריתם הראשון שנראה.

אלגוריתם $\# 1$

מתקבל $\underline{w}_{1}$ וננרמל אותו: $\underline{u}_{1}=\frac{1}{\left\lVert \underline{w}_{1} \right\rVert_{2}}\underline{w}_{1}$ (אם זה $0$ אז נשמיט את הוקטור שכן אין לו השפעה על התהליך)
כעת, ברור שמתקיים $sp\left\{ \underline{w}_{1} \right\}=sp\left\{ \underline{u}_{1} \right\}$ .
מתקבל $\underline{w}_{2}$ . אנו נרצה שהוקטור $\underline{u}_{2}$ יקיים את התכונות: הנורמה=1, אנכי ל- $\underline{u}_{1}$ והספאן צריך להיות זהה למקור.
נעשה זאת באמצעות קילוף $\underline{u}_{1}$ מהוקטור $\underline{w}_{2}$ להשגת אנכיות:
$\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}$ . (אם הוקטור לפני נרמול מאופס, פירוש הדבר הוא שהוא נפרש מקודמו ולכן לא חשוב ונתעלם ממנו)
כעת, נוכל לראות כי הפרישות זהות:
$sp\left\{ \underline{u}_{1},\underline{u}_{2} \right\}\subseteq sp\left\{ \underline{w}_{1},\underline{w}_{2} \right\}$
ואז לפי משפט מאלגברה הם שווים כי המימדים שלהם זהים.
מתקבל $\underline{w}_{3}$ . כעת נעבוד בדרך דומה לממקודם:
$\underline{u}_{3}=\underline{w}_{3}-c_{1}\underline{u}_{1}-c_{2}\underline{u}_{2}$
כעת נדרוש: $\underline{u}_{1}^t(\underline{w}_{3}-c_{1}\underline{u}_{1}-c_{2}\underline{u}_{2})=0$ ואז:
$\underline{u}_{1}^t\underline{w}_{3}-c_{1}=0 \land \underline{u}_{2}^t\underline{w}_{3}-c_{2}=0$
הוקטור כעת לא מנורמל ולכן ננרמל אותו בדיוק כמו ממקודם. $\underline{u}_{3}=\frac{1}{\left\lVert \underline{u}_{3} \right\rVert_{2}}\underline{u}_{3}$ .
כעת אנו יודעים שהם פורשים את אותו הדבר במקור בדיוק מאותה סיבה כמו ממקודם.

כעת בצעד $k$ נבצע:

מתקבל $\underline{w}_{k}$ .
נגדיר: $\displaystyle \underline{u}_{k}=\underline{w}_{k}-\sum_{j=1}^{k-1}c_{j}\underline{u}_{j}$
נדרוש: $\left\{ \begin{matrix}0=\underline{u}_{1}^t\underline{u}_{k}=\underline{u}_{1}^t\underline{w}_{k}-c_{1}\implies c_{1}=\underline{u}_{1}^t\underline{w}_{k}\\ 0=\underline{u}_{2}^t\underline{u}_{k}=\underline{u}_{2}^t\underline{w}_{k}-c_{2}\implies c_{2}=\underline{u}_{2}^t\underline{w}_{k}\\ \vdots \\ 0=\underline{u}_{k-1}^t\underline{u}_{k}=\underline{u}_{k-1}^t\underline{w}_{k}-c_{k-1}\implies c_{k-1}=\underline{u}_{k-1}^t\underline{w}_{k}\end{matrix} \right\}$
נבצע נרמול(כמובן אם עובד, אחרת נתעלם מהוקטור): $\displaystyle \underline{u}_{k}=\frac{1}{\left\lVert \underline{u}_{k} \right\rVert_{2}}\underline{u}_{k}$

זהו בדיוק האלגוריתם. יש לו נוסחה סגורה וקל מאוד לתכנת אותו :)

אלגוריתם $\# 2$

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

\begin{align*} & \underline{w}_{1}=r_{11}\underline{u}_{1} \\ & \underline{w}_{2}=r_{21}\underline{u}_{1}+r_{22}\underline{u}_{2} \\ & \underline{w}_{3}=r_{31}\underline{u}_{1}+r_{32}\underline{u}_{2}+r_{33}\underline{u}_{3} \\ & \vdots \\ & \underline{w}_{L}=r_{L1}\underline{u}_{1}+r_{L2}\underline{u}_{2}+r_{L3}\underline{u}_{3}+\dots+r_{LL}\underline{u}_{L} \end{align*}

ברור שאת המקדם $r_{11}$ ניתן לקבוע כמו באלגוריתם הקודם ע"י נרמול של הוקטור $\underline{w}_{1}$ . כלומר, $r_{11}^2=\left\lVert \underline{w}_{1} \right\rVert_{2}^2$ .
מהמשוואה השנייה נקבל די בקלות: $\underline{u}_{2}=\frac{1}{r_{22}}(\underline{w}_{2}-r_{21}\underline{u}_{1})$ נוכל למצוא את $r_{21}$ בקלות בשל האנכיות של $\underline{u}_{1}$ של $\underline{u}_{2}$ כך:

\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}

את המקדם $r_{22}$ נקבע על מנת לקבל נרמול של $\underline{u}_{2}$ כך:

\left\lVert \underline{w}_{2} \right\rVert _{2}^2 =\left\lVert r_{21}\underline{u}_{1}+r_{22}\underline{u}_{2} \right\rVert _{2}^2=r_{21}^2+r_{22}^2\implies r_{22}=\pm \sqrt{ \left\lVert \underline{w}_{2} \right\rVert_{2}^2 -r_{21}^2 }

כעת, נעשה זאת באופן כללי למשוואה ה- $k$ -ית:

\underline{w}_{k}=r_{k1}\underline{u}_{1}+r_{k2}\underline{u}_{2}+\dots+{r}_{kk}\underline{u}_{k}

נמצא את $k-1$ המקדמים הראשונים לפי אנכיות הוקטורים האורתונורמליים. יהי $j=1,2,\dots,k-1$ אזי:

\underline{u}_{j}^t\underline{w}_{k}=r_{kj}

את המקדם $r_{kk}$ נקבע כך:

r_{kk}=\pm \sqrt{ \left\lVert \underline{w}_{k} \right\rVert_{2}^2-\sum_{j=1}^{k-1} r_{kj}^2 }

אלגוריתם $\#3$

מתקבל $\underline{w}_{1}$ . ננרמל אותו לקבלת $\underline{u}_{1}=\frac{1}{\left\lVert \underline{w}_{1} \right\rVert_{2}}\underline{w}_{1}$ .
ננקה את כל הוקטורים הנתונים ע"י קילוף $\underline{u}_{1}$ מתוכם. נעשה זאת כך:
$\forall 2\leq j\leq L:\; \underline{w}_{j}=\underline{w}_{j}-(\underline{u}_{1}^t\underline{w}_{j})\underline{u}_{1}$
מתקבל $\underline{w}_{2}$ . ננרמל אותו לקבלת $\underline{u}_{2}=\frac{1}{\left\lVert \underline{w}_{2} \right\rVert_{2}}\underline{w}_{2}$ . כעת, ננקה את שאר הוקטורים:
$\forall 3\leq j\leq L:\; \underline{w}_{j}=\underline{w}_{j}-(\underline{u}_{2}^t\underline{w}_{j})\underline{u}_{2}$

בצעד ה- $k$ מתקבל $\underline{w}_{k}$ . ננרמל אותו: $\underline{u}_{k}=\frac{1}{\left\lVert \underline{w}_{k} \right\rVert_{2}}\underline{w}_{k}$ ואז ננקה את שאר הוקטורים: $\forall k+1\leq j\leq L:\; \underline{w}_{j}=\underline{w}_{j}-(\underline{u}_{k}^t\underline{w}_{j})\underline{u}_{k}$ וזה הכל.

Algorithm 2 Stable Gram-Schmidt (SGS)

Input: A set of linearly independent vectors $W = \{w_1, w_2, \dots, w_L\}$

Output: An orthonormal basis $U = \{u_1, u_2, \dots, u_L\}$

1:for $k = 1$ to $L$ do

2: $u_k \gets \frac{w_k}{\|w_k\|_2}$ // Normalization step

3:for $j = k+1$ to $L$ do

4: $w_j \gets w_j - (u_k^T w_j) u_k$ // Orthogonalization (peeling) step

5:end for

6:end for

7:return $U$

סיבוכיות האלגוריתמים

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

כל פעולת רנמול דורשת $2n$ פעולות.
כל פעולת קילוף דורשת $2n$ פעולות.

נסתכל על כל האלגוריתם:

בצעד הראשון יש נרמול אחד ו- $n-1$ קילופים
בצעד השני יש נרמול אחד ו- $n-2$ קילופים

וכך הלאה ולכן נקבל שמספר הפעולות הוא $L+\frac{L(L-1)}{2}$ פעולות ולכן הסיבוכיות היא $\Theta(nL^2)$ .

פירוק $QR$

נסתכל שוב על האלגוריתם השני, ה-Modified Gram-Schmidt ועל המשוואות שאנו מקבלים:

\begin{align*} & \underline{w}_{1}=r_{11}\underline{u}_{1} \\ & \underline{w}_{2}=r_{21}\underline{u}_{1}+r_{22}\underline{u}_{2} \\ & \underline{w}_{3}=r_{31}\underline{u}_{1}+r_{32}\underline{u}_{2}+r_{33}\underline{u}_{3} \\ & \vdots \\ & \underline{w}_{L}=r_{L1}\underline{u}_{1}+r_{L2}\underline{u}_{2}+r_{L3}\underline{u}_{3}+\dots+r_{LL}\underline{u}_{L} \end{align*}

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

A=\begin{pmatrix} \vert & \vert & \vert & & \vert \\ \underline{w}_{1} & \underline{w}_{2} & \underline{w}_{3} & \dots & \underline{w}_{L} \\ \vert & \vert & \vert & & \vert \end{pmatrix}

נקח גם את ה- $\underline{u}$ -ים ונשים גם אותם במטריצה:

Q=\begin{pmatrix} \vert & \vert & \vert & & \vert \\ \underline{u}_{1} & \underline{u}_{2} & \underline{u}_{3} & \dots & \underline{u}_{L} \\ \vert & \vert & \vert & & \vert \end{pmatrix}

נרצה לראות איזה קשר יש בין $Q$ ל- $A$ . מהמשוואות פשוט אפשר לראות כי מתקיים:

A=Q\begin{pmatrix} r_{11} & r_{21} & r_{31} & \dots & r_{L1} \\ 0 & r_{22} & r_{32} & \dots & r_{L2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & r_{LL} \end{pmatrix}=QR

בואו נשתכנע שזה נכון.

נתחיל בלהוציא עמודה אחת מהמטריצה באמצעות וקטור שכולו אפסים חוץ מ- $1$ אחד בלבד. אורך הוקטור הזה הוא $L$ . נקבל:

\begin{align*} \underline{w}_{1}=\begin{pmatrix} \vert & \vert & \vert & & \vert \\ \underline{w}_{1} & \underline{w}_{2} & \underline{w}_{3} & \dots & \underline{w}_{L} \\ \vert & \vert & \vert & & \vert \end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix}&=\begin{pmatrix} \vert & \vert & \vert & & \vert \\ \underline{u}_{1} & \underline{u}_{2} & \underline{u}_{3} & \dots & \underline{u}_{L} \\ \vert & \vert & \vert & & \vert \end{pmatrix}\begin{pmatrix} r_{11} & r_{21} & r_{31} & \dots & r_{L1} \\ 0 & r_{22} & r_{32} & \dots & r_{L2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & r_{LL} \end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix} \\ &=\begin{pmatrix} \vert & \vert & \vert & & \vert \\ \underline{u}_{1} & \underline{u}_{2} & \underline{u}_{3} & \dots & \underline{u}_{L} \\ \vert & \vert & \vert & & \vert \end{pmatrix}\begin{pmatrix} r_{11} \\ 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix}=r_{11}\underline{u}_{1} \end{align*}

קיבלנו בדיוק את המשוואה. כעת נבדוק האם זה גם מתקיים למשוואה השנייה:

\begin{align*} \underline{w}_{2}=\begin{pmatrix} \vert & \vert & \vert & & \vert \\ \underline{w}_{1} & \underline{w}_{2} & \underline{w}_{3} & \dots & \underline{w}_{L} \\ \vert & \vert & \vert & & \vert \end{pmatrix}\begin{pmatrix} 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}&=\begin{pmatrix} \vert & \vert & \vert & & \vert \\ \underline{u}_{1} & \underline{u}_{2} & \underline{u}_{3} & \dots & \underline{u}_{L} \\ \vert & \vert & \vert & & \vert \end{pmatrix}\begin{pmatrix} r_{11} & r_{21} & r_{31} & \dots & r_{L1} \\ 0 & r_{22} & r_{32} & \dots & r_{L2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & r_{LL} \end{pmatrix}\begin{pmatrix} 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix} \\ &=\begin{pmatrix} \vert & \vert & \vert & & \vert \\ \underline{u}_{1} & \underline{u}_{2} & \underline{u}_{3} & \dots & \underline{u}_{L} \\ \vert & \vert & \vert & & \vert \end{pmatrix}\begin{pmatrix} r_{21} \\ r_{22} \\ 0 \\ \vdots \\ 0 \end{pmatrix}=r_{21}\underline{u}_{1}+r_{22}\underline{u}_{2} \end{align*}

זה גם בדיוק המשוואה שקיבלנו.
כך, אם נמשיך הלאה גם נקבל את כל השאר(הוכחה? לא בקורס הזה)

מה קורה אם $A$ ריבועית והפיכה? אם היא תוזן לתהליך גרם-שמידט הכל ילך ללא בעיות.
נקבל גם כי $A=QR$ כאשר $Q$ תהיה מטריצה אורתונורמלית, שכן היא ריבועית ועמודותיה הן ה- $\underline{u}$ -ים שמצאנו בהתליך גרם-שמידט.

משפט

כל מטריצה ריבועית והפיכה $A$ ניתנת לפירוק יחיד מהצורה $A=QR$ כאשר:

$Q$ מטריצה אורתונורמלית
$R$ מטריצה משולשת עליונה בה איברי האלכסון הראשי כולם חיוביים.

הוכחה(שהיא בצעם רעיון ההוכחה): כיוון שמהטריצה הפיכה, עמודותיה בת" ולכן בתהליך ה- $GS$ יתקבלו $n$ וקטורי מוצא ואלו ייצרו מטריצה אורתונורמלית.
היחידות נובעת מדרישות החיוביות של איברי האלכסון של $R$ כפי שמתקבלים באופן יחיד מאלגוריתם ה- $MGS$ .

פירוק $QR$ קיים גם למטריצות שאינן הפיכות. אז יתקבלו ערכי $0$ באלכסון הראשי של $R$ .

דוגמה

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

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

A=QR=\begin{pmatrix} 0.5 & -0.5 & 0.707 & 0 \\ 0.5 & -0.5 & -0.707 & 0 \\ 0.5 & 0.5 & 0 & -0.707 \\ 0.5 & 0.5 & 0 & 0.707 \end{pmatrix}\begin{pmatrix} 2 & 1 & 5 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & -0.707 \\ 0 & 0 & 0 & 0.707 \end{pmatrix}

נשים לב כי נוצרו לנו $4$ וקטורים אורתונורמליים - איך? הרי אחד מהוקטורים המקוריים אינו בת"ל עם האחרים.
נשים לב כי קיבלנו ב- $R$ אזהרה בדמות $0$ באלכסון שאומר לנו שהעמודה השלישית שלנו היא לא הכי בריאה.

נראה כעת איך פותרים את הבעיה שהוצגה בדוגמה.
נתונה המטריצה $A$ ועליה אנו מבצעים גרם-שמידט.

בתהליך הגרם שמידט: אם נתקלת בעמודה ב- $A$ תלויה בקודמיה, זרוק אותה והמשך בתהליך
בתהליך פירוק $QR$ : אם נתקלת בעמודה התלויה בקודמיה, אי אפשר לזרוקה! לכן:
1. הצג אותה כצירוף של הוקטורים שכבר נוצרו.
2. הגרל/בחר וקטור חדש שימלא את מקומה להמשך תהליך הגרם-שמידט

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

פירוק $QR$ למטריצות שאינן ריבועיות

פירוק $QR$ קיים גם למטריצות מלבניות מכל צורה שהיא.
כשהמטריצה רחבה ונמוכה, עמודותיה חייבות להיות ת"ל. אם נניח ש- $n$ העמודות הראשונות בת"ל, נקבל כי יתר העמודות תלויות בהן, לכן, עמודות $R$ המתאימות מלאות.
3 - אורתוגונליות ופירוק QR 2026-06-01 11.41.49.excalidraw.svg
כדי למצוא את שאר עמודות המטריצה לאחר האלגוריתם למטריצות ריבועיות שיצר את $Q$ נוכל לבצע:

\underline{w}_{7}=Q\underline{r}_{7} \implies \underline{r}_{7}=Q^{t}\underline{w}_{7}

כעת, המטריצה שלנו גבוהה וצרה. ניתן להציע שני מבני פירוק - האחד עם $Q$ מלאה שבה מוסיפים וקטורי סרק לעמודותיה של $Q$ להשלמת מטריצה אורתונורמלית.
3 - אורתוגונליות ופירוק QR 2026-06-01 11.45.39.excalidraw.svg
הגישה האחרת קרויה $Economy\; QR$ והיא מסתפרת ב- $Q$ ברוחב $A$ .

שימושי הפירוק

שימוש ב- $QR$ לפתרון מערכות משוואות

נתונה לנו מערכת משוואות $A\underline{x}=\underline{b}$ נוכל להשתמש בפירוק $QR$ על מנת לפתורה. נדון בשלושה מקרים:

$A$ ריבועית והפיכה
$A$ מלבנית עם יותר שורות מעמודות
$A$ מלבנית עם יותר עמודות משורות

מקרה 1

נתחיל בפירוק $A$ ל- $QR$ :

A\underline{x}=QR\underline{x}=\underline{b}

כעת, נכפיל ב- $Q^t$ :

R\underline{x}=Q^t\underline{b}

כעת, באמצעות החלפה אחורית נוכל למצוא את $\underline{x}$ .

למה זה לא טוב? עלה לנו $n^3$ כדי להשיג את $QR$ . אך פירוק $LU$ כולו הוא $\frac{n^3}{3}$ ולכן הוא עדיף.
אז למה אנו רואים את זה? את זה אנו נגלה עוד מעט.

מקרה 2

נתחיל בפירוק $A$ ל- $QR$ המלא(לא $Economy$ ) על מנת לקבל מטריצה ריבועית $Q$ .
נכפיל את הוקטור $\underline{b}$ ב- $Q^t$ .
כעת עלינו לפתור את המערכת הנותרת ע"י החלפה אחורית, אלא שתחתית המטריצה $R$ מאופסת ולכן החלק התחתון בוקטור $Q^t\underline{b}$ חייב להיות 0 על מנת להבטיח פתרון.
⇐ אם החלק התחתון אינו מאופס, לא קיים פתרון למערכת.

מקרה 3

$A$ מלבנית רחבה ונניח שוב כי דרגתה מלאה. נתחיל בפירוק $QR$ ונכפיל את הוקטור $\underline{b}$ ב- $Q^t$ .
המערכת שנותרה מספרת על דרגות החופש הקיימות במערכת המקורית.

שימוש בפירוק לפתרון בעיית ריבועים פחותים

נניח כי עלינו לפתור את בעיית הריבועים הפחותים $\underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2$ ונניח כי יש לבעיה הזו פתרון יחיד(כלומר, $A$ ריבועית או מלבנית גבוהה ודרגתה מלאה)
נתחיל בפירוק $A$ ל- $QR$ . פירוק זה אינו ה- $Economy$ על מנת לקבל מטריצה $Q$ ריבועית. אזי:

\left\lVert QR\underline{x}-\underline{b} \right\rVert _{2}^2=\left\lVert Q(R\underline{x}-Q^t\underline{b}) \right\rVert _{2}^2 \underset{\begin{matrix} \downarrow \\ \R{\text{משפט}} \end{matrix}}{=}\left\lVert R\underline{x}-Q^t\underline{b} \right\rVert _{2}^2=\left\lVert Q^t\underline{b}-R\underline{x} \right\rVert _{2}^2

[אפשר להוסיף ציור אם יהיה לי כח אחר כך]
ניתן לפצל את וקטור השגיאה לשני חלקים נפרדים והשגיאה הכוללת היא סכום שתי השגיאות הללו.

את הרכיב הראשון ניתן להביא לערך $0$ ע"י פתרון של החלפה אחורית.
החלק הנותר לא ניתן לשינוי. סכום ריבועיו של החלק התחתון של $Q^t\underline{b}$ קובעים את גובה המינימום של הבעיה הריבועית.

הערה

יכולנו להשתמש ב- $Economy\; QR$ לחישוב הפתרון.

סיבוכיות התהליך הזה

נניח שאנו פועלים עם מטריצה $A$ בגודל $m \times n$ .

בתהליך עם פירוק $QR$ נקבל:

חישוב ה- $Economy-QR$ חמטריצה ידרוש $mn^2$ - זהו החלק הדומיננטי במלא התהליך.
הכפלת הוקטור $\underline{b}$ ב- $Q^t$ תדרוש $nm$ פעולות.
פעולת ההחלפה האחורית תדרוש $\frac{n^2}{2}$ פעולות.

מהי החלופה? חישוב $A^tA$ ופתרון באמצעות פירוק $Cholesky$ .

חישוב $A^tA$ דורש $mn^2$ פעולות
פירוק $Cholesky$ ידרוש $\frac{n^3}{6}$ פעולות
החלפה קדמית ואחרוית ב- $n^2$ פעולות

לכן, בשביל לפתור בעיית ריבועים פחותים, הרבה יותר עדיף להשתמש בפירוק $QR$ מאשר הדרכים הרגילות.

סדרה של בעיות ריבועים פחותים

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

\left\{ \underset{\underline{x}_{k}}{\min}\left\lVert A_{k}\underline{x}_{k}-\underline{b} \right\rVert_{2}^2 \right\}_{k=1}^L

כאשר מספר עמודות $A_{k}$ הוא בדיוק $k$ ו- $k-1$ העמודות הראשונות שלה הן עמודות $A_{k-1}$ .
למה זה מעניין? למשל, בקירוב פולינומיאלי, הדבר שקול לבניית סדרת קירובים עם דרגת פולינום הולכת ועולה.

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

\underset{\underline{x}}{\min}\left\lVert A_{L}\underline{x}-\underline{b} \right\rVert _{2}^2=\underset{\underline{x}}{\min}\left\lVert R_{L}\underline{x}-Q_{L}^t\underline{b} \right\rVert _{2}^2

נשים לב כי לאור העובדה שתהליך הגרם-שמידט הוא סדרתי, פירוק ה- $QR$ של המטריצה $A_{L-1}$ מוכל בפירוק של $A_{L}$ .
לכן, נבצע פירוק $QR$ יחיד ואז פשוט נשתמש בחלקים של המטריצות שאנו צריכים על מנת לפתור את הבעיה.

הערה

השימוש ב- $QR$ נותן יתרון חדש ומעניין: אם נרצה לדעת את הפתרון לאותה בעיה אך עבור שימוש ב- $k<L$ העמודות הראשונות של $A_{L}$ בלבד, פתרון זה נגיש - לשם כך, נקח את החלק העליון של הוקטור $Q^t\underline{b}$ ואת החלק העליון של המטריצה $R$ ונפתור מערכת משוואות זו.

3 - אורתוגונליות ופירוק QR

אלגוריתמים נומריים

אורתוגונליות ופירוק QR

3 - אורתוגונליות ופירוק QR

אלגוריתמים נומריים

אורתוגונליות ופירוק QR

מטריצות אורתונומרליות