О некоторых компонентах операционной среды интерполяции

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Орловский Государственный технический университет

О некоторых компонентах операционной среды интерполяции

Студент Правдин А.Л.

Main components of program tools for interpolation are suggested and discussed in this article.

В работе обсуждаются и предлагаются основные компоненты программных средств интерполяции.

Введение

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

В настоящей работе обсуждаются простейшие компоненты операционной среды интерполяции.

1. Требования и задачи

Традиционно интерполяция связана со следующими функциями [6-8]:

1) вычисление значений интерполяционных полиномов Лагранжа и интерполяционных тригонометрических полиномов в форме Гаусса по введенным данным;

2) нахождения ошибки (погрешности) при интерполировании;

3) языкового представления упомянутых полиномов: а) с индексированными переменными; б) в виде массива числовых значений;

4) экспорта текстовых файлов с информацией о виде полинома и исходных данных.

При организации интерактивного процесса к отмеченным функциям должны быть добавлены следующие возможности [9-12]:

5) автоматизированный ввод исходных данных с редактированием входных данных;

6) графическое представление интерполяционных полиномов;

7) автомасштабирование при графическом отображении;

8) назначение узлов интерполяции;

9) выбор координат точек и их свойств с использованием ресурса компьютера, в частности «мыши»;

10) контроль недопустимых значений;

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

12) сдвиг графика (с системой координат) по координатным осям;

13) раздельное масштабирование по координатным осям и простейшее авто- масштабирование.

14) ведение журнала действий и реализация механизма отката на основные операции с исходными данными.

Практический опыт работы показывает, что эффективность процесса машинного интерполирования во многом связана с наличием:

15) параллельного отображения элементарных функций при вводе и выводе;

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

17) возможности экспорта изображений в файлы с расширением «BMP» и экспорта и импорта исходных данных программы и её настроек в виде файлов с расширением «APX»;

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

2. Пути реализации требований.

Интерполяционная формула

В общем виде интерполирующая функция имеет следующий вид:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

где g(x) - некая образующая функция, (xi,yi) - координаты узловых точек, k - количество узловых точек (при g(x) x - полином Лагранжа).

Чтобы оптимизировать вычисления, можно один раз на каждую итерацию основного цикла по вычислению суммы производить одно (а не 2*k, для числителя и знаменателя) вычисление значений g(x) и g(xi). Очевидно, что следует учесть данную оптимизацию при построении реальных систем, так как время выполнения очень сильно зависит от количества узловых точек. Кроме того, уместен будет предварительный подсчёт всех значений g(xi), i=1,2…k и сохранение этих значений в основную структуру данных, либо, в параллельную основной. Это сократит время выполнения подсчёта значения функции, так как останутся только операции вычитания и умножения (наиболее быстрые аппаратно) и по одной операции деления на каждую итерацию цикла.

В простейшем случае можно проводить вычисления следующим образом. Общим для всех интерполяционных функций данного класса является цикл суммирования. Он вынесен отдельно. На каждом шаге значение накапливающего параметра увеличивается на величину, возвращаемую подпрограммой - функцией, в которую передаются текущее значение счётчика и абсцисса очередной узловой точки, помноженное на значение ординаты очередной узловой точки, в соответствии с формулой (1). Эти подпрограммы определены отдельно для каждого типа реализованных интерполяционных функций, так как различны для них. Каждая подпрограмма содержит в себе цикл, в котором параллельно (так, как число итераций равно) вычисляются два накапливающих мультипликативных параметра - числитель и знаменатель. После цикла числитель делится на знаменатель, возвращая значение функции - результат подпрограммы. Кроме того, для сокращения числа проверок (основного критерия сложности алгоритмов), имеет смысл проверять тип вычисляемой функции не на каждой итерации основного цикла, а перед его выполнением, что немного увеличивает объём кода.

Важным теоретическим моментом интерполяции следует считать назначение узлов интерполяции. Изначально, имеется некоторый набор входных данных. Из них следует выбрать те точки, которые наиболее важны (что определяется имперически, исходя из предметной области), и назначить их узловыми. Тогда по остальным можно будет ориентироваться в расчёте погрешности: насколько точно предложенная интерполяционная функция приближается к исходной последовательности данных. Это влечёт необходимость добавления в алгоритм построения функции проверок на вхождение очередной точки во множество узловых. Можно хранить узловые и не узловые точки в отдельных структурах: это значительно увеличит скорость вычислений.

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

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

Ввод данных.

Как известно, это самый рутинный этап работы. Основной инструмент точного ввода - заполнение таблицы. Изначально, пользователь указывает координаты точки и её роль: узел или нет. Выбирая точки в таблице можно изменять значения ранее введённых точек. Размер таблицы не фиксирован. Инструмент приближённого ввода - перетаскивание точек мышью. (Уместно было бы реализовать так же создание новой точки мышью). Этот инструмент довольно точен, так как: во-первых, логические координаты мыши (зависящие от текущих настроек масштабов и смещений) отображаются в специальном поле, удобно расположенном в области вывода; во-вторых, программой отображаются линейка и сетка. Очень удобна возможность отображения графика одной из шести основных элементарных функций. Во-первых, это даёт возможность перетащить точки на известные значения, во-вторых - сравнить полученную интерполяционную функцию с элементарной, что даёт важную на практике возможность - определить тот класс элементарных функций, которые лучше всего интерполируются той или иной функцией.

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

Вывод информации.

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

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

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

Кроме отмеченного важная нагрузка ложится на рабочие файлы программы, в которые она сохраняет данные и настройки. Следует добавить такую функцию как импорт и экспорт файлов, содержащих только координаты точек (импорт - множество изначально узловых точек и экспорт - значения интерполирующей функции через определённый шаг). Это, на первый взгляд простое дополнение, открывает важные возможности: повторную интерполяцию и простой ввод данных с физических устройств. Позже, повторную интерполяцию желательно реализовать, в том числе, без использования внешних файлов. Если возникнет такая необходимость, то для программы возможна разработка более сложного, чем условно названный `APX', формата, включающего данные, команды, настройки и отчёты.

Практика показывает важность использования операций с данными как возможности отмены действий [13-15]. Для этого необходимо запоминать тип очередной операции и сопряжённые с ней данные, которые утрачивались или изменялись на данном шаге. Для этого можно не менять структуру программы, если реализован механизм запоминания и восстановления информации и добавление вызовов нужных подпрограмм в обработчики событий работы с данными. В качестве развития можно предложить следующее. Во-первых, обеспечить визуальное представление действиям истории; во-вторых, реализовать экспорт истории (в том числе - события об ошибках, имена экспортируемых файлов, обязательное сохранение вида конечного полинома) в некоторый файл, реализовав, таким образом, полноценный механизм создания отчётов; в третьих - усовершенствовать структуру данных для хранения записей в истории (двусвязное кольцо, с указателями на объекты - экземпляры определенных классов - потомков абстрактного класса 'история').

программный операционный интерполяция

3. Структура программы

Как в любой программе, связанной с интерактивным выводом, основные функции связаны с перерисовкой, в данном случае, графиков интерполяторов. Однако изначально была выбрана такая декомпозиция программы [16,17], которая позволила модернизировать слабо-функциональный прототип в относительно удобную и функциональную систему. К основополагающим решениям следует отнести следующие: разделение подпрограмм на подпрограммы ввода данных и подпрограммы вывода (используя схему: ввод - модель - вывод); последовательная декомпозиция функций вывода, позволяющая, с одной стороны производить перерисовку вызовом одной команды, а с другой - возможность использования более детальных подпрограмм для реализации других иерархий; выделение преобразований координат (от экранных к внутренним и обратно).

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

Не смотря на удачную, в целом, структуру, остаётся проблема её дальнейшего развития, что естественно повлечёт её изменение. Новая структура программы для наибольшей расширяемости должна быть объектной. Поэтому, на основе объектного подхода может быть предложена модель [Рис. 1], отражающая взаимодействия классов объектов, содержащих реализацию различных функций системы. Так, например, абстрактный класс 'График', который содержит классы 'Графики элементарных' и 'Графики интерполяторов'. Для отображения можно создать неограниченное количество объектов - экземпляров данных классов, что, в сочетании с визуализацией и удобным доступом к параметрам каждого конкретного экземпляра даст пользователю мощный и точный инструмент. Если отображать апертуры в том числе и для графиков элементарных функций, что реализуется простым наследованием этой возможности из родительского класса 'График', то можно относительно просто сравнивать функции на приближённое соответствие. Если же требуется более точное решение, то отображение графика ошибки (тоже имеющего свои параметры, а следовательно, возможность экспорта, повторной интерполяции и т.д.) предоставит его.

Начальный вариант операционной среды интерполяции создан с использованием средств визуального программирования [18,19] в виде пакета программ Alex21soft_Aproxymator объёмом около 900 Кбайт.

Выводы

Экспериментальная проверка программной среды для организации процессов моделирования сложных функций показала удобство использования, простоту настройки программной системы и широту интерполяционных возможностей [Рис. 2].

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

Литература

1. Сергиенко А.Б. Цифровая обработка сигналов - Спб.: Питер, 2003. - 604 с.

2. Дьяконов В.П. MATLAB: учебный курс. - СПб: Питер, 2001. - 560 с.

3. Дьяконов В.П. Mathcad 8/2000: Специальный справочник. - СПб: Питер, 2001.-592 с.

4. Дьяконов В., Круглов В. Математические пакеты расширения MATLAB. Специальный справочник. - Спб.: Питер, 2001. - 592 с.

5. Гультяев А. Визуальное моделирование в среде MATLAB. - Спб.: Питер, 2001.-432 с.

6. Хемминг Р.В. Численные методы для научных работников и инженеров: Пер. с англ. /Под ред. Р.С. Гутера. - 2-е изд. - М.: Наука, 1972. - 400 с.

7. Ахиезер Н.И. Лекции по теории аппроксимации. -2-е изд.- М.: Наука, 1965 - 408 с.

8. Микеладзе Ш.Е. Численные методы математического анализа. - М.: Гос. изд. тех.-теоретич. лит., 1953. - 528 с.

9. Раков В.И. Базовые формулы приближения с производными при моделировании сигналов. // Совр. пробл. строит. материаловед.: Матер. пятых акад. чт. РААСН/Воронеж. ВГАСА. - Воронеж, 1999. - С.357-362.

10. Раков В.И. О границах автоматизации процессов моделирования нелинейностей. // Совр. пробл. строит. материаловедения: Материалы Седьмых академ. чтений РААСН / БелГТАСМ. - Белгород, 2001. - Ч.2. - С.249-254.

11. Раков В.И. К обоснованию необходимости применения средств интерактивной аппроксимации при моделировании сигналов/ Аэродинамика, механика и аэрокосмические технологии (АМАТ-2001): сб. тр. первой всерос. элект. науч.-техн. конф. - Воронеж: ВГТУ, 2001. - Ч.2. - С. 69 - 78.

12. Раков В.И. О сходимости и обобщении метода интерактивной аппроксимации. /Аэродинамика, механика и аэрокосмические технологии (АМАТ-2001): сб. тр. первой всерос. элект. науч.-техн. конф. - Воронеж: ВГТУ, 2001. - Ч.2. - С. 79-88.

13. Боэм Б. Инженерное проектирование программного обеспечения. - М.: Радио и связь, 1985. - 140 с.

14. Сахал Д. Технический прогресс: концепции, модели, оценки. - М.: Финансы и статистика, 1992. - 67 с.

15. Липаев В.В. Управление разработкой программных средств: методы, стандарты, технология. - М.: Финансы и статистика, 1993. - 160 с.

16. Ахо А. Компиляторы: принципы, технологии, инструменты. - М.: Изд. дом «Вильямс», 2001. - 768с: ил.

17. Буч Г. Объектно-ориентированное проектирование. - М.: Радио и связь, 1993. - 443 с.

18. Дантеман Д. Программирование в среде Delphi. - Киев: DiaSoft Ltd., 1995. - 608 с.

19. Федоров А. Создание Windows- приложений в среде Delphi. - М.: Компьютер-Пресс, 1995. - 288 с.

Размещено на Allbest.ru