Реферат: Алгоритм компактного хранения и решения СЛАУ высокого порядка

Тогда уравнение (9) перепишем  в виде:

Cy=b.     (11)

Здесь элементы сij известны, так как матрица А системы (7) считается уже разложенной на произведение двух треугольных матриц С и В.

Перемножив матрицы в левой части равенства (11), получаем систему уравнений из которой получаем следующие формулы для определения неизвестных:

неизвестные yi удобно вычислять вместе с элементами bij.

После того как все yi определены по формулам (12), подставляем их в уравнение(10).

Так как коэффициенты bij определены (8), то значения неизвестных, начиная с последнего, вычисляем по следующим формулам:

К прямым методам, использующим свойство разреженности А, можно отнести: алгоритм минимальной степени, алгоритм минимального дефицита, древовидное блочное разбиение для асимметричного разложения, методы вложенных или параллельных сечений и др.

Метод Гаусса.

Пусть дана система

Ax = b

где А – матрица размерности m x m.

В предположении, что , первое уравнение системы

,

делим на коэффициент , в результате получаем уравнение

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

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

Совокупность проведенных вычислений называется прямым ходом метода Гаусса.

Из -го уравнения системы (2)  определяем , из ()-го уравнения определяем  и т.д. до . Совокупность таких вычислений называют обратным ходом метода Гаусса.

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

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

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

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

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