לכסון אורתוגונלי

לכסון אורתוגונלי

אלגוריתם

• מצא את הע"ע של המטריצה A
• מצא בסיסים אורתונורמליים למרחבים העצמיים של המטריצה A
  • מצא בסיסים למרחבים העצמיים של המטריצה A
  • הפעל אלגוריתם גרם-שמידט על מנת להפוך כל אחד מהבסיסים האלו (בנפרד) לאורתונורמלי
• שים את כל הוקטורים מכל הבסיסים בעמודות מטריצה P, היא בהכרח תהיה אורתוגונלית.
• [math]\displaystyle{ P^*AP=D }[/math] הינה מטריצה אלכסונית

הוכחה לאלגוריתם

• ידוע שאם עמודות P הינן וקטורים עצמיים של A אזי [math]\displaystyle{ P^{-1}AP=D }[/math] אלכסונית
• ידוע שאם P אורתוגונלית אזי [math]\displaystyle{ P^t=P^{-1} }[/math]
• נובע שאם נמצא P אורתוגונלית שעמודותיה הן וקטורים עצמיים של A אזי [math]\displaystyle{ D=P^{-1}AP=P^tAP }[/math] אלכסונית.

טענה

A לכסינה אורתוגונלית אם"ם A סימטרית

הוכחה

בכיוון הראשון, נניח A לכסינה א"ג ולכן [math]\displaystyle{ A=PDP^t }[/math] ולכן [math]\displaystyle{ A^t=PD^tP^t=PDP^t=A }[/math] (כי D אלכסונית).

בכיוון השני, נניח שA סימטרית. נוכיח שוקטורים עצמיים של ערכים עצמיים שונים שלה מאונכים זה לזה. נניח u ו"ע עם ע"ע a וw ו"ע עם ע"ע b אזי [math]\displaystyle{ \lt Au,w\gt =\lt u,Aw\gt }[/math] כי A צל"ע (מעל הממשיים צל"ע=סימטרי).

לכן, [math]\displaystyle{ a\lt u,w\gt =\lt au,w\gt =\lt Au,w\gt =\lt u,Aw\gt =\lt u,bw\gt =b\lt u,w\gt }[/math] ולכן [math]\displaystyle{ a\lt u,w\gt =b\lt u,w\gt }[/math] אבל ידוע שאלו ע"ע שונים כלומר [math]\displaystyle{ a \neq b }[/math] ולכן בהכרח [math]\displaystyle{ \lt u,w\gt =0 }[/math] כלומר הם מאונכים.

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