Итерационные методы решения СЛАУ

1.

Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет
имени М. Т. Калашникова»
Кафедра «АСОИУ»
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
Автор Исенбаева Е.Н., старший преподаватель
Ижевск
2013

2. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ(СЛАУ)

Итерационные методы - методы,
в которых решение может быть
получено с заданной точностью
путем сходящихся бесконечных
процессов.
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
2

3. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ(СЛАУ)

Размерность системы
велика
используют итерационные
методы
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
3

4. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ(СЛАУ)

Итерационные методы:
–метод простых итераций
–метод Зейделя
–метод релаксации
– метод Шульца
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
4

5. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

Решить систему линейных алгебраических
уравнений итерационными методами.
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
5

6. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
6

7. ПРИВЕДЕНИЕ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Преобразуем систему (1) тем или
иным способом к системе вида
х = αх+β
(2),
где х- тот же вектор неизвестных,
α, β – некоторые новые матрица и
вектор соответственно.
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
7

8. ПРИВЕДЕНИЕ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Система (2):
-приведена к нормальному виду
-пригодна для итерационного
процесса.
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
8

9. МЕТОД ПРОСТЫХ ИТЕРАЦИЙ

• Используя систему (2),
определяем последовательность
приближений
к неподвижной
точке х* рекуррентным
равенством
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
9

10. МЕТОД ПРОСТЫХ ИТЕРАЦИЙ

• Метод простых итераций(МПИ)итерационный процесс (3),
начинающийся с некоторого
вектора:
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
10

11. ПРИБЛИЖЕНИЯ К РЕШЕНИЮ СЛАУ

x
( k 1)
2
x
(k )
21 1
22 x
(k )
2
... 2 n x
(k )
n
2
…
x
( k 1)
n
x
(k )
n1 1
n2 x
(k )
2
... nn x
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
(k )
n
n
11

12. ВЫБОР НАЧАЛЬНОГО ПРИБЛИЖЕНИЯ

Сходимость МПИ
гарантирована при любом
начальном векторе
.
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
12

13. ВЫБОР НАЧАЛЬНОГО ПРИБЛИЖЕНИЯ

ближе к точному
решению х*
итераций потребуется
меньше.
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
13

14. ВЫБОР НАЧАЛЬНОГО ПРИБЛИЖЕНИЯ

Нет никакой информации о грубом
решении задачи (2) или решении
близкой задачи → за
обычно
принимают вектор β свободных
членов системы (2).
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
14

15. СПОСОБЫ ПРИВЕДЕНИЯ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Диагональное преобладание:
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
15

16. СПОСОБЫ ПРИВЕДЕНИЯ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Новая матрица коэффициентов
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
16

17. СПОСОБЫ ПРИВЕДЕНИЯ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Новый вектор свободных членов
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
17

18. СПОСОБЫ ПРИВЕДЕНИЯ СЛАУ К НОРМАЛЬНОМУ ВИДУ

→
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
18

19. СПОСОБЫ ПРИВЕДЕНИЯ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Имея систему:
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
19

20. СПОСОБЫ ПРИВЕДЕНИЯ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
20

21. ПРИМЕРЫ ПРИВЕДЕНИЯ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
21

22. ПРИМЕРЫ ПРИВЕДЕНИЯ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
22

23. ПРИМЕРЫ ПРИВЕДЕНИЯ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
23

24. ПРИМЕРЫ ПРИВЕДЕНИЯ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
24

25. ПРИМЕРЫ ПРИВЕДЕНИЯ СЛАУ К НОРМАЛЬНОМУ ВИДУ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
25

26. ПОСТРОЕНИЕ ИТЕРАЦИОННОГО ПРОЦЕССА МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
26

27. ПОСТРОЕНИЕ ИТЕРАЦИОННОГО ПРОЦЕССА МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
27

28. ПОСТРОЕНИЕ ИТЕРАЦИОННОГО ПРОЦЕССА МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
28

29. УСЛОВИЯ СХОДИМОСТИ ИТЕРАЦИОННОГО ПРОЦЕССА

Дана СЛАУ, приведенная к
нормальному виду х=β+αх
Теорема 1. Пусть ||α||≤q<1. Тогда при
любом начальном векторе
МПИ сходится к единственному
решению х* и при всех
кєN справедливы оценки погрешности:
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
29

30. УСЛОВИЯ СХОДИМОСТИ ИТЕРАЦИОННОГО ПРОЦЕССА

Здесь обозначение ||.|| используется для
матричных и векторных норм,
согласованных между собой, т.е. таких, что
||Ax||≤||A||*||x||.
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
30

31. УСЛОВИЯ СХОДИМОСТИ ИТЕРАЦИОННОГО ПРОЦЕССА

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
31

32. УСЛОВИЯ СХОДИМОСТИ ИТЕРАЦИОННОГО ПРОЦЕССА

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
32

33. АПРИОРНАЯ И АПОСТЕРИОРНАЯ ОЦЕНКИ

Априорная оценка позволяет
подсчитывать заранее число итераций k,
достаточное для получения решения х* с
заданной точностью ε при выбранном
начальном векторе
Наименьшее целое решение неравенства
относительно k
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
33

34. АПРИОРНАЯ И АПОСТЕРИОРНАЯ ОЦЕНКИ

Апостериорной оценкой пользуются
непосредственно в процессе вычислений
и применяют для останова процесса
итераций при выполнении неравенства:
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
34

35. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

записать сходящийся процесс простых итераций. За
сколько шагов этого процесса, начатого с нуль-вектора,
можно достичь точности ε=0,001 по норме-максимум?
Найти третье приближение, оценить его абсолютную
погрешность и сравнить ее с истинной погрешностью,
зная точное решение системы
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
35

36. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Решение: Учитывая очевидную близость матрицы
данной системы к единичной матрице, выделим
единицы из диагональных элементов, в результате чего
система преобразуется к виду:
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
36

37. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
37

38. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
38

39. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Априорная оценка погрешностей:
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
39

40. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

При заданном векторе x(0)=0
первым приближением
, служит
вектор β свободных членов;
следовательно
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
40

41. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Требуемое количество шагов, достаточное
для достижения точности 0,001, может быть
найдено как первое из последовательности
натуральных чисел k, удовлетворяющих
неравенству:
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
41

42. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
42

43. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
43

44. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
44

45. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ПРОСТЫХ ИТЕРАЦИЙ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
45

46. МЕТОД ЗЕЙДЕЛЯ

Метод Зейделя - это такое
видоизменение МПИ(3) решения
СЛАУ, приведенных к виду (2), при
котором для подсчета i-й компоненты
(к+1)го приближения к искомому
вектору х* используется уже
найденные на этом, т.е. (к+1) шаге,
новые значения первых (i-1)
компонент.
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
46

47. МЕТОД ЗЕЙДЕЛЯ

-матрица
коэффициентов
-вектор свободных
членов
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
47

48. МЕТОД ЗЕЙДЕЛЯ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
48

49. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ЗЕЙДЕЛЯ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
49

50. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ЗЕЙДЕЛЯ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
50

51. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ЗЕЙДЕЛЯ

Начнем процесс итераций с того же начального приближения
при к=0,1,2 последовательно получаем:
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
, далее
51

52. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ЗЕЙДЕЛЯ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
52

53. ПРИМЕР РЕШЕНИЯ МЕТОДОМ ЗЕЙДЕЛЯ

Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
53

54. ПРЕИМУЩЕСТВА ИТЕРАЦИОННЫХ МЕТОДОВ

1.Если итерации сходятся достаточно
быстро, т.е. для решения системы
требуется менее k итераций, то
получаем выигрыш во времени, т.к.
число арифметических действий,
необходимых для одной итерации,
пропорционально n,а общее число
арифметических действий в методе
Гаусса пропорционально n.
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
54

55. ПРЕИМУЩЕСТВА ИТЕРАЦИОННЫХ МЕТОДОВ

2.Погрешности округлений в МПИ
сказываются значительно меньше, чем
в методе Гаусса. Кроме того, МПИ
является самоисправляющимся, т.е.
отдельные ошибки, допущенные в
вычислениях, не отражаются на
окончательном результате, т.к.
ошибочное приближение можно
рассматривать как новый начальный
вектор.
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
55

56. ПРЕИМУЩЕСТВА ИТЕРАЦИОННЫХ МЕТОДОВ

3.МПИ становится особенно
выгодным для решения систем, у
которых значительное число
нулевых коэффициентов(при
решении уравнений в частных
производных).
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
56

57. ПРЕИМУЩЕСТВА ИТЕРАЦИОННЫХ МЕТОДОВ

4.Итерационные методы легко
программируются на ЭВМ.
Особенно метод Зейделя.
Курс «Вычислительная математика»
Тема «Итерационные методы решения СЛАУ»
57

58.

СПАСИБО ЗА ВНИМАНИЕ
© ФГБОУ ВПО ИжГТУ имени М.Т. Калашникова, 2013
© Исенбаева Елена Насимьяновна, 2013