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

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

(2.1)

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

Метод Гаусса.

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

Рассмотрим систему из трех уравнений с тремя неизвестными:

(2.2)

Система уравнений (2.2) приводится к эквивалентной системе с треугольной матрицей:

(2.3)

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

Процесс приведения системы (2.2) к системе (2.3) называется прямым ходом, а нахождение неизвестных , , из системы (2.3) называется обратным ходом.

Прямой ход исключения: Исключаем из уравнений (II) и (III) системы (2.2). Для этого умножаем уравнение (I) на и складываем со вторым, затем умножаем на и складываем с третьим.

В результате получаем следующую систему:

(2.4)

Из полученной системы (2.4) исключаем . Для этого умножая новое уравнение на и складываем со вторым уравнением, получим уравнение:

(2.5)

Взяв из каждой системы (2.2), (2.4) и (2.5) первые уравнения, получим систему уравнений с треугольной матрицей.

Обратный ход: Из уравнения (III²) находим . Из уравнения (II¢) находим . Из уравнения (I) находим . Коэффициенты , называются ведущими элементами 1-го и 2-го шагов исключения неизвестных. Они должны быть отличны от нуля. Если они равны нулю, то, меняя местами строки, необходимо на их место вывести ненулевые элементы.

Аналогичным путем методом Гаусса решаются системы уравнений с неизвестными.

Пример 2.1. Решить систему уравнений методом Гаусса:

Решение: Удалить члены с из 2-го и 3-го уравнений можно, вычитая из 2-й строки 1-ую, умноженную на , а из 3-й - первую, умноженную на :

2-я строка делится на :

2-я строка умножается на и вычитается из 3-й:

3-я строка делится на :

Процедура обратного хода дает исходное решение:

; ;

Метод обратной матрицы.

Систему (2.1) можно представить в матричном виде как

,

где

Решение можно выразить, используя умножение на матрицу , обратную к :

Пример 2.2. Решить систему уравнений методом обратной матрицы с помощью программы Excel:

Порядок решения.

1) Ввести матрицу и вектор в рабочий лист Excel (рис. 2.1).

2) Выделить ячейки для хранения обратной матрицы ; например, ячейки A8:D11.

3) Вызвать мастер функций, в категории «Математические» выбрать функцию вычисления обратной матрицы МОБР. В диалоговом окне аргументов функции заполнить поле ввода «Массив» - указать диапазон ячеек матрицы - в нашем случае A2:D5. Нажать кнопку OK. В первой ячейке выделенного под обратную матрицу диапазона (A8) появится число.

4) Чтобы получить всю обратную матрицу, нажать клавишу F2 для перехода в режим редактирования, а затем одновременно клавиши Ctrl+Shift+Enter. В ячейках A8:D11 появятся значения обратной матрицы .

5) Выделить ячейки для хранения вектора-столбца ; например, ячейки F8:F11.

6) Вызвать мастер функций, в категории «Математические» выбрать функцию матричного умножения МУМНОЖ. В диалоговом окне аргументов функции в поле ввода «Массив1» указать диапазон ячеек матрицы - в нашем случае A8:D11, в поле ввода «Массив2» указать диапазон ячеек вектора - в нашем случае F2:F5. Нажать кнопку OK. В первой ячейке выделенного под результат диапазона (F8) появится число.

7) Чтобы получить весь вектор , нажать клавишу F2 для перехода в режим редактирования, а затем одновременно клавиши Ctrl+Shift+Enter. В ячейках F8:F11 появятся значения решения системы уравнений:

; ; ;

	A	B	C	D	E	F	G
	A					B
		-2		-4
			-3			-7
		-1
		-5		-4		-5
	1/A					X
	0,098005	-0,09214	0,071009	-0,0534	X1=	1,767019
	0,201878	-0,85446	0,403756	-0,3615	X2=	9,807512
	0,019366	-0,31162	0,163732	-0,04049	X3=	2,702465
	-0,02758	0,049883	0,069836	-0,00293	X4=	-0,48533
Рис. 2.1. Решение системы линейных уравнений методом обратной матрицы с помощью программы Excel.

Метод прогонки.

Применяется для решения систем уравнений с трехдиагональной (ленточной) матрицей. Такая система уравнений записывается в виде:

, (2.6)

.

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

, (2.7)

Уменьшим в формуле (2.7) индекс на единицу: и подставим в (2.6):

Выразим :

(2.8)

Сравнивая (2.7) и (2.8), получим:

(2.9)

Поскольку , то

, (2.10)

Теперь по формулам (2.9) и (2.10) можно вычислить прогоночные коэффициенты и (). Это прямой ход прогонки. Зная прогоночные коэффициенты, по формулам (2.7), можно вычислить все () (обратный ход прогонки). Поскольку , то и . Далее вычисляем , ,..., , .

 

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

 

Решение. Коэффициенты записываем в виде таблицы 2.1.

 

				Таблица 2.1
	-2			-1
	0,1		-1	-5
	-1

Прямой ход прогонки. По формулам (2.9) и (2.10) определяем прогоночные коэффициенты и ().

, т.к.

Обратный ход прогонки. По формулам (2.7) вычисляем все (). Поскольку , то .

Далее вычисляем:

Вычисляем невязки ()

Алгоритм метода прогонки:

1. Ввести число уравнений

2. Ввести ().

3. Вычислить и ; ().

4. Вычислить ().

5. Вычислить невязки ().

6. Напечатать , ().

 

На рис. 2.2 приведена программа решения методом прогонки.

CLC

INPUT N

DIM A(N),B(N),C(N),D(N),U(N),V(N),X(N+1),R(N)

FOR I=1 TO N

INPUT A(I),B(I),C(I),D(I)

U(I)=-C(I)/(A(I)*U(I-1)+B(I))

V(I)=(D(I)-A(I)*V(I-1))/(A(I)*U(I-1)+B(I))

NEXT I

FOR I=N TO 1 STEP -1

X(I)=U(I)*X(I+1)+V(I)

NEXT I

FOR I=1 TO N

R(I)=D(I)-A(I)*X(I-1)-B(I)*X(I)-C(I)*X(I+1)

PRINT ²X²;I; ²=²; X(I), ²R²; I; ²=²; R(I)

NEXT I

Рис.2.2. Программа решения системы линейных алгебраических уравнений методом прогонки на языке QUICK BASIC.

 

Пример 2.4. Решить систему уравнений из примера (2.3) методом прогонки с помощью программы Excel.

Порядок решения.

1) Ввести в ячейки A1:G1 заголовки столбцов (рис. 2.3).

2) В ячейки A3:D6 – коэффициенты . Строки выше и ниже данных оставить пустыми.

3) В ячейку E3 – формулу =-C3/(A3*E2+B3)

4) В ячейку F3 – формулу =(D3-A3*F2)/(A3*E2+B3)

5) В ячейку G3 – формулу =G4*E3+F3

6) Выделить ячейки E3:G3 и скопировать формулы в соседние ячейки E4:G4 … E6:G6 при помощи маркера заполнения.

7) В ячейках G3:G6 появятся значения решения системы уравнений.

 

	A	B	C	D	E	F	G	H
	a	b	c	d	u	v	x
					-0,1	0,5	0,5
	-2			-1	-0,1087
	0,1		-1	-5	0,250681	-1,25341
	-1
Рис. 2.3. Решение системы линейных алгебраических уравнений методом прогонки с помощью программы Excel.