Кафедра математического анализа

Метод ГАУССА и его модификации

    Методические указания для лабораторных занятий и самостоятельной работы студентов по вычислительной математике специальностей Математика 050201, Информатика 050202, Физика 050203    

Курган 2006

Кафедра математического анализа

Дисциплина «Математика» (специальности 050201,050202, 050203)

Составил: канд. пед. наук, доцент Михащенко Т.Н.

Составлены на основании ГОС ВПО для специальностей Математика «050201.65», Информатика «050202.65», Физика «050203.65». Методические указания могут быть использованы для проведения лабораторных занятий и организации самостоятельной работы студентов специальности 050202 – Информатика с дополнительной специальностью математика, 050201 – Математика с дополнительной специальностью информатика                                                                         

Введение

Как утверждается в книге известного американского математика Валяха, 75% всех расчётных математических задач приходится на решение систем линейных алгебраических уравнений. Это не удивительно, так как математические модели тех или иных явлений или процессов либо сразу строятся как линейные, либо сводятся к таковым. Поэтому трудно переоценить роль, которую играет выбор эффективного способа решения системы линейных уравнений. Современная вычислительная математика располагает большим арсеналом методов, а математическое обеспечение ЭВМ­ – многими пакетами прикладных программ, позволяющих решать различные возникающие на практике линейные системы.

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

В пособии содержатся методические рекомендации по организации вычислений, задание для лабораторной работы по теме «Методы решения систем линейных уравнений», все схемы снабжены подробными инструкциями по их применению и алгоритмизированы для программирования на ЭВМ.

На выбор студенту предлагается несколько модификаций проведения и оформления вычислений: полная и компактная схемы Гаусса, модификация Краута-Дулитла, схема Гаусса с выбором главного элемента и схема Халецкого. 

1. Компактная схема Гаусса

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

Рассмотрим порядок составления схемы для системы четырёх уравнений с четырьмя неизвестными. Все результаты вычислений будем записывать в одну таблицу (табл. 1).

Порядок заполнения таблицы, прямой ход:

1) Записываем коэффициенты данной системы в четырёх строках и пяти столбцах раздела I (табл. 1).

2) Суммируем все коэффициенты по строке и записываем сумму в столбце å (столбец контроля), например a₁₆= .

3) Делим все числа, стоящие в первой строке, на a₁₁ и результаты b_1j=a_1j /a₁₁ записываем в пятой строке раздела I.

4) Вычисляем  и делаем проверку. Если вычисления ведутся постоянным знаком после запятой, то числа b₁₆ и  не должны отличаться более чем на единицу последнего разряда. В противном случае следует проверить действия пункта 3.

5) Вычисляем коэффициенты a  (i =2,3,4; j=2,3,4,5,6):a =a_ij–a_i1b_1j.

6)   Результаты записываем в первые три строки раздела II.

7) Делаем проверку. Сумма элементов каждой строки  (i=2,3,4) не должна отличаться от a  более чем на единицу последнего разряда (если все вычисления ведутся с постоянным числом знаков после запятой).

8) Делим все элементы первой строки раздела II на a  и результаты записываем в четвёртой строке раздела II. Делаем проверку как в пункте 4.

9) Вычисляем a ,  a =a –a b , (i=3,4; j=3,4,5,6). Делаем проверку, как в пункте 6.

10) Делим элементы первой строки раздела III на a  и находим числа b =a /a . Все результаты записываем в третьей строке раздела III. Делаем проверку.

11) Вычисляем a =a  - a b . Результаты записываем в разделе IV.

Таблица 1

Компактная схема Гаусса

	i	ai1	ai2	ai3	ai4	ai5	S= ai6
I	1	a11	a12	a13	a14	a15	Sa1j = a16
	2	a21	a22	a23	a24	a25	Sa2j = a26
	3	a31	a32	a33	a34	a35	Sa3j = a36
	4	a41	a42	a43	a44	a45	Sa4j = a46
		1	b12	b13	b14	b15	a16 / a11= b15
II	2		a	a	a	a	a
	3		a	a	a	a	a
	4		a	a	a	a	a
			1	b	b	b	a /a =b
III	3			a	a	a	a
	4			a	a	a	a
				1	b	b	a /a =b
IV	4				a	a	a
V					1	x4
				1		x3
			1			x2
		1				x1

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

12) В разделе V записываем единицы, как это указано в табл. 1, вычисляем x₄=a /a .

13) Для вычисления значений x₃,x₂,x₁ используются лишь строки разделов I, II, III, содержащие единицы (отмеченные строки). Так для вычисления x₃ умножаем x₄ на b  и получившееся произведение вычитаем из b . При этом единицы, расставленные в разделе V, помогают находить для x_i (i=3,2,1) соответствующие коэффициенты    в    отмеченных    строках.  Таким  образом,

x₃= b - b x_4.

14) Вычисляем x₂, и затем x₁, для чего используем элементы отмеченной строки раздела II:       x₂= b - b x₄- b  x₃,  

x₁= b - b x₄ - b x₃ - b x₂.

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

Решим с помощью компактной схемы Гаусса систему уравнений, все вычисления занесем в таблицу (табл.2):

Следуя порядку действий, указанному в параграфе 1, получаем значения неизвестных: x₄=0,068976; х₃=-1,815417; x₂=0,964032; х₁=4,870672.

Проверка показывает, с какой точностью получен результат, погрешность вычислений не превосходит соответственно 0,0000029;  0,0000028; 0,000001; 0,000016 в первом, втором, третьем и четвертом уравнениях.

Таблица 2

2. Модификация Краута – Дулитла

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

Порядок заполнения таблицы, прямой ход:

1) Записываем коэффициенты системы a_ijдля i=1,2,3,4; j=1,2,3,4,5 в разделе I (табл.3).

2) Суммируем коэффициенты по каждой строке и результаты заносим в столбец å в качестве a_i6 (i=1,2,3,4).

3) При i=2,3,4 находим числа m_i1= a_i1 / a₁₁ и записываем их в разделе II.

4) При j=2,3,4,5,6 вычисляем коэффициенты a  по формуле a = a_2j ­– m₂₁а_1j и записываем их вразделе III.

5) Контроль: сумма  не должна отличаться от a  более чем на единицу последнего разряда.

6) При i=3,4 находим числа т_i2по формуле т_i2=(a_i2– m_i1a₁₂)/ a  и заносим в раздел IV.

7)  При j=3,4,5,6 вычисляем коэффициенты a  по формуле

 a = a_3j – m₃₁a_1j – m₃₂ a  и записываем в раздел V.

8) Находим число m₄₃=(a₄₃ – m₄₁а₁₃ – m₄₂a )/ a  и записываем его в раздел VI.

9) При j=4,5,6 находим коэффициенты a  по формуле                                         a = a_4j – m₄₁a_1j – m₄₂a  – m₄₃a   и записываем в раздел VII.

10) Контроль: сравниваем сумму a ­ + a  с числом a .

Обратный ход осуществляется аналогично компактной схеме Гаусса. Находим неизвестные x₄, x₃, x₂, x₁ по формулам: a x₄=a ,  a x₃+a x₄= a ,  a x₂+ a x₃+ a x₄= a ,     a₁₁x₁+a₁₂x₂+a₁₃x₃+a₁₄x₄= a₁₅.Вычисления по этим формулам ведутся без промежуточных за­писей. Результаты записываются в разделе VIII таблицы.

Таблица 3

Схема Краута – Дулитла

	ai1	ai2	ai3	ai4	ai5	å= ai6
I	a11 a21 a31 a41	a12 a22 a32 a42	a13 a23 a33 a43	a14 a24 a34 a44	a15 a25 a35 a45	a16 = åa1j a26 = åa2j a36 = åa3j a46 = åa4j
II	m21 m31 m41
III		a	a	a	a	a
IV		m32 m42
V			a	a	a	a
VI			m43
VII				a	a	a
VIII	1	1	1	1	x4 x3 x2 x1

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

Решим предыдущую систему с помощью схемы Краута – Дулитла систему уравнений, результаты вычислений занесем в таблицу (табл.4).

Таблица 4