علاقة التكرار

يتم تعريف المضروب بواسطة العلاقة التكرارية

${\displaystyle n!=n\cdot (n-1)!\quad {\text{لـ}}\quad n>0,}$

والشرط الأولي

${\displaystyle 0!=1.}$

هذا مثال على علاقة تكرارية خطية بمعاملات متعددة الحدود من الدرجة 1، مع متعددة الحدود البسيطة (في n )

${\displaystyle n}$

باعتباره معاملها الوحيد.

من أمثلة العلاقات التكرارية الخريطة اللوجستية المحددة بواسطة

${\displaystyle x_{n+1}=rx_{n}(1-x_{n}),}$

لثابت معين${\displaystyle r.}$يعتمد سلوك التسلسل بشكل كبير على${\displaystyle r,}$لكنها مستقرة عندما تكون الحالة الأولية${\displaystyle x_{0}}$يختلف.

تُعدّ العلاقة التكرارية من الرتبة الثانية التي تحققها أعداد فيبوناتشي مثالًا نموذجيًا لعلاقة تكرارية خطية متجانسة ذات معاملات ثابتة (انظر أدناه). تُعرَّف متتالية فيبوناتشي باستخدام العلاقة التكرارية.

${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$

مع الشروط الأولية

${\displaystyle F_{0}=0}$

${\displaystyle F_{1}=1.}$

وبشكل صريح، ينتج عن التكرار المعادلات التالية

${\displaystyle F_{2}=F_{1}+F_{0}}$

${\displaystyle F_{3}=F_{2}+F_{1}}$

${\displaystyle F_{4}=F_{3}+F_{2}}$

إلخ.

نحصل على متتالية أعداد فيبوناتشي، التي تبدأ

٠، ١، ١، ٢، ٣، ٥، ٨، ١٣، ٢١، ٣٤، ٥٥، ٨٩، ...

يمكن حل المعادلة التكرارية بالطرق الموضحة أدناه، مما ينتج عنه صيغة بينيه ، والتي تتضمن قوى جذري كثير الحدود المميز.${\displaystyle t^{2}=t+1}$الدالة المولدة للمتتالية هي الدالة الكسرية

${\displaystyle {\frac {t}{1-tt^{2}}}.}$

تُعطى معاملات ذات الحدين كمثال بسيط على علاقة تكرارية متعددة الأبعاد${\displaystyle {\tbinom {n}{k}}}$، والتي تحسب طرق الاختيار${\displaystyle k}$عناصر من مجموعة${\displaystyle n}$العناصر. يمكن حسابها بواسطة علاقة التكرار

${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}$

مع الحالات الأساسية${\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}$باستخدام هذه الصيغة لحساب قيم جميع معاملات ذات الحدين، ينتج مصفوفة لانهائية تُسمى مثلث باسكال . ويمكن أيضًا حساب القيم نفسها مباشرةً باستخدام صيغة أخرى ليست تكرارية، ولكنها تستخدم المضروب والضرب والقسمة، وليس الجمع فقط.

${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$

يمكن أيضًا حساب معاملات ذات الحدين باستخدام علاقة تكرارية أحادية البعد:

${\displaystyle {\binom {n}{k}}={\binom {n}{k-1}}(n-k+1)/k,}$

بالقيمة الأولية${\textstyle {\binom {n}{0}}=1}$(لا يُعرض ناتج القسمة على شكل كسر للتأكيد على ضرورة حسابه بعد الضرب، تجنبًا لإدخال أعداد كسرية). يُستخدم هذا التكرار على نطاق واسع في الحواسيب لأنه لا يتطلب إنشاء جدول كما هو الحال في التكرار ثنائي الأبعاد، ولا يتضمن أعدادًا صحيحة كبيرة جدًا كما هو الحال في صيغة المضروب (إذا استخدمنا${\textstyle {\binom {n}{k}}={\binom {n}{n-k}},}$(جميع الأعداد الصحيحة الداخلة في هذه العملية أصغر من النتيجة النهائية).

تتعلق العلاقات التكرارية أحادية المتغير أو أحادية البعد بالمتتاليات (أي الدوال المعرفة على شبكات أحادية البعد). أما العلاقات التكرارية متعددة المتغيرات أو متعددة الأبعاد فتتعلق بـ${\displaystyle n}$الشبكات ذات الأبعاد n. الدوال المعرفة على${\displaystyle n}$يمكن أيضًا دراسة الشبكات باستخدام معادلات الفرق الجزئي. ^{[ 5 ]}

علاوة على ذلك، بالنسبة لعلاقة التكرار الخطي غير المتجانسة من الدرجة الأولى العامة ذات المعاملات المتغيرة:

${\displaystyle a_{n+1}=f_{n}a_{n}+g_{n},\qquad f_{n}\neq 0,}$

وهناك أيضًا طريقة جيدة لحلها: ^{[ 6 ]}

${\displaystyle a_{n+1}-f_{n}a_{n}=g_{n}}$

${\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {f_{n}a_{n}}{\prod _{k=0}^{n}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}$

${\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}$

يترك

${\displaystyle A_{n}={\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}},}$

ثم

${\displaystyle A_{n+1}-A_{n}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}$

${\displaystyle \sum _{m=0}^{n-1}(A_{m+1}-A_{m})=A_{n}-A_{0}=\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}$

${\displaystyle {\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}=A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}$

${\displaystyle a_{n}=\left(\prod _{k=0}^{n-1}f_{k}\right)\left(A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}\right)}$

إذا طبقنا الصيغة على${\displaystyle a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}}$وخذ الحد${\displaystyle h\to 0}$، نحصل على صيغة المعادلات التفاضلية الخطية من الدرجة الأولى ذات المعاملات المتغيرة؛ يصبح المجموع تكاملاً، ويصبح الناتج دالة أسية للتكامل.

يمكن حل العديد من العلاقات التكرارية الخطية المتجانسة باستخدام متسلسلات فرط هندسية معممة . وتؤدي حالات خاصة من هذه العلاقات إلى علاقات تكرارية لكثيرات الحدود المتعامدة ، والعديد من الدوال الخاصة . على سبيل المثال، حل المعادلة

${\displaystyle J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1}}$

يُعطى بواسطة

${\displaystyle J_{n}=J_{n}(z),}$

دالة بيسل ، بينما

${\displaystyle (b-n)M_{n-1}+(2n-b+z)M_{n}-nM_{n+1}=0}$

يتم حلها بواسطة

${\displaystyle M_{n}=M(n,b;z)}$

المتسلسلة الهندسية الفائقة المتقاربة . تُسمى المتتابعات التي تمثل حلولًا لمعادلات الفرق الخطية ذات المعاملات متعددة الحدود بالمتتابعات التكرارية من النوع P. توجد خوارزميات معروفة لإيجاد حلول متعددة الحدود أو نسبية أو هندسية فائقة لهذه المعادلات التكرارية تحديدًا.

علاوة على ذلك، بالنسبة لعلاقة التكرار الخطي غير المتجانسة العامة ذات المعاملات الثابتة، يمكن حلها بناءً على تغيير المعامل. ^{[ 7 ]}

تأخذ معادلة الفرق الكسرية من الدرجة الأولى الشكل التالي:${\displaystyle w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}}$يمكن حل هذه المعادلة بكتابة${\displaystyle w_{t}}$كتحويل غير خطي لمتغير آخر${\displaystyle x_{t}}$والتي تتطور بدورها بشكل خطي. بعد ذلك، يمكن استخدام الطرق القياسية لحل معادلة الفرق الخطية في${\displaystyle x_{t}}$.

التكرار الخطي من الرتبة${\displaystyle d}$،

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},}$

لها المعادلة المميزة

${\displaystyle \lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.}$

العلاقة التكرارية مستقرة ، مما يعني أن التكرارات تتقارب بشكل مقارب إلى قيمة ثابتة، إذا وفقط إذا كانت القيم الذاتية (أي جذور المعادلة المميزة)، سواء كانت حقيقية أو مركبة، جميعها أقل من واحد في القيمة المطلقة.

في معادلة الفرق المصفوفي من الدرجة الأولى

${\displaystyle [x_{t}-x^{*}]=A[x_{t-1}-x^{*}]}$

مع متجه الحالة${\displaystyle x}$ومصفوفة الانتقال${\displaystyle A}$،${\displaystyle x}$يتقارب بشكل مقارب إلى متجه الحالة المستقرة${\displaystyle x^{*}}$إذا وفقط إذا كانت جميع القيم الذاتية لمصفوفة الانتقال${\displaystyle A}$(سواء كانت أعدادًا حقيقية أو مركبة) لها قيمة مطلقة أقل من  1.

ضع في اعتبارك التكرار غير الخطي من الدرجة الأولى

${\displaystyle x_{n}=f(x_{n-1}).}$

هذا التكرار مستقر محليًا ، مما يعني أنه يتقارب إلى نقطة ثابتة${\displaystyle x^{*}}$من نقاط قريبة بما فيه الكفاية من${\displaystyle x^{*}}$إذا كان ميل${\displaystyle f}$ في جوار${\displaystyle x^{*}}$أصغر من الواحد بالقيمة المطلقة: أي،

${\displaystyle |f'(x^{*})|<1.}$

قد يكون للتكرار غير الخطي نقاط ثابتة متعددة، وفي هذه الحالة قد تكون بعض النقاط الثابتة مستقرة محليًا والبعض الآخر غير مستقر محليًا؛ بالنسبة للدالة المستمرة f، لا يمكن أن تكون نقطتان ثابتتان متجاورتان مستقرتين محليًا.

قد يكون للعلاقة التكرارية غير الخطية دورة زمنية.${\displaystyle k}$ل${\displaystyle k>1}$تكون هذه الدورة مستقرة، أي أنها تجذب مجموعة من الشروط الأولية ذات القياس الموجب، إذا كانت الدالة المركبة

${\displaystyle g(x):=f\circ f\circ \cdots \circ f(x)}$

مع${\displaystyle f}$الظهور${\displaystyle k}$تكون الأوقات مستقرة محليًا وفقًا للمعيار نفسه:

${\displaystyle |g'(x^{*})|<1,}$

أين${\displaystyle x^{*}}$أي نقطة في الدورة.

في علاقة تكرارية فوضوية ، المتغير${\displaystyle x}$تبقى ضمن منطقة محدودة لكنها لا تتقارب أبدًا إلى نقطة ثابتة أو دورة جاذبة؛ أي نقاط ثابتة أو دورات في المعادلة غير مستقرة. انظر أيضًا الخريطة اللوجستية ، والتحويل الثنائي ، وخريطة الخيمة .

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

تُستخدم الخريطة اللوجستية إما مباشرةً لنمذجة النمو السكاني، أو كنقطة انطلاق لنماذج أكثر تفصيلًا لديناميكيات السكان. في هذا السياق، تُستخدم معادلات الفرق المقترنة غالبًا لنمذجة تفاعل مجموعتين سكانيتين أو أكثر . على سبيل المثال، يُعطى نموذج نيكلسون-بيلي لتفاعل المضيف والطفيلي بالصيغة التالية:

${\displaystyle N_{t+1}=\lambda N_{t}e^{-aP_{t}}}$

${\displaystyle P_{t+1}=N_{t}(1-e^{-aP_{t}}),}$

مع${\displaystyle N_{t}}$يمثلون المضيفين، و${\displaystyle P_{t}}$الطفيليات، في بعض الأحيان${\displaystyle t}$.

تُعدّ المعادلات التكاملية التفاضلية شكلاً من أشكال العلاقات التكرارية المهمة في علم البيئة المكانية . وتُعتبر هذه المعادلات، إلى جانب معادلات تفاضلية أخرى، مناسبة بشكل خاص لنمذجة التجمعات السكانية أحادية الجيل .

تُعد العلاقات التكرارية ذات أهمية أساسية في تحليل الخوارزميات . ^{[ 8 ] [ 9 ]} إذا صُممت خوارزمية بحيث تقسم مشكلة إلى مشاكل فرعية أصغر ( فرق تسد )، فإن وقت تشغيلها يُوصف بعلاقة تكرارية.

ومن الأمثلة البسيطة على ذلك الوقت الذي تستغرقه الخوارزمية للعثور على عنصر في متجه مرتب مع${\displaystyle n}$العناصر، في أسوأ الأحوال.

ستبحث الخوارزمية البسيطة من اليسار إلى اليمين، عنصرًا واحدًا في كل مرة. أسوأ سيناريو ممكن هو عندما يكون العنصر المطلوب هو الأخير، وبالتالي يكون عدد المقارنات${\displaystyle n}$.

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

${\displaystyle c_{1}=1}$

${\displaystyle c_{n}=1+c_{n/2}}$

سيكون التعقيد الزمني لذلك هو${\displaystyle O(\log _{2}(n))}$.

في معالجة الإشارات الرقمية ، يمكن لعلاقات التكرار أن تُنمذج التغذية الراجعة في النظام، حيث تصبح المخرجات في وقت ما مدخلات في وقت لاحق. ومن ثم، تنشأ هذه العلاقات في مرشحات الاستجابة النبضية اللانهائية (IIR) الرقمية .

على سبيل المثال، معادلة مرشح مشط IIR "التغذية الأمامية" للتأخير${\displaystyle T}$يكون:

${\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha y_{t-T},}$

أين${\displaystyle x_{t}}$المدخل في الوقت${\displaystyle t}$،${\displaystyle y_{t}}$هو الناتج في الوقت${\displaystyle t}$، و${\displaystyle \alpha }$يتحكم هذا في مقدار الإشارة المتأخرة التي تُعاد إلى المخرج. ومن هذا نستنتج أن

${\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha ((1-\alpha )x_{t-T}+\alpha y_{t-2T})}$

${\displaystyle y_{t}=(1-\alpha )x_{t}+(\alpha -\alpha ^{2})x_{t-T}+\alpha ^{2}y_{t-2T}}$

إلخ.

تُستخدم العلاقات التكرارية، وخاصةً العلاقات التكرارية الخطية، على نطاق واسع في الاقتصاد النظري والتطبيقي. ^{[ 10 ] [ 11 ]} فعلى وجه الخصوص، في الاقتصاد الكلي، يمكن تطوير نموذج لقطاعات اقتصادية واسعة النطاق (القطاع المالي، قطاع السلع، سوق العمل، إلخ) حيث تعتمد تصرفات بعض الفاعلين على متغيرات سابقة. ثم يُحل النموذج لإيجاد القيم الحالية للمتغيرات الرئيسية ( سعر الفائدة ، الناتج المحلي الإجمالي الحقيقي ، إلخ) بدلالة القيم السابقة والحالية لمتغيرات أخرى.

• باتشيلدر، بول م. (1967). مقدمة في المعادلات التفاضلية الخطية . منشورات دوفر.
• ميلر، كينيث س. (1968). المعادلات التفاضلية الخطية . دبليو إيه بنجامين.
• فيلمور، جاي ب.؛ ماركس، موريس ل. (1968). "المتتاليات الخطية المتكررة". مجلة SIAM للمراجعات . المجلد  10، العدد  3. الصفحات 324-353 . JSTOR 2027658 .  
• بروسو، ألفريد (1971). التكرار الخطي ومتتاليات فيبوناتشي . جمعية فيبوناتشي.
• توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 1990. ISBN 0-262-03293-7الفصل الرابع: التكرارات، الصفحات  62-90.
• غراهام، رونالد ل .؛ كنوث، دونالد إي .؛ باتاشنيك، أورين (1994). الرياضيات الملموسة: أساس لعلوم الحاسوب (  الطبعة الثانية). أديسون-ويسلي. ISBN 0-201-55802-5.
• إندرز، والتر (2010). السلاسل الزمنية الاقتصادية القياسية التطبيقية (  الطبعة الثالثة). مؤرشف من الأصل بتاريخ 10-11-2014.
• كول، بول؛ فلاهيف، ماري ؛ روبسون، روبي (2005). المعادلات التفاضلية: من الأرانب إلى الفوضى . سبرينغر. ISBN 0-387-23234-6.الفصل السابع.
• جاك، إيان (2006). الرياضيات للاقتصاد والأعمال (  الطبعة الخامسة). برنتيس هول. الصفحات 551-568 . ISBN  0-273-70195-9.الفصل 9.1: المعادلات التفاضلية.
• مينه، تانغ؛ فان تو، تان (2006). "استخدام الدوال المولدة لحل المعادلات التكرارية الخطية غير المتجانسة" (ملف PDF) . وقائع المؤتمر الدولي للمحاكاة والنمذجة والتحسين، SMO'06 . الصفحات 399-404 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 4 مارس 2016. تاريخ الاسترجاع: 7 أغسطس 2014 . 
• بوليانين، أندريه د. "المعادلات التفاضلية والوظيفية: الحلول الدقيقة" .في EqWorld - عالم المعادلات الرياضية.
• بوليانين، أندريه د. "المعادلات التفاضلية والوظيفية: الطرق" .في EqWorld - عالم المعادلات الرياضية.
• وانغ، شيانغ-شنغ؛ وونغ، رودريك (2012). "السلوك التقاربي لكثيرات الحدود المتعامدة عبر علاقات التكرار". التحليل والتطبيقات 10 (2): 215-235 . arXiv : 1101.4371 . doi : 10.1142/S0219530512500108 . S2CID 28828175 .