Задача по линейной алгебре на тему билинейные формы

[khuglar]

Здравствуйте помогите решить задачу:

За столом сидят $n$ старателей, перед каждым из которых находится кучка золотого песка. Каждую минуту происходит следующее: по общей команде каждый из них перекладывает в свою кучку половину песка из кучки левого соседа и половину – из кучки правого соседа.
Опишите асимптотическое поведение кучек
(а) при $n = 3$;
(б) при произвольном $n$

Я решил для (a), получилось что у всех старателей в итоге будет одинаково золота.
Я нашел матрицу преобразования(команду когда им говорят взять песок у соседних).

$$\begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & 0 & \frac{1}{2}\\ \frac{1}{2} & \frac{1}{2} & 0 \end{bmatrix}$$

В общем нашел у этой матрицы собственные значение, потом вектора, разложил на $CAC^1$ и посчитал. Для общего случая не понимаю что делать.

[zykov]

khuglar в сообщении #1582537 писал(а):

Для общего случая не понимаю что делать.

Для нечётного $n$ так же к среднему сходится.
Для чётного $n$ сходится к бистабильному случаю (как например для вектора $(0,1,0,1)$).
Это если сумма чётных номеров не равна сумме нечётных. Если равны, то тоже к среднему сходится.

[Null]

Собственные вектора с комплексными элементами легко подбираются. От сюда можно найти собственные значения.

[khuglar]

Я знаю что для решение нужно найти предел от $x_n = A \cdot x_{n-1}$, но не понимаю как предел найти. Там по идее все сходится к тому, что эти землекопы переходят в собственные значения матрицы.

[Null]

Найдите собственные векторы оператора. Это вполне реально.

[StepV]

khuglar в сообщении #1582537 писал(а):

Я нашел матрицу преобразования(команду когда им говорят взять песок у соседних).

Неоднозначно можно понимать условие. У вас получилась матрица, когда каждый отдает двум другим по половине своей кучки, и получает у соседей их половины. Т.е. операция идет в один этап. Если считать, что все-таки операция происходит в два этапа:
этап 1: у каждого остается половина его кучки плюс половина кучки соседа слева,
этап 2: из нового количества остается половина плюс половина кучки соседа справа.
Тогда матриц две, но результат для трех игроков остается тотже.

[khuglar]

StepV в сообщении #1582655 писал(а):

khuglar в сообщении #1582537 писал(а):

Я нашел матрицу преобразования(команду когда им говорят взять песок у соседних).

Неоднозначно можно понимать условие. У вас получилась матрица, когда каждый отдает двум другим по половине своей кучки, и получает у соседей их половины. Т.е. операция идет в один этап. Если считать, что все-таки операция происходит в два этапа:
этап 1: у каждого остается половина его кучки плюс половина кучки соседа слева,
этап 2: из нового количества остается половина плюс половина кучки соседа справа.
Тогда матриц две, но результат для трех игроков остается тотже.

Все происходит в 1 этап

[мат-ламер]

Наверное топик-стартер разобрался с задачей. А я кое-что не понял.

Null в сообщении #1582592 писал(а):

Собственные вектора с комплексными элементами легко подбираются. От сюда можно найти собственные значения.

Null в сообщении #1582638 писал(а):

Найдите собственные векторы оператора. Это вполне реально.

Для нечётных $n$ можно догадаться, что одно собственное значение равно единице и можно догадаться про соответствующий собственный вектор. А что с остальными собственными значениями? По-видимому они по модулю не больше единицы. Но нам желательно доказать, что они все по модулю строго меньше единицы. Для чётных $n$ можно догадаться, что есть собственные значения $+1$ и $-1$ и можно догадаться на счёт соответствующих собственных векторов. А что на счёт остальных собственных значений?

А если решать вообще без матриц, то можно догадаться на счёт стабильного состояния. Но нам же надо доказать сходимость к нему.

И причём тут билинейные формы?

-- Чт фев 23, 2023 15:04:38 --

Может решать надо просто найдя предел $B=\lim \limits_{k \to \infty} A^k$ . Для нечётных $n$ (это размерность матрицы) все элементы матрицы B по-видимому равны $1 \slash n$ . Для чётных $n=2m$ элементы матрицы $B$ с чётной суммой номера строки столбца равны $1\slash m$ . Остальные элементы нулевые. Доказать это наверное можно с помощью некоторых рекуррентных соотношений. Но является этот путь решения задачи самым простым, не знаю.

-- Чт фев 23, 2023 15:30:37 --

Можно, наверное, решать и так (вариант для нечётных $n$ ). Рассмотреть величину $(x_1-x_2)^2+...+(x_n-x_1)^2$ и показать, что она уменьшается (причём, с определённой скоростью).

[мат-ламер]

Чуток прояснилось. Поскольку матрица $A$ симметрична, то её собственные значения действительны и она диагонализируема. Подробности чуть позже.

[Null]

мат-ламер в сообщении #1582930 писал(а):

И причём тут билинейные формы?

Не знаю.
$k$-тый собственный вектор $(e^{\frac{2\pi ki}{n}},e^{\frac{4\pi ki}{n}},\dots, e^{\frac{2(n-1)\pi ki}{n}})$
Соответствующее собственное значение $\cos(\frac{2\pi k}{n})$

[мат-ламер]

Null Спасибо! Пока изложу кратко своё видение проблемы, подробности оставляя топик-стартеру. Итак, у нас матрица $A$ с действительными собственными значениями. Из того, что количество золотого песка сохраняется, то есть $\left\|Ax \right\|_1=\left\|x \right\|_1$ , можно доказать, что спектр матрицы $A$ принадлежит отрезку $[-1,1]$ . Анализируя собственные значения, по модулю равные единице, можно конкретно для данного случая вычислить собственные вектора для этих значений. Тут будет разная ситуация для чётных и нечётных $n$ . Для нечётных $n$ будет единственный собственный вектор, который отвечает собственному значению $1$ . Для чётных $n$ будет один собственный вектор для $\lambda =1$ и один собственный вектор для $\lambda = -1$ . Пространство в обоих случаях разлагается в прямую сумму подпространств, среди которых будут и описанные собственные вектора. У всех остальных инвариантных подпространств собственные значения по модулю будут меньше единицы. Теперь разложим наш начальный вектор на сумму векторов, каждый из которых лежит в некотором инвариантном пространстве. В процессе итераций все слагаемые, где собственные значения по модулю меньше единицы, зануляются. Для нечётных $n$ в пределе получается вектор с равными координатами. Для чётных $n$ предел будет "пульсирующий". (Надеюсь топик-стартер правильно тут меня поймёт).

[khuglar]

Спасибо вам ребята за помощь. Не особо понял откуда косинус и экспонента только. С нечетным случаем я вроде справился. Буду пока додумывать дальше, чтобы получить полную картину.

[zykov]

мат-ламер в сообщении #1582930 писал(а):

А если решать вообще без матриц, то можно догадаться на счёт стабильного состояния

Можно и без матриц.
Для нечётных, сделать замену переменных сдвинув все значения на одну величину, чтобы сумма в новых переменных равнялась нулю. Тогда сам вектор сходится к нулю.
Потом рассмотреть, как ведёт себя величина "сумма квадратов". Легко показать, что она уменьшается, если не равна нулю. Нужно только поазать, что она уменьшается не менее чем на какой-то конечный процент.
Для чётных аналогично, но надо отдельно рассмотреть подпоследовательности с чётными номерами и с нечётными, а сам вектор разбить на два подвектора - с чётными и нечётными индексами. Для каждого из этих двух подвекторов сделать свою замену переменных, чтобы сумма элементов в нём стала равна нулю. Тогда он будет сходится к нулю в подпоследовательности.

-- 24.02.2023, 01:26 --

khuglar в сообщении #1582993 писал(а):

Не особо понял откуда косинус и экспонента только

Представьте, что у вас очень длинный вектор и значения на нём меняются медленно от индекса. Тогда можно рассмотреть этот вектор как дискретизацию непрерывной функции $y(x)$, где $x$ принимает целые значения $1, 2, 3, ..., n$.
Тогда $y(k+1) \approx y(k)+y'(k)+\frac{y''(k)}{2}$ и $y(k-1) \approx y(k)-y'(k)+\frac{y''(k)}{2}$.
Значит $\frac{y(k-1)+y(k+1)}{2} \approx y(k)+\frac{y''(k)}{2}$.
Получаем $\frac{\partial y}{\partial t} = \frac12 \frac{\partial^2 y}{\partial x^2}$ - уравнение диффузии.
Собственные значения для правой части - экспоненты. Экспоненты с мнимыми коэффициентами дают гармоники.

[svv]

Обозначим нашу матрицу $C$, тогда $C=\frac 1 2(A+A^T)$, где
$A=\begin{bmatrix}0&1&0&\cdots&0&0\\0&0&1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&0&\cdots&1&0\\0&0&0&\cdots&0&1\\1&0&0&\cdots&0&0\end{bmatrix}$
Эта матрица ортогональна $\Rightarrow A^{-1}=A^T$. Она циклически сдвигает элементы вектора, на который умножается, значит, $A^n=E$. Поэтому собственные значения $A$ (и $A^T$) имеют вид $\lambda_k=e^{\frac{2\pi k}{n}i}.$ (Я пока не утверждаю, что каждое $\lambda_k$ является с.з.)
Имеем (при $\lambda\neq 0$)
$\det(A-\lambda E)\det(A^T-\lambda E)=-2\lambda\det(C-\frac{\lambda+\lambda^{-1}}2E)$
Левая часть равна нулю, только если $\lambda$ равно какому-то из $\lambda_k$. Отсюда с.з. матрицы $C$ могут быть только
$\frac{\lambda_k+\lambda_k^{-1}}2=\cos\frac{2\pi k}{n}$.

[khuglar]

Спасибо всем!!!! Разобрался!