الجبر الخطي العددي

📅 آخر تحديث: ٢٤ يوليو ٢٠٢٦
✍️ نُشر في: ٢٤ يوليو ٢٠٢٦
📷 يحتوي على 32 صور
الموسوعة الحرة

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

يهدف الجبر الخطي العددي إلى حل مسائل الرياضيات المتصلة باستخدام حواسيب ذات دقة محدودة، لذا فإن تطبيقاته في العلوم الطبيعية والاجتماعية واسعة النطاق تمامًا كتطبيقات الرياضيات المتصلة. غالبًا ما يُعد جزءًا أساسيًا من مسائل الهندسة وعلوم الحاسوب ، مثل معالجة الصور والإشارات ، والاتصالات ، والتمويل الحاسوبي ، ومحاكاة علوم المواد ، وعلم الأحياء البنيوي ، واستخراج البيانات ، والمعلوماتية الحيوية ، وديناميكا الموائع ، والإحصاء الحاسوبي . تُستخدم طرق المصفوفات بشكل خاص في طرق الفروق المحدودة ، وطرق العناصر المحدودة ، ونمذجة المعادلات التفاضلية . وبالنظر إلى التطبيقات الواسعة للجبر الخطي العددي، يرى لويد ن. تريفثين وديفيد باو الثالث أنه " أساسي للعلوم الرياضية مثل حساب التفاضل والتكامل والمعادلات التفاضلية"، [ 1 ] على الرغم من أنه مجال صغير نسبيًا . [ ٢ ] نظرًا لأن العديد من خصائص المصفوفات والمتجهات تنطبق أيضًا على الدوال والمؤثرات، يمكن اعتبار الجبر الخطي العددي نوعًا من التحليل الوظيفي الذي يركز بشكل خاص على الخوارزميات العملية. [ ١ ] : ٩

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

تاريخ

طُوِّر الجبر الخطي العددي على يد رواد الحوسبة مثل جون فون نيومان ، وآلان تورينج ، وجيمس هـ. ويلكنسون ، وألستون سكوت هاوسهولدر ، وجورج فورسايث ، وهاينز روتشاوزر ، وذلك لتطبيق الحواسيب الأولى على مسائل في الرياضيات المتصلة، مثل مسائل المقذوفات وحلول أنظمة المعادلات التفاضلية الجزئية . [ 2 ] وتُعد محاولة جون فون نيومان وهيرمان جولدستين عام 1947 أول محاولة جادة لتقليل خطأ الحاسوب في تطبيق الخوارزميات على البيانات الحقيقية. [ 3 ] وقد نما هذا المجال مع تطور التكنولوجيا التي مكّنت الباحثين من حل مسائل معقدة على مصفوفات ضخمة للغاية وعالية الدقة، وبرزت بعض الخوارزميات العددية مع تطور تقنيات مثل الحوسبة المتوازية التي جعلتها مناهج عملية لحل المشكلات العلمية. [ 2 ]

تحليل المصفوفات

المصفوفات المقسمة

في العديد من مسائل الجبر الخطي التطبيقي، من المفيد تبني منظور المصفوفة باعتبارها سلسلة من متجهات الأعمدة. على سبيل المثال، عند حل النظام الخطيx=أ-1ب{\displaystyle x=A^{-1}b}بدلاً من فهم x على أنه ناتج عنأ-1{\displaystyle A^{-1}}مع b ، من المفيد اعتبار x متجه المعاملات في التوسع الخطي لـ b في الأساس المُشكَّل من أعمدة A. [ 1 ] : 8 يُعدّ اعتبار المصفوفات سلسلة من الأعمدة نهجًا عمليًا لأغراض خوارزميات المصفوفات. وذلك لأن خوارزميات المصفوفات غالبًا ما تحتوي على حلقتين متداخلتين: إحداهما على أعمدة المصفوفة A ، والأخرى على صفوفها . على سبيل المثال، بالنسبة للمصفوفاتأم×ن{\displaystyle A^{m\times n}}والمتجهاتxن×1{\displaystyle x^{n\times 1}}وyم×1{\displaystyle y^{m\times 1}}يمكننا استخدام منظور تقسيم الأعمدة لحساب y  := Ax + y كما يلي

لـ q = 1 : n لـ p = 1 : m y ( p ) = A ( p , q ) * x ( q ) + y ( p ) نهاية نهاية

تحليل القيم المفردة

تحليل القيم المفردة للمصفوفةأم×ن{\displaystyle A^{m\times n}}يكونأ=يوΣV*{\displaystyle A=U\Sigma V^{\ast }}حيث U و V وحدات ، وΣ{\displaystyle \Sigma }هي قطرية . المدخلات القطرية لـΣ{\displaystyle \Sigma }تُسمى هذه القيم بالقيم المفردة للمصفوفة A. لأن القيم المفردة هي الجذور التربيعية للقيم الذاتية للمصفوفة A.أأ*{\displaystyle AA^{\ast }}توجد علاقة وثيقة بين تحليل القيم المفردة وتحليل القيم الذاتية. وهذا يعني أن معظم طرق حساب تحليل القيم المفردة تشبه طرق حساب القيم الذاتية؛ [ 1 ] : 36 ولعل أكثر الطرق شيوعًا هي تلك التي تتضمن إجراءات هاوسهولدر . [ 1 ] : 253

تحليل QR

تحليل المصفوفة باستخدام طريقة QRأم×ن{\displaystyle A^{m\times n}}هي مصفوفةسؤالم×م{\displaystyle Q^{m\times m}}ومصفوفةRم×ن{\displaystyle R^{m\times n}}بحيث يكون A = QR ، حيث Q مصفوفة متعامدة و R مصفوفة مثلثية علوية . [ 1 ] : 50 [ 4 ] : ​​223. الخوارزميتان الرئيسيتان لحساب تحليلات QR هما عملية غرام-شميدت وتحويل هاوسهولدر . يُستخدم تحليل QR غالبًا لحل مسائل المربعات الصغرى الخطية ، ومسائل القيم الذاتية (عن طريق خوارزمية QR التكرارية ).

تحليل LU

يتكون تحليل LU للمصفوفة A من مصفوفة مثلثية سفلية L ومصفوفة مثلثية علوية U بحيث يكون A = LU . يتم إيجاد المصفوفة U من خلال عملية تحويل المصفوفة A إلى مصفوفة مثلثية علوية، والتي تتضمن ضرب A من اليسار بسلسلة من المصفوفات.م1،...،من-1{\displaystyle M_{1},\ldots ,M_{n-1}}لتشكيل المنتجمن-1⋯م1أ=يو{\displaystyle M_{n-1}\cdots M_{1}A=U}وبالتالي، فإن ذلك يعادلل=م1-1⋯من-1-1{\displaystyle L=M_{1}^{-1}\cdots M_{n-1}^{-1}}[ 1 ] : 147 [ 4 ] : ​​96​

تحليل القيم الذاتية

تحليل القيم الذاتية للمصفوفةأم×م{\displaystyle A^{m\times m}}يكونأ=XΛX-1{\displaystyle A=X\Lambda X^{-1}}حيث تمثل أعمدة X المتجهات الذاتية للمصفوفة A ، وΛ{\displaystyle \Lambda }هي مصفوفة قطرية عناصرها القطرية هي القيم الذاتية المناظرة للمصفوفة A. [ 1 ] : 33 لا توجد طريقة مباشرة لإيجاد تحليل القيم الذاتية لمصفوفة عشوائية. ولأنه من غير الممكن كتابة برنامج يجد الجذور الدقيقة لكثير حدود عشوائي في وقت محدود، فإن أي خوارزمية عامة لحل القيم الذاتية يجب أن تكون تكرارية بالضرورة. [ 1 ] : 192

الخوارزميات

حذف غاوسي

من منظور الجبر الخطي العددي، تُعدّ عملية الحذف الغاوسي إجراءً لتحليل المصفوفة A إلى تحليلها LU ، وهو ما تُنجزه عملية الحذف الغاوسي عن طريق ضرب A من اليسار بسلسلة من المصفوفات.لم-1⋯ل2ل1أ=يو{\displaystyle L_{m-1}\cdots L_{2}L_{1}A=U}حتى تصبح U مثلثًا علويًا و L مثلثًا سفليًا، حيثل≡ل1-1ل2-1⋯لم-1-1{\displaystyle L\equiv L_{1}^{-1}L_{2}^{-1}\cdots L_{m-1}^{-1}}[ 1 ] : 148 تُعرف البرامج البسيطة لحذف غاوس بعدم استقرارها الشديد، وتُنتج أخطاءً جسيمة عند تطبيقها على المصفوفات ذات الأرقام المعنوية الكثيرة. [ 2 ] الحل الأبسط هو إدخال التمحور ، الذي يُنتج خوارزمية حذف غاوس مُعدلة ومستقرة. [ 1 ] : 151

حلول الأنظمة الخطية

عادةً ما تتعامل الجبر الخطي العددي مع المصفوفات على أنها سلسلة من متجهات الأعمدة. لحل النظام الخطيx=أ-1ب{\displaystyle x=A^{-1}b}النهج الجبري التقليدي هو فهم x على أنه ناتج ضربأ-1{\displaystyle A^{-1}}مع b . أما الجبر الخطي العددي فيفسر x على أنه متجه معاملات التوسع الخطي لـ b في الأساس المشكل من أعمدة A. [ 1 ] : 8

يمكن استخدام العديد من طرق التحليل المختلفة لحل المسألة الخطية، وذلك اعتمادًا على خصائص المصفوفة A والمتجهين x و b ، مما قد يجعل الحصول على تحليل معين أسهل بكثير من غيره. إذا كان A = QR تحليل QR للمصفوفة A ، فإنّ:Rx=سؤال*ب{\displaystyle Rx=Q^{\ast }b}هذا سهل الحساب مثل تحليل المصفوفة. [ 1 ] : 54 إذاأ=XΛX-1{\displaystyle A=X\Lambda X^{-1}}هي تحليل القيم الذاتية A ، ونسعى لإيجاد b بحيث يكون b = Ax ، معب′=X-1ب{\displaystyle b'=X^{-1}b}وx′=X-1x{\displaystyle x'=X^{-1}x}ثم لديناب′=Λx′{\displaystyle b'=\Lambda x'}[ 1 ] : 33 يرتبط هذا ارتباطًا وثيقًا بحل النظام الخطي باستخدام تحليل القيم المفردة، لأن القيم المفردة للمصفوفة هي القيم المطلقة لقيمها الذاتية، والتي تُكافئ أيضًا الجذور التربيعية للقيم المطلقة للقيم الذاتية لمصفوفة غرام .X*X{\displaystyle X^{*}X}وإذا كان A = LU تحليلًا لـ A باستخدام طريقة LU ، فإنه يمكن حل المعادلة Ax = b باستخدام المصفوفات المثلثية Ly = b و Ux = y . [ 1 ] : 147 [ 4 ] : ​​99

تحسين المربعات الصغرى

تُشير تحليلات المصفوفات إلى عدد من الطرق لحل النظام الخطي r = b − Ax حيث نسعى إلى تقليل قيمة r ، كما هو الحال في مسألة الانحدار . تحل خوارزمية QR هذه المسألة عن طريق حساب تحليل QR المُختزل للمصفوفة A وإعادة ترتيبها للحصول علىR^x=سؤال^*ب{\displaystyle {\widehat {R}}x={\widehat {Q}}^{\ast }b}يمكن بعد ذلك حل هذا النظام المثلثي العلوي لإيجاد قيمة x . كما يقترح تحليل القيم المفردة (SVD) خوارزمية للحصول على المربعات الصغرى الخطية. وذلك بحساب تحليل القيم المفردة المختزل.أ=يو^Σ^V*{\displaystyle A={\widehat {U}}{\widehat {\Sigma }}V^{\ast }}ثم حساب المتجهيو^*ب{\displaystyle {\widehat {U}}^{\ast }b}، نُختزل مسألة المربعات الصغرى إلى نظام قطري بسيط. [ 1 ] : 84 إن حقيقة إمكانية إنتاج حلول المربعات الصغرى بواسطة تحليل QR وتحليل القيم المفردة تعني أنه بالإضافة إلى طريقة المعادلات العادية الكلاسيكية لحل مسائل المربعات الصغرى، يمكن أيضًا حل هذه المسائل بطرق تشمل خوارزمية غرام-شميدت وطرق هاوسهولدر.

التكييف والاستقرار

لنفترض أن المشكلة عبارة عن دالةو:X→Y{\displaystyle f:X\to Y}حيث X هو فضاء متجهي معياري للبيانات و Y هو فضاء متجهي معياري للحلول. بالنسبة لبعض نقاط البياناتx∈X{\displaystyle x\in X}يُقال إن المسألة سيئة التكييف إذا أدى اضطراب صغير في x إلى تغيير كبير في قيمة f ( x ). يمكننا قياس ذلك من خلال تعريف رقم التكييف الذي يمثل مدى جودة تكييف المسألة، ويُعرَّف على النحو التالي: κ^=ليمدلتا→0رشفة‖دلتاx‖≤دلتا‖دلتاو‖‖دلتاx‖.{\displaystyle {\widehat {\kappa }}=\lim _{\delta \to 0}\sup _{\|\delta x\|\leq \delta }{\frac {\|\delta f\|}{\|\delta x\|}}.}

عدم الاستقرار هو ميل خوارزميات الحاسوب، التي تعتمد على حسابات الفاصلة العائمة ، إلى إنتاج نتائج تختلف اختلافًا كبيرًا عن الحل الرياضي الدقيق للمسألة. عندما تحتوي المصفوفة على بيانات حقيقية ذات أرقام معنوية كثيرة ، قد تُنتج العديد من خوارزميات حل مسائل مثل أنظمة المعادلات الخطية أو تحسين المربعات الصغرى نتائج غير دقيقة للغاية. يُعدّ ابتكار خوارزميات مستقرة للمسائل سيئة التكييف شاغلًا رئيسيًا في الجبر الخطي العددي. على سبيل المثال، يجعل استقرار طريقة التثليث هاوسهولدر منها طريقة حل قوية بشكل خاص للأنظمة الخطية، بينما يُعدّ عدم استقرار طريقة المعادلات العادية لحل مسائل المربعات الصغرى سببًا لتفضيل طرق تحليل المصفوفات مثل استخدام تحليل القيم المفردة. قد تكون بعض طرق تحليل المصفوفات غير مستقرة، ولكن يمكن تعديلها بسهولة لتصبح مستقرة؛ ومن الأمثلة على ذلك طريقة غرام-شميدت غير المستقرة، والتي يمكن تغييرها بسهولة لإنتاج طريقة غرام-شميدت المعدلة المستقرة . [ 1 ] : 140 مشكلة كلاسيكية أخرى في الجبر الخطي العددي هي اكتشاف أن حذف جاوس غير مستقر، ولكنه يصبح مستقرًا مع إدخال التمحور.

الأساليب التكرارية

هناك سببان يجعلان الخوارزميات التكرارية جزءًا مهمًا من الجبر الخطي العددي. أولًا، لا يوجد حل مباشر للعديد من المسائل العددية المهمة؛ ولإيجاد القيم الذاتية والمتجهات الذاتية لمصفوفة عشوائية، لا يمكننا إلا اتباع نهج تكراري. ثانيًا، لا توجد خوارزميات غير تكرارية لمصفوفة عشوائيةم×م{\displaystyle m\times m}المصفوفة تتطلبيا(م3){\displaystyle O(m^{3})}الوقت، وهو حد أدنى مرتفع بشكل مدهش بالنظر إلى أن المصفوفات لا تحتوي إلا علىم2{\displaystyle m^{2}}يمكن للأساليب التكرارية الاستفادة من عدة خصائص لبعض المصفوفات لتقليل هذا الوقت. على سبيل المثال، عندما تكون المصفوفة متفرقة ، يمكن للخوارزمية التكرارية تخطي العديد من الخطوات التي يتبعها الأسلوب المباشر بالضرورة، حتى لو كانت خطوات زائدة في حالة المصفوفة ذات البنية المعقدة.

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

برمجة

تستخدم العديد من لغات البرمجة تقنيات التحسين في الجبر الخطي العددي، وهي مصممة لتنفيذ خوارزميات الجبر الخطي العددي. تشمل هذه اللغات MATLAB و Analytica و Maple و Mathematica . أما لغات البرمجة الأخرى، التي لم تُصمم خصيصًا للجبر الخطي العددي، فلديها مكتبات توفر إجراءات الجبر الخطي العددي والتحسين؛ فلكل من C و Fortran حزم مثل Basic Linear Algebra Subprograms و LAPACK ، ولـ Python مكتبة NumPy ، ولـ Perl مكتبة Perl Data Language . تعتمد العديد من أوامر الجبر الخطي العددي في R على هذه المكتبات الأساسية مثل LAPACK . [ 5 ] يمكن العثور على المزيد من المكتبات في قائمة المكتبات العددية .

مراجع

  1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 تريفثين، لويد؛ باو الثالث، ديفيد (1997). الجبر الخطي العددي (  الطبعة الأولى). فيلادلفيا: SIAM. ISBN 978-0-89871-361-9.
  2. 1 2 3 4 غولوب، جين هـ. "تاريخ الجبر الخطي العددي الحديث" (ملف PDF) . قسم الإحصاء بجامعة شيكاغو . تم الاطلاع عليه بتاريخ 17 فبراير 2019 .
  3. ↑ فون نيومان، جون؛ غولدستاين، هيرمان هـ. (1947). "العكس العددي للمصفوفات ذات الرتبة العالية" . نشرة الجمعية الرياضية الأمريكية . 53 (11): 1021-1099 . doi : 10.1090/s0002-9904-1947-08909-6 . S2CID 16174165 . 
  4. 1 2 3 غولوب، جين هـ.؛ فان لون، تشارلز ف. (1996). حسابات المصفوفات ( الطبعة الثالثة). بالتيمور: مطبعة جامعة جونز هوبكنز. ISBN  0-8018-5413-X.
  5. ↑ ريكرت، جوزيف (29 أغسطس 2013). "لغة البرمجة R والجبر الخطي" . مدونة R. تم الاطلاع عليه في 17 فبراير 2019 .

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

  • دونغارا، جاك ؛ هامرلينغ، سفين (1990). "تطور البرمجيات العددية للجبر الخطي الكثيف". في: كوكس، إم جي؛ هامرلينغ، إس. (محرران). الحساب العددي الموثوق . أكسفورد: مطبعة كلارندون. ص 297-327 . ISBN  0-19-853564-3.
  • كلود بريزينسكي وجيرارد ميورانت وميشيلا ريديفو-زاجليا (2022): رحلة عبر تاريخ الجبر الخطي العددي ، SIAM، ISBN 978-1-61197-722-6.
  • ديميل، جيه دبليو (1997): الجبر الخطي العددي التطبيقي ، سيام.
  • Ciarlet, PG , Miara, B., & Thomas, JM (1989): مقدمة في الجبر الخطي العددي والتحسين ، مطبعة جامعة كامبريدج.
  • تريفثين، لويد؛ باو الثالث، ديفيد (1997): الجبر الخطي العددي (الطبعة الأولى)، SIAM، ISBN 978-0-89871-361-9
  • جولوب، جين هـ.؛ فان لون، تشارلز ف. (1996): حسابات المصفوفات (الطبعة الثالثة)، مطبعة جامعة جونز هوبكنز. ISBN 978-0-8018-5413-2
  • جي دبليو ستيوارت (1998): خوارزميات المصفوفات، المجلد الأول: التحليلات الأساسية ، سيام، رقم ISBN 978-0-89871-414-2
  • غيغاواط ستيوارت (2001): خوارزميات المصفوفة المجلد الثاني: الأنظمة الذاتية ، SIAM، ISBN 978-0-89871-503-3
  • فارغا، ريتشارد س. (2000): تحليل المصفوفات التكراري ، سبرينغر.
  • يوسف سعد (2003)  : الطرق التكرارية للأنظمة الخطية المتفرقة ، الطبعة الثانية، SIAM، ISBN 978-0-89871534-7
  • راف فاندبريل، مارك فان باريل، ونيكولا ماستروناردي (2008): حسابات المصفوفات والمصفوفات شبه المنفصلة، ​​المجلد 1: الأنظمة الخطية ، مطبعة جامعة جونز هوبكنز، ISBN 978-0-8018-8714-7
  • راف فاندبريل، مارك فان باريل، ونيكولا ماستروناردي (2008): حسابات المصفوفات والمصفوفات شبه المنفصلة، ​​المجلد 2: طرق القيم الذاتية والقيم المفردة ، مطبعة جامعة جونز هوبكنز، ISBN 978-0-8018-9052-9
  • Higham, NJ (2002): دقة واستقرار الخوارزميات العددية ، SIAM.
  • Higham, NJ (2008): Functions of Matrics: Theory and Computation , SIAM.
  • ديفيد س. واتكينز (2008): مشكلة القيم الذاتية للمصفوفة: طرق الفضاء الجزئي GR و Krylov ، SIAM.
  • Liesen, J., and Strakos, Z. (2012): Krylov Subspace Methods: Principles and Analysis , Oxford Univ. Press.