мер, в п. 18.2.1 с т4, т2 и &С (т4, т2) соответственно вместо рассматриваемых нами сейчас х, у и ф (х, г/)), мы будем писать max ф (х, у) и min ф (х, у).
х,У х* У
13.3.3. Здесь может оказаться полезной графическая иллюстрация. Предположим, что областью определения ф для х, у является конечное множество. Обозначим для простоты возможные значения х (в этой области) через 1, . . ., t, а значения у через 1, . . ., s. Тогда значения ф (х, у), соответствующие всем х, у в этой области, т. е. всем комбинациям х = 1, . . . t, у = 1, . . ., s, можно расположить в виде прямоугольной таблицы. Возьмем прямоугольник, у которого t строк и s столбцов. Будем использовать числа х = 1, . . ., t для нумерации строк, а числа у = = 1, . . ., s для нумерации столбцов. На месте пересечения строки х и столбца у (или, говоря короче, в клетке х, у) напишем значение ф (х, у) (табл. 1). Такая таблица чисел, известная в математике под названием прямоугольной матрицы, полностью описывает функцию ф (х, у). Стоящие в таблице значения ф (х, у) называются элементами матрицы.
Таблица 1
| | | | | | |
| Ф(1, 1) | Ф(1,2) | | ф(1, У) | | ф (1 , S) |
| ф(2, 1) | Ф(2, 2) | | ф(2, У) | | Ф(2,*) |
| | | | | | |
| ф (х, 1) | | | ф У) | | ф (xi s) |
| | | | | | |
| ф 1) | Ф(*, 2) | | ф(г, у) | | ф(*, s) |
/ Заметим теперь, что max ф (х, у) есть максимум ф (х, у) в строке х
max max ф (х, у)
х у,
является поэтому максимумом среди максимумов по строкам. С другой стороны,
max ф (х, у)
есть максимум ф (х, у) в столбце у. Следовательно, max max ф (х, у)
является максимумом среди максимумов по столбцам. Наши утверждения в п. 13.3.2 относительно (13:1) можно теперь сформулировать так: максимум среди максимумов по строкам - тот же, что и максимум среди
максимумов по столбцам; оба они являются абсолютным максимумом ф (х, у) в матрице. Во всяком случае, в такой форме эти утверждения должны быть интуитивно ясны. Утверждения относительно (13:2) получаются тем же способом, если вместо шах взять min.
13.4. Смешанный случай. Седловые точки
13.4.1. Рассмотрим теперь (13:3). Используя терминологию п. 13.3.3, мы можем сказать, что левая часть (13:3) есть максимум среди минимумов по строкам, а правая часть - минимум среди максимумов по столбцам. Эти два числа не являются ни абсолютными максимумами, ни абсолютными минимумами, и наперед не видно, почему они должны быть равны. Они и в самом деле не равны. Две функции, для которых они различны, приведены в табл. 2 и табл. 3. Функция, для которой они равны, приведена в табл. 4. (Все эти таблицы должны быть истолкованы в смысле объяснений к табл. 1 в п. 13.3.3).
Таблица 3. t = s = 3 Таблица 4. t = s = 2
Таблица 2. t = s=2
| | | Минимум по строкам |
| | | |
| | | |
Максимум по столбцам | | | |
Максимум среди минимумов по строкам = -1.
Минимум среди максимумов по столбцам=1.
| | | | Минимум по строкам |
| | | | |
| | | | |
| | | | |
Максимум по столбцам | | | | |
Максимум среди минимумов по строкам = - 1.
Минимум среди максимумов по столбцам =1.
| | | Минимум по строкам |
| -2 1 | |
| | | |
Максимум по столбцам | | | |
Максимум среди минимумов по строкам =-1.
Минимум среди максимумов по столбцам=-1.
Эти таблицы, так же как и общий вопрос о коммутативности max и min, будут играть существенную роль в теории игр двух лиц с нулевой суммой. Действительно, мы увидим, что они представляют примеры игр, которые являются типичными для некоторых важных возможностей в этой теории (см. п. 18.1.2). Но в данный момент мы хотим обсудить их сами по себе, без каких-либо ссылок на их приложения.
13.4.2. Так как равенство (13:3) не является ни всегда истинным, ни всегда ложным, желательно рассмотреть связь между двумя его частями
(13:4)
max min ф (х, у) и min max ф (я, у)
х у ух
более полно. Таблицы 2-4, которые в известной степени иллюстрируют поведение (13:3), наводят на некоторые соображения о возможном соотношении между этими выражениями. В частности:
(13:А) Во всех трех таблицах левая часть (13:3) (т. е. первое выражение в (13:4)) правой части (13:3) (т. е. второго выражения в (13:4)).
(13:В) В табл. 4, для которой (13:3) выполняется, существует элемент матрицы, который является одновременно минимальным в своей строке и максимальным в своем столбце. (Таким элементом оказывается здесь -1 в левом нижнем углу матрицы.) В других таблицах - табл. 2, табл. 3 - где (13:3) не выполняется, такого элемента нет.
Целесообразно ввести общее понятие, которое описывает свойства элемента, упомянутого в (13:В). Введем следующее определение.
Пусть ф (х, у) - некоторая функция двух аргументов. В этом случае пара х0, у о называется седловой точкой функции ф, если ф (х, у0) принимает максимальное значение при х = х0, а ф (х0, у) принимает минимальное значение при у = у0.
Причины для использования термина седловая точка таковы. Представим себе матрицу элементов х, у (х - 1, . . ., t, у = 1, . . ., s) как карту горной местности; высотой горы над элементом х, у будем считать значение ф (х, у). Тогда определение седловой точки х0, у0 действительно, по существу, описывает седло, или перевал в этой точке (т. е. над элементом х0, у о); строка х0 является горным хребтом, а столбец у0 - дорогой (от долины к долине), которая пересекает этот хребет.
Формула (13:С*) в п. 13.5.2 тоже находится в соответствии с этой интерпретацией х).
13.4.3. Табл. 2 и табл. 3 показывают, что функция ф может не иметь седловой точки вообще. С другой стороны, возможно, что функция обладает и несколькими седловыми точками. Но на всех седловых точках х0, у0, если они вообще существуют, функция должна достигать одного и того же значения ф (х0, у0)2). Мы обозначим это значение, если оно вообще существует, через SsLx/y ф (х, у) - седловое значение ф (х, у) 3).
Теперь мы сформулируем теоремы, которые обобщают замечания (13:А), (13:В). Мы обозначаем их через (13:А*), (13:В*) (подчеркнем, что они справедливы для всех функций ф (х, у)).
г) Все это тесно связано с некоторыми более общими математическими теориями, содержащими экстремальные проблемы, вариационное исчисление и т. д., хотя, строго говоря, не является частным случаем этих теорий. См. M.Morse, The Critical point of functions and the calculus of variations in the large, Bull. Am. Math. Society, Jan.- Feb. 1929, pp. 38 cont., а также What is analysis in the large? Am. Math. Monthly XLIX (1942), 358 cont.
2) Это следует из (13:C*) в п. 13.5.2. Существует простое непосредственное доказательство этого утверждения. Рассмотрим две седловые точки х0, у0: скажем xQ, у0 и xl, yl.
Тогда
ф (*S, У о) = max ф (х, у0) ф (xl у0) min ф «, у) = ф (a$, yl), х у
т. е. ф (xq, у0) ф (xq, yi). Аналогично ф (xq, yl) ф (х0, у0). Следовательно,
Ф У о) = Ф (*о» Уо)-
3) Ясно, что операция S&x/yq> (#> у) связывает обе переменные х, у. См. п. 13.2.3.