Алгоритм компактного хранения и решения СЛАУ высокого порядка (стр. 2 из 5)
А=СВ,
Где
, 
Причем элементы сij и bij определяются по формулам:
, 
Уравнение (7) можно записать в следующем виде:
CBx=b. (9)
Произведение Bx матрицы B на вектор-столбец x является вектором-столбцом, который обозначим через y:
Bx=y.(10)
Тогда уравнение (9) перепишем в виде:
Cy=b. (11)
Здесь элементы сij известны, так как матрица А системы (7) считается уже разложенной на произведение двух треугольных матриц С и В.
Перемножив матрицы в левой части равенства (11), получаем систему уравнений из которой получаем следующие формулы для определения неизвестных:
неизвестные yi удобно вычислять вместе с элементами bij.
После того как все 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].