Алгоритм компактного хранения и решения СЛАУ высокого порядка
B на вектор-столбец x является вектором-
столбцом, который обозначим через y:
Bx=y. (10)
Тогда уравнение (9) перепишем в виде:
Cy=b. (11)
Здесь элементы сij известны, так как матрица А системы (7) считается
уже разложенной на произведение двух треугольных матриц С и В.
Перемножив матрицы в левой части равенства (11), получаем систему
уравнений из которой получаем следующие формулы для определения
неизвестных:
[pic]
неизвестные yi удобно вычислять вместе с элементами bij.
После того как все yi определены по формулам (12), подставляем их в
уравнение (10).
Так как коэффициенты bij определены (8), то значения неизвестных,
начиная с последнего, вычисляем по следующим формулам:
[pic]
К прямым методам, использующим свойство разреженности А, можно отнести:
алгоритм минимальной степени, алгоритм минимального дефицита, древовидное
блочное разбиение для асимметричного разложения, методы вложенных или
параллельных сечений и др.
Метод Гаусса.
Пусть дана система
Ax = b
где А – матрица размерности m x m.
В предположении, что [pic], первое уравнение системы
[pic], [pic]
делим на коэффициент [pic], в результате получаем уравнение
[pic]
Затем из каждого из остальных уравнений вычитается первое уравнение,
умноженное на соответствующий коэффициент [pic]. В результате эти уравнения
преобразуются к виду
[pic]
первое неизвестное оказалось исключенным из всех уравнений, кроме
первого. Далее в предположении, что [pic], делим второе уравнение на
коэффициент [pic] и исключаем неизвестное из всех уравнений, начиная со
второго и т.д. В результате последовательного исключения неизвестных
система уравнений преобразуется в систему уравнений с треугольной матрицей
[pic]
Совокупность проведенных вычислений называется прямым ходом метода
Гаусса.
Из [pic]-го уравнения системы (2) определяем [pic], из ([pic])-го
уравнения определяем [pic] и т.д. до [pic]. Совокупность таких вычислений
называют обратным ходом метода Гаусса.
Реализация прямого метода Гаусса требует [pic] арифметических операций,
а обратного - [pic] арифметических операций.
1.2 Итерационные методы решения СЛАУ
Метод итераций (метод последовательных приближений).
Приближенные методы решения систем линейных уравнений позволяют
получать значения корней системы с заданной точностью в виде предела
последовательности некоторых векторов. Процесс построения такой
последовательности называется итерационным (повторяющимся).
Эффективность применения приближенных методов зависят от выбора
начального вектора и быстроты сходимости процесса.
Рассмотрим метод итераций (метод последовательных приближений). Пусть
дана система n линейных уравнений с n неизвестными:
Ах=b, (14)
Предполагая, что диагональные элементы aii [pic] 0 (i = 2, ..., n),
выразим xi через первое уравнение систем x2 - через второе уравнение и т.
д. В результате получим систему, эквивалентную системе (14):
[pic]
Обозначим [pic]; [pic], где i == 1, 2, ...,n; j == 1,2,..., n. Тогда
система (15) запишется таким образом в матричной форме
[pic]
Решим систему (16) методом последовательных приближений. За нулевое
приближение примем столбец свободных членов. Любое (k+1)-е приближение
вычисляют по формуле
[pic]
Если последовательность приближений x(0),...,x(k) имеет предел [pic],
то этот предел является решением системы (15), поскольку в силу свойства
предела [pic], т.е. [pic] [4,6].
Метод Зейделя.
Метод Зейделя представляет собой модификацию метода последовательных
приближений. В методе Зейделя при вычислении (k+1)-го приближения
неизвестного xi (i>1) учитываются уже найденные ранее (k+1)-е приближения
неизвестных xi-1.
Пусть дана линейная система, приведенная к нормальному виду:
[pic] (17)
Выбираем произвольно начальные приближения неизвестных и подставляем в
первое уравнение системы (17). Полученное первое приближение подставляем во
второе уравнение системы и так далее до последнего уравнения. Аналогично
строим вторые, третьи и т.д. итерации.
Таким образом, предполагая, что k-е приближения [pic]известны, методом
Зейделя строим (k+1)-е приближение по следующим формулам:
[pic]
[pic]
где k=0,1,...,n
[pic]
Метод Ланцоша.
Для решения СЛАУ высокого порядка (1), матрица, коэффициентов которой
хранится в компактном нижеописанном виде, наиболее удобным итерационным
методом является метод Ланцоша [4], схема которого имеет вид:
[pic] (18)
[pic]
где
[pic]
Преимуществом данного метода является его высокая скорость сходимости к
точному решению. Кроме того, доказано, что он обладает свойством
«квадратичного окончания», т.е. для положительно определенной матрицы можно
гарантировано получить точное решение при количестве итераций [pic]. Размер
требуемой памяти на каждой итерации не изменяется, т.к. не требует
преобразование матрицы [pic]. В качестве критерия остановки данного
итерационного процесса обычно используют соотношение
[pic], (19)
где [pic]- заданная точность. В качестве другого критерия сходимости
иногда удобнее использовать среднеквадратичную разность между решениями,
полученными на соседних итерациях:
[pic] (20)
Среднеквадратичную разность необходимо контролировать при выполнении
каждых k наперед заданных итераций.
Отдельно следует рассмотреть проблему выбора начального приближения
[pic]. Доказывается, что при положительно определенной матрице [pic],
итерационный процесс (18) всегда сходится при любом выборе начального
приближения. При решении контактных задач, когда для уточнения граничных
условий в зоне предполагаемого контакта требуется большое количество
решений СЛАУ вида (1), в качестве начального приближения для первого
расчета используется правая часть системы (1), а для каждого последующего
пересчета - решение, полученное на предыдущем. Такая схема позволяет
значительно сократить количество итераций, необходимых для достижения
заданной точности (19) или (20) [10,11].
2 МЕТОДЫ КОМПАКТНОГО ХРАНЕНИЯ МАТРИЦЫ ЖЕСТКОСТИ
Матрица жесткости, получающаяся при применении МКЭ, обладает
симметричной структурой, что позволяет в общем случае хранить только
верхнюю треугольную часть матрицы. Однако для задач с большим количеством
неизвестных это так же приводит к проблеме нехватки памяти. Предлагаемый в
данной работе метод, позволяет хранить только ненулевые члены матрицы
жесткости. Суть его заключается в следующем.
Первоначально, с целью выявления связей каждого узла с другими,
производится анализ структуры дискретизации области на КЭ. Например, для КЭ
- сетки, изображенной на рис. 1, соответствующая структура связей будет
иметь вид:
|№ узла |1 |2 |3 |4 |5 |6 |7 |
|Связи |1, 2, |1, 2, |2, 3, |3, 4, |1, 4, |1, 2, |1, 4, |
| |5, 6, 7|3, 6 |4, 6 |5, 6, 7|5, 7 |3, 4, |5, 6, 7|
| | | | | | |6, 7 | |
Тогда, для хранения матрицы жесткости необходимо построчно запоминать
информацию о коэффициентах, соответствующих узлам, с которыми связан
данный узел. На рис. 2 приведены матрица жесткости и ее компактное
представление для сетки изображенной на рис 1 [9].
Текст подпрограммы, реализующий предложенный алгоритм анализа структуры
КЭ-разбиения тела, приведен в Приложении 1.
Данный способ компактного хранения матрицы жесткости позволяет легко
его использовать совместно с каким-нибудь численным методом. Наиболее
удобным для этой цели представляется использование вышеизложенного
итерационного метода Ланцоша, так как на каждой итерации требуется только
перемножать матрицу коэффициентов СЛАУ и заданный вектор. Следовательно,
для использования предложенного метода компактного хранения СЛАУ необходимо
построить прямое и обратное преобразование в первоначальную квадратную
матрицу.
Пусть [pic]– элемент первоначальной квадратной матрицы размерностью
[pic], а [pic] - ее компактное представление. Тогда для обратного
преобразования будут справедливы следующие соотношения:
[pic], (*)
где m – количество степеней свободы (m=1,2,3).
Для прямого преобразования будут справедливы соотношения, обратные к
соотношениям (*).
3 ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ
Для проверки предлагаемого метода компактного хранения матрицы
жесткости была решена задача о контактном взаимодействии оболочечной
конструкции и ложемента [12] (рис. 4).
| |  скачать работу |
Алгоритм компактного хранения и решения СЛАУ высокого порядка |
