ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ
ЛИНЕЙНОЙ АЛГЕБРЫ

Лектор: профессор А.М. Мацокин

(Есть конспекты всех лекций, билеты по ВМЛА и Численному анализу)

3 семестр

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

Введение: классические задачи линейной алгебры, методы их решения, основанные на теории определителей, оценка количества арифметических действий.

Векторные и матричные нормы, согласованные и подчиненные нормы. Число обусловленности (невырожденной) матрицы. Оценки возмущения решения системы линейных алгебраических уравнений при возмущении матрицы и правой части.

2. Прямые методы решения систем линейных
алгебраических уравнений

Метод исключения неизвестных (метод Гаусса), схема единственного деления. Теорема о разложении квадратной матрицы в произведение нижней и верхней треугольных матриц. Теорема о LDU-разложении квадратной матрицы. Разложение Холесского, метод квадратного корня: устойчивость к ошибкам округления при вычислении разложения, (число обусловленности сомножителя).

Выбор главного элемента по столбцу, матрицы перестановок, LU-разложение PA матрицы. Числа обусловленности сомножителей в LU-разложении квадратной матрицы A.

Число обусловленности произведения QA, где Q - ортогональная (унитарная) матрица. Матрицы вращения, QR-разложение квадратной матрицы A.

Матрицы отражения, HR-разложение матрицы A.

Метод прогонки для систем линейных алгебраических уравнений с трехдиагональными матрицами. Диагональное преобладание. Метод матричной прогонки (формулы).

3. Итерационные методы решения систем линейных уравнений

Двухслойные (одношаговые) итерационные методы. Вектор ошибки, вектор невязки, матрицы перехода. Канонический вид двухслойного однопараметрического итерационного метода. Достаточное условие сходимости стационарного итерационного метода. Теорема о необходимом и достаточном условии сходимости стационарного итерационного метода. Асимптотическая скорость сходимости.

Метод простой итерации, теорема о сходимости, выбор оптимального параметра. Метод Якоби, достаточное условие сходимости (лемма Гершгорина). Метод Зейделя (Гаусса-Зейделя).

Определение функционала ошибки Ф(z), подчиненного итерационному методу, существование такого функционала - достаточное условие сходимости итерационного метода. Теорема о достаточном условии ( ) сходимости стационарного итерационного метода Сходимость метода Зейделя для систем с симметричными, положительно определенными матрицами. Релаксация, сходимость метода релаксации для систем с симметричными, положительно определенными матрицами.

Нестационарные итерационные методы. Вариационный принцип выбора параметров. Метод наискорейшего спуска, сходимость для систем с симметричными, положительно определенными матрицами. Метод минимальных невязок, сходимость для систем с положительно определенными матрицами.

Многопараметрические итерационные методы. Метод простой итерации с чебышевским набором параметров. Оценка сходимости.

Трехчленные формулы чебышевского итерационного метода.

Метод сопряженных градиентов: построение A-ортогонального базиса, двухчленные формулы реализации, оценка сходимости метода.

4. Итерационные методы решения задачи на собственные значения и векторы симметричной матрицы

Характеристический полином матрицы, непрерывная зависимость его корней от коэффициентов.

Степенной метод приближенного вычисления максимального по модулю собственного значения и соответствующего ему собственного вектора симметричной, положительно определенной матрицы. Его применение для вычисления минимального или ближайшего к наперед заданному числу собственного значения.

Закон инерции и LDL*-разложение симметричной матрицы. Приведение симметричной матрицы к трехдиагональному виду ортогональным преобразованием подобия (с помощью матриц вращения). Якобиевая симметричная матрица, свойства последовательности ее главных миноров, теорема о количестве ее отрицательных собственных значений, простота собственных значений. Метод деления пополам приближенного вычисления i-го собственного значения якобиевой матрицы, вычисление соответствующего ему собственного вектора.

Метод вращений: инвариантность суммы квадратов элементов матрицы при умножении ее на ортогональную матрицу, изменение суммы квадратов внедиагональных элементов матрицы при ортогональном преобразовании подобия с помощью матриц вращения, оценка сходимости к нулю сумм квадратов внедиагональных элементов последовательности матриц метода вращения, оценки точности приближения собственных значений и векторов.

QR-алгоритм. Теорема о сходимости (по форме) последовательности матриц QR-алгоритма к верхней треугольной матрице в случае простых собственных значений.

Литература

  1. Бахвалов Н.С. Численные методы. М.: Наука, 1975.
  2. Воеводин В.В. Вычислительнные основы линейной алгебры. М.: Наука, 1977.
  3. Годунов С.К. Решение систем линейных уравнений. Новосибирск: Наука, Сиб. отд-ние, 1980.
  4. Коновалов А.Н. Введение в вычислительные методы линейной алгебры. Новосибирск: ВО "Наука", Сибирская издательская фирма, 1993.
  5. Самарский А.А., Гулин А.В. Численные методы. М.: Наука, 1989.
  6. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М.: Л.: Физматгиз, 1963.