Перейти к основному содержимому

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

НЕ ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ
Архитектору Инженеру

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

В отличие от символьных пакетов (CAS), численные методы оперируют конкретными числами и итерациями — как процессор в игре, симуляторе или ML-тренировке. Символьные вычисления в Python — SymPy — уравнения и производные; численные массивы — NumPy — массивы и матрицы; теория стека — Анализ данных — NumPy и SciPy.

Решение уравнений f(x) = 0​

Метод Ньютона (касательных)​

Линеаризация в текущей точке, быстрая квадратичная сходимость при хорошем старте. Требует производную (или секущую аппроксимацию). Риск: расходимость, попадание в другой корень.

Метод бисекции (деления отрезка)​

Если f(a) и f(b) разных знаков и f непрерывна — корень на [a,b]. Делим пополам, сохраняем половину с сменой знака. Гарантированная линейная сходимость, медленнее Ньютона. Часто комбинируют: бисекция локализует, Ньютон уточняет.

Интерполяция и аппроксимация​

ПодходЦельРиск
Интерполяцияточно через узлы данныхфеномен Рунге на равномерной сетке при высоком градусе
Аппроксимация"лучшее" приближение при шуменеверная модель → систематическая ошибка

Полином Лагранжа — классическая интерполяция; на многих узлах осциллирует у краёв. На практике чаще сплайны (кусочно-гладкие).

Метод наименьших квадратов (МНК)​

Минимизируется сумма квадратов отклонений Σ (yᵢ − ŷᵢ)². Для линейной модели по параметрам — система линейных уравнений; при нормальных независимых ошибках совпадает с оценкой максимального правдоподобия.

Основа регрессии, калибровки датчиков, обучения линейных моделей. Обобщения — взвешенный МНК, L1/L2-регуляризация (гребень, лассо).

Ключевые понятия​

  • Погрешность округления — ограниченная точность float.
  • Погрешность метода — накапливается за итерации.
  • Устойчивость — малые изменения входа не разрушают результат.

Связь с IT​

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

Пример — бисекция и Ньютон для √2​

def bisect(f, a, b, eps=1e-9):
    fa, fb = f(a), f(b)
    if fa * fb > 0:
        raise ValueError("нет смены знака")
    while b - a > eps:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:
            b = m
        else:
            a = m
    return (a + b) / 2

def newton(f, df, x0, eps=1e-12, max_iter=50):
    x = x0
    for _ in range(max_iter):
        fx = f(x)
        if abs(fx) < eps:
            return x
        dfx = df(x)
        if dfx == 0:
            break
        x -= fx / dfx
    return x

f = lambda x: x * x - 2
print("бисекция:", bisect(f, 1.0, 2.0))
print("Ньютон:", newton(f, lambda x: 2 * x, 1.5))

МНК на шумных точках​


import numpy as np

xs = np.linspace(0, 1, 20)
ys = 2.5 * xs + 1.0 + np.random.default_rng(0).normal(0, 0.15, size=20)
a, b = np.polyfit(xs, ys, deg=1)
print(f"оценка: y ≈ {a:.2f}·x + {b:.2f}")

Дальше: Формальные языки и автоматы.

Содержание