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

1. Численное решение систем линейных алгебраических уравнений С Л А У

2.

3. Общий вид СЛАУ

a11 x1 a12 x 2 a1 j x j a1n x n b1
a 21 x1 a 22 x 2 a 2 j x j a 2 n x n b2
ai1 x1 ai 2 x 2 aij x j ain x n bi
a n1 x1 a n 2 x 2 a nj x j a nn x n bn
где a – коэффициенты системы,
b – свободные члены,
х – неизвестные
n – количество уравнений в системе и количество неизвестных (порядок системы)

4. Запись СЛАУ в матричной форме

A X B
b1
a11 a12 a1 j a1n
b2
a 21 a 22 a 2 j a 2 n
A
ai1 ai 2 aij ain
a n1 a n 2 a nj a nn
X x1 x 2 x j xn
B
bi
bn

5. При решении СЛАУ возможно возникновение 3 случаев:

1. Пример:
2. Пример:
3. Пример:
5 x1 2 x 2 31
3 x1 x 2 1
x1 3
x2 8
5 x1 2 x 2 31
10 x1 4 x 2 62
5 x1 2 x 2 31
10 x1 4 x 2 28

6. 2 класса методов решения СЛАУ:

1. Прямые методы.
2. Итерационные методы.

7. Прямые методы

Достоинство: устойчивость методов.
Недостаток: точность решения зависит от
особенностей метода и от количества
уравнений.

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

Достоинство: точность решения задается
пользователем.
Недостаток: методы являются неустойчивыми.

9. Метод Гаусса (метод последовательного исключения неизвестных)

Метод Гаусса
(метод последовательного
Является прямым методом.
исключения
неизвестных)
Исходные данные:
1.
А
2.
В

10. Алгоритм метода Гаусса:

Ввод исходных данных.
2. Прямой ход.
3. Обратный ход.
4. Вывод результатов.
1.

11. Метод Гаусса для 3 уравнений с 3-мя неизвестными (система 3-го порядка)

1. х1:
a11 x1 a12 x 2 a13 x3 b1
a 21 x1 a 22 x 2 a 23 x3 b2
a x a x a x b
32 2
33 3
3
31 1
b1 a12 x 2 a13 x3
x1
a11
a11
a11
2. х1 подставляется во все оставшиеся уравнения системы.

12.

Получим следующее:
a
a
a
a 22 a12 21 x 2 a 23 a13 21 x3 b2 b1 21
a11
a11
a11
a
a
a
a32 a12 31 x 2 a33 a13 31 x3 b3 b1 31
a11
a11
a11
3. Новые обозначения:
a31
a11
a 21
a ' 22 a 22 a12
a11
a '32 a32 a12
a
a ' 23 a 23 a13 21
a11
a31
a '33 a33 a13
a11
a
b' 2 b2 b1 21
a11
a31
b'3 b3 b1
a11

13.

Новая система:
a11 x1 a12 x 2 a13 x3 b1
a' 22 x 2 a ' 23 x3 b' 2
a'32 x 2 a'33 x3 b'3
4. х2:
b' 2 a ' 23 x3
x2
a ' 22
a ' 22
5. х2 подставляется во все оставшиеся
уравнения системы.

14.

Получим следующее:
a '32
a'
a'33 a ' 23
x3 b'3 b' 2 32
a ' 22
a ' 22
6. Новые обозначения:
a'32
a' '33 a'33 a' 23
a' 22
b' '3 b'3 b' 2
a'32
a' 22
Новая система в верхнетреугольном виде:
a11 x1 a12 x 2 a13 x3 b1
a' 22 x 2 a' 23 x3 b' 2
a' '33 x3 b' '3

15.

7. Неизвестные вычисляются в обратном порядке (обратный
ход):
b' ' 3
x3
a ' '33
b' 2 a ' 23 x3
x2
a ' 22
b1 a12 x 2 a13 x3
x1
a11

16. Блок-схема метода Гаусса ввод исходных данных прямой ход обратный ход вывод результатов

НАЧАЛО
k=1, n-1
x(n)=b(n)/a(n,n)
i=k+1, n
i=n-1,1,-1
c=a(i,k)/a(k,k)
S=0
i=1, n
ввод
n
вывод
x(i)
i=1, n
КОНЕЦ
j=1, n
a(i,k)=0
j=i+1, n
j=k+1, n
S= S+a(i,j)* x(j)
ввод
a(i, j)
ввод
b(i)
a(i,j)= a(i,j)- a(k,j)*c
x(i)= (b(i)-S)/a(i,i)
b(i)= b(i)- b(k)*c

17.

ЗАМЕЧАНИЕ
В случае единственности решения СЛАУ методом
Гаусса всегда находится необходимое
решение.
Необходимо выполнения условия:
a ii 0

18. Метод Зейделя (метод простых итераций)

Является итерационным методом.
Исходные данные:
1.
А
2.
В
3.
4.
Х(0)
Е

19. Метод Зейделя для 3 уравнений с 3-мя неизвестными

a11 x1 a12 x 2 a13 x3 b1
a 21 x1 a 22 x 2 a 23 x3 b2
a x a x a x b
32 2
33 3
3
31 1
1.
Из 1-го уравнения выражаем неизвестное х1,
из
2-го уравнения - х2, из 3-го - х3.

20.

Получим новую систему:
1
b1 a12 x2 a13 x3
x1
a11
1
b2 a 21 x1 a 23 x3
x2
a 22
1
b3 a31 x1 a32 x2
x3
a33
2. В правую часть 1-го уравнения подставляем начальные
приближения неизвестных х2(0) и х3(0). Получаем уточненное
значение неизвестного х1(1).
3. В правую часть 2-го уравнения подставляем начальное
приближение неизвестного х3(0) и уточненное значение х1(1).
Получаем уточненное значение неизвестного х2(1).
4. В правую часть 3-го уравнения подставляем уточненные
значения неизвестных х1(1) и х2(1). Получаем уточненное
значение неизвестного х3(1).

21.

(1)
1
(0)
(0)
x
b
a
x
a
x
1
12 2
13 3
1
a11
(1)
1
(1)
(0)
x
b
a
x
a
x
2
2
21 1
23 3
a 22
(1)
1
(1)
(1)
x
b
a
x
a
x
3
3
31 1
32 2
a33
5. Далее рассчитывается разность между значениями
начальных приближений и уточненными значениями
неизвестных.
(1)
(0)
x1 x1
E
и
Если
то считается, что значения х1(1), х2(1), х3(1)
(0)
являются
данной системы. В
x 2(1) xрешением
E
2
противном случае эти значения
принимаются
за начальное приближение и
и
процесс
повторяется.
(1)
(0)
x3 x3
E

22.

ЗАМЕЧАНИЕ
Метод Зейделя является итерационным, итерации
сходятся не всегда.
Итерации всегда сходятся при выполнении
следующего условия:
aii aij
i j
условие преобладания диагональных
коэффициентов.

23.

НАЧАЛО
R=0
i=1, n
ввод
n, E
вывод
i=1, n
x(i)
i=1, n
S=0
КОНЕЦ
j=1, n
j=1, n
ввод
a(i, j)
не
т
i≠j
да
ввод
b(i), x(i)
S=S + a(i,j)*x(j)
W= (b(i) – S)/a(i, i)
Блоксхема
метода
Зейделя
d = | W - x(i) |
R<d
да
не
т
x(i) = W
да
R>E
не
т
R=d

24. Метод Крамера для решения СЛАУ 2-го и 3-го порядка

Прямой метод. Метод линейной алгебры.
Исходные данные:
1.
А
2.
В

25. Условие существования единственного решения СЛАУ

det A ≠ 0

26. Метод Крамера для системы 2-го порядка

b1 a12
a11 x1 a12 x 2 b1
a 21 x1 a 22 x 2 b2
b2 a 22
b1 a 22 a12 b2
x1
a11 a12
a11a 22 a12 a 21
a 21 a 22
a11 b1
a 21 b2
a11b2 b1 a 21
x2
a11 a12
a11a 22 a12 a 21
a 21 a 22

27. Метод Крамера для системы 3-го порядка

a11 x1 a12 x 2 a13 x3 b1
a 21 x1 a 22 x 2 a 23 x3 b2
a x a x a x b
32 2
33 3
3
31 1
x1
b1 a12 a13
a11 b1 a13
a11 a12 b1
b2 a 22 a 23
a 21 b2 a 23
a 21 a 22 b2
b3 a32 a33
a31 b3 a33
a31 a32 b3
a11 a12 a13
x2
a11 a12 a13
x3
a11 a12 a13
a 21 a 22 a 23
a 21 a 22 a 23
a 21 a 22 a 23
a31 a32 a33
a31 a32 a33
a31 a32 a33

28. Окончательные формулы:

b1 a 22 a33 b1 a 23 a32 b2 a12 a33 b2 a13 a32 b3 a12 a 23 b3 a13 a 22
x1
a11a 22 a33 a11a 23 a32 a 21 a12 a33 a 21a13 a32 a31a12 a 23 a31a13 a 22
a11b2 a33 a11 a 23b3 a 21b1 a33 a 21a13b3 a31b1 a 23 a31 a13b2
x2
a11a 22 a33 a11a 23 a32 a 21a12 a33 a 21a13 a32 a31 a12 a 23 a31a13 a 22
a11a 22 b3 a11b2 a32 a 21a12 b3 a 21b1 a32 a31a12 b2 a31b1 a 22
x3
a11a 22 a33 a11a 23 a32 a 21a12 a33 a 21a13 a32 a31 a12 a 23 a31a13 a 22
Для систем более высоких порядков
метод Крамера практически не
применяется

29.

Реализация метода Крамера
в электронных таблицах
Microsoft Excell
Функция
МОПРЕД(матрица)

30. Функция МОПРЕД

31. Пример расчета определителя