Возведение матрицы в степень. Вычисление результатов выражений с матрицами.
Здесь мы продолжим начатую в первой части тему операций над матрицами и разберём пару примеров, в которых потребуется применять несколько операций сразу.
Возведение матрицы в степень.
Пусть k – целое неотрицательное число. Для любой квадратной матрицы $A_{n\times n}$ имеем: $$ A^k=\underbrace{A\cdot A\cdot \ldots \cdot A}_{k \; раз} $$
При этом полагаем, что $A^0=E$, где $E$ – единичная матрица соответствующего порядка.
Пример №4
Задана матрица $ A=\left(\begin{array} {cc} 1 & 2 \\ -1 & -3 \end{array} \right)$. Найти матрицы $A^2$ и $A^6$.
Решение
Согласно определению $A^2=A\cdot A$, т.е. для нахождения $A^2$ нам просто нужно умножить матрицу $A$ саму на себя. Операция умножения матриц рассматривалась в первой части темы, поэтому тут просто запишем процесс решения без подробных пояснений:
$$ A^2=A\cdot A=\left(\begin{array} {cc} 1 & 2 \\ -1 & -3 \end{array} \right)\cdot \left(\begin{array} {cc} 1 & 2 \\ -1 & -3 \end{array} \right)= \left(\begin{array} {cc} 1\cdot 1+2\cdot (-1) & 1\cdot 2+2\cdot (-3) \\ -1\cdot 1+(-3)\cdot (-1) & -1\cdot 2+(-3)\cdot (-3) \end{array} \right)= \left(\begin{array} {cc} -1 & -4 \\ 2 & 7 \end{array} \right). $$Чтобы найти матрицу $A^6$ у нас есть два варианта. Вариант первый: банально продолжить домножать $A^2$ на матрицу $A$:
$$ A^6=A^2\cdot A\cdot A\cdot A\cdot A. $$Однако можно пойти несколько более простым путём, используя свойство ассоциативности умножения матриц. Расставим скобки в выражении для $A^6$:
$$ A^6=A^2\cdot A\cdot A\cdot A\cdot A=A^2\cdot (A\cdot A)\cdot (A\cdot A)=A^2\cdot A^2\cdot A^2. $$Если при решении первым способом потребовалось бы четыре операции умножения, то для второго способа – лишь две. Поэтому пойдём вторым путём:
$$ A^6=A^2\cdot A^2\cdot A^2=\left(\begin{array} {cc} -1 & -4 \\ 2 & 7 \end{array} \right)\cdot \left(\begin{array} {cc} -1 & -4 \\ 2 & 7 \end{array} \right)\cdot \left(\begin{array} {cc} -1 & -4 \\ 2 & 7 \end{array} \right)=\\= \left(\begin{array} {cc} -1\cdot (-1)+(-4)\cdot 2 & -1\cdot (-4)+(-4)\cdot 7 \\ 2\cdot (-1)+7\cdot 2 & 2\cdot (-4)+7\cdot 7 \end{array} \right)\cdot \left(\begin{array} {cc} -1 & -4 \\ 2 & 7 \end{array} \right)= \left(\begin{array} {cc} -7 & -24 \\ 12 & 41 \end{array} \right)\cdot \left(\begin{array} {cc} -1 & -4 \\ 2 & 7 \end{array} \right)=\\= \left(\begin{array} {cc} -7\cdot(-1)+(-24)\cdot 2 & -7\cdot (-4)+(-24)\cdot 7 \\ 12\cdot (-1)+41\cdot 2 & 12\cdot (-4)+41\cdot 7 \end{array} \right)= \left(\begin{array} {cc} -41 & -140 \\ 70 & 239 \end{array} \right). $$Ответ: $A^2=\left(\begin{array} {cc} -1 & -4 \\ 2 & 7 \end{array} \right)$, $A^6=\left(\begin{array} {cc} -41 & -140 \\ 70 & 239 \end{array} \right)$.
Пример №5
Заданы матрицы $ A=\left(\begin{array} {cccc} 1 & 0 & -1 & 2 \\ 3 & -2 & 5 & 0 \\ -1 & 4 & -3 & 6 \end{array} \right)$, $ B=\left(\begin{array} {ccc} -9 & 1 & 0 \\ 2 & -1 & 4 \\ 0 & -2 & 3 \\ 1 & 5 & 0 \end{array} \right)$, $ C=\left(\begin{array} {ccc} -5 & -20 & 13 \\ 10 & 12 & 9 \\ 3 & -15 & 8 \end{array} \right)$. Найти матрицу $D=2AB-3C^T+7E$.
Решение
Вычисление матрицы $D$ начнем с нахождения результата произведения $AB$. Матрицы $A$ и $B$ можно перемножать, так как количество столбцов матрицы $A$ равно количеству строк матрицы $B$. Обозначим $F=AB$. При этом матрица $F$ будет иметь три столбца и три строки, т.е. будет квадратной (если этот вывод кажется неочевидным, посмотрите описание умножения матриц в первой части этой темы). Найдем матрицу $F$, вычислив все её элементы:
$$ F=A\cdot B=\left(\begin{array} {cccc} 1 & 0 & -1 & 2 \\ 3 & -2 & 5 & 0 \\ -1 & 4 & -3 & 6 \end{array} \right)\cdot \left(\begin{array} {ccc} -9 & 1 & 0 \\ 2 & -1 & 4 \\ 0 & -2 & 3 \\ 1 & 5 & 0 \end{array} \right)\\ \begin{aligned} & f_{11}=1\cdot (-9)+0\cdot 2+(-1)\cdot 0+2\cdot 1=-7; \\ & f_{12}=1\cdot 1+0\cdot (-1)+(-1)\cdot (-2)+2\cdot 5=13; \\ & f_{13}=1\cdot 0+0\cdot 4+(-1)\cdot 3+2\cdot 0=-3;\\ \\ & f_{21}=3\cdot (-9)+(-2)\cdot 2+5\cdot 0+0\cdot 1=-31;\\ & f_{22}=3\cdot 1+(-2)\cdot (-1)+5\cdot (-2)+0\cdot 5=-5;\\ & f_{23}=3\cdot 0+(-2)\cdot 4+5\cdot 3+0\cdot 0=7;\\ \\ & f_{31}=-1\cdot (-9)+4\cdot 2+(-3)\cdot 0+6\cdot 1=23; \\ & f_{32}=-1\cdot 1+4\cdot (-1)+(-3)\cdot (-2)+6\cdot 5=31;\\ & f_{33}=-1\cdot 0+4\cdot 4+(-3)\cdot 3+6\cdot 0=7. \end{aligned} $$В принципе, мы и дальше можем идти пошагово, но оставшееся выражение лучше рассматривать целиком, не отвлекаясь на вспомогательные действия. По сути, нам остались лишь операции умножения матриц на число, а также операции сложения и вычитания.
$$ D=2AB-3C^T+7E=2\cdot \left(\begin{array} {ccc} -7 & 13 & -3 \\ -31 & -5 & 7 \\ 23 & 31 & 7 \end{array} \right)-3\cdot \left(\begin{array} {ccc} -5 & 10 & 3 \\ -20 & 12 & -15 \\ 13 & 9 & 8 \end{array} \right)+7\cdot \left(\begin{array} {ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) $$Умножим матрицы в правой части равенства на соответствующие числа (т.е. на 2, 3 и 7):
$$ 2\cdot \left(\begin{array} {ccc} -7 & 13 & -3 \\ -31 & -5 & 7 \\ 23 & 31 & 7 \end{array} \right)-3\cdot \left(\begin{array} {ccc} -5 & 10 & 3 \\ -20 & 12 & -15 \\ 13 & 9 & 8 \end{array} \right)+7\cdot \left(\begin{array} {ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right)=\\= \left(\begin{array} {ccc} -14 & 26 & -6 \\ -62 & -10 & 14 \\ 46 & 62 & 14 \end{array} \right)-\left(\begin{array} {ccc} -15 & 13 & 9 \\ -60 & 36 & -45 \\ 39 & 27 & 24 \end{array} \right)+\left(\begin{array} {ccc} 7 & 0 & 0 \\ 0 & 7 & 0 \\ 0 & 0 & 7 \end{array} \right) $$Выполним последние действия: вычитание и сложение:
$$ \left(\begin{array} {ccc} -14 & 26 & -6 \\ -62 & -10 & 14 \\ 46 & 62 & 14 \end{array} \right)-\left(\begin{array} {ccc} -15 & 30 & 9 \\ -60 & 36 & -45 \\ 39 & 27 & 24 \end{array} \right)+\left(\begin{array} {ccc} 7 & 0 & 0 \\ 0 & 7 & 0 \\ 0 & 0 & 7 \end{array} \right)=\\ =\left(\begin{array} {ccc} -14-(-15)+7 & 26-30+0 & -6-9+0 \\ -62-(-60)+0 & -10-36+7 & 14-(-45)+0 \\ 46-39+0 & 62-27+0 & 14-24+7 \end{array} \right)= \left(\begin{array} {ccc} 8 & -4 & -15 \\ -2 & -39 & 59 \\ 7 & 35 & -3 \end{array} \right). $$ Задача решена, $D=\left(\begin{array} {ccc} 8 & -4 & -15 \\ -2 & -39 & 59 \\ 7 & 35 & -3 \end{array} \right)$.Ответ: $D=\left(\begin{array} {ccc} 8 & -4 & -15 \\ -2 & -39 & 59 \\ 7 & 35 & -3 \end{array} \right)$.
Пример №6
Пусть $f(x)=2x^2+3x-9$ и матрица $ A=\left(\begin{array} {cc} -3 & 1 \\ 5 & 0 \end{array} \right) $. Найти значение $f(A)$.
Решение
Если $f(x)=2x^2+3x-9$, то под $f(A)$ понимают матрицу:
$$ f(A)=2A^2+3A-9E. $$Именно так определяется многочлен от матрицы. Итак, нам нужно подставить матрицу $A$ в выражение для $f(A)$ и получить результат. Так как все действия были подробно разобраны ранее, то тут я просто приведу решение. Если процесс выполнения операции $A^2=A\cdot A$ для вас неясен, то советую глянуть описание умножения матриц в первой части этой темы.
$$ f(A)=2A^2+3A-9E=2A\cdot A+3A-9E=2 \left(\begin{array} {cc} -3 & 1 \\ 5 & 0 \end{array} \right)\cdot \left(\begin{array} {cc} -3 & 1 \\ 5 & 0 \end{array} \right)+3 \left(\begin{array} {cc} -3 & 1 \\ 5 & 0 \end{array} \right)-9\left(\begin{array} {cc} 1 & 0 \\ 0 & 1 \end{array} \right)=\\ =2 \left(\begin{array} {cc} (-3)\cdot(-3)+1\cdot 5 & (-3)\cdot 1+1\cdot 0 \\ 5\cdot(-3)+0\cdot 5 & 5\cdot 1+0\cdot 0 \end{array} \right)+3 \left(\begin{array} {cc} -3 & 1 \\ 5 & 0 \end{array} \right)-9\left(\begin{array} {cc} 1 & 0 \\ 0 & 1 \end{array} \right)=\\ =2 \left(\begin{array} {cc} 14 & -3 \\ -15 & 5 \end{array} \right)+3 \left(\begin{array} {cc} -3 & 1 \\ 5 & 0 \end{array} \right)-9\left(\begin{array} {cc} 1 & 0 \\ 0 & 1 \end{array} \right) =\left(\begin{array} {cc} 28 & -6 \\ -30 & 10 \end{array} \right)+\left(\begin{array} {cc} -9 & 3 \\ 15 & 0 \end{array} \right)-\left(\begin{array} {cc} 9 & 0 \\ 0 & 9 \end{array} \right)=\left(\begin{array} {cc} 10 & -3 \\ -15 & 1 \end{array} \right). $$Ответ: $f(A)=\left(\begin{array} {cc} 10 & -3 \\ -15 & 1 \end{array} \right)$.
math1.ru
возведение матрицы в степень — ПриМат
1. Выполнить сложение матриц:
.
Для сложения матриц нам необходимо каждый элемент первой матрицы сложить с соответствующим элементом из второй:
.
Следует также отметить, что операция сложения матриц коммутативна и ассоциативна. Например, пусть даны матрицы , и . Тогда:
.
Покажем выполнение ассоциативности сложения матриц:
;
.
;
.
Как видим, .
2. Выполнить умножение матрицы на число:
.
Для умножения матрицы на число мы умножаем каждый элемент матрицы на данное число:
.
Операция умножения матрицы на число ассоциативна, то есть , . Покажем это на конкретном примере:
Пусть дана матрица и .
Тогда ;
.
;
.
Как видим, .
3. Вычислить произведение матриц:
.
Для удобства будем называть первую матрицу а вторую матрицу . Для начала убедимся, что произведение данных матриц возможно. Даны матрицы размерностей и , следовательно умножение возможно, так как количество столбцов первой матрицы равно количеству строк второй. Для вычисления первого элемента результирующей матрицы умножим каждый элемент первой строки матрицы на соответствующие элементы первого столбца матрицы . Полученные значения сложим. Данную последовательность действий можно проиллюстрировать следующим образом:
Получим следующее:
.
Далее вычисляем первый элемент второго столбца результирующей матрицы. Умножаем все элементы первой строки матрицы на соответствующие им элементы из второго столбца матрицы и складываем полученные значения:
Для вычисления первого элемента второй строки результирующей матрицы мы будем аналогично умножать элементы второй строки матрицы на элементы первого столбца матрицы , складывая результаты:
.
Оставшиеся элементы вычисляются аналогично:
.
Отметим, что произведение матриц в общем случае некоммутативно и покажем это на примере.
Пусть даны матрицы .
Тогда .
.
Как видим, .
4. Возвести матрицу в степень:
.
Для возведения в степень необходимо данную матрицу умножить саму на себя. Заметим, что возводить в степень можно только квадратные матрицы.
.
5. Транспонировать матрицу:
.
Для транспонирования матрицы достаточно записать строки столбцами, а столбцы строками:
.
Таблица лучших: Действия над матрицами. Групповые свойства некоторых матриц
| Место | Имя | Записано | Баллы | Результат |
|---|---|---|---|---|
| Таблица загружается | ||||
| Нет данных | ||||
Действия над матрицами. Групповые свойства некоторых матриц
Лимит времени: 0
Информация
Тест на тему «Действия над матрицами. Групповые свойства некоторых матриц».
Вы уже проходили тест ранее. Вы не можете запустить его снова.
Тест загружается…
Вы должны войти или зарегистрироваться для того, чтобы начать тест.
Вы должны закончить следующие тесты, чтобы начать этот:
Правильных ответов: 0 из 4
Ваше время:
Время вышло
| Средний результат |
|
| Ваш результат |
|
- С ответом
- С отметкой о просмотре
Источники:
- Г. С. Белозеров. Конспект лекций.
- В. В. Воеводин «Линейная алгебра» (Издание второе, переработанное и дополненное, 1980г.), стр. 194-197.
- А. Г. Курош «Курс высшей алгебры» (Издание девятое, 1968 г.), стр. 99-102.
- И. В. Проскуряков. «Сборник задач по линейной алгебре» (1984 г.), стр. 112-115.
Поделиться ссылкой:
ib.mazurok.com
Возведение матрицы в степень, онлайн калькулятор
Наш онлайн калькулятор помогаем возводить квадратные матрицы в степень всего за несколько минут. Для возведения матрицы в натуральную степень выберите ее размер, заполните все элементы матрицы и степень, в которую ходите возвести (2, 3, 4 и т.д.) и нажмите кнопку «Вычислить» — калькулятор выдаст решение и ответ! Калькулятор автоматически перемножит матрицу саму на себя нужное количество раз и выдаст точный ответ.
Заполните элементы матрицы и степень Решили сегодня: раз, всего раз| Понравился сайт? Расскажи друзьям! | |||
Как возвести матрицу в степень онлайн
Следует заметить, что данной операции поддаются только квадратные матрицы. Равное число строк и столбцов – обязательное условие для возведения матрицы в степень. В ходе вычисления матрица будет помножена сама на себя требуемое количество раз.
Данный онлайн калькулятор предназначен для выполнения операции возведения матрицы в степень. Благодаря его использованию вы не только быстро справитесь с данной задачей, но и получите наглядное и развёрнутое представление о самом ходе вычисления. Это поможет лучше закрепить материал, полученный в теории. Увидев перед собой детальный алгоритм расчётов, вы лучше поймёте все его тонкости и впоследствии сможете не допускать ошибок в ручном вычислении. Кроме того, никогда не будет лишним перепроверить свои расчёты, и это тоже лучше всего осуществлять здесь.
Для того, чтобы возвести матрицу в степень онлайн, понадобится ряд простых действий. Первым делом укажите размер матрицы, нажав на иконки «+» или «-» слева от неё. Затем в поле матрицы введите числа. Также нужно указать степень, в которую возводится матрица. А далее вам остаётся лишь кликнуть на кнопку: «Вычислить» в нижней части поля. Полученный результат будет достоверным и точным, если вы внимательно и правильно ввели все значения. Вместе с ним вам будет предоставлена детальная расшифровка решения.
ru.solverbook.com
Возведение матрицы в степень
| Вы ввели следующие элементы массива |
| Матрица в заданной степени |
квадратная матрица в целочисленной степени
Квадратную матрицу можно возводить в целочисленную степень
Например матрица следующего вида
умножив матрицу саму на себя четыре раза, получим результат
Значение степени может быть от 2-х и выше.
У степенных матриц есть интересные свойства которые рассмотрим
Единичная матрица, то есть матрица у которой все значения равны нулю, кроме тех что стоят на главной диагонали(=1).
в любой степени будет тоже являтся единичной матрицой.
матрица вида
в кубической степени будет равна
а в 7 степени
Интересное свойство проявляется в матрице
Взяв в степень 4, 8, 12 и так далее — мы получаем единичную матрицу
А если же исходную матрицу брать в степени 2,6,10 и так далее то получаем «зеркальную» единичную матрицу
Нечетные степени тоже интересно преобразовывают матрицу. Но это мы рекомендуем самим увидеть и проанализировать.
Еще одна удивительная матрица это
Возводя её в любую степень получаем исходную матрицу. Много ли таких уникальных матриц, и насколько много было бы любопытно узнать.
Синтаксис
Jabber: step_m матрица; степень матрицы
где,
Матрица — строка, содержащая элементы матрицы ( в том числе и комплексные) разделенная пробелами
элементом матрицы может быть произвоольное корректное математическое выражение, содержащее как вещественые так и мнимые числа.
Степень матрицы- целочисленное, положительное значение
Убедительная просьба: Если уж пишете мнимые единицы то обозначайте их знаком i (ай) а не j(джи). Будьте внимательнее в написании исходных данных!!.
Примеры
Исходная матрица
Взяв эту матрицу в седьмой степени мы получим
Обратная матрица исходной, равна
Удачных расчетов!!
- Возведение полинома (многочлена) в степень >>
www.abakbot.ru
Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования
Недавно на хабре появилась неплохая статья про вычисление N-ного числа фибоначи за O(log N) арифметических операций. Разумный вопрос, всплывший в комментариях, был: «зачем это может пригодиться на практике». Само по себе вычисление N-ого числа фибоначи может и не очень интересно, однако подход с матрицами, использованный в статье, на практике может применяться для гораздо более широкого круга задач.В ходе этой статьи мы разберем как написать интерпретатор, который может выполнять простые операции (присвоение, сложение, вычитание и урезанное умножение) над ограниченным количеством переменных с вложенными циклами с произвольным количеством итераций за доли секунды (конечно, если промежуточные значения при вычислениях будут оставаться в разумных пределах). Например, вот такой код, поданный на вход интерпретатору:
loop 1000000000
loop 1000000000
loop 1000000000
a += 1
b += a
end
end
end
end
Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.
Я полагаю, что у читателя есть представление о том, что такое матрица, и что такое произведение матриц. В рамках этой статьи мы будем использовать исключетельно квадратные матрицы и полагаться на очень важное свойство умножения квадратных матриц — ассоциативность.
Для простоты ограничим наш интерпретатор четырьмя переменными — A, B, C и D. Для представления состояния интерпретатора в заданный момент будем использовать вектор размера пять, первые четыре элемента которого будут содержать значения четырех переменных соответственно, а последний будет на протяжении всей работы интерпретатора равен единице.
(A, B, C, D, 1)В начале работы интерпретатора будем полагать значения всех переменных равными нулю.
(0, 0, 0, 0, 1)Допустим, что первая операция в коде программы содержит строку
A += 5Эффект этой команды заключается в том, что значение переменной A увеличится на пять, в то время как значения остальных трех переменных не изменятся. Это можно претставить в виде следующей матрицы:
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
5 0 0 0 1Если посмотреть на нее, можно заметить, что она почти идентична единичной матрице (которая, как известно, при умножении любого вектора на нее не меняет его значения), за исключением последнего элемента в первом столбце, который равен пяти. Если вспомнить, как происходит умножение вектора на матрицу, можно понять, что значения всех элементов, кроме первого, не изменятся, в то время как значение первого элемента станет равно
v[0] * 1 + v[4] * 5Так как v[0] содержит текущее значение в переменной A, а v[4] всегда равен единице, то
v[0] * 1 + v[4] * 5 = A + 5Если вектор текущего состояния умножить на эту матрицу, полученный вектор будет соответствовать состоянию, в котором A на пять больше, что и требовалось.
Если матрицу поменять немного, убрав единицу в первом элементе первой строки:
0 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
5 0 0 0 1Как и прежде, значения всех элементов кроме первого не изменятся, в то время как первый элемент станет равным v[4] * 5, или просто пяти. Умножение вектора текущего состояния на такую матрицу эквивалентно выполнению команды
A = 5Посмотрим на такую матрицу:
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 1 0 1 0
0 0 0 0 1Единственное отличие ее от единичной матрицы — это второй элемент в четвертой строке, который равен единице. Очевидно, что умножение вектора текущего состояния на эту матрицу не изменит значения в первом и последних трех элементах, в то время как значение второго элемента изменится на
v[1] * 1 + v[3] * 1Так как v[1] содержит текущее значение переменной B, а v[3] содержит текущее значение переменной D, то умножение вектора состояния на такую матрицу эквивалентно выполнению команды B += D
Аналогично рассуждая можно понять, что умножение вектора состояния на следующую матрицу эквивалентно выполнению команды C *= 7
1 0 0 0 0
0 1 0 0 0
0 0 7 0 0
0 0 0 1 0
0 0 0 0 1Перейдем к комбинированию команд. Пусть вектор v задает текущее состояние, матрица Ma соответствует команде A += 5, а матрица Mm соответствует команде A *= 7. Тогда, чтобы получить вектор r для состояния после выполнения этих двух команд, надо сначала умножить v на Ma, а затем на Mm:
r = v * Ma * MmКак и ожидается, умножение вектора начального состояния на эти две матрицы приводит в состояние, в котором a=35:
1 0 0 0 0 7 0 0 0 0
0 1 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 1 0
5 0 0 0 1 0 0 0 0 1
0 0 0 0 1 5 0 0 0 1 35 0 0 0 1Рассмотрим другой пример — пусть вместо умножения на семь, мы просто хотим прибавить пять к A семь раз.
r = v * Ma * Ma * Ma * Ma * Ma * Ma * MaТут на помощь приходит ассоциативное свойство умножения матриц:
r = v * Ma * Ma * Ma * Ma * Ma * Ma * Ma =
v * (Ma * Ma * Ma * Ma * Ma * Ma * Ma) =
v * Ma ^ 7Это пример простого цикла — вместо того, чтобы умножать v на Ma семь раз, достаточно возвести матрицу Ma в седьмую степень, после чего выполнить только одно умножение. Если бы мы хотели выполнить следующие две операции в цикле три раза:
A += 5
B -= C(Пусть операция B -= C представляется матрицей Mbc), это бы выглядело следующим образом:
r = v * Ma * Mbc * Ma * Mbc * Ma * Mbc =
v * ((Ma * Mbc) * (Ma * Mbc) * (Ma * Mbc)) =
v * (Ma * Mbc) ^ 3Мы вычисляем матрицу, соответствующую телу цикла, только один раз, после чего возводим ее в степень.
Рассмотренных примеров достаточно, чтобы начать работать над интерпретатором простого языка, поддерживающего присваивание, сложение, вычитание, умножение (только на константу) и циклы. Для этого мы научимся представлять любую такую программу в виде матрицы размера N+1 на N+1, где N — это количество переменных, которыми программа оперирует, после чего будем просто умножать вектор с начальным состоянием на эту матрицу.
Правила представления программы в виде матрицы очень просты:
1. Каждая отдельная команда представляется в виде матрицы, отличающейся от единичной одним элементом (или двумя для операции присваивания). Примеры таких матриц рассмотрены выше в этой статье.
2. Несколько подряд идущих команд представляются в виде матрицы, равной произведению матричного представления каждой отдельной команды.
3. Цикл представляется в виде матрицы, представляющей тело цикла, возведенной в степень количества итераций цикла.
Если у нас есть функция identity, возвращающая единичную матрицу:
def identity():
return [[1 if i == j else 0 for j in range(REGS + 1)] for i in range(REGS + 1)]То фукнция, строящая матрицу для команды r1 += r2 (где r1 и r2 — переменные) может выглядеть так:
def addreg(r1, r2):
ret = identity()
ret[r2][r1] = 1
return retА для команды r += val (r — переменная, val — константа) вот так:
def addval(r, val):
ret = identity()
ret[REGS][r] = val
return retФункции для построения матриц других команд выглядят похоже — получается единичная матрица, в которой заменяется один элемент.
Интерпретатор без циклов теперь пишется очень просто — пусть матрица mat соответствует уже прочитанному коду. В начале она равна единичной матрице, потому что пустая программа не меняет состояния. Затем мы считываем команды по одной, разбиваем их на три элемента (левый операнд, оператор, правый операнд), и в зависимости от оператора домножаем матрицу, соответствующую всей программе, на матрицу, соответствующую текущей команде:
def doit():
mat = identity()
while True:
line = sys.stdin.readline().lower()
tokens = line.split()
if tokens[0] == 'loop':
# тут будет код для циклов
elif tokens[0] == 'end':
return mat
else:
r1 = reg_names.index(tokens[0])
try:
r2 = reg_names.index(tokens[2])
except:
r2 = -1
if tokens[1] == '+=':
if r2 == -1: cur = addval(r1, long(tokens[2]))
else: cur = addreg(r1, r2)
elif tokens[1] == '-=':
....
mat = matmul(mat, cur)Осталось дело за малым — добавить поддержку циклов. Цикл возводит матрицу тела цикла в степень количества итераций цикла. Возведение в степень, как известно, требует только O(log N) операций, где N — это степень, в которую матрица возводится. Алгоритм возведения в степень очень прост:
1. Если степень равна нулю, вернуть единичную матрицу.
2. Если степень четная, пусть 2N, то можно рекурсивно вычислить M^N, а затем вернуть квадрат получившейся матрицы.
3. Если степень нечетная, пусть 2N+1, то достаточно рекурсивно посчитать значение M^2N, и вернуть полученную матрицу, умноженную на M.
Так как каждые две итерации степень сокращается в двое, сложность такого алгоритма логарифмическая.
def matpow(m, p):
if p == 0: return identity()
elif p % 2 == 0:
tmp = matpow(m, p / 2)
return matmul(tmp, tmp)
else: return matmul(m, matpow(m, p - 1))В интерпретаторе теперь осталось добавить одну строку:
...
if tokens[0] == 'loop':
cur = matpow(doit(), long(tokens[1]))
...И интерпретатор готов.
Пример интерпретатора доступен на гитхабе. Весь код занимает меньше 100 строк.
Для теста скорости можно вернуться к уже упомянутым числам фибоначи. Например, такой код:
A = 1
B = 1
loop 100
C = A
C += B
A = B
B = C
end
endВычислит 101-ое и 102-ое числа фибоначи:
A = 573147844013817084101, B = 927372692193078999176
Замена 100 на 1000000 вычислит миллион первое и миллион второе числа за четыре секунды. Выполнение такой программы в лоб заняло бы гораздо больше, потому что программе приходится оперировать многотысячезначными числами. Если написать код, которому не приходится оперировать большими числами, например код для вычисления суммы арифметической прогрессии, приведенный в начале статьи, то количество итераций может уходить за рамки разумного, но код будет выполняться за доли секунды
loop 1000000000000000000000000000000000000000000000
loop 1000000000000000000000000000000000000000000000
loop 1000000000000000000000000000000000000000000000
a += 1
b += a
end
end
end
endНа практике этот подход может применяться, например, в оптимизирующих компиляторах, которые могут таким образом сворачивать циклы с большим количеством итераций, оперирующие на небольшом количестве переменных.
habr.com
Возведение матрицы в степень | C++ для приматов
#include <iostream>
#include <string>
#include <vector>
#include <deque>
using namespace std;
class matrix{ //создаем класс матрицы, в основном для красивого перемножения
private:
int n,m;
int long long **arr;
public:
matrix(){
n = 1; m = 1;
}
matrix(int x){
n = x; m = x;
arr = new int long long *[n];
for(int i = 0; i < n; i++){
arr[i] = new int long long [m];
}
for(int j = 0; j < this->n; j++){
for(int k = 0; k < this->m; k++){
arr[j][k] = 0;
}
}
}
matrix(int x, int y){
n = x; m = y;
arr = new int long long *[n];
for(int i = 0; i < n; i++){
arr[i] = new int long long [m];
}
for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор
for(int k = 0; k < this->m; k++){
arr[j][k] = 0;
}
}
} // выше были описанны конструкторы
~matrix(){
for(int i = 0; i < n; i++){
delete arr[i];
}
delete arr;
}// деструктор
void read(){
for(int j = 0; j < this->n; j++){
for(int k = 0; k < this->m; k++){
cin >> arr[j][k];
}
}
}//функция ввода
void write(){
for(int j = 0; j < this->n; j++){
for(int k = 0; k < this->m; k++){
cout << arr[j][k] << » «;
}
cout << endl;
}
}// функция вывода
void create(int x, int y){
n = x; m = y;
arr = new int long long *[n];
for(int i = 0; i < n; i++){
arr[i] = new int long long [m];
}
}//функция измененияколичества выделяемой под нас памяти
matrix& operator=(const matrix& x){
for(int j = 0; j < this->n; j++){
for(int k = 0; k < this->m; k++){
arr[j][k] = x.arr[j][k];
}
}
return *this;
}// переопределение оператора присваивания для матриц
const matrix operator*(const matrix& x){
matrix ans(this->n, this->m);
for(int i = 0; i < this->n; i++){
for(int j = 0; j < this->m; j++){
for(int k = 0; k < this->m; k++){
ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
}
}
}
return ans;
}//переопределение умножения для матриц
matrix& operator*=(const matrix& x){
matrix ans(this->n, this->m);
for(int i = 0; i < this->n; i++){
for(int j = 0; j < this->m; j++){
for(int k = 0; k < this->m; k++){
ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
}
}
}
*this=ans;
return *this;
}//переопределение присвоить равно
matrix& pow(int n){
string s;
for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0
s+= to_string((n >> i)&1);;
}
int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки
for(; s[i]!= ‘1’; i—){} //находим этот разряд,двигаясь с конца в поисках первой
matrix ans(this->n,this->m
cpp.mazurok.com
Как возвести матрицу в степень
Операции с матрицами требуют от человека в первую очередь усидчивости и внимательности. Необходимо тщательно проверять каждый свой шаг, чтобы получить точный результат. Алгоритм возведения матрицы в степень не отличается сложностью, однако может показаться довольно монотонным.Инструкция
- Освойте правила перемножения матриц для того, чтобы научиться возводить матрицу в степень. Обратите особенное внимание на ограничения: вы можете осуществлять операцию умножения только с матрицами, у которых число столбцов первого множителя совпадает с числом строк второго. В противном случае умножение не может быть произведено. Так, если вы хотите возвести в степень матрицу размером 3*2, то это действие является математически неверным и невозможным.
- Запомните, что результатом перемножения двух матриц является третья, размерность которой определяется количеством столбцов первой матрицы и строк во второй. В i-том столбце и j-той строчке результирующей матрицы стоит сумма произведений элементов множителей из i-того столбца первой матрицы и j-того столбца второй. При этом первый элемент i-того столбца умножается на первый элемент j-той строчки, второй – на второй и т.д.
- Возведение матрицы в степень представляет собой простое перемножение матриц, в котором первый и второй множители равны между собой. Проводите последовательные вычисления. Вне зависимости от того, в какую степень требуется возвести матрицу, начинайте с возведения в квадрат. Затем полученный результат умножьте на исходную матрицу, чтобы получить кубическую степень. Продолжайте, пока не достигнете требуемого результата. Не забывайте, что в случае умножения матриц итог меняется от перестановки множителей.
- Воспользуйтесь интернетом и услугами он-лайн калькуляторов, позволяющих перемножать матрицы без усилий. Вам потребуется только ввести данные: размер матрицы (не забывайте, что в степень можно возвести только квадратные матрицы), а также ее значения. Это потребует некоторого времени и внимания, чтобы не ошибиться при вводе элементов. Однако это значительно увеличит вероятность получения точного и достоверного результата.
completerepair.ru