«Утверждаю»
	Председатель Ученого совета математико-механического факультета СПбГУ, декан математико-механического факультета СПбГУ профессор Леонов Г.А. ________________ «10» мая 2012 г.

Программа вступительного экзамена

по специальности научных работников

01.01.07

«Вычислительная математика»
«Теория приближенных вычислений»

Утверждена на заседании Ученого совета математико-механического факультета СПбГУ, протокол № 5 от 10.05.2012.

Санкт-Петербург

2012
Специализация «Параллельные алгоритмы»
Математическая физика
1. Линейные операторы и функционалы. Теорема Хана - Банаха.

2. Нормированные пространства. Основные определения и свойства.

Гильбертово пространство.

3. Линейные операторы и функционалы в гильбертовом пространстве.

4. Интегральное представление функционалов в пространствах

измеримых функций.

5. Компактные операторы.

6. Сопряжённое уравнение. Теорема об обратном операторе.

7. Функциональное уравнение 2-го рода. Спектр. Резольвента.

8. Альтернатива Фредгольма.

9. Положительно определенные операторы.

10. Функционал энергии и задача об его минимуме.

11. Простейшая краевая задача для обыкновенного линейного дифференциального оператора.

12. Собственный спектр положительно определенных операторов /понятие о спектре, собственные числа и элементы/.

13. Разложение по собственному спектру положительно определенного

оператора.

14. Задача Штурма - Лиувилля.

15. Дифференциальные уравнения 2-го порядка, краевые условия и краевые задачи. Задача Коши, проблема существования и единственности решения.

16. Решения из класса обобщенных функций.

Сингулярные решения уравнений 2-го порядка.

17. Задачи Дирихле и Неймана.

18. Вариационный метод.

19. Уравнение теплопроводности, волновое уравнение.

20. Метод итерации. Теорема о сжатых отображениях.

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

22. Решение системы алгебраических уравнений методами исключений.

23. Оценки погрешности приближенного решения системы.

24. Итерационный метод нахождения собственных значений

и собственных векторов матриц.

25. Интерполирование. Погрешность, конечные разности.

26. Формулы Лагранжа и Ньютона.

Функциональный анализ
27. Комплексное гильбертово пространство.

Изоморфизм сепарабельных гильбертовых пространств.

28. Ортогональные системы в гильбертовых пространствах.

Неравенство Бесселя. Замкнутость и полнота. Ортогональные разложения.

29. Линейные функционалы. Слабая сходимость. Теорема Рисса.

Слабая компактность.

30. Непрерывные полуторалинейные функционалы и операторы.

Инволюция. Самосопряженность.

31. Сходимость операторных последовательностей

(сильная, слабая, поточечная). Непрерывность линейных операций.

32. Конечномерные и компактные операторы. Определения.

Свойство конечномерной аппроксимации. Операторы Гильберта - Шмидта.

33. Операторы проектирования. Алгебра проекторов.

Последовательности проекторов.

Вычислительные методы

34. Машинные представления действительного числа.

Влияние формы представления на вычислительный процесс.

35. Задачи линейной алгебры. Понятие о псевдорешении.

36. Гладкая аппроксимация и интерполяция.

Сплайны Шонберга. Минимальные сплайны.

37. Производная нелинейной операции. Метод Ньютона.

38. Вторая производная нелинейной операции.

Скорость сходимости метода Ньютона.

39. Вычисление многократных интегралов.

Кубатурные формулы. Метод Монте-Карло.

40. Метод последовательных приближений для интегральных уравнений.

41. Метод механических квадратур. Метод моментов.

42. Некорректные задачи. Постановки Адамара и Тихонова,

понятие о регуляризаторе.

43. Некорректная задача для интегрального уравнения первого рода.

44. Вариационный метод. Абстрактная схема.

45. Метод Ритца дли задачи Дирихле

46. Вариационно - сеточные методы. Оценка сходимости.

47. Сеточные методы. Постановка задачи. Аппроксимация, сеточный шаблон.

48. Устойчивость и сходимость. Теорема о порядке сходимости на решении.

49. Нестационарная задача. Оценка сходимости.

50. Задача Коши. Периодические решения. Условие Неймана.

51. Задача линейного программирования.

Понятие вершины. Базисные переменные.

52. Симплекс-метод для задач линейного программирования.

Теория сплайнов и распараллеливание

53. 
    Интерполяция и аппроксимация функций. Интерполяция Лагранжа, Эрмита, Эрмита-Биркгофа. Интерполяционные полиномы.
    
54. 
    Нахождение неточно заданной входной информа-ции и исправление. Влияние округления при вычислениях на ЭВМ
    

55. Приближение различными типами сплайнов.

56. Эрмитовы кубические сплайны. В-сплайны. Минимальные сплайны.

57. Минимальные лагранжевы сплайны. Аппроксимационные тождества.

58. Обработка информации с помощью сплайнов

59. Применение минимальных сплайнов для сжатия

и восстановления числовых потоков,

60. Применение к решению задач математической физики и

распараллеливание.

61. Решение краевых задач вариационно-разностным методом.

Устойчивость вычислений. Приближения в комплексной области.

Теория всплесков и цифровые фильтры
62. О понятии "всплеск". Цифровые фильтры. Быстрое дискретное

преобразование Фурье

63. Обработка сигналов и изображений. Естественная параллельная

структура всплесковых преобразований

64. Кратно-масштабное уравнение и масштабирующая функция.

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

66. Переход от одного базиса к другому. Формулы декомпозиции и

реконструкции

67. Ортовсплески в ортогональном разложении

цепочки вложенных пространств. Кратно-масштабный анализ.

68. Образующие минимальные сплайны. Пространства минимальных

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

69. Псевдосвертка и калибровочное соотношение. Цепочки приведенных сплайнов.

70. Формулы декомпозиции и реконструкции и их

распараллеливание. Распараллеливание всплесковой фильтрации сигнала

71. О построении вейвлетного разложения на неравномерной сетке

Литература

[1] Л.В.Канторович, Г.П.Акилов. Функциональный анализ. Наука.1977

(главы 1,2,4-7,9,11,12-14,17,18).

[2] А.Я.Хелемский. Лекции по функционаьному анализу. М.: МЦНМО,

2004. 552 с.

[3] С.Г.Михлин. Линейные уравнения в частных производных. Высшая школа. 1977

(главы 1-5,8-12,14,15,17,18,20-24).

[4] И.П.Мысовских. Лекции по методам вычислений. СПб. 1998.

[5] И.К.Даугавет. Введение в келассическую теори приближения

функций. СПб. 2011. 232 с.

[6] С.В.Яхонтов, Н.К.Косовский, Т.М.Косовская. Эффективные по

времени и памяти алгоритмические приближения чисел и функций.

СПб. 2012. 256 с.

[7] С.Г.Михлин. Вариационные методы в математической физике. 1970. 512 с.

[8] И.Г.Бурова, Ю.К.Демьянович. Теория минимальных сплайнов и их приложения. СПб.: Издательство С.-Петербургского университета, 2010. 364 с.

[9] Yukiya Aoyama, Jun Nakano. RS/6000 SP: Practical MPI Programming. IBM. Technical Sup-port Organization. 2000. 221 p.

www.redbook.ibm.com, 2003.

[10] И.Добеши. Десять лекций по вейвлетам. Ижевск: НИЦ "Регулярная и хаотическая динами-ка". 2001. 464 с.

[11] Ю.К.Демьянович. Минимальные сплайны \& всплески СПб. 2003. 200 с.

[12] Ю.К.,Демьянович, И.Г.Бурова и др. Параллельные алгоритмы. Разработка и реализация. М., 2012. 344 с.

Специализация «Статистическое моделирование»

1.ТЕОРИЯ ВЕРОЯТНОСТЕЙ

1.Случайные события и их вероятности

Аксиомы теории вероятностей. Вероятность и ее свойства.

Распределение, функция распределения, плотность распределения.

Их свойства. Типы распределений.

2.Числовые характеристики случайных величин.

Математическое ожидание и его свойства.

Моменты случайных величин.

Неравенство Чебышева и Йенсена.

Корреляционная матрица и ее свойства.
3. Характеристические функции

Многомерное нормальное распределение.

4. Сходимость случайных величин

Типы сходимости и связь между ними.

Слабая сходимость распределений .

Слабый закон больших чисел.

Центральная предельная теорема.
5. Последовательность независимых случайных величин

Закон нуля и единицы.

Неравенство Колмогорова.

Усиленный закон больших чисел.

6. Дискретные цепи Маркова

Классификация марковских цепей.

Матрица перехода и ее свойства.

Теорема о предельном поведении переходных вероятностей в марковской цепи.

7. Условные вероятности и условные математические ожидания.
II. МАТЕМАТИЧЕСКАЯ СТАТИСТИКА
1. Основные понятия.

Гистограммы. Числовые характеристики реальных данных.

Генеральная и выборочная совокупности.

Функция правдоподобия.

Статистики. Достаточные статистики.
2. Принцип выбора точечных оценок.

Эффективность, несмещенность, состоятельность.

Неравенство Рао-Крамера.

Свойство выборочных характеристик.

3. Методы построения точечных оценок.

Метод моментов.

Метод максимального правдоподобия. Свойства оценок.

Метод наименьших квадратов. Свойства оценок.

4. Построение доверительных интервалов.

Построение доверительных интервалов для параметров нормального распределения.

5. Проверка статистических гипотез.

Общая проверка гипотез.

Два рода ошибок статистических исследований.

Лемма Неймана-Пирсона.

Критерий

Гипотезы однородности, независимости, согласия.

Проверка гипотез о параметрах нормального распределения.
6. Многомерная статистика.

Регрессионный анализ (общая схема).

Частотные, множественные и канонические коэффициенты корреляции.

Метод главных компонент.

Дисперсионный анализ (однофакторная схема).
7. Планирование эксперимента.

Факторные планы: дробные реплики полного факторного плана, латинские квадраты,

сбалансированные неполноблочные планы.

Основные понятия теории планирования регрессионного эксперимента.

Теорема эквивалентности Кифера-Вольфовица.

Случайная и систематическая погрешности при неадекватности линейной модели.

Несмещенное (робастное) планирование.
III. МЕТОД МОНТЕ-КАРЛО

1. Моделирование случайных величин.

Основные методы получения псевдослучайных чисел.

Моделирование случайных величин с заданным распределением.

Понятие имитационной модели.

Моделирование марковских процессов.

2. Методы оценивания интегралов.

3. Оценки по поглощению для решения интегральных уравнений.

IV. МЕТОДЫ ВЫЧИСЛЕНИЙ

1. Действия с приближенными величинами.

2. Решение алгебраических уравнений.

3. Решение систем линейных уравнений.

Метод исключения Гаусса.

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

4. Задача интерполирования. Интерполяционный многочлен Лежандра.

5. Численное дифференцирование и интегрирование.

6. Решение обыкновенных дифференциальных уравнений.

Метод Рунге-Кутта.

7. Вопросы общей теории решения дифференциальных и интегральных уравнений.

Основные понятия. Теорема о близких уравнениях. Теорема сходимости.

8. Решение интегральных уравнений.

Методы замены ядра на вырожденное.

Метод механических квадратур.

9. Решение дифференциальных уравнений.

Проекционные методы.

Метод Галеркина для уравнений II-рода.

Метод Ритца.

10.Метод сеток решения задач математической физики.

ЛИТЕРАТУРА

1. 
   Ширяев А.Н. Вероятность. М., МЦНМО, 2007.
   
2. 
   Боровков А.А. Теория вероятностей. М., Либроком, 2009.
   
3. 
   Феллер В. Теория вероятностей и ее приложения. т. 1,2 - М.:Мир, 1984.
   
4. 
   Биллингсли Л. Сходимость вероятностных мер. М., Наука, 1981.
   
5. 
   Ермаков С.М., Михайлов Г.А. Статистическое моделирование. М., Наука, 1982.
   
6. 
   Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 1983.
   
7. 
   Ивченко Г.И., Медведев Ю.И. Введение в математическую статистику. М.: ЛКИ, 2010.
   
8. 
   Крамер Г. Математические методы в статистике. М., РХД, 2003.
   
9. 
   Кендалл М., Стьюарт А.Г. Статистические выводы и связи. М.: Наука, 1973.
   
10. 
    Рао С. Линейные статистические выводы. М.: Наука, 1968.
    
11. 
    Дрейпер Н., Смит Г., Прикладной регрессионный анализ. Множественная регрессия. М.Диалектика, 2011.
    
12. 
    Леман Э. Проверка статистических гипотез. М., Наука, 1979.
    
13. 
    Ермаков С.М., Жиглявский А.А. Математическая теория оптимального эксперимента. М., Наука, 1987.
    
14. 
    Сидняев Н.И., Вилисова Н.Т. Введение в теорию планирования эксперимента, М: МГТИ, 2011.
    
15. 
    Мысовских И.П. Лекции по методам вычислений, СПб, Изд-во С.-Петербургского университета, 1998.
    
16. 
    Хакимзянов Г. С., Черный С. Г. Методы вычислений: В 4 ч. Новосибирск: НГУ, 2003
    
17. 
    Березин И.С., Жидков М.В. Методы вычислений. М., Физматгиз, 1962.
    
18. 
    Канторович А.В., Акилов Г.П. Функциональный анализ. BHV-Санкт-Петербург, Невский Диалект, 2004.
    
19. 
    Михлин С.Г. Вариационные методы в математической физике. М., Наука, 1970.
    
20. 
    Годунов С.К., Рябенький В.С. Разностные схемы. Введение в теорию. М., Наука, 1977.
    
21. 
    Васильев Ф.П. Методы решения экстремальных задач. М., Наука,1981.
    
22. 
    Карманов В.Г. Математическое программирование. М., Наука, 1985.
    
23. 
    Жиглявский А.А. Математическая теория глобального случайного поиска. Л., ЛГУ, 1985.
    
24. 
    Ермаков С.М. Метод Монте-Карло в вычислительной математике. Вводный курс. - СПб.: Невский Диалект, М.: Бином. Лаборатория знаний, 2009, 192 с.
    

Специализация «Вычислительная математика» и «Исследование операций»
I. Функциональный анализ.
1. Топологические и метрические пространства.
Общие сведения о множествах. Полнота и сепарабельность. Компактность в метри-

ческих пространствах.

2. Векторные пространства.
Основные определения. Линейные операторы и функционалы. Выпуклые множества и

полунормы. Теорема Хана-Банаха.

3. Нормированные пространства.
Основные определения и свойства. Нормированные пространства измеримых функций

и последовательностей. Гильбертово пространство.

4. Линейные операторы и функционалы.
Пространство операторов и сопряженное пространство. Функционалы и операторы в

конкретных пространствах. Линейные операторы и функционалы в гильбертовом про-

странстве. Распространение линейных операторов. Последовательность линейных опе-

раторов. Основные теоремы. Некоторые приложения к теории функций.

5. Компактные и сопряженные операторы.
Компактные множества в нормированных пространствах. Компактные операторы.

Сопряженные операторы. Компактные соамосопряженные операторы в гильбертовом

пространстве. Интегральное представление самосопряженного оператора.
6. Интегральные операторы.
Интегральное представление операторов. Операторы в пространствах последователь-

ностей и в пространствах функций. Теоремы вложения Соболева.

7. Функциональные уравнения.
Сопряженное уравнение. Уравнения с компактным ядром. Спектр. Резольвента. Аль-

тернатива Фредгольма. Применение к интегральным уравнениям.

8. Общая теория приближенных методов.
Общая теория уравнений второго рода. Уравнения, приводящиеся к уравнениям второ-

го рода. Применения к бесконечным системам уравнений, к интегральным и диффе-

ренциальным уравнениям.
9. Дифференцирование нелинейных операторов. Теорема о неявной функции. Метод

Ньютона и его применение к конкретным функциональным уравнениям.

II. Уравнения математической физики.
1. Интегралы, зависящие от параметра.

2. Средние функции и обобщенные производные.

3. Пространства функций с обобщенными производными.
4. Положительно определенные операторы.
5. Собственный спектр положительно определенного оператора.
6. Уравнения и краевые задачи.
7. Характеристики. Канонический вид. Формулы Грина.
8. Обобщенные решения дифференциальных уравнений.
9. Уравнение Лапласа и гармонические функции.
10. Задачи Дирихле и Неймана.
11. Теория потенциала. Интегральные уравнения теории потенциала.
12. Вариационный метод. Слабые решения.
13. Спектр задач Дирихле и Неймана.
14. Уравнение теплопроводности и задача Коши для него.
15. Волновое уравнение и задача Коши для него.
16. Метод Фурье.

III. Численные методы.

1. 
   Численное решение нелинейных уравнений и систем нелинейных уравнений.
   
2. 
   Решение систем линейных алгебраических уравнений.
   
3. 
   Вычисление собственных значений и собственных векторов матриц.
   
4. 
   Интерполирование. Алгебраическое интерполирование. Тригонометрическое интер-
   

полирование. Эрмитово интерполирование. Алгебраические многочлены наилучшего

равномерного приближения.

5. Численное интегрирование.
6. Решение обыкновенных дифференциальных уравнений.
7. Решение дифференциальных уравнений в частных производных.
8. Решение интегральных уравнений второго рода.


Литература

1. 
   Канторович Л.В., Акилов Г.П. Функциональный анализ. 1977.
   Часть 1, главы 1. 2. 4-7, 9, 11.
   Часть 2, главы 12-14, 17, 18
   (или соответствующие главы из других изданий этой книги)
   
2. 
   Михлин С.Г. Линейные уравнения в частных производных. 1977.
   Главы 1-5, 8-12, 15, 17, 18, 20-24.
   
3. 
   Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы высшей математики. Минск. Т.1, 1972. Т.2, 1975.
   Глава 1.
   

Глава 2: §§ 2.1, 2.2, 2.3, 2.6
Глава 3: §§ 3.1, 3.2, 3.5, 3.6
Глава 4: §§ 4.1-4.5
Глава 5: §§ 5.1-5.6, 5.11
Главы 6, 7, 8

4. 
   Бирман М.Ш., Соломяк М.З. Спектральная теория самосопряженных операторов в гильбертовом пространстве. 2010.
   
5. 
   Уоткинс Д. Основы матричных вычислений. 2006.
   
6. 
   Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. 2002.
   
7. 
   Даугавет И.К. Теория приближенных методов. Линейные уравнения. 2006.
   

Даугавет И.К. Введение в классическую теорию приближения функций. 2011.