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

7.5. Ленточная и профильная формы записи матрицы

Когда треугольное разложение выполнено, то обычно оказывается, что нижняя треугольная матрица плотнее (содержит меньше нулей), чем исходная матрица. Как было указано выше, самые левые ненулевые элементы в любой строке матрицы должны в общем случае совпадать с самыми левыми ненулевыми элементами в соответствующей строке исходной матрицы Иными словами, все нули на левом крае матрицы в разложении сохраняются. Нулевые элементы, лежащие справа от самого левого ненулевого элемента, наоборот, в общем случае не воспроизводятся; при этом говорят, что они дополняются. Конечно, в результате численных операций любой отдельный элемент матрицы может оказаться нулевым. Такие нули иногда называют «вычисленными нулями». Рассматриваемые же здесь нули являются следствием топологической структуры матрицы. Они остаются нулями в любой матрице с такой же структурой независимо от ее численных значений и называются «структурными нулями». Для примера рассмотрим матрицу Элементы в этой матрице нулевые. Но сравнение с формулой (7.11) показывает, что они дополняются в процессе разложения. С другой стороны, элементы становятся в нулевыми элементами в результате численных операций. Для проверки этого достаточно выполнить разложение для другой матрицы с такой же структурой, как но с иными численными значениями элементов. Значения в матрице не всегда остаются нулевыми, хотя левые крайние нули сохраняются.

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

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

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

заполняются нулями. Например, матрица в (7.10) может быть записана в едином массиве как

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

Преимуществом ленточной записи является простота: необходим лишь один новый информационный параметр — полуширина Но и эта форма записи может оказаться относительно малоэффективной, так как многие строки могут содержать еще и структурные нули. В самом деле, в записи вида (7.19) присутствуют четыре структурных нуля. Существует метод так называемой профильной записи, при котором их можно исключить. Для этого записываются только те члены каждой строки, которые расположены между самыми левыми ненулевыми элементами и диагональю. Матрица (7.10) записывается таким способом в виде одномерного массива

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

В рассматриваемом здесь случае требуемый объем записи для сокращен до 22 элементов, к которому следует

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

Существует еще один метод экономии объема памяти. Тщательное рассмотрение уравнений (7.6) — (7.11) показывает, что после вычисления элементов матрицы соответствующий элемент больше никогда не используется. Следовательно, нет необходимости запоминать ни ни достаточно записать в память лишь один из массивов, разместить там и затем по мере выполнения разложения записывать туда же Если же матрица понадобится для каких-либо целей позднее, то ее можно ввести с любого внешнего запоминающего устройства. Процедуры треугольного разложения, прямого исключения и обратной подстановки остаются неизменными для матриц, записанных в компактной форме. Однако изменения в записи данных приводят к необходимости менять систему индексов (т. е. индексацию массивов в программах). Поскольку нет необходимости выполнять операции с крайними левыми нулями, то в суммах (7.7) и (7.9) можно проводить суммирование, начиная не с (левый край полной матрицы), а от первого ненулевого элемента. Таким образом, формулу (7.9) можно упростить

где для ленточной записи нижний предел суммирования равен

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

Аналогично следует ограничить и нижний предел суммирования в (7.7).

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

Следует отметить, что элементы строки вычислены с использованием элементов строки, непосредственно

предшествующей Но строки с номерами, меньшими, чем не используются. Следовательно, нет надобности запоминать строки в ОЗУ, необходимы только строки от до Таким образом, ОЗУ необходимо для хранения элементов ленточной записи для строк, или чисел. Число столбцов разреженной матрицы зачастую значительно меньше, чем общее количество ее строк Поэтому во многих больших программах используется внешнее хранение информации, при котором матрица ленточной записи) записывается на диске, ленте или другом внешнем носителе. Треугольное разложение затем выполняется путем вычисления одной или более строк записи их на выходном устройстве и затем переносом оставшихся строк в ОЗУ и считыванием с одной или более дополнительных строк Матрицы пропускаются таким образом через память, при этом в них одновременно находятся только по менее) строк. Подобным образом обрабатывают матрицы порядка с шириной порядка 500. Матрицы размером 5-103 при для такого «внешнего» треугольного разложения и последующего решения уравнений требуют объема ОЗУ около 125 -103 слов, что вполне соответствует возможностям современных ЭВМ среднего класса. Запись самой матрицы в ленточной форме требует 25-105 слов памяти, или 125-105 слов (если разреженность не используется). В этом последнем случае для записи были бы необходимы тысячи метров магнитной ленты.

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