عنصر محوري

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

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

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

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

${\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&0&-1&-11\\0&2&-1&-3\end{array}}\right]}$

النظام الناتج عن التمحور هو كما يلي، وسيسمح لخوارزمية الحذف والاستبدال العكسي بإخراج الحل إلى النظام.

${\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&2&-1&-3\\0&0&-1&-11\end{array}}\right]}$

علاوة على ذلك، يُفضّل عمومًا في طريقة الحذف الغاوسي اختيار عنصر محوري ذي قيمة مطلقة كبيرة ، مما يُحسّن الاستقرار العددي . ويتأثر النظام التالي بشكل كبير بخطأ التقريب عند تطبيق الحذف الغاوسي والتعويض العكسي.

${\displaystyle \left[{\begin{array}{cc|c}0.00300&59.14&59.17\\5.291&-6.130&46.78\\\end{array}}\right]}$

يملك هذا النظام الحل الدقيق x₁ = 10.00 و x₂ = 1.000، ولكن عند تطبيق خوارزمية الحذف والتعويض العكسي باستخدام حسابات مكونة من أربعة أرقام، تتسبب القيمة الصغيرة للعدد _{11 في} انتشار _أخطاء تقريبية طفيفة. تعطي الخوارزمية بدون التمحور تقريبًا x₁ ≈ 9873.3 و x₂ ≈ 4. في هذه الحالة _، يُفضّل تبديل الصفين بحيث يكون العدد ₂₁ في موضع التمحور _.

${\displaystyle \left[{\begin{array}{cc|c}5.291&-6.130&46.78\\0.00300&59.14&59.17\\\end{array}}\right].}$

بالنظر إلى هذا النظام، فإن خوارزمية الحذف والتعويض العكسي باستخدام العمليات الحسابية المكونة من أربعة أرقام تعطي القيم الصحيحة x ₁ = 10.00 و x ₂ = 1.000.

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

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

هناك استراتيجية أخرى، تُعرف باسم "محور الرخ"، تُبدّل أيضًا الصفوف والأعمدة، لكنها تضمن فقط أن يكون العنصر المحوري المُختار هو أكبر عنصر ممكن في صفه وعموده في آنٍ واحد، وليس أكبر عنصر ممكن في المصفوفة الفرعية المتبقية بأكملها. ^{[ 2 ]} عند تطبيق هذه الاستراتيجية على الحواسيب التسلسلية، تكون تكلفتها المتوقعة ثلاثة أضعاف تكلفة المحور الجزئي تقريبًا، وبالتالي فهي أرخص من المحور الكامل. وقد ثبت أن محور الرخ أكثر استقرارًا من المحور الجزئي، نظريًا وعمليًا.

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

${\displaystyle \left[{\begin{array}{cc|c}30&591400&591700\\5.291&-6.130&46.78\\\end{array}}\right]}$

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

تتضمن هذه المقالة مواد من Pivoting on PlanetMath ، المرخصة بموجب رخصة Creative Commons Attribution/Share-Alike .

• آر إل بيردن، جيه دي فيرز، التحليل العددي ، الطبعة الثامنة، تومسون بروكس/كول، 2005. رقم ISBN 0-534-39200-8
• جي إتش غولوب، سي إف لون، حسابات المصفوفات ، الطبعة الثالثة، جونز هوبكنز، 1996. ISBN 0-8018-5414-8.
• فوكودا، كومي ؛ تيرلاكي، تاماس (1997). توماس م. ليبلينغ؛ دومينيك دي ويرا (محرران). "طرق التقاطع: نظرة جديدة على خوارزميات المحور". البرمجة الرياضية، السلسلة ب . أوراق من  الندوة الدولية السادسة عشرة حول البرمجة الرياضية التي عُقدت في لوزان،  1997. 79 ( 1-3 ): 369-395 . CiteSeerX 10.1.1.36.9373 . doi : 10.1007/BF02614325 . MR 1464775. S2CID 2794181. نسخة أولية بصيغة Postscript .   
• تيرلاكي، تاماس؛ تشانغ، شو  تشونغ (1993). "قواعد المحور للبرمجة الخطية: دراسة استقصائية للتطورات النظرية الحديثة". حوليات بحوث العمليات . الانحلال في مسائل التحسين. 46-47 (1): 203-233 . CiteSeerX 10.1.1.36.7658 . doi : 10.1007/BF02096264 . ISSN 0254-5330 . MR 1260019. S2CID 6058077 .