אנליזה נומרית/פתרון מערכת משוואות לינאריות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 145:
{b_1} & {c_1} & { } & { } & { 0 } \\
{a_2} & {b_2} & {c_2} & { } & { } \\
{ } & {a_3} & {b_3} & \
{ } & { } & \
{ 0 } & { } & { } & {
\end{matrix} \right]▼
\left[ \begin{matrix}▼
{x_1 } \\ {x_2 } \\ \cdot \\ \cdot \\ {x_n } \\ ▼
\end{matrix} \right]
=
\left
{d_1 } \\ {d_2 } \\ \cdot \\ \cdot \\ {
\end{matrix} \right
\quad\Rightarrow\quad
\begin{array}{lcl}
b_1x_1 + c_1x_2 & = & d_1 \\
a_2x_1 + b_2x_2 + c_2x_3 & = & d_2 \\
\vdots & { } & { } \\
a_ix_{i-1} + b_ix_i + c_ix_{i+1} & = & d_i \\
\vdots & { } & { } \\
a_Nx_{N-1} + b_Nx_N & = & d_N \\
\end{array}</math>
יש לנו אם כן, 3N-2 איברים, אשר חלקם יכולים להיות 0.
על מנת להגיע לפתרון, נבצע דירוג של שורה אחר שורה: נכפיל את השורה הראשונה ב- <math>\ -{a_2 \over b_1}</math> ונוסיף אותה לשורה השנייה, כך שנקבל:
:<math>\ \overbrace{\left( b_2 - {a_2c_1 \over b_1} \right)}^{\beta_2} x_2 +c_2x_3= \overbrace{d_2- {a_2d_2 \over b_1}}^{\delta_2} \quad\Rightarrow\quad \beta_2x_2+ c_2x_3= \delta_2</math>
כעת נכפיל את את המשוואה ב- <math>\ -{a_3 \over \beta_2}</math> ונוסיף אותה לשורה השלישית, כך שנקבל:
:<math>\ \overbrace{\left( b_3 - {a_3c_2 \over \beta_2} \right)}^{\beta_3} x_3 +c_3x_4= \overbrace{d_3- {a_3\delta_2 \over \beta_2}}^{\delta_3} \quad\Rightarrow\quad \beta_3x_3+ c_3x_4= \delta_3</math>
כעת, אחרי שעברנו לכתיב β,δ ניתן להכליל ולומר שהמשוואות ה-(i-1)-ית וה-i-ית הן מן הצורה:
:<math>\ \beta_{i-1}x_{i-1}+ c_{i-1}x_i= \delta_{i-1}</math>
:<math>\ a_ix_{i-1}+ b_ix_i+ c_ix_{i+1}= d_i</math>
בהתאמה, כך שכאשר נכפיל את המשוואה ה-(i-1)-ית ב- <math>\ -{a_i \over \beta_{i-1}}</math>, ונוסיף למשוואה ה-i-ית, נקבל:
:<math>\ \overbrace{\left( b_i - {a_ic_{i-1} \over \beta_{i-1}} \right)}^{\beta_i} x_i +c_ix_{i+1}= \overbrace{d_i- {a_i\delta_{i-1} \over \beta_{i-1}}}^{\delta_i} \quad\Rightarrow\quad \beta_ix_i+ c_ix_{i+1}= \delta_i</math>
לשם השלמת התמונה, נביט בשתי המשוואות האחרונות:
:<math>\ \beta_{N-1}x_{N-1}+ c_{N-1}x_N= \delta_{N-1}</math>
:<math>\ a_Nx_{N-1}+ b_Nx_N= d_N</math>
נכפיל את המשוואה ה-(N-1)-ית ב- <math>\ -{a_N \over \beta_{N-1}}</math>, ונוסיף למשוואה ה-N-ית, כך שנקבל:
:<math>\ \overbrace{\left( b_N - {a_Nc_{N-1} \over \beta_{N-1}} \right)}^{\beta_N} x_N= \overbrace{d_N- {a_N\delta_{N-1} \over \beta_{N-1}}}^{\delta_N} \quad\Rightarrow\quad \beta_Nx_N= \delta_N</math>
מכאן מחלצים את x<sub>N</sub> ומקבלים את שאר הנעלמים על ידי הצבה לאחור.
כאשר נצטרך לכתוב תכנית מחשב, נרצה להכליל את כתיב β,δ גם על השורה הראשונה. לשם כך נוכל להגדיר:
:# <math>\ \delta_1=d_1,\ \beta_1=b_1</math>, ואז האלגוריתם ימשיך:
:# <math>\ \beta_i= \left( b_i - {a_ic_{i-1} \over \beta_{i-1}} \right) \quad,\quad \delta_i= d_i- {a_i\delta_{i-1} \over \beta_{i-1}}</math> עבור <math>\ i=2,3,...,N</math>.
:# <math>\ x_N= {\delta_N \over \beta_N}</math>
:# <math>\ x_i= -{c_ix_{i+1}+ \delta_i \over \beta_i}</math> עבור <math>\ i=N-1,N-2,...,2,1</math>.
בהערכה פשוטה מתקבל כי מספר הפעולות המקסימלי לשיטה זו הינו 5N-4.
===קישורים חיצוניים===
| |||