2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Лучшее приближение корня суммой 2-х корней
Сообщение27.10.2011, 16:13 
Не знаю как решать, мне задачка понравилась

Найти для натурального $A$ натуральные $x,y$ такие, чтобы выражение $\sqrt{A}\approx \sqrt{x}+\sqrt{y}$ являлось лучшим приближением.

Позаимствовано у Андрея А отсюда:
http://www.mathhelpplanet.com/viewtopic.php?f=48&t=8809 (новая тема)
http://e-science.ru/forum/index.php?s=e ... opic=11670 (старая тема)

 
 
 
 Re: Лучшее приближение корня суммой 2-х корней
Сообщение27.10.2011, 17:45 

(Оффтоп)

Цитата:
Если эту штуку можно решить, не прибегая к подбору значений, то существует, кажется, очень красивый способ нахождения делителей целого числа вообще
А не слишком ли амбициозную (и вредную) задачу поставил себе Андрей.

 
 
 
 Re: Лучшее приближение корня суммой 2-х корней
Сообщение27.10.2011, 18:24 

(Оффтоп)

Shadow в сообщении #496501 писал(а):
А не слишком ли амбициозную (и вредную) задачу поставил себе Андрей.

А что, это какая-то известная сложная задача? Может NP-полная? :?
Согласен насчет вредности - трудная задачка, по-моему.

 
 
 
 Re: Лучшее приближение корня суммой 2-х корней
Сообщение27.10.2011, 19:27 
Аватара пользователя
$x=A$, $y=0$

 
 
 
 Re: Лучшее приближение корня суммой 2-х корней
Сообщение27.10.2011, 19:29 
Аватара пользователя

(Оффтоп)

Legioner93, 0- не натуральное

 
 
 
 Re: Лучшее приближение корня суммой 2-х корней
Сообщение27.10.2011, 19:29 
Аватара пользователя
Legioner93,

в РФ ноль не считается натуральным (номер статьи не помню).

 
 
 
 Re: Лучшее приближение корня суммой 2-х корней
Сообщение27.10.2011, 19:30 
Аватара пользователя

(Оффтоп)

у меня считается

Sonic86 в сообщении #496516 писал(а):
Может NP-полная?

Кстати тоже так подумал.

 
 
 
 Re: Лучшее приближение корня суммой 2-х корней
Сообщение28.10.2011, 06:29 
Legioner93 в сообщении #496561 писал(а):
Кстати тоже так подумал.

Просто автор задачи утверждает, что он решил задачку для всех составных чисел - это уже множество меры 1. Может она и не NP-полная. Короче, решить надо.

 
 
 
 Re: Лучшее приближение корня суммой 2-х корней
Сообщение28.10.2011, 10:06 
Cоображения следующие:
$\sqrt{A} - \sqrt{x} = \sqrt{y}$
$\sqrt{4Ax} = A+x-y$
Меняя $y$ справа можно сделать любое целое нужного диапазона.
Соответственно нужно подобрать множитель к числу $4A$ сделав его близким к квадрату.
Если в лоб, то можно решить уравнение $4Ax=(z-1)(z+1)$
в случае составного $A$ - оно элементарно. Хорошие приближения мы точно получим, но гарантии наилучшего, правда, нет.

 
 
 
 Re: Лучшее приближение корня суммой 2-х корней
Сообщение02.11.2011, 07:24 
Для числа $805$ точное приближение такое:
$\sqrt{805} \approx \sqrt{66} + \sqrt{410}, \epsilon \approx 2,6 \cdot 10^{-5}$. Я какую-то формулу нашел, но это - первый контрпример к ней. Было бы интересно знать соображения, из которых такое приближение находится точно.

 
 
 
 Re: Лучшее приближение корня суммой 2-х корней
Сообщение02.11.2011, 08:46 
Аватара пользователя

(Оффтоп)

AKM в сообщении #496559 писал(а):
в РФ ноль не считается натуральным

В РФ нет логиков? :twisted:

 
 
 
 Re: Лучшее приближение корня суммой 2-х корней
Сообщение13.11.2011, 10:46 
В общем, целиком задача не решилась.
Основную часть решения ТС изложил в теме по ссылке, полученное решение в итоге упирается в перебор, что плохо. У ТС изначально были только приближения снизу, но существенной разницы между задачами похоже нет.
В случае составных $n$ используется такой прием:
$(A^2+B^2)(C^2+D^2)=(AC+BD)^2+(AD-BC)^2$. Заменяя переменные на корни из них, имеем $(A+B)(C+D)=(\sqrt{AC}+\sqrt{BD})^2+(\sqrt{AD}-\sqrt{BC})^2$ При $AD-BC= \pm 1$ получаем
$\sqrt{(A+B)(C+D)} \approx \sqrt{AC}+\sqrt{BD}$. В случае, когда $n=pq, p,q \in \mathbb{P}$ мы, решая уравнение $AD-BC= \pm 1$, получаем 2 приближения сверху и снизу и выбираем точное. А в случае большего числа делителей перебор увеличивается. Оптимальное значение достигается при наиболее близких друг к другу значениях корней $\sqrt{AC},\sqrt{BD}$
Другой прием - формула $\sqrt{A} \approx \sqrt{\frac{(A-B)^2+\Delta}{4A}}+\sqrt{\frac{(A+B)^2+\Delta}{4A}}$, где $B:B^2 \equiv - \Delta \pmod{A}$ - наименьшее по модулю (чем меньше, тем точнее приближение). Прием работает как для составных, так и для простых. Для составных $A$ поиск наименьшего $B$ сводится к перебору решений, число вариантов выбора растет с увеличением числа делителей (экспоненциально). Для простых $A$ решения для заданного $\Delta$ могут не существовать или быть тривиальными, поэтому приходится перебирать $\Delta$ + не получилось доказать (скорее, это просто неверно), то погрешность растет с ростом $\Delta$. Величина $\Delta$ растет не быстрее, чем $\ln A$.
Сведение $\sqrt{n} \approx \sqrt{x} + \sqrt{y}$ к уравнению $t^2-(n-k)t+\frac{k^2+ \Delta}{4}=0$ дает в лучшем случае то же самое ($t=x;y$)

:-(

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group