Лема про вкладені відрізки

Лема про вкладені відрізки, або принцип вкладених відрізків Коші — Кантора, або принцип неперервності Кантора — фундаментальне твердження у математичному аналізі, яке стверджує, що будь-яка послідовність вкладених відрізків на дійсній прямій, довжина яких прямує до нуля, має єдину спільну точку.

Мотивація

Обчислення квадратних коренів

Намагаючись знайти квадратний корінь з числа $x>1$, можна бути впевненим, що $1\leqslant {\sqrt {x}}\leqslant x$, це дає перший відрізок $I_{0}=[1,x]$, у якому потрібно знайти ${\sqrt {x}}$. Якщо знайти наступне більше повне квадратне число $k^{2}>x$, то можна отримати такий наступний відрізок: $I_{1}=[1,k]$.

Інші відрізки $I_{n}=[a_{n},b_{n}],n\in \mathbb {N}$ тепер можна визначити рекурсивно, використовуючи послідовність середніх точок $m_{n}={\frac {a_{n}+b_{n}}{2}}$. Враховуючи, що відрізок $I_{n}$ вже відомий (починаючи з $I_{1}$), можна визначити наступний:

$I_{n+1}:=\left\{{\begin{matrix}\left[m_{n},b_{n}\right]&{\text{якщо}}\;\;m_{n}^{2}\leqslant x\\\left[a_{n},m_{n}\right]&{\text{якщо}}\;\;m_{n}^{2}>x\end{matrix}}\right.$

Тобто порівнюємо середину відрізка $I_{n}$ з ${\sqrt {x}}$, щоб визначити, чи є вона меншою чи більшою за ${\sqrt {x}}$. Якщо середина менша, то її встановлюємо як лівий кінець наступного відрізка $I_{n+1}$, а якщо середина більша, то встановити її як правий кінець наступного відрізка. Це гарантує, що ${\sqrt {x}}\in I_{n+1}$. У цій конструкції відрізки вкладені, а їх довжина $|I_{n}|$ зменшується вдвічі на кожному кроці рекурсії. Таким чином, можна отримати нижню та верхню оцінки для ${\sqrt {x}}$ з як завгодно хорошою точністю (за умови достатнього часу обчислень).

Можна також обчислити ${\sqrt {y}}$, при $0<y<1$. У цьому випадку $1/y>1$, і алгоритм можна використати, поклавши $x:=1/y$ і обчисливши зворотне значення після досягнення бажаного рівня точності.

Приклад

Щоб продемонструвати цей алгоритм, розглянемо приклад того, як його можна використати, щоб знайти значення ${\sqrt {19}}$. Оскільки $1^{2}<19<5^{2}$, то перший відрізок для алгоритму можна визначити як $I_{1}:=[1,5]$. Таким чином, використовуючи цей відрізок, можна перейти до наступного кроку алгоритму, обчисливши його середину, визначивши, чи квадрат знайденої середини більший або менший за 19, і встановивши відповідно кінці наступного відрізка, потім повторити процес:

${\begin{aligned}m_{1}&={\dfrac {1+5}{2}}=3&&\Rightarrow \;m_{1}^{2}=9\leqslant 19&&\Rightarrow \;I_{2}=[3,5]\\m_{2}&={\dfrac {3+5}{2}}=4&&\Rightarrow \;m_{2}^{2}=16\leqslant 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\leqslant 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}}$

Кожного разу, коли обчислюється нова середня точка, діапазон можливих значень для ${\sqrt {19}}$ зменшується, значення, які залишаються в межах відрізка, стають все ближчими до фактичного значення ${\sqrt {19}}=4.35889894\dots$. Тобто кожна послідовна зміна в кінцях відрізка, в якому знаходитися ${\sqrt {19}}$, дозволяє оцінити значення ${\sqrt {19}}$ з більшою точність — або через збільшення лівого кінця відрізка, або через зменшення правого кінця відрізка.

Цю процедуру можна повторювати стільки разів, скільки необхідно для досягнення бажаного рівня точності. Теоретично, повторюючи кроки необмежено, можна прийти до справжнього значення цього квадратного кореня.

Метод Герона

Вавилонський метод використовує більш ефективний алгоритм, який швидше наближається до значення ${\sqrt {x}}$. Сучасний опис із використанням вкладених відрізків схожий на наведений вище алгоритм, але замість послідовності середніх точок використовується послідовність $\{c_{n}\}_{n\in \mathbb {N} }$, задана наступним чином:

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

Це призводить до послідовності відрізків $I_{n+1}:=\left[{\frac {x}{c_{n}}},c_{n}\right]$, де $I_{1}=[0,k]$ і $k^{2}>x$, які швидко забезпечуюють гарні верхні та нижні оцінки для ${\sqrt {x}}$. На практиці потрібно обчислювати лише $c_{n}$, що збігається до ${\sqrt {x}}$. Цей алгоритм є окремим випадком методу Ньютона.

Обчислення числа π

π можна оцінити шляхом обчислення периметрів описаного та вписаного багатокутників.

Як показано на зображенні, коло можна наближати за допомогою вписаних і описаних правильних многокутників. Довжина кола діаметра $1$ дорівнює числу $\pi$ за визначенням цього числа.

Близько 250 р. до н.е. Архімед із Сіракуз почав з правильних шестикутників, чиї довжини сторін можна безпосередньо обчислити через діаметр кола. Крім того, можна знайти спосіб обчислення довжини сторони правильного $2n$-кутника з попереднього $n$-кутника, починаючи з правильного шестикутника. Послідовно подвоюючи кількість ребер до 96-кутників, Архімед досяг оцінки ${\tfrac {223}{71}}<\pi <{\tfrac {22}{7}}$. Верхня оцінка $22/7\approx 3.143$ досі часто використовується як грубе, але прагматичне наближення числа $\pi$.

Приблизно в 1600 році нашої ери метод Архімеда все ще був основним методом обчислення числа π. Цей метод насправді не дуже швидко збігається — Голландському математику Людольфу ван Цейлену для обчислення більш ніж тридцяти цифр числа π після коми знадобилося десятиліття. Незабаром були знайдені більш потужні методи обчислення.

Інші реалізації

Ранні випадки використання послідовностей вкладених відрізків (їх можна описати за допомогою сучасної математики) можна знайти в попередниках диференціального та інтегрального числення. В інформатиці послідовності вкладених відрізків використовуються в алгоритмах чисельних обчислень. На відміну від математичних нескінченних послідовностей, застосовуваний обчислювальний алгоритм завершується в певний момент, коли шукане число було знайдене або достатньо добре наближене.

Формулювання

Нехай $\{[a_{n},b_{n}]\mid n\geqslant 1\}$ — послідовність відрізків, для яких виконуються наступні умови:

1) $\forall n\geqslant 1\,[a_{n+1},b_{n+1}]\subseteq [a_{n},b_{n}]$,

2) $\forall \varepsilon >0$ існує $n\in \mathbb {N}$ таке, що $b_{n}-a_{n}<\varepsilon$.

Тоді існує єдина точка $x\in \mathbb {R}$ така, що для будь-якого $n\in \mathbb {N}$ буде $x\in [a_{n},b_{n}]$, тобто

$\bigcap \limits _{n=1}^{\infty }[a_{n},b_{n}]=\{x\}$.

Зауваження

Відрізки у формулюванні теореми не можна замінити на відкриті інтервали або напівінтервали. Наприклад,

$\bigcap \limits _{n=1}^{\infty }\left(0,{\frac {1}{n}}\right)=\varnothing$

$\bigcap \limits _{n=1}^{\infty }\left(0,{\frac {1}{n}}\right]=\varnothing$

$\bigcap \limits _{n=1}^{\infty }\left[-{\frac {1}{n}},0\right)=\varnothing$

Доведення

Існування спільної точки. Оскільки

$[a,b]\subseteq [c,d]\,\Leftrightarrow \,c\leqslant a\leqslant b\leqslant d$,

то за умовою 1)

$\forall n\geqslant 1\,a_{1}\leqslant a_{2}\leqslant \dots \leqslant a_{n}<b_{n}\leqslant b_{n-1}\leqslant \dots \leqslant b_{1}$.

Розглянемо множину $A:=\{a_{1},\dots ,a_{n},\dots \}$ і доведемо, що при будь-якому $m\in \mathbb {N}$ число $b_{m}$ є верхнею межею множини $A$. Дійсно, якщо $n\leqslant m$, то за умовою 1)

$[a_{m},b_{m}]\subseteq [a_{n},b_{n}]\,\Leftrightarrow \,a_{n}\leqslant a_{m}<b_{m}\leqslant b_{n}$, звідки $a_{n}<b_{m}$.

Якщо ж $n>m$, то за цією умовою

$[a_{n},b_{n}]\subseteq [a_{m},b_{m}]\,\Leftrightarrow \,a_{m}\leqslant a_{n}<b_{n}\leqslant b_{m}$ і знову $a_{n}<b_{m}$.

За теоремою про існування точної верхньої межі

$\exists x\in \mathbb {R} :\,x=\sup A$,

причому згідно з означенням точної верхньої межі $\forall n\in \mathbb {N} \,a_{n}\leqslant x$ і $\forall m\in \mathbb {N} \,x\leqslant b_{m}$. Тому для довільного $n\in \mathbb {N} \,x\in [a_{n},b_{n}]$.

Єдиність спільної точки. Припустимо, що існує $y\in \mathbb {R}$ таке, що $\forall n\in \mathbb {N} \,y\in [a_{n},b_{n}]$. Не втрачаючи загальності, припустимо, що $y\geqslant x$. Тоді з умови 2) виливає, що

$\forall \varepsilon >0\,\exists n\in \mathbb {N} :\,0\leqslant y-x\leqslant b_{n}-a_{n}<\varepsilon$,

тобто $\forall \varepsilon >0$ буде $0\leqslant y-x<\varepsilon$, звідси $y=x$ (якщо $y>x$, то досить узяти $\varepsilon :={\frac {1}{2}}(y-x)$, щоб отримати суперечність), що завершує доведення леми.

Зауваження. Якщо з формулювання леми вилучити умову 2), то, повторюючи міркування з доведення існування спільної точки, отримаємо, що існує принаймні одна спільна точка, яка не обов'язково єдина.

Див. також

• Бісекція
• Метод бісекції
• Теорема Кантора про перетини

Література

• Дороговцев А. Я. Математичний аналіз. Частина 1. — К. : Либідь, 1993. — 320 с. — ISBN 5-325-00380-1.(укр.)
• Зорич В. А. Математический анализ. — 10-е. — М : МЦНМО, 2019. — Т. 1. — 564 с. — ISBN 978-5-4439-4029-8.(рос.)
• Григорій Михайлович Фіхтенгольц. Курс диференціального та інтегрального числення. — 2023. — 1900+ с.(укр.)