لماذا متوسط التخميد سحرية تسريع التقارب بين نقطة ثابتة الآلات الحاسبة ؟

Question

أنا أقرأ من خلال SICP ، والكتاب الفرشاة على تقنية متوسط التخميد في الحوسبة النقاط الثابتة من الوظائف.أنا أفهم أنه من الضروري في بعض الحالات ، أي مربع جذور من أجل رطبة من التذبذب وظيفة y = x/y ومع ذلك, أنا لا أفهم لماذا سحرية الإيدز التقارب بين نقطة ثابتة حساب وظيفة.مساعدة ؟

تحرير

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

Answer 1

إلا يسرع تلك المهام التي تتكرر التطبيقات "هوب حول" fixpoint.حدسي انها مثل إضافة الفرامل إلى البندول - سيتوقف عاجلا مع الفرامل.

ولكن ليس كل وظيفة لديها هذه الخاصية.النظر في f(x)=x/2.هذه الوظيفة سوف تتلاقى عاجلا دون متوسط التخميد (سجل قاعدة الخطوات 2 مقابل سجل قاعدة (4/3) الخطوات) ، لأنه نهج fixpoint من جانب واحد.

Answer 2

في حين لا أستطيع الإجابة على سؤالك على اساس رياضي, سأحاول على بديهية واحدة:fixpoint تقنيات تحتاج إلى "شقة" وظيفة الرسم البياني حول ..حسنا..fixpoint.وهذا يعني:إذا الصورة الخاصة بك fixpoint الدالة على X-Y المخطط, سوف ترى أن وظيفة يعبر قطري (+x+y) بالضبط في صحيح النتيجة.في خطوة من fixpoint خوارزمية كنت التخمين X القيمة التي يجب أن يكون ضمن الفاصل حول نقطة التقاطع حيث المشتقة الأولى بين (-1..+1) وتأخذ القيمة Y.ذ أن كنت أخذت يكون أقرب إلى نقطة التقاطع لأن بدءا من تقاطع ذلك يمكن الوصول إليه من خلال اتباع المسار الذي له أصغر المنحدر من +/-1 في المقابل السابقة X القيمة التي يمكنك الاستفادة منها في هذا المعنى الدقيق المنحدر -1.فمن الواضح على الفور الآن أن أصغر المنحدر أكثر طريقة جعل نحو نقطة التقاطع (الوظيفة الحقيقية القيمة) عند استخدام Y جديدة X.أفضل الاستيفاء وظيفة مسلي ثابت ، الذي المنحدر 0, يعطيك القيمة الحقيقية في الخطوة الأولى.

آسف لجميع الرياضيين.