назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [ 36 ] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]


36

мер, в п. 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.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [ 36 ] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]