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

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

بيانات عامّة

الصنف	خوارزمية إيجاد الجذور

تعديل - تعديل مصدري - تعديل ويكي بيانات

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

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

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

${\displaystyle x=(2x-5)^{1 \over 3}=g_{1}(x)}$

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

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

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

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

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

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

${\displaystyle [a.b]}$

البرهان :

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

نفترض أن ${\displaystyle g(a)\neq a}$ وَ ${\displaystyle g(b)\neq b}$

${\displaystyle g(a)>a,g(b)<b{\Leftarrow }}$

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

${\displaystyle h(a)=g(a)-a>0}$

${\displaystyle h(b)=g(b)-b<0}$

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

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

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

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

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

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

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

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

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

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

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

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

نظرية (2)

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

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

حدود الخطأ

نتيجة :

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

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

و أيضًا

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

مثال :

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

الحل :

1. نختار ${\displaystyle f(x)=0}$

${\displaystyle x^{3}-2x-5=0}$

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

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

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

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

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

${\displaystyle g'(x)={2 \over 3}(2x-5)^{-2 \over 3}}$

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

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

${\displaystyle {g''(2)}={0.23},{g''(3)}={0.2}}$

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

${\displaystyle |g'(x)|<0.23}$

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

1. نفترض أن ${\displaystyle x_{0}=2.5}$

${\displaystyle x_{1}=f(2.5)=2.2544346}$

${\displaystyle x_{2}=2.1036120}$

${\displaystyle x_{3}=2.0959274}$

${\displaystyle x_{4}=2.0947605}$

${\displaystyle x_{5}=2.0945832}$

${\displaystyle x_{6}=2.0945563}$

${\displaystyle x_{7}=2.0945522}$

${\displaystyle |{x_{7}}-{x_{6}}|=|2.0945563-2.0945522|=4.1\times 10^{-6}<10^{-5}}$

مراجع