максимумов по столбцам; оба они являются абсолютным максимумом ф (х, у) в матрице. Во всяком случае, в такой форме эти утверждения должны быть интуитивно ясны. Утверждения относительно (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.

Максимум среди минимумов по строкам =-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.

(13:А*) Всегда

max min ф (х, у) rg min max ф (х, у).

х у ух

(13:В*) Мы имеем

max min ф (х, у) = min max ф (х, у)

х у ух

тогда и только тогда, когда существует седловая точка х0, Уо функции ф.

13.5. Доказательства основных фактов

13.5.1. Во-первых, определим для каждой функции ф (х, у) два множества: Av и В®, min ф (х, у) является функцией от х. Пусть А®

будет множеством всех тех х0, при которых эта функция достигает своего максимального значения. Аналогично max ф (х, у) является функцией

от у. Пусть В® будет множеством всех тех у0, при которых эта функция достигает своего минимального значения. Теперь мы докажем (13:А*) и (13:В*).

Доказательство (13:А*). Выберем х0 из А* и у0 из Бф. Тогда max min ф (х, у) - min ф (х0, у) ф (х0, у о) max ф (х, у0) = min max ф (х, у),

х у у х ух

т. е. max min ф (x, i/) g min max ф (x, г/), что и требовалось.

х у у X

Доказательство необходимости существования седловой точки в (13:В*). Предположим, что

max min ф (х, у) = min max ф (х, у).

х у ух

Выберем х0 в 4Ф и у0 в 5Ф; тогда мы имеем

max ф (х, у о) = min max ф (х, у) = max min ф (х, у) = min ф (х0, у).

х ух х у у

Следовательно, для любого х

Ф (х, у о) max ф (х, у0) = min <р (х0, у) Ф (х0, у0),

т. е. ф (х0, Уо) ф (х, уо), так что ф (х, у0) принимает свое максимальное значение при х = х0. Точно так же для любого у*

Ф (х0, у) min ф (х0, у) = max ф (х, у0) ф (х0, у0),

т. е. ф (яо, у о) Ф (#о, У)\ поэтому ф (х0, у) достигает минимума при у = у0.

Следовательно, пара х0, у0 составляет седловую точку.

Доказательство достаточности существования седловой точки в (13:В*). Пусть х0, Уо - седловая точка. Тогда

max min ф (х, у) min ф (х0, у) = ф (х0, у о),

х у у

min max ф (х, у) max ф (х, у0) = у(х0, Уо)-

ух x