Sgt/lecture12

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
ยุบ

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 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

ในสัปดาห์นี้ เราเรียนเรื่องการแก้สมการ Ax = b เมื่อกำหนดเมทริกซ์ A และ b ให้ได้อย่างรวดเร็ว

เรื่องแรกได้เรียนคือ ถ้าหากเรามีเมทริกซ์ B ที่ เมทริกซ์ A และถ้าเราแก้สมการ Bx' = b ได้อย่างรวดเร็ว

x' จะเป็นคำตอบที่ห่างจาก x มากแค่ไหน

ซึ่งการจะบอกว่าห่างแค่ไหนนั้น เราจะใช้ตัวชี้วัดเป็นสิ่งที่เรียกว่า A-norm ซึ่งคล้ายกับ Eucilidian norm นิยามดังนี้

ให้ x เป็นเวคเตอร์ Euclidian norm ของ x เขียนแทนด้วย

A-norm จะนิยามดังนี้

ให้ Ax = b และ Bx' = b เราจะจำกัดค่า ดังนี้