אלגוריתם ללכסון מטריצה

תהי נתונה מטריצה [math]\displaystyle{ A }[/math]. נרצה לבדוק האם היא לכסינה, ואם כן - למצוא מטריצה שמלכסנת אותה.

מציאת פולינום אופייני

[math]\displaystyle{ p_A(x):=\left|xI-A\right| }[/math].

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

[math]\displaystyle{ \lambda }[/math] ערך עצמי של [math]\displaystyle{ A }[/math] אם ורק אם [math]\displaystyle{ p_A(\lambda)=0 }[/math].

לכל שורש [math]\displaystyle{ \lambda }[/math] של [math]\displaystyle{ p_A(x) }[/math], נוציא מהפולינום גורם [math]\displaystyle{ (x-\lambda) }[/math], עד שנגיע למצב [math]\displaystyle{ p_A(x)=(x-\lambda_1)^{r_1}\cdots(x-\lambda_k)^{r_k} }[/math].

אם נותר בפולינום גורם שאינו מתפרק לגורמים לינאריים כאלה, אז המטריצה אינה לכסינה ואפשר לעצור כאן.

[math]\displaystyle{ \lambda_1,\dots,\lambda_k }[/math] הם הערכים העצמיים השונים של [math]\displaystyle{ A }[/math], ו [math]\displaystyle{ r_1,\dots,r_k }[/math] הם הריבויים האלגבריים שלהם, בהתאמה.

מציאת בסיסים למרחבים העצמיים

לכל ערך עצמי [math]\displaystyle{ \lambda }[/math] של [math]\displaystyle{ A }[/math], מחשבים את המרחב העצמי [math]\displaystyle{ V_\lambda:=\left\{v\in \mathbb{F}^n : Av=\lambda v\right\}=N(A-\lambda I) }[/math], אוסף הפתרונות של המערכת ההומוגנית המתאימה למטריצה [math]\displaystyle{ A-\lambda I }[/math].

מוצאים בסיס עבור מרחב זה. אם בבסיס יש פחות איברים מהריבוי האלגברי של [math]\displaystyle{ \lambda }[/math], אז המטריצה אינה לכסינה ולא צריך להמשיך.

כל עוד יש מספיק וקטורים כמו בריבוי האלגברי, ממשיכים הלאה לערכים העצמיים הבאים.

• תזכורת למעוניינים: מציאת בסיס למרחב האפס

בדיקה האם המטריצה לכסינה, ואם כן מציאת המטריצה המלכסנת

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

בעמודה [math]\displaystyle{ i }[/math] של המטריצה [math]\displaystyle{ D }[/math] יופיע הערך העצמי המתאים לוקטור העצמי ששמנו בעמודה [math]\displaystyle{ i }[/math] של [math]\displaystyle{ P }[/math].