طريقة القوى التكرارية

إيجاد الاتجاه المهيمن بالضرب المتكرر

حلّ كثير الحدود المميز غير عملي لمصفوفة $1000\times1000$ ، وكثيرًا ما نريد الزوج الذاتي الأكبر فقط، كالمكوّن الرئيسي الأول مثلًا. تجده طريقة القوى التكرارية بضرب المصفوفة في متجه فحسب. ابدأ بأي متجه $\mathbf x_0$ وكرّر $\mathbf x_{k+1}=A\mathbf x_k/\lVert A\mathbf x_k\rVert$ . كل عملية ضرب تمدّ المركّبة على امتداد المتجه الذاتي المهيمن أكثر من غيرها، فبعد خطوات كافية يشير المتجه في اتجاهه.

\mathbf x_{k+1}=\frac{A\mathbf x_k}{\lVert A\mathbf x_k\rVert},\qquad \lambda\approx\frac{\mathbf x_k^{T}A\mathbf x_k}{\mathbf x_k^{T}\mathbf x_k},\qquad e_k\propto\Big|\frac{\lambda_2}{\lambda_1}\Big|^{k}

(1)

نكتب $\mathbf x_0=c_1\mathbf v_1+c_2\mathbf v_2+\cdots$ بدلالة المتجهات الذاتية. بعد $k$ خطوة تُضرب المعاملات في $\lambda_i^k$ فتكون نسبة الثاني إلى الأول $(\lambda_2/\lambda_1)^k$ . تتقارب الطريقة حين يكون $|\lambda_1|>|\lambda_2|$ ويكون للمتجه الابتدائي مركّبة على $\mathbf v_1$ ، وتتحدد السرعة بـ $|\lambda_2/\lambda_1|$ : القيم المتقاربة تعني تقاربًا بطيئًا. التطبيع يمنع الفيض العددي فقط، فالمهم هو الاتجاه. وتقدير القيمة الذاتية هو حاصل ريلي. وللزوج التالي نطرح $\lambda_1\mathbf v_1\mathbf v_1^{T}$ من مصفوفة متماثلة $A$ ونكرر، وهذا يسمى الانكماش.

بضع خطوات يدويةلتكن

A=\begin{pmatrix}2&1\\1&2\end{pmatrix}

وقيمتاها الذاتيتان 3 و1 ومتجهها الذاتي المهيمن

(1,1)

. نبدأ من

\mathbf x_0=(1,0)

. فيكون

A\mathbf x_0=(2,1)

وحاصل ريلي لـ

(2,1)

يساوي

\frac{(2,1)\cdot(5,4)}{5}=\frac{14}{5}=2.8

وهو قريب من 3. والجداء التالي

A(2,1)=(5,4)

يكاد يكون على اتجاه

(1,1)

. ويتقلص الخطأ بالعامل

|\lambda_2/\lambda_1|=1/3

في كل خطوة، ولكسب عامل

10^{-6}

نحتاج

k

يحقق

3^k\ge10^6

أي

k=13

التحديث: اضرب في $A$ واقسم على النظيم وكرّر؛ وكل خطوة تكلف ضربًا واحدًا لمصفوفة في متجه.
السرعة: يتناقص الخطأ مثل $|\lambda_2/\lambda_1|^k$ فالقيم العليا المتقاربة تتقارب ببطء.
الشروط: فجوة $|\lambda_1|>|\lambda_2|$ ومتجه ابتدائي غير عمودي على $\mathbf v_1$ .

الفكرة نفسها ترتّب صفحات الويبطريقة القوى التكرارية هي الطريقة وراء PageRank، وبها يُحسب بكلفة قليلة المكوّن الرئيسي الأول لآلاف الأصول حين تكون مصفوفة التباين المشترك ضخمة أو لا تُكوَّن صراحة (إذ لا يتاح إلا الجداءات

A\mathbf x

). تكلف إجراءات المكتبات للتحليل الكامل نحو

n^3

عملية بينما تكلف كل خطوة قوى

n^2

لمصفوفة كثيفة.

المختبر: ما الذي يُقيَّم

إلى ماذا تتقارب15 نقطة
حاصل ريلي20 نقطة
نسبة التقارب10 نقطة
كم تكرارًا15 نقطة
الخوارزمية بالترتيب15 نقطة
متى تبطؤ أو تفشل15 نقطة
لماذا نطبّع10 نقطة

إيجاد الاتجاه المهيمن بالضرب المتكرر

\mathbf x_{k+1}=\frac{A\mathbf x_k}{\lVert A\mathbf x_k\rVert},\qquad \lambda\approx\frac{\mathbf x_k^{T}A\mathbf x_k}{\mathbf x_k^{T}\mathbf x_k},\qquad e_k\propto\Big|\frac{\lambda_2}{\lambda_1}\Big|^{k}

(1)

بضع خطوات يدويةلتكن

A=\begin{pmatrix}2&1\\1&2\end{pmatrix}

وقيمتاها الذاتيتان 3 و1 ومتجهها الذاتي المهيمن

(1,1)

. نبدأ من

\mathbf x_0=(1,0)

. فيكون

A\mathbf x_0=(2,1)

وحاصل ريلي لـ

(2,1)

يساوي

\frac{(2,1)\cdot(5,4)}{5}=\frac{14}{5}=2.8

وهو قريب من 3. والجداء التالي

A(2,1)=(5,4)

يكاد يكون على اتجاه

(1,1)

. ويتقلص الخطأ بالعامل

|\lambda_2/\lambda_1|=1/3

في كل خطوة، ولكسب عامل

10^{-6}

نحتاج

k

يحقق

3^k\ge10^6

أي

k=13

التحديث: اضرب في $A$ واقسم على النظيم وكرّر؛ وكل خطوة تكلف ضربًا واحدًا لمصفوفة في متجه.
السرعة: يتناقص الخطأ مثل $|\lambda_2/\lambda_1|^k$ فالقيم العليا المتقاربة تتقارب ببطء.
الشروط: فجوة $|\lambda_1|>|\lambda_2|$ ومتجه ابتدائي غير عمودي على $\mathbf v_1$ .

A\mathbf x

). تكلف إجراءات المكتبات للتحليل الكامل نحو

n^3

عملية بينما تكلف كل خطوة قوى

n^2

لمصفوفة كثيفة.

المختبر: ما الذي يُقيَّم

إلى ماذا تتقارب15 نقطة
حاصل ريلي20 نقطة
نسبة التقارب10 نقطة
كم تكرارًا15 نقطة
الخوارزمية بالترتيب15 نقطة
متى تبطؤ أو تفشل15 نقطة
لماذا نطبّع10 نقطة

طريقة القوى التكرارية

إيجاد الاتجاه المهيمن بالضرب المتكرر

المختبر: ما الذي يُقيَّم

سجّل الدخول لتشغيل الكود الخاص بك.

طريقة القوى التكرارية

إيجاد الاتجاه المهيمن بالضرب المتكرر

المختبر: ما الذي يُقيَّم

سجّل الدخول لتشغيل الكود الخاص بك.