Основы представления многомерных данных. Решение линейных многомерно-матричных уравнений на основе псевдообращения многомерной матрицы

Пусть M - произвольная точка на плоскости с координатами и , вычисленными относительно заданной прямолинейной координатной системы. Однородными координатами этой точки называется любая тройка одновременно не равных нулю чисел , связанных с заданными числами и следующими соотношениями:

Рис. 3. Преобразование координат точки на плоскости в однородные координаты

При решении задач компьютерной графики однородные координаты обычно вводятся так: произвольной точке на плоскости ставится в соответствие точка в пространстве (рис. 3).

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

Вектор с координатами является направляющим вектором прямой, соединяющей точки и . Эта прямая пересекает плоскость в точке , которая однозначно определяет точку координатной плоскости .

Тем самым между произвольной точкой с координатами и множеством троек чисел вида , при не равной 0, устанавливается (взаимно однозначное) соответствие, позволяющее считать числа новыми координатами этой точки.

В проективной геометрии для однородных координат принято следующее обозначение: или более общее, (напомним, что здесь непременно требуется, чтобы числа одновременно в нуль не обращались).

Применение однородных координат оказывается удобным уже при решении простейших задач.

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

Рассмотрим другой случай. Чтобы результаты преобразования не приводили к арифметическому переполнению, для точки с координатами можно взять, например,. В результате получим .

Приведенные примеры показывают полезность использования однородных координат при проведении расчетов. Однако основной целью введения однородных координат в дискретной математике является их несомненное удобство в применении к геометрическим преобразованиям.

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

В самом деле, считая , сравним две записи: помеченную символом * и нижеследующую, матричную:

.

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

Тем самым сравниваемые записи можно считать равносильными.

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

На каждом этапе ищется матрица, соответствующая тому или иному из выделенных выше случаев А, Б, В и Г, обладающих хорошо выраженными геометрическими свойствами.

Выпишем соответствующие матрицы третьего порядка.

А. Матрица вращения (rotation)

.

Б. Матрица растяжения (сжатия) (dilatation)

.

В. Матрица отражения (reflection)

.

Г. Матрица переноса (translation)

.

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

Общая матрица преобразования при известных и получается перемножением матриц простейших преобразований .

Демонстрационный пример (файл преобразование.exe)

Рассмотрим фигуру, состоящую из 8 точек, координаты которых представлены в табл. 1.2. На рис. 4 отображен процесс ввода данных точек.

Таблица 1.2.

Исходные данные

Рис. 4. Ввод координат точек

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

o поворот на 90 градусов (рис. 7),

o растяжение с коэффициентом увеличения по осям и 0,5 и 0,7 соответственно (рис. 8),

o перенос фигуры влево на 30 и вверх на 60 единиц отсчета (рис. 9),

o отражение фигуры относительно оси y (рис. 10).

На рис. 11 отображен окончательный результат пересчета координат всех точек.

Рис. 5. Исходная совокупность точек

Рис. 6. Аппроксимированная область

Рис. 7. Область после операции «Поворот»

Рис. 8. Область после операции «Растяжение/Сжатие»

Рис. 9. Область после операции «Перенос»

Рис. 10. Область после операции «Отражение»

Рис. 11. Результирующая (преобразованная) совокупность точек

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

Порядок выполнения работы

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

2. Произвести аналитическое преобразование старшинства индексов.

В каждом варианте необходимо сделать 3 задания.

2.1. Необходимо индекс k сделать старшим индексом, а индекс i - младшим индексом.

2.2. Необходимо индекс l сделать старшим индексом, а индекс j - младшим индексом.

2.3. Необходимо индекс k сделать старшим индексом, а индекс i - младшим индексом, а также индекс l сделать старшим индексом, а индекс j - младшим индексом

3. Пример выполнения - Primer.xls. Выполнение работы LAB_RAB.xls.

4. Построение выпуклой области.

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

.

Например, , тогда ;

, тогда .

Для учебных целей примем =300, =50.

4.2. Открыть файл obras.exe, система меню которого ориентирована на реализацию всех этапов построения области работоспособности.

4.3. В демонстрационном режиме (программа Преобразование. exe) произвести преобразования области.

Содержание отчета

1. Краткое описание алгоритмов - аналитическое преобразование старшинства индексов, построения выпуклой области дискретного конечного множества элементов.

2. Координаты исходных и преобразованных точек.

3. Графическое преставление исходной и преобразованной области.

4. Представление преобразованной области множеством элементов и системой неравенств.

2. решение линейных многомерно-матричных уравнений на основе псевдообращения многомерной матрицы

2.1 Оценка устойчивости решения системы линейных уравнений

Методы определения числа обусловленности матрицы системы

Имеем систему линейных алгебраических уравнений:

А(1,1) Х(1,0) = b(1,0). (1)

Правые части получили погрешность:

b1(1,0) = b (1,0) + з (1,0). (2)

При наличии ошибок на входе, выходная величина также будет изменена:

Х1(1,0) = Х(1,0) + r(1,0). (3)

Если бы ошибок не было, то на выходе была бы величина Х.

А(1,1) • r(1,0) = з (1,0) - уравнение ошибки. (4)

В уравнении (1) зададим Х с нормой, равной 1:

.

При этом норма b тоже будет изменяться:

,

m ? || b(1,0)|| ? M.

При произвольной норме наше уравнение перепишется в виде:

m || X(1,0)|| ? || b(1,0)|| ? M || X(1,0)||.

Тогда м = - число обусловленности матрицы. Оно играет большую роль при выборе алгоритма обработки.

Перепишем уравнение с учетом изменений: вместо Х поставим r, а вместо b - з:

m || r(1,0)|| ? || з(1,0)|| ? M || r(1,0)||.

Имея эти два неравенства, найдем отношение:

, з - ошибка выхода.

Это неравенство показывает усиление ошибки со входа на выход.

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

А - матрица общего вида

.

Находим определитель матрицы и приравниваем к нулю.

Тогда:

.

Если исходная матрица А симметричная, то есть аij = aji , то для нее:

,

.

Возьмем систему уравнений:

.

Изменим 1,95 и 1,92 на некоторую величину:.

Тогда Х1 = 3, Х2 = -1,06.

Графическое представление (качественное):

У

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

Х

Если бы прямые были ортогональны друг другу, то изменение правых частей привело бы к изменению решения:

У

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

Х

Вернемся к нашему примеру:

,

.

множество матрица разложение индекс

Матрица симметричная, из диагональных элементов вычитаем :

= 0

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

2.2 Метод сингулярного разложения матрицы

Многоиндексные задачи линейного оценивания можно формализовать в виде многомерно-матричных уравнений

Y(p,0) = H(p,q)X(q,0) + V(p,0) , (5)

где X(q,0) - столбец оцениваемых характеристик, или массивов; Y(p,0) - столбец наблюдений, или измерений; H(p,q) - известная матрица преобразования; V(p,0) - столбец ошибок измерений.

Матрица H+(q,p) может быть выражена через сингулярное разложение матрицы H(p,q).

Прямое и обратное сингулярные преобразования многомерной матрицы имеют вид

, (6)

, (7)

где U(p,p), V(q,q) - многомерные ортогональные матрицы собственных элементов для матриц H(p,q)HT(p,q) и HT(p,q) H(p,q) соответственно; 1/2(p,q) - диагональная многомерная матрица сингулярных чисел H(p,q). Выражение для псевдообращения H(p,q) через сингулярное разложение запишется в виде

. (8)

Псевдообращение диагональных элементов 1/2(p,q) означает вычисление их обратных значений, а для «нулевых» элементов (величина «нулевых» элементов меньше некоторого малого числа ) результат псевдообращения будет равен нулю. Основная трудность вычисления псевдообратной матрицы через сингулярное разложение заключается в нахождении матриц U(p,p), V(q,q). После определения многомерной псевдообратной матрицы псевдорешение многомерного уравнения (5) находится в виде

. (9)

Это решение минимизирует норму

.

2.3 Определение псевдообратной матрицы для произвольной матрицы на основе метода ортогонализации Грамма-Шмидта (ГШО)

1. Столбцы матрицы , которые обозначим , преобразуются методом ГШО в ортогональные векторы (не обязательно, чтобы они получились ортонормированными). Из множества этих векторов образуется матрица .

Ортогонализация столбцов матрицы методом ГШО производится по уравнениям ;

, (10)

где .

Здесь - норма вектора, определяемая выражением .

Сравнивая нормы векторов , принимают решение об обнулении вектора с малой нормой.

2. Столбцы матрицы переставляются с помощью матрицы перестановок таким образом, что

, (11)

где

Матрица перестановок может быть подобрана следующим образом. Если требуется поменять местами i - столбец и j - столбец, то в единичной - матрице нужно сделать следующие замены: ; . В общем случае матрица может включать произведение нескольких перестановочных матриц.

3. Столбцы исходной матрицы переставляются с помощью матрицы перестановок , применяемой в п.2. При этом получают новую матрицу со столбцами, которые обозначим, например, так:

;

.

4. Вычисляются вспомогательные коэффициенты

5. Вычисляется матрица размером с элементами

.

6. Вычисляется матрица размером с элементами

7. Вспомогательная матрица находится методом ГШО из столбцов матрицы , т.е. к столбцам матрицы, сформированной из двух матриц , , применяют процедуру, аналогичную процедуре (10), но с тем отличием, что после получения каждого ортогонального вектора, начиная с первого вектора, его нормируют путем деления всех компонентов вектора на его норму. Условно эту процедуру можно представить в виде следующей цепочки преобразований:

.

Здесь размер матриц ;

; ;

.

8. Вычисляется матрица .

9. Используя матрицу, полученную в (11), вычисляем матрицу

.

10. С помощью вспомогательных матриц , , , , , вычисленных в пп. 2, 5, 6, 8, 9, определяется псевдообратная матрица

.

Оценка коэффициентов линейной регрессии определяется выражением .

Пример 1. Получение устойчивого решения системы линейных уравнений на основе использования псевдообратных матриц.

Система уравнений имеет вид

Её точное решение:

Рассмотрим систему с измененной правой частью:

Её точное решение: , т.е. решение неустойчиво.

Как и ранее, исследуем матрицу системы на обусловленность. Матрица в данном случае симметрична. Тогда на основании того, что , имеем

Обусловленность матрицы , т.е. матрица системы плохо обусловлена и необходимо применять методы повышения устойчивости решения. Рассмотрим два метода.

2.3.1 Построение псевдообратной матрицы для симметричной матрицы на основе сингулярной матрицы

Используя уравнения , определяем собственные векторы матрицы

; .

После нормировки

; .

На основании соотношения (8)

определяем псевдообратную матрицу (в примере примем q=1).

.

Решение при «точных» данных

.

Решение при измененной правой части

.

Из полученных результатов видно, что решение задачи с помощью псевдообращения становится менее чувствительным к ошибкам (изменениям) исходных данных.

2.3.2 Построение псевдообратной матрицы на основе метода ортогонализации Грамма-Шмидта

1. Используя (10), определяем ортогональные векторы

; ;

; .

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

2. Таким образом, число независимых столбцов k=1.

Матрица перестановок .

3. ; .

4. .

5. .

6. .

7. .

8. .

9. .

10. .

Решение при «точных» данных

.

Решение при измененной правой части

,

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

Порядок выполнения работы

1.В режиме обучения выполнить в демонстрационном режиме получение решения методом ГШО.

2.В режиме выполнения получить решение методом ГШО.

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

Содержание отчета

1. Краткое описание алгоритмов решения методом ГШО, методом сингулярного разложения матриц.

2.Результаты решения систем линейных алгебраических уравнений методом ГШО, методом сингулярного разложения матриц.

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

3. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ НА ОСНОВЕ МЕТОДА МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ

3.1 Формирование нелинейной функции многих переменных

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

Ф = Ф(X1,X2,…,Xn). (1)

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

Функцию можно задавать в виде точного описания последовательности операций над численными значениями переменных X1,X2,…,Xn. Функция должна обладать свойством однозначности, т.е. при любом наборе численных значений X1,X2,…,Xn принимать только одно значение.

Будем считать набор численных значений X1,X2,…,Xn координатами некоторой точки n-мерного пространства, которую можно представить вектором . Для такой точки можно подсчитать значения функции . Выделим из совокупности точек n-мерного пространства те точки, которым соответствуют равные значения функции , где Ф0 - некоторое численное значение. Геометрическое место точек с равными значениями функции называют поверхностью равного уровня. Изменив уровень Ф0 функции, получим другую поверхность равного уровня, причем различные поверхности равных уровней вложены одна в другую, но нигде не соприкасаются. Отсутствие общих точек у этих поверхностей непосредственно следует из свойства однозначности функции.

Градиентом функции будем называть вектор

, (2)

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

Исходные данные: начальная точка поиска ; градиент функции ; градиент функции в начальной точке нормируется по уравнению , где ; ; начальная матрица nЧn, равная единичной матрице, H(1,1) = E[1,1]; е - коэффициент, задающий точность одномерного поиска; Д - точность поиска минимума функции.

1. Вычисляем вектор направления . (3)

2. Формируем вектор (4)

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

Начальное значение шага одномерного поиска б0 принимается равным 1, если выполняется условие , иначе величина уменьшается. регулировка масштаба одномерного поиска заложена в формуле (3), так как величина модуля зависит от модуля градиента и по мере приближения к минимуму функции неограниченно убывает. Уменьшение шага поиска по мере приближения к минимуму многомерной функции является необходимым, иначе трудно будет достаточно точно определить координаты этого минимума.

3. Вычисляем градиент и приращение градиента

. (5)

4. Находим новую матрицу Н по рекуррентной формуле

. (6)

5. Переходим на этап 1 с новыми начальными условиями.

Отметим некоторые вычислительные особенности метода ДФП. Метод подвержен накоплению ошибок, вследствие чего рекомендуется время от времени «забывать» накопленную информацию и начинать вычислительный процесс заново. Для этого необходимо предусмотреть «обновление» расчетов. Оно заключается в замене с некоторой периодичностью (обычно через n или 2n итераций) текущей матрицы Н единичной матрицей Е. При обновлении на каждой итерации метод ДФП превращается в метод наискорейшего спуска.

При расчете на ЭВМ первая производная функции по некоторому параметру Xi заменяется первой разделенной разностью

, (7)

где X1, Xi, Xn - координаты точки , в которой вычисляется производная.

Для метода ДФП рассматриваются 2 варианта реализации, которые различаются только методами одномерного поиска. В первом варианте применяется метод золотого сечения, во втором - квадратичная аппроксимация. Рассмотрим кратко эти методы.

3.1.1 Сокращение интервала неопределенности методом золотого сечения

Название метода указывает на его связь с золотым делением отрезка, т.е. таким делением отрезка на две неравные части X и Y (X>Y), при котором

,

где .

Для нахождения минимума функции необходимо прежде всего определить интервал неопределенности, т.е. отрезок на прямой, внутрь которого попадает точка Xm с минимальным значением функции Ф(Xm). Для ускорения поиска на этапе выделения интервала неопределенности необходимо ввести переменный шаг в (4):

; б-1 = 0; б0 = 1, (8)

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

На рис. 1 изображена последовательность точек б0, б1, б2 , полученная согласно алгоритму (8).

Рис. 1. Последовательность точек б

Из рис.1 видно, что интервал неопределенности лежит между точками б0 и б2. Выберем новую точку б3 так, чтобы получить золотое сечение интервала неопределенности (рис. 2).

Рис. 2. Сокращение интервала неопределенности

Вычислительный процесс сокращения интервала необходимо продолжить, пока не будет выполнено условие одномерного поиска

, (9)

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

3.1.2 Сокращение интервала неопределенности методом квадратичной аппроксимации

В основе метода лежит аппроксимация функции Ф() квадратичным полиномом. Для ускорения поиска на этапе выделения интервала неопределенности необходимо ввести, как и ранее, переменный шаг i в (4):

; (10)

0 = 1, если при этом происходит убывание функции, -1 = 0, - коэффициент, численное значение которого в начале одномерного поиска равно нулю, а затем возрастает на 1 через каждые R шагов. Пусть произведены измерения функции в точках 0, 1, 2 согласно алгоритму . Интервал неопределенности лежит между точками 0 и 2 (рис. 1). Для сокращения интервала заменяем реальную функцию Ф() аппроксимирующей функцией Фапр(), которая проходит через те же точки 0, 1, 2, Фапр()=a2+b+c и имеет координату минимума опт= - b/(2a). Связывая неизвестные коэффициенты a, b, c со значениями 0, 1, 2 и Ф(0), Ф(1), Ф(2) получаем расчетную формулу:

. (11)

Причем точка 3=опт (рис. 2) попадает внутрь интервала неопределенности 2 - 0.

Новый интервал неопределенности уменьшился и стал равным 2 - 1. Вычислительный процесс сокращения интервала необходимо продолжить, пока не будет выполнено условие одномерного поиска (9).

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

,

где H - симметричная и положительно определенная матрица вторых частных и смешанных производных (матрица Гессе, или гессиан), с - постоянный вектор, b - константа.

Оптимальное решение приведенной задачи соответствует нулевым значениям первых производных, то есть

, откуда .

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

Среди подобных алгоритмов одним из наиболее популярных и используемых в пакете Optimization Toolbox является так называемый BFGS-алгоритм, получивший свое название по фамилиям предложивших его авторов (Broyden, Fletcher, Goldfarb, Shanoo), в котором аппроксимация Н производится итерационно, по формуле

, где , .

Заметим, что наиболее удобно иметь аппроксимацию не матрицы Н, а обратной к ней матрицы Н-1, приведенное рекуррентное соотношение подобную замену допускает, при этом сам алгоритм становится практически идентичным хорошо известному отечественным исследователям алгоритму Давидона-Флетчера-Пауэлла, за тем исключением, что в последнем векторы q заменены на векторы s и наоборот.

Именно такие алгоритмы являются основой численных методов, заложенных в распространенные математические пакеты прикладных программ (MS Excel, Mathcad, Mathlab).

Блок-схема алгоритма минимизации функции многих переменных метода Давидона-Флетчера-Пауэлла приведена на рис. 3.

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

Рис. 3. Блок-схема алгоритма минимизации функции

3.1.3 Минимизация многомерной функции при наличии линейных ограничений на основе метода Давидона-Флетчера-Пауэлла

.

Имеются ограничения:

.

Ранее (без ограничений) матрица была единичной, теперь она рассчитывается по формуле:

3.2 Учебный пример выполнения лабораторной работы

3.2.1 Минимизация многомерных функций

1. Перед выполнением учебных примеров необходимо изучить теоретический материал.

2. Открыть программу lor2a.exe -”Минимизация функции многих переменных (демонстрационная программа)”. Диалоговое меню программы имеет следующие пункты:

1) просмотр функции в целом [для всех вариантов она имеет вид

F = (x12 + x2 - 11)2 + (x1 + x22 - 7)2]);

2) просмотр функции по квадрантам;

3) метод золотого сечения;

4) метод квадратичной аппроксимации;

5) задание/снятие ограничений.

Просмотреть график функции (с линиями уровня) целиком и по квадрантам. Записать координаты начальной точки в тетрадь (в частности, для 1 варианта это x1 = -3,4 и х2 = -3,7), которую можно просмотреть ближе, записав указанный квадрант. Уточнить координаты точки двумя методами: золотого сечения и квадратичной аппроксимации. Координаты минимума, полученные этими методами (без задания ограничений), равны: х1 = -3,779, х2 = -3,283. Можно просмотреть направление движения точки по графику, выбрав соответствующий пункт меню. В тетрадь записать координаты точки минимума, количество итераций, за которое достигнуто решение, и оптимальное значение Alpha.

Далее накладывается ограничение на направление поиска минимума (для всех вариантов оно различно, в частности, для первого варианта имеет вид: -2х1 - 3х2 + 5 = 0). Начальные значения координат точки минимума х1 = -4, х2 = 4,3. Зарисовать в тетради направление движения точки по графику. Вдоль данного направления координаты точки минимума имеют значения: х1 = -2,557, х2 = 3,371 (метод золотого сечения дает этот результат после 2-й итерации при б = 0,002, метод квадратичной аппроксимации после 3-й итерации при б = 0,82).

3.Открыть программу lor4.exe. - ”Минимизация многомерной функции. Реализация градиентного метода”.

Диалоговое меню:

1) вычисление F(x1, x2);

2) Grad;

3) нормирование градиента;

4) формирование вектора положения;

5) выход.

Все данные заносить в таблицу, вид которой предложен в самой программе. Значения F1 и F2 получаются из значений нормированного градиента, взятых с противоположным знаком. Для взятой произвольно начальной точки х1 = 4, х2 = 3 градиентный метод дает следующие результаты.

Видно, что минимум функции равен 0,22662 в точке (1,215; 1,798) при alpha равном 7. Результат достигнут на седьмой итерации, но если процесс поиска минимума затянулся, то через 5 шагов alpha можно увеличивать вдвое. Построить график зависимости F=F(б).

4. Открыть программу lor.exe. - ”Программа минимизации функции многих переменных”.

Система меню ориентирована на реализацию всех этапов минимизации многомерной функции методом ДФП, который может использоваться для численной реализации других методов: координатного спуска в методе Гаусса-Зейделя, наискорейшего спуска и других градиентных методов.

1. Вычисление функции F(X1, X2) (в лабораторной работе только для простоты выполнения и наглядности визуализации исходных данных и результатов оптимизации число переменных n в целевой функции берут равным двум).

2. Вычисление GRAD(X1, X2) [реализация выражения (7)].

3. Нормирование градиента (осуществляется лишь в начальной точке поиска минимума, при дальнейших операциях эта итерация может опускаться).

4. Вычисление вектора направления [реализация выражения (3)].

5. Формирование вектора положения [реализация выражения (4)].

6. Сокращение интервала неопределенности методом золотого сечения [реализация выражения (8)]. При выполнении данной операции, если не соблюдается условие , принять и так до тех пор, пока не произойдет убывание функции.

7. Золотое деление отрезка (деление отрезка на две неравные части X и Y (X>Y)), при котором , где .

8. Вычисление вектора направления на второй и последующих итерациях [реализация последовательно выражений (6), (3)].

9. Поиск интервала неопределенности методом квадратичной аппроксимации [реализация выражения (10)]. Рекомендации по выбору б те же, что и в меню под номером 6.

10. Определение координаты минимума в методе квадратичной аппроксимации [реализация выражения (11)].

11. Построение графика функции (Х2 - ордината, Х1 - абсцисса).

12. Завершение работы.

Записать координаты начальной точки в тетрадь и начертить таблицу, как в программе lor4.exe.Проделать 2 итерации по поиску минимума функции (первые пять пунктов, т.е., alfa при этом равны 0 и 1 соответственно). Для дальнейшего определения значения alfa перейти к п. 6. Найти alfa по предлагаемой формуле и высчитывать далее по первым пяти пунктам вектор положения с учетом нового значения alfa. После нахождения точки минимума методом золотого сечения перейти ко второму методу. Для этого начертить еще одну такую же таблицу, переписать туда результаты первых двух итераций и перейти к п. 9 для определения значения alfa, далее продолжить работу по пяти пунктам и по п. 9.

5. Открыть программу lor5.exe - ”Программа минимизации функции многих переменных (со сбойными результатами)”.

Диалоговое меню программы имеет вид, как и у lor4.exe. Начертить в тетради исходную таблицу. Для начальной точки взять такие же координаты, как и в программе lor4.exe. Найти координаты точки минимума. При вычислении функции F убедиться, что налицо сбойный результат (при x1 = 4, x2 = 3 значение F = 34684,888). При выполнении работы сбой постепенно ликвидируется, но результат будет достигнут за большее количество шагов (для уменьшения количества итераций целесообразно использовать рекомендации по изменению б из предыдущего пункта). Построить график зависимости F=F(б).

6. Открыть программу lor6.exe. - ”Программа минимизации функции многих переменных без сбойных результатов. Адаптация”.

Диалоговое меню программы имеет вид, как и у lor4.exe. Начертить в тетради исходную таблицу и найти координаты точки минимума (начальные данные такие же, как и в предыдущей программе). Сравнить результаты 5-й и 6-й программ. Построить график зависимости F=F(б).

Отметим, что использованные в программе алгоритмы минимизации многомерных функций являются стандартными и применяются во всех известных математических пакетах, разработанных в Windows (Excel, MathCad, MathLab, Mathematica).

Одним из самых распространенных и наиболее популярных в вузовской среде является пакет Microsoft Excel, обладающий удобным и понятным интерфейсом, подробной справочной системой, мощным инструментарием и множеством математических функций.

Содержание отчета

1. Краткое описание алгоритма минимизации функции многих переменных.

2. Результаты поиска минимума функции многих переменных при отсутствии и наличии сбойных результатов.

3. Кратко изложить реализацию методов: координатного спуска в методе Гаусса-Зейделя, наискорейшего спуска.

4. МЕТОДЫ АППРОКСИМАЦИИ ФУНКЦИЙ

4.1 Быстрое преобразование Фурье

Матрица дискретного преобразования Фурье имеет вид:

где

.

Коэффициенты разложения сигнала имеют вид: .

Применяя обратное преобразование Фурье, получаем аппроксимированное представление сигнала где B(m,l)=W-lm.

Для сокращения числа операций целесообразно применять БПФ, представленный в матричной форме. Матрица преобразований имеет вид

, (1)

где In - единичная матрица размером (n n), Aj=A1A2…An - кронекеровское произведение, Ai=A1A2…An - прямая сумма.

,

где , N = 2n - число отсчетов.

На основе формулы (1) для n = 4 получаем спектр:

(2)

где ; .

i = 2,4,6,8 j = 1,3,5,7

Результаты представлены FKP с двоично-инверсными номерами.

Пример представления спектра с двоично-инверсными номерами дан в таблице 1.

Таблица 1

4.2 Быстрое преобразование Уолша

Функции Уолша обладают интересными свойствами, привлекающими к ним все большее внимание. Они принимают всего два значения {+1 или -1} и потому удобны для вычислений на ЭВМ. Существует различное упорядочение функций Уолша .Рассмотрим одну из возможных систем функций Уолша - систему Уолша-Адамара. Элементарная матрица Адамара, состоящая из одного элемента (N=1), имеет вид H1=[1]. Для N=2 элементами матрицы Адамара будут элементарные матрицы ( H1): . Для N = 4 элементами матрицы Адамара будут матрицы ( H2):

.

Для N=2n имеем

.

Дискретное преобразование Уолша, как и дискретное преобразование Фурье, представляется в матричной форме:

FY=HN*S/N; S= (HN)T*FY.

Здесь FY-коэффициенты спектрального разложения по функциям Уолша, S-дискретные временные отсчеты сигнала.

Быстрое преобразование Уолша (БПУ) можно получить из формулы для БПФ (10),исключив фазосдвигающие составляющие.

Матрица преобразований упрощается и имеет вид:

.

Коэффициенты спектрального разложения по функциям Уолша имеют прямую последовательность в отличие от БПФ, имеющей последовательность с двоично-инверсными номерами.

4.3 Быстрое преобразование Хаара

Преобразование Хаара основывается на использовании ортогональной матрицы Хаара. Приведем пример матрицы Хаара четвертого порядка:

и матрицы Хаара восьмого порядка:

Для записи алгоритма БПХ введем следующие обозначения матриц:

U02=[1 1]; U12=[1 -1]; I2= ;

,

где , ? - знаки прямой суммы.

.

Таким образом, матрица Хаара представлена в виде произведения «n» слабо заполненных матриц.

Быстрое преобразование Хаара - самое быстрое из используемых ортогональных функций.

Дискретное преобразование Хаара, как и дискретное преобразование Фурье, представляется в матричной форме:

;

.

.

Здесь использовано правило для транспонирования произведения матриц: [M1*M2*M3]Т=[М3Т*М2Т*М1Т].

Коэффициенты спектрального разложения по функциям Хаара имеют прямую последовательность в отличие от БПФ, имеющей последовательность с двоично-инверсными номерами.

4.4 Методы аппроксимации на основе функций гибкой структуры

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

, (3)

где (4)

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

За критерий близости исходного процесса и аппроксимирующей функции примем квадратичный критерий

. (5)

Можно подбирая параметры , i=1,2,…,N;, найти их значения, обеспечивающие минимум выбранного критерия (5). Однако этот путь сложный, длительный, так как потребует многократного численного вычисления интеграла (5).

Ставится задача - на основе оценок , определённых из условия минимума критерия (5) только при двух различных значениях , а именно и , определить «истинные» значения параметров процесса T1 и , .

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

(6)

и

, (7)

определённые из условия минимума критерия (5) при двух различных масштабах времени и , т. е. «измеряемые» величины могут быть представлены в виде:

, (8)

, (9)

где (10)

. (11)

Подставляя в уравнения (8), (9) вместо Y(t) его аппроксимирующее выражение из (3), получаем

, (12)

где (13)

. (14)

Задавшись некоторым значением из (12), определим оценку . Эта оценка зависит от двух параметров T21, .

, (15)

где (16)

Аналогично, задавшись тем же значением из (12), определим оценку . Эта оценка будет зависеть от двух параметров T22, .

. (17)

Здесь (18)

При оценки и совпадут (при отсутствии помех). На практике за истинное значение T1 принимается значение , при котором величина квадратичного критерия

Q=[-][-]= (19)

принимает минимальное значение.

Коэффициенты матриц , i=1,2 зависят лишь от отношения T1/T21 в уравнении (16) и от отношения T1/T22 в уравнении (18). Матрицы могут быть протабулированы заранее для выбранной системы функций . Коэффициенты матриц для различных N в представлении (1) и для T22/T21=10 представлены в файле Масштаб.xls. Таким образом, алгоритм определения T1 сводится к последовательному вычислению выражений (15) и (17) при различных значениях и определению минимума критерия (19).

За истинное значение вектора целесообразно принять среднее значение двух оценок

=1/2 [+] (20)

или ту оценку, которая соответствует значению T2i, ближайшему к T1. Однако желательно при найденном оптимальном значении Т1 произвести вычисление оценок .

Рассмотрим методику определения «истинного» масштаба T1 на следующем примере.

Наблюдаемый процесс имеет вид

, (21)

то есть С1=1; T1=6.

1. Задавшись =2 и =20, определяем векторы

, (22)

. (23)

Вычисления этих векторов могут производиться или непосредственно по формулам (8), (9) или значения этих векторов могут быть получены в результате эксперимента над исследуемым объектом.

(24)

. (25)

2. Придавая T1 значения T1=1,2,…,10, производим вычисления

. (26)

. (27)

. (28)

и т. д. (29)

3. При каждом значении T1 вычисляем ошибку в определении параметров

(30)

и величину критерия

. (31)

Результаты вычислений сведены в таблицу 2.

Таблица 2.

Результаты вычислений

Подобные документы

• Решение систем линейных уравнений

  Метод Гаусса - последовательное исключение переменных из системы уравнений. Определение понятия расширенной матрицы. Метод Крамера, расчет определителя системы. Метод обратной матрицы. Расчет алгебраических дополнений для элементов полученной матрицы.
  
  презентация [184,4 K], добавлен 21.09.2013
  

• Матрицы, Метод Гаусса

  Понятие матрицы. Метод Гаусса. Виды матриц. Метод Крамера решения линейных систем. Действия над матрицами: сложение, умножение. Решение систем линейных уравнений методом Гаусса. Элементарные пребразования систем. Математические перобразования.
  
  лекция [45,4 K], добавлен 02.06.2008
  

• Решение матричных уравнений. Базисный минор. Ранг. Действия над матрицами

  Понятие равных матриц, их суммы и произведения. Нахождение элемента матрицы, свойства ее произведения. Расположение вне главной диагонали элементов квадратной матрицы. Понятие обратной матрицы, матричные уравнения. Теорема о базисном миноре, ранг матрицы.
  
  реферат [105,3 K], добавлен 21.08.2009
  

• Алгебра матриц. Системы линейных уравнений

  Выполнение действий над матрицами. Определение обратной матрицы. Решение матричных уравнений и системы уравнений матричным способом, используя алгебраические дополнения. Исследование и решение системы линейных уравнений методом Крамера и Гаусса.
  
  контрольная работа [63,2 K], добавлен 24.10.2010
  

• Определитель матрицы

  Вид в матричной форме, определитель матрицы, алгебраического дополнения и всех элементов матрицы, транспоная матрица. Метод Крамера, правило Крамера — способ решения квадратных систем линейных алгебраических уравнений с определителем основной матрицы.
  
  задача [93,5 K], добавлен 08.11.2010
  

• Решение матричных уравнений

  Базовые действия над матрицами. Решение матричных уравнений с помощью обратной матрицы и с помощью элементарных преобразований. Понятия обратной и транспонированной матриц. Решение матричных уравнений различных видов: АХ=В, ХА=В, АХВ=С, АХ+ХВ=С, АХ=ХА.
  
  курсовая работа [172,0 K], добавлен 09.09.2013
  

• Метод квадратных корней для симметричной матрицы при решении систем линейных алгебраических уравнений

  Исследование метода квадратных корней для симметричной матрицы как одного из методов решения систем линейных алгебраических уравнений. Анализ различных параметров матрицы и их влияния на точность решения: мерность, обусловленность и разряженность.
  
  курсовая работа [59,8 K], добавлен 27.03.2011
  

• Определители матрицы и системы линейных алгебраических уравнений

  Основные действия над матрицами, операция их умножения. Элементарные преобразования матрицы, матричный метод решения систем линейных уравнений. Элементарные преобразования систем, методы решения произвольных систем линейных уравнений, свойства матриц.
  
  реферат [111,8 K], добавлен 09.06.2011
  

• Упорядоченные множества

  Теория частичных действий как естественное продолжение теории полных действий. История создания и перспективы развития теории упорядоченных множеств. Частично упорядоченные множества. Вполне упорядоченные множества. Частичные группоиды и их свойства.
  
  реферат [185,5 K], добавлен 24.12.2007
  

• Задачи линейной алгебры. Понятие матрицы. Виды матриц. Операции с матрицами. Решение задач на преобразование матриц

  Основные операции над матрицами и их свойства. Произведение матриц или перемножение матриц. Блочные матрицы. Понятие определителя. Панель инструментов Матрицы. Транспонирование. Умножение. Определитель квадратной матрицы. Модуль вектора.
  
  реферат [109,2 K], добавлен 06.04.2003
  

• Элементы линейной алгебры

  Линейные операции над матрицами. Умножение и вычисление произведения матриц. Приведение матрицы к ступенчатому виду и вычисление ранга матрицы. Вычисление обратной матрицы и определителя матрицы, а также решение систем линейных уравнений методом Гаусса.
  
  учебное пособие [658,4 K], добавлен 26.01.2009
  

• Решение систем линейных алгебраических уравнений

  Задачи вычислительной линейной алгебры. Математическое моделирование разнообразных процессов. Решение систем линейных алгебраических уравнений большой размерности. Метод обратной матрицы и метод Гаусса. Критерии совместности и определенности системы.
  
  курсовая работа [220,0 K], добавлен 21.10.2011
  

• Системы линейных уравнений и неравенств

  Основные понятия теории систем уравнений. Метод Гаусса — метод последовательного исключения переменных. Формулы Крамера. Решение систем линейных уравнений методом обратной матрицы. Теорема Кронекер–Капелли. Совместность систем однородных уравнений.
  
  лекция [24,2 K], добавлен 14.12.2010
  

• Умножение матрицы. Теория вероятности

  Преобразование матрицы: умножение, приведение коэффициентов на главной диагонали матрицы к 1. Решение системы уравнений методом Крамера. Определители дополнительных матриц. Определение вероятности события (теория вероятности), математическая статистика.
  
  контрольная работа [73,5 K], добавлен 21.10.2010
  

• Матрицы и определители

  Понятие матрицы, ее ранга, минора, использование при действиях с векторами и изучении систем линейных уравнений. Квадратная и прямоугольная матрица. Элементарные преобразования матрицы. Умножение матрицы на число. Класс диагональных матриц, определители.
  
  реферат [102,8 K], добавлен 05.08.2009
  

• Совместность и решение системы линейных уравнений

  Решение системы линейных уравнений методом Гауса. Преобразования расширенной матрицы, приведение ее к треугольному виду. Средства матричного исчисления. Вычисление алгебраических дополнений матрицы. Решение матричного уравнения по правилу Крамера.
  
  задача [26,8 K], добавлен 29.05.2012
  

• Решение матриц

  Правила произведения матрицы и вектора, нахождения обратной матрицы и ее определителя. Элементарные преобразования матрицы: умножение на число, прибавление, перестановка и удаление строк, транспонирование. Решение системы уравнений методом Гаусса.
  
  контрольная работа [462,6 K], добавлен 12.11.2010
  

• Матрицы и определители

  Понятие, типы и алгебра матриц. Определители квадратной матрицы и их свойства, теоремы Лапласа и аннулирования. Понятие обратной матрицы и ее единственность, алгоритм построения и свойства. Определение единичной матрицы только для квадратных матриц.
  
  реферат [296,6 K], добавлен 12.06.2010
  

• Матрицы и определители. Системы линейных уравнений. Уравнение плоскости

  Разложение определителя 4-го порядка. Проверка с помощью функции МОПРЕД() в программе Microsoft Excel. Нахождение обратной матрицы. Решение системы линейных уравнений методом обратной матрицы и методом Гаусса. Составление общего уравнения плоскости.
  
  контрольная работа [138,7 K], добавлен 05.07.2015
  

• Решение уравнений системы матриц

  Расчет денежных расходов предприятия на выпуск изделий, при выражении их стоимости при помощи матриц. Проверка совместимости системы уравнений и их решение по формулам Крамера и с помощью обратной матрицы. Решение алгебраических уравнений методом Гаусса.
  
  контрольная работа [576,6 K], добавлен 28.09.2014
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам