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

באנליזה נומרית, איטרציות יעקובי למציאת ערכים עצמיים, היא שיטה איטרטיבית הנותנת, בדיוק המבוקש, את הערכים העצמיים והווקטורים העצמיים של המטריצה $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) $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}}$

זאת אומרת, מטריצת היחידה ששורה ועמודה $i$ ו $j$ הוחלפו במטריצת סיבוב בזווית $\alpha$ (מטריצה כזו ידועה גם בשם סיבובי גיבנס או סיבובי יעקובי )

כאשר:

$\cot \alpha =\beta \pm {\sqrt {\beta ^{2}+1}}$

ו -

$\beta ={\frac {a_{ii}-a_{jj}}{2a_{ij}}}$

או -

$s={\frac {1}{\sqrt {\cot \alpha ^{2}+1}}}$

$c=s\cot \alpha$.

אז ההצמדה של $A$ ב- $Q_{(i,j)}$ מקיימת:

• המטריצה $Q_{(i,j)}^{*}AQ_{(i,j)}$ הרמיטית.
• הערכים העצמיים והווקטורים העצמיים של $A$ ושל $Q_{(i,j)}^{*}AQ_{(i,j)}$ זהים.
• האיברים ה-$(i,j)$ וה-$(j,i)$ של $Q_{(i,j)}^{*}AQ_{(i,j)}$ הם 0.

האלגוריתם

   $A_{0}=A$ 
   $k=1$ 
   $U$ מטריצת היחידה בגודל n.
   כל עוד סכום רבועי האיברים מחוץ לאלכסון גדול מהשגיאה המותרת בצע:
          $\rightarrow (p,q)$   האינדקס של האיבר המקסימלי ב $A_{k}$.
          יהיה $Q_{(p,q)}$ כמו ב (1)
          נסמן $A_{k}=Q_{(p,q)}^{*}A_{k-1}Q_{(p,q)}$ 
          $U\leftarrow UQ_{(p,q)}$
   $A_{k}$ היא מטריצה אלכסונית (עד כדי השגיאה המותרת) ו-$U$ מטריצה אוניטרית, כל ש-$A=U^{*}AU$

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

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

בשביל להוכיח התכנסות, מספיק להראות שהערך של הפונקציה: $\mathrm {off} (A_{k})=\sum _{i\neq j}(a_{ij}^{k})^{2}$ קטן בכל איטרציה. נשים לב שמכך שנורמת פרובניוס (שאותה נסמן ב$\|\cdot \|_{F}$) נשמרת כשמצמידים במטריצה אורתוגונלית נובע ש-

${a_{pp}^{k}}^{2}+{a_{qq}^{k}}^{2}={a_{pp}^{k}}^{2}+{a_{qq}^{k}}^{2}+2{a_{pq}^{k}}^{2}={a_{pp}^{k-1}}^{2}+{a_{qq}^{k-1}}^{2}+2{a_{pq}^{k-1}}^{2}$

נחסום את $\mathrm {off} (A_{k})$:

$\mathrm {off} (A_{k})=\sum _{i\neq j}(a_{ij}^{k})^{2}=\|A_{k}\|_{F}-\sum _{i}{a_{ii}^{k}}^{2}=\|A_{k-1}\|_{F}-\sum _{i}{a_{ii}^{k}}^{2}=\|A_{k-1}\|_{F}-\sum _{i\neq p,q}{a_{ii}^{k-1}}^{2}+{a_{pp}^{k}}^{2}+{a_{qq}^{k}}^{2}=\mathrm {off} (A_{k-1})-2{a_{pq}^{k}}^{2}$

הראינו שבכל איטרציה, הפונקציה $\mathrm {off} (A_{k})$ קטנה במספר חיובי, ולכן האיטרציות מתכנסות.

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

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