Список тем численного анализа - List of numerical analysis topics

Это Список числовой анализ темы.

Общий

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

Ошибка

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

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

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

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

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

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

Базовые концепты

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

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

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

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

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

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

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

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

Интерполяция и приближение

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

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

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

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

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

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

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

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

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

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

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

Прочие интерполянты

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

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

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

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

Разное

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

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

Видеть # Числовая линейная алгебра для линейных уравнений

Алгоритм поиска корней - алгоритмы решения уравнения ж(Икс) = 0

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

Оптимизация

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

Базовые концепты

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

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

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

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

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

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

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

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

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

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

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

Оптимальный контроль

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

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

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

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

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

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

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

Приложения

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

Разное

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

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

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

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

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

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

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

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

Численные уравнения в частных производных - численное решение дифференциальных уравнений в частных производных (PDE)

Конечно-разностные методы

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

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

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

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

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

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

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

Способы улучшения этих методов

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

Сетки и сетки

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

Анализ

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

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

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

Приложения

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

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

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

Журналы

• Acta Numerica
• Математика вычислений (опубликовано Американское математическое общество )
• Журнал вычислительной и прикладной математики
• BIT вычислительная математика
• Numerische Mathematik
• Журналы из Общество промышленной и прикладной математики
  • Журнал SIAM по численному анализу
  • Журнал SIAM по научным вычислениям

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

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