ผลต่างระหว่างรุ่นของ "Sgt/lecture1"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(เพิ่มนิยาม Eigenvector, Eigenvalue อย่าย่อ)
 
(ไม่แสดง 2 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 1: แถว 1:
 +
<noinclude>{{Sgt/เนื้อหา}}</noinclude>
 
{{หัวคำบรรยาย|Spectral graph theory}}
 
{{หัวคำบรรยาย|Spectral graph theory}}
  
แถว 34: แถว 35:
 
== Spectral Theory ==
 
== Spectral Theory ==
  
ให้เมทริกซ์ <math>M</math> ที่มีมิติ <math>n \times n</math> และ <math>M = M^{\top}</math> (นั่นคือ เป็น เมทริกซ์สมมาตร) แล้ว ได้ว่ามี eigenvalue จำนวน <math>n</math> ตัวดังนี้
+
ให้เมทริกซ์ <math>M</math> ที่มีมิติ <math>n \times n</math> และ <math>M = M^{\top}</math> (เมทริกซ์สมมาตร) แล้ว ได้ว่ามี eigenvalue จำนวน <math>n</math> ตัวดังนี้
<math>\lambda_1 \le \lambda_2 \le \ldots \le \lambda_n</math> (นั่นคือ เรียงจากน้อยไปมาก) และมี eigenvector
+
 
<math>\phi_i</math> ที่สอดคล้องกับ eigenvalue <math>\lambda_i</math> โดยที่ <math>\lambda_i \cdot \lambda_j = 0</math>
+
:<math>
สำหรับ <math>i \ne j</math> (นั่นคือ eigenvector ทุกตัวตั้งฉากกัน)
+
\lambda_1 \le \lambda_2 \le \ldots \le \lambda_n
 +
</math>
 +
 
 +
(เรียงค่า eigenvalue จากน้อยไปมาก) และมี eigenvector <math>\phi_i</math> ที่สอดคล้องกับ eigenvalue <math>\lambda_i</math> โดยที่
 +
 
 +
:<math>
 +
\phi_i \perp \phi_j
 +
</math>
 +
 
 +
สำหรับทุก <math>i \ne j</math>

รุ่นแก้ไขปัจจุบันเมื่อ 07:32, 2 กุมภาพันธ์ 2558

Spectral Graph Theory

  1. บทนำและทบทวนพีชคณิตเชิงเส้น (ณัฐวุฒิ)
  2. คุณสมบัติของ Eigenvalue ต่อกราฟ (ธานี,ณัฐวุฒิ)
  3. คุณสมบัติของ Eigenvalue ต่อกราฟ[2] (ภัทร)
  4. คุณสมบัติของ Eigenvalue ลำดับที่สองบนกราฟต่างๆ (ธานี)
  5. Cheeger Inequality (ศุภชวาล)
  6. การทดลอง Cheeger Inequality และ Effective Resistance (ธานี)
  7. Random Walks และ Psuedo Random Generator (ศุภชวาล)
  8. Psuedo Random Generator[2] (ภัทร)
  9. Coding Theory และ Expander code (ธานี)
  10. Expander graph from Linear coding (ภัทร)
  11. Chebyshev polynomial (ศุภชวาล)
  12. Preconditioning (ธานี)

แก้ไขกล่องนี้แก้ไขสารบัญ

บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

สัปดาห์แรกของ Spectral Graph Theory เป็นการเกริ่นนำความรู้พื้นฐานที่จะใช้ในวิชานี้ ซึ่งประกอบไปด้วยการทำความรู้จักกับ eigenvector, eigenvalue และ spectral theory

Eigenvector, Eigenvalue

สำหรับเมทริกซ์จตุรัส นิยาม eigenvector และ eigenvalue ดังนี้

เนื่องจาก

สมการข้างต้น จะมีคำตอบที่ ไม่เป็นศูนย์ ก็ต่อเมื่อ

การแก้สมการ determinant จะทำให้ได้เซ็ตคำตอบของ eigenvalue ทั้งหมดของ หลังจากนั้นจึงแทนค่า eigenvalue แต่ละตัวเพื่อหา eivenvector ที่สอดคล้องกันต่อไป

Spectral Theory

ให้เมทริกซ์ ที่มีมิติ และ (เมทริกซ์สมมาตร) แล้ว ได้ว่ามี eigenvalue จำนวน ตัวดังนี้

(เรียงค่า eigenvalue จากน้อยไปมาก) และมี eigenvector ที่สอดคล้องกับ eigenvalue โดยที่

สำหรับทุก