Гауссово исключение

Алгоритм решения систем линейных уравнений

Анимация исключения Гаусса. Красная строка исключает следующие строки, зеленые строки меняют их порядок.

В математике метод исключения Гаусса , также известный как сокращение строк , представляет собой алгоритм решения систем линейных уравнений . Он состоит из последовательности операций по строкам, выполняемых над соответствующей матрицей коэффициентов. Этот метод также можно использовать для вычисления ранга матрицы, определителя квадратной матрицы и обратной обратимой матрицы . Метод назван в честь Карла Фридриха Гаусса (1777–1855). Чтобы выполнить сокращение строк матрицы, используется последовательность элементарных операций над строками для изменения матрицы до тех пор, пока нижний левый угол матрицы не будет заполнен нулями, насколько это возможно. Существует три типа элементарных операций над строками:

• Поменяв местами две строки,
• Умножение строки на ненулевое число,
• Добавление кратного одной строки к другой строке.

Используя эти операции, матрицу всегда можно преобразовать в верхнюю треугольную матрицу , и фактически в ту, которая находится в форме ступенчатой ​​строки . Как только все ведущие коэффициенты (самый левый ненулевой элемент в каждой строке) равны 1, и каждый столбец, содержащий ведущий коэффициент, имеет нули в других местах, говорят, что матрица находится в приведенной форме ступенчатой ​​строки . Эта окончательная форма уникальна; другими словами, она не зависит от последовательности используемых операций над строками. Например, в следующей последовательности операций над строками (где две элементарные операции над разными строками выполняются на первом и третьем шагах) третья и четвертая матрицы находятся в форме ступенчатой ​​строки, а окончательная матрица является уникальной приведенной формой ступенчатой ​​строки. $${\displaystyle {\begin{bmatrix}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{bmatrix}}\to {\begin{bmatrix}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{bmatrix}}}$$

Использование строчных операций для преобразования матрицы в сокращенную строчную ступенчатую форму иногда называетсяИсключение Гаусса–Жордана . В этом случае терминисключение Гауссаотносится к процессу, пока он не достигнет своей верхней треугольной или (нередуцированной) строчной ступенчатой ​​формы. По вычислительным причинам при решении систем линейных уравнений иногда предпочтительнее остановить строчные операции до того, как матрица будет полностью редуцирована.

Определения и пример алгоритма

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

Другая точка зрения, которая оказывается очень полезной для анализа алгоритма, заключается в том, что сокращение строк производит матричное разложение исходной матрицы. Элементарные операции над строками можно рассматривать как умножение слева исходной матрицы на элементарные матрицы . Альтернативно, последовательность элементарных операций, которая сокращает одну строку, можно рассматривать как умножение на матрицу Фробениуса . Затем первая часть алгоритма вычисляет LU-разложение , в то время как вторая часть записывает исходную матрицу как произведение однозначно определенной обратимой матрицы и однозначно определенной приведенной матрицы ступенчатой ​​строки.

Операции со строками

Существует три типа элементарных строчных операций, которые можно выполнять над строками матрицы:

1. Перестановка двух строк.
2. Умножение строки на ненулевой скаляр .
3. Добавление скалярного кратного одной строки к другой.

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

Эшелонная форма

Для каждой строки в матрице, если строка не состоит только из нулей, то самая левая ненулевая запись называется ведущим коэффициентом (или опорной точкой ) этой строки. Таким образом, если два ведущих коэффициента находятся в одном столбце, то операция строки типа 3 может быть использована, чтобы сделать один из этих коэффициентов нулевым. Затем, используя операцию перестановки строк, всегда можно упорядочить строки так, чтобы для каждой ненулевой строки ведущий коэффициент находился справа от ведущего коэффициента строки выше. Если это так, то говорят, что матрица находится в форме ступенчатой ​​строки. Таким образом, нижняя левая часть матрицы содержит только нули, и все нулевые строки находятся под ненулевыми строками. Слово «ступень» здесь используется, потому что можно грубо представить, что строки ранжируются по их размеру, причем самая большая находится наверху, а самая маленькая — внизу.

Например, следующая матрица имеет ступенчатую форму, а ее ведущие коэффициенты показаны красным цветом: $${\displaystyle {\begin{bmatrix}0&\color {red}{\mathbf {2} }&1&-1\\0&0&\color {red}{\mathbf {3} }&1\\0&0&0&0\end{bmatrix}}.}$$

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

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

Пример алгоритма

Предположим, что цель состоит в том, чтобы найти и описать множество решений следующей системы линейных уравнений: $${\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\qquad (L_{1})\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\qquad (L_{2})\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\qquad (L_{3})\end{alignedat}}}$$

Таблица ниже представляет собой процесс сокращения строк, применяемый одновременно к системе уравнений и связанной с ней расширенной матрице . На практике обычно не имеют дело с системами в терминах уравнений, а вместо этого используют расширенную матрицу, которая больше подходит для компьютерных манипуляций. Процедуру сокращения строк можно обобщить следующим образом: исключить x из всех уравнений ниже L ₁ , а затем исключить y из всех уравнений ниже L ₂ . Это приведет систему к треугольной форме . Затем, используя обратную подстановку, можно решить для каждого неизвестного.

Во втором столбце описывается, какие операции со строками были только что выполнены. Так что для первого шага x исключается из L ₂ путем добавления ⁠3/2⁠ L ₁ в L ₂ . Затем x удаляется из L ₃ путем добавления L ₁ к L ₃ . Эти операции со строками обозначены в таблице как $${\displaystyle {\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2},\\L_{3}+L_{1}&\to L_{3}.\end{aligned}}}$$

После того, как y также исключается из третьей строки, результатом становится система линейных уравнений в треугольной форме, и, таким образом, первая часть алгоритма завершена. С вычислительной точки зрения быстрее решать переменные в обратном порядке, процесс, известный как обратная подстановка. Видно, что решение z = −1 , y = 3 и x = 2. Таким образом, существует единственное решение исходной системы уравнений.

Вместо того, чтобы останавливаться, как только матрица примет ступенчатую форму, можно продолжать, пока матрица не примет ступенчатую форму с сокращенными строками, как это сделано в таблице. Процесс сокращения строк до тех пор, пока матрица не будет сокращена, иногда называют исключением Гаусса-Жордана, чтобы отличить его от остановки после достижения ступенчатой ​​формы.

История

Метод исключения Гаусса появляется — хотя и без доказательства — в китайском математическом тексте Глава восьмая: Прямоугольные массивы из Девяти глав о математическом искусстве . Его использование проиллюстрировано в восемнадцати задачах с двумя-пятью уравнениями. Первое упоминание книги под таким названием датируется 179 годом нашей эры, но части ее были написаны еще примерно в 150 году до нашей эры. ^{[1] [2] [3]} Она была прокомментирована Лю Хуэем в 3 веке.

Метод в Европе берет начало из заметок Исаака Ньютона . ^{[4] [5]} В 1670 году он написал, что во всех известных ему книгах по алгебре не было урока по решению одновременных уравнений, который затем предоставил Ньютон. Кембриджский университет в конечном итоге опубликовал заметки как Arithmetica Universalis в 1707 году, спустя много времени после того, как Ньютон оставил академическую жизнь. Заметки широко копировались, что сделало (то, что сейчас называется) Гауссово исключение стандартным уроком в учебниках по алгебре к концу 18-го века. Карл Фридрих Гаусс в 1810 году разработал обозначение для симметричного исключения, которое было принято в 19-м веке профессиональными ручными компьютерами для решения нормальных уравнений задач наименьших квадратов. ^[6] Алгоритм, который преподается в средней школе, был назван в честь Гаусса только в 1950-х годах из-за путаницы в истории предмета. ^[7]

Некоторые авторы используют термин исключение Гаусса для обозначения только процедуры, пока матрица не будет в ступенчатой ​​форме, и используют термин исключение Гаусса–Жордана для обозначения процедуры, которая заканчивается в приведенной ступенчатой ​​форме. Название используется потому, что это вариация исключения Гаусса, описанная Вильгельмом Йорданом в 1888 году. Однако метод также появляется в статье Клазена, опубликованной в том же году. Джордан и Клазен, вероятно, открыли исключение Гаусса–Жордана независимо. ^[8]

Приложения

Исторически первым применением метода редукции строк было решение систем линейных уравнений. Ниже приведены некоторые другие важные применения алгоритма.

Вычисление детерминант

Чтобы объяснить, как метод исключения Гаусса позволяет вычислить определитель квадратной матрицы, нам нужно вспомнить, как элементарные операции со строками изменяют определитель:

• Перестановка двух строк умножает определитель на −1
• Умножение строки на ненулевой скаляр умножает определитель на тот же скаляр.
• Добавление к одной строке скалярного множителя другой не изменяет определитель.

Если гауссово исключение, примененное к квадратной матрице A , дает ступенчатую матрицу строк B , пусть d будет произведением скаляров, на которые был умножен определитель, используя приведенные выше правила. Тогда определитель A является частным от деления на d произведения элементов диагонали B : $${\displaystyle \det(A)={\frac {\prod \operatorname {diag} (B)}{d}}.}$$

С вычислительной точки зрения, для матрицы n × n этот метод требует только O( n ³ ) арифметических операций, в то время как использование формулы Лейбница для определителей требует операций (количество слагаемых в формуле, умноженное на количество умножений в каждом слагаемом) , а рекурсивное разложение Лапласа требует O( n 2 ⁿ ) операций, если под-определители запоминаются для вычисления только один раз (количество операций в линейной комбинации, умноженное на количество под-определителей для вычисления, которые определяются их столбцами) . Даже на самых быстрых компьютерах эти два метода непрактичны или почти непрактичны для n выше 20. ${\displaystyle (n\,n!)}$

Нахождение обратной матрицы

Вариант метода исключения Гаусса, называемый методом исключения Гаусса–Жордана, может быть использован для нахождения обратной матрицы, если она существует. Если A — квадратная матрица размером n × n , то можно использовать редукцию строк для вычисления ее обратной матрицы , если она существует. Сначала единичная матрица размером n × n увеличивается справа от A , образуя блочную матрицу размером n × 2 n [ A | I ] . Теперь, применяя элементарные операции со строками, найдите сокращенную ступенчатую форму этой матрицы размером n × 2 n . Матрица A обратима тогда и только тогда, когда левый блок может быть приведен к единичной матрице I ; в этом случае правый блок конечной матрицы равен A ⁻¹ . Если алгоритм не может привести левый блок к I , то A необратима.

Например, рассмотрим следующую матрицу: $${\displaystyle A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}.}$$

Чтобы найти обратную матрицу, берем следующую матрицу, дополненную тождеством, и сокращаем ее до строки 3 × 6: $${\displaystyle [A|I]=\left[{\begin{array}{ccc|ccc}2&-1&0&1&0&0\\-1&2&-1&0&1&0\\0&-1&2&0&0&1\end{array}}\right].}$$

Выполняя операции со строками, можно проверить, что сокращенная ступенчатая форма этой расширенной матрицы имеет вид $${\displaystyle [I|B]=\left[{\begin{array}{rrr|rrr}1&0&0&{\frac {3}{4}}&{\frac {1}{2}}&{\frac {1}{4}}\\0&1&0&{\frac {1}{2}}&1&{\frac {1}{2}}\\0&0&1&{\frac {1}{4}}&{\frac {1}{2}}&{\frac {3}{4}}\end{array}}\right].}$$

Можно представить себе каждую операцию строки как левое произведение элементарной матрицы . Обозначая через B произведение этих элементарных матриц, мы показали слева, что BA = I , и, следовательно, B = A ⁻¹ . Справа мы сохранили запись BI = B , которая, как мы знаем, является искомой обратной. Эта процедура нахождения обратной работает для квадратных матриц любого размера.

Вычисление рангов и баз

Алгоритм исключения Гаусса может быть применен к любой матрице A размером m × n . Таким образом, например, некоторые матрицы размером 6 × 9 могут быть преобразованы в матрицу, имеющую ступенчатую форму, например , где звездочки — произвольные элементы, а a , b , c , d , e — ненулевые элементы. Эта ступенчатая матрица T содержит массу информации об A : ранг A равен 5, поскольку в T 5 ненулевых строк ; векторное пространство, охватываемое столбцами A , имеет базис, состоящий из его столбцов 1, 3, 4, 7 и 9 (столбцы с a , b , c , d , e в T ), а звездочки показывают, как другие столбцы A могут быть записаны в виде линейных комбинаций базисных столбцов. $${\displaystyle T={\begin{bmatrix}a&*&*&*&*&*&*&*&*\\0&0&b&*&*&*&*&*&*\\0&0&0&c&*&*&*&*&*\\0&0&0&0&0&0&d&*&*\\0&0&0&0&0&0&0&0&e\\0&0&0&0&0&0&0&0&0\end{bmatrix}},}$$

Все это применимо и к форме сокращенного ряда эшелона, которая представляет собой особый формат ряда эшелона.

Эффективность вычислений

Количество арифметических операций, необходимых для выполнения сокращения строк, является одним из способов измерения вычислительной эффективности алгоритма. Например, для решения системы из n уравнений для n неизвестных путем выполнения операций над строками на матрице, пока она не примет ступенчатую форму, а затем решения для каждого неизвестного в обратном порядке, требуется n ( n + 1)/2 делений, (2 n ³ + 3 n ² − 5 n )/6 умножений и (2 n ³ + 3 n ² − 5 n )/6 вычитаний, ^[9] что в общей сложности составляет приблизительно 2 n ³ /3 операций. Таким образом, арифметическая сложность ( временная сложность , где каждая арифметическая операция занимает единицу времени, независимо от размера входов) составляет O( n ³ ) .

Эта сложность является хорошей мерой времени, необходимого для всего вычисления, когда время для каждой арифметической операции приблизительно постоянно. Это имеет место, когда коэффициенты представлены числами с плавающей точкой или когда они принадлежат конечному полю . Если коэффициенты являются целыми числами или точно представленными рациональными числами , промежуточные элементы могут расти экспоненциально большими, поэтому битовая сложность является экспоненциальной. ^[10] Однако алгоритм Барейсса является вариантом гауссовского исключения, который избегает этого экспоненциального роста промежуточных элементов; при той же арифметической сложности O( n ³ ) он имеет битовую сложность O( n ⁵ ) , и поэтому имеет сильно полиномиальную временную сложность.

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

Алгоритм Барейса

Первый сильно полиномиальный по времени алгоритм для метода Гаусса был опубликован Джеком Эдмондсом в 1967 году. ^{[11] : 37} Независимо и почти одновременно Эрвин Барейсс открыл другой алгоритм, основанный на следующем замечании, который применим к варианту метода Гаусса без деления.

В стандартном методе исключения Гаусса из каждой строки , расположенной ниже опорной, вычитается число, кратное значению , где и — записи опорного столбца и соответственно. ${\displaystyle R_{i}}$ ${\displaystyle R_{k}}$ ${\displaystyle R_{k}}$ ${\displaystyle r_{i,k}/r_{k,k},}$ ${\displaystyle r_{i,k}}$ ${\displaystyle r_{k,k}}$ ${\displaystyle R_{i}}$ ${\displaystyle R_{k},}$

Вариант Барейсса заключается в замене на Это создает ступенчатую форму строк, которая имеет те же нулевые элементы, что и при стандартном исключении Гаусса. ${\displaystyle R_{i}}$ ${\textstyle {\frac {r_{k,k}R_{i}-r_{i,k}R_{k}}{r_{k-1,k-1}}}.}$

Главное замечание Барейса заключается в том, что каждый элемент матрицы, сгенерированный этим вариантом, является определителем подматрицы исходной матрицы.

В частности, если начать с целых записей, то деления, происходящие в алгоритме, являются точными делениями, дающими целые числа. Таким образом, все промежуточные записи и конечные записи являются целыми числами. Более того, неравенство Адамара обеспечивает верхнюю границу абсолютных значений промежуточных и конечных записей, и, таким образом, немного усложняет использование мягкой нотации O. ${\displaystyle {\tilde {O}}(n^{5}),}$

Более того, поскольку верхняя граница размера конечных записей известна, сложность может быть получена с помощью модульного вычисления с последующим использованием либо китайского остатка , либо поднятия Гензеля . ${\displaystyle {\tilde {O}}(n^{4})}$

Как следствие, следующие задачи могут быть решены за строго полиномиальное время с той же битовой сложностью: ^{[11] : 40}

• Проверка того, являются ли m заданных рациональных векторов линейно независимыми
• Вычисление определителя рациональной матрицы
• Вычисление решения рациональной системы уравнений Ax = b
• Вычисление обратной матрицы невырожденной рациональной матрицы
• Вычисление ранга рациональной матрицы

Числовая нестабильность

Одной из возможных проблем является численная нестабильность , вызванная возможностью деления на очень малые числа. Если, например, ведущий коэффициент одной из строк очень близок к нулю, то для сокращения строки матрицы необходимо будет выполнить деление на это число. Это означает, что любая ошибка, которая существовала для числа, близкого к нулю, будет усилена. Гауссово исключение численно устойчиво для диагонально доминирующих или положительно определенных матриц. Для общих матриц Гауссово исключение обычно считается устойчивым при использовании частичного поворота , хотя есть примеры устойчивых матриц, для которых оно нестабильно. ^[12]

Обобщения

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

Алгоритм Бухбергера является обобщением метода Гаусса на системы полиномиальных уравнений . Это обобщение в значительной степени зависит от понятия порядка монома . Выбор порядка переменных уже подразумевается в методе Гаусса, что проявляется в выборе работы слева направо при выборе позиций опорных точек.

Вычисление ранга тензора порядка больше 2 является NP-трудной задачей . ^[13] Следовательно, если P ≠ NP , не может быть полиномиального аналога метода исключения Гаусса для тензоров более высокого порядка (матрицы являются представлениями массивов тензоров порядка 2).

Псевдокод

Как объяснялось выше, метод исключения Гаусса преобразует заданную матрицу 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) /* Выполнить для всех строк ниже опорной точки: */ для i = h + 1 ... m: f := A[i, k] / A[h, k] /* Заполните нулями нижнюю часть столбца сводной таблицы: */ А[i, k] := 0 /* Выполнить для всех оставшихся элементов в текущей строке: */ для j = k + 1 ... n: А[i, j] := А[i, j] - А[h, j] * f /* Увеличить опорную строку и столбец */ ч := ч + 1 к := к + 1

Этот алгоритм немного отличается от рассмотренного ранее, выбирая опорную точку с наибольшим абсолютным значением . Такое частичное поворотное движение может потребоваться, если в месте поворотного движения запись матрицы равна нулю. В любом случае, выбор наибольшего возможного абсолютного значения опорной точки улучшает численную устойчивость алгоритма, когда для представления чисел используется плавающая точка. ^[14]

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

Смотрите также

• Фанчэн (математика)
• Процесс Грама–Шмидта — еще один процесс приведения матрицы к некоторому каноническому виду.

Ссылки

1. "DOCUMENTA MATHEMATICA, Vol. Дополнительный том: Истории оптимизации (2012), 9-14". www.emis.de . Получено 2022-12-02 .
2. Кэлинджер 1999, стр. 234–236.
3. Тимоти Гауэрс; Джун Барроу-Грин; Имре Лидер (8 сентября 2008 г.). The Princeton Companion to Mathematics. Princeton University Press. стр. 607. ISBN 978-0-691-11880-2.
4. Гркар 2011a, стр. 169–172
5. Гркар 2011b, стр. 783–785
6. Лауритцен, стр. 3
7. Гркар 2011б, стр. 789
8. Althoen, Steven C.; McLaughlin, Renate (1987), «Редукция Гаусса–Жордана: краткая история», The American Mathematical Monthly , 94 (2), Математическая ассоциация Америки: 130–142, doi : 10.2307/2322413, ISSN  0002-9890, JSTOR  2322413
9. Фарбразер 1988, стр. 12
10. Фан, Синь Гуй; Хавас, Джордж (1997). «О наихудшей сложности целочисленного гауссовского исключения». Труды международного симпозиума 1997 года по символьным и алгебраическим вычислениям . ISSAC '97. Кихеи, Мауи, Гавайи, США: ACM. стр. 28–31. doi :10.1145/258726.258740. ISBN 0-89791-875-4.
11. Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация, Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер документа : 10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, г-н  1261419
12. Голуб и Ван Лоан 1996, §3.4.6
13. Хиллар, Кристофер; Лим, Лек-Хенг (2009-11-07). «Большинство тензорных задач являются NP-трудными». arXiv : 0911.1393 [cs.CC].
14. Кургалин, Сергей; Борзунов, Сергей (2021). «Алгебра и геометрия с Python». SpringerLink . doi :10.1007/978-3-030-61541-3.

Цитируемые работы

• Аткинсон, Кендалл А. (1989), Введение в численный анализ (2-е изд.), Нью-Йорк: John Wiley & Sons , ISBN 978-0471624899.
• Больх, Гюнтер; Грайнер, Стефан; де Меер, Герман; Триведи, Кишор С. (2006), Сети очередей и цепи Маркова: моделирование и оценка производительности с использованием приложений компьютерной науки (2-е изд.), Wiley-Interscience , ISBN 978-0-471-79156-0.
• Калинджер, Рональд (1999), Контекстуальная история математики , Prentice Hall , ISBN 978-0-02-318285-3.
• Farebrother, RW (1988), Линейные вычисления наименьших квадратов , СТАТИСТИКА: Учебники и монографии, Марсель Деккер, ISBN 978-0-8247-7661-9.
• Лауритцен, Нильс, Выпуклость бакалавриата: от Фурье и Моцкина до Куна и Такера.
• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Джонс Хопкинс, ISBN 978-0-8018-5414-9.
• Гркар, Джозеф Ф. (2011a), «Как обычное исключение стало исключением Гаусса», Historia Mathematica , 38 (2): 163–218, arXiv : 0907.2397 , doi : 10.1016/j.hm.2010.06.003, S2CID  14259511
• Гркар, Джозеф Ф. (2011b), «Математики метода Гаусса» (PDF) , Notices of the American Mathematical Society , 58 (6): 782–792
• Хайэм, Николас (2002), Точность и устойчивость численных алгоритмов (2-е изд.), SIAM , ISBN 978-0-89871-521-7.
• Кац, Виктор Дж. (2004), История математики, краткая версия , Addison-Wesley , ISBN 978-0-321-16193-2.
• Kaw, Autar; Kalu, Egwu (2010). "Численные методы с приложениями: Глава 04.06 Исключение Гаусса" (PDF) (1-е изд.). Университет Южной Флориды. Архивировано (PDF) из оригинала 2012-09-07.
• Липсон, Марк; Липшуц, Сеймур (2001), Очерк теории и проблем линейной алгебры Шаума , Нью-Йорк: McGraw-Hill , стр. 69–80, ISBN 978-0-07-136200-9
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Раздел 2.2», Numerical Recipes: The Art of Scientific Computing (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8, архивировано из оригинала 2012-03-19 , извлечено 2011-08-08

Внешние ссылки

• Интерактивный дидактический инструмент