По столбцам

А) Метод Гаусса для решения систем линейных уравнений

Пусть требуется решить систему п линейных алгебра­ических уравнений с п неизвестными:

(3.9)

Прямой ходметода Гаусса преобразует систему (3.9) к треугольному виду исключением соответствующих неиз­вестных. Пусть a₁₁ ¹ 0 . Первый шаг заключается в исклю­чении переменной x₁с помощью первого уравнения из ос­тальных уравнений. Разделим первое уравнение на a₁₁:

; . (3.10)

Затем от второго уравнения вычтем первое уравне­ние, умноженное на a₂₁. В результате, на месте второго уравнения получим уравнение, не содержащее х₁. Чтобы исключить х₁ из третьего уравнения, вычтем из первое уравнение, умноженное на a₃₁. Аналогично ис­ключаем х₁из четвертого и последующих уравнений. Для исключения х₁из i-го уравнения (i = 2, 3, ... , п)приме­ним формулы

; . (3.11)

В результате этих вычислений получим систему вида

(3.12)

На втором шаге исключаем переменную х₂с помощью второго уравнения из третьего и последующих уравне­ний. Предположим, что ¹ 0. Разделим второе уравне­ние на :

; . (3.13)

Затем в системе (3.12) с помощью второй строки исключим

х₂ из i-го уравнения (i = 3, 4, ... , n), применяя формулы:

; . (3.14)

Система (3.12) преобразуется к следующему виду:

(3.15)

1. В общем случае на шаге т для т = 1, 2,..., n - 1,

делим сначала т-е уравнение на :

; , (3.16)

а затем исключаем переменную x_m c помощью m-го уравнения из i-го, где

i = m +1,..., n:

; . (3.17)

Здесь предполагается, что на каждом шаге выполня­ется условие ¹ 0.

В результате (n - 1)-го шага система (3.9) приобретает вид

(3.18)

2. Обратный ход метода Гаусса вычисляет неизвест­ные x_i в обратном порядке. Из последнего уравнения в (3.18) находим

х_п = (3.19)

Неизвестные x_i определяем по следующим формулам:

x_i = i = n - 1,n - 2,..., 1.(3.20)

Метод Гаусса предполагает, что на т-мшаге выполня­ется условие ¹ 0. Если это условие не выполняется, то алгоритм перестанет работать, так как столкнется с делением на 0. Кроме этого, в случае выполнения усло­вия ¹ 0, может возникнуть ситуация, когда ведущий элемент близок к нулю, что также может привести к неприятностям в виде больших погрешностей.

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

Метод Гаусса с выбором главного элемента по стол­бцамотличается от алгоритма (3.16) – (3.20) только тем, что перед преобразованием (3.16) нужно выполнить по­иск максимального по модулю элемента в т-мстолбце и переставить строки системы уравнений так, чтобы мак­симальный элемент стал диагональным элементом матри­цы коэффициентов.

б) Алгоритм метода Гаусса с выбором главного элемента

1. Для т = 1, 2, ... , п - 1 выполним преобразования: Найдем максимальный по абсолютной величине эле­мент в т-м столбце. Пусть это будет элемент a_im.Если i ¹ т, то меняем местами i-ю и т-юстроки:

r =, = , = r , j = 1, ... , п;

r = b_i, b_i = b_т, b_т = r.

Элементы матрицы и вектора-столбца свободных членов после преобразования на т-м шаге обозначим , , причем = , = b_i.

Делим т-е уравнение на ведущий элемент :

; ,

затем исключаем переменную х_т с помощью m-го урав­нения из i-го, где

i = т + 1,..., п:

; .

2.Вычисляем неизвестные x_i в обратном порядке:

х_п =; x_i = i = n - 1,n - 2,..., 1.

Приведенный вариант метода Гаусса дает решение и тогда, когда обычный метод Гаусса перестает работать из-за деления на 0.

При реализации метода Гаусса на каком-либо языке программирования удобно использовать исходные матри­цу a и вектор bдля хранения промежуточных результатов преобразований. Приведенные формулы преобразова­ний записываются как операторы присваивания, т. е. имена переменных a_ij и b_i записываются без верхних ин­дексов.

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

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

Отметим, что последний вари­ант с выбором главного элемента считается лучшим.

Общее число операций для решения системы уравне­ний методом Гаусса составляет приблизительно 2n³/3 + 2n², при этом большая часть, т. е. 2п³/3, операций при­ходится на прямой ход.