Алгоритм компактного хранения и решения СЛАУ высокого порядка - (реферат)
p>После того как все yi определены по формулам (12), подставляем их в уравнение (10). Так как коэффициенты bijопределены (8), то значения неизвестных, начиная с последнего, вычисляем по следующим формулам:К прямым методам, использующим свойство разреженности А, можно отнести: алгоритм минимальной степени, алгоритм минимального дефицита, древовидное блочное разбиение для асимметричного разложения, методы вложенных или параллельных сечений и др.
Метод Гаусса.
Пусть дана система
Ax = b
где А – матрица размерности m x m.
В предположении, что , первое уравнение системы
,
делим на коэффициент , в результате получаем уравнение
Затем из каждого из остальных уравнений вычитается первое уравнение, умноженное на соответствующий коэффициент. В результате эти уравнения преобразуются к виду
первое неизвестное оказалось исключенным из всех уравнений, кроме первого. Далее в предположении, что, делим второе уравнение на коэффициент и исключаем неизвестное из всех уравнений, начиная со второго и т. д. В результате последовательного исключения неизвестных система уравнений преобразуется в систему уравнений с треугольной матрицей
Совокупность проведенных вычислений называется прямым ходом метода Гаусса. Из -го уравнения системы (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, соответствующая структура связей будет иметь вид: № узла
1
2
3
4
5
6
7
Связи
1, 2, 5, 6, 7
1, 2, 3, 6
2, 3, 4, 6
3, 4, 5, 6, 7
1, 4, 5, 7
1, 2, 3, 4, 6, 7
1, 4, 5, 6, 7
Тогда, для хранения матрицы жесткости необходимо построчно запоминать информацию о коэффициентах, соответствующих узлам, с которыми связан данный узел. На рис. 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.
Время решения (сек)
Метод
Гаусса
280
2. 2101
-2. 4608
1. 3756
-5. 2501
1. 7406
-2. 3489
Метод Ланцоша
150
2. 2137
-2. 4669
1. 3904
-5. 2572
1. 7433
-2. 3883
