תרגיל 1
הציעו דרך לחשב את פירוק שור של מטריצה לכסינה A A A Q R QR QR A A A
כיוון שהמטריצה לכסינה, קיימים S S S D D D S − 1 A S S^{-1}AS S − 1 A S S S S Q R QR QR S = Q R S=QR S = QR S S S R R R
S − 1 A S = ( Q R ) − 1 A ( Q R ) = R − 1 Q H A Q R = D S^{-1}AS=(QR)^{-1}A(QR)=R^{-1}Q^HAQR=D S − 1 A S = ( QR ) − 1 A ( QR ) = R − 1 Q H A QR = D נעביר את ההכפלות של R R R
Q H A Q = R D R − 1 = T Q^HAQ=RDR^{-1}=T Q H A Q = R D R − 1 = T T T T
הראו שמטריצה סימטרית חיובית מוגדרת A A A A = M M t A=MM^t A = M M t M M M הדרכה: השתמשו בעבודה שמטריצה סימטרית חיובית מוגדרת ניתנת לפירוק ספקטרלי ולאחר מכן השתמשו בפירוק Q R QR QR
המטריצה A A A Q Q Q D D D
A = Q D Q t = Q D 1 2 D 1 2 Q t = B B t A=QDQ^t=QD^{\frac{1}{2}}D^{\frac{1}{2}}Q^t=BB^t A = Q D Q t = Q D 2 1 D 2 1 Q t = B B t נבצע פירוק Q R QR QR B t B^t B t B t = Q R B^t=QR B t = QR B = R t Q t B=R^tQ^t B = R t Q t
A = R t Q t Q R = R t R A=R^tQ^tQR=R^tR A = R t Q t QR = R t R R t R^t R t Q R QR QR A A A
תרגיל 2
ראינו בכיתה כי עבור מטריצה A ∈ R m × n A \in \mathbb{R}^{m\times n} A ∈ R m × n r r r A = U Σ V t A=U\Sigma V^t A = U Σ V t U ∈ R m × m U \in \mathbb{R}^{m\times m} U ∈ R m × m V ∈ R n × n V \in \mathbb{R}^{n\times n} V ∈ R n × n Σ = d i a g ( σ 1 , … , σ r , 0 , … , 0 ) ∈ R m × n \Sigma=diag(\sigma_{1},\dots,\sigma_{r},0,\dots,0)\in \mathbb{R}^{m\times n} Σ = d ia g ( σ 1 , … , σ r , 0 , … , 0 ) ∈ R m × n A † = V Σ † U t A^{\dagger}=V\Sigma ^{\dagger}U^t A † = V Σ † U t Σ † = d i a g ( 1 σ 1 , … , 1 σ r , 0 , … , 0 ) \Sigma ^{\dagger}=diag\left( \frac{1}{\sigma_{1}},\dots, \frac{1}{\sigma_{r}},0,\dots,0 \right) Σ † = d ia g ( σ 1 1 , … , σ r 1 , 0 , … , 0 )
הראו כי ( A † ) t = ( A t ) † (A^{\dagger})^t=(A^t)^{\dagger} ( A † ) t = ( A t ) †
הוכחה:
( A † ) t = ( V Σ † U t ) t = U ( Σ † ) t V t = U ( Σ † ) t V t = ( V Σ t U t ) † = ( ( U Σ V t ) t ) † = ( A t ) † (A^{\dagger})^t=(V\Sigma ^{\dagger}U^t)^t=U(\Sigma ^{\dagger})^tV^t=U(\Sigma ^{\dagger})^tV^t=(V\Sigma^t U^t)^{\dagger}=((U\Sigma V^t)^t)^{\dagger}=(A^t)^{\dagger} ( A † ) t = ( V Σ † U t ) t = U ( Σ † ) t V t = U ( Σ † ) t V t = ( V Σ t U t ) † = (( U Σ V t ) t ) † = ( A t ) † ∎
הראו כי במקרה בו A A A A † = ( A t A ) − 1 A t A^{\dagger}=(A^tA)^{-1}A^t A † = ( A t A ) − 1 A t
הוכחה:
( A t A ) − 1 A t = ( V Σ t U t U Σ V t ) − 1 V Σ t U t = ( V Σ t Σ V t ) − 1 V Σ t U t = ↓ V − 1 = V t V ( Σ t Σ ) − 1 V t V Σ t U t = ↓ V t V = I V ( Σ t Σ ) − 1 Σ t U t (A^tA)^{-1}A^t\!=\!(V\Sigma^t U^tU\Sigma V^t)^{-1}V\Sigma^t U^t\!=\!(V\Sigma^t\Sigma V^{t})^{-1}V\Sigma^t U^t \!\!\!\!\!\!\!\underset{\begin{matrix}
\downarrow \\
V^{-1}=V^t
\end{matrix}}{=}\!\!\!\!\!\!\! V(\Sigma^{t}\Sigma)^{-1}V^tV\Sigma^t U^t \!\!\!\!\!\underset{\begin{matrix}
\downarrow \\
V^tV=I
\end{matrix}}{=}\!\!\!\!\!\!V(\Sigma^t\Sigma)^{-1}\Sigma^t U^t ( A t A ) − 1 A t = ( V Σ t U t U Σ V t ) − 1 V Σ t U t = ( V Σ t Σ V t ) − 1 V Σ t U t ↓ V − 1 = V t = V ( Σ t Σ ) − 1 V t V Σ t U t ↓ V t V = I = V ( Σ t Σ ) − 1 Σ t U t נשים לב כי A A A Σ \Sigma Σ Σ \Sigma Σ
( Σ t Σ ) − 1 = ( Σ − 1 ) 2 = ( 1 σ 1 2 1 σ 2 2 ⋱ 1 σ n 2 ) (\Sigma^t\Sigma)^{-1}=(\Sigma^{-1})^2=\begin{pmatrix}
\frac{1}{\sigma_{1}^2} \\
& \frac{1}{\sigma_{2}^2} \\
& & \ddots \\
& & & \frac{1}{\sigma_{n}^2}
\end{pmatrix} ( Σ t Σ ) − 1 = ( Σ − 1 ) 2 = σ 1 2 1 σ 2 2 1 ⋱ σ n 2 1 לכן נקבל כי:
( Σ t Σ ) − 1 Σ t = ( 1 σ 1 2 1 σ 2 2 ⋱ 1 σ n 2 ) ( σ 1 σ 2 ⋱ σ n ) = ( 1 σ 1 1 σ 2 ⋱ 1 σ n ) = ↓ הגדרה Σ † (\Sigma^t\Sigma)^{-1}\Sigma^t=\begin{pmatrix}
\frac{1}{\sigma_{1}^2} \\
& \frac{1}{\sigma_{2}^2} \\
& & \ddots \\
& & & \frac{1}{\sigma_{n}^2}
\end{pmatrix}\begin{pmatrix}
{\sigma_{1}} \\
& {\sigma_{2}} \\
& & \ddots \\
& & & {\sigma_{n}}
\end{pmatrix}=\begin{pmatrix}
\frac{1}{\sigma_{1}} \\
& \frac{1}{\sigma_{2}} \\
& & \ddots \\
& & & \frac{1}{\sigma_{n}}
\end{pmatrix} \underset{\begin{matrix}
\downarrow \\
\R{\text{הגדרה}}
\end{matrix}}{=}\Sigma ^{\dagger} ( Σ t Σ ) − 1 Σ t = σ 1 2 1 σ 2 2 1 ⋱ σ n 2 1 σ 1 σ 2 ⋱ σ n = σ 1 1 σ 2 1 ⋱ σ n 1 ↓ הגדרה = Σ † ולכן מתקיים:
( A t A ) − 1 A t = V Σ † U t = ↓ הגדרה A † (A^tA)^{-1}A^t=V\Sigma ^{\dagger}U^t \underset{\begin{matrix}
\downarrow \\
\R{\text{הגדרה}}
\end{matrix}}{=}A^{\dagger} ( A t A ) − 1 A t = V Σ † U t ↓ הגדרה = A † ∎
הראו כי A A † A = A AA^{\dagger}A=A A A † A = A A t A A † = A t A^tAA^{\dagger}=A^t A t A A † = A t
הוכחה: משוואה ראשונה:
A A † A = U Σ V t V Σ † U t U Σ V t = ↓ U t U = I V t V = I U Σ Σ † Σ V t AA^{\dagger}A=U\Sigma V^tV\Sigma ^{\dagger}U^tU\Sigma V^t \underset{\begin{matrix}
\downarrow \\
U^tU=I \\
V^tV=I
\end{matrix}}{=}U\Sigma\Sigma ^{\dagger}\Sigma V^t A A † A = U Σ V t V Σ † U t U Σ V t ↓ U t U = I V t V = I = U Σ Σ † Σ V t נביט על Σ Σ † Σ \Sigma\Sigma ^{\dagger}\Sigma Σ Σ † Σ
Σ Σ † Σ = Σ ( 1 σ 1 ⋱ 1 σ r 0 ⋱ 0 ) ( σ 1 ⋱ σ r 0 ⋱ 0 ) = Σ ( 1 ⋱ 1 0 ⋱ 0 ) \Sigma\Sigma ^{\dagger}\Sigma=\Sigma \begin{pmatrix}
\frac{1}{\sigma_{1}} \\
& \ddots \\
& & \frac{1}{\sigma_{r}} \\
& & & 0 \\
& & & & \ddots \\
& & & & & 0
\end{pmatrix}\!\!\begin{pmatrix}
\sigma_{1} \\
& \ddots \\
& & \sigma_{r} \\
& & & 0 \\
& & & & \ddots \\
& & & & & 0
\end{pmatrix}\!\!=\!\Sigma\! \begin{pmatrix}
1 \\
& \ddots \\
& & 1 \\
& & & 0 \\
& & & & \ddots \\
& & & & & 0
\end{pmatrix} Σ Σ † Σ = Σ σ 1 1 ⋱ σ r 1 0 ⋱ 0 σ 1 ⋱ σ r 0 ⋱ 0 = Σ 1 ⋱ 1 0 ⋱ 0 Σ Σ † Σ = ( σ 1 ⋱ σ r 0 ⋱ 0 ) ( 1 ⋱ 1 0 ⋱ 0 ) = ( σ 1 ⋱ σ r 0 ⋱ 0 ) = Σ \Sigma\Sigma ^{\dagger}\Sigma=\!\!\begin{pmatrix}
\sigma_{1} \\
& \ddots \\
& & \sigma_{r} \\
& & & 0 \\
& & & & \ddots \\
& & & & & 0
\end{pmatrix}\!\!\!\begin{pmatrix}
1 \\
& \ddots \\
& & 1 \\
& & & 0 \\
& & & & \ddots \\
& & & & & 0
\end{pmatrix}=\begin{pmatrix}
\sigma_{1} \\
& \ddots \\
& & \sigma_{r} \\
& & & 0 \\
& & & & \ddots \\
& & & & & 0
\end{pmatrix}=\Sigma Σ Σ † Σ = σ 1 ⋱ σ r 0 ⋱ 0 1 ⋱ 1 0 ⋱ 0 = σ 1 ⋱ σ r 0 ⋱ 0 = Σ לכן מתקיים:
A A † A = U Σ V t = A AA^{\dagger}A=U\Sigma V^t=A A A † A = U Σ V t = A משוואה שנייה:
A t A A † = V Σ t U t U Σ V t V Σ † U t = ↓ U t U = I V t V = I V Σ t Σ Σ † U t = V Σ 2 Σ † U t A^tAA^{\dagger}=V\Sigma^tU^tU\Sigma V^tV\Sigma ^{\dagger}U^t\underset{\begin{matrix}
\downarrow \\
U^tU=I \\
V^tV=I
\end{matrix}}{=} V\Sigma^t\Sigma\Sigma ^{\dagger}U^t=V\Sigma^2\Sigma ^{\dagger}U^t A t A A † = V Σ t U t U Σ V t V Σ † U t ↓ U t U = I V t V = I = V Σ t Σ Σ † U t = V Σ 2 Σ † U t נבצע דרך דומה:
Σ Σ Σ † = Σ ( σ 1 ⋱ σ r 0 ⋱ 0 ) ( 1 σ 1 ⋱ 1 σ r 0 ⋱ 0 ) = Σ ( 1 ⋱ 1 0 ⋱ 0 ) \Sigma\Sigma \Sigma^{\dagger}=\Sigma \begin{pmatrix}
\sigma_{1} \\
& \ddots \\
& & \sigma_{r} \\
& & & 0 \\
& & & & \ddots \\
& & & & & 0
\end{pmatrix}\!\!\begin{pmatrix}
\frac{1}{\sigma_{1}} \\
& \ddots \\
& & \frac{1}{\sigma_{r}} \\
& & & 0 \\
& & & & \ddots \\
& & & & & 0
\end{pmatrix}\!\!=\!\Sigma\! \begin{pmatrix}
1 \\
& \ddots \\
& & 1 \\
& & & 0 \\
& & & & \ddots \\
& & & & & 0
\end{pmatrix} ΣΣ Σ † = Σ σ 1 ⋱ σ r 0 ⋱ 0 σ 1 1 ⋱ σ r 1 0 ⋱ 0 = Σ 1 ⋱ 1 0 ⋱ 0 ומפה, באותו אופן כמו הנ"ל נקבל כי:
Σ Σ Σ † = Σ \Sigma\Sigma\Sigma ^{\dagger}=\Sigma ΣΣ Σ † = Σ ולכן:
A t A A † = V Σ 2 Σ † U t = V Σ U t = A t A^tAA^{\dagger}=V\Sigma^2\Sigma ^{\dagger}U^t=V\Sigma U^t=A^t A t A A † = V Σ 2 Σ † U t = V Σ U t = A t ∎
הראו כי A A † AA^{\dagger} A A †
הוכחה: סימטריות:
( A A † ) t = ( U Σ V t V Σ † U t ) t = ↓ V t V = I Σ t = Σ ( Σ † ) t = Σ † U Σ † Σ U t (AA^{\dagger})^t=(U\Sigma V^tV\Sigma ^{\dagger}U^t)^t \underset{\begin{matrix}
\downarrow \\
V^tV=I \\
\Sigma^t=\Sigma \\
(\Sigma ^{\dagger})^t=\Sigma ^{\dagger}
\end{matrix}}{=}U\Sigma ^{\dagger}\Sigma U^t ( A A † ) t = ( U Σ V t V Σ † U t ) t ↓ V t V = I Σ t = Σ ( Σ † ) t = Σ † = U Σ † Σ U t נשים לב כי:
Σ † Σ = ( 1 ⋱ 1 0 ⋱ 0 ) = Σ Σ † \Sigma^{\dagger}\Sigma=\begin{pmatrix}
1 \\
& \ddots \\
& & 1 \\
& & & 0 \\
& & & & \ddots \\
& & & & & 0
\end{pmatrix}=\Sigma\Sigma ^{\dagger} Σ † Σ = 1 ⋱ 1 0 ⋱ 0 = Σ Σ † ( A A † ) t = U Σ Σ † U t = U Σ V t V Σ † U t = A A † (AA^{\dagger})^t=U\Sigma\Sigma ^{\dagger}U^t=U\Sigma V^tV\Sigma ^{\dagger}U^t=AA^{\dagger} ( A A † ) t = U Σ Σ † U t = U Σ V t V Σ † U t = A A † איידמפוטנטיות:
( A A † ) 2 = A A † A A † = ↓ סעיף ג’ A A † (AA^{\dagger})^2=AA^{\dagger}AA^{\dagger} \underset{\begin{matrix}
\downarrow \\
\R{\text{סעיף ג'}}
\end{matrix}}{=}AA^{\dagger} ( A A † ) 2 = A A † A A † ↓ סעיף ג’ = A A † ∎
הראו שמתקיים:
∥ A x ‾ − b ‾ ∥ 2 2 = ∥ A x ‾ − A A † b ‾ ∥ 2 2 + ∥ ( I − A A † ) b ‾ ∥ 2 2 \left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2=\left\lVert A\underline{x}-AA^{\dagger}\underline{b} \right\rVert _{2}^2+\left\lVert (I-AA^{\dagger})\underline{b} \right\rVert _{2}^2 ∥ A x − b ∥ 2 2 = A x − A A † b 2 2 + ( I − A A † ) b 2 2 רמז: העזרו בפירוק b ‾ = A A † b ‾ + ( I − A A † ) b ‾ \underline{b}=AA^{\dagger}\underline{b}+(I-AA^{\dagger})\underline{b} b = A A † b + ( I − A A † ) b
הוכחה:
∥ A x ‾ − b ‾ ∥ 2 2 = ∥ A x ‾ − ( A A † b ‾ + ( I − A A † ) b ‾ ) ∥ 2 2 = ∥ A x ‾ − A A † b ‾ − ( I − A A † ) b ‾ ∥ 2 2 \left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2=\left\lVert A\underline{x}-(AA^{\dagger}\underline{b}+(I-AA^{\dagger})\underline{b}) \right\rVert _{2}^2=\left\lVert A\underline{x}-AA^{\dagger}\underline{b}-(I-AA^{\dagger})\underline{b} \right\rVert _{2}^2 ∥ A x − b ∥ 2 2 = A x − ( A A † b + ( I − A A † ) b ) 2 2 = A x − A A † b − ( I − A A † ) b 2 2 ⟨ A x ‾ − A A † b ‾ , ( I − A A † ) b ‾ ⟩ = ( A x ‾ − A A † b ‾ ) t ( ( I − A A † ) b ‾ ) = ( x ‾ t A t − b ‾ t ( A t ) † A t ) ( b ‾ − A A † b ‾ ) = \left\langle A\underline{x}-AA^{\dagger}\underline{b}, (I-AA^{\dagger})\underline{b} \right\rangle=(A\underline{x}-AA^{\dagger}\underline{b})^t((I-AA^{\dagger})\underline{b})=(\underline{x}^tA^t-\underline{b}^t(A^t)^{\dagger}A^t)(\underline{b}-AA^{\dagger}\underline{b})= ⟨ A x − A A † b , ( I − A A † ) b ⟩ = ( A x − A A † b ) t (( I − A A † ) b ) = ( x t A t − b t ( A t ) † A t ) ( b − A A † b ) = = x ‾ t A t b ‾ − x ‾ t A t A A † b ‾ − b ‾ t ( A t ) † A t b ‾ + b ‾ t ( A A † ) t ( A A † ) b ‾ = ↓ סעיף ג’ b ‾ t ( ( A t ) † A t A A † ) b ‾ − b ‾ t ( A t ) † A t b ‾ = =\underline{x}^tA^t\underline{b}-\underline{x}^tA^tAA^{\dagger}\underline{b}-\underline{b}^t(A^t)^{\dagger}A^t\underline{b}+\underline{b}^t(AA^{\dagger})^t(AA^{\dagger})\underline{b} \underset{\begin{matrix}
\downarrow \\
\R{\text{סעיף ג'}}
\end{matrix}}{=}\underline{b}^t((A^t)^{\dagger}A^tAA^{\dagger})\underline{b}-\underline{b}^t(A^t)^{\dagger}A^t\underline{b}= = x t A t b − x t A t A A † b − b t ( A t ) † A t b + b t ( A A † ) t ( A A † ) b ↓ סעיף ג’ = b t (( A t ) † A t A A † ) b − b t ( A t ) † A t b = = ↓ סעיף ג’ b ‾ t ( ( A t ) † A t ) b ‾ − b ‾ t ( ( A t ) † A t ) b ‾ = 0 \underset{\begin{matrix}
\downarrow \\
\R{\text{סעיף ג'}}
\end{matrix}}{=}\underline{b}^t((A^t)^{\dagger}A^t)\underline{b}-\underline{b}^t((A^t)^{\dagger}A^t)\underline{b}=0 ↓ סעיף ג’ = b t (( A t ) † A t ) b − b t (( A t ) † A t ) b = 0 לכן, לפי הגדרה, הוקטורים A x ‾ − A A † b ‾ , ( I − A A † ) b ‾ A\underline{x}-AA^{\dagger}\underline{b}, (I-AA^{\dagger})\underline{b} A x − A A † b , ( I − A A † ) b
∥ A x ‾ − b ‾ ∥ 2 2 = ∥ A x ‾ − A A † b ‾ ∥ 2 2 + ∥ ( I − A A † ) b ‾ ∥ 2 2 \left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2=\left\lVert A\underline{x}-AA^{\dagger}\underline{b} \right\rVert _{2}^2+\left\lVert (I-AA^{\dagger})\underline{b} \right\rVert _{2}^2 ∥ A x − b ∥ 2 2 = A x − A A † b 2 2 + ( I − A A † ) b 2 2 ∎
הסיקו מסעיף ה כי כל פתרון לבעיה arg min x ‾ ∥ A x ‾ − b ‾ ∥ 2 2 \underset{\underline{x}}{\arg\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2 x arg min ∥ A x − b ∥ 2 2 A x ‾ = A A † b ‾ A\underline{x}=AA^{\dagger}\underline{b} A x = A A † b
הוכחה: ( I − A A † ) b ‾ (I-AA^{\dagger})\underline{b} ( I − A A † ) b ∥ ( I − A A † ) b ‾ ∥ 2 2 \left\lVert (I-AA^{\dagger})\underline{b} \right\rVert_{2}^2 ( I − A A † ) b 2 2 ∥ A x ‾ − A A † b ‾ ∥ 2 2 \left\lVert A\underline{x}-AA^{\dagger}\underline{b} \right\rVert_{2}^2 A x − A A † b 2 2 0 0 0 A x ‾ − A A † b ‾ = 0 A\underline{x}-AA^{\dagger}\underline{b}=0 A x − A A † b = 0
A x ‾ = A A † b ‾ A\underline{x}=AA^{\dagger}\underline{b} A x = A A † b ∎
הראו כי וקטור x ‾ \underline{x} x A x ‾ = A A † b ‾ A\underline{x}=AA^{\dagger}\underline{b} A x = A A † b A t A x ‾ = A t b ‾ A^tA\underline{x}=A^t\underline{b} A t A x = A t b רמז: העזרו בתוצאה השנייה מסעיף ג'.
הוכחה: x ‾ \underline{x} x A x ‾ = A A † b ‾ A\underline{x}=AA^{\dagger}\underline{b} A x = A A † b A t A^t A t
A t A x ‾ = A t A A † b ‾ = ↓ סעיף ג’ A t b ‾ A^tA\underline{x}=A^tAA^{\dagger}\underline{b} \underset{\begin{matrix}
\downarrow \\
\R{\text{סעיף ג'}}
\end{matrix}}{=}A^t\underline{b} A t A x = A t A A † b ↓ סעיף ג’ = A t b ∎
תרגיל 3
נתונה מערכת המשוואות ההומוגנית הבאה:
A x ‾ = ( 1 2 − 1 1 − 2 − 1 2 0 − 2 1 0 − 1 ) ( x 1 x 2 x 3 ) = ( 0 0 0 0 ) A\underline{x}=\begin{pmatrix}
1 & 2 & -1 \\
1 & -2 & -1 \\
2 & 0 & -2 \\
1 & 0 & -1
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2} \\
x_{3}
\end{pmatrix}=\begin{pmatrix}
0 \\
0 \\
0 \\
0
\end{pmatrix} A x = 1 1 2 1 2 − 2 0 0 − 1 − 1 − 2 − 1 x 1 x 2 x 3 = 0 0 0 0 הראו שלמערכת זו יש ∞ \infty ∞
הוכחה: 2 2 2 ∞ \infty ∞ ∎
מצאו פתרון x ‾ \underline{x} x ∥ x ‾ ∥ 2 = 1 \left\lVert \underline{x} \right\rVert_{2}=1 ∥ x ∥ 2 = 1
נמצא את הפתרונות לממ"ל באמצעות דירוג:
( 1 2 − 1 0 1 − 2 − 1 0 2 0 − 2 0 1 0 − 1 ) R 2 = R 2 − R 1 R 3 = R 3 − 2 R 4 → ( 1 2 − 1 0 0 − 4 0 0 0 0 0 0 1 0 − 1 0 ) R 1 = R 1 − R 4 R 2 = − 1 4 R 2 → ( 0 2 0 0 0 1 0 0 0 0 0 0 1 0 − 1 0 ) \left(\begin{array}{ccc|c}
1 & 2 & -1 & 0 \\
1 & -2 & -1 & 0 \\
2 & 0 & -2 & 0 \\
1 & 0 & -1
\end{array}\right)\overrightarrow{\begin{matrix}
R_{2}=R_{2}-R_{1} \\
R_{3}=R_{3}-2R_{4}
\end{matrix}}\left(\begin{array}{ccc|c}
1 & 2 & -1 & 0 \\
0 & -4 & 0 & 0 \\
0 & 0 & 0 & 0 \\
1 & 0 & -1 & 0
\end{array}\right) \overrightarrow{\begin{matrix}
R_{1}=R_{1}-R_{4} \\
R_{2}=-\frac{1}{4}R_{2}
\end{matrix}}\left(\begin{array}{ccc|c}
0 & 2 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 \\
1 & 0 & -1 & 0
\end{array}\right) 1 1 2 1 2 − 2 0 0 − 1 − 1 − 2 − 1 0 0 0 R 2 = R 2 − R 1 R 3 = R 3 − 2 R 4 1 0 0 1 2 − 4 0 0 − 1 0 0 − 1 0 0 0 0 R 1 = R 1 − R 4 R 2 = − 4 1 R 2 0 0 0 1 2 1 0 0 0 0 0 − 1 0 0 0 0 R 1 → R 3 → R 4 → R 1 → ( 1 0 − 1 0 0 1 0 0 0 2 0 0 0 0 0 0 ) R 3 = R 3 − 2 R 2 → ( 1 0 − 1 0 0 1 0 0 0 0 0 0 0 0 0 0 ) \overrightarrow{\begin{matrix}
R_{1}\to R_{3}\to R_{4}\to R_{1}
\end{matrix}}\left(\begin{array}{ccc|c}
1 & 0 & -1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 2 & 0 & 0 \\
0 & 0 & 0 & 0
\end{array}\right)\overrightarrow{R_{3}=R_{3}-2R_{2}}\left(\begin{array}{ccc|c}
1 & 0 & -1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{array}\right) R 1 → R 3 → R 4 → R 1 1 0 0 0 0 1 2 0 − 1 0 0 0 0 0 0 0 R 3 = R 3 − 2 R 2 1 0 0 0 0 1 0 0 − 1 0 0 0 0 0 0 0 אנו יודעים כי הפתרון מקיים x 1 = x 3 x_{1}=x_{3} x 1 = x 3 x 2 = 0 x_{2}=0 x 2 = 0
∥ x ‾ ∥ 2 = x ‾ t x ‾ = x 1 2 + x 2 2 + x 3 2 = 2 x 1 2 = 1 \left\lVert \underline{x} \right\rVert _{2}=\sqrt{ \underline{x}^t\underline{x} }=\sqrt{ x_{1}^2+x_{2}^2+x_{3}^2 }=\sqrt{ 2x_{1}^2 }=1 ∥ x ∥ 2 = x t x = x 1 2 + x 2 2 + x 3 2 = 2 x 1 2 = 1 x 1 = x 1 2 = 1 2 x_{1}=\sqrt{ x_{1}^2 }=\frac{1}{\sqrt{ 2 }} x 1 = x 1 2 = 2 1 ולכן, פתרון x ‾ \underline{x} x ∥ x ‾ ∥ 2 = 1 \left\lVert \underline{x} \right\rVert_{2}=1 ∥ x ∥ 2 = 1 x ‾ = ( 1 2 0 1 2 ) \underline{x}=\begin{pmatrix} \frac{1}{\sqrt{ 2 }} \\ 0 \\ \frac{1}{\sqrt{ 2 }}\end{pmatrix} x = 2 1 0 2 1
עקב שגיאות במידידות התקבלה המטריצה הבאה:
A = ( 1 2 − 1 1 − 2 − 1 2 0 − 2 1 0 + 1 ) A=\begin{pmatrix}
1 & 2 & -1 \\
1 & -2 & -1 \\
2 & 0 & -2 \\
1 & 0 & {\color{red}+1}
\end{pmatrix} A = 1 1 2 1 2 − 2 0 0 − 1 − 1 − 2 + 1 הראו שלמערכת החדשה ישנו פתרון יחיד הנתון ע"י x ‾ = 0 ‾ \underline{x}=\underline{0} x = 0
נראה כי אין פתרון לא טריוויאלי למערכת המשוואות ההומוגנית:
( 1 2 − 1 0 1 − 2 − 1 0 2 0 − 2 0 1 0 1 0 ) R 2 = R 2 − R 1 R 3 = R 3 − 2 R 1 R 4 = R 4 − R 1 → ( 1 2 − 1 0 0 − 4 0 0 0 − 4 0 0 0 − 2 2 0 ) R 2 = 1 − 4 R 2 R 4 ↔ − 1 2 R 3 → ( 1 2 − 1 0 0 1 0 0 0 1 − 1 0 0 − 4 0 0 ) \left(\begin{array}{ccc|c}
1 & 2 & -1 & 0 \\
1 & -2 & -1 & 0 \\
2 & 0 & -2 & 0 \\
1 & 0 & 1 & 0
\end{array}\right)\overrightarrow{\begin{matrix}
R_{2}=R_{2}-R_{1} \\
R_{3}=R_{3}-2R_{1} \\
R_{4}=R_{4}-R_{1}
\end{matrix}}\left(\begin{array}{ccc|c}
1 & 2 & -1 & 0 \\
0 & -4 & 0 & 0 \\
0 & -4 & 0 & 0 \\
0 & -2 & 2 & 0
\end{array}\right)\overrightarrow{\begin{matrix}
R_{2}=\frac{1}{-4}R_{2} \\
R_{4}\leftrightarrow -\frac{1}{2}R_{3}
\end{matrix}}\left(\begin{array}{ccc|c}
1 & 2 & -1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 1 & -1 & 0 \\
0 & -4 & 0 & 0
\end{array}\right) 1 1 2 1 2 − 2 0 0 − 1 − 1 − 2 1 0 0 0 0 R 2 = R 2 − R 1 R 3 = R 3 − 2 R 1 R 4 = R 4 − R 1 1 0 0 0 2 − 4 − 4 − 2 − 1 0 0 2 0 0 0 0 R 2 = − 4 1 R 2 R 4 ↔ − 2 1 R 3 1 0 0 0 2 1 1 − 4 − 1 0 − 1 0 0 0 0 0 R 4 = R 4 + 4 R 2 R 3 = R 3 − R 2 R 1 = R 1 − 2 R 2 → ( 1 0 − 1 0 0 1 0 0 0 0 − 1 0 0 0 0 0 ) \overrightarrow{\begin{matrix}
R_{4}=R_{4}+4R_{2} \\
R_{3}=R_{3}-R_{2} \\
R_{1}=R_{1}-2R_{2}
\end{matrix}}\left(\begin{array}{ccc|c}
1 & 0 & -1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & -1 & 0 \\
0 & 0 & 0 & 0
\end{array}\right) R 4 = R 4 + 4 R 2 R 3 = R 3 − R 2 R 1 = R 1 − 2 R 2 1 0 0 0 0 1 0 0 − 1 0 − 1 0 0 0 0 0 נקבל מפה כי x 1 = x 3 x_{1}=x_{3} x 1 = x 3 x 2 = x 3 = 0 x_{2}=x_{3}=0 x 2 = x 3 = 0 x ‾ = ( 0 0 0 ) \underline{x}=\begin{pmatrix}0 \\ 0 \\ 0\end{pmatrix} x = 0 0 0 x ‾ = 0 ‾ \underline{x}=\underline{0} x = 0
אנו מעוניינים למצוא פתרון אחר למערכת המקיים ∥ x ‾ ∥ 2 = 1 \left\lVert \underline{x} \right\rVert_{2}=1 ∥ x ∥ 2 = 1
min x ‾ ∥ A x ‾ ∥ 2 2 s . t . ∥ x ‾ ∥ 2 = 1 \underset{\underline{x}}{\min}\left\lVert A\underline{x} \right\rVert _{2}^2 \;\quad s.t. \quad \left\lVert \underline{x} \right\rVert _{2}=1 x min ∥ A x ∥ 2 2 s . t . ∥ x ∥ 2 = 1 הראו שהפתרון לבעיה זו מתקבל ע"י x ‾ = v ‾ min \underline{x}=\underline{v}_{\min} x = v m i n v ‾ min \underline{v}_{\min} v m i n V V V S V D SV\!D S V D A A A
הוכחה:
min x ‾ ∥ A x ‾ ∥ 2 2 = min x ‾ ∥ U Σ V t x ‾ ∥ 2 2 = ↓ אורתונורמלית U U min x ‾ ∥ Σ V t x ‾ ∥ 2 2 \underset{\underline{x}}{\min}\left\lVert A\underline{x} \right\rVert _{2}^2=\underset{\underline{x}}{\min}\left\lVert U\Sigma V^t\underline{x} \right\rVert _{2}^2 \underset{\begin{matrix}
\downarrow \\
\R{\text{ אורתונורמלית}}U
\end{matrix}}{=}U\underset{\underline{x}}{\min}\left\lVert \Sigma V^t\underline{x} \right\rVert _{2}^2 x min ∥ A x ∥ 2 2 = x min U Σ V t x 2 2 ↓ אורתונורמלית U = U x min Σ V t x 2 2 נגדיר z ‾ = V t x ‾ \underline{z}=V^t\underline{x} z = V t x ∥ x ‾ ∥ 2 = 1 \left\lVert \underline{x} \right\rVert_{2}=1 ∥ x ∥ 2 = 1 V V V
∥ z ‾ ∥ 2 = ∥ V t x ‾ ∥ 2 = ∥ x ‾ ∥ 2 = 1 \left\lVert \underline{z} \right\rVert _{2}=\left\lVert V^t\underline{x} \right\rVert _{2}=\left\lVert \underline{x} \right\rVert _{2}=1 ∥ z ∥ 2 = V t x 2 = ∥ x ∥ 2 = 1 ולכן נמצא את הפתרון עבור:
min z ‾ : ∥ z ‾ ∥ 2 = 1 ∥ Σ z ‾ ∥ 2 = min z ‾ : ∥ z ‾ ∥ 2 = 1 ∣ ∑ i = 1 r σ i z i ∣ \underset{\underline{z}:\;\; \left\lVert \underline{z} \right\rVert_{2}=1 }{\min}\left\lVert \Sigma \underline{z} \right\rVert _{2}=\underset{\underline{z}:\;\; \left\lVert \underline{z} \right\rVert_{2}=1 }{\min}\left\lvert \sum_{i=1}^r \sigma_{i}z_{i} \right\rvert z : ∥ z ∥ 2 = 1 min ∥ Σ z ∥ 2 = z : ∥ z ∥ 2 = 1 min i = 1 ∑ r σ i z i נתון לנו כי ∥ z ‾ ∥ 2 = 1 \left\lVert \underline{z} \right\rVert_{2}=1 ∥ z ∥ 2 = 1 1 1 1 Σ \Sigma Σ ∥ Σ z ‾ ∥ 2 \left\lVert \Sigma \underline{z} \right\rVert_{2} ∥ Σ z ∥ 2 Σ \Sigma Σ 1 1 1 σ m i n \sigma_{min} σ min z ‾ \underline{z} z
כעת, נוכל למצוא את x ‾ \underline{x} x
z ‾ = V t x ‾ ⟹ V z ‾ = x ‾ \underline{z}=V^t\underline{x} \implies V\underline{z}=\underline{x} z = V t x ⟹ V z = x v ‾ m i n = ( ∣ ∣ ∣ v ‾ 1 v ‾ 2 … v ‾ m i n ∣ ∣ ∣ ) ( 0 ⋮ 0 1 ) = x ‾ \underline{v}_{min}=\begin{pmatrix}
\vert & \vert & & \vert \\
\underline{v}_{1} & \underline{v}_{2} & \dots & \underline{v}_{min} \\
\vert & \vert & & \vert
\end{pmatrix}\begin{pmatrix}
0 \\
\vdots \\
0 \\
1
\end{pmatrix}=\underline{x} v min = ∣ v 1 ∣ ∣ v 2 ∣ … ∣ v min ∣ 0 ⋮ 0 1 = x לכן, x ‾ = v ‾ m i n \underline{x}=\underline{v}_{min} x = v min ∎
חשבו את פירוק S V D SV\!D S V D A A A
נמצא תחילה את A t A A^tA A t A
A t A = ( 1 1 2 1 2 − 2 0 0 − 1 − 1 − 2 1 ) ( 1 2 − 1 1 − 2 − 1 2 0 − 2 1 0 1 ) = ( 7 0 − 5 0 8 0 − 5 0 7 ) A^tA=\begin{pmatrix}
1 & 1 & 2 & 1 \\
2 & -2 & 0 & 0 \\
-1 & -1 & -2 & 1
\end{pmatrix}\begin{pmatrix}
1 & 2 & -1 \\
1 & -2 & -1 \\
2 & 0 & -2 \\
1 & 0 & 1
\end{pmatrix}=\begin{pmatrix}
7 & 0 & -5 \\
0 & 8 & 0 \\
-5 & 0 & 7
\end{pmatrix} A t A = 1 2 − 1 1 − 2 − 1 2 0 − 2 1 0 1 1 1 2 1 2 − 2 0 0 − 1 − 1 − 2 1 = 7 0 − 5 0 8 0 − 5 0 7 נמצא כעת את הע"ע שלה ובכך את הסינגולריים של A A A
∣ A t A − λ I ∣ = ∣ 7 − λ 0 − 5 0 8 − λ 0 − 5 0 7 − λ ∣ = ( 7 − λ ) ∣ 8 − λ 0 0 7 − λ ∣ − 5 ∣ 0 − 5 8 − λ 0 ∣ = ( 7 − λ ) 2 ( 8 − λ ) − 25 ( 8 − λ ) = ( 8 − λ ) ( ( 7 − λ ) 2 − 25 ) = ( 8 − λ ) ( 49 − 14 λ + λ 2 − 25 ) = ( 8 − λ ) ( λ 2 − 14 λ + 24 ) = ( 8 − λ ) ( 12 − λ ) ( 2 − λ ) = 0 \begin{align*}
|A^tA-\lambda I|&=\begin{vmatrix}
7-\lambda & 0 & -5 \\
0 & 8-\lambda & 0 \\
-5 & 0 & 7-\lambda
\end{vmatrix}=(7-\lambda)\begin{vmatrix}
8-\lambda & 0 \\
0 & 7-\lambda
\end{vmatrix}-5\begin{vmatrix}
0 & -5 \\
8-\lambda & 0
\end{vmatrix} \\
&=(7-\lambda)^2(8-\lambda)-25(8-\lambda)=(8-\lambda)((7-\lambda)^2-25) \\
&=(8-\lambda)(49-14\lambda+\lambda^2-25)=(8-\lambda)(\lambda^2-14\lambda+24) \\
&=(8-\lambda)(12-\lambda)(2-\lambda) = 0
\end{align*} ∣ A t A − λ I ∣ = 7 − λ 0 − 5 0 8 − λ 0 − 5 0 7 − λ = ( 7 − λ ) 8 − λ 0 0 7 − λ − 5 0 8 − λ − 5 0 = ( 7 − λ ) 2 ( 8 − λ ) − 25 ( 8 − λ ) = ( 8 − λ ) (( 7 − λ ) 2 − 25 ) = ( 8 − λ ) ( 49 − 14 λ + λ 2 − 25 ) = ( 8 − λ ) ( λ 2 − 14 λ + 24 ) = ( 8 − λ ) ( 12 − λ ) ( 2 − λ ) = 0 הערכים הסינגולריים של A A A
σ 1 = 12 , σ 2 = 8 , σ 3 = 2 \sigma_{1}=\sqrt{ 12 }, \quad \sigma_{2}=\sqrt{ 8 }, \quad \sigma_{3}=\sqrt{ 2 } σ 1 = 12 , σ 2 = 8 , σ 3 = 2 ⇓ \Downarrow ⇓ Σ = ( 12 0 0 0 8 0 0 0 2 ) \Sigma=\begin{pmatrix}
\sqrt{ 12 } & 0 & 0 \\
0 & \sqrt{ 8 } & 0 \\
0 & 0 & \sqrt{ 2 }
\end{pmatrix} Σ = 12 0 0 0 8 0 0 0 2 נמצא את הו"ע של A t A A^tA A t A
σ 1 = 12 : ‾ ( − 5 0 − 5 0 0 − 4 0 0 − 5 0 − 5 0 ) R 3 = R 3 − R 1 R 2 = − 1 4 R 2 → ( − 5 0 − 5 0 0 1 0 0 0 0 0 0 ) R 1 = − 1 5 R 1 → ( 1 0 1 0 0 1 0 0 0 0 0 0 ) V σ 1 = 12 = { ( t 0 − t ) t ∈ R } = s p { ( 1 0 − 1 ) } σ 2 = 8 : ‾ ( − 1 0 − 5 0 0 0 0 0 − 5 0 − 1 0 ) R 3 = R 3 − 5 R 1 → ( − 1 0 − 5 0 0 0 0 0 0 0 24 0 ) 1 24 R 3 ↔ R 2 R 1 = − R 1 − 5 R 3 ∗ → ( 1 0 0 0 0 0 1 0 0 0 0 0 ) V σ 2 = 8 = { ( 0 t 0 ) t ∈ R } = s p { ( 0 1 0 ) } σ 3 = 2 : ‾ ( 5 0 − 5 0 0 6 0 0 − 5 0 5 0 ) R 1 = 1 5 R 1 R 2 = 1 6 R 2 R 3 = − 1 5 R 3 → ( 1 0 − 1 0 0 1 0 0 1 0 − 1 0 ) R 3 = R 3 − R 1 → ( 1 0 − 1 0 0 1 0 0 0 0 0 0 ) V σ 3 = 2 = { ( t 0 t ) t ∈ R } = s p { ( 1 0 1 ) } \begin{align*}
\underline{\sigma_{1}=12:}\;\;\; & \left(\begin{array}{ccc|c}
-5 & 0 & -5 & 0 \\
0 & -4 & 0 & 0 \\
-5 & 0 & -5 & 0
\end{array}\right)\overrightarrow{\begin{matrix}
R_{3}=R_{3}-R_{1} \\
R_{2}=-\frac{1}{4}R_{2}
\end{matrix}}\left(\begin{array}{ccc|c}
-5 & 0 & -5 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0
\end{array}\right)\overrightarrow{R_{1}=-\frac{1}{5}R_{1}}\left(\begin{array}{ccc|c}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0
\end{array}\right) \\
& V_{\sigma_{1}=12}=\left\{ \begin{array}{c|c}
\begin{pmatrix}
t \\
0 \\
-t
\end{pmatrix} & t \in \mathbb{R}
\end{array} \right\}=sp\left\{ \begin{pmatrix}
1 \\
0 \\
-1
\end{pmatrix} \right\} \\
\underline{\sigma_{2}=8:}\;\;\;\; & \left(\begin{array}{ccc|c}
-1 & 0 & -5 & 0 \\
0 & 0 & 0 & 0 \\
-5 & 0 & -1 & 0
\end{array}\right)\overrightarrow{R_{3}=R_{3}-5R_{1}}\left(\begin{array}{ccc|c}
-1 & 0 & -5 & 0 \\
0 & 0 & 0 & 0\\
0 & 0 & 24 & 0
\end{array}\right)\overrightarrow{\begin{matrix}
\frac{1}{24}R_{3}\leftrightarrow R_{2} \\
R_{1}=-R_{1}-5R_{3}^*
\end{matrix}}\!\left(\begin{array}{ccc|c}
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0
\end{array}\right) \\
& V_{\sigma_{2}=8}=\left\{ \begin{array}{c|c}
\begin{pmatrix}
0 \\
t \\
0
\end{pmatrix} & t \in \mathbb{R}
\end{array} \right\}=sp\left\{ \begin{pmatrix}
0 \\
1 \\
0
\end{pmatrix} \right\} \\
\underline{\sigma_{3}=2:}\;\;\;\; & \left(\begin{array}{ccc|c}
5 & 0 & -5 & 0 \\
0 & 6 & 0 & 0 \\
-5 & 0 & 5 & 0
\end{array}\right)\overrightarrow{\begin{matrix}
R_{1}=\frac{1}{5}R_{1} \\
R_{2}=\frac{1}{6}R_{2} \\
R_{3}=-\frac{1}{5}R_{3}
\end{matrix}}\left(\begin{array}{ccc|c}
1 & 0 & -1 & 0 \\
0 & 1 & 0 & 0 \\
1 & 0 & -1 & 0
\end{array}\right)\overrightarrow{R_{3}=R_{3}-R_{1}}\left(\begin{array}{ccc|c}
1 & 0 & -1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0
\end{array}\right) \\
& V_{\sigma_{3}=2}=\left\{ \begin{array}{c|c}
\begin{pmatrix}
t \\
0 \\
t
\end{pmatrix} & t \in \mathbb{R}
\end{array} \right\}=sp\left\{ \begin{pmatrix}
1 \\
0 \\
1
\end{pmatrix} \right\}
\end{align*} σ 1 = 12 : σ 2 = 8 : σ 3 = 2 : − 5 0 − 5 0 − 4 0 − 5 0 − 5 0 0 0 R 3 = R 3 − R 1 R 2 = − 4 1 R 2 − 5 0 0 0 1 0 − 5 0 0 0 0 0 R 1 = − 5 1 R 1 1 0 0 0 1 0 1 0 0 0 0 0 V σ 1 = 12 = ⎩ ⎨ ⎧ t 0 − t t ∈ R ⎭ ⎬ ⎫ = s p ⎩ ⎨ ⎧ 1 0 − 1 ⎭ ⎬ ⎫ − 1 0 − 5 0 0 0 − 5 0 − 1 0 0 0 R 3 = R 3 − 5 R 1 − 1 0 0 0 0 0 − 5 0 24 0 0 0 24 1 R 3 ↔ R 2 R 1 = − R 1 − 5 R 3 ∗ 1 0 0 0 0 0 0 1 0 0 0 0 V σ 2 = 8 = ⎩ ⎨ ⎧ 0 t 0 t ∈ R ⎭ ⎬ ⎫ = s p ⎩ ⎨ ⎧ 0 1 0 ⎭ ⎬ ⎫ 5 0 − 5 0 6 0 − 5 0 5 0 0 0 R 1 = 5 1 R 1 R 2 = 6 1 R 2 R 3 = − 5 1 R 3 1 0 1 0 1 0 − 1 0 − 1 0 0 0 R 3 = R 3 − R 1 1 0 0 0 1 0 − 1 0 0 0 0 0 V σ 3 = 2 = ⎩ ⎨ ⎧ t 0 t t ∈ R ⎭ ⎬ ⎫ = s p ⎩ ⎨ ⎧ 1 0 1 ⎭ ⎬ ⎫ לכן נקבל כי:
V = ( 1 0 1 0 1 0 − 1 0 1 ) V=\begin{pmatrix}
1 & 0 & 1 \\
0 & 1 & 0 \\
-1 & 0 & 1
\end{pmatrix} V = 1 0 − 1 0 1 0 1 0 1 כעת, ננרמל את הו"ע של A t A A^tA A t A U U U
V σ 1 : ‾ u ‾ 1 = v ‾ 1 ∥ v ‾ 1 ∥ 2 = 1 ∥ v ‾ 1 ∥ 2 ( 1 0 − 1 ) ∥ v ‾ 1 ∥ 2 2 = v ‾ 1 t v ‾ 1 = ( 1 0 − 1 ) ( 1 0 − 1 ) = 1 + ( − 1 ) 2 = 2 u ‾ 1 = ( 1 2 0 − 1 2 ) V σ 2 : ‾ u ‾ 2 = v ‾ 2 ∥ v ‾ 2 ∥ 2 = 1 ∥ v ‾ 2 ∥ 2 ( 0 1 0 ) ∥ v ‾ 2 ∥ 2 2 = v ‾ 2 t v ‾ 2 = ( 0 1 0 ) ( 0 1 0 ) = 1 u ‾ 2 = v ‾ 2 = ( 0 1 0 ) V σ 3 : ‾ u ‾ 3 = v ‾ 3 ∥ v ‾ 3 ∥ 2 = 1 ∥ v ‾ 3 ∥ 2 ( 1 0 1 ) ∥ v ‾ 1 ∥ 2 2 = v ‾ 2 t v ‾ 2 = ( 1 0 1 ) ( 1 0 1 ) = 1 + 1 = 2 u ‾ 3 = ( 1 2 0 1 2 ) \begin{align*}
\underline{V_{\sigma_{1}}:}\;\; & \underline{u}_{1}=\frac{\underline{v}_{1}}{\left\lVert \underline{v}_{1} \right\rVert_{2} }=\frac{1}{\left\lVert \underline{v}_{1} \right\rVert_{2} }\begin{pmatrix}
1 \\
0 \\
-1
\end{pmatrix} \\
& \left\lVert \underline{v}_{1} \right\rVert _{2}^2=\underline{v}_{1}^t\underline{v}_{1}=\begin{pmatrix}
1 & 0 & -1
\end{pmatrix}\begin{pmatrix}
1 \\
0 \\
-1
\end{pmatrix}=1+(-1)^2=2 \\
& \underline{u}_{1}=\begin{pmatrix}
\frac{1}{\sqrt{ 2 }} \\
0 \\
-\frac{1}{\sqrt{ 2 }}
\end{pmatrix} \\
\underline{V_{\sigma_{2}}:}\;\; & \underline{u}_{2}=\frac{\underline{v}_{2}}{\left\lVert \underline{v}_{2} \right\rVert_{2} }=\frac{1}{\left\lVert \underline{v}_{2} \right\rVert_{2} }\begin{pmatrix}
0 \\
1 \\
0
\end{pmatrix} \\
& \left\lVert \underline{v}_{2} \right\rVert _{2}^2=\underline{v}_{2}^t\underline{v}_{2}=\begin{pmatrix}
0 & 1 & 0
\end{pmatrix}\begin{pmatrix}
0 \\
1 \\
0
\end{pmatrix}=1 \\
& \underline{u}_{2}=\underline{v}_{2}=\begin{pmatrix}
0 \\
1 \\
0
\end{pmatrix} \\
\underline{V_{\sigma_{3}}:}\;\; & \underline{u}_{3}=\frac{\underline{v}_{3}}{\left\lVert \underline{v}_{3} \right\rVert_{2} }=\frac{1}{\left\lVert \underline{v}_{3} \right\rVert_{2} }\begin{pmatrix}
1 \\
0 \\
1
\end{pmatrix} \\
& \left\lVert \underline{v}_{1} \right\rVert _{2}^2=\underline{v}_{2}^t\underline{v}_{2}=\begin{pmatrix}
1 & 0 & 1
\end{pmatrix}\begin{pmatrix}
1 \\
0 \\
1
\end{pmatrix}=1+1 = 2 \\
& \underline{u}_{3}=\begin{pmatrix}
\frac{1}{\sqrt{ 2 }} \\
0 \\
\frac{1}{\sqrt{ 2 }}
\end{pmatrix}
\end{align*} V σ 1 : V σ 2 : V σ 3 : u 1 = ∥ v 1 ∥ 2 v 1 = ∥ v 1 ∥ 2 1 1 0 − 1 ∥ v 1 ∥ 2 2 = v 1 t v 1 = ( 1 0 − 1 ) 1 0 − 1 = 1 + ( − 1 ) 2 = 2 u 1 = 2 1 0 − 2 1 u 2 = ∥ v 2 ∥ 2 v 2 = ∥ v 2 ∥ 2 1 0 1 0 ∥ v 2 ∥ 2 2 = v 2 t v 2 = ( 0 1 0 ) 0 1 0 = 1 u 2 = v 2 = 0 1 0 u 3 = ∥ v 3 ∥ 2 v 3 = ∥ v 3 ∥ 2 1 1 0 1 ∥ v 1 ∥ 2 2 = v 2 t v 2 = ( 1 0 1 ) 1 0 1 = 1 + 1 = 2 u 3 = 2 1 0 2 1 לכן נקבל כי:
U = ( 1 2 0 1 2 0 1 0 − 1 2 0 1 2 ) U=\begin{pmatrix}
\frac{1}{\sqrt{ 2 }} & 0 & \frac{1}{\sqrt{ 2 }} \\
0 & 1 & 0 \\
-\frac{1}{\sqrt{ 2 }} & 0 & \frac{1}{\sqrt{ 2 }}
\end{pmatrix} U = 2 1 0 − 2 1 0 1 0 2 1 0 2 1 ולכן נקבל כי:
A = U Σ V t = ( 1 2 0 1 2 0 1 0 − 1 2 0 1 2 ) ( 12 0 0 0 8 0 0 0 2 ) ( 1 0 − 1 0 1 0 1 0 1 ) A=U\Sigma V^t=\begin{pmatrix}
\frac{1}{\sqrt{ 2 }} & 0 & \frac{1}{\sqrt{ 2 }} \\
0 & 1 & 0 \\
-\frac{1}{\sqrt{ 2 }} & 0 & \frac{1}{\sqrt{ 2 }}
\end{pmatrix}\begin{pmatrix}
\sqrt{ 12 } & 0 & 0 \\
0 & \sqrt{ 8 } & 0 \\
0 & 0 & \sqrt{ 2 }
\end{pmatrix}\begin{pmatrix}
1 & 0 & -1 \\
0 & 1 & 0 \\
1 & 0 & 1
\end{pmatrix} A = U Σ V t = 2 1 0 − 2 1 0 1 0 2 1 0 2 1 12 0 0 0 8 0 0 0 2 1 0 1 0 1 0 − 1 0 1 וזוהי התוצאה :)
מצאו את הפתרון לבעיית הריבועים הפחותים שהוגדרה בסעיף ד' ואת ערך השגיאה המתקבל.
הפתרון לבעיית הריבועים הפחותים הזו הוא בדיוק x ‾ = v ‾ m i n = ( 1 0 1 ) \underline{x}=\underline{v}_{min}=\begin{pmatrix}1 \\ 0 \\ 1\end{pmatrix} x = v min = 1 0 1
∥ A v ‾ m i n ∥ 2 2 \left\lVert A\underline{v}_{min} \right\rVert _{2}^2 ∥ A v min ∥ 2 2 לפי פיתוח ה-S V D SV\!D S V D A v ‾ i = σ i u ‾ i A\underline{v}_{i}=\sigma_{i}\underline{u}_{i} A v i = σ i u i
∥ A v ‾ m i n ∥ 2 2 = ∥ σ m i n u ‾ m i n ∥ 2 2 = ↓ הומוגניות ∣ σ m i n ∣ 2 ∥ u ‾ m i n ∥ 2 2 = ↓ ∀ 1 ≤ i ≤ n : ∥ u ‾ i ∥ 2 = 1 σ m i n 2 \left\lVert A\underline{v}_{min} \right\rVert _{2}^2=\left\lVert \sigma_{min}\underline{u}_{min} \right\rVert _{2}^2 \underset{\begin{matrix}
\downarrow \\
\R{\text{הומוגניות}}
\end{matrix}}{=}|\sigma_{min}|^2\left\lVert \underline{u}_{min} \right\rVert _{2}^2 \underset{\begin{matrix}
\downarrow \\
\forall 1\leq i\leq n:\;\; \left\lVert \underline{u}_{i} \right\rVert _{2}=1
\end{matrix}}{=}\sigma_{min}^2 ∥ A v min ∥ 2 2 = ∥ σ min u min ∥ 2 2 ↓ הומוגניות = ∣ σ min ∣ 2 ∥ u min ∥ 2 2 ↓ ∀1 ≤ i ≤ n : ∥ u i ∥ 2 = 1 = σ min 2 בבעיה הספציפית שלנו מתקיים כי ערך השגיאה הינו ∥ A v ‾ m i n ∥ 2 2 = σ m i n 2 = 2 \left\lVert A\underline{v}_{min} \right\rVert_{2}^2=\sigma_{min}^2=2 ∥ A v min ∥ 2 2 = σ min 2 = 2
תרגיל 4
אנו מפתחים משק וידאו שנועד לרוץ על טלפונים ניידים.Q ∈ R 3 × 3 Q \in \mathbb{R}^{3\times 3} Q ∈ R 3 × 3 A ∈ R 3 × 3 A \in \mathbb{R}^{3\times 3} A ∈ R 3 × 3 A A A Q Q Q
arg min Q ∈ R 3 × 3 ∥ A − Q ∥ F 2 s . t . Q t Q = I \underset{Q \in \mathbb{R}^{3\times 3}}{\arg \min}\left\lVert A-Q \right\rVert _{F}^2 \;\;\; s.t. \;\;\; Q^tQ=I Q ∈ R 3 × 3 arg min ∥ A − Q ∥ F 2 s . t . Q t Q = I הראו כי בעיה זו שקולה לבעיה:
arg max Q ∈ R 3 × 3 t r ( Q t A ) s . t . Q t Q = I \underset{Q \in \mathbb{R}^{3\times3}}{\arg \max}\ tr(Q^tA)\;\; s.t. \;\; Q^tQ=I Q ∈ R 3 × 3 arg max t r ( Q t A ) s . t . Q t Q = I הוכחה:
∥ A − Q ∥ F 2 = t r ( ( A − Q ) t ( A − Q ) ) = t r ( A t A − A t Q − Q t A + Q t Q ) = t r ( A t A − A t Q − Q t A + I ) \left\lVert A-Q \right\rVert _{F}^2=tr((A-Q)^t(A-Q))=tr(A^tA-A^tQ-Q^tA+Q^tQ)=tr(A^tA-A^tQ-Q^tA+I) ∥ A − Q ∥ F 2 = t r (( A − Q ) t ( A − Q )) = t r ( A t A − A t Q − Q t A + Q t Q ) = t r ( A t A − A t Q − Q t A + I ) = t r ( A t A ) − t r ( A t Q ) − t r ( Q t A ) + t r ( I ) = ↓ t r ( A B ) = t r ( B A ) 3 + t r ( A t A ) − 2 t r ( A t Q ) =tr(A^tA)-tr(A^tQ)-tr(Q^tA)+tr(I) \underset{\begin{matrix}
\downarrow \\
tr(AB)=tr(BA)
\end{matrix}}{=} 3+tr(A^tA)-2tr(A^tQ) = t r ( A t A ) − t r ( A t Q ) − t r ( Q t A ) + t r ( I ) ↓ t r ( A B ) = t r ( B A ) = 3 + t r ( A t A ) − 2 t r ( A t Q ) על מנת לקבל את הערך המינימלי עבור ∥ A − Q ∥ F 2 = 3 + t r ( A t A ) − 2 t r ( A t Q ) \left\lVert A-Q \right\rVert_{F}^2=3+tr(A^tA)-2tr(A^tQ) ∥ A − Q ∥ F 2 = 3 + t r ( A t A ) − 2 t r ( A t Q ) 2 t r ( A t Q ) 2tr(A^tQ) 2 t r ( A t Q ) 3 + t r ( A t A ) 3+tr(A^tA) 3 + t r ( A t A )
arg min Q ∈ R 3 × 3 t r ( Q t A ) s . t . Q t Q = I \underset{Q \in \mathbb{R}^{3\times_{3}}}{\arg \min}\ tr(Q^tA)\;\; s.t. \;\; Q^tQ=I Q ∈ R 3 × 3 arg min t r ( Q t A ) s . t . Q t Q = I ∎
ראינו בהרצאה כי מתקיים ∥ B ∥ F 2 = t r ( B t B ) \left\lVert B \right\rVert_{F}^2=tr(B^tB) ∥ B ∥ F 2 = t r ( B t B )
arg max Z ∈ R 3 × 3 t r ( Z D ) s . t . Z t Z = I \underset{Z \in \mathbb{R}^{3\times_{3}}}{\arg \max}\ tr(ZD)\;\; s.t.\;\; Z^tZ=I Z ∈ R 3 × 3 arg max t r ( Z D ) s . t . Z t Z = I כאשר Z Z Z Q Q Q D D D
הוכחה: S V D SV\!D S V D A A A
t r ( Q t A ) = t r ( U Σ V t Q t ) = ↓ t r ( A B ) = t r ( B A ) t r ( Σ V t Q t U ) tr(Q^tA)=tr(U\Sigma V^tQ^t)\underset{\begin{matrix}
\downarrow \\
tr(AB)=tr(BA)
\end{matrix}}{=}tr(\Sigma V^tQ^tU) t r ( Q t A ) = t r ( U Σ V t Q t ) ↓ t r ( A B ) = t r ( B A ) = t r ( Σ V t Q t U ) נגדיר אופרטור ליניארי T : R 3 × 3 → R 3 × 3 T:\mathbb{R}^{3\times3}\to \mathbb{R}^{3\times3} T : R 3 × 3 → R 3 × 3 T ( Q ) = V t Q t U T(Q)=V^tQ^tU T ( Q ) = V t Q t U V , U V,U V , U S V D SVD S V D A A A
T ( α 1 Q 1 + Q 2 ) = V t ( α 1 Q 1 + Q 2 ) t U = V t ( α 1 Q 1 t + Q 2 t ) U = α 1 V t Q 1 t U + V t Q 2 t U = α 1 T ( Q 1 ) + T ( Q 2 ) T(\alpha_{1}Q_{1}+Q_{2})\!=\!V^t(\alpha_{1}Q_{1}+Q_{2})^tU\!=\!V^t(\alpha_{1}Q_{1}^t+Q_{2}^t)U=\alpha_{1}V^tQ_{1}^tU+V^tQ_{2}^tU=\alpha_{1}T(Q_{1})+T(Q_{2}) T ( α 1 Q 1 + Q 2 ) = V t ( α 1 Q 1 + Q 2 ) t U = V t ( α 1 Q 1 t + Q 2 t ) U = α 1 V t Q 1 t U + V t Q 2 t U = α 1 T ( Q 1 ) + T ( Q 2 ) לכן, לפי הגדרה, האופרטור ליניארי.Q ∈ R 3 × 3 Q \in \mathbb{R}^{3\times3} Q ∈ R 3 × 3 Q Q t = Q t Q = I QQ^t=Q^tQ=I Q Q t = Q t Q = I
( T ( Q ) ) t T ( Q ) = U t Q V V t Q t U = ↓ V t V = I U t Q Q t U = U t U = ↓ U t U = I I (T(Q))^tT(Q)=U^tQVV^tQ^tU \underset{\begin{matrix}
\downarrow \\
V^tV=I
\end{matrix}}{=}U^tQQ^tU=U^tU \underset{\begin{matrix}
\downarrow \\
U^tU=I
\end{matrix}}{=}I ( T ( Q ) ) t T ( Q ) = U t Q V V t Q t U ↓ V t V = I = U t Q Q t U = U t U ↓ U t U = I = I לכן, לכל מטריצה אורתונורמלית ב-R 3 × 3 \mathbb{R}^{3\times 3} R 3 × 3 Q ∈ R 3 × 3 Q \in \mathbb{R}^{3\times3} Q ∈ R 3 × 3 ( T ( Q ) ) t T ( Q ) = I (T(Q))^tT(Q)=I ( T ( Q ) ) t T ( Q ) = I
U t Q V V t Q t U = ↓ V t V = I U t Q Q t U = I U^tQVV^tQ^tU \underset{\begin{matrix}
\downarrow \\
V^tV=I
\end{matrix}}{=}U^tQQ^tU=I U t Q V V t Q t U ↓ V t V = I = U t Q Q t U = I נכפיל מימין ב-U t U^t U t U U U
Q Q t = I QQ^t=I Q Q t = I לכן, Q Q Q T ( Q ) ⟺ T(Q)\iff T ( Q ) ⟺ Q ∈ R 3 × 3 Q \in \mathbb{R}^{3\times 3} Q ∈ R 3 × 3 T ( Q ) = Z T(Q)=Z T ( Q ) = Z Z t Z = I Z^tZ=I Z t Z = I Q t Q = I Q^tQ=I Q t Q = I D = Σ D=\Sigma D = Σ
arg min Z ∈ R 3 × 3 t r ( Z D ) s . t . Z t Z = I \underset{Z \in \mathbb{R}^{3\times3}}{\arg \min}\ tr(ZD)\;\; s.t. \;\; Z^tZ=I Z ∈ R 3 × 3 arg min t r ( Z D ) s . t . Z t Z = I ∎
הראו כי Z = I Z=I Z = I רמז: מצאו חסם הדוק לביטוי מהסעיף הקודם והראו כיצד ניתן להשיגו.
הוכחה: D D D
Z D = ( σ 1 z 11 σ 2 z 12 … σ r z 1 r 0 … 0 σ 1 z 21 σ 2 z 22 … σ r z 2 r 0 … 0 ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ σ 1 z ( n − 1 ) 1 σ 2 z ( n − 1 ) 2 … σ r z ( n − 1 ) r 0 … 0 σ 1 z n 1 σ 2 z n 2 … σ r z n r 0 … 0 ) ZD=\begin{pmatrix}
\sigma_{1}z_{11} & \sigma_{2}z_{12} & \dots & \sigma_{r}z_{1r} & 0 & \dots & 0 \\
\sigma_{1}z_{21} & \sigma_{2}z_{22} & \dots & \sigma_{r}z_{2r} & 0 & \dots & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots & & \vdots \\
\sigma_{1}z_{(n-1)1} & \sigma_{2}z_{(n-1)2} & \dots & \sigma_{r}z_{(n-1)r} & 0 & \dots & 0 \\
\sigma_{1}z_{n1} & \sigma_{2}z_{n2} & \dots & \sigma_{r}z_{nr} & 0 & \dots & 0
\end{pmatrix} Z D = σ 1 z 11 σ 1 z 21 ⋮ σ 1 z ( n − 1 ) 1 σ 1 z n 1 σ 2 z 12 σ 2 z 22 ⋮ σ 2 z ( n − 1 ) 2 σ 2 z n 2 … … ⋱ … … σ r z 1 r σ r z 2 r ⋮ σ r z ( n − 1 ) r σ r z n r 0 0 ⋮ 0 0 … … … … 0 0 ⋮ 0 0 לכן נקבל כי:
t r ( Z D ) = ∑ i = 1 r σ i z i i tr(ZD)=\sum_{i=1}^r \sigma_{i}z_{ii} t r ( Z D ) = i = 1 ∑ r σ i z ii נתון כי Z t Z = I Z^tZ=I Z t Z = I Z Z Z 1 ≤ j ≤ n 1\leq j\leq n 1 ≤ j ≤ n
∥ z ‾ j ∥ 2 2 = ∑ i = 1 n z j i 2 = 1 ⟹ − 1 ≤ z j j ≤ 1 \left\lVert \underline{z}_{j} \right\rVert_{2}^2= \sum_{i=1}^n z_{ji}^2=1 \implies -1\leq z_{jj} \leq 1 z j 2 2 = i = 1 ∑ n z ji 2 = 1 ⟹ − 1 ≤ z jj ≤ 1 לכן:
t r ( Z D ) ≤ ∑ i = 1 r σ i tr(ZD)\leq \sum_{i=1}^r \sigma_{i} t r ( Z D ) ≤ i = 1 ∑ r σ i זה מתקיים עבור Z = I Z=I Z = I i i i I i i = 1 I_{ii}=1 I ii = 1 ∎
מהי המטריצה האופטימלית Q ∗ Q^* Q ∗
כדי למצוא את המטריצה האופטימלית, צריך לזכור מהו Z Z Z Z ∗ = T ( Q ∗ ) = V t ( Q ∗ ) t U = I Z^*=T(Q^*)=V^t(Q^*)^tU=I Z ∗ = T ( Q ∗ ) = V t ( Q ∗ ) t U = I
( Q ∗ ) t = V U t (Q^*)^t=VU^t ( Q ∗ ) t = V U t Q ∗ = U V t Q^*=UV^t Q ∗ = U V t כאשר U , V U,V U , V S V D SV\!D S V D A A A
תרגיל 5
דרגה יציבה של מטריצה A ∈ R n × n A \in \mathbb{R}^{n\times n} A ∈ R n × n
s r a n k ( A ) = ∥ A ∥ F 2 σ m a x 2 srank(A)=\frac{\left\lVert A \right\rVert _{F}^2}{\sigma_{max}^2} sr ank ( A ) = σ ma x 2 ∥ A ∥ F 2 כאשר ∥ A ∥ F \left\lVert A \right\rVert_{F} ∥ A ∥ F A A A σ m a x \sigma_{max} σ ma x A A A S V D SV\!D S V D
הראו כי אם כל n n n A A A v ‾ ≠ 0 \underline{v} \neq 0 v = 0 s r a n k ( A ) = 1 srank(A)=1 sr ank ( A ) = 1 רמז: ראינו בכיתה כי מתקיים ∥ A ∥ F 2 = t r ( A t A ) \left\lVert A \right\rVert_{F}^2=tr(A^tA) ∥ A ∥ F 2 = t r ( A t A ) t r ( A t A ) = ∑ i = 1 n σ i 2 tr(A^tA)=\displaystyle\sum_{i=1}^n \sigma_{i}^2 t r ( A t A ) = i = 1 ∑ n σ i 2
הוכחה:
s r a n k ( A ) = ∥ A ∥ F 2 σ m a x 2 = t r ( A t A ) σ m a x 2 = ∑ i = 1 n σ i 2 σ m a x 2 srank(A)=\frac{\left\lVert A \right\rVert _{F}^2}{\sigma_{max}^2}=\frac{tr(A^tA)}{\sigma_{max}^2}= \frac{\displaystyle \sum_{i=1}^n \sigma_{i}^2}{\sigma_{max}^2} sr ank ( A ) = σ ma x 2 ∥ A ∥ F 2 = σ ma x 2 t r ( A t A ) = σ ma x 2 i = 1 ∑ n σ i 2 אם A = ( ∣ ∣ ∣ v ‾ v ‾ … v ‾ ∣ ∣ ∣ ) A=\begin{pmatrix}\vert & \vert & & \vert \\ \underline{v} & \underline{v} & \dots & \underline{v} \\ \vert & \vert & & \vert\end{pmatrix} A = ∣ v ∣ ∣ v ∣ … ∣ v ∣
A t A = ( − v ‾ t − − v ‾ t − ⋮ − v ‾ t − ) ( ∣ ∣ ∣ v ‾ v ‾ … v ‾ ∣ ∣ ∣ ) = ( v ‾ t v ‾ … v ‾ t v ‾ ⋮ ⋱ ⋮ v ‾ t v ‾ … v ‾ t v ‾ ) A^tA=\begin{pmatrix}
- & \underline{v}^t & - \\
- & \underline{v}^t & - \\
& \vdots \\
- & \underline{v}^t & -
\end{pmatrix}\begin{pmatrix}\vert & \vert & & \vert \\ \underline{v} & \underline{v} & \dots & \underline{v} \\ \vert & \vert & & \vert\end{pmatrix}=\begin{pmatrix}
\underline{v}^t\underline{v} & \dots & \underline{v}^t\underline{v} \\
\vdots & \ddots & \vdots \\
\underline{v}^t\underline{v} & \dots & \underline{v}^t\underline{v}
\end{pmatrix} A t A = − − − v t v t ⋮ v t − − − ∣ v ∣ ∣ v ∣ … ∣ v ∣ = v t v ⋮ v t v … ⋱ … v t v ⋮ v t v מכיוון שיש n n n σ = 0 \sigma=0 σ = 0 n − 1 n-1 n − 1 n v ‾ t v ‾ = t r ( A t A ) = ∑ σ i n\underline{v}^t\underline{v}=tr(A^tA)=\sum \sigma_{i} n v t v = t r ( A t A ) = ∑ σ i σ m a x = n v ‾ t v ‾ \sigma_{max}=n\underline{v}^t\underline{v} σ ma x = n v t v
s r a n k ( A ) = σ m a x 2 + ∑ i = 1 n − 1 0 2 σ m a x 2 = σ m a x 2 σ m a x 2 = 1 srank(A)=\frac{\sigma_{max}^2+\sum_{i=1}^{n-1} 0^2}{\sigma_{max}^2}=\frac{\sigma_{max}^2}{\sigma_{max}^2}=1 sr ank ( A ) = σ ma x 2 σ ma x 2 + ∑ i = 1 n − 1 0 2 = σ ma x 2 σ ma x 2 = 1 ∎
הראו כי אם A A A s r a n k ( A ) = n srank(A)=n sr ank ( A ) = n
הוכחה: A A A S V D SV\!D S V D
A = U Σ V t A=U\Sigma V^t A = U Σ V t נקבע כי U = A U=A U = A U U U Σ = V t = V = I \Sigma=V^t=V=I Σ = V t = V = I A A A
s r a n k ( A ) = 1 σ m a x 2 ∑ i = 1 n σ i 2 = n σ m a x 2 σ m a x 2 = n srank(A)=\frac{1}{\sigma_{max}^2}\sum_{i=1}^n \sigma_{i}^2=\frac{n\sigma_{max}^2}{\sigma_{max}^2}=n sr ank ( A ) = σ ma x 2 1 i = 1 ∑ n σ i 2 = σ ma x 2 n σ ma x 2 = n ∎
באופן כללי, הראו כי תמיד מתקיים 1 ≤ s r a n k ( A ) ≤ n 1\leq srank(A)\leq n 1 ≤ sr ank ( A ) ≤ n
הוכחה: 0 ≤ σ 0\leq \sigma 0 ≤ σ s r a n k ( A ) srank(A) sr ank ( A ) 0 0 0 1 1 1 0 0 0
s r a n k ( A ) = 1 σ m a x 2 ∑ i = 1 n σ i 2 ≥ 0 + ⋯ + 0 + σ m a x 2 + 0 + ⋯ + 0 σ m a x 2 = 1 srank(A)= \frac{1}{\sigma_{max}^2}\sum_{i=1}^n \sigma_{i}^2\geq \frac{0+\dots+0+\sigma_{max}^2+0+\dots+0}{\sigma_{max}^2}=1 sr ank ( A ) = σ ma x 2 1 i = 1 ∑ n σ i 2 ≥ σ ma x 2 0 + ⋯ + 0 + σ ma x 2 + 0 + ⋯ + 0 = 1 המצב המקסימלי מתרחש כאשר כל הערכים הסינגולריים זהים, שכן אז הם כולם ה-m a x max ma x
s r a n k ( A ) = 1 σ m a x 2 ∑ i = 1 n σ i 2 ≤ n σ m a x 2 σ m a x 2 = n srank(A)= \frac{1}{\sigma_{max}^2}\sum_{i=1}^n \sigma_{i}^2 \leq \frac{n\sigma_{max}^2}{\sigma_{max}^2}=n sr ank ( A ) = σ ma x 2 1 i = 1 ∑ n σ i 2 ≤ σ ma x 2 n σ ma x 2 = n לכן מתקיים כי:
1 ≤ s r a n k ( A ) ≤ n 1\leq srank(A)\leq n 1 ≤ sr ank ( A ) ≤ n ∎
הראו כי הדרגה היציבה חוסמת מלמטה את דרגת המטריצה. כלומר:
s r a n k ( A ) ≤ r a n k ( A ) srank(A)\leq rank(A) sr ank ( A ) ≤ r ank ( A ) הוכחה: r a n k ( A ) = r rank(A)=r r ank ( A ) = r A A A r r r
s r a n k ( A ) = 1 σ m a x 2 ∑ i = 1 r σ i 2 ≤ 1 σ m a x 2 ∑ i = 1 r σ m a x 2 = r = r a n k ( A ) srank(A)=\frac{1}{\sigma_{max}^2}\sum_{i=1}^r \sigma_{i}^2\leq \frac{1}{\sigma_{max}^2}\sum_{i=1}^r \sigma_{max}^2=r =rank(A) sr ank ( A ) = σ ma x 2 1 i = 1 ∑ r σ i 2 ≤ σ ma x 2 1 i = 1 ∑ r σ ma x 2 = r = r ank ( A ) לכן מתקיים:
s r a n k ( A ) ≤ r a n k ( A ) srank(A)\leq rank(A) sr ank ( A ) ≤ r ank ( A ) ∎
תרגיל 6
נורמה ∥ ⋅ ∥ \lVert \cdot \rVert ∥ ⋅ ∥ A ∈ R m × n A \in \mathbb{R}^{m\times n} A ∈ R m × n Q ∈ R n × n Q \in \mathbb{R}^{n\times n} Q ∈ R n × n P ∈ R m × m P \in \mathbb{R}^{m\times m} P ∈ R m × m
∥ P A Q ∥ = ∥ A ∥ \left\lVert PAQ \right\rVert =\left\lVert A \right\rVert ∥ P A Q ∥ = ∥ A ∥ הראו כי נורמת פורביניוס אינווריאנטית יוניטרית. כלומר, הראו כי מתקיים ∥ P A Q ∥ F 2 = ∥ A ∥ F 2 \left\lVert PAQ \right\rVert_{F}^2=\left\lVert A \right\rVert_{F}^2 ∥ P A Q ∥ F 2 = ∥ A ∥ F 2
הוכחה:
∥ P A Q ∥ F 2 = t r ( Q t A t P t P A Q ) = ↓ P t P = I t r ( Q t A t A Q ) = ↓ t r ( A B ) = t r ( B A ) t r ( A t A Q Q t ) = ↓ Q t Q = Q Q t = I t r ( A t A ) = ∥ A ∥ F 2 \left\lVert PAQ \right\rVert _{F}^2=tr(Q^tA^tP^tPAQ) \underset{\begin{matrix}
\downarrow \\
P^tP=I
\end{matrix}}{=}tr(Q^tA^tAQ)\!\!\!\!\!\!\!\!\!\!\underset{\begin{matrix}
\downarrow \\
tr(AB)=tr(BA)
\end{matrix}}{=}\!\!\!\!\!\!\!\!\!\! tr(A^tAQQ^t) \!\!\!\!\!\!\!\!\!\!\underset{\begin{matrix}
\downarrow \\
Q^tQ=QQ^t=I
\end{matrix}}{=}\!\!\!\!\!\!\!\!\!\!tr(A^tA)=\left\lVert A \right\rVert _{F}^2 ∥ P A Q ∥ F 2 = t r ( Q t A t P t P A Q ) ↓ P t P = I = t r ( Q t A t A Q ) ↓ t r ( A B ) = t r ( B A ) = t r ( A t A Q Q t ) ↓ Q t Q = Q Q t = I = t r ( A t A ) = ∥ A ∥ F 2 ∎
נסמן ב-σ i ( A ) \sigma_{i}(A) σ i ( A ) i i i A A A
∥ A ∥ F = ∑ i = 1 σ i 2 ( A ) \left\lVert A \right\rVert _{F}=\sqrt{ \sum_{i=1} \sigma_{i}^2(A) } ∥ A ∥ F = i = 1 ∑ σ i 2 ( A ) רמז: העזרו בפירוק S V D SV\!D S V D A A A t r a c e trace t r a ce
הוכחה: A A A S V D SV\!D S V D A = U Σ V t A=U\Sigma V^t A = U Σ V t
∥ A ∥ F 2 = t r ( A t A ) = t r ( V Σ U t U Σ V t ) = ↓ U t U = I t r ( V Σ 2 V t ) = ↓ t r ( A B ) = t r ( B A ) t r ( V t V Σ 2 ) = ↓ V t V = I t r ( Σ 2 ) \left\lVert A \right\rVert _{F}^2=tr(A^tA)=tr(V\Sigma U^tU\Sigma V^t) \underset{\begin{matrix}
\downarrow \\
U^tU=I
\end{matrix}}{=}tr(V\Sigma^2V^t) \underset{\begin{matrix}
\downarrow \\
tr(AB)=tr(BA)
\end{matrix}}{=}tr(V^tV\Sigma^2) \underset{\begin{matrix}
\downarrow \\
V^tV=I
\end{matrix}}{=} tr(\Sigma^2) ∥ A ∥ F 2 = t r ( A t A ) = t r ( V Σ U t U Σ V t ) ↓ U t U = I = t r ( V Σ 2 V t ) ↓ t r ( A B ) = t r ( B A ) = t r ( V t V Σ 2 ) ↓ V t V = I = t r ( Σ 2 ) Σ \Sigma Σ A A A r a n k ( A ) = r rank(A)=r r ank ( A ) = r A A A r r r
Σ 2 = ( σ 1 2 ⋱ σ r 2 0 ⋱ 0 ) \Sigma^2=\begin{pmatrix}
\sigma_{1}^2 \\
& \ddots \\
& & \sigma_{r}^2 \\
& & & 0 \\
& & & & \ddots \\
& & & & & 0
\end{pmatrix} Σ 2 = σ 1 2 ⋱ σ r 2 0 ⋱ 0 ולכן:
∥ A ∥ F 2 = t r ( Σ 2 ) = ∑ i = 1 r σ i 2 ( A ) \left\lVert A \right\rVert_{F}^2= tr(\Sigma^2)=\sum_{i=1}^r \sigma_{i}^2(A) ∥ A ∥ F 2 = t r ( Σ 2 ) = i = 1 ∑ r σ i 2 ( A ) ולכן מתקיים:
∥ A ∥ F = ∑ i = 1 r σ i 2 ( A ) \left\lVert A \right\rVert _{F}=\sqrt{ \sum_{i=1}^r \sigma_{i}^2(A) } ∥ A ∥ F = i = 1 ∑ r σ i 2 ( A ) ∎