การแก้เมทริกซ์สามแนวทแยงด้วยอัลกอริธึมของโธมัส (Thomas Algorithm)

โพสต์นี้เป็นส่วนหนึ่งของชุดบทความเกี่ยวกับวิธีการอนุพันธ์จำกัด โพสต์อื่นในซีรีส์นี้มุ่งเน้นไปที่การประมาณอนุพันธ์ การแก้สมการการแพร่กระจายอย่างชัดเจน และวิธี Crank-Nicholson แบบปริยาย:

• การประมาณอนุพันธ์ด้วยวิธีผลต่างจำกัด
• การแก้สมการการแพร่แบบชัดแจ้ง (Explicit)
• วิธี Crank-Nicholson แบบปริยาย
• การแก้ระบบเมทริกซ์สามแนวทแยงด้วยอัลกอริธึมของโธมัส

ในบทช่วยสอนก่อนหน้านี้ ชุดของสมการเชิงเส้นทำให้สามารถสร้างสมการ tridiagonal matrix ได้ การแก้สมการนี้ช่วยให้สามารถคำนวณจุดกริดภายในได้ ระบบเชิงเส้นนี้ต้องการการแก้ไขที่ทุกช่วงเวลา ชัดเจนว่านี่ต้องใช้การคำนวณมากกว่าต่อช่วงเวลาเมื่อเปรียบเทียบกับงานที่ต้องใช้สำหรับตัวแก้ปัญหาแบบชัดเจน วิธีการแบบอิมพลิซิตตอบโต้ด้วยความสามารถในการเพิ่มช่วงเวลาของการคำนวณได้อย่างมาก

วิธีการที่ใช้ในการแก้ระบบเมทริกซ์นี้เป็นของ Llewellyn Thomas และรู้จักกันในชื่อว่า Tridiagonal Matrix Algorithm (TDMA) มันเป็นการประยุกต์ใช้การกำจัดแก๊สเซียนกับโครงสร้างแถบของเมทริกซ์ ระบบเดิมถูกเขียนเป็น:

$$\left[\begin{array}{cccccc}{b}_1& c_1& 0& 0& ...& 0\\ a_2& b_2& c_2& 0& ...& 0\\ 0& a_3& b_3& c_3& 0& 0\\ .& .& & & & .\\ .& .& & & & .\\ .& .& & & & c_{k-1}\\ 0& 0& 0& 0& a_k& b_k\end{array}\right]\left[\begin{array}{c}{f}_1\\ f_2\\ f_3\\ .\\ .\\ .\\ f_k\end{array}\right]=\left[\begin{array}{c}{d}_1\\ d_2\\ d_3\\ .\\ .\\ .\\ d_k\end{array}\right]$$

วิธีการเริ่มต้นโดยการสร้างสัมประสิทธิ์ $c_i^{\ast }$ และ $d_i^{\ast }$ แทนที่ $a_i$, $b_i$ และ $c_i$ ดังนี้:

$$c_i^{\ast }=\{\begin{array}{lr}\frac{c_1}{b_1}& ;i=1\\ \frac{c_i}{b_i-c_{i-1}^{\ast }{a}_i}& ;i=2,3,...,k-1\end{array}$$

$$d_i^{\ast }=\{\begin{array}{lr}\frac{d_1}{b_1}& ;i=1\\ \frac{d_i-d_{i-1}^{\ast }{a}_i}{b_i-c_{i-1}^{\ast }{a}_i}& ;i=2,3,...,k-1\end{array}$$

ด้วยสัมประสิทธิ์ใหม่เหล่านี้ สมการเมทริกซ์สามารถเขียนใหม่ได้ว่า:

$$\left[\begin{array}{cccccc}1& c_1^{\ast }& 0& 0& ...& 0\\ 0& 1& c_2^{\ast }& 0& ...& 0\\ 0& 0& 1& c_3^{\ast }& 0& 0\\ .& .& & & & .\\ .& .& & & & .\\ .& .& & & & c_{k-1}^{\ast }\\ 0& 0& 0& 0& 0& 1\end{array}\right]\left[\begin{array}{c}{f}_1\\ f_2\\ f_3\\ .\\ .\\ .\\ f_k\end{array}\right]=\left[\begin{array}{c}{d}_1^{\ast }\\ d_2^{\ast }\\ d_3^{\ast }\\ .\\ .\\ .\\ d_k^{\ast }\end{array}\right]$$

อัลกอริธึมสำหรับการแก้สมการเหล่านี้ตอนนี้เรียบง่ายและทำงาน 'ย้อนกลับ':

$$f_k=d_k^{\ast },f_i=d_k^{\ast }-c_i^{\ast }{x}_{i+1},i=k-1,k-2,...,2,1$$

ในขั้นตอนนี้ อัลกอริธึมสำหรับแต่ละจุดในตารางที่แต่ละช่วงเวลาได้ถูกสรุปไว้แล้ว ขั้นตอนสุดท้ายในการผลิตวิธีการคำนวณคือการนำอัลกอริธึมไปใช้ ซึ่งจะเป็นหัวข้อของการสอนครั้งถัดไป

อ้างอิง : Tridiagonal Matrix Solver via Thomas Algorithm

จาก https://www.quantstart.com/articles/Tridiagonal-Matrix-Solver-via-Thomas-Algorithm/