خوارزمية قيمة ذاتية

في الجبر الخطي، من أهم المسائل تصميم خوارزميات ذات كفاءة عالية ومستقرة لإيجاد القيم الممتلكة لمصفوفة. يمكن بواسطة خوارزمية القيمة الذاتية إيجاد المتجهات الممتلكة أيضًا.

كثيرة حدود مميزة

إذا علمت مصفوفة مربعة A، فإن قيمة ممتلكة λ ومتجهها الممتلك المصاحب v هما من التعريف، زوجان خاضعان للعلاقة

$A{\mathbf {v} }=\lambda {\mathbf {v} }\,\!,$

حيث v غير صفرية. بالمثل، $(A-\lambda I)\mathbf {v} =0$ (حيث ${\mathcal {}}I$ مصفوفة الوحدة) مقتضية أن $\det(A-\lambda I)=0$ . يمكن توسيع هذا المحدد إلى كثيرة حدود في λ، المعروفة بكثيرة حدود مميزة للمصفوفة A. أحد الطرق المعروفة لإيجاد القيم الممتلكة لمصفوفة صغيرة هي بإيجاد جذور كثيرة الحدود المميزة.

للأسف فإن هذه الطريقة محدودة. لا يمكن حل كثيرة حدود من الرتبة n > 4 بواسطة عدد محدد من العمليات الحسابية المتعاقبة.هناك طرق أكثر كفاءة وهي خوارزميات إيجاد الجذور لكثيرات حدود برتب أعلى.

معاودة القوى

الفكرة الأساسية لهذه الطريقة هي اختيار اعتباطي لمتجه أولي b ومن ثم ضربه المتكرر بالمصفوفة، وبشكل معاود احتساب Ab, A²b, A³b,…. بفرض أن القيم الممتلكة مرتبة حسب قيمتها بحيث تكون λ₁ الأكبر، وبمتجه ذاتي مصاحب v₁.بعدها كل تكرار يقايس المركبة b باتجاه v₁ بمقدار λ₁، وكل اتجاه آخر بقيمة أقل (بفرض |λ₂| < |λ₁|).باستثناء مجموعة قياس صفر، لأي متجه أولي ستتقارب النتيجة إلى متجه ممتلك متوافق مع القيمة الممتلكة الغالبة.

القيم الممتلكة لمصفوفة

في الرياضيات، خصوصًا في الجبر الخطي، تعد كثيرة الحدود المميزة أداة هامة عند وصف القيم الممتلكة لمصفوفة مربعة.

الأنواع

القيم الممتلكة ذات المصفوفات 2×2

يمكن إيجاد حل تحليلي لقيم ذاتية لمصفوفات 2×2 مباشرة من الصيغة الرباعية:

$A={\begin{bmatrix}a&b\\c&d\end{bmatrix}}$

فتكون كثيرة الحدود المميزة هي

${\rm {det{\begin{bmatrix}a-\lambda &b\\c&d-\lambda \end{bmatrix}}=(a-\lambda )(d-\lambda )-bc=\lambda ^{2}-(a+d)\lambda +(ad-bc)}}$

وتكون الحلول

$\lambda ={\frac {a+d}{2}}\pm {\sqrt {{\frac {(a+d)^{2}}{4}}+bc-ad}}={\frac {a+d}{2}}\pm {\frac {\sqrt {4bc+(a-d)^{2}}}{2}}$

لاحظ أن كثيرة الحدود المميزة لمصفوفة 2×2 يمكن كتابته بدلالة الأثر ${\mathcal {}}{\rm {tr}}(A)=a+d$ والمحدد ${\mathcal {}}{\rm {det}}(A)=ad-bc$ بالشكل

${\rm {det}}{\begin{bmatrix}a-\lambda &b\\c&d-\lambda \end{bmatrix}}={\rm {det}}\left[A-\lambda I_{2}\right]=\lambda ^{2}-\lambda {\rm {tr}}(A)+{\rm {det}}(A)$

حيث $I_{2}$ هي مصفوفة الوحدة 2×2. لذا يمكن كتابة حلول القيم الذاتية لمصفوفة 2×2 بالصورة

$\lambda ={\frac {1}{2}}\left({\rm {tr}}(A)\pm {\sqrt {{\rm {tr}}^{2}(A)-4{\rm {det}}(A)}}\right)$

قيم ممتلكة ذات مصفوفات 3×3

إذا كانت

$A={\begin{bmatrix}a&b&c\\d&e&f\\g&h&i\end{bmatrix}}$

فإن كثيرة الحدود المميزة لـA هو

$\det {\begin{bmatrix}a-\lambda &b&c\\d&e-\lambda &f\\g&h&i-\lambda \end{bmatrix}}=-\lambda ^{3}+\lambda ^{2}(a+e+i)+\lambda (db+gc+fh-ae-ai-ei)+(aei-afh-dbi+dch+gbf-gce).$

بالمثل يمكن كتابة كثيرة الحدود المميزة لمصفوفة 3×3 بدلالة الأثر ${\mathcal {}}{\rm {tr}}(A)$ و المحدد ${\mathcal {}}{\rm {det}}(A)$ على الصورة

${\rm {det}}\left[A-\lambda I_{3}\right]=-\lambda ^{3}+\lambda ^{2}{\rm {tr}}(A)+\lambda {\frac {1}{2}}\left[{\rm {tr}}(A^{2})-{\rm {tr}}^{2}(A)\right]+{\rm {det}}(A)$

حيث $I_{3}$ مصفوفة الوحدة 3×3.

طرق تقريبية برمجية لإيجاد القيم الممتلكة

في حال لم يكن لديك برامجيات علمية ذات دالة قيمة ممتلكة، فيما يلي مجموعة من الخطوات التي يمكنك استعمالها كشفرة عامة لمساعدتك في إنشاء برنامج لحل المسائل.

للنوع 2×2:

//we know there are two eigen values, so the
//equations from above can be hard-coded in with minimal effort

Eig11 = (a+d)/2 + sqrt(((a+d)*(a+d))/4 + bc – ad)
Eig12 = (a+d)/2 - sqrt(((a+d)*(a+d))/4 + bc – ad)
//eig11 is the value found using + and eig12 is the value using -
//or we get the same two eigenvalues with the modified equation
Eig21 = (a+d)/2 + sqrt(4bc + (a-d)(a-d))/2
Eig22 = (a+d)/2 - sqrt(4bc + (a-d)(a-d))/2

للنوع 3×3:

//a 3×3 is more complicated and requires several helper equations
//to accomplish due to the λ³ term.
//These steps should help you calculate eigen values for a matrix
//that has ***3 REAL eigen values***.

Define x,y,z
//Use the equation from above to get your cubic equation and
//combine all constant terms possible to
//give you a reduced equation we will use a, b, c and d to denote
//the coefficients of this equation.
Eqn = aλ³ + bλ² + cλ + d = 0
x = ((3c/a) – (b²/a²))/3
y = ((2b³/a³) – (9bc/a²) + (27d/a))/27
z = y²/4 + x³/27

Define I, j, k, m, n, p (so equations are not so cluttered)
i = sqrt(y²/4 - z)
j = -i^(1/3)
k = arccos(-(y/2i))
m = cos(k/3)
n = sqrt(3)*sin(k/3)
p = -(b/3a)

Define Eig1, Eig2, Eig3
Eig1 = -2j*m + p
Eig2 = j *(m + n) + p
Eig3 = j*(m - n) + p

القيم الممتلكة لمصفوفة متماثلة 3x3

ملاحظة: لاتعمل هذه الطريقة في حال المصفوفات المفردة (ذات قيمة أو أكثر ممتلكة صفرية).

% Given symmetric 3x3 matrix M, compute the eigenvalues
m = trace(M)/3;
K = M-m*eye(3);
q = det(K)/2;

p = 0
for i=1:3
    for  j=1:3
        p = p + K(i,j)^2;
    end
end
p = p/6;

phi = 1/3*atan2(sqrt(p^3-q^2), q);
if(phi<0)
    phi=phi+pi/3;
end

eig1 = m + 2*sqrt(p)*cos(phi)
eig2 = m - sqrt(p)*(cos(phi) + sqrt(3)*sin(phi))
eig3 = m - sqrt(p)*(cos(phi) - sqrt(3)*sin(phi))

القيم الممتلكة والمتجهات الممتلكة لمصفوفات خاصة

بالنسبة للمصفوفات التي تحقق الشرط $A^{2}=\alpha$ يمكن كتابة صيغ خاصة للقيم الممتلكة الممكنة.

$P_{+}={\frac {1}{2}}\left(I+{\frac {A}{\sqrt {\alpha }}}\right)$

$P_{-}={\frac {1}{2}}\left(I-{\frac {A}{\sqrt {\alpha }}}\right)$

مع

$AP_{+}={\sqrt {\alpha }}P_{+}\quad AP_{-}=-{\sqrt {\alpha }}P_{-}$

و

$P_{+}P_{+}=P_{+}\quad P_{-}P_{-}=P_{-}\quad P_{+}P_{-}=P_{-}P_{+}=0$

وهذا يعطي الحل مرة أخرى للمتطابقة

$I=P_{+}+P_{-}={\frac {1}{2}}\left(I+{\frac {A}{\sqrt {\alpha }}}\right)+{\frac {1}{2}}\left(I-{\frac {A}{\sqrt {\alpha }}}\right)$