خوارزمية جاكوبي للقيم الذاتية

الموسوعة الحرة

في الجبر الخطي العددي ، تُعد خوارزمية جاكوبي للقيم الذاتية طريقة تكرارية لحساب القيم الذاتية والمتجهات الذاتية لمصفوفة متناظرة حقيقية (وهي عملية تُعرف باسم التقطير ). سُميت هذه الخوارزمية نسبةً إلى كارل غوستاف جاكوب جاكوبي ، الذي اقترحها لأول مرة عام 1846، [ 1 ] ولكنها لم تُستخدم على نطاق واسع إلا في خمسينيات القرن العشرين مع ظهور الحواسيب. [ 2 ]

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

وصف

يتركS{\displaystyle S}لتكن مصفوفة متناظرة، وجي=جي(أنا،ج،θ){\displaystyle G=G(i,j,\theta )}لتكن مصفوفة دوران جيفنز . إذن:

S′=جي⊤Sجي{\displaystyle S'=G^{\top }SG\,}

متناظر ومماثل لـS{\displaystyle S}.

بالإضافة إلى،S′{\displaystyle S^{\prime }}يحتوي على مدخلات:

Sأناأنا′=ج2Sأناأنا-2sجSأناج+s2SججSجج′=s2Sأناأنا+2sجSأناج+ج2SججSأناج′=Sجأنا′=(ج2-s2)Sأناج+sج(Sأناأنا-Sجج)Sأناك′=Sكأنا′=جSأناك-sSجكك≠أنا،جSجك′=Sكج′=sSأناك+جSجكك≠أنا،جSكل′=Sكلك،ل≠أنا،ج{\displaystyle {\begin{aligned}S'_{ii}&=c^{2}\,S_{ii}-2\,sc\,S_{ij}+s^{2}\,S_{jj}\\S'_{jj}&=s^{2}\,S_{ii}+2sc\,S_{ij}+c^{2}\, S_ {jj}\\S'_{ij}&=S'_{ji}=(c^{2}-s^{2})\,S_{ij}+sc\,(S_{ii}-S_{jj})\\S'_{ik}&=S'_{ki}=c\,S_{ik}-s\,S_{jk}&k\neq أنا،j\\S'_{jk}&=S'_{kj}=s\,S_{ik}+c\,S_{jk}&k\neq i,j\\S'_{kl}&=S_{kl}&k,l\neq i,j\end{aligned}}}

أينs=الخطيئة⁡(θ){\displaystyle s=\sin(\theta )}وج=كوس⁡(θ){\displaystyle c=\cos(\theta )}.

منذجي{\displaystyle G}متعامد،S{\displaystyle S}وS′{\displaystyle S^{\prime }}لها نفس معيار فروبينيوس||⋅||F{\displaystyle ||\cdot ||_{F}}(مجموع الجذر التربيعي لمربعات جميع المكونات)، ومع ذلك يمكننا الاختيارθ{\displaystyle \theta }بحيثSأناج′=0{\displaystyle S_{ij}^{\prime }=0}وفي هذه الحالةS′{\displaystyle S^{\prime }}مجموع مربعات أكبر على القطر:

Sأناج′=كوس⁡(2θ)Sأناج+12الخطيئة⁡(2θ)(Sأناأنا-Sجج){\displaystyle S'_{ij}=\cos(2\theta )S_{ij}+{\tfrac {1}{2}}\sin(2\theta )(S_{ii}-S_{jj})}

اجعل هذا يساوي صفرًا، ثم أعد ترتيبه:

لون برونزي⁡(2θ)=2SأناجSجج-Sأناأنا{\displaystyle \tan(2\theta )={\frac {2S_{ij}}{S_{jj}-S_{ii}}}}

لوSجج=Sأناأنا{\displaystyle S_{jj}=S_{ii}}

θ=π4{\displaystyle \theta ={\frac {\pi }{4}}}

لتحسين هذا التأثير، يجب أن يكون S ij هو العنصر غير القطري ذو القيمة المطلقة الأكبر ، والذي يسمى المحور .

تُجري طريقة جاكوبي للقيم الذاتية عمليات تدوير متكررة حتى تصبح المصفوفة شبه قطرية. عندئذٍ، تُصبح العناصر الموجودة في القطر تقريبات للقيم الذاتية (الحقيقية) للمصفوفة S.

التقارب

لو ص=Sكل{\displaystyle p=S_{kl}} إذا كان عنصرًا محوريًا ، فبحسب التعريف |Sأناج|≤|ص|{\displaystyle |S_{ij}|\leq |p|} ل 1≤أنا،ج≤ن،أنا≠ج{\displaystyle 1\leq i,j\leq n,i\neq j}. يتركΓ(S)2{\displaystyle \Gamma (S)^{2}}يرمز إلى مجموع مربعات جميع العناصر غير القطرية لـS{\displaystyle S}. منذS{\displaystyle S}يحتوي بالضبط 2شمال:=ن(ن-1){\displaystyle 2N:=n(n-1)} بالنسبة للعناصر غير القطرية، لدينا ص2≤Γ(S)2≤2شمالص2{\displaystyle p^{2}\leq \Gamma (S)^{2}\leq 2Np^{2}} أو2ص2≥Γ(S)2/شمال{\displaystyle 2p^{2}\geq \Gamma (S)^{2}/N}. الآنΓ(Sج)2=Γ(S)2-2ص2{\displaystyle \Gamma (S^{J})^{2}=\Gamma (S)^{2}-2p^{2}}وهذا يعني Γ(Sج)2≤(1-1/شمال)Γ(S)2{\displaystyle \Gamma (S^{J})^{2}\leq (1-1/N)\Gamma (S)^{2}} أو Γ(Sج)≤(1-1/شمال)1/2Γ(S){\displaystyle \Gamma (S^{J})\leq (1-1/N)^{1/2}\Gamma (S)}أي أن سلسلة دورانات جاكوبي تتقارب خطيًا على الأقل بمعامل (1-1/شمال)1/2{\displaystyle (1-1/N)^{1/2}} إلى مصفوفة قطرية .

عدد منشمال{\displaystyle N}تُسمى دورات جاكوبي بالمسح؛ دعSσ{\displaystyle S^{\sigma }}لنرمز إلى النتيجة. التقدير السابق يعطي

Γ(Sσ)≤(1-1شمال)شمال/2Γ(S){\displaystyle \Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)}؛

أي أن سلسلة عمليات المسح تتقارب خطيًا على الأقل بمعامل ≈هـ1/2{\displaystyle e^{1/2}}.

مع ذلك، فإن النتيجة التالية لشونهاج [ 3 ] تؤدي إلى تقارب تربيعي محلي. ولتحقيق هذه الغاية، لنفترض أن S لها m قيمة ذاتية مميزة. λ1،...،λم{\displaystyle \lambda _{1},...,\lambda _{m}} مع التعددية ν1،...،νم{\displaystyle \nu _{1},...,\nu _{m}} ولنفترض أن d > 0 هي أقصر مسافة بين قيمتين ذاتيتين مختلفتين. ولنسمِّ عددًا من

شمالS:=ن(ن-1)2-∑μ=1م12νμ(νμ-1)≤شمال{\displaystyle N_{S}:={\frac {n(n-1)}{2}}-\sum _{\mu =1}^{m}{\frac {1}{2}}\nu _{\mu }(\nu _{\mu }-1)\leq N}

يقوم جاكوبي بتدوير عملية اكتساح Schönhage. لو Ss{\displaystyle S^{s}} يشير إلى النتيجة إذن

Γ(Ss)≤ن2-1(γ2د-2γ)،γ:=Γ(S)\displaystyle \Gamma (S^{s})\leq {\sqrt {{\frac {n}{2}}-1}}\left({\frac {\gamma ^{2}}{d-2\gamma }}\right),\quad \gamma :=\Gamma (S)} .

وبالتالي يصبح التقارب تربيعيًا بمجرد Γ(S)<د2+ن2-1{\displaystyle \Gamma (S)<{\frac {d}{2+{\sqrt {{\frac {n}{2}}-1}}}}}

يكلف

يمكن إجراء كل دورة جيفنز فييا(ن){\displaystyle O(n)}الخطوات عندما يكون العنصر المحوري p معروفًا. ومع ذلك ، يتطلب البحث عن p فحص جميع العناصر غير القطرية البالغ عددها N  ≈ 1/2 n² ، مما يعني أن هذا البحث يهيمن على التعقيد الإجمالي ويرفع التعقيد الحسابي لعملية المسح في خوارزمية جاكوبي الكلاسيكية إلى  يا(ن4){\displaystyle O(n^{4})}. تحقق الخوارزميات المتنافسةيا(ن3){\displaystyle O(n^{3})}التعقيد اللازم للقطر الكامل.

الحد الأقصى لصفوف التخزين المؤقت

يمكننا تقليل تعقيد إيجاد العنصر المحوري من O( N ) إلى O( n ) إذا أدخلنا مصفوفة فهرس إضافية. م1،...،من-1{\displaystyle m_{1},\,\dots \,,\,m_{n-1}} مع العقار الذيمأنا{\displaystyle m_{i}} يمثل فهرس أكبر عنصر في الصف i ، (حيث i = 1، ...، n − 1) من المجموعة S الحالية . عندئذٍ، يجب أن يكون فهرسا العنصر المحوري ( k ، l ) أحد الزوجين التاليين.  (أنا،مأنا){\displaystyle (i,m_{i})}كما يمكن تحديث مصفوفة الفهرس في حالة تعقيد متوسطة قدرها O( n ) : أولًا، يمكن إيجاد القيمة القصوى في الصفين المُحدَّثين k و l في O( n ) خطوة. في الصفوف الأخرى i ، تتغير القيم في العمودين k و l فقط . بالتكرار على هذه الصفوف، إذامأنا{\displaystyle m_{i}}إذا لم يكن k أو l ، يكفي مقارنة القيمة القصوى القديمة عندمأنا{\displaystyle m_{i}}إضافة المدخلات الجديدة وتحديثهامأنا{\displaystyle m_{i}}إذا لزم الأمر. إذامأنا{\displaystyle m_{i}}يجب أن تكون القيمة مساوية لـ k أو l ، ويتم إنقاص العنصر المقابل أثناء التحديث. يجب إيجاد القيمة القصوى في الصف i من البداية في تعقيد زمني قدره O( n ). ومع ذلك، سيحدث هذا في المتوسط ​​مرة واحدة فقط لكل دورة. وبالتالي، فإن كل دورة لها تعقيد زمني قدره O( n ) ، ومسح واحد له تعقيد زمني قدره O( n³ ) في الحالة المتوسطة، وهو ما يعادل عملية ضرب مصفوفة واحدة . بالإضافة إلى ذلك، مأنا{\displaystyle m_{i}} يجب تهيئتها قبل بدء العملية، وهو ما يمكن القيام به في خطوتين .

عادةً ما تتقارب طريقة جاكوبي ضمن الدقة العددية بعد عدد قليل من عمليات المسح. لاحظ أن القيم الذاتية المتعددة تقلل من عدد التكرارات لأنشمالS<شمال{\displaystyle N_{S}<N}.

جاكوبي الدوري والمتوازي

ثمة نهج بديل يتمثل في الاستغناء عن البحث تمامًا، والاكتفاء بجعل كل مسح يدور حول كل عنصر غير قطري مرة واحدة، بترتيب محدد مسبقًا. وقد ثبت أن خوارزمية جاكوبي الدورية هذه تحقق تقاربًا تربيعيًا، [ 4 ] [ 5 ] تمامًا مثل خوارزمية جاكوبي الكلاسيكية.

تعتمد إمكانية التوازي الخاصة بخوارزمية جاكوبي على الجمع بين خوارزمية جاكوبي الدورية وملاحظة أن دورانات جيفنز لمجموعات منفصلة من المؤشرات تتبادل، بحيث يمكن تطبيق عدة دورانات بالتوازي. وبشكل ملموس، إذاجي1{\displaystyle G_{1}}محاور بين المؤشراتأنا1،ج1{\displaystyle i_{1},j_{1}}وجي2{\displaystyle G_{2}}محاور بين المؤشراتأنا2،ج2{\displaystyle i_{2},j_{2}}ثم من{أنا1،ج1}∩{أنا2،ج2}=∅{\displaystyle \{i_{1},j_{1}\}\cap \{i_{2},j_{2}\}=\varnothing }يتبعجي1جي2=جي2جي1{\displaystyle G_{1}G_{2}=G_{2}G_{1}}لأن في مجال الحوسبةجي1جي2أ{\displaystyle G_{1}G_{2}A}أوجي2جي1أ{\displaystyle G_{2}G_{1}A}الجي1{\displaystyle G_{1}}لا يحتاج التدوير إلا إلى الوصول إلى الصفوفأنا1،ج1{\displaystyle i_{1},j_{1}}وجي2{\displaystyle G_{2}}لا يحتاج التدوير إلا إلى الوصول إلى الصفوفأنا2،ج2{\displaystyle i_{2},j_{2}}يمكن للمعالجين تنفيذ كلا الدورانين بالتوازي، لأنه لا يتم الوصول إلى أي عنصر من عناصر المصفوفة لكليهما.

إن تقسيم مجموعة أزواج المؤشرات في عملية مسح إلى فئات منفصلة مثنى مثنى يُكافئ تقسيم مجموعة حواف الرسم البياني الكامل إلى تطابقات ، وهو ما يُعادل تلوين الحواف ؛ فتصبح كل فئة لونية جولةً ضمن عملية المسح. ويُعرف الحد الأدنى لعدد الجولات بالمؤشر اللوني للرسم البياني الكامل، ويساوين{\displaystyle n}للفردين{\displaystyle n}لكنن-1{\displaystyle n-1}حتىن{\displaystyle n}قاعدة بسيطة للأعداد الفرديةن{\displaystyle n}تتمثل مهمتها في التعامل مع الأزواج{أنا1،ج1}{\displaystyle \{i_{1},j_{1}\}}و{أنا2،ج2}{\displaystyle \{i_{2},j_{2}\}}في نفس الجولة إذاأنا1+ج1≡أنا2+ج2(تعديلن){\displaystyle i_{1}+j_{1}\equiv i_{2}+j_{2}\textstyle {\pmod {n}}}حتىن{\displaystyle n}يمكن للمرء أن ينشئن-1{\displaystyle n-1}جولاتك=0،1،...،ن-2{\displaystyle k=0,1,\dotsc ,n-2}حيث زوج{أنا،ج}{\displaystyle \{i,j\}}ل1⩽أنا<ج⩽ن-1{\displaystyle 1\leqslant i<j\leqslant n-1}يدخل في الجولة(أنا+ج)تعديل(ن-1){\displaystyle (i+j){\bmod {(}}n-1)}بالإضافة إلى زوج{أنا،ن}{\displaystyle \{i,n\}}ل1⩽أنا⩽ن-1{\displaystyle 1\leqslant i\leqslant n-1}يدخل في الجولة2أناتعديل(ن-1){\displaystyle 2i{\bmod {(}}n-1)}وهذا يقلل من التعقيد الزمني لعملية المسح منيا(ن3){\displaystyle O(n^{3})}ليا(ن2){\displaystyle O(n^{2})}، لون/2{\displaystyle n/2}المعالجات متوفرة.

ستتألف الجولة من قيام كل معالج أولاً بحساب(ج،s){\displaystyle (c,s)}يتم تدوير المصفوفة، ثم تطبيق التدوير من اليسار (التدوير بين الصفوف). بعد ذلك، تتم مزامنة المعالجات قبل تطبيق تدوير النقل من اليمين (التدوير بين الأعمدة)، ثم تتم المزامنة مرة أخرى. يمكن لمعالجين الوصول إلى عنصر المصفوفة خلال جولة واحدة، ولكن ليس كلاهما خلال نفس نصف هذه الجولة.

يمكن تحقيق المزيد من التوازي عن طريق تقسيم العمل لدورة واحدة بين عدة معالجات، ولكن قد يصبح ذلك دقيقًا للغاية بحيث لا يكون عمليًا.

الخوارزمية

الخوارزمية التالية هي وصف لطريقة جاكوبي باستخدام رموز رياضية. تحسب هذه الخوارزمية متجهًا e يحتوي على القيم الذاتية ومصفوفة E تحتوي على المتجهات الذاتية المقابلة؛ أي،هـأنا{\displaystyle e_{i}} هي قيمة ذاتية والعمودهـأنا{\displaystyle E_{i}} متجه ذاتي متعامد لهـأنا{\displaystyle e_{i}}، i = 1، ...، n .

الإجراء جاكوبي ( S ∈ R n × n ؛ e ∈ R n ؛ E ∈ R n × n ) المتغيرات i ، k ، l ، m ، الحالة ∈ N ، s ، c ، t ، p ، y ، d ، r ∈ R، المؤشر ∈ N n ، المتغير ∈ L nدالة maxind( k ∈ N ) ∈ N ! فهرس أكبر عنصر غير قطري في الصف k، m := k + 1 ، من أجل i := k + 2 إلى n ، إذا كان | S ki | > | S km |، فإن m := i، نهاية الشرط ، نهاية الحلقة ، إرجاع m، نهاية الدالةالإجراء update( k ∈ N ; t ∈ R ) ! تحديث e k وحالته y := e k ; e k := y + t إذا تغيرت k و ( y = e k ) فإن changed k := false; state := state −1 وإذا لم تتغير k و ( y ≠ e k ) فإن changed k := true; state := state +1 endif endprocإجراء تدوير ( k ، l ، i ، j ∈ N ) ! قم بتدوير Sij ، Skl ┌ ┐ ┌ ┐┌ ┐ │ S كلل │ │ ج − الصورة ││ S كلل │ │ │ := │ ││ │ │ S ij │ │ s c ││ S ij │ └ ┘ └ ┘└ ┘ نهايةبروك ! تهيئة e و E والمصفوفات ind و changed E := I ; state := n for k := 1 to n do ind k := maxind( k ); e k := S kk ; changed k := true endfor while state ≠ 0 do ! الدوران التالي m := 1 ! إيجاد فهرس (k,l) للمحور p for k := 2 to n − 1 do if | S k ind k  | > | S m ind m  | then m := k endif endfor k := m ; l := ind m ; p := S kl ! حساب c = cos φ، s = sin φ y := ( e l − e k )/2; d := | y | + √( p 2 + y 2 ) r := √( p 2 + d 2 ); c := d / r ; s := p / r ; t := p 2 / d if y <0 then s := − s ; t := − t endif S kl := 0.0; update( k ,− t ); update( l , t ) ! تدوير الصفوف والأعمدة k و l من أجل i := 1 إلى k −1 قم بتدوير( i , k , i , l ) نهاية الحلقة من أجل i := k +1 إلى l −1 قم بتدوير( k , i , i , l ) نهاية الحلقة من أجل i := l +1 إلى n قم بتدوير( k , i , l , i ) نهاية الحلقة ! تدوير المتجهات الذاتية من أجل i := 1 إلى n قم ┌ ┐ ┌ ┐┌ ┐ │ ه إيك │ │ ج − ق ││ ه إيك │ │ │ := │ ││ │ │ إي إيل │ │ س ج ││ إي إيل │ └ ┘ └ ┘└ ┘ endfor ! تحديث جميع المؤشرات التي يُحتمل تغييرها ind i for i := 1 to n do ind i := maxind( i ) endfor loop endproc

ملحوظات

1. المصفوفة المنطقية المتغيرة تحتفظ بحالة كل قيمة ذاتية. إذا كانت القيمة العددية لـهـك{\displaystyle e_{k}} أوهـل{\displaystyle e_{l}}تتغير قيمة ` changed` خلال دورة تكرارية، ويتم تعيين المكون المقابل لها إلى `true` ، وإلا يتم تعيينه إلى `false` . يحسب المتغير ` state` عدد مكونات `changed` التي تحمل القيمة `true` . تتوقف الدورة التكرارية بمجرد أن تصبح قيمة `state` تساوي صفرًا. هذا يعني أن جميع التقريبات غير دقيقة.هـ1،...،هـن{\displaystyle e_{1},\,...\,,e_{n}} لقد تغيرت قيمته مؤخرًا، وبالتالي فمن غير المرجح أن يحدث ذلك إذا استمرت عملية التكرار. ويُفترض هنا أن عمليات الفاصلة العائمة تُقرّب على النحو الأمثل إلى أقرب عدد عشري.

2. يتلف المثلث العلوي للمصفوفة S بينما يبقى المثلث السفلي والقطر دون تغيير. وبالتالي، من الممكن استعادة S إذا لزم الأمر وفقًا لـ

لكل k := 1 إلى n − 1 ، قم بما يلي : استعد المصفوفة S. لكل l := k + 1 إلى n ، قم بما يلي: S kl := S lk. نهاية الحلقة. نهاية الحلقة.

3. لا تكون القيم الذاتية بالضرورة مرتبة تنازلياً. ويمكن تحقيق ذلك باستخدام خوارزمية فرز بسيطة.

لـ k := 1 إلى n − 1، اجعل m := k. لـ l := k + 1 إلى n، إذا كان el > em ، فاجعل m : = l. نهاية الشرط. نهاية الحلقة. إذا كان k ≠ m ، فبدّل em و k . بدّل Em و Ek . نهاية الشرط. نهاية الحلقة .

4. تمت كتابة الخوارزمية باستخدام تدوين المصفوفات (المصفوفات التي تبدأ من 1 بدلاً من المصفوفات التي تبدأ من 0).

5. عند تطبيق الخوارزمية، يجب تنفيذ الجزء المحدد باستخدام تدوين المصفوفة في وقت واحد.

٦. لا يُراعي هذا التطبيق بشكل صحيح حالة كون أحد الأبعاد فضاءً فرعياً مستقلاً. على سبيل المثال، إذا أُعطيت مصفوفة قطرية، فلن يتوقف التطبيق المذكور أعلاه أبداً، لأن أياً من القيم الذاتية لن يتغير. لذا، في التطبيقات العملية، يجب إضافة منطق إضافي لمراعاة هذه الحالة.

مثال

يترك S=(4-3060-35-30300-67542060-6751620-1050-35420-1050700){\displaystyle S={\begin{pmatrix}4&-30&60&-35\\-30&300&-675&420\\60&-675&1620&-1050\\-35&420&-1050&700\end{pmatrix}}}

ثم ينتج برنامج جاكوبي القيم الذاتية والمتجهات الذاتية التالية بعد 3 عمليات مسح (19 تكرارًا)  :

هـ1=2585.25381092892231{\displaystyle e_{1}=2585.25381092892231}

هـ1=(0.0291933231647860588-0.3287120557631889970.791411145833126331-0.514552749997152907){\displaystyle E_{1}={\begin{pmatrix}0.0291933231647860588\\-0.328712055763188997\\0.791411145833126331\\-0.514552749997152907\end{pmatrix}}}

هـ2=37.1014913651276582{\displaystyle e_{2}=37.1014913651276582}

هـ2=(-0.1791862905354548260.741917790628453435-0.100228136947192199-0.638282528193614892){\displaystyle E_{2}={\begin{pmatrix}-0.179186290535454826\\0.741917790628453435\\-0.100228136947192199\\-0.638282528193614892\end{pmatrix}}}

هـ3=1.4780548447781369{\displaystyle e_{3}=1.4780548447781369}

هـ3=(-0.5820756994972376500.3705021850670930580.5095786345017996260.514048272222164294){\displaystyle E_{3}={\begin{pmatrix}-0.582075699497237650\\0.370502185067093058\\0.509578634501799626\\0.514048272222164294\end{pmatrix}}}

هـ4=0.1666428611718905{\displaystyle e_{4}=0.1666428611718905}

هـ4=(0.7926082911637635850.4519231209015997940.3224163985818249920.252161169688241933){\displaystyle E_{4}={\begin{pmatrix}0.792608291163763585\\0.451923120901599794\\0.322416398581824992\\0.252161169688241933\end{pmatrix}}}

تطبيقات للمصفوفات المتناظرة الحقيقية

عندما تكون القيم الذاتية (والمتجهات الذاتية) لمصفوفة متناظرة معروفة، يمكن حساب القيم التالية بسهولة.

القيم المفردة
القيم المفردة لمصفوفة (مربعة)أ{\displaystyle A}هي الجذور التربيعية للقيم الذاتية (غير السالبة) لـأتيأ{\displaystyle A^{T}A}في حالة المصفوفة المتناظرةS{\displaystyle S}لدينا منSتيS=S2{\displaystyle S^{T}S=S^{2}}وبالتالي فإن القيم المفردة لـS{\displaystyle S}هي القيم المطلقة للقيم الذاتية لـS{\displaystyle S}.
المعيار 2 ونصف القطر الطيفي
المعيار 2 للمصفوفة A هو المعيار القائم على معيار المتجه الإقليدي؛ أي القيمة الأكبر‖أx‖2{\displaystyle \|Ax\|_{2}}عندما يمر x عبر جميع المتجهات مع‖x‖2=1{\displaystyle \|x\|_{2}=1}وهي أكبر قيمة مفردة لـأ{\displaystyle A}في حالة المصفوفة المتناظرة، تكون القيمة المطلقة الأكبر لمتجهاتها الذاتية، وبالتالي تساوي نصف قطرها الطيفي .
رقم الحالة
رقم حالة المصفوفة غير المنفردةأ{\displaystyle A}يُعرَّف بأنه الحالة(أ)=‖أ‖2‖أ-1‖2{\displaystyle {\mbox{cond}}(A)=\|A\|_{2}\|A^{-1}\|_{2}}في حالة المصفوفة المتناظرة، يُمثل هذا القيمة المطلقة لحاصل قسمة أكبر قيمة ذاتية على أصغر قيمة ذاتية. قد تُؤدي المصفوفات ذات أرقام الحالة الكبيرة إلى نتائج غير مستقرة عدديًا، حيث يُمكن أن يُؤدي اضطراب بسيط إلى أخطاء كبيرة. تُعد مصفوفات هيلبرت أشهر المصفوفات سيئة التكييف. على سبيل المثال، يبلغ رقم ​​حالة مصفوفة هيلبرت من الرتبة الرابعة 15514، بينما يبلغ 2.7  ×  10⁸ لمصفوفة من الرتبة الثامنة .
رتبة
مصفوفةأ{\displaystyle A}لديه رتبةر{\displaystyle r}إذا كان لديهر{\displaystyle r}الأعمدة المستقلة خطيًا، بينما الأعمدة المتبقية تعتمد خطيًا على هذه الأعمدة. أو بعبارة أخرى،ر{\displaystyle r}هو بُعد نطاق أ{\displaystyle A}علاوة على ذلك، فهو عدد القيم المفردة غير الصفرية.
في حالة المصفوفة المتناظرة، يُمثل r عدد القيم الذاتية غير الصفرية. لسوء الحظ، وبسبب أخطاء التقريب، قد لا تكون التقريبات العددية للقيم الذاتية الصفرية صفرًا (وقد يحدث أيضًا أن يكون التقريب العددي صفرًا بينما القيمة الحقيقية ليست كذلك). لذا، لا يمكن حساب الرتبة العددية إلا بتحديد أي من القيم الذاتية قريبة بما يكفي من الصفر.
المعكوس الزائف
المعكوس الزائف للمصفوفةأ{\displaystyle A}هي المصفوفة الفريدةX=أ+{\displaystyle X=A^{+}}والتيأX{\displaystyle AX}وXأ{\displaystyle XA}متناظرة والتيأXأ=أ،XأX=X{\displaystyle AXA=A,XAX=X}يحفظ. إذاأ{\displaystyle A}إذا كانت غير منفردة،أ+=أ-1{\displaystyle A^{+}=A^{-1}}.
عند استدعاء الإجراء jacobi (S, e, E)، فإن العلاقةS=هـتيالتشخيص(هـ)هـ{\displaystyle S=E^{T}{\mbox{Diag}}(e)E}يتحقق ذلك حيث تشير Diag( e ) إلى المصفوفة القطرية التي تحتوي على المتجه e على القطر.هـ+{\displaystyle e^{+}}لنرمز إلى المتجه حيث هـأنا{\displaystyle e_{i}}يتم استبدالها بـ1/هـأنا{\displaystyle 1/e_{i}}لو هـأنا≤0{\displaystyle e_{i}\leq 0}وبـ 0 إذا هـأنا{\displaystyle e_{i}}وهي (قريبة عدديًا من) الصفر. وبما أن المصفوفة E متعامدة، فإن المعكوس الزائف للمصفوفة S يُعطى بالصيغة التالية: S+=هـتيالتشخيص(هـ+)هـ{\displaystyle S^{+}=E^{T}{\mbox{Diag}}(e^{+})E}.
حل المربعات الصغرى
إذا كانت المصفوفةأ{\displaystyle A} إذا لم يكن النظام الخطي كامل الرتبة، فقد لا يكون له حل. أx=ب{\displaystyle Ax=b}ومع ذلك، يمكن البحث عن متجه x الذي يكون فيه ‖أx-ب‖2{\displaystyle \|Ax-b\|_{2}}هو الحد الأدنى. الحل هوx=أ+ب{\displaystyle x=A^{+}b}في حالة المصفوفة المتناظرة S كما سبق، يكون لديناx=S+ب=هـتيالتشخيص(هـ+)هـب{\displaystyle x=S^{+}b=E^{T}{\mbox{Diag}}(e^{+})Eb}.
مصفوفة أسية
منS=هـتيالتشخيص(هـ)هـ{\displaystyle S=E^{T}{\mbox{Diag}}(e)E}يجد المرءخبرة⁡S=هـتيالتشخيص(خبرة⁡هـ)هـ{\displaystyle \exp S=E^{T}{\mbox{Diag}}(\exp e)E}حيث إكس هـ{\displaystyle e} هو المتجه حيثهـأنا{\displaystyle e_{i}}يتم استبدالها بـخبرة⁡هـأنا{\displaystyle \exp e_{i}}وبالمثل،و(S){\displaystyle f(S)} يمكن حسابها بطريقة واضحة لأي دالة (تحليلية)و{\displaystyle f}.
المعادلات التفاضلية الخطية
المعادلة التفاضلية x′=أx،x(0)=أ{\displaystyle x'=Ax,x(0)=a}لديه الحلx(ت)=خبرة⁡(تأ){\displaystyle x(t)=\exp(tA)}بالنسبة للمصفوفة المتناظرةS{\displaystyle S}وبناءً على ذلك x(ت)=هـتيالتشخيص(خبرة⁡تهـ)هـأ{\displaystyle x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea}. لو أ=∑أنا=1نأأناهـأنا{\displaystyle a=\sum _{i=1}^{n}a_{i}E_{i}}هو توسعأ{\displaystyle a} بواسطة المتجهات الذاتية لـS{\displaystyle S}، ثمx(ت)=∑أنا=1نأأناخبرة⁡(تهـأنا)هـأنا{\displaystyle x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}}.
يترك دبليوs{\displaystyle W^{s}}ليكن الفضاء المتجهي الذي تولده المتجهات الذاتية لـS{\displaystyle S}والتي تتوافق مع قيمة ذاتية سالبة ودبليوu{\displaystyle W^{u}}وبالمثل بالنسبة للقيم الذاتية الموجبة. إذا أ∈دبليوs{\displaystyle a\in W^{s}}ثمليمت→∞x(ت)=0{\displaystyle {\mbox{lim}}_{t\rightarrow \infty }x(t)=0}أي أن نقطة التوازن 0 جاذبة لـx(ت){\displaystyle x(t)}. لوأ∈دبليوu{\displaystyle a\in W^{u}}ثمليمت→∞x(ت)=∞{\displaystyle {\mbox{lim}}_{t\rightarrow \infty }x(t)=\infty }أي أن الصفر ينفر من x(ت){\displaystyle x(t)}.دبليوs{\displaystyle W^{s}}ودبليوu{\displaystyle W^{u}}تُسمى هذه المشعبات بالمشعبات المستقرة وغير المستقرة لـS{\displaystyle S}. لوأ{\displaystyle a}إذا كان هناك مكونات في كلا المشعبين، فإن أحد المكونات ينجذب والآخر يتنافر.x(ت){\displaystyle x(t)}الأساليبدبليوu{\displaystyle W^{u}}مثلت→∞{\displaystyle t\to \infty }.

تطبيق جوليا

الكود التالي هو تطبيق مباشر للوصف الرياضي لخوارزمية جاكوبي للقيم الذاتية في لغة برمجة جوليا .

باستخدام الجبر الخطي ، اختباردالة find_pivot ( Sprime ) n = حجم ( Sprime ، 1 ) pivot_i = pivot_j = 0 pivot = 0.0لـ j = 1 : n لـ i = 1 : ( j - 1 ) إذا كانت القيمة المطلقة لـ Sprime [ i , j ] أكبر من pivot ، فإن pivot_i = i و pivot_j = j و pivot = القيمة المطلقة لـ Sprime [ i , j ] نهاية نهاية نهايةreturn ( pivot_i , pivot_j , pivot ) end# عمليًا، لا ينبغي إنشاء دالة مصفوفة دوران جيفنز بشكل صريح. givens_rotation_matrix ( n , i , j , θ ) G = Matrix { Float64 } ( I ,( n , n )) G [ i , i ] = G [ j , j ] = cos ( θ ) G [ i , j ] = sin ( θ ) G [ j , i ] = - sin ( θ ) return G end# S هي مصفوفة متناظرة من الرتبة n × n ، n = 4 ، sqrtS = randn ( n , n ); S = sqrtS * sqrtS ' ;# أكبر عنصر مسموح به خارج القطر الرئيسي للمصفوفة U' * S * U # حيث U هي المتجهات الذاتية tol = 1e-14Sprime = نسخة ( S ) U = مصفوفة { Float64 }( I ,( n , n ))بينما صحيح ( pivot_i ، pivot_j ، pivot ) = find_pivot ( Sprime )إذا كان المحور < التسامح، فتوقف .θ = اتان ( 2 * Sprime [ Pivot_i , Pivot_j ] / ( Sprime [ Pivot_j , Pivot_j ] - Sprime [ Pivot_i , Pivot_i ] )) / 2G = givens_rotation_matrix ( n , pivot_i , pivot_j , θ )# تحديث Sprime و U Sprime .= G '* Sprime * G U .= U * G end# أصبحت Sprime الآن (تقريبًا) مصفوفة قطرية # استخراج القيم الذاتية λ = diag ( Sprime )# فرز القيم الذاتية (والمتجهات الذاتية المقابلة U) حسب القيم المتزايدة i = sortperm ( λ ) λ = λ [ i ] U = U [ : , i ]# يجب أن تكون S مساوية لـ U * diagm(λ) * U' @test S ≈ U * diagm ( λ ) * U '

التعميمات

تم تعميم طريقة جاكوبي لتشمل المصفوفات الهرميتية المعقدة ، والمصفوفات الحقيقية والمعقدة غير المتناظرة العامة، بالإضافة إلى المصفوفات الكتلية.

بما أن القيم المفردة لمصفوفة حقيقية هي الجذور التربيعية للقيم الذاتية للمصفوفة المتناظرةS=أتيأ{\displaystyle S=A^{T}A}يمكن استخدامه أيضًا لحساب هذه القيم. في هذه الحالة، يتم تعديل الطريقة بحيث لا يلزم حساب S بشكل صريح، مما يقلل من خطر أخطاء التقريب . لاحظ أنجSجتي=جأتيأجتي=جأتيجتيجأجتي=بتيب{\displaystyle JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B} مع ب:=جأجتي{\displaystyle B\,:=JAJ^{T}}.

مراجع

  1. ^ جاكوبي، CGJ (1846). "Über ein leichtes Verfahren، die in der Theorie der Säkularstörungen vorkommenden Gleichungen numerisch aufzulösen" . مجلة كريل (باللغة الألمانية). 1846 (30): 51–94 . دوى : 10.1515/crll.1846.30.51 . S2CID 199546177 . 
  2. ↑ غولوب، جي إتش ؛ فان دير فورست، إتش إيه (2000). "حساب القيم الذاتية في القرن العشرين" . مجلة الرياضيات الحسابية والتطبيقية . 123 ( 1-2 ): 35-65 . doi : 10.1016/S0377-0427(00)00413-1 .
  3. ^ شونهاج، أ. (1964). "Zur Quadratischen Konvergenz des Jacobi-Verfahrens". Numerische Mathematik (باللغة الألمانية). 6 (1): 410-412 . دوى : 10.1007 / BF01386091 . السيد 0174171 . S2CID 118301078 .  
  4. ↑ ويلكنسون، جيه إتش (1962). "ملاحظة حول التقارب التربيعي لعملية جاكوبي الدورية". الرياضيات العددية . 6 : 296-300 . doi : 10.1007/BF01386321 .
  5. ↑ فان كيمبن، إتش بي إم (1966). "حول التقارب التربيعي لطريقة جاكوبي الدورية الخاصة". الرياضيات العددية . 9 : 19-22 . doi : 10.1007/BF02165225 .

للمزيد من القراءة

  • بريس، دبليو إتش؛ تيوكولسكي، إس إيه؛ فيترلينغ، دبليو تي؛ فلانيري، بي بي (2007)، "القسم 11.1. تحويلات جاكوبي لمصفوفة متناظرة" ، وصفات عددية: فن الحوسبة العلمية (  الطبعة الثالثة)، نيويورك: مطبعة جامعة كامبريدج، ISBN 978-0-521-88068-8تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 11 أغسطس 2011 ، وتمت معاينته بتاريخ 13 أغسطس 2011.
  • روتيسهاوزر، هـ. (1966). “سلسلة كتيبات الجبر الخطي: طريقة جاكوبي للمصفوفات المتماثلة الحقيقية”. الرياضيات الرقمية . 9 (1): 1– 10. دوى : 10.1007/BF02165223 . السيد 1553948 . S2CID 120520713 .  
  • سامح، أ.ح. (1971). " حول خوارزميات جاكوبي وما يشابهها للحاسوب المتوازي" . رياضيات الحوسبة . 25 (115): 579-590 . doi : 10.1090/s0025-5718-1971-0297131-6 . JSTOR 2005221. MR 0297131 .  
  • شروف، غوتام م. (1991). " خوارزمية متوازية للقيم الذاتية والمتجهات الذاتية لمصفوفة عقدية عامة". الرياضيات العددية . 58 (1): 779-805 . CiteSeerX 10.1.1.134.3566 . doi : 10.1007/BF01385654 . MR 1098865. S2CID 13904356 .   
  • فيسيليتش، ك. (1979). "حول فئة من الإجراءات الشبيهة بجاكوبي لقطرنة المصفوفات الحقيقية العشوائية". الرياضيات العددية . 33 (2): 157-172 . doi : 10.1007/BF01399551 . MR 0549446. S2CID 119919630 .  
  • فيسيليتش، ك.؛ وينزل، هـ. ج. (1979). "طريقة جاكوبي متقاربة تربيعيًا للمصفوفات الحقيقية ذات القيم الذاتية المركبة". الرياضيات العددية . 33 (4): 425-435 . doi : 10.1007/BF01399324 . MR 0553351. S2CID 119554420 .  
  • يوسف سعد: "إعادة النظر في طريقة تدوير فضاء جاكوبي الجزئي (الكتلي) لمسألة القيم الذاتية المتناظرة"، الخوارزميات العددية، المجلد 92 (2023)، الصفحات 917-944 . https://doi.org/10.1007/s11075-022-01377-w