ผลต่างระหว่างรุ่นของ "การแยกแบบโชเลสกี"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข |
|||
บรรทัด 29:
==วิธีการคำนวณ==
การแยกแบบโซเลสกี้มีวิธีคำนวณหลายแบบ ขั้นตอนวิธีที่อธิบายข้างล่างทั้งหมดนั้นใช้ ''n''<sup>3</sup>/3 [[ฟล็อปส์]](FLOPS) โดยที่ n คือขนาดของเมทริกซ์ '''A''' ดังนั้นการแยกแบบโซเลสกี้จึงมีประสิทธิภาพมากกว่าถึงสองเท่าเทียบกับการแยกแบบแอลยูซึ่งใช้ ''2n''<sup>3</sup>/3 ฟล็อปส์
===ขั้นตอนวิธีโซเลสกี้===
'''ขั้นตอนวิธีโซเลสกี้'''(Cholesky algorithm) เป็นวิธีการหาเมทริกซ์ '''L''' โดยปรับปรุงมาจาก[[ขั้นตอนวิธีเกาส์]]
ขั้นตอนวิธีเรียกซ้ำเริ่มต้นโดยให้ ''i'' := 1 และ
:<math>\mathbf{A}^{(1)} := \mathbf{A}.</math>
ที่ขั้นตอน ''i'', เมทริกซ์ '''A'''<sup>(''i'')</sup> มีรูปแบบดังนี้:
:<math>\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},
</math>
โดยที่ '''I'''<sub>''i''−1</sub> คือ [[เมทริกซ์เอกลักษณ์]] ที่มีขนาด ''i'' − 1.
ถ้าเรากำหนดให้เมทริกซ์ '''L'''<sub>''i''<sub> โดยที่
:<math>\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},
</math>
แล้วเราสามารถเขียน '''A'''<sup>(''i'')</sup> เป็น
:<math>
\mathbf{A}^{(i)} = \mathbf{L}_{i} \mathbf{A}^{(i+1)} \mathbf{L}_{i}^{*}
</math>
โดยที่
:<math>
\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}.
</math>
สังเกตว่า '''b'''<sub>''i''</sub> '''b'''<sub>''i''</sub><sup>*</sup> คือ ผลคูณภายนอก ดังนั้นเราจึงเรียกวิธีนี้ว่า ''รูปแบบผลคูณภายนอก''(Outer product version)
เราทำซ้ำตามวิธีการนี้ตั้งแต่ ''i'' เท่ากับ 1 จนถึง ''n'' โดยหลังจากจบขั้นตอนที่ ''n'' จะได้ '''A'''<sup>(''n''+1)</sup> = '''I''' ดังนั้น เมทริกซ์สามเหลี่ยมล่าง ''L'' ที่ต้องการคำนวณได้จาก
:<math>\mathbf{L} := \mathbf{L}_{1} \mathbf{L}_{2} \dots \mathbf{L}_{n}.</math>
{{โครงคณิตศาสตร์}}
| |||