Актуальность темы
Теория аппроксимации, которую можно рассматривать как основу вычислительных методов [2, 3, 5, 11, 26], имеет дело с приближением отдельных функций и классов функций, элементами заданных подпространств, каждое из которых состоит из функций, являющихся в каком-то смысле более простыми, чем аппроксимируемые функции [1, 18]. Чаще всего роль таких подпространств играют множество алгебраических многочленов или же (в периодическом случае) множество тригонометрических полиномов заданного порядка п.
Фундамент теории аппроксимации заложен классическими работами Гаусса, Чебышева, Вейерштрасса, Джексона, Бернштейна и др. о приближении многочленами индивидуальных функций и целых их классов.
Наиболее существенные результаты окончательного характера получены на классах периодических функций, что объясняется тем, что периодические функции обладают определенной симметрией экстремальных свойств.
Идеи и методы теории аппроксимации применяются в различных разделах математической науки, особенно прикладных направлений, так как задачи, связанные с необходимостью заменить один объект другим, близким в том или ином смысле к первому, но более простым для изучения, возникают очень часто.
Широкому проникновению идей и методов теории аппроксимации в самые разные области науки в немалой степени способствовало обнаружение глубоких связей между довольно далекими, на первый взгляд, экстремальными задачами функционального анализа. Наиболее четко и эффективно связи проявились при исследовании наилучшего приближения функций.
Классической проблемой, развитие которой имеет решающее значение для большого числа теоретических и прикладных задач, является задача аппроксимации функции, заданной таблично. Актуальность исследования дискретных экстремальных задач объясняется в первую очередь наличием широкой сферы их приложений.
Типичным является использование аппроксимации для прогнозирования, которое в свою очередь представляет собой вспомогательную процедуру в задаче принятия решений.
Задачи аппроксимационного содержания, как правило, являются задачами на экстремум: требуется найти точную верхнюю грань погрешности приближения заданным методом на фиксированном классе функций или указать для этого класса наилучший аппарат приближения.
Если вопросу выбора класса аппроксимирующих зависимостей (вида решающего правила в терминах теории принятия решений) уделяется существенное внимание, то вопрос выбора критерия оптимальности (или целевой функции, в терминах теории принятия решений), как правило, не обсуждается (используются традиционные минимумы суммы квадратов или модулей отклонений, или минимакс). Диссертационная работа посвящена именно второму вопросу.
Современная теория принятия решений представляет собой синтез моделей и методов, возникающих в различных дисциплинах — в математическом программировании [35, 36], исследовании операций [4, б, 17, 23, 25, 29, 52, 61], математической экономике [12, 19, 30, 32, 35, 53, 55, 66, 67].
Теория принятия решений является одной из наиболее интенсивно развивающихся сейчас отраслей знаний [7, 24, 48, 37, 51, 60, 65, 68]. Возрастающий интерес к исследованию задач принятия решений объясняется как теоретическими потребностями, так и важными практическими приложениями в технике, экономике, экологии и др. Использование научно обоснованных решений предполагает создание математических моделей разнообразных процессов и решение определенных задач оптимизации для этих моделей.
Процесс принятия решения рассматривается нами прежде всего как процесс преобразования информации [8, 40].
Все процессы функционирования человеческого общества отражаются посредством информации. Информация — это средство общения людей, через нее мы получаем сведения об окружающем мире и происходящих в нем процессах. Понятием «информация» оперируют все области знания, все сферы человеческой деятельности.
В кибернетике понятие информации трактуется как мера устранения неопределенности состояния системы. В теории принятия решений информация рассматривается с точки зрения технологии ее преобразования в целях управления, то есть как совокупность сведений, являющихся объектом передачи, хранения, обработки.
Речь здесь идет об особом виде информации — статистической, характеризующей количественные закономерности явлений в неразрывной связи с их качественным содержанием.
Накопленная информация в большом числе однотипных ситуаций является, как правило, объективным исходным материалом для формулировки правдоподобных гипотез о развитии ситуации (прогнозирования) и построения математических моделей функционирования систем.
Исходная информация для планирования, проектирования и управления в экономике, технике и военном деле, как правило, недостаточно полна или достоверна. Планирование производства обычно производится в условиях неполной информации об обстановке, в которой будет выполняться план и реализовываться производственная продукция. Работа автоматических устройств сопровождается непредвиденными случайными помехами. Еще сложнее обстоит дело в военных задачах, где помимо естественного недостатка информации возникает также возможность дезинформации. В этом случае задача принятия решений называется неопределенной [13, 33, 41, 56, 64], а ее решение связано с обработкой и аппроксимацией накопленной статистической информации.
Вопросы переработки и использования информации для принятия решений в условиях неопределенности, связанной с неполнотой исходной информации или ее искажением при передаче, являются одной из важнейших проблем информатики [9, 42, 57, 59, 69, 70, 73].
Целью работы является рассмотрение аппроксимации таблично заданной функции как вспомогательной процедуры в задаче принятия решений.
Объект исследования — теория принятия решений и теория аппроксимации.
Предметом исследования являются задачи, возникающие в процессе обработки информации для принятия решений в условиях неопределенности.
Исторический обзор. Любая задача, в которой исходная функция задается таблицей своих значений, требует применения того или иного метода аппроксимаций. Наиболее часто в качестве критерия аппроксимации выбирают метод наименьших квадратов.
История развития метода наименьших квадратов началась в 1806 г. с работы французского математика А. М. Лежандра, посвященной вычислению кометных орбит [44], где он впервые ввел понятие и изложил метод наименьших квадратов.
В 1809 г. К. Ф. Гаусс [16] дал первое вероятностное обоснование метода наименьших квадратов, а в 1810 г. он же [14] разработал вычислительную сторону метода для обработки неравноценных наблюдательных данных. В 1821 г. вышла в свет статья К. Ф. Гаусса с изложением этого метода применительно к топографическим задачам [15].
В своих работах К. Ф. Гаусс применял вероятностный подход к обоснованию метода наименьших квадратов. В статье [16] он излагал его как способ оценки параметров по критерию максимального правдоподобия в современной терминологии. В работе [15], критикуя избранный им ранее путь обоснования и опубликованные к тому времени исследования П. С. Лапласа по методу наименьших квадратов, К. Ф. Гаусс привел обоснование этого метода в форме минимизации дисперсий. Здесь впервые он рассматривает весовые коэффициенты как величины, обратные дисперсиям.
В 1812 г. Лаплас в фундаментальном трактате по теории вероятности [43] получил ряд важных результатов и применил их к методу наименьших квадратов, что позволило находить наивероятнейшие значения измеренных величин и степень достоверности этих расчетов.
Дальнейшие важные результаты были получены в теории метода наименьших квадратов в 1859 г. П. Л. Чебышевым [71], разработавшим теорию интерполирования по методу наименьших квадратов с помощью ортогональных полиномов, носящих его имя.
А. А. Марков в 1898 г. в работах [49], [50] внес в математическую статистику ряд весьма важных идей, прояснивших суть метода наименьших квадратов, и дал, в частности, общепринятое в настоящее время вероятностное обоснование метода.
После работ Маркова А. А. с двадцатых годов нынешнего века метод наименьших квадратов включился в математическую статистику как важная и естественная часть оценивания параметров.
В этой связи ряд интересных и важных результатов получен Дж. Нейманом [54] и Ф. Дэвид [28], А. Эйткеном [72], С. Pao [58].
В 1946 г. А. И. Колмогоровым [39] дано геометрической изложение метода наименьших квадратов.
На сегодняшний день метод наименьших квадратов в разных научных дисциплинах называется по-разному. Например, математики могут интерпретировать его как метод отыскания для заданной точки функционального пространства ближайшей точки в заданном подпространстве. Специалисты по численному анализу используют этот подход в вопросе об ошибках входной информации. Статистики вводят в свою постановку задачи вероятностные распределения и используют для описания этой области термины регрессионного анализа. Инженеры приходят к нему, занимаясь такими предметами как оценивание параметров или фильтрация.
Главное состоит в следующем: когда эти задачи (сформулированные в любом из заданных контекстов) достигают стадии конкретных расчетов, они содержат в себе одну и ту же центральную проблему, которую можно сформулировать следующим образом.
Пусть в результате проведенных экспериментов получены п пар чисел.
Таким образом, функция у (х) определена таблицей своих значений при заданных значениях аргументов Xi {г = 1, п). Табличные значения функции и аргумента назовем узлами таблицы. Далее везде предполагается, что Уг > 0, и значения аргумента упорядочены по возрастанию:
Х < Х2 < ¦ ¦ ¦ < Хп.
Требуется аппроксимировать исходную табличную функцию у{х) некоторой функцией /(ж, а), зависящей от неизвестного вектора параметров а.
Обозначим через ipi — квадрат отклонения в ¿—ой точке: (Vi ~ f (xi, aha2,. ., am) f. (0.1).
Согласно методу наименьших квадратов, в качестве оценок неизвестных параметров берутся такие их значения, при которых сумма квадратов отклонений экспериментальных значений угот соответствующих «теоретических» f (xi, a) с учетом весовых коэффициентов будет наименьшей:
Ф = ?A^^min. (0.2) г=1.
Рассматривая Ф как функцию от а, а^,., ат, необходимое условие ее экстремума можно записать в виде дФ = 0, к = 1,., т. (0.3) дак.
Решая полученную систему из т уравнений относительно т неизвестных параметров, можно найти искомые оценки.
Аналогично выглядит метод наименьших квадратов и в случае, когда ж-вектор. При этом Х{ в формуле (0.1) следует заменить набором хц, Х (2,. где хц обозначает значение j-тo аргумента функции у (х 1, Х2,. •, х8) в г-м эксперименте.
Систему уравнений (0.3) называют нормальной системой метода наименьших квадратов.
На практике наиболее часто применяются функции п п. у (х) = а0 + у (х) = ехр (а0 + Е агХг). г=1 г=1.
Параметры этих функций имеют качественный физический или экономический смысл и легко интерпретируются.
Так уравнение прямой у (х) = а^ + ах (полином первой степени) характеризует постоянный прирост, равный, а единицам при начальном уровне ао.
В уравнении параболы второго порядка у (х) = а^+ахх+а^х2 (полином второй степени) — коэффициент, а выражает начальную скорость роста, а коэффициент а2 — постоянную скорость изменения прироста (величина ускорения в среднем за изучаемый период равна единицам).
Экспонента у{х) = ехр (ао+ отражает постоянный относительный прирост, равный еах единицам, а у{х) = ехр (ао—ах + а2Х2) характеризует постоянный относительный прирост, равный е2″ 2 единицам (производные соответствующих логарифмов). п.
Оценки параметров в модели ехр (ао + ]Рагжг) находят путем примег=1 нения метода наименьших квадратов к логарифмам исходных данных.
Проблемой исследования является определение влияния весовых коэффициентов на оптимальное решение в задаче аппроксимации таблично заданной функции в методе наименьших квадратов (МНК) и в задаче чебышевской интерполяциинахождение оптимальных решений в задачах МНК и чебышевской интерполяции с дополнительными ограничениями на значения переменныхрассмотрение и решение задач аппроксимации с новыми несимметричными критериями аппроксимации.
В основу исследования положена следующая гипотеза: использование различных вариантов выбора весовых коэффициентов при аппроксимации таблично заданной функции и различных типов критериев аппроксимации и ограничений, соответствующих исходной задаче принятия решений (для решения которой и проводится аппроксимация), позволяет более гибко учитывать имеющуюся информацию и на этом основании изучать модели управления и строить решающие правила.
Для реализации поставленной цели и проверки сформулированной выше гипотезы потребовалось решить следующие задачи:
— рассмотреть различные значения весовых коэффициентов, используемые в методе наименьших квадратов, и определить их влияние на получаемое решение;
— исследовать задачу аппроксимации функции, проходящей через определенное количество точек (интеграция интерполирования и аппроксимации) ;
— рассмотреть и решить задачу приближения с несимметричными критериями аппроксимации;
— исследовать решение задачи аппроксимации с минимаксным критерием (чебышевская интерполяция) при наличии весовых коэффициентов и ограничений.
Методологическую основу работы составляют методы теории приближения функций, математического программирования, теории исследования операций.
Научная новизна. В работе представлен новый подход к проблеме приближения функции заданной на конечном числе точек. Задача приближения таблично заданной функции рассматривается как вспомогательная задача в процедуре принятия решений, что отражается на ее формулировке, то есть выборе критерия аппроксимации и дополнительных ограничений.
Работа состоит из введения, четырех глав и заключения. В первой главе (§§ 1.1, 1.2) рассматривается метод наименьших квадратов с весовыми коэффициентами.
§ 1.1 посвящен описанию метода наименьших квадратов с весовыми коэффициентами для случая линейной зависимости, рассматриваются некоторые варианты выбора весовых коэффициентов и исследуется их влияние на решение экстремальной задачи.
В § 1.2 подобное исследование проведено для случая квадратичной зависимости.
Во второй главе (§§ 2.1−2.3) рассмотрен метод наименьших квадратов с ограничениями на значения переменных.
В § 2.1 дается постановка задачи и вводятся основные обозначения.
В § 2.2 поставленная задача решается методом неопределенных коэффициентов.
В § 2.3 решение получено путем применения интерполяционного многочлена в форме Лагранжа и проведено сравнение с решением, полученным в предыдущем параграфе.
В третьей главе (§§ 3.1−3.4) рассматриваются задачи аппроксимации с несимметричными критериями и ограничениями.
§ 3.1 содержит общую постановку задачи с ограничениями на приближающую функцию.
В § 3.2 рассматривается задача о приближении табличной функции линейной, исходя из максимизации суммы эффективностей с гиперболическим критерием аппроксимации.
В § 3.3 задача, поставленная в § 3.2, рассматривается для квадратичной приближающей функции.
В § 3.4 рассматривается задача на минимум суммы относительных погрешностей, когда аппроксимирующая функция линейна, а критерий эффективности — гиперболическая функция.
Четвертая глава (§§ 4.1−4.3) посвящена задачам аппроксимации с минимаксным критерием.
§ 4.1 посвящен чебышевской интерполяции при наличии весовых коэффициентов.
В § 4.2 рассматривается общая дискретная задача аппроксимации с минимаксным критерием при наличии весовых коэффициентов и алгоритм Валле-Пуссена для задач этого типа.
В § 4.3 формулируется и решается задача аппроксимации с минимаксным критерием при наличии ограничений на значения переменных.
В тексте приводятся примеры, иллюстрирующие вводимые понятия и утверждения.
В заключении перечисляются основные результаты работы, а также обсуждаются возможные области их применения.
Таким образом, в диссертационной работе проведено исследование различных экстремальных аппроксимационных задач возникающих в теории принятия решений в условиях неопределенности, когда исходные данные представлены таблицей своих значений.
Практическая значимость работы. Новые постановки задачи аппроксимации, как вспомогательной задачи принятия решений, позволяют получать более адекватные знания о развитии ситуации, для описания которой была использована таблично заданная функция. Предложенный подход позволит строить реальные модели функционирования различных систем (экономических, экологических, социальных) в условиях ограниченной и неполной информации, а следовательно, принимать эффективные решения на основе имеющейся статистической информации.
Основные положения выносимые на защиту. Задача обработки (аппроксимации) статистической информации должна рассматриваться как составляющая в процессе управления (принятия решений), в связи с чем важным представляется:
— исследование влияния на решение различных значений весовых коэффициентов в методе наименьших квадратов аппроксимации таблично заданной функции;
— постановка и решение задачи интеграции аппроксимации и интерполирования функции;
— постановка и решение задачи приближения функции с несимметричными критериями аппроксимации;
— рассмотрение задач чебышевской интерполяции при наличии весовых коэффициентов и при наличии дополнительных ограничений на значения переменных.
Апробация работы. Результаты исследования докладывались на семинаре по теоретическим основам информатики кафедры информатики и дискретной математики МПГУ, на аспирантском объединении, а также опубликованы в 5 работах по теме исследования.
Основное содержание диссертации отражено в работах ([20], [21], [22], [62], [63]).
Основные результаты.
1) Исследовано влияние выбора различных видов весовых коэффициентов в методе наименьших квадратов на результат решения экстремальной задачи аппроксимации.
2) Рассмотрена задача построения алгебраического полинома наилучшего приближения в смысле метода наименьших квадратов при дополнительных ограничениях типа равенства на приближающую функцию (синтез задач аппроксимации и интерполяции) и получено ее решение:
— методом неопределенных коэффициентов;
— с использованием интерполяционного полинома в форме Лагранжа.
3) Рассмотрена и решена экстремальная задача аппроксимации, в которой оценкой близости служит гиперболический несимметричный критерий.
4) Рассмотрена и решена экстремальная задача на минимум суммы относительных погрешностей приближения.
5) Рассмотрены задачи чебышевской аппроксимации с минимаксным критерием при наличии весовых коэффициентов и ограничений типа равенств и методы их решения.
Реальные процессы управления и принятия решений протекают в условиях неопределенности, то есть неточного знания необходимых параметров. Поэтому задачи прогнозирования значений этих параметров являются важнейшим этапом управления и принятия решений. Предложенный в работе подход к задаче аппроксимации как вспомогательной при принятии решений позволяет более гибко учитывать имеющуюся информацию и на этом основании изучать модели управления и строить решающие правила.
Заключение
.
Классической проблемой обработки информации является задача аппроксимации функции, заданной таблично. Наиболее распространенным подходом к ее решению является метод наименьших квадратов. Однако если эта задача является вспомогательной по отношению к более общей задаче принятия решений, то традиционный квадратичный критерий аппроксимации не всегда отражает существо проблемы. Настоящая работа посвящена задачам, возникающим в процессе обработки информации для принятия решений в условиях неопределенности. В соответствии с сутью проблемы рассматриваются различные формулировки аппроксимацион-ных задач, определяющиеся видом критериев и ограничений.
