Линейные векторные пространства

называются компонентами вектора a = А .

Определение 2.

В матрице из т строк и п столбцов строки являются га- мерными векторами, столбцы — m-мерными векторами и т.д.

Вектор а = (а1,а2,...,а„) и вектор Ь = (b1,b2,...,bn) равны, если совпадают их компоненты, стоящие на одинаковых местах, т.е. если aj = bj при j =1,2,...,га.

Суммой векторов а и Ь называется вектор а + b = = +b1,a2 + b2,...,an + bn). Роль нуля играет нулевой вектор

О = (0,0,...,0).

Противоположным вектору а называется вектор -а = = (-а1,-а2,...,-а„); очевидно, что а + (-а) = 0 .

Разность векторов а - b = а + (-&).

Произведением вектора а на число X называется вектор Ха = (Ха1,Ха2,...,Хап). Из этого определения вытекают следующие важные свойства:

Х(а ±Ь) = Ха± ХЬ, (k ± А.)а = ka ± Ха, k(Xa) = (kX)a.

Следствиями этих свойств являются следующие свойства: 0 • а - 0, (-І)а = -а, X • 0 = 0. Скалярным произведением двух векторов а и & (А и В) называется действительное число, равное сумме произведений соответствующих компонент этих векторов:

АВ = Q-\b\ + а2Ь2 + ... + апЬп.

Например, левая часть линейного уравнения а\Х\ + а2х2 + + ... + апхп = Ъ может быть представлена в виде скалярного

произведения векторов А • X, где А = (а\,а2,...,ап), X =

= (Xl,X2,--;Xn).

Вектор В называется линейной комбинацией векторов А\, А2,..., Ап, если существуют такие числа Я4, Х2,..., Хп, при которых выполняется соотношение В = Я-jAi + Х2А2 + ... + + ХпАп. Система векторов А\, А2,..., АГ (г > 2) называется линейно-зависимой, если хотя бы один из векторов системы является линейной комбинацией остальных, и линейно-независимой — в противном случае.

Система векторов А\, А2,..., Аг — линейно-зависимая, если существуют такие числа Л-j, Х2,..., Хг, не все равные нулю, при которых имеет место равенство Х\А\ + А,зА2 + ... + Х,АГ — 0.

Если последнее соотношение возможно лишь в случае, когда все Xj = 0 (j = 1, г ), то система векторов называется линейно-независимой. Например, система векторов А\ — (2,4,3), А2 = (2,3,1), А3 — (5,3,2), А4 = (1,7,3) линейно-зависима: А\ + + 2А2 - А3 - А4 = 0.

Рангом системы векторов -A-i = (а11,а12,...,а1„),

А2 = (а21>«22>'"'а2л)>

- (omi,cim2,...,amn).

называется максимальное число линейно-независимых векторов этой системы. Ранг системы векторов равен рангу матрицы А, составленной из компонент векторов этой системы, т.е. наивысшему порядку минора матрицы А, отличного от нуля.

L Пример 4. Определить, является ли система векторов Aj - (5,4,3,2), А2 = (3,3,2,2), А3 = (8,1,3,-4) линейно-зависимой; если она линейно-зависима, то найти ее максимальную линейно-независимую подсистему.

Решение. Составим матрицу из компонент векторов и найдем ее ранг. Имеем А =

^5 4 3 . 2s 3 3 2 2 1,8 1 3 -4, 5 4 3 3

= 3*0.

Минор второго порядка Рассмотрим два минора третьего порядка, которые его окаймляют: = 2(59 - 59) = О.

= 118-118 = О,

5 4 3 3 3 2 8 13

5 4 2 3 3 2 8 1-4

Ранг матрицы А равен 2, поэтому система векторов является зависимой. В матрицах, составленных из компонент любых двух векторов данной системы, содержатся миноры второго порядка, отличные от нуля, например, 5 4 3 3 = -21 Ф 0, 5 4 = 3*0, 3 3 8 1 8 1 = -27 ф 0.

Поэтому максимальная линейно-независимая подсистема состоит из двух любых векторов, а третий вектор является их линейной комбинацией. ^

Базисом л-мерного векторного пространства называется любая совокупность п линейно-независимых векторов этого же пространства.

Теорема. Любой вектор л-мерного векторного пространства можно представить как линейную комбинацию векторов базиса, притом единственным образом.

Один из базисов л-мерного векторного пространства образует система единичных векторов

Д2 = (0,1,...,0)

Я„=(0,0,...,1).

Компоненты любого л-мерного вектора можно считать координатами этого вектора в единичном базисе.

Пусть задано л-мерное линейное пространство Еп.

Определение.

Множество на рис. 2.1а выпуклое, на рис. 2.16 — невыпуклое.

a)

Рис. 2.1

Определение. Функция /(X), заданная на выпуклом

множестве X с Еп, называется выпуклой, если для любых двух точек Xi и х2 из X и любого числа 0 < X < 1 выполняется соотношение

f[Xx2 + (1-А.)*!] < Щхг) + (1-Щ*і).

Определение. Функция /(X), заданная на выпуклом множестве X, называется вогнутой, если для любых двух точек Хі и х2 из X и любого числа 0 < А, < 1 выполняется соотношение

f[Xx2 + (1-А.)*!] > Xf(x2) + (l-A,)/(*i).

Если приведенные неравенства считать строгими и они выполняются при 0 < А. < 1, то функция /(X) — строго выпуклая (вогнутая).

Можно показать, что если /(X) — выпуклая функция, то функция -/(X) — вогнутая, и наоборот.

На рис. 2.2а функция /(X) — выпуклая, на рис. 2.26 — вогнутая. X

б)

X

а)

Справедливы следующие утверждения относительно выпуклых множеств и функций. 1.

Пересечение выпуклых множеств есть выпуклое мно> жество. 2.

Сумма вогнутых (выпуклых) функций есть вогнутая (выпуклая) функция. 3.

Вели /(X) — выпуклая функция при X >0, то множество всех точек, удовлетворяющих условиям f(X)< b, X > 0, выпукло (если оно не пустое; Ъ — постоянная). 4.

Пусть f(X) — выпуклая (вогнутая) функция, заданная

на замкнутом выпуклом множестве ХсЁ", тогда любой локальный минимум (максимум) f(X) на X является и глобальным.

Приведем необходимое и достаточное условие выпуклости функции многих переменных. Пусть функция

/(X) = f(xltx2 хп) имеет все частные производные второго

порядка, образующие матрицу d2f d2f d2f 8x1 d2f дх1дх2 d2f дхідхп d2f дх±дх2 дх2 дх2дхп d2f d2f d2f дхпдх1 дхпдх2 дх2 J Эта функция является выпуклой в области X тогда и только тогда, когда матрица Q для любой точки из этой области является неотрицательно (положительно) определенной.

Ян Я12 421 Я22

Яы

42n

9и 9І2 921 ?22

Япі Яп2 Япп

т.е. все главные миноры матрицы Q неотрицательны (положительны).

кь. Пример 5. Показать, что функция f(X) = 2х® * х2 - 6

является выпуклой при Xi > 0.

Составим матрицу из частных производных второго по-

рядка для f(X): Q(X)

Найдем определители

r12jcj 0Л

о oj

Aj = 12*!, Д2 = 0. Так как Ді > 0, Д2 = 0 при Х\ > 0, то функция является выпуклой. Л

Дадим определение глобального и локального максимумов. Функция f(x) достигает на замкнутом (т.е. включающем

свою границу) множестве X глобальный максимум в точке

-ff

х , если для любой точки, принадлежащей Х(х є X), выпол-

1с

няется условие f(x) < f(x ).

Функция f{x) достигает на замкнутом множестве X локального максимума в точке х°, если существует некоторая окрестность этой точки, для каждой точки которой выполняется условие f(x) < f(x°).

На рис. 2.3 *З° — точка

*

локального минимума; Хг — глобального минимума; а, х2° — точки локального максимума; р — точка глобального максимума.

Определения локального и глобального минимума формулируются аналогично.

Необходимые условия экстремума (максимума, минимума). Если в точке х° є X функция f(x) = f(x1,x2,...,xrl) имеет экстремум, то частные производные первого порядка равны нулю в этой точке:

dffjc0) _ — —г = О, ; = 1 ,п.

dXj

Достаточные условия существования экстремума здесь не формулируются. О самом существовании точек глобального минимума и максимума говорит следующая теорема.

Теорема Вейерштрасса. Если функция f(x) определена и непрерывна в ограниченной замкнутой области X, то она достигает в ней своих точных верхней и нижней границ (глобальный максимум и глобальный минимум).

Приведенные утверждения относительно выпуклых множеств и функций, условий существования экстремума позволяют делать выводы о свойствах тех или иных задач оптимального программирования, что является основой разработки и применения математических методов их решения. Например, симплекс-метод решения задачи линейного программирования использует, в частности, «свойство выпуклости» этой задачи: не существует локального экстремума, отличного от глобального.