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

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

2. СЛАУ n-го порядка

n
aij x j
j 1
bi ; i 1, n
В векторной форме:
a11 a12 a1n
a a a
21 22
2n
A
a a a
nn
n1 n 2
a11 x1 a12 x2 ... a1n xn b1
a x a x ... a x b
21 1 22 2
2n n
2
a n1 x1 an 2 x2 ... ann xn bn
Ax b
x1
x
x 2
x
n
b1
b
b 2
b
n
2

3.

Определитель (детерминант) матрицы А
n-го порядка:
a11 a12 a1n
a21 a22 a2 n
| A | D det A
( 1) k a1 a2 an
an1 an 2 ann
Здесь индексы , , ..., пробегают все
возможные n! перестановок номеров 1,
2, ..., n; k – число инверсий в данной
перестановке.
3

4. Метод исключения Гаусса

4

5.

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

6.

Получим новую систему, в которой первое
уравнение осталось неизменным, а остальные
больше не содержат член с х1, т.е. исключили
все коэффициенты первого столбца матрицы,
лежащие ниже главной диагонали:
a11 x1 a12 x 2 ... a1n x n b1
( 2)
( 2)
( 2)
0
x
a
x
...
a
x
b
1 22 2
2n n
2
0 x a ( 2) x ... a ( 2) x b ( 2)
nn n
n
1 n2 2
A (1)
a11 a12 a1n
( 2)
( 2)
0 a 22 a 2 n
( 2)
0 a n( 22) a nn
6

7.

При
помощи
второго
уравнения
исключаются коэффициенты при х2 из
третьего, четвертого и последующих
уравнений. Продолжая этот процесс,
можно исключить из матрицы все
коэффициенты, лежащие ниже главной
диагонали.
Исключение
неизвестных
повторяется до тех пор, пока в левой части
последнего n-го уравнения не останется
одно неизвестное хn
( n)
( n)
ann xn bn
7

8.

На
каждом
шаге
новые
значения
коэффициентов определяются через значения
на предыдущем шаге согласно
( k 1)
aml
(k )
(k )
( k ) a mk
aml akl ( k )
akk
bm( k 1) bm( k ) bk( k )
(k )
amk
(k )
akk
k 1, n 1; l k , n
где m – номер уравнения, из которого
исключается xk; k – номер неизвестного,
которое исключается из оставшихся (n–k)
уравнений (номер столбца, из которого
исключаются элементы); l – номер столбца
исходной матрицы.
8

9.

Обратный ход метода Гаусса состоит в
последовательном вычислении xn, xn–1, ...,
x1 по алгоритму
n
1
(k )
(k )
xk ( k ) bk aki xi , k n,1
akk
i k 1
Во время счета необходимо следить, чтобы
(k )
диагональный элемент akk 0
В противном случае прибегают к
перестановке строк матрицы и продолжают
расчет.
9

10.

Если элемент на главной диагонали мал, то
эта строка умножается на большие числа,
что приводит к значительным ошибкам
округления при вычитаниях. Чтобы
избежать этого, каждый цикл всегда
начинают с перестановки строк. Среди
элементов столбца находят главный, т. е.
наибольший по модулю в k-м столбце, и
перестановкой строк переводят его на
главную диагональ, после чего делают
исключения.
10

11. Метод прогонки

11

12.

Модификация метода Гаусса, применяемая
к
системам
с
матрицей
трехдиагонального
типа
(часто
встречаются при решении краевых задач
для
дифференциальных
уравнений
второго порядка). Каноническая форма:
aixi–1 + bixi + cixi+1 = di;
i= 1…n; a1 = cn = 0
12

13.

В развернутом виде:
b1x1 + c1x2
a2x1 + b2x2 + c2x3
a3x2 + b3x3 + c3x4
. . .
an–1xn–2 + bn–1xn–1 + cn–1xn
anxn–1 + bnxn
= d1;
= d2;
= d3;
= dn–1;
= dn .
При этом, как правило, все коэффициенты
bi 0.
13

14.

На
этапе прямого хода каждое
неизвестное xi выражается через xi+1
xi = Ai xi+1 + Bi для i = 1,2, ..., n–1,
посредством прогоночных коэффициентов
Ai и Bi, которые имеют следующий вид
ci
d i ai Bi 1
Ai ;
Bi
ei
ei
где еi = аi Аi–1 + bi (i=2,3, ..., n–1).
14

15.

Расчет
начинается
коэффициентов
c1
A1 ;
b1
с
вычисления
d1
B1
b1

16.

На этапе обратного хода из последнего
уравнения системы при i = n–1
d n an Bn 1
xn
bn an An 1
Далее
посредством
прогоночных
коэффициентов
последовательно
вычисляем xn–1, xn–2, ..., x1.
При условии | bi | | ai | + | ci |, деление
на «0» исключается, и система имеет
единственное решение.
16

17. Задание

1. Решить СЛАУ методом исключения
Гаусса. Привести результат решения, а
также вид матрицы системы и вектора
правой части после завершения
прямого хода метода.
2. Решить СЛАУ методом прогонки и
привести результат решения.

18. Кому какая система?

Для Гаусса

19. Для прогонки