نقطة ثابتة تكرارية
{{لا مصدر|تاريخ=يناير 2022}}
{{وصلات قليلة|تاريخ=أغسطس 2015}}
{{يتيمة|تاريخ=نوفمبر 2014}}
{{بطاقة خوارزمية}}
'''نقطة ثابتة تكرارية''' {{إنج|Fixed-point iteration}} تستخدم هذه الطريقة التكرارية لحل المعادلات و تتميز بأنها لا تتطلب حساب قيم أي مشتقات كما في [[طريقة نيوتن]] حيث لحل المعادلة <math>f(x)=0</math> نحتاج إلى حساب قيمة مشتقة الدالة <math>{f}</math> عند كل خطوة.

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

<math>x=(2x-5)^{1 \over3} = g_1 (x)</math>

أو <math>x={{-5+x^3} \over2} = g_2 (x)</math>

أو <math>x={5 \over{x^2 -2}} = g_3 (x)</math>

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

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

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

البرهان : 
# إذا كانت <math>g(b)=b</math> وَ <math>g(a)=a</math> حيث أن <math>a , b </math> نقط ثابتة . 
نفترض أن <math>g(a)\ne a</math> وَ <math>g(b)\ne b</math>

<math>g(a)>a , g(b)<b {\Leftarrow}</math>

<math>h(x)=g(x)-x  ,h\in C[a,b]</math>

<math>h(a)=g(a)-a>0 </math>

<math>h(b)=g(b)-b <0</math>

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

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

<math>h(c)=g(c)-c{\Leftarrow}</math>

<math>g(c)=c {\Leftarrow}</math>

<math>{c}{\Leftarrow}</math> نقطة ثابتة

# <math>{g'}</math> موجودة و يوجد عدد موجب <math>{k}</math> بحيث أن : <math>|g'(x)|\le k<1</math>

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

<math>g'({\xi})={{g(q)-g(p)} \over{q-p}} </math>

<math>g(q)-g(p)=(q-p)g'({\xi}) {\Leftarrow}</math>

<math>|g(q)-g(p)|=|(q-p)g'({\xi})| {\Leftarrow}</math>

<math>|g(q)-g(p)|=|(q-p)||g'({\xi})| {\Leftarrow}</math>

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

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

نستفيد من إضافة هذا الشرط في النظرية (2) لمعرفة ما إذا كانت الدالة <math>{g}</math> المختارة تقاربية .
==حدود الخطأ==
نتيجة :

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

<math>|{x_n}-x|{\le{k^n}} {max[{x_0}-a,b-{x_0}] }</math>

و أيضًا

<math>|{x_n}-x|\le{{k^n}\over{1-k}} |{x_1}-{x_0}| \forall n\ge1</math>

== تقارب طريقة النقطة الثابتة == 
لإيجاد علاقة تعطي الخطأ <math>{ \epsilon_{n+1}}</math> بدلالة <math>{ \epsilon_n}</math> : نفترض أن <math>{\xi}</math> هي القسمة المضبوطة للجذر إذًا :

<math>{x_n} = {\xi}+{ \epsilon_n}</math>

<math>{x_{n+}} = {\xi}+{ \epsilon_{n+1}}</math>

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

نحصل على <math>{\xi}+{\epsilon_{n+1}}=g({\xi}+{ \epsilon_n})</math>

<math>{ \epsilon_{n+1}}=g({\xi}+{\epsilon_n})-{\xi}</math>

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

إذًا <math>{\xi}=g({\xi})</math>

إذًا <math>{ \epsilon_{n+1}}=g({\xi}+{\epsilon_n})-g({\xi})</math>

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

<math>{ \epsilon_{n+1}}={\epsilon_n}.g'({\eta_n}) ; {\eta_n}\in({\xi},{{\xi}+{\epsilon_n}})</math>

<math>|{ \epsilon_{n+1}}|=|{\epsilon_n}|.|g'({\eta_n})|</math>

بالتالي يكون شرط التقارب <math>|g'({\eta_n})|<1 , \forall n</math>

== خطوات طريقة النقطة الثابتة == 
#نضع <math>f(x)=0</math> 
#<math>f(x)=0 {\Rightarrow}g(x)=x</math> 
#وضع قيمة ابتدائية و لتكن <math>{x_0}</math> 
#<math>{x_n}=g({x_n}-1)</math> ومن ثم نكرر هذه الخطوة إلى الوصول إلى معيار التوقف المطلوب .

مثال :

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

الحل : 
# نختار <math>f(x)=0</math>

<math>x^3 -2x -5=0</math>

<math>x=(2x-5)^{1 \over3}</math>

<math>g(x)=(2x-5)^{1 \over3}</math>

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

<math>g(2)=2.08 \in[2,3]     ,  g(3)=2.22\in[2,3]</math>

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

<math>g'(x)={2\over3}(2x-5)^{-2 \over3}</math>

إذًا هذه الدالة تزايدية مهما أخذت قيمة ل 
<math>{x}</math> 
في الفترة 
<math>[2,3]</math>

<math>g''(x)={-4\over9}{(2x-5)}^{-5 \over3}{<0} </math>
و 
<math>{g'}</math> تناقصية في هذه الفترة

<math> {g''(2)} = {0.23} ,  {g''(3)} = {0.2} </math>

وهذا يعني أن أعلى قيمة لدالة <math> {g'} </math> 
عند <math>g''(2) = 0.23 </math>

<math>|g'(x)|<0.23</math>

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

# نفترض أن <math>x_0 = 2.5</math>

<math>x_1 =f( 2.5)= 2.2544346</math>

<math>x_2 =2.1036120</math>

<math>x_3 = 2.0959274</math>

<math>x_4 =2.0947605</math>

<math>x_5 = 2.0945832</math>

<math>x_6 = 2.0945563</math>

<math>x_7 = 2.0945522</math>

:<math>|{x_7}-{x_6}| =|2.0945563-2.0945522|= 4.1\times10^{-6}<10^{-5}</math>

== مراجع ==
{{مراجع}}

{{شريط بوابات|رياضيات}}

[[تصنيف:خوارزميات إيجاد الجذور]]
[[تصنيف:رياضيات]]
نقطة ثابتة تكرارية  تستخدم هذه الطريقة التكرارية لحل المعادلات و تتميز بأنها لا تتطلب حساب قيم أي مشتقات كما في طريقة نيوتن حيث لحل المعادلة  نحتاج إلى حساب قيمة مشتقة الدالة  عند كل خطوة.

 فكرة هذه الطريقة  
تُعرف النقطة الثابتة لدالة بأنها القيمة التي لا تتغير عندها الدالة  ولحل معادلة ما  بطريقة النقطة الثابتة نضع أولًا المعادلة في الصورة  حيث  دالة في  والواقع أنه يمكن وضع أي معادلة  في هذه الصورة الخاصة المذكورة بعدد لا نهائي من الطرق . فمثلًا الدالة  نستطيع كتابتها كالتالي : 

أو 

أو 

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

نفترض أن لدينا معادلة على الصورة  و لنبدأ بقيمة قريبة من الجذر و لتكن  ثم نكون المتتالية من تقريب المتتابعة  ومن الواضح أنه إذا كانت لهذه المتتالية  نهاية   فإن   يكون جذرًا للمعادلة  و ذلك لأن  .

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

البرهان : 
 إذا كانت  وَ  حيث أن  نقط ثابتة . 
نفترض أن  وَ 

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

 بحيث أن 

 نقطة ثابتة

  موجودة و يوجد عدد موجب  بحيث أن : 

من نظرية القيمة المتوسطة نفترض أن  نقطتين ثابتتين 

 وهذا يؤدي إلى تناقض إذًا يوجد لدالة  نقطة ثابتة وحيدة .

 نظرية (2) 
بالإضافة إلى الشروط السابقة في النظرية (1)  موجودة في  و الثابت  بحيث  فإنه يوجد عدد  
 بحيث المتتابعة معرفة كالتالي  هذه المتتابعة تقاربية و تقترب من النقطة الثابتة الوحيدة .

نستفيد من إضافة هذا الشرط في النظرية (2) لمعرفة ما إذا كانت الدالة  المختارة تقاربية .
حدود الخطأ
نتيجة :

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

و أيضًا

 تقارب طريقة النقطة الثابتة  
لإيجاد علاقة تعطي الخطأ  بدلالة  : نفترض أن  هي القسمة المضبوطة للجذر إذًا :

وبالتعويض في صيغة النقطة الثابتة : 

نحصل على 

و بما أن 
 هي القسمة المضبوطة للجذر، أي أنها تحقق المعادلة 

إذًا 

إذًا 

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

بالتالي يكون شرط التقارب 

 خطوات طريقة النقطة الثابتة  
نضع  
 
وضع قيمة ابتدائية و لتكن  
 ومن ثم نكرر هذه الخطوة إلى الوصول إلى معيار التوقف المطلوب .

مثال :

 أثبت أنه يوجد نقطة ثابتة وحيدة لدالة  .
 ثم استخدم طريقة النقطة الثابتة لإيجاد جذر الدالة في الفترة  وحيث أن مقدار الخطأ 

الحل : 
 نختار 

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

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

إذًا هذه الدالة تزايدية مهما أخذت قيمة ل 
 
في الفترة 

و 
 تناقصية في هذه الفترة

وهذا يعني أن أعلى قيمة لدالة  
عند 

إذًا يوجد نقطة ثابتة ووحيدة في الفترة 

 نفترض أن 

 مراجع 

تصنيف:خوارزميات إيجاد الجذور
تصنيف:رياضيات