入れ子になった区間

このアルゴリズムを実証するために、次の値を求めるためにどのように使用できるかの例を示します。$\displaystyle {\sqrt {19}}}$。注意：${\displaystyle 1^{2}<19<5^{2}}$アルゴリズムの最初の区間は次のように定義できます。${\displaystyle I_{1}:=[1,5]}$、 以来$\displaystyle {\sqrt {19}}}$この区間内に必ず存在するはずです。したがって、この区間を利用して、区間の中点を計算し、中点の二乗が19より大きいか小さいかを判定し、それに応じて次の区間の境界を設定してから、このプロセスを繰り返すことで、アルゴリズムの次のステップに進むことができます。

${\displaystyle {\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}}}$（もちろん、下限区間も同様です。）このアルゴリズムはニュートン法の特殊なケースです。

なお、上記2つの性質を満たすこのような区間列を、縮小する入れ子区間と呼ぶ著者もいます。この場合、入れ子区間の列とは、性質1のみを満たす列を指します。

各シーケンスの交点${\displaystyle (I_{n})_{n\in \mathbb {N} }}$ 入れ子になった区間には、ちょうど１つの実数が含まれる${\displaystyle x}$。

証明：この命題は背理法によって容易に検証できる。2つの異なる数が存在すると仮定する。${\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と矛盾する。したがって、交差部分には最大で1つの数しか含まれない。${\displaystyle x}$完全性公理は、そのような実数が${\displaystyle x}$存在する。${\displaystyle \;\square }$

• この公理は、入れ子になった区間の列が必ずしも有理数を含むとは限らないという意味で基本的である。つまり、${\displaystyle \cap _{n\in \mathbb {N} }I_{n}}$収穫できる${\displaystyle \emptyset }$合理的な観点だけを考慮した場合。
• この公理は、下限と上限の存在（証明は後述）、コーシー列の収束、およびボルツァーノ＝ワイエルシュトラスの定理と同等である。つまり、これら4つのうち1つは公理的に導入する必要があり、残りの3つは順次証明できるということである。

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

そのような数字は1つだけ${\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}]}$次のような2つの特性を持つ。

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}}$しかし、これは至高の性質 1 (つまり、${\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}}$1つ手に入れる${\displaystyle s-a_{n}<s-\sigma }$そのため${\displaystyle a_{n}>\sigma }$この構築規則に従って、${\displaystyle a_{n}}$上限値となる必要がある${\displaystyle A}$これは、入れ子になった区間のすべてのシーケンスの性質2に矛盾する。

2つのステップで、${\displaystyle s}$は上限です${\displaystyle A}$そして下限と上限は存在し得ない。したがって${\displaystyle s}$は最高位である${\displaystyle A}$定義上。

既に述べたように、有界集合の上限と下限の存在は、完全性の結果である。${\displaystyle \mathbb {R} }$実際には、この2つは等価であり、つまり、どちらを公理的に導入しても構わないということである。

証明:${\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}}$。