Александр

Метод наименьших квадратов (МНК) в обработке экспериментальных данных

Борьба с шумом: почему интерполяция здесь бессильна?

При получении данных из реального мира (с датчиков температуры, акселерометров, телескопов, биржевых котировок) мы всегда имеем дело с помехами. Любой измерительный прибор имеет свою погрешность, на эксперимент влияют случайные факторы окружающей среды, возникает так называемый «белый шум». Если у нас есть массив таких зашумленных данных, применять к ним методы строгой интерполяции (проводить кривую точно через каждую точку) — грубейшая ошибка. В этом случае мы будем интерполировать не только полезный физический сигнал, но и сам шум, получая ломанную, не имеющую физического смысла кривую. Нам нужен метод, который проведет кривую не через точки, а «между» ними, улавливая общую закономерность и тренд, игнорируя случайные выбросы.

С этой задачей блестяще справляется Метод Наименьших Квадратов (МНК), впервые опубликованный Лежандром и строго обоснованный Карлом Фридрихом Гауссом. Этот алгоритм стал фундаментом математической статистики, эконометрики и современного машинного обучения (в частности, алгоритмов линейной и полиномиальной регрессии).

Математическая суть МНК

Идея метода заложена в его названии. Мы заранее выбираем вид функции (модель), которая, по нашему мнению, должна описывать процесс. Это может быть прямая линия (y = ax + b), парабола, экспонента или синусоида. Эта функция содержит неизвестные параметры (коэффициенты a и b), которые нам предстоит найти.

Для каждой экспериментальной точки мы вычисляем отклонение (невязку) — разницу между реальным измеренным значением и значением, которое предсказывает наша теоретическая функция при текущих коэффициентах. Если мы просто сложим все эти невязки, положительные и отрицательные отклонения могут компенсировать друг друга, дав ложную картину идеального совпадения. Поэтому мы возводим каждую невязку в квадрат (избавляясь от знаков минуса и усиливая штраф за крупные выбросы) и суммируем их. Полученная сумма квадратов ошибок (Loss function) является функцией от искомых параметров. Наша цель — найти такие коэффициенты модели, при которых эта сумма квадратов достигает абсолютного минимума.

Сведение к системе нормальных уравнений

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

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

Подробнее

Интерполяция и аппроксимация функций: многочлены Лагранжа и сплайны

Задача восстановления функции по точкам

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

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

Глобальная интерполяция: многочлен Лагранжа

Классическим подходом является алгебраическая интерполяция, при которой мы ищем интерполирующую функцию в виде полинома (многочлена). Согласно теореме Вейерштрасса, любую непрерывную функцию можно приблизить полиномом с любой заданной точностью. А фундаментальная теорема алгебры гласит, что через N+1 уникальную точку можно провести ровно один полином степени N.

Самым известным способом записи такого полинома является интерполяционный многочлен Лагранжа. Его формула строится элегантно и интуитивно понятно: это линейная комбинация базисных полиномов. Каждый базисный полином устроен так, что в одном конкретном узле сетки он равен единице, а во всех остальных узлах обращается в ноль. Многочлен Лагранжа прекрасен в теории, но имеет серьезный изъян на практике при большом количестве точек. Этот изъян известен как «феномен Рунге». Если мы попытаемся интерполировать функцию по большому количеству узлов, мы получим полином очень высокой степени (например, 20-й степени). Между узлами на краях интервала этот полином начнет демонстрировать дикие, высокоамплитудные осцилляции (раскачку), которые не имеют ничего общего с реальным поведением исходной физической величины.

Кубические сплайны: гибкость и гладкость

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

В математике сплайн — это функция, которая на каждом отдельном интервале между двумя соседними точками задается своим собственным полиномом (обычно третьей степени — кубический сплайн). Однако, в отличие от простого набора кривых, эти полиномы сшиваются в узлах особым образом. Накладываются жесткие условия не только на непрерывность самой функции (кривая не должна разрываться), но и на непрерывность ее первой производной (отсутствие изломов, гладкость) и второй производной (непрерывность кривизны). В результате получается идеально гладкая, визуально эстетичная и математически устойчивая кривая. Сплайны не подвержены осцилляциям Рунге и сегодня лежат в основе всей компьютерной графики (векторные шрифты, CAD-системы, 3D-моделирование).

Подробнее

Численное решение обыкновенных дифференциальных уравнений (ОДУ)

Задача Коши и потребность в численных методах

Обыкновенные дифференциальные уравнения (ОДУ) — это уравнения, связывающие независимую переменную (часто это время t), неизвестную функцию и ее производные. С помощью ОДУ описывается огромное количество динамических процессов во Вселенной: движение планет, рост популяций животных в биологии, радиоактивный распад, химические кинетические реакции и колебания маятника. Классической постановкой является задача Коши (задача с начальными условиями): нам известно уравнение эволюции системы и ее точное состояние в начальный момент времени. Требуется предсказать поведение системы в будущем.

Хотя в курсе высшей математики студенты изучают множество приемов аналитического интегрирования ОДУ (разделение переменных, уравнения Бернулли и т.д.), в реальной инженерной практике подавляющее большинство дифференциальных уравнений не имеет аналитического решения в виде явной функции. Особенно это касается нелинейных уравнений. В таких случаях применяются численные методы, позволяющие получить таблицу значений искомой функции в дискретных точках заданного интервала (узлах сетки).

Метод Эйлера: простота и геометрический смысл

Исторически первым и самым простым численным методом решения ОДУ является метод Эйлера, предложенный великим Леонардом Эйлером еще в 18 веке. Этот метод основан на разложении функции в ряд Тейлора и удержании только первых двух членов разложения.

Геометрический смысл метода предельно нагляден. Пусть мы находимся в начальной точке графика. Дифференциальное уравнение дает нам значение производной (то есть тангенс угла наклона касательной) в этой точке. Метод Эйлера предлагает сделать небольшой шаг вдоль этой касательной. Мы смещаемся на расстояние шага интегрирования h по оси абсцисс, вычисляем новую ординату и принимаем полученную точку за новое начальное условие. Процесс повторяется. Главный недостаток метода Эйлера — его низкая точность. Погрешность метода на одном шаге пропорциональна квадрату шага, а глобальная погрешность на всем интервале — первой степени шага (метод первого порядка точности). Чтобы получить приемлемый результат, приходится брать микроскопически малый шаг, что ведет к накоплению катастрофических ошибок округления.

Семейство методов Рунге-Кутты

Для достижения высокой точности без экстремального измельчения шага используются методы более высоких порядков, наиболее известным из которых является семейство методов Рунге-Кутты. Самым популярным в вычислительной практике является классический метод Рунге-Кутты четвертого порядка (часто обозначаемый как RK4).

Идея методов Рунге-Кутты заключается в том, чтобы на каждом шаге интегрирования вычислить значения функции правой части (наклоны касательных) не только в начальной точке отрезка, но и в нескольких промежуточных точках (пробных точках) внутри текущего интервала. В классическом методе RK4 вычисляются четыре таких коэффициента. Итоговое приращение функции вычисляется как взвешенная сумма этих четырех коэффициентов. Метод RK4 обладает глобальной погрешностью порядка O(h^4). Это значит, что уменьшение шага всего в два раза приводит к уменьшению ошибки в 16 раз. Благодаря идеальному балансу между вычислительной сложностью и высокой точностью, метод RK4 стал стандартом де-факто («рабочей лошадкой») во многих программных пакетах инженерного анализа.

Подробнее

Предупреждение

Метод наименьших квадратов (МНК) в обработке экспериментальных данных

Борьба с шумом: почему интерполяция здесь бессильна?

Математическая суть МНК

Сведение к системе нормальных уравнений

Интерполяция и аппроксимация функций: многочлены Лагранжа и сплайны

Задача восстановления функции по точкам

Глобальная интерполяция: многочлен Лагранжа

Кубические сплайны: гибкость и гладкость

Численное решение обыкновенных дифференциальных уравнений (ОДУ)

Задача Коши и потребность в численных методах

Метод Эйлера: простота и геометрический смысл

Семейство методов Рунге-Кутты

ГДЗ по математике

Книги

Фильмы

Старый сайт

Соц. сети