Решение системы линейных уравнений с помощью метода Гаусса и метода простой итерации

Министерство образования  и науки Российской Федерации

Московский государственный  университет экономики, статистики и информатики.

 

 

Кафедра Прикладной Математики

 

 

 

 

 

Курсовая работа по курсу:

«Численные методы»

на тему:

 

 

«Решение системы линейных уравнений с помощью метода Гаусса и метода простой итерации»

 

 

 

 

Выполнила: Корженко А.А. Группа ДЭК-201 Руководитель: Доцент, К.Т.Н Мастяева И.Н.

 

 

 

 

 

Москва, 2012г.

 

Содержание

 

І Введение

ІІ Решение системы линейных уравнений с помощью метода Гаусса и метода простой итерации:

2.1. Методы решения систем линейных алгебраических уравнений

2.2. Решение системы линейных уравнений с помощью метода Гаусса 2.3. Решение системы линейных уравнений с помощью метода простой итерации

2.4. Алгоритмизация приведения СЛАУ к эквивалентному виду

 

ІІІ Заключение

Список используемой литературы

 

ВВЕДЕНИЕ

Линейная алгебра –  часть алгебры, изучающая векторные (линейные) пространства и их подпространства, линейные отображения (операторы), линейные, билинейные, и квадратичные функции  на векторных пространствах.

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

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

Любой численный метод  линейной алгебры можно рассматривать  как некоторую последовательность выполнения арифметических операций над  элементами входных данных. Если при  любых входных данных численный  метод позволяет найти решение  задачи за конечное число арифметических операций, то такой метод называется прямым. В противоположном случае численный метод называется итерационным. Прямые методы - это такие, как метод Гаусса, метод окаймления, метод пополнения, метод сопряжённых градиентов и др. Итерационные методы – это метод простой итерации, метод вращений, метод переменных направлений, метод релаксации и др. В курсовой работе будут рассматриваться метод Гаусса и метод простой итерации.

 

2.1 Методы решения  систем линейных алгебраических  уравнений

 

К численным методам линейной алгебры относятся численные  методы решения систем линейных алгебраических уравнений, обращения матриц, вычисления определителей и нахождения собственных  векторов матриц.

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

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

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

Метод прогонки является одним  из эффективных методов решения  СЛАУ с трех - диагональными матрицами, возникающих при конечно-разностной аппроксимации задач для обыкновенных дифференциальных уравнений (ОДУ) и  уравнений в частных производных  второго порядка и является частным  случаем метода Гаусса. Рассмотрим следующую СЛАУ:

 

  (1)

 

Что бы решить данное уравнение  методом простой прогонки для начала нужно выразить из первого уравнения системы переменную x₀, а из последнего - переменную x_n, предполагая, что , и запишем эту систему в следующем виде:

  (2)

 

Затем нужно, как бы «прогонять» для каждого из уравнений, т.е.:

 

  (3)

В итоге получаются коэффициенты прогонки.

 

(4)

 

Для лучшего понимания  метода, представлен пример решения  системы линейных уравнений методом  прогонки.

 

Пример 1. Решить систему уравнений методом прогонки.

0,5 x₀ + 2 x₁ + 0,5 x₂ = - 12;

0,5 x₁ + 2 x₂ + 0,5 x₃ = - 6;

0,5 x₂ + 2 x₃+ 0,5 x₄  = 0;

x₀ = 0,5 x₁ – 4;          x₄ =  x₃ +2.

Решение.

Прямой ход. 
Подставим первое краевое условие в первое разностное уравнение:

0,5 (0,5 x₁ – 4) + 2 x₁ + 0,5 x₂ = - 12,  откуда

x₁ = - 0,22222 x₂  - 4,44444.

Выражение для  x₁ подставим во второе разностное уравнение:

0,5(- 0,22222 x₂  - 4,44444) + 2 x₂ + 0,5 x₃ = - 6, откуда

x₂ = - 0,26471 x₃  - 2,00001.

Выражение для  x₂ подставим в третье разностное уравнение:

0,5(- 0,26471 x₃  - 2,00001) + 2 x₃ + 0,5 x₄  = 0, откуда

x₃ = - 0,26772 x₄  + 0,53543.

Обратный ход.

Выражение для x3 подставим во второе краевое условие:

x₄ = - 0,26772 x₄  + 0,53543 + 2 ,  откуда    x₄ =1,99999.

Подставим  x4 в  выражение для x3 :

x₃ = - 0,26772   + 0,53543,    x₃ =0,000017.

Подставим x3 в  выражение для x2 :

x₂ = - 0,26471 ∙ 0 – 2,            x₂ = - 2,00001.

Подставим x2 в  выражение для x1 :

x₁ = - 0,22222 ∙ (-2)  - 4,44444,      x₁ = - 4,00000 ,

и, наконец, подставив x1 в первое краевое условие:

x₀ = 0,5 (-4) – 4 , найдём  x₀ = -6,00000.

 

На равнее с методом простой прогонки есть еще несколько методов решения системы линейных уравнений. Теперь рассмотрим метод из итерационных методов решения системы уравнения.

Итерация Гаусса-Зейделя

Процесс простой итерации иногда можно модифицировать для ускорения сходимости.

Отметим, что итеративный  процесс производит три последовательности – {х₁^(k)}, {х₂^(k)}, {х₃^(k)}, {х₄^(k)}. Кажется разумным, что х₁^(k+1) может быть использовано вместо х₂^(k). Аналогично х₁^(k+1) и х₂^(k+1) можно использовать в вычислении х₃^(k+1). Например, для уравнений из системы (5) это даст следующий вид итерационного процесса Гаусса-Зейделя, использующий (6):

  (5)

  (6)

Такой итерационный процесс  даст результаты: 
Таблица 1

k	х1(k)	х2(k)	х3(k)
0	1.0	2.0	2.0
1	1.75	3.75	2.95
2	1.95	3.96875	2.98625
3	1.995625	3.99609375	2.99903125
…	…	…	…
8	1.99999983	3.99999988	2.99999996
9	1.99999998	3.99999999	3.0
10	2.0	4.0	3.0

Т. е. к точному решению  мы пришли уже на 10-ом шаге итерации.

Вывод.

1. Способ итераций дает возможность получить последовательность приближенных значений, сходящихся к точному решению системы. Для этого система приводится к виду (для случая системы из четырех уравнений):

 

  (7)

Эти формулы как раз  и задают собственно итерационный процесс.

2. При этом чтобы итерационный процесс сходился к точному решению, достаточно, чтобы все коэффициенты системы были малы по сравнению с диагональными.

Это условие можно сформулировать и более точно:

Для сходимости процесса итераций достаточно, чтобы в каждом столбце  сумма отношений коэффициентов  системы к диагональным элементам, взятым из той же строки, была строго меньше единицы:

   (8)

 

2.2 Решение системы  линейных уравнений с помощью  метода Гаусса

Рассмотрим систему линейных алгебраических уравнений

.    (9)

Будем предполагать, что  определитель матрицы А отличен от нуля. Метод Гаусса основан на приведении матрицы А к треугольному виду. Это достигается последовательным исключением неизвестных из уравнений системы. Сначала с помощью первого уравнения исключается x₁ из всех последующих уравнений системы. Затем с помощью второго уравнения исключается x₂ из третьего и всех последующих уравнений. Этот процесс, называемый прямым ходом метода Гаусса, продолжается до тех пор, пока в левой части последнего (п-го) уравнения не останется лишь один член с неизвестным x_n , т.е. матрица системы будет приведена к треугольному виду.

Обратный ход метода Гаусса состоит в последовательном вычислении искомых неизвестных, т.е. решая последнее  уравнение, находим значение x_п; далее, используя это значение, из предыдущего уравнения вычисляем x_п-1 и т.д. Последним найдем x₁ из первого уравнения.

Одной из модификаций метода Гаусса является схема с выбором  главного элемента. Она состоит в  том, что требование a_kk¹0 (на a_kk происходит деление в процессе исключения) заменяется более жестким: из всех оставшихся в матрице элементов нужно выбрать наибольший по модулю и представить уравнение так, чтобы этот элемент оказался на месте ведущего элемента a_kk

ПРЯМОЙ ХОД

При реализации прямого хода метода Гаусса нет необходимости  действовать с переменными  . Достаточно указать алгоритм, согласно которому исходная матрица преобразуется к треугольному виду, и указать соответствующее преобразование  правых  частей системы.  Пусть осуществлены  первые (k-1) шагов, т.е. уже исключены переменные x_1, x₂,…,x_k-1 . Тогда имеем систему

  (10)

где - коэффициенты первой строки матрицы А; - коэффициент i-го уравнения при j переменной, полученный в результате преобразований системы на т–м шаге. Предположим, что в  k - ом уравнении коэффициент . Умножим k -ое уравнение системы на и вычтем полученное соотношение из i-го уравнения системы (10), где .

В результате последняя группа уравнений системы (10) примет вид:

где

 (11)

 

 

ОБОРАТНЫЙ ХОД

Обратный ход, как уже  указывалось, заключается в вычислении неизвестных .Последнее уравнение будет иметь вид

.

Откуда

.

Общая формула обратного  хода для вычисления переменной x_к имеет вид

. (12)

Основным ограничением метода является предположение о том, что все элементы , на которые производится деление, отличны от нуля. Число называется ведущим (или направляющим) элементом на k - м шаге исключения. Даже если какой-то ведущий элемент не равен нулю, а просто близок к нему, в процессе вычислений может происходить сильное накопление погрешностей. Избежать указанных трудностей позволяет метод Гаусса с выбором главного элемента. Основная идея метода состоит в том, чтобы на очередном шаге исключать не следующую по номеру переменную, а ту, коэффициент при которой является наибольшим по модулю.

Пусть на k - ом шаге имеем систему (10). Сначала добиваемся выполнения условия

,

путем перестановки двух уравнений системы (10), а также двух столбцов неизвестных со своими коэффициентами и соответствующей перенумерацией коэффициентов и неизвестных. При этом если переставляются столбцы, то соответствующая перестановка и перенумерация производятся и в уравнениях, которые на k - м шаге не преобразуются, т.е. при .

Найденный максимальный по модулю элемент (если , то этот главный элемент всегда отличен от нуля) называется k - м главным элементом. Затем осуществляются преобразования  k - го шага по формулам (11).

В большинстве существующих стандартных программ одновременно с решением системы линейных алгебраических уравнений (9) вычисляется определитель матрицы А. Определитель полученной в результате прямого хода треугольной матрицы равен произведению её диагональных элементов и отличается от определителя лишь знаком, поскольку в процессе преобразований осуществлялась перестановка строк в столбцов. Поэтому

,