Численные методы решения алгебраических уравнений

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

Линейные уравнения.

В программах автоматизации схемотехнического моделирования (ACM) решение системы линейных уравнений.

(1) Ах = Ь, где, А — квадратная матрица, b — вектор, является не только самостоятельной задачей, но и служит одной из наиболее часто повторяющихся процедур при решении других, более сложных функциональных задач, например при решении систем нелинейных уравнений.

В большинстве случаев для решения системы (1) на ЭВМ используются прямые методы, обеспечивающие решение за конечное число операций.

Прямые методы решения (1) можно разделить на зри группы [15]: => методы предварительного разложения матрицы, А на сомножители;

=> методы обращения матрицы, когда решение системы (1) отыскивается в виде х = A 'b, при этом обращение матрицы может быть выполнено с использованием методов первой группы;

=> методы решения (1) с матрицей, А специального вида, например, ленточного диагонального вида, который имеют схемы с цепочной (каскадной) структурой без обратных связей.

В программах ACM час то применяют методы первой группы, среди которых широкое распространение получил метод прямого Ш-разложения. Суть метода состоит в представлении исходной матрицы в виде произведения матриц A = LU, после чего система (1) решается последовательно как две подсистемы:

где L, U — нижняя и верхняя треугольные матрицы соответственно.

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

Следует выделить две проблемы, возникающие при решении (1):

=> сохранение высокой степени разреженности матрицы А в процессе решения. Количество ненулевых элементов в каждой строке исходной.

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

=> сохранение точности на уровне ошибок округления исходных данных. Из-за конечности разрядной сетки при решении (1) неизбежны ошибки вследствие округления промежуточных результатов. Эти ошибки в процессе решения могут быстро возрастать, что приведет к потере точности результата.

Специфика решения системы (1) состоит в необходимости высокой точности решения и одновременно сохранения разреженности матрицы А. Машинные алгоритмы различаются методом упаковки ненулевых элементов и критериями упорядочения для разреженности и точности.

Метод упаковки ненулевых элементов отражает способ хранения матрицы, А в виде списков. Список представляет собой одномерный массив, содержащий информацию о значении ненулевых элементов матрицы А, их номерах строк и столбцов. Методы упаковки разделяются:

=> на универсальные методы, пригодные для матриц любого вида. Они основаны на замене двумерного массива (матрицы А) одним или несколькими одномерными массивами (списками). По содержанию различают:

• • списки значений ненулевых элементов;
• • списки позиционных указателей, содержащие номера строк (столбцов) ненулевых элементов;
• • списки разделителей. Разделители позволяют выделять в отдельные группы ненулевые элементы, находящиеся в одной строке или столбце. В качестве разделителей можно использовать число ненулевых элементов в строке (столбце), порядковые номера первых или последних ненулевых элементов в строке (столбце) матрицы А;

=> на специальные методы, учитывающие структуру заполнения матрицы ненулевыми элементами. Они ориентированы на определенную структуру матрицы А.

Критерий упорядочения для разреженности определяет порядок обработки уравнений в системе (1), при котором число новых ненулевых элементов матрицы, А будет минимальным. Основными характеристиками этих критериев являются:

=> длина просмотра— количество уравнений, анализируемых для однократного применения критерия;

=> глубина просмотра — количество шагов разложения, необходимых для однократного применения критерия;

=> ширина просмотра — количество различных анализируемых порядков разложения на h шагах, необходимое для однократного применения критерия;

=> мощность критерия — количество уравнений в последовательности разложения, определяемое при однократном применении критерия. Пример критерия: i < у, если число исходных (до разложения) ненулевых элементов /-й строки матрицы меньше числа исходных ненулевых элементову'-й строки.

Критерий упорядочения применяется на каждом шаге разложения, в результате чего определяется номер уравнения (строки матрицы А), обработка которого дает минимальное число новых ненулевых элементов. Применение критерия на каждом из п шагов дает последовательность номеров уравнений, следуя которой при разложении матрицы, А получаем число новых ненулевых элементов, близкое к минимально возможному. На рис. 1 показана типовая структура матрицы, А после упорядочения и структуры Lи U-матриц после LU-разложсния.

Рис. 1. Структуры L и U-матриц после LU-разложения и типовая структура матрицы, А после упорядочения.

Критерии упорядочения для точности. Ошибка в вычислении коэффициента а$ матрицы, А в процессе решения системы (1) может быстро возрастать, приводя к большим ошибкам результата. В связи с этим вычислительный процесс при решении (1) нужно строить с учетом требований минимизации ошибок на каждом шаге решения. Для уменыпе;

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

О конфликтах между критериям и. Критерии упорядочения для разреженности и точности могут приводить к разным последовательностям обработки уравнений. Для разрешения конфликтов между ними устанавливается допустимое минимальное значение е диагонального элемента <*, (/ = 1,…, п). Если все а" больше 8, то работает критерий упорядочения для разреженности, если для некоторых ац это правило не выполняется, то приоритет отдается критерию упорядочения по точности и строка с минимальным значением ац обрабатывается в последнюю очередь. Реализация этого правила требует переупорядочения уравнений, но различным критериям.