ผลต่างระหว่างรุ่นของ "Sgt/lecture12"
Tanee (คุย | มีส่วนร่วม) |
Tanee (คุย | มีส่วนร่วม) |
||
(ไม่แสดง 1 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
แถว 20: | แถว 20: | ||
||x-x'||_A &= \sqrt{(x-x')^TA(x-x')} \\ | ||x-x'||_A &= \sqrt{(x-x')^TA(x-x')} \\ | ||
&= \sqrt{(x-B^{-1}b)^TA(x-B^{-1}b)} \\ | &= \sqrt{(x-B^{-1}b)^TA(x-B^{-1}b)} \\ | ||
− | &= ||I-AB^{-1}|| | + | &= ||I-AB^{-1}|| \cdot ||x||_A |
\end{align} | \end{align} | ||
</math> | </math> | ||
+ | |||
+ | |||
+ | ดังนั้น เราจะ bound ค่า norm ของ <math>||I-AB^{-1}||</math> ด้วย eigenvalue ที่มากที่สุดของมัน | ||
+ | . | ||
+ | . | ||
+ | . | ||
+ | . | ||
+ | . | ||
+ | . | ||
+ | ได้ไม่เกิน <math>\epsilon</math> | ||
+ | |||
+ | == Preconditioning == | ||
+ | |||
+ | อีกวิธีที่ทำได้คือ ใช้ iterative method เหมือนที่เรียนในสัปดาห์ที่แล้ว แต่ก่อนที่จะทำนั้น เราจะหาเมทริกซ์ B ที่มีคุณสมบัติ.... มาคูณทั้งสองฝั่ง | ||
+ | |||
+ | ทำให้การแก้สมการ Ax = b กลายเป็นการแก้สมการ <math>B^{-1}Ax = B^{-1}b</math> เพื่อให้ทำ iterative method ได้เร็วขึ้น |
รุ่นแก้ไขปัจจุบันเมื่อ 09:35, 21 พฤษภาคม 2558
บันทึกคำบรรยายวิชา 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 เราจะจำกัดค่า ดังนี้
ดังนั้น เราจะ bound ค่า norm ของ ด้วย eigenvalue ที่มากที่สุดของมัน
.
.
.
.
.
.
ได้ไม่เกิน
Preconditioning
อีกวิธีที่ทำได้คือ ใช้ iterative method เหมือนที่เรียนในสัปดาห์ที่แล้ว แต่ก่อนที่จะทำนั้น เราจะหาเมทริกซ์ B ที่มีคุณสมบัติ.... มาคูณทั้งสองฝั่ง
ทำให้การแก้สมการ Ax = b กลายเป็นการแก้สมการ เพื่อให้ทำ iterative method ได้เร็วขึ้น