Вот любопытная задача (я уже знаю решение, потом напишу, если никто не решит). Дано число с плавающей точкой. Пусть для определенности это будет компьютерный "double float" - примерно 16 десятичных цифр. Не большое и не маленькое (пусть будет от 0.01 до 100). Известно, что оно было получено делением одного целого на другое целое - . Нужен алгоритм, чтобы найти a и b - что-то более быстрое, чем просто перебор. Понятно, что при больших a и b не найти (насколько больших?), т.к. точность представления числа не позволит различить разные варианты.
Пример: Число иррациональное, т.е. не равно отношению каких-то целых. Но его можно приблизить рациональным. Так оценивает сверху, причем с очень высокой точностью () для таких маленьких a и b. Вот тоже вопрос - это просто случайность или есть для этого какая-то причина?
Цепная дробь? [math]\pi=3+1/(7+1/(16+...)) [math]\frac{355}{113}=3+1/(7+1/16) Есть такая красивая теорема, почему получаемое таким образом приближение лучше не только среди приближений со знаменателем не большим этого (в данном случае 113), но и среди приближений (с той же стороны,т.е. сверху или снизу) со знаменателем не больше знаменателя следующей подходящей дроби.Основывается на равенстве [math]p_{n-1}q_n-p_nq_{n-1}=(-1)^n, которое, оказывается, выполняется для всех соседних подходящих дробей [math]\frac {p_{n-1}}{q_{n-1}},\frac{p_n}{q_n}. У нулевого приближения [math]q_0=1,p_0=[\pi] и оно снизу.Следующее -сверху, и вообще все нечетные сверху значит, приближаемое число (в общем случае [math]\alpha) лежит между соседними подходящими дробями и точность приближения [math]|\alpha-\frac{p_{n-1}}{q_{n-1}}|\leq \frac 1{q_{n-1}q_n} Значит, Вам надо найти подходящие дроби со знаменателем не больше [math]10^8 и взять первую из них, которая обеспечивает требуемую точность [math]10^{-16}(последняя точно обеспечивает. Но могут быть и раньше. все они годятся как ответы к Вашей задаче.)
Верно! Цепные дроби - давно известный метод поиска приближений для иррациональных чисел в виде рационального числа. Алгоритм простой, разделяем число на целую часть (это будет очередное значение) и дробную часть. Дробную часть возводим в минус первую степень и к результату (который будет больше 1) применяем ту же процедуру, и т.д.. Если число было рациональным, то этот процесс когда-то оборвется - мы получим нулевую дробную часть на каком-то шаге. Так что этот алгоритм позволяет решить нашу задачу - как восстановить целые a и b, если только известно в форме числа с плавающей точкой. В этом случае, на каком-то шаге остаток резко окажется очень маленьким - порядка машинной точности. Но что если исходное число имело гораздо большую ошибку, чем машинная точность? Мы конечно можем посмотреть на ошибку приближения исходного числа нашей дробью, но эта ошибка в любом случае будет уменьшатся. Как было выше замечено, при приближениии дробью произвольного числа можно ожидать ошибку порядка . Значит можно ввести качество приближения в виде . Эта мера будет меньше 1 по абсолютной величине, но обычно ненамного меньше (может 0.5, может 0.1). Но если мера качества оказалась много меньше 1, то это индикатор того, что исходное число могло бы быть представлением этого рационального числа с ошибкой.
Я вспомнил про эту задачу при решении другой задачи с математической регаты. Точный ответ там , но Монтекарло даёт неточные значения в виде чисел с плавающей точкой. Можно ли по ним найти это ? Во первых, я написал Matlab код, который разлагает число в цепную дробь:
## Continued fraction function r = cont_frac(x, n) v = [floor(x)]; t = x; for k=2:n t = 1 / (t - v(k-1)); v(k) = floor(t);
a = 0; b = 1; for k1=k:-1:1 c = a + v(k1) * b; a = b; b = c; g = gcd(a, b); a = a / g; b = b / g; endfor err = b/a-x; printf('%d/%d, err=%g, tol=%g\n', b, a, err, err*a*a); endfor r = v; endfunction
Тут мы делаем несколько шагов и на каждом шаге печатаем саму дробь, ошибку приближения исходного числа этой дробью и качество этого приближения. Например Монтекарло дал три числа после итераций: 2.6639, 2.6712, 2.6597 Применим к ним эту функцию:
Тут мы видим, что все три раза возникает дробь , причем она имеет неплохую меру качества . Отсюда возникает оправданная гипотеза, что Монтекарло даёт приближения к точному значению .
Последний раз редактировалось zykov 23 июл 2020, 15:59, всего редактировалось 6 раз.
Отсюда видно, что дробь имеет аномально высокое качество , что гораздо меньше 1. Вот загадка - это просто случайность или для этого есть какая-то причина? Тут же есть ещё пара дробей с качеством похуже, но тоже неплохим (): и . Итересно, почему? Все три дают оценку сверху. Может дело в правильных описанных многоугольниках... Попробовал посмотреть правильный 710-угольник. Действительно хорошо приближается дробью , но всё же гораздо хуже чем приближается той же дробью (где-то на два порядка хуже).
Вот идея, если бы имело бы разложение в ряд начинающийся как , то это объясняло бы. Тут есть надежда, глядя на уже имеющиеся ряды для - Rapidly convergent series. Наверно есть целое семейство таких рядов. У этих двух рядов только первое слагаемое даёт ошибку и соответственно. У нас же два слагаемых (или одно, если их обратно объединить) даёт ошибку , так что может есть ряд чуть похуже тех двух, но дающий в начале .
Последний раз редактировалось zykov 23 июл 2020, 23:56, всего редактировалось 1 раз.
zykov писал(а):Как было выше замечено, при приближениии дробью произвольного числа можно ожидать ошибку порядка . Значит можно ввести качество приближения в виде . Эта мера будет меньше 1 по абсолютной величине...
Самое плохо приближаемое в этом смысле [math]\varphi =\frac {\sqrt 5+1}2=1+\frac 1{\varphi} и там не меньше 1 а как раз [math]\varphi Для рациональных х как уже сказано обратится в 0 Для алгебраических (корней какого-нибудь полинома с целыми коэффициентами) стремится к конечному пределу, отличному от 0 Для остальных (трансцедентных) стремится к 0, причем степенным образом, как [math]b^{-\varepsilon}(не все?). Это даже используется при доказательстве трансцедентности. В этом смысле трансцедентные промежуточные между алгебраическими и рациональными, а не наоборот. Сравните http://oeis.org/A001203
Последний раз редактировалось Ian 24 июл 2020, 06:08, всего редактировалось 1 раз.
Ian писал(а):Source of the post В этом смысле трансцедентные промежуточные между алгебраическими и рациональными, а не наоборот.
Это не совсем верно. Рациональное число приближается идеально только самим собой (дроби приводятся к несократимому виду). Если же попробовать приблизить рациональное число другими рациональными, то ошибка будет ещё хуже чем для алгебраических. Для алгебраических это , а для рациональных . Так что в этом смысле алгебраические лежат между рациональными и трансцендентными.
Пусть мы хотим приблизить числом , так что и . Тогда ошибка будет . Так как , то не менее 1 по абсолютной величине. Значит .
Вот ещё можно посмотреть, как плотно идут рациональные числа с ограниченным знаменателем. Возьмем некоторое и возмём все несократимые дроби , такие что . Наши числа будут в интервале от 0 до 1, но в дургих интервалах, например от 1 до 2 всё тоже самое - просто к нужно прибавить , что не изменит интервалы между числами. Отсортируем эти числа в порядке возрастания и посмотрим на интервалы между соседними. Вот график для , интервал умножен на :
linear
rational.png (60.74 KiB) 25837 просмотра
Видно, что максимальные пики размером 300 рядом с 0 и 1. Действительно в интервалах от до и от до нет других рациональных с ограниченным знаменателем. Потом есть большой пик около 1/2, далее пики около 1/3, 2/3, 1/4, 3/4 и т.д., что соответствует плохому приближению рациональных рациональными. Но подавляющий процент интервалов (где-то около 90%) имеют маленькую величину - менее . Самый маленький интервал лежит от до и имеет величину (между и такой же), т.е. имеет качество , что чуть больше 1. Вот тот же график в логарифмическом масштабе для интервалов:
log
rational_log.png (111.02 KiB) 25837 просмотра
Вобщем если выбирать произвольно для приближения какого-нибудь числа, то скорее всего качество будет около 1, типично до 2-3. Может подскакивать и до , если не повезло. Но алгоритм цепных дробей выбирает "хорошие" , так что качество гарантировано менее 1, а типично - 0.1-0.7.
Всего отрезков 27398 при (наверно можно комбинаторно найти количество несократимых дробей, скорее всего через последовательность простых чисел), так что среднее от длины отрезков . Медиана по этому набору отрезков . Хвост из высоких пиков подтягивает среднее вверх. При среднее будет , медиана будет .
Средняя ошибка приближения - это от средней длины отрезка.
zykov писал(а):Source of the post (наверно можно комбинаторно найти количество несократимых дробей, скорее всего через последовательность простых чисел)
Вероятность того, что любые случайным образом выбранных положительных целых чисел будут взаимно просты, равна , в том смысле, что при вероятность того, что положительных целых чисел, меньших, чем (и выбранных случайным образом), будут взаимно простыми, стремится к . Здесь — это дзета-функция Римана.
Так что видимо "среднее " стремится к . Т.е. среднее качество будет .
Получется, что "почти все числа алгебраические". Рациональных мало - их вообще счётное количество. А трансцендентных тоже получается "меньше" чем алгебраических в вероятностном смысле, т.к. трансцендентные "прижаты" к рациональным.
zykov писал(а):Получется, что "почти все числа алгебраические". Рациональных мало - их вообще счётное количество. А трансцендентных тоже получается "меньше" чем алгебраических в вероятностном смысле, т.к. трансцендентные "прижаты" к рациональным.
Алгебраических чисел тоже счетное множество и поэтому мера 0. Полную меру имеют трансцедентные.
Да, действительно. Количество многочленов с целочисленными коэффициентами ограниченной степени и с ограниченными коэффициентами конечно, у каждого такого многочлена конечное количество корней. Так что все корни таких многочленов можно пронумеровать постепенно увеличивая ограничение степени и ограничение коэффициентов.
Отсюда следует, что точность стремится к 0 почти всюду при [math]B\to\infty, а именно во всех трансцедентных точках, и в них ограничена сверху. По теореме Лебега о предельном переходе под знаком интеграла. интеграл (матожидание) тоже стремится к 0. А у Вас? И мне особенно интересно, как это матожидание стремится к 0. Как [math]\frac 1{\ln B}? [math]\frac 1{\ln \ln B}?
Матожидание качества стремится к при . Это факт. Это если для каждого считаем матожидание (например по ) и потом берем предел этого матожидания. Если сделать по-другому - для каждого найти предел качества и потом взять матожидание, то видимо ноль получится (т.к. этот предел ненулевой только для алгебраических точек).
Понял, тут недопонимание. Если для каждого мы ищем приближение с минимальной ошибкой, то качество (ошибка умноженная на ) для трансцендентных не стремится к нулю. Пример - цепная дробь для . Иногда возникают приближения с высоким качеством, но все другие имеют качество . Так что и матожидание стремится к константе больше нуля. Теорема утверждает другое - если для каждого искать приближение с максимальным , так что (смотри Irrationality measure), то для этих приближений качество будет стремится к нулю (но сами приближения не будут иметь минимальной ошибки).
PS: Только для некоторых чисел вроде Liouville numbers качество приближений с минимальной ошибкой стремится к нулю.
