18523

Алгоритмы решения математической модели БИС по постоянному току

Лекция

Информатика, кибернетика и программирование

Лекция 3 Алгоритмы решения математической модели БИС по постоянному току Существует несколько способов решения задачи анализа по постоянному току: Первый способ заключается в решении систем уравнений вида: F x = 0

Русский

2013-07-08

301.5 KB

1 чел.

Лекция 3

Алгоритмы решения математической модели БИС по постоянному току

Существует несколько способов решения задачи анализа по постоянному току:

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

F (x) = 0 ,                                                                  (1)

либо Ax = B (как частный случай).

     Второй способ - анализ «статики через динамику».

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

Математическая модель при этом имеет вид:

                                                             (2)

с дополнительным условием:

= 0 при  t → ∞

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

Третий способ заключается в том, что осуществляется поиск экстремума

некоторой функции Ф (x),  где - искомое решение.

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

 

E                     Y1

                      

                                 1

                      

                       Y2

 Рис. 1. Принципиальная электрическая схема.

В узле 1  выполняется равенство:

I1(φ) - I2(φ) = 0                                                          (3)

Если взять модуль выражения (3), то можно видеть, что в точке решения будет минимум функции:

Ф (х) = | I1(φ) - I2(φ) |=0.                                               (4)

Графически это можно представить в следующем виде (рис. 2)

 I    I2

 I1

     φ

  Рис. 2 Иллюстрация третьего способа

Очевидно, что первый и второй способы требуют решения систем линейных уравнений. Третий подход так же часто включает в себя решение таких систем. Рассмотрим некоторые алгоритмы решения СЛАУ.

                    

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

Представим СЛАУ в виде

A = b,                                                                     (5)

где А – заданная квадратная матрица порядка n, b – заданный вектор-столбец с n-компонентами,  – неизвестный вектор столбец с n-компонентами.

Выделим  три подхода решения таких систем:

  1.  Точные методы. Применяется при решении СЛАУ небольшой размерности.
  2.  Итерационные методы. Применяется при решении СЛАУ средней размерности.
  3.  Вероятностные методы. Применяется при решении СЛАУ большой размерности.

Рассмотрим один из точных методов решения.

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

Недостатком точных методов является большое число арифметических операций.  

Если число ненулевых элементов матрицы размерностью n имеет порядок n2 , т. е. матрица неразреженная, то для современных методов число необходимых операций при решении СЛАУ будет порядка n3 .

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

Метод последовательного исключения неизвестных. Метод Гаусса.

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

                        

                                                         (6)

                                                         (7)

Второе уравнение системы (7) получено умножением первого уравнения этой системы на коэффициент  a21/a11 и сложением со вторым  уравнением системы (6). Третье уравнение -  путем умножения первого уравнения этой системы на коэффициент  a31/a11 и сложением с третьим уравнением системы (6).

                                                         (8)

Третье уравнение системы (8) получено умножением второго уравнения  системы (7) на коэффициент  a32/a22 и сложением с третьим  уравнением системы (6).

Описанные этапы приводят к уравнению вида:    

Ux=Mb,

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

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

Для того чтобы этого избежать применяются:

  1.  Масштабирование коэффициентов. Подход заключается в «отбрасывании» порядков при коэффициентах уравнений.
  2.  Метод Гаусса с выбором ведущего элемента. Отличие его от выше описанной схемы состоит в том что на к-ом шаге в качестве ведущего элемента берется наибольший по абсолютной величине элемент в неприведенной части к-ого столбца. Строка, содержащая этот элемент переставляется с к-ой строкой. Так же переставляются элементы правой части.

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

Дополнительная информация приведена в Приложении 2.

Методы решения моделей по постоянному току. Линейный и нелинейный случаи (итерационные методы решения)

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

ƒ(х)=0.                                                               (9)

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

x=F(x)                                                               (10)

 

Целью  алгоритма является нахождение x=x*, которое сводит уравнение (10) к тождеству. Преобразуем уравнение (10) к виду

Y=x             Y= F(x).                                                     (11)

Тогда геометрическая интерпретация алгоритма будет выглядеть следующим образом (см. рис. 3)

Рис. 3. Геометрическая интерпретация алгоритма неподвижной точки.

Предполагаем, что мы начинаем итерационную процедуру выбрав х=х0, в результате получаем х1. Если  |x*-x1|<|x*-x0|, то выбор начального приближения х1 лучше, чем х0. В качестве начального приближения выбираем х1  и так далее пока

 |xк+1-xк|<ε.                                                               (12)

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

xк+1=F(xк)                                                         (13)

Критерий, гарантирующий сходимость, определяется следующим образом (принцип сжатых отображений): если  F(x) есть сжатие n-мерного пространства Rn в  Rn, т.е. константа  L<1, такая что

 || F(y)-F(x)||<||y-x|| , х,у Є Rn ,                                     (14)

 то  F(y)  имеет единственную неподвижную точку.

Последовательные итерации приводят к этой неподвижной точке. Если L близка к единице, то сходимость может быть достаточно медленной.

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

,                                                 (15)

где  - матричная неособенная функция от .

Ясно, что  может быть случайной функцией. Различные выборы  ведут к различным характеристикам сходимости. Большинство итерационных методов решения систем нелинейных уравнений является специальными случаями уравнения (15).

Например, , где - матрица Якоби.

Подставляя в формулу (15), получим  

.                                                      (16)

То есть приходим к методу Ньютона - Рафсона.

Метод Ньютона  применяется на практике в большинстве случаев, поэтому остановимся на нем подробнее.

Известно, что всякую функцию в окрестности решения можно разложить в ряд Тейлора

                (17)

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

,

=0

и вторая производная

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

Погрешность решения

.                                                             (18)

Нетрудно видеть, что  

.                                                    (19)

Если необходимо определить погрешность решения и сходимость, то нужно учесть второй порядок.

Об итерационном процессе, для которого ошибка  удовлетворяет соотношению

.                                                       (20)

говорят, что он имеет сходимость порядка p, то есть метод Ньютона имеет квадратичную сходимость. Например, на k-ой итерации погрешность решения:

, , ,  .

То есть, достаточно шести итераций для того, чтобы погрешность стала очень маленькой.

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

Локальная методическая погрешность

.

Различные подходы к выбору матрицы  (помимо метода Ньютона) приводят к методам Якоби, Гаусса–Зейделя, методу последовательной верхней релаксации. Перечисленные методы относятся к релаксационным.

Метод Якоби

Этот метод можно отнести к методам простой итерации.

В основе методов простой итерации лежит преобразование уравнения

                                                               (21)

к виду:

                                                            (22)

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

 ,                                                        (23)

где     Р – может быть произвольной функцией.

 Теорема о достаточном условии сходимости метода простой итерации. Если  < 1, то система уравнений (22) имеет единственное решение и итерационный процесс сходится к решению со скоростью геометрической прогрессии.

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

Метод Якоби:

                                          (24)

и т.д.

В общем случае

.

Для нелинейного случая

                                                   (25)

Метод Гаусса – Зейделя

В основе метода лежит уравнение вида:

,                                                       (26)

где L, U – нижнее и верхнее треугольное разложение матрицы А, D – диагональная матрица.

Без данного преобразования метод Гаусса-Зейделя выглядит следующим образом:

                                     (27)

                                                         (28)

Метод поверхностной верхней релаксации

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

                                                             (29)

- приращение, полученное по методу Гаусса-Зейделя,  - диагональная матрица параметров релаксации.

Общее условие сходимости: все собственные значения матрицы по модулю < 1.

Анализируя эти условие можно предположить, что для сходимости метода Якоби матрица А уравнения (21), должна быть близка к диагональной, а для сходимости метода Гаусса-Зейделя – почти нижней треугольной формы, т.е. условием сходимости обоих методов является преобладание диагональных элементов.

Рис.4 Иллюстрация метода Гаусса-Зейделя:а) сходится; б) расходится ;в) цикл.

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

Сравнивая рисунки 4а и 4б видно, что сходимость метода Гаусса-Зейделя может изменять характер при перестановке уравнений.

В случае, если матрица А симметрична, выполняется теорема.

Пусть А – вещественная симметричная положительно определенная матрица, тогда метод Гаусса-Зейделя сходится. Рассмотрим решение ММС методом Гаусса-Зейделя для схемы, представленной на рис.

Представим математическую модель схемы в виде:

Решим ее точным методом и методом Гаусса-Зейделя

                                                    (30)

 

                  

     Рис. 5 Эквивалентная схема.

                

Из системы (30) получим следующие уравнения:

                                                            (31)

Рассмотрим итерационную процедуру:

Из уравнения (31):

Введем погрешность:                                                                                               

Подставим в формулы погрешности уравнения (31) в преобразованном виде:

Таким образом, выражения для погрешностей примут вид:

Можно показать, что:

Условие сходимости к решению:  

Нетрудно видеть, что сходимость уравнений гарантируется при

     

Для приведенного примера

   при , то есть скорость сходимости к решению . Отметим, что при использовании МУП формируется структурно-симметричная матрица. Следовательно, при перестановке уравнений в полученной системе характер сходимости не меняется.

б

в

Y1=1

Y2=5000

Y3=1


 

А также другие работы, которые могут Вас заинтересовать

82588. Тормозная система 132.23 KB
  Второе назначение тормозной системы удержание автомобиля в неподвижном состоянии относительно дорожного покрытия на время стоянки. По способу привода в действие тормозные системы подразделяются на: Гидравлические Пневматические Механические Электромеханические Электропневматические ...
82589. Тракторы МТЗ-80 «Беларус» и МТЗ-82 «Беларус» 1.02 MB
  Введение МТЗ80 Беларус и МТЗ82 Беларус - марка универсально-пропашных колёсных тракторов выпускаемых Минским тракторным заводом с 1974 года по настоящее время в 2000-х годах под маркой Беларус 80 и Беларус 82. Тракторы МТЗ 80 и МТЗ 82 являются глубокой модернизацией выпускавшихся ранее...
82590. Философия экзистенциализма 24.39 KB
  Поскольку экзистенция есть осознание человеком своей конечности временности то основной характеристикой бытия является время. Но внутреннее переживание человеком будущего есть не что иное как страх смерти осознание человеком своей конечности.
82591. Этапы развития цитологии 49.38 KB
  Микроскоп - это, вероятно, самый широко распространенный инструмент биолога. Микроскоп внёс в биологию много нового и специфического, с его помощью был создан особый раздел науки о жизни-цитология. Благодаря ему была открыта новая область видения: микроскоп, как нередко говорят, «сделал доступным наблюдению новый мир».
82592. Ценовая политика фирмы 37.27 KB
  Нас со всех сторон окружают цены. Для того чтобы продать свой товар или услугу на рынке производитель должен назначить на них цены которые были бы приемлемы покупателям иначе их невозможно будет удачно продать на рынке.
82593. Выдающиеся полководцы Великой Отечественной войны 79.5 KB
  Полководец – это военный деятель или военачальник, непосредственно руководящий вооруженными силами государства или стратегическими, оперативно-стратегическими объединениями (фронтами) во время войны и добившийся высоких результатов в искусстве подготовки и ведения военных действий.
82594. Содержание и назначение расходов государственного бюджета 138.5 KB
  Расходы бюджета согласно Бюджетному кодексу РФ - это выплачиваемые из бюджета денежные средства, за исключением средств, являющихся источниками финансирования дефицита бюджета. В более широком смысле это система денежных отношений, связанная с экономико-правовым регулированием процесса...
82595. Система дошкольного образования 139.5 KB
  Система дошкольного образования Республики Беларусь обеспечивает реализацию конституционного права родителей на образование ребенка при первом же обращении их в органы образования. Каждой семье, каждому ребенку предоставляются возможности в получении качественного дошкольного образования...
82596. Основные течения философии ХIХ в. (позитивизм, марксизм, философия жизни, феноменология) 40.49 KB
  Философия XIX века включает различные философские течения и школы в том числе: романтизм и идеализм на подъеме немецкой философии противоположное движение позитивизм во Франции и Англии материализм Маркса и Фейербаха философия отдельных великих мыслителей Шопенгауэр Ницше Кьеркегор неокантианство...