איטרציות יעקובי למציאת ערכים עצמיים

באנליזה נומרית, איטרציות יעקובי למציאת ערכים עצמיים, היא שיטה איטרטיבית הנותנת, בדיוק המבוקש, את הערכים העצמיים והוקטורים העצמיים של המטריצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A } , כאשר $A$ הרמיטית (או סימטרית). השיטה קרויה על שם המתמטיקאי יעקב יעקבי. הרעיון של השיטה הוא להצמיד בכל איטרציה את המטריצה במטריצה אוניטרית כך שסכום רבועי האיברים שמחוץ לאלכסון יקטן, ובכך ללכסן את המטריצה.

רקע וסימונים

תהי $A$ מטריצה הרמיטית:

$A={\begin{bmatrix}a_{1,1}&a_{1,2}&...&a_{1,n}\\a_{2,1}&&...&a_{2,n}\\:&:&\ddots &:\\a_{n,1}&&...&a_{n,n}\\\end{bmatrix}}$

נסמן את המטריצה $Q_{(i,j)}$ :

(1) הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q_{(i,j)} = \begin{bmatrix} 1 & 0 & & & ... & & & 0 \\ 0 & 1 & & & ... & & & \\ & & \ddots & & : & & & \\ : & : & ... & \cos \alpha & ... & -\sin \alpha & ... & 0 \\ : & : & & &\ddots & & & : \\ & & ... & \sin \alpha & & \cos \alpha & ... & : \\ & & \ddots & & : & & \ddots & \\ 0 & & & & ... & & & 1\\ \end{bmatrix} }

זאת אומרת, מטריצת היחידה ששורה ועמודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i } ו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j } הוחלפו במטריצת סיבוב בזווית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha } (מטריצה כזו ידועה גם בשם סיבובי גיבנס או סיבובי יעקובי )

כאשר:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cot \alpha = \beta \pm \sqrt{\beta^2+1} }

ו -

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta = \frac{a_{ii} - a_{jj}}{2 a_{ij}} }

או -

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s = \frac{1}{\sqrt{\cot \alpha^2+1}} }

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c = s \cot \alpha } .

אז ההצמדה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A } ב- $Q_{(i,j)}$ מקיימת:

• המטריצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q_{(i,j)}^*AQ_{(i,j)} } הרמיטית.
• הערכים העצמיים והווקטורים העצמיים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A } ושל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q_{(i,j)}^*AQ_{(i,j)} } זהים.
• האיברים ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (i,j) } וה-$(j,i)$ של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q_{(i,j)}^*AQ_{(i,j)} } הם 0.

האלגוריתם

   הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle  A_0 = A }
 
   הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle  k=1 }
 
   הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle  U }
 מטריצת היחידה בגודל n.
   כל עוד סכום רבועי האיברים מחוץ לאלכסון גדול מהשגיאה המותרת בצע:
          $\rightarrow (p,q)$   האינדקס של האיבר המקסימלי ב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle  A_k }
.
          יהיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle  Q_{(p,q)} }
 כמו ב (1)
          נסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle  A_k = Q_{(p,q)}^* A_{k-1} Q_{(p,q)}  }
 
          הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle U\leftarrow UQ_{(p,q)}}

   הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle  A_k }
 היא מטריצה אלכסונית (עד כדי השגיאה המותרת) ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle  U }
 מטריצה אוניטרית, כל ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle  A = U^*AU }

הוכחת התכנסות

נוכיח למקרה הממשי, אך הוכחה למקרה המרוכב זהה.

בשביל להוכיח התכנסות, מספיק להראות שהערך של הפונקציה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{off}(A_k)=\sum_{i \neq j} (a^k_{ij})^2 } קטן בכל איטרציה. נשים לב שמכך שנורמת פרובניוס (שאותה נסמן ב$\|\cdot \|_{F}$) נשמרת כשמצמידים במטריצה אורתוגונלית נובע ש-

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle {a^k_{pp}}^2 +{a^k_{qq}}^2 = {a^k_{pp}}^2 +{a^k_{qq}}^2+ 2{a^k_{pq}}^2 = {a^{k-1}_{pp}}^2 +{a^{k-1}_{qq}}^2 + 2{a^{k-1}_{pq}}^2 }

נחסום את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{off}(A_k) } :

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{off}(A_k)=\sum_{i \neq j} (a^k_{ij})^2 = \|A_k\|_F - \sum_i {a^k_{ii}}^2 = \|A_{k-1}\|_F - \sum_i {a^k_{ii}}^2 = \|A_{k-1}\|_F - \sum_{i \neq p,q} {a^{k-1}_{ii}}^2 + {a^k_{pp}}^2 + {a^k_{qq}}^2 = \mathrm{off}(A_{k-1}) - 2{a^k_{pq}}^2 }

הראינו שבכל איטרציה, הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{off}(A_k)} קטנה במספר חיובי, ולכן האיטרציות מתכנסות.

אלגוריתמים נוספים למציאת ערכים עצמיים

• שיטת החזקה ושיטת החזקה ההפוכה
• אלגוריתם QR המבוסס על פירוק QR

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

23332262איטרציות יעקובי למציאת ערכים עצמיים