7 - שגיאות נומריות — אלגוריתמים נומריים

עד כה ראינו כל מיני כלים כמו $LU,QR,SVD$ וכדומה והנחנו תמיד כי הנתונים עליהם אנו עובדים מושלמים ובנוסף החישובים להם נדרש יעשו בצורה מושלמת.
בפרק זה נראה כי לא כך הדבר באמת ונראה כיצד נוכל להתמודד עם זה.

הערה

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

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

יצוג מספרים במחשב והערכת שגיאות

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

הגישה הפשוטה ביותר שעולה על הדעת לייצוג מספרים היא שיטת הנקודה הקבועה אשר בה כל מספר מיוצג ע"י אוסף של $t=n+k+1$ הספרות העשרוניות הבאות:

(\pm1)d_{k}d_{k-1}d_{k-2}\dots d_{1}d_{0}.d_{-1}d_{-2}d_{-3}\dots d_{-n}

פה הנקודה קבועה במקומה ולא יכולה לזוז.

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

דוגמה

במחשב שלנו $n=2,k=4$ ונניח שעלינו לחשב את הפעולה $45632.25\cdot65421.12$ .
התוצאה הנכונה היא $2985312903.12$ אלא שמספר זה חור מהתחום האפשרי לייצוג במחשב שלנו ולכן התוצאה שתוצג תהיה למעשה $99999.99$ כי זה המספר הגדול ביותר האפשרי להצגה והכי קרוב לתוצאה הנכונה.

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

מנטיסה עם $(\pm 1)d_{0}.d_{-1}d_{-2}\dots d_{-n}$ .
אקספוננט עם $(\pm1)e_{m}e_{m-1}\dots e_{1}e_{0}$ .

כך שנקבל:

(\pm 1)d_{0}.d_{-1}d_{-2}\dots d_{-n}\cdot 10^{(\pm1)e_{m}e_{m-1}\dots e_{1}e_{0}}

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

הגדרה 1 (שגיאה מוחלטת ויחסית)

בהינתן $x\neq 0$ וערכו המקורב $\tilde{x}$ , השגיאה המוחלטת והשגיאה היחסית של $x$ יוגדרו כך:

\Delta x=x-\tilde{x}\quad\R{\text{שגיאה מוחלטת:}}

r_{x}=\frac{\Delta x}{x} \quad \R{\text{שגיאה יחסית:}}

הערה

בדרך כלל נתייחס לערך המוחלט של שגיאות אלה.

דוגמה

נניח כי נתון לנו הערך $x=0.23875$ ואנו נדרשים לייצג אותו עם $n=3$ ספרות מימין לנקודה ע"י העגלה ⟸ $\tilde{x}=0.239$ .
בהעגלה שכזו, השגיאה המוחלטת חסומה ע"י $|\Delta x|=2.5\cdot 10^{-4}<5\cdot 10^{-4}$ .
במקרה הכללי שגיאה זו חסומה ע"י $|\Delta x|\leq 5\cdot10^{-(n+1)}$ .
נשים לב כי אם אנו מתקרבים לאפס, השגיאה הולכת ל- $\infty$ .

אם נניח כי $d_{k}\geq 1$ אזי $|x|\geq 10^k$ ואז החסם על השגיאה היחסית יהיה:

r_{x}=\left| \frac{\Delta x}{x} \right|\leq \frac{5\cdot 10^{-(n+1)}}{10^k}=5\cdot 10^{-n-1-k}=5\cdot 10^{-t}

דוגמה

נניח כי בידינו וקטור $\underline{x}$ באורך $N$ ורצוננו לחשב את הנורמה האוקלידית של וקטור זה $\left\lVert \underline{x} \right\rVert_{2}$ .
נתון שערכי $\underline{x}$ שגויים ומתקיים שסטייתם $\delta x_{k}$ מקיימת $|\delta x_{k}|\leq\epsilon$ .

\left\lVert \tilde{\underline{x}} \right\rVert _{2}=\sqrt{ \sum_{k=1}^N \tilde{x}_{k}^2 }=\sqrt{ \sum_{k=1}^N (x_{k}+\delta x_{k})^2 } \cong \sqrt{\sum_{k=1}^N (x_{k}^2+2x_{k}\delta x_{k}) }\leq \sqrt{ \left\lVert \underline{x} \right\rVert_{2}^2+2\epsilon \sum_{k=1}^N |x_{k}| }=\sqrt{ \left\lVert \underline{x} \right\rVert_{2}^2+2\epsilon \left\lVert \underline{x} \right\rVert_{1} }

ננקה זאת באמצעות טור טיילור.

f(x+\epsilon)\cong f(x)+\epsilon \nabla f(x)\implies \sqrt{ x+\epsilon } \cong \sqrt{ x }+\frac{\epsilon}{2\sqrt{ x }}

כעת, נוכל להשתמש בטור טיילור:

\left\lVert \underline{\tilde{x}} \right\rVert _{2}\cong \left\lVert \underline{x} \right\rVert _{2}+\frac{2\epsilon \left\lVert \underline{x} \right\rVert _{1}}{2\left\lVert \underline{x} \right\rVert_{2} }

לכן נקבל כי השגיאה האבסולוטית הינה $\displaystyle \epsilon \frac{\left\lVert \underline{x} \right\rVert_{1}}{\left\lVert \underline{x} \right\rVert_{2}}$ . נשים לב כי פה אנו לא רגישים לכפל בסקלר של הוקטור.
השגיאה יחסית תהיה $\displaystyle \epsilon \frac{\left\lVert \underline{x} \right\rVert_{1}}{\left\lVert \underline{x} \right\rVert_{2}^2}$ . נשים לב כי הביטוי הזה כן רגיש לכפל בסקלר של הוקטור.

דוגמה

נסתכל על אוסף מספרים קטנים וחיוביים ונרצה לסכום אותם.
המספרים שמורים בשיטת הנקודה הצפה כאשר $k=0,n=4,m=10$ .
אם היינו עושים זאת בשיטה הצפויה, כלומר:

double S = 0;
for (int k = 1; k <= N; k++)
{
	S += x[k];
}

נניח כי $N$ מאוד גדול וכי $0<x_{k}<1$ .
בחישוב זה תתעורר בעיה, עם הצטברות הסכום $S$ תדרש העגלה לאיברים המצטרפים ותצטבר שגיאה משמעותית. למשל:

S_{n+1}=S_{n}+x_{n}=243.32+0.56872=243.88

הפתרון שהוצע להתמודדות עם השגיאה המצטברת הוצע ע"י $Kahan$ והוא:

double S = 0, err = 0;
for (int k = 1; k <= N; k++)
{
	Stemp = S+x[k]+err;
	err = err + x[k]+S-Stemp;
	S = Stemp;
}

שגיאות בפתרון מערכת משוואות

נתמקד כעת בבעיה מסויימת ודרכה נמחיש את הרגישות לשגיאות נומריות. אנו נדון בפתרון מערכת המשוואות $A\underline{x}=\underline{b}$ .
אנו יודעים כי החישובים שלנו מושלמים, אך במקום לקבל את $\left\{ A,\underline{b} \right\}$ אנו מקבלים גרסה "רועשת" שלו $\left\{ \tilde{A},\underline{\tilde{b}} \right\}=\left\{ A+\delta A,\underline{b}+ \underline{\delta b} \right\}$ .

הערה

$\delta A$ היא מטריצה שונה ולא הכפלה של סקלר $\delta$ ב- $A$ .
כלומר, $\delta A \in \mathbb{R}^{n\times m}$ ו- $\delta$ לבדו לא קיים.

אנחנו נלך לפתור עם $\tilde{A},\underline{\tilde{b}}$ ונראה מה תהיה השגיאה ב- $\underline{x}$ .

(A+\delta A)(\underline{x}+ \underline{\delta x})=\underline{b}+ \underline{\delta b}

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

A\underline{x}A\underline{\delta x}+\delta A\underline{x}+\delta A\underline{\delta \underline{x}}=\underline{b}+\underline{\delta b} \implies A \underline{\delta x}+\delta A\underline{x}=\underline{\delta b}\implies \underline{\delta x}=A^{-1}(\underline{\delta b}-\delta A\underline{x})

לכאורה יכולנו לעצור פה, אך נזכר כי אין לנו את $\underline{\delta b}$ או $\delta A$ שכן יש לנו רק את $A+\delta A$ ואת $\underline{b}+\underline{\delta b}$ .
ננסה לחסום את הגודל כעת:

\left\lVert \underline{\delta x} \right\rVert =\left\lVert A^{-1}(\underline{\delta b}-\delta A\underline{x}) \right\rVert \leq \lVvert A^{-1} \rVvert \cdot\left\lVert \underline{\delta b}-\delta A\underline{x} \right\rVert \leq \lVvert A^{-1} \rVvert (\left\lVert \underline{\delta b} \right\rVert+\lVvert \delta A \rVvert\cdot \left\lVert \underline{x} \right\rVert )

\frac{\left\lVert \underline{\delta x}\right\rVert }{\left\lVert \underline{x} \right\rVert }\leq \lVvert A^{-1} \rVvert \left( \frac{\left\lVert \underline{\delta b} \right\rVert}{\left\lVert \underline{x} \right\rVert }+\lVvert \delta A \rVvert \right)=\lVvert A^{-1} \rVvert \lVvert A \rVvert \left( \frac{\left\lVert \underline{\delta b} \right\rVert}{\lVvert A \rVvert\cdot \left\lVert \underline{x} \right\rVert }+\frac{\lVvert \delta A \rVvert}{\lVvert A \rVvert } \right)

נזכר כי $\left\lVert \underline{b} \right\rVert=\left\lVert A\underline{x} \right\rVert\leq \lVvert A \rVvert\cdot \left\lVert \underline{x} \right\rVert$ ולכן:

\frac{\left\lVert \underline{\delta x} \right\rVert }{\left\lVert \underline{x} \right\rVert }\leq \lVvert A^{-1} \rVvert \lVvert A \rVvert \left( \frac{\left\lVert \underline{\delta b} \right\rVert }{\left\lVert \underline{b} \right\rVert }+\frac{\lVvert \delta A \rVvert }{\lVvert A \rVvert } \right)

זה יהיה החסם העליון על השגיאה שהוא תלוי בשגיאה היחסית של $A$ והשגיאה היחסית של $\underline{b}$ והן מוכפלות באיזושהי תכונה מוזרה של $A$ .
נשים לב כי $\lVvert A \rVvert_{2}=\sigma_{1}$ ו- $\lVvert A^{-1} \rVvert_{2}=\frac{1}{\sigma_{n}}$ ולכן:

\lVvert A^{-1} \rVvert \lVvert A \rVvert =\frac{\sigma_{1}}{\sigma_{n}}=\kappa \left\{ A \right\}

נזכר שזה בדיוק מספר המצב של המטריצה $A$ ולכן:

\frac{\left\lVert \underline{\delta x} \right\rVert }{\left\lVert \underline{x} \right\rVert }\leq \left( \frac{\left\lVert \underline{\delta b} \right\rVert }{\left\lVert \underline{b} \right\rVert }+\frac{\lVvert \delta A \rVvert }{\lVvert A \rVvert } \right)\kappa \left\{ A \right\}

כעת, נניח כי $\underline{\delta b}=0$ ולכן אנו שוגים אך ורק ב- $A$ . כלומר, המשוואה שלנו היא $\delta A\underline{x}=\underline{b}$ ולכן כעת מתקיים:

\frac{\left\lVert \underline{\delta x} \right\rVert }{\left\lVert \underline{x} \right\rVert }\leq \frac{\lVvert \delta A \rVvert }{\lVvert A \rVvert }\kappa \left\{ A \right\}

נשאל את עצמנו כעת מהו הוקטור $\underline{b}$ הגרוע ביותר שיכול להיות? כלומר, מיהו $\underline{b}$ שיוביל לשגיאה הגדולה ביותר האפשרית בפתרון המקורב.
שתי הפתרונות נתונים ע"י $\underline{x}=A^{-1}\underline{b} \land \underline{\hat{x}}=(A+\delta A)^{-1}\underline{b}$ ולכן:

\frac{\left\lVert \underline{\delta x} \right\rVert^2 }{\left\lVert \underline{x} \right\rVert^2 } =\frac{\left\lVert \underline{\hat{x}}-\underline{x} \right\rVert^2 }{\left\lVert \underline{x} \right\rVert^2 }=\frac{\left\lVert (A+\delta A)^{-1}\underline{b}-A^{-1}\underline{b} \right\rVert^2 }{\left\lVert A^{-1}\underline{b} \right\rVert^2 }=\frac{\left\lVert ((A+\delta A)^{-1}-A^{-1})\underline{b} \right\rVert ^2}{\left\lVert A^{-1}\underline{b} \right\rVert ^2}=\frac{\underline{b}^tM_{1}\underline{b}}{\underline{b}^tM_{2}\underline{b}}

כאשר $M_{1},M_{2}$ מטריצות חיוביות חצי מוגדרות.
זוהי בדיוק בעיית ע"ע מוכללת קלאסית ופתרונה הוא הו"ע המוכלל בעל הערך העצמי הגבוה ביותר וזה יהיה הוקטור $\underline{b}$ שייתן את המקסימום עבור הביטוי הזה.

שגיאה בחישוב ע"ע וו"ע

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

(A+\delta A)(\underline{v}+\underline{\delta v})=(\lambda+\delta\lambda)(\underline{v}+\underline{\delta v})

A\underline{v}+A\underline{\delta v}+\delta A\underline{v}+\delta A\underline{\delta v}=\lambda \underline{v}+\lambda\underline{\delta v}+\delta\lambda \underline{v}+\delta\lambda\underline{\delta v}

A\underline{\delta v}=\delta A\underline{v}=\lambda\underline{\delta v}+\delta\lambda \underline{v}

נשים לב כי כל ע"ע וו"ע מקיימים את הקשר הזה.
נזכר כי אוסף הו"ע של $A$ מהווה בסיס אורתונורמלי ולכן נוכל לייצג את $\underline{\delta v}_{1}$ כצ"ל שלהם:

\underline{\delta v}_{1}=\sum_{k=1}^n \alpha_{k}^1\underline{v}_{k}\implies \sum_{k=1}^n \alpha_{k}^1A\underline{v}_{k}+\delta A\underline{v}_{1}=\sum_{k=1}^n \lambda_{1}\alpha_{k}^1\underline{v}_{k}+\delta\lambda_{1}\underline{v}_{1}

נציב $A\underline{v}_{k}=\lambda_{k}\underline{v}_{k}$ ואז:

\delta\lambda_{1}\underline{v}_{1}=\sum_{k=1}^n (\lambda_{k}-\lambda_{1})\alpha_{k}^1\underline{v}_{k}+\delta A\underline{v}_{1}

נכפיל את שני האגפים ב- $\underline{v}_{1}$ :

\delta\lambda_{1}=\delta\lambda_{1}\underbracket{\underline{v}_{1}^t\underline{v}_{1}}_{1}=\underbrace{\sum_{k=1}^n (\lambda_{k}-\lambda_{1})\alpha_{k}^1\underline{v}_{1}^t\underline{v})_{k}}_{\begin{matrix} \R{\text{רק האיבר הראשון נותר בשל המכפלה}} \\ \R{\text{הפנימית וגם הוא מתאפס}} \end{matrix}}+\underline{v}_{1}^t\delta A\underline{v}_{1}=\underline{v}_{1}^t\delta A\underline{v}_{1}

קיבלנו כי השגיאה בע"ע בו אנו מטפלים שווה לביטוי $\underline{v}_{1}^t\delta A\underline{v}_{1}$ . נרצה לדעת מהו גודל הסקלר הזה:

|\delta\lambda_{1}|=|\underline{v}_{1}^t\delta A\underline{v}_{1}| \underset{\begin{matrix} \downarrow \\ \R{\text{אי שוויון קושי שוורץ}} \end{matrix}}{\leq} \left\lVert \underline{v}_{1} \right\rVert \cdot \left\lVert \delta A\underline{v}_{1} \right\rVert \leq \lVvert \delta A \rVvert

כיוון שהנ"ל תקף לכל נורמה שהיא, גם הרדיוס הספקטרלי של $\delta A$ , בהיותו המינימום על פני כל הנורמות, מהווה חסם לסטייה ב- $\lambda_{1}$ ולכן:

|\delta\lambda_{1}|\leq \rho \left\{ \delta A \right\}

הערה

יצוג מספרים במחשב והערכת שגיאות

(\pm1)d_{k}d_{k-1}d_{k-2}\dots d_{1}d_{0}.d_{-1}d_{-2}d_{-3}\dots d_{-n}

פה הנקודה קבועה במקומה ולא יכולה לזוז.

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

דוגמה

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

מנטיסה עם $(\pm 1)d_{0}.d_{-1}d_{-2}\dots d_{-n}$ .
אקספוננט עם $(\pm1)e_{m}e_{m-1}\dots e_{1}e_{0}$ .

כך שנקבל:

(\pm 1)d_{0}.d_{-1}d_{-2}\dots d_{-n}\cdot 10^{(\pm1)e_{m}e_{m-1}\dots e_{1}e_{0}}

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

הגדרה 1 (שגיאה מוחלטת ויחסית)

בהינתן $x\neq 0$ וערכו המקורב $\tilde{x}$ , השגיאה המוחלטת והשגיאה היחסית של $x$ יוגדרו כך:

\Delta x=x-\tilde{x}\quad\R{\text{שגיאה מוחלטת:}}

r_{x}=\frac{\Delta x}{x} \quad \R{\text{שגיאה יחסית:}}

הערה

בדרך כלל נתייחס לערך המוחלט של שגיאות אלה.

דוגמה

אם נניח כי $d_{k}\geq 1$ אזי $|x|\geq 10^k$ ואז החסם על השגיאה היחסית יהיה:

r_{x}=\left| \frac{\Delta x}{x} \right|\leq \frac{5\cdot 10^{-(n+1)}}{10^k}=5\cdot 10^{-n-1-k}=5\cdot 10^{-t}

דוגמה

\left\lVert \tilde{\underline{x}} \right\rVert _{2}=\sqrt{ \sum_{k=1}^N \tilde{x}_{k}^2 }=\sqrt{ \sum_{k=1}^N (x_{k}+\delta x_{k})^2 } \cong \sqrt{\sum_{k=1}^N (x_{k}^2+2x_{k}\delta x_{k}) }\leq \sqrt{ \left\lVert \underline{x} \right\rVert_{2}^2+2\epsilon \sum_{k=1}^N |x_{k}| }=\sqrt{ \left\lVert \underline{x} \right\rVert_{2}^2+2\epsilon \left\lVert \underline{x} \right\rVert_{1} }

ננקה זאת באמצעות טור טיילור.

f(x+\epsilon)\cong f(x)+\epsilon \nabla f(x)\implies \sqrt{ x+\epsilon } \cong \sqrt{ x }+\frac{\epsilon}{2\sqrt{ x }}

כעת, נוכל להשתמש בטור טיילור:

\left\lVert \underline{\tilde{x}} \right\rVert _{2}\cong \left\lVert \underline{x} \right\rVert _{2}+\frac{2\epsilon \left\lVert \underline{x} \right\rVert _{1}}{2\left\lVert \underline{x} \right\rVert_{2} }

דוגמה

double S = 0;
for (int k = 1; k <= N; k++)
{
	S += x[k];
}

S_{n+1}=S_{n}+x_{n}=243.32+0.56872=243.88

הפתרון שהוצע להתמודדות עם השגיאה המצטברת הוצע ע"י $Kahan$ והוא:

double S = 0, err = 0;
for (int k = 1; k <= N; k++)
{
	Stemp = S+x[k]+err;
	err = err + x[k]+S-Stemp;
	S = Stemp;
}

שגיאות בפתרון מערכת משוואות

הערה

$\delta A$ היא מטריצה שונה ולא הכפלה של סקלר $\delta$ ב- $A$ .
כלומר, $\delta A \in \mathbb{R}^{n\times m}$ ו- $\delta$ לבדו לא קיים.

אנחנו נלך לפתור עם $\tilde{A},\underline{\tilde{b}}$ ונראה מה תהיה השגיאה ב- $\underline{x}$ .

(A+\delta A)(\underline{x}+ \underline{\delta x})=\underline{b}+ \underline{\delta b}

A\underline{x}A\underline{\delta x}+\delta A\underline{x}+\delta A\underline{\delta \underline{x}}=\underline{b}+\underline{\delta b} \implies A \underline{\delta x}+\delta A\underline{x}=\underline{\delta b}\implies \underline{\delta x}=A^{-1}(\underline{\delta b}-\delta A\underline{x})

\left\lVert \underline{\delta x} \right\rVert =\left\lVert A^{-1}(\underline{\delta b}-\delta A\underline{x}) \right\rVert \leq \lVvert A^{-1} \rVvert \cdot\left\lVert \underline{\delta b}-\delta A\underline{x} \right\rVert \leq \lVvert A^{-1} \rVvert (\left\lVert \underline{\delta b} \right\rVert+\lVvert \delta A \rVvert\cdot \left\lVert \underline{x} \right\rVert )

\frac{\left\lVert \underline{\delta x}\right\rVert }{\left\lVert \underline{x} \right\rVert }\leq \lVvert A^{-1} \rVvert \left( \frac{\left\lVert \underline{\delta b} \right\rVert}{\left\lVert \underline{x} \right\rVert }+\lVvert \delta A \rVvert \right)=\lVvert A^{-1} \rVvert \lVvert A \rVvert \left( \frac{\left\lVert \underline{\delta b} \right\rVert}{\lVvert A \rVvert\cdot \left\lVert \underline{x} \right\rVert }+\frac{\lVvert \delta A \rVvert}{\lVvert A \rVvert } \right)

נזכר כי $\left\lVert \underline{b} \right\rVert=\left\lVert A\underline{x} \right\rVert\leq \lVvert A \rVvert\cdot \left\lVert \underline{x} \right\rVert$ ולכן:

\frac{\left\lVert \underline{\delta x} \right\rVert }{\left\lVert \underline{x} \right\rVert }\leq \lVvert A^{-1} \rVvert \lVvert A \rVvert \left( \frac{\left\lVert \underline{\delta b} \right\rVert }{\left\lVert \underline{b} \right\rVert }+\frac{\lVvert \delta A \rVvert }{\lVvert A \rVvert } \right)

\lVvert A^{-1} \rVvert \lVvert A \rVvert =\frac{\sigma_{1}}{\sigma_{n}}=\kappa \left\{ A \right\}

נזכר שזה בדיוק מספר המצב של המטריצה $A$ ולכן:

\frac{\left\lVert \underline{\delta x} \right\rVert }{\left\lVert \underline{x} \right\rVert }\leq \left( \frac{\left\lVert \underline{\delta b} \right\rVert }{\left\lVert \underline{b} \right\rVert }+\frac{\lVvert \delta A \rVvert }{\lVvert A \rVvert } \right)\kappa \left\{ A \right\}

\frac{\left\lVert \underline{\delta x} \right\rVert }{\left\lVert \underline{x} \right\rVert }\leq \frac{\lVvert \delta A \rVvert }{\lVvert A \rVvert }\kappa \left\{ A \right\}

\frac{\left\lVert \underline{\delta x} \right\rVert^2 }{\left\lVert \underline{x} \right\rVert^2 } =\frac{\left\lVert \underline{\hat{x}}-\underline{x} \right\rVert^2 }{\left\lVert \underline{x} \right\rVert^2 }=\frac{\left\lVert (A+\delta A)^{-1}\underline{b}-A^{-1}\underline{b} \right\rVert^2 }{\left\lVert A^{-1}\underline{b} \right\rVert^2 }=\frac{\left\lVert ((A+\delta A)^{-1}-A^{-1})\underline{b} \right\rVert ^2}{\left\lVert A^{-1}\underline{b} \right\rVert ^2}=\frac{\underline{b}^tM_{1}\underline{b}}{\underline{b}^tM_{2}\underline{b}}

שגיאה בחישוב ע"ע וו"ע

(A+\delta A)(\underline{v}+\underline{\delta v})=(\lambda+\delta\lambda)(\underline{v}+\underline{\delta v})

A\underline{v}+A\underline{\delta v}+\delta A\underline{v}+\delta A\underline{\delta v}=\lambda \underline{v}+\lambda\underline{\delta v}+\delta\lambda \underline{v}+\delta\lambda\underline{\delta v}

A\underline{\delta v}=\delta A\underline{v}=\lambda\underline{\delta v}+\delta\lambda \underline{v}

\underline{\delta v}_{1}=\sum_{k=1}^n \alpha_{k}^1\underline{v}_{k}\implies \sum_{k=1}^n \alpha_{k}^1A\underline{v}_{k}+\delta A\underline{v}_{1}=\sum_{k=1}^n \lambda_{1}\alpha_{k}^1\underline{v}_{k}+\delta\lambda_{1}\underline{v}_{1}

נציב $A\underline{v}_{k}=\lambda_{k}\underline{v}_{k}$ ואז:

\delta\lambda_{1}\underline{v}_{1}=\sum_{k=1}^n (\lambda_{k}-\lambda_{1})\alpha_{k}^1\underline{v}_{k}+\delta A\underline{v}_{1}

נכפיל את שני האגפים ב- $\underline{v}_{1}$ :

\delta\lambda_{1}=\delta\lambda_{1}\underbracket{\underline{v}_{1}^t\underline{v}_{1}}_{1}=\underbrace{\sum_{k=1}^n (\lambda_{k}-\lambda_{1})\alpha_{k}^1\underline{v}_{1}^t\underline{v})_{k}}_{\begin{matrix} \R{\text{רק האיבר הראשון נותר בשל המכפלה}} \\ \R{\text{הפנימית וגם הוא מתאפס}} \end{matrix}}+\underline{v}_{1}^t\delta A\underline{v}_{1}=\underline{v}_{1}^t\delta A\underline{v}_{1}

קיבלנו כי השגיאה בע"ע בו אנו מטפלים שווה לביטוי $\underline{v}_{1}^t\delta A\underline{v}_{1}$ . נרצה לדעת מהו גודל הסקלר הזה:

|\delta\lambda_{1}|=|\underline{v}_{1}^t\delta A\underline{v}_{1}| \underset{\begin{matrix} \downarrow \\ \R{\text{אי שוויון קושי שוורץ}} \end{matrix}}{\leq} \left\lVert \underline{v}_{1} \right\rVert \cdot \left\lVert \delta A\underline{v}_{1} \right\rVert \leq \lVvert \delta A \rVvert

|\delta\lambda_{1}|\leq \rho \left\{ \delta A \right\}