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


 

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

21150. Основные характеристики МПП общего применения на фольгированном диэлектрике 855.5 KB
  Основные характеристики МПП общего применения на фольгированном диэлектрике Показатель Характеристика Область применения Спецтехника вычислительная техника средства связи Класс точности 1;2; 3 Группа жесткости I IV Рекомендуемые максимальные размеры мм 360 х 420 γ = 033 Материал основания Стеклотекстолит фольгированный например СТФ1 СТФ2 стеклоткань СТП1 Минимальный диаметр отверстия мм Переходное 04 Сквозное 06 Минимальная ширина проводника мм 025 Тип производства Мелкосерийное серийное крупносерийное Методы...
21151. Культура українських земель XIX ст. Національно-культурне відродження 870.53 KB
  У XIX ст. розвиток української культури обумовлювався підпорядкуванням українських земель двом імперіям – Російській та Австро-Угорській. Обидві імперії були багатонаціональними, з титульною (панівною) нацією. І Росія, і Австро-Угорщина проводили колонізаторську політику, підтримували антиукраїнські сили
21152. Поиск и устранение неисправностей в CD-ROM 57.5 KB
  Много неприятностей доставляют и так называемые условные отказы плавающие неисправности когда чтение диска либо внезапно прекращается а потом возобновляется либо производится с ошибками. Конечно многие отказы связаны с дешевыми пиратскими дисками использование которых может нарушить бесперебойную работу устройства. Причем помимо того что информация на таком диске может не читаться использование несбалансированных дисков в высокоскоростных приводах зачастую ведет к разрушению как самого диска он буквально разлетается на мелкие...
21153. Неисправности винчестера 81.5 KB
  Изза сложности работ с парами металла понадобилось много лет для разработки технологии обеспечивающей практически идеальную поверхность диска при разумной стоимости. Эти дорожки содержат специальные файлы DOS основной каталог диска и информацию о распределении дискового пространства. Если головка упадет на эту область DOS не сможет читать с диска вообще и фактически все данные окажутся потерянными несмотря на то что каждый байт данных лежит нетронутый гдето на диске.
21155. Основные определения ПП 122.5 KB
  Печатная плата: 1 крепежные отверстия; 2 концевые печатные контакты; 3 монтажное отверстие; 4 место маркировки ПП; 5 печатный проводник; 6 ориентирующий паз. Односторонняя печатная плата ОПП ПП на одной стороне которой выполнены элементы проводящего рисунка рис. Двусторонняя печатная плата ДПП ПП на обеих сторонах которой выполнены элементы проводящего рисунка и все требуемые соединения в соответствии с электрической принципиальной схемой рис.
21156. ТЕХНОЛОГИЧЕСКИЙ ПРОЦЕСС В ЭЛЕКТРОННОЙ ПРОМЫШЛЕННОСТИ 141.5 KB
  Технологии производства полупроводниковой продукции с субмикронными размерами элементов основана на чрезвычайно широком круге сложных физикохимических процессов: получение тонких плёнок термическим и ионноплазменным распылением в вакууме механическая обработка пластин производится по 14му классу чистоты с отклонением от плоскостности не более 1 мкм широко применяется ультразвук и лазерное излучение используются отжиг в кислороде и водороде рабочие температуры при плавлении металлов достигают более 1500 C при этом диффузионные печи...
21157. Технология Hyper-Threading 701.5 KB
  Фактически технология HyperThreading позволяет организовать два логических процессора в одном физическом. После активации каждый из логических процессоров может самостоятельно и независимо от другого процессора выполнять свою задачу обрабатывать прерывания либо блокироваться. Таким образом от реальной двухпроцессорной конфигурации новая технология отличается только тем что оба логических процессора используют одни и те же исполняющие ресурсы одну и ту же разделяемую между двумя потоками кэшпамять и одну и ту же системную шину....
21158. Технология изготовления печатных плат 70.5 KB
  [2] Процесс изготовления печатной платы [3] Сравнительные характеристики методов производства и обоснование применяемого в данном проекте. [10] Основные характеристики: [11] Основы безопасности производства печатных плат. Особенностями производства ЭВМ на современном этапе являются: Использование большого количества стандартных элементов. Массовое производство стандартных блоков с использованием новых элементов унификация элементов создают условия для автоматизации их производства.