Основы программирования



              

Пример: приведение матрицы к ступенчатому виду методом Гаусса


В качестве примера работы с матрицами рассмотрим алгоритм Гаусса приведения матрицы к ступенчатому виду. Метод Гаусса - один из основных результатов линейной алгебры и аналитической геометрии, к нему сводятся множество других теорем и методов линейной алгебры (теория и вычисление определителей, решение систем линейных уравнений, вычисление ранга матрицы и обратной матрицы, теория базисов конечномерных векторных пространств и т.д.).

Напомним, что матрица A с элементами aij

называется ступенчатой, если она обладает следующими двумя свойствами:

  1. если в матрице есть нулевая строка, то все строки ниже нее также нулевые;
  2. пусть aij

    не равное 0 -- первый ненулевой элемент в строке с индексом i, т.е. элементы ail = 0 при l < j. Тогда все элементы в j-м столбце ниже элемента aij

    равны нулю, и все элементы левее и ниже aij

    также равны нулю: akl = 0 при k > i и l =< j.

Ступенчатая матрица выглядит примерно так:


здесь тёмными квадратиками отмечены первые ненулевые элементы строк матрицы. Белым цветом изображаются нулевые элементы, серым цветом - произвольные элементы.

Алгоритм Гаусса использует элементарные преобразования матрицы двух типов.

  • Преобразование первого рода: две строки матрицы меняются местами, и при этом знаки всех элементов одной из строк изменяются на противоположные.

  • Преобразование второго рода: к одной строке матрицы прибавляется другая строка, умноженная на произвольное число.

Элементарные преобразования сохраняют определитель и ранг матрицы, а также множество решений линейной системы. Алгоритм Гаусса приводит произвольную матрицу элементарными преобразованиями к ступенчатому виду. Для ступенчатой квадратной матрицы определитель равен произведению диагональных элементов, а ранг - числу ненулевых строк (рангом по определению называется размерность линейной оболочки строк матрицы).

Метод Гаусса в математическом варианте состоит в следующем:

  1. ищем сначала ненулевой элемент в первом столбце. Если все элементы первого столбца нулевые, то переходим ко второму столбцу, и так далее.


    Содержание  Назад  Вперед