Итерационные методы подпространств Крылова.
Курс 2, Прикладна математика
Основы вычислений в арифметике с плавающей точкой.
1. Система чисел с плавающей точкой. Представление вещественных чисел числами с плавающей точкой. Погрешности представления вещественных чисел числами с плавающей точкой.
2. Арифметические операции в системе чисел с плавающей точкой. Вычитание близких чисел. IEEE стандарт компьютерной арифметики. Устойчивые и неустойчивые алгоритмы. Почти некорректные, или плохо обусловленные задачи.
Прямые методы решения систем линейных алгебраических уравнений (СЛАУ).
3. Теорема о LU-разложении матрицы. Матрицы исключения. Матрица, обратная к матрице исключения. Произведение матриц исключения. Метод Гаусса. Алгоритм LU-разложения матрицы. Количество арифметических операций LU-разложения матрицы.
4. Нормы векторов и матриц. Согласованная матричная норма. Порождаемая матричная норма. Теоремы о порождаемой матричной норме. Эквивалентные матричные нормы. Лемма об обратимости матрицы (I-X).
5. Теория возмущений для СЛАУ. Число обусловленности матрицы. Свойства числа обусловленности. Теорема о геометрическом смысле числа обусловленности матрицы. Пример СЛАУ с плохо обусловленной матрицей(пример плохо обусловленной задачи).
6. Численная неустойчивость метода Гаусса (LU-разложения матрицы) в арифметике с плавающей точкой. Матрицы перестановок. PLU-разложение невырожденной матрицы. Метод Гаусса с частичным (полным) выбором главного элемента. Алгоритм метода Гаусса с частичным выбором главного элемента. Анализ ошибок метода Гаусса (с частичным выбором главного элемента) в арифметике с плавающей точкой.
7. Положительно определенные матрицы и их свойства. Разложение Холесского симметричной положительно определенной матрицы. Алгоритм разложения Холесского симметричной положительно определенной матрицы в форме внешних произведений. Количество арифметических операций разложения Холесского. Устойчивость разложения Холесского в арифметике с плавающей точкой.
8. Итерационное уточнение. Масштабирование уравнений и неизвестных.
Линейные задачи наименьших квадратов (ЛЗНК).
9. Решение ЛЗНК с помощью нормальных уравнений.
10. Теорема об QR-разложении матрицы. Классический и модифицированный методы Грама-Шмидта вычисления QR-разложения матрицы. Матрица отражения и ее свойства. Построение матрицы отражения, обнуляющей для заданого вектора все компоненты кроме первой. Построение QR-разложения матрицы с помощью матриц отражения. Метод отражений решения СЛАУ. Решение ЛЗНК с помощью QR-разложения.
11. Теорема о сингулярном разложении матрицы. Построение SVD-разложения. Геометрическая интерпретация SVD-разложения. Решение ЛЗНК с помощью SVD-разложения.
12. Псевдообратная матрица. Обусловленность ЛЗНК.
Итерационные методы решения линейных систем.
Классические итерационные методы.
13. Метод простой итерации, необходимое и достаточное условие сходимости. Достаточные условия сходимости простой итерации. Теорема о радиусе спектра матрицы, коэффициент и показатель сходимости итерационного процесса.
14. Простая итерация с оптимальным выбором параметра. Показатель сходимости простой итерации с оптимальным выбором параметра.
15. Метод Зейделя, условия сходимости метода Зейделя. Геометрическая интерпретация метода Зейделя.
16. Многочлены Чебышева и из свойства. Метод Ричардсона. Показатель сходимости метода Ричардсона.
Итерационные методы подпространств Крылова.
17. Подпространства Крылова. Алгоритм Арнольди построения ОНБ подпространства Крылова. Метод Арнольди решения СЛАУ (FOM). Метод GMRES.
18. Алгоритм Ланцоша построения ОНБ подпространства Крылова симметричной матрицы. Метод Ланцоша решения СЛАУ.
19. Метод сопряженных градиентов (CG). Сходимость метода сопряженных градиентов.
20. Предобуславливание. ILU-разложение матрицы. Алгоритм ILU-разложения матрицы.
Спектральные задачи.
21. Степенной метод нахождения максимального по модулю собственного значения. Обратная итерация нахождения минимального по модулю собственного значения. Исчерпывание вычитанием.
22. Роль сдвигов в частичной проблеме собственных значений, нахождение максимального, минимального или ближайшего к заданному значению собственного значения и соответствующего собственного вектора. Метод Ланцоша.
23. QR и QL-алгоритмы решения полной проблемы собственных значений для симметричной матрицы. Роль сдвигов в QR и QL алгоритмах.
24. Метод вращений решения полной проблемы собственных значений