Найти рациональное число

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 28 июл 2020, 00:01

Ian писал(а):Source of the post Ну а строгий ответ каково матожидание качества приближений со знаменателями $\leq B$ у Вас есть ?

Я же написал:
zykov писал(а):Source of the post Т.е. среднее качество будет $$\frac{\zeta(2)}{2} = \frac{\pi^2}{12} \approx 0.822$$.

Это матожидание качества приближения дающего минимальную ошибку среди всех $b$, таких что $b \leq B$.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Найти рациональное число

Сообщение Ian » 28 июл 2020, 09:26

Да, я хотел узнать [math], где
[math]
как оно зависит от В и как быстро стремится к 0
Это могло бы иметь такое применение. пусть мы измерениями получили какое-то действительное число и подходящую дробь к нему [math], тогда можно составить доверительный интервал радиуса например [math], в частности потому, что с вероятносью 1 его истинное значение трансцедентно

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 28 июл 2020, 12:41

Понятно.
Тут у меня другой случай.
  1. Берем $B$ (довольно большое)
  2. Для каждого $x \in [0, 1]$ находим приближение с минимальной ошибкой среди $a/b$, таких что $0 \leq a \leq b \leq B$
  3. Усредняем эти ошибки по $x \in [0, 1]$
  4. Умножаем среднее на $B^2$ и получаем какое-то число
  5. Устремляем $B \to \infty$ и это число (каждое для своего $B$) устремляется к $$\frac{\zeta(2)}{2} = \frac{\pi^2}{12} \approx 0.822$$
Если умножать ошибку не на $B^2$, а на $b^2$ - то не знаю. По идее должно быть меньше, т.к. $b \leq B$. Но вряд ли оно к нулю стремится, т.к. обычно $b$ будет порядка $B$.
Если искать приближение не с мимнимальной ошибкой, а с лучшим качеством (или лучшим $\mu$), то тоже не знаю. Может в этом случае качество и стремится к нулю.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 28 июл 2020, 18:25

zykov писал(а):Source of the post это число (каждое для своего $B$) устремляется к $$\frac{\zeta(2)}{2} = \frac{\pi^2}{12} \approx 0.822$$

Тут я ошибся.
Да, это матожидание, но в довольно странном смысле. Сначала равновероятно выбирается интервал, только потом внутри интервала равномерно выбирается $x$. При этом короткие интервалы имеют такой же вес, как и длинные.
Если же равномерно выбирать $x \in [0, 1]$, то короткие интервалы (внутри них качество лучше) будут иметь меньший вес. Т.е. матожидание качества будет ещё хуже.

Вот посчитал на компьютере матождание качества $|err| \cdot b^2$ для некоторых $B$:

Код: Выбрать все

  10: 0.52795
  30: 0.69242
 100: 0.87435
 300: 1.0413
1000: 1.2243
3000: 1.3912

Вобщем к нулю оно не стремится. Наоборот растёт. Причем похоже, что логарифмически растёт. Если так, то оно к бесконечности стремится.
Последний раз редактировалось zykov 29 июл 2020, 01:18, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 29 июл 2020, 01:13

В предыдущем случае было матожидание качества, если для каждого $x$ выбирать приближение с минимальной ошибкой.

Сейчас другой алгоритм сделал - более сложный. Считает матожидание качества, если выбирать приближение с наилучшим качеством.
Тут считает долго. В предыдущем было достаточно просто пройтись по списку интервалов. Здесь же нужно сначала построить ломаную оптимального качества. Для каждой рациональной точки из набора берем перевернутый треугольник $y \leq b^2|x-x_0|$ и берем пересечение этих множеств. Ломаная огибающяя это пересечение сверху и будет ломаная оптимального качества. Дальше уже просто - матожидание ищется суммированием по таким трапециям.
Вот получилось матожидание качества в зависимости от $B$:

Код: Выбрать все

  10: 0.13390
  30: 0.10868
 100: 0.090933
 300: 0.079330
1000: 0.069798

Немного похоже на логарифм в минус первой степени, но трудно сказать.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 29 июл 2020, 01:34

Вот на картинке ломаная оптимального качества для $B=20$:
rational_optimalQ_B20.png
rational_optimalQ_B20.png (158.68 KiB) 22711 просмотра

Если присмотреться, то около $0.1415$, будет хорошее приближение для $\pi$ в виде $22/7$.
А ещё есть точки около 0.38, которые оптимально приближаются нулём. Они там и при больших $B$ остаются, т.к. $2 - \phi \approx 0.382$, где $\phi = \frac{\sqrt 5 +1}{2}$ - золотое сечение.
Последний раз редактировалось zykov 29 июл 2020, 18:31, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 29 июл 2020, 15:34

Переписал алгоритм на C++, т.к. Matlab не очень дружит с ассоциативными структурами данных (нужно для построения ломаной).
Вот получилось:

Код: Выбрать все

    B       Q1       Q2
   10:  0.52795   0.133905
   30:  0.692418  0.108681
  100:  0.874348  0.0909331
  300:  1.04134   0.0793299
 1000:  1.22426   0.0697979
 3000:  1.39119   0.063004
10000:  1.57416   0.0570066
20000:  1.6795    0.0540705

Дальше уже памяти не хватает.
Ломаная содержит примерно $\frac{9}{\pi^2} B^2 \approx 0.912 B^2$ точек.
При $B=20000$ это уже $3.64 \cdot 10^8$ точек (несколько гигабайт памяти).

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 29 июл 2020, 21:55

Ian писал(а):Source of the post Да, я хотел узнать $E\psi$, где
$\psi(x)=min_{b \leq B}(err(x,b)*b^2)$
как оно зависит от В и как быстро стремится к 0

Есть некоторые подвижки.
Пусть $q(B)$ - это матожидание качества.
Если мы увеличиваем $B$ на 1, это значит, что из площади под ломаной мы должны исключить для точек $x_a = \frac{a}{B+1}$ перевернутые треугольники $y \geq |x - x_a| (B+1)^2$ (все они очень узкие для больших $B$).
Тут можно грубо оценить исключаемую площадь в среднем на одну точку как $q^2(B) / (B+1)^2$. Вообще говоря тут нужно было бы подставить среднее квадрата качества, но его у нас нет, так что ставим квадрат среднего. Ещё неизвестно, есть ли там какие корреляции.
Второй вопрос, это количество точек $x_a$ (количество $a$ несократимых с $B+1$). Оно зависит от разложения $B+1$ на простые множители. Если например $B+1$ простое, то таких точек будет $B$ штук. Если не простое, то будет меньше точек.
Опять же грубо положим, что в среднем у нас $k(B+1)$ таких точек, где $k$ - какая-то константа.
Тогда получаем: $$q(B+1) = q(B) - k \frac{q^2(B)}{B+1}$$.
Тут можно перейти к дифференциальному уравнению $$q'(B) = -k \frac{q^2(B)}{B+1}$$.
Его решение: $q(B) = (c + k \ln(B+1))^{-1}$.
По рассчитанным точкам $B=10000$ и $B=20000$ можно подобрать $k \approx 1.3742$ и $c \approx 4.8846$.
Правда глядя на график можно заметить, что $k$ не совсем константа. Это дифференциальное значение медленно уменьшается.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 29 июл 2020, 22:48

Используя эту идею с вырезанием треугольников написал ещё один алгоритм, который не требует много памяти, т.к. не рассчитывает полностью ломаную качества, но считает он не точно, а с небольшой ошибкой.
Идея такая, что для меньшего $B_{ref}$ полностью рассчитывается ломаная качества, а потом перебираются все точки $a/b$, где $B_{ref} < b \leq B$ и из площади под ломаной вычитаются треугольники для каждой точки. Результат был бы точный, если бы разные треугольники не пересекались (под ломаной), но иногда (довольно редко) они пересекаются, поэтому мы вычитаем слишком много и результат оказывается заниженный, но не сильно, если $B$ ненамного больше чем $B_{ref}$.

Вот результаты расчёта и вычисления по формуле:

Код: Выбрать все

  B      точно     Bref=3k   Bref=10k     формула
  3k:  0.0630040      -          -       0.0629418
 10k:  0.0570066  0.0570069      -       0.0570064
 15k:  0.0552494      -          -       0.0552515
 20k:  0.0540705  0.0540618      -       0.0540705
 30k:      -      0.0524410  0.0524966   0.0524892
 60k:      -      0.0497233      -       0.0499898
100k:      -      0.0477296  0.0483116   0.0482950

Вот ещё для 100k посчиталось при $B_{ref}=20k$: $0.0483436$ (почти 2 часа считало).

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Найти рациональное число

Сообщение Ian » 30 июл 2020, 09:18

zykov писал(а):Второй вопрос, это количество точек $x_a$ (количество $a$ несократимых с $B+1$). Оно зависит от разложения $B+1$ на простые множители. Если например $B+1$ простое, то таких точек будет $B$ штук. Если не простое, то будет меньше точек.
Опять же грубо положим, что в среднем у нас $k(B+1)$ таких точек, где $k$ - какая-то константа.
Тогда получаем: $$q(B+1) = q(B) - k \frac{q^2(B)}{B+1}$$.
Тут можно перейти к дифференциальному уравнению $$q'(B) = -k \frac{q^2(B)}{B+1}$$.
Его решение: $q(B) = (c + k \ln(B+1))^{-1}$.
По рассчитанным точкам $B=10000$ и $B=20000$ можно подобрать $k \approx 1.3742$ и $c \approx 4.8846$.
Правда глядя на график можно заметить, что $k$ не совсем константа. Это дифференциальное значение медленно уменьшается.

Это выражается через функцию Эйлера
https://en.wikipedia.org/wiki/Euler's_totient_function
Для нее много асимптотических равенств. Нужны какие-то интегральные, так как k(как Вы исходно его определили, до огрубления) всюду плотно прыгает по [0,1]

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 30 июл 2020, 13:24

Это да, только нас интересует усреднённое по большому интервалу значение.
Кроме того, в конечном счёте $k$ включает в себя ещё артефакты при усреднении качества $q$, а не только процент количества (оно вот оказалось больше 1).
Но в целом формула неплохо согласуется при больших $B$ (до 100k точно, наверно и до 1M).
Мне вот интересно - с ростом $B$ это $k$ будет к конечному пределу стремится или к нулю (ну тогда уж и $c$ может меняться).
Дальше 100k уже трудно считать. Тем более, что нужен логарифмический мосштаб и нужно на порядки увеличивать.
Так что нужен какой-то аналитический метод для больших $B$.
Последний раз редактировалось zykov 30 июл 2020, 17:58, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 30 июл 2020, 17:57

Ian писал(а):Source of the post всюду плотно прыгает по [0,1]

Да, это одна из причин отклонения значения по формуле от точного значения.
Точное значение имеет заметные флуктуации (делает скачки от одного $B$ до другого), а формула выдаёт усреднённое значение.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 31 июл 2020, 17:37

zykov писал(а):Source of the post Его решение: $q(B) = (c + k \ln(B+1))^{-1}$.

Есть ещё подвижки.
Если взять точные значения (для приличной регрессии я посчитал все точные значени от 1k до 10k) и построить график - $1/q$ от $\ln(B+1)$, то результат очень близок к прямой (в среднем, не считая флуктуаций), но всё равно имеет хотя и маленькую, но значимую выпуклость вверх. Так что, если сделать линейную регрессию, то к $B=100k$ набегает заметная ошибка.
Пробовал добавить квадратный член. Всё равно к 100k ошибка набегает. Впрочем оно и понятно - квадратная аппроксимация (да и многочленом более высокой степени) хороша для интерполяции, а для экстраполяции толку мало, если конечно нет причин ожидать именно квадратичного закона.

Вобщем тут лучше подходит приближение рядом Лорана около точки $+\infty$.
Получается: $q(B) = (c + k \ln(B+1) + k_1 \ln^{-1}(B+1) + k_2 \ln^{-2}(B+1))^{-1}$
(Пробовал только одну поправку добавить - тоже работает, но с двумя поправками заметно лучше.)
Эти 4 коэффициента нашел регрессией по всем точкам от 1k до 10k:

Код: Выбрать все

c=6.4983659  k=1.2984793  k1=-10.064678  k2=14.978246

Эта формула даёт довольно точный результат. Причем не только для интерполяции, но главное - для экстраполяции.

Код: Выбрать все

  B      точно     Bref=3k   Bref=10k     формула
  10:  0.133905       -          -       0.12469382
  30:  0.108681       -          -       0.1075662
 100:  0.0909331      -          -       0.090798274
 300:  0.0793299      -          -       0.07933196
  1k:  0.0697979      -          -       0.069801954
  3k:  0.0630040      -          -       0.063005966
 10k:  0.0570066  0.0570069      -       0.05700686
 15k:  0.0552494      -          -       0.05524956
 20k:  0.0540705  0.0540618      -       0.054070574
 30k:      -      0.0524410  0.0524966   0.052496173
 60k:      -      0.0497233      -       0.050016678
100k: (0.0483436) 0.0477296  0.0483116   0.048340774

(Для 100k точного значения нет, есть только при Bref=20k.)
При $B=10$ ошибка большая. Дальше уже лучше идёт. Начиная с $B=300$ и до $B=100k$ формула даёт очень хорошую точность, т.е. экстраполяция действительно работает.
Ещё раз подчеркну, что не следует ожидать идеальной точности между формулой и точным значением, т.к. формула даёт гладкую усреднённую величину, а точное значение подвержено небольшим, но резким, псевдослучайным скачкам (зависит от разложения $B$ на простые множители).

PS: по формуле матожидание качества достигнет $0.01$ при $B \approx 2.2 \cdot 10^{31}$.
Последний раз редактировалось zykov 31 июл 2020, 21:53, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 31 июл 2020, 17:44

Вот график ошибки в пределах от 1k до 10k между формулой и точным значением:
rational_err_1k10k.png
rational_err_1k10k.png (68.47 KiB) 22639 просмотра

Заметной выпуклости для третьей поправки уже нет. Но есть какие-то затухающие осцилляции с большим периодом.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 31 июл 2020, 21:40

zykov писал(а):Source of the post (Пробовал только одну поправку добавить - тоже работает, но с двумя поправками заметно лучше.)

Понятно, что $k_1$ и $k_2$ будут иметь уменьшаюшийся эффект по мере роста $B$ (правда вырасти оно должно очень сильно, т.к. там логарифм).
Но главный эффект от них при регрессии в области 1k-10k. Если их не использовать, то их наклон прибавляется к $k$ и здесь эта добавка будет расти с ростом $B$, вместо того чтобы уменьшатся.
Т.е. эффект в том, что регрессия точнее определяет $c$ и $k$.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 31 июл 2020, 22:13

zykov писал(а):Source of the post Получается: $q(B) = (c + k \ln(B+1) + k_1 \ln^{-1}(B+1) + k_2 \ln^{-2}(B+1))^{-1}$

Возможно интересно, эта формула соответствует дифуру:
$$q'(B) = -\frac{q^2(B)}{B+1} \left(k - \frac{k_1}{\ln^2(B+1)} - \frac{2 k_2}{\ln^3(B+1)}\right)$$
Это что-то говорит о корреляциях, т.к. средний процент несократимых дробей стремится к $\frac{1}{\zeta(2)} = \frac{6}{\pi^2} \approx 0.608$.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 31 июл 2020, 22:32

Вот тут любопытно, что раз есть минус вторая и минус третья степени, то тут могла бы быть и минус первая степень в этой сумме.
Тогда дифур $$q'(B) = -\frac{q^2(B)}{B+1} \left(k + \frac{k_0}{\ln(B+1)}\right)$$ имеет решение $$q(B) = (c + k \ln(B+1) + k_0 \ln \ln(B+1))^{-1}$$.
Правда $\ln \ln(B+1)$ очень близок к линейной функции при $B$ в диапазоне 1k-10k (да и при 100k), так что при регрессии в области 1k-10k оно скорее всего сливается с $c + k \ln(B+1)$.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 31 июл 2020, 23:08

Вот новая формула: $q(B) = (c + k \ln(B+1) + k_0 \ln \ln(B+1) + k_1 \ln^{-1}(B+1) + k_2 \ln^{-2}(B+1))^{-1}$

Код: Выбрать все

c=2.9378477  k=1.2416152  k0=1.376538  k1=1.0099525  k2=0.17295692

Тут $k$ заметно скорректировался, а это асимптотика при очень больших $B$.
Эта формула даёт экстраполяцию ещё точнее.
При 100k точность выше, чем раньше. Даже при 10 точность довольно высока.

Код: Выбрать все

  B      точно     Bref=3k   Bref=10k     формула
  10:  0.133905       -          -       0.13209547
  30:  0.108681       -          -       0.10859443
 100:  0.0909331      -          -       0.090907443
 300:  0.0793299      -          -       0.079341839
  1k:  0.0697979      -          -       0.069802039
  3k:  0.0630040      -          -       0.063005983
 10k:  0.0570066  0.0570069      -       0.057006881
 15k:  0.0552494      -          -       0.055249723
 20k:  0.0540705  0.0540618      -       0.054070929
 30k:      -      0.0524410  0.0524966   0.052496959
 60k:      -      0.0497233      -       0.050018689
100k: (0.0483436) 0.0477296  0.0483116   0.04834411

(Для 100k точного значения нет, есть только при Bref=20k.)

PS: по новой формуле матожидание качества достигнет $0.01$ при $B \approx 7.6 \cdot 10^{31}$.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 01 авг 2020, 17:53

zykov писал(а):Source of the post Тогда дифур $$q'(B) = -\frac{q^2(B)}{B+1} \left(k + \frac{k_0}{\ln(B+1)}\right)$$ имеет решение $$q(B) = (c + k \ln(B+1) + k_0 \ln \ln(B+1))^{-1}$$.

Вот ещё можно посмотреть под таким углом.
Если $q(B)$ - усреднённое качество (сглаженное по $B$), то для него видимо верен такой дифур:
$$q'(B) = -\frac{q^2(B)}{B+1} K(\ln^{-1}(B+1))$$, где $K(x)$ - некоторая нелинейная функция, которую например можно аппроксимировать кубическим многочленом $K(x)=k + k_0 x - k_1 x^2 - 2 k_2 x^3$ на интервале от $0$ до $\ln^{-1} 7.4 \approx 0.5$.
Т.е. $$\left(\frac{1}{q(B)}\right)' = \frac{1}{B+1} K(\ln^{-1}(B+1))$$, и значит
$$\frac{1}{q(B)} = с + \int \frac{1}{B+1} K(\ln^{-1}(B+1)) \; dB$$

Интересно, что это за функция K(x) могла бы быть?
Выглядит вот так:
rational_Kx.png
rational_Kx.png (14.94 KiB) 22595 просмотра

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Найти рациональное число

Сообщение zykov » 01 авг 2020, 18:02

Если сделать замену переменной $y=\frac 1 q$ и $t = \ln^{-1}(B+1)$, соответственно $B+1 = e^{1/t}$.
Тогда $y'(t) = -t^{-2} K(t)$ и $y(t) = C - \int t^{-2} K(t) \; dt$.


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 8 гостей