ในทางคณิตศาสตร์การวนซ้ำกำลัง (หรือที่รู้จักกันในชื่อวิธีกำลัง ) เป็นอัลกอริทึมค่าลักษณะเฉพาะ : เมื่อกำหนดเมทริกซ์ที่สามารถทำให้เป็นแนวทแยงได้ อัลกอริทึมจะสร้างจำนวน ซึ่งเป็นค่า ลักษณะเฉพาะที่มากที่สุด (ในค่าสัมบูรณ์) ของและเวกเตอร์ที่ไม่เป็นศูนย์ซึ่งเป็นเวกเตอร์ลักษณะ เฉพาะที่สอดคล้องกัน ของนั่นคืออัลกอริทึมนี้ยังเป็นที่รู้จักในชื่อการวนซ้ำของVon Mises ^{[ 1 ]}${\displaystyle A}$${\displaystyle \lambda }$${\displaystyle A}$${\displaystyle v}$${\displaystyle \lambda }$${\displaystyle Av=\lambda v}$

การวนซ้ำกำลัง (Power iteration) เป็นอัลกอริธึมที่ง่ายมาก แต่การลู่เข้าอาจช้า การดำเนินการที่ใช้เวลานานที่สุดของอัลกอริธึมคือการคูณเมทริกซ์ด้วยเวกเตอร์ ดังนั้นจึงมีประสิทธิภาพสำหรับเมทริกซ์สปาร์ส ขนาดใหญ่มาก ที่มีการใช้งานที่เหมาะสม ความเร็วในการลู่เข้าเป็นไป ตามสูตร โดย ที่คือจำนวนการวนซ้ำ และและ คือค่าไอเกนที่มีค่าสัมบูรณ์มากที่สุดและค่าไอเกนที่มีค่าสัมบูรณ์มากเป็นอันดับสองตามลำดับ (ดูในส่วนถัดไป ) กล่าวอีกนัยหนึ่ง การลู่เข้าเป็นแบบเลขชี้กำลังโดยมีฐานเป็นช่องว่างสเปกตรัม ${\displaystyle A}$${\displaystyle (\lambda _{2}/\lambda _{1})^{k}}$${\displaystyle k}$${\displaystyle \lambda _{1}}$${\displaystyle \lambda _{2}}$

อัลกอริทึมการวนซ้ำกำลังเริ่มต้นด้วยเวกเตอร์ซึ่งอาจเป็นค่าประมาณของเวกเตอร์ลักษณะเฉพาะที่เด่นที่สุดหรือเวกเตอร์สุ่ม วิธีการนี้อธิบายได้ด้วยความสัมพันธ์เวียนเกิด${\displaystyle b_{0}}$

${\displaystyle b_{k+1}={\frac {Ab_{k}}{\lVert Ab_{k}\rVert }}}$

ดังนั้น ในแต่ละรอบการทำซ้ำ เวกเตอร์จะถูกคูณด้วยเมทริกซ์และปรับให้เป็น เวกเตอร์หน่วย${\displaystyle b_{k}}$${\displaystyle A}$

ถ้าเราสมมติว่ามีค่าไอเกนค่าหนึ่งที่มีขนาดใหญ่กว่าค่าไอเกนค่าอื่นๆ อย่างชัดเจน กล่าวคือ ${\displaystyle A}$

${\displaystyle \left\vert \lambda _{1}\right\vert >\left\vert \lambda _{2}\right\vert \geq \ldots \geq \left\vert \lambda _{n}\right\vert \geq 0}$

และหากเวกเตอร์เริ่มต้นมีส่วนประกอบที่ไม่เป็นศูนย์ในทิศทางของเวกเตอร์ลักษณะเฉพาะที่เกี่ยวข้องกับค่าลักษณะเฉพาะที่เด่นที่สุด ลำดับย่อยจะลู่เข้าสู่เวกเตอร์ลักษณะเฉพาะที่เกี่ยวข้องกับค่าลักษณะเฉพาะที่เด่นที่สุด ${\displaystyle b_{0}}$${\displaystyle \left(b_{k}\right)}$

หากไม่มีข้อสมมติสองข้อข้างต้น ลำดับนี้อาจไม่ลู่เข้า ในลำดับนี้ ${\displaystyle \left(b_{k}\right)}$

${\displaystyle b_{k}=e^{i\phi _{k}}v_{1}+r_{k}}$,

โดยที่เป็นเวกเตอร์ลักษณะเฉพาะที่เกี่ยวข้องกับค่าลักษณะเฉพาะที่เด่นที่สุด และการมีอยู่ของเทอมแสดงว่าไม่ลู่เข้าเว้นแต่ภายใต้สมมติฐานสองข้อที่ระบุไว้ข้างต้น ลำดับที่กำหนดโดย ${\displaystyle v_{1}}$${\displaystyle \|r_{k}\|\rightarrow 0}$${\displaystyle e^{i\phi _{k}}}$${\displaystyle \left(b_{k}\right)}$${\displaystyle e^{i\phi _{k}}=1}$${\displaystyle \left(\mu _{k}\right)}$

${\displaystyle \mu _{k}={\frac {b_{k}^{*}Ab_{k}}{b_{k}^{*}b_{k}}}}$

ลู่เข้าสู่ค่าลักษณะเฉพาะที่เด่นที่สุด (ด้วยอัตราส่วนเรย์ลี )

เราสามารถคำนวณค่านี้ได้โดยใช้อัลกอริทึมต่อไปนี้ (แสดงใน Python ด้วย NumPy):

import numpy as npจากnumpy นำเข้าtyping เป็นnptdef random_vector ( dimension : int ) -> npt . NDArray [ np . float64 ]:rng = np.random.default_rng ( )​​​คืนค่าrng.random ( dimension )​def power_method (ตอบ: npt​ NDArray [ np . float64 ],จำนวนรอบการทำซ้ำ: จำนวนเต็ม,) - > npt NDArray [ np . float64 ]:ถ้าA.shape [ 0 ] ! = A.shape [ 1 ] :​​raise ValueError ( "A ต้องเป็นเมทริกซ์จัตุรัส" )# เลือกเวกเตอร์เริ่มต้นแบบสุ่มเพื่อลดโอกาส# ว่ามันตั้งฉากกับเวกเตอร์ลักษณะเฉพาะที่เด่นที่สุดb_k = random_vector ( A . shape [ 1 ])# ปรับเวกเตอร์เริ่มต้นให้เป็นเวกเตอร์หน่วยb_k / = np.linalg.norm ( b_k )​​​สำหรับ_ ในช่วง( จำนวนรอบ):# คูณด้วยเมทริกซ์b_k1 = A @ b_k# คำนวณความยาวของเวกเตอร์ใหม่b_k1_norm = np.linalg.norm ( b_k1 )​​​​# หยุดการทำงานหากเวกเตอร์ใหม่มีค่าอยู่ในช่วงความแม่นยำของเครื่องที่เท่ากับ 0ถ้าnp.isclose ( b_k1_norm , 0.0 ) :​raise ValueError ( "เมธอด Power สร้างเวกเตอร์เป็นศูนย์" )# ปรับเวกเตอร์ให้เป็นค่าปกติสำหรับการวนซ้ำครั้งต่อไปb_k = b_k1 / b_k1_norm# ส่งคืนเวกเตอร์ลักษณะเฉพาะเด่นโดยประมาณส่งคืนb_k

เวกเตอร์ลู่เข้าสู่เวกเตอร์ลักษณะเฉพาะที่เกี่ยวข้อง ในอุดมคติแล้ว ควรใช้ค่าสัมประสิทธิ์เรย์ลีเพื่อหาค่าลักษณะเฉพาะที่เกี่ยวข้อง ${\displaystyle b_{k}}$

อัลกอริทึมนี้ใช้ในการคำนวณ Google PageRank

นอกจากนี้ ยังสามารถใช้วิธีนี้ในการคำนวณรัศมีสเปกตรัม (ค่าลักษณะเฉพาะที่มีขนาดใหญ่ที่สุด สำหรับเมทริกซ์จัตุรัส) โดยการคำนวณอัตราส่วนเรย์ลีห์

${\displaystyle \rho (A)=\max \left\{\vert \lambda _{1}\vert ,\vert \lambda _{2}\vert ,\ldots ,\vert \lambda _{n}\vert \right\}={\frac {b_{k}^{\top }Ab_{k}}{b_{k}^{\top }b_{k}}}.}$

ให้แยกเมทริกซ์ ออกเป็นรูปแบบจอร์แดนแคนอนิก : โดยที่คอลัมน์แรกของคือเวกเตอร์ลักษณะเฉพาะของ ที่สอดคล้องกับค่าลักษณะเฉพาะเด่นเนื่องจากโดยทั่วไปแล้วค่าลักษณะเฉพาะเด่นของ มีเพียงค่าเดียว บล็อกจอร์แดนแรกของคือเมทริกซ์โดยที่คือค่าลักษณะเฉพาะที่ใหญ่ที่สุดของในแง่ของขนาด เวกเตอร์เริ่มต้นสามารถเขียนได้เป็นผลรวมเชิงเส้นของคอลัมน์ของ: ${\displaystyle A}$${\displaystyle A=VJV^{-1}}$${\displaystyle V}$${\displaystyle A}$${\displaystyle \lambda _{1}}$${\displaystyle A}$${\displaystyle J}$${\displaystyle 1\times 1}$${\displaystyle [\lambda _{1}],}$${\displaystyle \lambda _{1}}$${\displaystyle A}$${\displaystyle b_{0}}$${\displaystyle V}$

${\displaystyle b_{0}=c_{1}v_{1}+c_{2}v_{2}+\ldots +c_{n}v_{n}.}$

ตามสมมติฐานมีส่วนประกอบที่ไม่เป็นศูนย์ในทิศทางของเวกเตอร์ลักษณะเฉพาะที่เด่นดังนั้น ${\displaystyle b_{0}}$${\displaystyle c_{1}\neq 0}$

ความสัมพันธ์เวียนเกิดที่มีประโยชน์ในการคำนวณสำหรับสามารถเขียนใหม่ได้ดังนี้: ${\displaystyle b_{k+1}}$

${\displaystyle b_{k+1}={\frac {Ab_{k}}{\|Ab_{k}\|}}={\frac {A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}},}$

โดยที่นิพจน์ดังกล่าวสามารถวิเคราะห์ได้ง่ายกว่าด้วยวิธีการดังต่อไปนี้: ${\displaystyle {\frac {A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}}}$

${\displaystyle {\begin{aligned}b_{k}&={\frac {A^{k}b_{0}}{\|A^{k}b_{0}\|}}\\&={\frac {\left(VJV^{-1}\right)^{k}b_{0}}{\|\left(VJV^{-1}\right)^{k}b_{0}\|}}\quad {\text{(since}}\,A\,{\text{is diagonalizable)}}\\&={\frac {VJ^{k}V^{-1}b_{0}}{\|VJ^{k}V^{-1}b_{0}\|}}\\&={\frac {VJ^{k}V^{-1}\left(c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}\right)}{\|VJ^{k}V^{-1}\left(c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}\right)\|}}\\&={\frac {VJ^{k}\left(c_{1}e_{1}+c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\|VJ^{k}\left(c_{1}e_{1}+c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\|}}\\&=\left({\frac {\lambda _{1}}{|\lambda _{1}|}}\right)^{k}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\left\|v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\right\|}}\end{aligned}}}$

นิพจน์ข้างต้นสามารถลดรูปได้ดังนี้${\displaystyle k\to \infty }$

${\displaystyle \left({\frac {1}{\lambda _{1}}}J\right)^{k}={\begin{bmatrix}[1]&&&&\\&\left({\frac {1}{\lambda _{1}}}J_{2}\right)^{k}&&&\\&&\ddots &\\&&&\left({\frac {1}{\lambda _{1}}}J_{m}\right)^{k}\\\end{bmatrix}}\rightarrow {\begin{bmatrix}1&&&&\\&0&&&\\&&\ddots &\\&&&0\\\end{bmatrix}}\quad {\text{as}}\quad k\to \infty .}$

ลิมิตนี้เป็นผลมาจากข้อเท็จจริงที่ว่าค่าไอเกนของมีขนาดน้อยกว่า 1 ดังนั้น ${\displaystyle {\frac {1}{\lambda _{1}}}J_{i}}$

${\displaystyle \left({\frac {1}{\lambda _{1}}}J_{i}\right)^{k}\to 0\quad {\text{as}}\quad k\to \infty .}$

ดังนั้นจึงสรุปได้ว่า:

${\displaystyle {\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\to 0\quad {\text{as}}\quad k\to \infty }$

โดยใช้ข้อเท็จจริงนี้สามารถเขียนในรูปแบบที่เน้นความสัมพันธ์กับเมื่อมีขนาดใหญ่ได้: ${\displaystyle b_{k}}$${\displaystyle v_{1}}$${\displaystyle k}$

${\displaystyle {\begin{aligned}b_{k}&=\left({\frac {\lambda _{1}}{|\lambda _{1}|}}\right)^{k}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\left\|v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\right\|}}\\[6pt]&=e^{i\phi _{k}}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}}{\|v_{1}\|}}+r_{k}\end{aligned}}}$

ที่ไหนและเช่น${\displaystyle e^{i\phi _{k}}=\left(\lambda _{1}/|\lambda _{1}|\right)^{k}}$${\displaystyle \|r_{k}\|\to 0}$${\displaystyle k\to \infty }$

ลำดับนี้มีขอบเขต ดังนั้นจึงมีลำดับย่อยที่ลู่เข้า โปรดสังเกตว่าเวกเตอร์ลักษณะเฉพาะที่สอดคล้องกับค่าลักษณะเฉพาะที่เด่นที่สุดนั้นมีเอกลักษณ์เฉพาะตัวโดยมีค่าเพียงค่าเดียวเท่านั้น ดังนั้นถึงแม้ลำดับนี้อาจจะไม่ลู่เข้า แต่ก็ เกือบจะเป็นเวกเตอร์ลักษณะเฉพาะของสำหรับค่า ที่มีขนาดใหญ่ ${\displaystyle \left(b_{k}\right)}$${\displaystyle \left(b_{k}\right)}$${\displaystyle b_{k}}$${\displaystyle A}$${\displaystyle k}$

หรืออีกวิธีหนึ่ง หาก เมทริกซ์ สามารถ ทำให้เป็นเมทริกซ์ทแยงมุมได้การพิสูจน์ต่อไปนี้จะให้ผลลัพธ์เดียวกัน: ${\displaystyle A}$

ให้และ เป็นค่าลักษณะเฉพาะ (นับรวมความซ้ำซ้อน) ของเรียงลำดับตามค่าสัมบูรณ์จากมากไปน้อย (อนุญาตให้เท่ากันได้) นั่นคือและให้เป็นเวกเตอร์ลักษณะเฉพาะที่สอดคล้องกัน สมมติว่าเป็นค่าลักษณะเฉพาะที่เด่นที่สุด ดังนั้นสำหรับทุก. ${\displaystyle \lambda _{1},\lambda _{2},\ldots ,\lambda _{m}}$${\displaystyle m}$${\displaystyle A}$${\displaystyle |\lambda _{1}|\geq |\lambda _{2}|\ldots \geq |\lambda _{m}|}$${\displaystyle v_{1},v_{2},\ldots ,v_{m}}$${\displaystyle \lambda _{1}}$${\displaystyle |\lambda _{1}|>|\lambda _{j}|}$${\displaystyle j>1}$

เวกเตอร์เริ่มต้นสามารถเขียนได้ดังนี้: ${\displaystyle b_{0}}$

${\displaystyle b_{0}=c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{m}v_{m}.}$

ถ้าเลือกแบบสุ่ม (ด้วยความน่าจะเป็นแบบสม่ำเสมอ) แล้วด้วยความน่าจะเป็น 1ทีนี้ ${\displaystyle b_{0}}$${\displaystyle c_{1}\neq 0}$

${\displaystyle {\begin{aligned}A^{k}b_{0}&=c_{1}A^{k}v_{1}+c_{2}A^{k}v_{2}+\cdots +c_{m}A^{k}v_{m}\\&=c_{1}\lambda _{1}^{k}v_{1}+c_{2}\lambda _{2}^{k}v_{2}+\cdots +c_{m}\lambda _{m}^{k}v_{m}\\&=c_{1}\lambda _{1}^{k}\left(v_{1}+{\frac {c_{2}}{c_{1}}}\left({\frac {\lambda _{2}}{\lambda _{1}}}\right)^{k}v_{2}+\cdots +{\frac {c_{m}}{c_{1}}}\left({\frac {\lambda _{m}}{\lambda _{1}}}\right)^{k}v_{m}\right)\\&\to c_{1}\lambda _{1}^{k}v_{1}&&\left|{\frac {\lambda _{j}}{\lambda _{1}}}\right|<1{\text{ for }}j>1\end{aligned}}}$

ในทางกลับกัน:

${\displaystyle b_{k}={\frac {A^{k}b_{0}}{\|A^{k}b_{0}\|}}.}$

ดังนั้น จึงลู่เข้าสู่ (ผลคูณของ) เวกเตอร์ลักษณะเฉพาะ การลู่เข้าเป็นการลู่เข้าเชิงเรขาคณิตโดยมีอัตราส่วน ${\displaystyle b_{k}}$${\displaystyle v_{1}}$

${\displaystyle \left|{\frac {\lambda _{2}}{\lambda _{1}}}\right|.}$

ดังนั้น วิธีการนี้จะลู่เข้าช้าลงหากมีค่าไอเกนที่มีขนาดใกล้เคียงกับค่าไอเกนหลัก

แม้ว่าวิธีการวนซ้ำกำลัง (power iteration) จะประมาณค่าไอเกนเพียงค่าเดียวของเมทริกซ์ แต่ก็ยังคงมีประโยชน์สำหรับปัญหาการคำนวณ บางอย่าง ตัวอย่างเช่นGoogleใช้ในการคำนวณPageRankของเอกสารในเครื่องมือค้นหา^{[ 2 ]}และTwitterใช้เพื่อแสดงคำแนะนำแก่ผู้ใช้ว่าควรติดตามใคร^{[ 3 ]}วิธีการวนซ้ำกำลังเหมาะอย่างยิ่งสำหรับเมทริกซ์แบบเบาบางเช่น เมทริกซ์เว็บ หรือเป็นวิธีการที่ไม่ต้องใช้เมทริกซ์ ซึ่งไม่จำเป็นต้องจัดเก็บเมทริกซ์สัมประสิทธิ์ อย่างชัดเจน แต่สามารถเข้าถึงฟังก์ชันที่ประเมินผลคูณเมทริกซ์-เวกเตอร์ได้สำหรับเมทริกซ์ที่ไม่สมมาตรที่มีสภาพดี วิธีการวนซ้ำกำลังสามารถทำงานได้ดีกว่า การวนซ้ำ Arnoldiที่ ซับซ้อนกว่าสำหรับเมทริกซ์สมมาตร วิธีการวนซ้ำกำลังไม่ค่อยได้ใช้ เนื่องจากความเร็วในการลู่เข้าสามารถเพิ่มขึ้นได้ง่ายโดยไม่ต้องเสียสละต้นทุนต่อการวนซ้ำที่น้อยนิด ดูตัวอย่างเช่นการวนซ้ำ LanczosและLOBPCG${\displaystyle A}$${\displaystyle Ax}$

อัลกอริทึมค่าลักษณะเฉพาะขั้นสูงบางส่วนสามารถเข้าใจได้ว่าเป็นรูปแบบต่างๆ ของการวนซ้ำกำลัง ตัวอย่างเช่น วิธี การวนซ้ำผกผันใช้การวนซ้ำกำลังกับเมทริกซ์ อัลกอริทึมอื่นๆ พิจารณาพื้นที่ย่อยทั้งหมดที่สร้างขึ้นโดยเวกเตอร์พื้นที่ย่อยนี้เรียกว่าพื้นที่ย่อย Krylovสามารถคำนวณได้โดยการวนซ้ำ Arnoldiหรือ การวน ซ้ำ Lanczos การวนซ้ำ Gram ^{[ 4 ]}เป็นวิธีการแบบซูเปอร์ลิเนียร์และกำหนดได้ในการคำนวณคู่ค่าลักษณะเฉพาะที่ใหญ่ที่สุด ${\displaystyle A^{-1}}$${\displaystyle b_{k}}$

• การวนซ้ำของผลหารเรย์ลี
• การวนซ้ำแบบผกผัน