- •III семестр. Ммф нгу
- •Конспект лекций1
- •2003 – 2004 Учебный год
- •Содержание
- •Лекция 1. Традиционные задачи линейной алгебры
- •Векторные и матричные нормы
- •Число обусловленности
- •Лекция 2. Прямые методы решения линейных уравнений Метод исключения Гаусса – схема единственного деления
- •Теорема об lu разложении
- •Разложение Холесского
- •Метод квадратного корня
- •Метод вращений решения системы уравнений Элементарная матрица вращения
- •–Ый шаг метода вращений
- •Решение системы с вырожденной матрицей –разложение с перестановками столбцов матрицы
- •Совместность системы с вырожденной матрицей
- •Применение –разложения с перестановками столбцов для решения совместной системы
- •Метод прогонки решения систем с трехдиагональной матрицей –разложение трехдиагональной матрицы :
- •Формулы метода прогонки для системы :
- •Асимптотическая скорость сходимости
- •Метод Зейделя (Гаусса–Зейделя, Некрасова)
- •Необходимое и достаточное условие сходимости метода Зейделя в случае симметричной матрицы с положительной главной диагональю
- •Лекция 7. Функционал ошибки
- •Метод полной релаксации
- •Метод неполной релаксации
- •Метод минимальных невязок
- •Метод простой итерации
- •Оценки сходимости мнс и ммн
- •Лекция 9. Метод Ричардсона с чебышевскими параметрами Задача оптимизации параметров
- •Полином Чебышева и решение задачи оптимизации параметров
- •Циклический метод Ричардсона: формулы и сходимость
- •Об устойчивости метода Ричардсона
- •Трехчленные формулы реализации метода Ричардсона с чебышевскими параметрами
- •Лекция 10. Многошаговые методы. Вариационная оптимизация
- •Метод сопряженных градиентов
- •Переобуславливатель
- •Положительно определенные матрицы
- •Лекция 11. Проблема собственных значений
- •Корректность задачи на собственные значения
- •Степенной метод вычисления максимального собственного значения матрицы
- •Степенной метод вычисления минимального собственного значения матрицы
- •Применение ортогонализации и степенного метода для вычисления очередного собственного значения
- •Лекция 12. Метод деления пополам (бисекций)
- •Идея метода бисекций вычисления
- •Приведение самосопряженной матрицы к трехдиагональному виду ортогональным преобразованием подобия с помощью матриц вращения
- •Якобиевы матрицы
- •О вычислении чпз
- •О вычислении собственного вектора
- •Лекция 13. Метод вращений (Якоби)
- •Выбор вращения
- •Сходимость собственных значений
- •Сходимость собственных векторов
- •Литература
Метод вращений решения системы уравнений Элементарная матрица вращения
Доказать, что – унитарная матрица, т.е. .
Доказать, что .
Доказать, что при умножении на матрицу матрицы слева ( ) изменяются только и строки матрицы .
–Ый шаг метода вращений
Предположим, что после шага система с помощью умножения слева на ортогональную матрицу приведена к виду , где
.
Тогда –ый шаг состоит из умножения системы слева на элементарные матрицы вращений :
, где
, если ,
, если .
В результате получим , где .
Выполнив шаг, получим систему с верхней треугольной матрицей: (заметим, что, если , то и ).
Если определить унитарную матрицу , то справедлива
Теорема. .
Доказать, что .
Лекция 4.
Метод отражений решения системы уравнений
Матрица отражения
|
Доказать, что , . |
–ый шаг метода отражений
Предположим, что после шага система с помощью умножения слева на ортогональную матрицу приведена к виду , где
.
Тогда –ый шаг состоит из умножения системы слева на ортогональную матрицу вращения :
,
где |
|
если или , |
|
|
если (здесь , – первый орт), |
|
|
если (здесь ). |
Выполнив шаг, получим систему с верхней треугольной матрицей: (заметим, что, если , то и ).
Решение системы с вырожденной матрицей –разложение с перестановками столбцов матрицы
1– ый шаг. |
Определим номер столбца матрицы из условия и матрицу перестановок . Для матрицы определим матрицу отражения : . Доказать: |
–ый шаг. |
После шага имеем . Определяем номер столбца из условия и для определяем матрицу отражения : . Доказать: . |
Ответ: |
Если , то после шагов имеем , где и – ортогональные матрицы. |
Совместность системы с вырожденной матрицей
Система называется совместной, если она имеет решение. Следовательно, система совместна .
– общее решение системы, где – любое ее решение.
Теорема. |
Если система совместна ( ), то совместна система и множества решений этих систем совпадают. |
Система несовместна, если .
В этом случае ее обобщенным решением (относительно векторной нормы ) называют вектор .
Доказать: общее решение совместной системы совпадает с множеством ее обобщенных решений.
Доказать: множество обобщенных решений совпадает с общим решением системы .
Применение –разложения с перестановками столбцов для решения совместной системы
Выполним эквивалентное преобразование совместной системы :
.
Из–за ошибок округления эта система будет иметь вид:
,
где матрица и вектор должны иметь малые по модулю элементы. Заменяем их на нулевые матрицу и вектор (диагональные элементы матрицы по модулю мажорируют все левее и ниже лежащие элементы, как только очередной диагональный элемент стал “намного” меньше предыдущего, то и остальные элементы почти нулевые):
,
очевидно, что общее решение этой системы определяется формулой
,
а решение исходной системы .