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


[Старт] [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]


50

Прежде чем доказывать (16:В), заметим, что вторая альтернатива

явным образом исключает первую, поскольку у принадлежит гиперплоскости, а не полупространству (т. е. выполняется (16:2:а), а не (16:2:Ь) из (16:А:Ь)).

Перейдем теперь к доказательству.

Доказательство. Предположим, что у не принадлежит С.

Возьмем тогда точку из С, которая лежит ближе всего к г/, т. е. для которой величина

достигает своего минимального значения.

Рассмотрим любую другую точку и из С. Тогда при любом t, для которого 0 5g t :g 1, tu + (1 - t) z также принадлежит С. Из свойства минимальности точки z (см. выше) мы имеем

\ta + (l-t)z-y\*\l-y\\

т. е.

\(7-y) + t(u-7)\\7-y\\

2 {(zt - у г) +1 (щ - zt)Y 3> S (z, - г/г)2-

г=1 г=1

Выполняя элементарные алгебраические преобразования, мы получаем

2 2 (zi-yi)(ui-zi)t + 2 (Ui-Zi)H0. Для t>0 (причем, конечно, Jgl) имеем, следовательно,

2 2 (Zi-yt)(ut-zi)+ 2 (M*-Zf)2f0.

г=1 г=1

Если £ -> 0, то левая сторона неравенства стремится к

2 2 (zi - yt) (Ui - zt).

Таким образом,

(16:3) 2(**--Жи-**)3=0/

Так как ui - yi - {ui - zi)-\-(Zi - yi), это означает следующее: 2 (а, - г/;) (UJ - г/г)= 2 -Ы2 = Н- 1ГГ3-

г=1 г=1

Далее, гфу (z принадлежит С, а у - нет); следовательно, z - г/2>0. Значит, и левая сторона неравенства >> 0. Мы получаем

(16:4) 2 (Zi-Vi) Щ > 2 (zt -уг) уь

г=1 г=1

11 Дж. Нейман, О. Моргенштерн



Положим ai=zt - yi; тогда случай at = ... =ап = 0 исключается, так как

-* -> *

%Фу (см. предыдущие рассуждения). Положим также Ъ~ 2j aiUi- Таким

образом, равенство

(16:2:а*) Sc = b

->

определяет гиперплоскость, которой точка г/, очевидно, принадлежит. Далее, пусть

(16:2:Ь*) 2***.>ь

- полупространство, порожденное этой гиперплоскостью; тогда (16:4) ->

утверждает, что и принадлежит этому пролупространству.

Поскольку и - произвольный элемент из С, доказательство завершено.

Это алгебраическое доказательство можно провести также на геометрическом языке.

Сделаем это сначала для случая п = 2 (т. е. для плоскости). Ситуация

-> ->•

изображена на рис. 19: z - точка из С, ближайшая к данной точке у;

Гиперплоскость (16-3) Рис. 19. Рис. 20.

это значит, что расстояние z - у \ принимает на z свое минимальное

значение. Поскольку у и z фиксированы, а и-переменная точка (принадлежащая С), неравенство (16:3) определяет гиперплоскость и одно

из полупространств, порожденных ею. Легко проверить, что z принадле-

жит этой гиперплоскости и сама гиперплоскость состоит из точек и, для которых эти три точки образуют прямой угол (т. е. для которых

векторы z - у и и - z %ортогональны). Фактически это означает, что

2 (zt - Уг) (иг - zi) - 0- Очевидно, что все множество С должно лежать

на этой гиперплоскости или по ту сторону от нее, которая не содержит у. Если какая-либо точка и из С лежала бы на г/-стороне,#то нашлись бы точ-

ки из сегмента [z, и], лежащие ближе к г/, чем z. (См. рис. 20. Вычисления на страницах 161-162, в надлежащей интерпретации, именно это и показывают.) Поскольку С содержит зима, следовательно, и весь сегмент [z, и], это противоречит утверждению о том, что точка z является ближайшей точкой к у из точек множества С



§ 16] * ЛИНЕЙНОСТЬ и выпуклость 163

Переход от (16:3) к (16:4) соответствует параллельному переносу гиперплоскости I в положение II (параллельному, ибо коэффициенты

т = Zi - yt при ut, i = 1, . . ., п, не изменяются.) Теперь у принадлежит гиперплоскости, а С - порожденному ею полупространству (рис. 21).

Случай 72 = 3 можно наглядно представить себе сходным образом.

Такой геометрический способ рассуждений можно распространить и на произвольное п. Если читатель сможет убедить себя в том, что он обладает тг-мерной «геометрической интуицией», то Предыдущие рассуждения могут быть восприняты как доказательство, верное в пространстве п измерений. Можно даже избежать и этого, рассуждая следующим способом. Каково бы ни было п, доказательство имеет дело одновременно только с тремя точками, а именно

с точками у, z, и. Через три точки всегда мож- Рис. 21.

но провести плоскость (двумерную). Если мы будем рассматривать только эту плоскость, то рис. 19-21 и связанные с ними рассуждения могут быть использованы без дополнительной интерпретации.

Как бы то ни было, приведенное выше чисто алгебраическое доказательство является абсолютно строгим. Мы привели геометрические аналогии главным образом в надежде, что* это облегчит понимание алгебраических выкладок, выполненных в ходе доказательства.

16.4. Теорема об альтернативах для матриц

16.4.1. Теорема (16:В) позволяет сделать очень важный для нашей дальнейшей работы вывод.

Мы начнем с рассмотрения прямоугольной матрицы в смысле п. 13.3.3 с п строками и т столбцами и элементами a(i, у). (См. рис. 11 в п. 13.3.3, где ф; х, у, t, s соответствуют нашим a, i, j, п, т.) Иными словами, a (i, у) является совершенно произвольной функцией двух переменных i -- = 1, . . ., п и у = 1, . . ., т. Построим некоторые векторы из Ьп.

Для каждого 7 = 1, . . ., т возьмем вектор хд = {х\, . . ., х3п} с х{=

= a (i, 7), а для каждого 1 = 1, . . ., п - координатный вектор 6==

= {6jJ (см. конец п. 16.1.3; мы здесь заменили / на Z). Применим теперь

->

теорему (16:В) из п. 16.3 в случае р = п-{-ткп-{-т векторам х1, ... . . ., хт, б1, . . ., бп (которые выступают в роли х1, . . ., xv). Положим

у = о.

Выпуклое множество С, натянутое на х1, . . ., хт, б1, . . ., бп, может содержать 0. Если это имеет место, то из (16:2:d) в п. 16.2.2 следует, что

(16:5) tO, tm0, sO, sn0,

(16:6) 2*>+Е*г = 1

j=l 1=1

[Старт] [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]