Zhestkov4 окт в 17:46

Линейная алгебра: четыре разных подхода к одной задаче

Средний

4 мин

25K

Математика * Учебный процесс в IT

+76

Комментарии 18

misha_erementchouk 4 окт в 19:51

Техническое. В третьей задаче финальную часть можно сократить, используя спектральное представление

$A = \lambda_1 P_1 + \lambda_2 P_2,$

где

$P_k = \frac{1}{2} h_k h_k^T$

проекторы на собственные подпространства и множитель 1/2 учитывает нормировку собственных векторов, определенных в тексте. Отсюда сразу получаем ответ

$A^{100} = \frac{3^{100}}{2} \left( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right) + \frac{(-1)^{100}}{2} \left( \begin{matrix} 1 & -1 \\ -1 & 1 \end{matrix} \right)$

который, разумеется, совпадает с тем, что в тексте.

Zhestkov 4 окт в 19:56

В самом деле, можно и так :) Здорово, спасибо!

rootdefault 4 окт в 23:12

В первой задаче точно нужно возведение в степень после закрывающей скобки матрицы? )) а то сейчас записанное условие немного отличается от того что мы потом решаем ;)

Zhestkov 5 окт в 04:29

Спасибо! Поправил :)

aamonster 5 окт в 08:09

Спасибо. Вроде всё несложное (кроме последней задачки, теорему Гамильтона-Кэли я не помнил, надо будет с листочком бумаги поискать другое решение), но вспомнить студенческие годы приятно :-)

Zhestkov 5 окт в 19:13

Спасибо за обратную связь!

tarlex2001 5 окт в 15:04

У вас опечатка в последней задаче : а = 4950 .

И зачем так сложно : записываем первых три члена ряда Тейлора функции x^100 в точке x = -1 и сразу получаем остаток :

1- 100 ( x + 1 ) + 4950 * ( x + 1 ) ^2

Zhestkov 5 окт в 17:07

Спасибо за обратную связь и замеченную опечатку, поправил! Конечно, можно так. Но и тем способом вышло очень быстро, а на ум пришло первым :)

bk_space 6 окт в 05:42

Коршуны налетели, коршуны

Zhestkov 8 окт в 21:26

Кто понял, тот понял :)

KvanTTT 6 окт в 11:28

Забавно, что все эти примеры скорей всего быстро решаются тупым перемножением матриц в системах компьютерной алгебры. 2000 умножений - это должно быть немного.

Timosha_Kulikov 6 окт в 11:52

Ну как бэ, если в лоб перемножать, то сложность О(n^3)

KvanTTT 6 окт в 14:06

Здесь сложность линейная N, т.к. матрицы фиксированного размера (считаем, что умножение одной матрицы на другую происходит за константу).

bk_space 6 окт в 12:06

Речь же не о решениях в лоб, а о подходах к таким расчётам. Если для человека 1000 - запредельное значение, то для систем компьютерной алгебры это число просто станет другим, скажем, 10^12. Однако сам подход к решению таких задач не поменяется, лишь константы будут другие.

Калькулятор позволит легко сложить 20 чисел, сформированных по некоторому правилу, в лоб, но это не делает формулу суммы арифметической прогрессии бесполезной)

KvanTTT 6 окт в 14:07

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

fshp 6 окт в 16:00

Для возведения в степень 2000 потребуется 15 умножений.

lea 6 окт в 20:54

потребуется 15 умножений

13 используя addition chain exponentiation (1,2,4,5,10,20,40,50,100,200,400,500,1000,2000)

Soukhinov 23 дек в 22:25

А ещё можно выключить мозг и сделать так:

$\renewcommand{\arraystretch}{1.15} \begin{gathered} \begin{aligned} A&=\begin{pmatrix} 1&2&0\\ -3&-3&1\\ 2&2&-1 \end{pmatrix} &\qquad A^{2}&=\begin{pmatrix} -5&-4&2\\ 8&5&-4\\ -6&-4&3 \end{pmatrix}\\[10pt] A^{4}&=\begin{pmatrix} -19&-8&12\\ 24&9&-16\\ -20&-8&13 \end{pmatrix} &\qquad A^{8}&=\begin{pmatrix} -71&-16&56\\ 80&17&-64\\ -72&-16&57 \end{pmatrix}\\[10pt] A^{16}&=\begin{pmatrix} -271&-32&240\\ 288&33&-256\\ -272&-32&241 \end{pmatrix} &\qquad A^{32}&=\begin{pmatrix} -1055&-64&992\\ 1088&65&-1024\\ -1056&-64&993 \end{pmatrix} \end{aligned}\\[10pt] A^{64}=\begin{pmatrix} -4159&-128&4032\\ 4224&129&-4096\\ -4160&-128&4033 \end{pmatrix} \end{gathered}$

Тогда:

$A^{100}=A^{64}A^{32}A^{4}= \begin{pmatrix} -10099 & -200 & 9900\\ 10200 & 201 & -10000\\ -10100 & -200 & 9901 \end{pmatrix}.$

На олимпиадах ведь можно калькуляторами пользоваться? А калькуляторы поддерживают матричные вычисления.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий