Есть такая задача. Есть некоторая функция z=f(x,y) на какомто прямоугольнике. есть эпсилон. надо разбить этот прямоугольник на какието меньшие прямоугольники так чтобы ошибка аппроксимации этой функции плоскостями на этих прямоугольниках была не больше эпсилон причем количество этих меньших прямоугольников должно быть как можно меньше (т.е. сетка неравномерная)
Есть какая литература на эту тему? а то вообще не знаю с какой стороны подступиться.
Функция достаточно хорошая т.е. производные посчитать можно.
но как выбрать оптимальное или почти оптимальное разбиение- не представляю

1. Задача разбивания области на многоугольники сама по себе сложная. Нерешённая в целом ряде случаев и приложений.
2. На прямоугольнике, если он получен, приближающая функцию плоскость строится методом наименьших квадратов.
Больше не знаю.

черт. не думал что так сложно. думал такие задачи уже решены. видел видео повышения детализации в зависимости от степени близости объекта. просто подумал что она там именно как я написал. но видимо там просто разномасштабные равномерные сетки. но это не очень интересное решение)

Ничего сложного здесь нет, если правильно выбрать критерий оптимальности. Если у вас есть некоторый епсилон, к которому нужно стремиться, то криетрием оптимальности будет относительная разность невязки функции на сетке и непрерывной функции. Чтобы эту разность посчитать нужно задаться некоторой метрикой или нормой. В общем случае подходящая норма зависит от пространства в котором вы работаете с функцией (не зная функцию ничего сказать невозможно) и некоторых условий (дифференцируемость, гладкость, непрерывность, область определения, векторая функция или скалярная...). Я полагаю ваша функция гладкая и, как вы сказали, дифференцируема. Поэтому можно задаться обычной L2-norm (google it). 

Осталось только выработать критерий по которому сетку нужно измельчать (refining) или укрупнять (coarsening). Опять же критерий этот зависит от вашей функции. Если функция скалярная, то возьмите в качестве критерия её производную в точке по направлениям, другими словами градиент функции. Если градиент большой в некоторой точки, то соответственно функция меняется быстро и требуется более мелкая сетка, чтобы с большей точностью аппроксимировать функцию. 

На практике это будет итеративная процедура типа:
1.    Задаётесь начальной сеткой
2.    Считаете производные функции в центрах прямоугольников (или на гранях или на вершинах...)
3.    Считаете относительную невязку
4.    Если больше епсилон, выбираете некоторые процент прямоугольников (например 50%) в которых производная наибольшая и разбиваете каждый на 4ре более мелких прямоугольника. Переходите на шаг 2.


Это сообщение отредактировал(а) W4FhLF - 4.6.2012, 10:31

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

Вы бы всё-таки описали задачу, где возникла такая необходимость и что представляет из себя ваша функция? Можно было бы отправить вас в гугл с запросом "adaptive mesh refinement", но боюсь вы быстро заблудитесь. 

Прямоугольники не думаю, что проще на самом деле. Если в общем случае. Во всяком случае когда речь зайдёт о реализации, то треугольники тут в выигрыше, т.к. существуют универсальные библиотеки типа netgen и tetgen. 

Это сообщение отредактировал(а) W4FhLF - 4.6.2012, 13:39

откуда взял? - посмотрел на утубе видео по тесселяции на новых видюхах. видимо еще студенчество не полностью выветрилось. тянет на приключения) дибильные задачи на автомате в голову лезут) хочу мир перевернуть
а за "adaptive mesh refinement" - спасибо! отлично. почти то что я и хотел. почитаю и может добью в той формулировке что сам себе придумал)

tt0100, если задача просто аппроксимировать какую-то функцию (заданную аналитически) с некоторой точностью, то вы не в том направлении пошли. Здесь уместнее подход реализованный, например, в пакете: http://www2.maths.ox.ac.uk/chebfun/

... чебышев? не. он одномерный вроде.
скорее это как еслибы я захотел одномерную аналитическую функцию аппроксимировать б-сплайном с наименьшим числом узлов. ну или просто набором прямых. собственно я про почти прямые - про плоскости думал)
+ не люблю полиномы больших степеней - они на практике для большого количества вычислений неудобны - скорость быстро падает. в лоб - если не использовать библиотеки повышенной точности - точность только для разовых вычислений норм. если 10-20 тыс - уже заметно.
если кос акос (для чебышева) - тоже медленно. хотя может и не так как с в лоб