אלגוריתם ללכסון מטריצה: הבדלים בין גרסאות בדף

גרסה אחרונה מ־09:32, 21 באוקטובר 2012

תהי נתונה מטריצה [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].

@@ שורה 1: / שורה 1: @@
-תהי מטריצה A. נרצה לדעת האם היא לכסינה ומהי המטריצה המלכסנת שלה
+תהי נתונה מטריצה <math>A</math>. נרצה לבדוק האם היא לכסינה, ואם כן - למצוא מטריצה שמלכסנת אותה.
 ===מציאת פולינום אופייני===
 <math>p_A(x):=\left|xI-A\right|</math>.
-===מציאות ערכים עצמיים של המטריצה===
+===מציאת הערכים העצמיים של המטריצה וריבויים האלגברי===
-x הינו ע"ע של A אם ורק אם x הינו שורש של הפולינום האופייני של A
+<math>\lambda</math> ערך עצמי של <math>A</math> אם ורק אם <math>p_A(\lambda)=0</math>.
-===מציאת מרחבים עצמיים של הערכים העצמיים===
+לכל שורש <math>\lambda</math> של <math>p_A(x)</math>, נוציא מהפולינום גורם <math>(x-\lambda)</math>,
+עד שנגיע למצב
+<math>p_A(x)=(x-\lambda_1)^{r_1}\cdots(x-\lambda_k)^{r_k}</math>.
-המרחב העצמי של ע"ע x מוגדר להיות:
+'''אם נותר בפולינום גורם שאינו מתפרק לגורמים לינאריים כאלה, אז המטריצה אינה לכסינה''' ואפשר לעצור כאן.
-::<math>V_x:=\{v|Av=xv\}</math>
+<math>\lambda_1,\dots,\lambda_k</math> הם הערכים העצמיים השונים של <math>A</math>,
+ו
+<math>r_1,\dots,r_k</math>
+הם הריבויים האלגבריים שלהם, בהתאמה.
-קל להוכיח כי <math>V_x=N(A-xI)</math>. במילים, המרחב העצמי של ע"ע הוא אוסף הפתרונות של המערכת ההומוגנית המתאימה למטריצה A-xI.
+===מציאת בסיסים למרחבים העצמיים===
+לכל ערך עצמי <math>\lambda</math> של <math>A</math>, מחשבים את המרחב העצמי
+<math>V_\lambda:=\left\{v\in \mathbb{F}^n : Av=\lambda v\right\}=N(A-\lambda I)</math>,
+אוסף הפתרונות של המערכת ההומוגנית המתאימה למטריצה <math>A-\lambda I</math>.
-*מומלץ להיזכר ב[[88-112 לינארית 1 תיכוניסטים קיץ תשעא/מערך תרגול/7|מציאת בסיס למרחב האפס]]
+מוצאים בסיס עבור מרחב זה. אם בבסיס יש פחות איברים מהריבוי האלגברי של <math>\lambda</math>,
+אז '''המטריצה אינה לכסינה''' ולא צריך להמשיך.
-===מציאת בסיסים למרחבים העצמיים===
+כל עוד יש מספיק וקטורים כמו בריבוי האלגברי, ממשיכים הלאה לערכים העצמיים הבאים.
-ידוע מלינארית 1 כי בסיס למרחב האפס מורכב מהפתרונות הפונדומנטליים של המערכת ההומוגנית
+*תזכורת למעוניינים: [[88-112 לינארית 1 תיכוניסטים קיץ תשעא/מערך תרגול/7|מציאת בסיס למרחב האפס]]
 ===בדיקה האם המטריצה לכסינה, ואם כן מציאת המטריצה המלכסנת===
-אם סכום מימדי המרחבים העצמיים שווה למימד המרחב כולו (ניתן לגלות לפי מספר האיברים בבסיסים), אזי המטריצה לכסינה והמטריצה המלכסנת P היא המטריצה שעמודותיה הם הוקטורים מהבסיסים הנ"ל.
+אם הגענו עד שלב זה, מובטח שהמטריצה לכסינה, והמטריצה המלכסנת <math>P</math> היא המטריצה שעמודותיה הם הוקטורים העצמיים בבסיסים שמצאנו.
+כלומר, המטריצה <math>D:=P^{-1}AP</math> היא מטריצה אלכסונית.
+בעמודה <math>i</math> של המטריצה <math>D</math> יופיע הערך העצמי המתאים לוקטור העצמי ששמנו בעמודה <math>i</math> של <math>P</math>.
-אחרת, המטריצה אינה לכסינה
+==דוגמאות==