عدد الشرط للمصفوفة: باقي صغير وخطأ كبير

ثبت المعيار قبل الحساب

للمصفوفة الحقيقية المربعة القابلة للعكس نستخدم ‖z‖∞=maxᵢ|zᵢ| و‖A‖∞=maxᵢΣⱼ|aᵢⱼ|: أكبر مجموع مطلق لصف، لا أكبر خانة. [2]

نستخدم κ∞(A)=‖A‖∞‖A⁻¹‖∞؛ والحساسية تتوقف على المعيار ونوع المسألة. [1]

خذ A=[[1,1],[1,1.01]]. محددها0.01، ومعكوسها [[101,−100],[−100,100]]. مجموعا صفوف A هما2 و2.01؛ ومجموعا الصفوف المطلقة في المعكوس201 و200. لذلك κ∞=2.01×201=404.01.

اختر x=(1,1) متجهًا عموديًا، فيكون b=Ax=(2,2.01). لدينا ‖x‖∞=1 و‖b‖∞=2.01. هذه أعداد مفترضة محسوبة، وليست قياسات أو نتيجة تشغيل خوارزمية تقريبية.

المقدار نفسه والاتجاه مختلف

نثبت A ونغير b فقط. الحل الجديد x+Δx يحقق A(x+Δx)=b+Δb، وبالتالي Δx=A⁻¹Δb. نختار Δb=(0,0.001)، فنحصل على Δx=(−0.1,0.1)، والحل الجديد(0.9,1.1).

تغير البيانات النسبي هو ‖Δb‖∞/‖b‖∞=0.001/2.01=1/2010، أي نحو0.04975%. وتغير الحل النسبي0.1/1=10%. عامل التضخيم الفعلي هو201.

لو اخترنا Δb=(0.001,0.001)، لأعطى المعكوس Δx=(0.001,0). مقدار تغير البيانات لم يتبدل، لكن تغير الحل صار0.1%، وعامل التضخيم2.01.

واختر Δb=(0.001,−0.001): عندئذ Δx=(0.201,−0.2)، والحل(1.201,0.8). تغير الحل20.1%، وعامل التضخيم404.01، مساوٍ لعدد الشرط في هذا المثال.

العدد الكبير يصف أسوأ حساسية، ولا يفرضها على كل اتجاه. [1]

لماذا قد يخدعنا الباقي الصغير؟

لننظر إلى x̂=(0.9,1.1) كمرشح لحل النظام الأصلي. نحصل على A x̂=(2,2.011)، وبالتالي r=b−A x̂=(0,−0.001). الباقي النسبي1/2010 صغير، لكن الخطأ x̂−x=(−0.1,0.1) نسبته10%.

نشتق الحد من تعريف الباقي: A(x−x̂)=r، فيكون x−x̂=A⁻¹r. ومن تعريف المعيار المستحث ‖x−x̂‖∞≤‖A⁻¹‖∞‖r‖∞. كذلك ‖b‖∞=‖Ax‖∞≤‖A‖∞‖x‖∞. بجمع العلاقتين، للبيانات غير الصفرية، نحصل على ‖x−x̂‖∞/‖x‖∞≤κ∞(A)‖r‖∞/‖b‖∞. [1][2]

في الأعداد المختارة، الحد404.01/2010=0.201، أي20.1%. الخطأ الفعلي10% أقل منه؛ الحد لا يدعي المساواة في كل مرة. الاضطراب ذو الإشارتين المتعاكستين في القسم السابق يبلغ هذا الحد.

في تفسير يثبت A، يكون المرشح حلًا دقيقًا للثوابت b−r؛ أي إن الباقي يقيس تغييرًا في البيانات، بينما الخطأ الأمامي يقارن الحلين. هذا التفريق لا يثبت استقرار خوارزمية كاملة بمجرد مثال واحد. [3]

المحدد والاستقرار سؤالان مختلفان

اضرب جميع عناصر A في1000. يصبح المحدد det(1000A)=1000²×0.01=10000. المعكوس الجديد A⁻¹/1000، والمعياران2010 و0.201، وحاصل ضربهما404.01 كما كان. كبر المحدد لم يزل الحساسية.

ولكل عدد c≠0، لدينا (cA)⁻¹=A⁻¹/c؛ معيار الأول |c|‖A‖∞، والثاني ‖A⁻¹‖∞/|c|. يلغي العاملان بعضهما، فيبقى عدد الشرط ثابتًا تحت هذا الضرب الكلي. هذا لا يقول إن تغيير صف أو عمود وحده يبقيه ثابتًا.

بالعكس، B=10⁻⁸I₂ محددها10⁻¹⁶، لكن معياريها10⁻⁸ و10⁸، فعدد شرطها1. المحدد الصغير هنا لا يعني حساسية نسبية كبيرة؛ إنه يعكس مقياس العناصر.

الاستقرار الخلفي وصف للخوارزمية: تعطي جوابًا لمسألة قريبة. ومع مسألة حساسة قد يبقى الفرق عن الحل الأصلي كبيرًا. [3] في مثالنا حسبنا حلول اضطرابات محددة بالضبط؛ لم نقارن برامج أو دقة أعداد عائمة.

اربط الباقي النسبي بعدد الشرط؛ وجود المعكوس أو كبر المحدد لا يضمن الدقة.