7 - פירוק QR — אלגוריתמים נומריים

משפט

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

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

מה קורה כאשר אחת העמודות תלויה בקודמויה? פירוש הדבר שהמטריצה $A$ אינה הפיכה.
תהליך $GS$ יניב $n-1$ וקטורים אורתונורמליים לכן, כל פעם שאנו מקבלים עמודה פגומה נחליף אותה בווקטור בת"ל שרירותי ועליו נפעיל את $GS$ .

משפט

תהא $A \in \mathbb{R}^{n\times m}$ אז קיים פירוק $QR$ כך ש- $Q \in \mathbb{R}^{n\times m}$ אורתונורמלית ו- $R \in \mathbb{R}^{n\times m}$ "משולשת עליונה".

A=QR

תרגיל

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

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

א. בצעו את תהליך גרם-שמידט על עמודות המטריצה.
ב. מהו פירוק ה- $QR$ למטריצה זו?

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

\underline{u}_{1}=\frac{1}{\left\lVert \begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix} \right\rVert }\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}=\frac{1}{\sqrt{ 3 }}\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}

\underline{v}_{2}=\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1}=\frac{1}{3}\begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix} \underset{\begin{matrix} \downarrow \\ \R{\text{הסקלר לא משנה שכן לאחר מכן אנו מנרמלים}} \end{matrix}}{=} \begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix}

\underline{v}_{3}=\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}=\begin{pmatrix} 3 \\ -1 \\ 2 \end{pmatrix}

\underline{v}_{4}=\underline{w}_{4}-\underline{u}_{1}^t\underline{w}_{4}\underline{u}_{1}=\frac{1}{3}\begin{pmatrix} -1 \\ 5 \\ 4 \end{pmatrix}\underset{\begin{matrix} \downarrow \\ \R{\text{הסקלר לא משנה שכן לאחר מכן אנו מנרמלים}} \end{matrix}}{=}\begin{pmatrix} -1 \\ 5 \\ 4 \end{pmatrix}

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

\underline{u}_{2}=\frac{1}{\left\lVert \begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix} \right\rVert }\begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix}=\frac{1}{\sqrt{ 45 }}\begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix}

\underline{v}_{3}=\underline{v}_{3}-\underline{u}_{2}^t\underline{v}_{3}\underline{u}_{2}=\frac{1}{2}\begin{pmatrix} 2 \\ -3 \\ -1 \end{pmatrix}

\underline{v}_{4}=\underline{v}_{4}-\underline{u}_{2}^t\underline{v}_{4}\underline{u}_{2}=\frac{1}{2}\begin{pmatrix} -6 \\ 9 \\ 3 \end{pmatrix}

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

\underline{u}_{3}=\frac{1}{\sqrt{ 14 }}\begin{pmatrix} 2 \\ -3 \\ -1 \end{pmatrix}

מכיוון שזה הצטרף למשפחת האורתונרומליים אנו יודעים כי בהכרח $\underline{v}_{4}=0$ .
פה סיימנו את גרם שמידט שכן קיבלנו בסיס לתת מרחב של $\mathbb{R}^3$ שהוא מרחב העמודות של המטריצה והוא:

\left\{ \frac{1}{\sqrt{ 3 }}\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}, \frac{1}{\sqrt{ 42 }}\begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix}, \frac{1}{\sqrt{ 14 }}\begin{pmatrix} 2 \\ -3 \\ -1 \end{pmatrix} \right\}

פתרון ב':
ממה שמצאנו עכשיו נרצה למצוא את $QR$ .
לפי גרם-שמידט אנו כבר יודעים מהי המטריצה האורתונרומלית:

Q=\begin{pmatrix} \frac{1}{\sqrt{ 3 }} & \frac{4}{\sqrt{ 42 }} & \frac{2}{\sqrt{ 14 }} \\ \frac{1}{\sqrt{ 3 }} & \frac{1}{\sqrt{ 42 }} & -\frac{3}{\sqrt{ 14 }} \\ -\frac{1}{\sqrt{ 3 }} & \frac{5}{\sqrt{ 42 }} & -\frac{1}{\sqrt{ 14 }} \end{pmatrix}

עכשיו כדי למצוא את $R$ נוכל לבצע כפל מטריצות עם $W$ ו- $Q^t$ שכן $A=QR$ ולכן, מכיוון ש- $Q$ אורתונורמלית, $R=Q^tA$ .
כך נקבל:

R=\begin{pmatrix} \frac{3}{\sqrt{ 3 }} & -\frac{1}{\sqrt{ 3 }} & -\frac{3}{\sqrt{ 3 }} & \frac{1}{\sqrt{ 3 }} \\ 0 & \frac{14}{\sqrt{ 42 }} & \frac{21}{\sqrt{ 42 }} & \frac{7}{\sqrt{ 42 }} \\ 0 & 0 & \frac{7}{\sqrt{ 14 }} & -\frac{7}{\sqrt{ 14 }} \end{pmatrix}

וזוהי התשובה שלנו.

תרגיל

נתונה מטריצה $A$ שהעמודה ה- $i$ שלה היא: $\displaystyle A_{i}=\sum_{k=1}^i e_{i}$ .
א. מצאו את פירוק $QR$ שלה.
ב. כעת נתונה מטריצה $G$ משולשת עליונה והפיכה. אז מהו פירוק $QR$ של $GA$ ? (כך ש- $R$ חיובית באלכסון)
ג. המטריצה $C$ נבנית כך שעמודות $A$ הם וקטורים עצמיים שלה עם ע"ע שונים מאפס. מה יתקבל בתהליך גרם-שמידט עבור עמודות $C$ ?

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

Q=I

כאשר:

R=Q^tA=A

אז פירוק $QR$ הוא:

A=IA

(ואוו כזה מפתיע)

פתרון ב':
נשים לב כי מתקיים $GA=I\cdot GA$ כי מכפלה של משולשות עליונות היא משולשת עליונה.

\forall 1\leq i\leq n:\;\;Q_{i}=\begin{cases} -e_{i} & (GA)_{ii}<0 \\ e_{i} & else \end{cases}

R_{row-i}=\begin{cases} -(GA)_{row-i} & (GA)_{ii}<0 \\ (GA)_{row-i} & else \end{cases}

ואלו בדיוק המטריצות שלנו.

פתרון ג':
נשים לב כי $C$ יש $n$ מ"ע אשר פורשים את המרחב. (למה? דנה נמה) וגם מתקיים $C=ADA^{-1}$ .
מכיוון שכל המטריצות $A,D,A^{-1}$ הן משולשות עליונות אזי $C$ משולשת עליונה.
לפי סעיף קודם נדע כי יתקבל בגרם שמידט:

\left\{-e_{j}| (C)_{jj}< 0 \right\} \cup \left\{ e_{j}| (C)_{jj}\geq 0 \right\}

משפט

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

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

משפט

תהא $A \in \mathbb{R}^{n\times m}$ אז קיים פירוק $QR$ כך ש- $Q \in \mathbb{R}^{n\times m}$ אורתונורמלית ו- $R \in \mathbb{R}^{n\times m}$ "משולשת עליונה".

A=QR

תרגיל

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

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

א. בצעו את תהליך גרם-שמידט על עמודות המטריצה.
ב. מהו פירוק ה- $QR$ למטריצה זו?

\underline{u}_{1}=\frac{1}{\left\lVert \begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix} \right\rVert }\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}=\frac{1}{\sqrt{ 3 }}\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}

\underline{v}_{2}=\underline{w}_{2}-\underline{u}_{1}^t\underline{w}_{2}\underline{u}_{1}=\frac{1}{3}\begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix} \underset{\begin{matrix} \downarrow \\ \R{\text{הסקלר לא משנה שכן לאחר מכן אנו מנרמלים}} \end{matrix}}{=} \begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix}

\underline{v}_{3}=\underline{w}_{3}-\underline{u}_{1}^t\underline{w}_{3}\underline{u}_{1}=\begin{pmatrix} 3 \\ -1 \\ 2 \end{pmatrix}

\underline{v}_{4}=\underline{w}_{4}-\underline{u}_{1}^t\underline{w}_{4}\underline{u}_{1}=\frac{1}{3}\begin{pmatrix} -1 \\ 5 \\ 4 \end{pmatrix}\underset{\begin{matrix} \downarrow \\ \R{\text{הסקלר לא משנה שכן לאחר מכן אנו מנרמלים}} \end{matrix}}{=}\begin{pmatrix} -1 \\ 5 \\ 4 \end{pmatrix}

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

\underline{u}_{2}=\frac{1}{\left\lVert \begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix} \right\rVert }\begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix}=\frac{1}{\sqrt{ 45 }}\begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix}

\underline{v}_{3}=\underline{v}_{3}-\underline{u}_{2}^t\underline{v}_{3}\underline{u}_{2}=\frac{1}{2}\begin{pmatrix} 2 \\ -3 \\ -1 \end{pmatrix}

\underline{v}_{4}=\underline{v}_{4}-\underline{u}_{2}^t\underline{v}_{4}\underline{u}_{2}=\frac{1}{2}\begin{pmatrix} -6 \\ 9 \\ 3 \end{pmatrix}

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

\underline{u}_{3}=\frac{1}{\sqrt{ 14 }}\begin{pmatrix} 2 \\ -3 \\ -1 \end{pmatrix}

\left\{ \frac{1}{\sqrt{ 3 }}\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}, \frac{1}{\sqrt{ 42 }}\begin{pmatrix} 4 \\ 1 \\ 5 \end{pmatrix}, \frac{1}{\sqrt{ 14 }}\begin{pmatrix} 2 \\ -3 \\ -1 \end{pmatrix} \right\}

פתרון ב':
ממה שמצאנו עכשיו נרצה למצוא את $QR$ .
לפי גרם-שמידט אנו כבר יודעים מהי המטריצה האורתונרומלית:

Q=\begin{pmatrix} \frac{1}{\sqrt{ 3 }} & \frac{4}{\sqrt{ 42 }} & \frac{2}{\sqrt{ 14 }} \\ \frac{1}{\sqrt{ 3 }} & \frac{1}{\sqrt{ 42 }} & -\frac{3}{\sqrt{ 14 }} \\ -\frac{1}{\sqrt{ 3 }} & \frac{5}{\sqrt{ 42 }} & -\frac{1}{\sqrt{ 14 }} \end{pmatrix}

עכשיו כדי למצוא את $R$ נוכל לבצע כפל מטריצות עם $W$ ו- $Q^t$ שכן $A=QR$ ולכן, מכיוון ש- $Q$ אורתונורמלית, $R=Q^tA$ .
כך נקבל:

R=\begin{pmatrix} \frac{3}{\sqrt{ 3 }} & -\frac{1}{\sqrt{ 3 }} & -\frac{3}{\sqrt{ 3 }} & \frac{1}{\sqrt{ 3 }} \\ 0 & \frac{14}{\sqrt{ 42 }} & \frac{21}{\sqrt{ 42 }} & \frac{7}{\sqrt{ 42 }} \\ 0 & 0 & \frac{7}{\sqrt{ 14 }} & -\frac{7}{\sqrt{ 14 }} \end{pmatrix}

וזוהי התשובה שלנו.

תרגיל

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

Q=I

כאשר:

R=Q^tA=A

אז פירוק $QR$ הוא:

A=IA

(ואוו כזה מפתיע)

פתרון ב':
נשים לב כי מתקיים $GA=I\cdot GA$ כי מכפלה של משולשות עליונות היא משולשת עליונה.

\forall 1\leq i\leq n:\;\;Q_{i}=\begin{cases} -e_{i} & (GA)_{ii}<0 \\ e_{i} & else \end{cases}

R_{row-i}=\begin{cases} -(GA)_{row-i} & (GA)_{ii}<0 \\ (GA)_{row-i} & else \end{cases}

ואלו בדיוק המטריצות שלנו.

\left\{-e_{j}| (C)_{jj}< 0 \right\} \cup \left\{ e_{j}| (C)_{jj}\geq 0 \right\}