ขอถามเกี่ยวกับ Complexity of Gaussian elimination
 

อ่านจาก wikipedia ได้ว่า การทำ Gaussian elimination matrix ขนาด $n \times n$ จะใช้ operation ประมาณ $\frac{2n^3}{3}$ operations.
ดังนั้นจึงมี complexity $O(n^3)$

ช่วยขยายความให้ทีว่ามันมายังไงครับ

แล้วถ้า matrix ที่ไม่ใช่ square matrix หละครับ คิด complexity ในการทำ Gaussian elimination อย่างไร

ผมก็ไม่แม่นเรื่องนี้ เพราะไม่ได้ใช้จริงจัง และเคยแต่อ่านผ่านๆ

สมมติว่าเราจะทำ Gaussian elimination ของ matrix ขนาด $n \times n$ แถวที่ $m$ แบบง่ายๆ

ขั้นแรก เราต้องการให้ $a_{m,m} = 1$ จึงต้องคูณสมาชิกทุกตัวของแถวที่ $m$ ด้วยค่า $\frac{1}{a_{m,m}}$ นับจำนวนครั้งที่คูณได้ $n - m + 1$ ครั้ง

ขั้นที่สอง เราต้องการให้ $a_{x,m} = 0$ สำหรับทุก $x > m$ ตรงจุดนี้ต้องคูณสมาชิกทุกตัวของแถวที่ $m$ ด้วยค่า $-a_{x,m}$ แล้วนำไปรวมกับสมาชิกแต่ละตัวของแถว $x$ นับจำนวนครั้งที่คูณและนำมาบวกได้ $2(n - m + 1)(n - m)$ ครั้ง

เราต้องทำสองขั้นตอนดังกล่าว ตั้งแต่ค่า $m = 1$ จนถึงค่า $m = n$ ดังนั้นจำนวน operation ที่ใช้คือ
\[\sum_{m = 1}^{n} (n - m + 1) + 2(n - m + 1)(n - m) = \frac{2n^3}{3} + \frac{n^2}{2} - \frac{n}{6}\]
จึงได้ complexity เป็น $O(n^3)$

ถ้าเข้าใจหลักการแล้ว น่าจะคำนวณกรณีที่ไม่ใช่ square matrix ได้นะครับ :rolleyes:

ในขั้นตอนที่สอง นี่พจน์ $(n-m+1)(n-m )$ คือ จำนวน operations ในการคูณเพื่อทำให้แถวใต้ $a_{n,n}$ เป็นศูนย์ ใช่ไหมครับ

เลข2 นี่มายังไงครับ



ขอบคุณล่วงหน้าครับ

$(n - m + 1)(n - m)$ เป็นจำนวนครั้งในการคูณ ซึ่งก็เท่ากับจำนวนครั้งในการบวกด้วย เมื่อนำมารวมกันค่าที่ได้จึงเป็น 2 เท่าของค่านี้ครับ

Thank you หลายเด้อครับ