2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Рациональное число с наименьшим знаменателем в интервале
Сообщение27.03.2009, 03:28 
Как найти рациональное число с наименьшим знаменателем в интервале $(a;b)$.
$a < \frac{m}{n} < b \Longrightarrow an < m < bn$ т.е. нужно найти такое минимальное $n$, что между $an, bn$ содержится целое число. Как решить эту задачу? Неужели только перебором? Может можно сократить область поиска?

 
 
 
 
Сообщение27.03.2009, 03:55 
Аватара пользователя
А если попробовать рациональные приближения $a$ и $b$ (цепными дробями)? Отталкиваться от тех из них, которые имеют погрешности, сравнимые с $|a-b|$.

 
 
 
 
Сообщение27.03.2009, 07:10 
Аватара пользователя
Ну а в каком виде заданы $a$ и $b$?

 
 
 
 
Сообщение29.03.2009, 05:02 
Профессор Снэйп писал(а):
Ну а в каком виде заданы $a$ и $b$?
Пусть $a, b$ - рациональные

 
 
 
 Re: Рациональное число с наименьшим знаменателем в интервале
Сообщение30.03.2009, 16:45 
Аватара пользователя
ellipse писал(а):
Как найти рациональное число с наименьшим знаменателем в интервале $(a;b)$.
$a < \frac{m}{n} < b \Longrightarrow an < m < bn$ т.е. нужно найти такое минимальное $n$, что между $an, bn$ содержится целое число.

Ограничение сверху на $n$ - это сумма знаменателей чисел $a$ и $b$. Дело в том, что если $a=\frac{p_a}{q_a} < b=\frac{p_b}{q_b}$, где $p_a$, $p_b$, $q_a$ и $q_b$ - натуральные числа, то
$$a < \frac{p_a + p_b}{q_a + q_b} < b.$$
При этом эта верхняя грань достижима на соседних членах рядов Фарея, причем в этом случае $\frac{p_a + p_b}{q_a + q_b}$ представляет собой несократимую дробь.

 
 
 
 
Сообщение30.03.2009, 21:22 
Предположим $a < \frac mn <b$ и $\frac mn$ (несократимая) дробь с наименьшим знаменателем в этом интервале. Рассмотрим дроби $\frac m{n-1}$ и $\frac {m-1}{n-1}$ знаменатель этих дробей меньше $n$, значит,согласно сделанному предположению они лежат вне интервала $(a,b)$,поэтому $\frac m{n-1}>b$$\frac {m-1}{n-1}<a$. Следовательно, $\frac m{n-1}-\frac {m-1}{n-1}=\frac 1{n-1}>b-a$,отсюда получаем оценку $n<\frac1{b-a}+1$. Числа $a$ и $b$ не обязательно предполагать рациональными.

 
 
 
 
Сообщение30.03.2009, 22:08 
Аватара пользователя
Тут все предлагают верхние оценки для $n$, которые в некоторых случаях могут быть точны. Ну а если оценка получена и она оказалась достаточно велика? Насколько я понял, автора интересует именно этот случай и он спрашивает, можно ли избежать перебора.

 
 
 
 
Сообщение30.03.2009, 23:09 
Аватара пользователя
А тупо берём среднее арифметическое и идём по его подходящим дробям. И только.

 
 
 
 
Сообщение30.03.2009, 23:33 
Аватара пользователя
ИСН писал(а):
А тупо берём среднее арифметическое и идём по его подходящим дробям. И только.

Докажите.

 
 
 
 
Сообщение30.03.2009, 23:44 
Аватара пользователя
Ну как. (Я не все нужные слова знаю.) Искать такое число на интервале - это значит искать некоторое наилучшее приближение к середине интервала (наилучшее - в смысле, которое лучше всех с меньшим знаменателем), а все такие приближения суть её подходящие дроби, вроде так.

 
 
 
 
Сообщение30.03.2009, 23:54 
Аватара пользователя
ИСН в сообщении #200445 писал(а):
Искать такое число на интервале - это значит искать некоторое наилучшее приближение к середине интервала (наилучшее - в смысле, которое лучше всех с меньшим знаменателем)

Эта предпосылка неверна.

 
 
 
 Re: Рациональное число с наименьшим знаменателем в интервале
Сообщение31.03.2009, 02:58 
Аватара пользователя
maxal писал(а):
Ограничение сверху на $n$ - это сумма знаменателей чисел $a$ и $b$. Дело в том, что если $a=\frac{p_a}{q_a} < b=\frac{p_b}{q_b}$, где $p_a$, $p_b$, $q_a$ и $q_b$ - натуральные числа, то
$$a < \frac{p_a + p_b}{q_a + q_b} < b.$$
При этом эта верхняя грань достижима на соседних членах рядов Фарея, причем в этом случае $\frac{p_a + p_b}{q_a + q_b}$ представляет собой несократимую дробь.

Отсюда следует и алгоритм для нахождения искомого числа с наименьшим знаменателем:
1) если $a$ и $b$ являются соседними элементами ряда Фарея $F_{\max\{q_a,q_b\}}$, то решение уже указано выше;
2) в противном случае нужно "достроить" все дроби ряда Фарея $F_{\max\{q_a,q_b\}}$, находящиеся между $a$ и $b$, и выбрать из них дробь с наименьшим знаменателем. Для этого можно начать с чуть большего отрезка (покрывающего $[a,b]$) ряда $F_{\min\{q_a,q_b\}}$ и достроить его стандартным образом (см. ссылку выше) до отрезка ряда $F_{\max\{q_a,q_b\}}.$

Сложность здесь пропорциональна разности знаменателей $|q_a - q_b|$ и количеству дробей в $F_{\max\{q_a,q_b\}}$, находящихся между $a$ и $b$.

 
 
 
 
Сообщение31.03.2009, 11:53 
Аватара пользователя
Крутил так и сяк – нет, не понимаю. Вот число; оно попало на интервал, а все с меньшими знаменателями – не попали. А оно попало. Значит, оно ближе к середине интервала, чем те. То есть, значит, наилучшее приближение для этой середины.
Или как?

 
 
 
 
Сообщение31.03.2009, 12:13 
та при чем тут середина. "Лучшее" число на интервале (1/2 - 1/1000000, 1) совсем не рядом с серединой этого интервала.

 
 
 
 
Сообщение31.03.2009, 13:42 
Аватара пользователя
Бывают разные наилучшие приближения. В данном случае это почти наилучшее приближение первого рода ("почти" потому, что в определении наил. прибл. рассматриваются и дроби со знаменателем, равным рассматриваемому); среди них помимо подходящих ещё промежуточные дроби встречаются.

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


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