การแยกแบบโชเลสกี

ในเรื่องเมทริกซ์ การแยกแบบโชเลสกี  ซึ่งตั้งชื่อตาม อ็องเดร หลุยส์ โชเลสกี นักคณิตศาสตร์ชาวฝรั่งเศส เป็นวิธีการแยกเมทริกซ์ของเมทริกซ์สมมาตรที่เป็นบวกแน่นอน (Symmetric positive-definite matrix) ไปเป็น เมทริกซ์สามเหลี่ยมล่าง (Lower triangular matrix) และ เมทริกซ์สลับเปลี่ยนของเมทริกซ์สามเหลี่ยมล่าง
เมทริกซ์จัตุรัส (Square Matrix) ใด ๆ A สามารถเขียนให้อยู่ในรูปผลคูณของ เมทริกซ์สามเหลี่ยมล่าง L และ เมทริกซ์สามเหลี่ยมบน (Upper triangular matrix) U หรือเรียกว่า การแยกแบบแอลยู (LU decomposition) ซึ่งหาก A เป็นเมทริกซ์สมมาตรที่เป็นบวกแน่นอนแล้ว เราสามารถหาเมทริกซ์ U ที่เป็นเมทริกซ์สลับเปลี่ยนของ L ได้ เรียกวิธีนี้ว่า "การแยกแบบโชเลสกี"
ทั้งวิธีการแยกแบบแอลยู และ แบบโชเลสกี ใช้ในการแก้ปัญหาเรื่องสมการเชิงเส้น โดยวิธีการแยกแบบโชเลสกีจะมีประสิทธิภาพมากกว่า
นิยาม.
ให้ A เป็นเมทริกซ์สมมาตรที่เป็นบวกแน่นอนของจำนวนจริง ดังนั้น A สามารถแยกเป็น
 <math>\mathbf{A} = \mathbf{L} \mathbf{L}^{\top}</math>
โดยที่ L คือ เมทริกซ์สามเหลี่ยมล่างที่สมาชิกแนวทแยงมุมมีค่าเป็นบวก และ LT คือ เมทริกซ์สลับเปลี่ยนของ L
ส่วนขยายจำนวนเชิงซ้อน.
จากนิยามข้างบนสามารถขยายไปยังเมทริกซ์ของจำนวนเชิงซ้อนได้โดย ถ้า A เป็นเมทริกซ์ผูกพันในตัว (Self-adjoint matix หรือ Hermitian matrix) และเป็นบวกแน่นอนแล้ว A สามารถแยกได้เป็น
 <math>\mathbf{A} = \mathbf{L} \mathbf{L}^{*}</math>
โดยที่ L* คือ เมทริกซ์สลับเปลี่ยนสังยุค (Conjugate transpose) ของ L
การแยกแบบโชเลสกีมีคุณสมบัติความเป็นหนึ่งเดียวกล่าวคือ ถ้า A เป็นเมทริกซ์ผูกพันในตัวและเป็นบวกแน่นอนแล้ว จะมีเมทริกซ์สามเหลี่ยมล่างที่มีสมาชิกแนวทแยงมุมเป็นบวก L เพียงตัวเดียวเท่านั้นที่ทำให้ A = LL* ในทางกลับกัน ถ้า A สามารถแยกได้เป็น LL* โดยที่ L เป็นเมทริกซ์สามเหลี่ยมล่างที่มีสมาชิกแนวทแยงมุมเป็นบวกแล้ว A จะเป็นเมทริกซ์ผูกพันในตัวและเป็นบวกแน่นอน
การประยุกต์ใช้.
การแยกแบบโชเลสกีส่วนใหญ่ใช้ในการแก้ปัญหาสมการเชิงเส้น Ax = b ถ้าเมทริกซ์ A สมมาตรและเป็นบวกแน่นอน เราสามารถแก้ปัญหา Ax = b โดยเริ่มแรกการคำนวณการแยกแบบโชเลสกี A = LLT จากนั้นหา y ที่ทำให้ Ly = b และสุดท้ายหา x ที่ทำให้ LTx = y
ระบบที่มีรูปแบบ Ax = b โดยที่ A สมมาตรและเป็นบวกแน่นอน เกิดขึ้นบ่อยครั้งในการประยุกต์ใช้ ยกตัวอย่างเช่น สมการทั่วไปในเรื่องกำลังสองน้อยสุดเชิงเส้น (linear least square) หรืออาจพบในเรื่องเกี่ยวกับฟังก์ชันพลังงานซึ่งต้องเป็นบวกในทางฟิสิกส์ และเกิดขึ้นบ่อยครั้งในการแก้ปัญหาเชิงตัวเลขของสมการเชิงอนุพันธ์ย่อย (Partial differential equation)
การแยกแบบโชเลสกียังใช้ในเรื่องวิธีมอนเตการ์โล ในการจำลองระบบที่มีหลายตัวแปรสัมพันธ์กัน โดยเมทริกซ์สหสัมพันธ์ (Correlation) ระหว่างตัวแปรจะถูกแยกเพื่อหาเมทริกซ์สามเหลี่ยมล่าง L เพื่อใช้กับเวกเตอร์ของช็อกจำลองที่ไม่สัมพันธ์กัน (Uncorrelated simulated shock) u ทำให้ได้ช็อกเวกเตอร์ (Shock vector) Lu มี่มีคุณสมบัติความแปรปรวนร่วมเกี่ยว (Covariance) ของระบบที่เรากำลังจำลองอยู่
วิธีการคำนวณ.
การแยกแบบโชเลสกีมีวิธีคำนวณหลายแบบ ขั้นตอนวิธีที่อธิบายข้างล่างทั้งหมดนั้นใช้ "n"3/3 ฟล็อปส์ (FLOPS) โดยที่ n คือขนาดของเมทริกซ์ A ดังนั้นการแยกแบบอจึงมีประสิทธิภาพมากกว่าถึงสองเท่าเทียบกับการแยกแบบแอลยูซึ่งใช้ "2n"3/3 ฟล็อปส์
ขั้นตอนวิธีอ.
ขั้นตอนวิธีโชเลสกี (Cholesky algorithm) เป็นวิธีการหาเมทริกซ์ L โดยปรับปรุงมาจากขั้นตอนวิธีเกาส์
ขั้นตอนวิธีเรียกซ้ำเริ่มต้นโดยให้ "i" := 1 และ
 <math>\mathbf{A}^{(1)} := \mathbf{A}.</math>
ที่ขั้นตอน "i", เมทริกซ์ A ("i") มีรูปแบบดังนี้:
 <math>\mathbf{A}^{(i)}
\mathbf{I}_{i-1} & 0 & 0 \\
0 & a_{i,i} & \mathbf{b}_{i}^{*} \\
</math>
โดยที่ I"i"−1 คือ เมทริกซ์เอกลักษณ์ ที่มีขนาด "i" − 1.
ถ้าเรากำหนดให้เมทริกซ์ L"i" โดยที่
 <math>\mathbf{L}_{i}
\mathbf{I}_{i-1} & 0 & 0 \\
0 & \sqrt{a_{i,i}} & 0 \\
</math>
แล้วเราสามารถเขียน A ("i") เป็น
 <math>
</math>
โดยที่
 <math>
\mathbf{I}_{i-1} & 0 & 0 \\
0 & 1 & 0 \\
</math>
สังเกตว่า b"i" b"i"* คือ ผลคูณภายนอก ดังนั้นเราจึงเรียกวิธีนี้ว่า "รูปแบบผลคูณภายนอก" (Outer product version)
เราทำซ้ำตามวิธีการนี้ตั้งแต่ "i" เท่ากับ 1 จนถึง "n" โดยหลังจากจบขั้นตอนที่ "n" จะได้ A ("n"+1) = I ดังนั้น เมทริกซ์สามเหลี่ยมล่าง "L" ที่ต้องการคำนวณได้จาก
 <math>\mathbf{L} := \mathbf{L}_{1} \mathbf{L}_{2} \dots \mathbf{L}_{n}</math>