Программа по курсу

"Методы оптимизации"

ЦЕЛИ И ЗАДАЧИ

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

Задачами данного курса являются:

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

Структура и содержание дисциплины

№

п/п

Разделы и темы

Содержание

1

Постановка основных экстремальных задач теории приближений.

Задачи I (о наилучшем приближении из фиксированного множества), II (задача I для класса приближаемых элементов), III ( задача II для класса приближающих множеств), IV (о фиксированном методе приближения), V (о наилучшем методе приближения из класса). Примеры методов приближений (Фурье, Фейер, Лагранж, Бернштейн, Валле-Пуссен). N-поперечник по Колмогорову, ε-энтропия, чебышевский центр.

 

2

Задача I (о наилучшем приближении из фиксированного множества в банаховом пространстве). Аппроксимация многочленами на отрезке

Существование и единственность. Строго нормированные пространства. Аппроксимация в гильбертовом пространстве. Характеризация наилучших приближений из замкнутого выпуклого множества. Свойства определителей Грама, неравенства Фишера, Адамара. Теорема Валле-Пуссена, теорема Чебышева об альтернансе. Многочлены Чебышева и связанные с ними экстремальные задачи.

 

3

Обобщенные многочлены, системы Чебышева, теорема Хаара.

Примеры и свойства систем Чебышева. Теорема Хаара о единственности приближения. Обобщение Колмогорова теоремы об альтернансе.

 

4

Наилучшие приближения в пространстве L.

Теорема Маркова о наилучшем приближении непрерывной функции в L. Теорема Никольского о двойственности, связь с задачей линейного программирования. Линейные условия Куна-Таккера.

 

5

Алгоритмы типа Ремеза.

Алгоритмы I, II приближения непрерывной функции обобщенными многочленами. Различные параметризации многочленов. Асимптотическая формула Бернштейна для фазовой функции.

 

6

Вычисление матричных функций. Рациональные крыловские приближения.

Сведение задачи расчета exp(A) к наилучшему рациональному (n-1,n) приближению exp(z) на спектре A. Вычисление значений матричных функций на векторе при помощи рациональных крыловских приближений.

 

7

Метод Каратеодори-Фейера.

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

 

8

Чебышевские стационарные методы. Упорядочение корней оператора перехода.

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

 

9

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

Связь метода (би)-сопряженных градиентов и (несимметричного) метода Ланцоша. Связь метода минимальных невязок и метода Арнольди. Экстремальные задачи, решениями которых служат невязочные многочлены рассмотренных методов. Спектральные оценки сходимости, хаусдорфово множество, формула Келдыша.

 

Перечень контрольных вопросов для сдачи экзамена в 8-ом семестре:

1.  Сформулировать теорему о перпендикуляре (характеризация наилучшего среднеквадратичного приближения из подпространства).

2.  Сформулировать теорему Хаара о единственности наилучшего приближения в пространстве непрерывных функций.

3.  Сформулировать теорему Никольского о задаче, двойственной к задаче наилучшего приближения в L из подпространства.

4.  Какую задачу оптимизации решают полиномы, порождаемые методом сопряженных градиентов?

5.  Определите многочлен Чебышева I, II родов.

6.  Какой многочлен является решением задачи минимизации чебышевской нормы многочлена на отрезке с единичным старшим коэффициентом фиксированной степени?

7.  Подпространства Крылова, метод сопряженных градиентов для систем с положительно определенной симметричной матрицей. Связь с методом Ланцоша.

8.  Метод минимальных невязок, геометрическая и алгебраическая версии. Связь с методом Арнольди.

9.  Спектральная теория сходимости Крыловских методов. Обоснование сверхлинейной сходимости.

Основная литература.

«Лекции по теории аппроксимации». М.: Наука, 1965.

«Функциональный анализ и вычислительная математика». М.: Физматлит, 2000.

«Методы численного анализа». М.: Изд. центр «Академия», 2007.

Деммель Дж. «Вычислительная линейная алгебра». М.: Мир, 2001.

Saad Y. «Iterative methods for sparse linear systems». SIAM, Philadelphia, 2003.

Saad Y. «Numerical methods for large eigenvalue problems». Revised Edition, SIAM, Philadelphia, 2011.

Trefethen L. N. et al. Barycentric Remez algorithms for best polynomial approximation in the CHEBFUN system. Rep. 08/20, Oxford p. Lab., NAG. December 2008.

Gutknecht M., Trefethen L. N. Real polynomial Chebyshev approximation by the Carathéodory-Fejér method, SINUM 19(2): 358-371, 1982.

Дополнительная литература.

, Приближение функций тригонометрическими полиномами в среднем, Изв. АН СССР 10: 207-256, 1946.

Ремез численных методов чебышевского приближения. Киев, «Наукова думка», 1969.

Gutknecht M., The unsymmetric Lanczos algorithms and their relations to Padé approximation, continued fractions and the qd-algorithm, in: Proc. Copper Mountain Conf. Iter. Meth., 1990, 46pp.

Пособия и методические указания.

« Лекции по курсу «Численные методы». М.: Мехмат МГУ, 2006.

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

http://www-users. cs. umn. edu/~saad/

http://people. maths. ox. ac. uk/trefethen/