תרגיל 1
לאורך כל שאלה זו נתון כי S , T S,T S , T ρ \rho ρ
נתונה מערכת דינמית x ‾ k + 1 = T x ‾ k \underline{x}_{k+1}=T\underline{x}_{k} x k + 1 = T x k T T T ρ ( T ) ≥ 1 \rho(T)\geq1 ρ ( T ) ≥ 1 x ‾ 0 \underline{x}_{0} x 0
נסתכל על המטריצה T = ( 0 0 0 1 ) T=\begin{pmatrix}0 & 0\\ 0 & 1\end{pmatrix} T = ( 0 0 0 1 ) λ = 0 , 1 \lambda=0,1 λ = 0 , 1 r ( T ) < n r(T)<n r ( T ) < n ρ ( T ) = max λ i = 1 ≥ 1 \rho (T)=\max \lambda_{i}=1\geq 1 ρ ( T ) = max λ i = 1 ≥ 1 x ‾ 0 = ( 1 1 ) \underline{x}_{0}=\begin{pmatrix}1\\ 1\end{pmatrix} x 0 = ( 1 1 )
x ‾ k = T k x ‾ 0 = ( 0 k 0 0 1 k ) ( 1 1 ) = ( 0 0 0 1 ) ( 1 1 ) = ( 0 1 ) \underline{x}_{k}=T^k\underline{x}_{0}=\begin{pmatrix}
0^k & 0 \\
0 & 1^k
\end{pmatrix}\begin{pmatrix}
1 \\
1
\end{pmatrix}=\begin{pmatrix}
0 & 0 \\
0 & 1
\end{pmatrix}\begin{pmatrix}
1 \\
1
\end{pmatrix}=\begin{pmatrix}
0 \\
1
\end{pmatrix} x k = T k x 0 = ( 0 k 0 0 1 k ) ( 1 1 ) = ( 0 0 0 1 ) ( 1 1 ) = ( 0 1 ) ולכן:
lim k → ∞ x ‾ k = lim k → ∞ ( 0 1 ) = ( 0 1 ) ≠ ( 0 0 ) \lim_{ k \to \infty } \underline{x}_{k}=\lim_{ k \to \infty } \begin{pmatrix}
0 \\
1
\end{pmatrix}=\begin{pmatrix}
0 \\
1
\end{pmatrix}\neq \begin{pmatrix}
0 \\
0
\end{pmatrix} k → ∞ lim x k = k → ∞ lim ( 0 1 ) = ( 0 1 ) = ( 0 0 ) ולכן, המערכת אינה מתכנסת עבור x ‾ 0 \underline{x}_{0} x 0
הוכיחו או הפריכו כי ∥ ∣ T t T ∣ ∥ 2 \sqrt{ \lVvert T^tT \rVvert_{2} } ∥ ∣ T t T ∣ ∥ 2 T T T
הטענה נכונה .הוכחה: T t T T^tT T t T
∥ ∣ T t T ∣ ∥ 2 = ↓ פיתוח מההרצאה σ 1 ( T t T ) = λ 1 ( T t T ) = σ 1 ( A ) = ↓ פיתוח מההרצאה ∥ ∣ T ∣ ∥ 2 2 \sqrt{ \lVvert T^tT \rVvert_{2} } \underset{\begin{matrix}
\downarrow \\
\R{\text{פיתוח מההרצאה}}
\end{matrix}}{=}\sqrt{ \sigma_{1}(T^tT) }=\sqrt{ \lambda_{1}(T^tT) }=\sigma_{1}(A)\underset{\begin{matrix}
\downarrow \\
\R{\text{פיתוח מההרצאה}}
\end{matrix}}{=}\lVvert T \rVvert _{2}^2 ∥ ∣ T t T ∣ ∥ 2 ↓ פיתוח מההרצאה = σ 1 ( T t T ) = λ 1 ( T t T ) = σ 1 ( A ) ↓ פיתוח מההרצאה = ∥ ∣ T ∣ ∥ 2 2 ולכן, מכיוון ש-∥ ∣ T ∣ ∥ 2 \lVvert T \rVvert_{2} ∥ ∣ T ∣ ∥ 2 ∥ ∣ T t T ∣ ∥ 2 \sqrt{ \lVvert T^tT \rVvert_{2} } ∥ ∣ T t T ∣ ∥ 2 ∎
הוכיחו או הפריכו כי ∥ T 2 ∥ F \sqrt{ \left\lVert T^2 \right\rVert_{F} } ∥ T 2 ∥ F T T T
הטענה לא נכונה .A = ( 0 1 0 0 ) A=\begin{pmatrix}0 & 1 \\ 0 & 0\end{pmatrix} A = ( 0 0 1 0 )
∥ A 2 ∥ F = ∥ ( 0 1 0 0 ) ( 0 1 0 0 ) ∥ F = ∥ ( 0 0 0 0 ) ∥ F = 0 \sqrt{ \left\lVert A^2 \right\rVert_{F} }=\sqrt{ \left\lVert \begin{pmatrix}
0 & 1 \\
0 & 0
\end{pmatrix}\begin{pmatrix}
0 & 1 \\
0 & 0
\end{pmatrix} \right\rVert_{F} }=\sqrt{ \left\lVert \begin{pmatrix}
0 & 0 \\
0 & 0
\end{pmatrix} \right\rVert_{F} }=0 ∥ A 2 ∥ F = ( 0 0 1 0 ) ( 0 0 1 0 ) F = ( 0 0 0 0 ) F = 0 נשים לב כי עבור A ≠ 0 A\neq 0 A = 0 ∥ A 2 ∥ F = 0 \sqrt{ \left\lVert A^2 \right\rVert_{F} }=0 ∥ A 2 ∥ F = 0
נתונה מערכת דינמית x ‾ k + 1 = T x ‾ k \underline{x}_{k+1}=T\underline{x}_{k} x k + 1 = T x k n n n ∥ ∣ T n ∣ ∥ < 1 \lVvert T^n \rVvert<1 ∥ ∣ T n ∣ ∥ < 1
הוכחה: ρ { T } ≤ ∥ ∣ T n ∣ ∥ < 1 \rho\left\{ T \right\}\leq \lVvert T^n \rVvert<1 ρ { T } ≤ ∥ ∣ T n ∣ ∥ < 1 ρ { T } < 1 \rho \left\{ T \right\}<1 ρ { T } < 1 x ‾ k + 1 = T k x ‾ 0 → k → ∞ 0 \underline{x}_{k+1}=T^k\underline{x}_{0}\rarrowlim{k\to \infty}0 x k + 1 = T k x 0 k → ∞ 0 ∎
עבור שני הסעיפים הבאים ידוע כי ρ { T } < 1 , ρ { T } < 1 \rho \left\{ T \right\}<1,\;\rho \left\{ T \right\}<1 ρ { T } < 1 , ρ { T } < 1
x ‾ t e m p = T x ‾ k x ‾ k + 1 = S x ‾ t e m p \begin{matrix}
\underline{x}_{temp}=T\underline{x}_{k} \\
\underline{x}_{k+1}=S\underline{x}_{temp}
\end{matrix} x t e m p = T x k x k + 1 = S x t e m p הוכיחו או הפריכו שמערכת זו יציבה, כלומר מתכנסת ל-0 0 0 x ‾ 0 \underline{x}_{0} x 0 S , T S,T S , T
הטענה נכונה .הוכחה: x ‾ k + 1 = T x ‾ k \underline{x}_{k+1}=T\underline{x}_{k} x k + 1 = T x k ∥ ∣ T n ∣ ∥ < 1 \lVvert T^n \rVvert<1 ∥ ∣ T n ∣ ∥ < 1 ∥ ∣ T ∣ ∥ 2 < 1 \lVvert T \rVvert_{2}<1 ∥ ∣ T ∣ ∥ 2 < 1 x ‾ k + 1 = T x ‾ k \underline{x}_{k+1}=T\underline{x}_{k} x k + 1 = T x k
x ‾ k + 1 = S x ‾ t e m p = S T x ‾ k \underline{x}_{k+1}=S\underline{x}_{temp}=ST\underline{x}_{k} x k + 1 = S x t e m p = ST x k עבור מטריצות סימטריות כגון T , S T,S T , S
∥ ∣ T ∣ ∥ 2 = ρ { T } ∧ ∥ ∣ S ∣ ∥ 2 = ρ { S } \lVvert T \rVvert _{2}= \rho \left\{ T \right\} \land \lVvert S \rVvert_{2}=\rho \left\{ S \right\} ∥ ∣ T ∣ ∥ 2 = ρ { T } ∧ ∥ ∣ S ∣ ∥ 2 = ρ { S } לפי תכונות של נורמות מתקיים:
∥ ∣ S T ∣ ∥ 2 ≤ ∥ ∣ S ∣ ∥ 2 ⋅ ∥ ∣ T ∣ ∥ 2 < ↓ ρ { T } , ρ { S } < 1 1 ⋅ 1 = 1 \lVvert ST \rVvert_{2} \leq \lVvert S \rVvert _{2}\cdot \lVvert T \rVvert _{2} \underset{\begin{matrix}
\downarrow \\
\rho \left\{ T \right\},\rho \left\{ S \right\}<1
\end{matrix}}{<} 1\cdot 1=1 ∥ ∣ ST ∣ ∥ 2 ≤ ∥ ∣ S ∣ ∥ 2 ⋅ ∥ ∣ T ∣ ∥ 2 ↓ ρ { T } , ρ { S } < 1 < 1 ⋅ 1 = 1 ולכן, לפי הנ"ל, המערכת מתכנסת ל-0 0 0 x ‾ 0 \underline{x}_{0} x 0 ∎
הוכיחו או הפריכו כי מערכת זו יציבה לכל S , T S,T S , T
הטענה אינה נכונה .S = ( 0 0 10 0 ) , T = ( 0 10 0 0 ) S=\begin{pmatrix}0 & 0 \\ 10 & 0\end{pmatrix},T=\begin{pmatrix}0 & 10 \\ 0 & 0\end{pmatrix} S = ( 0 10 0 0 ) , T = ( 0 0 10 0 ) ρ { S T } < 1 \rho \left\{ ST \right\}<1 ρ { ST } < 1
S T = ( 0 0 10 0 ) ( 0 10 0 0 ) = ( 0 0 0 100 ) ST=\begin{pmatrix}
0 & 0 \\
10 & 0
\end{pmatrix}\begin{pmatrix}
0 & 10 \\
0 & 0
\end{pmatrix}=\begin{pmatrix}
0 & 0 \\
0 & 100
\end{pmatrix} ST = ( 0 10 0 0 ) ( 0 0 10 0 ) = ( 0 0 0 100 ) S T ST ST λ = 100 \lambda=100 λ = 100 S T ST ST ρ { S T } > 1 \rho \left\{ ST \right\}>1 ρ { ST } > 1 x ‾ k + 1 = S T x ‾ k \underline{x}_{k+1}=ST\underline{x}_{k} x k + 1 = ST x k
תרגיל 2
נתונה מערכת דינמית מהצורה x ‾ k + 1 = T x ‾ k + c ‾ \underline{x}_{k+1}=T\underline{x}_{k}+\underline{c} x k + 1 = T x k + c T T T n × n n\times n n × n c ‾ ∈ R n \underline{c} \in \mathbb{R}^n c ∈ R n c ‾ \underline{c} c T T T x ‾ ∗ \underline{x}^* x ∗ x ‾ ∗ = T x ‾ ∗ + c ‾ \underline{x}^*=T\underline{x}^*+\underline{c} x ∗ = T x ∗ + c A x ‾ = b ‾ A\underline{x}=\underline{b} A x = b A A A
על מנת שהמשוואה הנתונה תהיה פתרון של מערכת המשוואת נדרוש כי x ‾ ∗ = A − 1 b ‾ \underline{x}^*=A^{-1}\underline{b} x ∗ = A − 1 b A A A
( I − T ) x ‾ ∗ = c ‾ ⟹ ( I − T ) A − 1 b ‾ = c ‾ (I-T)\underline{x}^*=\underline{c}\implies (I-T)A^{-1}\underline{b}=\underline{c} ( I − T ) x ∗ = c ⟹ ( I − T ) A − 1 b = c וזוהי המשוואה שעל T , c ‾ T,\underline{c} T , c
מפה והלאה נניח כי T T T r a n k ( T ) = 1 rank(T)=1 r ank ( T ) = 1 e ‾ k + 1 = T e ‾ k \underline{e}_{k+1}=T\underline{e}_{k} e k + 1 = T e k e ‾ k ≡ x ‾ k − x ‾ ∗ \underline{e}_{k}\equiv \underline{x}_{k}-\underline{x}^* e k ≡ x k − x ∗
עבור ניחוש התחלתי x ‾ 0 \underline{x}_{0} x 0 x ‾ 1 , x ‾ 2 \underline{x}_{1},\underline{x}_{2} x 1 , x 2 x ‾ 2 − x ‾ ∗ = α ( x ‾ 1 − x ‾ ∗ ) \underline{x}_{2}-\underline{x}^*=\alpha(\underline{x}_{1}-\underline{x}^*) x 2 − x ∗ = α ( x 1 − x ∗ ) α ∈ R \alpha \in \mathbb{R} α ∈ R
הוכחה: e ‾ k = x ‾ k − x ‾ ∗ \underline{e}_{k}=\underline{x}_{k}-\underline{x}^* e k = x k − x ∗
x ‾ 2 − x ‾ ∗ = e ‾ 2 = T e ‾ 1 = T 2 e ‾ 0 = T 2 ( x ‾ 0 − x ‾ ∗ ) \underline{x}_{2}-\underline{x}^*=\underline{e}_{2}=T\underline{e}_{1}=T^2\underline{e}_{0}=T^2(\underline{x}_{0}-\underline{x}^*) x 2 − x ∗ = e 2 = T e 1 = T 2 e 0 = T 2 ( x 0 − x ∗ ) נתון כי r a n k ( T ) = 1 rank(T)=1 r ank ( T ) = 1 u , v ∈ R n u,v \in \mathbb{R}^n u , v ∈ R n T = v ‾ u ‾ t T=\underline{v}\;\!\underline{u}^t T = v u t
T 2 = v ‾ u ‾ t v ‾ u ‾ t = ( u ‾ t v ‾ ) v ‾ u ‾ t = ( u ‾ t v ‾ ) T T^2=\underline{v}\;\!\underline{u}^t\underline{v}\;\underline{u}^t=(\underline{u}^t\underline{v})\underline{v}\;\!\underline{u}^t=(\underline{u}^t\underline{v})T T 2 = v u t v u t = ( u t v ) v u t = ( u t v ) T ולכן:
x ‾ 2 − x ‾ ∗ = ( u ‾ t v ‾ ) T ( x ‾ 0 − x ‾ ∗ ) \underline{x}_{2}-\underline{x}^*=(\underline{u}^t\underline{v})T(\underline{x}_{0}-\underline{x}^*) x 2 − x ∗ = ( u t v ) T ( x 0 − x ∗ ) בנוסף, מתקיים כי:
x ‾ 1 − x ‾ ∗ = e ‾ 1 = T e ‾ 0 = T ( x ‾ 0 − x ‾ ∗ ) \underline{x}_{1}-\underline{x}^*=\underline{e}_{1}=T\underline{e}_{0}=T(\underline{x}_{0}-\underline{x}^*) x 1 − x ∗ = e 1 = T e 0 = T ( x 0 − x ∗ ) לכן:
( u ‾ t v ‾ ) ( x ‾ 1 − x ‾ ∗ ) = ( u ‾ t v ‾ ) T ( x ‾ 0 − x ‾ ∗ ) = x ‾ 2 − x ‾ ∗ (\underline{u}^t\underline{v})(\underline{x}_{1}-\underline{x}^*)=(\underline{u}^t\underline{v})T(\underline{x}_{0}-\underline{x}^*)=\underline{x}_{2}-\underline{x}^* ( u t v ) ( x 1 − x ∗ ) = ( u t v ) T ( x 0 − x ∗ ) = x 2 − x ∗ נגדיר α = u ‾ t v ‾ ∈ R \alpha=\underline{u}^t\underline{v}\in \mathbb{R} α = u t v ∈ R
x ‾ 2 − x ‾ ∗ = α ( x ‾ 1 − x ‾ ∗ ) \underline{x}_{2}-\underline{x}^*=\alpha(\underline{x}_{1}-\underline{x}^*) x 2 − x ∗ = α ( x 1 − x ∗ ) ∎
הראו כי x ‾ ∗ = ε x ‾ 2 + ( 1 − ε ) x ‾ 1 \underline{x}^*=\epsilon \underline{x}_{2}+(1-\epsilon)\underline{x}_{1} x ∗ = ε x 2 + ( 1 − ε ) x 1 ε ∈ R \epsilon \in \mathbb{R} ε ∈ R ε \epsilon ε α \alpha α
x ‾ 2 − x ‾ ∗ = α ( x ‾ 1 − x ‾ ∗ ) = α x ‾ 1 − α x ‾ ∗ ⟹ α x ‾ 1 − x ‾ 2 = ( α − 1 ) x ‾ ∗ \underline{x}_{2}-\underline{x}^*=\alpha(\underline{x}_{1}-\underline{x}^*)=\alpha \underline{x}_{1}-\alpha \underline{x}^*\implies \alpha \underline{x}_{1}-\underline{x}_{2}=(\alpha-1)\underline{x}^* x 2 − x ∗ = α ( x 1 − x ∗ ) = α x 1 − α x ∗ ⟹ α x 1 − x 2 = ( α − 1 ) x ∗ ⟹ x ‾ ∗ = α α − 1 x ‾ 1 − 1 α − 1 x ‾ 2 \implies \underline{x}^*=\frac{\alpha}{\alpha-1}\underline{x}_{1}-\frac{1}{\alpha-1}\underline{x}_{2} ⟹ x ∗ = α − 1 α x 1 − α − 1 1 x 2 אם נגדיר ε = − 1 α − 1 \epsilon=-\frac{1}{\alpha-1} ε = − α − 1 1 α − 1 = − 1 ε \alpha-1=-\frac{1}{\epsilon} α − 1 = − ε 1 α = 1 − 1 ε \alpha=1-\frac{1}{\epsilon} α = 1 − ε 1
x ‾ ∗ = ( 1 − 1 ε ) ( − ε ) x ‾ 1 + ε x ‾ 2 = ε x ‾ 2 + ( 1 − ε ) x ‾ 1 \underline{x}^*=\left( 1-\frac{1}{\epsilon} \right)(-\epsilon)\underline{x}_{1}+\epsilon \underline{x}_{2}=\epsilon \underline{x}_{2}+(1-\epsilon)\underline{x}_{1} x ∗ = ( 1 − ε 1 ) ( − ε ) x 1 + ε x 2 = ε x 2 + ( 1 − ε ) x 1
בהמשך לסעיף ג', נגדיר את בעיית הריבועים הפחותים עבור הסקלר ε ∗ \epsilon_{*} ε ∗
ε ∗ = arg min ε 1 2 ∥ A ( ε x ‾ 2 + ( 1 − ε ) x ‾ 1 ) − b ‾ ∥ 2 2 \epsilon_{*}=\underset{\epsilon}{\arg\min} \frac{1}{2}\left\lVert A(\epsilon \underline{x}_{2}+(1-\epsilon)\underline{x}_{1})-\underline{b} \right\rVert _{2}^2 ε ∗ = ε arg min 2 1 ∥ A ( ε x 2 + ( 1 − ε ) x 1 ) − b ∥ 2 2 רשמו נוסחה מפורשת וקלה לחישוב עבור ε ∗ \epsilon_{*} ε ∗ A , b ‾ , x ‾ 1 , x ‾ 2 A,\underline{b},\underline{x}_{1},\underline{x}_{2} A , b , x 1 , x 2
A ( ε x ‾ 2 + ( 1 − ε ) x ‾ 1 ) − b ‾ = ε A x ‾ 2 + ( 1 − ε ) A x ‾ 1 − b ‾ = ε A x ‾ 2 + A x ‾ 1 − ε A x ‾ 1 − b ‾ A(\epsilon \underline{x}_{2}+(1-\epsilon)\underline{x}_{1})-\underline{b}=\epsilon A\underline{x}_{2}+(1-\epsilon)A\underline{x}_{1}-\underline{b}=\epsilon A\underline{x}_{2}+A\underline{x}_{1}-\epsilon A\underline{x}_{1}-\underline{b} A ( ε x 2 + ( 1 − ε ) x 1 ) − b = ε A x 2 + ( 1 − ε ) A x 1 − b = ε A x 2 + A x 1 − ε A x 1 − b = ε ( A x ‾ 2 − A x ‾ 1 ) + A x ‾ 1 − b ‾ =\epsilon(A\underline{x}_{2}-A\underline{x}_{1})+A\underline{x}_{1}-\underline{b} = ε ( A x 2 − A x 1 ) + A x 1 − b נסמן v ‾ = A ( x ‾ 2 − x ‾ 1 ) \underline{v}=A(\underline{x}_{2}-\underline{x}_{1}) v = A ( x 2 − x 1 ) u ‾ = b ‾ − A x ‾ 1 \underline{u}=\underline{b}-A\underline{x}_{1} u = b − A x 1
ε ∗ = arg max ε 1 2 ∥ ε v ‾ − u ‾ ∥ 2 2 \epsilon_{*}=\underset{\epsilon}{\arg \max} \frac{1}{2}\left\lVert \epsilon \underline{v}-\underline{u} \right\rVert _{2}^2 ε ∗ = ε arg max 2 1 ∥ ε v − u ∥ 2 2 נשים לב כי v ‾ , u ‾ \underline{v},\underline{u} v , u
v ‾ t v ‾ ε ∗ = v ‾ t u ‾ \underline{v}^t\underline{v}\epsilon_{*}=\underline{v}^t\underline{u} v t v ε ∗ = v t u נחלק בסקלר v ‾ t v ‾ \underline{v}^t\underline{v} v t v
ε ∗ = v ‾ t u ‾ v ‾ t v ‾ = ( x ‾ 2 t − x ‾ 1 t ) A t ( b ‾ − A x ‾ 1 ) ( x ‾ 2 t − x ‾ 1 t ) A t A ( x ‾ 2 − x ‾ 1 ) \epsilon_{*}=\frac{\underline{v}^t\underline{u}}{\underline{v}^t\underline{v}}=\frac{(\underline{x}_{2}^t-\underline{x}_{1}^t)A^t(\underline{b}-A\underline{x}_{1})}{(\underline{x}_{2}^t-\underline{x}_{1}^t)A^tA(\underline{x}_{2}-\underline{x}_{1})} ε ∗ = v t v v t u = ( x 2 t − x 1 t ) A t A ( x 2 − x 1 ) ( x 2 t − x 1 t ) A t ( b − A x 1 ) וזוהי הנוסחה המפורשת והקלה לחישוב עבור ε ∗ \epsilon_{*} ε ∗
נגדיר:
A = ( 1 0 1 − 2 1 1 1 2 1 ) , b ‾ = ( 3.5 1 2 ) A=\begin{pmatrix}
1 & 0 & 1 \\
-2 & 1 & 1 \\
1 & 2 & 1
\end{pmatrix},\;\; \underline{b}=\begin{pmatrix}
3.5 \\
1 \\
2
\end{pmatrix} A = 1 − 2 1 0 1 2 1 1 1 , b = 3.5 1 2 הוכיחו או הפריכו כי שיטת גאוס-איידל לפתרון המערכת A x ‾ = b ‾ A\underline{x}=\underline{b} A x = b x ‾ \underline{x} x x ‾ 0 \underline{x}_{0} x 0
הטענה אינה נכונה .הוכחה: L , D , U L,D,U L , D , U A = L + D + U A=L+D+U A = L + D + U
x ‾ k + 1 = ( L + D ) − 1 ( b ‾ − U x ‾ k ) \underline{x}_{k+1}=(L+D)^{-1}(\underline{b}-U\underline{x}_{k}) x k + 1 = ( L + D ) − 1 ( b − U x k ) נבדוק מיהי המטריצה T T T
x ‾ k + 1 = − ( L + D ) − 1 U x ‾ k + ( L + D ) − 1 b ‾ \underline{x}_{k+1}=-(L+D)^{-1}U\underline{x}_{k}+(L+D)^{-1}\underline{b} x k + 1 = − ( L + D ) − 1 U x k + ( L + D ) − 1 b נסמן T = − ( L + D ) − 1 U T=-(L+D)^{-1}U T = − ( L + D ) − 1 U T T T T T T
∣ T − λ I ∣ = ∣ λ I − T ∣ = ∣ λ I + ( L + D ) − 1 U ∣ |T-\lambda I|=|\lambda I-T|=|\lambda I+(L+D)^{-1}U| ∣ T − λ I ∣ = ∣ λ I − T ∣ = ∣ λ I + ( L + D ) − 1 U ∣ נשים לב כי D = ( 1 1 1 ) D=\begin{pmatrix}1 \\ & 1 \\ & & 1\end{pmatrix} D = 1 1 1 L = ( − 2 1 2 ) L=\begin{pmatrix} \\ -2 \\ 1 & 2 & \end{pmatrix} L = − 2 1 2 L + D = ( 1 − 2 1 1 2 1 ) L+D=\begin{pmatrix}1 \\ -2 & 1 \\ 1 & 2 & 1\end{pmatrix} L + D = 1 − 2 1 1 2 1 ∣ L + D ∣ = 1 |L+D|=1 ∣ L + D ∣ = 1
∣ T − λ I ∣ = ∣ L + D ∣ ∣ T − λ I ∣ = ∣ L + D ∣ ∣ λ I + ( L + D ) − 1 U ∣ = ∣ λ ( L + D ) + U ∣ |T-\lambda I|=|L+D||T-\lambda I|=|L+D||\lambda I+(L+D)^{-1}U|=|\lambda(L+D)+U| ∣ T − λ I ∣ = ∣ L + D ∣∣ T − λ I ∣ = ∣ L + D ∣∣ λ I + ( L + D ) − 1 U ∣ = ∣ λ ( L + D ) + U ∣ נציב כעת את המטריצות:
∣ T − λ I ∣ = ∣ λ 0 1 − 2 λ λ 1 λ 2 λ λ ∣ = λ ∣ λ 1 2 λ λ ∣ + ∣ − 2 λ λ λ 2 λ ∣ = λ ( λ 2 − 2 λ ) + ( − 4 λ 2 − λ 2 ) = λ 3 − 7 λ 2 = λ 2 ( λ − 7 ) = 0 ⟹ λ 1 , 2 = 0 , λ 3 = 7 \begin{align*}
|T-\lambda I|&=\begin{vmatrix}
\lambda & 0 & 1 \\
-2\lambda & \lambda & 1 \\
\lambda & 2\lambda & \lambda
\end{vmatrix}=\lambda \begin{vmatrix}
\lambda & 1 \\
2\lambda & \lambda
\end{vmatrix}+\begin{vmatrix}
-2\lambda & \lambda \\
\lambda & 2\lambda
\end{vmatrix}=\lambda(\lambda^2-2\lambda)+(-4\lambda^2-\lambda^2)=\lambda^3-7\lambda^2 \\
&=\lambda^2(\lambda-7)=0 \implies \lambda_{1,2}=0, \; \lambda_{3}=7
\end{align*} ∣ T − λ I ∣ = λ − 2 λ λ 0 λ 2 λ 1 1 λ = λ λ 2 λ 1 λ + − 2 λ λ λ 2 λ = λ ( λ 2 − 2 λ ) + ( − 4 λ 2 − λ 2 ) = λ 3 − 7 λ 2 = λ 2 ( λ − 7 ) = 0 ⟹ λ 1 , 2 = 0 , λ 3 = 7 לכן, ρ { T } = 7 > 1 \rho \left\{ T \right\}=7>1 ρ { T } = 7 > 1 x ‾ 0 \underline{x}_{0} x 0 ∎
האם ניתן לפתור את המערכת מסעיף ה' באמצעות שתי איטרציות של גאוס-איידל בשיטה שהוצעה בסעיפים ב'-ד'?
ראינו כי לא משנה מהם x ‾ 1 , x ‾ 2 \underline{x}_{1},\underline{x}_{2} x 1 , x 2 ε ∗ \epsilon_{*} ε ∗ x ‾ ∗ \underline{x}^* x ∗
תרגיל 3
נתונה מערכת המשוואות הבאה A x ‾ = b ‾ A\underline{x}=\underline{b} A x = b
A = ( 6 1 2 2 10 3 3 4 14 ) , b ‾ = ( 9 15 21 ) A=\begin{pmatrix}
6 & 1 & 2 \\
2 & 10 & 3 \\
3 & 4 & 14
\end{pmatrix},\;\;\; \underline{b}=\begin{pmatrix}
9 \\
15 \\
21
\end{pmatrix} A = 6 2 3 1 10 4 2 3 14 , b = 9 15 21 נרצה למצוא את x ‾ \underline{x} x x ‾ k + 1 = T x ‾ k + c ‾ \underline{x}_{k+1}=T\underline{x}_{k}+\underline{c} x k + 1 = T x k + c T , c ‾ T,\underline{c} T , c
יהיו 3 מטריצות L , D , U L,D,U L , D , U A = L + D + U A=L+D+U A = L + D + U
x ‾ k + 1 = − D − 1 ( L + U ) ⏟ T x ‾ k + D − 1 b ‾ ⏟ c ‾ \underline{x}_{k+1}=\underbrace{-D^{-1}(L+U)}_{T}\underline{x}_{k}+\underbrace{D^{-1}\underline{b}}_{\underline{c}} x k + 1 = T − D − 1 ( L + U ) x k + c D − 1 b נסתכל על המטריצות D , L , U D,L,U D , L , U
L = ( 0 0 0 2 0 0 3 4 0 ) , D = ( 6 0 0 0 10 0 0 0 14 ) , U = ( 0 1 2 0 0 3 0 0 0 ) L=\begin{pmatrix}
0 & 0 & 0 \\
2 & 0 & 0 \\
3 & 4 & 0
\end{pmatrix},\;\; D=\begin{pmatrix}
6 & 0 & 0 \\
0 & 10 & 0 \\
0 & 0 & 14
\end{pmatrix},\;\; U=\begin{pmatrix}
0 & 1 & 2 \\
0 & 0 & 3 \\
0 & 0 & 0
\end{pmatrix} L = 0 2 3 0 0 4 0 0 0 , D = 6 0 0 0 10 0 0 0 14 , U = 0 0 0 1 0 0 2 3 0 ולכן:
D − 1 = ( 1 6 0 0 0 1 10 0 0 0 1 14 ) D^{-1}=\begin{pmatrix}
\frac{1}{6} & 0 & 0 \\
0 & \frac{1}{10} & 0 \\
0 & 0 & \frac{1}{14}
\end{pmatrix} D − 1 = 6 1 0 0 0 10 1 0 0 0 14 1 ובכך:
T = − ( 1 6 0 0 0 1 10 0 0 0 1 14 ) ( 0 1 2 2 0 3 3 4 0 ) = − ( 0 1 6 1 3 2 10 0 3 10 3 14 4 14 0 ) = ( 0 − 1 6 − 1 3 − 1 5 0 − 3 10 − 3 14 − 4 14 0 ) T=-\begin{pmatrix}
\frac{1}{6} & 0 & 0 \\
0 & \frac{1}{10} & 0 \\
0 & 0 & \frac{1}{14}
\end{pmatrix}\begin{pmatrix}
0 & 1 & 2 \\
2 & 0 & 3 \\
3 & 4 & 0
\end{pmatrix}=-\begin{pmatrix}
0 & \frac{1}{6} & \frac{1}{3} \\
\frac{2}{10} & 0 & \frac{3}{10} \\
\frac{3}{14} & \frac{4}{14} & 0
\end{pmatrix}=\begin{pmatrix}
0 & -\frac{1}{6} & -\frac{1}{3} \\
-\frac{1}{5} & 0 & -\frac{3}{10} \\
-\frac{3}{14} & -\frac{4}{14} & 0
\end{pmatrix} T = − 6 1 0 0 0 10 1 0 0 0 14 1 0 2 3 1 0 4 2 3 0 = − 0 10 2 14 3 6 1 0 14 4 3 1 10 3 0 = 0 − 5 1 − 14 3 − 6 1 0 − 14 4 − 3 1 − 10 3 0 בנוסף:
c ‾ = ( 1 6 1 10 1 14 ) ( 9 15 21 ) = ( 9 6 15 10 21 14 ) = ( 1.5 1.5 1.5 ) = 1.5 ( 1 1 1 ) \underline{c}=\begin{pmatrix}
\frac{1}{6} \\
& \frac{1}{10} \\
& & \frac{1}{14}
\end{pmatrix}\begin{pmatrix}
9 \\
15 \\
21
\end{pmatrix}=\begin{pmatrix}
\frac{9}{6} \\
\frac{15}{10} \\
\frac{21}{14}
\end{pmatrix}=\begin{pmatrix}
1.5 \\
1.5 \\
1.5
\end{pmatrix}=1.5\begin{pmatrix}
1 \\
1 \\
1
\end{pmatrix} c = 6 1 10 1 14 1 9 15 21 = 6 9 10 15 14 21 = 1.5 1.5 1.5 = 1.5 1 1 1
הוכיחו שהמטריצה שמצאתם מקיימת את השוויון: ρ ( T ) = ∥ ∣ T ∣ ∥ ∞ \rho(T)=\lVvert T \rVvert_{\infty} ρ ( T ) = ∥ ∣ T ∣ ∥ ∞
הוכחה: ∥ ∣ T ∣ ∥ ∞ = max k { ∑ j = 1 n ∣ t k j ∣ } \lVvert T \rVvert_{\infty}=\underset{k}{\max}\left\{ \sum_{j=1}^n |t_{kj}| \right\} ∥ ∣ T ∣ ∥ ∞ = k max { ∑ j = 1 n ∣ t kj ∣ } T T T − 1 2 -\frac{1}{2} − 2 1 ∥ ∣ T ∣ ∥ ∞ = 1 2 \lVvert T \rVvert_{\infty}=\frac{1}{2} ∥ ∣ T ∣ ∥ ∞ = 2 1 v ‾ = ( 1 1 1 ) \underline{v}=\begin{pmatrix}1 \\ 1 \\ 1\end{pmatrix} v = 1 1 1 λ = − 1 2 \lambda=-\frac{1}{2} λ = − 2 1 T T T v ‾ \underline{v} v ∣ − 1 2 ∣ ≤ ρ { T } ≤ ∥ ∣ T ∣ ∥ ∞ = 1 2 \left| -\frac{1}{2} \right|\leq \rho \left\{ T \right\}\leq \lVvert T \rVvert_{\infty}=\frac{1}{2} − 2 1 ≤ ρ { T } ≤ ∥ ∣ T ∣ ∥ ∞ = 2 1 ρ { T } = ∥ ∣ T ∣ ∥ ∞ \rho \left\{ T \right\}=\lVvert T \rVvert_{\infty} ρ { T } = ∥ ∣ T ∣ ∥ ∞ ∎
נתון שהפתרון למערכת המשוואות הנתונה הוא x ‾ ∗ = ( 1 1 1 ) \underline{x}^*=\begin{pmatrix}1 \\ 1 \\ 1\end{pmatrix} x ∗ = 1 1 1 x ‾ 0 = ( 5 − 23 − 5 ) \underline{x}_{0}=\begin{pmatrix}5 \\ -23 \\ -5\end{pmatrix} x 0 = 5 − 23 − 5 x ‾ k \underline{x}_k x k e ‾ k = x ‾ k − x ‾ ∗ \underline{e}_{k}=\underline{x}_{k}-\underline{x}^* e k = x k − x ∗
חשבו את השגיאה ההתחלתית ∥ e ‾ 0 ∥ ∞ \left\lVert \underline{e}_{0} \right\rVert_{\infty} ∥ e 0 ∥ ∞
e ‾ k = e ‾ 0 − x ‾ ∗ = ( 5 − 23 − 5 ) − ( 1 1 1 ) = ( 4 − 24 − 6 ) \underline{e}_{k}=\underline{e}_{0}-\underline{x}^*=\begin{pmatrix}
5 \\
-23 \\
-5
\end{pmatrix}-\begin{pmatrix}
1 \\
1 \\
1
\end{pmatrix}=\begin{pmatrix}
4 \\
-24 \\
-6
\end{pmatrix} e k = e 0 − x ∗ = 5 − 23 − 5 − 1 1 1 = 4 − 24 − 6 לכן מתקיים כי:
∥ e ‾ 0 ∥ ∞ = max 1 ≤ k ≤ 3 ∣ e k 0 ∣ = 24 \left\lVert \underline{e}_{0} \right\rVert _{\infty}=\underset{1\leq k\leq 3}{\max}|e^0_{k}|=24 ∥ e 0 ∥ ∞ = 1 ≤ k ≤ 3 max ∣ e k 0 ∣ = 24
הוכיחו כי אם ρ ( T ) = ∥ ∣ T ∣ ∥ ∞ \rho(T)=\lVvert T \rVvert_{\infty} ρ ( T ) = ∥ ∣ T ∣ ∥ ∞ ∥ e ‾ k ∥ ∞ ≤ ( ρ ( T ) ) k ∥ e ‾ 0 ∥ ∞ \left\lVert \underline{e}_{k} \right\rVert_{\infty}\leq(\rho (T))^k\left\lVert \underline{e}_{0} \right\rVert_{\infty} ∥ e k ∥ ∞ ≤ ( ρ ( T ) ) k ∥ e 0 ∥ ∞
הוכחה: x ‾ ∗ = T x ‾ ∗ + c ‾ \underline{x}^*=T\underline{x}^*+\underline{c} x ∗ = T x ∗ + c x ‾ k = T x ‾ k − 1 + c ‾ \underline{x}_{k}=T\underline{x}_{k-1}+\underline{c} x k = T x k − 1 + c
x ‾ k − x ‾ ∗ = T ( x ‾ k − 1 − x ‾ ∗ ) = T e ‾ k − 1 \underline{x}_{k}-\underline{x}^*=T(\underline{x}_{k-1}-\underline{x}^*)=T\underline{e}_{k-1} x k − x ∗ = T ( x k − 1 − x ∗ ) = T e k − 1 לכן, מתקיים כי:
x ‾ k − x ‾ ∗ = T e ‾ k − 1 = T ( T e ‾ k − 2 ) = ⋯ = T k e ‾ 0 \underline{x}_{k}-\underline{x}^*=T\underline{e}_{k-1}=T(T\underline{e}_{k-2})=\dots=T^k\underline{e}_{0} x k − x ∗ = T e k − 1 = T ( T e k − 2 ) = ⋯ = T k e 0 ולכן מתקיים:
∥ e ‾ k ∥ ∞ = ∥ T k e ‾ 0 ∥ ∞ ≤ ∥ ∣ T k ∣ ∥ ∞ ∥ e ‾ 0 ∥ ∞ ≤ ∥ ∣ T ∣ ∥ ∞ k ∥ e ‾ 0 ∥ ∞ = ( ρ { T } ) k ∥ e ‾ 0 ∥ ∞ \left\lVert \underline{e}_{k} \right\rVert _{\infty}=\left\lVert T^k\underline{e}_{0} \right\rVert _{\infty}\leq \lVvert T^k \rVvert _{\infty} \left\lVert \underline{e}_{0} \right\rVert _{\infty}\leq \lVvert T \rVvert ^k_{\infty}\left\lVert \underline{e}_{0} \right\rVert _{\infty}=(\rho \left\{ T \right\})^k\left\lVert \underline{e}_{0} \right\rVert _{\infty} ∥ e k ∥ ∞ = T k e 0 ∞ ≤ ∥ ∣ T k ∣ ∥ ∞ ∥ e 0 ∥ ∞ ≤ ∥ ∣ T ∣ ∥ ∞ k ∥ e 0 ∥ ∞ = ( ρ { T } ) k ∥ e 0 ∥ ∞ ∎
מהו מספר האיטרציות k k k x ‾ k \underline{x}_{k} x k ∥ e ‾ k ∥ ∞ ≤ 0.01 \left\lVert \underline{e}_{k} \right\rVert_{\infty}\leq 0.01 ∥ e k ∥ ∞ ≤ 0.01
מסעיף קודם מתקיים:
∥ e ‾ k ∥ ∞ ≤ ( ρ { T } ) k ∥ e ‾ 0 ∥ ∞ \left\lVert \underline{e}_{k} \right\rVert _{\infty}\leq (\rho \left\{ T \right\})^k\left\lVert \underline{e}_{0} \right\rVert _{\infty} ∥ e k ∥ ∞ ≤ ( ρ { T } ) k ∥ e 0 ∥ ∞ אנו יודעים כי ρ { T } = 1 2 \rho \left\{ T \right\}=\frac{1}{2} ρ { T } = 2 1 ∥ e ‾ 0 ∥ ∞ = 24 \left\lVert \underline{e}_{0} \right\rVert_{\infty}=24 ∥ e 0 ∥ ∞ = 24
24 2 k = 0.01 ⟹ 2400 = 2 k ⟹ log 2 2400 = k ⟹ k ≤ 11.2288 \frac{24}{2^k}= 0.01 \implies 2400=2^k\implies \log_{2} 2400=k\implies k\leq 11.2288 2 k 24 = 0.01 ⟹ 2400 = 2 k ⟹ log 2 2400 = k ⟹ k ≤ 11.2288 ולכן מספר האיטרציות הינו הדרוש הינו 12 12 12
חשבו את הוקטור x ‾ 1 \underline{x}_{1} x 1
x ‾ 1 = ( 0 − 1 6 − 1 3 − 1 5 0 − 3 10 − 3 14 − 4 14 0 ) ( 5 − 23 − 5 ) + 1.5 ( 1 1 1 ) = ( 5.5 0.5 5.5 ) + 1.5 ( 1 1 1 ) = ( 7 2 7 ) \underline{x}_{1}=\begin{pmatrix}
0 & -\frac{1}{6} & -\frac{1}{3} \\
-\frac{1}{5} & 0 & -\frac{3}{10} \\
-\frac{3}{14} & -\frac{4}{14} & 0
\end{pmatrix}\begin{pmatrix}
5 \\
-23 \\
-5
\end{pmatrix}+1.5\begin{pmatrix}
1 \\
1 \\
1
\end{pmatrix}=\begin{pmatrix}
5.5 \\
0.5 \\
5.5
\end{pmatrix}+1.5\begin{pmatrix}
1 \\
1 \\
1
\end{pmatrix}=\begin{pmatrix}
7 \\
2 \\
7
\end{pmatrix} x 1 = 0 − 5 1 − 14 3 − 6 1 0 − 14 4 − 3 1 − 10 3 0 5 − 23 − 5 + 1.5 1 1 1 = 5.5 0.5 5.5 + 1.5 1 1 1 = 7 2 7
השתמשו בשגיאה בפועל של הוקטור x ‾ 1 \underline{x}_{1} x 1 k k k ∥ e ‾ k ∥ ∞ ≤ 0.01 \left\lVert \underline{e}_{k} \right\rVert_{\infty}\leq 0.01 ∥ e k ∥ ∞ ≤ 0.01
e ‾ 1 = ( 7 2 7 ) − ( 1 1 1 ) = ( 6 1 6 ) ⟹ ∥ e ‾ 1 ∥ ∞ = 6 \underline{e}_{1}=\begin{pmatrix}
7 \\
2 \\
7
\end{pmatrix}-\begin{pmatrix}
1 \\
1 \\
1
\end{pmatrix}=\begin{pmatrix}
6 \\
1 \\
6
\end{pmatrix}\implies \left\lVert \underline{e}_{1} \right\rVert _{\infty}=6 e 1 = 7 2 7 − 1 1 1 = 6 1 6 ⟹ ∥ e 1 ∥ ∞ = 6 נוכל כעת לחשב עם החסם ההתחלתי e ‾ 1 \underline{e}_{1} e 1 e ‾ 0 \underline{e}_{0} e 0
∥ e ‾ k ∥ ∞ ≤ ( ρ { T } ) k − 1 ∥ e ‾ 1 ∥ ∞ \left\lVert \underline{e}_{k} \right\rVert _{\infty}\leq (\rho \left\{ T \right\})^{k-1}\left\lVert \underline{e}_{1} \right\rVert _{\infty} ∥ e k ∥ ∞ ≤ ( ρ { T } ) k − 1 ∥ e 1 ∥ ∞ כעת נדרוש שוב כי:
6 2 k − 1 = 0.01 ⟹ 600 = 2 k − 1 ⟹ 9.22 = k − 1 ⟹ k ≤ 10.22 \frac{6}{2^{k-1}}= 0.01 \implies 600= 2^{k-1}\implies 9.22= k-1\implies k\leq 10.22 2 k − 1 6 = 0.01 ⟹ 600 = 2 k − 1 ⟹ 9.22 = k − 1 ⟹ k ≤ 10.22 לכן, נגלה כעת כי מספר האיטרציות הדרוש כדי להבטיח ∥ e ‾ k ∥ ∞ ≤ 0.01 \left\lVert \underline{e}_{k} \right\rVert_{\infty}\leq 0.01 ∥ e k ∥ ∞ ≤ 0.01 11 11 11
תרגיל 4
בכיתה למדנו על שיטת Jacobi . לעיתים, שיטה זו אינה מתכנסת (מתבדרת) או שהיא מתכנסת תוך כדי תנודתיות חזקה ("זיג-זג") סביב הפתרון. על מנת לשפר את ההתכנסות, נציג את שיטת Jacobi המשוקללת. הרעיון הוא לא לקבל את האיטרציה הבאה של Jacobi באופן מלא, אלא לבצע ממוצע משוקלל בין הערך הנוכחי לבין הערך החדש ששיטת Jacobi מציעה.
x ‾ k + 1 = ( 1 − ω ) x ‾ k + ω x ‾ J a c ( k + 1 ) \underline{x}_{k+1}=(1-\omega)\underline{x}_{k}+\omega \underline{x}_{Jac}^{(k+1)} x k + 1 = ( 1 − ω ) x k + ω x J a c ( k + 1 ) כאשר ω \omega ω x ‾ J a c ( k + 1 ) \underline{x}_{Jac}^{(k+1)} x J a c ( k + 1 ) מתוך המיקום הנוכחי x ‾ k \underline{x}_{k} x k
נסמן את המטריצה A A A A = D + L + U A=D+L+U A = D + L + U a i i ≠ 0 a_{ii}\neq 0 a ii = 0 T J a c = − D − 1 ( L + U ) T_{Jac}=-D^{-1}(L+U) T J a c = − D − 1 ( L + U )
הראו כי ניתן לרשום את שיטת Jacobi המשוקללת כמערכת דינמית מהצורה x ‾ k + 1 = T ω x ‾ k + c ‾ ω \underline{x}_{k+1}=T_{\omega}\underline{x}_{k}+\underline{c}_{\omega} x k + 1 = T ω x k + c ω T ω T_{\omega} T ω c ‾ ω \underline{c}_{\omega} c ω T J a c , D , b ‾ , ω T_{Jac},D,\underline{b},\omega T J a c , D , b , ω
x ‾ k + 1 = ( 1 − ω ) x ‾ k + ω x ‾ J a c k + 1 = ( 1 − ω ) x ‾ k + ω T J a c x ‾ k + ω c ‾ J a c = ( ( 1 − ω ) I + ω T J a c ) x ‾ x + ω D − 1 b ‾ \begin{align*}
\underline{x}_{k+1}&=(1-\omega)\underline{x}_{k}+\omega \underline{x}_{Jac}^{k+1}=(1-\omega)\underline{x}_{k}+\omega T_{Jac}\underline{x}_{k}+\omega \underline{c}_{Jac}=((1-\omega)I+\omega T_{Jac})\underline{x}_{x}+\omega D^{-1}\underline{b}
\end{align*} x k + 1 = ( 1 − ω ) x k + ω x J a c k + 1 = ( 1 − ω ) x k + ω T J a c x k + ω c J a c = (( 1 − ω ) I + ω T J a c ) x x + ω D − 1 b ולכן מתקיים כי במערכת הדינמית עבור שיטת J a c o b i Jacobi J a co bi
T ω = ( 1 − ω ) I + ω T J a c , c ‾ ω = ω D − 1 b ‾ T_{\omega}=(1-\omega)I+\omega T_{Jac},\;\;\; \underline{c}_{\omega}=\omega D^{-1}\underline{b} T ω = ( 1 − ω ) I + ω T J a c , c ω = ω D − 1 b
הוכיחו כי אם הסדרה { x ‾ k } \left\{ \underline{x}_{k} \right\} { x k } x ‾ ∗ \underline{x}^* x ∗ x ‾ ∗ \underline{x}^* x ∗ A x ‾ = b ‾ A\underline{x}=\underline{b} A x = b ω ≠ 0 \omega\neq 0 ω = 0
הוכחה: { x ‾ k } \left\{ \underline{x}_{k} \right\} { x k } x ‾ ∗ \underline{x}^* x ∗
x ‾ ∗ = ( ( 1 − ω ) I + ω T J a c ) x ‾ ∗ + ω D − 1 b ‾ \underline{x}^*=((1-\omega)I+\omega T_{Jac})\underline{x}^*+\omega D^{-1}\underline{b} x ∗ = (( 1 − ω ) I + ω T J a c ) x ∗ + ω D − 1 b x ‾ ∗ ( I − I + ω I − ω T J a c ) = ω D − 1 b ‾ \underline{x}^*(I-I+\omega I-\omega T_{Jac})=\omega D^{-1}\underline{b} x ∗ ( I − I + ω I − ω T J a c ) = ω D − 1 b נזכר כי T J a c = − D − 1 ( L + U ) T_{Jac}=-D^{-1}(L+U) T J a c = − D − 1 ( L + U )
x ‾ ∗ ( ω I + ω D − 1 ( L + U ) ) = ω D − 1 b ‾ \underline{x}^*(\omega I+\omega D^{-1}(L+U))=\omega D^{-1}\underline{b} x ∗ ( ω I + ω D − 1 ( L + U )) = ω D − 1 b x ‾ ∗ ( I + D − 1 ( L + U ) ) = D − 1 b ‾ \underline{x}^*(I+D^{-1}(L+U))=D^{-1}\underline{b} x ∗ ( I + D − 1 ( L + U )) = D − 1 b נכפיל ב-D D D
x ‾ ∗ ( D + L + U ) = b ‾ \underline{x}^*(D+L+U)=\underline{b} x ∗ ( D + L + U ) = b נזכר כי A = L + D + U A=L+D+U A = L + D + U
A x ‾ ∗ = b ‾ A\underline{x}^*=\underline{b} A x ∗ = b ולכן, x ‾ ∗ \underline{x}^* x ∗ A x ‾ = b ‾ A\underline{x}=\underline{b} A x = b ∎
יהיו λ i \lambda_i λ i T J a c T_{Jac} T J a c μ i ( ω ) \mu_{i}(\omega) μ i ( ω ) T ω T_{\omega} T ω λ i \lambda_{i} λ i μ i ( ω ) \mu_{i}(\omega) μ i ( ω )
נגדיר:
p ( x ) = ω x + 1 − ω p(x)=\omega x+1-\omega p ( x ) = ω x + 1 − ω נציב את T J a c T_{Jac} T J a c p p p
p ( T J a c ) = ω T J a c + ( 1 − ω ) I = T ω p(T_{Jac})=\omega T_{Jac}+(1-\omega)I=T_{\omega} p ( T J a c ) = ω T J a c + ( 1 − ω ) I = T ω לפי משפט, אם λ i \lambda_{i} λ i A A A B = p ( A ) B=p(A) B = p ( A ) p ∈ F n [ x ] p \in \mathbb{F}_n[x] p ∈ F n [ x ] p ( λ i ) p(\lambda_{i}) p ( λ i ) B B B T ω T_{\omega} T ω p ( λ i ) = ω λ i + 1 − ω p(\lambda_{i})=\omega\lambda_{i}+1-\omega p ( λ i ) = ω λ i + 1 − ω
לפי משפט, אם ρ { T } < 1 \rho \left\{ T \right\}<1 ρ { T } < 1 x ‾ k = T x ‾ k − 1 + c ‾ \underline{x}_{k}=T\underline{x}_{k-1}+\underline{c} x k = T x k − 1 + c T T T max i ∣ ω λ i + 1 − ω ∣ < 1 \underset{i}{\max}|\omega\lambda_{i}+1-\omega|<1 i max ∣ ω λ i + 1 − ω ∣ < 1
נתון מקרה ספציפי בו מטריצת האיטרציה של Jacobi, המסומנת T J a c T_{Jac} T J a c
λ 1 = − 2 , λ 2 = 1 2 \lambda_{1}=-2,\;\;\lambda_{2}=\frac{1}{2} λ 1 = − 2 , λ 2 = 2 1
האם שיטת Jacobi הרגילה(ω = 1 \omega=1 ω = 1
מצאו תחום ערכים עבור ω \omega ω
פתרון (1): max i ∣ λ i ∣ = 2 > 1 \underset{i}{\max}|\lambda_{i}|=2>1 i max ∣ λ i ∣ = 2 > 1
פתרון (2):
{ ∣ 1 2 ω + 1 − ω ∣ < 1 ⟹ ∣ 1 − 1 2 ω ∣ < 1 ⟹ − 1 < 1 − 1 2 ω < 1 ⟹ { − 2 < − 1 2 ω ⟹ 4 > ω − 1 2 ω < 0 ⟹ ω > 0 ∣ − 2 ω + 1 − ω ∣ < 1 ⟹ ∣ 1 − 3 ω ∣ < 1 ⟹ − 1 < 1 − 3 ω < 1 ⟹ { − 2 < − 3 ω ⟹ 2 3 > ω − 3 ω < 0 ⟹ ω > 0 \begin{cases}
\left| \frac{1}{2}\omega+1-\omega \right|<1\implies |1-\frac{1}{2}\omega|<1 \implies -1<1-\frac{1}{2}\omega<1 \implies \begin{cases}
-2<-\frac{1}{2}\omega\implies 4>\omega \\
-\frac{1}{2}\omega <0\implies \omega>0
\end{cases} \\
|-2\omega+1-\omega|<1\implies |1-3\omega|<1\implies -1<1-3\omega <1\implies \begin{cases}
-2<-3\omega\implies \frac{2}{3}>\omega \\
-3\omega<0\implies \omega>0
\end{cases}
\end{cases} ⎩ ⎨ ⎧ 2 1 ω + 1 − ω < 1 ⟹ ∣1 − 2 1 ω ∣ < 1 ⟹ − 1 < 1 − 2 1 ω < 1 ⟹ { − 2 < − 2 1 ω ⟹ 4 > ω − 2 1 ω < 0 ⟹ ω > 0 ∣ − 2 ω + 1 − ω ∣ < 1 ⟹ ∣1 − 3 ω ∣ < 1 ⟹ − 1 < 1 − 3 ω < 1 ⟹ { − 2 < − 3 ω ⟹ 3 2 > ω − 3 ω < 0 ⟹ ω > 0 לכן, לפי המשפט הנ"ל, המערכת תתכנס עבור 0 < ω < 2 3 0<\omega< \frac{2}{3} 0 < ω < 3 2
בהמשך לסעיף ד', מהו ערך ה-ω \omega ω ρ { T ω } \rho \left\{ T_{\omega} \right\} ρ { T ω }
נרצה למצוא את ω \omega ω
min 0 < ω < 2 3 ( max i ∣ ω λ i + 1 − ω ∣ ) \underset{0<\omega< \frac{2}{3}}{\min}(\underset{i}{\max} |\omega\lambda_{i}+1-\omega|) 0 < ω < 3 2 min ( i max ∣ ω λ i + 1 − ω ∣ ) מכיוון שיש לנו שני ע"ע נוכל להסתכל עליהם כפונקציות:
f 1 ( ω ) = ∣ 1 − 1 2 ω ∣ f 2 ( ω ) = ∣ 1 − 3 ω ∣ f_{1}(\omega)=\left| 1-\frac{1}{2}\omega \right| \qquad \qquad f_{2}(\omega)=\left| 1-3\omega \right| f 1 ( ω ) = 1 − 2 1 ω f 2 ( ω ) = ∣ 1 − 3 ω ∣ נגדיר כעת:
f ( ω ) = ρ { T } ( ω ) = max i f i ( ω ) f(\omega)=\rho \left\{ T \right\}(\omega)=\underset{i}{\max}f_{i}(\omega) f ( ω ) = ρ { T } ( ω ) = i max f i ( ω ) על מנת למצוא את f f f
{ 0 < ω ≤ 1 3 , 1 − 1 2 ω = 1 − 3 ω ⟹ 2.5 ω = 0 ⟹ ω = 0 1 3 < ω < 2 3 , 1 − 1 2 ω = 3 ω − 1 ⟹ 3.5 ω = 2 ⟹ ω = 0.5714 \begin{cases}
0<\omega\leq \frac{1}{3}, & 1-\frac{1}{2}\omega=1-3\omega\implies 2.5\omega=0\implies \omega=0 \\
\frac{1}{3}< \omega< \frac{2}{3}, & 1-\frac{1}{2}\omega=3\omega-1\implies 3.5\omega=2\implies \omega=0.5714
\end{cases} { 0 < ω ≤ 3 1 , 3 1 < ω < 3 2 , 1 − 2 1 ω = 1 − 3 ω ⟹ 2.5 ω = 0 ⟹ ω = 0 1 − 2 1 ω = 3 ω − 1 ⟹ 3.5 ω = 2 ⟹ ω = 0.5714 עלינו לבדוק בכל תחום איזו פונקציה היא המקסימלית על מנת לבנות את f ( ω ) f(\omega) f ( ω ) ω \omega ω
{ 0 ≤ ω ≤ 1 3 , 1 − 1 2 ⋅ 1 4 = 0.875 > 0.25 = 1 − 3 ⋅ 1 4 1 3 < ω ≤ 0.5714 , 1 − 1 2 ⋅ 1 2 = 0.75 > 0.5 = 3 ⋅ 1 2 − 1 0.5714 ≤ ω < 2 3 , 1 − 1 2 ⋅ 0.6 = 0.7 < 0.8 = 3 ⋅ 0.6 − 1 \begin{cases}
0\leq \omega\leq \frac{1}{3}, & 1-\frac{1}{2}\cdot \frac{1}{4}=0.875> 0.25=1-3\cdot \frac{1}{4} \\
\frac{1}{3}< \omega\leq 0.5714, & 1-\frac{1}{2}\cdot \frac{1}{2}=0.75> 0.5=3\cdot \frac{1}{2}-1 \\
0.5714\leq \omega< \frac{2}{3}, & 1-\frac{1}{2}\cdot 0.6=0.7<0.8=3\cdot 0.6-1
\end{cases} ⎩ ⎨ ⎧ 0 ≤ ω ≤ 3 1 , 3 1 < ω ≤ 0.5714 , 0.5714 ≤ ω < 3 2 , 1 − 2 1 ⋅ 4 1 = 0.875 > 0.25 = 1 − 3 ⋅ 4 1 1 − 2 1 ⋅ 2 1 = 0.75 > 0.5 = 3 ⋅ 2 1 − 1 1 − 2 1 ⋅ 0.6 = 0.7 < 0.8 = 3 ⋅ 0.6 − 1 לכן, נקבל כי:
f ( ω ) = { f 1 ( ω ) 0 < ω ≤ 0.5714 f 2 ( ω ) 0.5714 < ω < 2 3 f(\omega)=\begin{cases}
f_{1}(\omega) & 0< \omega\leq 0.5714 \\
f_{2}(\omega) & 0.5714<\omega < \frac{2}{3}
\end{cases} f ( ω ) = { f 1 ( ω ) f 2 ( ω ) 0 < ω ≤ 0.5714 0.5714 < ω < 3 2 נשים לב כי נקודת הקיצון של פונקציה זו היא בדיוק ב-ω = 0.5714 \omega=0.5714 ω = 0.5714 ω \omega ω