ГАУССА МЕТОД

ГАУССА МЕТОД - метод последовательного исключения неизвестных для нахождения решений системы линейных уравнений, впервые описанный К. Гауссом [1]. Пусть дана система

f_j(х) - a_j = a_j1x₁ + ... + a_jтx_т - а_j = 0, j = 1, ..., m, (S⁰)

где a_ji, а_j - элементы произвольного поля Р. Без ограничения общности можно считать, что а₁₁ ≠ 0. Г. м. состоит в следующем. Из второго уравнения системы S⁰ вычитают первое ее уравнение, умноженное почленно на а₂₁/а₁₁, из третьего - первое, умноженное на а₃₁/а₁₁, ..., из m-го - первое, умноженное на а_m1/а₁₁. Пусть S¹ - система полученных уравнений-разностей. При наличии ненулевого коэффициента в S¹ (после возможного изменения порядка уравнений и переменных) поступают с ней так же, как с системой S⁰, и т. д. Если ранг r системы S⁰ (т. е. ранг матрицы ее коэффициентов) меньше числа m, то на r-м шага появляется система S^r с нулевыми коэффициентами при всех неизвестных; при r = m система S^r считается пустой. Система S⁰ тогда и только тогда совместна, когда система S^r либо совместна (т. е. не имеет отличных от нуля свободных членов), либо пуста.

Процесс получения одного из решений (совместной) системы S⁰ может быть описан следующим образом. Берется к.-л. решение (х⁰_r, ..., х⁰_n) системы S^r-1. Придавая значения х⁰_r, ..., х⁰_n неизвестным х_r, ..., х_n в к.-л. уравнении системы S^r-2, имеющем ненулевой коэффициент при х_r-1 (напр., в первом ее уравнении), находят из него x_r-1 = x⁰_r-1 и получают решение (х⁰_r-1, х⁰_r, ..., х⁰_n) системы S^r-2. Иначе говоря, значение x⁰_r-1 получается из системы S^r-2 при замене в ней неизвестных х_r, ..., х_n взятыми их значениями. Значения х⁰_r-1, х⁰_r, ..., х⁰_n подставляются затем в систему S^r-3, находится значение х_r-2 = х⁰_r-2, и получают решение (х⁰_r-2, ..., х⁰_n) и т. д. Найденные так значения х⁰₁, ..., x⁰_r-1 составляют вместе со взятыми значениями х⁰_r, ..., х⁰_n решение (х⁰₁, х⁰₂, ..., х⁰_n) системы S⁰ (см. [2]).

Описанный метод допускает следующее обобщение (см. [4]). Пусть U - нек-рое подпространство векторного пространства Рⁿ и Р^m(U) - множество всех решений {р₁, р₂, ..., р_m) уравнения

p₁f₁(x) + p₂f₂(x) + ... + p_mf_m(x) = 0. (*)

где х пробегает U. Для произвольной конечной системы

pⁱ = (pⁱ₁, pⁱ₂, ..., pⁱ_m), i = 1, 2, ..., l

ненулевых образующих элементов пространства P^m(U) составляется система

(х - неизвестное), наз. U-сверткой системы S⁰. Если пространство P^m(U) не содержит ненулевых элементов, то считается, что система S⁰ имеет пустую U-свертку. Если система S⁰ совместна, то при любом U ее U-свертка совместна или пуста. Установлено, что для совместности системы S⁰ достаточно, чтобы совместной или пустой была ее U-свертка хотя бы для одного U. Пусть, далее, U₁, U₂, ..., U_n - подпространства, порождаемые в пространстве Рⁿ векторами е₁ = (1, 0, ..., 0), е₂ = (0, 1, ..., 0), ..., е_n = (0, 0, ..., 1). Для U = U_i уравнение (*) сводится к уравнению

a_1ip₁ + a_2ip₂ + ... + a_mip_m = 0.

Пусть, напр., i = 1. Если при этом а₁₁ ≠ 0, то в качестве ненулевых образующих элементов пространства Р^m(U₁) можно взять векторы (а₂₁/а₁₁, -1, 0, ..., 0), (a₃₁/a₁₁, 0, -1, ..., 0), ..., (а_m1/а₁₁ 0, 0, ..., -1), и тогда U₁-свертывание системы S⁰ совпадает с процедурой исключения неизвестного х₁ в Г. м.

U-свертывание системы S⁰ при U = U_i + U_k есть процедура одновременного исключения двух неизвестных x_i и х_k. Пусть, напр., i = 1 и k = 2. Если при этом

то для получения (U₁ + U₂)-свертки системы S⁰ можно взять строки матрицы

где

Чередуя исключения отдельных неизвестных с исключением тех или иных пар (или в общем случае наборов) неизвестных, можно для нахождения решений системы S⁰ строить те или иные алгоритмы, обобщающие Г. м.

Лит.: [1] Gauss С. F., Beiträge zur Theorie der algebraischen Gleichungen, Gü tt., 1849; [2] Куpош А. Г., Курс высшей алгебры, 10 изд., М., 1971; [3] Фаддеев Д. К., Фаддеева В. Н., Вычислительные методы линейной алгебры, 2 изд., М.-Л., 1963; [4] Черников С. Н., Линейные неравенства, М., 1968.

С. Н. Черников.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.

Только для вас дипломат кожаный EMINSA на выгоднейших условиях.