Ченцов С.В. Автоматизированное проектирование средств и систем управления

Подождите немного. Документ загружается.

ТЕМА 4. МЕТОДЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ: МЕТОДЫ АНАЛИЗА ССУ

Лекция 7. Алгоритмы и методы анализа статических режимов ССУ в интегрированных САПР



Автоматизированное проектирование средств и систем управления. Курс лекций

101

а б

Рис.7.1. а – ленточно-диаганальная; б – блочно-диагональная

Например, электронные схемы с цепочной структурой без ОС имеют

ленточную структуру матрицы. Для решения систем с ленточными матрица-

ми наиболее эффективным является метод прогонки при решении трехдиаго-

нальных систем















............

..aaa

..aa

343332

232221

000

1211

.



Метод прогонки состоит из двух этапов: прямая прогонка, заключаю-

щаяся в расчёте прогоночных коэффициентов

i,i

i, i

-a











,

i,i

i, i

-a















.

p = 0 при i = 1,2,..,n.

Обратная прогонка состоит в расчёте

V с 1



p V ,

V =

i

1i

p при i = n-1, n-2,..,1.

Достоинство: вместо хранения в памяти трёх диагоналей матрицы А и

вектора

В можно организовать хранение только двух векторов L и P, необхо-

димых для обратной прогонки. Эта задача решается на этапе формирования

ММ, причем модель формируется не в виде

AV = B, а в виде векторов L и P.

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

анализа.

Основными методами решения систем ЛАУ второй группы – итераци-

онными методами являются линейные стационарные методы первого поряд-

ка, формула которых имеет вид:

C HV V









ТЕМА 4. МЕТОДЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ: МЕТОДЫ АНАЛИЗА ССУ

Лекция 7. Алгоритмы и методы анализа статических режимов ССУ в интегрированных САПР



Автоматизированное проектирование средств и систем управления. Курс лекций

102

где i = 0, 1, 2,... – номер итерации; H – итерационная матрица, выбор которой

является решающим;

С – соответствующий известный вектор.

Метод линейный и стационарный, так как

Н и С не зависят от номера

итерации и от

. Порядок метода определяется количеством предыдущих

значений

V, использованных в данном методе. Основные характеристики

данного метода – сходимость итераций и скорость сходимости к точному

решению

V*.

Выражение

C HV V

i 1i







сходится, если для любого начального при-

ближения

последовательность

V ,

V ,..., определяемая с помощью линейно-

го стационарного метода, сходится к

V*. Необходимое и достаточное условие

сходимости:



ρ(H) ,

где

ρ(H) – спектральный радиус матрицы H.

В зависимости от выбора

H и C получаются различные итерационные

методы: простой итерации, Зейделя, релаксационные. Для практической реа-

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

димости и установить критерий окончания итерационного процесса.

Введем вектор ошибки на

k-ой итерации E

= V

– V*. Можно показать,

что

EHE

 , где ║E║,║H║ – соответствующие векторные и матрич-

ные нормы. Следовательно,

║H

║ определяет, во сколько раз была уменьше-

на норма ошибки после

k-итераций, т. е. скорость сходимости. Способы ус-

корения сходимости весьма разнообразны, но часто основываются на оценке

максимального

M(H) и минимального m(H) по модулю собственных значе-

ний матрицы

H. Идеальным критерием окончания итераций является норма

вектора ошибки

, но непосредственно ее определить невозможно, так как

нет точного решение

V*. Поэтому для итерационного процесса при решении

системы (6.3)

вводится вектор приращений

1kk k

V V V







, связанный с век-

тором ошибки следующим равенством

k k

V (H I)E ,







где

I – единичная матрица. Переходим к оценке по нормам

VIHE 

1

)(. Это соотношение можно представить в виде

VHE 

1

))(1( .

(7.2)

Из (7.2)

следует, что вектор приращений можно использовать в качест-

ве критерия окончания итераций, но при 1ρ(H)  применяют соотношение и

оценивают M(H).

ТЕМА 4. МЕТОДЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ: МЕТОДЫ АНАЛИЗА ССУ

Лекция 7. Алгоритмы и методы анализа статических режимов ССУ в интегрированных САПР



Автоматизированное проектирование средств и систем управления. Курс лекций

103

Недостатками итерационных методов являются малая скорость сходи-

мости, низкая точность. Достоинствами – экономичность с точки зрения за-

трат времени и памяти на одну итерацию.

Рассмотрим применение метода Гаусса – Зейделя (его преимущества:

простота, лёгкость программирования; линейная скорость сходимости) на

примере решения системы

11 1 12 2 13 3 1

21 1 22 2 23 3 2

31 1 32 2 33 3 3

aV aV aV b









Предположим, что диагональные элементы отличны от нуля (в против-

ном случае можно переставить уравнения). Выразим неизвестные из первого,

второго и третьего уравнений системы



1122133

2211233

3311322

vbavav





Зададим некоторые начальные (нулевые) приближения значений неиз-

вестных

(0)

1 1

V V ,V V ,V V  . Подставляя эти значения в правую часть

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

ных:





)(

vab

)(

313

2121



,







)(

vab

)(

323

1212



,







)(

vab

)(

232

1313



.



ТЕМА 4. МЕТОДЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ: МЕТОДЫ АНАЛИЗА ССУ

Лекция 7. Алгоритмы и методы анализа статических режимов ССУ в интегрированных САПР



Автоматизированное проектирование средств и систем управления. Курс лекций

104

Итерационный процесс продолжается, пока значения

(k)(k)(k)

, V , VV

321

не станут близкими с заданной погрешностью к значениям

)(k-)(k-)(k-

, V , VV

Развитие метода Зейделя – метод релаксации.

(

(k ) (k) (k)

iiii

V V V V ),







где  – релаксационный параметр.

Условие сходимости (10.6)

выполняется, если 0 <  < 2. Оптимальным

значением релаксационного параметра называется значение 

опт

, при кото-

ром достигается минимум ρ(Н

). На практике для многих случаев

опт

(1 1 ( ))





,

так как ρ(Н) < 1, то 1<



опт

<2.

Математическая модель технической системы для анализа статических

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

уравнений (НАУ) вида [6

,0F(V)





(7.3)

где V – вектор фазовых переменных.

В отличие от систем ЛАУ для решения систем НАУ не существует

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

ние. Поэтому основными методами решения систем НАУ являются итераци-

онные методы, в основе которых лежит принцип последовательных прибли-

жений, выполняющихся по формуле [7

, 10]:

)(VV





,



где )(

V – некоторый функционал исходной системы, который строится так,

чтобы обеспечить выполнение условия

VVlim





, где V*= (V

*, V

*, …,

*) – решение системы.

ТЕМА 4. МЕТОДЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ: МЕТОДЫ АНАЛИЗА ССУ

Лекция 7. Алгоритмы и методы анализа статических режимов ССУ в интегрированных САПР



Автоматизированное проектирование средств и систем управления. Курс лекций

105

Основными характеристиками методов решения систем НАУ являются

скорость сходимости и область сходимости, определяемая условиями сходи-

мости [12

Скорость сходимости оценивается по изменению расстояния до точки

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

сходимости, если выполняется условие

k*k*

VVaVV 

1

и квадратич-

ную скорость сходимости

1 k*k*

VVaVV 



, где a ≤ 1, V* – точка ре-

шения,

VV  – какая-либо норма вектора. Теоретические условия сходи-

мости различны для различных методов и не пригодны в практических рас-

четах схем. Исходя из этого, на практике, учитывая, что V* неизвестна, про-

верку сходимости метода выполняют на каждой итерации по условию

11 



kkkk

VVVV .

(7.4)

Условие (7.4)

не априорное условие сходимости, а лишь средство кон-

троля сходимости. Область значений фазовых переменных, в которой выпол-

няется условие (7.4)

, называется областью сходимости. Сходящийся вычис-

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

)( или





V .

При расчете электронных устройств СУ эти условия обычно неизвест-

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

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

сти в возможно большей области начальных приближений и в более широ-

ком диапазоне численных значений параметров функции F(V) = 0. При рас-

чете больших схем (n > 100) кроме алгоритмической на

дежности метода до-

бавляется требование минимизации вычислительных затрат, т. е. уменьшения

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

нения одной итерации и объемом памяти необходимого для реализации ме-

тода. Численных методов, удовлетворяющих этим требованиям, нет, поэтому

при принятии решения о включении методов решения систем НАУ в состав

САПР необходимо обеспечивать компромисс.

Рассмотрим основные классы методов решения систем НАУ, исполь-

зуемых в САПР при анализе технических систем.

Первая группа – прямые ил

и итерационные методы решения систем

НАУ:

метод простых итераций;

метод Ньютона;

ТЕМА 4. МЕТОДЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ: МЕТОДЫ АНАЛИЗА ССУ

Лекция 7. Алгоритмы и методы анализа статических режимов ССУ в интегрированных САПР



Автоматизированное проектирование средств и систем управления. Курс лекций

106

метод Ньютона – Брайдена.

При решении системы уравнений ММ технического объекта методом

простых итераций ее представляют в виде:

1112

2212

V F(V, V , .., V )

V F(V, V, .., V )

. . . . . . . . .

Vn Fn(V , V , .., Vn)





Алгоритм напоминает метод Гаусса – Зейделя. Пусть в результате пре-

дыдущей итерации получены значения неизвестных V

= а

, V

= а

,.., V

= а

тогда выражение для следующих итераций:

1112

2212

12 1n

nn n-

V F (a , a , .., a )

V F (V , a , .., a )

. . . . . . . . . .

V F(V, V , .., V , a





Итерационный процесс продолжается, пока изменения неизвестных в

двух последовательных итерациях не станут малыми:





.По ско-

рости сходимости метод простых итераций относится к методам с линейной

скоростью сходимости. Условия сходимости для метода простых итераций:

1max 







или

1max





,

где



– собственные значения матрицы Якоби. Количественные формули-

ровки условий сходимости для других методов решения систем НАУ сложны

и на практике не используются.

При включении метода простых итераций в состав САПР нужно учи-

тывать следующие недостатки: начальные приближения должны быть близ-

кими к истинному решению, иначе итерации могут не сходиться; начальное

приближение V

задается пользователем на основе знания им приближенного

ТЕМА 4. МЕТОДЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ: МЕТОДЫ АНАЛИЗА ССУ

Лекция 7. Алгоритмы и методы анализа статических режимов ССУ в интегрированных САПР



Автоматизированное проектирование средств и систем управления. Курс лекций

107

решения системы (предметной области исследования объекта проектирова-

ния), либо выбирается автоматически, как в методе движущейся в области

сходимости.

Среди итерационных методов решения систем НАУ в САПР часто ис-

пользуют метод Ньютона. Его главное достоинство – высокая скорость схо-

димости. В основе лежит использование разложения функции

0),....,,(



VVVF в ряд Тейлора (члены со вторыми и выше производными

отбрасываются). Решение ищут в виде

V 

1

, где

V

– поправка на

(i+1)-итерацию.

Приближение к корню V* производится с выбранного исходного при-

ближения V

. В методе Ньютона поправка определяется как

)(

V 





, где

1

– обратная матрица Якоби, вычисленная на i-ой

итерации. Однако вычисление



неэффективно, поэтому используют ре-

шение системы ЛАУ

)(

Я 

Пусть известны приближенные значения неизвестных а

, а

,.., а

. Зада-

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

Δv .., ,

Δv ,

Δv

, бла-

годаря которым решение системы запишется в виде

11 1

22 2

vaΔv

. . . . . . . . . .

vaΔv





(7.5)

Разложим (7.3)

с учётом (7.5) в ряд Тейлора

( ,.., ) ( ,.., ) .. ,

11 11 1

.....................

( ,.., ) ( ,.., ) .. .

11 1

vv Faa v v

nn n

Fv v Fa a v v

nnn n n



     



     





(7.6)

Левые части системы (7.6)

равны нулю, отсюда получим систему ЛАУ

относительно приращений

...............

.. .

VVF





    













    











(7.7)

ТЕМА 4. МЕТОДЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ: МЕТОДЫ АНАЛИЗА ССУ

Лекция 7. Алгоритмы и методы анализа статических режимов ССУ в интегрированных САПР



Автоматизированное проектирование средств и систем управления. Курс лекций

108

Значения F

, F

,.., F

и их производные вычисляются при v

= а

,... и т. д. Определителем системы (7.7) является Якобиан. Для сущест-

вования единственного решения Я



0 на каждой итерации.

Процесс решения системы НАУ методом Ньютона состоит в определе-

нии приращений

V

к значениям Vi на каждой итерации. При





Vmax

решение прекращается. Сходимость ухудшается с увеличением n.

Достоинства применения метода Ньютона при решении систем НАУ

для анализа статических характеристик объектов проектирования, по сравне-

нию с другими методами: увеличивается скорость сходимости, так как у ме-

тода Ньютона квадратичная скорость сходимости (по сравнению с линейной

скоростью метода простых итераций); всегда имеет область сходимости для

реальных схем. Недостатками являют

ся малый размер области сходимости

(меньше чем для метода простых итераций) и V

нужно выбирать близко к

V*; увеличиваются затраты памяти для размещения матрицы Якоби. Метод

Ньютона эффективен, если F(V) – выпуклая функция, решение с









достигается за 3–5 итераций.

Первый недостаток метода Ньютона привел к появлению второй груп-

пы методов решения систем НАУ, методов, повышающих вероятность схо-

димости метода Ньютона – методы продолжения решения по параметру. Эта

группа методов делится на две подгруппы:

1) с ограниченным параметром:



метод с одной итерацией;



метод движущейся области сходимости;

2) с неограниченным параметром (методы установления):



явные;



неявные.

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

выделяют параметр, влияющий на положение точки корня в пространстве

фазовых переменных. Например, напряжение источника питания U

ип

. Систе-

ма уравнений ММ проектируемого объекта решается методом Ньютона мно-

гократно при ступенчатом изменении параметра.

Пусть при U

ип

, стремящемся к нулю, точное решение V* также стре-

мится к нулю. Тогда при первом решении выбираем V

= 0 и находим значе-

ние V

*, соответствующее U

ип1

. Затем увеличиваем U

ип

и решаем систему

НАУ при V

= V

* и так далее до решения системы уравнений при истинном

значении U

ип

Методы установления – методы анализа, основанные на интегрирова-

нии дифференциальных уравнений ММ технического объекта на большом

интервале времени, т. е. в качестве неограниченного параметра выбирается

время. Как уже отмечалось, достоинством такого подхода является единство

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

Недостатком – увеличение временной емкости программы анализа.

ТЕМА 4. МЕТОДЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ: МЕТОДЫ АНАЛИЗА ССУ

Лекция 7. Алгоритмы и методы анализа статических режимов ССУ в интегрированных САПР



Автоматизированное проектирование средств и систем управления. Курс лекций

109

Третья группа методов – методы оптимизации. Эти методы основаны

на эквивалентности результатов решения системы F(V) = 0 итерационными

методами и минимизации какого-либо из функционалов









FVФ

FVФ )()(

),(

)(





хорошо отработанными методами оптимизации. Количество решений систе-

мы F(V) = 0 равно количеству минимумов. Таким образом, локальные мето-

ды оптимизации можно использовать при расчёте статического режима схем

с одним состоянием равновесия (ключи, усилители). Если схема имеет не-

сколько состояний равновесия (триггеры и т. д.), то локальные методы могут

и не дать нужного решения. Недост

аток: уступает методу Ньютона по скоро-

сти сходимости. В целом методы оптимизации не нашли широкого использо-

вания при расчете схем.

Решение систем АУ как математического описания СУ имеет место во

многих процедурах функционального проектирования. От решения системы

АУ зависит эффективность выполнения проектной процедуры анализа СУ,

поэтому при разработке проектирующей подсистемы нужно правильно вы-

брать метод решения системы АУ для его включения в состав САПР. При

этом нужно учитывать, что численный метод ещ

е не является программи-

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

в определенной последовательности с определенным началом и достижимым

концом. Выбор определенного метода и его преобразование в алгоритм и

программу – попытка оптимизировать исходные положения и поставленные

дополнительные требования [10

К исходным положениям отнесем следующие положения:



постановка задачи и общие предположения решения;



дополнительная информация об исходных данных (специальный тип

матриц, вид числового материала и др.);



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

Дополнительными требованиями являются:



специальные требования к выходным данным (например, точность);



степень универсальности (должна решаться единичная задача или

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

САПР);



минимизация времени счета, ограничение памяти.

Эти условия выбора метода анализа технического объекта или метода

решения системы уравнений ММ проектируемого объекта противоречивы,

ТЕМА 4. МЕТОДЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ: МЕТОДЫ АНАЛИЗА ССУ

Лекция 7. Алгоритмы и методы анализа статических режимов ССУ в интегрированных САПР



Автоматизированное проектирование средств и систем управления. Курс лекций

110

поэтому применяют эмпирические правила выбора методов при решении об

их включении в состав САПР [12



основной принцип выбора метода есть принцип непосредственного

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

ную задачу, а не ведет к решению через решаемые подзадачи (например, соб-

ственные значения вычисляются методом Якоби, а не как корни характери-

стического многочлена);



«математически элегантные» решения часто являются непросматри-

ваемыми относительно распространения ошибок и неустойчивости и числено

неблагоприятными;



теоретическая сходимость при численной реализации не будет га-

рантией сходимости (теоретически расходящиеся методы могут быть чис-

ленно пригодны).

Ко всему перечисленному: ход процесса решения системы уравнений

ММ СУ определяется параметрами управлении, значения которых вычисля-

ют в ходе реализации программы. Так, условиями останова, как правило, яв-

ляются неравенства

или ( ) , 0, 0

1212

VV FV



  

.

В первом случае возникает опасность потери точности при образова-

нии разности, во втором случае при выборе ε

малым ошибка округления

может исказить обрыв или ему помешать.

На эффективность используемого метода оказывают влияние не толь-

ко особенности самого метода, но и особенности решаемой задачи: размер-

ность системы уравнений (n); число обусловленности (z); разрешенность

матрицы Якоби (s). Кроме этого, полезно учитывать особенности архитек-

турной платформы, в частности, быстродействие (Б).

При выборе метода анализа необходим

о ориентироваться на некоторые

диапазоны значений этих факторов, характерных для моделей проектируе-

мых объектов в соответствующей предметной области.

Выбор метода решения систем АУ основан на взаимосвязи

И / БTм n

, где Тм – затраты машинного времени; n – порядок системы АУ,

принимаемый за оценку сложности задачи;

 – среднее число арифметиче-

ских операций, приходящихся на единицу сложности задач на одной итера-

ции; И – среднее число итераций.

Для метода Гаусса И = 1 при n < 50

(2 nn 



, при учете раз-

ряженности (n > 50)



= const. Подсчитано, что 25





для ключевых элек-

тронных схем;

8



для математических моделей с трехдиагональной мат-

рицей.