2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 экстремальные точки множества
Сообщение13.09.2010, 07:15 
Помогите, пожалуйста, разобраться с доказательством.

Даны два множества:

$X=\{(x_1, x_2, ..., x_n)\in R^n, x_j\geq 0, j=1, 2, ..., n, \sum_{j=1}^n{x_j}\leq K\}$;

$Y=\{y\in R^n, y=Ax, x \in X\}$,

здесь $A$ - $m \times n$ матрица.

Нужно доказать, что если $y$ - экстремальная точка $Y$, то $y=Ax$, где $x$ - экстремальная точка $X$.

Рассуждения: предположим противное, т.е.
$y$ - экстремальная точка $Y$, $y=Ax$, но здесь $x$ не является экстремальной точкой $X$.
Это означает, что существуют точки $x_1, x_2, x_1 \neq x_2, x_1 \neq x, x_2 \neq x: x=x_1/2 + x_2/2$.
Умножив это равенство слева на матрицу А, получим
$Ax=Ax_1/2+Ax_2/2$ или $y=y_1/2+y_2/2$, что противоречит тому что $y$ - экстремальная точка.

В этом доказательстве мне непонятно, как мы можем знать, что $Ax_1\neq Ax_2$. Кто-нибудь может помочь? Спасибо.

 
 
 
 Re: экстремальные точки множества
Сообщение13.09.2010, 08:02 
Вектор $y \in \mathbb R^m$. А есть какие-нибудь ограничения на ранг матрицы $A$?

 
 
 
 Re: экстремальные точки множества
Сообщение13.09.2010, 15:02 
Я думаю, что в этом случае матрица $A$ имеет линейно-независимые столбцы. Только не знаю, как это строго доказать.

 
 
 
 Re: экстремальные точки множества
Сообщение13.09.2010, 16:35 
2Alexey1
Цитата:
Вектор $y\in\mathbb{R}^m$

Из условия ясно следует, что $A$ -- квадратная.

2Anya90
Цитата:
В этом доказательстве мне непонятно, как мы можем знать, что $Ax_1\neq Ax_2$

Допустим $Ax_1=Ax_2$. Если умножить обе части на $A^{-1}$, то получится $x_1=x_2$, опаньки. :) Ну это на случай если $A$ -- обратимая.

 
 
 
 Re: экстремальные точки множества
Сообщение13.09.2010, 16:43 
Circiter в сообщении #351945 писал(а):
Из условия ясно следует, что $A$ -- квадратная.
Откуда это следует? В условии написано $A$ это матрица $m \times n$.
Anya90 в сообщении #351908 писал(а):
Я думаю, что в этом случае матрица $A$ имеет линейно-независимые столбцы. Только не знаю, как это строго доказать.
Что значит доказать? Вы условия подгоняйте под доказательство?

 
 
 
 Re: экстремальные точки множества
Сообщение13.09.2010, 17:17 
Alexey1 писал(а):
Откуда это следует?

Ну там же написано $y\in R^{\color{blue}n}$

 
 
 
 Re: экстремальные точки множества
Сообщение13.09.2010, 17:23 
Circiter в сообщении #351964 писал(а):
Ну там же написано $y\in R^{\color{blue}n}$
А дальше что там написано?

 
 
 
 Re: экстремальные точки множества
Сообщение13.09.2010, 17:44 
2Alexey1
Опечатка получается? :)

2Anya90
А там точно в условии $\leqslant K$, а не наоборот? :)

 
 
 
 Re: экстремальные точки множества
Сообщение13.09.2010, 18:49 
Ах, да, это я глупость ляпнул. :)

 
 
 
 Re: экстремальные точки множества
Сообщение14.09.2010, 05:30 
Да, я опечаталась. $y \in R^m$.

Мне непонятно, как доказать, что матрица$A$ обратима. Хватает ли данных условий, чтобы это утверждать?
Натолкните, пожалуйста, на мысль.

 
 
 
 Re: экстремальные точки множества
Сообщение14.09.2010, 05:37 
Если Вам нужно условие при котором матрица $A$ обратима, то это условие: $A$ квадратная матрица с линейно независимыми столбцами.

 
 
 
 Re: экстремальные точки множества
Сообщение14.09.2010, 05:44 
Хорошо. Это не мой случай. Она прямоугольная.

Вариант, предложенный выше, не подходит. Не объясните ли Вы поподробнее, что подразумевалось, когда Вы спрашивали про ранг. Если ранг полный, то столбцы будут л.нез., но как узнать, полный ли он?

 
 
 
 Re: экстремальные точки множества
Сообщение14.09.2010, 05:57 
Если столбцы линейно независимы, то $Ax=\sum\limits_{i=1}^{n}A_ix_i$, где $A_i$ столбцы матрицы $A$, то есть это просто линейная комбинация столбцов. При этих условиях, $Ax_1-Ax_2=A(x_1-x_2)=0$ только в том случае, если $x_1=x_2$, так как столбцы являются линейно независимыми.

 
 
 
 Re: экстремальные точки множества
Сообщение14.09.2010, 09:46 
Аватара пользователя
А что такое экстремальная точка? не лежащая во внутренности отрезка?

 
 
 
 Re: экстремальные точки множества
Сообщение14.09.2010, 18:04 
paha в сообщении #352264 писал(а):
А что такое экстремальная точка? не лежащая во внутренности отрезка?
Эта точка множества которая не может быть представлена как линейная комбинация двух других точек множества, то есть $x$ - экстремальная точка $X$, если $\not{\exists} z,y \in X, \ \not \exists \lambda \in (0,1), \ x = \lambda z+(1-\lambda)y$.

 
 
 [ Сообщений: 24 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group