Вспомним метод решения СЛАУ , основанный на LU-разложении матрицы системы, подробно рассмотренный в лекции 7. Исходная система представляется в эквивалентном виде: . После обозначения произведения матрицы на вектор неизвестных через вектор новых неизвестных (), решение исходной системы сводится к последовательному решению двух треугольных систем:
1. ; решением этой СЛАУ, матрица которой является нижней треугольной с единицами на главной диагонали, является вектор ;
2. . С учетом полученного на предыдущем шаге , рассматриваемая система в матричном виде представляется следующим образом: . Полученная СЛАУ – это система с верхней треугольной матрицей . Ее решение в матричном виде: .
Таким образом, при решении СЛАУ LU-методом сначала происходит преобразование матрицы СЛАУ (т.е. ее треугольное разложение ), и лишь затем происходит преобразование вектора правой части (при решении первой треугольной системы получаем новый вектор правой части для СЛАУ , решение которой является искомый вектор ).
|
|
Вспомним теперь матричное представление метода Гаусса без перестановок, полученное в лекции 8. Исходная СЛАУ постепенно преобразуется к верхнему треугольному виду путем умножения на соответствующие матрицы исключения (см.лекц.8) на каждом шаге метода Гаусса:
1 шаг метода Гаусса (исключения в первом столбце матрицы СЛАУ): ;
2 шаг (исключения во втором столбце матрицы СЛАУ): ;
И т.д.
Последний -ый шаг: .
Таким образом, в методе Гаусса преобразование матрицы СЛАУ и вектора правой части происходит одновременно. Получаемая в итоге матрица СЛАУ – это верхняя треуольная матрица . Обозначим ее . Обозначим через произведение нижних треугольных с единицами на главной диагонали матриц исключения: . Эта матрица невырожденная, а потому из равенства следует, что , причем - нижняя треугольная матрица с единицами на главной диагонали. Если теперь обозначить эту матрицу через , то получим известное нам треугольное разложение матрицы: , где - нижняя треугольная с единицами на главной диагонали, а - верхняя треугольная матрица, которое в соответствии с теоремой об LU-разложении определяется однозначно. СЛАУ, получаемая на последнем шаге метода Гаусса запишется в виде:
т.е. ,
а ,
что полностью отвечает матричному виду решения СЛАУ, полученному методом, основанном на LU-разложении матрицы СЛАУ.
Таким образом, метод Гаусса без выбора главного элемента и метод решения СЛАУ, основанный на LU-разложении матрицы системы отличаются друг от друга только порядком проведения одних и тех же операций: в методе Гаусса преобразование матрицы и вектора правой части СЛАУ осуществляется параллельно (одновременно), а в методе, основанном на LU-разложении сначала преобразовывается матрица, а затем вектор правой части (последовательные преобразования), хотя сами преобразования матрицы и вктора правой части носят одинаковый характер в обоих методах. Таким образом, количество операций, необходимых для решения СЛАУ LU-методом, такое же, как и количество операций в методе Гаусса без выбора главного элемента - . При этом само треугольное разложение матрицы СЛАУ требует операций и является наиболее трудоемким в ходе решения СЛАУ, а решение двух треугольных систем требует, как уже было показано выше, потребует операций.
|
|
Необходимо заметить, что большинство распространенных точных методов решения СЛАУ можно рассматривать как варианты метода Гаусса, вычислительная сложность которых определяется как , отличающиеся между собой лишь некоторыми деталями.
Как правило, метод LU-разложения используется тогда, когда нужно решить несколько систем с одной и той же матрицей. В этом случае наиболее трудоемкий в вычислительном смысле процесс LU-разложения матрицы проводится 1 раз (это операций). А решение двух треугольных систем многократно (это операций).