อัลกอริทึมค่าลักษณะเฉพาะแบบแบ่งและพิชิต

อัลกอริทึมหาค่าลักษณะเฉพาะ แบบแบ่งและพิชิต (Divide-and-conquer eigenvalue algorithms)เป็นกลุ่มของอัลกอริ ทึมหาค่าลักษณะเฉพาะ สำหรับ เมทริก ซ์เฮอร์มิเชียนหรือเมทริกซ์สมมาตรจริง ซึ่งในช่วงไม่กี่ปีมานี้ (ประมาณทศวรรษ 1990) ได้กลายเป็นอัลกอริทึมที่แข่งขันได้ในแง่ของความเสถียรและประสิทธิภาพกับอัลกอริทึมแบบดั้งเดิม เช่นอัลกอริทึม QRแนวคิดพื้นฐานของอัลกอริทึมเหล่านี้คือ วิธี การแบ่งและพิชิตจากวิทยาการคอมพิวเตอร์ปัญหาค่าลักษณะเฉพาะจะถูกแบ่งออกเป็นสองปัญหาที่มีขนาดประมาณครึ่งหนึ่งของปัญหาหลัก แต่ละปัญหาจะถูกแก้แบบเรียกซ้ำและค่าลักษณะเฉพาะของปัญหาหลักจะถูกคำนวณจากผลลัพธ์ของปัญหาที่เล็กกว่าเหล่านี้

บทความนี้กล่าวถึงแนวคิดพื้นฐานของอัลกอริธึมตามที่ Cuppen เสนอไว้ครั้งแรกในปี 1981 ซึ่งไม่เสถียรในเชิงตัวเลขหากไม่มีการปรับปรุงเพิ่มเติม

เช่นเดียวกับอัลกอริธึมหาค่าลักษณะเฉพาะส่วนใหญ่สำหรับเมทริกซ์เฮอร์มิเชียน วิธีการแบ่งและพิชิตเริ่มต้นด้วยการลดรูปให้อยู่ใน รูปแบบเมทริกซ์ สามแถวสำหรับเมทริกซ์ วิธีมาตรฐานสำหรับวิธีนี้ ผ่านการสะท้อนของ Householderจะใช้การคำนวณเลขทศนิยม หรือหาก ต้องการ เวกเตอร์ลักษณะเฉพาะด้วยก็เช่นกัน มีอัลกอริธึมอื่นๆ เช่นการวนซ้ำของ Arnoldiซึ่งอาจทำงานได้ดีกว่าสำหรับเมทริกซ์บางประเภท เราจะไม่พิจารณาเรื่องนี้เพิ่มเติมในที่นี้ ${\displaystyle m\times m}$${\displaystyle {\frac {4}{3}}ม^{3}}$${\displaystyle {\frac {8}{3}}ม^{3}}$

ในบางกรณี เราสามารถลดทอนปัญหาค่าลักษณะเฉพาะให้เป็นปัญหาย่อยๆ ได้ ลองพิจารณาเมทริกซ์บล็อกแนวทแยง

${\displaystyle T={\begin{bmatrix}T_{1}&0\\0&T_{2}\end{bmatrix}}.}$

ค่าลักษณะเฉพาะและเวกเตอร์ลักษณะเฉพาะของ นั้นก็คือค่าลักษณะเฉพาะและเวกเตอร์ลักษณะเฉพาะของ และ นั่นเองและโดยส่วนใหญ่แล้ว การแก้ปัญหาเล็กๆ สองปัญหานี้จะเร็วกว่าการแก้ปัญหาดั้งเดิมทั้งหมดในคราวเดียว เทคนิคนี้สามารถนำไปใช้เพื่อเพิ่มประสิทธิภาพของอัลกอริธึมหาค่าลักษณะเฉพาะหลายๆ อย่างได้ แต่มีความสำคัญเป็นพิเศษสำหรับหลักการแบ่งและพิชิต (divide-and-conquer) ${\displaystyle T}$${\displaystyle T_{1}}$${\displaystyle T_{2}}$

สำหรับส่วนที่เหลือของบทความนี้ เราจะถือว่าอินพุตของอัลกอริทึมแบบแบ่งและพิชิตคือเมทริกซ์สมมาตรสามแถวที่เป็นจำนวนจริงอัลกอริทึมนี้สามารถปรับเปลี่ยนได้สำหรับเมทริกซ์เฮอร์มิเชียน ${\displaystyle m\times m}$${\displaystyle T}$

ส่วน การหารในอัลกอริธึมแบบ แบ่งและพิชิต มาจากการตระหนักว่าเมทริกซ์สามแถวนั้น "เกือบ" เป็นเมทริกซ์บล็อกแนวทแยง

ขนาดของเมทริกซ์ย่อยที่เราจะเรียกว่าและคือซึ่ง เกือบจะเป็นเมทริกซ์แนวทแยงมุมแบบบล็อก ไม่ว่า จะเลือกอย่างไรก็ตาม เพื่อประสิทธิภาพ เรามักจะ เลือก ${\displaystyle T_{1}}$${\displaystyle n\times n}$${\displaystyle T_{2}}$${\displaystyle (mn)\times (mn)}$${\displaystyle T}$${\displaystyle n}$${\displaystyle n\approx m/2}$

เราเขียนในรูปแบบเมทริกซ์บล็อกแนวทแยง พร้อมกับ การแก้ไข อันดับ 1 : ${\displaystyle T}$

ความแตกต่างเพียงอย่างเดียวระหว่างและคือ รายการด้านล่างขวาในถูกแทนที่ด้วยและในทำนองเดียวกันรายการด้านบนซ้ายใน ถูกแทนที่ด้วย ${\displaystyle T_{1}}$${\displaystyle {\hat {T}}_{1}}$${\displaystyle t_{nn}}$${\displaystyle {\hat {T}}_{1}}$${\displaystyle t_{nn}-\beta }$${\displaystyle {\hat {T}}_{2}}$${\displaystyle t_{n+1,n+1}}$${\displaystyle t_{n+1,n+1}-\beta }$

ส่วนที่เหลือของขั้นตอนการหารคือการหาค่าลักษณะเฉพาะ (และถ้าต้องการเวกเตอร์ลักษณะเฉพาะ) ของและนั่นคือการหาเมทริกซ์ทแยงมุมและซึ่งสามารถทำได้โดยการเรียกซ้ำของอัลกอริทึมแบบแบ่งและพิชิต แม้ว่าการใช้งานจริงมักจะเปลี่ยนไปใช้อัลกอริทึม QR ที่เลื่อนโดยปริยายสำหรับเมทริกซ์ย่อยที่มีขนาดเล็กพอ^{[ 1 ]}${\displaystyle {\hat {T}}_{1}}$${\displaystyle {\hat {T}}_{2}}$${\displaystyle {\hat {T}}_{1}=Q_{1}D_{1}Q_{1}^{T}}$${\displaystyle {\hat {T}}_{2}=Q_{2}D_{2}Q_{2}^{T}}$

ส่วน "พิชิต " ของอัลกอริธึมนี้เป็นส่วนที่ไม่ค่อยเข้าใจง่ายนัก เมื่อทราบค่าเมทริกซ์ทแยงมุมของเมทริกซ์ย่อยที่คำนวณไว้ข้างต้นแล้ว เราจะหาค่าเมทริกซ์ทแยงมุมของเมทริกซ์ต้นฉบับได้อย่างไร?

ขั้นแรก กำหนดให้โดยที่คือแถวสุดท้ายของและคือแถวแรกของ จากนั้นจึงสามารถแสดงได้อย่างง่ายดายว่า ${\displaystyle z^{T}=(q_{1}^{T},q_{2}^{T})}$${\displaystyle q_{1}^{T}}$${\displaystyle Q_{1}}$${\displaystyle q_{2}^{T}}$${\displaystyle Q_{2}}$

${\displaystyle T={\begin{bmatrix}Q_{1}&\\&Q_{2}\end{bmatrix}}\left({\begin{bmatrix}D_{1}&\\&D_{2}\end{bmatrix}}+\beta zz^{T}\right){\begin{bmatrix}Q_{1}^{T}&\\&Q_{2}^{T}\end{bmatrix}}}$

งานที่เหลืออยู่คือการค้นหาค่าไอเกนของเมทริกซ์แนวทแยงบวกกับการแก้ไขอันดับหนึ่ง ก่อนที่จะแสดงวิธีการทำเช่นนั้น เรามาทำให้สัญลักษณ์ง่ายขึ้นก่อน เรากำลังมองหาค่าไอเกนของเมทริกซ์โดยที่เป็นเมทริกซ์แนวทแยงที่มีสมาชิกแตกต่างกัน และเป็นเวกเตอร์ใดๆ ที่มีสมาชิกไม่เป็นศูนย์ ในกรณีนี้ ${\displaystyle D+ww^{T}}$${\displaystyle D}$${\displaystyle w}$${\displaystyle w={\sqrt {|\beta |}}\cdot z}$

กรณีที่รายการเป็นศูนย์นั้นง่าย เนื่องจากถ้า w _iเป็นศูนย์ ( ,d _i ) จะเป็นคู่ค่าลักษณะเฉพาะ ( อยู่ในฐานมาตรฐาน) ของเนื่องจาก . ${\displaystyle e_{i}}$${\displaystyle e_{i}}$${\displaystyle D+ww^{T}}$${\displaystyle (D+ww^{T})e_{i}=De_{i}=d_{i}e_{i}}$

ถ้าเป็นค่าลักษณะเฉพาะ เราจะได้ว่า: ${\displaystyle \lambda }$

${\displaystyle (D+ww^{T})q=\lambda q}$

เวกเตอร์ลักษณะเฉพาะที่สอดคล้องกันอยู่ ที่ไหน ตอนนี้${\displaystyle q}$

${\displaystyle (D-\lambda I)q+w(w^{T}q)=0}$

${\displaystyle q+(D-\lambda I)^{-1}w(w^{T}q)=0}$

${\displaystyle w^{T}q+w^{T}(D-\lambda I)^{-1}w(w^{T}q)=0}$

โปรดจำไว้ว่าเป็นค่าสเกลาร์ที่ไม่เป็นศูนย์ ทั้ง และไม่เป็นศูนย์ ถ้าเป็นศูนย์จะเป็นเวกเตอร์ลักษณะเฉพาะของโดยถ้าเป็นเช่นนั้นจะมีตำแหน่งที่ไม่เป็นศูนย์เพียงตำแหน่งเดียว เนื่องจากเป็นเส้นทแยงมุมที่แตกต่างกัน ดังนั้นผลคูณภายในจึงไม่สามารถเป็นศูนย์ได้ ดังนั้นเราจึงได้: ${\displaystyle w^{T}q}$${\displaystyle w}$${\displaystyle q}$${\displaystyle w^{T}q}$${\displaystyle q}$${\displaystyle D}$${\displaystyle (D+ww^{T})q=\lambda q}$${\displaystyle q}$${\displaystyle D}$${\displaystyle w^{T}q}$

${\displaystyle 1+w^{T}(D-\แลมบ์ดา I)^{-1}w=0}$

หรือเขียนในรูปสมการสเกลาร์

${\displaystyle 1+\sum _{j=1}^{m}{\frac {w_{j}^{2}}{d_{j}-\lambda }}=0.}$

สมการนี้เรียกว่าสมการเชิงตรรกะดังนั้นปัญหาจึงลดลงเหลือเพียงการหาค่ารากของฟังก์ชันตรรกยะที่กำหนดโดยด้านซ้ายของสมการนี้

การแก้สม การเชิงฆราวาส ที่ไม่เป็นเชิงเส้นสามารถทำได้โดยใช้วิธีการวนซ้ำ เช่นวิธี Newton–Raphsonอย่างไรก็ตาม รากแต่ละรากสามารถหาได้ใน การวนซ้ำ O (1) ซึ่งแต่ละครั้งต้องใช้การคำนวณ (สำหรับฟังก์ชันตรรกยะดีกรี -) ทำให้ต้นทุนของส่วนการวนซ้ำของอัลกอริทึมนี้สูง ขึ้น วิธีมัลติโพลแบบเร็วก็ถูกนำมาใช้เพื่อแก้สมการเชิงฆราวาสในการดำเนินการเช่นกัน^{[ 2 ] [ 1 ]}${\displaystyle \Theta (m)}$${\displaystyle m}$${\displaystyle \Theta (m^{2})}$${\displaystyle \Theta (m\log(m))}$

W จะใช้ทฤษฎีบทหลักสำหรับความสัมพันธ์เวียนเกิดแบบแบ่งและพิชิตเพื่อวิเคราะห์เวลาการทำงาน โปรดจำไว้ว่าข้างต้นเราได้ระบุว่าเราเลือกเราสามารถเขียนความสัมพันธ์เวียนเกิดได้ดังนี้: ${\displaystyle n\approx m/2}$

${\displaystyle T(m)=2\times T\left({\frac {m}{2}}\right)+\Theta (m^{2})}$

ในสัญลักษณ์ของทฤษฎีบทมาสเตอร์และดังนั้นเห็นได้ชัดว่าดังนั้นเราจึงมี ${\displaystyle a=b=2}$${\displaystyle \log _{b}a=1}$${\displaystyle \Theta (m^{2})=\Omega (m^{1})}$

${\displaystyle T(m)=\Theta (m^{2})}$

ข้างต้น เราได้ชี้ให้เห็นว่าการลดเมทริกซ์เฮอร์มิเชียนให้เป็นรูปแบบเมทริกซ์สามแถวต้องใช้การคำนวณแบบฟล็อป ซึ่งทำให้เวลาในการทำงานของส่วนแบ่งและพิชิตนั้นน้อยลงไปมาก และในจุดนี้ยังไม่ชัดเจนว่าอัลกอริทึมแบบแบ่งและพิชิตมีข้อดีอะไรเหนือกว่าอัลกอริทึม QR (ซึ่งก็ใช้การคำนวณแบบฟล็อปสำหรับเมทริกซ์สามแถวเช่นกัน) ${\displaystyle {\frac {4}{3}}m^{3}}$${\displaystyle \Theta (m^{2})}$

ข้อดีของการแบ่งและพิชิต (divide-and-conquer) จะเกิดขึ้นเมื่อต้องการเวกเตอร์ลักษณะเฉพาะ (eigenvectors) ด้วย ในกรณีเช่นนี้ การลดรูปให้อยู่ในรูปแบบเมทริกซ์สามแถว (tridiagonal form) จะใช้เวลาแต่ส่วนที่สองของอัลกอริทึมก็ใช้เวลาเช่นกัน สำหรับอัลกอริทึม QR ที่มีความแม่นยำเป้าหมายที่เหมาะสม จะใช้เวลา ในขณะที่สำหรับการแบ่งและพิชิตจะ ใช้เวลา เหตุผลของการปรับปรุงนี้คือ ในการแบ่งและพิชิตส่วนของอัลกอริทึม (การคูณเมทริกซ์) จะแยกออกจากการวนซ้ำ ในขณะที่ใน QR จะต้องเกิดขึ้นในทุกขั้นตอนการวนซ้ำ เมื่อรวมการคำนวณสำหรับการลดรูป การปรับปรุงโดยรวมจะเปลี่ยนจากเป็นการคำนวณ ${\displaystyle {\frac {8}{3}}m^{3}}$${\displaystyle \Theta (m^{3})}$${\displaystyle \approx 6m^{3}}$${\displaystyle \approx {\frac {4}{3}}m^{3}}$${\displaystyle \Theta (m^{3})}$${\displaystyle Q}$${\displaystyle {\frac {8}{3}}m^{3}}$${\displaystyle \approx 9m^{3}}$${\displaystyle \approx 4m^{3}}$

การใช้งานจริงของอัลกอริทึมแบบแบ่งและพิชิตแสดงให้เห็นว่า ในปัญหาค่าลักษณะเฉพาะที่สมจริงส่วนใหญ่ อัลกอริทึมนี้ทำงานได้ดีกว่าที่คาดการณ์ไว้ เหตุผลก็คือ บ่อยครั้งที่เมทริกซ์และเวกเตอร์มีแนวโน้มที่จะมีความเบาบางเชิงตัวเลขหมายความว่า มีค่าจำนวนมากที่มีค่าน้อยกว่า ความแม่นยำ ของเลขทศนิยมทำให้สามารถลดขนาดเชิงตัวเลข ได้ กล่าวคือ การแบ่งปัญหาออกเป็นปัญหาย่อยที่ไม่เกี่ยวข้องกัน ${\displaystyle Q}$${\displaystyle z}$

อัลกอริทึมที่นำเสนอในที่นี้เป็นเวอร์ชันที่ง่ายที่สุด ในการใช้งานจริงหลายๆ ครั้ง จะใช้การแก้ไขอันดับ 1 ที่ซับซ้อนกว่านี้เพื่อรับประกันความเสถียร บางเวอร์ชันยังใช้การแก้ไขอันดับ 2 อีกด้วย

มีเทคนิคการหาค่ารากเฉพาะสำหรับฟังก์ชันตรรกยะที่อาจให้ผลลัพธ์ที่ดีกว่าวิธีนิวตัน-ราฟสัน ทั้งในด้านประสิทธิภาพและความเสถียร เทคนิคเหล่านี้สามารถนำมาใช้ปรับปรุงส่วนการวนซ้ำของอัลกอริทึมแบบแบ่งและพิชิตได้

อัลกอริทึมแบบแบ่งและพิชิตสามารถประมวลผลแบบขนาน ได้อย่างง่ายดาย และ แพ็กเกจการคำนวณ พีชคณิตเชิงเส้นเช่นLAPACKมีการใช้งานแบบขนานที่มีคุณภาพสูง