ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.08.2019
Просмотров: 4702
Скачиваний: 6
Лекция 9
66
1.9
Лекция 9
1.9.1
Элементы линейной алгебры
Норма вектора — это отображение из
R
n
в
R
, обозначаемое
kxk и удовле-
творяющее свойствам:
1)
kxk
>
0,
kxk = 0 ⇔ x = 0,
2)
kαxk = |α| · kxk, α — скаляр,
3)
kx + yk
6
kxk + kyk.
Примеры:
1.
kxk
1
=
P
i
|x
i
|,
2.
kxk
2
=
r
P
i
x
2
i
— евклидова норма,
3.
kxk
∞
=
kxk
c
= max
i
|x
i
| — равномерная норма.
Векторное пространство с введённой в нём нормой называют нормиро-
ванным. Одновременно оно является метрическим, так как норма опреде-
ляет метрику — расстояние между элементами пространства:
ρ(x, y) =
kx − yk.
Норма квадратной матрицы
A — это отображение из
R
n
×n
в
R
, обо-
значаемое
kAk и удовлетворяющее свойствам:
1)
kAk
>
0,
kAk = 0 ⇔ A = 0 (матрица размера n × n из нулей),
2)
kαAk = |α| · kAk, α — скаляр,
3)
kA + Bk
6
kAk + kBk,
4)
kABk
6
kAk · kBk.
Норма матрицы
A согласована с нормой вектора x, если
kAxk
6
kAk · kxk.
5
Все три нормы — это частные случаи Гёльдеровой нормы
kxk
p
= (
P |x
i
|
p
)
1/p
для
p = 1, 2,
∞.
Лекция 9
67
Норма матрицы
A называется подчинённой норме вектора x, если
kAk
вводится следующим образом:
kAk = sup
x
6=0
kAxk
kxk
= sup
kxk=1
kAxk.
Нетрудно видеть, что подчинённая норма согласована с соответствующей
метрикой векторного пространства. В самом деле:
kAxk
kxk
6
sup
x
6=0
kAxk
kxk
=
kAk,
отсюда
kAxk
6
kAk · kxk.
В дальнейшем интерес будут представлять согласованные нормы. Но
таких норм может оказаться много. Чтобы избежать неоднозначности,
выбирают единственную подчинённую норму, которая в то же время яв-
ляется согласованной.
Вывод формул для вычисления подчинённым матричных норм
k · k
1
,
k · k
2
и
k · k
∞
приведён в задаче 6.6 в главе «Практические занятия».
Следует отметить, что в конечномерном линейном пространстве все
нормы эквивалентны в том смысле, что, если имеет место
kx
n
k
α
−→
n
→∞
0
для бесконечной последовательности
{x
n
} в некоторой норме α, то в лю-
бой другой норме
β также
kx
n
k
β
−→
n
→∞
0.
Пусть для данной матрицы
A найдётся такой ненулевой вектор x, что
Ax = λx, где λ
∈
R
. Тогда x называется собственным вектором, а
λ —
собственным значением.
Лемма 9.1. Пусть
λ — собственное значение матрицы A и det A
6= 0,
тогда
1/λ — собственное значение матрицы A
−1
.
Доказательство. Так как
det A
6= 0, то матрица A
−1
существует. Умно-
жим равенство
Ax = λx слева на A
−1
A
−1
Ax = A
−1
λx
откуда
A
−1
x
=
1
λ
x
.
Лекция 9
68
Матрица
A называется положительно определённой (A > 0) (неотри-
цательно определённой,
A
>
0), если (Ax, x) > 0 ((Ax, x)
>
0) для любых
x
6= 0.
Пусть
A > 0 и x — собственный вектор матрицы A, тогда Ax = λx и
(Ax, x) = (λx, x) = λ(x, x).
Из
(Ax, x) > 0 и (x, x) > 0 вытекает, что λ > 0. Аналогично из A
>
0
следует, что
λ
>
0.
Заметим, что для любой матрицы
A и любой согласованной матричной
нормы выполняется неравенство
kAk
>
|λ|, где λ — собственное значение
матрицы
A. В самом деле, по определению собственного значения матри-
цы
Ax = λx
. По свойству согласованной матричной нормы
kAxk
6
kAk · kxk. Далее
kλxk = |λ|kxk. В итоге получаем kAk
>
|λ|.
1.9.2
Численные методы и линейная алгебра
Численные методы линейной алгебры — бурно развивающийся раздел чис-
ленных методов. Приведём для подтверждения этого динамику числа на-
учных публикаций за последние 200 лет:
1. с 1828 г. по 1974 г. (т.е. за 147 лет) — 4000 наименований;
2. с 1975 г. по 1980 г. (т.е. за 5 лет) — 3000;
3. с 1981 г. по 1984 г. (т.е. за 3 лет) — 4000.
Задачи линейной алгебры — это:
• решение систем линейных алгебраических уравнений (СЛАУ),
• вычисление определителей и обращение матриц,
• вычисление собственных значений и собственных векторов матриц.
Лекция 9
69
1.9.3
Прямые методы решения СЛАУ
Пусть требуется найти решение системы
a
11
x
1
+ a
12
x
2
+ . . . + a
1n
x
n
= f
1
,
a
21
x
1
+ a
22
x
2
+ . . . + a
2n
x
n
= f
2
,
· · · · · · · · · · · · · · · · · · · · · · · ·
a
n1
x
1
+ a
n2
x
2
+ . . . + a
nn
x
n
= f
n
,
(9.1)
или в компактной (векторной) форме
Ax = f .
Мы будем считать, что
∆ = det A
6= 0, то есть решение (9.1) существует
и единственно.
В принципе, известны формулы Крамера, дающие в явной форме ре-
шение задачи (9.1):
x
i
= ∆
i
/∆,
где
∆
i
— определитель матрицы, которая получается из матрицы
A заме-
ной столбца с номером
i столбцом правых частей (9.1). Определители при
этом предлагается вычислять по формулам, рассматриваемым в курсах
линейной алгебры. Например, для
∆:
∆ =
X
σ
(
−1)
|σ|
a
1σ(1)
a
2σ(2)
. . . a
nσ(n)
,
где
σ — перестановка чисел 1, 2, . . . n, а
|σ| — чётность перестановки. Ко-
личество различных перестановок
σ равно n!
Однако в качестве конкретного метода решения системы (9.1) данные
формулы совершенно неприменимы, так как при подсчёте каждого опре-
делителя по приведённой выше формуле надо вычислить
n! слагаемых,
что нереально при весьма умеренных
n. Например, уже при n = 100 име-
ем
100!
10
90
. Если одно слагаемое вычисляется, скажем за
10
−7
сек, то
время расчёта составит нереальное для практики значение
T
10
90
· 10
−7
сек
=
10
83
86400
суток
≈ 3 · 10
75
лет
.
Лекция 9
70
Метод Гаусса
Метод состоит их прямого и обратного ходов.
В прямом ходе система уравнений с помощью элементарных преобра-
зований строк матрицы приводится к верхнетреугольному виду. Не огра-
ничивая существенно общности, рассмотрим работу прямого хода на при-
мере системы трёх уравнений.
a
11
a
12
a
13
a
21
a
22
a
23
a
31
a
32
a
33
f
1
f
2
f
3
→
a
11
a
12
a
13
0
a
(1)
22
a
(1)
23
0
a
(1)
32
a
(1)
33
f
1
f
(1)
2
f
(1)
3
→
a
11
a
12
a
13
0
a
(1)
22
a
(1)
23
0
0
a
(2)
33
f
1
f
(1)
2
f
(2)
3
Главный элемент.
Обратимся к примеру системы (см. задачу 1.1 в гла-
ве «Практические занятия»)
(
−10
−7
x
1
+ x
2
= 1,
x
1
+ 2x
2
= 4.
Мы видели, что в одном из вариантов метода исключения результаты по-
лучались совершенно неверными. Напомним «механизм» возникновения
больших погрешностей: деление на малые числа, появление больших (по
величине) промежуточных результатов, потеря точности при вычитании
больших (близких друг к другу) чисел.
Таким образом, порядок последовательного исключения неизвестных
может сильно сказаться на результатах расчетов (тем более для систем
высокого порядка такой исход весьма вероятен). Уменьшить опасность
подобного рода, т. е. уменьшить в процессе выкладок вероятность деления
на малые числа, позволяют варианты метода Гаусса с выбором главного
элемента.
Выбор главного элемента по столбцам. Перед исключением
x
1
отыски-
вается
max
i
|a
i1
|. Допустим, максимум соответствует i = i
0
. Тогда первое
уравнение в исходной системе (9.1) меняем местами с
i
0
-м уравнением.
(Для компьютера эта процедура связана с перестановкой двух строк рас-
ширенной матрицы (9.1).) После этого осуществляется первый шаг исклю-
чения. Затем перед исключением
x
2
из оставшихся уравнений отыскива-
ется
max
26i6n
|a
(1)
i2
| осуществляется соответствующая перестановка уравнений