Ctrl+K

Домашнее задание

Домашнее задание#

Задание 1. Генератор случайных матриц.#

Реализовать генератор матриц, который должен поддерживать функции:

  • Генерация абсолютно случайной матрицы \(n\times m\)

  • Генерация случайной диагональной матрицы \(n\times n\)

  • Генерация случайной верхнетреугольной матрицы

  • Генерация случайной нижнетреугольной матрицы

  • Генерация симметричной матрицы

  • Генерация вырожденной матрицы

  • Генерация матрицы ступенчатого вида \(n\times n\) ранга \(m\)

  • Генерация возмущения матрицы \(n\times m\), каждый элемент которой не превосходит по модулю заданный \(\varepsilon\). Оценить величину нормы матрицы возмущений в зависимости от параметра \(\varepsilon\) (оценить верхную границу).

Оценить численно вероятность того, что созданная матрица будет вырожденной для какого-либо случая выше.

# Реализую произвольную m,n, верхнетреугольную и симметричную. Остальное на вас - вам нужно дописать функцию.
# Не забудьте откомментировать ваши изменения в документации к функции!

import numpy as np

def matrix_generate(rows, columns, type_ = "full", eps = 0):
    """
    matrix_generate(rows, columns, type_ = "full")

    Создаёт случайную матрицу выбранного типа.

    Если матрицу нужных размеров создать нельзя должен выдать
    строку f"Error with type {type_} and shape ({rows},{columns})".

    Parameters
    ----------

    rows : int
        Количество строк в создаваемой матрице.
    columns : int
        Количество столбцов в создаваемой матрице.
    type_ : str, optional
        Тип создаваемой матрицы: "full", "upper_triangular", "symmetric" и т.д.
    eps: float, optional
        Дополнительное число, использующееся при генерации для некоторых типов матриц.

    Returns
    -------
    out : ndarray or str
        Выдаёт матрицу нужного типа либо ошибку.

    Notes
    -----
    Поддерживаемые типы матриц:
        "full","upper_triangular",
        "symmetric",
        ...


    """

    A = None

    if type_ == "full":
0,
        A = np.random.random(size=(rows, columns))

    elif type_ == "upper_triangular":

        A = np.random.random(size=(rows, columns))

        for i in range(rows):
            for j in range(columns):
                if (i > j):
                    A[i, j] = 0

        # Для нижнетреугольной подумайте, как сделать без циклов for :) (звёздочка)

    elif type_ == "symmetric":

        if rows != columns:
            return f"Error with type {type_} and shape ({rows},{columns})"

        else:

            A = np.random.random(size=(rows, columns))

            for i in range(rows):
                for j in range(columns):
                    if (i > j):
                        A[i, j] = A[j, i]

            # И эту секцую тоже перепишите без for (звёздочка). Учтите, что портить uniform распределение нельзя.

    return A

matrix_generate(1, 3)

array([[0.92729915, 0.46372064, 0.3302204 ]])

matrix_generate(4, 4, type_ = "upper_triangular")

array([[0.29095118, 0.48243508, 0.33314696, 0.11652231],
       [0.        , 0.38207998, 0.3216804 , 0.19134324],
       [0.        , 0.        , 0.19209787, 0.8512658 ],
       [0.        , 0.        , 0.        , 0.83580995]])

matrix_generate(4, 3, type_ = "upper_triangular")

array([[0.53609234, 0.36418414, 0.88111427],
       [0.        , 0.98355036, 0.59701315],
       [0.        , 0.        , 0.73738553],
       [0.        , 0.        , 0.        ]])

matrix_generate(4, 4, type_ = "symmetric")

array([[0.1556073 , 0.68119342, 0.99206063, 0.21796994],
       [0.68119342, 0.11418224, 0.15759881, 0.11224172],
       [0.99206063, 0.15759881, 0.70145001, 0.26590431],
       [0.21796994, 0.11224172, 0.26590431, 0.03111788]])

matrix_generate(4, 1, type_ = "symmetric")

'Error with type symmetric and shape (4,1)'

Задание 2. Вычисление матричных норм и числа обусловленности.#

Реализовать вычисление трех основных норм векторов (L1, L2 и максимальную) и подчиненных им матричных норм. Реализовать вычисление числа обусловленности.

Примечание: для вычисления собственных значений можно использовать linalg.eigvals из модуля scipy.

Задание 3. Эквивалентность первых двух норм.#

Найдите константы \(C_1\) и \(C_2\) такие, что

\(\ C_1||\mathbf{x}||_2\leq||\mathbf{x}||_1\leq C_2||\mathbf{x}||_2\)

Указание: в качестве подсказки можно использовать визуализацию норм из документа с теорией.

Задание 4. Евклидова и бесконечная норма.#

Пусть x — вектор размерности m, а A — матрица m×n. Докажите следующие неравенства и приведите примеры таких x и A, при которых неравенства обращаются в равенства:

  • \(\|x\|_2 \leq \sqrt{m} \cdot \|x\|_{\infty}\)

  • \(\|A\|_{\infty} \leq \sqrt{n} \cdot \|A\|_2\)

Задание 5. Норма Фробениуса.#

Докажите, что для любой унитарной матрицы U (и для произвольной матрицы A) имеет место равенство

\(\| U A \|_F = \| AU \|_F = \| A \|_F\) ,

где \(\| \cdot \|_F\) — норма Фробениуса.

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

Задание 6*. Тензорная свёртка.#

Рассмотрим функцию, отображающую шесть тензоров на один тензор: \(Z\left(\lambda^{(1)}, \lambda^{(2)}, \lambda^{(3)}, \Gamma^{(1)}, \Gamma^{(2)}, U\right)\) :

\[ Z_{a h i j}=\sum_{b c d e f g} \lambda^{(1)}{ }_{a b} \Gamma_{c b d}^{(1)} \lambda^{(2)}{ }_{d e} \Gamma_{f e g}^{(2)} \lambda_{g h}^{(3)} U_{i j c f} \]

редположив, что все индексы пробегают значения от 1 до χ, проведите эксперимент и сравните скорость различных реализаций функции Z. Исследуйте значения χ в диапазоне 3–50.

  • В файле convolution. ipynb вы можете найти релизацию глупого способа вычисления этой свертки, который требует \(\chi^4 \times \chi^6=\chi^{10}\) операций. На самом деле это можно вычислить гораздо быстрее!

  • С помощью функции numpy . einsum (нужно использовать аргумент optimize), можно добиться намного большей производительности. Чтобы понять, что происходит под капотом, воспользуйтесь функцией numpy.einsum_path. Какое минимальное количество операций требуется для вычисления \(Z\) ?

  • Посмотрев на вывод функции numpy.einsum_path, peализуйте алгоритм для вычисления \(Z\), который столь же эффективен, как numpy.einsum, но использует более элементарные numpy.dot и numpy.tensor_dot.

Содержание