הבעיות שראינו עד כה, פירוק LU, פירוק $SV\!D$ וכדומה, נהדרות כאשר אנו מדברים על גדלים סופיים וקטנים של מטריצות, אבל מה עם מטריצות בגודל $1000\times1000$ או בגדלים השואפים ל- $\infty$ ? פה נדרש משהו חזק יותר.

בפרק זה נראה דרך לצמצם בעיות גדולות לבעיות קטנות יותר והכל דרך המשוואה $\underline{u}_{k+1}=A\underline{u}_{k}$ אשר מייד נראה כמה היא חזקה.
הרעיון בעצם בתהליכים איטרטיביים הוא לקחת איזושהי בעיה ולהתחיל מפתרון שרירותי מסויים ואז לדייק אותו קצת ואז לדייק אותו עוד קצת ואז עוד קצת וחוזר חלילה עד אשר אנו מגיעים לפתרון המדוייק.

תהליכים איטרטיביים

נסתכל על מערכת דינמית פשוטה המתחילה בוקטור $u_{0}$ ומטריצה ריבועית בגודל $n\times n$ בשם $T$ . המערכת שלנו הינה:

\underline{u}_{k}=T\underline{u}_{k-1}=T(T\underline{u}_{k-2})=T(T(T\underline{u}_{k-3}))=\dots=T^k\underline{u}_{0}

נשים לב כי $T^k\underline{u}_{0}$ נותן לנו את $\underline{u}_{k}$ .

נניח כעת כי $T$ לכסינה, כלומר יש לה $n$ ו"ע המהווים בסיס ולכן ניתן לכתוב כי $T=VAV^{-1}$ . נציב את פירוק זה למערכת:

\underline{u}_{k}=T^k\underline{u}_{0}=(VAV^{-1})^k\underline{u}_{0}=VA^kV^{-1}\underline{u}_{0}

נסמן $V^{-1}\underline{u}_{0}=x\underline{u}_{0}$ ואז: $\underline{u}_{k}=VA^k\underline{x}_{0}$ .

\underline{u}_{k}\!=\!VA^k\underline{x}_{0}\!=\!\!\begin{pmatrix} \vert & & \vert \\ \underline{v}_{1} & \dots & \underline{v}_{n} \\ \vert & & \vert \end{pmatrix}\!\!\!\begin{pmatrix} \lambda_{1}^k & & 0 \\ & \ddots \\ 0 & & \lambda_{n}^k \end{pmatrix}\!\!\!\begin{pmatrix} x_{0}(1) \\ \vdots \\ x_{0}(n) \end{pmatrix}\!\!=\!\!\begin{pmatrix} \vert & & \vert \\ \underline{v}_{1} & \dots & \underline{v}_{n} \\ \vert & & \vert \end{pmatrix}\!\!\!\begin{pmatrix} x_{0}(1)\lambda_{1}^k \\ \vdots \\ x_{0}(n)\lambda_{n}^k \end{pmatrix}\!\!=\sum_{j=1}^n x_{0}(j)\lambda_{j}^k\underline{v}_{j}

נשים לב שההשפעה של $k$ נמצאת רק בחזקה של ה- $\lambda$ -ים.
נשים לב כי אם כל הע"ע קטנים מ- $1$ אז מתקיים: $\underline{u}_{k}\rarrowlim{k\to \infty} \underline{0}$ . אנו נראה עניין מיוחד בזה בהמשך.

דוגמה

נניח ונתונים לנו: $T=\begin{pmatrix}0.3 & 0.1 \\ 0.1 & 0.3\end{pmatrix},\;\;\underline{u}_{0}=\begin{pmatrix}1\\ 2\end{pmatrix}$ .
נרצה תחילה למצוא את הע"ע:

\lambda_{1}=0.4 \quad \underline{v}_{1}=\begin{pmatrix} 1 \\ 1 \end{pmatrix} \qquad \land \qquad \lambda_{2}=0.2 \quad \underline{v}_{2}=\begin{pmatrix} -1 \\ 1 \end{pmatrix}

אזי מתקיים:

V\underline{x}_{0}=\underline{u}_{0}=\begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} x_{0}(1) \\ x_{0}(2) \end{pmatrix}=\begin{pmatrix} 1 \\ 2 \end{pmatrix} \implies \begin{pmatrix} x_{0}(1) \\ x_{0}(2) \end{pmatrix}=\frac{1}{2}\begin{pmatrix} 3 \\ 1 \end{pmatrix}

ואז מתקיים:

\underline{u}_{k}=\sum_{j=1}^n x_{0}(j)\lambda_{j}^k \underline{v}_{j}=\frac{3}{2}\cdot 0.4^k \begin{pmatrix} 1 \\ 1 \end{pmatrix}+\frac{1}{2}\cdot 0.2^k\begin{pmatrix} -1 \\ 1 \end{pmatrix}=\frac{1}{2}\begin{pmatrix} 3\cdot 0.4^k-0.2^k \\ 3\cdot 0.4^k+0.2^k \end{pmatrix} \rarrowlim{k\to \infty} \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}

דוגמה

נסתכל על סדרת פיבונצי המוגדרת: $f_{k+2}=f_{k+1}+f_{k}, \qquad \qquad f_{1}=f_{0}=1$ .
נגדיר: $\underline{u}_{k}=\begin{pmatrix}f_{k} \\ f_{k+1}\end{pmatrix}=\begin{pmatrix}0 & 1 \\ 1 & 1\end{pmatrix}\begin{pmatrix}f_{k-1} \\ f_{k}\end{pmatrix}=T\underline{u}_{k-1}$ . לכן, הפעם $T=\begin{pmatrix}0 & 1\\1 & 1\end{pmatrix}, \underline{u}_{0}=\begin{pmatrix}1 \\ 1\end{pmatrix}$ .
נמצא את הע"ע: $\lambda_{1}=1.618,\lambda_{2}=-0.618$ ואז $\underline{v}_{1}=\begin{pmatrix}-\lambda_{2} \\ 1\end{pmatrix}\land \underline{v}_{2}=\begin{pmatrix}-\lambda_{1} \\ 1\end{pmatrix}$ ואז נקבל:

V\underline{x}_{0}=\underline{u}_{0}=\begin{pmatrix} -\lambda_{2} & -\lambda_{1} \\ 1 & 1 \end{pmatrix}\begin{pmatrix} x_{0}(1) \\ x_{0}(2) \end{pmatrix}=\begin{pmatrix} 1 \\ 1 \end{pmatrix} \underset{\begin{matrix} a=1.17 \\ b=-0.17 \end{matrix}}{\implies} \begin{pmatrix} x_{0}(1) \\ x_{0}(2) \end{pmatrix}=\begin{pmatrix} a \\ b \end{pmatrix}

ואז נקבל את הנוסחה הבאה:

\underline{u}_{k}=\dots=a(\lambda_{1})^k\begin{pmatrix} -\lambda_{2} \\ 1 \end{pmatrix}+b(\lambda_{2})^k\begin{pmatrix} -\lambda_{2} \\ 1 \end{pmatrix}

כלומר נקבל:

f_{k+1}=a\lambda_{1}^k+b\lambda_{2}^k

וזוהי נוסחה סגורה עבור סדרת פיבונאצי.
האם היא מתכנסת? כמובן שלא, היא הולכת ל- $\infty$ .

הגדרה 1 (מערכת יציבה אסימפטוטית)

מערכת דינמית מהצורה $\underline{u}_{k}=T\underline{u}_{k-1}=T^k\underline{u}_0$ תקרא יציבה אסימפטוטית אם מתקיים כי:

\lim_{ k \to \infty } \underline{u}_{k}=0

באופן דומה, נאמר כי המטריצה $T$ יציבה אם מתקיים כי $T^k \rarrowlim{k\to \infty}0$ .

הגדרה 2 (רדיוס ספקטרלי)

תהי $T$ מטריצה כלשהי.
הרדיוס הספקטרלי שלה מוגדר כך:

\rho\left\{ T \right\}=\underset{1\leq k\leq n}{\max}|\lambda_{k}|=|\lambda_{1}|

זהו בעצם הרדיוס של הדסקה שמרכזה בראשית הצירים והיא מכסה את כל הע"ע של המטריצה $T$ .

משפט

תהי מערכת דינמית מהצורה $\underline{u}_{k}=T\underline{u}_{k-1}=T^k\underline{u}_{0}$ בה המטריצה $T$ לכסינה.
המערכת תהיה יציבה אסימפטוטית אם מתקיים כי כל הע"ע בעלי גודל קטן ממש מ- $1$ . כלומר:

\forall j \in[1,n]:\;\; |\lambda_{j}|<1

הוכחה:
עבור מטריצות לכסינות מתקבל:

\underline{u}_{k}=VA^k\underline{x}_{0}=\sum_{j=1}^n x_{0}(j)\lambda_{j}^k \underline{v}_{j}

נבדוק את נורמת הוקטור $\underline{u}_{k}$ . אם היא מתכנסת לאפס, אז כל איברי הוקטור מתכנסים לאפס.

\left\lVert \underline{u}_{k} \right\rVert _{2}=\left\lVert \sum_{j=1}^nx_{0}(j)\lambda_{j}^k \underline{v}_{j}\right\rVert \underset{\begin{matrix} \downarrow \\ \R{\text{אי שוויון המשולש}} \end{matrix}}{\leq} \sum_{j=1}^n \left\lVert x_{0}(j)\lambda_{j}^k\underline{v}_{j} \right\rVert_{2} \underset{\begin{matrix} \downarrow \\ \R{\text{הומוגניות}} \end{matrix}}{=}\sum_{j=1}^n |x_{0}(j)\lambda_{j}^k|\left\lVert \underline{v}_{j} \right\rVert _{2}

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

\left\lVert \underline{u}_{k} \right\rVert _{2}\leq \sum_{j=1}^n|x_{0}(j)|\cdot|\lambda_{j}|^k\leq \sum_{j=1}^n |x_{0}(j)|\cdot |\lambda_{1}|^k\leq p\left\{ T \right\}^k\sum_{j=1}^n |x_{0}(j)|=\rho\left\{ T \right\}^k\left\lVert \underline{x}_{0} \right\rVert _{1} \rarrowlim{k\to \infty} 0

הערך העצמי המקסימלי, המיוצג ע"י הרדיוס הספקטרלי, קטן מ-1 ולכן בחזקה השואפת ל- $\infty$ הוא מתכנס ל- $0$ .
∎

הערה

אנו חייבים לדרוש שכל הע"ע יהיו קטנים מ- $1$ כדי שזה יעבוד.
ניתן להגיד כי מתקיים בערך: $\underline{u}_{k}=VA^k\underline{x}_{0}=\displaystyle\sum_{j=1}^n x_{0}(j)\lambda_{j}^k\underline{v}_{j}\approx x_{0}(1)\lambda_{1}^k\underline{v}_{1}$ .
בהמשך להנ"ל, אם נקבע כי $x_{0}(1)=0$ אזי נחשוב כי השפעתו של הע"ע הגדול תנוטרל, אך אין זה כך. שגיאות נומריות מזעריות יגרמו לע"ע זה לקחת שליטה בסופו של דבר על מלוא התהליך.

עד כה ראינו כי אם המערכת $\underline{u}_{k}=T^k\underline{u}_{0}$ פועלת ע"י מטריצה $T$ לכסינה, הרדיוס הספקטרלי שלה $p\left\{ T \right\}$ יקבע אם תחול התכנסות לאפס.
בדיקה זו היא מורכבת מאוד ומוגבלת למטריצות לכסינות בלבד, נרצה לראות משהו אחר, אשר יעבוד גם עבור מטריצות לא לכסינות. משהו שייצג איזשהו מרחק של מטריצות מהאפס. זה נשמע כמו נורמה, ולזה באמת יקראו נורמות של מטריצות.

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

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

משפט

בהינתן כל שתי נורמות המוגדרות לוקטורים במימד $n$ :

\lVert \cdot \rVert_{B}, \quad \lVert \cdot\rVert_{A}

המקיימות את האקסיומות הנדרשות, קיימים בהכרח שני קבועים $0<c_{1}<c_{2}<\infty$ כך שמתקיים:

\forall \underline{v}\in \mathbb{F}^n:\;\; c_{1}\left\lVert \underline{v} \right\rVert _{A}\leq \left\lVert \underline{v} \right\rVert _{B}\leq c_{2}\left\lVert \underline{v} \right\rVert _{A}

מסקנה

\left\lVert \underline{v}_{k} \right\rVert _{A} \rarrowlim{k\to \infty} \underline{0} \iff \left\lVert \underline{v}_{k} \right\rVert _{B} \rarrowlim{k\to \infty} \underline{0}

הגדרה 3 (נורמה אופרטיבית(מושרית))

בהינתן הנורמה הוקטורית $\lVert \cdot\rVert_{A}$ לוקטורים ממימד $n$ .
נגדיר את הנורמה האופרטיבית של המטריצה $T$ בגודל $n\times n$ ע"י

\lVvert T \rVvert _{A}=\underset{\underline{v}:\;\left\lVert \underline{v} \right\rVert_{A}=1 }{\max}\left\lVert T\underline{v} \right\rVert _{A}=\underset{\underline{v}\neq 0}{\max} \frac{\left\lVert T\underline{v} \right\rVert _{A}}{\left\lVert \underline{v} \right\rVert_{A} }

הנורמה הזו קובעת את "אורך" המטריצה $T$ ע"י מציאת שיעור ה"ניפוח" המירבי שלה.

הוכחה: (שזה נורמה)

חיוביות:
$\forall \underline{v},\; \left\lVert T\underline{v} \right\rVert _{A}\geq 0:\;\;\ \lVvert T \rVvert _{A}=\underset{\underline{v}:\;\left\lVert \underline{v} \right\rVert_{A}=1 }{\max} \left\lVert T\underline{v} \right\rVert _{A}\geq 0$
אם נניח כי $\lVvert T \rVvert_{A}=0$ אזי מתקיים כי:
$\forall \underline{v} \neq 0,\; \left\lVert T\underline{v} \right\rVert _{A}=0:\;\; T\underline{v}=\underline{0}$
זה מתקיים רק עבור $T=0$ .
הומוגניות:
$\lVvert \alpha T \rVvert _{A}=\underset{\underline{v}:\; \left\lVert \underline{v} \right\rVert_{A}=1 }{\max}\left\lVert \alpha T\underline{v} \right\rVert _{A} \underset{\begin{matrix} \downarrow \\ \R{\text{הומוגניות}} \end{matrix}}{=}\underset{\underline{v}:\;\left\lVert \underline{v} \right\rVert_{A}=1 }{\max}|\alpha|\left\lVert T\underline{v} \right\rVert _{A}=|\alpha|\underset{\underline{v}:\;\left\lVert \underline{v} \right\rVert_{A}=1 }{\max}\left\lVert T\underline{v} \right\rVert _{A}=|\alpha|\lVvert T \rVvert _{A}$
אי שוויון המשולש:
$\begin{align*} \lVvert T_{1}+T_{2} \rVvert _{A}&=\underset{\underline{v}:\;\left\lVert \underline{v} \right\rVert_{A} }{\max}\left\lVert (T_{1}+T_{2})\underline{v} \right\rVert _{A}\leq \underset{\underline{v}:\; \left\lVert \underline{v} \right\rVert_{A}=1 }{\max}(\left\lVert T_{1}\underline{v} \right\rVert_{A}+\left\lVert T_{2}\underline{v} \right\rVert_{A} ) \\ &\leq \underset{\underline{v}:\; \left\lVert \underline{v} \right\rVert_{A}=1 }{\max}\left\lVert T_{1}\underline{v} \right\rVert _{A}+\underset{\underline{v}:\; \left\lVert \underline{v} \right\rVert_{A}=1 }{\max}\left\lVert T_{2}\underline{v} \right\rVert _{A}=\lVvert T_{1} \rVvert _{A}+\lVvert T_{2} \rVvert _{A} \end{align*}$

ולכן: $\lVvert T_{1}+T_{2} \rVvert_{A}\leq \lVvert T_{1} \rVvert_{A}+\lVvert T_{2} \rVvert_{A}$ .
∎

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

תהי $\lVert \cdot \rVert_{A}$ נורמה ותהי $\lVvert \cdot \rVvert_{A}$ הנורמה האופרטיבית המושרת ממנה. אזי:

$\forall \underline{v}\in \mathbb{R}^n \land T \in \mathbb{R}^{n\times n}:\;\; \left\lVert T\underline{v} \right\rVert_{A}\leq \lVvert T \rVvert_{A}\left\lVert \underline{v} \right\rVert_{A}$
$\forall T_{1},T_{2} \in \mathbb{R}^{n\times n}:\;\; \lVvert T_{1}T_{2} \rVvert_{A}\leq \lVvert T_{1} \rVvert_{A}\lVvert T_{2} \rVvert_{A}$
$\forall T \in \mathbb{R}^{n\times n}:\;\; \lVvert T^k \rVvert_{A}\leq \lVvert T \rVvert_{A}^k$
$\forall \underline{x}_{1}\R{\text{ עם הו"ע }}\lambda_{1}\R{\text{ לכסינה בעלת ע"ע הגדול ביותר }}T \in \mathbb{R}^{n\times n}:\;\; \rho \left\{ T \right\}\leq \lVvert T \rVvert_{A}$

הוכחה:
סעיף 1:

\left\lVert T\underline{v} \right\rVert _{A}=\frac{\left\lVert T\underline{v} \right\rVert_{A}}{\left\lVert \underline{v} \right\rVert_{A} }\leq \left[ \underset{\underline{v}\neq0}{\max} \frac{\left\lVert T\underline{v} \right\rVert_{A}}{\left\lVert \underline{v} \right\rVert_{A`} } \right]\cdot \left\lVert \underline{v} \right\rVert _{A}=\lVvert T \rVvert_{A}\left\lVert \underline{v} \right\rVert _{A}

סעיף 2:

\lVvert T_{1}T_{2} \rVvert_{A}=\underset{\underline{v}\neq 0}{\max} \frac{\left\lVert T_{1}T_{2}\underline{v} \right\rVert_{A}}{\left\lVert \underline{v} \right\rVert_{A} }\underset{\begin{matrix} \downarrow \\ (1) \end{matrix}}{\leq} \underset{\underline{v}\neq 0}{\max} \frac{\lVvert T_{1} \rVvert_{A} \left\lVert T_{2}\underline{v} \right\rVert_{A}}{\left\lVert \underline{v} \right\rVert_{A} }=\lVvert T_{1} \rVvert_{A}\lVvert T_{2} \rVvert _{A}

סעיף 3: מיידי מסעיף 2.
סעיף 4:

\lVvert T \rVvert_{A}=\underset{\underline{v}\neq 0}{\max} \frac{\left\lVert T\underline{v} \right\rVert_{A}}{\left\lVert \underline{v} \right\rVert_{A} }\geq \frac{\left\lVert T\underline{x}_{1} \right\rVert_{A}}{\left\lVert \underline{x}_{1} \right\rVert_{A} }= \frac{\left\lVert \lambda \underline{x}_{1} \right\rVert_{A}}{\left\lVert \underline{x}_{1} \right\rVert_{A} }=|\lambda_{1}|=\rho(T)

∎

מסקנה (מסעיף 4)

אם $\lVvert T \rVvert_{A}<1$ אזי גם $\rho \left\{ T \right\}<1$ .

נשים לב כי עבור המערכת הדינמית $\underline{u}_{k}=T^k\underline{u}_{0}$ .

\left\lVert \underline{u}_{k} \right\rVert_{A}=\left\lVert T^k\underline{u}_{0} \right\rVert_{A}\leq \lVvert T^k \rVvert_{A}\left\lVert \underline{u}_{0} \right\rVert_{A}\leq \lVvert T \rVvert_{A}^k \left\lVert \underline{u}_{0} \right\rVert _{A}

עבור $T$ המקיימת $\lVvert T \rVvert_{A}<1$ מתקיים:

\left\lVert \underline{u}_{k} \right\rVert_{A}\leq \lVvert T \rVvert ^k\left\lVert \underline{u}_{0} \right\rVert _{A} \rarrowlim{k\to \infty}0

משפט (מסקנה מסעיף 3)

עבור המערכת הדינמית $\underline{u}_{k}=T^k\underline{u}_{0}$ אם מתקיים כי $\lVvert T \rVvert_{A}<1$ עבור איזושהי נורמה $\lVert \cdot \rVert_{A}$ אזי המערכת מובטחת להתכנס אסימפטוטית.

הוכחה: ראו הנ"ל.

הערה

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

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

אנו נתחיל עם נורמת ה- $\infty$ כדוגמה. (כאשר $\left\lVert \underline{v} \right\rVert_{\infty}=\underset{1\leq k\leq n}{\max}|v_{k}|$ )
נתייחס לוקטור $T\underline{v}$ :

\left\lVert T\underline{v} \right\rVert_{\infty}\!\!=\!\underset{k}{\max}\!\left\{ \left| \sum_{j=1}^n t_{kj}v_{j} \right| \right\}\!\leq \!\underset{k}{\max}\!\left\{ \sum_{j=1}^n |t_{kj}|\cdot|v_{j}| \right\}\!\!\leq\! \underset{k}{\max}\!\left\{ \sum_{j=1}^n |t_{jk}|\underset{\ell}{\max}|v_{j}| \right\}\!\!=\!\underset{k}{\max}\!\left\{ \sum_{j=1}^n |t_{kj}| \right\}\!\left\lVert \underline{v} \right\rVert _{\infty}

\implies \frac{\left\lVert T\underline{v} \right\rVert_{\infty}}{\left\lVert \underline{v} \right\rVert_{\infty} }\leq \underset{k}{\max}\left\{ \sum_{j=1}^n |t_{kj}| \right\}

\implies \lVvert T \rVvert _{\infty}\leq \underset{k}{\max}\left\{ \sum_{j=1}^n |t_{kj}| \right\}

קיבלנו פה חסם עליון לנורמה. מתי זה יהיה שווה?
אם לכל $T$ שייבחר, נוכל למצוא וקטור $\underline{v}^*$ שיגרום לשוויון, בהכרח ביטוי זה הוא הנורמה: $\displaystyle \frac{\left\lVert T\underline{v}^* \right\rVert_{\infty}}{\left\lVert \underline{v}^* \right\rVert_{\infty}}=\underset{k}{\max}\left\{ \sum_{j=1}^n |t_{kj}| \right\}$ .
בואו נשתכנע(כי הוכחה זה מעל רמת הקורס הזה) שקיים וקטור שכזה:

נניח כי ביטוי משיג את שיאו עבור השורה הראשונה $k=1$ , אזי נמצא וקטור $\underline{v}^*$ מנורמל שאיברים הם $\pm 1$ כשהסימנים תואמים את סימני איברי השורה. אזי נקבל:
$T\underline{v}=\begin{pmatrix} t_{11} & t_{12} & t_{13} & \cdots & t_{1n} \\ \vdots & \vdots & \vdots & & \vdots \\ t_{n1} & t_{n2} & t_{n3} & \cdots & t_{nm} \end{pmatrix}\begin{pmatrix} \pm 1 \\ \vdots \\ \pm 1 \end{pmatrix}=\begin{pmatrix} \displaystyle\sum_{j=1}^n |t_{1j}| \\ \vdots \end{pmatrix}$
ולכן:

מסקנה

\lVvert T \rVvert_{\infty}=\underset{k}{\max}\left\{ \sum_{j=1}^n |t_{kj}| \right\}

חישוב הנורמה $\lVvert T \rVvert_{1}$ נעשה בדרך כמעט אחד לאחד כמו נורמת ה- $\infty$ ולכן נדלג על הדוגמה.
נראה כעת מה קורה עם $\lVvert T \rVvert_{2}$ :

\lVvert T \rVvert_{2}=\underset{x\neq 0}{\max} \frac{\left\lVert T\underline{x} \right\rVert_{2}}{\left\lVert \underline{x} \right\rVert_{2} }=\underset{\underline{x}\neq 0}{\max} \frac{\left\lVert U\Sigma V^t\underline{x} \right\rVert_{2}}{\left\lVert \underline{x} \right\rVert_{2} } \underset{\begin{matrix} \downarrow \\ \R{\text{תכונות מטריצה אורתונורמלית}} \end{matrix}}{=}\underset{\underline{x}\neq 0}{\max} \frac{\left\lVert \Sigma V^t\underline{x} \right\rVert_{2}}{\left\lVert \underline{x} \right\rVert_{2} }

נגדיר $\underline{z}=V^t\underline{x}$ ונקבל:

\lVvert T \rVvert_{2}=\underset{z\neq 0}{\max} \frac{\left\lVert \Sigma \underline{z} \right\rVert _{2}}{\left\lVert V\underline{z} \right\rVert_{2} } \underset{\begin{matrix} \downarrow \\ \R{\text{תכונות מטריצה אורתונורמלית}} \end{matrix}}{=}\underset{z\neq 0}{\max} \frac{\left\lVert \Sigma \underline{z} \right\rVert _{2}}{\left\lVert \underline{z} \right\rVert_{2} }=\underset{z\neq 0}{\max} \sqrt{ \frac{\displaystyle \sum_{k=1}^n \sigma_{k}^2z_{k}^2}{\displaystyle \sum_{k=1}^n z_{k}^2} }=\sigma_{1}

גילינו כי נורמת השתיים המושרית של מטריצה הוא לא הע"ע אלא הערך הסינגולרי הכי גדול שלה.
לפי תכונות נורמה מושרית מתקיים כי $|\lambda_{1}|\leq \sigma_{1}$ .

הקשר בין נורמת פורביניוס לנורמה שראינו עכשיו

\left\lVert T \right\rVert_{F}^2=\mathrm{Tr}\left\{ T^2T \right\}=\mathrm{Tr}\left\{ V\Sigma^tU^tU\Sigma V^t \right\}=\mathrm{Tr}\left\{ V\Sigma^t\Sigma V^t \right\} \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\underset{\begin{matrix} \downarrow \\ \mathrm{Tr}\left\{ AB \right\}=\mathrm{Tr}\left\{ BA \right\} \end{matrix}}{=}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\mathrm{Tr}\left\{ V^tV\Sigma^t\Sigma \right\}=\mathrm{Tr}\left\{ \Sigma^t\Sigma \right\}=\sum_{k=1}^n \sigma_{k}^2

לכן מתקיים כי:

\left\lVert T \right\rVert _{F}\geq \sigma_{1}=\lVvert T \rVvert _{2}

משפט הדיסקאות של גרשגורן

נסתכל כעת על גישאה אחרת לאומדן יציבותה של המטריצה $T$ המציעה דרך למקם את הע"ע במישור המרוכב.

משפט (גרשגורן)

למטריצה $T$ ריבועית כלשהי בגודל $n\times n$ נגדיר $n$ דסקאות כך:

D_{k}=\left\{ \begin{array}{c|c} z \in \mathbb{C} & \displaystyle |z-t_{kk}|\leq \sum_{j\neq k}^{\begin{matrix} \\ \end{matrix}}|t_{jk}| \end{array} \right\}

אזי, כל הע"ע של $T$ מוכלים באיחוד של הדיסקאות הללו.

הערה

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

$90\%$ מהוכחה:
נניח כי $\lambda$ הוא ע"ע של $T$ עם ו"ע $\underline{x}$ ולכן $T\underline{x}=\lambda \underline{x}$ .
נניח כי האיבר הדומיננטי(הגדול בערכו המוחלט) ב- $\underline{x}$ הוא $x_{1}$ .
נארגן מחדש את המשוואה הראשונה במערכת $T\underline{x}=\lambda \underline{x}$ :

t_{11}x_{1}+\sum_{j=2}^n t_{1j}x_{j}=\lambda x_{1}\implies \sum_{j=2}^n t_{1j}x_{j}=(\lambda-t_{11})x_{1}\implies \sum_{j=2}^{n} t_{1j} \frac{x_{j}}{x_{1}}=(\lambda-t_{11})

לכן נקבל:

|\lambda-t_{11}|=\left| \sum_{j=2}^n t_{1j} \frac{x_{j}}{x_{1}} \right|\leq \sum_{j=2}^n |t_{1j}|\cdot \left| \frac{x_{j}}{x_{1}} \right| \leq \sum_{j=2}^n |t_{1j}|

מכיוון שאיננו יודעים באיזה אלמנט של $\underline{x}$ מתקבל האיבר הדומיננטי, אנו "סורקים" על פני כל השורות.
∎

דוגמה

עבור המטריצה $T=\begin{pmatrix}4 & 0.4 & 0.2 & 1\\0.9 & 2 & 0.3 & -0.7\\-0.2 & 0.1 & 1 & 0.5 \\ 1 & 1 & -0.4 & 3\end{pmatrix}$ נמצא את הטבעות:

D_{1}=\left\{ z \in \mathbb{C}| |z-4|\leq1.6 \right\} \quad D_{2}=\left\{ z \in \mathbb{C}| |z-2|\leq 1.9 \right\}

D_{3}=\left\{ z \in \mathbb{C}| |z-1|\leq 0.8 \right\} \quad D_{4}=\left\{ z \in \mathbb{C}| |z-3|\leq 2.4 \right\}

הע"ע של $T$ הינם: $\lambda_{1}=4.74,\lambda_{2}=1.18,\lambda_{3}=2.04+0.79i,\lambda_{4}=2.04-0.79i$ .
נשים לב כי הם באמת בתוך הלולאות.

דוגמה

עבור המטריצה מהדוגמה הקודמת, מה צריך להיות $a$ על מנת להבטיח את יציבותה של המטריצה $aT$ ?

a< \frac{1}{|\lambda_{1}|}=\frac{1}{4.74}

ע"פ משפט גרשגורן, ניכר כי הנקודה הרחוקה ביותר מהראשית היא $5.6$ ולכן, אם אנו לא יודעים את הע"ע נוכל לדרוש משהו חלש יותר: $a< \frac{1}{5.6}$

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

מטריצה $T$ נקראת דומיננטית באלכסון אם מתקיים כי כל איבר אלכסון גדול ממש(בערכו המוחלט) מסכום יתר האיברים בשורתו.
כלומר,

\forall 1\leq k\leq n:\;\; |t_{kk}|> \sum_{j\neq k}\left|t_{kj}\right|

מסקנה

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

מסקנה (מהמסקנה)

מטריצה דומיננטית באלכסון בהכרח הפיכה כי אפס לא יכול להיות ע"ע שלה.

פתרון בעיות באמצעות אלגוריתמים איטרטיביים

פתרון מערכת משוואות $Ax=b$

נקח $A$ ריבועית והפיכה ונרצה לפתור את מערכת המשוואות $A\underline{x}=\underline{b}$ .
הבעיה שלנו היא ש- $A$ ענקית. כלומר, $n\gg 1000$ ולכן $LU,QR$ או $SVD$ לא יעבדו שכן לוקח להם יותר מידי זמן.
בנוסף, שיטות הפתרון הנ"ל מובילות לפתרון מדוייק ואנו סבבה עם להתפשר על פתרון "מספיק קרוב" שיושג עם מעט חישובים.

Proposition

בחר פתרון אתחול מסויים $\underline{x}_{0}$ (למשל $\underline{0}$ )
עדכן פתרון זה באופן איטרטיבי ע"י הנוסחה $\underline{x}_{k+1}=T\underline{x}_{k}+\underline{c}$ .

כעת נגלה מהן $T,c$ ולמה זה בכלל יעבוד?

מחד, בהנחה שחלה התכנסות, עבור $k\to \infty$ נגיע לפתרון $\underline{x}^*$ המקיים $\underline{x}^*=T\underline{x}^*+\underline{c}$ , מאידך, אנו רוצים שפתרון זה יהיה $\underline{x}^*=A^{-1}\underline{b}$ .
לכן נקבל את הקשר:

(I-T)A^{-1}\underline{b}=\underline{c}

דוגמה

נבחר $\underline{c}=\underline{b}$ וכמו כן $T=I-A$ .
ברור שהבחירה מקיימת את המשוואה ולכן $\underline{x}_{k+1}=T\underline{x}_{k}+\underline{c}=(I-A)\underline{x}_{k}+\underline{b}$ .
אם אלגוריתם זה יתכנס, הוא ישאף לפתרון הנכון.

Proposition (לבחירה שיטתית)

נעביר את $A\underline{x}$ אגף לקבלת $\underline{0}=-A\underline{x}+\underline{b}$ . נוסיף $\underline{x}$ לשני האגפים כעת: $\underline{x}=(I-A)\underline{x}+\underline{b}$ . נקבל אם כן:

\underline{x}_{k+1}=(I-A)\underline{x}_{k}+\underline{b}

כעת אם האלגוריתם יתכנס הוא יגיע לפתרון הנכון.

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

כעת נרצה לדעת מה צריך לדרוש כדי שהמשוואה תתכנס:

אם התהליך יתכנס נקבל $\underline{x}^*=T\underline{x}^*+\underline{c}$
נחסר את משוואה זו ונקבל: $(\underline{x}_{k+1}-\underline{x}^*)=T(\underline{x}_{k}-\underline{x}^*)$
נסמן $\underline{e}_{k}=\underline{x}_{k}-\underline{x}^*$ ואז $\underline{e}_{k+1}=T\underline{e}_{k}$ .

מסקנה

אם $T$ יציבה, אזי התהליך יתכנס.

אלגוריתם ג'קובי

תהי $A$ מטריצה.
את $A$ ניתן תמיד לפצל לסכום מהתצורה $A=L+D+U$ כאשר:

$L$ - משולשת תחתונה ממש
$U$ - משולשת עליונה ממש
$D$ - אלכסונית

A\underline{x}=\underline{b}\implies (L+U+D)\underline{x}=\underline{b} \implies D\underline{x}=\underline{b}-(L+U)\underline{x}\implies \underline{x}=D^{-1}(\underline{b}-(L+U)\underline{x})

נקבל אם כן כי:

\underline{x}_{k+1}=D^{-1}(\underline{b}-(L+U)\underline{x}_{k})=D^{-1}(\underline{b}-(A-D)\underline{x}_{k})=\underline{x}_{k}+D^{-1}(\underline{b}-A\underline{x}_{k})

נשים לב כי זה ממש אלגנטי, אם $\underline{b}-A\underline{x}_{k}=0$ המערכת בעצם אומרת לנו שהגענו לפתרון כי מנקודה זו מתקיים $\underline{x}_{k+1}=\underline{x}_{k}$ .

הערה

אם יש אפסים באלכסון של $D$ לא נוכל להרשות לעצמנו לבצע את האלגוריתם הזה.

מיהם $\left\{ T,\underline{c} \right\}$ בסיפור הזה והאם $T$ יציבה?

\underline{x}_{k+1}=\underbrace{-D^{-1}(L+U)}_{T}\underline{x}_{k}+\underbrace{D^{-1}\underline{b}}_{\underline{c}}

הערה

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

משפט (אלגוריתם

Jacobi

)

\underline{x}_{k+1}=D^{-1}(\underline{b}-(L+U)\underline{x}_{k})

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

הוכחה:
עלינו להראות כי $T=-D^{-1}(L+U)$ יציבה אם $A$ דומיננטית באלכסון.
נסתכל על שורה $k$ במטריצה $T$ :

\begin{pmatrix} -\frac{a_{k1}}{a_{kk}} & -\frac{a_{k2}}{a_{kk}} & \cdots & -\frac{a_{k(k-1)}}{a_{kk}} & 0 & -\frac{a_{k(k+1)}}{a_{kk}} & \cdots & -\frac{a_{k(n-1)}}{a_{kk}} & -\frac{a_{kn}}{a_{kk}} \end{pmatrix}

סכום הערכים המוחלטים של איברי שורה זו הואL

\frac{|a_{k1}|+|a_{k2}|+\dots+|a_{k(k-1)}|+|a_{k(k+1)}|+\dots+|a_{k(n-1)}|+|a_{kn}|}{|a_{kk}|}

בשל היות $A$ דומיננטית באלכסון, מנה זו בהכרח קטנה מ- $1$ ולכן, מפאת העובדה שזה מתקיים לכל שורה, $\lVvert T \rVvert_{\infty}<1$ ולכן $T$ יציבה.
∎

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

נבצע מעבר אלגברי על המשוואה ונקבל:

D\underline{x}_{k+1}+(L+U)\underline{x}_{k}=\underline{b}

בהינתן $\underline{x}_{k}$ באיטרציה ה- $k$ המשוואה פועלת כך:

הקפא את כל איברי הפתרון למעט ה- $j$ ועדכן אותו על מנת לקיים את המשוואה.
כל משוואה מעדכנת איבר אחד בפתרון.
צירוף מקבילי של כל אלה נותן את $\underline{x}_{k+1}$ .

פה נשים לב למשהו מוזר, אם עדכנו כבר את $j$ האיברים הראשונים, למה לא לנצל את ערכם העדכני בעדכון האיבר ה- $j+1$ ? את זה נפתור באמצעות האלגוריתם הבא:

אלגוריתם גאוס-איידל

נבנה משוואה איטרטיבית חדשה תוך שאנו מנצלים את הפירוק $A=L+D+U$ בנוסף לאסטרטגיית נקודת השבת.

A\underline{x}=\underline{b}\implies (L+D+U)\underline{x}=\underline{b}\implies (D+L)\underline{x}=\underline{b}-U\underline{x}\implies \underline{x}=(L+D)^{-1}(\underline{b}-U\underline{x})

\underline{x}_{k+1}=(L+D)^{-1}(\underline{b}-U\underline{x}_{k+1})

זהו אלגוריתם גאוס-איידל (באנגלית כותבים את השמות שלהם: $Gauss-Seidel$ )

לכאורה עלינו להפוך כאן מטריצה, אך זה לא הסיפור - אנו בעצם יכולים לפתור את מערכת המשוואות $(L+D)\underline{x}_{k+1}=\underline{b}-U\underline{x}_{k}$ מה שיעשה באמצעות החלפה קדמית, כאשר אנו מעדכנים את וקטור הפתרון איבר-איבר בצורה סדרתית.

נשים לב להבדל משמעותי מהאלגוריתם הקודם שכן פה, בהינתן $\underline{x}_{k}$ באיטרציה ה- $k$ , המשוואה פועלת הפעם כך:

הקפא את כל איברי הפתרון למעט ה- $j$ ועדכן אותו.

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

משפט (אלגוריתם

Gauss-Seidel

)

\underline{x}_{k+1}=(L+D)^{-1}(\underline{b}-U\underline{x}_{k})

מתכנס לפתרון מערכת משוואות $A\underline{x}=\underline{b}$ אם $A$ מטריצה סימטרית וחיובית מוגדרת, או דומיננטית באלכסון.

ההוכחה מורכבת מעט ולכן לא בקורס הזה.

הערה

ישנו אלגוריתם נוסף הנקרא $SOR$ והוא

\underline{x}_{k+1}=(L+\alpha D)^{-1}(\underline{b}-((1-\alpha)D+U)\underline{x}_{k})

עבור $\alpha=1$ אלגוריתם זה מתלכד עם גאוס-איידל.
בדרך כלל נבחר את $\alpha$ עם ערך גדול מ- $1$ על מנת לסחוט התכנסות מהירה יותר.

שימוש באלגוריתם למטריצות כלליות

אם היינו רוצים לפתור מערכת משוואות עם מטריצה כללית $A$ , אז על מנת להפוך אותה לחיובית מוגדרת נכפיל ב- $A^t$ ונקבל:

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

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

פתרון בעיות ריבועים פחותים

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

\underset{\underline{x}}{\min} \frac{1}{2}\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2=\underset{\underline{x}}{\min} \frac{1}{2}\underline{x}^tK\underline{x}-\underline{x}^t\underline{f}+c

אנו יודעים כי הפתרון לבעיה זו עד כה היה:

A^tA\underline{x}=A^t\underline{b} \qquad \lor \qquad K\underline{x}=\underline{f}

אנו טכנית יכולים לחשב את המטריצה $K=A^tA$ ואז לבצע את גאוס איידל אך זה לא פתרון טוב שכן הכפלת מטריצות בגדלים העצומים הללו היא פעולה שלוקחת מלאאאאאא זמן.

אלגוריתם השיפוע המירבי

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

שיטה 1

הגישה הראשונה תפעל ברוח הגישה של נקודת השבת שראינו ממקודם.

A^tA\underline{x}=A^t\underline{b} \underset{\mu\neq 0}{\implies} \underline{0}=\mu(A^t\underline{b}-A^tA\underline{x}) \implies \underline{x}=\underline{x}+\mu A^t(\underline{b}-A\underline{x})

\Downarrow

\underline{x}_{k+1}=\underline{x}_{k}+\mu A^t(\underline{b}-A\underline{x}_{k})=(\underbrace{I-\mu A^tA}_{T})\underline{x}_{k}+\mu A^t\underline{b}

נשים לב כי נדרש כי $T$ שלנו תהיה יציבה, כלומר, ש- $I-\mu A^tA$ תהיה יציבה על מנת שהאלגוריתם יתכנס.
נשים לב בנוסף כי במטריצה הזו יש לנו פרמטר $\mu$ שנוכל לשחק איתו ובכך אולי להשיג מטריצות יציבות.

שיטה 2

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

f(\underline{x})=\frac{1}{2}\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2\implies \nabla f(\underline{x})=A^t(A\underline{x}-\underline{b})

בכל איטרציה, כשאנו בנקודה $\underline{x}_{k}$ , נחשב את הגרדיאנט של $f(x)$ בנקודה זו, ונלך בכיוון ההפוך לכיוונו כך:

\underline{x}_{k+1}=\underline{x}_{k}-\mu A^t(A\underline{x}_{k}-\underline{b})

המקדם $\mu$ נחוץ כי אנו צריכים לקבוע איזו כברת דרך לעשות בכיוון הנבחר.

מוצאים את המקדם

בשתי השיטות הגענו בסוף לאותה המשוואה בעלת המקדם $\mu$ . נרצה למצוא אותו כך שהמטריצה $T=I-\mu A^tA$ תהיה יציבה.
נשים לב כי $A^tA$ חיובית מוגדרת ולכן יש לה $n$ ע"ע ממשיים וחיוביים.
נקח $\lambda$ שהינו ע"ע של $A^tA$ עם ו"ע התואם לו $\underline{v}$ ונקבל:

A^tA\underline{v}=\lambda \underline{v}\implies -\mu A^tA\underline{v}=-\mu\lambda \underline{v}\implies I\underline{v}-\mu A^tA\underline{v}=\underline{v}-\mu\lambda \underline{v}\implies (I-\mu A^TA)\underline{v}=(1-\mu\lambda)\underline{v}

קיבלנו אם כן כי $1-\mu\lambda$ הוא ע"ע של $T$ עם אותו ו"ע.

מסקנה

עבור הע"ע של $A^tA$ המסומנים $\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n-1}\geq\lambda_{n}>0$ נקבל כי לכל $1\leq k\leq n$ הערך $(1-\mu\lambda_{k})$ הוא ע"ע של $T=I-\mu A^tA$ .

מסקנה (מהמסקנה)

כדי ש- $T$ תהיה יציבה, עלינו לדרוש:

g(\mu)=\underset{1\leq k\leq n}{\max} |1-\mu\lambda_{k}|< 1

מה שראינו פה זה פונקציה, לכן, נוכל לחקור אותה ולהגיע לפתרון. נסתכל על גרף הפונקציה:
5 - שיטות איטרטיביות 2026-07-02 10.20.03.excalidraw.svg

כעת, נוכל לקחת את המקסימום של כל חלק וזו תהיה $g(\mu)$ שלנו:
5 - שיטות איטרטיביות 2026-07-02 10.24.47.excalidraw.svg
כעת, ברור כי על מנת להבטיח התכנסות אנו חייבים לדרוש כי:

0<\mu< \frac{2}{\lambda_{1}}

כעת, לאחר שהגדרנו גבולות ברורים למקדם, אנו נרצה למצוא את המקדם האופטימלי, זה שיביא לנו את ההתכנסות הכי מהירה ⟸ הוא נקודת המינימום של $g(\mu)$ שראינו בגרף הנ"ל.
על מנת למצוא את הנקודה הזו, נמצא את נקודת החיתוך בין הגרפים הירוק והצהוב:

1-\mu\lambda_{n}=\mu\lambda_{1}-1

2=\mu(\lambda_{1}+\lambda_{n})

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

g\left( \frac{2}{\lambda_{1}+\lambda_{n}} \right)=\frac{\lambda_{1}-\lambda_{n}}{\lambda_{1}+\lambda_{n}}=\frac{\kappa \left\{ A^tA \right\}-1}{\kappa \left\{ A^tA \right\}+1}=p\left\{ T \right\}

אנו רואים כי אשר מפר המצב של $A^tA$ גבוה, ההתכנסות תהיה איטית.

עוד משחקים על המקדם

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

נסתכל על השיטה:

נניח כי עתה סיימנו את האיטרציה ה- $k$ ובידינו הפתרון הזמני $\underline{x}_{k}$ .
באיטרציה הבאה אנו נפעל לפי העדכון הבא:
$\underline{x}_{k+1}=\underline{x}_{k}-\mu A^t(A\underline{x}_{k}-\underline{b})=\underline{x}_{k}-\mu \underline{e}_{k}$
נבחר את הערך של $\mu$ כך שגובה הפונקציה יהיה המינימלי האפשרי כך:
$f(\underline{x}_{k+1})=\frac{1}{2}\left\lVert A\underline{x}_{k+1}-\underline{b} \right\rVert _{2}^2=\frac{1}{2}\left\lVert A\underline{x}_{k}-\mu A\underline{e}_{k}-\underline{b} \right\rVert _{2}^2=f(\mu)$
נשים לב כי הנעלם היחיד בפונקציה הזו הוא $\mu$ ובנוסף, זוהי רק פרבולה חד מימדית ("חזרתם לכיתה ט'" - מיקי אלעד)
נגזור את הביטוי שקיבלנו באמצעות גזירה מטריצית וקטורית ונקבל:
$\frac{df(\mu)}{d\mu}=-\underline{e}_{k}^tA^t(A\underline{x}_{k}-\mu A\underline{e}_{k}-\underline{b})=0$
נשים לב כי מתקיים:
$\mu \underline{e}_{k}^tA^tA\underline{e}_{k}=\underline{e}_{k}^tA^t(A\underline{x}_{k}-\underline{b})=\underline{e}_{k}^t\underline{e}_{k}$
ולכן נקבל כי:
$\mu=\frac{\underline{e}_{k}^t\underline{e}_{k}}{\underline{e}_{k}^tA^tA\underline{e}_{k}}=\frac{\left\lVert \underline{e}_{k} \right\rVert _{2}^2}{\left\lVert A\underline{e}_{k} \right\rVert_{2}^2 }$

וזה האלגוריתם המלא:

Algorithm 3 Normalized Steepest Descent (NSD)

Require: Matrix $A$ , Target vector $b$ , Initial guess vector $x_0$

Ensure: Approximate solution vector $x$

1: // Initialization

2: $k \gets 0$

3: $x_k \gets x_0$

4:while convergence criteria not met do

5: // Calculate the error vector

6: $e_k \gets A^T(A x_k - b)$

7: // Calculate the transformed vector

8: $f_k \gets A e_k$

9: // Calculate the optimal step size

10: $\mu_k \gets \frac{e_k^T e_k}{f_k^T f_k}$

11: // Update the solution

12: $x_{k+1} \gets x_k - \mu_k e_k$

13: // Increment the iteration counter

14: $k \gets k + 1$

15:end while

16:return $x_k$

לאלגוריתם יש בעיה

מסתבר שכיווני הצעידה שלנו באלגוריתם יוצרים בעיה.

\underline{x}_{k+1}=\underline{x}_{k}-\mu_{k}\underline{e}_{k}=\underline{x}_{k}-\mu_{k}A^t(A\underline{x}_{k}-\underline{b})

\underline{e}_{k+1}=A^t(A\underline{x}_{k+1}-\underline{b})=A^t(A(\underline{x}_{k}-\mu_{k}\underline{e}_{k})-\underline{b})=A^t(A\underline{x}_{k}-\underline{b})-\mu_{k}A^tA\underline{e}_{k}=(I-\mu_{k}A^tA)\underline{e}_{k}

זה לא מפתיע שכן $\underline{e}_{k}$ הוא וקטור השגיאה של פתרון המשוואה הנורמלית, וראינו כבר כי השגיאה צפויה להתנהג לפי $\underline{e}_{k+1}=T\underline{e}_{k}$ .
נכפיל משוואה זו משמאל ב- $\underline{e}_{k}^t$ ונקבל:

\underline{e}_{k}^t\underline{e}_{k+1}=\underline{e}_{k}^t(I-\mu_{k}A^tA)\underline{e}_{k}=\underline{e}_{k}^t\underline{e}_{k}-\mu_{k}\underline{e}_{k}^tA^tA\underline{e}_{k}\underset{\begin{matrix} \downarrow \\ \mu_{k}=\frac{\underline{e}_{k}^t\underline{e}_{k}}{\underline{e}_{k}^tA^tA\underline{e}_{k}} \end{matrix}}{=}0

מה שקורה פה בעצם הוא שהזווית בין כל שגיאה של כל איטריצה שואפת להיות $90\degree$ - האלגוריתם הזה מזגזג בצורה מטורפת.
זה לא הכי טוב, אבל זה האלגוריתם ויש דרכים להתמודד עם זה.

הפתרון הנפוץ ביותר הוא לסדר מעט את נוסחת האיטרציה לקבלת נוסחה מורכבת מעט יותר אשר איתה קצב ההתכנסות יכול להשתפר פלאים:

\underline{x}_{k+1}=\underline{x}_{k}-\mu_{k}\underline{e}_{k}+\theta_{k}\underline{x}_{k-1}

פתרון בעיות ערכים עצמיים ווקטורים עצמיים

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

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

\underline{u}_{k}=VA^k\underline{x}_{0}=\sum_{j=1}^n x_{0}(j)\cdot \lambda_{j}^k\underline{v}_{j}

נניח כי הע"ע מסודרים בסדר יורד לפי ערכם המוחלט ובנוסף נניח כי $|\lambda_{1}|>|\lambda_{2}|\geq |\lambda_{3}|\geq \dots\geq |\lambda _{n-1}|\geq |\lambda_{n}|$ . כלומר, שני הע"ע אשר בערך מוחלט הם הגדולים ביותר, אינם שווים.
כךף נוכל להגיד את הדבר הבא כאשר $k$ גדול דיו:

\underline{u}_{k}=\sum_{j=1}^n x_{0}(j)\cdot \lambda_{j}^k\underline{v}_{j} \cong x_{0}(1)\cdot\lambda_{1}^k\underline{v}_{1}

\underline{u}_{k}=T\underline{u}_{k-1} \cong Const\cdot\lambda_{1}^k\underline{v}_{1}

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

\frac{\underline{u}_{k}^t\underline{u}_{k+1}}{\underline{u}_{k}^t\underline{u}_{k}}=\frac{\underline{u}_{k}^tT\underline{u}_{k}}{\underline{u}_{k}^t\underline{u}_{k}}=\frac{\underline{u}_{k}^t(\lambda_{1}\underline{u}_{k})}{\underline{u}_{k}^t\underline{u}_{k}}\cong \lambda_{1}

יש אלגוריתם, אז הכל אחלה - וייייייייייייייייייייייי
אלא, שיש בעיה אחת, הוא לא עובד!!! זאת מפאת העובדה שהמקדם $\lambda_{1}^k$ או צולל לאפס או תופח ל- $\infty$ ומגיעים מהר מאוד לבעיות נומריות קשות.

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

Algorithm 4 Power Method

Require: Matrix $T$ , Initial normalized guess vector $u_0$

Ensure: Approximate dominant eigenvector $u_k$

1: // Initialization

2: $u_0 \gets \text{initial normalized vector}$

3: $k \gets 1$

4:while convergence criteria not met do

5: // Update the output of the dynamic system

6: $u_k \gets T u_{k-1}$

7: // Normalize the solution vector

8: $u_k \gets \frac{u_k}{\|u_k\|_2}$

9: // Increment the iteration counter

10: $k \gets k + 1$

11:end while

12:return $u_k$

משפט

שיטת החזקה מובטחת להגיע לוקטור העצמי המתייחס לע"ע הגדול ביותר אם מתקימים שני התנאים הבאים:

ע"ע זה מבודד, כלומר, $|\lambda_{1}|>|\lambda_{2}|$ .
וקטור האיתחול אינו מנוון את הו"ע המבוקש:

\underline{u}_{k}=VA^k\underline{x}_{0}=\sum_{j=1}^n x_{0}(j)\cdot \lambda_{j}^k\underline{v}_{j}\implies x_{0}(1)\neq 0

הערה על ההוכחה שאין: אם נכניס הנחה נוספת של היות $T$ לכסינה, כבר הוכחנו זאת בנכתב למעלה, אך מסתבר שדרישת הלכסינות אינה דרושה ואת החלק הזה לא נוכיח בקורס.

מסקנה

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

גרסאות לאלגוריתם

גרסת ההיפוך

אם נרצה לכוון לע"ע הקטנים ביותר נרצה להפוך את ההתכנסות ולכן:

\underline{u}_{k}=T^{-1}\underline{u}_{k-1}

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

גרסת ההזזה

אם משוואת העדכון תשתנה כך:

\underline{u}_{k}=(T-\alpha I)\underline{u}_{k-1}

אזי האלגוריתם יתמקד בע"ע של $T-\alpha I$ הרחוק ביותר מהראשית.

מציאת כל הע"ע והו"ע

אם נרצה למצוא מספר ע"ע וו"ע לא נוכל להריץ את התהליך מספר פעמים, שכן כל התוצאות יהיו הוקטור הראשון.
נניח מעתה כי המטריצה $T$ סימטרית ולכן ידוע כי וקטוריה העצמיים אמורים להיות אורתוגונליים.
לכן, נוכל להריץ את התהליך במקביל ולבצע אורתוגונליזציה בין הוקטורים אחרי כל איטרציה, כצעד שמחליף את הנרמול הנפרד לוקטורים.
גישה זו עובדת יפה אך רק למטריצות סימטריות. גרסה למטריצות שאינן סימטריות אנו נראה בתרגול :)

Algorithm 5 Iterative Solution for Eigenvalue Problems (Subspace Iteration)

Require: Symmetric matrix $T$ of size $n \times n$ , Number of desired eigenvectors $J$

Ensure: Matrix $U_k \in \mathbb{R}^{n \times J}$ containing approximate dominant eigenvectors

1: // Initialization

2: // Set initial eigenvectors to form an orthonormal set

3: $U_0 \gets \text{initial orthonormal matrix } \in \mathbb{R}^{n \times J}$

4: $k \gets 1$

5:while convergence criteria not met do

6: // Update the output of the dynamic system

7: $U_k \gets T U_{k-1}$

8: // Apply Gram-Schmidt (QR) process on $U_k$

9: $U_k \gets \text{Orthonormalize}(U_k)$

10: // Increment the iteration counter

11: $k \gets k + 1$

12:end while

13:return $U_k$

5 - שיטות איטרטיביות

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

שיטות איטרטיביות

5 - שיטות איטרטיביות

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

שיטות איטרטיביות

תהליכים איטרטיביים

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

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

הקשר בין נורמת פורביניוס לנורמה שראינו עכשיו

משפט הדיסקאות של גרשגורן

פתרון בעיות באמצעות אלגוריתמים איטרטיביים

פתרון מערכת משוואות $Ax=b$

אלגוריתם ג'קובי

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

אלגוריתם גאוס-איידל

שימוש באלגוריתם למטריצות כלליות

פתרון בעיות ריבועים פחותים

אלגוריתם השיפוע המירבי

שיטה 1

שיטה 2

מוצאים את המקדם

עוד משחקים על המקדם

לאלגוריתם יש בעיה

פתרון בעיות ערכים עצמיים ווקטורים עצמיים

גרסאות לאלגוריתם

גרסת ההיפוך

גרסת ההזזה

מציאת כל הע"ע והו"ע

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

שיטות איטרטיביות

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

שיטות איטרטיביות

תהליכים איטרטיביים

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

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

הקשר בין נורמת פורביניוס לנורמה שראינו עכשיו

משפט הדיסקאות של גרשגורן

פתרון בעיות באמצעות אלגוריתמים איטרטיביים

פתרון מערכת משוואות Ax=bAx=bAx=b

אלגוריתם ג'קובי

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

אלגוריתם גאוס-איידל

שימוש באלגוריתם למטריצות כלליות

פתרון בעיות ריבועים פחותים

אלגוריתם השיפוע המירבי

שיטה 1

שיטה 2

מוצאים את המקדם

עוד משחקים על המקדם

לאלגוריתם יש בעיה

פתרון בעיות ערכים עצמיים ווקטורים עצמיים

גרסאות לאלגוריתם

גרסת ההיפוך

גרסת ההזזה

מציאת כל הע"ע והו"ע

פתרון מערכת משוואות $Ax=b$