Алгоритм компактного хранения и решения СЛАУ высокого порядка
Страница 2
Далее к каждой неглавной i-й строке прибавим главную строку, умноженную на соответствующий множитель mi; для этой строки.
В результате получим новую матрицу, все элементы q-го столбца которой, кроме apq, состоят из нулей.
Отбросив этот столбец и главную p-ю получим новую матрицу, число строк и столбцов которой на единицу меньше. Повторяем те же операции с получившейся матрицей, после чего получаем новую матрицу и т.д.
Таким образом, построим последовательность матриц, последняя из которых является двучленной матрицей-строкой (главной строкой). Для определения неизвестных xi объединяем в систему все главные строки, начиная с последней.
Изложенный метод решения системы линейных уравнений с n неизвестными называется методом главных элементов. Необходимое условие его применения состоит том, что определитель матрицы не равен нулю [6,7].
Схема Халецкого.
Пусть система линейных уравнений дана в матричном виде.
Ax=b (7)
Где А - квадратная матрица порядка n, а x,b - векторы столбцы.
Представим матрицу А в виде произведения нижней треугольной матрицы С и верхней треугольной матрицы В с единичной диагональю, т.е.
А=СВ,
Где
, 
Причем элементы с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], схема которого имеет вид: