Фрактальная интерполяция

[vlad_light]

Здравствуйте!
Мне по теме курсовой нужно разобраться в фрактальной интерполяции(аппроксимации).
В литературе, которую я читал, существуют 2 варианта задания фрактальных интерполяционных функций:
$T^{(on)} x \to f, n \to \infty$ - где x - любая функция.
$W^{(on)} (X) \to A, n \to \infty$ - где Х - любое множество.
Мне нужно придумать оператор Т для функции $x^2, x \in [0,1]$, либо оператор W для множества $\{(x,x^2) | x \in [0,1]\}$.
В качестве набора точек можно взять любые 3 точки из $[0,1]$, например: $\{(0,0),(0.5,0.25),(1,1)\}$
Функция $T^{(on)} x$ не обязательно должна быть непрерывной, но должна проходить через набор точек.
Вскоре выложу свои наработки, а пока прошу посоветовать что-либо по данному вопросу, либо привести похожий пример.
Заранее спасибо!

[vlad_light]

1 Часть
У нас есть функция $f(x)=x^2$ на отрезке $x\in[0,1]$ и набор точек: $\{(0,0),(0.5,0.25),(1,1),\}$.
$\omega_n\left( \begin{array}{cc} x \\ y \end{array} \right)=\left( \begin{array}{cc} a_n & 0 \\ c_n & d_n \end{array} \right)\left( \begin{array}{cc} x \\ y \end{array} \right)+\left( \begin{array}{cc} e_n \\ f_n \end{array} \right)$
Оператор $\omega_n$ будет оператором сжатия при $0\le d_n < 1$. Тогда оператор $W(G)=\cup_{n=1}^N \omega_n(G), G \in H(\mathbb R^2)$ также будет оператором сжатия.
Тогда, согласно т. Банаха, существует единственная неподвижная точка оператора $W(G^*)=G^*$. Более того: $\forall G \in H(\mathbb R^2) : W^{(on)}(G)=G^*$, где $H(\mathbb R^2)$ - множество всех компактов $\mathbb R^2$, а $W^{(on)}(G)=W(W^{(on-1)}(G))$ - n-ая итерация оператора W.
$G:=\{(x,x^2)|x \in [0,1]\}$ - график ф-ции $x^2$ на отрезке [0,1].
Задача: найти оператор W для нашего множества G такой, чтоб: $W(G)=G$.
2 Часть
Мы выбираем:
1) Разбиение $\lambda =\{a=x_0<...<x_n=b\}$
2)Набор точек: $a\le \alpha_i<\beta_i \le b$
3)набор биекций $\phi_i:[\alpha_i,\beta_i] \to [x_{i-1},x_i]$
4)набор равномерных по первой переменной отображений, который удовлетворяют условию Липшица по второй переменной: $\psi_i \in C([a,b]\times \mathbb R),|\psi_i(x,y_1)-\psi_i(x,y_2) |\le d_i |y_1 - y_2| $
$I_i:=[x_{i-1},x_i)$
Тогда фрактальный оператор выглядит так:
$(Tf)(x)=\sum_{i=1}^n \psi_i (\phi_i^{-1}(x),f(\phi_i^{-1}(x))) \cdot \mathbb {I}_{I_i}(x)$, где $x \in [a,b], f \in X -$ метрическое пространство функций.
Задача: найти оператор Т для нашей функции $f(x)=x^2$.

Данные две задачи эквивалентны. Нужно разобраться хотя бы в одной из них.
Вопросы:
По 1-ой части: каким образом мы подбираем коэффициенты $n,a_n,c_n,e_n,f_n$. Также я не знаю, как выглядят функции множеств (например W(G)). С такими я сталкивался только при изучении интеграла Лебега, но ничего общего с этими я не нашёл. Также хотел бы увидеть аналогичный пример другой функции, например $sin x$ на $[0,\frac{\pi}{2}]$.
По 2-ой части: каким образом мы выбираем данные из пунктов 2)-4) ? Также желателен какой-нибудь пример такого оператора.

Очень прошу намекнуть, в какую сторону думать, потому что литература по этому вопросу достаточно однообразная и приведённые в ней примеры я не понимаю

[mkot]

vlad_light в сообщении #420743 писал(а):

1 Часть
У нас есть функция $f(x)=x^2$ на отрезке $x\in[0,1]$ и набор точек: $\{(0,0),(0.5,0.25),(1,1),\}$.
$\omega_n\left( \begin{array}{cc} x \\ y \end{array} \right)=\left( \begin{array}{cc} a_n & 0 \\ c_n & d_n \end{array} \right)\left( \begin{array}{cc} x \\ y \end{array} \right)+\left( \begin{array}{cc} e_n \\ f_n \end{array} \right)$

Функции $w_n$ они же не абы какие, а с вполне понятными условиями.
Пусть у вас для определённости будет $N +1$ точка
$(x_0, y_0), (x_1, y_1), \ldots, (x_N, y_N)$, тогда функций $w_n$ будет $N$
штук: $w_1, \ldots, w_N$, и
на всех их нужно наложить условия:
$w_n\left(\begin{array}{c}x_0 \\ y_0 \end{array}\left) = \left(\begin{array}{c}x_{n-1} \\ y_{n-1} \end{array}\right)$,

$w_n\left(\begin{array}{c}x_N \\ y_N \end{array}\left) = \left(\begin{array}{c}x_{n} \\ y_{n} \end{array}\right)$.

Таким образом вы получаете по четыре уравнения на $a_n, c_n, d_n, e_n, f_n$. Т. о. $a_n, c_n, e_n, f_n$ можно выразить через $d_n$,
$d_n$ считать свободным параметром, требуя от него только $|d_n| < 1$.

Ну и всё, далее очевидным образом конструируется сжимающий оператор.

(Оффтоп)

(Хотя с этим не сталкивался, может и ошибаюсь).

[vlad_light]

Спасибо за ответ!
Допустим, мы определим коэффициенты таким образом:
$a_n=\frac{x_n-x_{n-1}}{x_N-x_0}$
$e_n=\frac{x_Nx_{n-1}-x_0x_n}{x_N-x_0}$
$c_n=\frac{y_n-y_{n-1}}{x_N-x_0} - d_n\frac{y_N-y_0}{x_N-x_0}$
$f_n=\frac{x_Ny_{n-1}-x_0y_n}{x_N-x_0} - d_n\frac{x_Ny_0-x_0y_N}{x_N-x_0}$
При таких условиях будет сохраняться непрерывность функции. Выпишем коэффициенты для нашего прмера:
$a_1=0.5 \ \ \ \ \ \ \ \ \ a_2=0.5 $
$e_1=0 \ \ \ \ \ \ \ \ \ \ \ \ e_2=0.5$
$c_1=0.25-d_1 \ \ c_2=0.75-d_2$
$f_1=0 \ \ \ \ \ \ \ \ \ \ \ f_2=0.25$
$\omega_1\left( \begin{array}{cc} x \\ y \end{array} \right)=\left( \begin{array}{cc} 0.5 & 0 \\ 0.25-d_1 & d_1 \end{array} \right) \left( \begin{array}{cc} x \\ y \end{array} \right)$
$\omega_2\left( \begin{array}{cc} x \\ y \end{array} \right)=\left( \begin{array}{cc} 0.5 & 0 \\ 0.75-d_2 & d_2 \end{array} \right) \left( \begin{array}{cc} x \\ y \end{array} \right)+ \left( \begin{array}{cc} 0.5 \\ 0.25 \end{array} \right)$
Тогда у нас существует единственное компактное множество $G^*=\{(x,f(x)|x \in [0,1])\}$ такое, что $W(G^*)=\omega_1(G^*) \cup \omega_2(G^*)=G^*$ и для любого $G \in \mathcal H(\mathbb R^2)$ - множество всех компактов $\mathbb R^2$ будет выполняться условие: $W^{(on)}(G) \to G^*, n \to \infty$, а функция $f(x)$ из множества $G^*$ будет называться фрактальной интерполирующей функцией.
Тогда наш оператор $W(G), G \in \mathcal H(\mathbb R^2)$ будет задаваться набором 8 чисел.
Если то, что я написал - правильно, тогда есть ещё пару вопросов:
1. Пускай $W^{(on)}(G):=\{(x,f_{(n)}(x))|x \in [a,b]\}, n<\infty$, G^*:=\{(x,f(x))|x \in [a,b]\}. Вопрос: связаны ли коэффициенты $d_k, k = \overline{1,N}$ с величиной наилучшего приближения $||f-f_{(n)}||_{C[a,b]}=\max\limits_{x \in [a,b]} |f(x)-f_{(n)}(x)|$ или она зависит только от $n$, т.е. имеет ли смысл писать $||f-f_{(n)}||_{C[a,b]}=\min\limits_{|d_k|<1, k=\overline{1,N}}\max\limits_{x \in [a,b]} |f(x)-f_{(n)}(x)|$. Если да - то как, если нет - то зачем нужны эти коэффициенты?
(Я знаю, что при $d_k=0$ график функции $f_{(n)}(x)$ становится кусочно-линейным. Чем ближе $d_k$ к 1, тем меньше деформируется(выравнивается) первоначальная функция. Правильно ли то, что величина наилучшего приближения будет меньше при увеличении $d_k<1$, если первоначальная функция похожа на $f(x)$ и как связать степень "похожести" с коэффициентами $d_k$?)
2. Как выглядит аппроксимирующая функция? Можно ли её получить из интерполирующей?
Заранее спасибо за ответы!

[mkot]

vlad_light в сообщении #421064 писал(а):

При таких условиях будет сохраняться непрерывность функции. Выпишем коэффициенты для нашего прмера:
$a_1=0.5 \ \ \ \ \ \ \ \ \ a_2=0.5 $
$e_1=0 \ \ \ \ \ \ \ \ \ \ \ \ e_2=0.5$
$c_1=0.25-d_1 \ \ c_2=0.75-d_2$
$f_1=0 \ \ \ \ \ \ \ \ \ \ \ f_2=0.25$
$\omega_1\left( \begin{array}{cc} x \\ y \end{array} \right)=\left( \begin{array}{cc} 0.5 & 0 \\ 0.25-d_1 & d_1 \end{array} \right) \left( \begin{array}{cc} x \\ y \end{array} \right)$
$\omega_2\left( \begin{array}{cc} x \\ y \end{array} \right)=\left( \begin{array}{cc} 0.5 & 0 \\ 0.75-d_2 & d_2 \end{array} \right) \left( \begin{array}{cc} x \\ y \end{array} \right)+ \left( \begin{array}{cc} 0.5 \\ 0.25 \end{array} \right)$

Хммм... вам же нужно для фунции $f(x) = x^2$. Несложно убедиться, тогда
что $d_1=\frac14$, $d_2=\frac14$.

[vlad_light]

Ммм... А откуда Вы взяли $\frac{1}{4}$? Объясните подробнее, пожалуйста.
А остальное всё я правильно написал?

[mkot]

vlad_light в сообщении #421180 писал(а):

Ммм... А откуда Вы взяли $\frac{1}{4}$? Объясните подробнее, пожалуйста.

Я просто подставил точку $(x, x^2)$ в $w_1$ и $w_2$ и потребовал, чтобы она перешла в точку на графике функции $f(x) = x^2$, то есть в точку вида $(\mbox{что-то}, \mbox{что-то}^2)$.

Зачем нужны коэффициенты d_k? Нуууу, на сколька я понимаю, они влияют на фрактальную размерность полученного графика. То есть функция-то как правило не известна, известен только набор пар чисел, и известно также какой фрактальной размерности должен получиться результат, исходя из этого и выбирают. Но не буду вас запутывать, посмотрите лучше в книге Майкла Барнсли (M. Barnsley Fractals Everywhere), книгу легко можно найти, и там, по-моему, много про это сказано.

[vlad_light]

Спасибо, я разобрался!
А по аппроксимации можете что-то подсказать, потому что в книге Барнсли(по которой я как раз и изучаю эту тему) написано только про интерполяцию. И на сколько отличаются фрактальная аппроксимация от $C[a,b]$(полиномами, тригонометрическими полиномами)?

[mkot]

vlad_light в сообщении #421317 писал(а):

А по аппроксимации можете что-то подсказать, потому что в книге Барнсли(по которой я как раз и изучаю эту тему) написано только про интерполяцию. И на сколько отличаются фрактальная аппроксимация от $C[a,b]$(полиномами, тригонометрическими полиномами)?

Тут я вам уже не подскажу.

[Circiter]

2vlad_light

Цитата:

И на сколько отличаются фрактальная аппроксимация от $C[a,b]$(полиномами, тригонометрическими полиномами)?

Преимущество фрактального приближения заключается в том, что этот метод, скажем так, обладает "творческим" потенциалом и может эксплуатировать самоподобность аппроксимируемого объекта для "дорисовывания" деталей, которые другие методы приближения предсказывают плохо.

Других достоинств, вроде как и нет... Достаточно заметить, что фрактальная интерполяция для своих внутренних нужд может использовать, например, полиномиальную интерполяцию; к тому же, процесс восстановления объекта по его компактному описанию носит итеративный характер, что тоже не всегда хорошо...

Ещё добавлю, по вашей "второй части" (хотя, надеюсь, что вы и сами уже во всем разобрались). Вы спрашивали, как именно выбираются точки для разбиений и как выбираются те функции. Вроде бы, все это задается a priori, и уже потом вы при конструировании компактного описания (т.е. самого фрактального оператора, итерации которого сходятся к аппроксимируемому объекту) выбираете какую функцию к чему применить руководствуясь стремлением к наибольшей похожести исходных данных на их образ от первой итерации фрактального оператора (при интерполяции добиваются не просто наибольшей похожести, а полной неподвижности узлов интерполяции относительно действия этого оператора). В общем здесь квадратичный по времени перебор виден + определение похожести в некоторой метрике (например, в хаусдорфовой, для тяжелых случаев).

Как-то так... :) Наверное, в этом смысле, ваша "первая часть" была интересней.

[vlad_light]

Спасибо за ответ! Ещё пару вопросов возникло)
1. Неужели в мире так много вещей, которые состоят из деталей себе подобных? Мне говорили, что фракталами хорошо оценивать негладкие объекты (в отличии от $C[a,b]$). Например, единичный квадрат полиномами аппроксимировать плохо. Приведите, пожалуйста, пример аппроксимации квадрата фракталами.
2. Мне известно, что фракталы используют для сжатия данных, например изображений. В этом случае нам более важно компактное описание оператора, чем скорость сжатия (хотя я не понимаю, зачем, с точки зрения программирования, жертвовать скоростью ради объёма). Также я слышал, что фракталы используются для прогнозирования результатов

(Оффтоп)

(насколько я помню, этот метод называется экстерполяция)

например на биржевых рынках. Здесь также прошу привести пример применения фракталов (можно без расчётов).
3. Во второй части я не разобрался Я не понимаю, как выбирать функцию, руководствуясь стремлением к похожести наших данных? Квадратичный перебор, т.е. такую задачу имеет смысл решать только с помощью компьютера? Если нет - то приведите, пожалуйста, соотвествующий пример.
Спасибо!

[Circiter]

2vlad_light

Цитата:

Неужели в мире так много вещей, которые состоят из деталей себе подобных?

Настоящих фрактальных объектов очень мало. Поэтому подобрать (построить) нетривиальный сжимающий оператор, оставляющий приближаемый объект неподвижным или очень похожим на оригинальную версию, вообще говоря, невозможно. По этой причине объект дробят на блоки двумя способами -- на мелкие непересекающиеся и на крупные частично перекрывающиеся, а потом пытаются найти похожие блоки. Ищутся соответствия "большой блок / маленький блок". Здесь существенно, что один из сопоставляемых блоков больше, ведь отображение, делающие большой блок похожим на маленький блок в таком случае будет сжимающим, а это нужно для существования неподвижной точки.

Раз уж вы упомянули сжатие изображений, то попробую объяснит на примере фрактальной обработки картинки. Допустим у вас есть игра-мозаика. В ней есть коробка с фрагментами (словарь) и эталонная картинка, которую вы пытаетесь собрать из доступных вам кусочков. При фрактальном кодировании фрагменты не даются вам заранее, а извлекаются из самого эталонного изображения, деформируются и кладутся на новое место. Лишь-бы в результате получилась та-же картинка.

И вот здесь-то и заключена магия -- раз словарь формируется динамически из эталонного объекта, то во фрактальном описании должны быть лишь команды вроде "взять большой кусочек с такими координатами, отразить слева-направо, скукожить, сделать более зеленым и положить на новые координаты" (набор возможных операций обычно ограничен всего несколькими самыми ходовыми функциями). То есть сами данные хранить не надо, только команды (они занимают меньше места чем пиксели изображения и на этом основано сжатие). Если все эти инструкции выполнять над эталонной картинкой, то получится она же самая (она является неподвижной точкой).

Такой набор инструкции сам по себе не единственен, но его можно немного преобразовать и получить что-то типа сигнатуры картинки. Это может применяться при распознавании образов. То есть при поиске картинки в базе данных просто путем сравнения сигнатур фрактальных кодов.

Однако, вернемся к основной теме. Нам известно, что конструктивные теоремы о неподвижной точке для сжимающих отображений утверждают не только существование неподвижной точки, но и говорят о её уникальности и даже предлагают рецепт её нахождения путем многократного применения инструкций (итерирования фрактального оператора) начиная с произвольной картинки. Т.е. если мы построили фрактальное описание пингвина, то мы получим картинку пингвина, даже если начнем итерации с картинки хомяка. Причем, если мы начнем с картинки похожей на пингвина, то уже после первой итерации получим изображение очень близкое к оригиналу, а вот одна итерация на хомяке даст мусор; это опять же можно использовать для распознавания образов.

Опять отвлекся. Итак, фрактальный декомпрессор восстанавливает оригинальный объект, но он не знает размеров исходного изображения и поэтому его можно обмануть, сообщив завышенные размеры. Теорема о неподвижной точке все-равно сработает и фрактальный декомпрессор все-равно выдаст исходную картинку (затратив больше итераций, то есть проработав больше времени). При этом ему придется дорисовать недостающие детали, это используется при фрактальном фотоулучшении. Именно на этом основана фрактальная интерполяция/аппроксимация.

Вы видимо легко сможете подобрать примеры изображений, в которых найдется маленький кусоче, который не похож ни на один большой кусок той-же картинки. Возьмем классический пример со знаком бесконечности ($\infty$): в центральной части линии пересекаются и этот крестик не похож ни на один другой блок изображения знака бесконечность. Это не создает проблем в задачах распознавания, но неприемлемо в задачах интерполяции и сжатия. Для решения такой проблемы применяют иерархическое подразбиение нехороших блоков. В примере со знаком бесконечность мы можем поделить крестик на четыре части, каждая из которых легко сопоставляется с другими участками всей картинки.

Цитата:

зачем, с точки зрения программирования, жертвовать скоростью ради объёма

Подумайте о сжатии видео. :)

Цитата:

Также я слышал, что фракталы используются для прогнозирования результатов

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

Цитата:

Приведите, пожалуйста, пример аппроксимации квадрата фракталами.

Извините, лень. Принцип я объяснил. К настоящим фракталам эта задача отношения почти не имеет.

Цитата:

Квадратичный перебор, т.е. такую задачу имеет смысл решать только с помощью компьютера?

Даже для компьютера это сложно.

Цитата:

Я не понимаю, как выбирать функцию, руководствуясь стремлением к похожести наших данных?

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

P.S.: Есть ещё один, альтернативный способ фрактальной аппроксимации. Берется какой-нибудь известный фрактал (e.g., множество Мандельброта), режется на куски, и уже из этих кусков собирается эталонный объект.

-- Сб мар 12, 2011 01:50:02 --

Ссылки могу такие дать (на тему фрактальной интерполяции в 1D):
W.O.Cochran, J.C.Hart, P.J.Flynn, On Approximating Rough Curves with Fractal Functions;
E.Guerin, E.Tosan, A.Baskurt, A Fractal Approximation of Curves.

[Circiter]

Попробовал самостоятельно повторить ваш путь с ручной интерполяцией функции $x\mapsto x^2$, просто интереса ради; но потом стало лень и задумку я до конца не довел. Зато я попробую показать связь между тем, что я писал ранее и вашим способом с матрицами. Потом я ещё несколько слов об аппроксимации скажу.

Итак, имеется функция $f\colon[0;\ 1]\to\mathbb{R}$, график которой играет роль эталонного объекта. Значения функции известны в точках $x_1=0$, $x_2=0,5$, $x_3=1$ и равны соответственно $f(x_1)=0$, $f(x_2)=0.25$, $f(x_3)=1$.

Базисом фрактального интерполянта выбирается набор сжимающих функций $\omega_i\colon[0;\ 1]\times\mathbb{R}\to[0;\ 1]\times\mathbb{R}$.

Теперь мы делим область определения эталонной функции (а область эта сейчас равна $[0;\ 1]$) на подотрезки двумя способами -- на маленькие неперекрывающиеся (например, разбиваем область определения на отрезки серией точек) и на большие, возможно, перекрывающиеся. Перебираем все маленькие подотрезки и для каждого ищем такой большой подотрезок, что под действием одной из $\omega_i$ соответствующий кусок графика эталонной функции $f$ становится похож (близок в некоторой метрике) на кусок графика, соотвующий текущему маленькому подотрезку (а лучше равен ему). N.B., хотя каждая $\omega_i$ преобразует всего одну точку графика, но мы предполагаем, что эту функцию можно применить и к куску графика, т.е., сразу ко всем его точкам по-очереди.

Тот способ, который вы использовали ранее является в точности частным случаем только что описанного. В качестве функций $\omega_i$ вы брали сжимающие аффинные функции (вам хватило двух), т.е. композиции линейного преобразования (умножения на матрицу) и сдвига (сложения с вектором), потом накладывали на них некоторые естественные ограничения, описывающие поведение функций на границах подотрезков и позволявшие решая системы уравнений отыскать нужные коэффициенты (один коэффициент все-равно оставался лишним и играл роль управляющего параметра, контролируещего аккуратность аппроксимации). То есть вы не подбирали функции, а вычисляли их. Ну и наконец, делили область определения функции на маленькие участки, пользуясь контрольными точками интерполяции, а деление на большие подотрезки и вовсе не производили, считая, что большой подотрезок у вас всего один и совпадает со всем $[0;\ 1]$.

Другими словами, вы пытались приблизить каждый подотрезок сразу всем графиком. В результате у вас получился искомый интерполянт $W(\cdot)=\omega_1(\cdot)\cup\omega_2(\cdot)$. Его можно применить поточечно (возможно с прореживанием) к графику любой функции (например к $x\mapsto x$), потом ещё раз применить тот же оператор к результату предыдущей итерации и т.д. Через парочку итераций должен начать вырисовываться график $f$ (я не пробовал, но позже попытаюсь).

Теперь можно попробовать сформулировать отличия фрактальной интерполяции от фрактальной аппроксимации более точно. Вспомним ваш алгоритм. Делим область определения на маленькие неперескающиеся участки, подыскиваем для них похожие большие области и вычисляем функции (подбираем коэффициенты), преобразующие подходящий большой блок в текущий маленький. В результате, для каждого маленького блока получается своя аффинная функция, т.е. по одной функции на каждый участок. Если в качестве такого участка выбран отрезок между соседними узлами (коих всего $n+1$), то у нас окажется $n$ сжимающих функций. Думаю, что именно такая точная притирка и характеризует именно интерполяцию.

Можно считать, что вы не вычисляли функции $\omega_i$, а выбирали их, но из всего класса аффинных сжимающих преобразований нужной размерности. А вот когда этот класс функций существенно ограничен, вот тогда и получается задача не интерполяции, но задача аппроксимации. Да, скорее всего, различия именно таковы (кроме того, от аппроксимации не требуют точности в узлах). Понятно, что раз у нас нет в этом более общем случае возможности точно подобрать функцию, такую, что для участка графика, соответсвующего малому подотрезку, --- обозначим этот кусок графика как $A$, --- и участка графика, соответствующего большому подотрезку, --- обозначим этот кусок графика как $B$, --- выполняется $A=\omega_i(B)$, то, как я и говорил в предудщих сообщениях, мы вынуждены искать (подбирать) функцию, минимизирующую разницу между $A$ и $\omega_i(B)$. То есть приходится минимизировать $\|A-\omega_i(B)\|\to\min$.

Более точно, для каждого малого участка $A_i$ мы ищем $\omega$ и $B$ такие, что $\rho(A_i,\ \omega(B))=\min\limits_{j,\ k}\rho(A_i,\ \omega_j(B_k))$, где $\rho$ - некоторая метрика (или равномерная или хаусдорфова, или ещё какая). Обычно для этих целей, по крайней мере в задачах фрактальной компрессии, юзают МНК.

В общем, если я какие-то ошибки допускаю, поправьте. Ну и хотелось бы узнать, получилось ли у вас воссоздать ветку параболы итерированием полученных вами функций $\omega_1,\ \omega_2$...

[vlad_light]

Да, получилось. Теперь интерполирую функцию $f(x)=x^n, x \in [0,1], n \in \mathbb N; M=\{(0,0),(\frac{1}{2}, \frac{1}{2^n}),(1,1)\}$.
Преобразования $\omega_i$ у меня получились такими:
$\omega_1 \left( \begin{array}{cc} x \\ y \end{array} \right)= \left( \begin{array}{cc} \frac{1}{2} & 0 \\ \frac{1}{2^n}-d_1 & d_1 \end{array} \right)\left( \begin{array}{cc} x \\ y \end{array} \right)$
$\omega_2 \left( \begin{array}{cc} x \\ y \end{array} \right)= \left( \begin{array}{cc} \frac{1}{2} & 0 \\ 1- \frac{1}{2^n}-d_2 & d_2 \end{array} \right)\left( \begin{array}{cc} x \\ y \end{array} \right)+\left( \begin{array}{cc} \frac{1}{2} \\ \frac{1}{2^n} \end{array} \right)$
Подставим точку $(x,x^n)$ в $\omega_1$.Тогда, очевидно, $d_1:=\frac{1}{2^n}$:
$$\omega_1 \left( \begin{array}{cc} x \\ x^n \end{array} \right)= \left( \begin{array}{cc} \frac{1}{2} & 0 \\ 0 & \frac{1}{2^n} \end{array} \right)\left( \begin{array}{cc} x \\ x^n \end{array} \right)=\left( \begin{array}{cc} \frac{1}{2}x \\ \frac{1}{2^n}x^n \end{array} \right)=\left( \begin{array}{cc} \frac{1}{2}x \\ (\frac{1}{2}x)^n \end{array} \right)$.
Тоже самое сделаем с $\omega_2$:
$\omega_2 \left( \begin{array}{cc} x \\ x^n \end{array} \right)= \left( \begin{array}{cc} \frac{1}{2} & 0 \\ 1- \frac{1}{2^n}-d_2 & d_2 \end{array} \right)\left( \begin{array}{cc} x \\ x^n \end{array} \right)+\left( \begin{array}{cc} \frac{1}{2} \\ \frac{1}{2^n} \end{array} \right)=\left( \begin{array}{cc} \frac{1}{2}x+\frac{1}{2} \\ (1-\frac{1}{2^n}-d_2)x+d_2x^n+\frac{1}{2^n} \end{array} \right)$
Очевидно, что $(1-\frac{1}{2^n}-d_2)x+d_2x^n+\frac{1}{2^n} \neq (\frac{1}{2}x+\frac{1}{2})^n$ для $\forall x \in [0,1]$
Помогите, пожалуйста, найти величину:
$\mathbf E(g_{d_2}(x))=\inf\limits_{d_2 \in \mathbb R} \max\limits_{x \in [0,1]} |(1-\frac{1}{2^n}-d_2)x+d_2x^n+\frac{1}{2^n}-\frac{1}{2^n}\sum\limits_{k=0}^nC_n^kx^k|$=?
Я делал так:
$d_2:=1-\frac{1}{2^n} \Rightarrow \mathbf E(g_{d_2}(x))=\max\limits_{x \in [0,1]} |(1-\frac{1}{2^n})x^n+\frac{1}{2^n}-\frac{1}{2^n}\sum\limits_{k=0}^nC_n^kx^k|=\\ =|(1-\frac{1}{2^n})1^n+\frac{1}{2^n}-\frac{1}{2^n}\sum\limits_{k=0}^nC_n^k1^k|=|1-\frac{1}{2^n}+\frac{1}{2^n}-\frac{2^n}{2^n}|=0$
Вопрос: где я ошибся?

(Оффтоп)

Подозреваю, что неправильно раскрыл максимум... Помогите раскрыть правильно)

[vlad_light]

В предыдущем примере имеет смысл рассматривать $|d_2|<1+\epsilon$
Расскажите, пожалуйста, как вообще минимизировать функционал
$\matbf {E}(g_d(x,f(x)))=\inf\limits_d ||g_d(x,\widetilde f(x))-\widetilde{f}(Ax+B)||_{\mathbb X}$, где $A,B \in \mathbb R$ - заданы, $g_d(x,\widetilde f(x))$ - ф-ция, зависящая от $x \in [a,b], \widetilde f(x) \in \mathbb D$ - компакт и $d \in [-1-\epsilon,1+\epsilon], \epsilon>0$, а $\widetilde{f}(x)$ - некоторая заданная функция из $\mathbb X$, $\mathbb X$ - нормированное пространство, в нашем случае $C([a,b])$, но я думаю, что подойдёт и $L_p([a,b])$.
Я догадываюсь, что руками это сделать сложно. Поэтому прошу либо дать ссылку, где это можно посчитать, либо написать какие-то (пускай и грубые) оценки.

(Оффтоп)

Оценка $|a+b| \leqslant |a|+|b|$ получается слишком грубой. Хотел бы увидеть что-то по-лучше.