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

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

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

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 – количество уравнений в системе и количество неизвестных (порядок системы)

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

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 a in
a n1 a n 2 a nj a nn
X x1 x 2 x j x n
B
bi
bn

4. При решении СЛАУ возможно возникновение 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

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

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

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

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

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

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

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

Является прямым методом.
Исходные данные:
1. А
2. В

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

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

10. Метод Гаусса для 3 уравнений с 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:
b1 a12 x 2 a13 x3
x1
a11
a11
a11
2. х1 подставляется во все оставшиеся уравнения системы.

11.

Получим следующее:
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 21
b' 2 b2 b1
a11
a31
b'3 b3 b1
a11

12.

Новая система:
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 подставляется во все оставшиеся
уравнения системы.

13.

Получим следующее:
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
a '32
b ' ' 3 b ' 3 b ' 2
a ' 22
Новая система в верхнетреугольном виде:
a11 x1 a12 x 2 a13 x3 b1
a ' 22 x 2 a ' 23 x3 b' 2
a ' '33 x3 b' '3

14.

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

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

НАЧАЛО
k=1, n-1
x(n)=b(n)/a(n,n)
i=1, n
i=k+1, n
i=n-1,1,-1
вывод
c=a(i,k)/a(k,k)
S=0
ввод
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

16.

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

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

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

18. Метод Зейделя для 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.

19.

Получим новую систему:
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).

20.

(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
a
33
5. Далее рассчитывается разность между значениями начальных
приближений и уточненными значениями неизвестных.
Если
x1(1) x1( 0 ) E
и
x 2(1) x 2( 0 ) E
и
x3(1) x3( 0 ) E
то считается, что значения х1(1), х2(1), х3(1)
являются решением данной системы. В
противном случае эти значения
принимаются за начальное приближение и
процесс повторяется.

21.

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

22.

НАЧАЛО
R=0
i=1, n
i=1, n
вывод
ввод
n, E
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

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

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

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

det A ≠ 0

25. Метод Крамера для системы 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
a11 a 22 a12 a 21
a 21 a 22
a11 b1
a 21 b2
a11 b2 b1 a 21
x2
a11 a12
a11 a 22 a12 a 21
a 21 a 22

26. Метод Крамера для системы 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

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

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

28.

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

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

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