Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Описание метода Гаусса
Рассмотрим систему линейных алгебраических уравнений Ax=b, (1.1) где – вектор неизвестных; – вектор свободных членов; , – невырожденная матрица размерами . В силу невырожденности матрицы A для однородной системы уравнений с вектором правых частей имеем единственное тривиальное решение . Для неоднородной системы имеем единственное решение , где A-1 – матрица, обратная A. В курсе высшей математики решение СЛАУ (1.1) обычно выражают по формулам Крамера в виде отношений определителей. Для решения СЛАУ больших порядков эти формулы непригодны, т.к. требуют вычисления (n+1) определителей, а вычисление каждого определителя требует числа арифметических действий порядка n!. В силу того, что n! чрезвычайно быстро растет с увеличением n, решение СЛАУ, например, порядка 100 по формулам Крамера не может быть получено за приемлемое время ни на одной из существующих ЭВМ. На практике требуется решать СЛАУ порядка n=103 и выше. Другая причина неприменимости формул Крамера на ЭВМ – катастрофический рост ошибок округления, называемый численной неустойчивостью. Алгоритм метода исключения неизвестных был изобретен в 3 веке до нашей эры, хотя и носит имя Гаусса. Идея алгоритма состоит в приведении СЛАУ к эквивалентной ей системе с треугольной матрицей (прямой ход исключения), а затем к нахождению неизвестных последовательными подстановками (обратный ход). Данный метод требует числа арифметических операций порядка . Он используется для решения СЛАУ с . Объединим матрицу А и вектор b в расширенную матрицу размерами n ´ (n +1), которая содержит всю известную информацию о системе (1.1). . Опишем вначале прямой ход, первый шаг которого состоит в обнулении всех элементов первого столбца матрицы , кроме того, что находится в первой строке. Введем обозначение для i -й строки матрицы . C матрицей можно обращаться так же, как с исходной системой (1.1), например, осуществлять элементарные преобразования. В качестве последних будем использовать перестановки строк, прибавление к элементам данной строки элементов какой-либо другой строки, умноженных на одно и то же число. Найдем ненулевой элемент в первом столбце матрицы . Такой элемент найдется всегда ибо, в противном случае, весь первый столбец состоит из нулей и матрица – вырожденная. Пусть , тогда поменяем местами строки номера r и 1. Если , то, естественно, перестановка не требуется. Затем вычтем из каждой строки номера i, первую строку, умноженную на число , где . В результате все элементы i -ой строки изменят свои значения и эта строка принимает следующий вид: . В итоге матрица принимает вид . (1.2) Тот же алгоритм может быть применен на втором шаге к - матрице, которая получается из , если убрать в ней первую строку и первый столбец. Применение этого алгоритма j раз приводит к матрице . В матрице полученные нули располагаются в столбцах с номерами от 1 до j ниже диагонали. Эти нули сохраняются во время следующих шагов алгоритма. В результате применения алгоритма n раз система (1.1), в конечном счете, преобразуется в Rx=C, (1.3) где R – верхняя (правая) треугольная матрица, т.е. . (1.4) Значения неизвестных можно вычислить из (1.4) по формулам , , . (1.5) Процесс приведения системы (1.1) к треугольному виду (1.3) называется прямым ходом, а нахождение неизвестных по формулам (1.5) называется обратным ходом. Произведем подсчет числа арифметических операций в методе Гаусса. Число арифметических операций, необходимое для реализации прямого хода в методе Гаусса для решения систем уравнений порядка n, равно . (1.6) При обратном ходе . (1.7) Из формул (1.6) и (1.7) получаем оценку общего числа арифметических действий . Если имеется p систем вида (1.1) с одинаковыми матрицами A и разными правыми частями b1, b2, …, bp, то целесообразно прямой ход осуществлять для всех систем одновременно, для чего следует вместо одной правой части, задаваемой вектором-столбцом, производить операции над p правыми частями (матрицей порядка ). Количество арифметических операций, необходимое для реализации прямого хода метода Гаусса с учетом (1.6) и (1.7), есть . Количество арифметических операций, необходимое для реализации p обратных ходов (для p систем) методом Гаусса, есть , откуда следует, что общее количество арифметических операций, необходимое для реализации p систем с разными правыми частями, равно .
|