Аппроксимация — математический метод¶

Аппроксимация (от лат. approximatio — приближение) — в математике и вычислительной технике замена сложного объекта (функции, распределения, набора данных) более простым объектом, который достаточно точно описывает исходный, но удобнее для анализа, вычислений или хранения. Понятие лежит в основе численных методов, машинного обучения, теории сигналов и вычислительной геометрии.

¶Основные понятия

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

• Абсолютная погрешность — $\max |f(x) - \tilde{f}(x)|$ (наибольшее отклонение).
• Среднеквадратичная погрешность — $\sqrt{\int |f(x) - \tilde{f}(x)|^2 dx}$.
• Относительная погрешность — отношение абсолютной погрешности к значению функции.

Задача аппроксимации формулируется так: для заданной функции $f$ из некоторого пространства найти элемент $\tilde{f}$ из более простого подпространства (например, многочленов степени не выше $n$), минимизирующий выбранную метрику.

¶Основные виды аппроксимации

¶Полиномиальная аппроксимация

Наиболее распространённый класс — приближение функций многочленами. Существует несколько классических схем:

• Ряды Тейлора — локальное приближение в окрестности точки $x_0$: $f(x) \approx \sum_{k=0}^{n} \frac{f^{(k)}(x_0)}{k!}(x - x_0)^k$. Точность растёт с увеличением порядка $n$, но сходимость гарантируется только внутри радиуса сходимости.
• Многочлены Чебышёва — приближение на отрезке с минимизацией наибольшего отклонения. Разложение функции в ряд по многочленам Чебышёва обладает свойством «наилучшего приближения» в смысле равномерной нормы.
• Интерполяция — построение многочлена, проходящего точно через заданные узлы. Интерполяционный многочлен Лагранжа и формулы Ньютона — классические примеры.

¶Наилучшее приближение в смысле Чебышёва

Теорема Чебышёва утверждает: если $f$ непрерывна на отрезке $[a,b]$, то среди многочленов степени не выше $n$ существует единственный многочлен, наиболее близкий к $f$ в равномерной норме. Этот многочлен характеризуется чередованием знаков отклонения в $(n+2)$ точках — так называемое свойство «равных отклонений».

¶Наименьшие квадраты

Метод наименьших квадратов (МНК, метод Гаусса) минимизирует суммарный квадрат отклонений. Для дискретных данных $\{(x_i, y_i)\}$ ищется параметрическая модель $\tilde{f}(x; \theta)$, минимизирующая $\sum_i (y_i - \tilde{f}(x_i; \theta))^2$. Для линейной по параметрам модели задача сводится к решению системы линейных уравнений. МНК применяется в статистике, обработке сигналов, фотограмметрии и калибровке оборудования.

¶Сплайны

Сплайновая аппроксимация — приближение кусочно-полиномиальными функциями. Кубические сплайны (используемые, в частности, в пакете MATLAB и в PostScript) обеспечивают непрерывность второй производной в узлах соединения, что даёт гладкую кривую при умеренном числе параметров. Сплайны широко применяются в компьютерной графике (B-сплайны, кривые Безье) и моделировании корпусов судов и кузовов автомобилей.

¶Численная аппроксимация интегралов и производных

• Квадратурные формулы — аппроксимация определённого интеграла $\int_a^b f(x)dx \approx \sum_i w_i f(x_i)$. Формулы трапеций, Симпсона, Гаусса — стандартные примеры.
• Конечные разности — приближение производной: $f'(x) \approx \frac{f(x+h) - f(x)}{h}$.
• Разложение в ряды — асимптотические разложения для вычисления специальных функций (функция ошибок, Бесселя, гамма-функция).

¶Аппроксимация в теории сигналов

В обработке сигналов аппроксимация означает представление сигнала в виде конечной комбинации базисных функций:

• Разложение в ряд Фурье — представление периодического сигнала суммой гармоник.
• Вейвлет-разложение — анализ сигнала в масштабе и времени одновременно, применяется в сжатии изображений (стандарт JPEG 2000).
• Квантование и сэмплирование — дискретизация непрерывного сигнала по времени и амплитуде, основа цифрового звука и видео.

¶Аппроксимация в теории вероятностей и статистике

• Нормальное распределение как аппроксимация суммы большого числа случайных величин (центральная предельная теорема).
• Аппроксимация биномиального распределения нормальным (формула де Муавра — Лапласа) и пуассоновским (при малых $p$ и большом $n$).
• Кривые регрессии — аппроксимация выборочных данных параметрической моделью (линейная, показательная, логарифмическая регрессия).

¶Приближённые алгоритмы и вычислительная сложность

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

• Аппроксимирующие алгоритмы NP-трудных задач — например, полиномиальные схемы аппроксимации для задач покрытия, раскраски графов, коммивояжёра.
• Алгоритмы с гарантией качества — для некоторых задач известны аппроксимации с ограниченным коэффициентом приближения (PTAS, FPTAS).
• Методы Монте-Карло — приближённое вычисление интегралов и вероятностей случайной выборкой.

¶История

Термин «аппроксимация» в математическом смысле закрепился в XIX веке в работах П. Л. Чебышёва, который сформулировал теорию наилучших приближений и ввёл понятие равномерной нормы. Развитие вычислительной математики в XX веке (появление ЭВМ) превратило аппроксимацию в один из основных инструментов естествознания и инженерии. В России значительный вклад в теорию приближений внесли С. Н. Бернштейн, Д. К. Фаддеев, В. Л. Гончаров.

¶Применение

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

¶Источники

• Тихонов А. Н., Самарский А. А. Уравнения математической физики
• Чебышёв П. Л. Об определении наименьших величин методом наименьших квадратов
• Крылов А. Н. Лекции о приближённых вычислениях
• Сборник «Математический практикум» под редакцией И. Н. Бронштейна
• Пресс У., Теквольд С., Фленнер Х. Численные методы на ЭВМ