تكرار الطاقة

في الرياضيات ، تُعرف طريقة التكرار الأسي (المعروفة أيضًا باسم طريقة القوة ) بأنها خوارزمية للقيم الذاتية : بالنظر إلى مصفوفة قابلة للتقطير${\displaystyle A}$ستنتج الخوارزمية رقمًا${\displaystyle \lambda }$، وهي أكبر قيمة ذاتية (بالقيمة المطلقة) لـ${\displaystyle A}$ومتجه غير صفري${\displaystyle v}$، وهو متجه ذاتي مناظر لـ${\displaystyle \lambda }$، إنه،${\displaystyle Av=\lambda v}$تُعرف هذه الخوارزمية أيضًا باسم تكرار فون ميزس . ^{[ 1 ]}

تُعدّ خوارزمية التكرار الأسي خوارزمية بسيطة للغاية، ولكنها قد تتقارب ببطء. وتُعتبر عملية ضرب المصفوفات العملية الأكثر استهلاكًا للوقت في هذه الخوارزمية.${\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}}}}$

يتقارب إلى القيمة الذاتية المهيمنة (مع حاصل قسمة رايلي ).

يمكن حساب ذلك باستخدام الخوارزمية التالية (الموضحة بلغة بايثون باستخدام مكتبة NumPy ):

استيراد numpy كـ npfrom numpy import typing as nptدالة random_vector ( بُعد : عدد صحيح ) -> npt . NDArray [ np . float64 ]:rng = np.random.default_rng ( )​​​return rng.random ( dimension )​​دالة power_method (ج : معاهدة حظر الانتشار النووي . NDArray [ np . تعويم64 ]،عدد التكرارات : عدد صحيح ،) -> معاهدة عدم الانتشار . NDArray [ np . تعويم64 ]:إذا كان شكل A [ 0 ] لا يساوي شكل A [ 1 ] :raise ValueError ( "يجب أن تكون المصفوفة مربعة." )# اختر متجهًا أوليًا عشوائيًا لتقليل الاحتمالية# أنه متعامد مع المتجه الذاتي المهيمن.b_k = random_vector ( A . shape [ 1 ])# قم بتطبيع المتجه الأولي.b_k / = np.linalg.norm ( b_k )​​​for _ in range ( num_iterations ):# اضرب في المصفوفة.b_k1 = A @ b_k# احسب طول المتجه الجديد.b_k1_norm = np.linalg.norm ( b_k1 )​​​​# توقف إذا كان المتجه الجديد ضمن دقة الآلة التي تساوي 0.إذا كانت قيمة np.isclose ( b_k1_norm , 0.0 ) :raise ValueError ( "أنتج أسلوب الأس متجهًا صفريًا." )# قم بتطبيع المتجه للتكرار التالي.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}\|}}\\&={\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 .}$

تنتج النهاية من حقيقة أن القيمة الذاتية لـ${\displaystyle {\frac {1}{\lambda _{1}}}J_{i}}$مقدارها أقل من 1، لذا

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

لو${\displaystyle b_{0}}$يتم اختيارها عشوائياً (باحتمالية منتظمة)، ثم${\displaystyle c_{1}\neq 0}$باحتمالية 1. الآن،

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

وبالتالي، فإن الطريقة تتقارب ببطء إذا كانت هناك قيمة ذاتية قريبة في مقدارها من القيمة الذاتية المهيمنة.

على الرغم من أن طريقة التكرار الأسي تُقارب قيمة ذاتية واحدة فقط للمصفوفة، إلا أنها تظل مفيدة في بعض المسائل الحسابية . على سبيل المثال، تستخدمها جوجل لحساب ترتيب الصفحات (PageRank) للمستندات في محرك بحثها ، ^{[ 2 ]} ويستخدمها تويتر لعرض توصيات للمستخدمين بشأن من يتابعونه. ^{[ 3 ]} تُعد طريقة التكرار الأسي مناسبة بشكل خاص للمصفوفات المتفرقة ، مثل مصفوفة الويب، أو كطريقة لا تتطلب تخزين مصفوفة المعاملات.${\displaystyle A}$بشكل صريح، ولكن يمكن بدلاً من ذلك الوصول إلى دالة تقيّم نواتج ضرب المصفوفة في المتجه${\displaystyle Ax}$بالنسبة للمصفوفات غير المتناظرة ذات الحالة الجيدة، قد تتفوق طريقة التكرار الأسي على طريقة أرنولدي الأكثر تعقيدًا . أما بالنسبة للمصفوفات المتناظرة، فنادرًا ما تُستخدم طريقة التكرار الأسي، نظرًا لإمكانية زيادة سرعة تقاربها بسهولة دون التضحية بالتكلفة المنخفضة لكل تكرار؛ انظر، على سبيل المثال، تكرار لانكزوس و LOBPCG .

يمكن فهم بعض خوارزميات القيم الذاتية الأكثر تقدماً على أنها اختلافات في تكرار القوة. على سبيل المثال، تطبق طريقة التكرار العكسي تكرار القوة على المصفوفة${\displaystyle A^{-1}}$. أما الخوارزميات الأخرى فتنظر إلى الفضاء الفرعي الكامل الناتج عن المتجهات.${\displaystyle b_{k}}$يُعرف هذا الفضاء الجزئي باسم فضاء كريلوف الجزئي . ويمكن حسابه باستخدام تكرار أرنولدي أو تكرار لانكزوس . أما تكرار غرام ^{[ 4 ]} فهو طريقة فائقة الخطية وحتمية لحساب أكبر زوج من القيم الذاتية.

• تكرار حاصل قسمة رايلي
• التكرار العكسي