نقطة ثابتة تكرارية - ويكيبيديا

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يناير 2022)

هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (أغسطس 2015)

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (نوفمبر 2014)

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

بيانات عامّة

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

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

نقطة ثابتة تكرارية (بالإنجليزية: 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}}$ نقطة ثابتة وحيدة .

بالإضافة إلى الشروط السابقة في النظرية (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}}$