הצגת המקור של הדף "איטרציות יעקובי למציאת ערכים עצמיים"

ב[[אנליזה נומרית]], '''[[איטרציה|איטרציות]] יעקובי למציאת [[ערך עצמי|ערכים עצמיים]]''', היא [[שיטה איטרטיבית]] הנותנת, בדיוק המבוקש, את הערכים העצמיים וה[[וקטור עצמי|וקטורים העצמיים]] של ה[[מטריצה]] <math> A </math>, כאשר <math> A </math> [[מטריצה הרמיטית|הרמיטית]] (או [[מטריצה סימטרית|סימטרית]]).
השיטה קרויה על שם ה[[מתמטיקאי]] [[קרל גוסטב יעקב יעקובי|יעקב יעקובי]].
הרעיון של השיטה הוא [[מטריצות צמודות|להצמיד]] בכל איטרציה את המטריצה ב[[מטריצה אוניטרית]] כך שסכום רבועי האיברים שמחוץ לאלכסון יקטן, ובכך [[ליכסון מטריצות|ללכסן]] את המטריצה.

==רקע וסימונים==
תהי <math> A </math> מטריצה הרמיטית:

<math>
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}
</math>

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

(1)
<math>
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}
</math>

זאת אומרת, מטריצת היחידה ששורה ועמודה <math> i </math> ו <math> j </math> הוחלפו ב[[מטריצת סיבוב]] ב[[זווית]] <math> \alpha </math> (מטריצה כזו ידועה גם בשם [[סיבובי גיבנס]] {{אנ|givens rotation}}  או [[סיבובי יעקובי]] {{אנ|jacobi rotations}} )

כאשר: 
 
: <math> \cot \alpha = \beta \pm \sqrt{\beta^2+1} </math> 

ו - 

: <math> \beta = \frac{a_{ii} - a_{jj}}{2 a_{ij}} </math> 

או -

: <math> s = \frac{1}{\sqrt{\cot \alpha^2+1}}  </math>
: <math> c = s \cot \alpha </math>.


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

==האלגוריתם==

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

== הוכחת התכנסות ==
נוכיח למקרה [[מספר ממשי|הממשי]], אך הוכחה למקרה [[מספר ממשי|המרוכב]] זהה.

בשביל להוכיח [[התכנסות (מתמטיקה)|התכנסות]], מספיק להראות שהערך של ה[[פונקציה]]:
<math> \mathrm{off}(A_k)=\sum_{i \neq j} (a^k_{ij})^2 </math>
קטן בכל איטרציה.
נשים לב שמכך ש[[נורמת פרובניוס]] {{אנ|Matrix_norm#Frobenius_norm}} (שאותה נסמן ב<math> \| \cdot \|_F</math>) נשמרת כשמצמידים ב[[מטריצה אורתוגונלית]] נובע ש-

: <math> {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  </math>

נחסום את <math> \mathrm{off}(A_k) </math>:

: <math> \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 </math>

הראינו שבכל איטרציה, הפונקציה <math> \mathrm{off}(A_k)</math> קטנה במספר חיובי, ולכן האיטרציות מתכנסות.

==אלגוריתמים נוספים למציאת ערכים עצמיים==
* [[שיטת החזקה]] {{אנ|power method}} ו[[שיטת החזקה ההפוכה]] {{אנ|Inverse iteration}}
* [[אלגוריתם QR]] {{אנ|QR algorithm}} המבוסס על [[פירוק QR]]



[[קטגוריה:אנליזה נומרית]]