Главная > Разное > Метод конечных элементов для радиоинженеров и инженеров-электриков
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.4. Время и память ЭВМ, необходимые для треугольного разложения

Для оценки эффективности метода треугольного разложения оценим общее время работы и объем памяти ЭВМ. Обе оценки будут приведены для полной (полностью заполненной) матрицы; будут рассмотрены также упрощения, возникающие в случае разреженных матриц.

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

строки треугольной матрицы, определяется суммой операций, требуемых для нахождения элементов этой строки

кроме того, добавляется еще одна операция — извлечение квадратного корня. Количество операций, необходимых для вычисления всей матрицы, равно сумме операций, необходимых для преобразования отдельных строк

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

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

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

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

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

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

Для выполнения обращения и записи обращенной матрицы необходим объем памяти, больший, чем при вычислении треугольных множителей, и при этом он зачастую намного больше. Рассмотрим вновь уравнение (7.9), определяющее операции, необходимые для вычисления элемента треугольной матрицы Предположим, что элемент исходной матрицы коэффициентов равен нулю. Из (7.9) видно, что соответствующий элемент также равен нулю. Далее, если элементы равны нулю, то в сумме (7.9) все слагаемые обращаются в нуль; таким образом, должны обращаться в нуль и соответствующие элементы Конечно, это утверждение не выполняется для всех нулевых элементов матрицы Если в оставшейся части есть какие-либо ненулевые элементы, то сумма в формуле (7.9) в общем случае не обращается в нуль и соответствующий элемент скорее всего также будет отличен от нуля. Таким образом, можно заключить, что ненулевые элементы в левой части любой строки в общем случае всегда соответствуют самым левым ненулевым элементам той же строки матрицы но в области между этими элементами и диагональю матрица может быть более плотной, чем матрица

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

<< Предыдущий параграф Следующий параграф >>
Оглавление