|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
||||
|
||||
ขอถามเกี่ยวกับ 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 อย่างไร |
#2
|
||||
|
||||
ผมก็ไม่แม่นเรื่องนี้ เพราะไม่ได้ใช้จริงจัง และเคยแต่อ่านผ่านๆ
สมมติว่าเราจะทำ 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 ได้นะครับ
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson. |
#3
|
||||
|
||||
ในขั้นตอนที่สอง นี่พจน์ $(n-m+1)(n-m )$ คือ จำนวน operations ในการคูณเพื่อทำให้แถวใต้ $a_{n,n}$ เป็นศูนย์ ใช่ไหมครับ
เลข2 นี่มายังไงครับ ขอบคุณล่วงหน้าครับ 22 พฤษภาคม 2008 11:14 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ คนบ้า |
#4
|
||||
|
||||
$(n - m + 1)(n - m)$ เป็นจำนวนครั้งในการคูณ ซึ่งก็เท่ากับจำนวนครั้งในการบวกด้วย เมื่อนำมารวมกันค่าที่ได้จึงเป็น 2 เท่าของค่านี้ครับ
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson. |
#5
|
||||
|
||||
Thank you หลายเด้อครับ
|
หัวข้อคล้ายคลึงกัน | ||||
หัวข้อ | ผู้ตั้งหัวข้อ | ห้อง | คำตอบ | ข้อความล่าสุด |
Gauss Elimination | jae_bau | คณิตศาสตร์อุดมศึกษา | 1 | 03 สิงหาคม 2008 16:57 |
|
|