Метод Гаусса для решения систем линейных алгебраических уравнений (СЛАУ)

May 20, 2009 / Author AlexR / Category Posts, Численные методы / Comment

Теоретическая часть

Метод Гаусса представляет собой обобщение способа подстановки и состоит в последовательном исключении неизвестных до тех пор, пока не останется одно уравнение с одним неизвестным.

При этом матрица СЛАУ приводится  треугольному виду, где ниже главной диагонали располагаются только нули.

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

Имеем Ax=b, где A=[aij] – матрица размерности n?n, det A>0, b=(a1, n+1, …, an, n+1)T.

В предположении, что a11>0, первое уравнение системы (1):

S((j=1;n) a{0}{i,j}*x{j})=b{0}{j}, i=1,..,n

делим на коэффициент a11, в результате получаем уравнение

x{1}+S((j=2,n) a{1}{1,j}*x{j}=b{1}{1}

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

S((j=2,n) a{1}{i,j}x{j}=b{1}{j}, i=2,..,n

Первое неизвестное оказалось исключенным из всех уравнений, кроме первого. Далее предполагаем, что a{1}{2,2} и исключаем неизвестное x2 из всех уравнений, начиная со второго, и т.д. В результате последовательного исключения неизвестных система уравнений преобразуется в систему уравнений с треугольной матрицей (2):

x{i}+S((j=i+1,n) a{i}{i,j}*x{j}=b{i}{i}, i=1,..,n

Совокупность проведенных действий называется прямым ходом метода Гаусса.

Из nго уравнения системы (2) определяем xn, из (n-1)-го – xn-1 и т.д. до x1. Совокупность таких действий называется обратным ходом метода Гаусса.

Реализация прямого хода требует N~(2*n^3)/3 арифметических операций, а обратного – N~n^2 арифметических операций.

Алгоритм

Блок-схема к методу Гаусса

Описание входной информации: Str (Stlb) – количество строк (столбцов) в расширенной матрице, Ab [i, j] – матрица A (i – строки, j – столбцы).

Описание выходной информации: Ans – матрица-ответ.


Ссылки для скачивания:
Метод Гаусса на MatLab7
Метод Гаусса на Pascal ABC

Вернуться назад

11 Comments to “Метод Гаусса для решения систем линейных алгебраических уравнений (СЛАУ)”

Comments

  1. AlexR

    Лио, да, согласен. Рисовал в университете, прошло много времени, теперь и сам ничего понять не могу. Не знаю как работу приняли =)

  2. Лио

    бредовая блок схема. переходы между картинками не совпадают. ужаааааас

  3. Лио

    ужасная блок схема! непонятно ничего…переходы не совпадают вообще.

  4. AlexR

    ОфигевшийСтудент, Вы были правы. Я отредактировал программу на PascalABC. NET. Теперь все в порядке

  5. AlexR

    Вы не представляете, но я тоже эту программу сдавал в университете, почему-то у меня все верно работает. Но я все равно ее еще раз проверю.

  6. ОфигевшийСтудент

    прога не работает, ответы левые выдает, препод в универе офигел, как увидел!!

  7. 123123

    блок схема ужастна, ничего не понятно

  8. AlexR

    Я старался описать каждую переменную и ход программы в комментариях к программам.

  9. den

    Объясните мне пожалуйста как рабаотает программа(поэтапно плз) и что означает каждая из переменныйх.Плз.

  10. AlexR

    Dap, Вы все верно говорите. Есть свои функции в MatLab, с помощью которых можно решить ту или иную задачу. Об этом можно прочитать в любом самоучителе. Но в этом разделе показываются программы сделанные своими руками. Если возможность есть, если есть более оптимизированное решение задачи, пожалуйста, можно его изложить. Я же изначально задавал себе цель решить задачу, не пользуясь преднаписанными функциями MatLab’a. Мне интересно было не исходное решение, а изучение метода, в данном случае, Гаусса и его реализация на компьютере. А так, конечно, для того, чтобы на скорую руку решить задачу можно пользоваться функциями.

  11. dap

    Приведенный здесь метод Гаусса на матлаб не оптимизирован. матлаб известен своей быстротой в матричных вычислениях, а приведенный алгоритм вычисляет треугольную матрицу поэлементно. Было бы лучше вычислять не каждый элемент строки по отдельности, а всю строку разом. Также удобнее пользоваться встроенными в матлаб функцией поиска максимума (она и порядковый номер максимального элемента выдавать умеет), поэлементное перемножение двух векторов/матриц и тому подобное.
    В целом реализация наглядна, но для реальных задач (где встречаются матрицы большого порядка) неприменима.

Comments