การแยกแบบโซเลสกี้

จากวิกิพีเดีย สารานุกรมเสรี

ในเรื่องเมทริกซ์ การแยกแบบโซเลสกี้ (Cholesky decomposition) ซึ่งตั้งชื่อตาม หลุยส์ อังเดร โซเลสกี้ นักคณิตศาสตร์ชาวฝรั่งเศส เป็นวิธีการแยกเมทริกซ์ของเมทริกซ์สมมาตรที่เป็นบวกแน่นอน(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 คือ เมทริกซ์สามเหลี่ยมล่างที่สมาชิกแนวทแยงมุมมีค่าเป็นบวก และ LT คือ เมทริกซ์สลับเปลี่ยนของ 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 = LLT จากนั้นหา y ที่ทำให้ Ly = b และสุดท้ายหา x ที่ทำให้ LTx = y

ระบบที่มีรูปแบบ Ax = b โดยที่ A สมมาตรและเป็นบวกแน่นอน เกิดขึ้นบ่อยครั้งในการประยุกต์ใช้ ยกตัวอย่างเช่น สมการทั่วไปในเรื่องกำลังสองน้อยสุดเชิงเส้น(linear least square) หรืออาจพบในเรื่องเกี่ยวกับฟังก์ชันพลังงานซึ่งต้องเป็นบวกในทางฟิสิกส์ และเกิดขึ้นบ่อยครั้งในการแก้ปัญหาเชิงตัวเลขของสมการเชิงอนุพันธ์ย่อย(Partial differential equation)

การแยกแบบโซเลสกี้ยังใช้ในเรื่อง วิธีมอนติคาร์โล (Monte Carlo method) ในการจำลองระบบที่มีหลายตัวแปรสัมพันธ์กัน โดยเมทริกซ์สหสัมพันธ์(Correlation)ระหว่างตัวแปรจะถูกแยกเพื่อหาเมทริกซ์สามเหลี่ยมล่าง L เพื่อใช้กับเวกเตอร์ของช็อกจำลองที่ไม่สัมพันธ์กัน(Uncorrelated simulated shock) u ทำให้ได้ช็อกเวกเตอร์(Shock vector) Lu มี่มีคุณสมบัติความแปรปรวนร่วมเกี่ยว(Covariance)ของระบบที่เรากำลังจำลองอยู่

[แก้] วิธีการคำนวณ

การแยกแบบโซเลสกี้มีวิธีคำนวณหลายแบบ ขั้นตอนวิธีที่อธิบายข้างล่างทั้งหมดนั้นใช้ n3/3 ฟล็อปส์(FLOPS) โดยที่ n คือขนาดของเมทริกซ์ A ดังนั้นการแยกแบบโซเลสกี้จึงมีประสิทธิภาพมากกว่าถึงสองเท่าเทียบกับการแยกแบบแอลยูซึ่งใช้ 2n3/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},

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

ถ้าเรากำหนดให้เมทริกซ์ Li โดยที่

\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}.

สังเกตว่า bi bi* คือ ผลคูณภายนอก ดังนั้นเราจึงเรียกวิธีนี้ว่า รูปแบบผลคูณภายนอก(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)



  การแยกแบบโซเลสกี้ เป็นบทความเกี่ยวกับ คณิตศาสตร์ ที่ยังไม่สมบูรณ์ ต้องการตรวจสอบ เพิ่มเนื้อหา หรือเพิ่มแหล่งอ้างอิง คุณสามารถช่วยเพิ่มเติมหรือแก้ไข เพื่อให้สมบูรณ์มากขึ้น
ข้อมูลเกี่ยวกับ การแยกแบบโซเลสกี้ ในภาษาอื่น สามารถหาอ่านได้จากเมนู ภาษาอื่น ๆ ด้านซ้ายมือ
ภาษาอื่น