الفترات المتداخلة

لتوضيح هذه الخوارزمية، إليك مثال على كيفية استخدامها لإيجاد قيمة${\displaystyle {\sqrt {19}}}$لاحظ أنه منذ${\displaystyle 1^{2}<19<5^{2}}$يمكن تعريف الفترة الأولى للخوارزمية على النحو التالي:${\displaystyle I_{1}:=[1,5]}$، منذ${\displaystyle {\sqrt {19}}}$يجب بالتأكيد إيجادها ضمن هذه الفترة. وبالتالي، باستخدام هذه الفترة، يمكن الانتقال إلى الخطوة التالية من الخوارزمية عن طريق حساب نقطة المنتصف للفترة، وتحديد ما إذا كان مربع نقطة المنتصف أكبر من أو أصغر من 19، وتحديد حدود الفترة التالية وفقًا لذلك قبل تكرار العملية.

$\begin{aligned}m_{1}=\dfrac{1+5}{2}=3&&\Rightarrow \;m_{1}^{2}=9\leq 19&&\Rightarrow \;I_{2}=[3,5]\\m_{2}=\dfrac{3+5}{2}=4&&\Rightarrow \;m_{2}^{2}=16\leq 19&&\Rightarrow \;I_{3}=[4,5]\\m_{3}=\dfrac{4+5}{2}=4.5&&\Rightarrow \;m_{3}^{2}=20.25>19&&\Rightarrow \;I_{4}=[4,4.5]\\m_{4}=\dfrac {4+4.5}{2}}=4.25&&\Rightarrow \;m_{4}^{2}=18.0625\leq 19&&\Rightarrow \;I_{5}=[4.25,4.5]\\m_{5}&={\dfrac {4.25+4.5}{2}}=4.375&&\Rightarrow \;m_{5}^{2}=19.140625>19&&\Rightarrow \;I_{5}=[4.25,4.375]\\&\vdots &&\end{aligned}}}$

في كل مرة يتم فيها حساب نقطة منتصف جديدة، يتم تحديد نطاق القيم الممكنة لـ${\displaystyle {\sqrt {19}}}$يمكن تضييق النطاق بحيث تقترب القيم المتبقية ضمن هذا النطاق أكثر فأكثر من القيمة الفعلية لـ${\displaystyle {\sqrt {19}}=4.35889894\dots }$أي أن كل تغيير متتالٍ في حدود الفترة التي تقع ضمنها ${\displaystyle {\sqrt {19}}}$يجب أن يكذب يسمح بقيمة${\displaystyle {\sqrt {19}}}$ليتم تقديرها بدقة أكبر، إما عن طريق زيادة الحدود الدنيا للفترة أو تقليل الحدود العليا للفترة.

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

تستخدم الطريقة البابلية خوارزمية أكثر كفاءة تُنتج تقريبات دقيقة لـ${\displaystyle {\sqrt {x}}}$لـ${\displaystyle x>0}$بل وأسرع. الوصف الحديث باستخدام الفترات المتداخلة مشابه للخوارزمية المذكورة أعلاه، ولكن بدلاً من استخدام سلسلة من نقاط المنتصف، يتم استخدام سلسلة${\displaystyle (c_{n})_{n\in \mathbb {N} }}$مقدم من

${\displaystyle c_{n+1}:={\frac {1}{2}}\cdot \left(c_{n}+{\frac {x}{c_{n}}}\right)}$.

ينتج عن ذلك سلسلة من الفترات الزمنية المعطاة بواسطة${\displaystyle I_{n+1}:=\left[{\frac {x}{c_{n}}},c_{n}\right]}$و${\displaystyle I_{1}=[0,k]}$، أين${\displaystyle k^{2}>x}$، سيوفر حدودًا عليا وسفلى دقيقة لـ${\displaystyle {\sqrt {x}}}$سريع جدًا. عمليًا، فقط${\displaystyle c_{n}}$يجب أخذ ذلك في الاعتبار، وهو ما يتقارب مع${\displaystyle {\sqrt {x}}}$(وكذلك الحال بالنسبة للحد الأدنى للفترة). هذه الخوارزمية هي حالة خاصة من طريقة نيوتن .

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

تقاطع كل تسلسل${\displaystyle (I_{n})_{n\in \mathbb {N} }}$ تحتوي الفترات المتداخلة على عدد حقيقي واحد فقط${\displaystyle x}$.

البرهان: يمكن التحقق من هذه العبارة بسهولة عن طريق التناقض. لنفترض وجود عددين مختلفين${\displaystyle x,y\in \cap _{n\in \mathbb {N} }I_{n}}$. من${\displaystyle x\neq y}$ويترتب على ذلك أنهم يختلفون بـ${\displaystyle |x-y|>0.}$بما أن كلا العددين يجب أن يكونا ضمن كل فترة، فإن ذلك يترتب عليه أن${\displaystyle |I_{n}|\geq |x-y|}$للجميع${\displaystyle n\in \mathbb {N} }$وهذا يتعارض مع الخاصية 2 من تعريف الفترات المتداخلة؛ لذلك، يمكن أن يحتوي التقاطع على عدد واحد على الأكثر${\displaystyle x}$تضمن بديهية الاكتمال أن هذا العدد الحقيقي${\displaystyle x}$موجود.${\displaystyle \;\square }$

• تُعد هذه البديهية أساسية بمعنى أن سلسلة من الفترات المتداخلة لا تحتوي بالضرورة على عدد نسبي - مما يعني أن${\displaystyle \cap _{n\in \mathbb {N} }I_{n}}$قد ينتج عنه${\displaystyle \emptyset }$، إذا أخذنا في الاعتبار الأسباب المنطقية فقط.
• تُكافئ هذه البديهية وجود الحد الأدنى والحد الأعلى (البرهان أدناه)، وتقارب متتابعات كوشي، ونظرية بولزانو-فايرشتراس . وهذا يعني أنه يجب تقديم إحدى هذه البديهيات الأربع بشكل بديهي، بينما يمكن إثبات البديهيات الثلاث الأخرى تباعًا.

لو${\displaystyle A\subset \mathbb {R} }$له حد أعلى، أي يوجد عدد${\displaystyle b}$بحيث${\displaystyle x\leq b}$للجميع${\displaystyle x\in A}$يمكن للمرء الاتصال بالرقم${\displaystyle s=\sup(A)}$أعلى​${\displaystyle A}$، لو

1. الرقم${\displaystyle s}$يمثل الحد الأعلى لـ${\displaystyle A}$، معنى${\displaystyle \forall x\in A:\;x\leq s}$
2. ${\displaystyle s}$هو الحد الأعلى الأدنى لـ${\displaystyle A}$، معنى${\displaystyle \forall \sigma <s:\;\exists x\in A:\;x>\sigma }$

رقم واحد فقط من هذا القبيل${\displaystyle s}$يمكن أن يوجد. وبالمثل، يمكن تعريف الحد الأدنى (${\displaystyle \inf(B)}$) من مجموعة${\displaystyle B\subset \mathbb {R} }$، أي أنها محدودة من الأسفل، باعتبارها الحد الأدنى الأكبر لتلك المجموعة.

كل مجموعة${\displaystyle A\subset \mathbb {R} }$له قيمة عليا (قيمة دنيا)، إذا كان محدودًا من الأعلى (من الأسفل).

البرهان: دون فقدان للعمومية، يمكن للمرء أن ينظر إلى مجموعة${\displaystyle A\subset \mathbb {R} }$والتي لها حد أعلى. يمكن الآن إنشاء متتالية${\displaystyle (I_{n})_{n\in \mathbb {N} }}$من الفترات المتداخلة${\displaystyle I_{n}=[a_{n},b_{n}]}$، والتي لها الخاصيتان التاليتان:

1. ${\displaystyle b_{n}}$يمثل الحد الأعلى لـ${\displaystyle A}$للجميع${\displaystyle n\in \mathbb {N} }$
2. ${\displaystyle a_{n}}$لا يمثل أبدًا حدًا أعلى لـ${\displaystyle A}$لأي${\displaystyle n\in \mathbb {N} }$.

يتبع البناء أسلوب التكرار بالبدء بأي رقم${\displaystyle a_{1}}$، وهذا ليس حدًا أعلى (مثلاً${\displaystyle a_{1}=c-1}$، أين ${\displaystyle c\in A}$وحد أعلى اعتباطي${\displaystyle b_{1}}$ل${\displaystyle A}$). منح${\displaystyle I_{n}=[a_{n},b_{n}]}$بالنسبة للبعض${\displaystyle n\in \mathbb {N} }$يمكن للمرء حساب نقطة المنتصف${\displaystyle m_{n}:={\frac {a_{n}+b_{n}}{2}}}$وحدد

${\displaystyle I_{n+1}:=\left\{{\begin{matrix}\left[a_{n},m_{n}\right]&&{\text{if}}\;m_{n}\;{\text{is an upper bound of}}\;A\\\left[m_{n},b_{n}\right]&&{\text{if}}\;m_{n}\;{\text{is not an upper bound}}\end{matrix}}\right.}$

لاحظ أن هذا التسلسل الفاصل محدد جيدًا، ومن الواضح أنه تسلسل من الفترات المتداخلة بحكم بنائه.

والآن لنبدأ${\displaystyle s}$ليكن العدد في كل فترة (الذي يضمن وجوده البديهية ) .${\displaystyle s}$يمثل الحد الأعلى لـ${\displaystyle A}$وإلا فهناك عدد${\displaystyle x\in A}$بحيث${\displaystyle x>s}$علاوة على ذلك، فإن هذا من شأنه أن يستلزم وجود فترة زمنية${\displaystyle I_{m}=[a_{m},b_{m}]}$مع${\displaystyle b_{m}-a_{m}<x-s}$، منها${\displaystyle b_{m}-s<x-s}$يتبع ذلك، بسبب${\displaystyle s}$كما أنه عنصر من${\displaystyle I_{m}}$لكن هذا يتناقض مع الخاصية الأولى للأعلى (بمعنى${\displaystyle b_{m}<s}$للجميع${\displaystyle m\in \mathbb {N} }$). لذلك${\displaystyle s}$في الواقع، يمثل هذا الحد الأعلى لـ${\displaystyle A}$.

افترض وجود حد أدنى وحد أعلى${\displaystyle \sigma <s}$ل${\displaystyle A}$. منذ${\displaystyle (I_{n})_{n\in \mathbb {N} }}$إذا كانت سلسلة من الفترات المتداخلة، فإن أطوال الفترات تصبح صغيرة بشكل تعسفي؛ على وجه الخصوص، توجد فترة طولها أصغر من${\displaystyle s-\sigma }$لكن من${\displaystyle s\in I_{n}}$يحصل المرء${\displaystyle s-a_{n}<s-\sigma }$وبالتالي${\displaystyle a_{n}>\sigma }$باتباع قواعد هذا البناء،${\displaystyle a_{n}}$سيكون هذا حدًا أعلى لـ${\displaystyle A}$، وهو ما يتناقض مع الخاصية 2 لجميع تسلسلات الفترات المتداخلة.

في خطوتين، تم إثبات أن${\displaystyle s}$يمثل الحد الأعلى لـ${\displaystyle A}$وأنه لا يمكن أن يوجد حد أدنى وحد أعلى. لذلك${\displaystyle s}$هو أعلى مستوى لـ${\displaystyle A}$بحسب التعريف.

كما تبين، فإن وجود القيم العليا والدنيا للمجموعات المحدودة هو نتيجة لاكتمال${\displaystyle \mathbb {R} }$في الواقع، الاثنان متكافئان، مما يعني أنه يمكن إدخال أي منهما بشكل بديهي.

البرهان: ليكن${\displaystyle (I_{n})_{n\in \mathbb {N} }}$مع${\displaystyle I_{n}=[a_{n},b_{n}]}$لتكن سلسلة من الفترات المتداخلة. إذن المجموعة${\displaystyle A:=\{a_{1},a_{2},\dots \}}$محصور من الأعلى، حيث كل${\displaystyle b_{n}}$يمثل حدًا أعلى. وهذا يعني أن الحد الأعلى الأدنى${\displaystyle s=\sup(A)}$يفي${\displaystyle a_{n}\leq s\leq b_{n}}$للجميع${\displaystyle n\in \mathbb {N} }$. لذلك${\displaystyle s\in I_{n}}$للجميع${\displaystyle n\in \mathbb {N} }$، على التوالى${\displaystyle s\in \cap _{n\in \mathbb {N} }I_{n}}$.