Re: минимальное покрытие

[jetyb]

Есть отрезок, есть его покрытие: для каждой точки отрезка $x$ есть содержащая его окрестность, т.е. интервал с центром в точке $x$ длины $f(x)$, где $f(x)$ - положительная, сравнительно легковычислимая функция. Требуется найти минимальное покрытие отрезка.

Задача возникла в процессе решения одного уравнения: в любой точке $a$ может быть найдено его решение в виде ряда, для радиуса сходимости которого выполнена оценка: $R(a)>f(a)$. $f$ представляет собой рациональную дробь, только в ней еще присутствуют функции $\min$ и $\max$. Надо решить уравнение на отрезке, использовав как можно меньше разложений в ряд.

Пробовал просто "гнать" решение, пробовал находить точку максимума $f(x)$ и удалять ее вместе с окрестностью, искал покрытие в виде пересекающихся только в одной точке отрезков,- полученные результаты не особо вдохновили. Может быть, я просто изобретаю велосипед, а алгоритм решения таких задач известен?
Подскажите, пожалуйста.

[Padawan]

Может лучше попытаться получить явное выражение для $R(a)$ ? Какой-ряд то получается?

[jetyb]

Получается ряд по целым степеням $x$, коэффиценты которого определяются рекуррентным соотношением. Задача нахождения радиуса сходимости сама по себе нетривиальна, я не уверен, что формула радиуса сходимости будет проще полученной его оценки. Сама оценка у меня такая:

$$R>\frac{2\varepsilon r_0}{\left((a^2-1)r_0+a\right)\max\left(\frac{\left|\frac{a}{r_0}\left((a^2-1)r_0+a\right)+2ar_0^2\varepsilon+2r_0^2\varepsilon^2\right|}{\left((a^2-1)r_0+a\right)^2},\frac{1}{|r_0|}+\frac{\max(2|a|,|a^2-1|)}{\min\left(\left|(a^2-1)r_0+a \right|,\left|\frac{a}{2\varepsilon r_0^2}\left((a^2-1)r_0+a\right)+ar_0+r_0\varepsilon\right|\right)}\right) }$$

Здесь $\varepsilon$ - малый параметр, $r_0$ - константа, $a$ - точка, в которой считается ряд.

[worm2]

Может быть, поможет "жадный" алгоритм: левая граница отрезка (пусть будет $a$) должна быть покрыта; попробуем будет выбрать для её покрытия наибольшее $x$, что $x-f(x) \leqslant a$, а затем применить этот алгоритм к оставшемуся отрезку?

Если "жадный" алгоритм слишком примитивен, то есть смутное ощущение, что динамическое программирование как-то здесь можно попробовать применить...

Есть также смутное подозрение, что "жадный" алгоритм можно допилить до оптимального. Может быть, применять его на каждом шаге с учётом того, что точка $x$ может лежать левее текущего левого конца отрезка?

[Padawan]

Всё равно, радиус сходимости должен вести себя более-менее регулярно, ведь он равен расстоянию до ближайшей особой точки. Если не трудно, выпишите рекуррентные соотношения для коэффициентов?

-- Сб апр 10, 2010 15:38:41 --

Постройте график функции $f=f(a)$. А какой отрезок, кстати, покрываем?

[jetyb]

Собственно, такой алгоритм я пробовал:

jetyb в сообщении #308238 писал(а):

искал покрытие в виде пересекающихся только в одной точке отрезков

Результат есть, но он меня не устроил: при множественных переразложениях слишком возрастала погрешность вычисления решения.
Искать максимальнуе по радиусу окрестность среди покрывающих левую точку попробую.

Коэффиценты этого ряда выглядят так:
$r_0=const\neq 0\quad 0<\varepsilon\ll 1$
$r_1=-\frac{1}{\varepsilon r_0}\left((a^2-1)r_0+a\right)$
$r_2=-\frac{1}{2\varepsilon r_0}\left(\varepsilon r_1^2+2ar_0+(a^2-1)r_1+1\right)$
$r_3=-\frac{1}{3\varepsilon r_0}\left(3\varepsilon r_1r_2+r_0+2ar_1+(a^2-1)r_2\right)$
$r_4=-\frac{1}{4\varepsilon r_0}\left(\varepsilon(4r_1r_3+2r_2r_2)+r_1+2ar_2+(a^2-1)r_3\right)$
$\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots$
$r_{n+1}=-\frac{1}{(n+1)\varepsilon r_0}\left(\varepsilon\sum\limits_{i=1}^{n}(n+1-i)r_ir_{n+1-i}+r_{n-2}+2ar_{n-1}+(a^2-1)r_n\right)$
В принципе(см. оценку радиуса) ряд где-то сходится на всей прямой, но мне интересна окрестность отрезка $[-1;2]$.

[Padawan]

Это коэффициенты разложения в окрестности точки $a$ ? То есть по степеням $x-a$?

[jetyb]

Да, центр координат переносится в точку $(a;0):x=\tilde{x}+a$, затем берутся разложения по степеням $\tilde{x}=x-a$.

[Padawan]

Понятно. Тогда искомая функция $F(a)$ должна удовлетворять дифф. уравнению $F'(a)=-\dfrac 1{\varepsilon r_0}\left( (a^2-1)r_0+a\right)$. Решается просто.

[jetyb]

Нет, я решаю похожее уравнение(Ван-дер-Поля), но не такое:

$$FF'+(\tilde{x}^2+2a\tilde{x}+a^2-1)F+\tilde{x}+a=0$$

[Padawan]

Так... Что-то с коэффициентами тогда не то. Ведь разложение функции $F(x)$ в окрестности точки $x=a$ имеет вид

$$F(x)=F(a)+F'(a)(x-a)+F''(a)/2!\cdot (x-a)^2+\ldots$$

У Вас получается $F(a)=r_0$ для любого $a$, чушь какая-то. Я чего-то не понимаю?

-- Сб апр 10, 2010 16:27:12 --

У функции $F$ какие аргументы? Что такое $a$ ? Параметр? Тогда почему он изменяется?

[jetyb]

У функции $F$ аргумент один. Степенное разложение ищется в точке $(a;r_0)$(т.е. решается дифур с н.у. $F(a)=r_0$). Получившийся степенной ряд зависит от $a$ и от $r_0$. Но оценка его радиуса сходимости не зависит от $r_0$; там взят особый $r_0^*=const$, такой, чтобы оценка была верна для интересующей меня области. То есть во втором моем сообщении считайте, что вместо $r_0$ стоит $r_0^*$.

[Padawan]

Вы должны выбрать какое-то одно $a$, в котором ставится начальное условие. А то у Вас получается при разных $a$ одно и то же начальное условие.

Похоже мы друг-друга не понимаем. Сформулирую я
Ищется аналитическое решение $F=F(x)$ дифференциального уравнения

$$FF'+(x^2-1)F+x=0,$$

удовлетворяющее начальному условию $F(a)=r_0$.
Требуется для $x_0\in [-1,2]$ оценить радиус сходимости ряда Тейлора функции $F$ в точке $x_0$, т.е. расстояние от $x_0$ до ближайшей особой точки функции $F$.

[jetyb]

Padawan,
Благодарю за желание разобраться в математической подоплеке задачи, но для меня в этом нет необходимости. У меня нет сомнений в правильности решения: хоть оно и довольно объемное(для форума), я сам его много раз перепроверял, его смотрели у меня другие люди. Возникающие в ходе решения вопросы, которые через сообщения на форуме решаются за полчаса, в личном общении объясняются за две минуты. Объяснение решения здесь только затянет время.
Сюда я написал, чтобы узнать метод решения возникшей задачи по программированию, а не обсуждать правильность возникновения такой задачи.

[Padawan]

Как хотите, программируйте. Дело не в том, что Вы эту функцию не правильно считаете, просто не эффективно. Я же заинтересовался Вашим сообщением именно потому, что покрытие не произвольное, а образованное кругами аналитичности. Мне кажется, что там проще все можно сделать. Было бы произвольное покрытие, я бы писать не стал.