خوارزمية لانكزوس

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

لو${\displaystyle \lambda }$هي قيمة ذاتية لـ${\displaystyle T}$، و${\displaystyle x}$متجهها الذاتي (${\displaystyle Tx=\lambda x}$)، ثم${\displaystyle y=Vx}$هو متجه ذاتي مناظر لـ${\displaystyle A}$بنفس القيمة الذاتية:

$${\displaystyle {\begin{aligned}Ay&=AVx\\&=VTV^{*}Vx\\&=VTIx\\&=VTx\\&=V(\lambda x)\\&=\lambda Vx\\&=\lambda y.\end{aligned}}}$$

وبالتالي، تقوم خوارزمية لانكزوس بتحويل مشكلة تحليل القيم الذاتية لـ${\displaystyle A}$في مسألة تحليل القيم الذاتية لـ${\displaystyle T}$.

1. بالنسبة للمصفوفات ثلاثية الأقطار، يوجد عدد من الخوارزميات المتخصصة، والتي غالبًا ما تتميز بتعقيد حسابي أفضل من الخوارزميات العامة. على سبيل المثال، إذا${\displaystyle T}$هو${\displaystyle m\times m}$إذن، المصفوفة المتناظرة ثلاثية الأقطار هي:
   • يسمح التكرار المستمر بحساب متعددة الحدود المميزة في${\displaystyle O(m^{2})}$العمليات، وتقييمها في نقطة ما${\displaystyle O(m)}$العمليات.
   • يمكن استخدام خوارزمية القيم الذاتية القائمة على أسلوب فرق تسد لحساب التحليل الذاتي الكامل لـ${\displaystyle T}$في${\displaystyle O(m^{2})}$العمليات.
   • يمكن لطريقة الأقطاب المتعددة السريعة ^{[ 8 ]} حساب جميع القيم الذاتية في وقت قصير جدًا${\displaystyle O(m\log m)}$العمليات.
2. من المعروف أن بعض خوارزميات تحليل القيم الذاتية العامة، ولا سيما خوارزمية QR ، تتقارب بشكل أسرع مع المصفوفات ثلاثية الأقطار مقارنةً بالمصفوفات العامة. التعقيد التقاربي لخوارزمية QR ثلاثية الأقطار هو${\displaystyle O(m^{2})}$تمامًا كما هو الحال بالنسبة لخوارزمية فرق تسد (على الرغم من أن العامل الثابت قد يكون مختلفًا)؛ نظرًا لأن المتجهات الذاتية معًا لها${\displaystyle m^{2}}$العناصر، هذا هو الأمثل تقاربياً .
3. حتى الخوارزميات التي لا تتأثر معدلات تقاربها بالتحويلات الوحدوية، مثل طريقة القوة والتكرار العكسي ، قد تستفيد من تحسينات الأداء على المستوى المنخفض عند تطبيقها على المصفوفة ثلاثية الأقطار${\displaystyle T}$بدلاً من المصفوفة الأصلية${\displaystyle A}$. منذ${\displaystyle T}$تتميز هذه الطريقة بأنها متفرقة للغاية، حيث تقع جميع العناصر غير الصفرية في مواقع يمكن التنبؤ بها بدرجة عالية، مما يسمح بتخزين مضغوط مع أداء ممتاز فيما يتعلق بالتخزين المؤقت . وبالمثل،${\displaystyle T}$هي مصفوفة حقيقية جميع متجهاتها الذاتية وقيمها الذاتية حقيقية، بينما${\displaystyle A}$قد تحتوي المصفوفات عمومًا على عناصر ومتجهات ذاتية مركبة، لذا فإن الحساب الحقيقي يكفي لإيجاد المتجهات الذاتية والقيم الذاتية لـ${\displaystyle T}$.
4. لو${\displaystyle n}$كبير جدًا، ثم يتم تقليله${\displaystyle m}$لهذا السبب.${\displaystyle T}$سيسمح الحجم الذي يمكن التحكم فيه بإيجاد القيم الذاتية والمتجهات الذاتية الأكثر تطرفًا لـ${\displaystyle A}$في${\displaystyle m\ll n}$في هذه المنطقة، يمكن اعتبار خوارزمية لانكزوس بمثابة مخطط ضغط مع فقدان البيانات للمصفوفات الهرميتية، والتي تؤكد على الحفاظ على القيم الذاتية القصوى.

إن الجمع بين الأداء الجيد للمصفوفات المتفرقة والقدرة على حساب العديد من القيم الذاتية (دون حساب جميعها) هو السبب الرئيسي لاختيار استخدام خوارزمية لانكزوس.

على الرغم من أن مسألة القيم الذاتية غالبًا ما تكون الدافع وراء تطبيق خوارزمية لانكزوس، إلا أن العملية الأساسية التي تؤديها الخوارزمية هي تحويل المصفوفة إلى مصفوفة ثلاثية القطر، والتي حظيت فيها تحويلات هاوسهولدر المستقرة عدديًا بالأفضلية منذ خمسينيات القرن الماضي. خلال ستينيات القرن الماضي، تم تجاهل خوارزمية لانكزوس. وقد تجدد الاهتمام بها بفضل نظرية تقارب كانيل-بيج وتطوير طرق لمنع عدم الاستقرار العددي، ولكن خوارزمية لانكزوس لا تزال الخوارزمية البديلة التي يتم اللجوء إليها فقط في حال عدم كفاية تحويلات هاوسهولدر. ^{[ 9 ]}

تشمل الجوانب التي تختلف فيها الخوارزميتان ما يلي:

• يستغل لانكزوس${\displaystyle A}$كونها مصفوفة متفرقة، بينما هاوسهولدر ليس كذلك، وسوف يقوم بتوليد التعبئة .
• يعمل لانكزوس طوال الوقت مع المصفوفة الأصلية${\displaystyle A}$(ولا توجد مشكلة في معرفة ذلك ضمنيًا فقط)، في حين أن هاوسهولدر الخام يريد تعديل المصفوفة أثناء الحساب (على الرغم من أنه يمكن تجنب ذلك).
• تُنتج كل تكرارات خوارزمية لانكزوس عمودًا آخر من مصفوفة التحويل النهائية.${\displaystyle V}$بينما ينتج تكرار طريقة هاوسهولدر عاملاً آخر في التحليل الوحدوي.${\displaystyle Q_{1}Q_{2}\dots Q_{n}}$ل${\displaystyle V}$ومع ذلك، يتم تحديد كل عامل بواسطة متجه واحد، لذا فإن متطلبات التخزين هي نفسها لكلا الخوارزميتين، و${\displaystyle V=Q_{1}Q_{2}\dots Q_{n}}$يمكن حسابها في${\displaystyle O(n^{3})}$وقت.
• هاوسهولدر مستقر عدديًا، بينما لانكزوس الخام ليس كذلك.
• يتميز لانكزوس بالتوازي الشديد، مع وجود فقط${\displaystyle O(n)}$نقاط التزامن (حسابات${\displaystyle \alpha _{j}}$و${\displaystyle \beta _{j}}$). أما هاوسهولدر فهو أقل توازياً، إذ يحتوي على تسلسل من${\displaystyle O(n^{2})}$كميات قياسية محسوبة يعتمد كل منها على الكمية السابقة في التسلسل.

طريقة القوة لإيجاد القيمة الذاتية ذات أكبر مقدار والمتجه الذاتي المقابل لها لمصفوفة${\displaystyle A}$تقريبًا

1. اختر متجهًا عشوائيًا${\displaystyle u_{1}\neq 0}$.
2. ل${\displaystyle j\geqslant 1}$(حتى اتجاه${\displaystyle u_{j}}$(تقاربت النتائج) افعل:
   1. يترك${\displaystyle u_{j+1}'=Au_{j}.}$
   2. يترك${\displaystyle u_{j+1}=u_{j+1}'/\|u_{j+1}'\|.}$

• في الغالب${\displaystyle j}$حد،${\displaystyle u_{j}}$يقترب من المتجه الذاتي المعياري المقابل لأكبر قيمة ذاتية.

من الانتقادات التي يمكن توجيهها لهذه الطريقة أنها مُهدرة للموارد: فهي تُهدر الكثير من الجهد (عمليات ضرب المصفوفة في المتجه في الخطوة 2.1) لاستخراج المعلومات من المصفوفة.${\displaystyle A}$لكنها لا تولي اهتمامًا إلا للنتيجة الأخيرة؛ وعادةً ما تستخدم التطبيقات نفس المتغير لجميع المتجهات.${\displaystyle u_{j}}$حيث تقوم كل عملية تكرار جديدة باستبدال نتائج العملية السابقة. قد يكون من الأفضل بدلاً من ذلك الاحتفاظ بجميع النتائج الوسيطة وتنظيم البيانات.

معلومة واحدة متاحة بسهولة من المتجهات${\displaystyle u_{j}}$هي سلسلة من فضاءات كريلوف الجزئية . إحدى طرق التعبير عن ذلك دون إدخال مجموعات في الخوارزمية هي الادعاء بأنها تحسب

مجموعة فرعية${\displaystyle \{v_{j}\}_{j=1}^{m}}$على أساس${\displaystyle \mathbb {C} ^{n}}$بحيث${\displaystyle Ax\in \operatorname {span} (v_{1},\dotsc ,v_{j+1})}$لكل${\displaystyle x\in \operatorname {span} (v_{1},\dotsc ,v_{j})}$وكل شيء${\displaystyle 1\leqslant j<m;}$

وهذا يتحقق بشكل بديهي بواسطة${\displaystyle v_{j}=u_{j}}$طالما${\displaystyle u_{j}}$مستقل خطيًا عن${\displaystyle u_{1},\dotsc ,u_{j-1}}$(وفي حالة وجود مثل هذا الاعتماد، يمكن للمرء مواصلة التسلسل عن طريق الاختيار كـ${\displaystyle v_{j}}$متجه عشوائي مستقل خطيًا عن${\displaystyle u_{1},\dotsc ,u_{j-1}}$أساس يحتوي على${\displaystyle u_{j}}$ومع ذلك، من المرجح أن تكون المتجهات سيئة التكييف عدديًا ، لأن هذه السلسلة من المتجهات مصممة عمدًا للتقارب إلى متجه ذاتي لـ${\displaystyle A}$ولتجنب ذلك، يمكن للمرء أن يجمع بين تكرار القوة وعملية غرام-شميدت ، لإنتاج أساس متعامد لهذه الفضاءات الفرعية لكريلوف.

1. اختر متجهًا عشوائيًا${\displaystyle u_{1}}$المعيار الإقليدي${\displaystyle 1}$. يترك${\displaystyle v_{1}=u_{1}}$.
2. ل${\displaystyle j=1,\dotsc ,m-1}$يفعل:
   1. يترك${\displaystyle u_{j+1}'=Au_{j}}$.
   2. للجميع${\displaystyle k=1,\dotsc ,j}$يترك${\displaystyle g_{k,j}=v_{k}^{*}u_{j+1}'}$(هذه هي إحداثيات${\displaystyle Au_{j}=u_{j+1}'}$فيما يتعلق بمتجهات الأساس${\displaystyle v_{1},\dotsc ,v_{j}}$.)
   3. يترك${\displaystyle w_{j+1}=u_{j+1}'-\sum _{k=1}^{j}g_{k,j}v_{k}}$(إلغاء مكون من${\displaystyle u_{j+1}'}$هذا في${\displaystyle \operatorname {span} (v_{1},\dotsc ,v_{j})}$.)
   4. لو${\displaystyle w_{j+1}\neq 0}$ثم دع${\displaystyle u_{j+1}=u_{j+1}'/\|u_{j+1}'\|}$و${\displaystyle v_{j+1}=w_{j+1}/\|w_{j+1}\|}$،

      وإلا فاختر كما هو${\displaystyle u_{j+1}=v_{j+1}}$متجه عشوائي ذو معيار إقليدي${\displaystyle 1}$وهو متعامد مع جميع${\displaystyle v_{1},\dotsc ,v_{j}}$.

العلاقة بين متجهات تكرار القوة${\displaystyle u_{j}}$والمتجهات المتعامدة${\displaystyle v_{j}}$هل هذا

${\displaystyle Au_{j}=\|u_{j+1}'\|u_{j+1}=u_{j+1}'=w_{j+1}+\sum _{k=1}^{j}g_{k,j}v_{k}=\|w_{j+1}\|v_{j+1}+\sum _{k=1}^{j}g_{k,j}v_{k}}$.

وهنا يمكن ملاحظة أننا لسنا بحاجة فعلياً إلى${\displaystyle u_{j}}$متجهات لحساب هذه${\displaystyle v_{j}}$، لأن${\displaystyle u_{j}-v_{j}\in \operatorname {span} (v_{1},\dotsc ,v_{j-1})}$وبالتالي الفرق بين${\displaystyle u_{j+1}'=Au_{j}}$و${\displaystyle w_{j+1}'=Av_{j}}$هو في${\displaystyle \operatorname {span} (v_{1},\dotsc ,v_{j})}$، والذي يتم إلغاؤه بواسطة عملية التعامد. وبالتالي، يتم حساب نفس الأساس لسلسلة فضاءات كريلوف الفرعية بواسطة

1. اختر متجهًا عشوائيًا${\displaystyle v_{1}}$المعيار الإقليدي${\displaystyle 1}$.
2. ل${\displaystyle j=1,\dotsc ,m-1}$يفعل:
   1. يترك${\displaystyle w_{j+1}'=Av_{j}}$.
   2. للجميع${\displaystyle k=1,\dotsc ,j}$يترك${\displaystyle h_{k,j}=v_{k}^{*}w_{j+1}'}$.
   3. يترك${\displaystyle w_{j+1}=w_{j+1}'-\sum _{k=1}^{j}h_{k,j}v_{k}}$.
   4. يترك${\displaystyle h_{j+1,j}=\|w_{j+1}\|}$.
   5. لو${\displaystyle h_{j+1,j}\neq 0}$ثم دع${\displaystyle v_{j+1}=w_{j+1}/h_{j+1,j}}$،

      وإلا فاختر كما هو${\displaystyle v_{j+1}}$متجه عشوائي ذو معيار إقليدي${\displaystyle 1}$وهو متعامد مع جميع${\displaystyle v_{1},\dotsc ,v_{j}}$.

المعاملات مسبقًا${\displaystyle h_{k,j}}$مُرضٍ

${\displaystyle Av_{j}=\sum _{k=1}^{j+1}h_{k,j}v_{k}}$للجميع${\displaystyle j<m}$;

التعريف${\displaystyle h_{j+1,j}=\|w_{j+1}\|}$قد يبدو الأمر غريباً بعض الشيء، ولكنه يتناسب مع النمط العام.${\displaystyle h_{k,j}=v_{k}^{*}w_{j+1}'}$منذ

${\displaystyle v_{j+1}^{*}w_{j+1}'=v_{j+1}^{*}w_{j+1}=\|w_{j+1}\|v_{j+1}^{*}v_{j+1}=\|w_{j+1}\|.}$

لأن متجهات تكرار القوة${\displaystyle u_{j}}$التي تم استبعادها من هذا التكرار تحقق${\displaystyle u_{j}\in \operatorname {span} (v_{1},\ldots ,v_{j}),}$المتجهات${\displaystyle \{v_{j}\}_{j=1}^{m}}$والمعاملات${\displaystyle h_{k,j}}$تحتوي على معلومات كافية من${\displaystyle A}$ذلك كله${\displaystyle u_{1},\ldots ,u_{m}}$يمكن حسابها، لذا لم يُفقد شيء من خلال تبديل المتجهات. (في الواقع، اتضح أن البيانات التي تم جمعها هنا تعطي تقريبات أفضل بكثير لأكبر قيمة ذاتية مما يحصل عليه المرء من عدد مماثل من التكرارات في طريقة القوة، على الرغم من أن ذلك ليس واضحًا بالضرورة في هذه المرحلة.)

تُعرف هذه العملية الأخيرة بتكرار أرنولدي . ثم تظهر خوارزمية لانكزوس كتبسيط ناتج عن حذف خطوات حسابية تبين أنها بديهية عندما${\displaystyle A}$هيرميتية - وخاصة معظمها${\displaystyle h_{k,j}}$تبين أن المعاملات تساوي صفرًا.

بشكل أساسي، إذا${\displaystyle A}$هل هو هيرميتي إذن؟

${\displaystyle h_{k,j}=v_{k}^{*}w_{j+1}'=v_{k}^{*}Av_{j}=v_{k}^{*}A^{*}v_{j}=(Av_{k})^{*}v_{j}.}$

ل${\displaystyle k<j-1}$نحن نعلم ذلك${\displaystyle Av_{k}\in \operatorname {span} (v_{1},\ldots ,v_{j-1})}$و منذ ذلك الحين${\displaystyle v_{j}}$بحكم البناء، وبما أن المتتالية متعامدة مع هذا الفضاء الجزئي، فإن هذا الجداء الداخلي يجب أن يكون صفرًا. (وهذا هو السبب الرئيسي أيضًا في إمكانية إعطاء متتاليات كثيرات الحدود المتعامدة دائمًا علاقة تكرارية ثلاثية الحدود ).${\displaystyle k=j-1}$يحصل المرء

${\displaystyle h_{j-1,j}=(Av_{j-1})^{*}v_{j}={\overline {v_{j}^{*}Av_{j-1}}}={\overline {h_{j,j-1}}}=h_{j,j-1}}$

لأن الأخير حقيقي لأنه معيار متجه.${\displaystyle k=j}$يحصل المرء

${\displaystyle h_{j,j}=(Av_{j})^{*}v_{j}={\overline {v_{j}^{*}Av_{j}}}={\overline {h_{j,j}}},}$

وهذا يعني أن هذا حقيقي أيضاً.

بصورة أكثر تجريدًا، إذا${\displaystyle V}$هي المصفوفة ذات الأعمدة${\displaystyle v_{1},\ldots ,v_{m}}$ثم الأرقام${\displaystyle h_{k,j}}$يمكن تحديدها كعناصر من عناصر المصفوفة${\displaystyle H=V^{*}AV}$، و${\displaystyle h_{k,j}=0}$ل${\displaystyle k>j+1;}$المصفوفة${\displaystyle H}$هي هيسنبرغ العليا . منذ

${\displaystyle H^{*}=\left(V^{*}AV\right)^{*}=V^{*}A^{*}V=V^{*}AV=H}$

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

إحدى طرق توصيف المتجهات الذاتية لمصفوفة هيرميتية${\displaystyle A}$وهي بمثابة نقاط ثابتة في حاصل قسمة رايلي

${\displaystyle r(x)={\frac {x^{*}Ax}{x^{*}x}},\qquad x\in \mathbb {C} ^{n}.}$

وعلى وجه الخصوص، أكبر قيمة ذاتية${\displaystyle \lambda _{\max }}$هو الحد الأقصى العالمي لـ${\displaystyle r}$وأصغر قيمة ذاتية${\displaystyle \lambda _{\min }}$هو الحد الأدنى العالمي لـ${\displaystyle r}$.

ضمن فضاء فرعي منخفض الأبعاد${\displaystyle {\mathcal {L}}}$ل${\displaystyle \mathbb {C} ^{n}}$قد يكون من الممكن تحديد الحد الأقصى${\displaystyle x}$والحد الأدنى${\displaystyle y}$ل${\displaystyle r}$. تكرار ذلك لسلسلة متزايدة${\displaystyle {\mathcal {L}}_{1}\subset {\mathcal {L}}_{2}\subset \cdots }$ينتج سلسلتين من المتجهات:${\displaystyle x_{1},x_{2},\ldots }$و${\displaystyle y_{1},y_{2},\dotsc }$بحيث${\displaystyle x_{j},y_{j}\in {\mathcal {L}}_{j}}$و

${\displaystyle {\begin{aligned}r(x_{1})&\leqslant r(x_{2})\leqslant \cdots \leqslant \lambda _{\max }\\r(y_{1})&\geqslant r(y_{2})\geqslant \cdots \geqslant \lambda _{\min }\end{aligned}}}$

ثم يطرح السؤال كيفية اختيار الفضاءات الفرعية بحيث تتقارب هذه المتتاليات بمعدل أمثل.

من${\displaystyle x_{j}}$، الاتجاه الأمثل الذي ينبغي فيه البحث عن قيم أكبر لـ${\displaystyle r}$هو ذلك التدرج${\displaystyle \nabla r(x_{j})}$وكذلك من${\displaystyle y_{j}}$الاتجاه الأمثل الذي يجب اتباعه للبحث عن قيم أصغر لـ${\displaystyle r}$وهو ذلك التدرج السالب${\displaystyle -\nabla r(y_{j})}$. على العموم

${\displaystyle \nabla r(x)={\frac {2}{x^{*}x}}(Ax-r(x)x),}$

لذا فإن الاتجاهات ذات الأهمية يسهل حسابها في حساب المصفوفات، ولكن إذا رغب المرء في تحسين كليهما${\displaystyle x_{j}}$و${\displaystyle y_{j}}$ثم هناك اتجاهان جديدان يجب أخذهما في الاعتبار:${\displaystyle Ax_{j}}$و${\displaystyle Ay_{j};}$منذ${\displaystyle x_{j}}$و${\displaystyle y_{j}}$يمكن أن تكون متجهات مستقلة خطيًا (بل إنها قريبة من التعامد)، ولا يمكن للمرء بشكل عام أن يتوقع${\displaystyle Ax_{j}}$و${\displaystyle Ay_{j}}$أن تكون متوازية. ليس من الضروري زيادة أبعاد${\displaystyle {\mathcal {L}}_{j}}$بواسطة${\displaystyle 2}$في كل خطوة إذا${\displaystyle \{{\mathcal {L}}_{j}\}_{j=1}^{m}}$تُعتبر فضاءات فرعية من نوع كريلوف، لأنه حينها${\displaystyle Az\in {\mathcal {L}}_{j+1}}$للجميع${\displaystyle z\in {\mathcal {L}}_{j},}$وبالتالي، على وجه الخصوص، بالنسبة لكليهما${\displaystyle z=x_{j}}$و${\displaystyle z=y_{j}}$.

بمعنى آخر، يمكننا البدء بمتجه أولي عشوائي${\displaystyle x_{1}=y_{1},}$قم بإنشاء فضاءات المتجهات

${\displaystyle {\mathcal {L}}_{j}=\operatorname {span} (x_{1},Ax_{1},\ldots ,A^{j-1}x_{1})}$

ثم ابحث${\displaystyle x_{j},y_{j}\in {\mathcal {L}}_{j}}$بحيث

${\displaystyle r(x_{j})=\max _{z\in {\mathcal {L}}_{j}}r(z)\qquad {\text{and}}\qquad r(y_{j})=\min _{z\in {\mathcal {L}}_{j}}r(z).}$

منذ${\displaystyle j}$طريقة القوة n التكرار${\displaystyle u_{j}}$ينتمي إلى${\displaystyle {\mathcal {L}}_{j},}$ويترتب على ذلك أن التكرار لإنتاج${\displaystyle x_{j}}$و${\displaystyle y_{j}}$لا يمكن أن يتقارب بشكل أبطأ من طريقة القوة، وسيحقق نتائج أفضل بتقريب القيمتين الذاتيتين المتطرفتين. بالنسبة للمسألة الفرعية للتحسين${\displaystyle r}$في بعض${\displaystyle {\mathcal {L}}_{j}}$من الملائم أن يكون لدينا أساس متعامد${\displaystyle \{v_{1},\ldots ,v_{j}\}}$بالنسبة لهذا الفضاء المتجهي . وبالتالي، نعود مرة أخرى إلى مشكلة الحساب التكراري لمثل هذه القاعدة لتسلسل فضاءات كريلوف الفرعية.

بعد${\displaystyle m}$خطوات التكرار لخوارزمية لانكزوس،${\displaystyle T}$هو${\displaystyle m\times m}$مصفوفة متناظرة حقيقية، والتي على غرار ما سبق لها${\displaystyle m}$القيم الذاتية${\displaystyle \theta _{1}\geqslant \theta _{2}\geqslant \dots \geqslant \theta _{m}.}$يُفهم التقارب في المقام الأول على أنه تقارب لـ${\displaystyle \theta _{1}}$ل${\displaystyle \lambda _{1}}$(والتقارب المتناظر لـ${\displaystyle \theta _{m}}$ل${\displaystyle \lambda _{n}}$) مثل${\displaystyle m}$ينمو، وثانياً تقارب نطاق معين${\displaystyle \theta _{1},\ldots ,\theta _{k}}$من القيم الذاتية لـ${\displaystyle T}$لنظرائهم${\displaystyle \lambda _{1},\ldots ,\lambda _{k}}$ل${\displaystyle A}$غالبًا ما يكون تقارب خوارزمية لانكزوس أسرع بعدة مراتب من تقارب خوارزمية التكرار الأسي. ^{[ 9 ] : 477}

حدود${\displaystyle \theta _{1}}$ينبع ذلك من التفسير المذكور أعلاه للقيم الذاتية باعتبارها قيمًا قصوى لمعامل رايلي${\displaystyle r(x)}$. منذ${\displaystyle \lambda _{1}}$هو الحد الأقصى مسبقًا لـ${\displaystyle r}$في مجمل${\displaystyle \mathbb {C} ^{n},}$بينما${\displaystyle \theta _{1}}$هو مجرد الحد الأقصى على${\displaystyle m}$فضاء كريلوف ذو الأبعاد n، نحصل بشكل بديهي على${\displaystyle \lambda _{1}\geqslant \theta _{1}}$. على العكس من ذلك، أي نقطة${\displaystyle x}$يوفر فضاء كريلوف الفرعي حدًا أدنى${\displaystyle r(x)}$ل${\displaystyle \theta _{1}}$لذلك إذا أمكن إثبات نقطة ما والتي${\displaystyle \lambda _{1}-r(x)}$إذا كانت صغيرة، فإن هذا يوفر حدًا ضيقًا لـ${\displaystyle \theta _{1}}$.

البعد${\displaystyle m}$فضاء كريلوف الفرعي هو

${\displaystyle \operatorname {span} \left\{v_{1},Av_{1},A^{2}v_{1},\ldots ,A^{m-1}v_{1}\right\},}$

لذا يمكن التعبير عن أي عنصر منه على النحو التالي${\displaystyle p(A)v_{1}}$لبعض كثيرات الحدود${\displaystyle p}$درجة علمية على الأكثر${\displaystyle m-1}$معاملات تلك المعادلة متعددة الحدود هي ببساطة معاملات التركيبة الخطية للمتجهات.${\displaystyle v_{1},Av_{1},A^{2}v_{1},\ldots ,A^{m-1}v_{1}}$ستتبين أن متعددة الحدود التي نريدها تحتوي على معاملات حقيقية، ولكن في الوقت الحالي، يجب أن نسمح أيضًا بالمعاملات المركبة، وسنكتبها على النحو التالي:${\displaystyle p^{*}}$بالنسبة لكثير الحدود الذي تم الحصول عليه عن طريق المرافق المركب لجميع معاملات${\displaystyle p}$في هذه المعلمة للفضاء الفرعي لكريلوف، لدينا

${\displaystyle r(p(A)v_{1})={\frac {(p(A)v_{1})^{*}Ap(A)v_{1}}{(p(A)v_{1})^{*}p(A)v_{1}}}={\frac {v_{1}^{*}p(A)^{*}Ap(A)v_{1}}{v_{1}^{*}p(A)^{*}p(A)v_{1}}}={\frac {v_{1}^{*}p^{*}(A^{*})Ap(A)v_{1}}{v_{1}^{*}p^{*}(A^{*})p(A)v_{1}}}={\frac {v_{1}^{*}p^{*}(A)Ap(A)v_{1}}{v_{1}^{*}p^{*}(A)p(A)v_{1}}}}$

باستخدام التعبير الخاص بـ${\displaystyle v_{1}}$باعتبارها توليفة خطية من المتجهات الذاتية، نحصل على

${\displaystyle Av_{1}=A\sum _{k=1}^{n}d_{k}z_{k}=\sum _{k=1}^{n}d_{k}\lambda _{k}z_{k}}$

وبشكل أعم

${\displaystyle q(A)v_{1}=\sum _{k=1}^{n}d_{k}q(\lambda _{k})z_{k}}$

لأي متعددة حدود${\displaystyle q}$.

هكذا

${\displaystyle \lambda _{1}-r(p(A)v_{1})=\lambda _{1}-{\frac {v_{1}^{*}\sum _{k=1}^{n}d_{k}p^{*}(\lambda _{k})\lambda _{k}p(\lambda _{k})z_{k}}{v_{1}^{*}\sum _{k=1}^{n}d_{k}p^{*}(\lambda _{k})p(\lambda _{k})z_{k}}}=\lambda _{1}-{\frac {\sum _{k=1}^{n}|d_{k}|^{2}\lambda _{k}p(\lambda _{k})^{*}p(\lambda _{k})}{\sum _{k=1}^{n}|d_{k}|^{2}p(\lambda _{k})^{*}p(\lambda _{k})}}={\frac {\sum _{k=1}^{n}|d_{k}|^{2}(\lambda _{1}-\lambda _{k})\left|p(\lambda _{k})\right|^{2}}{\sum _{k=1}^{n}|d_{k}|^{2}\left|p(\lambda _{k})\right|^{2}}}.}$

يتمثل أحد الفروق الرئيسية بين البسط والمقام هنا في أن${\displaystyle k=1}$يختفي الحد في البسط، لكنه لا يختفي في المقام. وبالتالي، إذا كان بإمكان المرء اختيار${\displaystyle p}$أن تكون كبيرًا في${\displaystyle \lambda _{1}}$ولكن إذا كانت صغيرة عند جميع القيم الذاتية الأخرى، فسيحصل المرء على حد ضيق للخطأ${\displaystyle \lambda _{1}-\theta _{1}}$.

منذ${\displaystyle A}$يحتوي على قيم ذاتية أكثر بكثير من${\displaystyle p}$قد يبدو هذا الأمر صعباً، لكن إحدى طرق تحقيقه هي استخدام كثيرات حدود تشيبيشيف . كتابة${\displaystyle c_{k}}$للحصول على الدرجة${\displaystyle k}$متعددة حدود تشيبيشيف من النوع الأول (التي تحقق${\displaystyle c_{k}(\cos x)=\cos(kx)}$للجميع${\displaystyle x}$لدينا متعددة حدود تبقى في النطاق${\displaystyle [-1,1]}$على الفترة الزمنية المعروفة${\displaystyle [-1,1]}$لكنها تنمو بسرعة خارجها. مع بعض التعديلات على الوسيط، يمكننا جعلها تُحدد جميع القيم الذاتية باستثناء${\displaystyle \lambda _{1}}$داخل${\displaystyle [-1,1]}$. يترك

${\displaystyle p(x)=c_{m-1}\left({\frac {2x-\lambda _{2}-\lambda _{n}}{\lambda _{2}-\lambda _{n}}}\right)}$

(في حالة${\displaystyle \lambda _{2}=\lambda _{1}}$استخدم بدلاً من ذلك أكبر قيمة ذاتية أقل من${\displaystyle \lambda _{1}}$ثم القيمة القصوى لـ${\displaystyle |p(\lambda _{k})|^{2}}$ل${\displaystyle k\geqslant 2}$يكون${\displaystyle 1}$والقيمة الدنيا هي${\displaystyle 0}$، لذا

${\displaystyle \lambda _{1}-\theta _{1}\leqslant \lambda _{1}-r(p(A)v_{1})={\frac {\sum _{k=2}^{n}|d_{k}|^{2}(\lambda _{1}-\lambda _{k})|p(\lambda _{k})|^{2}}{\sum _{k=1}^{n}|d_{k}|^{2}|p(\lambda _{k})|^{2}}}\leqslant {\frac {\sum _{k=2}^{n}|d_{k}|^{2}(\lambda _{1}-\lambda _{k})}{|d_{1}|^{2}|p(\lambda _{1})|^{2}}}\leqslant {\frac {(\lambda _{1}-\lambda _{n})\sum _{k=2}^{n}|d_{k}|^{2}}{|p(\lambda _{1})|^{2}|d_{1}|^{2}}}.}$

بالإضافة إلى

${\displaystyle p(\lambda _{1})=c_{m-1}\left({\frac {2\lambda _{1}-\lambda _{2}-\lambda _{n}}{\lambda _{2}-\lambda _{n}}}\right)=c_{m-1}\left(2{\frac {\lambda _{1}-\lambda _{2}}{\lambda _{2}-\lambda _{n}}}+1\right);}$

الكمية

${\displaystyle \rho ={\frac {\lambda _{1}-\lambda _{2}}{\lambda _{2}-\lambda _{n}}}}$

وبالتالي، فإن نسبة فجوة الطاقة الذاتية الأولى إلى قطر بقية الطيف لها أهمية بالغة بالنسبة لمعدل التقارب هنا. وكذلك كتابة

${\displaystyle R=e^{\operatorname {arcosh} (1+2\rho )}=1+2\rho +2{\sqrt {\rho ^{2}+\rho }},}$

يمكننا أن نستنتج أن

${\displaystyle {\begin{aligned}\lambda _{1}-\theta _{1}&\leqslant {\frac {(\lambda _{1}-\lambda _{n})\left(1-|d_{1}|^{2}\right)}{c_{m-1}(2\rho +1)^{2}|d_{1}|^{2}}}\\[6pt]&={\frac {1-|d_{1}|^{2}}{|d_{1}|^{2}}}(\lambda _{1}-\lambda _{n}){\frac {1}{\cosh ^{2}((m-1)\operatorname {arcosh} (1+2\rho ))}}\\[6pt]&={\frac {1-|d_{1}|^{2}}{|d_{1}|^{2}}}(\lambda _{1}-\lambda _{n}){\frac {4}{\left(R^{m-1}+R^{-(m-1)}\right)^{2}}}\\[6pt]&\leqslant 4{\frac {1-|d_{1}|^{2}}{|d_{1}|^{2}}}(\lambda _{1}-\lambda _{n})R^{-2(m-1)}\end{aligned}}}$

وبالتالي، فإن معدل التقارب يتحكم فيه بشكل رئيسي من خلال${\displaystyle R}$، لأن هذا الحد يتقلص بمعامل${\displaystyle R^{-2}}$لكل تكرار إضافي.

للمقارنة، يمكن للمرء أن ينظر في كيفية اعتماد معدل تقارب طريقة القوة على${\displaystyle \rho }$ولكن بما أن طريقة القوة حساسة بشكل أساسي لنسبة القيم المطلقة للقيم الذاتية، فنحن بحاجة إلى${\displaystyle |\lambda _{n}|\leqslant |\lambda _{2}|}$للفجوة الذاتية بين${\displaystyle \lambda _{1}}$و${\displaystyle \lambda _{2}}$أن تكون الطرف المهيمن. في ظل هذا القيد، فإن الحالة التي تُرجّح كفة أسلوب القوة هي تلك التي${\displaystyle \lambda _{n}=-\lambda _{2}}$لذا ضع ذلك في اعتبارك. في المراحل الأخيرة من طريقة القوة، متجه التكرار:

${\displaystyle u=(1-t^{2})^{1/2}z_{1}+tz_{2}\approx z_{1}+tz_{2},}$^{[ ملاحظة 1 ]}

حيث تؤدي كل تكرارة جديدة فعلياً إلى مضاعفة${\displaystyle z_{2}}$-السعة${\displaystyle t}$بواسطة

${\displaystyle {\frac {\lambda _{2}}{\lambda _{1}}}={\frac {\lambda _{2}}{\lambda _{2}+(\lambda _{1}-\lambda _{2})}}={\frac {1}{1+{\frac {\lambda _{1}-\lambda _{2}}{\lambda _{2}}}}}={\frac {1}{1+2\rho }}.}$

ثم يكون تقدير أكبر قيمة ذاتية هو

${\displaystyle u^{*}Au=(1-t^{2})\lambda _{1}+t^{2}\lambda _{2},}$

لذا ينبغي مقارنة الحد الأعلى لمعدل تقارب خوارزمية لانكزوس بـ

${\displaystyle \lambda _{1}-u^{*}Au=(\lambda _{1}-\lambda _{2})t^{2},}$

والذي يتقلص بمعامل${\displaystyle (1+2\rho )^{-2}}$لكل تكرار. وبالتالي، فإن الفرق يكمن في ذلك بين${\displaystyle 1+2\rho }$و${\displaystyle R=1+2\rho +2{\sqrt {\rho ^{2}+\rho }}}$في${\displaystyle \rho \gg 1}$المنطقة، الأخيرة أشبه بـ${\displaystyle 1+4\rho }$ويؤدي أداءً مماثلاً لطريقة القوة مع فجوة ذاتية أكبر بمرتين؛ وهو تحسن ملحوظ. إلا أن الحالة الأكثر تعقيدًا هي حالة${\displaystyle \rho \ll 1,}$في أي${\displaystyle R\approx 1+2{\sqrt {\rho }}}$يُعدّ هذا تحسّناً أكبر على الفجوة الذاتية؛${\displaystyle \rho \gg 1}$المنطقة هي التي يحقق فيها خوارزمية لانكزوس أقل تحسن من حيث التقارب مقارنةً بطريقة القوة.

في عام 1995، نشر بيتر مونتغمري خوارزمية، تستند إلى خوارزمية لانكزوس، لإيجاد عناصر الفضاء الصفري لمصفوفة متفرقة كبيرة على GF(2) ؛ نظرًا لأن مجموعة الأشخاص المهتمين بالمصفوفات المتفرقة الكبيرة على الحقول المنتهية ومجموعة الأشخاص المهتمين بمسائل القيم الذاتية الكبيرة نادرًا ما تتداخل، فإن هذا يسمى غالبًا خوارزمية لانكزوس الكتلية دون التسبب في ارتباك غير معقول.