نقطة ثابتة تكرارية ( Fixed-point iteration)

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

نقطة ثابتة تكرارية ( 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 \over3} = g_1 (x)

أو x={{-5+x^3} \over2} = 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,12,...... ومن الواضح أنه إذا كانت لهذة المتتالية x_0 , x_1 , x_2 نهاية {\xi} فإن {\xi} يكون جذرًا للمعادلة x=g(x) و ذلك لأن {\xi}=g({\xi }) .

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

إذا كانت ل دالة و 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)|\le k , \forall x\in(a,b) فإنه يوجد بالضبط نقطة واحدة في
[a.b]

البرهان :

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

g(a)>a , g(b)
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)|\le 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} نقطة ثابتة وحيدة .


بالإضافة إلى الشروط السابقة في النظرية (١) {g' } موجودة في (a,b) و الثابت 0
نستفيد من إضافة هذا الشرط في النظرية (٢) لمعرفة ما إذا كانت الدالة {g} المختارة تقاربية .

نتيجة :

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

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

و أيضًا

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

لإيجاد علاقة تعطي الخطأ { \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}
الحل :

نختار f(x)=0
x^3 -2x -5=0

x=(2x-5)^{1 \over3}

g(x)=(2x-5)^{1 \over3}

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

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

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

g'(x)={2\over3}(2x-5)^{-2 \over3}

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

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

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

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

|g'(x)|<0.23

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

نفترض أن 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\times10^{-6}<10^{-5}