Учебник Численные методы для начинающих

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

1. 1 Зачем нужны численные методы

   1. Когда формулы заканчиваются

      Большинство реальных уравнений не решается «в лоб» формулой. Численные методы дают приближённый, но управляемый по точности ответ.

   2. Откуда берётся приближение: дискретизация и итерация

      Две универсальные стратегии всех численных методов: разбить непрерывное на конечные кусочки и приближаться к ответу шаг за шагом.

   3. Что такое погрешность и зачем её оценивать

      Абсолютная и относительная погрешность, погрешность метода и округления — базовый словарь, без которого нельзя говорить о точности.

2. 2 Машинная арифметика и обусловленность

   1. Плавающая точка IEEE 754: как компьютер хранит дроби

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

   2. Машинный эпсилон и почему 0.1 + 0.2 ≠ 0.3

      Машинный эпсилон — порог, ниже которого добавка теряется при сложении с единицей. Из-за него простейшие десятичные равенства нарушаются.

   3. Потеря значимости и накопление ошибок

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

   4. Устойчивость алгоритма и обусловленность задачи

      Обусловленность — свойство задачи (чувствительность ответа к данным), устойчивость — свойство алгоритма. Это разные вещи, и обе критичны.

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

   1. Метод бисекции: медленно, но надёжно

      Деление отрезка пополам гарантированно находит корень непрерывной функции, если на концах отрезка она имеет разные знаки.

   2. Метод Ньютона: квадратичная сходимость и её цена

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

   3. Метод секущих: Ньютон без производной

      Если производную взять негде, её заменяют разностью по двум последним точкам. Сходимость почти как у Ньютона, но дешевле.

   4. Простая итерация и условие сходимости

      Уравнение переписывают в виде x = g(x) и крутят. Сойдётся ли это — решает производная g: нужно |g'| < 1 у корня.

   5. Порядок сходимости: как его измерить

      Порядок p и константа C описывают, как быстро падает ошибка. Измерить p можно прямо по последовательности приближений.

4. 4 Системы линейных уравнений

   1. Метод Гаусса с выбором главного элемента

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

   2. LU-разложение: решаем много систем дёшево

      Один раз раскладываем A = LU за O(n³), а потом решаем систему с любой правой частью за O(n²). Незаменимо, когда правых частей много.

   3. Прогонка для трёхдиагональных систем

      Когда ненулевые элементы только на трёх диагоналях, систему решают методом прогонки за линейное время O(n) вместо кубического.

   4. Итерационные методы: Якоби и Зейдель

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

   5. Число обусловленности матрицы

      Оно показывает, насколько решение системы чувствительно к шуму в данных. Большое κ(A) — сигнал, что результату нельзя слепо верить.

5. 5 Интерполяция

   1. Полином Лагранжа: кривая через точки

      Через n+1 точку проходит единственный полином степени n. Формула Лагранжа выписывает его явно из готовых базисных множителей.

   2. Разделённые разности Ньютона

      Та же интерполяция, но в инкрементной форме: добавил узел — дописал одно слагаемое. Коэффициенты считают через разделённые разности.

   3. Феномен Рунге: почему высокая степень опасна

      Кажется, чем больше узлов, тем точнее. Но на равномерной сетке полином высокой степени дико осциллирует у краёв — это феномен Рунге.

   4. Кубические сплайны

      Вместо одного полинома высокой степени — гладкая склейка кубиков на каждом отрезке. Никакого Рунге, плавность и устойчивость.

6. 6 Аппроксимация и метод наименьших квадратов

   1. Метод наименьших квадратов: линия сквозь облако

      Через зашумлённые точки проводят прямую, минимизирующую сумму квадратов вертикальных отклонений. Минимум даёт пару простых формул.

   2. Полиномиальная аппроксимация и нормальные уравнения

      Для кривой сложнее прямой МНК сводится к системе нормальных уравнений. Решив её Гауссом, получаем коэффициенты полинома любой степени.

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

   1. Конечные разности: производная по точкам

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

   2. Прямоугольники и трапеции

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

   3. Формула Симпсона: парабола вместо отрезка

      Заменяя кривую на каждой паре полосок параболой, получаем формулу четвёртого порядка — резкий скачок точности почти бесплатно.

   4. Адаптивное интегрирование и квадратуры Гаусса

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

   5. Метод Монте-Карло: интеграл через случайность

      Бросая случайные точки, оценивают интеграл по среднему значению функции. Медленно в 1D, но незаменимо в высоких размерностях.

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

   1. Метод Эйлера: первый шаг в мир ОДУ

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

   2. Рунге-Кутты RK4: рабочая лошадка

      Четыре пробных наклона на шаге дают четвёртый порядок точности. RK4 — стандарт де-факто для решения ОДУ.

   3. Системы ОДУ и жёсткие уравнения

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

9. 9 Собственные значения, оптимизация и анализ ошибок

   1. Степенной метод: главное собственное значение

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

   2. Одномерная оптимизация: золотое сечение и парабол

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

   3. Экстраполяция Ричардсона: бесплатно повысить порядок

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

   4. Практика численного кода и выбор метода

      Масштабирование, тестирование на известных решениях, контроль погрешности — и сводная таблица: какой метод когда брать.