Список тем численного анализа

Это список численного анализа тем .

Общий

• Проверенные цифры
• Итерационный метод
• Скорость сходимости — скорость, с которой сходящаяся последовательность приближается к своему пределу.
  • Порядок точности - скорость, с которой численное решение дифференциального уравнения сходится к точному решению.
• Ускорение ряда — методы ускорения скорости сходимости ряда.
  • Процесс дельта-квадрата Эйткена - наиболее полезен для линейно сходящихся последовательностей.
  • Минимальная полиномиальная экстраполяция — для векторных последовательностей
  • Экстраполяция Ричардсона
  • Преобразование Шэнкса - аналогично процессу дельта-квадрата Эйткена, но применяется к частичным суммам.
  • Преобразование Ван Вейнгаардена — для ускорения сходимости знакопеременного ряда.
• Абрамовиц и Стегун - книга, содержащая формулы и таблицы многих специальных функций.
  • Цифровая библиотека математических функций — преемница книги Абрамовица и Стегуна
• Проклятие размерности
• Локальная и глобальная конвергенция: нужно ли вам хорошее начальное предположение, чтобы добиться сходимости
• Суперконвергенция
• Дискретизация
• Коэффициент разницы
• Сложность:
  • Вычислительная сложность математических операций
  • Сглаженный анализ — измерение ожидаемой производительности алгоритмов при небольших случайных изменениях входных данных в наихудшем случае.
• Символьно-числовое вычисление — сочетание символьных и числовых методов.
• Культурно-исторические аспекты:
  • История численного решения дифференциальных уравнений с помощью компьютеров
  • Задачи на сто долларов, стозначные задачи - список из десяти задач, предложенных Ником Трефетеном в 2002 году.
  • Международные семинары по решеточной КХД и численному анализу
  • Хронология численного анализа после 1945 года
• Общие классы методов:
  • Метод коллокации — дискретизирует непрерывное уравнение, требуя, чтобы оно выполнялось только в определенных точках.
  • Метод установки уровня
    • Набор уровней (структуры данных) — структуры данных для представления наборов уровней.
  • Численные методы Sinc — методы, основанные на функции sinc, sinc( x ) = sin( x ) / x
  • методы АБС

Ошибка

Анализ ошибок (математика)

• Приближение
• Ошибка аппроксимации
• Катастрофическая отмена
• Номер условия
• Ошибка дискретизации
• с плавающей запятой Число
  • Защитная цифра — дополнительная точность, введенная во время вычислений для уменьшения ошибки округления.
  • Усечение — округление числа с плавающей запятой путем отбрасывания всех цифр после определенной цифры.
  • Ошибка округления
    • Числовая точность в Microsoft Excel
  • Арифметика произвольной точности
• Интервальная арифметика — представляет каждое число двумя числами с плавающей запятой, между которыми гарантированно находится неизвестное число.
  • Интервальный подрядчик — сопоставляет интервал с подинтервалом, который все еще содержит неизвестный точный ответ.
  • Интервальное распространение — сокращение интервальных областей без удаления какого-либо значения, соответствующего ограничениям.
    • См. также: Метод интервальных граничных элементов , Интервальный конечный элемент.
• Потеря значимости
• Числовая ошибка
• Численная стабильность
• Распространение ошибки:
  • Распространение неопределенности
  • Остаток (численный анализ)
• Относительное изменение и разница — относительная разница между x и y равна | х - у | / max(| x |, | y |)
• Значительные цифры
  • Искусственная точность — когда числовое значение или семантика выражаются с большей точностью, чем было первоначально получено в результате измерений или ввода пользователя.
  • Ложная точность — указание более значимых цифр, чем необходимо.
• Лемма
• Ошибка усечения — ошибка, допущенная при выполнении только конечного числа шагов.
• Хорошо поставленная задача
• Аффинная арифметика

Элементарные и специальные функции

• Неограниченный алгоритм
• Суммирование:
  • Алгоритм суммирования Кахана
  • Попарное суммирование — немного хуже суммирования Кахана, но дешевле.
  • Бинарное расщепление
  • 2Сумма
• Умножение:
  • Алгоритм умножения — общее обсуждение, простые методы
  • Алгоритм Карацубы — первый алгоритм, который быстрее простого умножения.
  • Умножение Тума – Кука - обобщение умножения Карацубы.
  • Алгоритм Шёнхаге – Штрассена - основан на преобразовании Фурье, асимптотически очень быстрый.
  • Алгоритм Фюрера - асимптотически немного быстрее, чем Шёнхаге – Штрассена.
• Алгоритм деления — для вычисления частного и/или остатка двух чисел.
  • Длинное деление
  • Восстановление подразделения
  • Невосстанавливающееся деление
  • Отделение СРТ
  • Деление Ньютона-Рафсона : использует метод Ньютона для нахождения обратной величины D и умножает эту обратную величину на N, чтобы найти окончательное частное Q.
  • Гольдшмидтское подразделение
• Возведение в степень:
  • Возведение в степень возведением в степень
  • Возведение в степень по цепочке сложения
• Мультипликативные обратные алгоритмы : для вычисления мультипликативного обратного числа (обратного).
  • метод Ньютона
• Полиномы:
  • метод Горнера
  • Схема Эстрина — модификация схемы Хорнера с большими возможностями распараллеливания.
  • Алгоритм Кленшоу
  • Алгоритм Де Кастельжо
• Квадратные корни и другие корни:
  • Целочисленный квадратный корень
  • Методы вычисления квадратных корней
  • n-й корневой алгоритм
  • гипот — функция ( x ² + и ² ) ^1/2
  • Алгоритм альфа-макс плюс бета-мин — аппроксимирует гипотезу (x,y)
  • Быстрый обратный квадратный корень — вычисляет 1 / √ x, используя детали системы с плавающей запятой IEEE.
• Элементарные функции (экспонента, логарифм, тригонометрические функции):
  • Тригонометрические таблицы — разные способы их составления
  • CORDIC — алгоритм сдвига и сложения с использованием таблицы арктангенсов
  • Алгоритм БКМ — алгоритм сложения и сложения с использованием таблицы логарифмов и комплексных чисел.
• Гамма-функция:
  • Приближение Ланцоша
  • Приближение Спуджа — модификация приближения Стирлинга; легче применять, чем Ланцош
• метод AGM — вычисляет среднее арифметико-геометрическое; связанные методы вычисляют специальные функции
• Метод FEE (быстрая оценка E-функции) — быстрое суммирование рядов, например степенного ряда для e. ^х
• Точные таблицы Гала — таблица значений функций с неравным интервалом для уменьшения ошибки округления.
• Алгоритм Spigot - алгоритмы, которые могут вычислять отдельные цифры действительного числа.
• Приближения π :
  • π-алгоритм Лю Хуэя - первый алгоритм, который может вычислять π с произвольной точностью.
  • Формула Лейбница для π — знакопеременный ряд с очень медленной сходимостью
  • Произведение Уоллиса - бесконечное произведение, медленно сходящееся к π/2.
  • Формула Вьета — более сложное бесконечное произведение, которое сходится быстрее.
  • Алгоритм Гаусса – Лежандра - итерация, которая сходится квадратично к π, на основе среднего арифметико-геометрического.
  • Алгоритм Борвейна - итерация, которая четвертично сходится к 1/π, и другие алгоритмы.
  • Алгоритм Чудновского — быстрый алгоритм вычисления гипергеометрического ряда.
  • Формула Бейли-Борвейна-Плуффа - может использоваться для вычисления отдельных шестнадцатеричных цифр числа π.
  • Формула Белларда — более быстрая версия формулы Бейли–Борвейна–Плуффа.
  • Список формул, включающих π

Численная линейная алгебра

Численная линейная алгебра - исследование численных алгоритмов решения задач линейной алгебры.

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

• Типы матриц, встречающихся в численном анализе:
  • Разреженная матрица
    • Ленточная матрица
    • Двудиагональная матрица
    • Трехдиагональная матрица
    • Пятиугольная матрица
    • Матрица горизонта
  • Циркулирующая матрица
  • Треугольная матрица
  • Диагонально доминирующая матрица
  • Блочная матрица — матрица, состоящая из меньших матриц.
  • Матрица Стилтьеса - симметричная положительно определенная с неположительными недиагональными элементами
  • Матрица Гильберта - пример матрицы, которая крайне плохо обусловлена ​​(и, следовательно, с ней трудно обращаться).
  • Матрица Уилкинсона - пример симметричной трехдиагональной матрицы с парами почти, но не совсем равных собственных значений.
  • Сходящаяся матрица - квадратная матрица, последовательные степени которой приближаются к нулевой матрице.
• Алгоритмы умножения матриц:
  • Уличный алгоритм
  • Алгоритм Копперсмита – Винограда
  • Алгоритм Кэннона — распределенный алгоритм, особенно подходящий для процессоров, расположенных в двухмерной сетке.
  • Алгоритм Фрейвальдса — рандомизированный алгоритм проверки результата умножения.
• Матричное разложение :
  • LU-разложение — нижний треугольник, умноженный на верхний треугольник
  • QR-разложение — ортогональная матрица, умноженная на треугольную матрицу
    • Факторизация RRQR - QR-факторизация, выявляющая ранг, может использоваться для вычисления ранга матрицы.
  • Полярное разложение — унитарная матрица, умноженная на положительно-полуопределенную эрмитову матрицу.
  • Разложения по подобию:
    • Собственное разложение — разложение по собственным векторам и собственным значениям.
    • Жорданова нормальная форма — двудиагональная матрица определенного вида; обобщает собственное разложение
      • Каноническая форма Вейра — перестановка жордановой нормальной формы
    • Разложение Жордана – Шевалле - сумма коммутирующей нильпотентной матрицы и диагонализируемой матрицы.
    • Разложение Шура - преобразование подобия, приводящее матрицу к треугольной матрице.
  • Разложение по сингулярным значениям — унитарная матрица, умноженная на диагональную матрицу, умноженная на унитарную матрицу
• Разделение матрицы - выражение данной матрицы в виде суммы или разности матриц.

Решение систем линейных уравнений

• Исключение по Гауссу
  • Форма эшелона строк — матрица, в которой все записи ниже ненулевой записи равны нулю.
  • Алгоритм Барейсса - вариант, который гарантирует, что все записи остаются целыми числами, если исходная матрица имеет целые записи.
  • Алгоритм трехдиагональной матрицы - упрощенная форма исключения Гаусса для трехдиагональных матриц.
• LU-разложение — запишите матрицу как произведение верхне- и нижнетреугольной матрицы.
  • Разложение матрицы Краута
  • Сокращение LU — специальная распараллеленная версия алгоритма декомпозиции LU.
• Блочное разложение LU
• Разложение Холецкого - для решения системы с положительно определенной матрицей.
  • Алгоритм минимальной степени
  • Символическое разложение Холецкого
• Итеративное уточнение - процедура превращения неточного решения в более точное.
• Прямые методы для разреженных матриц:
  • Фронтальный решатель - используется в методах конечных элементов.
  • Вложенное рассечение — для симметричных матриц на основе разделения графа.
• Рекурсия Левинсона - для матриц Теплица
• Алгоритм SPIKE — гибридный параллельный решатель для узкополосных матриц
• Циклическое сокращение — удалите четные или нечетные строки или столбцы, повторите
• Итерационные методы:
  • метод Якоби
  • Метод Гаусса – Зейделя
    • Последовательное чрезмерное расслабление (SOR) - метод ускорения метода Гаусса – Зейделя.
      • Симметричное последовательное перерасслабление (ССОР) — вариант СОР для симметричных матриц.
    • Алгоритм обратной подгонки - итерационная процедура, используемая для подбора обобщенной аддитивной модели, часто эквивалентная Гауссу – Зейделю.
  • Модифицированная итерация Ричардсона
  • Метод сопряженных градиентов (CG) — предполагает, что матрица положительно определена.
    • Вывод метода сопряженных градиентов
    • Нелинейный метод сопряженных градиентов — обобщение для задач нелинейной оптимизации
  • Метод бисопряженного градиента (BiCG)
    • Метод стабилизации бисопряженного градиента (BiCGSTAB) — вариант BiCG с лучшей сходимостью.
  • Метод сопряженных невязок — аналогичен CG, но только предполагается, что матрица симметрична.
  • Обобщенный метод минимальной невязки (GMRES) — на основе итерации Арнольди.
  • Итерация Чебышева - избегает внутренних продуктов, но требует ограничений спектра.
  • Метод Стоуна (SIP — Строго неявная процедура) — использует неполное LU-разложение.
  • Метод Качмажа
  • Прекондиционер
    • Неполная факторизация Холецкого - разреженное приближение к факторизации Холецкого
    • Неполная LU-факторизация - разреженное приближение к LU-факторизации
  • Итерация Удзавы — для проблем с седловым узлом
• Недоопределенные и переопределенные системы (системы, не имеющие или более одного решения):
  • Численное вычисление нулевого пространства - найдите все решения недоопределенной системы.
  • Псевдообратная задача Мура – ​​Пенроуза - для поиска решения с наименьшей 2-нормой (для недоопределенных систем) или наименьшей невязкой.
  • Разреженная аппроксимация — для поиска самого разреженного решения (т. е. решения с максимально возможным количеством нулей).

Алгоритмы собственных значений

Алгоритм собственных значений — численный алгоритм поиска собственных значений матрицы.

• Итерация мощности
• Обратная итерация
• Итерация фактора Рэлея
• Arnoldi iteration — based on Krylov subspaces
• Алгоритм Ланцоша — Арнольди, специализирующийся на положительно определенных матрицах.
  • Блочный алгоритм Ланцоша - для случаев, когда матрица находится над конечным полем.
• QR-алгоритм
• Алгоритм собственных значений Якоби - выберите небольшую подматрицу, которую можно точно диагонализировать, и повторите.
  • Вращение Якоби — строительный блок, почти вращение Гивенса
  • Метод Якоби для комплексных эрмитовых матриц
• Алгоритм собственных значений «разделяй и властвуй»
• Метод свернутого спектра
• LOBPCG — метод локально оптимального блочного предварительно обусловленного сопряженного градиента
• Возмущение собственных значений - устойчивость собственных значений при возмущениях матрицы.

Другие концепции и алгоритмы

• ортогонализации Алгоритмы :
  • Процесс Грама – Шмидта
  • Преобразование домохозяина
    • Оператор Householder - аналог преобразования Householder для общих пространств внутреннего продукта
  • Ротация Гивенса
• Krylov subspace
• Псевдообратная блочная матрица
• Бидиагонализация
• Алгоритм Катхилла – Макки — меняет местами строки/столбцы в разреженной матрице, чтобы получить узкополосную матрицу.
• Транспонирование матрицы на месте — вычисление транспонирования матрицы без использования большого количества дополнительной памяти.
• Поворотный элемент — запись в матрице, на которой концентрируется алгоритм.
• Безматричные методы — методы, которые получают доступ к матрице только путем оценки матрично-векторных произведений.

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

Интерполяция — постройте функцию, проходящую через некоторые заданные точки данных.

• Интерполяция ближайшего соседа — принимает значение ближайшего соседа.

Полиномиальная интерполяция

Полиномиальная интерполяция — интерполяция полиномами.

• Линейная интерполяция
• Феномен Рунге
• Матрица Вандермонда
• Полиномы Чебышева
• Чебышевские узлы
• Константы Лебега
• Различные формы интерполянта:
  • Полином Ньютона
    • Разделенные различия
    • Алгоритм Невилла — для оценки интерполянта; на основе формы Ньютона
  • Полином Лагранжа
  • Полином Бернштейна — особенно полезен для аппроксимации
  • Формула интерполяции Брахмагупты - формула квадратичной интерполяции седьмого века
• Расширения на несколько измерений:
  • Билинейная интерполяция
  • Трилинейная интерполяция
  • Бикубическая интерполяция
  • Трикубическая интерполяция
  • Точки Падуи — набор точек в R ² с уникальным полиномиальным интерполянтом и минимальным ростом константы Лебега
• Интерполяция Эрмита
• Интерполяция Биркгофа
• Abel–Goncharov interpolation

Сплайн-интерполяция

Сплайн-интерполяция — интерполяция кусочными полиномами.

• Сплайн (математика) — кусочные полиномы, используемые в качестве интерполянтов.
• Совершенный сплайн — полиномиальный сплайн степени m которого равна ±1. , m -я производная
• Кубический сплайн Эрмита
  • Центростремительный сплайн Катмулла – Рома - особый случай кубических сплайнов Эрмита без самопересечений и точек возврата.
• Монотонная кубическая интерполяция
• Эрмитовый сплайн
• Кривая Безье
  • Алгоритм Де Кастельжо
  • составная кривая Безье
  • Обобщения на большее количество измерений:
    • Треугольник Безье — отображает треугольник в R. ³
    • Поверхность Безье — отображает квадрат в R. ³
• B-сплайн
  • Бокс-сплайн — многомерное обобщение B-сплайнов.
  • Усеченная степенная функция
  • Алгоритм Де Бура - обобщает алгоритм Де Кастельжо.
• Неравномерный рациональный B-сплайн (NURBS)
  • Т-сплайн — можно рассматривать как NURBS-поверхность, для которой ряд контрольных точек может заканчиваться.
• Сплайн Кочанека – Бартельса
• Патч Кунса — тип параметризации многообразия, используемый для плавного соединения других поверхностей.
• М-сплайн — неотрицательный сплайн.
• I-сплайн — монотонный сплайн, определенный через M-сплайны.
• Сглаживающий сплайн — сплайн, плавно подогнанный к зашумленным данным.
• Цветение (функционал) — уникальная аффинная симметричная карта, связанная с полиномом или сплайном.
• См. также: Список тем по числовой вычислительной геометрии.

Тригонометрическая интерполяция

Тригонометрическая интерполяция — интерполяция тригонометрическими полиномами.

• Дискретное преобразование Фурье — можно рассматривать как тригонометрическую интерполяцию в эквидистантных точках.
  • Связь между преобразованиями Фурье и рядами Фурье
• Быстрое преобразование Фурье (БПФ) — быстрый метод вычисления дискретного преобразования Фурье.
  • Алгоритм Блюстейна БПФ
  • Алгоритм БПФ Брууна
  • Алгоритм БПФ Кули – Тьюки
  • Алгоритм БПФ с разделенным основанием - вариант Кули – Тьюки, который использует смесь оснований 2 и 4.
  • Алгоритм Герцеля
  • Алгоритм БПФ с простым коэффициентом
  • Алгоритм БПФ Рейдера
  • Перестановка с обращением битов - конкретная перестановка векторов с 2. ^м записи, используемые во многих БПФ.
  • Схема бабочки
  • Коэффициент поворота — тригонометрические постоянные коэффициенты, которые умножаются на данные.
  • Циклотомное быстрое преобразование Фурье - для БПФ над конечными полями
  • Методы вычисления дискретных сверток с фильтрами с конечной импульсной характеристикой с использованием БПФ:
    • Перекрытие – метод добавления
    • Метод сохранения перекрытия
• Сигма-аппроксимация
• Ядро Дирихле - свертка любой функции с ядром Дирихле дает ее тригонометрический интерполянт.
• Феномен Гиббса

Другие интерполяторы

• Простое рациональное приближение
  • Моделирование полиномиальной и рациональной функцией - сравнение полиномиальной и рациональной интерполяции
• Вейвлет
  • Непрерывный вейвлет
  • Матрица переноса
  • См. также: Список тем функционального анализа , Список преобразований, связанных с вейвлетами.
• Обратное взвешивание расстояния
• Радиальная базисная функция (РБФ) — функция вида ƒ( x ) = φ (| x − x ₀ |)
  • Полигармонический сплайн — часто используемая радиальная базисная функция.
  • Тонкий пластинчатый сплайн — особый полигармонический сплайн: r ² журнал г
  • Иерархический RBF
• Поверхность подразделения — построенная путем рекурсивного разделения кусочно-линейного интерполянта.
  • Поверхность подразделения Кэтмалла – Кларка
  • Поверхность подразделения Ду – Сэбина
  • Поверхность разделения контура
• Слерп (сферическая линейная интерполяция) — интерполяция между двумя точками на сфере.
  • Обобщенная интерполяция кватернионов — обобщает slerp для интерполяции между более чем двумя кватернионами.
• Иррациональное базовое дискретно-взвешенное преобразование
• Интерполяция Неванлинны – Пика - интерполяция аналитическими функциями в единичном круге с учетом границы
  • Матрица Пика - интерполяция Неванлинны – Пика имеет решение, если эта матрица является положительно полуопределенной.
• Многомерная интерполяция — интерполируемая функция зависит от более чем одной переменной.
  • Интерполяция Барнса - метод двумерных функций с использованием гауссианов, распространённых в метеорологии.
  • Поверхность Кунса — комбинация линейной интерполяции и билинейной интерполяции
  • Повторная выборка Ланцоша — на основе свертки с функцией sinc
  • Интерполяция естественных соседей
  • Интерполяция значений ближайшего соседа
  • поверхность ПДЭ
  • Трансфинитная интерполяция — строит функцию в плоской области по ее значениям на границе.
  • Анализ поверхности тренда — на основе полиномов пространственных координат низкого порядка; использует разрозненные наблюдения
  • Метод, основанный на полиномах, указан в разделе «Полиномиальная интерполяция».

Теория приближения

Теория приближения

• Порядки приближения
• Лемма Лебега
• Подгонка кривой
  • Реконструкция векторного поля
• Модуль непрерывности — измеряет гладкость функции.
• Наименьшие квадраты (аппроксимация функции) — минимизирует ошибку в L ² -норма
• Алгоритм минимаксной аппроксимации — минимизирует максимальную ошибку на интервале (L ^∞ -норма)
  • Теорема об эквиколебаниях — характеризует наилучшее приближение в L ^∞ -норма
• Несостоятельный набор точек - функция из заданного функционального пространства определяется однозначно значениями на таком наборе точек.
• Теорема Стоуна – Вейерштрасса - непрерывные функции можно равномерно приближать полиномами или некоторыми другими функциональными пространствами.
• Приближение полиномами:
  • Линейное приближение
  • Полином Бернштейна — основа полиномов, полезных для аппроксимации функции.
  • Константа Бернштейна — ошибка при аппроксимации | х | полиномом
  • Алгоритм Ремеза — для построения наилучшего полиномиального приближения в L ^∞ -норма
  • Неравенство Бернштейна (математический анализ) - оценка максимума производной многочлена в единичном круге
  • Теорема Мергеляна - обобщение теоремы Стоуна – Вейерштрасса для полиномов.
  • Теорема Мюнца–Саса — вариант теоремы Стоуна–Вейерштрасса для многочленов, если некоторые коэффициенты должны быть равны нулю.
  • Лемма Брэмбла – Гильберта - верхняя оценка L ^п ошибка полиномиальной аппроксимации в нескольких измерениях
  • Дискретные полиномы Чебышева — полиномы, ортогональные относительно дискретной меры.
  • Теорема Фавара - полиномы, удовлетворяющие подходящим трехчленным рекуррентным соотношениям, являются ортогональными полиномами.
• Приближение рядами Фурье/тригонометрическими полиномами:
  • Неравенство Джексона — верхняя оценка наилучшего приближения тригонометрическим полиномом
    • Теорема Бернштейна (теория приближения) — обратная неравенству Джексона
  • Теорема Фейера - средние Чезаро частичных сумм рядов Фурье сходятся равномерно для непрерывных периодических функций
  • Неравенство Эрдеша – Турана - ограничивает расстояние между вероятностью и мерой Лебега с точки зрения коэффициентов Фурье.
• Различные приближения:
  • Перемещение по методу наименьших квадратов
  • Аппроксимант Паде
    • Таблица Паде - таблица аппроксимаций Паде
  • Теорема Хартогса – Розенталя - непрерывные функции можно равномерно приближать рациональными функциями на множестве нулевой меры Лебега.
  • Оператор Саса – Миракяна - аппроксимация e ^{− п} х ^к на полубесконечном интервале
  • Оператор Саса–Миракяна–Канторовича
  • Оператор Баскакова - обобщает полиномы Бернштейна, операторы Саса – Миракяна и операторы Люпаса.
  • Оператор Фавара — аппроксимация суммами гауссианов
• Суррогатная модель — применение: замена функции, которую сложно вычислить, более простой функцией.
• Конструктивная теория функций - область, изучающая связь между степенью приближения и гладкостью.
• Универсальное дифференциальное уравнение - дифференциально-алгебраическое уравнение, решения которого могут приближать любую непрерывную функцию.
• Задача Фекете — найти на сфере N точек, которые минимизируют некоторую энергию.
• Условие Карлемана — условие, гарантирующее, что мера однозначно определяется своими моментами.
• Условие Крейна — условие плотности экспоненциальных сумм во взвешенном L. ² космос
• Теорема летаргии - об расстоянии точек метрического пространства от членов последовательности подпространств.
• Представление Виртингера и теорема о проектировании
• Журналы:
  • Конструктивное приближение
  • Журнал теории приближения

Разнообразный

• Экстраполяция
  • Линейный прогнозный анализ — линейная экстраполяция
• Унисольвентные функции — функции, для которых задача интерполяции имеет единственное решение.
• Регрессионный анализ
  • Изотоническая регрессия
• Уплотнение по кривой
• Интерполяция (компьютерная графика)

Нахождение корней нелинейных уравнений

См. #Числовая линейная алгебра для линейных уравнений.

Алгоритм поиска корня — алгоритмы решения уравнения f ( x ) = 0

• Общие методы:
  • Метод бисекции — простой и надежный; линейная сходимость
    • Алгоритм Лемера – Шура — вариант для сложных функций
  • Итерация с фиксированной точкой
  • метод Ньютона — основан на линейной аппроксимации текущей итерации; квадратичная сходимость
    • Теорема Канторовича - дает область вокруг решения, в которой сходится метод Ньютона.
    • Фрактал Ньютона — указывает, какое начальное условие к какому корню сходится при итерации Ньютона.
    • Метод квазиньютона — использует приближение якобиана:
      • Метод Бройдена - использует обновление якобиана первого ранга.
      • Симметричный ранг один - симметричное (но не обязательно положительно определенное) обновление якобиана первого ранга.
      • Формула Дэвидона-Флетчера-Пауэлла - обновление якобиана, в котором матрица остается положительно определенной
      • Алгоритм Бройдена-Флетчера-Гольдфарба-Шенно - обновление якобиана второго ранга, в котором матрица остается положительно определенной.
      • Метод BFGS с ограниченной памятью — усеченный, безматрицный вариант метода BFGS, подходящий для больших задач.
    • Метод Стеффенсена - вместо производной используются разделенные разности.
  • Метод секущих — основан на линейной интерполяции на последних двух итерациях.
  • Метод ложного положения — метод секущих с идеями метода деления пополам.
  • Метод Мюллера - основан на квадратичной интерполяции на последних трех итерациях.
  • Обобщенный метод секущего Сиди - варианты метода секущего более высокого порядка
  • Обратная квадратичная интерполяция — аналогична методу Мюллера, но интерполирует обратную квадратичную интерполяцию.
  • Метод Брента — сочетает в себе метод деления пополам, метод секущих и обратную квадратичную интерполяцию.
  • Метод Риддерса — подбирает линейную функцию, умноженную на экспоненту, по последним двум итерациям и их средней точке.
  • Метод Галлея — использует f , f ' и f ''; достигает кубической сходимости
  • Метод Хаусхолдера — использует первые d производные для достижения порядка d + 1; обобщает метод Ньютона и Галлея
• Методы для полиномов:
  • Жертва не удалась
  • Метод Бэрстоу
  • Метод Дюрана – Кернера
  • метод Греффе
  • Алгоритм Дженкинса – Трауба — быстрый, надежный и широко используемый.
  • метод Лагерра
  • Метод расщепления круга
• Анализ:
  • Полином Уилкинсона
• Численное продолжение — отслеживание корня по мере изменения одного параметра в уравнении.
  • Кусочно-линейное продолжение

Оптимизация

Математическая оптимизация - алгоритм поиска максимумов или минимумов заданной функции.

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

• Активный набор
• Вариант решения
• Ограничение (математика)
  • Оптимизация с ограничениями - изучает проблемы оптимизации с ограничениями.
  • Бинарное ограничение — ограничение, в котором участвуют ровно две переменные.
• Угловое решение
• Допустимая область — содержит все решения, которые удовлетворяют ограничениям, но могут не быть оптимальными.
• Глобальный оптимум и локальный оптимум
• Максимумы и минимумы
• Слабая переменная
• Непрерывная оптимизация
• Дискретная оптимизация

Линейное программирование

Линейное программирование (также относится к целочисленному программированию ) — целевая функция и ограничения линейны.

• Алгоритмы линейного программирования:
  • Симплексный алгоритм
    • Правило Бланда - правило, позволяющее избегать циклирования в симплексном методе.
    • Куб Клее–Минти — возмущенный (гипер)куб; симплекс-метод имеет экспоненциальную сложность в такой области
    • Алгоритм крест-накрест - аналогичен симплексному алгоритму.
    • Метод Big M — вариант симплексного алгоритма для задач с ограничениями «меньше» и «больше».
  • Метод внутренней точки
    • Эллипсоидный метод
    • Алгоритм Кармаркара
    • Метод предиктора-корректора Мехротры
  • Генерация столбца
  • k-аппроксимация набора k-попаданий — алгоритм для конкретных задач ЛП (чтобы найти взвешенный набор попаданий)
• Проблема линейной дополнительности
• Разложения:
  • Разложение Бендерса
  • Разложение Данцига – Вольфа
  • Теория двухуровневого планирования
  • Разделение переменных
• Базовое решение (линейное программирование) — решение в вершине допустимой области.
• Элиминация Фурье – Моцкина
• Базис Гильберта (линейное программирование) — набор целочисленных векторов в выпуклом конусе, которые порождают все целочисленные векторы в конусе.
• Проблема типа LP
• Линейное неравенство
• Проблема перечисления вершин - перечислить все вершины допустимого множества.

Выпуклая оптимизация

Выпуклая оптимизация

• Квадратичное программирование
  • Линейный метод наименьших квадратов (математика)
  • Всего наименьших квадратов
  • Алгоритм Франка – Вольфа
  • Последовательная минимальная оптимизация - разбивает большие проблемы QP на серию наименьших возможных проблем QP.
  • Билинейная программа
• Поиск базиса — минимизация L ₁ -нормы вектора с линейными ограничениями.
  • Шумоподавление при поиске базиса (BPDN) — регуляризованная версия преследования при поиске базиса
    • Алгоритм в толпе - алгоритм решения проблемы шумоподавления при преследовании базиса.
• Линейное матричное неравенство
• Коническая оптимизация
  • Полуопределенное программирование
  • Программирование конуса второго порядка
  • Оптимизация суммы квадратов
  • Квадратичное программирование (см. выше)
• Метод Брегмана - метод действия строки для задач строго выпуклой оптимизации.
• Метод проксимального градиента - используйте расщепление целевой функции на сумму возможных недифференцируемых частей.
• Метод субградиента — расширение метода наискорейшего спуска для задач с недифференцируемой целевой функцией.
• Двояковыпуклая оптимизация - обобщение, при котором целевая функция и набор ограничений могут быть двояковыпуклыми.

Нелинейное программирование

Нелинейное программирование — самая общая задача оптимизации в привычных рамках.

• Частные случаи нелинейного программирования:
  • См. Линейное программирование и выпуклую оптимизацию выше.
  • Геометрическое программирование - проблемы, связанные с знаками или полиномами.
    • Сигномиальный - похож на многочлены, но показатели степени не обязательно должны быть целыми числами.
    • Посином — знак с положительными коэффициентами.
  • Квадратичная программа с квадратичными ограничениями
  • Дробно-линейное программирование — цель — соотношение линейных функций, ограничения линейны.
    • Дробное программирование — цель — соотношение нелинейных функций, ограничения линейные.
  • Нелинейная проблема дополнительности (NCP) — найдите x такой, что x ≥ 0, f ( x ) ≥ 0 и x ^Т ж ( Икс ) знак равно 0
  • Наименьшие квадраты — целевая функция представляет собой сумму квадратов.
    • Нелинейный метод наименьших квадратов
    • Алгоритм Гаусса – Ньютона
      • Алгоритм BHHH — вариант Гаусса – Ньютона в эконометрике
      • Обобщенный метод Гаусса – Ньютона - для нелинейных задач наименьших квадратов с ограничениями.
    • Алгоритм Левенберга – Марквардта
    • Итеративно перевзвешенный метод наименьших квадратов (IRLS) — решает взвешенную задачу наименьших квадратов на каждой итерации.
    • Частичные наименьшие квадраты — статистические методы, аналогичные анализу главных компонентов.
      • Нелинейный итерационный метод частичных наименьших квадратов (NIPLS)
  • Математическое программирование с равновесными ограничениями — ограничения включают вариационные неравенства или дополнительности.
  • Одномерная оптимизация:
    • Поиск золотого сечения
    • Последовательная параболическая интерполяция — на основе квадратичной интерполяции на протяжении последних трёх итераций.
• Общие алгоритмы:
  • Концепции:
    • Направление спуска
    • Значение предположения — начальное предположение решения, с которого начинается алгоритм.
    • Поиск линии
      • Поиск строки с возвратом
      • Условия Вульфа
  • Градиентный метод — метод, который использует градиент в качестве направления поиска.
    • Градиентный спуск
      • Стохастический градиентный спуск
    • Итерация Ландвебера - в основном используется для некорректных задач.
  • Последовательное линейное программирование (SLP) — замените проблему задачей линейного программирования, решите ее и повторите.
  • Последовательное квадратичное программирование (SQP) — замените задачу задачей квадратичного программирования, решите ее и повторите.
  • Метод Ньютона в оптимизации
    • См. также раздел «Алгоритм Ньютона» в разделе « Нахождение корней нелинейных уравнений».
  • Нелинейный метод сопряженных градиентов
  • Методы без производных
    • Координатный спуск — движение в одном из координатных направлений.
      • Адаптивный спуск по координатам — адаптируйте направления координат к целевой функции.
      • Случайный спуск по координатам — рандомизированная версия
    • Метод Нелдера-Мида
    • Поиск по шаблону (оптимизация)
    • Метод Пауэлла - основан на сопряженном градиентном спуске.
    • Методы Розенброка — метод без производных, аналогичный методу Нелдера – Мида, но с гарантированной сходимостью.
  • Расширенный метод Лагранжа — заменяет ограниченные задачи неограниченными задачами с добавлением члена к целевой функции.
  • Троичный поиск
  • Табу-поиск
  • Управляемый локальный поиск - модификация алгоритмов поиска, которая увеличивает штрафы во время поиска.
  • Реактивная поисковая оптимизация (RSO) — алгоритм автоматически адаптирует свои параметры.
  • Алгоритм ММ — мажорирование-минимизация, широкий набор методов.
  • Наименьшие абсолютные отклонения
    • Алгоритм ожидания-максимизации
      • Максимизация ожидания упорядоченного подмножества
  • Поиск ближайшего соседа
  • Картографирование пространства — использует «грубые» (идеальные или с низкой точностью) и «точные» (практичные или высокоточные) модели.

Оптимальное управление и бесконечномерная оптимизация

Оптимальное управление

• Принцип минимума Понтрягина — бесконечномерная версия множителей Лагранжа
  • Уравнения Костата - уравнение для «множителей Лагранжа» в принципе минимума Понтрягина.
  • Гамильтониан (теория управления) — принцип минимума гласит, что эту функцию следует минимизировать.
• Типы проблем:
  • Линейно-квадратичный регулятор - динамика системы представляет собой линейное дифференциальное уравнение, цель - квадратичная.
  • Линейно-квадратично-гауссово управление (LQG) - динамика системы представляет собой линейную СДУ с аддитивным шумом, цель квадратичная.
    • Уравнения оптимального проектирования — метод уменьшения размерности задачи управления ЛКГ
• Алгебраическое уравнение Риккати — матричное уравнение, встречающееся во многих задачах оптимального управления.
• Bang-bang control - управление, которое резко переключается между двумя состояниями.
• Принцип ковекторного отображения
• Дифференциальное динамическое программирование - использует локально-квадратичные модели динамики и функции стоимости.
• Точка DNSS - начальное состояние для некоторых задач оптимального управления с несколькими оптимальными решениями.
• Условие Лежандра – Клебша — условие второго порядка решения задачи оптимального управления.
• Псевдоспектральное оптимальное управление
  • Псевдоспектральный метод Беллмана - основан на принципе оптимальности Беллмана.
  • Псевдоспектральный метод Чебышева - использует полиномы Чебышева (первого рода).
  • Плоский псевдоспектральный метод - сочетает в себе псевдоспектральный метод Росса – Фару с дифференциальной плоскостностью.
  • Псевдоспектральный метод Гаусса - использует коллокацию в точках Лежандра – Гаусса.
  • Псевдоспектральный метод Лежандра - использует полиномы Лежандра.
  • Метод псевдоспектрального узла — обобщение псевдоспектральных методов оптимального управления.
  • Псевдоспектральный метод Росса – Фахру - класс псевдоспектральных методов, включающий Чебышева, Лежандра и завязывание узлов.
• Лемма Росса – Фару - условие коммутации операций дискретизации и двойственности.
• Пи-лемма Росса - существует фундаментальная постоянная времени, в пределах которой должно быть вычислено управляющее решение для обеспечения управляемости и устойчивости.
• Модель Сетхи - задача оптимального управления, моделирующая рекламу

Бесконечномерная оптимизация

• Полубесконечное программирование — бесконечное число переменных и конечное число ограничений или наоборот.
• Оптимизация формы , Оптимизация топологии — оптимизация по набору регионов.
  • Топологическая производная - производная по изменению формы.
• Обобщенное полубесконечное программирование — конечное число переменных, бесконечное количество ограничений.

Неопределенность и случайность

• Подходы к борьбе с неопределенностью:
  • Марковский процесс принятия решения
  • Частично наблюдаемый марковский процесс принятия решений
  • Надежная оптимизация
    • Максиминная модель Уолда
  • Оптимизация сценария — ограничения неопределенны
  • Стохастическое приближение
  • Стохастическая оптимизация
  • Стохастическое программирование
  • Стохастический градиентный спуск
• случайной оптимизации Алгоритмы :
  • Случайный поиск — случайный выбор точки в шаре вокруг текущей итерации.
  • Имитация отжига
    • Адаптивный моделируемый отжиг — вариант, при котором параметры алгоритма настраиваются в ходе вычислений.
    • Алгоритм Великого Потопа
    • Отжиг в среднем поле - детерминированный вариант имитации отжига.
  • Байесовская оптимизация — рассматривает целевую функцию как случайную функцию и ставит над ней априорную величину.
  • Эволюционный алгоритм
    • Дифференциальная эволюция
    • Эволюционное программирование
    • Генетический алгоритм , Генетическое программирование
      • Генетические алгоритмы в экономике
    • MCACEA (Эволюционный алгоритм коэволюции нескольких скоординированных агентов) — использует эволюционный алгоритм для каждого агента.
    • Стохастическая аппроксимация одновременных возмущений (SPSA)
  • Луус-Яакола
  • Оптимизация роя частиц
  • Стохастическое туннелирование
  • Поиск гармонии - имитирует процесс импровизации музыкантов.
  • см. также раздел «Метод Монте-Карло».

Теоретические аспекты

• Выпуклый анализ — функция f такая, что f ( tx + (1 − t ) y ) ≥ tf ( x ) + (1 − t ) f ( y ) для t ∈ [0,1]
  • Псевдовыпуклая функция — функция f такая, что из ∇ f · ( y − x ) ≥ 0 следует f ( y ) ≥ f ( x )
  • Квазивыпуклая функция — функция f такая, что f ( tx + (1 − t ) y ) ⩽ max( f ( x ), f ( y )) для t ∈ [0,1]
  • Субпроизводная
  • Геодезическая выпуклость - выпуклость функций, определенных на римановом многообразии.
• Двойственность (оптимизация)
  • Слабая двойственность - двойственное решение дает оценку основному решению.
  • Сильная двойственность — первичные и двойственные решения эквивалентны.
  • Теневая цена
  • Двойной конус и полярный конус
  • Разрыв двойственности — разница между первичным и двойственным решением
  • Теорема двойственности Фенхеля - связывает проблемы минимизации с проблемами максимизации выпуклых сопряжений.
  • Функция возмущения - любая функция, которая относится к основным и двойственным задачам.
  • Условие Слейтера - достаточное условие соблюдения сильной двойственности в задаче выпуклой оптимизации.
  • Полная двойственная целостность — концепция двойственности целочисленного линейного программирования.
  • Двойственность Вульфа - когда целевая функция и ограничения дифференцируемы.
• Лемма Вольфа
• Условия Каруша – Куна – Такера (ККТ) — достаточные условия оптимальности решения.
  • Условия Фрица Джона — вариант условий ККТ
• Множитель Лагранжа
  • Множители Лагранжа в банаховых пространствах
• Полунепрерывность
• Теория дополнительности — исследование задач с ограничениями вида ⟨ u , v ⟩ = 0
  • Проблема смешанной дополнительности
    • Смешанная задача линейной дополнительности
    • Алгоритм Лемке — метод решения (смешанных) задач линейной дополнительности.
• Теорема Данскина - используется при анализе минимаксных задач.
• Теорема о максимуме - максимум и максимизатор непрерывны как функция параметров при некоторых условиях.
• Никаких бесплатных обедов в поиске и оптимизации
• Релаксация (аппроксимация) — приближение заданной задачи более простой задачей путем ослабления некоторых ограничений.
  • Лагранжева релаксация
  • Релаксация линейного программирования - игнорирование ограничений целостности в задаче линейного программирования.
• Самосогласованная функция
• Сниженная стоимость — стоимость увеличения переменной на небольшую величину.
• Твердость аппроксимации — вычислительная сложность получения приближенного решения.

Приложения

• В геометрии:
  • Геометрическая медиана — точка, минимизирующая сумму расстояний до заданного набора точек.
  • Центр Чебышева — центр наименьшего шара, содержащего заданный набор точек.
• В статистике:
  • Итерированные условные режимы — максимизация совместной вероятности марковского случайного поля
  • Методология поверхности отклика - используется при планировании экспериментов.
• Автоматическое размещение этикеток
• Сжатое зондирование — восстановление сигнала на основе знания о том, что он разреженный или сжимаемый.
• Проблема с обрезкой материала
• Оптимизация спроса
• Диспетчеризация по месту назначения — метод оптимизации диспетчеризации лифтов.
• Минимизация энергии
• Максимизация энтропии
• Высоко оптимизированная толерантность
• Оптимизация гиперпараметров
• Проблема с контролем запасов
  • Модель поставщика новостей
  • Расширенная модель поставщика новостей
  • Система сборки на заказ
• Декодирование линейного программирования
• Задача линейного поиска — найти точку на линии, перемещаясь вдоль этой линии.
• Приближение низкого ранга - найти лучшее приближение, ограничение состоит в том, что ранг некоторой матрицы меньше заданного числа.
• Метаоптимизация — оптимизация параметров метода оптимизации.
• Многопрофильная оптимизация проектирования
• Оптимальное распределение вычислительного бюджета — максимизируйте общую эффективность моделирования для поиска оптимального решения.
• Проблема с бумажным пакетом
• Оптимизация процесса
• Рекурсивная экономика — люди с течением времени принимают серию двухпериодных решений по оптимизации.
• Диета Стиглера
• Проблема с распределением пространства
• Стресс-мажоризация
• Оптимизация траектории
• Теория транспорта
• Оптимизация формы крыла

Разнообразный

• Комбинаторная оптимизация
• Динамическое программирование
  • уравнение Беллмана
  • Уравнение Гамильтона – Якоби – Беллмана - аналог уравнения Беллмана с непрерывным временем.
  • Обратная индукция — решение задач динамического программирования путем рассуждения назад во времени.
  • Оптимальная остановка — выбор оптимального времени для совершения того или иного действия.
    • Алгоритм шансов
    • Проблема Роббинса
• Глобальная оптимизация :
  • БРСТ-алгоритм
  • Алгоритм MCS
• Многоцелевая оптимизация — существует несколько противоречивых целей.
  • Алгоритм Бенсона - для линейной векторной оптимизации задач
• Двухуровневая оптимизация - изучает проблемы, в которых одна проблема встроена в другую.
• Оптимальная подструктура
• Алгоритм проекции Дикстры - находит точку пересечения двух выпуклых множеств.
• Алгоритмические концепции:
  • Барьерная функция
  • Метод штрафа
  • Доверительный регион
• Тестовые функции для оптимизации :
  • Функция Розенброка — двумерная функция с долиной в форме банана.
  • Функция Химмельблау — двумерная с четырьмя локальными минимумами, определяемая формулой $f(x,y)=(x^{2}+y-11)^{2}+(x+y^{2}-7)^{2}$
  • Функция Растригина — двумерная функция со многими локальными минимумами.
  • Функция Шекеля — мультимодальная и многомерная
• Общество математической оптимизации

Числовая квадратура (интегрирование)

Численное интегрирование — численная оценка интеграла.

• Метод прямоугольника — метод первого порядка, основанный на (кусочной) постоянной аппроксимации.
• Правило трапеций — метод второго порядка, основанный на (кусочной) линейной аппроксимации.
• Правило Симпсона — метод четвертого порядка, основанный на (кусочной) квадратичной аппроксимации.
  • Адаптивный метод Симпсона
• Правило Буля — метод шестого порядка, основанный на значениях в пяти равноудаленных точках.
• Формулы Ньютона-Котеса - обобщают вышеуказанные методы.
• Метод Ромберга - экстраполяция Ричардсона в применении к правилу трапеций.
• Гауссова квадратура — максимально возможная степень с заданным количеством точек.
  • Квадратура Чебышева – Гаусса - расширение квадратуры Гаусса для интегралов с весом (1 - x ² ) ^±1/2 на [−1, 1]
  • Квадратура Гаусса – Эрмита — расширение квадратуры Гаусса для интегралов с весом exp(− x ² ) на [−∞, ∞]
  • Квадратура Гаусса – Якоби - расширение квадратуры Гаусса для интегралов с весом (1 - x ) ^а (1 + х ) ^б на [−1, 1]
  • Квадратура Гаусса – Лагерра - расширение квадратуры Гаусса для интегралов с весом exp(− x ) на [0, ∞]
  • Квадратурная формула Гаусса – Кронрода - вложенное правило, основанное на квадратуре Гаусса.
  • Правила Гаусса – Кронрода
• Квадратура Тань-Шинь - вариант квадратуры Гаусса, который хорошо работает с особенностями в конечных точках.
• Квадратура Кленшоу – Кертиса - основана на расширении подынтегрального выражения с помощью полиномов Чебышева.
• Адаптивная квадратура — адаптация подинтервалов, на которые делится интервал интегрирования, в зависимости от подынтегральной функции.
• Интеграция Монте-Карло - берет случайные выборки подынтегральной функции.
  • См. также метод #Монте-Карло.
• Метод систем квантованных состояний (QSS) — основан на идее квантования состояний.
• Квадратура Лебедева - использует сетку на сфере с октаэдрической симметрией.
• Разреженная сетка
• Приближение Купмана
• Численное дифференцирование - для интегралов дробного порядка.
  • Численное сглаживание и дифференцирование
  • Метод сопряженного состояния - аппроксимирует градиент функции в задаче оптимизации.
• Формула Эйлера-Маклорена

Численные методы для решения обыкновенных дифференциальных уравнений

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

• Метод Эйлера — самый простой метод решения ОДУ.
• Явные и неявные методы . Неявные методы требуют решения уравнения на каждом этапе.
• Обратный метод Эйлера — неявный вариант метода Эйлера.
• Правило трапеций — неявный метод второго порядка
• Методы Рунге – Кутты — один из двух основных классов методов решения начальных задач.
  • Метод средней точки — метод второго порядка с двумя этапами.
  • Метод Хойна — либо метод второго порядка с двумя этапами, либо метод третьего порядка с тремя этапами.
  • Метод Богацкого-Шампина - четырехэтапный метод третьего порядка (FSAL) и встроенный метод четвертого порядка.
  • Метод Кэша – Карпа — метод пятого порядка с шестью этапами и встроенным методом четвертого порядка.
  • Метод Дормана – Принса — семиэтапный метод пятого порядка (FSAL) и встроенный метод четвертого порядка.
  • Метод Рунге – Кутты – Фельберга - метод пятого порядка с шестью этапами и встроенным методом четвертого порядка.
  • Метод Гаусса – Лежандра - семейство A-стабильных методов с оптимальным порядком, основанных на квадратурах Гаусса.
  • Группа Мясника - алгебраический формализм, включающий корневые деревья для анализа методов Рунге – Кутты.
  • Список методов Рунге – Кутты
• Линейный многошаговый метод — еще один основной класс методов решения начальных задач.
  • Формула обратного дифференцирования — неявные методы порядка 2–6; особенно подходит для жестких уравнений
  • Метод Нумерова — метод четвертого порядка для уравнений вида $y''=f(t,y)$
  • Метод предиктора-корректора - использует один метод для аппроксимации решения, а другой - для повышения точности.
• Общие линейные методы — класс методов, инкапсулирующих линейные многошаговые методы и методы Рунге-Кутты.
• Алгоритм Булирша – Стоера - сочетает в себе метод средней точки с экстраполяцией Ричардсона для достижения произвольного порядка.
• Экспоненциальный интегратор — основан на разделении ОДУ на линейную часть, решаемую точно, и нелинейную часть.
• Методы, предназначенные для решения ОДУ классической физики:
  • Метод Ньюмарка-бета - основан на расширенной теореме о среднем значении.
  • Интеграция Verlet — популярный метод второго порядка.
  • Интеграция Leapfrog — другое название интеграции Verlet.
  • Алгоритм Бимана — двухэтапный метод, расширяющий метод Верле.
  • Динамическая релаксация
• Геометрический интегратор - метод, сохраняющий некоторую геометрическую структуру уравнения.
  • Симплектический интегратор - метод решения уравнений Гамильтона, сохраняющий симплектическую структуру.
    • Вариационный интегратор - симплектические интеграторы, полученные с использованием основного вариационного принципа.
    • Полунеявный метод Эйлера - вариант метода Эйлера, который является симплектическим при применении к разделимым гамильтонианам.
  • Дрейф энергии - явление, при котором энергия, которую следует сохранять, уходит из-за числовых ошибок.
• Другие методы решения задач начального значения (IVP):
  • Двунаправленная линия задержки
  • Схема замещения частичных элементов
• Методы решения двухточечных краевых задач (БВП):
  • Метод съемки
  • Метод прямой многократной съемки — разделяет интервал на несколько подинтервалов и применяет метод съемки к каждому подинтервалу.
• Методы решения дифференциально-алгебраических уравнений (ДАУ), т. е. ОДУ с ограничениями:
  • Алгоритм ограничений — для решения уравнений Ньютона с ограничениями.
  • Алгоритм Пантелидеса — для снижения индекса DEA.
• Методы решения стохастических дифференциальных уравнений (СДУ):
  • Метод Эйлера-Маруямы - обобщение метода Эйлера для СДУ.
  • Метод Мильштейна — метод сильного первого порядка.
  • Метод Рунге-Кутты (СДУ) - обобщение семейства методов Рунге-Кутты для СДУ.
• Методы решения интегральных уравнений:
  • Метод Нистрема — заменяет интеграл правилом квадратур.
• Анализ:
  • Ошибка усечения (числовое интегрирование) — локальные и глобальные ошибки усечения и их взаимосвязь.
    • Веер леди Уиндермир (математика) - телескопическая идентичность, касающаяся локальных и глобальных ошибок усечения
• Жесткое уравнение — грубо говоря, ОДУ, для которого нестабильным методам требуется очень короткий размер шага, а стабильным методам — нет.
  • L-стабильность — метод A-стабилен и функция устойчивости обращается в нуль на бесконечности.
• Адаптивный размер шага — автоматическое изменение размера шага, когда это кажется выгодным.
• Parareal — алгоритм параллельного интегрирования во времени.

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

Численные уравнения в частных производных — численное решение уравнений в частных производных (ЧДУ).

Методы конечных разностей

Метод конечных разностей — основан на аппроксимации дифференциальных операторов разностными операторами.

• Конечная разность — дискретный аналог дифференциального оператора
  • Коэффициент конечной разности - таблица коэффициентов конечно-разностных аппроксимаций производных.
  • Дискретный оператор Лапласа — конечно-разностная аппроксимация оператора Лапласа
    • Собственные значения и собственные векторы второй производной - включают собственные значения дискретного оператора Лапласа.
    • Сумма Кронекера дискретных лапласианов - используется для оператора Лапласа в нескольких измерениях.
  • Дискретное уравнение Пуассона — дискретный аналог уравнения Пуассона с использованием дискретного оператора Лапласа.
• Трафарет (численный анализ) — геометрическое расположение точек сетки, на которое влияет базовый шаг алгоритма.
  • Компактный трафарет — трафарет, в котором используется только несколько точек сетки, обычно только ближайшие и диагональные соседи.
    • Компактная разностная схема высшего порядка
  • Некомпактный трафарет — любой некомпактный трафарет.
  • Пятиточечный трафарет — двумерный трафарет, состоящий из точки и четырех ее непосредственных соседей на прямоугольной сетке.
• Методы конечных разностей для уравнения теплопроводности и связанных с ним УЧП:
  • Схема FTCS (центральное пространство в прямом времени) - явный первый порядок
  • Метод Кранка – Николсона - неявный второй порядок
• Методы конечных разностей для гиперболических УЧП, таких как волновое уравнение:
  • Метод Лакса – Фридрихса — явный метод первого порядка.
  • Метод Лакса – Вендрофа — явный метод второго порядка.
  • Метод МакКормака — явный метод второго порядка
  • Схема против ветра
    • Разностная схема против ветра для конвекции - схема первого порядка для задач конвекции-диффузии
  • Теорема Лакса – Вендрофа - консервативная схема для гиперболической системы законов сохранения сходится к слабому решению.
• Неявный метод чередующегося направления (ADI) — обновление с использованием потока в направлении x , а затем с использованием потока в y . направлении
• Нестандартная конечно-разностная схема
• Конкретные приложения:
  • Методы конечных разностей для ценообразования опционов
  • Метод конечных разностей во временной области - метод конечных разностей для электродинамики.

Методы конечных элементов, методы градиентной дискретизации

Метод конечных элементов — основан на дискретизации пространства решений. метод градиентной дискретизации - основанный как на дискретизации решения, так и на его градиенте.

• Метод конечных элементов в строительной механике - физический подход к методам конечных элементов
• Метод Галёркина — метод конечных элементов, в котором невязка ортогональна пространству конечных элементов.
  • Разрывный метод Галёркина — метод Галеркина, в котором приближенное решение не является непрерывным.
• Метод Рэлея – Ритца — метод конечных элементов, основанный на вариационных принципах.
• Метод спектральных элементов - методы конечных элементов высокого порядка.
• hp-FEM — вариант, в котором автоматически адаптируются и размер, и порядок элементов.
• Примеры конечных элементов:
  • Билинейный четырехугольный элемент , также известный как элемент Q4.
  • Треугольный элемент постоянной деформации (CST), также известный как элемент T3.
  • Квадратичный четырехугольный элемент , также известный как элемент Q8.
  • Элементы барсума
• Метод прямой жесткости — особая реализация метода конечных элементов, часто используемая в структурном анализе.
• Метод Треффца
• Обновление конечных элементов
• Расширенный метод конечных элементов - помещает функции, адаптированные к задаче, в пространство аппроксимации.
• Функционально-градуированные элементы — элементы для описания функционально-градуированных материалов.
• Суперэлемент — особая группа конечных элементов, используемая как один элемент.
• Интервальный метод конечных элементов - сочетание конечных элементов с интервальной арифметикой.
• Дискретное внешнее исчисление — дискретная форма внешнего исчисления дифференциальной геометрии.
• Модальный анализ с использованием МКЭ — решение задач на собственные значения для поиска собственных колебаний.
• Лемма Сеа - решение в пространстве конечных элементов является почти лучшим приближением в этом пространстве истинного решения.
• Патч-тест (конечные элементы) — простой тест качества конечного элемента.
• MAFELAP (MAthematics of Finite ELEments and APplications) — международная конференция в Университете Брюнеля.
• NAFEMS — некоммерческая организация, устанавливающая и поддерживающая стандарты в области компьютерного инженерного анализа.
• Оптимизация многофазной топологии - метод, основанный на конечных элементах, для определения оптимального состава смеси.
• Интервальный конечный элемент
• Прикладной элементный метод — для моделирования трещин и обрушения конструкций.
• Метод Вуда – Армера — метод структурного анализа, основанный на конечных элементах, используемый для расчета арматуры для бетонных плит.
• Изогеометрический анализ — интегрирует конечные элементы в традиционные инструменты проектирования САПР на основе NURBS.
• Итерация Лубиньяка
• Матрица жесткости — конечномерный аналог дифференциального оператора
• Сочетание с бессеточными методами:
  • Ослабленная слабая форма — форма PDE, более слабая, чем стандартная слабая форма.
  • G-пространство - функциональное пространство, используемое при формулировке ослабленной слабой формы.
  • Сглаженный метод конечных элементов
• Вариационный многомасштабный метод
• Список пакетов программного обеспечения для конечных элементов

Другие методы

• Спектральный метод — основан на преобразовании Фурье.
  • Псевдоспектральный метод
• Метод линий — сводит УЧП к большой системе обыкновенных дифференциальных уравнений.
• Метод граничных элементов (МГЭ) — основан на преобразовании УЧП в интегральное уравнение на границе области.
  • Метод интервальных граничных элементов - версия, использующая интервальную арифметику.
• Метод аналитических элементов — аналогичен методу граничных элементов, но интегральное уравнение оценивается аналитически.
• метод конечных объемов — основан на разделении домена на множество мелких доменов; популярный в вычислительной гидродинамике
  • Схема Годунова — консервативная схема первого порядка для течения жидкости, основанная на кусочно-постоянной аппроксимации.
  • Схема MUSCL — вариант схемы Годунова второго порядка.
  • AUSM — адвективный метод расщепления вверх по течению
  • Ограничитель потока - ограничивает пространственные производные (потоки), чтобы избежать паразитных колебаний.
  • Решатель Римана — решатель задач Римана (закон сохранения с кусочно-постоянными данными)
  • Свойства схем дискретизации — методы конечного объема могут быть консервативными, ограниченными и т. д.
• Метод дискретных элементов — метод, при котором элементы могут свободно перемещаться относительно друг друга.
  • Расширенный метод дискретных элементов — добавляет к каждой частице такие свойства, как деформация.
  • Подвижный клеточный автомат — сочетание клеточных автоматов с дискретными элементами.
• Методы Meshfree — не используют сетку, а используют представление поля частицами.
  • Дискретный бессеточный метод наименьших квадратов — основан на минимизации взвешенного суммирования квадратов невязок.
  • Метод диффузного элемента
  • Метод конечного набора точек - представляет континуум облаком точек.
  • Полунеявный метод движущихся частиц
  • Метод фундаментальных решений (МФС) — представляет решение как линейную комбинацию фундаментальных решений.
  • Варианты МФС с точками источника на физической границе:
    • Метод граничного узла (БКМ)
    • Метод граничных частиц (BPM)
    • Регуляризованный бессеточный метод (РММ)
    • Метод сингулярной границы (SBM)
• Методы, предназначенные для решения задач электромагнетизма:
  • Метод конечных разностей во временной области - метод конечных разностей
  • Строгий анализ связанных волн - полуаналитический метод пространства Фурье, основанный на теореме Флоке.
  • Метод матрицы линий передачи (TLM) - основан на аналогии между электромагнитным полем и сеткой линий передачи.
  • Единая теория дифракции , специально разработанная для задач рассеяния.
• Частица в ячейке - особенно используется в гидродинамике.
  • Многофазный метод частиц в ячейках — твердые частицы рассматриваются как числовые частицы и жидкость.
• Схема высокого разрешения
• Метод шоковой фиксации
• Удержание завихренности - для потоков с преобладанием вихрей в гидродинамике, аналогично захвату ударной волны.
• Метод разделенного шага
• Метод быстрого марша
• Ортогональное сочетание
• Решеточные методы Больцмана — для решения уравнений Навье-Стокса.
• Решатель Роу — для решения уравнения Эйлера.
• Релаксация (итерационный метод) — метод решения эллиптических уравнений в частных уравнениях путем преобразования их в эволюционные уравнения.
• Широкие классы методов:
  • Миметические методы — методы, которые в некотором смысле учитывают структуру исходной задачи.
  • Мультифизика — модели, состоящие из различных подмоделей с разной физикой.
  • Метод погруженных границ — для моделирования упругих структур, погруженных в жидкость.
• Мультисимплектический интегратор - расширение симплектических интеграторов, предназначенных для ОДУ.
• Метод растянутой сетки — для решения задач, связанных с поведением упругой сетки.

Методы улучшения этих методов

• Многосеточный метод — использует иерархию вложенных сеток для ускорения методов.
• Методы декомпозиции домена — разделяют домен на несколько поддоменов и решают PDE на этих поддоменах.
  • Аддитивный метод Блэка
  • Абстрактный аддитивный метод Шварца — абстрактная версия аддитивного метода Шварца без привязки к геометрической информации.
  • Метод разложения балансирующей области (BDD) - предобуславливатель для симметричных положительно определенных матриц
  • Балансирующая декомпозиция домена по ограничениям (BDDC) — дальнейшее развитие BDD
  • Разрыв и межсоединение методом конечных элементов (FETI)
  • ФЕТИ-ДП — дальнейшее развитие ФЕТИ
  • Метод фиктивной области - предобуславливатель, построенный с помощью структурированной сетки на фиктивной области простой формы.
  • Методы растворов — сетки на субдомене не объединяются.
  • Метод Неймана – Дирихле - объединяет задачу Неймана в одной подобласти с задачей Дирихле в другой подобласти.
  • Методы Неймана – Неймана - методы декомпозиции области, использующие задачи Неймана в подобластях.
  • Оператор Пуанкаре – Стеклова - отображает тангенциальное электрическое поле на эквивалентный электрический ток.
  • Метод дополнения Шура — ранний и базовый метод для поддоменов, которые не перекрываются.
  • Альтернативный метод Шварца — ранний и базовый метод для перекрывающихся подобластей.
• Грубое пространство - вариант задачи, в котором используется дискретизация с меньшим количеством степеней свободы.
• Адаптивное уточнение сетки — использует вычисленное решение для уточнения сетки только там, где это необходимо.
• Метод быстрых мультиполей — иерархический метод оценки межчастичных взаимодействий.
• Идеально согласованный слой — искусственный поглощающий слой для волновых уравнений, используемый для реализации поглощающих граничных условий.

Сетки и сетки

• Классификация сеток / Типы сеток :
  • Полигональная сетка — состоит из полигонов в 2D или 3D.
  • Треугольная сетка — состоит из треугольников в 2D или 3D.
    • Триангуляция (геометрия) - разделение данной области на треугольники или многомерный аналог.
    • Нетупая сетка — сетка, в которой все углы меньше или равны 90°.
    • Триангуляция множества точек - треугольная сетка, в которой все заданные точки являются вершинами треугольника.
    • Триангуляция полигона — треугольная сетка внутри многоугольника.
    • Триангуляция Делоне - триангуляция, при которой ни одна вершина не находится внутри центра описанной окружности треугольника.
    • Ограниченная триангуляция Делоне - обобщение триангуляции Делоне, которое включает в триангуляцию определенные необходимые сегменты.
    • Триангуляция Питтвея - для любой точки треугольник, содержащий ее, имеет ближайшего соседа этой точки в качестве вершины.
    • Триангуляция минимального веса — триангуляция минимальной общей длины ребра.
    • Кинетическая триангуляция — триангуляция, движущаяся во времени.
    • Триангулированная нерегулярная сеть
    • Квазитриангуляция - разделение на симплексы, где вершины являются не точками, а отрезками с произвольным наклоном.
  • Объемная сетка — состоит из трехмерных фигур.
  • Регулярная сетка - состоит из конгруэнтных параллелограммов или аналога более высокой размерности.
  • Неструктурированная сетка
  • Геодезическая сетка — изотропная сетка на сфере.
• Генерация сетки
  • Создание сетки на основе изображений — автоматическая процедура создания сеток на основе данных трехмерного изображения.
  • Марширующие кубы — извлекает полигональную сетку из скалярного поля.
  • Параллельная генерация сетки
  • Алгоритм Руперта — создает качественную триангуляризацию Делоне на основе кусочно-линейных данных.
• Подразделения:
• Аполлонова сеть — неориентированный граф, образованный рекурсивным разделением треугольника.
• Барицентрическое подразделение - стандартный способ разделения произвольных выпуклых многоугольников на треугольники или его многомерный аналог.
• Улучшение существующей сетки:
  • Второй алгоритм Чу — улучшает триангуляризацию Делоне за счет уточнения треугольников низкого качества.
  • Сглаживание по Лапласу — улучшает полиномиальные сетки за счет перемещения вершин.
• Алгоритм Jump-and-Walk — для поиска треугольника в сетке, содержащей заданную точку.
• Пространственный континуум скручивания - двойное представление сетки, состоящей из шестигранников.
• Псевдотреугольник — односвязная область между любыми тремя взаимно касающимися выпуклыми множествами.
• Симплициальный комплекс — все вершины, отрезки линий, треугольники, тетраэдры,…, составляющие сетку.

Анализ

• Теорема Лакса об эквивалентности - непротиворечивый метод сходится тогда и только тогда, когда он стабилен.
• Условие Куранта – Фридрихса – Леви - условие устойчивости гиперболических УЧП.
• Анализ устойчивости фон Неймана - все компоненты Фурье ошибки должны быть стабильными.
• Численная диффузия - диффузия, введенная численным методом, сверх той, которая естественным образом присутствует.
  • Ложная диффузия
• Численная дисперсия
• Числовое сопротивление — то же, только с сопротивлением вместо диффузии.
• Слабая формулировка - функционально-аналитическая переформулировка УЧП, необходимая для некоторых методов.
• Уменьшение общей вариации — свойство схем, не вносящих паразитных колебаний.
• Теорема Годунова — линейные монотонные схемы могут быть только первого порядка.
• Проблема Моца — эталонная проблема для проблем сингулярности

Метод Монте-Карло

• Варианты метода Монте-Карло:
  • Прямое моделирование Монте-Карло
  • Метод квази-Монте-Карло
  • Цепь Маркова Монте-Карло
    • Алгоритм Метрополиса – Гастингса
      • Multiple-try Metropolis - модификация, позволяющая увеличить размер шага.
      • Алгоритм Ванга и Ландау — расширение Метрополиса Монте-Карло
      • Уравнение вычислений состояния с помощью быстрых вычислительных машин - статья 1953 года, предлагающая алгоритм Метрополиса Монте-Карло.
      • Мультиканонический ансамбль - метод выборки, использующий Метрополис – Гастингс для вычисления интегралов.
    • Выборка Гиббса
    • Соединение из прошлого
    • Цепь Маркова с обратимым прыжком Монте-Карло
  • Динамический метод Монте-Карло
    • Кинетический Монте-Карло
    • Алгоритм Гиллеспи
  • Фильтр твердых частиц
    • Дополнительный сажевый фильтр
  • Обратный Монте-Карло
  • Алгоритм демона
• Выборка псевдослучайных чисел
  • Выборка с обратным преобразованием — общий и простой метод, но дорогостоящий в вычислительном отношении.
  • Отбраковочная выборка — выборка из более простого распределения, но отклонение некоторых выборок.
    • Алгоритм Зиккурата — использует заранее рассчитанную таблицу, охватывающую распределение вероятностей прямоугольными сегментами.
  • Для выборки из нормального распределения:
    • Преобразование Бокса – Мюллера
    • Полярный метод Марсальи
  • Генератор случайных чисел свертки — генерирует случайную величину как сумму других случайных величин.
  • Индексированный поиск
• Методы уменьшения дисперсии :
  • Противоположные варианты
  • Варианты управления
  • Выборка по важности
  • Стратифицированная выборка
  • Алгоритм Вегаса
• Последовательность с низким расхождением
  • Конструирование последовательностей с низким расхождением
• Генератор событий
• Параллельный отпуск
• Зонтичный отбор проб — улучшает отбор проб в физических системах со значительными энергетическими барьерами.
• Гибрид Монте-Карло
• Ансамбльный фильтр Калмана — рекурсивный фильтр, подходящий для задач с большим количеством переменных.
• Выборка пути перехода
• Метод прогулки по сферам - для генерации точек выхода броуновского движения из ограниченных областей.
• Приложения:
  • Ансамблевое прогнозирование — создание нескольких числовых прогнозов на основе слегка начальных условий или параметров.
  • Модель флуктуации связи - для моделирования конформации и динамики полимерных систем.
  • Итерационная фильтрация
  • Легкий транспорт Метрополис
  • Локализация Монте-Карло — оценивает положение и ориентацию робота.
  • Методы Монте-Карло для электронного транспорта
  • Метод Монте-Карло для транспорта фотонов
  • Методы Монте-Карло в финансах
    • Методы Монте-Карло для определения цены опционов
    • Методы квазимонте-карло в финансах
  • Молекулярное моделирование Монте-Карло
    • Молекулярная динамика интеграла по путям - включает интегралы по путям Фейнмана.
  • Квантовый Монте-Карло
    • Диффузия Монте-Карло - использует функцию Грина для решения уравнения Шредингера.
    • Гауссов квантовый метод Монте-Карло
    • Интеграл по траекториям Монте-Карло
    • Рептация Монте-Карло
    • Вариационный Монте-Карло
  • Методы моделирования модели Изинга:
    • Алгоритм Свендсена – Ванга - вся выборка разделена на кластеры с равным спином.
    • Алгоритм Вольфа - улучшение алгоритма Свендсена – Ванга.
    • Алгоритм Метрополиса – Гастингса
  • Вспомогательное поле Монте-Карло — вычисляет средние значения операторов в задачах квантовой механики многих тел.
  • Метод перекрестной энтропии — для многоэкстремальной оптимизации и выборки по важности.
• Также смотрите список тем статистики

Приложения

• Вычислительная физика
  • Вычислительная электромагнетика
  • Вычислительная гидродинамика (CFD)
    • Численные методы в механике жидкости
    • Моделирование больших вихрей
    • Гидродинамика сглаженных частиц
    • Аэроакустическая аналогия - используется в числовой аэроакустике для сведения источников звука к простым типам излучателей.
    • Стохастический метод Эйлера Лагранжа — использует эйлерово описание для жидкостей и лагранжиан для структур.
    • Явная алгебраическая модель напряжения
  • Вычислительная магнитогидродинамика (CMHD) - изучает электропроводящие жидкости.
  • Климатическая модель
  • Численный прогноз погоды
    • Геодезическая сетка
  • Небесная механика
    • Численная модель Солнечной системы
  • Метод квантового скачка - используется для моделирования открытых квантовых систем, работает с волновой функцией.
  • Метод динамического расчета конструкции (DDAM) — для оценки воздействия подводных взрывов на оборудование.
• Вычислительная химия
  • Списки ячеек
  • Связанный кластер
  • Теория функционала плотности
  • DIIS - прямая инверсия в итеративном подпространстве (или из него)
• Вычислительная социология
• Вычислительная статистика

Программное обеспечение

Большой список программного обеспечения см. в списке программного обеспечения для численного анализа .

Журналы

• Акта Нумерика
• Математика вычислений (опубликовано Американским математическим обществом )
• Журнал вычислительной и прикладной математики
• БИТ Численная математика
• Численная математика
• Журналы Общества промышленной и прикладной математики
  • Журнал SIAM по численному анализу
  • Журнал SIAM по научным вычислениям

Исследователи

• Кливский художник
• Джин Х. Голуб
• Джеймс Х. Уилкинсон
• Маргарет Х. Райт
• Николас Дж. Хайэм
• Ник Трефетен
• Питер Лакс
• Ричард С. Варга
• Ульрих В. Кулиш
• Vladik Kreinovich