שינויים
יצירת דף עם התוכן "{{המשך הגיע|תיאור=נושא הקירוב לווקטורים|תאריך=30.7.12}} == תהליך גרם־שמידט (Gram-Schmidt) == התהליך מי..."
{{המשך הגיע|תיאור=נושא הקירוב לווקטורים|תאריך=30.7.12}}
== תהליך גרם־שמידט (Gram-Schmidt) ==
התהליך מייצר קבוצה אורתוגונלית/אורתונורמלית מקבוצה בת״ל כך שהן פורסות את אותו המרחב.
השלבים, ללא נרמול:
# <math>\tilde\mathbf u_1=\mathbf u_1</math>
# <math>\tilde\mathbf u_2=\mathbf u_2-\mbox{proj}_{\tilde\mathbf u_1}(\mathbf u_2)</math>
...
<math>\tilde\mathbf u_n=\mathbf u_n-\sum_{k=1}^n\mbox{proj}_{\tilde\mathbf u_k}(\mathbf u_n)</math>
=== דוגמה ===
נתון בסיס <math>B=\{\mathbf x_1,\mathbf x_2,\mathbf x_3\}\subset\mathbb R^3</math> כאשר <math>\mathbf x_1=\begin{pmatrix}1\\2\\3\\0\end{pmatrix},\mathbf x_2=\begin{pmatrix}1\\2\\0\\0\end{pmatrix},\mathbf x_3=\begin{pmatrix}1\\0\\0\\1\end{pmatrix}</math>. ניצור באמצעותם בסיס אורתוגונלי:{{left|<math>\begin{align}\mathbf u_1=\mathbf x_1\\\mathbf u_2=\mathbf x_2-\frac{\langle\mathbf x_2,\mathbf u_1\rangle}{\langle\mathbf u_1,\mathbf u_1\rangle}\mathbf u_1=\begin{pmatrix}1\\2\\0\\0\end{pmatrix}-\frac5{14}\begin{pmatrix}1\\2\\3\\0\end{pmatrix}=\begin{pmatrix}9/14\\9/7\\-15/14\\0\end{pmatrix}\\\mathbf u_3=\mathbf x_3-\frac{\langle\mathbf x_3,\mathbf u_1\rangle}{\langle\mathbf u_1,\mathbf u_1\rangle}\mathbf u_1-\frac{\langle\mathbf x_3,\mathbf u_2\rangle}{\langle\mathbf u_2,\mathbf u_2\rangle}\mathbf u_2=\begin{pmatrix}1\\0\\0\\1\end{pmatrix}-\frac1{14}\begin{pmatrix}1\\2\\3\\0\end{pmatrix}-\frac1{70}\begin{pmatrix}9\\18\\-15\\0\end{pmatrix}=\begin{pmatrix}4\\-2\\0\\5\end{pmatrix}\end{align}</math>. נסים לב שהכפלנו כמה מהווקטורים בסקלר (14,5), מה שכמובן לא פגע באורתונורמליות.
קיבלנו מערכת אורתונורמלית <math>\left\{\begin{pmatrix}1\\2\\3\\0\end{pmatrix},\begin{pmatrix}9\\18\\-15\\0\end{pmatrix},\begin{pmatrix}4\\-2\\0\\5\end{pmatrix}\right\}</math>.
=== דוגמה נוספת ===
נתון מרחב פולינומים <math>P_n[x]</math> הנפרש ע״י <math>B=\left\{1,x,x^2,\dots,x^n\right\}</math>. נגדיר כפלה פנימית באופן הבא: <math>\langle p,q\rangle=\int\limits_{-1}^1 p(x)q(x)\mathrm dx</math>. נעזר בתהליך גרם־שמידט ונמצא מערכת אורתוגונילית:{{left|<math>\begin{align}p_0(x)=1\\p_1(x)=x-0=x&\langle x,p_0(x)\rangle=\int\limits_{-1}^1x\mathrm dx=0\\p_2(x)=x^2-0-\frac{2/3}2\cdot1=\frac{3x^2-1}3&\langle x^2,p_0\rangle=\frac23,\langle x^2,p_1\rangle=0,\langle p_0,p_0\rangle=2\\p_3(x)=\frac{5x^3-3x}2\\p_4(x)=\frac{35x^4-30x^2+3}8\\\vdots\end{align}</math>}}
הערה: בסופו של התהליך מתקבלת סדרה של פולינומים אורתוגונליים הנקראים פולינומי לג׳נדר.
מתקיים <math>\int\limits_{-1}^1 p_n(x)p_m(x)\mathrm dx=\begin{cases}0,&n\ne m\\\frac2{2n+1},&n=m\end{cases}</math>. בנוסף, קיימת נוסחה רקורסיבית <math>\begin{cases}p_0(x)=1,p_1(x)=x\\(k+1)p_{k+1}(x)-(2k+1)xp_k(x)+kp_{k-1}(x)=0\end{cases}</math>.
פולינומי צ׳ביצב נוצרים מהמכפלה הפנימית <math>\langle p,q\rangle=\int\limits_{-1}^1\frac{p(x)q(x)}\sqrt{1-x^2}\mathrm dx</math>:{{left|<math>\begin{align}T_0(x)=1\\T_1(x)=x\\T_2(x)=2x^2-1\\T_3(x)=4x^3-3x\\T_4(x)=8x^4-8x^2+1\\T_5(x)=16x^5-20x^3+5x\end{align}</math>}}
קיימת נוסחת רודריגז: <math>T_n(x)=\frac{\sqrt{1-x^2}}{(-1)^n(2n-1)!!}\frac{\mathrm d^n}{\mathrm dx^n}\left(1-x^2\right)^{n-\frac12}</math>. נוסחה רקורסיבית: <math>\begin{cases}T_0(x)=1,T_1(x)=x\\T_{k+1}(x)-2xT_k(x)+T_{k-1}(x)=0\end{cases}</math>. מתקיים <math>\int\limits_{-1}^1\frac{T_n(x)T_m(x)}\sqrt{1-x^2}\mathrm dx=\begin{cases}0,&n\ne m\\\pi,&n=m=0\\\tfrac\pi2,&\text{else}\end{cases}</math>.
פולינומי לגר (Laguerre) נוצרים מ־<math>\langle p,q\rangle=\int\limits_0^\infty \mathrm e^{-x}p(x)q(x)\mathrm dx</math>. נוסחתם הרקורסיבית: <math>\begin{cases}L_0(x)=1,L_1(x)=-x+1\\(k+1)L_{k+1}(x)-(2k+1-x)L_k(x)+kL_{k-1}(x)=0\end{cases}</math>
פולינומי הרמיט (Hermite):‏ <math>\langle p,q\rangle=\int\limits_{-\infty}^\infty\mathrm e^{-x^2}p(x)q(x)\mathrm dx</math> ו־<math>\begin{cases}H_0(x)=1,H_1(x)=2x\\H_{k+1}(x)=2xH_k(x)-2kH_{k-1}(x)\end{cases}</math>.
''הערה:'' פולינומי לגר והרמיט לא יופיע במבחן.
=== תרגיל ===
מצא בסיס אורתונורמלי <math>\{w_1,w_2,w_3\}</math> מהבסיס הבא: <math>\{1,x,x^2\}</math> בקטע <math>[0,1]</math> בקרה של המכפלה הפנימית הסטנדרטית: <math>\langle p,q\rangle=\int\limits_0^1 p(x)q(x)\mathrm dx</math>.
==== פתרון ====
<math>\|1\|^2=\int\limits_0^11\mathrm dx=1</math> ולכן <math>w_1(x)=\frac1{\|1\|}=1</math>.
<math>u_2(x)=x-\frac{\langle x,1\rangle}{\langle1,1\rangle}\cdot1=x-\int\limits_0^1x\mathrm dx=x-\frac12</math>. עתה <math>\left\|x-\frac12\right\|^2=\int\limits_0^1\left(x-\frac12\right)^2\mathrm dx=\frac1{12}</math>. לכן <math>w_2(x)=\frac{x-\frac12}{\left\|x-\frac12\right\|}=\sqrt{12}\left(x-\frac12\right)</math>.
<math>u_3(x)=x^2-\left\langle x^2,1\right\rangle\cdot1-\left\langle x^2,\sqrt{12}\left(x-\frac12\right)\right\rangle\cdot\sqrt{12}\left(x-\frac12\right)=x^2-x+\frac16</math>. ננרמל: <math>\|u_3\|^2=\frac1{180}</math> ולכן <math>w_3(x)=\sqrt{180}\left(x^2-x+\frac16\right)</math>
=== תרגיל ===
מצא קירוב ל־<math>f(x)=1-x^4</math> בעזרת 3 פולינומי לג׳נדר הראשונים בקטע <math>[-1,1]</math>.
==== פתרון ====
הקירוב מקיים <math>\tilde f(x)=a_0 P_0(x)+a_1 P_1(x)+a_2 P_2(x)</math> כאשר <math>a_k=\frac{\langle f,P_k\rangle}{\langle P_k,P_k\rangle}=\frac{2k+1}2\langle f,P_k\rangle</math>. נחשב:{{left|<math>\begin{align}a_0=\frac12\int\limits_{-1}^1\left(1-x^4\right)\mathrm dx=\frac45\\a_1=\frac32\int\limits_{-1}^1\left(1-x^4\right)x\mathrm dx=0\\a_2=\frac52\int\limits_{-1}^1\left(1-x^4\right)\frac{3x^2-1}2\mathrm dx=-\frac47\end{align}</math>}}
לכן <math>\tilde f(x)=\frac45-\frac47\frac{3x^2-1}2=\frac{38-30x^2}{35}</math>. {{משל}}
=== תרגיל ===
מצא קירוב ל־<math>f(x)=\sqrt{2x+3}</math> באמצעות 3 פולינומי לג׳נדר הראשונים בקטע <math>[0,2]</math>.
==== פתרון ====
''דרך א:'' לחשב את פולינומי לג׳נדר בקטע <math>[0,2]</math> ולפתור כרגיל.
''דרך ב:'' נשתמש בטרנספורמציה לינארית <math>[0,2]\to[-1,1]</math>. טרנספורמציה כזאת חייבת לקיים <math>x\mapsto x-1</math>. לכן, כאשר <math>t=x-1</math>, מספיק לחשב קירוב ל־<math>g(t)=\sqrt{2t+5}=f(t+1)=f(x)</math> ב־<math>[-1,1]</math> ואז נוכל למצוא קירוב ל־<math>f</math> ב־<math>[0,2]</math>:{{left|<math>\begin{align}a_0=\frac12\int\limits_{-1}^11\sqrt{2t+5}\mathrm dt\approx2.2207\\a_1=\frac32\int\limits_{-1}^1 t\sqrt{2t+5}\mathrm dt\approx0.45\\a_2=\frac52\int\limits_{-1}^1\sqrt{2t+5}\frac{3t^2-1}2\mathrm dt\approx0.0314\end{align}</math>}}
לכן <math>\tilde g(t)\approx2.2207+0.45t+0.0314\frac{3t^2-1}2</math> נציב <math>t=x-1</math> ולכן <math>\tilde f(x)\approx2.2207+0.45(x-1)+0.0314\frac{3(x-1)^2-1}2</math>. {{משל}}
= הקדמה לשיעור הבא =
נדון במכפלה הפנימית <math>\langle f,g\rangle=\frac1\pi\int\limits_{-\pi}^\pi f(x)g(x)\mathrm dx</math> ונבדוק שהמערכת הבאה אורתונורמלית <math>\left\{\frac1\sqrt2,\sin(x),\cos(x),\sin(2x),\cos(2x),\dots\right\}</math>.
== תהליך גרם־שמידט (Gram-Schmidt) ==
התהליך מייצר קבוצה אורתוגונלית/אורתונורמלית מקבוצה בת״ל כך שהן פורסות את אותו המרחב.
השלבים, ללא נרמול:
# <math>\tilde\mathbf u_1=\mathbf u_1</math>
# <math>\tilde\mathbf u_2=\mathbf u_2-\mbox{proj}_{\tilde\mathbf u_1}(\mathbf u_2)</math>
...
<math>\tilde\mathbf u_n=\mathbf u_n-\sum_{k=1}^n\mbox{proj}_{\tilde\mathbf u_k}(\mathbf u_n)</math>
=== דוגמה ===
נתון בסיס <math>B=\{\mathbf x_1,\mathbf x_2,\mathbf x_3\}\subset\mathbb R^3</math> כאשר <math>\mathbf x_1=\begin{pmatrix}1\\2\\3\\0\end{pmatrix},\mathbf x_2=\begin{pmatrix}1\\2\\0\\0\end{pmatrix},\mathbf x_3=\begin{pmatrix}1\\0\\0\\1\end{pmatrix}</math>. ניצור באמצעותם בסיס אורתוגונלי:{{left|<math>\begin{align}\mathbf u_1=\mathbf x_1\\\mathbf u_2=\mathbf x_2-\frac{\langle\mathbf x_2,\mathbf u_1\rangle}{\langle\mathbf u_1,\mathbf u_1\rangle}\mathbf u_1=\begin{pmatrix}1\\2\\0\\0\end{pmatrix}-\frac5{14}\begin{pmatrix}1\\2\\3\\0\end{pmatrix}=\begin{pmatrix}9/14\\9/7\\-15/14\\0\end{pmatrix}\\\mathbf u_3=\mathbf x_3-\frac{\langle\mathbf x_3,\mathbf u_1\rangle}{\langle\mathbf u_1,\mathbf u_1\rangle}\mathbf u_1-\frac{\langle\mathbf x_3,\mathbf u_2\rangle}{\langle\mathbf u_2,\mathbf u_2\rangle}\mathbf u_2=\begin{pmatrix}1\\0\\0\\1\end{pmatrix}-\frac1{14}\begin{pmatrix}1\\2\\3\\0\end{pmatrix}-\frac1{70}\begin{pmatrix}9\\18\\-15\\0\end{pmatrix}=\begin{pmatrix}4\\-2\\0\\5\end{pmatrix}\end{align}</math>. נסים לב שהכפלנו כמה מהווקטורים בסקלר (14,5), מה שכמובן לא פגע באורתונורמליות.
קיבלנו מערכת אורתונורמלית <math>\left\{\begin{pmatrix}1\\2\\3\\0\end{pmatrix},\begin{pmatrix}9\\18\\-15\\0\end{pmatrix},\begin{pmatrix}4\\-2\\0\\5\end{pmatrix}\right\}</math>.
=== דוגמה נוספת ===
נתון מרחב פולינומים <math>P_n[x]</math> הנפרש ע״י <math>B=\left\{1,x,x^2,\dots,x^n\right\}</math>. נגדיר כפלה פנימית באופן הבא: <math>\langle p,q\rangle=\int\limits_{-1}^1 p(x)q(x)\mathrm dx</math>. נעזר בתהליך גרם־שמידט ונמצא מערכת אורתוגונילית:{{left|<math>\begin{align}p_0(x)=1\\p_1(x)=x-0=x&\langle x,p_0(x)\rangle=\int\limits_{-1}^1x\mathrm dx=0\\p_2(x)=x^2-0-\frac{2/3}2\cdot1=\frac{3x^2-1}3&\langle x^2,p_0\rangle=\frac23,\langle x^2,p_1\rangle=0,\langle p_0,p_0\rangle=2\\p_3(x)=\frac{5x^3-3x}2\\p_4(x)=\frac{35x^4-30x^2+3}8\\\vdots\end{align}</math>}}
הערה: בסופו של התהליך מתקבלת סדרה של פולינומים אורתוגונליים הנקראים פולינומי לג׳נדר.
מתקיים <math>\int\limits_{-1}^1 p_n(x)p_m(x)\mathrm dx=\begin{cases}0,&n\ne m\\\frac2{2n+1},&n=m\end{cases}</math>. בנוסף, קיימת נוסחה רקורסיבית <math>\begin{cases}p_0(x)=1,p_1(x)=x\\(k+1)p_{k+1}(x)-(2k+1)xp_k(x)+kp_{k-1}(x)=0\end{cases}</math>.
פולינומי צ׳ביצב נוצרים מהמכפלה הפנימית <math>\langle p,q\rangle=\int\limits_{-1}^1\frac{p(x)q(x)}\sqrt{1-x^2}\mathrm dx</math>:{{left|<math>\begin{align}T_0(x)=1\\T_1(x)=x\\T_2(x)=2x^2-1\\T_3(x)=4x^3-3x\\T_4(x)=8x^4-8x^2+1\\T_5(x)=16x^5-20x^3+5x\end{align}</math>}}
קיימת נוסחת רודריגז: <math>T_n(x)=\frac{\sqrt{1-x^2}}{(-1)^n(2n-1)!!}\frac{\mathrm d^n}{\mathrm dx^n}\left(1-x^2\right)^{n-\frac12}</math>. נוסחה רקורסיבית: <math>\begin{cases}T_0(x)=1,T_1(x)=x\\T_{k+1}(x)-2xT_k(x)+T_{k-1}(x)=0\end{cases}</math>. מתקיים <math>\int\limits_{-1}^1\frac{T_n(x)T_m(x)}\sqrt{1-x^2}\mathrm dx=\begin{cases}0,&n\ne m\\\pi,&n=m=0\\\tfrac\pi2,&\text{else}\end{cases}</math>.
פולינומי לגר (Laguerre) נוצרים מ־<math>\langle p,q\rangle=\int\limits_0^\infty \mathrm e^{-x}p(x)q(x)\mathrm dx</math>. נוסחתם הרקורסיבית: <math>\begin{cases}L_0(x)=1,L_1(x)=-x+1\\(k+1)L_{k+1}(x)-(2k+1-x)L_k(x)+kL_{k-1}(x)=0\end{cases}</math>
פולינומי הרמיט (Hermite):‏ <math>\langle p,q\rangle=\int\limits_{-\infty}^\infty\mathrm e^{-x^2}p(x)q(x)\mathrm dx</math> ו־<math>\begin{cases}H_0(x)=1,H_1(x)=2x\\H_{k+1}(x)=2xH_k(x)-2kH_{k-1}(x)\end{cases}</math>.
''הערה:'' פולינומי לגר והרמיט לא יופיע במבחן.
=== תרגיל ===
מצא בסיס אורתונורמלי <math>\{w_1,w_2,w_3\}</math> מהבסיס הבא: <math>\{1,x,x^2\}</math> בקטע <math>[0,1]</math> בקרה של המכפלה הפנימית הסטנדרטית: <math>\langle p,q\rangle=\int\limits_0^1 p(x)q(x)\mathrm dx</math>.
==== פתרון ====
<math>\|1\|^2=\int\limits_0^11\mathrm dx=1</math> ולכן <math>w_1(x)=\frac1{\|1\|}=1</math>.
<math>u_2(x)=x-\frac{\langle x,1\rangle}{\langle1,1\rangle}\cdot1=x-\int\limits_0^1x\mathrm dx=x-\frac12</math>. עתה <math>\left\|x-\frac12\right\|^2=\int\limits_0^1\left(x-\frac12\right)^2\mathrm dx=\frac1{12}</math>. לכן <math>w_2(x)=\frac{x-\frac12}{\left\|x-\frac12\right\|}=\sqrt{12}\left(x-\frac12\right)</math>.
<math>u_3(x)=x^2-\left\langle x^2,1\right\rangle\cdot1-\left\langle x^2,\sqrt{12}\left(x-\frac12\right)\right\rangle\cdot\sqrt{12}\left(x-\frac12\right)=x^2-x+\frac16</math>. ננרמל: <math>\|u_3\|^2=\frac1{180}</math> ולכן <math>w_3(x)=\sqrt{180}\left(x^2-x+\frac16\right)</math>
=== תרגיל ===
מצא קירוב ל־<math>f(x)=1-x^4</math> בעזרת 3 פולינומי לג׳נדר הראשונים בקטע <math>[-1,1]</math>.
==== פתרון ====
הקירוב מקיים <math>\tilde f(x)=a_0 P_0(x)+a_1 P_1(x)+a_2 P_2(x)</math> כאשר <math>a_k=\frac{\langle f,P_k\rangle}{\langle P_k,P_k\rangle}=\frac{2k+1}2\langle f,P_k\rangle</math>. נחשב:{{left|<math>\begin{align}a_0=\frac12\int\limits_{-1}^1\left(1-x^4\right)\mathrm dx=\frac45\\a_1=\frac32\int\limits_{-1}^1\left(1-x^4\right)x\mathrm dx=0\\a_2=\frac52\int\limits_{-1}^1\left(1-x^4\right)\frac{3x^2-1}2\mathrm dx=-\frac47\end{align}</math>}}
לכן <math>\tilde f(x)=\frac45-\frac47\frac{3x^2-1}2=\frac{38-30x^2}{35}</math>. {{משל}}
=== תרגיל ===
מצא קירוב ל־<math>f(x)=\sqrt{2x+3}</math> באמצעות 3 פולינומי לג׳נדר הראשונים בקטע <math>[0,2]</math>.
==== פתרון ====
''דרך א:'' לחשב את פולינומי לג׳נדר בקטע <math>[0,2]</math> ולפתור כרגיל.
''דרך ב:'' נשתמש בטרנספורמציה לינארית <math>[0,2]\to[-1,1]</math>. טרנספורמציה כזאת חייבת לקיים <math>x\mapsto x-1</math>. לכן, כאשר <math>t=x-1</math>, מספיק לחשב קירוב ל־<math>g(t)=\sqrt{2t+5}=f(t+1)=f(x)</math> ב־<math>[-1,1]</math> ואז נוכל למצוא קירוב ל־<math>f</math> ב־<math>[0,2]</math>:{{left|<math>\begin{align}a_0=\frac12\int\limits_{-1}^11\sqrt{2t+5}\mathrm dt\approx2.2207\\a_1=\frac32\int\limits_{-1}^1 t\sqrt{2t+5}\mathrm dt\approx0.45\\a_2=\frac52\int\limits_{-1}^1\sqrt{2t+5}\frac{3t^2-1}2\mathrm dt\approx0.0314\end{align}</math>}}
לכן <math>\tilde g(t)\approx2.2207+0.45t+0.0314\frac{3t^2-1}2</math> נציב <math>t=x-1</math> ולכן <math>\tilde f(x)\approx2.2207+0.45(x-1)+0.0314\frac{3(x-1)^2-1}2</math>. {{משל}}
= הקדמה לשיעור הבא =
נדון במכפלה הפנימית <math>\langle f,g\rangle=\frac1\pi\int\limits_{-\pi}^\pi f(x)g(x)\mathrm dx</math> ונבדוק שהמערכת הבאה אורתונורמלית <math>\left\{\frac1\sqrt2,\sin(x),\cos(x),\sin(2x),\cos(2x),\dots\right\}</math>.
