Ассоциативные алгебры

kukina_eg


Задачи и незадачи


Previous Entry Share Next Entry
Положительно определенная форма
Ассоциативные алгебры
kukina_eg
Задача снова из пробного варианта ШАД Яндекс.

Задача. Есть неизвестная нам квадратичная форма Q(v) в n-мерном пространстве. Разрешается задавать вопрос вида "Чему равно Q(v)?" Какое наименьшее количество вопросов надо задать, чтобы определить, является ли форма Q положительно определенной?

Квадратичная форма Q(v) в фиксированном базисе может быть представлена как Q(x1,..., xn)=a11x1x1+...+aijxixj+...+annxnxn.

Квадратичная форма называется положительно определенной, если для любого ненулевого v она принимает положительные значения.

Естественно, мы можем задать какой-то вопрос "чему равно Q(v)" и получить в ответ отрицательное число, после чего сразу отвечаем отрицательно на вопрос о положительной определенности квадратичной формы. А нас интересует, после какого вопроса мы сможем ответить на вопрос гарантировано!

Заметим, что каждый вопрос дает нам линейное уравнение на коэффициенты aij. Всего у нас n(n+1)/2 переменных.

Если система линейных уравнений совместна (а в нашем случае она обязана быть совместна), некоторые переменные мы найдем со всей определенностью (например, a11=5). Некоторые будут независимые и могут быть равными любому числу. А остальные будут зависимые и будут вычисляться в зависимости от независимых. При этом, естественно, вот такие неопределенные, но зависимые переменные мы можем наоборот внести в список независимых переменных. Поэтому по большому счету все переменные делятся на определенные и неопределенные. Одну конкретную неопределенную переменную можно взять равной чему угодно.

Если уравнений меньше, чем переменных, то обязательно будут независимые переменные, т.е. будут неопределенные.
Предположим, что переменная aii неопределенная. Тогда берем ее отрицательной. И значение Q(ei)=aii≤0. Мы не сможем утверждать, что форма положительно определена.

Предположим, что все переменные aii определены и положительны. А переменная aij неопределена. Рассмотрим Q(ei+x ej)=aii+aijx+ajjx^2. Если D=aij2-4iiaij>=0, то у многочлена есть корни и нельзя утверждать, что форма положительно определена. (А взяв достаточно большое aij, этого легко можно добиться).

Таким образом, если вопросов задано меньше, чем n(n+1)/2 мы никак не сможем утверждать, что форма является положительно определенной. (Иногда сможем случайно определить обратное.)

Докажем, что n(n+1)/2 вопросов достаточно.
1. Спрашиваем про Q(ei). Определяем aii.
2. Спрашиваем про Q(ei+ej)=aiijjij. Поскольку aii и аjj мы уже знаем, определяем aij.
Это в сумме как раз нужное количество вопросов.

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

  • 1
Спасибо!

  • 1
?

Log in

No account? Create an account