Лекции Дудорова(Оптимизация.) / lection_dudarov / Лекция 5

9

Лекция 5

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

Уравнение вида , где a_j (j=1..n), b – постоянные значения, а x_j (j=1..n) – переменные, называется линейным.

Совокупность линейных уравнений образует систему линейных алгебраических уравнений (СЛАУ):

(1)

Данная система состоит из m уравнений и n неизвестных. Здесь a_ij – постоянные коэффициенты, b_i – свободные члены, i=1..m, j=1..n.

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

Система называется совместной, если существует хотя бы одно решение этой системы. В противном случае система называется несовместной.

Система называется неоднородной, если хотя бы один свободный член в ней не равен нулю. В противном случае система называется однородной.

Система называется нормальной, если число уравнений равно числу неизвестных. Если уравнений больше, чем переменных, система называется переопределённой (переобусловленной). Если уравнений меньше, чем переменных, система называется недоопределённой (недообусловленной).

Совместная система, имеющая одно решение, называется определённой. Если совместная система имеет множество решений, она называется неопределённой.

Для решения вопроса определённости СЛАУ используется определитель матрицы постоянных коэффициентов.

– система неопределённая (совместная, имеет множество решений).

– система несовместная (нет решений).

– система определённая (совместная, имеет одно решение, так как определитель не равен нулю).

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

Точные методы

(точное решение достигается за конечное число вычислений):

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

2. Метод Крамера;

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

4. Метод главных элементов;

5. Метод квадратных корней.

Итерационные методы

(приближённое решение получается с заданной точностью за некоторое число итераций):

1. Метод простых итераций;

2. Метод Гаусса-Зейделя;

3. Метод релаксации.

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

Метод обратной матрицы. Если обратная матрица найдена каким-либо итерационным способом, данный метод может быть отнесён к группе итерационных методов.

Матричная форма записи СЛАУ:

. (2)

Если определитель матрицы постоянных коэффициентов () не равен нулю, то существует обратная матрица . Умножим обе части системы (2) слева на обратную матрицу:

(3)

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

Задание 1. Решить систему уравнений методом обратной матрицы.

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

; ; ...; .

Задание 2. Решить систему уравнений методом Крамера.

;

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

Исходную систему уравнений (1) перепишем в виде:

(4)

Алгоритм решения СЛАУ методом Гаусса рассмотрим на примере системы трёх линейных алгебраических уравнений.

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

1.1. из всех строк, после первой, вычитается первая, умноженная на k_i; здесь , где в числителе – первый элемент строки, из которой вычитают, в знаменателе – элемент вычитаемой строки, находящийся на главной диагонали:

(5)

1.2. из всех строк, после второй, вычитается вторая, умноженная на k_i; здесь , где в числителе – второй элемент строки матрицы (5), из которой вычитают, в знаменателе – элемент вычитаемой строки, находящийся на главной диагонали матрицы (5):

(6)

1.3. для системы n уравнений данная процедура повторяется n–1 раз.

2. Полученная треугольная СЛАУ решается снизу вверх.

Для решения СЛАУ методом Гаусса необходимо выполнить следующие требования.

1. Диагональные элементы матрицы на любом этапе преобразования пункта 1 алгоритма не должны быть равны нулю.

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

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

Задание 3. Решить систему уравнений методом Гаусса, округляя на каждом этапе преобразований отношение k_i до второго десятичного знака. Оценить абсолютную и относительную ошибки каждого из найденных элементов вектора решений.

k₂=–0,67; k₃=0,67;

k₃=–1;

Таблица 1

Результаты исследования точности решения, полученного по методу Гаусса

Переменная	Корень по методу Гаусса	Истинное значение корня	Абсолютная погрешность	Относительная погрешность
x1	2,02	2,00	0,02	1,0
x2	1,06	1,00	0,06	6,0
x3	3,00	3,00	0,00	0,0

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

Сущность метода простых итераций заключается в преобразовании исходной СЛАУ (2) к итерационной форме (7) и нахождении последовательности приближений векторов значений переменных.

, (7)

где в матрице и векторе :

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

; (8а)

; (8б)

. (8в)

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

Алгоритм решения СЛАУ методом простых итераций следующий.

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

2. Задаётся начальное приближение элементов вектора переменных и точность решения системы.

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

(9)

4. Цикл на этапе 3 повторяется до выполнения одного из следующих условий:

• превышено максимально допустимое число итераций;

• 

• 

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

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

Метод Гаусса-Зейделя представляет собой модификацию метода простых итераций. Его отличительной особенностью является та, что при расчёте элементов вектора решения системы уравнений на каждом шаге итерации, кроме найденных на предыдущем шаге, используются также значения переменных, уже найденные на текущем шаге итерации. Таким образом, система (9) имеет вид:

(10)

Благодаря такому подходу скорость решения СЛАУ увеличивается.