Разное

Как возвести в n степень матрицу: Как возвести матрицу в степень? OTUS

Решение модуля 4.7 Поколение Python: для продвинутых

Главная » Ответы на Stepik » Поколение Python: курс для продвинутых

Опубликовано: Рубрика: Поколение Python: курс для продвинутыхАвтор: admin

Представляю вам ответы и решения урока 4.7(Операции над матрицами в математике) на курс «Поколение Python: курс для продвинутых»

Модуль 4.6

Все модули

Модуль 6.1

Найти сумму матриц

2  3  4
6  7  8
10 11 12

Найти произведение матрицы

3  6  9
12 15 18
21 24 27

Одну матрицу можно умножать на другую только тогда, когда

количество столбцов в первой матрице совпадает с количеством строк во второй матрице

Результат умножения матрицы размера Am×n​ на матрицу размером Bn×k​ – матрица C с размером

Cm×k

Найти произведение матриц

Примечание.  Мы умножаем строку первой матрицы на столбец второй матрицы. Чтобы найти элемент c_{ij}cij​ результирующей матрицы C = A \times BC=A×B мы умножаем каждый элемент ii-ой строки матрицы AA на соответствующий ему элемент jj-ого столбца матрицы BB и суммируем произведения.
12 15 18
24 30 36
36 45 54

Найти произведение матриц

Примечание. Мы умножаем строку первой матрицы на столбец второй матрицы. Чтобы найти элемент c_{ij}cij​ результирующей матрицы C = A \times BC=A×B мы умножаем каждый элемент ii-ой строки матрицы AA на соответствующий ему элемент jj-ого столбца матрицы BB и суммируем произведения.
-2 -2 1 2

Для матрицы

  1 0
100 1

Напишите программу для вычисления суммы двух матриц.

Формат входных данных
Напишите программу для вычисления суммы двух матриц.На вход программе подаются два натуральных числа nn и mm — количество строк и столбцов в матрицах, затем элементы первой матрицы, затем пустая строка, далее следуют элементы второй матрицы.

n, m = [int(i) for i in input().split()]
matrix1 = [[int(i) for i in input().split()] for _ in range(n)]
a = input()
matrix2 = [[int(i) for i in input().split()] for _ in range(n)]
matrix3 = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        matrix3[i][j] += matrix1[i][j] + matrix2[i][j]
for row in matrix3:
    print(*row)

Напишите программу, которая перемножает две матрицы.

Формат входных данных
На вход программе подаются два натуральных числа nn и mm — количество строк и столбцов в первой матрице, затем элементы первой матрицы, затем пустая строка. Далее следуют числа mm и kk — количество строк и столбцов второй матрицы затем элементы второй матрицы.

n, m = [int(i) for i in input().split()]
a = [[int(j) for j in input().split()] for _ in range(n)]
input()
m, k = [int(i) for i in input().split()]
b = [[int(j) for j in input().split()] for _ in range(m)]
c = [[0] * k for i in range(n)]
for i in range(n):
    for j in range(k):
        el = 0
        for r in range(m):
            el += a[i][r] * b[r][j]
        c[i][j] = el
for row in c:
    print(*row)

Напишите программу, которая возводит квадратную матрицу в m-ую степень.

Формат входных данных
На вход программе подаётся натуральное число n — количество строк и столбцов в матрице, затем элементы матрицы, затем натуральное число mm.

n = int(input())
a = [list(map(int, list(input().split()))) for _ in range(n)]
m = int(input())
def multi(a, b):
    n = len(a)
    b = list(zip(*b))
    return [[sum([a[i][r] * b[j][r] for r in range(n)]) for j in range(n)] for i in range(n)]
def expo(a, m):
    c = list(a)
    for _ in range(m-1):
        c = multi(c, a)
    return c
result = expo(a, m)
[print(*row) for row in result]

7 10 528 просмотров

Понравилась статья? Поделиться с друзьями:

Быстрое возведение в степень и подсчёт чисел Фибоначчи

Быстрое возведение в степень и подсчёт чисел Фибоначчи

☰ Оглавление

  • Первая страница
  • Онлайн инструменты ▽
    • Редактор иконок favicon. ico онлайн
    • Игра «Жизнь» онлайн
    • Онлайн навигатор по множеству (фракталу) Мандельброта
    • Онлайн конвертер PNG в favicon.ico
    • Интерактивная схема солнечной системы
    • Пересчёт дат в Юлианские дни
    • Объяснение и онлайн-демо, как работает HTML5 canvas transform
    • Онлайн генератор периодических фонов
    • Онлайн конвертер цветов из HSV в RGB
    • Онлайн URL-перекодировщик
    • Онлайн генератор QR-кодов
    • Покрутить 4D-гиперкуб
    • Получение географических координат точки на карте
    • «Сапёр» на бесконечном поле онлайн
    • Черепаший язык онлайн
    • Калькулятор индекса массы тела
    • Для самых маленьких ▽
      • Рисовалка для детей до трёх лет
      • «Робот» для детей с трёх-четырёх лет
      • «Морской бой» для самых маленьких
    • Простой чат
  • Инструменты ▽
    • Docker ▽
      • Docker устанавливаем и разбираемся
      • Пример использования Docker для изучения Ruby on Rails
      • Пример использования Docker для запуска MySQL
      • Почему docker требует root-прав
    • JavaScript ▽
      • Букмарклеты для JavaSctipt/HTML-разработчика
      • Использование «use strict» в JavaScript
      • Небольшая памятка по JavaScript
      • Простой минификатор/оптимизатор JavaScript
      • Мои плагины для хрома
    • Python ▽
      • Сводная таблица методов основных типов данных Python 2 и 3
      • Инструменты для Python-разработчика
      • Удобная командная строка Python
      • Утечки памяти в Python: метод __del__ и сборка мусора
      • Работа с нитями в Python
    • Файловая система ▽
      • FS: перемещение, переименование, архивирование
      • Монтирование sshfs с помощью systemd
    • Shell ▽
      • Работа с историей команд bash
      • Консоль/bash. настройка
      • Отправка e-mail с картинками чистым shell скриптом
      • Конвертирование аудио
      • Конвертирование видео
    • Управляем тактовой частотой процессора
    • Совместный доступ к mercurial по SSH
    • Передача файлов по сети
    • Безопасное хранение и передача данных
    • Нотификатор
    • Xorg. Настройка
    • Xorg. Настройка нестандартной клавиатуры
    • Synergy: Много мониторов с одной клавиатурой и мышкой
    • Ssh. Настройка
    • Ssh. Настройка туннелирования через NAT и firewall
    • Pidgin для хакеров
    • Печать
    • USB-Flash. монтирование
    • Доступ к данным по MTP
    • Настройка aspell
    • Iptables. Port knocking
    • Sudo, sudoers, visudo
    • Swap в файле в Linux
    • Добрый kill (gdb)
    • Изменить размер tmp (tmpfs)
    • Установка Arch Linux на USB-Flash
    • Эмуляция в QEMU
    • GRUB2 вручную
    • Системные утилиты
    • Настройка редактора vi
    • Краткое руководство по vi
    • HTML-валидатор
    • VDS/VPS
      • Начальная настройка
      • Сборка nginx
      • Настройка nginx
      • Сборка uWSGI (Django+CGI)
      • Настройка uWSGI
    • Управление сетью в Ubuntu с помощью netctl (Arch Linux)
    • Настройка WiFi точки доступа под Linux
  • CS: Искусственный интеллект ▽
    • Метрики в машинном обучении: precision, recall и не только
    • Оценка точности классификатора
    • Нейронные сети на простейших примерах
      • Что такое нейрон (очень коротко)
      • Пример задачи и демонстрация, как нейрон её решает
      • Пример обучения нейрона
      • Что осталось за сценой в задаче для одного нейрона
    • Деревья принятия решений
    • Байесовское машинное обучение
    • Примеры кода numpy, scipy, matplotlib
      • Метод наименьших квадратов
      • Построение системы рекомендаций, на основе текстов
      • Диффузионные реакции (реакции с диффузией)
  • CS: Разное ▽
    • RSA-шифрование на пальцах
    • SQRT-декомпозиция
    • О пользе рекурсии
    • Дискретная бисекция
    • Top-K из N (куча)
    • Быстрое возведение в степень и подсчёт чисел Фибоначчи
    • Алгебра логики
    • Небольшая памятка по C++
    • Проблема останова
    • Примеры простейших серверов на Python
      • Простейший форкающийся сервер
      • Простейший prefork-сервер
      • Простейший многонитевой сервер
      • Многонитевой сервер с простым взаимодействием между нитями
      • Асинхронный сервер
    • Кумулятивное вычисление статистических характеристик
    • Пять задач, которые хорошо бы уметь решать за час
  • Теория относительности ▽
    • Об этих заметках
    • Пространство-время как геометрия
    • Физическая интерпретация
    • Универсальность скорости света
    • Эквивалентность инерциальных систем отсчёта
    • Относительность пространственных и временных интервалов
    • Движение быстрее света
    • Парадокс близнецов
    • Заключение
  • Теория вероятностей ▽
    • Как нас обманывает интуиция
    • Парадокс Монти Холла
    • Парадокс двух конвертов
  • Квантовая механика ▽
    • Принцип неопределённости на классических примерах
  • Фракталы ▽
    • Фрактальная размерность
    • Фрактальные деревья
    • Применение фракталов
    • Комплексная размерность
  • Гиперкуб
  • Обучение и преподавание ▽
    • О репетиторстве
    • Типичные ошибки на экзаменах
    • Лёгкая подготовка к экзаменам
    • Как отвечать на экзамене
  • Как я худел
  • Личное ▽
    • Обо мне (как бы резюме)
    • Благодарности
    • Мои ошибки
    • Немного фотографий
    • Копирование этих материалов

Рекурсивный подход

Строго говоря, это не самый рациональный алгоритм, он требует логарифмическое время и логарифмическую память.

Но, на мой взгляд, он ярче других демонстрирует саму идею, лежащую в основе решения.

def pow(x, p):
    if p == 0:
        return 1
    t = pow(x * x, p // 2)
    if p % 2:
        t *= x
    return t

На каждом шаге рекурсии вы редуцируете задачу x**n и (x**2)**(n/2). Т.е. за один шаг вы вдвое понижаете степень.

Быстрое возведение в положительную целую степень

Эту идею можно реализовать и без рекурсии.

def pow(x, p):
    m = x
    t = 1
    while p:
        if p % 2:
            t *= m
        m *= m
        p //= 2
    return t

Мы получили логарифмическую сложность по времени, но уже константную сложно по памяти.

Быстрое возведение в любую целую степень

Любопытно, что небольшое дополнение к алгоритму позволяет расширить его возможности:

def pow(x, p):
    if p < 0:
        p = -p
        x = 1. / x
    m = x
    t = 1
    while p:
        if p % 2:
            t *= m
        m *= m
        p //= 2
    return t

Напомню, то числа Фибоначчи — это последовательность, в котором два первых числа равны 0 и 1 (или 1 и 1), а каждое последующее равно сумме двух предыдущих.

Предлагаю принять такие обозначения:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  при n >= 2

Числа Фибоначчи можно получать возведением в степень матрицы:

|1 1|n   |F(n+1) F(n)  |
|1 0|  = |F(n)   F(n-1)|

Справедливость этой формулы можно проверить разными способами. Можно внимательно присмотреться. Можно вспомнить/доказать, что F(n+m)=F(n-1)F(m)+F(n)F(m+1). Можно просто посмотреть, что будет при умножении матриц:

|F(n+1) F(n)  | |1 1|   |F(n+1)+F(n) F(n+1)+0|   |F(n+2) F(n+1)|
|F(n)   F(n-1)| |1 0| = |F(n)+F(n-1) F(n)+0  | = |F(n+1) F(n)  |

То есть, умножив матрицу из чисел Фибоначчи на матрицу с тремя единицами, мы сделали один шаг в последовательности Фибоначчи.

Быстрый поиск чисел Фибоначчи

def matrix_mul(a, b):
    return [[
        a[0][0] * b[0][0] + a[0][1] * b[1][0],
        a[0][0] * b[0][1] + a[0][1] * b[1][1]
    ], [
        a[1][0] * b[0][0] + a[1][1] * b[1][0],
        a[1][0] * b[0][1] + a[1][1] * b[1][1]
    ]]
def pow(p):
    m = [[1, 1], [1, 0]]
    t = [[1, 0], [0, 1]]
    while p:
        if p % 2:
            t = matrix_mul(t, m)
        m = matrix_mul(m, m)
        p //= 2
    return t
def fib(n):
    return pow(n)[1][0]

Это уже знакомы нам алгоритм возведения в степень, но не числа, а матрицы.

Быстрый поиск чисел Фибоначчи с помощью numpy

Используя библиотеки, решить эту задачу можно в одну строчку:

import numpy as np
def fib(n):
    return np.linalg.matrix_power(
        np.array([[1, 1], [1, 0]], dtype='O'),
        n
    )[1,0]

Единственно, что следует не забыть, это dtype='O', т.к. иначе, вы очень быстро упрётесь в ограничения разрядности. И, что самое печальное, numpy не предупредить вас об этом. Просто выдаст не правильный результат.



Что такое дробная степень матрицы? – Ник Хайэм

Корень матрицы — это матрица такая, что , и ее можно записать . Для рационального числа (где и — целые числа) определить сложнее: это или ? Эти две возможности могут быть разными даже для . В более общем смысле, как мы можем определить для произвольного действительного числа ?

Напомним, во-первых, что для ненулевого комплексного скаляра мы определяем , где главный логарифм: принимающий значения в полосе . Мы можем обобщить это определение на матрицы. Для невырожденной матрицы определим

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

Наиболее важным частным случаем является положительное целое число, и в этом случае

Мы можем проверить, что

, так что определение действительно дает корень th. Матрица называется главным корнем.

Возвращаясь к случаю рационального , заметим, что

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

Интегральное выражение для справедливо для

Другое представление для с дается биномиальным разложением

Для вещественных матриц вида

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

Вычисление

Эту формулу можно использовать для вычислений, но она является несколько косвенной, поскольку необходимо аппроксимировать как экспоненту, так и логарифм. Хайэм и Лин (2013) разработали более прямой алгоритм, основанный на разложении Шура и приближении Паде степенной функции. Код MATLAB доступен на файловом обмене MathWorks.

Если диагонализируется, так что для некоторого неособого с , то . Эта формула безопасна для использования в вычислениях только в том случае, если она хорошо обусловлена. Для дефектных (недиагонализуемых) мы можем выразить через каноническую форму Жордана, но это выражение бесполезно в вычислительном отношении, потому что каноническая форма Жордана не может быть надежно вычислена.

Обратная функция

Если тогда , по определению квадратного корня. Если из этого следует? Ясно, что ответ «нет» вообще потому, что, например, не подразумевает .

С помощью функции раскручивания матрицы можно показать, что для . Следовательно, функция является обратной функцией для .

Обратная ошибка

Как проверить качество приближения к ? Ибо мы можем проверить остаток , но на самом деле естественного остатка нет. Вместо этого мы можем посмотреть на обратную ошибку.

Для аппроксимации обратная ошибка — это матрица такая, что . Предположим, что и неособы и что . Тогда, как показано в предыдущем разделе, следует . Следовательно, нормальная относительная обратная ошибка равна

Приложения со стохастическими матрицами

Важным применением дробных матричных степеней являются цепи Маркова с дискретным временем, которые возникают в таких областях, как финансы и медицина. Матрица перехода для марковского процесса — это матрица, элементом которой является вероятность перехода из состояния в состояние за временной шаг. Она имеет неотрицательные элементы и сумма строк равна , так что это стохастическая матрица. На практике матрица перехода может быть рассчитана для определенного периода времени, скажем, одного года, но может потребоваться матрица перехода для более короткого периода, скажем, одного месяца. Если — матрица перехода для периода времени, то стохастический корень — это матрица перехода для периода времени в меньший раз. Поэтому (годы в месяцы) и (недели в дни) входят в число интересующих нас значений. К сожалению, это не обязательно стохастическая матрица. Более того, может иметь стохастический корень th, который не равен . Например, стохастическая матрица

имеет главный квадратный корень

, но не является стохастическим из-за отрицательных элементов. Однако квадратный корень

является стохастическим. (Интересно, что это тоже квадратный корень из !)

Возможны самые разнообразные конфигурации в отношении существования, природы (первичные или непервичные) и количества стохастических корней. Higham и Lin (2011) описывают различные возможности, которые могут возникнуть. Они отмечают, что стохастическая нижняя треугольная матрица

имеет стохастический корень th, а именно для всех . Например, до трех значащих цифр

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

Приложения в дробных дифференциальных уравнениях

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

Ссылки

Это минимальный набор ссылок, который содержит дополнительные полезные ссылки внутри.

  • Брайан Дэвис, Встраиваемые марковские матрицы, Electronic J. Вероятность 15, 1474–1486, 2010.
  • Роберто Гарраппа и Марина Пополицио, Об использовании матричных функций для дробных дифференциальных уравнений в частных производных, Math. вычисл. Моделирование C-25(81), 1045–1056, 2011.
  • Николас Дж. Хайэм, Функции матриц: теория и вычисления, Общество промышленной и прикладной математики, Филадельфия, Пенсильвания, США, 2008.
  • Николас Дж. Хайэм и Лицзин Лин, О корнях стохастических матриц, Приложение линейной алгебры. 435(3), 448–463, 2011.
  • Николас Хайэм и Лицзин Лин, Усовершенствованный алгоритм Шура-Паде для дробных степеней матрицы и их производных Фреше, SIAM J. Matrix Anal. заявл. 34(3), 1341–1360, 2013.
  • Эммануэль Лорин и Саймон Тиан, Численное исследование дробных линейных алгебраических систем, Math. вычисл. Моделирование 182, 495–513, 2021.

Связанные записи в блоге

Опубликовано автором Nick HighamОпубликовано в рубрике что-естьОтмечено matrix_function.

NumPy linalg.matrix_power: вычисление степени квадратной матрицы

Автор Танви Бугдани / 3 января 2023 г. 16 февраля 2023 г.

В этом уроке мы узнаем, как возвести матрицу в заданную степень в линейной алгебре с помощью метода linalg.matrix_power в Python, присутствующего в модуле NumPy.

Метод numpy.linalg.matrix_power() используется для возведения квадратной матрицы в целочисленную степень n.

Давайте сначала посмотрим на синтаксис функции.

Также проверьте: Numpy linalg.eig — вычисление собственных значений и правых собственных векторов квадратного массива

  • Параметры:
    • a массив MxM. Входная матрица, которую необходимо возвести в степень.
    • n , целое число, степень или показатель степени. Он может быть положительным, отрицательным или нулевым.
  • Возвратов: или . Возвращаемая матрица имеет ту же форму, что и a . Если n положительное или нулевое значение, тип возвращаемого значения — целочисленный. Если n отрицательное, то тип возвращаемого значения — число с плавающей запятой.
  • Увеличивает: LinAlgError для неквадратных матриц или (для отрицательных степеней), обратная величина которых не может быть вычислена.

Примечание. Если определитель матрицы равен нулю, то нельзя вычислить ее обратную.

Эта функция очень похожа на функцию numpy.power(n, p) , которая принимает два параметра: число n и степень p и возводит n в степень p .


Примеры numpy.linalg.matrix_power

Теперь начнем с нескольких примеров метода numpy linalg matrix power.

Использование numpy.linalg.matrix_power с положительной силой

 импортировать numpy как np
матрица = [[2, 5], [1, 3]]
# расчет степени матрицы
mat_power_2 = np.linalg.matrix_power (матрица, 2)
mat_power_3 = np.linalg.matrix_power (матрица, 3)
print("Матрица = \n", матрица,
      "\nМатричная мощность 2 = \n", mat_power_2,
      "\nМатричная мощность 3 = \n", mat_power_3)
 

Выход:

 Матрица =
 [[2, 5], [1, 3]]
Мощность матрицы 2 =
 [[ 9 25]
 [ 5 14]]
Мощность матрицы 3 =
 [[ 43 120]
 [ 24 67]]
 

Матрица, возведенная в степень 2, рассчитывается путем умножения матрицы на саму себя следующим образом:

Шаг 1 Шаг 2 Шаг 3 Шаг 4 – Окончательный результат степени матрицы 2

Приведенная выше матрица является результатом степени матрицы 2. Теперь, чтобы вычислить степень матрицы 3 , мы можем умножить степень матрицы 2 на заданную матрицу. То есть

Шаг 1Шаг 2Шаг 3Шаг 4 – Окончательный результат степени матрицы 3

Использование numpy.

linalg.power() с отрицательной степенью

Когда мы передаем в функцию отрицательную степень, n , она сначала вычисляет обратную матрицу, а затем возводит обратную в степень abs(n) .

Для матрицы 2×2, например:

Обратное вычисляется как:

 импортировать numpy как np
матрица = [[2, 5], [1, 3]]
# расчет степени матрицы
mat_power = np.linalg.matrix_power (матрица, -2)
print("Matrix = \n", matrix, "\nMatrix power -2 = \n", mat_power)
 

Выход:

 Матрица =
 [[2, 5], [1, 3]]
Мощность матрицы -2 =
 [[ 14. -25.]
 [-5. 9.]]
 

В этом примере

Обратная матрица вычисляется следующим образом:

Теперь возведите эту обратную матрицу в степень абс(-2), т.е. 2 , как показано ниже:

Окончательный результат степени матрицы -2

Использование numpy.linalg.matrix_power с 0

Когда ноль передается в качестве степени функции numpy.linalg.matrix_power , возвращается единичная матрица той же формы, что и входная матрица.

 импортировать numpy как np
матрица_1 = [[2, 5], [1, 3]]
matrix_2 = [[4, 2, 5], [1, 8, 3], [6, 0, 2]]
# расчет степени матрицы
mat_1_power_0 = np.linalg.matrix_power (matrix_1, 0)
mat_2_power_0 = np.linalg.matrix_power (matrix_2, 0)
print("Матрица 1 = \n", matrix_1,
      "\nМатрица 1 мощность 0 = \n", mat_1_power_0,
      "\nМатрица 2 = \n", matrix_2,
      "\nМатрица 2 мощность 0 = \n", mat_2_power_0)
 

Выход:

 Матрица 1 =
 [[2, 5], [1, 3]]
Степень матрицы 1 0 =
 [[1 0]
 [0 1]]
Матрица 2 =
 [[4, 2, 5], [1, 8, 3], [6, 0, 2]]
Степень матрицы 2 0 =
 [[1 0 0]
 [0 1 0]
 [0 0 1]]
 

Поскольку матрица 1 представляет собой матрицу 2×2, выход представляет собой единичную матрицу 2×2, и аналогично, выход матрицы 2, возведенный в 0, представляет собой единичную матрицу 3×3.


Заключение

Итак, в этом уроке мы узнали о функции numpy.linalg.matrix_power , которая используется в линейной алгебре для вычисления степени квадратной матрицы.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *