نقطة ثابتة تكرارية

نقطة ثابتة تكرارية

نقطة ثابتة تكرارية (بالإنجليزية: Fixed-point iteration)‏ تستخدم هذه الطريقة التكرارية لحل المعادلات و تتميز بأنها لا تتطلب حساب قيم أي مشتقات كما في طريقة نيوتن حيث لحل المعادلة $f(x)=0$ نحتاج إلى حساب قيمة مشتقة الدالة $f$ عند كل خطوة.

فكرة هذه الطريقة

تُعرف النقطة الثابتة لدالة بأنها القيمة التي لا تتغير عندها الدالة $g(p)=p$ ولحل معادلة ما $f(x)=0$ بطريقة النقطة الثابتة نضع أولًا المعادلة في الصورة $x=g(x)$ حيث $g$ دالة في $x$ والواقع أنه يمكن وضع أي معادلة $f(x_0)=0$ في هذه الصورة الخاصة المذكورة بعدد لا نهائي من الطرق . فمثلًا الدالة $f(x)=x^3-2x-5$ نستطيع كتابتها كالتالي : $x^3-2x-5=0$

$x=(2x-5{)}^{\frac{1}{3}}=g_1(x)$

أو $x=\frac{-5+x^3}{2}=g_2(x)$

أو $x=\frac{5}{x^2-2}=g_3(x)$

ويتم اختيار صيغة من الصيغ الخاصة $x=g(x)$ بحيث يؤدي حلها بطريقة النقطة الثابتة إلى التباعد أو التقارب حسب اختيار الدالة كما سيوضح في النظرية .

نفترض أن لدينا معادلة على الصورة $x=g(x)$ و لنبدأ بقيمة قريبة من الجذر و لتكن $x=x_0$ ثم نكون المتتالية من تقريب المتتابعة $x_{n+1}=g(x_n);n=0,1,2,......$ ومن الواضح أنه إذا كانت لهذه المتتالية $x_0,x_1,x_2$ نهاية $\xi$ فإن $\xi$ يكون جذرًا للمعادلة $x=g(x)$ و ذلك لأن $\xi =g(\xi )$ .

مالذي يضمن وجود النقطة الثابتة ؟! و كيف أستطيع تحديد دالة تقاربية ؟! سيوضح ذلك النظرية التالية . نظرية (1)

1. إذا كانت ل دالة و $g\in C[a.b]$ أي دالة متصلة و قابلة للاشتقاق وَ $g(x)\in C[a.b]$ لأي قيمة $x\in C[a.b]$ فإن الدالة $g$ نقطة ثابتة على الأقل .
2. بالإضافة إلى أن $g^{\prime }(x)$ موجودة في $(a,b)$ و العدد الموجب $k,k<1$ موجود و يحقق أن $|g^{\prime }(x)|\le k,\mathrm{\forall }x\in (a,b)$ فإنه يوجد بالضبط نقطة واحدة في

$[a.b]$

البرهان :

1. إذا كانت $g(b)=b$ وَ $g(a)=a$ حيث أن $a,b$ نقط ثابتة .

نفترض أن $g(a)\ne a$ وَ $g(b)\ne b$

$g(a)>a,g(b)<b\Leftarrow$

$h(x)=g(x)-x,h\in C[a,b]$

$h(a)=g(a)-a>0$

$h(b)=g(b)-b<0$

و باستخدام نظرية القيمة المتوسطة نحصل على :

$\mathrm{\exists }c\in [a,b]$ بحيث أن $h(c)=0$

$h(c)=g(c)-c\Leftarrow$

$g(c)=c\Leftarrow$

$c\Leftarrow$ نقطة ثابتة

1. $g^{\prime }$ موجودة و يوجد عدد موجب $k$ بحيث أن : $|g^{\prime }(x)|\le k<1$

من نظرية القيمة المتوسطة نفترض أن $p,q$ نقطتين ثابتتين $\mathrm{\exists }\xi \in (p,q)\subseteq [a,b]\Leftarrow$

$g^{\prime }(\xi )=\frac{g(q)-g(p)}{q-p}$

$g(q)-g(p)=(q-p)g^{\prime }(\xi )\Leftarrow$

$|g(q)-g(p)|=|(q-p)g^{\prime }(\xi )|\Leftarrow$

$|g(q)-g(p)|=|(q-p)||g^{\prime }(\xi )|\Leftarrow$

$|q-p|<|q-p|\Leftarrow$ وهذا يؤدي إلى تناقض إذًا يوجد لدالة $g$ نقطة ثابتة وحيدة .

نظرية (2)

بالإضافة إلى الشروط السابقة في النظرية (1) $g^{\prime }$ موجودة في $(a,b)$ و الثابت $0<k<1$ بحيث $|g^{\prime }(x)|\le k\mathrm{\forall }x\in (a,b)$ فإنه يوجد عدد $p_0$ $[a,b]$ بحيث المتتابعة معرفة كالتالي $x_n=g(x_{n-1});n\le 1$ هذه المتتابعة تقاربية و تقترب من النقطة الثابتة الوحيدة .

نستفيد من إضافة هذا الشرط في النظرية (2) لمعرفة ما إذا كانت الدالة $g$ المختارة تقاربية .

حدود الخطأ

نتيجة :

عند تحقق الشروط في نظرية (1) و نظرية (2) فإن حدود الخطأ الناتجة من استخدام $x_n$ لتقريب إلى $x$ تعطى بالعلاقة التالية :

$|x_n-x|\le k^{n}max[x_0-a,b-x_0]$

و أيضًا

$|x_n-x|\le \frac{k^n}{1-k}|x_1-x_0|\mathrm{\forall }n\ge 1$

تقارب طريقة النقطة الثابتة

لإيجاد علاقة تعطي الخطأ ${ϵ}_{n+1}$ بدلالة ${ϵ}_n$ : نفترض أن $\xi$ هي القسمة المضبوطة للجذر إذًا :

$x_n=\xi +{ϵ}_n$

$x_{n+}=\xi +{ϵ}_{n+1}$

وبالتعويض في صيغة النقطة الثابتة : $x_{n+1}=g(x_n)$

نحصل على $\xi +{ϵ}_{n+1}=g(\xi +{ϵ}_n)$

${ϵ}_{n+1}=g(\xi +{ϵ}_n)-\xi$

و بما أن $\xi$ هي القسمة المضبوطة للجذر، أي أنها تحقق المعادلة $g(x)=x$

إذًا $\xi =g(\xi )$

إذًا ${ϵ}_{n+1}=g(\xi +{ϵ}_n)-g(\xi )$

و بتطبيق نظرية القيمة المتوسطة نجد أن :

${ϵ}_{n+1}={ϵ}_n.g^{\prime }({\eta }_n);{\eta }_n\in (\xi ,\xi +{ϵ}_n)$

$\left|{ϵ}_{n+1}\right|=\left|{ϵ}_n\right|.|g^{\prime }({\eta }_n)|$

بالتالي يكون شرط التقارب $|g^{\prime }({\eta }_n)|<1,\mathrm{\forall }n$

خطوات طريقة النقطة الثابتة

1. نضع $f(x)=0$
2. $f(x)=0\Rightarrow g(x)=x$
3. وضع قيمة ابتدائية و لتكن $x_0$
4. $x_n=g(x_n-1)$ ومن ثم نكرر هذه الخطوة إلى الوصول إلى معيار التوقف المطلوب .

مثال :

1. أثبت أنه يوجد نقطة ثابتة وحيدة لدالة $f(x)=x^3-2x-5$ .
2. ثم استخدم طريقة النقطة الثابتة لإيجاد جذر الدالة في الفترة $[2,3]$ وحيث أن مقدار الخطأ $ϵ=10^{-5}$

الحل :

1. نختار $f(x)=0$

$x^3-2x-5=0$

$x=(2x-5{)}^{\frac{1}{3}}$

$g(x)=(2x-5{)}^{\frac{1}{3}}$

نختبرنظرية (1)

$g(2)=2.08\in [2,3],g(3)=2.22\in [2,3]$

ندرس تزايد أو تناقص الدالة لمعرفة أعلى قيمة

$g^{\prime }(x)=\frac{2}{3}(2x-5{)}^{\frac{-2}{3}}$

إذًا هذه الدالة تزايدية مهما أخذت قيمة ل $x$ في الفترة $[2,3]$

$g^{″}(x)=\frac{-4}{9}{(2x-5)}^{\frac{-5}{3}}<0$ و $g^{\prime }$ تناقصية في هذه الفترة

$g^{″}(2)=0.23,g^{″}(3)=0.2$

وهذا يعني أن أعلى قيمة لدالة $g^{\prime }$ عند $g^{″}(2)=0.23$

$|g^{\prime }(x)|<0.23$

إذًا يوجد نقطة ثابتة ووحيدة في الفترة $[2,3]$

1. نفترض أن $x_0=2.5$

$x_1=f(2.5)=2.2544346$

$x_2=2.1036120$

$x_3=2.0959274$

$x_4=2.0947605$

$x_5=2.0945832$

$x_6=2.0945563$

$x_7=2.0945522$

$|x_7-x_6|=|2.0945563-2.0945522|=4.1\times 10^{-6}<10^{-5}$