Алгоритм Риша

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

    Назван в честь Роберта Генри Риша. Сам Риш, который разработал алгоритм в 1968 году, называл его «разрешающей процедурой», поскольку метод решает, является ли первообразная от функции элементарной функцией. Наиболее подробное исследование алгоритма представлено на 100 страницах книги «Алгоритмы компьютерной алгебры» Кейта Геддеса, Стефана Цапора и Джорджа Лабана.

Источник: Википедия

Связанные понятия

Элементарные функции — функции, которые можно получить с помощью конечного числа арифметических действий и композиций из следующих основных элементарных функций...
Интеграл Даниеля — одно из обобщений интеграла Римана, альтернативное понятию интеграла Лебега.
Дифференциальная теория Галуа — раздел математики, который изучает группы Галуа дифференциальных уравнений.
Точное нахождение первообразной (или интеграла) произвольных функций — процедура более сложная, чем «дифференцирование», то есть нахождение производной. Зачастую, выразить интеграл в элементарных функциях невозможно.

Подробнее: Методы интегрирования
Быстрые алгоритмы — это область вычислительной математики, которая изучает алгоритмы вычисления заданной функции с заданной точностью с использованием как можно меньшего числа битовых операций.
Квадратичное программирование (англ. quadratic programming, QP) — это процесс решения задачи оптимизации специального типа, а именно — задачи оптимизации (минимизации или максимизации) квадратичной функции нескольких переменных при линейных ограничениях на эти переменные. Квадратичное программирование является частным случаем нелинейного программирования.
Вычислительные (численные) методы — методы решения математических задач в численном видеПредставление как исходных данных в задаче, так и её решения — в виде числа или набора чисел.
Система линейных алгебраических уравнений (линейная система, также употребляются аббревиатуры СЛАУ, СЛУ) — система уравнений, каждое уравнение в которой является линейным — алгебраическим уравнением первой степени.
Обобщённая фу́нкция или распределе́ние — математическое понятие, обобщающее классическое понятие функции.
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных. Также метод Ньютона может быть использован...
Алгоритм Гаусса — Ньютона используется для решения задач нелинейным методом наименьших квадратов. Алгоритм является модификацией метода Ньютона для нахождения минимума функции. В отличие от метода Ньютона, алгоритм Гаусса — Ньютона может быть использован только для минимизации суммы квадратов, но его преимущество в том, что метод не требует вычисления вторых производных, что может оказаться существенной трудностью.
В настоящее время отсутствует единое определение точно решаемой задачи для всех разделов математики. Это обусловлено особенностями самих задач и методов поиска их решения. Вместе с тем базовые теоремы, определяющие наличие и единственность решений, строятся на общих принципах, что будет показано ниже.

Подробнее: Точнорешаемая задача
Метод простой итерации — один из простейших численных методов решения уравнений. Метод основан на принципе сжимающего отображения, который применительно к численным методам в общем виде также может называться методом простой итерации или методом последовательных приближений. В частности, для систем линейных алгебраических уравнений существует аналогичный метод итерации.
Тео́рия алгори́тмов — наука, находящаяся на стыке математики и информатики, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов...
Задача выполнимости формул в теориях (англ. satisfiability modulo theories, SMT) — это задача разрешимости для логических формул с учётом лежащих в их основе теорий. Примерами таких теорий для SMT-формул являются: теории целых и вещественных чисел, теории списков, массивов, битовых векторов и т. п.
Разностная схема — это конечная система алгебраических уравнений, поставленная в соответствие какой-либо дифференциальной задаче, содержащей дифференциальное уравнение и дополнительные условия (например краевые условия и/или начальное распределение). Таким образом, разностные схемы применяются для сведения дифференциальной задачи, имеющей континуальный характер, к конечной системе уравнений, численное решение которых принципиально возможно на вычислительных машинах. Алгебраические уравнения, поставленные...
Численное решение уравнений и их систем состоит в приближённом определении корней уравнения или системы уравнений и применяется в случаях, когда точный метод решения неизвестен или трудоёмок.
Факторизация целых чисел для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Её сложность лежит в основе некоторых алгоритмов шифрования с открытым ключом, таких как RSA.
Функциональное уравнение — уравнение, выражающее связь между значением функции в одной точке с её значениями в других точках. Многие свойства функций можно определить, исследуя функциональные уравнения, которым эти функции удовлетворяют. Термин «функциональное уравнение» обычно используется для уравнений, несводимых простыми способами к алгебраическим уравнениям. Эта несводимость чаще всего обусловлена тем, что аргументами неизвестной функции в уравнении являются не сами независимые переменные, а...
О функции, см.: Интерполянт.Интерполя́ция, интерполи́рование (от лат. inter–polis — «разглаженный, подновлённый, обновлённый; преобразованный») — в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Термин «интерполяция» впервые употребил Джон Валлис в своём трактате «Арифметика бесконечных» (1656).

Подробнее: Интерполяция
Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS) (англ. Broyden — Fletcher — Goldfarb — Shanno algorithm) — итерационный метод численной оптимизации, предназначенный для нахождения локального максимума/минимума нелинейного функционала без ограничений.
Полуопределённое программирование (en: Semidefinite programming, SDP) — это подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством.
Интеграл Лебе́га — это обобщение интеграла Римана на более широкий класс функций.
В математике, матричная функция — это функция, отображающая матрицу в другую матрицу.
Квазианалити́ческие фу́нкции в математическом анализе — класс функций, которые, нестрого говоря, можно полностью реконструировать по их значениям на небольшом участке (например, на границе области). Такое свойство значительно облегчает решение дифференциальных уравнений и исследование других задач анализа. Поскольку это свойство выполняется для аналитических функций (см. Комплексный анализ), то класс квазианалитических функций содержит класс обычных аналитических функций и может рассматриваться как...

Подробнее: Квазианалитическая функция
Вариацио́нное исчисле́ние — раздел анализа, в котором изучаются вариации функционалов. Наиболее типичная задача — найти функцию, на которой заданный функционал достигает экстремального значения.
В статистике, дельта-методом называется результат, описывающий вероятностное распределение функции от асимптотически нормальной статистической оценки при известной асимптотической дисперсии этой оценки.

Подробнее: Дельта-метод
Метод неопределённых коэффициентов ― метод, используемый в математике для нахождения искомой функции в виде точной или приближённой линейной комбинации конечного или бесконечного набора базовых функций.
Многомерный анализ (также известный как многомерное или многовариантное исчисление) является обобщением дифференциального и интегрального исчислений для случая нескольких переменных.
Алгоритм исчисления порядка (index-calculus algorithm) — вероятностный алгоритм вычисления дискретного логарифма в кольце вычетов по модулю простого числа. На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с криптографией. Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный компьютер. Примером такого алгоритма является ГОСТ Р 34.10-2012.
Анзац-подход является важным методом при решении дифференциальных уравнений, где мы можем подставить пробные функции в систему уравнений и проверить наше решение.
Интегра́льное уравне́ние — функциональное уравнение, содержащее интегральное преобразование над неизвестной функцией. Если интегральное уравнение содержит также производные от неизвестной функции, то говорят об интегро-дифференциальном уравнении.
В вычислительной математике одной из наиболее важных задач является создание эффективных и устойчивых алгоритмов нахождения собственных значений матрицы. Эти алгоритмы вычисления собственных значений могут также находить собственные векторы.

Подробнее: Алгоритм вычисления собственных значений
Ля́мбда-исчисле́ние (λ-исчисление) — формальная система, разработанная американским математиком Алонзо Чёрчем, для формализации и анализа понятия вычислимости.
Лине́йная а́лгебра — раздел алгебры, изучающий объекты линейной природы: векторные (или линейные) пространства, линейные отображения, системы линейных уравнений, среди основных инструментов, используемых в линейной алгебре — определители, матрицы, сопряжение. Теория инвариантов и тензорное исчисление обычно (в целом или частично) также считаются составными частями линейной алгебры. Такие объекты как квадратичные и билинейные формы, тензоры и операции как тензорное произведение непосредственно вытекают...
Целевая функция — вещественная или целочисленная функция нескольких переменных, подлежащая оптимизации (минимизации или максимизации) в целях решения некоторой оптимизационной задачи. Термин используется в математическом программировании, исследовании операций, линейном программировании, теории статистических решений и других областях математики в первую очередь прикладного характера, хотя целью оптимизации может быть и решение собственно математической задачи. Помимо целевой функции в задаче оптимизации...
Детерминант Слэтера или слэтеровский детерминант — антисимметричная относительно перестановки частиц волновая функция многочастичной квантовомеханической системы, построенная из одночастичных функций.
Ядерные методы в машинном обучении — это класс алгоритмов распознавания образов, наиболее известным представителем которого является метод опорных векторов (МОВ, англ. SVM). Общая задача распознавания образов — найти и изучить общие типы связей (например, кластеров, ранжирования, главных компонент, корреляций, классификаций) в наборах данных. Для многих алгоритмов, решающих эти задачи, данные, представленные в сыром виде, явным образом преобразуются в представление в виде вектора признаков посредством...

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

Подробнее: Спектральный метод
Интеграл Курцвейля — Хенстока — обобщение интеграла Римана, позволяет полностью решить задачу о восстановлении дифференцируемой функции по её производной. Ни интеграл Римана (в том числе и несобственный), ни интеграл Лебега не дают решения этой задачи в общем случае.
Метод конечных разностей — численный метод решения дифференциальных уравнений, основанный на замене производных разностными схемами. Является сеточным методом.
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Винеровская теория нелинейных систем — подход к решению задач анализа и синтеза нелинейных систем с постоянными параметрами, при котором в качестве математической модели нелинейной системы рассматривается функционал, который ставит в соответствие каждой функции (входному сигналу системы за рассматриваемое время) число (мгновенный выходной сигнал системы).
Вычислительная математика — раздел математики, включающий круг вопросов, связанных с производством разнообразных вычислений. В более узком понимании вычислительная математика — теория численных методов решения типовых математических задач. Современная вычислительная математика включает в круг своих проблем изучение особенностей вычисления с применением компьютеров.
Метод итерации — численный метод решения математических задач, приближённый метод решения системы линейных алгебраических уравнений. Суть такого метода заключается в нахождении по приближённому значению величины следующего приближения (являющегося более точным).
Система уравнений — это условие, состоящее в одновременном выполнении нескольких уравнений относительно нескольких (или одной) переменных.
Дифференциальное уравнение в частных производных (частные случаи также известны как уравнения математической физики, УМФ) — дифференциальное уравнение, содержащее неизвестные функции нескольких переменных и их частные производные.
В математике, норма́льная фо́рма — простейший либо канонический вид, к которому объект приводится эквивалентными преобразованиями.
Метод разделения переменных — метод решения дифференциальных уравнений, основанный на алгебраическом преобразовании исходного уравнения к равенству двух выражений, зависящих от разных независимых переменных.
а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я