Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Численные методы линейной алгебры
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Математические и компьютерные методы решения задач естествознания
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299)

1. Дисциплина относится к базовой части ОПОП ВО (или к вариативной части ОПОП ВО, или является факультативом).

2. Входные требования для освоения дисциплины (модуля): учащиеся должны владеть знаниями по математическому анализу и линейной алгебре в объеме, соответствующем программе первого года обучения основных образовательных программ бакалавриата по укрупненным группам направлений и специальностей 01.00.00 «Математика и механика», 02.00.00 «Компьютерные и информационные науки» (или отсутствуют).

3. Результаты обучения по дисциплине (модулю), соотнесенные с требуемыми компетенциями выпускников.

Компетенции выпускников, частично формируемые при реализации дисциплины (модуля):

•	ОПК-1.Б Способность применять и адаптировать существующие математические и компьютерные методы для разработки и реализации алгоритмов решения актуальных задач в области фундаментальной и прикладной математики
•	ОПК-2.Б Способность применять и модифицировать математические модели, а также интерпретировать полученные математические результаты при решения задач в области профессиональной деятельности 
•	ПК-2.Б Способность понимать и применять в научно-исследовательской деятельности современный математический аппарат

Планируемые результаты обучения по дисциплине (модулю):
Знать:
1.	основные прямые методы решения совместных систем линейных алгебраических  уравнений;
2.	основные итерационные методы, используемые для специальных классов линейных алгебраических уравнений;
3.	основные методы   компьютерного решения задач на собственные значения матриц;
наиболее  широко используемые методы решения нелинейных уравнений и систем.
Уметь: 
1.	применять на практике подходящие прямые методы решения  совместных систем линейных уравнений;
2.	находить среди известных и применять для решения соответствующих классов линейных систем наиболее подходящие итерационные методы;
3.	решать задачи на собственные значения и  нелинейные уравнения и системы.

4. Формат обучения: лекции. 

5. Объем дисциплины (модуля) составляет 2 з.е., в том числе 36 академических часа лекций, 36 академических часов на самостоятельную работу обучающихся. 

6. Содержание дисциплины (модуля), структурированное по темам (разделам) с указанием отведенного на них количества академических часов и виды учебных занятий.
Наименование и краткое содержание разделов и тем дисциплины (модуля),

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Прямые методы линейной алгебры. Метод исключения Гаусса, LU факторизация матрицы. Трудоемкость и необходимые и достаточные условия LU факторизации. Метод Холецкого и  факторизации для симметричных матриц. Их трудоемкость. Метод блочного исключения. Обращение матрицы. Быстрое преобразование Фурье. Устойчивость вычислительных алгоритмов линейной алгебры. Метод Гаусса с выбором ведущего элемента и QR факторизация; методы вращений и отражений и их устойчивость.	26	14		14	12	
2.	Итерационные методы. Одношаговые методы. Неявные методы. Предобуславливатели. Нестационарные методы. Чебышевский итерационный метод, его скорость сходимости и устойчивость. Метод скорейшего спуска и его сходимость. Метод сопряженных градиентов и его скорость сходимости. Неполное разложение Холецкого как предобуславливатель в методе сопряженных градиентов.  	14	8		8	6	
3.	Задача на собственные значения. Степенной метод решения частной проблемы собственных значений. Метод обратных итераций. Сдвиги. Базовая версия QR алгоритма и его сходимость. Эффективная реализация QR алгоритма: приведение матрицы к верхней форме Хессенберга, использование неявных сдвигов. 	14	8	 	 8	6	
4.	Методы решения нелинейных уравнений. Метод бисекции. Метод простых итераций. Метод Ньютона и его скорость сходимости.  О методах решения систем уравнений. 	10	 6	 	6	4	
Итоговая  аттестация: письменный зачет	8				8	
Итого	72	36		36	36	

7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)

Вопросы к письменному зачету

1.	Метод исключения Гаусса.
2.	 Треугольное разложение матрицы.
3.	 -разложение матрицы.
4.	 Метод Холецкого.
5.	 Метод вращений Гивенса.
6.	 Метод отражений Хаусхолдера.
7.	 Ленточный вариант треугольного разложения.
8.	 Метод блочного исключения.
9.	 Метод Гаусса с выбором главного элемента.
10.	 Метод простых итераций для линейных систем.
11.	 Чебышевский итерационный метод.
12.	 Метод наискорейшего спуска.
13.	 Метод сопряженных градиентов.
14.	 Метод сопряженных градиентов с предобуславливателем.
15.	 Степенной метод.
16.	 Метод обратных итераций.
17.	 Итерации с отношением Рэлея.
18.	 -алгоритм.
19.	 Метод одновременных (ортогональных) итераций.
20.	 -алгоритм со сдвигом.
21.	 Метод деления отрезка пополам.
22.	 Метод простых итераций для нелинейных уравнений.
23.	 Метод Ньютона.
24.	 Метод секущих.

Сформулировать (и доказать) следующие утверждения 

1.	 Теорема единственности треугольного разложения.
2.	 Теорема существования треугольного разложения.
3.	 Теорема существования и единственности разложения Холецкого.
4.	 Теорема единственности -факторизации.
5.	 Теорема об относительной погрешности при возмущении матрицы и  правой части.
6.	 Теорема о сходимости метода наискорейшего спуска.
7.	 Теорема о сходимости метода сопряженных градиентов.
8.	 Теорема о невязках в методе сопряженных градиентов.
9.	 Лемма о связи невязок и векторов спуска в методе сопряженных градиентов.
10.	 Теорема о канонической форме Шура (формулировка).
11.	 Теорема о вещественной канонической форме Шура (формулировка).
12.	 Теорема о сходимости степенного метода.
13.	 Теорема об ортогональном подобии матрице Хессенберга.
14.	Теорема об инвариантности формы Хессенберга при -итерациях.
15.	Теорема о сходимости одновременных итераций.
16.	 Теорема о сходимости метода простых итераций для нелинейного уравнения.
17.	Теорема о сходимости метода Ньютона.
18.	 Теорема об апостериорной оценке в методе Ньютона.
19.	 Априорная оценка для метода секущих.
20.	 Оценка скорости сходимости метода секущих с произвольного начального приближения. 

  Дать определение следующих объектов 

1.	 Матрица вращения.
2.	 Матрица отражения.
3.	 Ленточная матрица.
4.	 Полуширина ленточной матрицы.
5.	 Число обусловленности матрицы.
6.	 Матрица перестановок.
7.	 Многочлены Чебышева первого рода.
8.	 Невязка.
9.	 -сопряженные векторы.
10.	 Предобуславливатель.
11.	 Подобные матрицы.
12.	 Ортогонально подобные матрицы.
13.	 Каноническая форма Шура.
14.	 Вещественная каноническая форма Шура.
15.	 Отношение Рэлея.
16.	 Матрица подобия.
17.	 Матрица Хессенберга.
18.	 Подпространство Крылова.

Задачи 
1.	Доказать, что произведение нижних треугольных матриц есть нижняя треугольная матрица.
2.	Доказать, что обратная к невырожденной нижней треугольной матрице есть нижняя треугольная матрица.
3.	Доказать, что произведение верхних треугольных матриц есть верхняя треугольная матрица.
4.	Доказать, что для построения разложения Холецкого требуется                             
      операций умножения, деления и извлечения корня.
5.	Вывести формулы для вычисления элементов матриц из -разложения матрицы  при условии, что  а diag. 
6.	 Пусть   – невырожденная трехдиагональная матрица. Какова трудоемкость вычисления  ?
7.	Вывести формулы для вычисления элементов матрицы, получающейся из матрицы  после обращения в нуль всех элементов первого столбца, за исключением первого, методом вращений.
8.	Доказать, что для построения -факторизации матрицы  при помощи метода вращений требуется   действий умножения.
9.	Доказать, что для построения -факторизации матрицы с полушириной ленты  требуется 
                                
     операций умножения и деления.
10.	 Доказать, что матрица перестановок является ортогональной.
11.	 Вывести формулы для элементов матриц и из треугольного разложения если 
а) diag,  
     б) diag
12.	 Вывести формулы прямой и обратной подстановок.
13.	 Вывести формулы для элементов множителя Холецкого, если . Выписать формулы прямой и обратной подстановок.
14.	 Найти треугольное разложение матрицы                                        .
 
15.	 Найти множители Холецкого следующих матриц
16.	Построить матрицу отражений, переводящую вектор  в вектор,  коллинеарный вектору.

17.	Построить матрицу отражений, переводящую вектор  (при ) в вектор, коллинеарный вектору .
18.	Построить матрицу отражений, переводящую вектор  в вектор, коллинеарный ,       .
19.	Построить такую матрицу вращений , что , где  - верхняя треугольная матрица, а .
20.	Доказать, что 
      а)  
      б)  
      в)  
    Привести примеры векторов , на которых достигаются  соответствующие равенства.
21.	. Доказать, что если , то   можно принять за   норму вектора . Найти постоянные эквивалентности в соотношениях, связывающих эту норму с .
22.	Найти квадратный корень из матрицы , если . 
23.	 Пусть const >0, . Методом простых итераций решить систему 
  
При каких 	ограничениях на  метод сходится? При каком   сходимость наилучшая? Существенно ли предположение ?
24.	Найти оптимальное значение итерационного параметра в методе простых итераций при решении системы с матрицей
                                              .
25.	При каких  и  сходится метод простых итераций, если 
                              ?
26.	Степенным методом найти -е приближение к максимальному по  модулю собственному значению и соответствующему нормированному собственному вектору матрицы
                                                  .
27.	Степенным методом найти -е приближение к максимальному по модулю собственному значению и соответствующему нормированному собственному вектору матрицы
                                                    .
Примеры зачетных билетов.

Пример 1.
1.	Изложить степенной метод. Указать задачу, для решения которой метод  предназначен. Сформулировать утверждение о сходимости.
2.	Доказать теорему о сходимости метода наискорейшего спуска.
3.	Дать определение ленточной матрицы.
4.	Доказать, что обратная к невырожденной нижней треугольной матрице есть нижняя треугольная матрица.

Пример 2.

1.	Изложить чебышевский итерационный метод. Указать задачу, для решения которой метод  предназначен. Привести оценку скорости сходимости.
2.	Доказать теорему о единственности треугольного разложения.
3.	Дать определение матрицы Хессенберга.
4.	Доказать, что произведение верхних треугольных матриц есть верхняя треугольная матрица.  
  
ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) дисциплине (модулю)

Оценка
РО и
соответствующие виды оценочных средств 	незачет	зачет	
Знания
Письменный зачет	Отсутствие достаточного количества знаний	Приемлемое количество знаний	
Умения
Письменный зачет 	Отсутствие достаточного количества умений	Приемлемое количество умений	

Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)
	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	основные методы решенияобщих и некоторых специальных СЛАУ;
2.	основные явные и предобусловленные итерационные методы решения СЛАУ;
3.	основные методы решения частной и полной задач на собственные значения.

Уметь: 
1.	применять на практике подходящие методы решения СЛАУ;
2.	решать задачи на собственные значения;
3.	решать нелинейные уравнения и системы.	

ОПК-1.Б	
8. Ресурсное обеспечение:
Основная литература:

1.	В.Б. Андреев Численные методы. М.: МАКС Пресс. 2013.
2.	А.А. Самарский, А.В. Гулин. Численные методы. М.: Наука. 1989.
3.	Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. М.:  Наука. 1989. 
             Дополнительная литература

1.	Дж. Деммель. Вычислительная линейная алгебра. Теория и приложения. М.: Мир. 2001.
2.	Е.Е. Тыртышников. Методы численного анализа. М.: Издательский центр «Академия». 2007.
3.	Д. Уоткинс. Основы матричных вычислений. М.: БИНОМ. Лаборатория знаний. 2006.

Материально-техническкое обеспечение: наличие литературы в библиотеке учебных пособий.   
аудитория с партами и меловой доской. 

9. Язык преподавания - русский.

10. Преподаватели: профессор факультета ВМК МГУ В.Б. Андреев

11. Автор программы:  профессор факультета ВМК МГУ В.Б. Андреев.