Материал: лекция 2 ММОСУ

Решение треугольной системы осуществляется путем обратной подстановки k=n, n-1, …, 1.

обычно хранят на месте исходных элементов aij , bi , поэтому их прежние значения будут изменены. Приведем программу, реализующую алгоритм решения СЛАУ методом исключения.

LU-факторизация матриц

Впроцессе исключения по Гауссу исходная матрица СЛАУ А приведена

кверхней треугольной матрице

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

Можно показать, что

A LU ,

путем обратной подстановки

xn u1nn yn ,

или, в общем виде:

xk u1kk yk j nk u1kjxj , k n,n 1, ,1.

Таким образом, применение LU-факторизации сводит решение исходной СЛАУ к последовательному решению двух СЛАУ c треугольными матрицами. Если требуется решить несколько СЛАУ о одной и той же матрицей А и различными правыми частями

то предварительная LU-факторизация матрицы системы А позволяет существенно сократить трудоемкость решения n систем, сводя задачу к решению 2n СЛАУ с треугольными матрицами

Lyi bi ,

Uxi yi .

Вычисление определителя и обратной матрицы

Определитель матрицы А является побочным продуктом LU-факторизации матрицы А, действительно:

det A det LU det L det U .

Второе равенство получено на основании того, что определитель произведения матриц равен произведению определителей сомножителей.

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

следовательно

det A in 1uii .

В MATLAB реализована функция вычисления определителя матрицы

D = det(A).

Перейдем к рассмотрению вопроса о вычислений обратной матрицы. По определению обратная матрица X удовлетворяет матричному алгебраическому уравнению

AX I

Представим матрицы X и I в виде наборов их столбцов

где ei – вектор, который имеет все нулевые элементы за исключением i-ого, равного 1. Тогда матричное уравнение для обратной матрицы можно переписать в виде

A x1 | x2 | | xn e1 |e2 | |en ,

то есть представляет собой n СЛАУ вида

Axi ei, i 1, ,n.

Таким образом, для вычисления обратной матрицы необходимо решить n СЛАУ и составить из полученных решений матрицу. Учитывая, что все n СЛАУ имеют одинаковую матрицу А, целесообразно произвести ее LUфакторизацию и свести задачу вычисления обратной матрицы к решению 2n СЛАУ с треугольными матрицами

Обусловленность СЛАУ. Анализ ошибок решения СЛАУ

Определение: СЛАУ плохо обусловлена, если малые изменения элементов матрицы А или вектора b приводят к большим изменениям в решении.

Рассмотрим пример плохо обусловленной СЛАУ:

0,8x1 0,4x2 1, 0,79x1 0,41x2 .

Решения этой системы x0 для 0 и x для малого значения будут сильно отличаться. Это связано с тем, что на плоскости x1x2 уравнения системы задают “почти” параллельные прямые 1 и 2 (рис. 2.1). Следовательно, уравнения являются “почти” линейнозависимыми, и при их малом изменении относительно друг друга точка пересечения прямых будет значительно меняться.