742.50K

Категория: $Математика$ Математика

Похожие презентации:

Вычислительная математика. Лекция 5. Системы линейных алгебраических уравнений

Системы линейных алгебраических уравнений

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

Системы линейных алгебраических уравнений

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

Системы линейных алгебраических уравнений (лекция 1)

Системы линейных алгебраических уравнений

Решение систем линейных алгебраических уравнений

Системы линейных уравнений

Системы линейных алгебраических уравнений

1.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Лекция 5
СИСТЕМЫ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ
УРАВНЕНИЙ
С Л А У

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Дана система линейных алгебраических уравнений
Ax b , где
A - вещественная квадратная матрица порядка n,
b (b1 , b2 ,..., bn )T - заданный вектор,
x ( x1 , x2 ,..., xn )T - искомый вектор.
Предполагается, что det A 0. Тогда для каждого
вектора b система имеет единственное решение.

3.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Вид системы в развернутом виде:
a11 x1 a12 x2 ...a1n x b1
a21 x1 a22 x2 ...a2 n x b2
.......................................
a1n x1 a2 n xn ...ann x bn .

4.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Если задана некоторая произвольная система
уравнений, то без предварительного исследования
нельзя сказать, имеет ли она какое-либо решение
и, в случае, если решение существует, является
ли оно единственным.На этот вопрос существует
три ответа.
1. Решение системы уравнений существует и
является единственным. Например,
2 x y 4
x y 1.

5.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Решение этой системы x 1 и y 2 .
Геометрическое представление системы двух линейных
уравнений, имеющей единственное решение. Координаты
точки пересечения представляют собой искомое решение.

6.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Система уравнений вообще не имеет решения.
4 x 6 y 10
2 x 3 y 6.
Две прямые параллельны,
они нигде не пересекаются,
и система не имеет решения.
Геометрическое представление системы двух линейных
уравнений, не имеющей решения.

7.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
3. Система уравнений имеет бесконечное
множество решений
Два уравнения описывают
одну и ту же прямую линию.
Любая точка, лежащая на
этой линии, является
решением этой системы.
Геометрическое представление системы двух линейных
уравнений, имеющей бесконечное множество решений

8.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Две последние
системы уравнений называются
вырожденными. С точки зрения обычной математики
линейных уравнений всегда является или вырожденной
или невырожденной. С точки же зрения вычислений могут
существовать почти вырожденные системы, при решении
которых получаются недостоверные значения неизвестных.
Рассмотрим систему уравнений:
5 x 7 y 12
7 x 10 y 17.

9.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Эта система имеет единственное решение x 1, y 1.
Теперь рассмотрим пару значений x 2.415, y 0.
При подстановке этих значений в исходные уравнения
получаем
5 x 7 y 12.075
7 x 10 y 16.905.
После округления до двух
значащих цифр правые
части равенств совпадают
с правыми частями исходных уравнений. Дело в том, что
две прямые линии, описываемые двумя уравнениями этой
системы, почти параллельны.
Системы такого типа называются плохо обусловленными.

10.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Методы решения СЛАУ подразделяются на
• прямые (конечные, точные);
• итерационные (бесконечные, приближенные).
Прямые:
Итерационные:
Гаусса
Простых итераций
LU-разложений
Зейделя
Жордано
Квадратного корня
Релаксаций

11.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
МЕТОД
ГАУССА
Метод основан на идее последовательного
исключения неизвестных. Введем n 1
множителей
a i1
mi
, i 2, 3,..., n
a11
и вычтем из каждого уравнения первое,
умноженное на mi

12.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Обозначая
a1ij aij mi a1 j , i 2, 3,..., n,
bi1 bi mi bi ,
j 2,3,...., n,
для всех уравнений, начиная со второго, получаем
a1i1 0, i 2, 3,..., n.
Преобразованная система запишется в виде:
a11 x1 a12 x2 ...a1n x b1
0
a x ...a
1
22 2
1
2n
x b
1
2
.......................................
0
a12 n xn ...a1nn x bn1 .

13.

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
5
Продолжая таким же образом на некотором k -м
этапе мы исключаем x k с помощью множителей
( k 1)
i
m
Тогда
( k 1)
ik
( k 1)
kk
a
a
(k )
ij
a
akk( k 1) 0.
, i k 1,..., n,
( k 1)
ij
a
( k 1) ( k 1)
i
kj
m
a
bi( k ) bi( k 1) mi( k 1)bk( k 1)
,
k 1, ..., n 1.
При k n 1 происходит исключение x n 1
из последнего уравнения.

14.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Окончательная треугольная система уравнений
записывается следующим образом:
a11 x1 a12 x2 ...a1n x b1
x2 ...a2 n x b2
a22
.......................................
a n 1nn x f n 1n .
Такая система уравнений называется треугольной.
Приведение матрицы к треугольной называется
прямым ходом.

15.

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
5
Треугольная система легко решается обратным
ходом по следующим формулам:
bn( n 1)
xn ( n 1) ,
ann
xj
(f
( j 1)
j
a
xn 1
( j 1)
jn
n
( j 1)
jj
b
x ... a
a
( n 2)
n 1
( n 2)
n 1,n n
( n 2)
n 1,n 1
a
a
( j 1)
j , j 1
x j 1 )
x
, ... ,
, j n 2, n 3,..., 1.
В результате получаем искомое решение.

16.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Вычисление определителя методом Гаусса
Для вычисления определителя матрицы
A
решаем систему Ax b и выполняем прямой
ход метода Гаусса:
det A a11 a
(1)
22
a
( 2)
33
... a
( n 1)
nn
.

17.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Метод
LU – р а з л о ж е н и й
Пусть A — данная матрица, а L и U - нижняя
(левая) и верхняя (правая) треугольные матрицы:
1 0
l21 1
L
... ...
ln1 ln 2
...
...
...
...
0
0
...
1
u11 u12
0 u
22
U
... ...
0
0
... u1n
... u2 n
... ...
... unn

18.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Справедливо следующее утверждение:
Если все главные миноры квадратной матрицы
A отличны от нуля, то существуют такие
нижняя L и верхняя U треугольные матрицы,
что A LU .
Если элементы диагонали одной из матриц L или U
фиксированы (ненулевые), то такое разложение
единственно.

19.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Перемножая нижнюю и верхнюю матрицы
приходим к матрице уравнений размерностью n*n :

20.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Элементы матриц L и U могут быть вычислены
с помощью следующих формул:
i 1
uij aij lik ukj
(i j ),
k 1
j 1
1
lij aij lik ukj (i j ).
k 1
u jj

21.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Запишем исходную систему Ax b так: LUx b .
T
Введем вспомогательный вектор y y1, y 2 ,..., y n
решение системы сводится к решению двух систем с
треугольными матрицами коэффициентов:
Ly b,
Ux y.
Запишем уравнение Ly b в развернутом виде:

22.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Все yi могут быть найдены по формуле:
i 1
yi bi lik yk , i 1, 2,..., n.
k 1
Развернем теперь векторно-матричное уравнение Ux y
u11 x1 u12 x2 ... u1n xn y1
u x ... u x y
22 2
2n n
2
.......... .......... .....
u nn xn y n
Значения неизвестных xi находятся в обратном порядке:
n
1
xi yi uik xk ,
uii
k i 1
i n, n 1,...,1

23.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Метод
Жордано
1. Выбирается первая колонка слева, в которой
есть хоть одно отличное от нуля значение.
2. Если самое верхнее число в этой колонке есть
нуль, то меняется вся первая строка матрицы с
другой строкой матрицы, где в этой колонке нет
нуля.
3. Все элементы первой строки делятся на
верхний элемент выбранной колонки.

24.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
4. Из оставшихся строк вычитается первая строка,
умноженная на первый элемент соответствующей
строки, с целью получить первым элементом
каждой строки (кроме первой) нуль.
5. Далее проводим такую же процедуру с матрицей,
получающейся из исходной матрицы после
вычёркивания первой строки и первого столбца.
6. После повторения этой процедуры n-1 раз
получаем верхнюю треугольную матрицу.

25.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
7. Вычитаем из предпоследней строки последнюю
строку, умноженную на соответствующий
коэффициент, с тем, чтобы в предпоследней
строке осталась только 1 на главной диагонали.
8. Повторяем предыдущий шаг для последующих
строк. В итоге получаем единичную матрицу и
решение на месте свободного вектора (с ним
необходимо проводить все те же преобразования).

26.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Пример.
Решить следующую систему уравнений:
2 x1 x2 x3 2
3 x1 x2 2 x3 3
x
x3 3
1
.
Прямой ход
Исключим переменную x1 из всех уравнений, за
исключением первого. Поменяем местами 1 и 3 уравнения
(порядок уравнений в системе не имеет значения).

27.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
x3 3
x1
3x1 x2 2 x3 3
2x x x 2
1 2 3
1 0 1
3 1 2
2 1 1
3
3
2
Из уравнения 2 вычитаем уравнение 1, умноженное на 3.
x3 3
x1
x2 5 x3 6
2x x x 2
1
2
3
1
1 0
0 1 5
2 1 1
3
6
2

28.

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
5
Из уравнения 3 вычитаем уравнение 1, умноженное на 2.
1
3
1 0
x3 3
x1
x2 5 x3 6
0 1 5 6
x2 3 x3 4
0 1 3 4
Исключим переменную x2 из последнего уравнения.
Из уравнения 3 вычитаем уравнение 2.
x1
x3 3
x2 5 x3 6
2 x3 2
1 0
0 1
0 0
1
5
2
3
6
2

29.

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
5
Обратный ход.
Коэффициенты уравнения 3 разделим на 2.
x1
x3 3
x2 5 x3 6
x3 1
1
1 0
0 1 5
0 0
1
3
6
1
Исключим переменную x3 из 1 и 2 уравнений.
Из уравнения 1 вычитаем уравнение 3.
x1
2
x2 5 x3 6
x3 1
0
1 0
0 1 5
0 0
1
2
6
1

30.

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
5
К уравнению 2 прибавим уравнение 3, умноженное на 5.
x1
x2
2
1
x3 1
Получаем решение:
1 0
0 1
0 0
x1 2
x2 1
x3 1 .
0
0
1
2
1
1

31.

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
5
Вычисление элементов обратной матрицы
Обратной к матрице A называют такую матрицу
A для которой A A A A E , где
1
1 0 ... 0
0 1 ... 0
E
.
. . ... .
0 0 ... 1
1
a11 a12
a21 a22
A
.
.
an1 an 2
1
... a1n
x11
... a2 n
x21
1
. A
.
... .
... ann
xn1
x12
x22
.
xn 2
... x1n
... x2 n
... .
... xnn
Для вычисления элементов обратной матрицы A
используем соотношение
A A 1 E.
1

32.

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
5
1
A
Умножая матрицу A на
и приравнивая каждый элемент
произведения соответствующему элементу матрицы E
2
неизвестными
n
получим систему из n уравнений с
2
xij
(i, j 1,2,..., n).
Так, умножая почленно каждую строку матрицы A на
первый столбец матрицы A
1
и каждый раз приравнивая
полученное произведение соответствующему элементу
первого столбца матрицы E , получаем систему

33.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
a11 x11 a12 x21 a13 x31 ... a1n xn1 1,
a21 x11 a22 x21 a23 x31 ... a2 n xn1 0
......................................................
an1 x11 an 2 x21 an 3 x31 ... ann xn1 0

34.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Аналогично при умножении строк матрицы A на второй
столбец матрицы A
1
образуется еще одна система
a11 x12 a12 x22 a13 x32 ... a1n xn 2 0,
a21 x12 a22 x22 a23 x32 ... a2 n xn 2 1
......................................................
an1 x12 an 2 x22 an 3 x32 ... ann xn 2 0
и так далее…

35.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Метод прогонки

36.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА

37.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА

38.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА

39.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА

40.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА

41.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Итерационные методы решения СЛАУ
Дана система линейных алгебраических уравнений
a11 x1 a12 x2 ... a1n xn b1
a x a x ... a x b
21 1 22 2
2n n
2
, det A 0
....................................................
an1 x1 an 2 x2 ... ann xn bn
Для построения итерационных формул нужно систему
привести к виду: X C X , где

42.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
x1
x2
X
xn
0
a21
a
C 22
...
an1
a
nn
a12
a11
...
0
...
...
an 2
ann
...
...
a1n
b1
a
a11
11
a2 n
b2
a22 a22
...
bn
0
a
nn

43.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
В результате получаем:
a1,n
b1 a1,2
x1
x2 ...
a1,1 a1,1
a1,1
a2,1
a2,n
b2
x2
x1 ...
a2,2 a2,2
a2,2
..............................................
an,1
an,n 1
bn
xn
x1 ...
xn 1.
an,n an,n
an,n

44.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Далее справа подставляем предыдущие приближения
X k начиная с X 0 и слева получаем последующие
приближения X
k 1
.
В результате получаем итерационные формулы вида:
X
( k 1)
C X
(k )
Начиная с X 0, получим последовательность векторов
X 0 , X 1 , X 2 ,..., X k ,... Если эта последовательность сходится,
то она сходится к решению системы.
В результате получаем формулы метода итерации.

45.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Метод простой итерации
a1,n ( k )
b1 a12 ( k )
( k 1)
x1
x2 ...
xn
a11 a11
a11
( k 1)
2
x
a2,n ( k )
b2 a21 ( k )
x1 ...
xn
a22 a22
a22
.............................................................
an ,n 1 ( k )
bn an ,1 ( k )
( k 1)
xn
x1 ...
xn 1.
ann ann
ann
Или иначе:
n a
b
i, j k
k 1
i
xi
xj
ai ,i j 1 ai ,i
j i

46.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Эти формулы используем при k 0, 1,... и получаем
последовательность векторов X 0 , X 1 , X 2 ,..., X k .
0
X
За начальный вектор
будем брать столбец свободных
членов или X 0 0.
Условие окончания поиска:
k 1
i
x x
k
i
, i 1..n
Достаточные условия сходимости метода:
n
n
aii aij
j 1
или
a jj aij
i 1
Если условия выполнены, то процесс простой итерации
сходится к единственному решению системы независимо
от выбора начального приближения.

47.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА

48.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Метод Зейделя
Идея метода Зейделя заключается в том, что
при вычислении (k 1) -го приближения
неизвестной xi учитываются уже вычисленные
ранее (k 1) -е приближения неизвестных
x1 , x2 , ..., xi 1
Итерационные формулы метода Зейделя будут
иметь следующий вид:

49.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
n a
b
1 j (k )
( k 1)
1
x1
xj ,
a11 j 2 a11
n a
b
a
2 j (k )
x2( k 1) 2 21 x1( k 1)
xj ,
a22 a22
j 3 a22
...........................................................
a
n 1 nj x ( k 1) ,
bn
( k 1)
xn
ann j
k 0, 1, 2,...
ann j 1
Или иначе:
i 1 a
n a
b
i , j k 1
i, j k
k 1
i
xi
xj
xj
ai ,i j 1 ai ,i
j i 1 ai ,i

50.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Условия сходимости метода Зейделя те же, что у
метода простой итерации : преобладание диагональных
элементов.
Для метода Зейделя имеется еще теорема о сходимости:
Пусть матрица A — вещественная, симметричная,
определенная матрица. Тогда метод Зейделя
сходится.

51.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
Метод релаксации (ослабления)
Пусть имеем систему линейных уравнений
a11 x1 a12 x2 ...a1n xn b1
a 21 x1 a 22 x2 ...a 2 n xn b2
.......... .......... .......... .......... .
a n1 x1 a n 2 x2 ...a nn xn bn
Преобразуем эту систему с.о.: перенесем правую часть
налево и разделим первое уравнение на a11, второе на
a 22 и т.д. Тогда получим систему, приготовленную к
релаксации:

52.

5
ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
x1 c12 x2 ... c1n xn d1 0
c21 x1 x2 ... c2 n xn d 2 0
.......... .......... .......... .......... .........
cn1 x1 cn 2 x2 ... xn d n 0
где
cij
aij
aii
(i j ),
bi
di
aii

53.

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА
5
Пусть x
(0)
( x1( 0) ,
x2( 0) , ..., xn( 0) ) - начальное
приближение решения системы. Подставляя эти значения
в систему, получим невязки
n
(0)
1
d1 x
c1 j x
(0)
2
d2 x
c2 j x
R
R
(0)
1
(0)
2
j 2
n
j 1,
j 2
(0)
j
(0)
j
.......... .......... .......... .......... ..
n 1
Rn( 0 ) d n xn( 0 ) cnj x (j0 )
j 1