Схема Гаусса с выбором главного элемента

Рассмотрим линейную систему уравнений:

Запишем расширенную матрицу коэффициентов системы:

M= .

Среди элементов матрицы a_ij (i, j =1,...,n) выберем наибольший по модулю, называемый главным элементом. Пусть им будет, например, элемент a_pq. Строка с номером p, содержащая главный элемент, называется главной строкой. Далее вычисляем множители m_i = a_iq / a_pq для всех i p. Затем преобразуем матрицу следующим образом: из каждой i -й неглавной строки вычитаем почленно главную строку, умноженную на m_i. В результате получим матрицу, у которой все элементы q -го столбца, за исключением, а_pq равны нулю. Отбрасывая этот столбец и главную строку, получим новую матрицу M _t с меньшим на единицу числом строк и столбцов.

Над матрицей M₁, повторяем те же операции, после чего получим матрицу M_2,и т. д. Такие преобразования продолжаем до тех пор, пока не получим матрицу, содержащую одну строку из двух элементов, которую считаем тоже главной. Затем объединяем все главные строки, начиная с последней. После некоторой перестановки они образуют треугольную матрицу, эквивалентную исходной. На этом заканчивается этап вычислений, называемый прямым ходом. Решив систему с полученной треугольной матрицей коэффициентов, найдем последовательно значения неизвестных x _i (i =1,2,...,n). Этот этап вычислений называется обратным ходом.

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

Результаты всех вычислений удобно записывать в таблицу.

Прямой ход:

1) Записываем в первом разделе таблицы коэффициенты системы

a_ij (i =1,2,3,4; j =1,2,3,4,5).

2) В столбце = a_{i 6} записываем суммы коэффициентов по каждой строке.

3) Находим главный элемент, подчёркиваем его.

4) Находим числа m_i по формуле m_i= a_iq / a_pq, где a_pq – главный элемент и результаты записываем в столбце m_i раздела I.

5) Из каждой i –ой строки вычитаем главную строку, умноженную на соответствующий элемент m_i.

6) Контроль: находим суммы и сравниваем с a_i6.

Решим с помощью данного метода ту же самую систему уравнений: .

Результаты всех вычислений будем записывать в таблицу (табл. 5):

Прямой ход:

1) Записываем в первом разделе таблицы коэффициенты системы

a_ij (i= 1,2,3,4; j =1,2,3,4,5).

2) В столбце = a_{i 6} записываем суммы коэффициентов по каждой строке.

3) Находим главный элемент. В данной системе им будет коэффициент a ₁₄= -8,2 (p =1, q =4), выделяем этот элемент.

4) Находим числа m_i (i= 2,3,4). Для этого делим элементы столбца a_{i 4} на a ₁₄ и результаты записываем в столбце m_i разделаI:

m ₂= = =-0,292683; m ₃= = =0,3170732; m ₄= = =-0,256098.

5) Вычисляем коэффициенты новой матрицы. Из каждой i –ой (i= 2,3,4) строки вычитаем главную строку, умноженную на соответствующий элемент m_i.

Так, при i= 2 будем иметь:

1 – (-0,292683)*2=1,5853659;

2,8 –­ (-0,292683)*(-3,5)= 1,7756098;

3,6 – (-0,292683)*2,7=4,3902439;

2,4 – (-0,292683)*(-8,2)=0;

1,2 ­– (-0,292683)*0,9=1,4634146;

11 – (-0,292683)*(-6,1)= 9,2146341.

При i= 3,4 продолжаем вычисления аналогичным образом. Результаты записываем в разделе II. При этом не выписываем главную строку.

6) Контроль: находим суммы и сравниваем с , например, 9,2146341= и т.д.

7) Выбираем главный элемент, выделяем его. В нашем случае это будет = -6,8963415.

8) Делим элементы столбца a_{i 2} на . Получаем числа:

= -0,257471;

-0,523431.

9) Вычисляем коэффициенты . Для этого из каждой i –ой (i= 2,3) строки вычитаем главную строку, умноженную на соответствующий элемент . Так, при i= 2 будем иметь:

1,5853659–(-0,257471)*5,5121951=

=3,0045977;

1,7756098 – (-0,257471)*(-6,8963415)=0;

4,3902439 – (-0,257471)*5,4914634=

=5,8041379;

1,4634146 – (-0,257471)*10,2304878=

=4,0974713;

9,2146341 – (-0,257471)* 14,3378049=

=12,9062069.

При i= 3 вычисления ведутся аналогично. Результаты записываем в разделе III, оставляя свободными уже столбцы a_{i 2} и a_{i 4}.

10) Контроль: сумма (i= 2,3) должна равняться ; это условие выполняется.

11) Выбираем главный элемент, выделяем его. В нашем случае это будет =5,8041379.

12) Находим -0,30697. Записываем в столбец m_i раздела III.

13) Вычисляем коэффициенты . Для этого из третьей строки вычитаем главную строку, умноженную на соответствующий элемент . Получаем:

3,2511052 – (-0,30697)*3,2511052=

=4,1734273;

-1,7816976 – (-0,30697)*5,8041379=0;

19,0695844 – (-0,30697)*4,0974713=

=20,3273862;

Таблица 5

	i	mi	ai 1	ai 2	ai 3	ai 4	ai 5	= ai 6	
I				-3,5	2,7	-8,2	0,9	-6,1
	-0,29268		2,8	3,6	2,4	1,2
	0,31707		2,5	-3,8	-2,6		11,1
	-0,25609		-6	4,8	2,1		15,9
II		-0,25741	1,585365	1,775609	4,3902439		1,46341	9,214634	9,21463
	-0,52343	0,365853	3,609756	-4,656097		13,7146	13,03414	13,0341
		5,512195	-6,89634	5,491463		10,2304	14,33780	14,3378
III			3,004597		5,804137		4,09747	12,90620	12,9062
	-0,30697	3,251105		-1,781697		19,0695	20,53899	20,5389
IV			4,17342				20,3273	24,50081	24,5008
V			4,87066				x1
			0,964032			x2
				-1,815417		x3
					0,06897	x4

20,5389920 – (-0,30697)* 2,9062069=

=24,5008135.

14) Контроль: .

15) Выписываем главные строки каждого раздела. Получим систему, эквивалентную данной системе:

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

16) Результаты вычислений при реализации обратного хода записываем в разделе V: x₁=20,3273862/4,1734273= 4,8706698,

x₃=(4,0974713 – 3,0045977*4,8706698)/ 5,8041379= -1,8154172,

x₂=(10,2304878 – 5,5121951*4,8706698 – 5,4914634*(-1,8154172))/

/ (-6,8963415)= 0,9640325,

x₄=(0,9 – 2*4,8706698+3,5*0,9640325 – 2,7*(-1,8154172))/(-8,2)=0,0689755.