2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

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

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Улучшаема ли оценка сверху у функции?
Сообщение20.07.2011, 16:45 
Заслуженный участник


08/04/08
8559
$f(x)= \{ \frac{x}{a}\} + \{ \frac{x}{b}\} - \{ \frac{x}{ab}\}$, где $a,b>1$ - натуральные взаимно простые числа, $\{ t \}$ - дробная часть $t$. $f(x)$ оценивается сверху как $f(x) \leqslant 2$. Улучшаема ли эта оценка сверху? Как это доказать?

(Оффтоп)

теги: максимум функции, наибольшее значение

 Профиль  
                  
 
 Re: Улучшаема ли оценка сверху у функции?
Сообщение20.07.2011, 17:05 
Заслуженный участник


09/02/06
4397
Москва
Когда $a,b$ неограниченные, то неулучшаемо. Например $x=a-1,b=a+1$.

 Профиль  
                  
 
 Re: Улучшаема ли оценка сверху у функции?
Сообщение20.07.2011, 17:38 
Заслуженный участник


08/04/08
8559
Руст в сообщении #469946 писал(а):
Когда $a,b$ неограниченные, то неулучшаемо. Например $x=a-1,b=a+1$.

Проверил. Действительно так, спасибо. Разница $d(a,b)$ между максимумом и оценкой сверху примерно похожа на $O(a^{-1})$.

А если пытаться функциями от $a,b$ оценивать? (получается, что эти функции будут стремиться к 2 снизу при $a,b \to + \infty$). Может быть даже получится найти сам супремум?
У меня уже получилось:
$d(2,b)=\frac{1}{2}+1-\frac{1}{2b} \leqslant \frac{3}{2}$
$d(3,b) \leqslant \frac{1}{2}+\frac{4}{3}$
$d(4,b) \leqslant \frac{1}{2}+\frac{6}{4}$
$d(5,b) \leqslant \frac{1}{2}+\frac{8}{5}$

 Профиль  
                  
 
 Re: Улучшаема ли оценка сверху у функции?
Сообщение20.07.2011, 19:55 
Заслуженный участник


09/02/06
4397
Москва
$f(x)$ имеет период $ab$. Рассмотрим вначале целые $x=ay+bz$.
Тогда $f(x)=\{\frac{bz}{a}\}+\{\frac{ay}{b}\}-\{\frac{ay+bz}{ab}\}}$.
Меняем $z$ от 0 до a-1, y от 0 до b-1.
$f(x)=f(y,z), f(y,z+1)=f(y,z)+\frac{b\mod a -1}{a}+0,\pm 1$. Аналогично для y. Поэтому, максимум достигается, когда $f(x)=2-\frac{gcd(b-1,a)}{a}-\frac{gcd(a-1,b)}{b}$. Когда $x$ действительное максимум не достигается, супремум на $\frac{a+b-1}{ab}$ больше максимума по целым х.

 Профиль  
                  
 
 Re: Улучшаема ли оценка сверху у функции?
Сообщение30.08.2011, 07:54 
Заслуженный участник


08/04/08
8559
Руст в сообщении #469987 писал(а):
$f(x)=2-\frac{gcd(b-1,a)}{a}-\frac{gcd(a-1,b)}{b}$

Кажется, общая формула неверна. :roll:
Для $f(x)= \{ \frac{x}{3}\} + \{ \frac{x}{5}\} - \{ \frac{x}{15}\}$ ее максимум на целых числах у меня вышел $\frac{14}{15}$ в точке $x=\min \{ 3;5\}-1$, а по формуле получаем $2-\frac{\gcd(5-1,3)}{3}-\frac{\gcd(3-1,5)}{5} = 2-\frac{1}{3}-\frac{1}{5}=1+\frac{7}{15}$.

 Профиль  
                  
 
 Re: Улучшаема ли оценка сверху у функции?
Сообщение30.08.2011, 12:23 
Заслуженный участник


08/04/08
8559
Для простых различных $a,b, b>a$ вышло $f_{\max} \geqslant \left( 2- \frac{1+ b \mod a}{b}\right) \left( 1- \frac{1}{a}\right)$. $x$ - первое подходящее, не превосходящее $b$.

 Профиль  
                  
 
 Re: Улучшаема ли оценка сверху у функции?
Сообщение16.12.2011, 15:50 
Заслуженный участник


08/04/08
8559
Максимум можно вычислить за $O(\ln b), a<b$ операций.
При $f(x)= ab(\{ \frac{x}{a}\} + \{ \frac{x}{b}\} - \{ \frac{x}{ab}\}), x \in \mathbb{N}, 1 \leqslant x \leqslant ab$ ясно, что максимум находится либо среди чисел $x \equiv -1 \pmod a$, либо среди чисел $x \equiv -1 \pmod b$. Будем рассматривать только 1-й случай, 2-й аналогичен.
$x=ak-1$:
$f(ak-1)=b(a-1)+a((ak-1) \mod b)-ak-1=$ $ab-b-1+a(-k+(ak-1) \mod b), 1 \leqslant x \leqslant b$ - достаточно найти максимум скобки.
Положим $a=a_1, b=a_0$, $f_k(x)=-q_kx+e_k (a_kx+c_k) \mod a_{k-1}$, где $q_k \in \mathbb{Q}, e_k = \pm 1, c_k \in \mathbb{Z}, 1 \leqslant x \leqslant a_{k-1}$. Рассмотрим 2-е слагаемое при $x \in \mathbb{R}$ - функция разрывна, распадается на отрезки. Высшими точками $x_h$ функции $e(ax+c) \mod m$ назовем наибольшие значения функции на каждом из этих отрезков. Тогда ясно, что функция $f_k(x)$ имеет точку максимума среди высших точек. Легко найти формулу для высших точек:
1. $e=1 \Rightarrow x_h(t)= \left[ \frac{tm-c-1}{a} \right]$
2. $e=-1 \Rightarrow x_h(t)= \left[ \frac{tm-c-1}{a} \right]+1$
Будем рассматривать случай $e=1$ (2-й случай аналогичен). Для $f_k(x)$ получаем $x_h(t)=\left[ \frac{ta_{k-1}-c_k-1}{a_k} \right]$, причем $1 \leqslant t \leqslant a_k<a_{k-1}$ - интервал уменьшается. Обозначим $a_{k+1}=a_k \mod a_{k-1}$. Подставляем
$f_k(\left[ \frac{ta_{k-1}-c_k-1}{a_k} \right])=-q_k \left[ \frac{ta_{k-1}-c_k-1}{a_k} \right]+e_k (a_k\left[ \frac{ta_{k-1}-c_k-1}{a_k} \right]+c_k) \mod a_{k-1}$
$=-q_k \frac{ta_{k-1}-c_k-1}{a_k} - \frac{(ta_{k-1}-c_k-1) \mod a_k}{a_k}$ $+e_k (ta_{k-1}-c_k-1+c_k-(ta_{k-1}-c_k-1) \mod a_k) \mod a_{k-1}$
$=q_k\frac{c_k+1}{a_k} -q_k\frac{ta_{k-1}}{a_k} - \frac{(ta_{k+1}-c_k-1) \mod a_k}{a_k}$ $+e_k (a_{k-1}-1-(ta_{k+1}-c_k-1) \mod a_k) \mod a_{k-1}$
$=q_k\frac{c_k+1}{a_k} -q_k\frac{ta_{k-1}}{a_k} - \frac{(ta_{k+1}-c_k-1) \mod a_k}{a_k}$ $+e_k(a_{k-1}-1)-e_k(ta_{k+1}-c_k-1) \mod a_k$
$=q_k\frac{c_k+1}{a_k}+e_k(a_{k-1}-1) -q_k\frac{ta_{k-1}}{a_k}$ $-e_k(1+\frac{e_k}{a_k})(ta_{k+1}-c_k-1) \mod a_k$
В полученном выражении отделяем константы, выносим коэффициент перед $X \mod a_k$ - получаем новое выражение $f_{k+1}(t)$ того же вида, для которого нужно найти максимум уже на меньшем отрезке.
Из формулы $a_{k+1}=a_k \mod a_{k-1}$ получаем логарифмическую оценку скорости.

Еще бы смочь выписать явную формулу для максимума - было бы просто прекрасно. Вот только формула страшная будет. :-(

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group