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

نقطة ثابتة تكرارية (بالإنجليزية: 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)^{1 \over 3}=g_{1}(x)$

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

أو $x={5 \over {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)

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

$[a.b]$

البرهان :

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

نفترض أن $g(a)\neq a$ وَ $g(b)\neq 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$

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

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

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

$g(c)=c{\Leftarrow }$

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

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

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

$g'({\xi })={{g(q)-g(p)} \over {q-p}}$

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

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

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

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

نظرية (2)[عدل]

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

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

حدود الخطأ[عدل]

نتيجة :

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

$|{x_{n}}-x|{\leq {k^{n}}}{max[{x_{0}}-a,b-{x_{0}}]}$

و أيضًا

$|{x_{n}}-x|\leq {{k^{n}} \over {1-k}}|{x_{1}}-{x_{0}}|\forall n\geq 1$

تقارب طريقة النقطة الثابتة[عدل]

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

${x_{n}}={\xi }+{\epsilon _{n}}$

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

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

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

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

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

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

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

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

${\epsilon _{n+1}}={\epsilon _{n}}.g'({\eta _{n}});{\eta _{n}}\in ({\xi },{{\xi }+{\epsilon _{n}}})$

$|{\epsilon _{n+1}}|=|{\epsilon _{n}}|.|g'({\eta _{n}})|$

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

خطوات طريقة النقطة الثابتة[عدل]

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

مثال :

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