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

2.1. Cистемы линейных уравнений. Метод Гаусса.

2.2. Разреженные системы уравнений. LU-факторизация.

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

Пусть имеется система линейных алгебраических уравнений (СЛАУ)

, (1)

Где - матрица коэффициентов размером , - вектор-столбец свободных членов, - -мерный вектор переменных:

.

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

Лучшим методом решения СЛАУ для электронных схем является метод -факторизации: метод разложения матрицы на нижнюю - и верхнюю - треугольные матрицы. Преимущество метода -факторизации по сравнению с методом Гаусса состоит в том, что здесь можно не производить операций с нулевыми элементами. Кроме того, решение получается более просто, если изменяется только вектор , или при транспонировании матрицы , что имеет место при расчете динамических схем во временной области, при анализе чувствительности электронных схем и т.д.

Рассмотрим методику представления матрицы системы уравнений (1) в виде произведения нижней и верхней - треугольных матриц (метод Краута):

(2)

,

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

Для поддиагональных элементов, когда , имеем .

Для наддиагональных элементов () имеем .

Отсюда получаем выражения для элементов матриц и

; (3)

; (4)

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

После -разложения матрицы перепишем уравнение (1) в виде

. (5)

Введем вспомогательный вектор

. (6)

Этот вектор легко определяется из уравнения

, (7)

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

получаем

Или в общем виде имеем

, (8)

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

Возвращаемся к (6) и определяем вектор неизвестных

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

, , . (9)

Этот процесс называется обратной подстановкой или обратным ходом(как в методе Гаусса).

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

Анализ выражений (3) и (4) показывает, что при , (); , (), т.е. 1-й столбец совпадает с 1-столбцом , а 1-я строка - это 1-я строка , нормированная на значение .

Далее по формуле (3) следует рассчитать 2-й столбец (), по формуле (4) – 2-ю строку , (), затем 3-й столбец матрицы и 3-ю строку матрицы и т.д. Последним вычисляется элемент . С учетом того, что нулевые элементы матриц и , а также единичную диагональ заполнять не нужно, то матрицу в процессе вычислений можно записать в нижний треугольник матрицы , а - в верхний треугольник (если исходную матрицу сохранять не нужно).

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

В результате имеем следующий алгоритм -факторизации:

1. : , ,

2. : , ,

, ,

3. : ,

Прямая подстановка:

, ;

Обратная подстановка:

,

Проверить индексы! Скорее всего, есть опечатки

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

Поиск по сайту: