Kaholicl в 11:52, 3 ноября 2025

2025-11-03T11:52:27Z

← Предыдущая версия		Версия от 11:52, 3 ноября 2025
Строка 1:		Строка 1:
	~~вправравраврп~~		{{algorithm
			\| name = Адаптивный крестовый метод
			\| serial_complexity = <math>O(k^2(m+n))</math>
			\| pf_height = <math>O(k)</math>
			\| pf_width = <math>O(m+n)</math>
			\| input_data = <math>O(k(m+n))</math>
			\| output_data = <math>O(k(m+n))</math>
			}}

			Основные авторы описания: [[Участник:Kaholicl\|П.А.Панов]]

			== Свойства и структура алгоритма ==

			=== Общее описание алгоритма ===

			'''Адаптивный крестовый метод''' (Adaptive Cross Approximation, ACA) — это итерационный алгоритм для построения низкоранговой аппроксимации матриц, который не требует вычисления и хранения всех элементов исходной матрицы. Метод был разработан для эффективной работы с матрицами, возникающими при дискретизации интегральных уравнений и в других приложениях вычислительной математики<ref>Bebendorf M. Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems. — Springer, 2008.</ref>.

			Основная идея метода заключается в построении аппроксимации матрицы <math>A \in \mathbb{R}^{m \times n}</math> в виде произведения двух матриц меньшей размерности: <math>A \approx U_k V_k^T</math>, где <math>U_k \in \mathbb{R}^{m \times k}</math>, <math>V_k \in \mathbb{R}^{n \times k}</math>, и <math>k \ll \min(m,n)</math>. При этом алгоритм вычисляет только <math>O(k(m+n))</math> элементов исходной матрицы вместо полных <math>O(mn)</math>.

			=== Математическое описание алгоритма ===

			Исходные данные: матрица <math>A</math> (заданная неявно, через функцию вычисления элементов), допустимая погрешность <math>\varepsilon</math>, максимальный ранг <math>k_{max}</math>.

			Вычисляемые данные: матрицы <math>U_k = [u_1, \ldots, u_k]</math> и <math>V_k = [v_1, \ldots, v_k]</math> такие, что <math>A \approx U_k V_k^T</math>.

			'''Формулы метода:'''

			'''Инициализация:'''
			* <math>j_1 = 1</math> (начальный ведущий столбец)
			* <math>k = 1</math>

			'''Основные итерационные формулы:'''
			* <math>
			\tilde{u}_k = A_{:,j_k} - \sum_{p=1}^{k-1} u_p (v_p^T)_{j_k}
			</math>
			* <math>
			i_k = \arg\max_{1 \leq i \leq m} \|(\tilde{u}_k)_i\|
			</math>
			* <math>
			u_k = \frac{\tilde{u}_k}{(\tilde{u}_k)_{i_k}}
			</math>
			* <math>
			\tilde{v}_k^T = A_{i_k,:} - \sum_{p=1}^{k-1} (u_p)_{i_k} v_p^T
			</math>
			* <math>
			v_k = \tilde{v}_k
			</math>
			* <math>
			j_{k+1} = \arg\max_{1 \leq j \leq n} \|(\tilde{v}_k)_j\|
			</math>

			'''Критерии остановки:'''
			* Если <math>\\|u_k v_k^T\\|_F \leq \varepsilon \\|A_k\\|_F</math>, где <math>A_k = \sum_{p=1}^k u_p v_p^T</math>
			* Или если <math>k = k_{max}</math>
			* Иначе: <math>k = k + 1</math>, перейти к следующей итерации

			'''Вычислительные характеристики:'''
			* Сложность одной итерации: <math>O(k(m+n))</math>
			* Общая сложность: <math>O(k^2(m+n))</math>
			* Объем памяти: <math>O(k(m+n))</math>
			* Количество вычисляемых элементов матрицы: <math>O(k(m+n))</math> вместо <math>O(mn)</math>

Kaholicl: Новая страница: «вправравраврп»

2025-11-03T10:07:46Z

Новая страница: «вправравраврп»

Новая страница

вправравраврп

Участник:Kaholicl/Адаптивный крестовый метод - История изменений

Kaholicl в 11:52, 3 ноября 2025

Kaholicl: Новая страница: «вправравраврп»