Г.М. Кобельков - Курс лекций по численным методам

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛОМОНОСОВАМеханико-математический факультетКурс лекций почисленным методамЛектор — Георгий Михайлович КобельковIV курс, 7–8 семестр, поток математиковМосква, 2006 г.Оглавление1.Представление вещественных чисел в компьютере1.1. Мантисса и порядок . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2. Округление и ошибки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.Аппроксимация функций2.1. Интерполяция многочленом Лагранжа . . . . . . . . . . . . . . . . . . . . .2.1.1. Постановка задачи и оценка её сложности . . . . . .

. . . . . . . . . .2.1.2. Оценка погрешности приближения функции многочленом Лагранжа2.1.3. Многочлены Чебышёва . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2. Тригонометрическая интерполяция . . . . . . . . . . . . . . . . . . . . . . .2.2.1.

Дискретное преобразование Фурье . . . . . . . . . . . . . . . . . . . .2.2.2. Быстрое дискретное преобразование Фурье . . . . . . . . . . . . . . .2.3. Разделённые разности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.1. Определение разделённой разности и её простейшие свойства . . . .2.3.2. Интерполяционная формула Ньютона . . . . . . . .

. . . . . . . . . .2.3.3. Интерполяция с кратными узлами . . . . . . . . . . . . . . . . . . . .2.4. Наилучшее приближение в нормированных пространствах . . . . . . . . .2.4.1. Общая теория . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .2.4.2. Наилучшее приближение многочленами. Чебышёвский альтернанс .2.4.3. Примеры многочленов наилучшего приближения . . . . . . . . . . .2.5. Ортогональные системы и их свойства . . . . . . . . . . . . . . . . . . . . .2.5.1. Гильбертовы пространства. Процесс ортогонализации . . . . . . . . .2.5.2. Ортогональные многочлены и их свойства . . .

. . . . . . . . . . . .2.6. Наилучшее приближение в гильбертовых пространствах . . . . . . . . . . .2.7. Сплайны . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.7.1. Определение сплайнов . . . . . . . . . . . . . . . . . . . . . . . . . . .2.7.2. В-сплайн . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . ...............................................................................................................................................................................................................................................................................................66667889101010111212131515151618191920Численные методы и дифференциальное исчисление3.1. Численное дифференцирование .

. . . . . . . . . . . . . . . .3.2. Сжатие информации . . . . . . . . . . . . . . . . . . . . . . . .3.2.1. Двумерный случай . . . . . . . . . . . . . . . . . . . . .3.3. Численное интегрирование . . . . . . . . . . . . . . . . . . . .3.3.1. Формула прямоугольников . . . . . . . . .

. . . . . . . .3.3.2. Метод трапеций . . . . . . . . . . . . . . . . . . . . . . .3.3.3. Метод Симпсона . . . . . . . . . . . . . . . . . . . . . . .3.4. Оценка погрешности квадратурных формул . . . . . . . . . .3.5. Подсчёт интегралов по составным квадратурным формулам3.5.1. Составные квадратурные формулы . . .

. . . . . . . . .3.5.2. Правило Рунге . . . . . . . . . . . . . . . . . . . . . . . .3.5.3. Интегрирование быстро осциллирующих функций . . .3.5.4. Оптимальные квадратуры . . . . . . . . . . . . . . . . .3.4.555.......................................................................................................................................................................................................................................................2121222223242424242626262727Численные методы линейной алгебры4.1. Точные методы .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.1.1. Метод отражений . . . . . . . . . . . . . . . . . . . . . . . . .4.1.2. Метод Холецкого . . . . . . . . . . . . . . . . . . . . . . . . .4.2. Итерационные методы . . . . . . . . . . . . . . . . . . . . . . . . . .4.2.1.

Метод простой итерации . . . . . . . . . . . . . . . . . . . . .4.2.2. Модификация метода простой итерации (метод Ричардсона)4.2.3. Upgrade метода Ричардсона, или чебышевское ускорение . .4.2.4. Линейный оптимальный процесс . . . . . . . . . . . . . . . .4.3. Другие методы .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.3.1. Метод скорейшего спуска . . . . . . . . . . . . . . . . . . . .4.3.2. Метод Ричардсона для несимметричных матриц . . . . . . .4.3.3. Метод решения симметричных плохо обусловленных систем4.3.4. Метод Зейделя . . . . . . . . . . . . . . . . . . . . . . . . . . ...........................................................................................................................................................................................................................................27272728282830313233333436372..........................4.4.5.4.3.5. Метод сопряжённых градиентов .

. . . . . . . . . . . . . . .Что делать, когда всё плохо? . . . . . . . . . . . . . . . . . . . . . .4.4.1. Метод регуляризации по Тихонову . . . . . . . . . . . . . . .4.4.2. Метод Поспелова для решения плохо обусловленных системНелинейные и дифференциальные уравнения5.1. Нелинейные уравнения . . .

. . . . . . . . . . . . . . . . . . . . .5.1.1. Метод половинного деления . . . . . . . . . . . . . . . . . .5.1.2. Метод простой итерации . . . . . . . . . . . . . . . . . . . .5.1.3. Метод Ньютона . . . . . . . . . . . . . . . . . . . . . . .

. .5.2. Дифференциальные уравнения . . . . . . . . . . . . . . . . . . . .5.2.1. Метод Эйлера и его модификации . . . . . . . . . . . . . .5.2.2. Метод Рунге – Кутта . . . . . . . . . . . . . . . . . . . . . .5.2.3. Метод Рунге априорной оценки погрешности .

. . . . . . .5.2.4. Обобщение метода Рунге – Кутта . . . . . . . . . . . . . . .5.3. Разностные схемы для решения дифференциальных уравнений5.3.1. Устойчивость схем в определениях и примерах . . . . . . .5.3.2. Метод Лебедева для решения жёстких систем ОДУ . . . .5.4. Простейшая краевая задача . . . . . . .

. . . . . . . . . . . . . .5.4.1. Разные определения и теоремы . . . . . . . . . . . . . . . .5.4.2. Три разностные схемы, спектральный признак . . . . . . .5.4.3. Спектральный признак устойчивости . . . . . . . . . . . .5.5. Схемы с весами . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .5.5.1. Явная схема . . . . . . . . . . . . . . . . . . . . . . . . . . .5.5.2. Неявная схема . . . . . . . . . . . . . . . . . . . . . . . . . .5.5.3. Схема с весами . . . . . . . . . . . . . . . . . . . . .

. . . .5.6. Сеточные теоремы вложения . . . . . . . . . . . . . . . . . . . . .5.7. Методы стрельбы и прогонки . . . . . . . . . . . . . . . . . . . .5.7.1. Метод прогонки . . . . . . . . . . . . . . . . . . . . . . . . .5.7.2. Метод стрельбы . . .

. . . . . . . . . . . . . . . . . . . . . .5.8. Повышение порядков аппроксимации. Метод баланса . . . . . .5.8.1. Пример номер раз . . . . . . . . . . . . . . . . . . . . . . . .5.8.2. Пример номер два . . . . . . . . . . . . . . . . . . . . . . . .5.8.3. Метод баланса . . . . . . . . . . . . .

. . . . . . . . . . . . .5.9. Метод конечных элементов (проекционный метод) . . . . . . . .5.10. Интегральные уравнения второго рода . . . . . . . . . . . . . . .3......................................................................................................37393940............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................41414142424343434545454647484849505151515152535354545455555657ПредисловиеЭтот документ представляет собой курс лекций по численным методам, читаемый в 7–8 семестре.

Порядокизложения материала наиболее соответствует курсу 2005–2006 г.Если выяснится, что в некоторых билетах чего-то катастрофически не хватает, но это не отражено в тексте,пишите. Кое-где явно написано, что «в лекциях муть», и исправить это не представляется возможным. Поймитеправильно, уважаемые читатели, нет ничего страшнее, чем написать какой-то бред и выдавать его за правду.Release notes21.05 Паша Наливайко победил тяжкий бред в очень-очень быстром преобразовании Фурье.

Несмотря на всюего быстроту, текст надо было писать не торопясь. . .21.05 А ещё добавился метод Поспелова в вольном изложении Александра Воронцова, за что ему отдельнаяблагодарность. В нем было исправлено немножко опечаток, и стало лучше.28.05 В данной версии написан метод конечных элементов в не менее вольном изложении автора конспекта.29.05 Гип-гип, ура! Появился метод баланса. Ещё замечен бред в одном из методов линейной алгебры (но нанего для простоты на экзамене можно забить).31.05 Обработан последний поступивший багрепорт от Паши Наливайко. Жить стало легче, жить стало веселее:)БлагодарностиЗа поиск опечаток спасибо Лёхе Басалаеву, Сергею Гладких, Паше Наливайко, Саше Воронцову, а также ивсем, кого я ещё забыл :)Последняя компиляция: 31 мая 2006 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.41.

Представление вещественных чисел в компьютере1.1. Мантисса и порядокВсем ясно, что хранить бесконечные десятичные дроби мы пока не умеем — памяти не хватит. Поэтомубудем хранить только их приближения с некоторой разумной точностью. Просто хранить сколько-то знаковпосле запятой глупо, ибо хочется уметь работать с числами вида 1 · 10100 и 1 · 10−100 , а отводить память под100 знаков крайне неэкономно. Кроме того, при работе с очень маленькими (или, наоборот, очень большими)числами нам не так уж важны младшие разряды, а важен порядок числа. Вот поэтому-то числа и хранят ввиде мантиссы и порядка.