Метод Гаусса

ФОРМУЛЫ КРАМЕРА

АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

СИСТЕМА ЛИНЕЙНЫХ

Пусть дана система m линейных уравнений с n неизвестными

a11x1 + a12x2 +... + a1nxn = b1

a21x1 + a22x2 +... + a2nxn = b2

..........................................

am1x1 + am2x2 +...+ amnxn = bm

Систему (Пример 37.3) можно записать в матрично-векторной форме

А Х = В,

где А - матрица коэффициентов, содержащая m строк и n столбцов:

Здесь В - заданный m-компонентный вектор, Х - искомый n-компонентный вектор;

Формы записи, определяют операцию умножения матрицы А на вектор Х /

Пусть число неизвестных равно числу уравнений, то есть n = m. Далее предположим, что система (3) невырождена, то есть ее определитель (детерминант) отличен от нуля: D = detA? 0. Тогда она имеет единственное решение, которое можно вычислить по формулам Крамера

Здесь Di = detAi, матрица Ai получается из матрицы A заменой i-го столбца столбцом правых частей B:

Хотя формулы Крамера дают решение системы (Пример 37.3) в явном виде, они неэффективны с вычислительной точки зрения [1], за исключением специальных случаев.

Пример 37.6.

Если вычислять определитель непосредственно по его определению, то нужно выполнить (n - 1)n! умножений и n! сложений. Положим n = 15 и возьмем ЭВМ с производительностью 106 умножений в секунду. Тогда вычисление только одного определителя потребует 14 " 15! ї 1,8 " 1013 умножений, в результате чего на вычисление решения уйдет около 10 лет непрерывной работы ЭВМ. Вместе с тем для решения такой системы аналогичной ЭВМ потребуется примерно 0,002 секунд с использованием метода Гаусса.

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

Процесс решения по методу Гаусса состоит из двух этапов, называемых прямым и обратным ходом. На первом этапе система (Пример 37.3) приводится к треугольному виду; на втором (обратный ход) идет последовательное определение неизвестных из указанной треугольной системы.

Для реализации метода Гаусса требуется примерно (2/3)n3 арифметических операций, причем основное число этих действий совершается на этапе прямого хода [1]. В качестве примера, иллюстрирующего метод Гаусса, рассмотрим следующую систему [ Пример 37.7. ]

Пример 37.7.

1,2357x1 + 2,1742x2 - 5,4834x3 = - 2,0735,

6,0696x1 - 6,2163x2 - 4,6921x3 = - 4,8388,

3,4873x1 + 6,1365x2 - 4,7483x3 = 4,8755.

Все результаты расчетов представлены в виде чисел с плавающей запятой с пятью значащими цифрами.

Первый шаг гауссова исключения сводится сначала к умножению первого уравнения на (- 4,9119), а затем на (- 2,8221). Полученные уравнения складываются со вторым и третьим уравнениями системы (Пример 37.7.). В результате получаем равносильную систему

1,2357x1 + 2,1742x2 - 5,4834x3 = - 2,0735,

-16,895x2 + 22,242x3 = 5,3462,

0,0007x2 + 10,727x3 = 10,727.

Чтобы сделать второй шаг, умножим второе уравнение на и сложим с третьим уравнением. С учетом этого получим систему треугольного вида

1,2357x1 + 2,1742x2 - 5,4834x3 = - 2,0735,

-16,895x2 + 22,242x3 = 5,3462,

10,728x3 = 10,727.

Решение указанной системы дает следующие значения неизвестных:

x1 = 0,99968, x2 = 0,99994, x3 = 0,9991.

Этот результат близок к точному решению системы (Пример 37.7.)

x1 = x2 = x3 = 1.

Отметим, что первый этап метода Гаусса может быть использован для вычисления определителя системы (Пример 37.7.)

Действительно, прямой ход метода Гаусса основан на том, что многократно выполняется операция сложения одной из строк матрицы (5) с другой строкой, взятой с некоторым множителем. Известно [1, 4], что такая операция не меняет определителя. Определитель треугольной матрицы равен произведению ее диагональных элементов. В нашем случае для системы (Пример 37.7.)

det R = 1,2357 " (-16,895) " 10,728 = - 223,97,

где R - треугольная матрица системы (9).

Подчеркнем, что метод Гаусса также устанавливает факт отсутствия решения системы (Пример 37.3) (несовместность), а также неединственность.

Пример 37.8.

Решить систему уравнений методом Гаусса:

x1 + x2 + x3 = 3,

2x1 + 3x2 + 4x3 = 9,

2x1 + 2x2 + 2x3 = 6.

В результате применения метода Гаусса к данной системе получаем следующий результат:

x1 + x2 + x3 = 3,

x2 + 2x3 = 3,

0 " x3 = 0.

Отсюда видно, что указанная система имеет неединственное решение.

Пример 37.9.

Решить систему уравнений методом Гаусса:

x1 + x2 + x3 = 3,

2x1 + 3x2 + 4x3 = 9,

2x1 + 2x2 + 2x3 = 7.

Используя процедуру Гаусса, получаем следующую систему:

x1 + x2 + x3 = 3,

x2 + 2x3 = 3,

0 " x3 = 1.

Таким образом, данная система не имеет решений, то есть несовместна:

x1, x2, x3 k.

Дата добавления: 2014-01-04