19231-1 (Алгоритм компактного хранения и решения СЛАУ высокого порядка), страница 2

Реализация прямого метода Гаусса требует арифметических операций, а обратного - арифметических операций.

1.2. Итерационные методы решения СЛАУ

Метод итераций (метод последовательных приближений).

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

Эффективность применения приближенных методов зависят от выбора начального вектора и быстроты сходимости процесса.

Рассмотрим метод итераций (метод последовательных приближений). Пусть дана система n линейных уравнений с n неизвестными:

Ах=b, (14)

Предполагая, что диагональные элементы aii 0 (i = 2, ..., n), выразим xi через первое уравнение систем x2 - через второе уравнение и т. д. В результате получим систему, эквивалентную системе (14):

Обозначим ; , где i == 1, 2, ...,n; j == 1,2,..., n. Тогда система (15) запишется таким образом в матричной форме

Решим систему (16) методом последовательных приближений. За нулевое приближение примем столбец свободных членов. Любое (k+1)-е приближение вычисляют по формуле

Если последовательность приближений x(0),...,x(k) имеет предел , то этот предел является решением системы (15), поскольку в силу свойства предела , т.е. [4,6].

Метод Зейделя.

Метод Зейделя представляет собой модификацию метода последовательных приближений. В методе Зейделя при вычислении (k+1)-го приближения неизвестного xi (i>1) учитываются уже найденные ранее (k+1)-е приближения неизвестных xi-1.

Пусть дана линейная система, приведенная к нормальному виду:

(17)

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

Таким образом, предполагая, что k-е приближения известны, методом Зейделя строим (k+1)-е приближение по следующим формулам:

где k=0,1,...,n

Метод Ланцоша.

Для решения СЛАУ высокого порядка (1), матрица, коэффициентов которой хранится в компактном нижеописанном виде, наиболее удобным итерационным методом является метод Ланцоша [4], схема которого имеет вид:

(18)

где

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

, (19)

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

(20)

Среднеквадратичную разность необходимо контролировать при выполнении каждых k наперед заданных итераций.

Отдельно следует рассмотреть проблему выбора начального приближения . Доказывается, что при положительно определенной матрице , итерационный процесс (18) всегда сходится при любом выборе начального приближения. При решении контактных задач, когда для уточнения граничных условий в зоне предполагаемого контакта требуется большое количество решений СЛАУ вида (1), в качестве начального приближения для первого расчета используется правая часть системы (1), а для каждого последующего пересчета - решение, полученное на предыдущем. Такая схема позволяет значительно сократить количество итераций, необходимых для достижения заданной точности (19) или (20) [10,11].

2 МЕТОДЫ КОМПАКТНОГО ХРАНЕНИЯ МАТРИЦЫ ЖЕСТКОСТИ

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

Первоначально, с целью выявления связей каждого узла с другими, производится анализ структуры дискретизации области на КЭ. Например, для КЭ - сетки, изображенной на рис. 1, соответствующая структура связей будет иметь вид:

Т
огда, для хранения матрицы жесткости необходимо построчно запоминать информацию о коэффициентах, соответствующих узлам, с которыми связан данный узел. На рис. 2 приведены матрица жесткости и ее компактное представление для сетки изображенной на рис 1 [9].

Текст подпрограммы, реализующий предложенный алгоритм анализа структуры КЭ-разбиения тела, приведен в Приложении 1.

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

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

, (*)

где m – количество степеней свободы (m=1,2,3).

Для прямого преобразования будут справедливы соотношения, обратные к соотношениям (*).

3 ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ

Для проверки предлагаемого метода компактного хранения матрицы жесткости была решена задача о контактном взаимодействии оболочечной конструкции и ложемента [12] (рис. 4).

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

Данная задача решалась методом конечных элементов при помощи системы FORL [5]. Дискретная модель ложемента (в трехмерной постановке) представлена на Рис. 5.

При построении данной КЭ-модели было использовано 880 узлов и 2016 КЭ в форме тетраэдра. Полный размер матрицы жесткости для такой задачи составляет байт, что приблизительно равно 2,7 Мбайт оперативной памяти. Размер упакованного представления составил около 315 Кбайт.

Данная задача решалась на ЭВМ с процессором Pentium 166 и 32 МБ ОЗУ двумя способами – методом Гаусса и методом Ланцоша. Сопоставление результатов решения приведено в Таблице 1.

Таблица 1.

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

ВЫВОДЫ.

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

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

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

ПРИЛОЖЕНИЕ 1

Исходный текст программы, реализующий анализ структуры КЭ-разбиения объекта.

#include

#include

#include

#include

#include

#include "matrix.h"