§ 6.11. Универсальные методы построения областей устойчивости и динамического качества

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

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

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

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

Получение более точного положения точки границы можно осуществить, применяя метод деления интервала, так, чтобы границы строились по точкам на расстоянии, равном половине стороны квадрата, или на расстояния, равном одной трети ее. Алгоритм движения вдоль границы искомой области иллюстрируется на рис. 6.9. При каждом пересечении границы

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

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

Рис. 6.9

Рис. 6.10

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

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

Можно применить более точный способ движения по границе искомой области («гусеничный» метод).

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

Рис. 6.11

Пусть имеются две точки принадлежащие искомой области на плоскости параметров и пусть интересующая нас область лежит справа от прямой, соединяющей точку Тогда приближенно можно указать следующую точку по формулам

Геометрически это означает, что сделан шаг по прямой, соединяющей точки от точки к точке равной расстоянию между этими точками (рис. 6.11, а, б).

В полученной точке с координатами вычисляется функционал При этом возможны два случая:

Анализируемая точка с координатами находится вне искомой области. Тогда выполняется поворот против часовой стрелки и производится определение положения новой точки по формулам

где — угол поворота.

Точка находится внутри искомой области. Для выхода на границу осуществляется поворот по часовой стрелке. Положение

новой точки определяется по формулам

В полученной точке вновь вычисляется функционал и проверяется знак разности

Если соблюдается условие , то точка находится точно на границе искомой области.

Если имеет место случай 1, то нахождение следующей точки выполняется по формулам (6.76) в соответствии со знаком разности

Эта процедура продолжается до тех пор, пока случай 1 не перейдет в случай 2 или наоборот.

Переход сопровождается переменой знака разности

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

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

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

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

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

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

Для данного угла имеем формулы:

а) при повороте по часовой стрелке , точка внутри области)

б) при повороте против часовой стрелки точка вне области)

Точность нахождения границы увеличивается при использовании малых углов.

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

где — шаг; — заданная точность.

Если заданы точность и шаг, то угол определяется по формуле

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

Тогда — число, показывающее, во сколько раз следующий шаг меньше предыдущего.

Координаты новой точки находятся по формулам

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

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

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

Изложенные методы использовались для построения областей устойчивости и подобластей с заданным расположением собственных чисел исходной матрицы А системы а также применялись для автоматизации отслеживания линий равного уровня. Программа слежения по контуру без адаптации содержит 337 операторов, с, адаптацией — 425 операторов.

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

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

Рис. 6.12

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

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

Координаты точки определяются по координатам точек помощью формул:

а) при выходе на границу извне

б) при выходе на границу изнутри

Из построения видно, что та из вершин, которая была последней, не отражается. В новом треугольнике отражается та вершина, которая находится в одинаковых условиях с соседней вершиной. В данном случае это вершина так как обе вершины «неустойчивы». Процесс последовательного движения вдоль границы и правила отражения вершин показаны на рис. 6.12, а - и.

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

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

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

2. Пересечение границы образует равносторонний треугольник с вершинами 1—2—3 (рис. 6.12, а).

3. Далее зеркально «отражается» та из вершин, которая находится в одинаковых условиях с соседней вершиной (одинаковые условия означают «устойчивость» или, наоборот, «неустойчивость», обеих вершин. Не отражается та вершина, которая была последней. В данном случае «отражается» вершина 2, так как точки 2 и 3 находятся в одинаковых условиях (устойчивы), а вершина 3 была последней.

4. Образуется новый равносторонний треугольник, в данном случае 1—3—4.

5. Опять зеркально «отражается» та из вершин, которая находится в одинаковых условиях с соседней вершиной (рис. 6.12, б).

6. Далее процесс слежения вдоль границы осуществляется аналогично вышеизложенному принципу (рис. 6.12, в-з).