משפט רושה-קפלי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

המשפט נקרא משפט רושה-קפלי באיטליה, משפט קרונקר-קפלי ברוסיה, משפט רושה-פונטן בצרפת ומשפט רושה-פרובניוס בספרד.

נוסח פורמלי[עריכת קוד מקור | עריכה]

נתונה מערכת משוואות לינאריות מהצורה הכללית הבאה:

\begin{alignat}{7}
a_{11} x_1 &&\; + \;&& a_{12} x_2   &&\; + \cdots + \;&& a_{1n} x_n &&\; = \;&&& b_1 \\
a_{21} x_1 &&\; + \;&& a_{22} x_2   &&\; + \cdots + \;&& a_{2n} x_n &&\; = \;&&& b_2 \\
\vdots\;\;\; &&     && \vdots\;\;\; &&                && \vdots\;\;\; &&     &&& \;\vdots \\
a_{m1} x_1 &&\; + \;&& a_{m2} x_2   &&\; + \cdots + \;&& a_{mn} x_n &&\; = \;&&& b_m \\
\end{alignat}


נסמן ב-[A] מטריצת המקדמים הסקלריים, ב-\bold{x} את וקטור המשתנים וב-\bold{b} את וקטור המקדמים החופשיים:


[A]=
\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{bmatrix},\quad

\bold{x}=
\begin{bmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n
\end{bmatrix},\quad

\bold{b}=
\begin{bmatrix}
b_1 \\
b_2 \\
\vdots \\
b_m
\end{bmatrix}


המשפט קובע כי למערכת המשוואות A\bold{x}=\bold{b} קיים פתרון, אם ורק אם הדרגה של המטריצה [A], שווה לדרגה של המטריצה [A|\bold{b}], המתקבלת מהוספת \bold{b} כעמודה ב-[A]. כלומר, rank[A]=rank[A|\bold{b}].

כמו כן, כאשר יש פתרונות הם מהווים מרחב אפיני מממד n-rank[A] (הזזה של מרחב וקטורי מאותו ממד). בפרט כאשר n=rank[A] המרחב הוא אפס ממדי ויש פתרון אחד בלבד. אחרת, יש אינסוף פתרונות.

הוכחה[עריכת קוד מקור | עריכה]

חלק ראשון[עריכת קוד מקור | עריכה]

הוכחה כי למערכת המשוואות קיים פתרון אם ורק אם הדרגה של [A] שווה לדרגה של [A|\bold{b}].

כיוון אחד של השקילות

נניח כי למערכת A\bold{x}=\bold{b} יש פתרון \bold{c}. כלומר, מתקיים כי A\bold{c}=\bold{b}.

נבטא זאת באופן מפורש:

\begin{bmatrix}a_{11}\\a_{21}\\ \vdots \\a_{m1}\end{bmatrix}c_1  + \begin{bmatrix}a_{12}\\a_{22}\\ \vdots \\a_{m2}\end{bmatrix}c_2 + \ldots +\begin{bmatrix}a_{1n}\\a_{2n}\\ \vdots \\a_{mn}\end{bmatrix}c_n =
 \begin{bmatrix}b_1\\b_2\\ \vdots \\b_m\end{bmatrix}

מכאן ש-\bold{b} הוא צירוף לינארי של העמודות של [A]. כלומר הוא שייך למרחב שנפרש על ידי וקטורי העמודות, ולכן ממד מרחב העמודות (הוא הדרגה של [A]) נשמר כנדרש.

כיוון שני של השקילות

נניח כי הדרגה אחרי הוספת \bold{b} זהה. כלומר \dim \mathrm{Span}(\bold{a_{1}}, \bold{a_{2}}, \ldots , \bold{a_{n}})=\dim \mathrm{Span}(\bold{a_{1}}, \bold{a_{2}}, \ldots , \bold{a_{n}}, \bold{b}), כאשר \bold{a_1},\bold{a_{2}},\ldots,\bold{a_n} הם העמודות של [A].

\mathrm{Span}(\bold{a_{1}}, \bold{a_{2}}, \ldots , \bold{a_{n}}) הוא תת-מרחב וקטורי של  \mathrm{Span}(\bold{a_{1}}, \bold{a_{2}}, \ldots, \bold{a_{n}}, \bold{b}), ומכיוון שממדיהם שווים הם בהכרח שווים.‏[1]

הוכחנו ש- \mathrm{Span}(\bold{a_{1}}, \bold{a_{2}}, \ldots , \bold{a_{n}}, \bold{b})=\mathrm{Span}(\bold{a_{1}}, \bold{a_{2}}, \ldots , \bold{a_{n}}), ולכן \bold{b} הוא צירוף לינארי של הווקטורים \bold{a_1},\bold{a_{2}},\ldots,\bold{a_n}. מקדמי הצירוף 
{(c_1, c_2, ..., c_n)} מהווים פתרון למערכת המשוואות A\bold{x}=\bold{b}.

חלק שני[עריכת קוד מקור | עריכה]

הוכחה כי קיים למערכת המשוואות פתרון יחיד אם ורק אם n=rank[A].

כיוון ראשון של השקילות

נניח כי עבור המערכת A\bold{x}=\bold{b} קיים פתרון יחיד, ונניח בשלילה כי rank[A]<n.‏[2]

מההנחה כי rank[A]<n נובע שעבור המערכת A\bold{x}=\bold{0} קיימים לפחות שני פתרונות. זה עומד בסתירה להנחה שלמערכת A\bold{x}=\bold{b} יש פתרון יחיד, כי אם \bold{x} פתרון שלה, הרי שגם אם נוסיף לו כל אחד משני הפתרונות של המערכת שערכה \bold{0} נקבל את אותה תוצאה.

כיוון שני של השקילות

נניח כי rank[A]=n, ונניח בשלילה שלמערכת A\bold{x}=\bold{b} קיימים שני פתרונות שונים.

מהנתון rank[A]=n נובע כי למערכת A\bold{x}=\bold{0} יש פתרון יחיד - הפתרון הטריוויאלי \bold{0}. אם נבחן את ההפרש של שני הפתרונות של A\bold{x}=\bold{b} נקבל גם כן \bold{0}, ולכן בהכרח שני הפתרונות שווים.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ קבוצת וקטורי הבסיס של התת-מרחב היא בלתי תלויה ומספר הווקטורים בה שווה לממד המרחב, ולכן היא פורשת גם את המרחב כולו.
  2. ^ לא ייתכן כי rank[A]>n, כי קיימים רק n איברים בקבוצה הנפרשת \mathrm{Span}(a_{1}, a_{2}, ... , a_{n}).