إيجاد الجذر بطريقة تنصيف الفترة

إيجاد الجذر

• بالنظر إلى الدالة (f(x، ابحث عن x^* بحيث يكون (f(x^*) = 0
• x^* هو جذر f أو صفر f
• أمثلة:
  • f(x) = x^2 - 2 ينتج عنه x^* = ± √2
  • f(x) = x cos x ينتج عنه x^* = 0, ± π/2, ± 3π/2,...

الافتراضات

• إذا كانت f(x) دالة مستمرة على [a, b] و sign(f(a)) ≠ sign(f(b))، فإنه يوجد x^* ∈ [a, b] بحيث f(x^*) = 0
  • نظرية القيمة المتوسطة
• إذا كانت f(x) قابلة للاشتقاق على (a, b) و f'(x) ≠ 0 لـ x ∈ (a, b)، فإن الجذر يكون فريدًا في (a, b)

طريقة تنصيف الفترة

• ابدأ بفترة [a, b] بحيث sign(f(a)) ≠ sign(f(b))
• احسب (f(c حيث c = (a+b)/2
• إذا كان sign(f(c)) = sign(f(a))، فإن الجذر يقع في [c, b]. اجعل a = c
• إذا كان sign(f(c)) ≠ sign(f(a))، فإن الجذر يقع في [a, c]. اجعل b = c
• كرر حتى يصبح |b - a| < ϵ أو |f(c)| < ϵ

الخوارزمية

• الإدخال: f, a, b, ϵ
• c = (a + b) / 2
• بينما (b - a > ϵ) قم بما يلي:
  • إذا كان sign(f(a)) == sign(f(c)) فإن a = c
  • وإلا b = c
  • نهاية الشرط
  • c = (a + b) / 2
• نهاية الحلقة
• الإرجاع: c

التقارب

• بعد n تكرار، تكون الفترة هي [an, bn] بطول (b - a) / 2^n
• الخطأ هو |x^* - cn| ≤ (b - a) / 2^n
• لتحقيق خطأ مقداره ϵ، نحتاج إلى (b - a) / 2^n ≤ ϵ ينتج عنه n ≥ log2( (b - a) / ϵ )
• طريقة تنصيف الفترة تتقارب خطيًا بمعدل 1/2 لكل تكرار
• عدد التكرارات معروف مسبقًا
• طريقة تنصيف الفترة مضمونة للتقارب إذا تم استيفاء الافتراضات

طريقة نيوتن

• ابدأ بتخمين أولي x0
• احسب خط المماس لـ f(x) عند x0: y = f(x0) + f'(x0)(x - x0)
• أوجد جذر خط المماس: 0 = f(x0) + f'(x0)(x - x0) ينتج عنه x = x0 - f(x0) / f'(x0)
• حدّث التخمين: xn+1 = xn - f(xn) / f'(xn)
• كرر حتى |xn+1 - xn| < ϵ أو |f(xn)| < ϵ

الخوارزمية

• الإدخال: f, f', x0, ϵ
• x = x0
• بينما |f(x)| > ϵ قم بما يلي:
  • x = x - f(x) / f'(x)
  • نهاية الحلقة
  • الإرجاع: x

التقارب

• طريقة نيوتن تتقارب تربيعيًا إذا كان التخمين الأولي قريبًا بدرجة كافية من الجذر
  • |xn+1 - x^| ≤ C |xn - x^|^2
• طريقة نيوتن قد لا تتقارب إذا لم يكن التخمين الأولي قريبًا بدرجة كافية من الجذر
  • قد تتباعد
  • قد تتذبذب
  • قد تتقارب إلى جذر مختلف
• طريقة نيوتن تتطلب مشتقة f(x)

2. تكرار النقطة الثابتة

2.1. x = g(x)

• بالنظر إلى الدالة (g(x، ابحث عن x^* بحيث يكون x^* = g(x^*)
• x^* هي نقطة ثابتة لـ g
• أمثلة:
  • g(x) = cos x ينتج عنه x^* ≈ 0.739085
  • g(x) = x^2 - 2 ينتج عنه x^* = -1, 2

2.2. الخوارزمية

• الإدخال: g, x0, ϵ
• x = x0
• بينما |x - g(x)| > ϵ قم بما يلي:
  • x = g(x)
  • نهاية الحلقة
  • الإرجاع: x

2.3. التقارب

• إذا كان |g'(x)| < 1 في جوار x^، فإن تكرار النقطة الثابتة يتقارب إلى x^ إذا كان التخمين الأولي قريبًا بدرجة كافية من x^*
• إذا كان |g'(x)| > 1 في جوار x^، فإن تكرار النقطة الثابتة يتباعد من x^
• تكرار النقطة الثابتة يتقارب خطيًا بمعدل |g'(x^*)|
  • |xn+1 - x^| ≈ |g'(x^)| |xn - x^*|

2.4. مثال

• f(x) = x^2 - 2 = 0 ينتج عنه x = ±√2
• x = g(x) = x^2 + x - 2
• g'(x) = 2x + 1
• |g'(√2)| = 2√2 + 1 > 1 ينتج عنه التباعد
• |g'(-√2)| = -2√2 + 1 < 1 ينتج عنه التقارب