متعددة حدود ويلكنسون

رسم بياني لكثير الحدود ويلكنسون

رسم بياني لـ${\displaystyle \operatorname {sgn}(w(x))\ln(1+|w(x)|)}$

في التحليل العددي ، تعد متعددة حدود ويلكنسون متعددة حدود محددة استخدمها جيمس إتش. ويلكنسون في عام 1963 لتوضيح صعوبة عند إيجاد جذور متعددة الحدود: يمكن أن يكون موقع الجذور حساسًا للغاية للاضطرابات في معاملات متعددة الحدود.

متعددة الحدود هي $${\displaystyle w(x)=\prod _{i=1}^{20}(xi)=(x-1)(x-2)\cdots (x-20).}$$في بعض الأحيان، يُستخدم مصطلح كثير الحدود لـ Wilkinson أيضًا للإشارة إلى بعض كثيرات الحدود الأخرى التي تظهر في مناقشة Wilkinson.

ظهرت متعددة حدود ويلكنسون في دراسة الخوارزميات لإيجاد جذور متعددة الحدود. $${\displaystyle p(x)=\sum _{i=0}^{n}c_{i}x^{i}.}$$ من الطبيعي في التحليل العددي التساؤل عما إذا كانت مسألة إيجاد جذور المعادلة p من المعاملات cᵢ _مسألة جيدة التكييف . أي أننا نأمل أن يؤدي تغيير طفيف في المعاملات إلى تغيير طفيف في الجذور. ولكن للأسف، هذا ليس هو الحال هنا.

تُعتبر المسألة سيئة التكييف عندما يكون لكثير الحدود جذر متعدد . على سبيل المثال، لكثير الحدود x² جذر مزدوج عند x = 0. ومع ذلك، ^فإن لكثير الحدود x² ^- ε (اضطراب بحجم ε ) جذورًا عند ±√ε ، وهو أكبر بكثير من ε عندما تكون ε صغيرة.  

لذا، من الطبيعي توقع حدوث سوء التكييف أيضًا عندما تكون أصفار كثيرة الحدود متقاربة جدًا. مع ذلك، قد تكون المسألة سيئة التكييف للغاية أيضًا بالنسبة لكثيرات الحدود ذات الأصفار المتباعدة. استخدم ويلكنسون كثيرة الحدود w ( x ) لتوضيح هذه النقطة (ويلكنسون، 1963).

في عام 1984، وصف الأثر الشخصي لهذا الاكتشاف:

أما بالنسبة لي شخصياً، فأعتبرها التجربة الأكثر إيلاماً في مسيرتي المهنية كمحلل رقمي. ^{[ 1 ]}

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

متعددة حدود ويلكنسون $${\displaystyle w(x)=\prod _{i=1}^{20}(xi)=(x-1)(x-2)\cdots (x-20)}$$ من الواضح أن للمعادلة 20 جذراً، تقع عند x = 1، 2، ...، 20. هذه الجذور متباعدة. ومع ذلك، فإن المعادلة لا تزال سيئة التكييف.

بتوسيع متعددة الحدود، نجد $$\displaystyle \begin{aligned}w(x)={}&x^{20}-210x^{19}+20615x^{18}-1256850x^{17}+53327946x^{16}\\&{}-1672280820x^{15}+40171771630x^{14}-756111184500x^{13}\\&{}+11310276995381x^{12}-135585182899530x^{11}\\&{}+1307535010540395x^{10}-10142299865511450x^{9}\\&{}+63 030812099294896x^{8}-311333643161390640x^{7}\\&{}+1206647803780373360x^{6}-3599979517947607200x^{5}\\&{}+8037811822645051776x^{4}-12870931245150988800x^{3}\\&{}+13803759753640704000x^{2}-8752948036761600000x\\&{}+2432902008176640000.\end{aligned}}}$$

إذا انخفض معامل x19 من ^{-210 بمقدار 2 -} 23 إلى -210.0000001192، فإن قيمة كثيرة الحدود w (20) تنخفض من 0 إلى -2 - ²³ 20 ¹⁹  = -6.25 × 10 ¹⁷ ، وينمو الجذر عند x = 20 إلى x ≈ 20.8 . يتداخل الجذران عند x = 18 و x = 19 ليشكلا جذرًا مزدوجًا عند x ≈ 18.62 ، والذي يتحول إلى زوج من الجذور المركبة المترافقة عند x ≈ 19.5 ± 1.9 i مع ازدياد الاضطراب. تصبح الجذور العشرين (لخمسة أرقام عشرية) $${\displaystyle {\begin{array}{rrrrr}1.00000&2.00000&3.00000&4.00000&5.00000\\[8pt]6.00001&6.99970&8.00727&8.91725&20.84691\\[8pt]10.09527\pm {}&11.79363\pm {}&13.99236\pm {}&16.73074\pm {}&19.50244\pm {}\\[-3pt]0.64350i&1.65233i&2.51883i&2.81262i&1.94033i\end{array}}}$$

بعض الجذور مُزاحة بشكل كبير، على الرغم من أن التغيير في المعامل ضئيل، وأن الجذور الأصلية تبدو متباعدة على نطاق واسع. وقد بيّن ويلكنسون، من خلال تحليل الاستقرار الذي نناقشه في القسم التالي، أن هذا السلوك مرتبط بحقيقة أن بعض الجذور α (مثل α  = 15) لها العديد من الجذور β "المتقاربة" بمعنى أن | α  − β | أصغر من | α |.  

اختار ويلكنسون التشويه 2 - ²³ لأن حاسوبه Pilot ACE كان يحتوي على معاملات فاصلة عائمة بدقة 30 بت ، لذا بالنسبة للأعداد القريبة من 210، كان 2 ^{- 23} خطأً في موضع البت الأول غير المُمثَّل في الحاسوب. يُمثَّل العددان الحقيقيان -210 و-210 - 2 - ²³ بنفس العدد ذي الفاصلة العائمة، مما يعني أن 2 - ²³ هو الخطأ الحتمي في تمثيل معامل حقيقي قريب من -210 بعدد ذي فاصلة عائمة على ذلك الحاسوب. يُظهر تحليل التشويه أن دقة المعامل 30 بت غير كافية لفصل جذور متعددة حدود ويلكنسون.

لنفترض أننا نُجري اضطرابًا على متعددة الحدود p ( x ₎ = Π( x - αj ₎ ذات الجذور αj ، وذلك بإضافة مضاعف صغير t · c ( x ) لمتعددة الحدود c ( x ) ، ونتساءل كيف يؤثر ذلك على الجذور αj _. في التقريب الأول، سيكون التغير في الجذور محكومًا بالمشتقة .$${\displaystyle {d\alpha _{j} \over dt}=-{c(\alpha _{j}) \over p^{\prime }(\alpha _{j})}.}$$ عندما تكون المشتقة صغيرة، تكون الجذور أكثر استقرارًا عند تغيرات الزمن t ، وعلى العكس ، إذا كانت هذه المشتقة كبيرة _، تكون الجذور غير مستقرة. وبالتحديد، إذا كان αj جذرًا مضاعفًا، فإن المقام يساوي صفرًا. في هذه الحالة، عادةً ما يكون αj _غير قابل للتفاضل بالنسبة إلى t (إلا إذا صادف أن c يساوي صفرًا عند هذه النقطة)، وتكون الجذور غير مستقرة للغاية.

بالنسبة للقيم الصغيرة لـ t، يُعطى الجذر المضطرب بواسطة متسلسلة القوى في t$${\displaystyle \alpha _{j}+{d\alpha _{j} \over dt}t+{d^{2}\alpha _{j} \over dt^{2}}{t^{2} \over 2!}+\cdots }$$ ومن المتوقع حدوث مشاكل عندما تكون قيمة | _t | أكبر من نصف قطر تقارب متسلسلة القوى هذه، والذي يُعطى بأصغر قيمة لـ | t | بحيث يصبح الجذر αj مضاعفًا. ويُمكن تقدير هذا النصف قطر تقريبًا بأخذ نصف المسافة من αj إلى أقرب جذر _، ثم قسمة الناتج على المشتقة المذكورة أعلاه.

في مثال متعددة حدود ويلكنسون من الدرجة 20، تُعطى الجذور بالعلاقة αj = j حيث j = 1، ...، 20 ، و c ( x ) تساوي x ^{19. لذا} _، تُعطى المشتقة بالعلاقة التالية: $${\displaystyle {d\alpha _{j} \over dt}=-{\alpha _{j}^{19} \over \prod _{k\neq j}(\alpha _{j}-\alpha _{k})}=-\prod _{k\neq j}{\alpha _{j} \over \alpha _{j}-\alpha _{k}}.\,\!}$$ وهذا يدل على أن الجذر α _j سيكون أقل استقرارًا إذا كان هناك العديد من الجذور α _k القريبة من α _j ، بمعنى أن المسافة |α _j  −  α _k | بينهما أصغر من |α _j |.

مثال : بالنسبة للجذر α₁ ₌  1، فإن مشتقته تساوي 1/19!، وهي قيمة صغيرة جدًا؛ لذا يظل هذا الجذر ثابتًا حتى مع التغيرات الكبيرة في t . ويعود ذلك إلى أن جميع الجذور الأخرى β بعيدة عنه، بمعنى أن | α₁ − β | = 1, 2, 3, ..., 19 أكبر من | α₁ | = _1. على سبيل المثال، حتى لو كانت قيمة t كبيرة جدًا مثل -10000000000، _فإن الجذر α₁ يتغير فقط من 1 إلى حوالي 0.99999991779380 (وهي قيمة قريبة جدًا من التقريب من الدرجة الأولى 1 + t /19! ≈ 0.99999991779365). وبالمثل، _فإن الجذور الصغيرة الأخرى لكثيرة حدود ويلكنسون لا تتأثر بتغيرات t .      

مثال . من ناحية أخرى، بالنسبة للجذر α ₂₀  = 20، فإن المشتقة تساوي −20 ¹⁹ /19! وهي قيمة ضخمة (حوالي 43000000)، لذا فإن هذا الجذر حساس للغاية للتغيرات الطفيفة في t . أما الجذور الأخرى β فهي قريبة من α ₂₀ ، بمعنى أن | β  − α ₂₀ | = 1, 2, 3, ..., 19 أقل من | α ₂₀ | = 20. بالنسبة لـ t = −2 ⁻²³ ، فإن التقريب من الدرجة الأولى 20 − t ·20 ¹⁹ /19! = 25.137... للجذر المضطرب 20.84... سيء للغاية؛ يتضح هذا الأمر بشكل أكبر بالنسبة للجذر α _19، حيث يحتوي الجذر المضطرب على جزء تخيلي كبير ، بينما يكون التقريب من الدرجة الأولى (وكذلك جميع التقريبات من الرتب الأعلى) حقيقيًا. ويعود سبب هذا التباين إلى أن | t | ≈ 0.000000119 أكبر من نصف قطر تقارب متسلسلة القوى المذكورة أعلاه (والذي يبلغ حوالي 0.0000000029، وهو أصغر قليلًا من القيمة 0.00000001 المُعطاة بالتقدير الأولي)، لذا لا تنطبق النظرية الخطية. أما بالنسبة لقيمة مثل t = 0.000000001، وهي أصغر بكثير من نصف قطر التقارب هذا، فإن التقريب من الدرجة الأولى 19.9569... يكون قريبًا بشكل معقول من الجذر 19.9509...   

للوهلة الأولى ، تبدو جذور كثيرة حدود ويلكنسون α₁ = ₁ و α₂₀ = _{20 متشابهة، إذ تقع على طرفي خط متناظر من الجذور، ولها نفس مجموعة المسافات 1، 2، 3، ...، 19 من الجذور الأخرى. مع ذلك} ، يُظهر التحليل السابق أن هذا مضلل للغاية: فالجذر α₂₀ = 20 أقل استقرارًا من α₁ ⁼ 1 ( _{للتغيرات الطفيفة} في معامل x ) بمعامل ²⁰ .

المثال الثاني الذي تناوله ويلكنسون هو $${\displaystyle w_{2}(x)=\prod _{i=1}^{20}(x-2^{-i})=(x-2^{-1})(x-2^{-2})\cdots (x-2^{-20}).}$$ الجذور العشرون لهذه المعادلة متعددة الحدود تشكل متتالية هندسية بنسبة مشتركة تساوي 2، ومن ثم فإن ناتج القسمة $${\displaystyle \alpha _{j} \over \alpha _{j}-\alpha _{k}}$$ لا يمكن أن تكون كبيرة. في الواقع، جذور w ₂ مستقرة تمامًا تجاه التغيرات النسبية الكبيرة في المعاملات.

التوسع $${\displaystyle p(x)=\sum _{i=0}^{n}c_{i}x^{i}}$$ يُعبّر عن متعددة الحدود في أساس معين ، وهو أساس أحاديات الحدود . إذا عُبّر عن متعددة الحدود في أساس آخر، فقد لا تكون مسألة إيجاد جذورها سيئة التكييف. على سبيل المثال، في صيغة لاغرانج ، لا يُؤدي تغيير طفيف في معامل واحد (أو عدة معاملات) إلى تغيير كبير في الجذور. في الواقع، فإن كثيرات الحدود الأساسية للاستيفاء عند النقاط 0، 1، 2، ...، 20 هي $${\displaystyle \ell _{k}(x)=\prod _{i=0,\ldots ,20 \atop i\neq k}{\frac {x-i}{k-i}},\qquad {\text{for}}\quad k=0,\ldots ,20.}$$

يمكن التعبير عن كل متعددة حدود (من الدرجة 20 أو أقل) في هذا الأساس: $${\displaystyle p(x)=\sum _{i=0}^{20}d_{i}\ell _{i}(x).}$$

بالنسبة لكثير الحدود ويلكنسون، نجد $${\displaystyle w(x)=(20!)\ell _{0}(x)=\sum _{i=0}^{20}d_{i}\ell _{i}(x)\quad {\text{with}}\quad d_{0}=(20!),\,d_{1}=d_{2}=\cdots =d_{20}=0.}$$

بالنظر إلى تعريف متعددة حدود أساس لاغرانج ℓ₀ ( x ) _{، فإن} تغيير المعامل d₀ لن يُحدث أي تغيير في جذور w . مع ذلك، فإن أي تغيير في المعاملات الأخرى (جميعها تساوي صفرًا) سيُحدث تغييرًا طفيفًا في الجذور. لذلك، فإن متعددة حدود ويلكنسون مُهيأة جيدًا في هذا الأساس.

ناقش ويلكنسون متعدد الحدود "الخاص به" في

• جيه إتش ويلكنسون (1959). تقييم أصفار كثيرات الحدود سيئة التكييف. الجزء الأول. الرياضيات العددية 1 : 150-166.
• جيه إتش ويلكنسون (1963). أخطاء التقريب في العمليات الجبرية . إنجلوود كليفس، نيو جيرسي: برنتيس هول.

وقد ورد ذكره في الكتب الدراسية القياسية في التحليل العددي، مثل

• إف إس أكتون، الطرق العددية الناجحة ، رقم ISBN 978-0-88385-450-1، ص  201.

مراجع أخرى:

• رونالد ج. موسير (يوليو 1986). جوارات جذور متعددة الحدود. رياضيات الحساب 47 (175): 265-273.
• جيه إتش ويلكنسون (1984). متعددة الحدود الخائنة في دراسات في التحليل العددي ، تحرير جي إتش غولوب، ص  1-28. (دراسات في الرياضيات، المجلد 24). واشنطن العاصمة: الجمعية الرياضية الأمريكية.

تم تقديم حساب عددي عالي الدقة في:

• Ray Buvel, كثيرات الحدود والدوال الكسرية ، جزء من دليل مستخدم حاسبة RPN (لغة بايثون)، تم استرجاعه في 29 يوليو 2006.