ПОИСК Статьи Чертежи Таблицы Методы решения систем линейных алгебраических уравнений из "Основы автоматизированного проектирования " Исключение п -1 неизвестных, где —порядок системы (3.32), называют прямым ходом, в процессе которого матрица коэффициентов приобретает треугольный вид. При обратном ходе последовательно вычисляют неизвестные, начиная с х . [c.106] При прямом ходе в соответствии с формулой (3.33) все элементы матрицы, которые первоначально были нулевыми, становятся ненулевыми, а матрица ока-зывается полностью насыщенной. Элементы, становящиеся ненулевыми в процессе гауссовых исключений, называют вторичными ненулями. Вторичные ненули в табл. 3.3 отмечены знаком . . [c.107] Во втором случае меняются местами первое и пятое уравнения. Матрицы коэффициентов имеют вид табл. 3.3 и 3.4, где ненулевые элементы представлены знаком + . Теперь вторичные ненули не появляются, матрица остается разреженной, высокая вычислительная эффективность сохраняется. [c.107] Таким образом, методы разреженных матриц должны включать в себя способы оптимального упорядочения строк и столбцов матриц. Используют несколько критериев оптимальности упорядочения. Простейшим из них является критерий расположения строк в порядке увеличения числа первичных нену-лей, более сложные критерии учитывают не только первичные ненули, но и появляющиеся вторичные ненули. [c.107] Методом разреженных матриц называют метод решения СЛАУ на основе метода Гаусса с учетом разреженности (первичной и вторичной) матрицы коэффициентов. [c.107] Метод разреженных матриц можно реализовать путем интерпретации и компиляции. В обоих случаях создаются массивы ненулевых коэффициентов матрицы (с учетом вторичных ненулей) и массивы координат этих ненулевых элементов. [c.108] При этом вьшгрыш в затратах памяти довольно значителен. Так, при матрице умеренного размера (200 х 200) без учета разреженности потребуется 320 Кбайт. Если же взять характерное значение 9 для среднего числа ненулей в одной строке, то для коэффициентов и указателей координат потребуется не более 28 Кбайт. [c.108] В случае интерпретации моделирующая программа для каждой операции в соответствии с (3.33) при Ф О и Ф О находит, используя указатели, нужные коэффициенты и выполняет арифметические операции по (3.33). Поскольку СЛАУ в процессе анализа решается многократно, то и операции поиска нужных коэффициентов также повторяются многократно, на что, естественно, тратится маппшное время. [c.108] Способ компиляции более экономичен по затратам времени, но уступает способу интерпретации по затратам памяти. При компиляции поиск нужных для (3.33) коэффициентов вьшолняется однократно перед численным решением задачи. Вместо непосредственного выполнения арифметических операций для каждой из них компилируется команда с найденными адресами ненулевых коэффициентов. Такие команды образуют рабочую программу решения СЛАУ, которая и будет решаться многократно. Очевидно, что теперь в рабочей программе будет вьшолняться минимально необходимое число арифметических операций. [c.108] Вернуться к основной статье