1. Метод Гаусса решения систем линейных алгебраических уравнений. Выбор главного элемента.
Метод Гаусса.
a |
x |
a |
x |
... a |
x a |
||
|
11 1 12 2 |
1n n |
1n 1 |
||||
|
|
x |
a |
x |
... a |
x |
a |
a |
|||||||
|
21 1 22 2 |
2n n |
2 n 1 |
||||
|
|
|
|
|
|
|
Решаем СЛАУ: |
...
Выполняем n-1 шаг вперёд (приведение матрицы к верхнеугольной), потом n-1 шаг назад (нахождение х)
a11 (1) |
1 |
|
|
|
|
|
|
|
|
||
|
|
(1) |
|
|
(0) |
|
|
||||
|
|
a |
|
|
|
|
|
|
|||
|
|
|
1 j |
|
|
|
|
j 2,3,..., n 1 |
|||
a |
|
|
|
|
|
|
|
, |
|||
|
|
(0) |
|
||||||||
1 j |
|
|
|
|
|
|
|
||||
|
|
|
|
|
a11 |
|
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
|
|
|
a(1) |
a(0) |
a(1) |
a(0) |
, i 2,.., n; |
j 2,..., n 1 |
||||||
ij |
|
|
ij |
|
ij |
|
|
i1 |
|
|
По аналогичной формуле преобразуются все нижеследующие строчки. На (n-2)-ом шаге получается треугольная матрица.
Метод Гаусса с выделением главного элемента.
1)В текущей строке находится max aij
2)Переставляются столбцы (то есть переименовываются хi в хj и наооборот), чтобы max aij оказался спереди.
Метод дает выше точность для матриц большой размерности
2. Метод простой итерации и метод Гаусса-Зейделя решения систем линейных алгебраических уравнений. Исследование сходимости.
Метод простой итерации решения СЛАУ.
Ax F, |
|
A |
|
0 |
|
|
|||
x(0) любое |
|
B E A |
x(k 1) B x(k) F
Сходится, если хотя бы одна норма у B < 1 по модулю, т.е., например,
если max| | < 1.
Этот метод имеет ограниченную область сходимости.
Доказательство:
(x * xk ) B(x * x(k 1) ) ... (B)k (x * x0)
B 1
для сходимости
Напишем это же самое в развёрнутом виде:
x |
(k 1) |
(1 a )x(k) |
a |
x(k) |
... f |
|
|
|
|
|||||||
|
1 |
11 |
1 |
12 2 |
|
|
1 |
|
|
|
||||||
|
|
(k 1) |
a x |
(k) |
(1 a |
|
)x |
(k) |
a |
x |
(k) |
... f |
|
|||
x |
|
|
|
|
|
|
|
|||||||||
|
2 |
21 1 |
|
22 |
|
2 |
|
23 |
3 |
|
2 |
|||||
|
|
(k 1) |
|
(k) |
|
(k) |
|
|
|
|
(k) |
... f3 |
||||
x3 |
a31x1 |
a32x2 |
|
|
(1 |
a33)x3 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Метод Зейделя.
Усовершенствуем предыдущую систему:
2
x(k 1) |
(1 a |
|
|
)x(k) a |
x(k) ... f |
|
|
|
|
|
|||||||
|
1 |
11 |
1 |
12 2 |
|
|
|
1 |
|
|
|
|
|
||||
|
|
(k 1) |
a x |
(k 1) |
(1 a |
)x |
(k) |
a x |
(k) |
... f |
|
||||||
x |
|
|
|
|
|
|
|
|
|||||||||
|
2 |
21 |
1 |
|
|
22 |
2 |
|
23 3 |
|
|
|
2 |
||||
|
|
(k 1) |
|
|
(k 1) |
|
(k 1) |
|
|
|
(k) |
... f3 |
|||||
x3 |
a31x1 |
|
a32x2 |
|
|
|
(1 a33)x3 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Свойства:
1)Скорость сходимости увеличивается.
2)Можно останавливаться в середине итерации (в середине цикла).
3)Области сходимости той же мощности (некоторые матрицы, которые методом последовательных приближений сходятся, методом Зейделя сходиться не будут, и наоборот).
4)Нет требования к симметричности или положительности .
Метод обеспечения сходимости метода Зейделя.
|
|
|
|
|
|
|
Ax F , если |
H |
0 |
||||
|
|
|
|
|
|
|
то две СЛАУ равносильны
HAx H F
тогда Bновое E HA
Выбор H, чтобы все | | < 1 у HA
Итерационный процесс:
1)
|
1 |
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
|
|||
|
|||||||||
a |
|
|
|
|
|
|
|
||
|
11 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
||||
|
0 |
0 |
0 |
0 |
|
||||
|
|
||||||||
|
a |
||||||||
|
|
|
|
|
|
|
|
||
H |
|
22 |
|
|
|
|
|
||
|
|
|
1 |
|
|
||||
|
0 |
0 |
|
|
0 |
0 |
|
||
|
|
||||||||
|
|
|
|
|
a |
|
|
|
|
|
|
|
|
32 |
|
|
|
||
0 |
0 |
0 ... |
0 |
||||||
|
|
|
|
|
|
|
1 |
|
|
|
0 |
0 |
0 |
0 |
|
|
|||
|
|||||||||
|
|
|
|
|
|
|
a |
|
|
|
|
|
|
|
|
|
nn |
2) Если 1) не дало результата (процесс не стал сходиться).
3
|
|
Q |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
Q |
|
не нули |
||
A |
не нули |
2 |
Q |
|
|
|
||
|
|
|
||||||
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
a |
|
|
|
|
|
|
|
|
nn |
|
|
|
|
|
|
|
|
Ищем блоки 2*2, если их нечётное количество, то останется 1 блок
1*1=ann
|
Q |
1 |
0 |
0 |
|
0 |
|
|
|
|
|
|
|||||
|
1 |
|
|
|
|
|
||
0 |
Q 1 |
0 |
|
0 |
||||
|
|
|
||||||
H |
|
|
2 |
Q 1 |
|
|
|
|
|
|
|
|
|||||
0 |
0 |
|
0 |
|||||
|
|
|
||||||
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
1 |
|
||
|
0 |
0 |
0 |
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
a |
|
|
|
|
|
|
|
|
nn |
|
3) и т. д.
4
3. Обращение матриц методом окаймления.
А:
На k-ом шаге находится обратная матрица углового минора k k, при этом известна обратная матрица для предыдущего углового минора (k-1)(k-1).
Будем искать Аk-1 в виде (матрица):
|
Pk-1 |
rk |
|
|
qk |
1/k |
|
Аk*Ak-1 = E = [Ak-1 Uk; Vk k]*[ Pk-1 qk; rk 1/k] = |
|||
[Ak-1*Pk-1+Uk*qk |
Ak-1*rk+Uk*1/k; |
Vk*Pk-1+ k*qkVk*rk+ k*1/k] = |
|
= [Ek-1 0; 0 1] |
|
|
|
(1)Ak-1*Pk-1+Uk*qk = E;
(2)Ak-1*rk+Uk*1/k = 0;
(3)Vk*Pk-1+ k*qk = 0T;
(4)Vk*rk+ k*1/k = 1;
Следовательно:
rk = -Аk-1-1 * Uk/k; (5)
Где Аk-1-1 известна на предыдущем шаге. Подставим (5) в (4):
5
Vk*(-Аk-1-1*Uk/k) + k/k = 1; k = k - Vk*Аk-1-1*Uk;
Подставим в (5):
rk = -Аk-1-1 * Uk/ k;
Выразим из (1) Pk-1 и подставим в (3): qk = -Vk*Аk-1/k;
Pk-1 = Аk-1-1 + (Аk-1*Uk*Vk Аk-1-1)/k.
6
4. Преобразование Хаусхолдера.
(Для приведения матрицы n*n к виду Хессенберга ровно за n-2 итерации)
Некоторые определения (воспоминания).
D – диагональная: aij 0 при i j
Q – ортогональная: Q QT QT Q E
R – правая (верхняя) прямоугольная: aij 0 |
при i j |
L – левая (нижняя) треугольная: aij 0 при i j
H – Хессенберга : 1) правая, верхняя aij |
0 |
при |
i j 1 |
2) левая, нижняя aij |
0 |
при |
j i 1 |
Подобные матрицы: если Q, что B = QTAQ (у подобных матриц одинаковые собственные значения)
Конец воспоминаний
Выполняется n-2 шага (начиная с последней строки, и далее вверх). На каждом шаге:
Исключаем нулевые элементы в очередной строке (j<i-1),
Пример i-ого шага: работаем со строкой l = n-i+1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
До главн. диаг. |
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
|
i =4 |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
x x x x x x |
x x x x |
|
|||||
|
|
x |
x |
x |
0 |
|
|
|
0 |
0 |
x |
x |
x |
|
|
|
|
||||||
|
|
0 |
0 |
x |
x |
|
|
|
|
|
1) Рассчитывается величина |
|
|
l 1 |
a2 |
|
|
|||
|
i |
|
j 1 |
lj |
7
|
|
|
T |
(a(i), a(i),..., a(i) |
, a(i) |
|
|
|
|
|||||||||
2) |
|
|
|
|
sign(a |
);0;0;...0) |
||||||||||||
U i |
|
|
||||||||||||||||
|
|
|
|
|
|
|
l1 |
l2 |
|
|
ll 2 |
ll 1 |
|
i |
ll 1 |
|
||
3) |
|
H |
|
|
|
1 |
UTU |
|
|
( |
это скаляр ) |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
i |
|
|
2 i |
i |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
UT |
|
|
|
|
|
|
|
|
|||
4) |
|
Pi |
|
E Ui |
|
i |
|
|
( это матрица) |
|
|
|
|
|||||
|
|
H |
i |
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5) |
|
A |
|
1 |
P A P |
|
- (первую Р не транспонируем, т.к. матрица симметричная) |
|||||||||||
|
|
i |
|
i i |
i |
|
|
|
|
|
|
|
|
8
5. QR – разложение матрицы.
Задача представить матрицу А в виде произведения: A Q R , где Q – ортогональная ( Q QT E), R -- верхнетреугольная.
Теорема: Если А – верхняя матрица Хессенберга, то у неё существует
QR – разложение, и оно осуществляется последовательным уничтожением поддиагональных нулей.
Q, R QR(A)
Уничтожаем а21 : (в общем случае: аij, где j = i+1)
|
|
|
|
1 |
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|||
|
|
|
|
|
c |
|
s |
|
|
|
|
|
|
|
|
|
|||||
Берём |
Qi |
|
|
|
|
|
|
, где |
|
||||||||||||
|
s |
|
c |
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
0 |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|||
c |
|
aii |
|
|
, |
s |
|
|
|
a ji |
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
a2 |
a2 |
|
|
a2 |
a2 |
|
|
||||||||||||||
|
|
ii |
ji |
|
|
|
|
|
ii |
|
|
|
ji |
|
|
||||||
Получаем: |
|
|
A(1) A |
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
A |
|
Q |
|
A |
|
|
|
|
|
|
|||||||||
|
|
|
|
(2) |
|
|
|
(1) |
|
(1) |
|
|
|
|
|
||||||
R A(n) Q(n 1) A(n 1) |
Q(n 1)Q(n 2) A(n 1) ... Q(n 1)Q(n 2) ... Q1A |
||||||||||||||||||||
Домножим слева на |
|
|
T T |
T |
|
||||||||||||||||
Q Q |
...Q |
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
n |
1 |
|||
|
|
|
QT QT |
...QT |
|
|
|
1) |
R |
A |
|
||||||||||
Получим: |
1 |
2 |
|
|
|
|
(n |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
QT QT |
...QT |
|
|
|
1) |
Q |
|
|||||||||||
|
|
|
|
1 |
2 |
|
|
|
|
(n |
|
|
|
|
|
Алгоритм:
1) Находим Q1
A(2) Q(1) A(1)
Q E Q(T1)
9
2)
A(3) Q(2) A(2) Q Q Q(T2)
…
n-1)
R Q(n 1) A(n 1)
Q Q QT
(n 1)
10