Обусловленность СЛАУ и методы решения плохо обусловленных СЛАУ

1. Обусловленность СЛАУ и методы решения плохо обусловленных СЛАУ

Устойчивость решения СЛАУ. Плохо
обусловленные СЛАУ. Число
обусловленности, его свойства. Метод
вращений решения плохо обусловленных
СЛАУ. Методы регуляризации решения
плохо обусловленных систем
Безбородникова Р.М.

2. Норма вектора

x ( x1 , x2 ...xn )
x - норма вектора
Свойства векторных норм
1) x 0, x 0 x (0,0,...0)
2) x x , R
3) x, y R n x y x y
x max xi
i 1, n
n
x l1 xi
i 1
xe
2
n
2
x
i
i 1

3. Норма матрицы

a11 a12 ... a1n
a
a
...
a
22
2n
А 21
...
a
n1 an 2 ... ann
A - норма матрицы
Свойства матричных норм
0 ... 0
1) A 0, A 0 A ...
0 ... 0
2) A A , R
x max xi
i 1, n
n
3) A, B R n ,n A B A B
x l1 xi
i 1
xe
3
n
2
x
i
i 1

4. Число обусловленности

• Дана СЛАУ вида Ах = b (1)
с обратимой матрицей А размера nхn.
Если система плохо обусловлена, то это
значит, что погрешности коэффициентов
матрицы А и правых частей b или же
погрешности их округления сильно искажают
решение системы.
Найдем выражение для полной оценки
погрешности решения системы.
4

5. Вычисление выражения для полной оценки погрешности решения системы

• Предположим, что правая часть уравнения (1)
получила приращение (возмущение) ∆b.
Реакцией решения х на возмущение ∆b правой
части будет вектор поправок ∆x:
А (х + ∆х) = b + ∆b . (2)
• получим оценку вида:
5

6. Число обусловленности

6

7. Число обусловленности

• Неравенства (5) и (6) показывают, что чем больше
число обусловленности, тем сильнее сказывается на
решении линейной системы ошибка в исходных
данных.
• Если число cond А велико, то система считается
плохо обусловленной.
7

8. Число обусловленности

• Можно дать оценку числа обусловленности
снизу. Оно следует из неравенства:
• т.е. число обусловленности не может быть
меньше единицы!
8

9. Число обусловленности

• Можно также получить оценку снизу числа
обусловленности через собственные числа
матрицы.
Следовательно,
оценкой
снизу
меры
обусловленности матрицы А может служить
величина |λ1|/|λn| (называемая иногда числом
9
обусловленности Тодда).

10. Свойства числа обусловленности

1)Cond (E)=1
2) Cond (A)≥1
3) Cond (A) ≥│λmax│/│λmin│
4) Cond (AB)≤ cond(A)*cond(B)
5) Cond (A)=Cond(αA)
10

11. Пример неустойчивой системы

11

12. Пример неустойчивой системы

12

13. Геометрическая трактовка понятия обусловленности

13

14. Метод вращений решения плохо обусловленных СЛАУ

• Прямой ход метода – приводим систему к треугольному виду.
• 1 шаг: исключаем неизвестное х1 из 2,3..n-ого уравнений слау.
• Первое уравнение умножают на c1, а второе на –s1. Складывают их
и записывают в качестве первого уравнения.
• Первое уравнение умножают на –s1, а второе на с1. Складывают их
и записывают в качестве второго уравнения.
c1a11 s1a21 x1 c1a12 s s a22 x2 ... c1a1n s1a2n xn c1b1 s1b2
s1a11 c1a21 x1 s1a12 c1a22 x2 ... s1a1n c1a2n xn s1b1 c1b2
s1a11 c1a 21 0 - условие обнуления
c1 s1 1 - условие нормировки
2
2
• Таким образом, для исключения х1 из 2-го уравнения вычисляют:
c1
a 11
a a
2
11
2
21
s1
a 21
a 112 a 221
14

15. Метод вращений решения плохо обусловленных СЛАУ

В результате получим систему:
a11 1 x1 a12 1 x2 ... a1 1n xn b1 1
1
1
1
a
x
...
a
x
b
22 2
2n n
2
a31x1 a32 x2 ... a3n xn b3
...............................................
an1 x1 an 2 x2 ... ann xn bn
1
(*)
____
a1 j c1 a1 j s1 a 2 j , j 1, n, b1 1 c1b1 s1b2
1
____
a 2 j s1 a1 j c1 a 2 j , j 2, n, b2 1 s1b1 c1b2
15

16. Метод вращений решения плохо обусловленных СЛАУ

• Это преобразование эквивалентно
умножению слева на матрицу:
c1 s1 0 0 ...
s1 c1 0 0 ...
0
0 1 0 ...
Q12
0 0 1 ...
0
... ... ... ... ...
0
0 0 0 ...
0
0
0
0
...
1
16

17. Метод вращений решения плохо обусловленных СЛАУ

• Затем первое уравнение системы (*) заменяют
линейной комбинацией первого и третьего
уравнений с коэффициентами c2 и s2, а третье
уравнение − аналогичной комбинацией с
коэффициентами −s2 и c2
c2
a11(1)
a a
(1) 2
11
(1) 2
31
s2
a 31
a a
(1) 2
11
2
31
17

18.

Результат преобразований
2
a 2 x1 a12
x2 ... a1 n2 xn b1 2
11
1
1
1
a
x
...
a
x
b
22 2
2n n
2
1
a32
x2 ... a3 1n xn b3 1
a41 x1 a42 x2 ... a4 n xn b4
................................................
an1 x1 an 2 x2 ... ann xn bn
2
1
с2
1
a11
a a
1 2
2
13
11
s2
a31
a a
1 2
11
2
31
____
a1 j c2 a1 j s2 a3 j , j 1, n, b1 2 c2b1 1 s2b3
1
____
a3 1j s2 a1 j c2 a3 j , j 2, n, b3 1 s2b1 1 c2b3
18

19. Метод вращений решения плохо обусловленных СЛАУ

Это преобразование эквивалентно умножению
слева на матрицу:
c 2 0 s 2 0 ...
0 1 0 0 ...
s 0 c 0 ...
2
Q13 2
0 0 1 ...
0
... ... ... ... ...
0
0 0 0 ...
0
0
0
0
...
1
19

20. Метод вращений решения плохо обусловленных СЛАУ

Исключая неизвестное х1 из всех последующих
уравнений получим систему:
Матрицы Qij называются
A(1)x=b(1), где
матрицами плоских вращений
(1)
A =Q1nˑˑˑQ13ˑQ12ˑA
b(1)=Q1nˑˑˑQ13ˑQ12ˑb
Действие матрицы Qkj на вектор х эквивалентно
повороту вектора х вокруг оси, перпендикулярной
плоскости ОХkXj на угол ϕkj такой что:
сkj cos kj
s kj sin kj
20

21. Метод вращений решения плохо обусловленных СЛАУ

• 2 шаг. Исключаем х2 из 3,4…n-ого
уравнений.
Получим систему:
A(2)x=b(2), где
A(2)=Q2nˑˑˑQ24ˑQ23ˑA(1)
b(2)= Q2nˑˑˑQ24ˑQ23ˑb(1)
21

22.

Итоговый результат
Результат преобразований
преобразований
a11 n 1 x1 a12 n 1 x 2 ... a1 nn 1 x n b1 n 1
n 1
n 1
n 1
a
x
...
a
x
b
22
2
2n
n
2
...........................................................
n 1
a nn
x n bn n 1
22

23. Пример (матричный подход)-1 шаг

Пример
(матричный
подход)-1
Пример
(вращение
матрицы)-1
шагшаг
23

24. Пример (вращение матрицы)-2 шаг

24

25. Пример (вращение матрицы)-3 шаг

25

26. Задача

• Используя метод вращений решить СЛАУ:
26

27. Метод регуляризации для решения плохо обусловленных систем

27

28. Метод регуляризации для решения плохо обусловленных систем

28

29. Метод регуляризации для решения плохо обусловленных систем

29

30. Выбор управляющего параметра α

30