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

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

Краснодарский университет МВД России
a a a ... a1n
22
M
M (( X
X )) (( M
M (( X
X ))
))
a a a ... a 2 n
по дисциплине «Численные методы
специальность 10.05.05 Безопасность
информационных технологий в
A
a 31«Технологии
a 32 защиты
a 33 информации
... a 3 n в
bbправоохранительной сфере специализация
правоохранительной сфере»
... ... ... ... ...
Тема
an№3
n2
an 3линейных
... ann
Численные методы решения
1 aсистем
12
13
Кафедра информатики11и математики
22
Учебно-наглядное
21 пособие
22
23
f
(
x
)
dx
f
(
x
)
dx
aa
алгебраических уравнений
Обсуждена и одобрена
на заседании кафедры
информатики и математики
Протокол № 20
от «01» июня 2022 г.
Лекция 2
Подготовил:
Заместитель начальника кафедры
канд. физико-математических наук
полковник полиции Е.В. Михайленко
Краснодар
2022

2.

Цель лекции: рассмотреть основные понятия систем
линейных алгебраических уравнений, изучить матричный
метод, метод Крамера и метод Гаусса решения таких
систем, рассмотреть применение метода Гаусса для
нахождения обратной матрицы, ознакомиться с понятиями
и методами решения однородных систем алгебраических
уравнений, фундаментальной системой решений.
Материально-техническое
видеопроектор, экран.
обеспечение:
компьютер,
Учебно-методическое обеспечение: учебно-методический
материал в электронном виде, программный комплекс
«Системы линейных уравнений».

3.

Основные вопросы
1. Метод итераций
2. Метод Зейделя

4. 1. Метод итераций

Простейшим итерационным методом решения СЛАУ является метод
простой итерации.
Пусть дана система n линейных уравнений с n неизвестными.
a11 x1 a12 x2 a13 x3 ... a1n xn b1
a x a x a x ... a x b
23 3
2n n
2
21 1 22 2
a31 x1 a32 x2 a33 x3 ... a3n xn b3 (1)
an1 x1 an 2 x2 an 3 x3 ... ann xn bn
Для того чтобы применить метод простой итерации, необходимо
систему уравнений привести к виду: х=Вх+с.
(2)

5.

Продолжая этот процесс дальше, получим последовательность приближений,
причем приближение строится следующим образом:
(3)
Последняя система (3) представляет собой расчетные формулы
метода простой итерации.

6.

Полученную систему (3) можно использовать, как итерационные
формулы, учитывая, что справа в равенствах стоят значения
переменных xi, полученные на предыдущем n-1 шаге вычислений, а
слева - новые значения на n щаге.
Сходимость метода простой итерации. Известно следующее
достаточное условие сходимости метода простой итерации. Если
элементы матрицы удовлетворяют условию:
то итерационная последовательность сходится к точному решению.
На практике для обеспечения сходимости итерационных методов
необходимо, чтобы значения диагональных элементов матрицы
СЛАУ были преобладающими по абсолютной величине по
сравнению с другими элементами.

7.

Критерий окончания.
Если требуется найти решение с точностью ε.
Зададим начальные приближения
и вычислим правую часть каждого уравнения системы (3), получим
новые приближения
Таким образом организуется итерационный процесс, который
заканчивается по условию: вычисления ведутся до тех пор, пока все
величины

8.

Пример 1.
Решить систему уравнений методом простой итерации с точностью ε=0,001
Заметим, что метод простой итерации сходится, так как выполняется условие
преобладания диагональных элементов:
Приведем систему к виду:

9.

В качестве начального приближения возьмем элементы столбца свободных
членов:
Вычисления будем вести до тех пор, пока все величины не станут
меньше
Последовательно вычисляем при k=1:
При k=2:

10.

11.

2. Метод Зейделя
Пусть дана система n линейных уравнений с n неизвестными.
a11 x1 a12 x2 a13 x3 ... a1n xn b1
a x a x a x ... a x b
23 3
2n n
2
21 1 22 2
a31 x1 a32 x2 a33 x3 ... a3n xn b3
an1 x1 an 2 x2 an 3 x3 ... ann xn bn
(1)
Разделим обе части каждого уравнения на диагональные элементы
x1 a12 / a11 x2 a13 / a11 x3 ... a1n / a11 xn b1 / a11
a / a x x a / a x ... a / a x b / a
23
22 3
2n
22 n
2
22
21 22 1 2
a31 / a33 x1 a32 / a33 x2 x3 ... a3n / a33 xn b3 / a33
an1 / ann x1 an 2 / ann x2 an 3 / ann x3 ... xn bn / ann

12.

Выразим из этой системы в каждом уравнении по одной неизвестной
x1 b1 / a11 ( a12 / a11 x2 a13 / a11 x3 ... a1n / a11 xn )
x2 b2 / a22 ( a21 / a22 x1 a23 / a22 x3 ... a2 n / a22 xn )
( 2)
x3 b3 / a33 ( a31 / a33 x1 a32 / a33 x2 a34 / a33 x4 ... a3n / a33 xn )
xn bn / ann ( an1 / ann x1 an 2 / ann x2 an 3 / ann x3 ... an ,n 1 / ann xn 1 )
Таким образом, систему уравнений можно записать в матричном виде
X B A X
0
b1 / a11
x1
a21 / a22
b2 / a22
x2
b / a ; A a / a
B
31
33
X x3 ;
3
33
...
a / a
b / a
x
n1 nn
n nn
n
,
(3)
a12 / a11
a13 / a11
0
a23 / a22
a32 / a33
0
...
...
an 2 / ann
an 3 / ann
где
... a1,n / a11
... a2 n / a22
... a3n / a33 .
...
...
...
0

13.

Используя соответствующую полученной системе рекуррентную
n
формулу
(k )
xi bi aij x (j k 1) ( 4)
j 1
на каждом k-том шаге получим новое значение i-той переменной.
Основная идея метода Зейделя состоит в том, что новые
полученные значения xi используются сразу же по мере получения для
расчета следующих переменных xi+1, xi+2, ..., xi+k.
Последовательно выполняя вычисления по строкам, получим:
x (2k ) a13
x (3 k ) ... a1n x (nk ) )
x 1( k 1) b1 ( a12
( k 1)
x 1( k 1) a23
x (3 k ) ... a2 n xn )
x 2 b2 ( a21
( k 1)
( k 1)
( k 1)
(k )
(k )
x
b
(
a
x
a
x
a
x
...
a
x
(5)
3
3
31 1
32 2
34 4
3n n )
xn bn ( an 1 x ( k 1) an 2 x ( k 1) an 3 x ( k 1) ... an ,n 1 x ( k 1) )
1
2
3
n 1

14.

Задания для самоподготовки