Main menu

Численное решение уравнений в частных производных: метод сеток

Повелители сложных систем: Уравнения математической физики

Если обыкновенные дифференциальные уравнения (ОДУ) описывают системы, зависящие только от одного параметра (например, от времени), то уравнения в частных производных (УЧП) описывают многомерные процессы, которые разворачиваются как во времени, так и в пространстве. Вся современная физика базируется на УЧП. Уравнение теплопроводности Фурье описывает нагрев и охлаждение деталей двигателя. Волновое уравнение описывает распространение звука, радиоволн и света. Уравнения Навье-Стокса управляют течением жидкостей и газов, позволяя проектировать аэродинамику самолетов и прогнозировать погоду. Уравнение Шредингера лежит в основе квантовой механики.

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

Дискретизация: превращение континуума в матрицу

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

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

Явные и неявные схемы: проблема устойчивости

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

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

Подробнее

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

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

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

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

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

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

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

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

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

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

Подробнее

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

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

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

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

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

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

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

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

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

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

Подробнее

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

1 класс 2 класс 3 класс
4 класс 5 класс 6 класс

Книги

Фильмы

Старый сайт

Соц. сети