Исходные данные:
1. уравнение кривой y=f(x). кривая непрерывная и дифференцируемая 2 раза.
2. е — погрешность.
Нужно: описать эту кривую минимальным количеством точек (лежащих на этой кривой) с максимальной погрешностью e (для примера, данную операцию делает Unigraphics).
PS. в Unigraphics точки располагаются неравномерно по длине кривой и сгущаются в местах увеличения кривизны (замечено при построениях в Unigraphics)
Re: Алгоритм нахождения точек на кривой
От:
Аноним
Дата:
19.11.10 21:13
Оценка:
Здравствуйте, i.m.p, Вы писали:
IMP>Помогите решить задачку.
IMP>Исходные данные: IMP>1. уравнение кривой y=f(x). кривая непрерывная и дифференцируемая 2 раза. IMP>2. е — погрешность.
IMP>Нужно: описать эту кривую минимальным количеством точек (лежащих на этой кривой) с максимальной погрешностью e (для примера, данную операцию делает Unigraphics).
IMP>PS. в Unigraphics точки располагаются неравномерно по длине кривой и сгущаются в местах увеличения кривизны (замечено при построениях в Unigraphics)
речь про кусочно линейную интерполяцию? "описать кривую точками" — это может значить всё что угодно.
К.Ю. Богачев Практикум на ЭВМ. Методы приближения функций http://2x5best.3dn.ru/load/9-1-0-18
страница 44
формула максимального шага:
e <= 1/8 *h^2 *|f''|
|f''| — норма на непрерывных функциях (максимум).
Это близко к тому что требуется. (связь погрешности и шага ), но явного алгоритма минимизации там нет.
Здравствуйте, i.m.p, Вы писали:
IMP>Помогите решить задачку.
IMP>Исходные данные: IMP>1. уравнение кривой y=f(x). кривая непрерывная и дифференцируемая 2 раза. IMP>2. е — погрешность.
IMP>Нужно: описать эту кривую минимальным количеством точек (лежащих на этой кривой) с максимальной погрешностью e (для примера, данную операцию делает Unigraphics).
IMP>PS. в Unigraphics точки располагаются неравномерно по длине кривой и сгущаются в местах увеличения кривизны (замечено при построениях в Unigraphics)
Disclaimer. Ни в коей мере не претендую на оптимальность или хотя бы правильность предлагаемого ниже подхода. Это не решение, а так, усталые пятничные мысли в направлении сабжа.
Прежде всего, я бы, наверное, по возможности перешёл к естественной (aka натуральной) параметризации кривой от греха подальше, так как в этом случае кривизна выразится просто как вторая производная (ну или её модуль, если угодно). В общем же случае пришлось бы формулы какие-то вспоминать — оно нам надо, в пятницу-то?
Задачу можно попробовать решать стохастически — генерировать случайные точки на кривой. В качестве целевого распределения для датчика случайных чисел неплохо бы использовать вторую производную твоей функции (ну там пронормировав предварительно). Профит в чём: величина второй производной по модулю равна кривизне исходной кривой. А нам надо, видимо, накидать побольше точек как раз туда, где кривая сильнее изгибается.
Далее я как-нибудь итерационно увеличивал бы количество точек так, чтобы интерполяционный многочлен Лагранжа был «похож» на исходную функцию в смысле пространства L₂ или что-то вроде.
Скорее всего, всё вышеизложенное жутко наивно и вообще профанация, так что лучше просто взять учебник по численным методам.
Здравствуйте, i.m.p, Вы писали:
IMP>Нужно: описать эту кривую минимальным количеством точек (лежащих на этой кривой) с максимальной погрешностью e (для примера, данную операцию делает Unigraphics).
Здравствуйте, i.m.p, Вы писали:
IMP>Помогите решить задачку.
IMP>Исходные данные: IMP>1. уравнение кривой y=f(x). кривая непрерывная и дифференцируемая 2 раза. IMP>2. е — погрешность.
IMP>Нужно: описать эту кривую минимальным количеством точек (лежащих на этой кривой) с максимальной погрешностью e (для примера, данную операцию делает Unigraphics).
IMP>PS. в Unigraphics точки располагаются неравномерно по длине кривой и сгущаются в местах увеличения кривизны (замечено при построениях в Unigraphics)
Придумай какую нибудь строго монотонную функцию зависящую от параметра Твоей кривой и имеющую производную тем больше чем сильнее меняется кривизна
Например что нибуть типа интеграла от модуля второй производной.
Точки при численном вычислении этой функции можешь взять через равный параметр
Для вычисление нужного Тебе распределения параметров воздействуй на равномерное распределение этих параметров обратной функцией
Здравствуйте, MBo, Вы писали:
MBo>Здравствуйте, i.m.p, Вы писали:
IMP>>Нужно: описать эту кривую минимальным количеством точек (лежащих на этой кривой) с максимальной погрешностью e (для примера, данную операцию делает Unigraphics).
