חזור לתיקייה: תרגול

1 - חזרה על אלגברה ליניארית

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • מרחבים ווקטוריים
  • איחוד וחיתוך מרחבים
  • דוגמות למרחבים ווקטורים
  • בסיס ומימד
  • מרחב מכפלה פנימית
  • נורמה
  • נורמה מושרית
  • מרחב מטרי

1 - חזרה על אלגברה ליניארית

02340125

אלגוריתמים נומריים

רשימות תרגול לקריאה בשבת

חזרה על אלגברה ליניארית

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

מרחבים ווקטוריים

הגדרה 1

קבוצה VVV נקראת מרחב וקטורי מעל שדה F\mathbb{F}F אם מוגדרות שתי פעולות - חיבור (+)(+)(+) וכפל (⋅)(\cdot)(⋅) בין איבר ב-VVV לאיבר ב-FFF, כך ש-VVV חבורה קומוטטיבית עם חיבור וכפל בסקלר.

הגדרה 2

עבור מרחב וקטורי VVV ועבור קבוצה של kkk וקטורים בו ו-kkk סקלרים בשדה F\mathbb{F}F, כל ביטוי מהצורה:

α1v‾1+α2v‾2+⋯+αkv‾k\alpha_{1}\underline{v}_{1}+\alpha_{2}\underline{v}_{2}+\dots+\alpha_{k}\underline{v}_{k}α1​v​1​+α2​v​2​+⋯+αk​v​k​

נקרא צירוף ליניארי והוא וקטור השייך למרחב VVV.

הגדרה 3

אוסף כל הצירופים הליניאריים α1v‾1+α2v‾2+⋯+αkv‾k\alpha_{1}\underline{v}_{1}+\alpha_{2}\underline{v}_{2}+\dots+\alpha_{k}\underline{v}_{k}α1​v​1​+α2​v​2​+⋯+αk​v​k​ נקרא המרחב הנפרש ע"י קבוצת הוקטורים הנ"ל אשר תקרא הקבוצה הפורשת. הקבוצה המתקבלת הינה תת מרחב של VVV וסימונה:

span{v‾1,v‾2,…,v‾k}span\left\{ \underline{v}_{1},\underline{v}_{2},\dots,\underline{v}_{k} \right\}span{v​1​,v​2​,…,v​k​}
משפט

פרישה ליניארית היא תת המרחב הקטן ביותר אשר יכול להכיל את כל הוקטורים הנ"ל(אם הם בת"ל).

איחוד וחיתוך מרחבים

הגדרה 4

בהינתן שני תתי-מרחבים של VVV שיקראו WWW ו-UUU, חיתוכם הוא בהכרח תת מרחב של W,U,VW,U,VW,U,V.

U∩W={z‾∣z‾∈U∧z‾∈W}U \cap W=\left\{ \underline{z} | \underline{z} \in U \land \underline{z} \in W \right\}U∩W={z​∣z​∈U∧z​∈W}
הגדרה 5

בהינתן שני תתי מרחבים של VVV שיקראו W,UW,UW,U נגדיר את סכומם כ:

U+W={u‾+w‾∣u‾∈U∧w‾∈W}U+W=\left\{ \underline{u}+\underline{w}|\underline{u}\in U \land \underline{w} \in W \right\}U+W={u​+w​∣u​∈U∧w​∈W}

חיבור זה הוא תת מרחב המקיים U,W⊆U+W⊆VU,W \subseteq U+W \subseteq VU,W⊆U+W⊆V.

דוגמות למרחבים ווקטורים

דוגמה

המרחב הכי מוכר הוא Rn\mathbb{R}^nRn הוא נבנה מכל הקורדינטות הנכתבות כאוסף של nnn סקלרים ממשיים בסידור כלשהו, x‾=(x1x2x3…xn)\underline{x}=\begin{pmatrix}x_{1} & x_{2} & x_{3} & \dots & x_{n}\end{pmatrix}x​=(x1​​x2​​x3​​…​xn​​) עם הגדרה פשוטה של חיבור וכפל בסקלר.

מה יהיו תתי מרחבים של המרחב Rn\mathbb{R}^nRn?

  • אם נתעניין בתת-קבוצה של כל הקודינטות המקיימות את התכונה x1+2x2−4x3+⋯−3xn=0x_{1}+2x_{2}-4x_{3}+\dots-3x_{n}=0x1​+2x2​−4x3​+⋯−3xn​=0 אזי יתקבל תת-מרחב של Rn\mathbb{R}^nRn.
  • אם הדרישה היא x1+2x2−4x3+⋯−3xn=1x_{1}+2x_{2}-4x_{3}+\dots-3x_{n}=1x1​+2x2​−4x3​+⋯−3xn​=1 אינו תת מרחב שכן וקטור האפס לא נמצא שם.
דוגמה

אם נסתכל על כל הפולינומיים האפשריים מדרגה nnn עם מקדמים ממשיים, p(x)=a0+a1x+a2x2+⋯+anxnp(x)=a_{0}+a_{1}x+a_{2}x^2+\dots+a_{n}x^np(x)=a0​+a1​x+a2​x2+⋯+an​xn אזי אוסף זה מגדיר מרחב וקטורי כאשר חיבור וכפל מוגדרים כמו שחושבים.

דוגמה

מעל תחום הגדרה משותף SSS, נגדיר את אוסף כל הפונקציות f:S→Rf:S\to \mathbb{R}f:S→R. אוסף זה יוצר מרחב, ובו חיבור וכפל מתקבלים ע"י:

∀x∈S:  (f+g)(x)=f(x)+g(x)∀x∈S:  (αf)(x)=αf(x)\begin{matrix} \forall x \in S:\; (f+g)(x)=f(x)+g(x) \\ \forall x \in S:\; (\alpha f)(x)=\alpha f(x) \end{matrix}∀x∈S:(f+g)(x)=f(x)+g(x)∀x∈S:(αf)(x)=αf(x)​

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

∀x∈S:  f(x)+3f′′(x)−3f′(x)=0\forall x \in S:\; f(x)+3f''(x)-3f'(x)=0∀x∈S:f(x)+3f′′(x)−3f′(x)=0

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

דוגמה

מרחב הפתרונות של משוואה הומוגנית:

(1131−3−12410037−3−1−600002214)(x1x2x3x4x5x6)=(0000)\begin{pmatrix} 1 & 1 & 3 & 1 & -3 & -1 \\ 2 & 4 & 1 & 0 & 0 & 3 \\ 7 & -3 & -1 & -6 & 0 & 0 \\ 0 & 0 & 2 & 2 & 1 & 4 \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \\ x_{6} \end{pmatrix}=\begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}​1270​14−30​31−12​10−62​−3001​−1304​​​x1​x2​x3​x4​x5​x6​​​=​0000​​

בסיס ומימד

הגדרה 6

עבור מרחב וקטורי VVV, קבוצת הוקטורים B={v‾1,v‾2,…,v‾k}∈VB=\left\{ \underline{v}_{1},\underline{v}_{2},\dots,\underline{v}_{k} \right\}\in VB={v​1​,v​2​,…,v​k​}∈V תקרא תלויה ליניארית אם קיימים α1,…,αk∈F\alpha_{1},\dots,\alpha_{k}\in \mathbb{F}α1​,…,αk​∈F כך שלא כולם אפסים כך ש:

α1v‾1+α2v‾2+⋯+αkv‾k=0‾\alpha_{1}\underline{v}_{1}+\alpha_{2}\underline{v}_{2}+\dots+\alpha_{k}\underline{v}_{k}=\underline{0}α1​v​1​+α2​v​2​+⋯+αk​v​k​=0​
הגדרה 7

יהי VVV המ"ו הנפרש מקבוצת וקטורים בת"ל. אזי קבוצה זו תקרא בסיס למרחב VVV ומספר האיברים בקבוצה הוא המימד של מרחב זה וסימונו dim⁡V\dim VdimV.

משפט (כמה משפטים)

  • לכל בסיס של מרחב וקטורי VVV יש את אותו מספר איברים
  • בכל קבוצה פורשת של VVV יש לפחות dim⁡V\dim VdimV איברים.
  • בסיס הוא קבוצה פורשת מינימלית וקבוצה בת"ל מקסימלית ב-VVV.
  • אם המימד של VVV הוא nnn, אז כל קבוצה של n+1n+1n+1 איברים היא ת"ל ב-VVV.
  • יהא BBB בסיס למ"ו VVV, אזי כל איבר ב-VVV ניתן לכתיבה כצירוף ליניארי של איברי BBB.
  • עבור מרחב וקטורי VVV ושני תתי מרחבים שלו - U,WU,WU,W מתקיים:
dim⁡(U+W)=dim⁡U+dim⁡W−dim⁡(U∩W) \dim(U+W)=\dim U+\dim W-\dim(U \cap W)dim(U+W)=dimU+dimW−dim(U∩W)

מרחב מכפלה פנימית

הגדרה 8 (מכפלה פנימית)

למרחב וקטורי VVV מעל שדה F\mathbb{F}F נגדיר פונקציה ⟨⋅,⋅⟩:V×V→F\langle \cdot,\cdot \rangle:V\times V\to \mathbb{F}⟨⋅,⋅⟩:V×V→F אשר תקרא מכפלה פנימית, אם היא מקיימת את התכונות הבאות.

  1. ליניאריות: ∀v‾,u‾,w‾∈V,∀α,β∈F:  ⟨αv‾+βu‾,w‾⟩=α⟨v‾,w‾⟩+β⟨u‾,w‾⟩\forall \underline{v},\underline{u},\underline{w}\in V,\forall\alpha,\beta \in \mathbb{F}:\; \langle\alpha \underline{v}+\beta \underline{u},\underline{w}\rangle=\alpha \langle\underline{v},\underline{w}\rangle+\beta \langle\underline{u},\underline{w}\rangle∀v​,u​,w​∈V,∀α,β∈F:⟨αv​+βu​,w​⟩=α⟨v​,w​⟩+β⟨u​,w​⟩
  2. סימטריות (הרמטיות): ∀v‾,u‾∈V:  ⟨v‾,u‾⟩=⟨u‾,v‾⟩‾\forall \underline{v},\underline{u}\in V:\; \langle\underline{v},\underline{u}\rangle=\overline{\langle\underline{u},\underline{v}\rangle}∀v​,u​∈V:⟨v​,u​⟩=⟨u​,v​⟩​ כלומר צמוד מרוכב.
  3. חיוביות לחלוטין: ∀v‾∈V:  ⟨v‾,v‾⟩≥0\forall \underline{v}\in V:\; \langle\underline{v},\underline{v}\rangle\geq0∀v​∈V:⟨v​,v​⟩≥0 ושוויון ל-0 מתקבל רק עבור v‾=0‾\underline{v}=\underline{0}v​=0​.

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

הגדרה 9 (ניצבות)

שני וקטורים במרחב מכפלה פנימית, v‾,u‾∈V\underline{v},\underline{u}\in Vv​,u​∈V ייחשבו כניצבים אם מתקיים כי ⟨v‾,u‾⟩=0\langle\underline{v},\underline{u}\rangle=0⟨v​,u​⟩=0. מקרה זה יסומן כ:

v‾⊥u‾\underline{v} \perp \underline{u}v​⊥u​

דוגמה

למרחב האוקלידי ה-nnn מימדי מעל שדה הממשיים, מכפלה פנימית נפוצה בשימוש היא ההבאה:

x‾=(x1x2x3…xn)y‾=(y1y2y3…yn)  ⟹  ⟨x‾,y‾⟩=∑k=1nxkyk\begin{matrix} \underline{x}=\begin{pmatrix} x_{1} & x_{2} & x_{3} & \dots & x_{n} \end{pmatrix} \\ \underline{y}=\begin{pmatrix} y_{1} & y_{2} & y_{3} & \dots & y_{n} \end{pmatrix} \end{matrix}\implies \langle\underline{x},\underline{y}\rangle=\sum_{k=1}^nx_{k}y_{k}x​=(x1​​x2​​x3​​…​xn​​)y​=(y1​​y2​​y3​​…​yn​​)​⟹⟨x​,y​⟩=k=1∑n​xk​yk​

כשעוסקים במספרים מרוכבים ההגדרה הזו משתנית בהרכח ל:

⟨x‾,y‾⟩=∑k=1nxkyk‾\langle\underline{x},\underline{y}\rangle=\sum_{k=1}^nx_{k}\overline{y_{k}}⟨x​,y​⟩=k=1∑n​xk​yk​​

נורמה

הגדרה 10 (נורמה)

למרחב וקטורי נורמי VVV מעל שדה F\mathbb{F}F, נגדיר פונקציה ∣∣⋅∣∣:V→R||\cdot||:V\to \mathbb{R}∣∣⋅∣∣:V→R אשר תקרא נורמה, אם היא מקיימת את התכונות הבאות:

  1. חיובית לחלוטין: ∀v‾∈V:∣∣v‾∣∣≥0\forall \underline{v}\in V:||\underline{v}||\geq 0∀v​∈V:∣∣v​∣∣≥0 ושוויון ל-000 מתקבל רק עבור v‾=0‾\underline{v}=\underline{0}v​=0​.
  2. הומוגניות: ∀v‾∈V,∀α∈F:∣∣αv‾∣∣=∣α∣∣∣v‾∣∣\forall \underline{v}\in V,\forall\alpha \in \mathbb{F}:||\alpha \underline{v}||=|\alpha|||\underline{v}||∀v​∈V,∀α∈F:∣∣αv​∣∣=∣α∣∣∣v​∣∣.
  3. אי שוויון המשולש: ∀v‾,u‾∈V:  ∣∣v‾+u‾∣∣≤∣∣v‾∣∣+∣∣u‾∣∣\forall \underline{v},\underline{u}\in V:\;||\underline{v}+\underline{u}||\leq ||\underline{v}||+||\underline{u}||∀v​,u​∈V:∣∣v​+u​∣∣≤∣∣v​∣∣+∣∣u​∣∣.

הגדרה 11 (מרחב וקטורי נורמי)

למרחב וקטורי בעל פונקציה נורמה יקרא מרחב וקטורי נורמי.

דוגמה

L2:  x‾=(x1x2x3…xn)  ⟹  ∣∣x‾∣∣2=∑k=1n∣xk∣2L^2:\;\underline{x}=\begin{pmatrix} x_{1} & x_{2} & x_{3} & \dots & x_{n} \end{pmatrix}\implies ||\underline{x}||_{2}=\sqrt{ \sum_{k=1}^n |x_{k}|^2 }L2:x​=(x1​​x2​​x3​​…​xn​​)⟹∣∣x​∣∣2​=k=1∑n​∣xk​∣2​
תרגיל

האם L∞:∣∣x‾∣∣∞=max⁡k=1,2,…,n∣xk∣L_{\infty}:||\underline{x}||_{\infty}=\underset{k=1,2,\dots,n}{\max}|x_{k}|L∞​:∣∣x​∣∣∞​=k=1,2,…,nmax​∣xk​∣ היא אכן נורמה?

עלינו לבחון את שלושת התכונות שעל נורמה חוקית לקיים:

  1. חיוביות: נשים לב שאם x‾=0‾\underline{x}=\underline{0}x​=0​ אז ברור שהנורמה היא 0. כמו כן,
    ∀x‾∈V:  ∣∣x‾∣∣∞=max⁡k=1,2,…,n∣xk∣≥0\forall \underline{x}\in V:\; ||\underline{x}||_{\infty}=\underset{k=1,2,\dots,n}{\max}|x_{k}|\geq0∀x​∈V:∣∣x​∣∣∞​=k=1,2,…,nmax​∣xk​∣≥0
  2. הומוגניות: ∀x‾∈V:  ∣∣cx‾∣∣∞=max⁡k=1,2,…,n∣cxk∣=∣c∣max⁡k=1,2,…,n∣xk∣=∣c∣∣∣x‾∣∣∞\forall \underline{x}\in V:\; ||c\underline{x}||_{\infty}=\underset{k=1,2,\dots,n}{\max}|cx_{k}|=|c|\underset{k=1,2,\dots,n}{\max}|x_{k}|=|c|||\underline{x}||_{\infty}∀x​∈V:∣∣cx​∣∣∞​=k=1,2,…,nmax​∣cxk​∣=∣c∣k=1,2,…,nmax​∣xk​∣=∣c∣∣∣x​∣∣∞​.
  3. אי שוויון המשולש:
    \begin{align*} \forall \underline{x},\underline{y}\in V:\; ||\underline{x}+\underline{y}||&=\underset{k=1,2,\dots,n}{\max}|x_{k}+y_{k}| \\ & \leq \underset{k=1,2,\dots,n}{\max}(|x_{k}|+|x_{k}|) \\ & \leq \underset{k=1,2,\dots,n}{\max}|x_{k}|+\underset{k=1,2,\dots,n}{\max}|y_{k}|=||\underline{x}||_{\infty}+||\underline{y}||_{\infty} \end{align*}

כנדרש.

נורמה מושרית

הגדרה 12 (נורמה מושרית)

דרך אחת לבניית נורמה היא ע"י המכפלה הפנימית, לפי:

∣∣v‾∣∣=△⟨v‾,v‾⟩||\underline{v}|| \overset{\triangle}{=}\sqrt{ \langle\underline{v},\underline{v}\rangle }∣∣v​∣∣=△⟨v​,v​⟩​

נורמה זו היא נורמה מושרית המקיימת את שלושת האקסיומות שהוזכרו בהגדרה הקודמת.

משפט (אי-שוויון קושי-שוורץ)

∣⟨v‾,u‾⟩∣≤∣∣v‾∣∣⋅∣∣u‾∣∣|\langle\underline{v},\underline{u}\rangle|\leq ||\underline{v}||\cdot||\underline{u}||∣⟨v​,u​⟩∣≤∣∣v​∣∣⋅∣∣u​∣∣

הוכחת אי השוויון נעשית ע"י פיתוח הביטוי ∣∣v‾+α⟨v‾,u‾⟩u‾∣∣2||\underline{v}+\alpha \langle\underline{v},\underline{u}\rangle\underline{u}||^2∣∣v​+α⟨v​,u​⟩u​∣∣2 כמשוואה ריבועית ודירשה לאי-שליליות.
בעזרת אי שוויון קושי-שוורץ מתאפשרת הוכחת אי-שוויון המשולש לנורמה מושרית.

משפט (שוויון המקבילית)

∣∣v‾+u‾∣∣2+∣∣v‾−u‾∣∣2=2∣∣v‾∣∣2+2∣∣u‾∣∣2||\underline{v}+\underline{u}||^2+||\underline{v}-\underline{u}||^2=2||\underline{v}||^2+2||\underline{u}||^2∣∣v​+u​∣∣2+∣∣v​−u​∣∣2=2∣∣v​∣∣2+2∣∣u​∣∣2

שימו לב- שיוויון זה נכון לנורמה מושרית.

משפט (תכונת פיתגורס)

אם v‾⊥u‾\underline{v} \perp \underline{u}v​⊥u​ אזי

∣∣v‾+u‾∣∣2=∣∣v‾∣∣2+∣∣u‾∣∣2||\underline{v}+\underline{u}||^2=||\underline{v}||^2+||\underline{u}||^2∣∣v​+u​∣∣2=∣∣v​∣∣2+∣∣u​∣∣2

מרחב מטרי

ראינו שניתן להצמיד למרחב וקטורי כלי עזר כמו מכפלה פנימית ו/או נורמה
הרעיון של מרחב וקטורי מטרי הוא להסוף להגדרות המרחב הבסיסיות הגדרת פונקציית מרחק בין שני וקטורים(זוהי המטריקה) עם תכונות מסויימות

d(v‾,u‾)d(\underline{v},\underline{u})d(v​,u​)

בחירה טבעית של מטריקה היא נורמת ההפרש. כלומר, d(v‾,u‾)=∣∣v‾−u‾∣∣d(\underline{v},\underline{u})=||\underline{v}-\underline{u}||d(v​,u​)=∣∣v​−u​∣∣.
ואז זו תהיה מטריקה מושרית מהגדרת הנורמה.