В математике метод исключения Гаусса , также известный как сокращение строки , представляет собой алгоритм решения систем линейных уравнений . Он состоит из последовательности операций, выполняемых над соответствующей матрицей коэффициентов. Этот метод также может быть использован для вычисления ранга матрицы, то определителя в виде квадратной матрицы , а обратный к обратимой матрице . Метод назван в честь Карла Фридриха Гаусса (1777–1855), хотя некоторые частные случаи этого метода, хотя и представленные без доказательства, были известны китайским математикам еще примерно в 179 году нашей эры.
Чтобы выполнить сокращение строки в матрице, используется последовательность элементарных операций со строкой для изменения матрицы до тех пор, пока нижний левый угол матрицы не будет заполнен нулями, насколько это возможно. Есть три типа операций с элементарными строками:
Используя эти операции, матрица всегда может быть преобразована в верхнюю треугольную матрицу , фактически имеющую форму эшелона строк . Когда все ведущие коэффициенты (крайний левый ненулевой элемент в каждой строке) равны 1, а каждый столбец, содержащий ведущий коэффициент, имеет нули в другом месте, матрица называется сокращенной эшелонированной строкой . Эта окончательная форма уникальна; другими словами, он не зависит от последовательности используемых операций со строками. Например, в следующей последовательности операций со строками (где две элементарные операции с разными строками выполняются на первом и третьем шагах) третья и четвертая матрицы - это матрицы в форме эшелона строк, а конечная матрица - это уникальная сокращенная строка эшелонированная форма.
Использование строковых операций для преобразования матрицы в сокращенную форму эшелона строк иногда называют исключением Гаусса – Жордана . В этом случае термин « исключение по Гауссу» относится к процессу до тех пор, пока он не достигнет своей верхней треугольной формы или (нередуцированной) формы эшелона строк. По вычислительным причинам при решении систем линейных уравнений иногда предпочтительнее остановить операции со строками до того, как матрица будет полностью сокращена.
Процесс сокращения строк использует элементарные операции со строками и может быть разделен на две части. Первая часть (иногда называемая прямым исключением) приводит данную систему к форме эшелона строк , из которой можно определить, нет ли решений, единственного решения или бесконечного множества решений. Вторая часть (иногда называемая обратной заменой ) продолжает использовать операции со строками до тех пор, пока не будет найдено решение; Другими словами, он преобразует матрицу в сокращенный ряд строк.
Другая точка зрения, которая оказывается очень полезной для анализа алгоритма, заключается в том, что сокращение строк приводит к матричному разложению исходной матрицы. Операции с элементарными строками можно рассматривать как умножение слева от исходной матрицы на элементарные матрицы . В качестве альтернативы последовательность элементарных операций, сокращающих одну строку, может рассматриваться как умножение на матрицу Фробениуса . Затем первая часть алгоритма вычисляет разложение LU , а вторая часть записывает исходную матрицу как произведение однозначно определенной обратимой матрицы и однозначно определенной уменьшенной матрицы эшелона строк.
Есть три типа операций с элементарными строками, которые могут выполняться со строками матрицы:
Если матрица связана с системой линейных уравнений, то эти операции не изменяют множество решений. Следовательно, если целью является решение системы линейных уравнений, то использование этих операций со строками может упростить задачу.
Для каждой строки в матрице, если строка не состоит только из нулей, то крайний левый ненулевой элемент называется ведущим коэффициентом (или опорной точкой ) этой строки. Таким образом, если два ведущих коэффициента находятся в одном столбце, то можно использовать строковую операцию типа 3 , чтобы обнулить один из этих коэффициентов. Затем, используя операцию перестановки строк, всегда можно упорядочить строки так, чтобы для каждой ненулевой строки ведущий коэффициент находился справа от ведущего коэффициента строки выше. Если это так, то говорят, что матрица имеет вид эшелона строк. Таким образом, нижняя левая часть матрицы содержит только нули, а все нулевые строки находятся ниже ненулевых строк. Слово «эшелон» используется здесь, потому что можно примерно представить строки, ранжированные по их размеру, причем самые большие находятся вверху, а самые маленькие - внизу.
Например, следующая матрица представлена в виде эшелона строк, и ее ведущие коэффициенты показаны красным:
Он имеет эшелонированную форму, потому что нулевая строка находится внизу, а ведущий коэффициент второй строки (в третьем столбце) находится справа от ведущего коэффициента первой строки (во втором столбце).
Матрица называется сокращенной эшелонированной строкой, если, кроме того, все ведущие коэффициенты равны 1 (что может быть достигнуто с помощью операции элементарной строки типа 2), и в каждом столбце, содержащем ведущий коэффициент, все другие записи в этом столбце равны нулю (что может быть достигнуто с помощью элементарных операций со строками типа 3).
Предположим, цель состоит в том, чтобы найти и описать множество решений следующей системы линейных уравнений :
В таблице ниже показан процесс сокращения строк, применяемый одновременно к системе уравнений и связанной с ней расширенной матрице . На практике системы обычно не рассматриваются в терминах уравнений, а вместо этого используется расширенная матрица, которая больше подходит для компьютерных манипуляций. Процедуру сокращения строки можно резюмировать следующим образом: исключить x из всех уравнений ниже L 1 , а затем исключить y из всех уравнений ниже L 2 . Это придаст системе треугольную форму . Затем, используя обратную подстановку, можно решить каждую неизвестную.
Система уравнений | Рядовые операции | Расширенная матрица |
---|---|---|
Матрица теперь имеет эшелонированную форму (также называемую треугольной формой). | ||
Второй столбец описывает, какие операции со строками были только что выполнены. Таким образом , для первого шага х исключается из L 2 путем добавления 3 / 2 L 1 до L 2 . Затем x удаляется из L 3 путем добавления L 1 к L 3 . Эти операции со строками помечены в таблице как
Когда y также удаляется из третьей строки, результатом является система линейных уравнений в треугольной форме, и, таким образом, первая часть алгоритма завершена. С вычислительной точки зрения быстрее решать переменные в обратном порядке, этот процесс известен как обратная подстановка. Видно, что решение z = −1 , y = 3 и x = 2 . Итак, есть единственное решение исходной системы уравнений.
Вместо остановки, когда матрица находится в эшелонированной форме, можно продолжить, пока матрица не будет в уменьшенной эшелонированной форме, как это сделано в таблице. Процесс сокращения строк до сокращения матрицы иногда называют исключением Гаусса – Жордана , чтобы отличить его от остановки после достижения эшелонированной формы.
Метод устранения появляется гауссовым - хотя и без доказательства - в китайской математическом тексте восьмой главы: прямоугольные массивы из Математика в девяти книг . Его использование проиллюстрировано в восемнадцати задачах с двумя-пятью уравнениями. Первое упоминание книги под этим названием датируется 179 годом нашей эры, но некоторые ее части были написаны примерно в 150 году до нашей эры. [1] [2] Это прокомментировал Лю Хуэй в III веке.
В Европе этот метод основан на записях Исаака Ньютона . [3] [4] В 1670 году он написал, что во всех известных ему книгах по алгебре не хватало уроков по решению одновременных уравнений, которые затем преподал Ньютон. Кембриджский университет в конце концов опубликовал заметки как Arithmetica Universalis в 1707 году, спустя много времени после того, как Ньютон оставил академическую жизнь. Примечания были широко имитированы, что сделало (то, что сейчас называется) методом исключения Гаусса стандартным уроком в учебниках алгебры к концу 18 века. Карл Фридрих Гаусс в 1810 году изобрел обозначение для симметричного исключения, которое было принято в 19 веке профессиональными ручными компьютерами для решения нормальных уравнений задач наименьших квадратов.[5] Алгоритм, который преподают в средней школе, был назван в честь Гаусса только в 1950-х годах из-за путаницы в истории предмета. [6]
Некоторые авторы используют термин « исключение Гаусса» только для обозначения процедуры до тех пор, пока матрица не перейдет в эшелонированную форму, и используют термин « исключение Гаусса – Жордана» для обозначения процедуры, которая заканчивается в форме сокращенного эшелона. Название используется потому, что это разновидность метода исключения Гаусса, описанного Вильгельмом Джорданом в 1888 году. Однако этот метод также появляется в статье Клазена, опубликованной в том же году. Джордан и Класен, вероятно, независимо открыли метод исключения Гаусса – Джордана. [7]
Исторически первым применением метода сокращения строк является решение систем линейных уравнений . Вот еще несколько важных приложений алгоритма.
Чтобы объяснить, как метод исключения Гаусса позволяет вычислить определитель квадратной матрицы, мы должны вспомнить, как элементарные операции со строками изменяют определитель:
Если метод исключения Гаусса, примененный к квадратной матрице A, дает матрицу B эшелона строк , пусть d будет произведением скаляров, на которые был умножен определитель, используя приведенные выше правила. Тогда определитель A - это частное по d произведения элементов диагонали B :
С вычислительной точки зрения для матрицы размера n × n этот метод требует только O ( n 3 ) арифметических операций, в то время как использование формулы Лейбница для определителей требует O ( n !) Операций (количество слагаемых в формуле), а рекурсивное разложение Лапласа требует O ( 2 n ) операции (количество вычисляемых подопределителей, если ни один из них не вычисляется дважды). Даже на самых быстрых компьютерах эти два метода непрактичны или почти неосуществимы при n выше 20.
Вариант исключения Гаусса, называемый исключением Гаусса – Жордана, может быть использован для нахождения обратной матрицы, если она существует. Если A является квадратной матрицей размера n × n , то можно использовать сокращение строки для вычисления ее обратной матрицы , если она существует. Сначала единичная матрица размера n × n увеличивается справа от A , образуя блочную матрицу n × 2 n [ A | I ] . Теперь, применяя элементарные операции со строками, найдите приведенную эшелонированную форму этой матрицы размера n × 2 n . Матрица A обратима тогда и только тогда, когда левый блок можно свести к единичной матрице I ; в этом случае правый блок финальной матрицы равен A −1 . Если алгоритм не может уменьшить левый блок до I , то A не обратим.
Например, рассмотрим следующую матрицу:
Чтобы найти обратную матрицу, нужно взять следующую матрицу, увеличенную на единицу, и уменьшить ее по строке до матрицы 3 × 6:
Выполняя операции со строками, можно проверить, что приведенная форма эшелона строк этой расширенной матрицы
Каждую строковую операцию можно рассматривать как левое произведение на элементарную матрицу . Обозначив через B произведение этих элементарных матриц, мы показали слева, что BA = I , а значит, B = A −1 . Справа мы сохранили запись BI = B , что, как мы знаем, является обратным желаемому. Эта процедура поиска обратного работает для квадратных матриц любого размера.
Алгоритм исключения Гаусса может быть применен к любой матрице A размера m × n . Таким образом, например, некоторые матрицы 6 × 9 могут быть преобразованы в матрицу, имеющую форму эшелона строк, например
где звездочки - произвольные записи, а a , b , c , d , e - ненулевые записи. В этом эшелоне матрица Т содержит большое количество информации о А : ранг из А 5, так как существует 5 ненулевых строк в Т ; векторное пространство , натянутое на столбцы А имеет базис , состоящий из его колонн 1, 3, 4, 7 и 9 (столбцов с , Ь , гр , д , е в Т), а звездочки показывают, как другие столбцы A могут быть записаны как линейные комбинации базовых столбцов. Это следствие дистрибутивности скалярного произведения в выражении линейной карты в виде матрицы .
Все это относится также к форме сокращенного эшелона строк, которая представляет собой особый формат эшелона строк.
Количество арифметических операций, необходимых для сокращения строк, является одним из способов измерения вычислительной эффективности алгоритма. Например, для решения системы из n уравнений для n неизвестных путем выполнения строковых операций над матрицей до тех пор, пока она не будет в форме эшелона, а затем решения для каждого неизвестного в обратном порядке, требуется n ( n + 1) / 2 деления, (2 n 3 + 3 n 2 - 5 n ) / 6 умножений и (2 n 3 + 3 n 2 - 5 n ) / 6 вычитаний, [8]в общей сложности около 2 л 3 /3 операций. Таким образом, он имеет арифметическую сложность O ( n 3 ) ; см Big O нотации .
Эта арифметическая сложность является хорошей мерой времени, необходимого для всего вычисления, когда время для каждой арифметической операции приблизительно постоянно. Это тот случай, когда коэффициенты представлены числами с плавающей запятой или когда они принадлежат конечному полю . Если коэффициенты являются целыми или точно представленными рациональными числами , промежуточные элементы могут расти экспоненциально, поэтому битовая сложность будет экспоненциальной. [9] Однако существует вариант исключения Гаусса, называемый алгоритмом Барейсса , который позволяет избежать этого экспоненциального роста промежуточных элементов и с той же арифметической сложностью O (n 3 ) , имеет битовую сложность O ( n 5 ) .
Этот алгоритм можно использовать на компьютере для систем с тысячами уравнений и неизвестных. Однако для систем с миллионами уравнений стоимость становится непомерно высокой. Эти большие системы обычно решаются с использованием итерационных методов . Специальные методы существуют для систем, коэффициенты которых следуют регулярному шаблону (см. Систему линейных уравнений ).
Чтобы преобразовать матрицу размера n × n в упрощенную форму с помощью строковых операций, требуется n 3 арифметических операций, что примерно на 50% больше шагов вычислений. [10]
Одна из возможных проблем - числовая нестабильность , вызванная возможностью деления на очень малые числа. Если, например, ведущий коэффициент одной из строк очень близок к нулю, то для уменьшения строки матрицы необходимо разделить на это число. Это означает, что любая ошибка, существующая для числа, близкого к нулю, будет усилена. Метод исключения Гаусса численно устойчив для диагонально доминирующих или положительно определенных матриц. Для общих матриц исключение Гаусса обычно считается устойчивым при использовании частичного поворота , хотя есть примеры стабильных матриц, для которых оно нестабильно. [11]
Исключение по Гауссу может выполняться по любому полю , а не только по действительным числам.
Алгоритм Бухбергера является обобщением метода исключения Гаусса на системы полиномиальных уравнений . Это обобщение сильно зависит от понятия мономиального порядка . Выбор порядка переменных уже подразумевается в исключении Гаусса, что проявляется как выбор работы слева направо при выборе положений поворота.
Вычислить ранг тензора порядка больше 2 NP-сложно . [12] Следовательно, если P ≠ NP , не может быть полиномиального времени аналога исключения Гаусса для тензоров более высокого порядка (матрицы представляют собой массивы, представляющие тензоры порядка 2).
В этом разделе не процитировать любые источники . ( Март 2018 г. ) |
Как объяснено выше, исключение Гаусса преобразует заданную матрицу A размера m × n в матрицу в виде эшелона строк .
В следующем псевдокоде , A[i, j]
обозначает запись матрицы A в строке i и столбце j с индексами, начинающимися с 1. Преобразование выполняется на месте , что означает, что исходная матрица теряется из-за того, что в конечном итоге будет заменена ее строково-эшелонированной формой.
h: = 1 / * Инициализация сводной строки * / k: = 1 / * Инициализация сводного столбца * /а h ≤ m и k ≤ n / * Находим k-ю опорную точку: * / i_max: = argmax (i = h ... m, abs (A [i, k])), если A [i_max, k] = 0 / * В этом столбце нет поворота, переход к следующему столбцу * / к: = к + 1 иначе поменять местами строки (h, i_max) / * Выполните для всех строк ниже pivot: * / для i = h + 1 ... m: f: = A [i, k] / A [h, k] / * Заполняем нулями нижнюю часть сводной колонки: * / A [i, k]: = 0 / * Выполнить для всех оставшихся элементов в текущей строке: * / для j = k + 1 ... n: A [i, j]: = A [i, j] - A [h, j] * f / * Увеличиваем сводную строку и столбец * / ч: = ч + 1 к: = к + 1
Этот алгоритм немного отличается от описанного ранее, поскольку он выбирает опорную точку с наибольшим абсолютным значением . Такой частичный поворот может потребоваться, если в точке поворота элемент матрицы равен нулю. В любом случае выбор максимально возможного абсолютного значения оси поворота улучшает числовую стабильность алгоритма, когда для представления чисел используется плавающая точка .
По завершении этой процедуры матрица будет в виде эшелона строк, и соответствующая система может быть решена путем обратной подстановки .
В Викиучебнике по линейной алгебре есть страница по теме: Исключение Гаусса |