Приведение системы линейных уравнений к треугольному виду

Приведение матрицы к треугольному виду

Приведение матрицы к треугольному виду методом Гаусса и методом Барейса.

Ниже два калькулятора для приведения матриц к треугольному, или ступенчатому, виду. Первый использует для этого метод Гаусса, второй — метод Барейса. Описание методов и немного теории — под калькуляторами.

Приведение матрицы к треугольному виду (метод Гаусса)

Приведение матрицы к треугольному виду (метод Барейса)

Итак, для начала определимся с понятием треугольной, или ступенчатой матрицы:
Матрица имеет ступенчатый вид, если:

1. Все нулевые строки матрицы стоят последними
2. Первый ненулевой элемент строки всегда находится строго правее первого ненулевого элемента предыдущей строки
3. Все элементы столбца под первым ненулевым элементом строки равны нулю (это впрочем следует из первых двух пунктов)

Пример ступенчатой матрицы:
1 0 2 5
0 3 0 0
0 0 0 4

Понятие треугольной матрицы более узкое, оно используется только для квадратных матриц (хотя я думаю, что это не строго), и формулируется проще: треугольная матрица — квадратная матрица, в которой все элементы ниже главной диагонали равны нулю. Строго говоря, это даже определение верхнетреугольной матрицы, но мы будем использовать его. Понятно, что такая верхнетреугольная матрица является также и ступенчатой.

Пример треугольной (верхнетреугольной) матрицы:
1 0 2 5
0 3 1 3
0 0 4 2
0 0 0 3
Кстати, определитель треугольной матрицы вычисляется простым перемножением ее диагональных элементов.

Чем же так интересны ступенчатые (и треугольные) матрицы, что к ним надо приводить все остальные? — спросите вы.
У них есть замечательной свойство, а именно, любую прямоугольную матрицу можно с помощью элементарных преобразований привести к ступенчатой форме.

Что же такое элементарные преобразования? — спросите вы.
Элементарными преобразованиями матрицы называют следующие операции:

1. перестановка любых двух строк (столбцов) матрицы
2. умножение любой строки (столбца) на призвольное, отличное от нуля, число
3. сложение любой строки (столбца) с другой строкой (столбцом), умноженной (умноженным) на произвольное, отличное от нуля, число.

И что? — спросите вы.
А то, что элементарные преобразования матрицы сохраняют эквивалентность матриц. А если вспомнить, что системы линейных алгебраический уравнений (СЛАУ) записывают как раз в матричной форме, то это означает, что элементарные преобразования матрицы не изменяют множество решений системы линейных алгебраических уравнений, которую представляет эта матрица.

Приведя матрицу системы линейных уравнений AX=B к треугольной форме A’X = B’, то есть, с соответствующими преобразованиями столбца B, можно найти решение этой системы так называемым «обратным ходом».

Чтобы было понятно, используем треугольную матрицу выше и перепишем систему уравнений в более привычной форме (столбец B я придумал сам):

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

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

Теперь про сам метод.
Собственно, как можно занулить переменную во втором уравнении? Вычтя из него первое, домноженное на коэффициент
Поясним на примере:

Зануляем во втором уравнении:

Во втором уравнении больше не содержится

Обобщенно алгоритм метода Гаусса можно представить следующим образом:

где N — число строк,
— i-тая строка,
— элемент, находящийся в i-той строке, j-том столбце

И все бы ничего, да и метод отличный, но. Дело все в делении на , присутствующем в формуле. Во-первых, если диагональный элемент будет равен нулю, то метод работать не будет. Во-вторых, в процессе вычисления будет накапливаться погрешность, и чем дальше, тем больше. Результат будет отличаться от точного.

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

Но есть еще более радикальная модификация метода Гаусса, которая называется методом Барейса (Bareiss).
Как можно избавиться от деления? Например, умножив перед вычитанием строку на . Тогда вычитать надо будет строку , домноженную только на , без всякого деления.
.
Уже хорошо, но возникает проблема с ростом значений элементов матрицы в ходе вычисления.

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

Кстати, то, что в случае целочисленных элементов исходной матрицы алгоритм Барейса приводит к треугольной матрице с целочисленными элементами, то есть без накопления погрешности вычислений — довольно важное свойство с точки зрения машинной арифметики.

Алгоритм Барейса можно представить следующим образом:

Алгоритм, аналогично методу Гаусса, также можно улучшить поиском максимума по столбцу(всей матрице) и перестановкой соответствующих строк (строк и столбцов).

Линейные уравнения. Решение систем линейных уравнений. Метод вращения.

Метод вращений. Как и в методе Гаусса, целью прямого хода преобразований в методе вращений является приведение системы линейных уравнений к треугольному виду методичным обнулением поддиагональных элементов сначала 1-го столбца, далее 2-го и так далее.

Допустим с₁ и s₁ – ненулевые числа. Умножаем 1-е уравнение системы на с₁, 2-е на s₁ и складываем их; уравнением, которое мы получили, заменяем 1-е уравнение системы. Далее 1-е уравнение начальной системы нужно умножить на – s₁, 2-е – на c₁ и итогом этого заменяем 2-е уравнение. Т.о., первые 2 уравнения заменяем уравнениями:

— условие исключения х₁ из второго уравнения и

Эти числа можно истолковать как cos и sin некоторого угла α₁ (поэтому метод так и называется — все шаги этого преобразования рассматриваются как вращение расширенной матрицы системы в плоскости индекса, который обнуляется).

После преобразований получаем систему:

Теперь 1-е уравнение системы заменяем полученным, результатом сложения итогов умножения 1-го и 3-го уравнений соответственно на:

а 3-е – уравнением, которое получим после сложения результатов умножения уравнений соответственно на – s₂ и с₂. Получаем систему:

Выполняя преобразование m-1 раз, приходим к системе:

Вид системы, которую мы получили, такой же, как и после 1-го этапа преобразований методом Гаусса. У этой системы следующие свойства: длина всех векторов-столбцов расширенной матрицы остается такая же, как у исходной матрицы. То есть, при выполнении преобразований не роста элементов нет.

Далее, по этому же алгоритму преобразуем матрицу:

В итоге m-1 этапов прямого хода система приведется к треугольному виду:

Определение неизвестных такое же как и в обратном ходе метода Гаусса.

Треугольная, или, трапециевидная структура последней системы дает нам поочередно 1 за другим вычислить значения неизвестных, начиная с последнего:

Метод Гаусса решения систем линейных уравнений путем приведения их к треугольному виду.

Метод Гаусса — точный метод решения систем линейных алгебраических уравнений.

Метод Гаусса (его еще называют методом гауссовых исключений) состоит в том, что совместную систему n линейных алгебраических уравнений относительно n неизвестных (определитель матрицы системы отличен от нуля)

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

решение которой находят по рекуррентным формулам

В матричной записи это означает, что сначала (прямой ход метода Гаусса) элементарными преобразованиями над строками приводят расширенную матрицу системы к ступенчатому виду:

а затем (обратный ход метода Гаусса) эту ступенчатую матрицу преобразуют так, чтобы в первых n столбцах получилась диагональная матрица

В результате получаем решение системы:

Опишем метод Гаусса последовательно.

Рассмотрим расширенную матрицу системы

Если это не так, и a₁₁ = 0, переставим строки матрицы так, чтобы a₁₁ ≠ 0. Это всегда возможно, т.к. в противном случае матрица содержит нулевой столбец, ее определитель равен нулю и система несовместна.

Элемент a₁₁ ≠ 0 называется ведущим элементом.

Умножим первую строку на число и прибавим ко второй строке,

затем умножим первую строку на число и прибавим к третьей строке, и т.д.,

т.е. последовательно умножаем первую строку на число и прибавляем к i-й строке, для i=2, 3, …, n.

Получим на первом шаге:

.

Предположим, что a (1) ₂₂ ≠ 0.

Если это не так, и a (1) ₂₂ = 0, переставим строки матрицы так, чтобы a (1) ₂₂ ≠ 0.

Здесь ведущий элемент a₂₂ ≠ 0.

Умножим вторую строку на число и прибавим к третьей строке,

затем умножим вторую строку на число и прибавим к четвертой строке, и т.д.,

т.е. последовательно умножаем вторую строку на число и прибавляем к i-й строке, для i=3, 4, …, n.

Получим на втором шаге:

Если это не так, и a ( k — 1) _kk = 0, переставим строки матрицы так, чтобы a ( k — 1) _kk ≠ 0.

Умножим k-ю строку на число и прибавим к i-й строке, для i=k+1, k+2, …, n.

Выполнив n-1 шаг получим:

.

Прямой ход закончен. Заметим, что все элементы на главной диагонали отличны от нуля.

Умножим последнюю строку на число и прибавим к предпоследней строке, затем умножим последнюю строку на число и прибавим к (n-2)-й строке, и т.д., т.е. последовательно умножаем последнюю строку на число и прибавляем к (n-i)-й строке, для i=1, 3, …, n-1.

Получим на первом шаге:

.

Умножим k-ю строку на число и прибавим к i-й строке, для i=k-1, k-2, …, n­-1.

Выполнив n-1 шаг получим:

Обратный ход закончен. Решение вычисляем по формулам:

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

Дата добавления: 2016-07-18 ; просмотров: 2398 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ