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

Калининградский государственный технический

университет»

Факультет фундаментальной подготовки

Кафедра высшей математики

КОНТРОЛЬНАЯ РАБОТА

По дисциплине

«ЧИСЛЕННЫЕ МЕТОДЫ»

Вариант № 6

Выполнил

Студент Ефремов Борис Сергеевич

Группа 11ЗАП

Шифр 11ЗАП-366

Проверил

Калининград 2012

Оглавление

Задание 1

Методом Гаусса решить системы линейных алгебраических уравнений Ax=b. Сравнить с точным решением.

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

Здесь описан алгоритм решения системы линейных уравнений с помощью так называемого метода Гаусса. Программу вы можете скачать разделе программы. Алгоритм реализован на языке С.

Пусть у нас есть система N линейных уравнений

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ +... a_1Nx_N = b₁
a₂₁x₁ + a₂₂x₂ + a₂₃x₃ +... a_2Nx_N = b₂
a₃₁x₁ + a₃₂x₂ + a₃₃x₃ +... a_3Nx_N = b₃
...
a_N1x₁ + a_N2x₂ + a_N3x₃ +... a_NNx_N = b_N

где x_i - неизвестные, a_ij - коэффициенты при неизвестных, b_i - свободные члены в уравнениях, i, j пробегают значения от 1 до N.

Цель задачи - зная a_ij и b_i найти x_i.

Суть метода Гаусса состоит в том, что с помощью некоторых операций исходную систему уравнений можно свести к более простой системе. Эта простая система имеет треугольный вид:

Особенность этой системы - в строках с номером i все коэффициенты a_ij при j< i равны нулю.

Если мы смогли привести нашу систему уравнений к такому треугольному виду, то решить уравнения уже просто. Из последнего уравнения находим x_N= b_N / a_NN. Дальше подставляем его в предпоследнее уравнение и находим из него x_N-1. Подставляем оба найденных решения в следующее с конца уравнение и находим x_N-2. И так далее, пока не найдем x₁, на чем решение заканчивается. Такая процедура называется обратной прогонкой.

Теперь перейдем к вопросу как же добиться того, чтобы система стала треугольной.

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

Нужно, чтобы во второй строке получилось уравнение, в которой отсутствует член при x₁. Прибавим к этой строке первую строку, умноженную на некоторое число M.

(a₁₁x₁ + a₁₂x₂ + a₁₃x₃ +... a_1Nx_N = b₁)*M +
a₂₁x₁ + a₂₂x₂ + a₂₃x₃ +... a_2Nx_N = b₂

Получим

(a₁₁*М + a₂₁) x₁ +... = b₁*M + b₂

Для того, чтобы член при x₁ равнялся нулю, нужно, чтобы M = - a₂₁ / a₁₁. Проделав эту операцию, получившееся уравнение запишем вместо второго и приступим к третьему уравнению. К нему мы прибавим первое уравнение, умноженное на M = - a₃₁ / a₁₁ и тоже получим ноль вместо члена при x₁. Такую операцию нужно проделать над всеми остальными уравнениями. В результате получим систему такого вида:

После этого будем избавляться от членов при x₂ в третьем, четвертом, N-ом уравнении. Для этого нужно к уравнению с j-м номером прибавить 2-ое уравнение, умноженное на M = - a_j2 / a₂₂. Проделав эту операцию над всеми остальными уравнениями, получим систему где нет членов с x₂ в уравнениях с номером больше 2.

И так далее... Проделав это для третьего члена, четвертого... до тех пор, пока не кончатся уравнения, получим в итоге систему треугольного вида.

Листинг программы на Паскале в приложении

Результат работы программы:

Vvedite chislo uravneniy n

Vvedite rasshirennuju matricu

po odnomu elementu po strokam

2 -1 0 -2

2 5 -2 -4

1 -1 3 2

2.0000000 -1.0000000 0.0000000 -2.0000000

2.0000000 5.0000000 -2.0000000 -4.0000000

1.0000000 -1.0000000 3.0000000 2.0000000

Dlja prodolgenija nagmite lubuju klavishu

1.0000000 -0.5000000 0.0000000 -1.0000000

0.0000000 1.0000000 -0.3333333 -0.3333333

0.0000000 0.0000000 1.0000000 1.0000000

Dlja prodolgenija nagmite lubuju klavishu

x1=-1.0000000000E+00

x2= 0.0000000000E+00

x3= 1.0000000000E+00

Полученное программой решение верно!

Задание 2

Методом половинного деления найти решения следующих уравнений с точностью 0, 01. Сравнить полученные результаты.