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

ในเรื่องเมทริกซ์ **การแยกแบบโชเลสกี** () ซึ่งตั้งชื่อตาม อ็องเดร หลุยส์ โชเลสกี นักคณิตศาสตร์ชาวฝรั่งเศส เป็นวิธีการแยกเมทริกซ์ของเมทริกซ์สมมาตรที่เป็นบวกแน่นอน (Symmetric positive-definite matrix) ไปเป็น เมทริกซ์สามเหลี่ยมล่าง (Lower triangular matrix) และ เมทริกซ์สลับเปลี่ยนของเมทริกซ์สามเหลี่ยมล่าง

เมทริกซ์จัตุรัส (Square Matrix) ใด ๆ **A** สามารถเขียนให้อยู่ในรูปผลคูณของ เมทริกซ์สามเหลี่ยมล่าง **L** และ เมทริกซ์สามเหลี่ยมบน (Upper triangular matrix) **U** หรือเรียกว่า การแยกแบบแอลยู (LU decomposition) ซึ่งหาก **A** เป็นเมทริกซ์สมมาตรที่เป็นบวกแน่นอนแล้ว เราสามารถหาเมทริกซ์ **U** ที่เป็นเมทริกซ์สลับเปลี่ยนของ **L** ได้ เรียกวิธีนี้ว่า *การแยกแบบโชเลสกี*

ทั้งวิธีการแยกแบบแอลยู และ แบบโชเลสกี ใช้ในการแก้ปัญหาเรื่องสมการเชิงเส้น โดยวิธีการแยกแบบโชเลสกีจะมีประสิทธิภาพมากกว่า

## นิยาม
ให้ **A** เป็นเมทริกซ์สมมาตรที่เป็นบวกแน่นอนของจำนวนจริง ดังนั้น **A** สามารถแยกเป็น

: \mathbf{A} = \mathbf{L} \mathbf{L}^{\top}

โดยที่ **L** คือ เมทริกซ์สามเหลี่ยมล่างที่สมาชิกแนวทแยงมุมมีค่าเป็นบวก และ **L**T คือ เมทริกซ์สลับเปลี่ยนของ **L**

## ส่วนขยายจำนวนเชิงซ้อน
จากนิยามข้างบนสามารถขยายไปยังเมทริกซ์ของจำนวนเชิงซ้อนได้โดย ถ้า **A** เป็นเมทริกซ์ผูกพันในตัว (Self-adjoint matix หรือ Hermitian matrix) และเป็นบวกแน่นอนแล้ว **A** สามารถแยกได้เป็น

: \mathbf{A} = \mathbf{L} \mathbf{L}^{*}

โดยที่ **L*** คือ เมทริกซ์สลับเปลี่ยนสังยุค (Conjugate transpose) ของ **L**

การแยกแบบโชเลสกีมีคุณสมบัติความเป็นหนึ่งเดียวกล่าวคือ ถ้า **A** เป็นเมทริกซ์ผูกพันในตัวและเป็นบวกแน่นอนแล้ว จะมีเมทริกซ์สามเหลี่ยมล่างที่มีสมาชิกแนวทแยงมุมเป็นบวก **L** เพียงตัวเดียวเท่านั้นที่ทำให้ **A** = **LL*** ในทางกลับกัน ถ้า **A** สามารถแยกได้เป็น **LL*** โดยที่ **L** เป็นเมทริกซ์สามเหลี่ยมล่างที่มีสมาชิกแนวทแยงมุมเป็นบวกแล้ว **A** จะเป็นเมทริกซ์ผูกพันในตัวและเป็นบวกแน่นอน

## การประยุกต์ใช้
การแยกแบบโชเลสกีส่วนใหญ่ใช้ในการแก้ปัญหาสมการเชิงเส้น **Ax** = **b** ถ้าเมทริกซ์ **A** สมมาตรและเป็นบวกแน่นอน เราสามารถแก้ปัญหา **Ax** = **b** โดยเริ่มแรกการคำนวณการแยกแบบโชเลสกี **A** = **LL**T จากนั้นหา **y** ที่ทำให้ **Ly** = **b** และสุดท้ายหา **x** ที่ทำให้ **L**T**x** = **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 และ
: \mathbf{A}^{(1)} := \mathbf{A}.

ที่ขั้นตอน *i*, เมทริกซ์ **A** (*i*)  มีรูปแบบดังนี้:
: \mathbf{A}^{(i)}
= 
\begin{pmatrix}
\mathbf{I}_{i-1} & 0 & 0 \\
0 & a_{i,i} & \mathbf{b}_{i}^{*} \\
0 & \mathbf{b}_{i} & \mathbf{B}^{(i)}
\end{pmatrix}

โดยที่ **I***i*−1 คือ เมทริกซ์เอกลักษณ์ ที่มีขนาด *i* − 1.

ถ้าเรากำหนดให้เมทริกซ์ **L***i* โดยที่
: \mathbf{L}_{i}
: = 
\begin{pmatrix}
\mathbf{I}_{i-1} & 0 & 0 \\
0 & \sqrt{a_{i,i}} & 0 \\
0 & \frac{1}{\sqrt{a_{i,i}}} \mathbf{b}_{i} & \mathbf{I}_{n-i}
\end{pmatrix}

แล้วเราสามารถเขียน **A** (*i*)  เป็น
: 
\mathbf{A}^{(i)} = \mathbf{L}_{i} \mathbf{A}^{(i+1)} \mathbf{L}_{i}^{*}

โดยที่
: 
\mathbf{A}^{(i+1)}
= 
\begin{pmatrix}
\mathbf{I}_{i-1} & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & \mathbf{B}^{(i)} - \frac{1}{a_{i,i}} \mathbf{b}_{i} \mathbf{b}_{i}^{*}
\end{pmatrix}


สังเกตว่า **b***i* **b***i** คือ ผลคูณภายนอก ดังนั้นเราจึงเรียกวิธีนี้ว่า *รูปแบบผลคูณภายนอก* (Outer product version)

เราทำซ้ำตามวิธีการนี้ตั้งแต่ *i* เท่ากับ 1 จนถึง *n* โดยหลังจากจบขั้นตอนที่ *n* จะได้ **A** (*n*+1)  = **I** ดังนั้น เมทริกซ์สามเหลี่ยมล่าง *L* ที่ต้องการคำนวณได้จาก
: \mathbf{L} := \mathbf{L}_{1} \mathbf{L}_{2} \dots \mathbf{L}_{n}

## ดูเพิ่ม
* วิธีการคำนวณเชิงตัวเลข (Numerical method)

หมวดหมู่:คณิตศาสตร์