МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«НОВОСИБИРСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

(НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ, НГУ)

УТВЕРЖДАЮ

_ «_»2014 г.

Рабочая программа дисциплины Вычислительные методы анализа и линейной алгебры Направление подготовки 010400 – Прикладная математика и информатика 010800 – Механика и математическое моделирование Квалификация (степень) выпускника Бакалавр Форма обучения Очная Новосибирск Аннотация рабочей программы Дисциплина «Вычислительные методы анализа и линейной алгебры» входит в Базовую часть Профессионального цикла ООП по направлениям подготовки «010400 – Прикладная математика и информатика», «010800 – Механика и математическое моделирование», все профили подготовки. Дисциплина реализуется в течение 3-го и 4-го семестров обучения на механико-математическом факультете Новосибирского государственного университета кафедрой математического моделирования ММФ НГУ.

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

Дисциплина «Вычислительные методы анализа и линейной алгебры» нацелена на формирование общекультурных компетенций ОК-1, ОК-7, ОК-9, ОК-10, ОК-11, ОК-14, ОК-15 и ОК-16 в рамках специальности. Одновременно эта дисциплина способствует формированию профессиональных компетенций ПК-1, ПК-2, ПК-3, ПК-4, ПК-5, ПК-6, ПК-7, ПК-8, ПК-9, ПК-10, ПК-11, ПК-12.

Преподавание дисциплины «Вычислительные методы анализа и линейной алгебры»

предусматривает следующие формы организации учебного процесса: лекции, семинарские практические занятия, занятия по практике на ЭВМ в компьютерном классе, самостоятельная (индивидуальная и, возможно, групповая) работа студентов.

Программой дисциплины предусмотрены следующие формы текущего и промежуточного контроля знаний: контрольные работы, самостоятельные и индивидуальные работы. Рубежный контроль осуществляется в форме экзамена. Кроме того, составной частью курса является предмет «Вычислительная практика на ЭВМ», продолжающийся в течение 3-го и 4-го семестров обучения. По нему предусмотрен текущий контроль в виде оценок за отдельные сданные задания и рубежный контроль в виде дифференцированного зачёта за каждый семестр (всего 2 дифференцированных зачёта).

Общая трудоемкость дисциплины составляет 252 академических часа (из них аудиторных), 7 зачётных единиц, 1 экзамен, 2 дифференцированных зачёта.

1. Цели освоения дисциплины.

Дисциплина «Вычислительные методы анализа и линейной алгебры» предназначена для студентов второго курса механико-математических факультетов университетов.

Главной целью освоения дисциплины является знакомство студентов с основами классических и современных вычислительных методов и конструктивных подходов к решению математических задач. Это включает изучение численных методов для решения ряда типовых задач анализа и линейной алгебры, вопросов теоретического обоснования этих методов и их реализации на цифровых ЭВМ, а также приобретение практических навыков их использования. Помимо большого самостоятельного значения в подготовке математиков-прикладников осваиваемый материал является основой для изучения дальнейших математических дисциплин – численных методов решения дифференциальных и интегральных уравнений, математического моделирования, математической статистики и методов обработки данных, оптимизации и оптимального управления, исследования операций и системного анализа, теории принятия решений. Студенты должны усвоить базовые понятия, лежащие в основе вычислительной математики, знать их взаимосвязи, уметь доказывать их свойства, применять их на практике, получить базу для дальнейшего самостоятельного освоения и применения современных вычислительных методов. Немаловажное значение имеет также расширение математического кругозора и повышение уровня математической культуры.

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

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

В первой части данный курс знакомит студентов с вычислительными методами анализа, под которыми понимаются методы решения задач интерполирования, приближения функций (теории аппроксимации), методы численного дифференцирования и методы вычисления определённых интегралов. По существу, эта часть курса является продолжением классического курса математического анализа. Вторая часть курса включает в себя вычислительные методы линейной алгебры, т.е. задачи решения систем линейных алгебраических уравнений (СЛАУ), вычисления определителей матриц и обратных матриц, а также введение в методы решения проблемы собственных значений для матриц. В этой части курс существенно дополняет и расширяет знания, полученные при изучении курса алгебры. На практических занятиях у студентов формируются навыки работы с понятийным аппаратом и умение использовать общие принципы и методы при решении конкретных математических задач. Практические занятия на ЭВМ органично дополняют семинарские занятия и служат закреплению пройденного.

2. Место дисциплины в структуре ООП бакалавриата.

Дисциплина «Вычислительные методы анализа и линейной алгебры» является частью математического цикла ООП по направлению подготовки «010400 – Прикладная математика и информатика», все профили подготовки.

Дисциплина «Вычислительные методы анализа и линейной алгебры» опирается на следующие дисциплины данной ООП:

Математический анализ (дифференциальное и интегральное исчисления);

Высшая алгебра (главным образом, линейная алгебра);

Аналитическая геометрия;

Теория алгоритмов;

Программирование;

Основы работы на ЭВМ.

Результаты освоения дисциплины «Вычислительные методы анализа и линейной алгебры» используются в следующих дисциплинах данной ООП:

Математическое моделирование;

Методы вычислений (численные методы решения дифференциальных уравнений);

Математическая статистика;

Обратные и некорректные задачи;

Дополнительные главы вычислительной математики;

Методы оптимизации и оптимального управления;

Исследование операций и теория принятия решений.

Особенностью дисциплины «Вычислительные методы анализа и линейной алгебры» является её существенно синтетический характер, значительная опора на предшествующие курсы алгебры, анализа и пр., и в то же время продолжение этих курсов на новом предметном и теоретическом уровне.

3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Вычислительные методы анализа и линейной алгебры».

Освоение дисциплины является вкладом в формирование следующих общекультурных компетенций:

способностью владеть культурой мышления, умение аргументированно и ясно строить устную и письменную речь (ОК-1);

способностью владеть одним из иностранных языков на уровне не ниже разговорного (ОК-7);

способностью осознать социальную значимость своей будущей профессии, обладать высокой мотивацией к выполнению профессиональной деятельности (ОК-9);

способностью и готовностью к письменной и устной коммуникации на родном языке (ОК-10);

способностью владения навыками работы с компьютером как средством управления информацией (ОК-11);

способностью использовать в научной и познавательной деятельности, а также в социальной сфере профессиональные навыки работы с информационными и компьютерными технологиями (ОК-14);

способностью работы с информацией из различных источников, включая сетевые ресурсы сети Интернет, для решения профессиональных и социальных задач способностью к интеллектуальному, культурному, нравственному, физическому и профессиональному саморазвитию, стремление к повышению своей квалификации и мастерства (ОК-16).

Вместе с тем, дисциплина «Вычислительные методы анализа и линейной алгебры»

нацелена на формирование следующих профессиональных компетенций в рамках специальности:

способностью демонстрации общенаучных базовых знаний естественных наук, математики и информатики, понимание основных фактов, концепций, принципов теорий, связанных с прикладной математикой и информатикой (ПК-1);

способностью приобретать новые научные и профессиональные знания, используя современные образовательные и информационные технологии (ПК-2);

способностью понимать и применять в исследовательской и прикладной деятельности современный математический аппарат (ПК-3);

способностью в составе научно-исследовательского и производственного коллектива решать задачи профессиональной деятельности (ПК-4);

способностью критически переосмысливать накопленный опыт, изменять при необходимости вид и характер своей профессиональной деятельности (ПК-5);

способностью осуществлять целенаправленный поиск информации о новейших научных и технологических достижениях в сети Интернет и из других источников способностью собирать, обрабатывать и интерпретировать данные современных научных исследований, необходимые для формирования выводов по соответствующим научным, профессиональным, социальным и этическим проблемам способностью формировать суждения о значении и последствиях своей профессиональной деятельности с учетом социальных, профессиональных и этических позиций (ПК-8);

способностью решать задачи производственной и технологической деятельности на профессиональном уровне, включая: разработку алгоритмических и программных решений в области системного и прикладного программирования (ПК-9);

способностью применять в профессиональной деятельности современные языки программирования и языки баз данных, операционные системы, электронные библиотеки и пакеты программ, сетевые технологии (ПК-10);

способностью приобретать и использовать организационно-управленческие навыки в профессиональной и социальной деятельности (ПК-11);

способностью составлять и контролировать план выполняемой работы, планировать необходимые для выполнения работы ресурсы, оценивать результаты собственной работы (ПК-12).

В результате освоения дисциплины обучающийся должен:

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

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

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

4. Структура и содержание дисциплины Общая трудоемкость дисциплины составляет 7 зачётных единиц, 252 часа. Структура и содержание дисциплины показаны в таблице (без вычислительной практики на ЭВМ):

1.1 Задача алгебраической интерполяции, су- 3 1 2 2 ществование и единственность её решения.

Интерполяционный полином Лагранжа.

Разделённые разности и их свойства. Интерполяционный полином Ньютона.

1.2 Оценка погрешности алгебраической ин- 3 2 4 2 терполяции с простыми узлами. Полиномы Чебышёва, их свойства и применение в интерполировании.

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

Примеры Бернштейна и Рунге. Теорема Фабера и теорема Марцинкевича, их значение для теории интерполяции.

Понятие о сплайне. Степень сплайна, его дефект. Интерполяционный кубический сплайн и его построение.

Задача численного дифференцирования:

интерполяционный подход, метод неопределённых коэффициентов. Оценка погрешности формул численного дифференцирования и поведение полной погрешности.

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

Задача численного интегрирования, квадратурные формулы. Интерполяционные квадратурные формулы, квадратуры Ньютона-Котеса. Квадратурные формулы прямоугольников, трапеций и Симпсона. Составные квадратурные формулы.

Гаусса, выбор узлов для них. Примеры квадратурных формул Гаусса. Погрешность квадратур Гаусса.

2.1 Сингулярные числа и сингулярные векторы 3 8 4 2 матриц. Спектральный радиус матрицы.

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

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

2.2 Метод Гаусса для решения систем линей- 3 9 2 2 ных алгебраических уравнений, его матричная интерпретация. Выбор ведущего элемента. LU-разложение матрицы, связь с методом Гаусса для решения СЛАУ.

2.3 Поведение числа обусловленности при мат- 3 10 4 2 ричных преобразованиях, мотивация применения ортогональных матриц при решении СЛАУ.

Ортогональные матрицы вращений и отражений. Метод Хаусхолдера (отражений) для решения систем линейных уравнений.

2.4 Метод Холесского для решения систем ли- 3 11 2 2 нейных уравнений.

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

2.5 Итерационные методы решения систем ли- 3 12 4 2 нейных алгебраических уравнений. Необходимые и достаточные условия сходимости стационарных одношаговых итерационных методов.

2.6 Способы подготовки системы линейных 3 13 2 2 уравнений к итерационному решению:

предобуславливание и расщепление матрицы системы. Оптимизация простейшего скалярного предобуславливателя.

2.7 Итерационный метод Якоби, условия его 3 14 4 2 сходимости. Сходимость метода Якоби для линейных систем с диагональным преобладанием.

Итерационный метод Гаусса-Зейделя, условия его сходимости. Сходимость метода Гаусса-Зейделя для линейных систем с диагональным преобладанием.

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

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

Теорема Гершгорина. Круги Гершгорина.

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

Метод вращений Якоби для решения симметричной матричной проблемы собственных значений.

QR-алгоритм для решения проблемы собственных значений. Характер его сходимости.

Применение сдвигов. Хессенбергова форма матрицы, её применение в QR-алгоритме.

5. Образовательные технологии Основной образовательной технологией, используемой в курсе «Вычислительные методы анализа и линейной алгебры», является традиционная лекционно-семинарская система обучения, дополненная занятиями по практике на ЭВМ по изученному материалу в течение 3-го и 4-го семестров. При этом практика на ЭВМ органично включает также элементы индивидуального обучения и, для наиболее успевающих студентов, опережающей самостоятельной работы. Цель семинарских практических занятий состоит в выработке устойчивых навыков решения ряда типовых задач и практическом освоении теории, сообщаемой в лекциях. На этих занятиях рекомендуется проведение двух контрольных работ в течение 3-го семестра. Для итоговой проверки уровня знаний студентов и их аттестации в конце 3-го семестра проводится экзамен по дисциплине.

На семинарских занятиях и на занятиях практики на ЭВМ предусмотрены активные и интерактивные формы проведения занятий в виде разбора конкретных задач и ситуаций, а также компьютерные демонстрации работы вычислительных методов и результатов решения типовых задач. При этом суммарный удельный вес активных форм обучения в представленном плане аудиторных занятий по дисциплине «Вычислительные методы анализа и линейной алгебры» составляет не менее 50% (что складывается из примерно 60% времени семинарских занятий + большая часть занятий практики на ЭВМ).

Для наглядного графического вывода результатов выполнения заданий практики на ЭВМ предусмотрено использование популярных свободно распространяемых программных продуктов Scilab, Octave и/или Gnuplot (конкретный выбор осуществляется по желанию преподавателя и студентов). Особенно следует отметить здесь Scilab – некоммерческий пакет компьютерной математики, сочетающий в себе мощные средства построения двумерных и трехмерных графиков с Matlab-подобным языком программирования высокого уровня, имеющим встроенные функции для решения ряда математических задач. Он имеет русскую локализацию интерфейса верхнего уровня и, в принципе, может выступать даже языком реализации заданий практики на ЭВМ.

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

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

1. Оценить трудоёмкость (количество арифметических операций) построения интерполяционного полинома в форме Лагранжа. Оцените трудоёмкость вычисления его 2. Оценить трудоёмкость (количество арифметических операций) построения интерполяционного полинома в форме Ньютона. Оцените трудоёмкость вычисления его 3. Сравнить трудоёмкости пересчета интерполяционных полиномов в форме Лагранжа и в форме Ньютона при добавлении нового интерполяционного узла. Сделать то же самое для случая удаления интерполяционного узла.

4. С какой точностью можно вычислить с помощью интерполяционной формулы Лагранжа для функции, выбрав узлы интерполирования, 5. Оценить максимальную погрешность кусочно-линейной интерполяции функции 7. На интервале задана таблица значений функции с постоянным шагом. Значение функции в произвольной точке восстанавливается с помощью интерполяционного полинома Ньютона по трём ближайшим узлам. Каким должен быть шаг h таблицы, чтобы погрешность интерполяции не превышала 10–5?

9. Как связана проблема выбора оптимальных узлов интерполяции со свойствами полиномов, наименее уклоняющихся от нуля?

10. Как задать краевые условия для кубического сплайна по значением интерполируемой функции на сетке? Какие формулы численного дифференцирования можно применять и почему?

11. Оценить трудоёмкость (количество арифметических операций) для построения интерполяционного кубического сплайна и вычисления его значения в произвольной 12. Сплайн второй степени интерполирует таблично заданную функцию, значения которой следующие:

13. На интервале [0, 4] найти наилучшее среднеквадратичное приближение функции с помощью полинома первой степени. Найти значение среднеквадратичного отклонения от этого полинома.

14. Докажите, что все коэффициенты полиномов, ортогональных в смысле, положительны, если интервал удовлетворяет условию .

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

16. Вычислить первую и вторую производные от таблично заданной функции 17. Какая из простейших квадратурных формул Ньютона-Котеса – формула прямоугольников или формула трапеций – имеет бльшую точность?

18. Как определить, является ли квадратурная формула интерполяционной?

19. Как практически определить алгебраическую степень точности квадратурной формулы?

20. Оценить число подинтервалов равномерного разбиения исходного интервала интегрирования, которое необходимо для вычисления интеграла по составной квадратурной формуле средних прямоугольников с погрешностью =10–3.

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

22. Построить квадратурную формулу Гаусса с двумя узлами на интервале [1, 2].

23. Для приближённого вычисления интеграла постройте квадратурную формулу интерполяционного типа по узлам –1, 0 и 1.

24. Удовлетворяет ли функция на интервале [0, 1] условиям теоремы о сжимающем отображении?

25. Используя метод Ньютона для решения уравнения x2 = a, построить алгоритм для приближённого вычисления арифметического значения.

26. Докажите, что уравнение имеет единственный корень при любом вещественном.

27. Каковы константы эквивалентности для векторных норм и ? Каковы векторы, на которых они достигаются?

ранг. Показать, что выражением 29. Докажите, что спектральное число обусловленности cond2( ) не меняется при перестановке строк или столбцов матрицы.

матричной нормой, которая согласована с векторными нормами и.

31. Доказать, что для любой квадратной -матрицы имеет место неравенство 32. Для матрицы найти значения чисел обусловленности cond1( ) и сond2( ).

33. Подсчитайте количество арифметических операций при решении системы линейных алгебраических уравнений методом Гаусса без выбора ведущего элемента.

34. Подсчитайте количество арифметических операций при решении системы линейных алгебраических уравнений методом Холесского.

35. Для матрицы найдите LU-разложение и разложение Холесского.

36. Верно ли, что любую матрицу Хаусхолдера (матриц отражения) можно представить конечным произведением матриц вращения?

37. Верно ли, что любую матрицу вращения можно представить конечным произведением матриц Хаусхолдера (матриц отражения)?

38. Подсчитайте количество арифметических операций, затрачиваемое для получения QR-разложения 39. Найти значения параметра, для которых будет сходиться метод простой итерации 40. Исследовать сходимость метода Гаусса-Зейделя в применении к системе линейных алгебраических уравнений в зависимости от параметра.

41. Найдите оптимальное значение параметра для метода простой итерации с матрицей 42. Для решения некоторой системы линейных алгебраических уравнений организован итерационный процесс Как называется этот итерационный процесс? Будет ли он сходиться к решению системы линейных алгебраических уравнений?

44. К системе линейных алгебраических уравнений имеющей решение, применяется итерационный метод Якоби с начальным приближением . Оцените количество итераций, необходимое для достижения абсолютной точности приближённого решения 10-6 в 1-норме.

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

47. Что может служить количественной мерой обусловленности задачи вычисления собственных значений квадратной матрицы?

48. Назовите различные стратегии обнуления внедиагональных элементов матрицы в итерационном методе Якоби (методе вращений) для решения симметричной проблемы собственных значений.

49. Оцените трудоёмкость (количество арифметических операций) приведения матрицы к хессенберговой форме с помощью матриц отражения и с помощью матриц 50. Будет ли сходиться степенной метод для нахождения доминирующего собственного значения в применении к матрице ? Будет ли сходиться для этой матрицы QR-алгоритм?

6.2. Примерный список вопросов для подготовки к экзамену по вычислительтным методам анализа и линейной алгебры:

1. Задачи интерполирования и приближения функций. Алгебраическая интерполяция. Существование и единственность решения задачи алгебраической интерполяции.

2. Интерполяционный полином Лагранжа.

3. Разделённые разности и их свойства. Интерполяционный полином Ньютона.

4. Оценка погрешности алгебраической интерполяции с простыми узлами.

5. Полиномы Чебышёва, их свойства и применение в интерполировании.

6. Задача алгебраической интерполяции с кратными узлами, существование и единственность её решения. Оценка погрешности алгебраической интерполяции с кратными узлами.

7. Численное дифференцирование, различные подходы к получению формул численного дифференцирования. Примеры разностных формул для первых и вторых производных.

8. Примеры разностных формул для первых и вторых производных. Оценка погрешности формул численного дифференцирования и поведение полной погрешности.

9. Теорема Вейерштрасса. Понятие интерполяционного процесса и его сходимости.

Пример Рунге. Теорема Фабера. Теорема Марцинкевича.

10. Понятие о сплайне. Степень сплайна, его дефект. Интерполяционный кубический сплайн и его построение.

11. Задача приближения функций. Наилучшее приближение в евклидовом пространстве.

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

14. Численное интегрирование, квадратурная формула и её остаточный член. Интерполяционные квадратурные формулы, формулы Ньютона-Котеса.

15. Квадратурные формулы прямоугольников и трапеций. Оценка их погрешности.

16. Квадратурная формула Симпсона, оценка её погрешности. Составные квадратурные формулы, их погрешность.

17. Алгебраическая степень точности квадратурных формул. Квадратурные формулы Гаусса, их простейшие представители.

18. Выбор узлов для квадратурных формул Гаусса в общем случае.

19. Примеры квадратурных формул Гаусса. Погрешность квадратур Гаусса.

20. Сингулярные числа и сингулярные векторы матрицы. Сингулярное разложение матрицы. Спектральный радиус матрицы и его свойства.

21. Нормы в пространствах векторов и матриц. Эквивалентность норм.

22. Согласованные и подчинённые нормы, примеры согласования и подчинения.

23. Матричный ряд Неймана.

24. Понятие об обусловленности математической задачи, два подхода к её определению.

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

26. Метод Гаусса для решения систем линейных алгебраических уравнений, его матричная интерпретация. Выбор ведущего элемента.

27. Вычисление обратной матрицы и определителя матрицы.

28. LU-разложение матрицы, условия его существования, связь с методом Гаусса для решения СЛАУ.

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. QR-алгоритм для решения проблемы собственных значений. Характер его сходимости. Хессенбергова форма матрицы, её применение в QR-алгоритме.

6.3. Примерный перечень задач вычислительной практики на ЭВМ.

Зачёт по практике на ЭВМ заключается в сдаче работающей программы (реализующей тот или иной метод) с проверкой корректности ответа, а также объяснением особенностей реализации и характеристик метода. В 3-м семестре обучения предусматривается сдача трёх заданий по темам:

1) Численное решение нелинейного уравнения;

2) Интерполирование;

3) Численное нахождение определённого интеграла.

В 4-м семестре обучения (когда лекционный курс уже не читается) задания по практике на ЭВМ охватывают темы:

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

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

3) Численное решение проблемы собственных значений.

Написание эссе, рефератов, курсовых работ и др. по дисциплине «Вычислительные методы анализа и линейной алгебры» не предусмотрено.

7. Учебно-методическое и информационное обеспечение дисциплины.

а) основная литература:

1. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. – Москва:

2. Вержбицкий В.М. Основы численных методов. – Москва: Высшая школа, 2009.

3. Деммель Дж. Вычислительная линейная алгебра. – Москва: Мир, 2001.

4. Тыртышников Е.Е. Методы численного анализа. – Москва: Академия, 2007.

5. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. – Санкт-Петербург–Москва–Краснодар: Лань, 2009.

6. Шарый С.П. Курс вычислительных методов. – Новосибирск: ИВТ СО РАН, 2013. Электронный учебник, доступный на http://www.ict.nsc.ru/matmod/index.php?file=u_posobiya б) дополнительная литература:

1. Алексеев Е.Р., Чеснокова О.В., Рудченко Е.А. Scilab. Решение инженерных и математических задач. – Москва: Alt Linux-Бином, 2008.

2. Барахнин В.Б., Шапеев В.П. Введение в численный анализ. – Санкт-Петербург– Москва–Краснодар: Лань, 2005.

3. Бахвалов Н.С., Корнев А.А., Чижонков Е.В. Численные методы. Решения задач и упражнения. – Москва: Дрофа, 2009.

4. Волков Е.А. Численные методы. – Санкт-Петербург-Москва-Краснодар: Лань, 5. Демидович Б.П., Марон И.А. Основы вычислительной математики. – СанктПетербург–Москва–Краснодар: Лань, 2009.

6. Квасов Б.И. Численные методы анализа и линейной алгебры. Учебное пособие.

Части 1-2. – Новосибирск: Новосибирский госуниверситет, 2009.

7. Коновалов А.Н. Введение в вычислительные методы линейной алгебры. – Новосибирск: Наука, 1993.

8. Мацокин А.М., Сорокин С.Б. Численные методы. Курс лекций. – Новосибирск:

Новосибирский госуниверситет, 2006.

9. Стечкин С.Б., Субботин Ю.Н. Сплайны в вычислительной математике. – Москва: Наука, 1976.

10. Хорн Р., Джонсон Ч. Матричный анализ. – Москва: Мир, 1989.

в) программное обеспечение и Интернет-ресурсы:

1. Scilab – a free scientific software package for numerical computations. – URL:

http://www.scilab.org.

2. GNU Octave. – URL: http://www.gnu.org/software/octave 3. GNUPLOT: a portable command-line driven graphing utility. – URL:

http://www.gnuplot.info.

8. Материально-техническое обеспечение дисциплины.

Доска, мел или фломастеры, тряпка (губка).

Ноутбук, медиа-проектор, экран.

Программное обеспечение для демонстрации слайд-презентаций.

Персональные компьютеры под управлением операционных систем Windows или Linux. Компиляторы популярных языков программирования C/C++, Fortran, Java, Pascal, Delphi и др. Свободно распространяемое программное обеспечение Scilab, Octave и/или gnuplot для математических расчётов и построения графиков.

Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению «010400 – Прикладная математика и информатика», все профили подготовки.

Рецензент (ы) Программа одобрена на заседании от _ года, протокол №