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

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

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

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

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

$${\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 , чтобы обнулить один из этих коэффициентов. Затем, используя операцию замены строк, всегда можно упорядочить строки так, чтобы для каждой ненулевой строки старший коэффициент находился справа от старшего коэффициента строки выше. В этом случае говорят, что матрица имеет форму эшелона строк. Таким образом, нижняя левая часть матрицы содержит только нули, а все нулевые строки находятся ниже ненулевых строк. Слово «эшелон» используется здесь потому, что можно грубо представить себе, что строки ранжируются по их размеру: самая большая находится вверху, а самая маленькая — внизу.

Например, следующая матрица имеет форму звена строк, а ее старшие коэффициенты показаны красным:

$${\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).

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

Предположим, что цель состоит в том, чтобы найти и описать множество решений следующей системы линейных уравнений:

$${\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 ₂ . Это придаст системе треугольную форму . Затем, используя обратную замену, можно решить каждое неизвестное.

Система уравнений	Операции со строками	Дополненная матрица
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\end{alignedat}}$		$\left[{\begin{array}{rrr|r}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&2y&{}+{}&z&{}={}&5&\end{alignedat}}$	${\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2}\\L_{3}+L_{1}&\to L_{3}\end{aligned}}$	$\left[{\begin{array}{rrr|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&2&1&5\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&&&-z&{}={}&1&\end{alignedat}}$	$L_{3}+-4L_{2}\to L_{3}$	$\left[{\begin{array}{rrr|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]$
Матрица теперь имеет эшелонированную форму (также называемую треугольной формой).
${\begin{alignedat}{4}2x&{}+{}&y&&&{}={}7&\\&&{\tfrac {1}{2}}y&&&{}={}{\tfrac {3}{2}}&\\&&&{}-{}&z&{}={}1&\end{alignedat}}$	${\begin{aligned}L_{1}-L_{3}&\to L_{1}\\L_{2}+{\tfrac {1}{2}}L_{3}&\to L_{2}\end{aligned}}$	$\left[{\begin{array}{rrr|r}2&1&0&7\\0&{\frac {1}{2}}&0&{\frac {3}{2}}\\0&0&-1&1\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&\quad &&{}={}&7&\\&&y&\quad &&{}={}&3&\\&&&\quad &z&{}={}&-1&\end{alignedat}}$	${\begin{aligned}2L_{2}&\to L_{2}\\-L_{3}&\to L_{3}\end{aligned}}$	$\left[{\begin{array}{rrr|r}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]$
${\begin{alignedat}{4}x&\quad &&\quad &&{}={}&2&\\&\quad &y&\quad &&{}={}&3&\\&\quad &&\quad &z&{}={}&-1&\end{alignedat}}$	${\begin{aligned}L_{1}-L_{2}&\to L_{1}\\{\tfrac {1}{2}}L_{1}&\to L_{1}\end{aligned}}$	$\left[{\begin{array}{rrr|r}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

Во втором столбце указано, какие операции со строками только что были выполнены. Итак, на первом этапе x исключается L2 _из добавлением 3/2 ​ от L ₁ до L ₂ . Затем x исключается L3 _​ путем L1 _{добавления} к L3 _. из Эти операции над строками помечены в таблице как

$${\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 году до нашей эры. Это прокомментировал Лю Хуэй в III веке.

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

Некоторые авторы используют термин «исключение Гаусса» для обозначения только процедуры до тех пор, пока матрица не примет эшелонированную форму, и используют термин «исключение Гаусса – Жордана» для обозначения процедуры, которая заканчивается в форме сокращенного эшелона. Это название используется потому, что оно представляет собой разновидность метода исключения Гаусса, описанного Вильгельмом Йорданом в 1888 году. Однако этот метод также появляется в статье Класена, опубликованной в том же году. Джордан и Клазен, вероятно, открыли исключение Гаусса – Джордана независимо.

Приложения

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

определителей

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

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

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

$$\det(A)={\frac {\prod \operatorname {diag} (B)}{d}}.$$

В вычислительном отношении для матрицы размера n × n этому методу требуется только O( n ³ ) арифметических операций, тогда как использование формулы Лейбница для определителей требует O( n !) операций (количества слагаемых в формуле), и рекурсивное разложение Лапласа требует O(2 ^н ) операций (количество поддетерминантов для вычисления, если ни один из них не вычисляется дважды). Даже на самых быстрых компьютерах эти два метода непрактичны или почти неосуществимы при n выше 20.

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

См. Также: Обратимая матрица.

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

Например, рассмотрим следующую матрицу:

$$A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}.$$

Чтобы найти обратную эту матрицу, берется следующая матрица, дополненная единицей, и сокращается по строкам до матрицы 3 × 6:

$$[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].$$

Выполняя операции со строками, можно проверить, что сокращенная форма эшелона строк этой расширенной матрицы имеет вид

$$[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 , которая, как мы знаем, является желаемой инверсией. Эта процедура поиска обратной работы работает для квадратных матриц любого размера.

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

Алгоритм исключения Гаусса можно применить к любой размера m × n матрице A . Таким образом, например, некоторые матрицы 6 × 9 могут быть преобразованы в матрицу, имеющую форму эшелона строк, например

$$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}},$$

где звездочки — произвольные записи, а a , b , c , d , e — ненулевые записи. Эта эшелонированная матрица T содержит огромное количество информации об A : ранг A равен 5 , имеется 5 ненулевых строк поскольку в T ; векторное пространство , охватываемое столбцами A, имеет основу, состоящую из столбцов 1, 3, 4, 7 и 9 (столбцы с a , b , c , d , e в T ), а звездочки показывают, как другие столбцы A можно записать как линейные комбинации базисных столбцов.

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

эффективность

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

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

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

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

Основная статья: Алгоритм Барейсса

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

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

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

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

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

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

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

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

Численная

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

Обобщения

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

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

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

Псевдокод

Как объяснялось выше, метод исключения Гаусса преобразует заданную размера m × n матрицу A в матрицу в форме звеньев строк .

следующем псевдокоде В 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: 
                  A[i, j] := A[i, j] - A[h, j] * f 
          /*  Увеличение сводной строки и столбца  */ 
          ч := ч + 1 
          к := к + 1 
 

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

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

См. также

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

Ссылки

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

• Аткинсон, Кендалл А. (1989), Введение в численный анализ (2-е изд.), Нью-Йорк: John Wiley & Sons , ISBN  978-0471624899 .
• Болх, Гюнтер; Грейнер, Стефан; де Меер, Герман; Триведи, Кишор С. (2006), Сети массового обслуживания и цепи Маркова: моделирование и оценка производительности с помощью компьютерных приложений (2-е изд.), Wiley-Interscience , ISBN  978-0-471-79156-0 .
• Калинджер, Рональд (1999), Контекстуальная история математики , Прентис Холл , ISBN  978-0-02-318285-3 .
• Фарбратер, 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) , Уведомления Американского математического общества , 58 (6): 782–792
• Хайэм, Николас (2002), Точность и стабильность числовых алгоритмов (2-е изд.), SIAM , ISBN  978-0-89871-521-7 .
• Кац, Виктор Дж. (2004), История математики, краткая версия , Аддисон-Уэсли , ISBN  978-0-321-16193-2 .
• Кау, Аутар; Калу, Эгву (2010). «Численные методы с приложениями: Глава 04.06 Исключение Гаусса» (PDF) (1-е изд.). Университет Южной Флориды. Архивировано (PDF) из оригинала 7 сентября 2012 г.
• Липсон, Марк; Липшуц, Сеймур (2001), Очерк теории и проблем линейной алгебры Шаума , Нью-Йорк: McGraw-Hill , стр. 69–80, ISBN  978-0-07-136200-9
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), «Раздел 2.2» , Численные рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN  978-0-521-88068-8 , заархивировано из оригинала 19 марта 2012 г. , получено 8 августа 2011 г.

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

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