مقالات

4.9: طريقة نيوتن - الرياضيات


أهداف التعلم

  • صف خطوات طريقة نيوتن.
  • اشرح ما تعنيه العملية التكرارية.
  • اعرف متى لا تعمل طريقة نيوتن.
  • تطبيق عمليات تكرارية على مواقف مختلفة.

في العديد من مجالات الرياضيات البحتة والتطبيقية ، نحن مهتمون بإيجاد حلول لمعادلة بالصيغة (f (x) = 0. ) ومع ذلك ، بالنسبة لمعظم الدوال ، من الصعب - إن لم يكن من المستحيل - حساب أصفارها صراحة. في هذا القسم ، نلقي نظرة على تقنية توفر طريقة فعالة للغاية لتقريب أصفار الوظائف. تستفيد هذه التقنية من تقريب الخط المماس وهي وراء الطريقة المستخدمة غالبًا بواسطة الآلات الحاسبة وأجهزة الكمبيوتر للعثور على الأصفار.

وصف طريقة نيوتن

ضع في اعتبارك مهمة إيجاد حلول ​​(f (x) = 0. ) إذا كان (f ) هو متعدد الحدود من الدرجة الأولى (f (x) = ax + b ) ، ثم حل ( f (x) = 0 ) معطاة بالصيغة (x = - frac {b} {a} ). إذا كان (f ) هو متعدد الحدود من الدرجة الثانية (f (x) = ax ^ 2 + bx + c ) ، يمكن إيجاد حلول ​​(f (x) = 0 ) باستخدام الصيغة التربيعية . ومع ذلك ، بالنسبة لكثيرات الحدود من الدرجة 3 أو أكثر ، يصبح العثور على جذور (f ) أكثر تعقيدًا. على الرغم من وجود الصيغ لكثيرات الحدود من الدرجة الثالثة والرابعة ، إلا أنها معقدة للغاية. أيضًا ، إذا كانت f هي كثير حدود من الدرجة 5 أو أكبر ، من المعروف أنه لا توجد مثل هذه الصيغ. على سبيل المثال ، ضع في اعتبارك الوظيفة

[f (x) = x ^ 5 + 8x ^ 4 + 4x ^ 3−2x − 7. nonumber ]

لا توجد صيغة تسمح لنا بإيجاد حلول ​​(f (x) = 0. ) توجد صعوبات مماثلة للدوال غير متعددة الحدود. على سبيل المثال ، ضع في اعتبارك مهمة إيجاد حلول لـ (tan (x) −x = 0. ) لا توجد صيغة بسيطة لحل هذه المعادلة. في مثل هذه الحالات ، يمكننا استخدام طريقة نيوتن لتقريب الجذور.

طريقة نيوتن يستخدم الفكرة التالية لتقريب حلول ​​(f (x) = 0. ) من خلال رسم رسم بياني لـ (f ) ، يمكننا تقدير جذر (f (x) = 0 ). دعونا نسمي هذا التقدير (x_0 ). ثم نرسم خط الظل إلى (f ) عند (x_0 ). إذا (f ′ (x_0) ≠ 0 ) ، فإن هذا الخط المماس يتقاطع مع (x ) - المحور عند نقطة ما ((x_1،0) ). لنكن الآن (x_1 ) هو التقريب التالي للجذر الفعلي. عادةً ، (x_1 ) أقرب من (x_0 ) إلى جذر حقيقي. بعد ذلك نرسم خط الظل إلى (f ) عند (x_1 ). إذا (f ′ (x_1) ≠ 0 ) ، فإن هذا الخط المماس يتقاطع أيضًا مع محور (x ) - ، مما ينتج عنه تقريب آخر ، (x_2 ). نواصل على هذا النحو ، واستنباط قائمة التقريبية: (x_0 ، ، x_1 ، ، x_2 ، ، ... ) عادةً ، الأرقام (x_0 ، ، x_1 ، ، x_2 ، ، ... ) بسرعة الاقتراب من الجذر الفعلي (x * ) ، كما هو موضح في الشكل التالي.

الآن دعونا نلقي نظرة على كيفية حساب التقديرات التقريبية (x_0، ، x_1، ، x_2، ، ... ((x_1،0) ) يكون (x ) - تقاطع خط الظل إلى (f ) عند (x_0 ). يتم الحصول على معادلة خط الظل هذا بواسطة

[y = f (x_0) + f ′ (x_0) (x − x_0). لا يوجد رقم]

لذلك ، يجب أن يفي (x_1 )

[f (x_0) + f ′ (x_0) (x_1 − x_0) = 0. nonumber ]

حل هذه المعادلة لـ (x_1 ) ، نستنتج ذلك

[x_1 = x_0− frac {f (x_0)} {f '(x_0)}. nonumber ]

وبالمثل ، فإن النقطة ((x_2،0) ) هي (x ) - تقاطع خط الظل إلى (f ) عند (x_1 ). لذلك ، يفي (x_2 ) بالمعادلة

[x_2 = x_1− frac {f (x_1)} {f '(x_1)}. nonumber ]

بشكل عام ، يرضي لـ (n> 0، x_n )

[x_n = x_ {n − 1} - frac {f (x_ {n − 1})} {f '(x_ {n − 1})}. التسمية {نيوتن} ]

بعد ذلك ، سنرى كيفية الاستفادة من هذه التقنية لتقريب جذر كثير الحدود (f (x) = x ^ 3−3x + 1. )

مثال ( PageIndex {1} ): إيجاد جذر لكثير الحدود

استخدم طريقة نيوتن لتقريب جذر (f (x) = x ^ 3−3x + 1 ) في الفاصل ([1،2] ). دع (x_0 = 2 ) وابحث عن (x_1، ، x_2، ، x_3، ، x_4، ) و (x_5 ).

المحلول

من الشكل ( PageIndex {2} ) ، نرى أن (f ) له جذر واحد على الفاصل ((1،2) ). لذلك يبدو (x_0 = 2 ) تقديرًا أوليًا معقولًا. لإيجاد التقريب التالي ، نستخدم المعادلة ref {نيوتن}. بما أن (f (x) = x ^ 3−3x + 1 ) ، فإن المشتق هو (f ′ (x) = 3x ^ 2−3 ). باستخدام المعادلة المرجع {نيوتن} مع (n = 1 ) (وآلة حاسبة تعرض (10 ​​) أرقامًا) ، نحصل على

[x_1 = x_0− frac {f (x_0)} {f '(x_0)} = 2− frac {f (2)} {f' (2)} = 2− frac {3} {9} ≈1.666666667. غير رقم ]

للعثور على التقريب التالي ، (x_2 ) ، نستخدم المعادلة مع (n = 2 ) وقيمة (x_1 ) المخزنة على الآلة الحاسبة. نجد ذلك

[x_2 = x_1- frac {f (x_1)} {f '(x_1)} ≈1.548611111. nonumber ]

واستمرارًا على هذا النحو نحصل على النتائج التالية:

  • (x_1≈1.666666667 )
  • (س_2≈1.548611111 )
  • (س_3≈1.532390162 )
  • (x_4≈1.532088989 )
  • (x_5≈1.532088886 )
  • (x_6≈1.532088886. )

نلاحظ أننا حصلنا على نفس القيمة لـ (x_5 ) و (x_6 ). لذلك ، فإن أي تطبيق لاحق لطريقة نيوتن سيعطي على الأرجح نفس القيمة لـ (x_n ).

تمرين ( PageIndex {1} )

مع ترك (x_0 = 0 ) ، لنستخدم طريقة نيوتن لتقريب جذر (f (x) = x ^ 3−3x + 1 ) عبر الفاصل ([0،1] ) عن طريق حساب ( x_1 ) و (x_2 ).

تلميح

استخدم المعادلة المرجع {نيوتن}.

إجابه

(س_1≈0.33333333 )
(س_2≈0.347222222 )

يمكن أيضًا استخدام طريقة نيوتن لتقريب الجذور التربيعية. نوضح هنا كيفية تقريب ( sqrt {2} ). يمكن تعديل هذه الطريقة لتقريب الجذر التربيعي لأي رقم موجب.

مثال ( PageIndex {2} ): البحث عن جذر مربع

استخدم طريقة نيوتن لتقريب ( sqrt {2} ) (الشكل ( PageIndex {3} )). دع (f (x) = x ^ 2−2 ) ، دع (x_0 = 2 ) ، واحسب (x_1 ، ، x_2 ، ، x_3 ، ، x_4 ، ، x_5 ). (نلاحظ أنه بما أن (f (x) = x ^ 2−2 ) لها صفر عند ( sqrt {2} ) ، فإن القيمة الأولية (x_0 = 2 ) هي خيار معقول لتقريب ( sqrt {2} )).

المحلول

بالنسبة إلى (f (x) = x ^ 2−2، ؛ f ′ (x) = 2x. ) من المرجع {نيوتن} ، نعلم ذلك

[ start {align *} x_n & = x_ {n − 1} - frac {f (x_ {n − 1})} {f '(x_ {n − 1})} [4pt]
& = x_ {n − 1} - frac {x ^ 2_ {n − 1} −2} {2x_ {n − 1}} [4pt]
& = frac {1} {2} x_ {n − 1} + frac {1} {x_ {n − 1}} [4pt]
& = frac {1} {2} left (x_ {n − 1} + frac {2} {x_ {n − 1}} right). end {align *} ]

وبالتالي،

(x_1 = frac {1} {2} left (x_0 + frac {2} {x_0} right) = frac {1} {2} left (2+ frac {2} {2} يمين) = 1.5 )

(x_2 = frac {1} {2} left (x_1 + frac {2} {x_1} right) = frac {1} {2} left (1.5+ frac {2} {1.5} يمين) ≈1.416666667. )

بالاستمرار على هذا النحو ، نجد ذلك

(س_1 = 1.5 )

(س_2≈1.416666667 )

(س_3≈1.414215686 )

(س_4≈1.414213562 )

(x_5≈1.414213562. )

نظرًا لأننا حصلنا على نفس القيمة لـ (x_4 ) و (x_5 ) ، فمن غير المرجح أن تتغير القيمة (x_n ) في أي تطبيق لاحق لطريقة نيوتن. نستنتج أن ( sqrt {2} ≈1.414213562. )

تمرين ( PageIndex {2} )

استخدم طريقة نيوتن لتقريب ( sqrt {3} ) عن طريق السماح (f (x) = x ^ 2−3 ) و (x_0 = 3 ). ابحث عن (x_1 ) و (x_2 ).

تلميح

بالنسبة إلى (f (x) = x ^ 2−3 ) ، يتم تقليل المعادلة ref {Newton} إلى (x_n = frac {x_ {n − 1}} {2} + frac {3} {2x_ { ن − 1}} ).

إجابه

(س_1 = 2 )
(س_2 = 1.75 )

عند استخدام طريقة نيوتن ، يتم تحديد كل تقدير تقريبي بعد التخمين الأولي من حيث التقريب السابق باستخدام نفس الصيغة. على وجه الخصوص ، من خلال تعريف الوظيفة (F (x) = x− left [ frac {f (x)} {f ′ (x)} right] ) ، يمكننا إعادة كتابة المعادلة المرجع {نيوتن} على النحو التالي (x_n = F (x_ {n − 1}) ). هذا النوع من العمليات ، حيث يتم تعريف كل (x_n ) من خلال (x_ {n − 1} ) بتكرار نفس الوظيفة ، هو مثال على عملية تكرارية. باختصار ، ندرس العمليات التكرارية الأخرى. أولاً ، دعونا نلقي نظرة على أسباب فشل طريقة نيوتن في العثور على جذر.

فشل طريقة نيوتن

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

  1. عند أحد التقريبات (x_n ) ، يكون المشتق (f ′ ) صفرًا عند (x_n ) ، ولكن (f (x_n) ≠ 0 ). نتيجة لذلك ، لا يتقاطع الخط المماس لـ (f ) عند (x_n ) مع (x ) - المحور. لذلك ، لا يمكننا مواصلة العملية التكرارية.
  2. التقريبات (x_0، ، x_1، ، x_2، ، ... ) قد تقترب من جذر مختلف. إذا كانت الوظيفة (f ) تحتوي على أكثر من جذر ، فمن الممكن ألا تقترب تقديراتنا من القيمة التي نبحث عنها ، ولكنها تقترب من جذر مختلف (انظر الشكل ( PageIndex {4} )). يحدث هذا الحدث غالبًا عندما لا نختار التقريب (x_0 ) قريبًا بدرجة كافية من الجذر المطلوب.
  3. قد تفشل التقديرات التقريبية في الاقتراب من الجذر بالكامل. في المثال ( PageIndex {3} ) ، نقدم مثالًا لوظيفة وتخمينًا أوليًا (x_0 ) بحيث لا تقترب التقديرات المتتالية أبدًا من الجذر لأن التقديرات المتتالية تستمر في التناوب ذهابًا وإيابًا بين قيمتين .

مثال ( PageIndex {3} ): عندما تفشل طريقة نيوتن

ضع في اعتبارك الوظيفة (f (x) = x ^ 3−2x + 2 ). دع (x_0 = 0 ). أظهر أن التسلسل (x_1 ، ، x_2 ، ، ... ) فشل في الاقتراب من جذر (f ).

المحلول

بالنسبة إلى (f (x) = x ^ 3−2x + 2، ) يكون المشتق (f ′ (x) = 3x ^ 2−2 ). لذلك ،

[x_1 = x_0− frac {f (x_0)} {f ′ (x_0)} = 0− frac {f (0)} {f ′ (0)} = - frac {2} {- 2} = 1. لا يوجد رقم]

في الخطوة التالية ،

[x_2 = x_1− frac {f (x_1)} {f '(x_1)} = 1− frac {f (1)} {f ′ (1)} = 1− frac {1} {1} = 0. لا يوجد رقم]

وبالتالي ، فإن الأرقام (x_0 ، ، x_1 ، ، x_2 ، ، ... ) تستمر في الارتداد ذهابًا وإيابًا بين (0 ) و (1 ) ولا تقترب أبدًا من جذر (f ) والذي يقع فوق الفاصل ([- 2، −1] ) (الشكل ( PageIndex {5} )). لحسن الحظ ، إذا اخترنا تقريبًا أوليًا (x_0 ) أقرب إلى الجذر الفعلي ، فيمكننا تجنب هذا الموقف.

تمرين ( PageIndex {3} )

بالنسبة إلى (f (x) = x ^ 3−2x + 2، ) دعنا (x_0 = −1.5 ) وابحث عن (x_1 ) و (x_2 ).

تلميح

استخدم المعادلة المرجع {نيوتن}.

إجابه

(س_1≈ − 1.842105263 )
(س_2≈ − 1.772826920 )

من المثال ( PageIndex {3} ) ، نرى أن طريقة نيوتن لا تعمل دائمًا. ومع ذلك ، عندما يعمل ، فإن تسلسل التقريبات يقترب من الجذر بسرعة كبيرة. يتم تضمين المناقشات حول مدى سرعة اقتراب تسلسل التقريبات من جذر تم العثور عليه باستخدام طريقة نيوتن في نصوص التحليل العددي.

العمليات المتكررة الأخرى

كما ذكرنا سابقًا ، طريقة نيوتن هي نوع من العمليات التكرارية. ننظر الآن إلى مثال لنوع مختلف من العمليات التكرارية.

ضع في اعتبارك دالة (F ) ورقم أولي (x_0 ). حدد الأرقام اللاحقة ​​(x_n ) بالصيغة (x_n = F (x_ {n − 1}) ). هذه العملية هي عملية تكرارية تنشئ قائمة من الأرقام (x_0 ، ، x_1 ، ، x_2 ، ، ... ، ، x_n ، ، .... ) قد تقترب قائمة الأرقام هذه من رقم محدد (x ^ * ) عندما يكبر (n ) ، أو قد لا يكون كذلك. في المثال ( PageIndex {4} ) ، نرى مثالاً للدالة (F ) والتخمين الأولي (x_0 ) بحيث تقترب قائمة الأرقام الناتجة من قيمة محدودة.

مثال ( PageIndex {4} ): إيجاد حد لعملية تكرارية

دعونا (F (x) = frac {1} {2} x + 4 ) ودعنا (x_0 = 0 ). للجميع (n≥1 ) ، دعنا (x_n = F (x_ {n − 1}) ). ابحث عن القيم (x_1، ، x_2، ، x_3، ، x_4، ، x_5 ). ضع تخمينًا حول ما يحدث لقائمة الأرقام هذه (x_1 ، ، x_2 ، ، x_3 ، ، ... ، ، x_n ، ، ... ) كـ (n → ∞ ). إذا كانت قائمة الأرقام (x_1 ، ، x_2 ، ، x_3 ، ، ... ) تقترب من رقم محدد (x ^ * ) ، إذن (x ^ * ) يرضي (x ^ * = F (x ^ *) ) و (x ^ * ) تسمى النقطة الثابتة لـ (F ).

المحلول

إذا (x_0 = 0 ) ، إذن

  • (x_1 = frac {1} {2} (0) + 4 = 4 )
  • (x_2 = فارك {1} {2} (4) + 4 = 6 )
  • (x_3 = frac {1} {2} (6) + 4 = 7 )
  • (x_4 = فارك {1} {2} (7) + 4 = 7.5 )
  • (x_5 = frac {1} {2} (7.5) + 4 = 7.75 )
  • (x_6 = frac {1} {2} (7.75) + 4 = 7.875 )
  • (x_7 = frac {1} {2} (7.875) + 4 = 7.9375 )
  • (x_8 = frac {1} {2} (7.9375) + 4 = 7.96875 )
  • (س _9 = فارك {1} {2} (7.96875) + 4 = 7.984375. )

من هذه القائمة ، نفترض أن القيم (x_n ) تقترب من (8 ).

يقدم الشكل ( PageIndex {6} ) وسيطة بيانية مفادها أن القيم تقترب من (8 ) كـ (n → ∞ ). بدءًا من النقطة ((x_0، x_0) ) ، نرسم خطًا رأسيًا للنقطة ((x_0، F (x_0)) ). الرقم التالي في قائمتنا هو (x_1 = F (x_0) ). نستخدم (x_1 ) لحساب (x_2 ). لذلك ، نرسم خطًا أفقيًا يربط ((x_0 ، x_1) ) بالنقطة ((x_1 ، x_1) ) على الخط (y = x ) ، ثم نرسم خطًا رأسيًا يربط (( x_1 ، x_1) ) إلى النقطة ((x_1 ، F (x_1)) ). الناتج (F (x_1) ) يصبح (x_2 ). بالاستمرار بهذه الطريقة ، يمكننا إنشاء عدد لا حصر له من مقاطع الخطوط. يتم احتجاز مقاطع الخط هذه بين السطور (F (x) = frac {x} {2} +4 ) و (y = x ). تقترب مقاطع الخط من نقطة تقاطع هذين الخطين ، والتي تحدث عند (x = F (x) ). حل المعادلة (x = frac {x} {2} +4، ) نستنتج أنهما يتقاطعان عند (x = 8 ). لذلك ، يتوافق دليلنا الرسومي مع دليلنا العددي على أن قائمة الأرقام (x_0 ، ، x_1 ، ، x_2 ، ، ... ) تقترب من (x * = 8 ) كـ (n → ∞ ).

تمرين ( PageIndex {4} )

ضع في اعتبارك الوظيفة (F (x) = frac {1} {3} x + 6 ). دع (x_0 = 0 ) ودع (x_n = F (x_ {n − 1}) ) لـ (n≥2 ). ابحث عن (x_1، ، x_2، ، x_3، ، x_4، ، x_5 ). ضع تخمينًا حول ما يحدث لقائمة الأرقام (x_1 ، ، x_2 ، ، x_3 ، ، ... ، x_n ، ، ... ) كـ (n → ∞. )

تلميح

ضع في اعتبارك النقطة التي يتقاطع فيها الخطان (y = x ) و (y = F (x) ).

إجابه

(x_1 = 6، ؛ x_2 = 8، ؛ x_3 = frac {26} {3}، ؛ x_4 = frac {80} {9}، ؛ x_5 = frac {242} {27} ؛ ؛ س ^ * = 9 )

العمليات المتكررة والفوضى

يمكن أن تسفر العمليات التكرارية عن بعض السلوك المثير للاهتمام للغاية. في هذا القسم ، رأينا العديد من الأمثلة على العمليات التكرارية التي تقترب من نقطة ثابتة. لقد رأينا أيضًا في مثال ( PageIndex {4} ) أن العملية التكرارية ترتد ذهابًا وإيابًا بين قيمتين. نسمي هذا النوع من السلوك دورة 2. يمكن أن تتقارب العمليات التكرارية مع دورات ذات فترات دورية مختلفة ، مثل دورتين ونصف ، و 4 دورات (حيث تكرر العملية التكرارية سلسلة من أربع قيم) ، و 8 دورات ، وما إلى ذلك.

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

ربما يكون أشهر مثال على الفوضى هو مجموعة ماندلبروت (انظر الشكل) ، الذي سمي على اسم بنوا ماندلبروت (1924-2010) ، الذي بحث في خصائصه وساعد في نشر مجال نظرية الفوضى. عادة ما يتم إنشاء مجموعة Mandelbrot بواسطة الكمبيوتر وتظهر تفاصيل رائعة عن التوسيع ، بما في ذلك النسخ الذاتي للمجموعة. تم عرض العديد من الإصدارات الملونة للمجموعة في المتاحف ويمكن العثور عليها عبر الإنترنت وفي الكتب الشائعة حول هذا الموضوع.

في هذا المشروع نستخدم الخريطة اللوجستية

[f (x) = rx (1 − x) ]

حيث (x∈ [0،1] ) و (r> 0 )

كوظيفة في عمليتنا التكرارية. الخريطة اللوجيستية هي وظيفة بسيطة مخادعة. ولكن ، بناءً على قيمة (r ) ، تعرض العملية التكرارية الناتجة سلوكًا مثيرًا للاهتمام. يمكن أن يؤدي إلى نقاط ثابتة ودورات وحتى فوضى.

لتصور السلوك طويل المدى للعملية التكرارية المرتبطة بالخريطة اللوجستية ، سنستخدم أداة تسمى مخطط شبكة العنكبوت. كما فعلنا مع العملية التكرارية التي فحصناها سابقًا في هذا القسم ، نرسم أولاً خطًا رأسيًا من النقطة ((x_0،0) ) إلى النقطة ((x_0، f (x_0)) = (x_0، x_1 ) ). ثم نرسم خطًا أفقيًا من تلك النقطة إلى النقطة ((x_1، x_1)، ) ثم نرسم خطًا رأسيًا إلى ((x_1، f (x_1)) = (x_1، x_2) ) ، ثم نواصل العملية حتى يصبح سلوك النظام على المدى الطويل واضحًا. يوضح الشكل السلوك طويل المدى للخريطة اللوجستية عند (r = 3.55 ) و (x_0 = 0.2 ). (لم يتم رسم التكرارات الأولى (100 ).) السلوك طويل المدى لهذه العملية التكرارية هو (8 ) - دورة.

  1. دع (r = 0.5 ) واختر (x_0 = 0.2 ). احسب أول (10 ​​) قيم في التسلسل ، إما يدويًا أو باستخدام الكمبيوتر. هل يبدو أن التسلسل يتقارب؟ إذا كان الأمر كذلك ، فما هي القيمة؟ هل ينتج عنه دورة؟ إذا كان الأمر كذلك ، فما نوع الدورة (على سبيل المثال ، (2 ) - دورة ، (4 ) - دورة.)؟
  2. ماذا يحدث عندما (r = 2 )؟
  3. بالنسبة إلى (r = 3.2 ) و (r = 3.5 ) ، احسب قيم التسلسل (100 ) الأولى. قم بإنشاء مخطط شبكة العنكبوت لكل عملية تكرارية. (تتوفر العديد من التطبيقات المجانية عبر الإنترنت التي تنشئ مخططات نسيج العنكبوت للخريطة اللوجستية.) ما هو السلوك طويل المدى في كل حالة من هذه الحالات؟
  4. الآن دع (r = 4. ) احسب قيم التسلسل (100 ) الأولى وقم بإنشاء مخطط شبكة العنكبوت. ما هو السلوك طويل المدى في هذه الحالة؟
  5. كرر العملية لـ (r = 4، ) لكن دع (x_0 = 0.201. ) كيف يقارن هذا السلوك بسلوك (x_0 = 0.2 )؟

المفاهيم الرئيسية

  • تقارب طريقة نيوتن جذور (f (x) = 0 ) بالبدء بتقريب أولي (x_0 ) ، ثم تستخدم خطوطًا مماسة للرسم البياني (f ) لإنشاء تسلسل تقريبي (x_1 ، ، x_2 ، ، x_3 ، ،…. )
  • عادةً ما تكون طريقة نيوتن طريقة فعالة للعثور على جذر معين. في حالات معينة ، تفشل طريقة نيوتن في العمل لأن قائمة الأرقام (x_0 ، ، x_1 ، ، x_2 ، ، ... ) لا تقترب من قيمة محدودة أو تقترب من قيمة أخرى غير الجذر المطلوب.
  • أي عملية يتم فيها إنشاء قائمة من الأرقام (x_0 ، ، x_1 ، ، x_2 ، ، ... ) من خلال تحديد رقم أولي (x_0 ) وتحديد الأرقام اللاحقة بالمعادلة (x_n = F (x_ {n − 1}) ) لبعض الوظائف (F ) هي عملية تكرارية. طريقة نيوتن هي مثال لعملية تكرارية ، حيث تكون الوظيفة (F (x) = x− left [ frac {f (x)} {f ′ (x)} right] ) لوظيفة معينة (F).

قائمة المصطلحات

عملية تكرارية
عملية يتم فيها إنشاء قائمة من الأرقام (x_0 ، x_1 ، x_2 ، x_3 ... ) بالبدء برقم (x_0 ) وتحديد (x_n = F (x_ {n − 1}) ) من أجل (ن 1 )
طريقة نيوتن
طريقة لتقريب جذور (f (x) = 0 ؛ ) باستخدام تخمين أولي (x_0 ) ؛ يتم تحديد كل تقريب لاحق بالمعادلة (x_n = x_ {n − 1} - frac {f (x_ {n − 1})} {f '(x_ {n − 1})} )

إعادة النظر في حساب التفاضل والتكامل رقم 9: طريقة نيوتن

مرحبًا بك في إدخال المدونة رقم 9 من 21 من حساب التفاضل والتكامل الخاص بنا. سنغطي اليوم طريقة نيوتن: طريقة فعالة وقوية لإيجاد جذور الوظائف.

العملية: طريقة نيوتن

الهدف: إيجاد جذور الدالة f (x). أي ، حل من أجل x: f (x) = 0

1. ابدأ بتخمين أولي. فليكن هذا x_n.

2. احسب x_ (n + 1) = x_n - f (x_n) / f '(x_n) (الدالة على مشتقها)

3. إذا تطابق x_n + 1 مع x_n ، تكون قد انتهيت ، ويكون الجذر هو x_n + 1. يمكنك تحديد مدى دقة الإجابة عن طريق تحديد عدد النقاط العشرية التي تريد مطابقتها. دقة الآلة الحاسبة (ما تراه على الشاشة) تختلف من 10 إلى 12 نقطة عشرية.

تحذير: يعد اختيار القيمة الأولية أمرًا مهمًا. عادةً ما يكون اختيار التخمينات الأولية القريبة من الجذر هو الأفضل ، لكن هذا لا يعمل دائمًا.

أيضًا ، هذه الطريقة ليست 100٪ في إيجاد الجذور. إذا حصلت على x_n و x_n + 1 تتخبط بين قيمتين مميزتين ، فستكون عالقًا في حلقة - لن يتم العثور على جذر.

أوصي باستخدام الآلة الحاسبة عند العمل باستخدام طريقة نيوتن. في الآلات الحاسبة العلمية ، قد تتمكن من الاستفادة من ميزة الإجابة الأخيرة ، بتعيين x_n = ans.

مثال: (TI -36X Pro ، TI-30 Multiview ، Casio fx-300 ، Casio fx-115ES ، معظم حاسبات الرسوم البيانية)
2 ENTER (يتم تخزين 2 في الجواب)
الجواب - f (الجواب) / f '(الجواب) (يحسب x_1 مع x_n = 2)
استمر في الضغط على ENTER

مشاكل
غالبًا ما تُستخدم طريقة نيوتن لتقدير الجذور النونية (الجذر التربيعي ، الجذر التكعيبي ، إلخ). ستكون المشكلة الأولى مثالاً على ذلك.

1. تقدير & # 87306 حتى 5 منازل عشرية.

لاحظ أن & # 87304 = 2 و & # 87309 = 3 ، مما يعني & # 87306 يقع بين 2 و 3. لنقم بتخمين أولي 2.5.

استخدم الدالة f (x) = x ^ 2 - 6. لماذا؟

يؤدي إيجاد جذر المعادلة أعلاه إلى & # 87306.

بعد أن x_0 هو التخمين الأولي ،
x_0 = 2.50000
س_1 = 2.45000
x_2 = 2.44949
x_3 = 2.44949

(x_1 = 2.5 - (2.5 ^ 2-6) / (2 * 2.5) = 2.45 ،
x_2 = 2.45 - (2.45 ^ 2 - 6) / (2 * 2.45) = 2.44949 وهكذا)

إذن ، حتى خمسة منازل عشرية ، & # 87306 & # 8776 2.44949

2. أوجد جذر المعادلة e ^ x - x = 5 لأي x> 0. دع x_0 = 2. (التخمين الأولي)

احصل على المعادلة بصيغة f (x) = 0:
ه ^ س - س = 5
ه ^ س - س - 5 = 0

ثم f (x) = e ^ x - x - 5 و f '(x) = e ^ x - 1 و

x_n + 1 = x_n - (e ^ x_n - x_n - 5) / (e ^ x_n - 1)

x_0 = 2.00000
س_1 = 1.93911
س_2 = 1.93685
x_3 = 1.93685

إذن ، جذر f (x) هو x & # 87761.93685.

3. حل x ^ 4 - 4x - 4 = 0 بشرط -1 تلميح: قد ترغب في رسم f (x) بيانيًا لتقدير تخمين أولي مناسب.

ثم f (x) = x ^ 4 - 4x - 4، f '(x) = 4x ^ 3 - 4، و

x_n + 1 = x_n - (x_n ^ 4 - 4x_n - 4) / (4x_n ^ 3 - 4)

بالحساب ، نحصل على:
x_0 = -0.50000
س_1 = -0.93056
x_2 = -0.86520
x_3 = -0.86198
x_4 = -0.86198

هذا يختتمها على طريقة نيوتن. بعد ذلك نتجه نحو التكامل! - إيدي


4.9: طريقة نيوتن - الرياضيات

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

خوارزمية طريقة نيوتن بسيطة وسهلة الاستخدام. يستخدم المشتق الأول للدالة ويعتمد على مفهوم التفاضل والتكامل الأساسي الذي مفاده أن مشتقة الدالة $ f $ عند $ x = c $ هي ميل خط المماس للرسم البياني لـ $ y = f (x) $ عند النقطة $ (c، f (c)) $. دعونا نبني طريقة نيوتن بعناية.

لنفترض أن $ y = f (x) $ دالة قابلة للتفاضل. هدفنا هو حل المعادلة $ f (x) = 0 $ لـ $ x $. دعنا نسمي الحل الدقيق لهذه المعادلة $ x = r $. انظر الرسم البياني أدناه.

نبدأ بـ $ أولي guess $ x_ <0> $. عند النقطة $ (x_ <0>، f (x_ <0>)) $ ارسم خط الظل. قم بالإشارة إلى $ x_ <1> $ على أنها النقطة التي يتقاطع فيها هذا الخط المماس مع المحور $ x $. النقطة $ x_ <1> $ هي تخميننا الثاني. يكرر. عند النقطة $ (x_ <1>، f (x_ <1>)) $ ارسم خط الظل. أشر إلى $ x_ <2> $ كنقطة يتقاطع فيها هذا الخط المماس مع المحور $ x $. النقطة $ x_ <2> $ هي تخميننا الثالث. يكرر . إلخ انظر الرسم البياني أدناه.

يمكننا أن نرى أن هذه التخمينات المتتالية ، $ x_ <0> ، x_ <1> ، x_ <2> ، x_ <3> ، cdots $ zig-zag طريقهم وتقترب أكثر فأكثر من الحل الدقيق $ x = ص دولار. لنقم بإنشاء $ recursion $ الذي سيولد سلسلة من التخمينات المتتالية. لنفكر أولاً في كيفية الانتقال من تخمين إلى آخر ، أي من تخمين $ x_ لتخمين $ x_ $. انظر الرسم البياني أدناه.

المنحدر $ $ لخط المماس عند النقطة $ (x_، و (x_)) $ هو $ I.) m = f '(x_) $ و $ II.) m = displaystyle = ) أكثر من x_ - x_ > $ الآن اضبط المنحدرين على قدم المساواة مع بعضهما البعض لتحصل على $ f '(x_) = ) أكثر من x_ - x_ > سهم طويل $ x_ $ - x_ = ) over f '(x_)> سهم طويل $ x_ $ = x_ - ) over f '(x_)> longrightarrow $ أي ، العودية لطريقة نيوتن هي $ x_ = x_ - ) over f '(x_)> $


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

    المشكلة 1: تطبيق طريقة نيوتن على المعادلة $ x ^ 3 + x-5 = 0 $. ابدأ بالتخمين الأولي المحدد ، $ x_ <0> $ ، وابحث عن $ x_ <1> $ و $ x_ <2> $. ثم استخدم جدول بيانات أو أداة تقنية أخرى لإيجاد حل لهذه المعادلة حتى خمسة منازل عشرية.

أ) استخدم التخمين الأولي $ x_ <0> = 0 $.
ب) استخدم التخمين الأولي $ x_ <0> = 1 $.
ج) استخدم التخمين الأولي $ x_ <0> = -1 $.

انقر هنا لمشاهدة حل مفصل للمشكلة 1.

أ) استخدم التخمين الأولي $ x_ <0> = 1 $.
ب) استخدم التخمين الأولي $ x_ <0> = 2 $.
ج) استخدم التخمين الأولي $ x_ <0> = 0.5 $.
د) استخدم التخمين الأولي $ x_ <0> = 1000 $!
هـ) استخدم التخمين الأولي $ x_ <0> = -500 $!

انقر هنا لمشاهدة حل مفصل للمشكلة 2.

انقر هنا لمشاهدة حل مفصل للمشكلة 3.

انقر هنا لمشاهدة حل تفصيلي للمشكلة 4.

انقر هنا للعودة إلى القائمة الأصلية لأنواع مختلفة من مشاكل التفاضل والتكامل.

تعليقاتك وإقتراحاتك مرحب بها. يرجى إرسال أي مراسلات بالبريد الإلكتروني إلى دوان قبة من خلال النقر على العنوان التالي:

يتم إرسال عبارة "شكرًا لك" الصادقة إلى اتحاد MathJax لجعل إنشاء صفحة الويب هذه أمرًا ممتعًا وسهلاً.


نريد تصغير $ f ( mathbf) $. أولاً ، نعتبر سلسلة Taylor المقتطعة من الدرجة الثانية:

$ و ( mathbf) تقريبا قبعة( mathbf) = و ( mathbf) + [ mathbf- mathbf] ^ T ، nabla f ( mathbf) + frac <1> <2> [ mathbf- mathbf] ^ T ، nabla ^ 2 f ( mathbf) [ mathbf- mathbf]$

النظر في Hessian Matrix $ nabla ^ 2 f ( mathbf) $ هو موجب محدد ، $ hat( mathbf) يمكن تصغير $ بسهولة:

لذلك لدينا القيمة المصغرة:

$ قبعة( mathbf) = و ( mathbf) - [ nabla ^ 2 f ( mathbf) ^ <-1> nabla f ( mathbf)] ^ T nabla f ( mathbf) + frac <1> <2> [ nabla ^ 2 f ( mathbf) ^ <-1> nabla f ( mathbf)] ^ T nabla ^ 2 f ( mathbf) [ nabla ^ 2 f ( mathbf) ^ <-1> nabla f ( mathbf)]$

لذا فإن الإنقاص على التقريب $ hat( mathbf) يُعطى $ بواسطة:

(مصفوفة هسه دائمًا ما تكون متناظرة للوظائف & quotويل التي تصرفت & quot)


مقدمة للتحسين ، الإصدار الرابع

مدح ل الطبعة الثالثة "... يوجه القارئ ويوجهه خلال مسار التعلم... يتم ذكر الأمثلة [e] بوضوح شديد ويتم تقديم النتائج مع الاهتمام بالتفاصيل." & # 160 & # 8212MAA مراجعات & # 160

محدث بالكامل ليعكس التطورات الجديدة في هذا المجال الطبعة الرابعة من مقدمة في التحسين يلبي الحاجة إلى معالجة يمكن الوصول إليها لنظرية التحسين وطرقه مع التركيز على التصميم الهندسي. يتم توفير التعريفات الأساسية والترميز بالإضافة إلى الخلفية الأساسية ذات الصلة للجبر الخطي والهندسة وحساب التفاضل والتكامل. & # 160

  • فصل جديد عن برمجة الأعداد الصحيحة & # 160
  • تغطية موسعة للطرق أحادية البعد # 160
  • أقسام محدثة وموسعة على متباينات المصفوفة الخطية & # 160
  • تمارين جديدة عديدة في نهاية كل فصل & # 160
  • تمارين MATLAB ومشكلات الحفر لتعزيز النظرية والخوارزميات التي تمت مناقشتها # 160
  • العديد من الرسوم البيانية والأشكال التي تكمل العرض المكتوب للمفاهيم الأساسية # 160
  • ملفات MATLAB M لتنفيذ النظرية والخوارزميات التي تمت مناقشتها (متوفرة عبر موقع الكتاب) & # 160

محتويات

تكمن الفكرة في البدء بتخمين أولي قريب بشكل معقول من الجذر الحقيقي ، ثم تقريب الدالة بخط المماس باستخدام حساب التفاضل والتكامل ، وأخيراً لحساب التقاطع x لهذا الخط المماس بواسطة الجبر الأولي. سيكون هذا التقاطع x عادةً تقريبًا أفضل لجذر الوظيفة الأصلية من التخمين الأول ، ويمكن تكرار الطريقة.

بشكل أكثر رسمية ، افترض F : (أ, ب) → ℝ هي دالة تفاضلية محددة في الفاصل الزمني (أ, ب) بقيم في الأعداد الحقيقية ℝ ، ولدينا بعض التقريب الحالي xن . ثم يمكننا اشتقاق الصيغة لتقريب أفضل ، xن + 1 بالإشارة إلى الرسم البياني الموجود على اليمين. معادلة خط المماس للمنحنى ذ = F (x) في x = xن يكون

حيث f ′ يدل على المشتق. التقاطع x لهذا الخط (قيمة x مما يجعل ذ = 0) كالتقريب التالي ، xن + 1 ، إلى الجذر ، بحيث يتم استيفاء معادلة خط الظل عندما (x، y) = (x n + 1، 0) ,0)> :

حل ل xن + 1 يعطي

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

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

اسم "طريقة نيوتن" مشتق من وصف إسحاق نيوتن لحالة خاصة للطريقة في تحليل لكل معادلات عدد لا نهاية له (كتب عام 1669 ، نشره ويليام جونز عام 1711) وفي De metodis fluxionum et serierum infinitarum (تمت كتابته عام 1671 ، وترجمته ونشره باسم طريقة التدفق في عام 1736 بواسطة جون كولسون). ومع ذلك ، فإن طريقته تختلف اختلافًا جوهريًا عن الطريقة الحديثة المذكورة أعلاه. طبق نيوتن الطريقة فقط على كثيرات الحدود ، بدءًا من تقدير الجذر الأولي واستخراج سلسلة من تصحيحات الخطأ. استخدم كل تصحيح لإعادة كتابة كثير الحدود من حيث الخطأ المتبقي ، ثم حل تصحيحًا جديدًا بإهمال شروط الدرجة الأعلى. لم يربط صراحةً الطريقة بالمشتقات أو يقدم صيغة عامة. طبق نيوتن هذه الطريقة على كل من المسائل العددية والجبرية ، وأنتج سلسلة تايلور في الحالة الأخيرة.

قد يكون نيوتن قد اشتق طريقته من طريقة مماثلة ولكن أقل دقة من قبل فييتا. يمكن العثور على جوهر طريقة فييتا في عمل عالم الرياضيات الفارسي شرف الدين الطوسي ، بينما استخدم خليفته جمشيد الكاشي شكلاً من طريقة نيوتن لحلها. x صن = 0 لإيجاد جذور N (Ypma 1995). كانت هناك حالة خاصة لطريقة نيوتن لحساب الجذور التربيعية معروفة منذ العصور القديمة وغالبًا ما تسمى الطريقة البابلية.

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

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

آرثر كايلي في عام 1879 م مشكلة نيوتن - فورييه الخيالية كان أول من لاحظ الصعوبات في تعميم طريقة نيوتن على الجذور المعقدة لكثيرات الحدود بدرجة أكبر من 2 وقيم أولية معقدة. فتح هذا الطريق أمام دراسة نظرية تكرارات الوظائف المنطقية.

طريقة نيوتن هي تقنية قوية - بشكل عام يكون التقارب تربيعيًا: عندما تتقارب الطريقة على الجذر ، يتم تربيع الفرق بين الجذر والتقريب (عدد الأرقام الدقيقة يتضاعف تقريبًا) في كل خطوة. ومع ذلك ، هناك بعض الصعوبات في هذه الطريقة.

صعوبة في حساب مشتق دالة تحرير

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

فشل طريقة التقارب في تحرير الجذر

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

تجاوز التحرير

If the first derivative is not well behaved in the neighborhood of a particular root, the method may overshoot, and diverge from that root. An example of a function with one root, for which the derivative is not well behaved in the neighborhood of the root, is

In some cases, Newton's method can be stabilized by using successive over-relaxation, or the speed of convergence can be increased by using the same method.

Stationary point Edit

If a stationary point of the function is encountered, the derivative is zero and the method will terminate due to division by zero.

Poor initial estimate Edit

A large error in the initial estimate can contribute to non-convergence of the algorithm. To overcome this problem one can often linearize the function that is being optimized using calculus, logs, differentials, or even using evolutionary algorithms, such as the stochastic tunneling. Good initial estimates lie close to the final globally optimal parameter estimate. In nonlinear regression, the sum of squared errors (SSE) is only "close to" parabolic in the region of the final parameter estimates. Initial estimates found here will allow the Newton–Raphson method to quickly converge. It is only here that the Hessian matrix of the SSE is positive and the first derivative of the SSE is close to zero.

Mitigation of non-convergence Edit

In a robust implementation of Newton's method, it is common to place limits on the number of iterations, bound the solution to an interval known to contain the root, and combine the method with a more robust root finding method.

Slow convergence for roots of multiplicity greater than 1 Edit

If the root being sought has multiplicity greater than one, the convergence rate is merely linear (errors reduced by a constant factor at each step) unless special steps are taken. When there are two or more roots that are close together then it may take many iterations before the iterates get close enough to one of them for the quadratic convergence to be apparent. However, if the multiplicity m of the root is known, the following modified algorithm preserves the quadratic convergence rate: [4]

This is equivalent to using successive over-relaxation. On the other hand, if the multiplicity m of the root is not known, it is possible to estimate m after carrying out one or two iterations, and then use that value to increase the rate of convergence.

If the multiplicity m of the root is finite then ز(x) = F(x) / f′(x) will have a root at the same location with multiplicity 1. Applying Newton's method to find the root of ز(x) recovers quadratic convergence in many cases although it generally involves the second derivative of F(x). In a particularly simple case, if F(x) = x m من ثم ز(x) = x / m and Newton's method finds the root in a single iteration with

Suppose that the function f has a zero at α , i.e., F (α) = 0 , and f is differentiable in a neighborhood of α .

If f is continuously differentiable and its derivative is nonzero at α , then there exists a neighborhood of α such that for all starting values x0 in that neighborhood, the sequence <xن> will converge to α . [5]

If the function is continuously differentiable and its derivative is not 0 at α and it has a second derivative at α then the convergence is quadratic or faster. If the second derivative is not 0 at α then the convergence is merely quadratic. If the third derivative exists and is bounded in a neighborhood of α , then:

If the derivative is 0 at α , then the convergence is usually only linear. Specifically, if f is twice continuously differentiable, f ′(α) = 0 and f ″(α) ≠ 0 , then there exists a neighborhood of α such that, for all starting values x0 in that neighborhood, the sequence of iterates converges linearly, with rate 1/2 [6] Alternatively, if f ′(α) = 0 and f ′(x) ≠ 0 for xα , x in a neighborhood U of α , α being a zero of multiplicity r , and if Fج ص (يو) , then there exists a neighborhood of α such that, for all starting values x0 in that neighborhood, the sequence of iterates converges linearly.

However, even linear convergence is not guaranteed in pathological situations.

In practice, these results are local, and the neighborhood of convergence is not known in advance. But there are also some results on global convergence: for instance, given a right neighborhood يو+ of α , if f is twice differentiable in يو+ and if f ′ ≠ 0 , F · f ″ > 0 in يو+ , then, for each x0 في يو+ the sequence xك is monotonically decreasing to α .

Proof of quadratic convergence for Newton's iterative method Edit

According to Taylor's theorem, any function F (x) which has a continuous second derivative can be represented by an expansion about a point that is close to a root of F (x). Suppose this root is α . Then the expansion of F (α) about xن is:


Non-polynomial Functions with Multiple Roots

When using a computer to find roots of more complicated functions it's best to understand what is going on and give the computer a guess close to your desired answer.

مثال 2

[Certain math software is not able to find the solution directly for us. We need to know how to properly use the tool to get the solution, either with graphs or setting up Newton's Method. This could involve giving an initial estimate for the root.]

There appear to be 2 roots, one near ر = &minus1 and the other near ر = 3 . However, if we look more carefully in the region near ر = 3 (by zooming in), we see that there is more than one root there.

By simple substitution, we can see that one of the roots is exactly ر = 3 :

Now for the root near ر = 3.4 .

We will use Newton's Method to approximate the root. We need to differentiate ذ = 1&minus ر 2 + 2 ر . Since we have ر as an exponent in our expression, we need to use logarithms when differentiating. [See how to differentiate logarithms in Derivative of the Logarithmic Function].

Let's differentiate 2 ر by itself first.

Take natural log of both sides:

So for Newton's Method in this example, we would have:

We can write this more conveniently (for later steps) showing the substitution as:

Now, doing another step of Newton's Method:

We can conclude that correct to 7 decimal places, ر = 3.4074505 .

Using Graphs Instead

Using a computer algebra system, we can zoom into the root and we can see (from where the graph cuts the ذ-axis) that ر is indeed close to `3.40745`.

Now for the negative case. يترك ر0 = &minus1 be our initial guess.

`t_2` `=-1.213076633-` `[(1-t^2+2^t)/(-2t+2^t ln 2)]_(t=-1.213076633)` `=-1.198322474`

`t_3` `=-1.198322474-` `[(1-t^2+2^t)/(-2t+2^t ln 2)]_(t=-1.198322474)` `=-1.198250199`

We could continue until we obtained the required accuracy.

Comparing this to the zoomed in graph, we can see that the solution is t = &minus1.198250197 , correct to 9 decimal places.

So the solutions for 1&minus ر 2 + 2 ر = 0 are

correct to 5 decimal places.


BIBLIOGRAPHY

Aristotle, Physics, Book I Nicomachean Ethics, Book III
cf. Thomas L. Health, Mathematics in Aristotle (Oxford,
1949), pp. 270-72. F. Bacon, The Philosophical Works of
Francis Bacon,
ed. J. M. Robertson (London, 1905), p. 249.
Isaac Barrow, Mathematical Lectures read in the Publick
Schools at the University of Cambridge,
trans. John Kirkby
(London, 1734) for Barrow's familiarity with Galileo's works
see Marie Boas Hall, “Galileo's Influence on Seventeenth-
Century English Scientists,” in Galileo, Man of Science, ed.
Ernan McMullin (New York and London, 1967), pp. 411-12.
Ernst Cassirer, Das Erkenntnisproblem, 3 vols. (Berlin,
1922-23), I, 136-44 for Randall's view, see his well-known
paper “Scientific Method in the School of Padua,” مجلة
of the History of Ideas,
1 (1940), 177-206, and its revision
in his The School of Padua and the Emergence of Modern
Science
(Padua, 1961). Cassirer accepted the results of
Randall's inquiry but could not “subscribe to his conclu-
sions,” for he believed Galileo's conception of the dual
method, despite the identity of the terms used, to be more
influenced by the mathematical tradition than by the phi-
losophers of Padua see his “Galileo's Platonism,” in M. P.
Ashley Montagu, ed. Studies and Essays in the History of
Science and Learning
(New York, 1946), pp. 279-97. I. B.
Cohen, Franklin and Newton, An Inquiry into Speculative
Newtonian Experimental Science
. (Philadelphia, 1956).
M. R. Cohen and I. Drabkin, eds., A Source Book in
Greek Science
(New York, 1948 Cambridge, Mass. 1959). أ.
Crombie, Robert Grosseteste and the Origins of Experimental
Science
(Oxford, 1953). Descartes, Oeuvres de Descartes, eds.
C. Adam and P. Tannery, 13 vols. (Paris, 1891-1912). Galen,
Claudii Galeni Opera omnia, ed. C. G. Kühn, 20 vols.
(Leipzig, 1821-33) idem, Galen on Medical Experience, ed.
and trans. R. Walzer (London and New York, 1944). Galileo
Galilei, “Letter to the Grand Duchess Christina” (1615),
in S. Drake, Discoveries and Opinions of Galileo (Garden
City, N.Y., 1957) idem, Opere di Galileo Galilei, ed. أ.
Favaro, 20 vols. (Florence, 1890-1909 reprint 1929-39)
idem, Dialogues Concerning Two New Sciences, trans. H.
Crew and A. de Salvio (New York, 1914) idem, Dialogue
Concerning the Two Chief World Systems,
trans. S. Drake
(Berkeley and Los Angeles, 1953). Neal Gilbert, Renaissance
Concepts of Method
(New York and London, 1960). Thomas
L. Hankins, Jean D'Alembert—Science and the Enlighten-
ment
(Oxford, 1970), passim. Jaako Hintikka, “Kant and the
Tradition of Analysis,” Deskription, Analytizität und Ex-
istenz, 3-4 Forschungsgespräch des internationalen For-
schungszentrum für Grundfragen der Wissenschaften Salz-
burg,
ed. Paul Weingartner (Pustet-Verlag, Salzburg, and
Munich, 1966), pp. 254-72. Robert Hooke, Micrographia
(London, 1665) Hooke used Bacon's term instantia crucis
but in one place modified it to read experimentum crucis.
See Richard S. Westfall, “The Development of Newton's
Theory of Color,” Isis, 53 (1962), 354, and note 46. For a
skeptical appraisal of Newton's famous experiment see
A. I. Sabra, Theories of Light from Descartes to Newton
(London, 1967), pp. 294-97. Sabra's argument that only
Newton's adherence to a corpuscular doctrine permitted
him to infer the heterogeneity of white light from this
experiment is inconclusive. W. S. Jevons, The Principles of
Science
(London and New York, 1905). P. S. de Laplace,
Exposition du système du monde, 6th ed. (Paris, 1835).
A. L. Lavoisier, Traité élémentaire de chimie (Paris, 1789).
Colin Maclaurin, Account of Sir Isaac Newton's Philo-
sophical Discoveries,
3rd ed. (London, 1775). Paul Mouy,
Le Développement de la physique cartésienne, 1646-1712
(Paris, 1934). Isaac Newton, Mathematical Principles of
Natural Philosophy,
ed. F. Cajori (Berkeley, 1934) idem,
Opticks, 4th ed. (1730) idem, Isaac Newton's Papers and
Letters on Natural Philosophy,
ed. I. B. Cohen (Cambridge,
Mass., 1958) idem, “Account of the Booke entituled Com-
mercium Epistolicum, etc.,” Philosophical Transactions, 19,
no. 342 (1717) trans. “Recensio,” in the second edition
(1722) of the Commercium for Newton's authorship of this
“Account” see Louis T. More, Isaac Newton (New York,
1934), pp. 590-91, note 43 idem, Universal Arithmetick
(London, 1728). Jacques Rohault, Traité de physique (Paris,
1671). W. J. 'sGravesande, Introductio ad philosophiam,
metaphysicam et logicam continens
(Leiden, 1736) trans.
into French as Oeuvres philosophiques et mathématiques de
Mr G. J. 'sGravesande,
ed. J. N. S. Allamand, two parts in
one vol. (Amsterdam, 1774). E. W. Strong, “Newton's
'Mathematical Way'” in Roots of Scientific Thought, eds.
Philip P. Wiener and Aaron Noland (New York, 1957) the
article is reprinted, somewhat abridged, from the مجلة
of the History of Ideas,
12 (1951), 90-110. Henry G. Van
Leeuwen, The Problem of Certainty in English Thought
(The Hague, 1963). Basil Willey, The Seventeenth Century
Background
(London, 1949).

[See also Baconianism Classification of the Sciences
Cosmology Experimental Science Newton's Opticks
Number Optics Unity of Science.]


Related Resources

Instructor

Buy Both and Save 25%!

This item: An Introduction to Optimization, 4th Edition

Cannot be combined with any other offers.

Buy Both and Save 25%!

This item: An Introduction to Optimization, 4th Edition

Cannot be combined with any other offers.

Buy Both and Save 25%!

This item: An Introduction to Optimization, 4th Edition

Cannot be combined with any other offers.


Damped Newton's Method

To help improve convergence, newton's method may be dampened with a constant α from (0,1].

Ideally, the each value of α should have the next iteration get as close to the root as possible. Only possible method of determining α is the Bank-Rose algorithm. Ώ]


شاهد الفيديو: طريقة نيوتن رافسون Newton raphson method (شهر اكتوبر 2021).