Вычислительные методы алгебры и оценивания. Семушин И.В. - 53 стр.

UptoLike

Составители:

Рубрика:

Векторно-ориентированные

алгоритмы LU-разложения

3.1 Гауссово исключение и ijk-алгоритмы

Рассмотрим систему линейных уравнений

Ax = b (3.1)

с невырожденной матрицей A размера (n × n). Мы считаем A заполненной

матрицей. Раз реженные матрицы расматриваются в разд. 5.

Как изложено в подразд. 2.1, наиболее известной формой гауссова исклю-

чения является та, в которой система (3.1) приводится к верхнетреугольному

виду путем вычитания одних уравнений, ум ноженных на подходящие числа,

из других уравнений; полученная треугольная систем а решается с помощью

обратной подстановки. Мате м а т ически все это э квивалентно тому, что вна-

чале строится разложение матрицы A, например вида A =

LU, где

L явля-

ется нижнетреугольной матрицей с единицами на главной диагонали, а U —

верхнетреугольная матрица с ненулевыми элементами на диагонали. Затем

решаются треугольные системы

Ly = b, Ux = y. (3.2)

Процесс их решения называется, соответств енно, прямой и обратной под-

становками.

Мы сосредоточимся вначале на

LU-разложении, поглощающем большую

часть времени вс его процесса, а затем вернемся к решению треугольных

систем. Псевдокод разложения приведен на рис. 3.1.

В цикле j на рис. 3.1 кратные k-й строки текущей матрицы A вычитаются

из расположенных ниже строк. Эти операции представляют собой триады,

в которых векторами я в ля ются строки м а трицы A [8].