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

Лекция 2. Системы линейных алгебраических уравнений

2.1 Решение систем линейных алгебраических уравнений

2.1.1 Определения и основные свойства матриц

Для начала напомним некоторые сведения из линейной алгебры. Рассмотрим систему из n линейных алгебраических уравнений (СЛАУ) с

n неизвестными x1, ,xn :

Определение: А — невырожденная, если для А существует A 1. Теорема: следующие утверждения эквивалентны:

1.А — невырождена;

2.det A 0;

3.линейная однородная система Ax 0 имеет единственное решение

x0;

4.для любого b система Ax b имеет единственное решение;

5.столбцы (строки) матрицы А линейно независимы, то есть для любой

комбинации чисел 1, 2, n , не все из которых равны нулю, линейная комбинация

матрицы А, если они удовлетворяют алгебраическому уравнению

Ax x

Собственный вектор — это такой вектор, который, будучи умножен на матрицу А, изменяет лишь свою длину.

Из определения собственного значения следует:

Ax x 0 A I x 0.

Так как x — собственный вектор и по определению x 0, то в соответствии с теоремой A I — вырожденная матрица, а det A I 0.

Левая часть последнего выражения — полином степени n относительно комплексной переменной , называемый характеристическим полиномом матрицы, следовательно собственные значения матрицы есть корни характеристического полинома матрицы A, их ровно n с учетом кратности.

Определение: совокупность всех собственных значений i in 1 матрицы

А называется спектром матрицы А, а величина

A max i

1 i n

называется спектральным радиусом. Определение: нормой матрицы А называется

Решение СЛАУ методом исключения

Одной из наиболее распространенных задач является задача решения СЛАУ

Ax b,

для заданных квадратной матрицы А и вектора b.

Если А — невырожденная матрица, то для нее существует обратная A 1.

Умножая СЛАУ на A 1 слева, получим решение: x A 1b.

Полученный метод решения СЛАУ неэффективен в силу большого времени вычислений.

Рассмотрим более эффективный алгоритм решения СЛАУ – метод исключения Гаусса. Этот алгоритм с некоторыми модификациями используют для решения СЛАУ до двухсотого порядка.

Вначале продемонстрируем работу алгоритма на примере следующей СЛАУ:

уравнения вычтем первое, умноженное на l21 24. Для исключения x1 в

третьем уравнения из него вычтем первое, умноженное на l31 14. В результате после первого шага исключения получим

На втором шаге алгоритма исключим x2 в третьем уравнении, для чего из третьего уравнения вычтем первое, умноженное на l32 12. После второго шага исключения получим

За два шага закончилась первая часть алгоритма — приведение системы к треугольной форме. Решение полученной треугольной системы осуществляется снизу вверх

x3 44 1;

x2 2 3 3x3 0;

x1 14 6 2x3 9x2 1.

Перейдем к построению алгоритма исключения для СЛАУ общего вида

Шаг 1: исключим x1 из уравнений с номерами 2,…, n путем вычитания:

из второго уравнения первого, умноженного на l21 a21a11 ;