عملية دلتا التربيعية لأيتكين

في التحليل العددي ، عملية دلتا تربيع أيتكين أو استقراء أيتكين هي طريقة تسريع سلسلة تستخدم لتسريع معدل تقارب تسلسل. وقد سميت على اسم ألكسندر أيتكين ، الذي قدم هذه الطريقة في عام 1926. ^{[1] وهي مفيدة للغاية لتسريع تقارب تسلسل يتقارب خطيًا. كان} سيكي كوا (1642 - 1708) معروفًا بشكل سابق وتم تطبيقه على تصحيح الدائرة، أي لحساب π.

نظرًا لأن التسلسل الذي يتم إعطاؤه باستخدام عملية دلتا التربيعية لأيتكين يرتبط بهذا التسلسل التسلسل الجديد ${\displaystyle X={(x_{n})}}$${\displaystyle n=0,1,2,3,\ldots ,}$

$${\displaystyle A[X]=(a_{n})={\left({\frac {x_{n}\,x_{n+2}-x_{n+1}^{2}}{x_{n}+x_{n+2}-2\,x_{n+1}}}\right)},}$$

والتي يمكن كتابتها أيضًا على النحو التالي

$${\displaystyle A[X]=\left(x_{n}-{\frac {\Delta x_{n})^{2}}{\Delta ^{2}x_{n}}}\right),}$$

مع وكلاهما نفس التسلسل جبريًا، ولكن الأخير أدى إلى تحسين الاستقرار العددي في التنفيذ الحسابي. ${\textstyle \Delta x_{n}=x_{n+1}-x_{n}}$${\textstyle \دلتا ^{2}x_{n}=x_{n}-2x_{n+1}+x_{n+2}=\دلتا x_{n+1}-\دلتا x_{n}.}$

${\textstyle A[X]}$غير محدد بشكل جيد إذا كان التسلسل يحتوي على عنصر صفر، والذي يحدث إذا كان تسلسل الفروق الأمامية ، يحتوي على أي حد متكرر. من وجهة نظر نظرية، إذا حدث ذلك فقط لعدد محدود من المؤشرات، فيمكن للمرء تطبيق عملية أيتكين فقط على جزء التسلسل الذي يحتوي على مؤشرات مثل آخر مؤشر يتكرر التسلسل عنده . في الممارسة العملية، توفر الحدود القليلة الأولى من التسلسل عادةً الدقة المطلوبة؛ أيضًا، عند حساب التسلسل عدديًا، يجب على المرء أن يحرص على إيقاف الحساب قبل أن تصبح أخطاء التقريب في المقام كبيرة جدًا، حيث قد يلغي تحويل التسلسل الأرقام المهمة . ${\textstyle \Delta ^{2}[X]=(\Delta ^{2}x_{n})}$${\textstyle \Delta [X]=(\Delta x_{n}),}$${\displaystyle X}$${\displaystyle n>n_{0}}$${\displaystyle n_{0}}$${\textstyle \دلتا [X]}$${\textstyle \دلتا ^{2}}$

عملية دلتا التربيعية لأيتكين هي طريقة تسريع التقارب وحالة خاصة من تحويل التسلسل غير الخطي .

يقال عن التسلسل الذي يتقارب إلى قيمة محددة أنه يتقارب خطيًا ، أو من الناحية الفنية بشكل أكثر دقة، خطيًا Q، إذا كان هناك رقم ما ${\textstyle X=(x_{n})}$${\textstyle \ell }$${\textstyle \mu \in (0,1)}$

$${\displaystyle \lim _{n\to \infty }{\frac {|x_{n+1}-\ell |}{|x_{n}-\ell |}}=\mu .}$$

وهذا يعني أن المسافة بين المتتالية ونهايتها تتقلص تقريبًا بنفس النسبة، في كل خطوة، وتصبح نسبة التخفيض أقرب وأقرب إلى تلك النسبة. ويُطلق على هذا أحيانًا أيضًا "التقارب الهندسي"، لأنه خاصية مميزة للمتسلسلة الهندسية ، أو "التقارب الأسي"، لأنه تقارب مثل${\displaystyle \mu ,}$${\displaystyle \mu ^{n}=\exp(n\ln \mu ).}$

ستعمل طريقة أيتكين على تسريع تقارب التسلسل إذا كان يفي بالشروط المحددة أعلاه${\displaystyle X}$${\displaystyle A[X]=(a_{n}),}$${\textstyle \lim _{n\to \infty }{\frac {a_{n}-\ell }{x_{n}-\ell }}=0.}$

${\displaystyle A}$ليس عامل خطي على المتتاليات، ولكنه خطي فيما يتعلق بإضافة المتتاليات الثابتة: إذا كان أي متتالي ثابت ، ثابت لجميع هذا واضح من تعبير من حيث عامل الفرق المحدود${\textstyle A[XC]=A[X]-C,}$${\displaystyle C}$${\displaystyle C=(c)}$${\displaystyle n.}$${\displaystyle A[X]}$ ${\displaystyle \دلتا .}$

لا تتقارب العملية الجديدة بشكل عام تربيعيًا، ولكن بالنسبة لتسلسل دالة متكرر يلبي بعض الدوال المتقاربة إلى نقطة ثابتة ، فإن تقارب التسلسل المتسارع يكون تربيعيًا. في هذه الحالة، تُعرف التقنية باسم طريقة ستيفنسن . ${\displaystyle x_{n+1}=f(x_{n})}$${\displaystyle f}$

تجريبيًا، تعمل عملية A على إزالة "مصطلح الخطأ الأكثر أهمية". ويمكن التحقق من ذلك من خلال النظر في تسلسل من النموذج ، حيث : سيذهب التسلسل بعد ذلك إلى الحد مثل يذهب إلى الصفر. ${\displaystyle x_{n}=\ell +a^{n}+b^{n}}$${\displaystyle 0<b<a<1}$${\displaystyle A[X]}$${\textstyle \ell }$${\displaystyle b^{n}}$

هندسيًا، هو رسم بياني للدالة الأسية التي تحقق ، ولها مقارب أفقي عند (إذا ). ${\displaystyle f(t)}$${\displaystyle f(n)=x_{n}}$${\displaystyle f(n+1)=x_{n+1}}$${\displaystyle f(n+2)=x_{n+2}}$${\displaystyle {\frac {x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n}-2x_{n+1}+x_{n+2}}}}$${\displaystyle x_{n}-2x_{n+1}+x_{n+2}\neq 0}$

يمكننا أيضًا أن نظهر أنه إذا تقاربت تسلسل إلى حدها بمعدل أكبر تمامًا من 1، فلن يكون لها معدل تقارب أفضل. (في الممارسة العملية، نادرًا ما يكون لدينا تقارب تربيعي على سبيل المثال، مما يعني أكثر من 30 (100 على التوالي) من الأرقام العشرية الصحيحة بعد 5 (7 على التوالي) تكرارات (بدءًا من رقم صحيح واحد)؛ وعادةً لا تكون هناك حاجة إلى تسارع في هذه الحالة.) ${\displaystyle X}$${\displaystyle \ell }$${\displaystyle A[X]}$

في الممارسة العملية، غالبًا ما تتقارب بشكل أسرع بكثير إلى الحد الأقصى مما يحدث، كما هو موضح في الحسابات النموذجية أدناه. عادةً، يكون الحساب (الذي يتضمن فقط حساب الفروق، وضرب واحد وقسمة واحدة) أرخص بكثير من حساب المزيد من حدود المتتالية . ومع ذلك، يجب توخي الحذر لتجنب إدخال أخطاء بسبب عدم الدقة الكافية عند حساب الفروق في البسط والمقام للتعبير. ${\displaystyle A[X]}$${\displaystyle X}$${\displaystyle A[X]}$${\displaystyle X}$

المثال 1 : يمكن تقريب قيمة عن طريق افتراض قيمة أولية لـ وتكرار التسلسل التالي، والذي يسمى طريقة هيرون : بدءًا من${\displaystyle {\sqrt {2}}\approx 1.4142136}$${\displaystyle x_{0}}$$${\displaystyle x_{n+1}={\frac {x_{n}+{\frac {2}{x_{n}}}}{2}}.}$$${\displaystyle x_{0}=1:}$

من الجدير بالذكر هنا أن طريقة أيتكين لا توفر تكلفة حساب تكرارين هنا؛ فحساب القيم الثلاث الأولى يتطلب القيم الخمس الأولى . كما أن القيمة الثانية أقل دقة من القيمة الرابعة، وهو أمر غير مفاجئ نظرًا لحقيقة أن عملية أيتكين هي الأنسب للتسلسلات التي تتقارب خطيًا وليس تربيعيًا، وطريقة هيرون لحساب الجذور التربيعية تتقارب تربيعيًا. ^{[ بحاجة لمصدر ]}${\textstyle A[X]}$${\textstyle X}$${\textstyle A[X]}$${\textstyle X}$

المثال 2 : يمكن حساب قيمة كمجموع لانهائي من خلال صيغة لايبنيز لـ π :${\displaystyle {\frac {\pi }{4}}}$

$${\displaystyle {\frac {\pi }{4}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}\approx 0.785398}$$

في هذا المثال، يتم تطبيق طريقة أيتكين على سلسلة متقاربة دون خطية وتسريع التقارب بشكل كبير. لا يزال التقارب دون خطي، ولكن أسرع بكثير من التقارب الأصلي: القيمة الأولى ، التي يتطلب حسابها القيم الثلاث الأولى، أقرب إلى الحد من القيمة الثامنة. ${\textstyle A[X]}$${\textstyle X}$${\textstyle X}$

فيما يلي مثال على استخدام استقراء أيتكن للمساعدة في إيجاد حد التسلسل عند إعطاء بعض القيم الأولية حيث يُفترض أن حد هذا التسلسل هو نقطة ثابتة (على سبيل المثال ). على سبيل المثال، إذا تم إعطاء التسلسل بواسطة مع نقطة البداية ، فستكون الدالة التي لها كنقطة ثابتة (انظر طرق حساب الجذور التربيعية )؛ هذه هي النقطة الثابتة التي سيتم تقريب قيمتها. ${\displaystyle x_{n+1}=f(x_{n})}$${\displaystyle x_{0},}$${\displaystyle f}$${\displaystyle \alpha =f(\alpha )}$${\textstyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {2}{x_{n}}}\right)}$${\displaystyle x_{0}=1,}$${\textstyle f(x):={\frac {1}{2}}\left(x+{\frac {2}{x}}\right),}$${\displaystyle \alpha :={\sqrt {2}}}$

يحسب هذا الرمز الزائف أيضًا تقريب Aitken إلى . سيتم الإشارة إلى عمليات الاستقراء الخاصة بـ Aitken بواسطة . أثناء حساب الاستقراء، من المهم التحقق مما إذا كان المقام أصبح صغيرًا جدًا، وهو ما قد يحدث إذا كان لدينا بالفعل قدر كبير من الدقة؛ بدون هذا الفحص، يمكن إدخال قدر كبير من الخطأ بواسطة القسمة. سيتم الإشارة إلى هذا العدد الصغير بواسطة . نظرًا لأن التمثيل الثنائي للنقطة الثابتة قد يكون لانهائيًا (أو على الأقل كبيرًا جدًا بحيث لا يتناسب مع الذاكرة المتاحة)، فإن الحساب سيتوقف بمجرد أن يكون التقريب ضمن القيمة الحقيقية. ${\displaystyle f^{\prime }(\alpha )}$aitkenXepsilontolerance

%تعتمد هذه الاختيارات على المشكلة التي يتم حلها 
x0 = 1 %القيمة الأولية f ( x ) = ( 1 / 2 ) * ( x + 2 / x ) %الدالة التي تجد العنصر التالي في التسلسل التسامح = 10 ^ - 10 %دقة 10 أرقام مطلوبة epsilon = 10 ^ - 16 %لا تقسم على رقم أصغر من هذا                        
          
            
              

maxIterations = 20 %لا تسمح باستمرار التكرارات إلى ما لا نهاية haveWeFoundSolution = false %هل تمكنا من إيجاد الحل ضمن التسامح المطلوب؟ ليس بعد            
   

بالنسبة إلى i = 1 : الحد الأقصى للتكرارات x1 = f ( x0 ) x2 = f ( x1 )      
      
      

    إذا ( x1 ~= x0 ) lambda = absoluteValue (( x2 - x1 ) / ( x1 - x0 )) %اختياري: يحسب تقريبًا لـ |f'(نقطة ثابتة)|، والذي يُشار إليه بـ lambda end   
                
    

    المقام = ( x2 - x1 ) - ( x1 - x0 );        

    إذا ( القيمة المطلقة ( المقام ) < إبسيلون ) % لتجنب زيادة الخطأ بشكل كبير، لا تقسم على رقم صغير جدًا اطبع ( 'تحذير: المقام صغير جدًا' ) break % اترك الحلقة end           
        
                                                
    

    aitkenX = x2 - ( ( x2 - x1 ) ^ 2 ) / المقام if ( absoluteValue ( aitkenX - x2 ) < afford ) %If the value is within afford print ( "The fixed point is " , aitkenX )) %Display the result of the Aitken extrapolation haveWeFoundSolution = true break %Done, so leave the loop end        
    
              
                
          
                                                
    

    x0 = aitkenX %تحديث x0 للبدء مرة أخرى                   النهاية                                       


إذا ( haveWeFoundSolution == false ) %إذا لم نتمكن من إيجاد حل ضمن التسامح المطلوب print ( "تحذير: غير قادر على إيجاد حل ضمن التسامح المطلوب لـ " , التسامح ) print ( "آخر استقراء محسوب كان " , aitkenX ) end      
     
     

• معدل التقارب
• حدود التسلسل
• تكرار النقطة الثابتة
• استقراء ريتشاردسون
• تحويل التسلسل
• تحول شانكس
• طريقة ستيفنسن

• ويليام إتش بريس وآخرون ، وصفات رقمية بلغة سي ، (1987)، مطبعة جامعة كامبريدج، رقم ISBN 0-521-43108-5 (انظر القسم 5.1) 
• أبراموفيتز وستيجون، دليل الدوال الرياضية ، القسم 3.9.7
• كيندال إي. أتكينسون، مقدمة في التحليل العددي ، (1989) جون وايلي وأولاده، ISBN 0-471-62489-6 

Original text

Rate this translation

Your feedback will be used to help improve Google Translate