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

נורמה של וקטור

עבור וקטור , האורך האוקלידי שלו מוגדר כ:

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

נורמת האינסוף - הרכיב הכי גדול בוקטור :
הנורמה 1 - סכום כל הרכיבים של הוקטור :

ההגדרה של נורמה היא מאוד כללית:

הגדרה:

נורמה היא פונקציה על רצף של מספרים סקלרים, המסומנת ב-, ומקיימת את התנאים הבאים:
1.

| \alpha \bar{x}|=|\alpha|| \bar{x}| \quad \forall a\in \mathbb{R}

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

דוגמה:

נניח ואנחנו נרצה למצוא את המרחק בין שני וקטורים:
$Missing \begin{pmatrix} or extra \end{pmatrix}11 \\ 12 \\ 13 \end{pmatrix} \quad \quad \bar{y}=\begin{pmatrix} 12 \\ 14 \\ 16 \end{pmatrix}$$ אז נגדיר: $$\bar{z}=\bar{y}-\bar{x}=\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}$$ אז מתקיים: $$\begin{aligned} & \| \bar{z}\|_{1}=1+2+3=6 \\ & \| \bar{z}\|_{2}=\sqrt{ 1+4+9 }\approx 3.7417 \\ & \| \bar{z}\|_{\infty} =3 \end{aligned}$$ למרות שהערכים של הנורמות שונים, הם בעלי אותו הסדר גודל.$

ניתן לראות בדוגמה האחרונה שמתקיים:

טענה זו נכונה בכללית. מעבר לכך, ניתן להוכיח כי לכל מתקיים:

Extra close brace or missing open brace\begin{gather} \| \bar{x}\|_{\infty }\leq \| \bar{x}\|_{2}\leq \sqrt{ n }\| \bar{x}\|_{\infty } \\ \| \bar{x}\|_{\infty}\leq \| \bar{x}\|_{1}\leq n\| \bar{x}\|_{\infty } \end{gather} } $$ האיור הבא מראה את כל הוקטורים ב-$\mathbb{R}^{2}$ שהנורמות שלהם שווים ל-$1$, לפי כל אחד מהנורמות שראינו: ![[Screenshot_20240215_223723_OneDrive.jpg|book]] > "מעגל היחידה" לפי כל אחד מהנורמות. נשים לב שהמעוין כלול בתוך העיגול, שהוא בעצמו כלול בתוך הריבוע. # נורמה של מטריצה ניזכר מאלגברה לינארית מהי מטריצה [[ALG1_009 טרנספורמציות לינאריות#סינגולריות|סינגולרית]]. בגדול, מטריצה לא [[ALG1_007 מטריצות הפיכות#מטריצה-הפיכה|הפיכה]] היא מטריצה **סינגולרית**. נורמה של מטריצה היא כלי שנותן לנו מדד לכמה מטריצה רחוקה מסינגולריות, ובכך למדוד את *יציבות* האלגוריתם שלנו. >[!Question]- מה הכוונה ביציבות? > >כאשר אנו מריצים אלגוריתם עבור ערכים כלשהם, אנחנו נרצה שעבור כל שינוי קטן בערכים שהכנסנו, יהיה גם שינוי קטן בתוצאה שלנו. ככל שהשינוי בתוצאה יותר קטן, נאמר שהאלגוריתם *יציב* יותר. אנו בהגדרת נורמה של מטריצה שהיא *מושרית* מהגדרת הנורמה לוקטור. לכן היא נקראת **נורמה מושרית**: >[!def] הגדרה: >**הנורמה המושרית** של מטריצה $A^{m\times n}$ מוגדרת כך: >$$\begin{aligned} > \| A\|_{}&=\max_{\bar{x}\neq 0} \dfrac{\| A\bar{x}\|_{} }{\| \bar{x}\|_{} } \\[2ex] > &=\max_{\| \bar{x}\|_{}=1 }\| A\bar{x}\|_{} > \end{aligned} $$ לא קשה להראות שהנורמה המושרית עומדת בכל התנאים להגדרה של נורמה. מעבר לכך, היא עומדת **בתנאי העקביות**: $$\| AB\|_{}\leq \| A\|_{}\| B\|_{} $$ בפרט, עבור כל וקטור $\bar{x}$ בעל הממדים הנכונים, מתקיים: $$\| A\bar{x}\|_{}\leq \| A\|_{}\| \bar{x}\|_{} $$ נחשב כעת את נורמה-$1$, נורמה-$2$ ונורמה-$\infty$ של מטריצה כללית, כדי לקבל נוסחאות יותר מקוצרות עבור כל אחת: ## נורמה-$\infty$ יהי $\bar{x}$ וקטור כך ש-$\| \bar{x}\|_{\infty}=1$. לפיכך, מתקיים: $$|x_{j}|\leq 1,\quad\quad j=1,\dots ,n$$ לכן, לפי נורמה-$\infty$ של וקטור: $$\begin{align} \| A\bar{x}\|_{\infty }&=\max_{i}\left| \sum_{j=1}^{n} a_{ij}x_{j}\right| \\[1ex] & \leq \max_{i}\sum_{j=1}^{n} |a_{ij}||x_{j}| \\[1ex] &\leq \max_{i}\sum_{j=1}^{n} |a_{ij}| \tag{1} \end{align} $$ נבחר אינדקס $p$ שהוא אינדקס השורה בעלת סכום הערכים המוחלטים הכי גדול ב-$A$: $$\sum_{j=1}^{n} |a_{pj}|=\max_{i}\sum_{j=1}^{n}|a_{ij}| $$ ולכן נוכל לרשום את $(1)$ כך: $$\| A\|_{\infty }=\max_{\| \bar{x}\|_{\infty } =1} \| A\bar{x}\|_{\infty } \leq \sum_{j=1}^{n} |a_{pj}| \tag{2}$$ נבחר כעת $\bar{x}$ אחר, כך ש: $$\tilde{x}_{j}=\begin{cases} 1 & & a_{pj}\geq 0 \\ 0 & & a_{pj}=0 \\ -1 & & a_{pj}\leq 0 \end{cases}$$ נקבל מכך ש: $$a_{pj}\tilde{x}_{j}=|a_{pj}|$$ אז עבור $\bar{x}=\tilde{x}$ מתקיים: $$\| A\tilde{x}\|_{\infty }=\max_{i}\left|\sum_{j=1}^{n} a_{ij}\tilde{x}_{j}\right|\geq \left| \sum_{j=1}^{n} a_{pj}\tilde{x}_{j}\right|=\sum_{j=1}^{n} |a_{pj}| \tag{3} $$ מאחר ומתקיים האי שוויון $\| A\tilde{x}\|_{\infty}\leq \| A\|_{\infty}$, נוכל לשלב את $(2)$ ו-$(3)$: $$\sum_{j=1}^{n} |a_{pj}|\leq \| A\tilde{x}\|_{\infty }\leq \| A\|_{\infty }\leq \sum_{j=1}^{n} |a_{pj}| $$ נקבל כי מתקיים שוויון לאורך כלל האי שוויון: $$\boxed { \| A\|_{\infty }=\max_{1\leq i\leq m}\sum_{j=1}^{n} |a_{ij}| }$$ כלומר, הנורמה-$\infty$ של $A$ היא הסכום המקסימלי של איברים *בשורה*. ## נורמה-$1$ נוכל באותה צורה להגיע למסקנה כי: $$\boxed{\| A\|_{1}=\max_{1\leq j\leq n}\sum_{i=1}^{m} |a_{ij}| }$$ כלומר, הנורמה-$1$ של $A$ היא הסכום המקסימלי של איברים *בעמודה*. ## נורמה-$2$ - רדיוס ספקטרלי כדי לחשב את הנורמה-$2$ של מטריצה, אנחנו צריכים לקחת בחשבון את ה[[ALG1_010 וקטורים עצמיים וערכים עצמיים#עע-ווע-למטריצה|ערכים העצמיים]] של המטריצה $A^{T}A$. >[!def] הגדרה: > > תהי $B$ מטריצה ריבועית $n\times n$, כך שיש לה $n$ ע"ע. **הרדיוס הספקטרלי** של $B$ מוגדר כ: > $$\rho(B)=\max_{}{\{ \left|\lambda\right| \mid \lambda \text{ is an eigenvalue of }B \}}$$ אם $(\tilde{\lambda},\tilde{x})$ הם זוג ע"ע וו"ע כך ש-$\lambda$ מקסימלי ל-$B$, ו-$\tilde{x}$ מנורמל כך ש-$\| \tilde{x}\|_{}=1$, אז: $$\rho(B)=\left|\tilde{\lambda}\right|=\| \tilde{\lambda}\tilde{x}\|_{}=\| B\tilde{x}\|_{}\leq \| B\|_{} $$ לכן, *כל נורמה מושרית* חסומה מלמטה ע"י הרדיוס הספרטרלי! >[!notes] הערה: > >רדיוס ספקטרלי של מטריצה ריבועית הוא *לא* הנורמה שלו. ניתן להראות (בעזרת הוכחה שלא ניכנס אליה) שעבור מטריצות שהן לא בהכרח ריבועיות (כלומר מסדר $m\times n$), מתקיים: $$\boxed { \| A\|_{2}=\sqrt{ \rho(A^{T}A) } } $$ כאשר נשים לב ש-$A^{T}A$ היא בהכרח מטריצה סימטרית (ריבועית) עם ע"ע חיוביים, $\lambda_{i}^{2}$, וממשפט שלא נוכיח אותו, הו"ע אורתוגונליים. בצורה אינטואיטיבית, אפשר לחשוב על הנורמה-$2$, שנקראת גם **הנורמה הספקטרלית**, כה'הגדלה' המקסימלית שמטריצה יכולה להפעיל על וקטור (אם חושבים על מטריצה כ[[ALG1_009 טרנספורמציות לינאריות#מטריצה-מייצגת|טרנספורמציה לינארית]]). <center><iframe width=400 height=600 scrolling="no" frameborder="0" src="https://www.wolframcloud.com/obj/demonstrations/Published/MatrixNormAndSpectralNorm?_view=EMBED" style="border:0;" class="geo"></iframe></center> ## מספר מצב **מספר מצב** של פונקציה מסוימת מודדת כמה התוצאה של הפונקציה משתנה ביחס לשינוי קטן בקלט שלה. כלומר, מספר מצב מתאר את היציבות של פונקציה כשלהי. במערכת משוואות לינארית $A\bar{x}=\bar{b}$ , המספר מצב נותן חסם עליון לכמה הניחוש $\tilde{x}$ יהיה קרוב לפתרון האמיתי $\bar{x}$. נשים לב שמספר מצב זוהי תכונה של המטריצה, ולא של האלגוריתם או הדיוק המספרי של המחשב שמחשב את התשובה. ניתן לחשוב על מספר מצב כהמידה בה הפתרון $\bar{x}$ ישתנה כתוצאה משינוי ב-$\bar{b}$. לכן, אם מספר המצב גדול, אפילו שינוי קטן ב-$\bar{b}$ יגרום לשגיאה גדולה ב-$\bar{x}$. >[!def] הגדרה: > >**מספר מצב** של מטריצה $A$ מוגדר כ: >$$\text{cond}(A)=\| A\|_{}\cdot \| A^{-1}\|_{} $$ >[!notes] הערה: >בעת חישוב של מספר המצב יש להשתמש באותו סוג נורמה לחישוב המטריצה והמטריצה ההופכית. נביט במערכת משוואות $A\bar{x}=\bar{b}$. בהינתן ניחוש של הפתרון $\tilde{x}$, נוכל לחסום את השגיאה היחסית. השגיאה האבסולוטית והשארית נתונים ע"י: $$\bar{e}_{\text{abs}} =\bar{x}-\tilde{x} \quad \quad \bar{r}=\bar{b}-A\tilde{x}$$ החסמים לשגיאה היחסית נתונים ע"י הנוסחה הבאה: $$\boxed{\dfrac{1}{\text{cond}(A)}\cdot \dfrac{\| \bar{r}\|_{} }{\| \bar{b}\|_{} }=\dfrac{\| \bar{e}_{\text{abs}}\|_{} }{\| \bar{x}\|_{} }=\text{cond}(A)\cdot \dfrac{\| \bar{r}\|_{} }{\| \bar{b}\|_{} } }$$

פנגייה

NUM1_003 נורמה

נורמה של וקטור

עמודים המציינים את העמוד הזה