Sgt/lecture12

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

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

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

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

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

ให้ x เป็นเวคเตอร์ Euclidian norm ของ x เขียนแทนด้วย $||x||={\sqrt {x^{T}x}}$

A-norm จะนิยามดังนี้ $||x||_{A}={\sqrt {x^{T}Ax}}$

ให้ Ax = b และ Bx' = b เราจะจำกัดค่า $||x-x'||_{A}$ ดังนี้

${\begin{aligned}||x-x'||_{A}&={\sqrt {(x-x')^{T}A(x-x')}}\\&={\sqrt {(x-B^{-1}b)^{T}A(x-B^{-1}b)}}\\&=||I-AB^{-1}||\cdot ||x||_{A}\end{aligned}}$