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

Численные методы (100)

Численное обращение преобразования Лапласа: борьба с некорректными задачами

Могущественный инструмент операционного исчисления

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

Именно на этапе возврата (обратного преобразования Лапласа) кроется главная проблема. Аналитическая формула обратного преобразования требует вычисления сложного контурного интеграла Римана-Меллина в комплексной плоскости с использованием теории вычетов. Для многих сложных передаточных функций (например, при моделировании теплопередачи, диффузии в пористых средах или вязкоупругих материалов) аналитически взять этот интеграл просто невозможно. Возникает необходимость в численном обращении.

Некорректность по Адамару и взрыв ошибок

Задача численного обращения преобразования Лапласа принадлежит к классу некорректно поставленных задач по Адамару. Это означает, что математический оператор, связывающий оригинал и изображение, обладает чудовищным сглаживающим свойством. Если мы возьмем функцию времени с резкими осцилляциями и добавим ее к нашему оригиналу, изображение по Лапласу изменится на микроскопическую величину.

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

Алгоритм Гавера-Стефеста и методы Фурье

За десятилетия было разработано более сотни различных методов численного обращения, но идеального, универсального не существует до сих пор. Одним из самых популярных среди инженеров является метод Стефеста (Gaver-Stehfest algorithm). Его прелесть заключается в том, что он требует значений функции-изображения только на действительной оси (без комплексных чисел). Алгоритм использует вероятностный подход и экстраполяцию Ричардсона, приближая оригинал взвешенной суммой значений изображения. Он потрясающе прост в программировании (всего несколько строк кода) и дает отличные результаты для монотонных, гладких функций без осцилляций (например, для процессов остывания).

Однако если система содержит синусоидальные колебания, метод Стефеста полностью разваливается. Для колебательных сигналов применяются методы, основанные на разложении в ряды Фурье (методы Дурбина, Крампа) и алгоритмы деформации контура интегрирования в комплексной плоскости (метод Талбота). На практике программные пакеты (такие как Mathematica или SciPy) часто содержат эвристические подпрограммы, которые анализируют структуру переданной функции и автоматически выбирают наиболее безопасный и точный численный алгоритм для обращения.

Подробнее

Интервальный анализ: вычисления с гарантированной математической точностью

Катастрофическая потеря значимости чисел с плавающей запятой

Все классические численные алгоритмы, реализуемые на компьютерах, используют формат чисел с плавающей запятой (стандарт IEEE 754). Этот формат неизбежно вносит погрешность округления при каждой арифметической операции. В большинстве инженерных задач эти крошечные ошибки (порядка 10 в минус 16 степени) не имеют значения. Однако в плохо обусловленных задачах, при вычитании близких чисел или в хаотических динамических системах (где малейшее изменение начальных условий ведет к радикальной смене траектории), ошибки округления накапливаются и полностью искажают результат. Компьютер может выдать ответ, который математически не имеет ничего общего с реальностью, и при этом никак не предупредить пользователя об ошибке.

Для управления полетами космических аппаратов, расчета доз облучения в медицинской лучевой терапии и проверки безопасности атомных реакторов такой риск неприемлем. Нам нужен способ не просто получить приближенный ответ, но и получить строгие математические гарантии того, что истинный ответ гарантированно находится внутри определенного диапазона. Эту революционную идею в 1960-х годах воплотил в жизнь американский математик Рамон Мур, создав новую ветвь математики — интервальный анализ.

Замена чисел на множества

В интервальном анализе базовым объектом оперирования является не конкретное число (скаляр), а замкнутый интервал (отрезок) на числовой оси: [a, b]. В этом отрезке a — это строгая нижняя граница, а b — строгая верхняя. Любые исходные данные с погрешностью (например, длина детали 10 мм с погрешностью 0.1 мм) сразу представляются как интервал [9.9, 10.1].

Далее переопределяются все арифметические операции (сложение, вычитание, умножение, деление) и базовые функции (синус, экспонента). Когда компьютер складывает два интервала, он складывает их нижние и верхние границы с особым аппаратным округлением (нижняя граница всегда округляется в меньшую сторону, верхняя — в большую). Это гарантирует, что истинный ответ никогда не выскользнет за пределы вычисленного результирующего интервала. Иными словами, интервальные вычисления предоставляют стопроцентную, математически строгую оценку глобальной погрешности алгоритма. Если в результате расчета орбиты спутника мы получили интервал расстояния до Земли [400 км, 405 км], мы можем быть абсолютно уверены, что спутник не упадет.

Проблема зависимости (эффект переоценки)

Главным препятствием на пути повсеместного внедрения интервальной арифметики является так называемая «проблема зависимости». Если в классической математике x - x всегда равно 0, то в интервальной арифметике, если мы возьмем интервал X = [1, 2] и вычтем его сам из себя, мы получим интервал [-1, 1], а не ноль. Алгоритм «забывает», что интервалы физически связаны (зависят от одной переменной), и рассматривает их как два независимых множества, принимающих наихудшие возможные значения.

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

Подробнее

Численные методы в финансовой математике: опционы и модель Блэка-Шоулза

От законов теплопроводности к ценообразованию на Уолл-Стрит

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

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

Биномиальные деревья и сеточные методы

Первым и самым наглядным численным подходом к оценке опционов стала модель биномиальных (и позже триномиальных) деревьев, предложенная Коксом, Россом и Рубинштейном в 1979 году. Время до исполнения опциона разбивается на множество мелких дискретных шагов. На каждом шаге предполагается, что цена акции может либо пойти вверх (с определенной вероятностью), либо пойти вниз. В результате строится огромная древовидная структура всех возможных траекторий цены.

Вычисления начинаются с конца дерева (даты экспирации), где выплата по опциону точно известна, и путем математического ожидания с дисконтированием сворачиваются обратно к сегодняшнему дню. Этот метод прекрасно подходит для американских опционов, так как на каждом узле дерева алгоритм может проверить, не выгоднее ли исполнить опцион прямо сейчас. Для более сложных задач биномиальные деревья уступают место классическим конечно-разностным методам (метод сеток), которые мы обсуждали ранее. Уравнение Блэка-Шоулза дискретизируется с использованием неявной схемы Кранка-Николсон. Образовавшаяся при этом матрица СЛАУ является трехдиагональной и мгновенно решается методом прогонки. Комбинация этих численных алгоритмов позволяет инвестиционным банкам оценивать риски и формировать портфели в режиме реального времени, пересчитывая гигантские матрицы котировок каждую миллисекунду.

Подробнее

Решение жестких краевых задач: метод ортогональной прогонки Годунова

Вычислительная катастрофа при интегрировании

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

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

Спасение через ортогонализацию

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

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

Подробнее

Сингулярное разложение матриц (SVD): математика рекомендательных систем и сжатия данных

Универсальный инструмент матричного анализа

В вычислительной линейной алгебре существует множество способов разложения матриц (LU, QR, спектральное разложение), однако Сингулярное Разложение (Singular Value Decomposition, SVD) занимает среди них абсолютно особое место. Если спектральное разложение применимо только к квадратным матрицам, то SVD позволяет разложить абсолютно любую прямоугольную матрицу. Эта математическая процедура стала одним из важнейших открытий XX века, заложив фундамент для современной науки о данных, обработки изображений и систем искусственного интеллекта.

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

Сжатие информации и метод главных компонент (PCA)

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

Этот принцип лежит в основе Метод Главных Компонент (PCA) — важнейшего алгоритма снижения размерности данных. Например, черно-белое изображение лица размером 1000x1000 пикселей (миллион чисел) с помощью усеченного SVD можно сжать до передачи всего 50 векторов, и глаз человека не заметит разницы в качестве. В знаменитом конкурсе Netflix Prize с призовым фондом в миллион долларов, победу одержала команда, алгоритм которой базировался именно на SVD. Матрица, где строками были пользователи, а столбцами — фильмы, содержала огромное количество пропусков (никто не смотрел все фильмы). SVD позволило выявить скрытые (латентные) факторы вкусов пользователей и жанров фильмов, блестяще предсказывая оценки, которые пользователи поставили бы еще не просмотренным картинам.

Подробнее

Метод конечных объемов (МКО): фундамент вычислительной гидродинамики

Законы сохранения как основа физики сплошных сред

Ранее мы рассматривали метод конечных разностей (МКР) и метод конечных элементов (МКЭ). Однако, когда дело доходит до моделирования течений газов и жидкостей (аэродинамика самолетов, течения в газопроводах, взрывы, горение в двигателях), инженеры обращаются к третьему, специализированному инструменту — методу конечных объемов (МКО, или Finite Volume Method, FVM). Именно этот алгоритм заложен в основу большинства ведущих коммерческих и открытых пакетов вычислительной гидродинамики (CFD), таких как ANSYS Fluent, CFX и OpenFOAM.

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

Контрольные объемы и расчет потоков на гранях

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

Поскольку масса, импульс или тепло не могут просто исчезнуть или появиться из ниоткуда, изменение этих величин внутри контрольного объема во времени может происходить только по одной причине: из-за перетекания (потока) этих величин через границы (грани) ячейки в соседние объемы или из них. Математически интеграл по объему преобразуется в интеграл по поверхности с помощью теоремы Остроградского-Гаусса. Таким образом, главная задача МКО сводится к максимально точному расчету потоков на гранях между ячейками. Что вытекло из ячейки А, то со стопроцентной точностью втекло в ячейку Б (консервативность метода).

Улавливание ударных волн и решатели Римана

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

Для решения этой проблемы российский математик Сергей Годунов в 1959 году предложил гениальную идею. Он предложил рассматривать разрыв параметров на гране между двумя ячейками как локальную задачу о распаде произвольного разрыва (задачу Римана в газовой динамике). Решая задачу Римана на каждой грани, алгоритм получает точные, физически обоснованные потоки, которые естественным образом учитывают направление распространения волн (скорость звука). Развитие этой идеи привело к созданию современных высокоразрешающих схем с ограничителями потоков (TVD-схемы, алгоритмы Roe, HLLC). Благодаря им МКО способен рассчитывать сложнейшие сверхзвуковые течения с резкими фронтами ударных волн без численных осцилляций, обеспечивая человечество инструментами для проектирования гиперзвуковых аппаратов и турбин.

Подробнее

Оптимизация в машинном обучении: стохастический градиентный спуск (SGD)

Большие данные и паралич классических методов

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

Проблема заключается в масштабах. Функция потерь нейросети складывается из ошибок на каждом отдельном примере из обучающей выборки. Если ваша выборка состоит из 10 миллионов изображений (как в датасете ImageNet), то для того, чтобы сделать всего один крошечный шаг градиентного спуска, компьютеру нужно прогнать через огромную нейросеть все 10 миллионов картинок, вычислить ошибку для каждой, сложить их и найти производные. Это чудовищно долго. Классический (полнопакетный) градиентный спуск в эпоху Big Data оказался вычислительно парализован.

Стохастичность: скорость в обмен на шум

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

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

Мини-батчи и адаптивные оптимизаторы (Adam)

В чистом виде SGD (по одному примеру) плохо использует возможности современных видеокарт (GPU), которые созданы для параллельных матричных вычислений. Поэтому золотым стандартом индустрии стал компромисс — SGD по мини-батчам (Mini-batch SGD). Выборка делится на небольшие случайные пакеты (от 32 до 512 примеров). Градиент вычисляется по этому пакету. Это дает и достаточную скорость благодаря матричным вычислениям на GPU, и спасительный стохастический шум.

Чтобы справиться с проблемой подбора скорости обучения (learning rate) и зигзагообразными колебаниями SGD в оврагах, математики разработали мощные надстройки. Введение «импульса» (Momentum) позволяет алгоритму накапливать скорость, двигаясь в постоянном направлении, и пробивать мелкие препятствия по инерции. Вершиной этой эволюции стал алгоритм Adam (Adaptive Moment Estimation), который для каждого отдельного из миллионов параметров нейросети вычисляет свою собственную, адаптивную скорость обучения, базируясь на скользящих средних градиентов и их квадратов. Сегодня Adam и его модификации (AdamW) являются инструментами по умолчанию для обучения подавляющего большинства систем искусственного интеллекта, от распознавания образов до больших языковых моделей.

Подробнее

Оценивание состояния систем: фильтр Калмана и анализ зашумленных данных

Проблема скрытых состояний и неточных датчиков

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

Решение этой задачи было найдено в 1960 году Рудольфом Калманом. Его алгоритм, получивший название Фильтр Калмана, стал одним из важнейших открытий в истории вычислительной математики и теории управления. Именно этот фильтр позволил бортовым компьютерам миссии «Аполлон» точно оценивать траекторию спускаемого модуля и успешно приземлиться на Луну, несмотря на сильнейшие шумы радаров.

Математика предсказаний и коррекций

Фильтр Калмана работает по принципу рекурсивного байесовского оценивания. Он не требует хранения огромного массива прошлых данных; ему нужны только результаты предыдущего шага и текущее измерение. Алгоритм элегантно объединяет два источника информации: физическую (математическую) модель системы и показания датчиков. Работа фильтра состоит из бесконечно повторяющегося двухтактного цикла: Предсказание (Predict) и Коррекция (Update).

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

Магия коэффициента усиления Калмана

Суть алгоритма скрыта в вычислении специальной матрицы — коэффициента усиления Калмана (Kalman Gain). Этот коэффициент определяет, кому алгоритм должен доверять больше в данный момент: своей математической модели или показаниям датчика. Если модель очень точная, а датчик сильно шумит (например, во время бури), коэффициент усиления уменьшается, и фильтр игнорирует скачки показаний, опираясь на физику. Если же модель неточна (возник непредсказуемый порыв ветра), а датчик высокоточный, коэффициент усиления возрастает, и фильтр жестко корректирует свою внутреннюю оценку по данным прибора.

Путем умножения матриц и обновления ковариаций, фильтр Калмана математически доказывает, что его оценка является оптимальной (минимизирует среднеквадратичную ошибку) для линейных систем с нормальным гауссовским шумом. Для нелинейных систем (с которыми мы работаем в 99% случаев) был разработан Расширенный фильтр Калмана (EKF), который на каждом шаге линеаризует уравнения с помощью матриц Якоби, оставаясь сегодня абсолютным стандартом в робототехнике, навигации дронов и системах автопилотов.

Подробнее

Глобальная оптимизация: генетические алгоритмы и эволюционные вычисления

Ловушка локальных минимумов

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

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

Биологическая метафора: хромосомы, популяции и отбор

В генетическом алгоритме параметры оптимизируемой задачи кодируются в виде цепочки чисел или битов. Эта цепочка называется «хромосомой» или «геномом» особи. Каждая особь представляет собой одно из возможных решений задачи. Алгоритм работает не с одним решением, а сразу с целой популяцией таких особей (например, генерирует 100 случайных начальных решений, разбросанных по всему пространству поиска).

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

Кроссовер и мутация: двигатели математического прогресса

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

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

Подробнее

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

Отличие краевой задачи от задачи Коши

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

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

Метод стрельбы: искусство прицеливания в математике

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

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

Метод конечных разностей и алгоритм прогонки

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

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

Подробнее
Subscribe to this RSS feed

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

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

Книги

Фильмы

Старый сайт

Соц. сети