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

где s - суммарное число перестановок строк и столбцов.

Если матрица заданной системы вырожденная, то перед исключением  некоторой неизвестной главный  элемент окажется равным нулю. Этим самым и обнаружится, что определитель заданной системы равен нулю.

Пример 2.  Схему вычислений по методу Гаусса с выбором главного элемента поясняет следующий пример:

2,74x₁–1,18x₂+3,17x₃ = 2,18;

1,12x₁+0,83x₂–2,16x₃ =  –1,15;

0,18x₁+1,27x₂+0,76x₃ = 3,23.

Решение ведется в таблице  2.

Выбираем максимальный элемент  в столбцах x₁, x₂ и x₃  раздела A (a₁₃=3,17). Заполняем столбец m_i раздела A, полученный делением элементов столбца x₃ (результат деления берется с обратным знаком) на максимальный элемент a₁₃=3,17:

 

 

Таблица 2

	mi	Коэффициенты при неизвестных			Свободные члены	å	å¢
		x1	x2	x3
А	–1 0,6814 –0,2397	2,74 1,12 0,18	–1,18 0,83 1,27	3,17 –2,16 0,76	2,18 –1,15 3,23	6,91 –1,36 5,44	—
Б	–1 0,1596	2,9870 –0,4768	0,0259 1,5528	— —	0,3355 2,7075	3,3484 3,7835	3,3485 3,7837
В	—	—	1,5569	—	2,7601	4,3170	4,3181

 

В столбец å записываются суммы коэффициентов строк матрицы A:

2,74+(–1,18)+3,17+2,18=6,91;

1,12+0,83+(–2,16)+(–1,15)= –1,36;

0,18+1,27+0,76+3,23=5,44.

Переход к разделу Б ведется следующим образом: строку, содержащую главный (ведущий) элемент, умножаем на m_i и прибавляем к соответствующей i-ой строке. Результат записываем в раздел Б. Строка с ведущим элементом в раздел Б не переписывается.

2,74×0,6814+1,12=2,9870;

(–1,18) × 0,6814 +0,83=0,0259;

2,18×0,6814+(–1,15)=0,3355;

6,91×0,6814+(–1,36)=3,3485

(результат заносится  в столбец å¢).

Далее считает сумму å в каждой строке раздела Б.

2,9870+0,0259+0,3355=3,3484;

–0,4768+1,5528+2,7075=3,7835.

Если столбцы å и å¢ совпадают (с заданной точностью), то вычисления выполнены верно и можно переходить к следующему шагу: выбираем главный элемент (2,9870), считаем m_i и т.д.

В результате обратного хода получаем:

 

 

 

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

Пусть для системы

 

получено приближенное решение  . Положим  .

Тогда для вектора поправки будем иметь уравнение

 

или  ,

где – вектор невязок для приближенного решения .

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

Найдем поправку к полученному в нашем примере решению

.

.

Коэффициенты при неизвестных D₁, D₂, D₃ уже имеются готовыми в таблице 2. Остается лишь преобразовать вектор свободных членов.

Прямой ход

Таблица 3.

 

	mi	Коэффициенты при неизвестных			Свободные члены	å	å¢
		D1	D2	D3
А	–1 0,6814 –0,2397	2,74 1,12 0,18	–1,18 0,83 1,27	3,17 –2,16 0,76	–0,0001 –0,0003 –0,0964	4,7299 –0,2103 2,1136	—
Б	–1 0,1596	2,9870 –0,4768	0,0259 1,5528	— —	–0,0004 –0,0964	3,0125 0,9796	3,0127 0,9798
В	—	—	1,5569	—	–0,0964	1,4605	1,4604

 

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

 

 

 

 

 

 

 

Вывод.

 

Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:

 

1.                 Путем элементарных преобразований  систему уравнений приводят к  эквивалентной ей системе с верхнетреугольной матрицей. Эти действия называют прямым ходом.

 

2.                 Из полученной треугольной системы  переменные находят с помощью  последовательных подстановок (обратный  ход).

 

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

 

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

 

Простейшим итерационным методом решения систем линейных уравнений является метод простой  итерации. Система уравнений (9) преобразуется к эквивалентному виду

.    (13)

Метод простой итерации состоит  в следующем. Выбирается произвольный вектор (начальное приближение) и строится итерационная последовательность векторов по формуле

   (14)

Приведем теорему о  достаточном условии сходимости метода простой итерации.

Если  , то система уравнений (13) имеет единственное решение и итерационный процесс (14) сходится к решению со скоростью геометрической прогрессии.

Допустим, что  - одно из решений системы (13), т.е. выполняется равенство

.    (15)

Отсюда, используя третью аксиому нормы и неравенство , получим:

   (16)

и

или, поскольку  ,

.

Из этого неравенства следует единственность решения однородной системы , т.е. при ,а следовательно, существование и единственность решения системы (14) при любом свободном члене .

Вычтем из равенства (15) равенство (14). Получим

  (17)

и, следовательно,

.

Отсюда на основании 3 аксиомы о норме имеем

,   (18)

т.е. норма разности между  точным решением и  -м приближением стремится к нулю при не медленнее геометрической прогрессии со знаменателем .

Оценим погрешность  -го приближения. Преобразуем равенство (17) к виду

.

Согласно третьей аксиоме  нормы и равенству

,

откуда

.  (18)

Кроме того, в силу (17) имеем

.  (19)

Из (18) и (19) окончательно получаем

.

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

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

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

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

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

 

 

Пример 4.    Методом простой итерации решить систему с точностью до 0,001.

4,5x1–1,8x2+3,6x3=–1,7;	(I)
3,1x1+2,3x2–1,2x3=3,6;	(II)
1,8x1+2,5x2+4,6x3=2,2.	(III)

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

7,6x1+0,5x2+2,4x3=1,9;	(I + II)
2,2x1+9,1x2+4,4x3=9,7;	(2III + II – I)
–1,3x1+0,2x2+5,8x3=–1,4.	(III – II)

 

Отсюда

10x₁=2,4x₁–0,5x₂–2,4x₃+1,9;

10x₂=–2,2x₁+0,9x₂–4,4x₃+9,7;

10x3=1,3x₁–0,2x₂+4,2x₃–1,4.

 

В окончательном виде наша система запишется следующим  образом:

x₁=0,24x₁–0,05x₂–0,24x₃+0,19;

x₂=–0,22x₁+0,09x₂–0,44x₃+0,97;

x₃=0,13x₁–0,02x₂+0,42x₃–0,14.

Матрица B и вектор  ͞c   для этой системы будут иметь вид:

;

.

Нормы матрицы  B и вектора будут соответственно равны:

= max(0,24+0,05+0,24; 0,22+0,09+0,44; 0,13+0,02+0,42)=

        = max(0,53; 0,75; 0,67)=0,75<1.

= max(0,24+0,22+0,13; 0,05+0,09+0,02; 0,24+0,44+0,42)=

= max(0,59; 0,16; 1,10)=1,10>1.

 

=max(0,19; 0,97; 0,14)=0,97.

==max(0,19+0,97+0,14)=1,30.

 

Т.к.< 1, то процесс итераций сходится, и теоретическое число итераций k будет определяться по формуле:

, или

, т.е.

 

Отсюда k ³ 28.

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

Вычисления располагаем  в таблице.

 

Номер итерации	x1	x2	x3
0	0,19	0,97	–0,14
1	0,2207	1,0703	–0,1915
2	0,2354	1,0988	–0,2118
3	0,2424	1,1088	–0,2196
4	0,2454	1,1124	–0,2226
5	0,2467	1,1138	–0,2237
6	0,2472	1,1143	–0,2241
7	0,2474	1,1145	–0,2243

 

На седьмой итерации имеем, что

.

Следовательно, необходимая  точность достигнута.

Ответ: x₁=0,2474; x₂=1,1145; x₃=–0,2243.

ЗАКЛЮЧЕНИЕ

 

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

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

Оптимальным же является комплексное  применение методов решения СЛАУ, т.е. получение приближенного решения  с помощью прямого метода и  последующего уточнения решения  с помощью итерационных методов.

 

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

 

 

1. Мастяева И.Н., Семенихина О.Н. ЧИСЛЕННЫЕ МЕТОДЫ: Учеьно – практическое пособие/МЭСИ. – М., 2003 – 241стр.;
2. И.Н. Мастяева, О.Н. Семенихина. Практикум по курсу «Численные методы»/ Московский государственный университет экономики, статистики и информатики. – М.:МЭСИ, 2003. – 71с..
3. Калиткин Н.Н. и др. Численные методы. М.: Наука, 1982
4. Турчак Л.И. Основы численных методов. М.: Наука, 1987