Мацокин А.М. “Вычислительные методы линейной алгебры.” Конспект лекций.

III семестр. Ммф нгу

Вычислительные методы линейной алгебры

Конспект лекций1

Мацокин А.М. – проф. кафедры вычислительной математики

2003 – 2004 Учебный год

Предлагаем Вашему вниманию конспект лекций семестрового курса «Вычислительные методы линейной алгебры», прочитанных профессором кафедры А.М. Мацокиным для студентов второго курса механико–математического факультета Новосибирского государственного университета.

Мы надеемся, что этот конспект будет полезен студентам ММФ НГУ для более полного усвоения курса и применения методов вычислительной математики в их дальнейшей учебной, научно–преподавательской и практической деятельности.

Ограничений на использование и распространение конспекта – нет.

Любым замечаниям автор конспекта будет только рад и принимает их по адресу

E-mail: matsokin@oapmg.sscc.ru

или

E-mail: mmf@nsu.ru

Содержание

Лекция 1. 4

Традиционные задачи линейной алгебры 4

Векторные и матричные нормы 5

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

Лекция 2. Прямые методы решения линейных уравнений 7

Метод исключения Гаусса – схема единственного деления 7

Теорема об LU разложении 8

Разложение Холесского 9

Метод квадратного корня 9

Лекция 3. 10

Метод исключения с выбором главного элемента по столбцу 10

Матрица перестановок 10

Элементарная матрица перестановок 10

Выбор главного элемента по столбцу. 10

Метод вращений решения системы уравнений 12

Элементарная матрица вращения 12

–ый шаг метода вращений 12

Лекция 4. 13

Метод отражений решения системы уравнений 13

Матрица отражения 13

–ый шаг метода отражений 13

Решение системы с вырожденной матрицей 14

–разложение с перестановками столбцов матрицы 14

Совместность системы с вырожденной матрицей 15

Применение –разложения с перестановками столбцов для решения совместной системы 15

Метод прогонки решения систем с трехдиагональной матрицей 16

–разложение трехдиагональной матрицы : 16

Формулы метода прогонки для системы : 16

Лекция 5. Итерационные методы решения линейных уравнений 17

Пример и основные определения 17

Пример: 17

Одношаговый (двухслойный) итерационный метод решения : 17

Стационарный одношаговый итерационный метод решения : 17

Условия сходимости стационарного итерационного метода 18

Достаточные условия: 18

Необходимое и достаточное условие: 18

Асимптотическая скорость сходимости 19

Лекция 6. 20

Метод Якоби 20

Сходимость в случае диагонального преобладания по строкам 20

Сходимость в случае диагонального преобладания по столбцам 20

Необходимое и достаточное условие сходимости метода Якоби в случае симметричной матрицы с положительной главной диагональю 21

Метод Зейделя (Гаусса–Зейделя, Некрасова) 21

Необходимое и достаточное условие сходимости метода Зейделя в случае симметричной матрицы с положительной главной диагональю 22

Лекция 7. 23

Функционал ошибки 23

Метод полной релаксации 23

Метод неполной релаксации 24

Оценка сходимости методов релаксации 25

Пример 26

Лекция 8. 27

Градиент, метод наискорейшего спуска 27

Метод минимальных невязок 27

Метод простой итерации 28

Оценки сходимости МНС и ММН 29

Лекция 9. Метод Ричардсона с чебышевскими параметрами 30

Задача оптимизации параметров 30

Полином Чебышева и решение задачи оптимизации параметров 30

Циклический метод Ричардсона: формулы и сходимость 32

Об устойчивости метода Ричардсона 33

Трехчленные формулы реализации метода Ричардсона с чебышевскими параметрами 35

Лекция 10. 36

Многошаговые методы. Вариационная оптимизация 36

Метод сопряженных градиентов 37

Переобуславливатель 38

Положительно определенные матрицы 39

Лекция 11. Проблема собственных значений 40

Корректность задачи на собственные значения 40

Степенной метод вычисления максимального собственного значения матрицы 41

Степенной метод вычисления минимального собственного значения матрицы 42

Применение ортогонализации и степенного метода для вычисления очередного собственного значения 42

Лекция 12. Метод деления пополам (бисекций) 43

Идея метода бисекций вычисления 43

Приведение самосопряженной матрицы к трехдиагональному виду ортогональным преобразованием подобия с помощью матриц вращения 44

Якобиевы матрицы 45

О вычислении ЧПЗ 47

О вычислении собственного вектора 47

Лекция 13. Метод вращений (Якоби) 48

Выбор вращения 49

Сходимость собственных значений 50

Сходимость собственных векторов 50

Литература 52