Трисекция угла

[mihaild]

mustang в сообщении #1334126 писал(а):

И куда в эту простоту воткнуть циркуль и линейку?

Ну как куда. У нас в каждый момент угол разбит на три части - то, что будет в конечной доле (для простоты считаем что это "правая" часть), то, чего не будет ("левая") и "рабочая область". Изначально весь угол является "рабочей областью". Дальше идем по двоичным цифрам, бьем рабочую область на две части. Если очередная цифра - $1$, то добавляем "правую половину" рабочей области к "правой" части, а новой "рабочей областью" становится левая половина. Если очередная цифра - $0$, то добавляем "левую половину" рабочей области к "левой" части, а новой "рабочей областью" становится правая половина.
Таким образом на каждом шаге нужный нам угол лежит где-то между "правая часть" и "правая часть"+"рабочая область". Т.к. градусная мера рабочей области после $k$ шагов равна $2^{-k}$ меры исходного угла - то относительная погрешность после $k$ шагов не превосходит $2^{-k}$ (относительно нашего ответа, не относительно правильного).

Построения тут получаются те же, что и у вас, но не надо ничего думать про ряды, достаточно посмотреть, как нужная нам доля записывается в двоичной системе исчисления.

[mustang]

grizzly в сообщении #1334104 писал(а):

mustang в сообщении #1334079 писал(а):

Я так понимаю, что в смысле конструктивной математики задача трисекции произвольного угла с помощью циркуля и линейки считается, таким образом, решённой.

Нет. Считается решённой задача приближённой трисекции угла. Вот только Вы её решили слишком уж трудоёмким способом. За то же количество операций какой-нибудь конкретный угол (80--100 градусов, для примера, чтобы не совсем маленький) можно разделить на три части с точностью на 2-3 порядка лучше Вашей (которую Вы не плохо посчитали). Ну или около того. Это если недолго думать. Я не удивлюсь, если кто-то придумает алгоритм ещё на несколько порядков точнее.

Я на другое обращаю внимание: алгоритм позволяет разделить на три части любой угол с любой наперёд заданной точностью за конечное число шагов.

Многие доказательства существования в математике имеют ровно такую же структуру: $\forall \varepsilon >0 \; \exists \alpha: \forall b>\alpha \; |F(b)-F(b^*)| < \varepsilon$, где $b^*$ - точное решение

[mihaild]

mustang в сообщении #1334134 писал(а):

Я на другое обращаю внимание: алгоритм позволяет разделить на три части любой угол с любой наперёд заданной точностью за конечное число шагов.

Только причем тут "конструктивная математика"? Что вообще понимается под "решением задачи на построение в смысле конструктивной математики"?

mustang в сообщении #1334134 писал(а):

Многие доказательства существования в математике имеют ровно такую же структуру: $\forall \varepsilon >0 \; \exists \alpha: \forall b>\alpha \; |F(b)-F(b^*)| < \varepsilon$, где $b^*$ - точное решение

Нет, доказательства не имеют такую структуру. Доказательство - это последовательность утверждений.

[mustang]

mihaild в сообщении #1334133 писал(а):

mustang в сообщении #1334126 писал(а):

И куда в эту простоту воткнуть циркуль и линейку?

Ну как куда. У нас в каждый момент угол разбит на три части - то, что будет в конечной доле (для простоты считаем что это "правая" часть), то, чего не будет ("левая") и "рабочая область". Изначально весь угол является "рабочей областью". Дальше идем по двоичным цифрам, бьем рабочую область на две части. Если очередная цифра - $1$, то добавляем "правую половину" рабочей области к "правой" части, а новой "рабочей областью" становится левая половина. Если очередная цифра - $0$, то добавляем "левую половину" рабочей области к "левой" части, а новой "рабочей областью" становится правая половина.
Таким образом на каждом шаге нужный нам угол лежит где-то между "правая часть" и "правая часть"+"рабочая область". Т.к. градусная мера рабочей области после $k$ шагов равна $2^{-k}$ меры исходного угла - то относительная погрешность после $k$ шагов не превосходит $2^{-k}$ (относительно нашего ответа, не относительно правильного).

Построения тут получаются те же, что и у вас, но не надо ничего думать про ряды, достаточно посмотреть, как нужная нам доля записывается в двоичной системе исчисления.

Четверть века назад про двоичную систему исчисления я ничего не знал, а про сумму половинок из апории Зенона уже слышал .

В принципе, можно делить угол на любое количество углов, точнее, отсекать от угла нужную долю.

Просто $\frac{1}{3}$ щекочет воображение . Да и алгоритм крайне простой для запоминания.

-- 23.08.2018, 17:42 --

mihaild в сообщении #1334136 писал(а):

Нет, доказательства не имеют такую структуру. Доказательство - это последовательность утверждений.

Ну так утверждения и написаны, что для любой наперёд заданной погрешности найдется такое конечное количество шагов алгоритма, что выполнив это или большее число шагов, полученный результат будет отличаться от истинного меньше, чем заданная погрешность.

mustang в сообщении #1334138 писал(а):

Только причем тут "конструктивная математика"? Что вообще понимается под "решением задачи на построение в смысле конструктивной математики"?

Могу, конечно, манкировать терминологией, за давностью лет. Возможно, неаккуратно распространяю термин "конструктивное доказательство", когда доказательство существования решения доказывается предъявлением (построением) решения.
Т.е. мы можем доказать существование двух корней у квадратного уравнения (основная теорема алгебры, если мне склероз не изменяет, частный случай), а можем написать известную школьную формулу.

Как можно убедиться, что предложенное является решением? Оно даёт сколь угодно малую ошибку.

[mustang]

Pphantom в сообщении #1334130 писал(а):

mustang в сообщении #1334126 писал(а):

И куда в эту простоту воткнуть циркуль и линейку?

Поскольку любой угол можно поделить пополам, многократное проведение такой процедуры позволит разделить его на $2^n$ частей, из которых требуемая треть угла набирается с любой заранее заданной точностью. Схема набора - это двоичное представление $1/3$, которое Евгений Машеров и написал. Т.е. берем четверть угла плюс шестнадцатую часть плюс $1/64$ часть плюс... и так пока не надоест требуемая точность не будет достигнута.

Ну да. Только не проще. В смысле количества построений.

Плюс разбиение угла на $2^n$ частей означает нехорошую зависимость сложности (количества элементарных операций с циркулем и линейкой) от задаваемой точности.

[mihaild]

mustang в сообщении #1334138 писал(а):

Ну так утверждения и написаны, что для любой наперёд заданной погрешности найдется такое конечное количество шагов алгоритма, что выполнив это или большее число шагов, полученный результат будет отличаться от истинного меньше, чем заданная погрешность.

Утверждение. А доказательство - это вывод утверждения из аксиом (или из уже доказанных утверждений). Не надо путать утверждения и их доказательства.

mustang в сообщении #1334138 писал(а):

Как можно убедиться, что предложенное является решением? Оно даёт сколь угодно малую ошибку.

Ну вы для любой точности предъявили построение, обеспечивающее эту точность. К точному построению это отношения не имеет.

Вообще, существование сколь угодно точного решения и точного решения - две большие разницы. Например, $\pI$ можно сколь угодно точно приблизить рациональными числами. А вот точно - нельзя.

mustang в сообщении #1334144 писал(а):

Плюс разбиение угла на $2^n$ частей означает нехорошую зависимость сложности (количества элементарных операций с циркулем и линейкой) от задаваемой точности.

Ну тут надо посмотреть внимательнее и увидеть, что не обязательно разбивать угол на $2^n$ частей, достаточно разбить на $2$, потом половину еще на $2$ и т.д. (всего $n$ разбиений) и потом из некоторых из получившихся частей составить угол. Число операций получается линейно по $n$.

[Pphantom]

mustang в сообщении #1334144 писал(а):

Плюс разбиение угла на $2^n$ частей означает нехорошую зависимость сложности (количества элементарных операций с циркулем и линейкой) от задаваемой точности.

Она как раз вполне хорошая - добавка каждых двух двоичных порядков требует совершения фиксированного количества действий, т.е. сложность логарифмическая. Вам же в действительности не надо делить пополам все очередные углы, достаточно проделывать это только с одним.

[grizzly]

Pphantom в сообщении #1334191 писал(а):

т.е. сложность логарифмическая.

А какую сложность будет давать последовательное применение алгоритма от Евгений Машеров? Там мы можем после каждого цикла откладывать трижды полученное приближение и далее работать с разницей между данным углом и утроением приближённого. Цена одного цикла фиксированная, что-то около 15 элементарных действий. Зато после второго цикла из 15 действий точность будет уже больше 10 знаков после запятой. А дальше ещё быстрее.

Деление пополам нам такого бонуса дать не может.

[Pphantom]

grizzly в сообщении #1334224 писал(а):

Деление пополам нам такого бонуса дать не может.

Конечно. Это скорее иллюстрация, что асимптотическая сложность даже совсем простого алгоритма оказывается вполне приличной (а для практических целей его вообще за глаза достаточно).

[grizzly]

Википедия мне напомнила про известный старый метод построения -- невсис (я решил, что в этой теме будет уместно о нём вспомнить). Там цикл всего 5 элементарых шагов, и хотя точность на каждом цикле растёт чуть медленнее, чем при делении хорды на 3, но при том же количестве операций невсис будет намного выгоднее.

[Pphantom]

grizzly в сообщении #1334287 писал(а):

Википедия мне напомнила про известный старый метод построения -- невсис (я решил, что в этой теме будет уместно о нём вспомнить).

Уже вспомнили: post1334021.html#p1334021

[grizzly]

Pphantom в сообщении #1334290 писал(а):

Уже вспомнили:

Проморгал :) Но я имел в виду небольшую его модификацию -- так чтобы он стал не совсем точным но совсем честным: откладываем нужное расстояние не от точки на окружности, а на продолжении стороны угла от точки пересечения с окружностью.

[ozheredov]

Munin в сообщении #1334057 писал(а):

Так и называется "трисектор".

Я подумал что это принципиальная схема перчатки Фредди Крюгера )

[Soul Friend]

grizzly в сообщении #1334296 писал(а):

так чтобы он стал не совсем точным но совсем честным: откладываем
нужное расстояние не от точки на окружности, а на продолжении стороны
угла от точки пересечения с окружностью

Вот честный, приближённый метод без невсиса:

зелёная линия - биссектриса.
Тупой угол сперва нужно разделить на четверть, и уже эту четверть этим методом разделить на три части, а после получившийся угол умножить на четыре. Думаю, так точнее будет.

[grizzly]

Soul Friend в сообщении #1334488 писал(а):

Думаю, так точнее будет.

За такое количество операций я бы попробовал сделать в 1000 раз точнее. Или даже в миллион (лень проверять).