خوارزمية القيم الذاتية بتقنية فرق تسد

تُعدّ خوارزميات القيم الذاتية القائمة على أسلوب فرق تسد فئةً من خوارزميات القيم الذاتية للمصفوفات المتناظرة الحقيقية أو الهرميتية ، والتي أصبحت مؤخرًا (حوالي تسعينيات القرن الماضي) منافسةً من حيث الاستقرار والكفاءة للخوارزميات التقليدية، مثل خوارزمية QR . ويستند المفهوم الأساسي لهذه الخوارزميات إلى أسلوب فرق تسد المُستخدم في علوم الحاسوب . حيث تُقسّم مسألة القيم الذاتية إلى مسألتين متساويتين تقريبًا في الحجم، تُحلّ كلٌّ منهما بشكلٍ تكراري ، وتُحسب القيم الذاتية للمسألة الأصلية من نتائج هاتين المسألتين الأصغر.

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

كما هو الحال مع معظم خوارزميات القيم الذاتية للمصفوفات الهرميتية، تبدأ خوارزمية فرق تسد بالاختزال إلى الشكل ثلاثي الأقطار .${\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}}.}$

القيم الذاتية والمتجهات الذاتية لـ${\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}$.

نكتب${\displaystyle T}$كمصفوفة قطرية كتلية، بالإضافة إلى تصحيح من الرتبة 1 :

الفرق الوحيد بين${\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 }$.

تتمثل الخطوة المتبقية من عملية القسمة في إيجاد القيم الذاتية (وإذا لزم الأمر، المتجهات الذاتية) لـ${\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}}$يمكن تحقيق ذلك من خلال استدعاءات متكررة لخوارزمية فرق تسد، على الرغم من أن التطبيقات العملية غالباً ما تتحول إلى خوارزمية QR المزاحة ضمنياً للمصفوفات الفرعية الصغيرة بما فيه الكفاية. ^{[ 1 ]}

الجزء غير البديهي من الخوارزمية هو الجزء الذي يُحدث الاختراق . بالنظر إلى عمليات التقطير للمصفوفات الفرعية، المحسوبة أعلاه، كيف نجد عملية التقطير للمصفوفة الأصلية؟

أولاً، حدد${\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 يساوي صفرًا، (${\displaystyle e_{i}}$،d _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-\lambda I)^{-1}w=0}$

أو مكتوبة كمعادلة قياسية،

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

تُعرف هذه المعادلة بالمعادلة العلمانية . ولذلك، اختُزلت المسألة إلى إيجاد جذور الدالة الكسرية المُعرَّفة بالطرف الأيسر من هذه المعادلة.

يمكن حل المعادلة العلمانية غير الخطية باستخدام تقنية تكرارية، مثل طريقة نيوتن-رافسون . ومع ذلك، يمكن إيجاد كل جذر في O (1) من التكرارات، ويتطلب كل منها O(1) من التكرارات.${\displaystyle \Theta (m)}$إخفاقات (لـ${\displaystyle m}$دالة كسرية من الدرجة n)، مما يجعل تكلفة الجزء التكراري من هذه الخوارزمية${\displaystyle \Theta (m^{2})}$تم استخدام طريقة الأقطاب المتعددة السريعة أيضًا لحل المعادلة العلمانية في${\displaystyle \Theta (m\log(m))}$العمليات. ^{[ 2 ] [ 1 ]}

سنستخدم نظرية ماستر للتكرارات القائمة على أسلوب فرق تسد لتحليل وقت التشغيل. تذكر أننا ذكرنا أعلاه أننا اخترنا${\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})}$

أشرنا أعلاه إلى أن اختزال المصفوفة الهرميتية إلى شكل ثلاثي الأقطار يأخذ${\displaystyle {\frac {4}{3}}م^{3}}$يفشل. هذا يُقلل بشكل كبير من وقت تشغيل جزء فرق تسد، وفي هذه المرحلة ليس من الواضح ما هي الميزة التي تقدمها خوارزمية فرق تسد على خوارزمية QR (التي تستغرق أيضًا${\displaystyle \Theta (m^{2})}$(العمليات الحسابية للمصفوفات ثلاثية الأقطار).

تكمن ميزة أسلوب فرق تسد عندما تكون هناك حاجة إلى المتجهات الذاتية أيضًا. في هذه الحالة، يتم اختزال المصفوفة إلى شكل ثلاثي الأقطار.${\displaystyle {\frac {8}{3}}م^{3}}$لكن الجزء الثاني من الخوارزمية يأخذ${\displaystyle \Theta (m^{3})}$كذلك. بالنسبة لخوارزمية QR ذات دقة هدف معقولة، هذا هو${\displaystyle \approx 6m^{3}}$أما بالنسبة لاستراتيجية فرق تسد، فهي${\displaystyle \approx {\frac {4}{3}}m^{3}}$ويعود سبب هذا التحسن إلى أنه في استراتيجية فرق تسد،${\displaystyle \Theta (m^{3})}$جزء من الخوارزمية (الضرب)${\displaystyle Q}$تُجرى عملية المصفوفات بشكل منفصل عن التكرار، بينما في منهجية QR، يجب أن تتم هذه العملية في كل خطوة تكرارية. إضافة${\displaystyle {\frac {8}{3}}م^{3}}$أما بالنسبة للتخفيضات، فإن التحسن الكلي يأتي من${\displaystyle \approx 9m^{3}}$ل${\displaystyle \approx 4m^{3}}$فشل.

أظهر الاستخدام العملي لخوارزمية فرق تسد أن الخوارزمية في معظم مسائل القيم الذاتية الواقعية، تحقق نتائج أفضل من ذلك. والسبب هو أن المصفوفات غالبًا ما...${\displaystyle Q}$والمتجهات${\displaystyle z}$تميل إلى أن تكون متفرقة عدديًا ، مما يعني أنها تحتوي على العديد من المدخلات ذات القيم الأصغر من دقة الفاصلة العائمة ، مما يسمح بالانكماش العددي ، أي تقسيم المشكلة إلى مشاكل فرعية غير مترابطة.

الخوارزمية المعروضة هنا هي أبسط نسخة. في العديد من التطبيقات العملية، تُستخدم تصحيحات من الرتبة الأولى أكثر تعقيدًا لضمان الاستقرار؛ بل إن بعض المتغيرات تستخدم تصحيحات من الرتبة الثانية.

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

يمكن بسهولة موازاة خوارزمية فرق تسد ، وتحتوي حزم الحوسبة الجبرية الخطية مثل LAPACK على تطبيقات متوازية عالية الجودة.

• ديميل، جيمس دبليو. (1997)، الجبر الخطي العددي التطبيقي ، فيلادلفيا، بنسلفانيا: جمعية الرياضيات الصناعية والتطبيقية ، رقم ISBN 0-89871-389-7MR 1463942​ .
• كوبين، JJM (1981). “طريقة فرق تسد لمشكلة المثلثية المتماثلة”. الرياضيات الرقمية . 36 (2): 177-195 . دوى : 10.1007 / BF01396757 . S2CID 120504744 .