Связь метода Гаусса с lu-факторизацией

Прямой ход метода Гаусса заключается в переходе к системе уравнений

,

где матрица U- верхняя правая треугольная матрица

.

Легко можно убедиться , что вектора f иyсвязаны отношением

,

где L- нижняя левая треугольная матрица

.

Просто подставляем ,и т.д. Таким образом, имеем

, ,

, .

Следовательно,

.

Метод Гаусса дает алгоритм приведения матрицы системы к виду A=LU. Прямой ход заключается в поиске матрицLиU, а обратный ход в решенииLy=f,Ux=y.

Теоретическое обоснование метода Гаусса заключено в следующей теореме.

Теорема. Любую квадратную матрицус отличными от нуля главными минорами можно представить в виде произведенияA=BC, гдеB- левая нижняя треугольная матрица, аC- верхняя правая треугольная матрица. Причем это разложение единственно с точностью до фиксации диагональных элементов одной из матриц.

Следствие. ПустьA- квадратная матрица с отличными от нуля главными минорами, тогда существуют единственные левая нижняя треугольная матрицаLи верхняя правая треугольная матрицаU, такие, чтоA=LU.

LU-факторизация - представление матрицы в виде произведения матрицыLиU.

Вычисление определителя

Решив систему уравнений методом Гаусса, можно одновременно вычислить определитель матрицы A.

Ax=f, A=LU,

где LиU- треугольные матрицы.

Определитель произведения матриц равен произведению определителей матриц. Определитель треугольной матрицы равен произведению ее диагональных элементов. Из этих двух свойств определителей следует (на главной диагонали матрицы Lстоят единицы):

.

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

Поэтому в общем случае, формула для вычисления определителя при LU-факторизации принимает вид:

,

где k- число перестановок строк или столбцов.

Примечание. При решении системы линейных алгебраических уравнений методом Гаусса нельзя заранее узнать, равен ли , или, другими словами, существует ли решение системы или нет.

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

Если в программе реализован метод с выбором главного элемента, то данная проверка осуществляется проще. Необходимо проверять на равенство нулю все найденные главные элементы перед проведением очередного шага исключения. Учитывая, что вещественное число на компьютере нулю точно никогда не равняется (например, число 0.00000000000000001), то необходимо проверку производить следующим образом -

If Abs(Гл.Элемент)< 0.00001 then ...

Обращение матрицы

Нахождение матрицы, обратной матрице A, эквивалентно решению матричного уравнения, гдеE- единичная матрица,X- искомая квадратная матрица.

Для дальнейшего важно заметить, что матричная система распадается на nнезависимых систем уравнений с одной и той же матрицейA,но с разными правыми частями. Эти системы имеют вид:

, .

где и.

Для решения подобной задачи можно использовать различные численные методы, но наиболее эффективным методом будет метод Гаусса с LU-факторизацией. Достаточно выполнить один раз прямой ходA=LUи потом просто решать треугольные системы уравненийLy=f и Ux=y.

Схема Халецкого

Схема Халецкого представляет собой вариант метода Гаусса с LU-факторизацией. Для системы уравненийAx=fиспользуют заменуA=BC, гдеB- левая нижняя треугольная матрица,C- правая верхняя треугольная матрица с 1 по главной диагонали. Далее решают две системы уравнений с треугольными матрицами.

Элементы матриц BиCопределяют по формулам:

(3.7)

и

. (3.8)

Далее искомый вектор xможет быть вычислен из цепи уравнений:

By=fиCx=y.

Решение yиxданных систем может быть получено по формулам:

(3.9)

и

. (3.10)

Числа можно вычислять вместе с коэффициентами.

Если матрица Aсимметрическая, т.е., то для определения коэффициентовиспользуется более простая формула

.

Для хранения матриц BиCможно использовать два массива, но, принимая во внимание вид матрицыC, возможно и сократить количество массивов до 1. При этом необходимо будет специально учитывать, что.