ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ความสัมพันธ์เวียนเกิดคือสมการที่ระบุว่าพจน์ที่ i ของลำดับตัวเลขเท่ากับผลรวมของพจน์ก่อนหน้า บ่อยครั้งที่สมการจะแสดงเฉพาะพจน์ก่อนหน้าเท่านั้น โดยมีพารามิเตอร์ที่ไม่ขึ้นกับค่า ของพจน์ที่ i พารามิเตอร์นี้เรียกว่าอันดับของความสัมพันธ์ หากทราบค่าของตัวเลขแรกๆ ในลำดับแล้ว สามารถคำนวณค่าของตัวเลขที่เหลือในลำดับได้โดยการใช้สมการซ้ำๆ ${\displaystyle n}$${\displaystyle k}$${\displaystyle k}$${\displaystyle n}$${\displaystyle k}$${\displaystyle k}$

ในความสัมพันธ์เวียนเกิดเชิงเส้น พจน์ ที่nจะเท่ากับฟังก์ชันเชิงเส้นของพจน์ก่อนหน้า ตัวอย่างที่มีชื่อเสียงคือความสัมพันธ์เวียนเกิดของจำนวนฟิโบนาชชีซึ่ง มี อันดับสอง และฟังก์ชันเชิงเส้นเพียงแค่บวกพจน์สองพจน์ก่อนหน้า ตัวอย่างนี้เป็นความสัมพันธ์เวียนเกิดเชิงเส้นที่มีสัมประสิทธิ์คงที่เนื่องจากสัมประสิทธิ์ของฟังก์ชันเชิงเส้น (1 และ 1) เป็นค่าคงที่ที่ไม่ขึ้นอยู่กับสำหรับความสัมพันธ์เวียนเกิดเหล่านี้ เราสามารถแสดงพจน์ทั่วไปของลำดับเป็นนิพจน์แบบปิดของได้ นอกจากนี้ความสัมพันธ์เวียนเกิดเชิงเส้นที่มีสัมประสิทธิ์พหุนามที่ขึ้นอยู่กับก็มีความสำคัญเช่นกัน เพราะฟังก์ชันพื้นฐาน ทั่วไป และฟังก์ชันพิเศษ หลายฟังก์ชัน มีอนุกรมเทย์เลอร์ที่มีสัมประสิทธิ์ที่สอดคล้องกับความสัมพันธ์เวียนเกิดดังกล่าว (ดูฟังก์ชันโฮโลโนมิก ) ${\displaystyle k}$$${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$${\displaystyle k}$${\displaystyle n.}$${\displaystyle n}$${\displaystyle n}$

การแก้สมการความสัมพันธ์เวียนเกิด หมายถึง การได้มาซึ่งคำตอบในรูปแบบปิด : ฟังก์ชันที่ไม่ใช้การเรียกซ้ำของ ${\displaystyle n}$

แนวคิดของความสัมพันธ์เวียนเกิดสามารถขยายไปสู่อาร์เรย์หลายมิติได้นั่นคือตระกูลดัชนีที่จัดทำดัชนีโดยทูเปิลของจำนวนธรรมชาติ

ความสัมพันธ์เวียนเกิดคือสมการที่แสดงแต่ละองค์ประกอบของลำดับเป็นฟังก์ชันขององค์ประกอบก่อนหน้า กล่าวโดยละเอียดกว่านั้น ในกรณีที่เกี่ยวข้องเฉพาะองค์ประกอบก่อนหน้าโดยตรง ความสัมพันธ์เวียนเกิดจะมีรูปแบบดังนี้

${\displaystyle u_{n}=\varphi (n,u_{n-1})\quad {\text{สำหรับ}}\quad n>0,}$

ที่ไหน

${\displaystyle \varphi :\mathbb {N} \times X\to X}$

เป็นฟังก์ชัน โดยที่Xเป็นเซตที่องค์ประกอบของลำดับต้องเป็นสมาชิก สำหรับใดๆฟังก์ชันนี้จะกำหนดลำดับที่ไม่ซ้ำกันโดยมี เป็นองค์ประกอบแรก เรียกว่าค่าเริ่มต้น^{[ 1 ]}${\displaystyle u_{0}\in X}$${\displaystyle u_{0}}$

การปรับเปลี่ยนคำจำกัดความเพื่อให้ได้ลำดับที่เริ่มต้นจากเทอมที่มีดัชนี 1 หรือสูงกว่านั้นทำได้ง่าย

นี่เป็นการนิยามความสัมพันธ์เวียนเกิดอันดับแรกความสัมพันธ์เวียนเกิดอันดับkมีรูปแบบดังนี้

${\displaystyle u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{nk})\quad {\text{สำหรับ}}\quad n\geq k,}$

โดยที่เป็นฟังก์ชันที่เกี่ยวข้องกับ องค์ประกอบ kตัวที่ต่อเนื่องกันของลำดับ ในกรณีนี้ จำเป็นต้องใช้ค่าเริ่มต้น kค่าเพื่อกำหนดลำดับ ${\displaystyle \varphi :\mathbb {N} \times X^{k}\to X}$

แฟกทอเรียลถูกนิยามโดยความสัมพันธ์เวียนเกิด

${\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}}$

เป็นต้น

เราได้ลำดับของตัวเลขฟิโบนาชชี ซึ่งเริ่มต้นจาก

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

สมการเวียนเกิดนี้สามารถแก้ไขได้ด้วยวิธีการที่อธิบายไว้ด้านล่าง ซึ่งจะ ได้ สูตรของบิเนต์โดยเกี่ยวข้องกับกำลังของรากทั้งสองของพหุนามลักษณะเฉพาะฟังก์ชันก่อกำเนิดของลำดับคือฟังก์ชันตรรกยะ${\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!(nk)!}}.}$

สัมประสิทธิ์ทวินามสามารถคำนวณได้โดยใช้ความสัมพันธ์เวียนเกิดแบบมิติเดียวเช่นกัน:

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

โดยใช้ค่าเริ่มต้น(การหารไม่ได้แสดงเป็นเศษส่วนเพื่อเน้นว่าต้องคำนวณหลังจากคูณแล้ว เพื่อไม่ให้เกิดตัวเลขเศษส่วน) สูตรเวียนเกิดนี้ใช้กันอย่างแพร่หลายในคอมพิวเตอร์ เพราะไม่จำเป็นต้องสร้างตารางเหมือนสูตรเวียนเกิดแบบสองมิติ และไม่เกี่ยวข้องกับจำนวนเต็มขนาดใหญ่มากเหมือนสูตรที่มีแฟกทอเรียล (หากใช้จำนวนเต็มที่เกี่ยวข้องทั้งหมดที่มีค่าน้อยกว่าผลลัพธ์สุดท้าย) ${\textstyle {\binom {n}{0}}=1}$${\textstyle {\binom {n}{k}}={\binom {n}{nk}},}$

เดอะตัวดำเนินการผลต่าง (Difference operator)คือตัวดำเนินการที่แปลงลำดับ (sequence)ไปเป็นลำดับ (sequence) และโดยทั่วไปแล้วแปลงฟังก์ชัน (function)ไปเป็นฟังก์ชัน (function) โดยทั่วไปจะใช้สัญลักษณ์และในสัญลักษณ์เชิงฟังก์ชันว่า ดังนี้ ${\displaystyle \Delta ,}$

${\displaystyle (\Delta f)(x)=f(x+1)-f(x).}$

ดังนั้นจึงเป็นกรณีพิเศษของ ความ แตก ต่างจำกัด

เมื่อใช้สัญลักษณ์ดัชนีสำหรับลำดับ นิยามจะกลายเป็น

${\displaystyle (\Delta a)_{n}=a_{n+1}-a_{n}.}$

โดยทั่วไปจะละ วงเล็บรอบคำว่า " และ" และต้องเข้าใจว่าเป็นพจน์ดัชนีnในลำดับไม่ใช่ใช้กับองค์ประกอบ${\displaystyle \Delta f}$${\displaystyle \Delta a}$${\displaystyle \Delta a_{n}}$${\displaystyle \Delta a,}$${\displaystyle \Delta }$${\displaystyle a_{n}.}$

ลำดับ ที่กำหนด${\displaystyle a=(a_{n})_{n\in \mathbb {N} },}$ผลต่างแรกของaคือ${\displaystyle \Delta a.}$

เดอะความแตกต่างประการที่สองคือ การคำนวณอย่างง่ายแสดงให้เห็นว่า ${\displaystyle \Delta ^{2}a=(\Delta \circ \Delta )a=\Delta (\Delta a)}$

${\displaystyle \Delta ^{2}a_{n}=a_{n+2}-2a_{n+1}+a_{n}.}$

โดยทั่วไปแล้ว ผลต่างลำดับที่kถูกกำหนดแบบเวียนซ้ำดังนี้และเรามี ${\displaystyle \Delta ^{k}=\Delta \circ \Delta ^{k-1},}$

${\displaystyle \Delta ^{k}a_{n}=\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}a_{n+kt}.}$

ความสัมพันธ์นี้สามารถกลับกันได้ ซึ่งจะได้ผลลัพธ์ดังนี้

${\displaystyle a_{n+k}=a_{n}+{k \choose 1}\Delta a_{n}+\cdots +{k \choose k}\Delta ^{k}(a_{n}).}$

เอสมการเชิงผลต่างอันดับkคือสมการที่เกี่ยวข้องกับkครั้งของลำดับหรือฟังก์ชัน ในทำนองเดียวกับที่สมการเชิงอนุพันธ์อันดับkเกี่ยวข้องกับอนุพันธ์อันดับแรกkของฟังก์ชัน

ความสัมพันธ์ทั้งสองข้างต้นช่วยให้สามารถแปลงความสัมพันธ์เวียนเกิดอันดับkไปเป็นสมการเชิงผลต่างอันดับkและในทางกลับกัน แปลงสมการเชิงผลต่างอันดับkไปเป็นความสัมพันธ์เวียนเกิดอันดับk ได้ การแปลงแต่ละครั้งเป็นการผกผันของการแปลงอีกครั้ง และลำดับที่เป็นคำตอบของสมการเชิงผลต่างก็คือลำดับที่สอดคล้องกับความสัมพันธ์เวียนเกิดนั่นเอง

ตัวอย่างเช่น สมการผลต่าง

${\displaystyle 3\Delta ^{2}a_{n}+2\Delta a_{n}+7a_{n}=0}$

เทียบเท่ากับความสัมพันธ์เวียนเกิด

${\displaystyle 3a_{n+2}=4a_{n+1}-8a_{n},}$

ในแง่ที่ว่าสมการทั้งสองนั้นสอดคล้องกับลำดับเดียวกัน

เนื่องจากลำดับจะสอดคล้องกับความสัมพันธ์เวียนเกิดหรือเป็นคำตอบของสมการผลต่างได้เท่ากัน การใช้คำว่า "สมการผลต่าง" จึงไม่จำกัดเฉพาะสมการที่ใช้ตัวดำเนินการผลต่าง^{[ 2 ] [ 3 ]}และคำว่า "ความสัมพันธ์เวียนเกิด" และ "สมการผลต่าง" สามารถใช้แทนกันได้^{[ 4 ]}ดูสมการผลต่างตรรกยะสมการผลต่างสัมประสิทธิ์คงที่เชิงเส้นและสมการผลต่างเมทริกซ์สำหรับตัวอย่างการใช้ "สมการผลต่าง" แทน "ความสัมพันธ์เวียนเกิด"

สมการเชิงผลต่างมีลักษณะคล้ายสมการเชิงอนุพันธ์ และความคล้ายคลึงนี้มักถูกนำมาใช้เพื่อเลียนแบบวิธีการแก้สมการเชิงอนุพันธ์เพื่อนำไปประยุกต์ใช้ในการแก้สมการเชิงผลต่าง และด้วยเหตุนี้จึงใช้ในการแก้ความสัมพันธ์เวียนเกิดด้วย

สมการผลรวมมีความสัมพันธ์กับสมการผลต่าง เช่นเดียวกับที่สมการปริพันธ์มีความสัมพันธ์กับสมการเชิงอนุพันธ์ โปรดดูแคลคูลัสมาตราเวลาสำหรับการรวมทฤษฎีของสมการผลต่างเข้ากับทฤษฎีของสมการเชิงอนุพันธ์

ความสัมพันธ์เวียนเกิดแบบตัวแปรเดียวหรือมิติเดียวเกี่ยวข้องกับลำดับ (เช่น ฟังก์ชันที่กำหนดบนกริดมิติเดียว) ความสัมพันธ์เวียนเกิดแบบหลายตัวแปรหรือมิติ n เกี่ยวข้องกับกริดมิติ n ฟังก์ชันที่กำหนดบนกริดมิติ n ยังสามารถศึกษาได้ด้วยสมการผลต่างย่อย^{[ 5 ]}${\displaystyle n}$${\displaystyle n}$

นอกจากนี้ สำหรับความสัมพันธ์เวียนเกิดเชิงเส้นไม่เอกพันธุ์อันดับแรกทั่วไปที่มีสัมประสิทธิ์ตัวแปร:

${\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-recursiveสำหรับสมการเวียนเกิดเฉพาะเหล่านี้ มีอัลกอริทึมที่เป็นที่รู้จักซึ่งสามารถหาคำตอบที่ เป็น พหุนามตรรกยะหรือไฮเปอร์จีโอเมตริกได้

นอกจากนี้ สำหรับความสัมพันธ์เวียนเกิดเชิงเส้นที่ไม่เป็นเอกพันธ์ทั่วไปที่มีสัมประสิทธิ์คงที่ สามารถแก้ปัญหาได้โดยอาศัยการเปลี่ยนแปลงของพารามิเตอร์^{[ 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^{*}]}$

ด้วยเวกเตอร์สถานะและเมทริกซ์การเปลี่ยนสถานะจะลู่เข้าสู่เวกเตอร์สถานะคงที่ในเชิงอะ ซิมโทติก ก็ต่อเมื่อค่าลักษณะเฉพาะทั้งหมดของเมทริกซ์การเปลี่ยนสถานะ(ไม่ว่าจะเป็นจำนวนจริงหรือจำนวนเชิงซ้อน) มีค่าสัมบูรณ์น้อยกว่า 1 ${\displaystyle x}$${\displaystyle A}$${\displaystyle x}$${\displaystyle x^{*}}$${\displaystyle A}$

พิจารณาความสัมพันธ์เวียนเกิดอันดับแรกแบบไม่เชิงเส้น

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

ความสัมพันธ์เวียนเกิดนี้มีเสถียรภาพในระดับท้องถิ่นหมายความว่ามันลู่เข้าสู่จุดคงที่จุดหนึ่งจากจุดที่อยู่ใกล้กับจุดนั้นมากพอหากความชันของความสัมพันธ์เวียนเกิด ในบริเวณใกล้เคียงกับจุดนั้นมีค่าสัมบูรณ์น้อยกว่า หนึ่ง นั่นคือ ${\displaystyle x^{*}}$${\displaystyle x^{*}}$${\displaystyle f}$${\displaystyle x^{*}}$

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

ความสัมพันธ์เวียนเกิดแบบไม่เชิงเส้นอาจมีจุดคงที่หลายจุด ซึ่งในกรณีนี้บางจุดอาจมีเสถียรภาพเฉพาะที่ และบางจุดอาจไม่มีเสถียรภาพเฉพาะที่ สำหรับฟังก์ชันต่อเนื่องf จุดคงที่ที่อยู่ติดกันสองจุดไม่สามารถมีเสถียรภาพเฉพาะที่ได้ทั้งคู่

ความสัมพันธ์เวียนเกิดแบบไม่เชิงเส้นอาจมีวัฏจักรที่มีคาบเท่ากับ n ได้เช่นกัน วัฏจักรดังกล่าวมีเสถียรภาพ หมายความว่ามันดึงดูดชุดเงื่อนไขเริ่มต้นที่มีค่าเป็นบวก หากฟังก์ชันประกอบ ${\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 y'(t)=f(t,y(t)),\ \ y(t_{0})=y_{0},}$

ด้วยวิธีของออยเลอร์และขนาดขั้นตอนเราสามารถคำนวณค่าต่างๆ ได้ ${\displaystyle h}$

${\displaystyle y_{0}=y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots }$

โดยการเกิดซ้ำ

${\displaystyle \,y_{n+1}=y_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh}$

ระบบสมการเชิงอนุพันธ์อันดับหนึ่งเชิงเส้นสามารถแปลงเป็นดิสครีตได้อย่างแม่นยำด้วยวิธีเชิงวิเคราะห์ โดยใช้วิธีการที่แสดงในบทความ เกี่ยวกับดิสครีต

สมการเชิงผลต่างที่รู้จักกันดีหลายสมการมีที่มาจากความพยายามในการจำลองพลวัตของประชากรตัวอย่างเช่นลำดับฟิโบนาชชีเคยถูกใช้เป็นแบบจำลองสำหรับการเติบโตของประชากรกระต่าย

แผนที่โลจิสติกส์ใช้โดยตรงในการจำลองการเติบโตของประชากร หรือใช้เป็นจุดเริ่มต้นสำหรับแบบจำลองพลวัตของประชากรที่ละเอียดกว่า ในบริบทนี้ สมการผลต่างแบบคู่มักถูกใช้เพื่อจำลองปฏิสัมพันธ์ของประชากร สองกลุ่มขึ้นไป ตัวอย่างเช่นแบบจำลอง Nicholson–Baileyสำหรับปฏิสัมพันธ์ระหว่างโฮสต์และปรสิตแสดงได้ดังนี้

${\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}$

อัลกอริทึมแบบง่ายจะค้นหาจากซ้ายไปขวา ทีละองค์ประกอบ สถานการณ์ที่แย่ที่สุดคือเมื่อองค์ประกอบที่ต้องการอยู่เป็นตัวสุดท้าย ดังนั้นจำนวนการเปรียบเทียบจึงเท่ากับ0 ${\displaystyle n}$

อัลกอริทึมที่ดีกว่าเรียกว่าการค้นหาแบบไบนารี (Binary Search ) อย่างไรก็ตาม อัลกอริทึมนี้ต้องการเวกเตอร์ที่เรียงลำดับแล้ว ขั้นแรกจะตรวจสอบว่าองค์ประกอบที่ต้องการค้นหาอยู่ตรงกลางของเวกเตอร์หรือไม่ ถ้าไม่อยู่ตรงกลาง ก็จะตรวจสอบว่าองค์ประกอบตรงกลางนั้นมากกว่าหรือน้อยกว่าองค์ประกอบที่ต้องการค้นหาหรือไม่ หลังจากนั้น สามารถทิ้งครึ่งหนึ่งของเวกเตอร์และเรียกใช้อัลกอริทึมอีกครั้งกับครึ่งที่เหลือ จำนวนการเปรียบเทียบจะกำหนดโดย...

${\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},}$

โดยที่คือสัญญาณอินพุต ณ เวลา 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 ]} โดยเฉพาะอย่างยิ่ง ในเศรษฐศาสตร์มหภาค อาจมีการพัฒนาแบบจำลองของภาคส่วนต่างๆ ของเศรษฐกิจ (ภาคการเงิน ภาคสินค้า ตลาดแรงงาน ฯลฯ) ซึ่งการกระทำของตัวแทนบางส่วนขึ้นอยู่กับตัวแปรที่ล่าช้า แบบจำลองจะถูกแก้หาค่าปัจจุบันของตัวแปรสำคัญ ( อัตราดอกเบี้ยผลิตภัณฑ์มวลรวมภายในประเทศที่แท้จริงฯลฯ) ในรูปของค่าในอดีตและปัจจุบันของตัวแปรอื่นๆ

• "ความสัมพันธ์เวียนเกิด" , สารานุกรมคณิตศาสตร์ , EMS Press , 2001 [1994]
• ไวส์สไตน์, เอริค ดับเบิลยู. "สมการเวียนเกิด" . แมธเวิลด์ .
• "คำแนะนำดัชนี OEIS "ดัชนี OEISรวบรวมตัวอย่างความสัมพันธ์เวียนเกิดเชิงเส้นหลายพันตัวอย่าง เรียงลำดับตามลำดับ (จำนวนพจน์) และลักษณะเฉพาะ (เวกเตอร์ของค่าสัมประสิทธิ์คงที่)