רקע וסימונים
עריכה
תהי A {\displaystyle A} מטריצה הרמיטית:
A = [ a 1 , 1 a 1 , 2 . . . a 1 , n a 2 , 1 . . . a 2 , n : : ⋱ : a n , 1 . . . a n , n ] {\displaystyle 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 ) {\displaystyle Q_{(i,j)}} :
(1)
Q ( i , j ) = [ 1 0 . . . 0 0 1 . . . ⋱ : : : . . . cos α . . . − sin α . . . 0 : : ⋱ : . . . sin α cos α . . . : ⋱ : ⋱ 0 . . . 1 ] {\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}}}
זאת אומרת, מטריצת היחידה ששורה ועמודה i {\displaystyle i} ו j {\displaystyle j} הוחלפו במטריצת סיבוב בזווית α {\displaystyle \alpha } (מטריצה כזו ידועה גם בשם סיבובי גיבנס (אנ' ) או סיבובי יעקובי (אנ' ) )
כאשר:
cot α = β ± β 2 + 1 {\displaystyle \cot \alpha =\beta \pm {\sqrt {\beta ^{2}+1}}} ו -
β = a i i − a j j 2 a i j {\displaystyle \beta ={\frac {a_{ii}-a_{jj}}{2a_{ij}}}} או -
s = 1 cot α 2 + 1 {\displaystyle s={\frac {1}{\sqrt {\cot \alpha ^{2}+1}}}}
c = s cot α {\displaystyle c=s\cot \alpha } .
אז ההצמדה של A {\displaystyle A} ב- Q ( i , j ) {\displaystyle Q_{(i,j)}} מקיימת:
המטריצה Q ( i , j ) ∗ A Q ( i , j ) {\displaystyle Q_{(i,j)}^{*}AQ_{(i,j)}} הרמיטית.
הערכים העצמיים והווקטורים העצמיים של A {\displaystyle A} ושל Q ( i , j ) ∗ A Q ( i , j ) {\displaystyle Q_{(i,j)}^{*}AQ_{(i,j)}} זהים.
האיברים ה-( i , j ) {\displaystyle (i,j)} וה-( j , i ) {\displaystyle (j,i)} של Q ( i , j ) ∗ A Q ( i , j ) {\displaystyle Q_{(i,j)}^{*}AQ_{(i,j)}} הם 0.
A 0 = A {\displaystyle A_{0}=A}
k = 1 {\displaystyle k=1}
U {\displaystyle U} מטריצת היחידה בגודל n.
כל עוד סכום רבועי האיברים מחוץ לאלכסון גדול מהשגיאה המותרת בצע:
→ ( p , q ) {\displaystyle \rightarrow (p,q)} האינדקס של האיבר המקסימלי ב A k {\displaystyle A_{k}} .
יהיה Q ( p , q ) {\displaystyle Q_{(p,q)}} כמו ב (1)
נסמן A k = Q ( p , q ) ∗ A k − 1 Q ( p , q ) {\displaystyle A_{k}=Q_{(p,q)}^{*}A_{k-1}Q_{(p,q)}}
U ← U Q ( p , q ) {\displaystyle U\leftarrow UQ_{(p,q)}}
A k {\displaystyle A_{k}} היא מטריצה אלכסונית (עד כדי השגיאה המותרת) ו-U {\displaystyle U} מטריצה אוניטרית, כל ש-A = U ∗ A U {\displaystyle A=U^{*}AU}
הוכחת התכנסות
עריכה
נוכיח למקרה הממשי , אך הוכחה למקרה המרוכב זהה.
בשביל להוכיח התכנסות , מספיק להראות שהערך של הפונקציה :
o f f ( A k ) = ∑ i ≠ j ( a i j k ) 2 {\displaystyle \mathrm {off} (A_{k})=\sum _{i\neq j}(a_{ij}^{k})^{2}}
קטן בכל איטרציה.
נשים לב שמכך שנורמת פרובניוס (אנ' ) (שאותה נסמן ב‖ ⋅ ‖ F {\displaystyle \|\cdot \|_{F}} ) נשמרת כשמצמידים במטריצה אורתוגונלית נובע ש-
a p p k 2 + a q q k 2 = a p p k 2 + a q q k 2 + 2 a p q k 2 = a p p k − 1 2 + a q q k − 1 2 + 2 a p q k − 1 2 {\displaystyle {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}} נחסום את o f f ( A k ) {\displaystyle \mathrm {off} (A_{k})} :
o f f ( A k ) = ∑ i ≠ j ( a i j k ) 2 = ‖ A k ‖ F − ∑ i a i i k 2 = ‖ A k − 1 ‖ F − ∑ i a i i k 2 = ‖ A k − 1 ‖ F − ∑ i ≠ p , q a i i k − 1 2 + a p p k 2 + a q q k 2 = o f f ( A k − 1 ) − 2 a p q k 2 {\displaystyle \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}} הראינו שבכל איטרציה, הפונקציה o f f ( A k ) {\displaystyle \mathrm {off} (A_{k})} קטנה במספר חיובי, ולכן האיטרציות מתכנסות.
אלגוריתמים נוספים למציאת ערכים עצמיים
עריכה