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



/ 7 XX

и

московский педагогический государственный университет

На правах рукописи

Самсонова Наталия Викторовна

Некоторые задачи теории аппроксимации и их приложения к принятию решений

Специальность 05.13.17 - теоретические основы информатики

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук, профессор, академик Международной Академии информатизации В.А. Горелик

Москва - 1998

СОДЕРЖАНИЕ

Введение 4

1 Метод наименьших квадратов с весовыми коэффициентами 17

1.1 Метод наименьших квадратов с весовыми коэффициентами: случай линейной зависимости............... 17

1.2 Метод наименьших квадратов с весовыми коэффициентами: случай квадратичной зависимости.............32

2 Метод наименьших квадратов с ограничениями 51

2.1 Постановка задачи................................................51

2.2 Метод неопределенных коэффициентов........................52

2.3 Решение исходной задачи с применением интерполяционного многочлена в форме Лагранжа............................63

3 Задача аппроксимации с несимметричными критериями и

ограничениями 70

3.1 Постановка задачи........................ 70

3.2 Задача на максимум суммы гиперболических оценок аппроксимации: линейный случай................. 72

3.3 Задача на максимум суммы гиперболических оценок ап-

проксимации: квадратичный случай.............. 78

3.4 Задача на минимум суммы относительных погрешностей . . 84

4 Задача аппроксимации с минимаксным критерием 93

4.1 Чебышевская интерполяция с весовыми коэффициентами . 93

4.2 Общая дискретная задача. Алгоритм Балле - Пуссена. ... 100

4.3 Чебышевская интерполяция с ограничениями........111

Заключение 125

Литература 127

Введение

Актуальность темы. Теория аппроксимации, которую можно рассматривать как основу вычислительных методов [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, рассматривается для квадратичной прибл