Контрольная работа: Поиск экстремума двумерной функции при помощи LabVIEW

На рис. 3 показана организация градиентного поиска. Градиентом функции y(x₁ , x₂ ) называется вектор с координатами, равными частным производным функции по соответствующим факторам. Градиент направлен в сторону максимальной крутизны поверхности отклика. Движение по направлению к минимуму производится следующим образом. Для начальной точки 1 находится градиент и в направлении обратном градиенту осуществляется перемещение на один шаг. Для новой точки опять находится градиент и производится перемещение на один шаг. И т. д., пока не будет достигнут экстремум. Признак достижения экстремума – изменение аргумента градиента на 180 градусов.

Рис. 4

Наиболее простым в реализации является метод покоординатного поиска (метод Гаусса – Зейделя). Поиск производится сначала по одной из координат до достижения местного экстремума, потом аналогично по другой координате и т.д., пока не будет достигнут экстремум функции (рис. 4). В процессе поиска постоянно сравнивается текущее значение отклика с предыдущим значением. Изменение знака этой разности говорит о достижении местного экстремума и о необходимости перехода к поиску по другой координате.

6. Метод Гаусса-Зейделя

В лабораторной работе метод Гаусса-Зейделя используется для поиска максимума двумерной функции

z = exp{[(x – x₀ )² + (y – y₀ )² ]/b}. (1)

Эта функция симметрична относительно плоскостей x = x₀ и y = y₀ , поэтому поиск завершается за два этапа: поиск по координате х и поиск по координате у. Структурная схема программы виртуального прибора приведена на рис. 5.

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

Координаты начальной точки x_нач и y_нач и величина шага поиска Δ задаются с лицевой панели. Напомним, что шаг поиска это величина приращения координаты за одну итерацию. Шаг поиска берем одинаковым по обеим координатам: Δх = Δу = Δ.

Рассмотрим, как производится определение направления поиска. Считаем, что поиск начинается по координате х. Сначала рассчитываются значения отклика в начальной точке z = z(x_нач , y_нач ) и отстоящих от нее по координате х на величину δх в сторону увеличения и уменьшения координаты: z₁ = z(x_нач + δх, y_нач ) и z₂ = z(x_нач – δх, y_нач ). Величина δх должна быть не больше шага поиска Δх. В зависимости от соотношения между z, z₁ и z₂ принимается решение о направлении поиска. Если z₂ < z < z₁ , то координата х в процессе поиска должна увеличиваться, шаг Δх = Δ положителен. Если z₂ > z > z₁ , то координата х должна уменьшаться, шаг Δх = -Δ отрицателен. Эти ситуации показаны на рис. 6 а) и в) для начальной точки, находящейся вблизи максимума.

Рис. 6

Если же z > z₁ и z > z₂ (рис. 6 б), то поиск проводить не нужно, так как точки, более близкой к экстремуму, при выбранном шаге поиска нет. Анализируя записанные соотношения между z, z₁ и z₂ , замечаем, что шаг Δx должен быть положительным, если z <z₁ , и отрицательным, если z <z₂ . В противном случае достигнут максимум и поиск не производится.

Блок-схема программы определения направления поиска приведена на рис. 7а). Текст программы записывается в структуре FormulaNode (пример текста представлен на рис. 7 б).

Рис. 7

После определения направления поиска производится изменение координаты х в сторону достижения максимума добавлением к х значения Δх в структуре While (рис. 8), пока вычисленное текущее значение z не станет меньше предыдущего. За максимальное значение z принимается предыдущее значение.

Рис. 8

Условием выхода из цикла While является равенство нулю шага поиска dx или отрицательная разность текущего и предыдущего значений z. Выводятся массивы переменных х, у и z для формирования траектории поиска и последние значения переменных х и у, которые являются начальными координатами для поиска по координате у.

Оценим ошибку определения экстремума. Ее значение можно определить, исследуя процесс поиска вблизи максимума. Рассмотрим подробнее эту ситуацию (рис. 9).Так как z(x) < z₁ , то принимается решение об изменении координаты х в сторону увеличения на величину шага Δx. Тогда вычисленное значение z(х + Δх) окажется меньше предыдущего z(х) и за максимальное значение будет принято z(х).

Рис. 9

Ошибка – это разность между истинной x_{m ист} и рассчитанной x_m координатами максимума. Чему равно максимальное значение ошибки? Если уменьшать х, то z(x) будет уменьшаться, а z(х + Δх) увеличиваться. Когда они сравняются, ошибка будет равна Δх/2. При дальнейшем уменьшении х значение z(х + Δх) становится больше значения z(х) и за максимальное значение принимается z(х + Δх). Ошибка становится равной -Δх/2. Таким образом, ошибка может принимать значения от -Δх/2 до Δх/2. Если координаты начальной точки поиска равномерно распределены в области определения функции z(x, y), то и ошибка равномерно распределена в интервале (-Δх/2, Δх/2).

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

Аналогично осуществляется поиск по координате у. Выходные переменные х, у и z структуры While, осуществляющей изменение координаты у, выводятся в виде массивов (как на рис 8) для формирования траектории поиска. А для индикации координат точки максимума выводятся последние значения переменных х, у и z.

Объединение массивов координат х, у и z, сформированных структурами While, производится функцией BuildArray, поставленной в режим формирования одномерного массива (щелкнуть ПКМ на BuildArray и в раскрывшемся меню активизировать ConcatenateInputs).

Для индикации траектории поиска используется графический индикатор 3DCurveGraph(рис. 10). Схема подсоединения к входам “xvector”, “yvector” и “zvector”, а также схема формирования массивов показана на рис. 11. На входы функций подаются одномерные массивы.