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

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

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

В математике метод исключения Гаусса , также известный как сокращение строк , представляет собой алгоритм решения систем линейных уравнений . Он состоит из последовательности операций над строками, выполняемых над соответствующей матрицей коэффициентов. Этот метод также можно использовать для вычисления ранга матрицы, определителя квадратной матрицы и обратной обратимой матрицы . Метод назван в честь Карла Фридриха Гаусса (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 исключается _из L2 добавлением3/2_от L1 до L2 . _{_} Затем x исключается _из L3 путемдобавления L1 к L3 _{. _} Эти операции над строками помечены в таблице как

$${\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 — это частное произведения элементов диагонали B по d :

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

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

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

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

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

a , b , c , d , eTAранг ATпространствоA,a , b , c , d , eTкакпроизведенияв виде матрицы

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

Вычислительная эффективность

Количество арифметических операций , необходимых для сокращения строк, является одним из способов измерения вычислительной эффективности алгоритма. Например, чтобы решить систему из 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 ⁵ ) .

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

Чтобы с помощью операций над строками привести матрицу размера n × n к уменьшенному эшелонированному виду, необходимо выполнить n ³ арифметических операций, что примерно на 50% больше вычислительных шагов. ^{[11] [ нужны разъяснения ]}

Алгоритм со строго полиномиальным временем

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

• Один из вариантов — представить каждое рациональное число в его сокращенной форме (два взаимно простых целых числа ). Однако это требует от нас сокращения каждой промежуточной дроби с использованием алгоритма Евклида , который имеет слабо-полиномиальное время, но не сильно-полиномиальное (он является полиномиальным в модели машины Тьюринга, но не в арифметической модели).
• Другой вариант — хранить каждое рациональное число в той форме, в которой оно вычислено, вообще без сокращения. Этот алгоритм требует полиномиального числа операций в арифметической модели, но размер кодирования растет экспоненциально, поэтому он не является полиномиальным в модели Тьюринга. Например, если входная матрица имеет 2 на главной диагонали, 1 под главной диагональю и 0 над главной диагональю, и мы всегда поворачиваемся к элементу главной диагонали, то числа на шаге k равны . ${\displaystyle 2^{2^{k}}}$
• Эдмондс использовал третий способ представления дробей, который частично сокращен, и доказал, что он приводит к полиномиальному времени выполнения как в арифметической модели, так и в модели машины Тьюринга.

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

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

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

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

Обобщения

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

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

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

Псевдокод

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

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

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

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

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

Рекомендации

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

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

• Аткинсон, Кендалл А. (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 г.

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

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