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

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

В математике метод исключения Гаусса , также известный как сокращение строк , представляет собой алгоритм решения систем линейных уравнений . Он состоит из последовательности операций над строками, выполняемых над соответствующей матрицей коэффициентов. Этот метод также можно использовать для вычисления ранга матрицы, определителя квадратной матрицы и обратной обратимой матрицы . Метод назван в честь Карла Фридриха Гаусса (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 ³ ) арифметические операции, тогда как использование формулы Лейбница для определителей требует $(n\,n!)$ операций (количество слагаемых в формуле, умноженное на количество умножений в каждом слагаемом) , и рекурсивное разложение Лапласа требует O( n 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 /* Initialization of the pivot row */
k := 1 /* Initialization of the pivot column */

while h ≤ m and k ≤ n
    /* Find the k-th pivot: */
    i_max := argmax (i = h ... m, abs(A[i, k]))
    if A[i_max, k] = 0
        /* No pivot in this column, pass to next column */
        k := k + 1
    else
        swap rows(h, i_max)
        /* Do for all rows below pivot: */
        for i = h + 1 ... m:
            f := A[i, k] / A[h, k]
            /* Fill with zeros the lower part of pivot column: */
            A[i, k] := 0
            /* Do for all remaining elements in current row: */
            for j = k + 1 ... n:
                A[i, j] := A[i, j] - A[h, j] * f
        /* Increase pivot row and column */
        h := h + 1
        k := k + 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 г.

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

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