В математике монотонная функция (или монотонная функция ) — это функция между упорядоченными множествами , которая сохраняет или меняет заданный порядок . [1] [2] [3] Эта концепция впервые возникла в исчислении , а затем была обобщена на более абстрактную теорию теории порядка .
В исчислении функция, определенная на подмножестве действительных чисел с действительными значениями, называется монотонной тогда и только тогда, когда она либо полностью не возрастает, либо совершенно не убывает. [2] То есть, согласно рис. 1, функция, которая монотонно возрастает, не обязательно должна только возрастать, она просто не должна убывать.
Функция называется монотонно возрастающей (также возрастающей или неубывающей ) [3] , если для всех и таких, что имеется , поэтому сохраняется порядок (см. рисунок 1). Аналогично, функция называется монотонно убывающей (также убывающей или невозрастающей ) [3] , если всякий раз , когда , то , поэтому она меняет порядок на обратный (см. рисунок 2).
Если порядок в определении монотонности заменить на строгий порядок , то получим более сильное требование. Функция, обладающая таким свойством, называется строго возрастающей (также возрастающей ). [3] [4] Опять же, инвертируя символ порядка, можно найти соответствующее понятие, называемое строго убывающим (также убывающим ). [3] [4] Функция, обладающая любым из этих свойств, называется строго монотонной . Функции, которые являются строго монотонными, являются взаимно однозначными (потому что для не равно , либо или и так, по монотонности, либо или , таким образом .)
Чтобы избежать двусмысленности, термины «слабо монотонно» , «слабо возрастающее » и «слабо убывающее» часто используются для обозначения нестрогой монотонности.
Термины «неубывающий» и «невозрастающий» не следует путать с (гораздо более слабыми) отрицательными определениями «не убывающий» и «не возрастающий». Например, немонотонная функция, показанная на рисунке 3, сначала падает, затем возрастает, затем снова падает. Следовательно, оно не уменьшается и не увеличивается, но оно не является ни неубывающим, ни невозрастающим.
Функция называется абсолютно монотонной на интервале , если производные всех порядков неотрицательны или неположительны во всех точках интервала.
Все строго монотонные функции обратимы , поскольку они гарантированно имеют взаимно однозначное отображение своего диапазона в свою область определения.
Однако функции, которые являются лишь слабо монотонными, не являются обратимыми, поскольку они постоянны на некотором интервале (и, следовательно, не являются взаимно однозначными).
Функция может быть строго монотонной в ограниченном диапазоне значений и, следовательно, иметь обратную функцию в этом диапазоне, даже если она не является строго монотонной всюду. Например, если строго возрастает в диапазоне , то оно имеет инверсию в диапазоне .
Термин «монотонный» иногда используется вместо « строго монотонный» , поэтому источник может утверждать, что все монотонные функции обратимы, хотя на самом деле это означает, что все строго монотонные функции обратимы. [ нужна цитата ]
Термин монотонное преобразование (или монотонное преобразование ) также может вызвать путаницу, поскольку он относится к преобразованию с помощью строго возрастающей функции. Так обстоит дело в экономике, когда порядковые свойства функции полезности сохраняются при монотонном преобразовании (см. Также монотонные предпочтения ). [5] В этом контексте термин «монотонное преобразование» относится к положительному монотонному преобразованию и предназначен для того, чтобы отличить его от «отрицательного монотонного преобразования», которое меняет порядок чисел. [6]
Для монотонной функции справедливы следующие свойства :
Эти свойства являются причиной того, почему монотонные функции полезны в технической работе по анализу . Другие важные свойства этих функций включают в себя:
Важным применением монотонных функций является теория вероятностей . Если – случайная величина , ее кумулятивная функция распределения является монотонно возрастающей функцией.
Функция называется унимодальной, если она монотонно возрастает до некоторой точки ( мода ), а затем монотонно убывает.
Когда - строго монотонная функция, то она инъективна в своей области определения, а если - область значений , то существует обратная функция для . Напротив, каждая постоянная функция монотонна, но не инъективна [7] и, следовательно, не может иметь обратной.
На графике показаны шесть монотонных функций. Их простейшие формы показаны в области графика, а выражения, использованные для их создания, показаны на оси Y.
Отображение называется монотонным , если каждый его слой связен ; то есть для каждого элемента множество (возможно, пустое) представляет собой связное подпространство
В функциональном анализе топологического векторного пространства оператор (возможно, нелинейный) называется монотонным оператором, если
Подмножество называется монотонным, если для каждой пары и в ,
Теория порядка рассматривает произвольные частично упорядоченные множества и предупорядоченные множества как обобщение действительных чисел. Приведенное выше определение монотонности актуально и в этих случаях. Однако термины «увеличение» и «уменьшение» избегаются, поскольку их обычное графическое представление не применимо к неполным порядкам . Более того, строгие отношения и во многих нетотальных порядках малопригодны, и поэтому для них не вводится дополнительная терминология.
Обозначаем отношение частичного порядка любого частично упорядоченного множества, монотонную функцию, также называемую изотонной , илисохраняющий порядок , удовлетворяющий свойству
для всех x и y в своей области. Композиция двух монотонных отображений также монотонна.
Двойное понятие часто называют антитоном , антимонотонностью или изменением порядка . Следовательно, функция антитона f удовлетворяет свойству
для всех x и y в своей области.
Постоянная функция бывает одновременно монотонной и антитонной; и наоборот, если f одновременно монотонна и антитонна и если область определения f представляет собой решетку , то f должно быть постоянным.
Монотонные функции занимают центральное место в теории порядка. Они появляются в большинстве статей на эту тему и в этих местах встречаются примеры из специальных приложений. Некоторые известные специальные монотонные функции являются вложениями порядка (функции, для которых тогда и только тогда и изоморфизмы порядка ( сюръективные вложения порядка).
В контексте поисковых алгоритмов монотонность (также называемая согласованностью) — это условие, применяемое к эвристическим функциям . Эвристика является монотонной, если для каждого узла n и каждого преемника n' из n , сгенерированного любым действием a , предполагаемая стоимость достижения цели из n не превышает стоимость шага достижения n' плюс предполагаемая стоимость достижения цель от n' ,
Это форма неравенства треугольника с n , n' и целью Gn , ближайшей к n . Поскольку любая монотонная эвристика также допустима , монотонность является более строгим требованием, чем допустимость. Некоторые эвристические алгоритмы, такие как A*, могут оказаться оптимальными при условии, что используемая ими эвристика монотонна. [8]
В булевой алгебре монотонной функцией называется такая функция, что для всех a i и b i из {0,1} , если a 1 ⩽ b 1 , a 2 ⩽ b 2 , ..., a n ⩽ b n (т. е. Декартово произведение {0, 1} n упорядочено по координатам ), тогда f( a 1 , ..., a n ) ≤ f( b 1 , ..., b n ) . Другими словами, булева функция является монотонной, если для каждой комбинации входных данных переключение одного из входных данных с ложного на истинное может привести только к переключению вывода с ложного на истинное, а не с истинного на ложное. Графически это означает, что n -арная булева функция является монотонной, когда ее представление в виде n -куба , помеченного значениями истинности, не имеет восходящего края от true до false . (Эта помеченная диаграмма Хассе является двойственной помеченной диаграмме Венна функции , которая является более распространенным представлением для n ≤ 3. )
Монотонные логические функции — это именно те, которые можно определить с помощью выражения, объединяющего входные данные (которое может встречаться более одного раза), используя только операторы и и или (в частности, не запрещено). Например, «содержится хотя бы два из a , b , c » — это монотонная функция от a , b , c , поскольку ее можно записать, например, как (( a и b ) или ( a и c ) или ( b и c )).
Число таких функций от n переменных известно как число Дедекинда n .
Решение SAT , как правило, NP-сложная задача, может быть эффективно достигнуто, когда все задействованные функции и предикаты являются монотонными и логическими. [9]