Вопросы с тегом «na.numerical-analysis»

40
Сложность нахождения собственного разложения матрицы

Мой вопрос прост: Что наихудшее время работы наилучшего известного алгоритма для вычисления eigendecomposition в качестве матрицы?n×nn×nn \times n Собственное разложение сводится к умножению матриц или в худшем случае наиболее известные алгоритмы (через SVD )?O(n3)O(n3)O(n^3) Обратите внимание, что...

31
Вычислительная сложность пи

Позволять L={n:the nth binary digit of π is 1}L={n:the nth binary digit of π is 1}L = \{ n : \text{the }n^{th}\text{ binary digit of }\pi\text{ is }1 \} (где считается закодированным в двоичном виде). Тогда что мы можем сказать о вычислительной сложности ? Понятно, что . И если я не ошибаюсь,...

27
Как в вычислениях указываются действительные числа?

Это может быть основной вопрос, но я читал и пытался понять статьи по таким темам, как вычисление равновесия по Нэшу и тестирование линейного вырождения, и не был уверен в том, как действительные числа указываются в качестве входных данных. Например, когда утверждается, что LDT имеет определенные...

23
Теорема об универсальной аппроксимации - нейронные сети

Я разместил это ранее на MSE, но было предложено, что здесь может быть лучшее место, чтобы спросить. Теорема универсального приближения утверждает, что «стандартная многослойная сеть прямой связи с одним скрытым слоем, которая содержит конечное число скрытых нейронов, является универсальным...

16
Как вычислить степени квадратных матриц?

Предположим, нам дана матрица , и пусть . Как быстро мы можем вычислить мощность этой матрицы?A∈RN×NA∈RN×NA \in \mathbb R^{N\times N}m∈N0m∈N0m \in \mathbb N_0AmAmA^m Следующая лучшая вещь по сравнению с вычислением продуктов - это использование быстрой экспоненты, для которой требуются матричные...

12
Численная устойчивость симплекс-метода

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

12
Мотивация для оценки объема

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

10
Целочисленные корни многочлена

Какой алгоритм мы можем использовать, чтобы найти все целочисленные корни многочлена с целыми коэффициентами?е( х )f(x)f(x) Я замечаю, что Мудрец может найти корни в течение нескольких секунд, даже когда все коэффициенты очень велики. Как это может сделать это?е( х...

9
Сложность нахождения собственного разложения * симметричной * матрицы

Это специализированная версия предыдущего вопроса: сложность нахождения собственного разложения матрицы . Для симметричных матриц NxN известно, что времени O (N ^ 3) достаточно для вычисления собственного разложения. Вопрос в том, можем ли мы достичь субкубической сложности?...

9
Доказательство для верхней границы суммы квадратов

В [1] Garey et al. определите то, что позже будет известно как проблема суммы квадратных корней в ходе разработки NP-полноты евклидовой TSP. Даны целые числа a1,a2,…,ana1,a2,…,ana_1, a_2, \ldots, a_n а также LLLопределить, если a1−−√+a2−−√+⋯+an−−√<La1+a2+⋯+an<L\sqrt{a_1} + \sqrt{a_2} + \cdots...