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

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
a11 a12 a1 j a1n
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 x2 x j xn
b1
b2
B
bi
bn

4.

При решении СЛАУ возможно
возникновение 3 случаев:
1. Пример:
2. Пример:
3. Пример:
5 x1 2 x2 31
3x1 x2 1
x1 3
x2 8
5 x1 2 x2 31
10 x1 4 x2 62
5 x1 2 x2 31
10 x1 4 x2 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 x2 a13 x3
x1
a11
a11
a11
2. х1 подставляется во все оставшиеся уравнения системы.

11.

Получим следующее:
a
a
a
a 22 a12 21 x2 a 23 a13 21 x3 b2 b1 21
a11
a11
a11
a
a
a
a32 a12 31 x2 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 21
a ' 23 a 23 a13
a11
a31
a '33 a33 a13
a11
a
b' 2 b2 b1 21
a11
b'3 b3 b1
a31
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'
a'
a'33 a' 23 32 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

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=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

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
a33
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
ввод
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

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 a12b2
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

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
a11a 22 a33 a11a 23 a32 a 21a12 a33 a 21a13 a32 a31a12 a 23 a31a13 a 22
a11b2 a33 a11a 23b3 a 21b1 a33 a 21a13b3 a31b1 a 23 a31a13b2
x2
a11a 22 a33 a11a 23 a32 a 21a12 a33 a 21a13 a32 a31a12 a 23 a31a13 a 22
a11a 22b3 a11b2 a32 a 21a12b3 a 21b1 a32 a31a12b2 a31b1 a 22
x3
a11a 22 a33 a11a 23 a32 a 21a12 a33 a 21a13 a32 a31a12 a 23 a31a13 a 22
Для систем более высоких порядков метод
Крамера практически не применяется

28.

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

29.

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

30.

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