אנליזה נומרית/פתרון מערכת משוואות לינאריות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מאין תקציר עריכה |
|||
שורה 39:
===שיטת גאוס===
בשיטת גאוס (הנקראת גם "שיטת הדרוג" או "שיטת החילוץ") מדרגים את המטריצה המורחבת [A|b] ובסוף מציבים לאחור. עבור מטריצה מסדר n יידרשו <math>\ {n^3 \over 3} +n^2 -{n\over 3}</math> פעולות.
===שיטת גאוס-ג'ורדן===
עבור מטריצה מסדר n יידרשו <math>\ {n^3 \over 2} +n^2 -{n\over 2}</math> פעולות.
===פירוק LU===
שורה 80:
'''שיטה אחרת:'''<br />
בהינתן מערכת מסדר n, נפתור את n הבעיות <math>\ \underline{A}\cdot\underline{x}_i= \underline{e}_i</math>, כאשר <math>\ \underline{e}_i</math> הם וקטורי הבסיס הסטנדרטי. לשם פתרון n הבעיות הללו ניתן להעזר בשיטות המופיעות בדף זה.
===פתרון מערכת תלת-אלכסונית===
פתרון מערכת תלת-אלכסונית מתבצע באמצעות אלגוריתם הנקרא TDMA (Tridiagonal matrix algorithm), או אלגוריתם תומס.
:<math>
\left[ \begin{matrix}
{b_1} & {c_1} & { } & { } & { 0 } \\
{a_2} & {b_2} & {c_2} & { } & { } \\
{ } & {a_3} & {b_3} & \ddots & { } \\
{ } & { } & \ddots & \ddots & {c_{N-1}}\\
{ 0 } & { } & { } & {a_N} & {b_N}\\
\end{matrix} \right]
\left\{ \begin{matrix}
{x_1 } \\ {x_2 } \\ \cdot \\ \cdot \\ {x_N } \\
\end{matrix} \right\}
=
\left\{ \begin{matrix}
{d_1 } \\ {d_2 } \\ \cdot \\ \cdot \\ {d_N } \\
\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.
'''שימושים:'''
* בהינתן מד"ר, אם נכתוב את משוואת הפרשים עבורה, נקבל מטריצה תלת-אלכסונית.
===קישורים חיצוניים===
{{מיזמים|ויקיפדיה=צורת ז'ורדן|ויקיפדיה 2=en:LU decomposition|שם ויקיפדיה 2=פירוק LU (אנגלית)|ויקיפדיה 3=מטריצה הפיכה|ויקיפדיה 4=en:Tridiagonal matrix algorithm|שם ויקיפדיה 4=אלגוריתם תומס}}
* [http://www.cs.colostate.edu/cameron/tridiagonal.html קוד מקור] לאלגוריתם תומס.
==שיטות איטרטיביות==
שורה 205 ⟵ 268:
דרך אחרת לפיתוח השיטה הוא באמצעות שימוש ייצוג המטריצה A באמצעות המכפלה DLU, כאשר D היא מטריצה אלכסונית (למידע נוסף ראו "קישורים חיצוניים").
===קישורים חיצוניים===
{{מיזמים|ויקיפדיה=en:Jacobi method|שם ויקיפדיה=שיטת Jacobi (אנגלית)|ויקיפדיה 2=en:Gauss-Seidel method|שם ויקיפדיה 2=שיטת Gauss-Seidel (אנגלית)|ויקיפדיה 3=en:Successive over-relaxation|שם ויקיפדיה 3=שיטת SOR (אנגלית)
* הסברים באתר MathWorld: [http://mathworld.wolfram.com/JacobiMethod.html שיטת Jacobi], [http://mathworld.wolfram.com/Gauss-SeidelMethod.html שיטת Gauss-Seidel], [http://mathworld.wolfram.com/SuccessiveOverrelaxationMethod.html שיטת SOR], [http://mathworld.wolfram.com/TridiagonalMatrix.html אלגוריתם תומס]
* הסברים באתר אוניברסיטת USCF על [http://math.fullerton.edu/mathews/n2003/SORmethodMod.html שיטת SOR] עם קטעי קוד עבור תוכנת Mathematica.
{{אנליזה נומרית|מוגבל=כן}}
| |||