21 июня 2006 г.

Простая математическая задачка

Задам-ка я простую математическую задачку. :)

Дана плоскость и на ней, для простоты -- координатная сетка. Двумерные вектора на этой плоскости обозначим ri.
Пусть задано отображение ri в r'i = Aijrj + Bi с некоторой симметричной и вещественной матрицей Aij и некоторым, тоже вещественным, двумерным вектором Bi.

Вопрос -- сколько на единичной окружности существует точек ri, для которых r'i окажется параллельно ri?

Если кому-то трудно представлять в терминах матрицы, то можно представить так: действие матрицы Aij на вектор -- это увеличение в ax раз иксовой координаты этого вектора и в ay раз -- игрековой координаты.

[Комментарии на Элементах]

7 комментариев:

  1. Пусть xi и x'i соответственно декартовы координаты вектора и его образа, а N размерность пространства. Условие о параллельности влечет за собой:

    x'i = kxi = Aijxj + Bi

    Или:

    (Aij-kEij)xj=-Bi (1)

    Здесь k это число, которое тоже входит в число неизвестных. Его следует определить из того, что xi лежит на единичной окружности, т.е.:

    xixi=1 (2)

    (1) и (2) образуют замкнутую систему относительно xi и k. В случае когда k такое, что det(Aij-kEij)<>1 систему решаем следующим образом:

    I. Решаем (1) как лин. сист. отн. xi.

    II. Замещаем получение таким образом xi в (2) в результате чего получаем полиномиальное уравнение степени 2N относительно k. Количество реальных корней этого алг. уравнения определяют количество точек на единичной окружности удовлетворяющие условие задачи. Согл. осн. теор. алгебры полином степени 2N имееи 2N комл. корн. Т.е. существуют не более чем 2N точки на един. N-сфере для которых их образ x'i будет параллелен xi в случае когда Bi<>0. Для N=2 вот здесь можно скачать архив с nb-файлом программы Математика, которой решает задачу и строит график точек:

    http://www.savefile.com/files/1959894

    -----

    Если Bi=0, то (1) решается отн. xi когда:

    det(Aij-kEij)=0 (3)

    Отсюда находим k. Имеем не более, чем N реальных корней. Эти корни для k замещаем в (1) из которой убираем одно уравнение. Редуцированная таким образом система отн. xi дополняем с уравн. (2). В зависимость от того сколько реальные корни (3) получаем не более чем N системы отн. xi в которых все уравнения линейные и гомогенные кроме одно, которое квадратично. Если не ошибаюсь у таких систем не более, чем 2N реальных решений. Поскольку у нас не более чем N разных систем отн. xi с одн. кв. уравн., то для Bi=0 могут существовать не более чем 2N^2 точек удовлетворяющих условие задачи. Но этот крайний случай вряд ли реализируется.

    ОтветитьУдалить
  2. Это все понятно -- Вы приходите к уравнению высокой степени, и дальше уже не можете идти, поручая вычисление (аналитические или численное) Математике. Но это не отвечает на поставленный вопрос -- ведь требется узнать, сколько именно при заданных Aij и Bi, и ответ "не более чем" не годится.

    Хитрость в этой задаче состоит в том, что решить ее можно самостоятельно и аналитически, минуя уравнение высокого порядка. И ответ получается довольно простой. По ссылке "Комментарии на Элементах" всё рассказано.

    ОтветитьУдалить
  3. Константин25/1/12 00:16

    не понимаю, для чего вы усложняете задачу, говоря о плоскости в пространстве, ведь с тем же успехом можно говорить просто о двумерной системе координат (тем более, вы даёте вектора r как двумерные - т.е. плоскость на которой они находятся сама не является подпространством ℝ³). Вектор B является вектором параллельного переноса и не влияет на направление r'. Если вектор B задан однозначно, к чему тогда нижний индекс i? Он, на мой взгляд так же не требуется и для вектора r.

    Так же непонятно мне и описание действия симметричной вещественной матрицы в последнем абзаце. Возьмём симметричную матрицу ((2,3),(3,5)). Результатом её действия на вектор (1,0) будет (2,3), а результатом для вектора (0,1) будет (3,5), что не соответствует вашему описанию. Желаемое вами действие описывается матрицей ((x,0),(0,y)).



    Решение этой задачи сводится к вопросу о собственных векторах - так как только для них векторы-отображения могут быть параллельны (или антипараллельны) исходным векторам r. В данном случае (в случае, если матрица А является симметричной матрицей 2x2) их два! Причём, о симметричных матрицах мы знаем, что её собственные векторы всегда ортогональны друг другу. Так же мы знаем, что в случае симметричных матриц из её собственных векторов всегда можно составить ортонормальный базиз, поэтому их именно два, а не максимиум два. Поскольку векторы в противоположном им направлении будут также собственными, всего мы имеем четыре вектора r на окружности, для которых r' окажется параллельным r.


    Векторы на единичной окружности имеют координаты (cos(φ),sin(φ)). Для частного случая симметричной 2x2-матрицы вида ((a,b),(b,a)) результатом действия этой матрицы на вектор на единичной окружности будет вектор ((a*cos(φ) + b*sin(φ)),((b*cos(φ) + a*sin(φ))), который является кратным вектора (cos(φ),sin(φ)) только в случае, если cos(φ) = sin(φ) или cos(φ) = -sin(φ), что верно только для углов pi/4, 3pi/4, 5pi/4 и 7pi/4. Поэтому для таких матриц точками r на окружности, для которых r' окажется параллелен r, всегда будут точки в направлении векторов (1,1), (-1,1), (-1,-1) и (1,-1), т.е. в точки на пересечении круга и биссектрис каждого из квадрантов.

    ОтветитьУдалить
  4. Константин25/1/12 00:38

    Для общего случая симметричных 2х2-матриц вида ((a,b),(b,c)) результатом их действия на векторы на единичной окружности будет вектор ((a*cos(φ) + b*sin(φ)),((b*cos(φ) + с*sin(φ))). Он является кратным вектора (cos(φ),sin(φ)) в том случае, если

    a*cos(φ) + b*sin(φ) = x*cos(φ)
    b*cos(φ) + с*sin(φ) = x*sin(φ)

    <=>

    a + b*tan(φ) = x
    b*cot(φ) + c = x

    <=> a + b*tan(φ) = b*cot(φ) + c

    <=> (a - c)/b = (cot(φ) - tan(φ))

    <=> (a - c)/b = cos(φ)/sin(φ) - sin(φ)/cos(φ)

    <=>

    (a - c)/b = (cos^2(φ) - sin^2(φ))/(sin(φ)cos(φ))

    <=> (a - c)/b = (cos(2φ))/(1/2*sin(2φ))

    <=> (a - c)/b = 2*cot(2φ)

    => φ = 1/2*arccot((a - c)/b)

    Для такого угла φ на единичной окружности будет вектор, который через симметричную матрицу А отобразится на параллельный себе вектор. По причинам, описанным выше, то же самое будет действительно для обоих векторов, стоящих ортогонально к нему, а так же к противоположному вектору (т.е. всего четыре).


    ________________

    Буду очень рад вашему отклику на мой ответ! :) Я нашёл ваш блог по запросу в яднексе "что интересного происходит в математике". Удачи!

    P.S.: прошу прощения за не совсем корректную математическую речь, своё математическое образование я получал (может быть, к сожалению) не в России. Буду рад, если вы поправите меня в моих выражениях.

    ОтветитьУдалить
  5. Константин25/1/12 00:40

    Ну вот! :D Прочитал о вас - я запросто всё то же самое мог бы написать на немецком! xDD

    ОтветитьУдалить
  6. Константин25/1/12 00:56

    хм, почитал комментарии на элементах и понял, что я поторопился отбросить вектор B параллельного перемещения, как не влияющий на ситуацию. Наверное, грубая ошибка. Ну хорошо, я рассмотрел только линейную часть. Взгляну попозже потом ещё внимательно.

    ОтветитьУдалить
  7. Константин, да, конечно, вектор B принципиально важен. Задача по-прежнему остается задачей о собственных векторах динейного преобразования, но имеющего нетривиальный сдвиг.

    Вообще, решение я написал давно на «Элементах», см. ссылку внизу поста.

    ОтветитьУдалить