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

โพสต์นี้เป็นส่วนหนึ่งของชุดบทความเกี่ยวกับวิธีผลต่างจำกัด (Finite Difference Method) โดยโพสต์อื่นๆ ในชุดนี้กล่าวถึง:

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

ในบทความก่อนหน้านี้ ชุดของสมการเชิงเส้นถูกจัดให้อยู่ในรูปของสมการเมทริกซ์สามแนวทแยง การแก้สมการนี้ทำให้สามารถคำนวณค่าที่จุดตารางภายใน (interior grid points) ได้ โดยระบบสมการนี้จะต้องถูกแก้ในทุกๆ ก้าวเวลา (time step) ซึ่งชัดเจนว่าวิธีนี้ใช้ทรัพยากรมากกว่าวิธีชัดแจ้งในแต่ละก้าวเวลา อย่างไรก็ตาม วิธีปริยายสามารถใช้ก้าวเวลาที่ใหญ่ขึ้นได้มาก ทำให้มีข้อได้เปรียบในระยะยาว

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

รูปแบบของระบบสมการ

สมการตั้งต้นสามารถเขียนได้ในรูปแบบ:

ai​ui−1n+1​+bi​uin+1​+ci​ui+1n+1​=di​

สำหรับ i=1,2,...,N−2

การกำหนดสัมประสิทธิ์ใหม่

อัลกอริธึมเริ่มต้นโดยสร้างสัมประสิทธิ์ใหม่ ci′​ และ di′​ แทนที่ ai​,bi​,ci และ di​ ดังนี้:

สำหรับ i=1:

c1′​=b1​c1​​,d1′​=b1​d1​​

สำหรับ i=2,3,...,N−2:

ci′​=bi​−ai​ci−1′​ci​​

di′​=bi​−ai​ci−1′​di​−ai​di−1′​​

การแทนระบบสมการใหม่

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

uin+1​=ci′​ui+1n+1​+di′​,สำหรับ i=1,2,...,N−2

อัลกอริธึมการแก้สมการ (Back Substitution)

เมื่อคำนวณ ci′​ และ di′​ ครบแล้ว สามารถหาค่า uin+1​ ถอยหลังจาก i=N−2 ลงมาถึง i=1 ได้ดังนี้:

ตั้งต้นที่:

uN−2n+1​=dN−2′​

ถอยกลับ:

uin+1​=ci′​ui+1n+1​+di′​,สำหรับ i=N−3,...,1

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

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

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