Участник:Роман Землянский/Zavolskov/Zemlyanskiy - История изменений

ASA в 13:10, 3 февраля 2017

2017-02-03T13:10:41Z

← Предыдущая версия		Версия от 13:10, 3 февраля 2017
Строка 1:		Строка 1:
	~~{{Assignment}}~~		{{Assignment\|IgorS}}

	~~<!--~~{{Assignment\|IgorS}}~~-->~~

	'''Метод «разделяй и властвуй» вычисления собственных значений и векторов симметричной трехдиагональной матрицы'''		'''Метод «разделяй и властвуй» вычисления собственных значений и векторов симметричной трехдиагональной матрицы'''

Роман Землянский в 15:57, 16 декабря 2016

2016-12-16T15:57:33Z

← Предыдущая версия		Версия от 15:57, 16 декабря 2016
Строка 1:		Строка 1:
			{{Assignment}}

	<!--{{Assignment\|IgorS}}-->		<!--{{Assignment\|IgorS}}-->

Роман Землянский: /* Математическое описание алгоритма */

2016-12-16T15:50:52Z

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

← Предыдущая версия		Версия от 15:50, 16 декабря 2016
Строка 148:		Строка 148:
	=== Решение векового уравнения ===		=== Решение векового уравнения ===

	~~=== Решение векового уравнения ===~~
	Подробно стоит поговорить о решении векового уравнения, которое является одной из основных частей алгоритма.		Подробно стоит поговорить о решении векового уравнения, которое является одной из основных частей алгоритма.

Роман Землянский: /* Математическое описание алгоритма */

2016-12-16T15:50:26Z

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

← Предыдущая версия		Версия от 15:50, 16 декабря 2016
Строка 145:		Строка 145:

	Основной выигрыш от использования дефляции состоит не в том, что убыстряется решение векового уравнения - этот этап в любом случае стоит лишь <math>O(n^{2})</math> операций. Выигрыш заключается в ускорении матричного умножения на последнем шаге алгоритма. Действительно, если <math>u_{i}=0</math>, то соответствующий собственный вектор есть i-й столбец <math>e_{i}</math> единичной матрицы. Это означает, что <math>e_{i}</math> является i-м столбцом в матрице <math>Q_{'}</math>, поэтому при формировании матрицы <math>Q</math> посредством левого умножения <math>Q_{1}</math> на <math>Q_{2}</math> вычисление i-го столбца не требует никаких затрат. Аналогичное упрощение имеет место в случае <math>d_{i} = d_{i+1}</math>. При дефляции многих собственных значений устраняется большая часть работы, связанной с матричным умножением.		Основной выигрыш от использования дефляции состоит не в том, что убыстряется решение векового уравнения - этот этап в любом случае стоит лишь <math>O(n^{2})</math> операций. Выигрыш заключается в ускорении матричного умножения на последнем шаге алгоритма. Действительно, если <math>u_{i}=0</math>, то соответствующий собственный вектор есть i-й столбец <math>e_{i}</math> единичной матрицы. Это означает, что <math>e_{i}</math> является i-м столбцом в матрице <math>Q_{'}</math>, поэтому при формировании матрицы <math>Q</math> посредством левого умножения <math>Q_{1}</math> на <math>Q_{2}</math> вычисление i-го столбца не требует никаких затрат. Аналогичное упрощение имеет место в случае <math>d_{i} = d_{i+1}</math>. При дефляции многих собственных значений устраняется большая часть работы, связанной с матричным умножением.

			=== Решение векового уравнения ===

			=== Решение векового уравнения ===
			Подробно стоит поговорить о решении векового уравнения, которое является одной из основных частей алгоритма.

			Предположим, что некоторое <math>u_{i}</math>, хотя и мало, все же недостаточно мало для того, чтобы была зарегистрирована дефляция. В этом случае применение метода Ньютона к решению векового уравнения встречается с затруднениями. Вспомним, что пересчет приближённого решения <math>u_{j}</math> уравнения <math>f(\lambda) = 0</math> в методе Ньютона основан на следующих положениях:

			1. Вблизи точки <math>\lambda = \lambda_{j}</math> функция <math>f(\lambda)</math> аппроксимируется линейной функцией <math>l(\lambda)</math>; график есть прямая линия, касающаяся графика функции <math>f(\lambda)</math> при <math>\lambda = \lambda_{j}</math>.

			2. В качестве <math>\lambda_{j+1}</math> берётся нуль этого линейного приближения, т.е. <math>l(\lambda_{j+1})=0</math>.

			Функция, показанная на рис.1, не доставляет видимых трудностей методу Ньютона, поскольку вблизи каждого своего нуля <math>f(\lambda)</math> достаточно хорошо аппроксимируется линейными функциями. Однако рассмотрим график функции на рис. 4. Она получена из функции на рис. 1 заменой значения .5 для <math>u_{i}^{2}</math> на .001. Это новое значение недостаточно мало для того, чтобы вызвать дефляцию. График функции в левой части рис.4 визуально не отличим от её вертикальных и горизонтальных асимптот, поэтому в правой части укрупненно воспроизведён фрагмент графика, прилегающий к вертикальной асимптоте <math>\lambda = 2</math>. Видно, что график слишком быстро "выполняет поворот" и для большей части значений <math>\lambda</math> почти горизонтален. Поэтому, применяя метод Ньютона почти к любому начальному приближению <math>\lambda_{0}</math>, мы получаем линейное приближение <math>l(\lambda)</math> с почти горизонтальным графиком и малым положительным угловым коэффициентом. В результате <math>\lambda_{1}</math> является отрицательным числом, огромным по абсолютной величине, которое совершенно бесполезно в качестве приближения к истинному корню.

			[[File:GraphNewton.png\|thumb\|center\|800px\|Рис. 4. График функции <math> f(\lambda) = 1 + \frac{10^{-3}}{1 - \lambda} + \frac{10^{-3}}{2 - \lambda} + \frac{10^{-3}}{3 - \lambda} + \frac{10^{-3}}{4 - \lambda}</math>]]

			Чтобы найти выход из этого положения, можно модифицировать метод Ньютона следующим образом: раз <math>f(\lambda)</math> нельзя хорошо приблизить линейной функцией <math>l(\lambda)</math>, попробуем взять в качестве приближения какую-нибудь другую простую функцию <math>h(\lambda)</math>. Нет ничего особого именно в прямых линиях: для метода Ньютона вместо <math>l(\lambda)</math> можно взять любое приближение <math>h(\lambda)</math>, значения и нули которого легко вычисляются. Функция <math>f(\lambda)</math> имеет полюсы в точках <math>d_{i}</math> и <math>d_{i+1}</math>, которые определяют её поведение в соответствующих окрестностях. Поэтому при поиске корня в интервале <math>(d_{i+1}, d_{i})</math> естественно выбрать функцию <math>h(\lambda)</math>, также имеющую эти полюсы, т.е. функцию вида
			<math>h(\lambda)= \frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda} + c_{3}</math>

			Константы <math>c_{1},c_{2}</math> и <math>c_{3}</math> обеспечивающие, что <math>h(\lambda)</math> есть приближение к <math>f(\lambda)</math>, можно выбрать несколькими способами. Отметим, что если <math>c_{1},c_{2}</math> и <math>c_{3}</math> уже известны, то уравнение <math>h(\lambda)=0</math> легко решается относительно <math>\lambda</math>, поскольку сводится к эквивалентному квадратному уравнению
			<math>c_{1}(d_{i+1}-\lambda)+c_{2}(d_{i}-\lambda)+c_{3}(d_{i}-\lambda)(d_{i+1}-\lambda)=0</math>

			Пусть <math>\lambda_{j}</math> - приближённое значение корня. определим <math>c_{1},c_{2}</math> и <math>c_{3}</math> так, чтобы
			<math>\frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda} + c_{3} = h(\lambda) \approx f(\lambda) = 1 + \rho \sum_{k=1, n} \frac{u_{k}^{2}} {d_{k}-\lambda} </math>

			для <math>\lambda</math> в окрестности <math>\lambda_{j}</math>. Заметим, что

			<math>f(\lambda) = 1 + \rho \sum_{k=1, i} \frac{u_{k}^{2}} {d_{k}-\lambda} + \rho \sum_{k=i+1, n} \frac{u_{k}^{2}} {d_{k}-\lambda} \equiv 1 + \psi_{1}(\lambda) + \psi_{2}(\lambda)</math>.

			Если <math>\lambda \in (d_{i+1},d_{i})</math>, то <math>\psi_{1}(\lambda)</math> есть сумма положительных слагаемых, а <math>\psi_{2}(\lambda)</math> - сумма отрицательных. Поэтому и <math>\psi_{1}(\lambda)</math>, и <math>\psi_{2}(\lambda)</math> могут быть вычислены с высокой точностью; однако при их сложении вполне вероятно взаимное уничтожение верных разрядов и потеря относительной точности в сумме. Возьмем числа <math>c_{1}</math> и <math>\hat{c_{1}}</math>, такие, что функция

			<math>h_{1}(\lambda) \equiv \hat{c_{1}} + \frac{c_{1}}{d_{i}-\lambda}</math> удовлетворяет условиям <math>h_{1}(\lambda_{j}) = \psi_{1}(\lambda_{j})</math> и <math>h_{1}^{'}(\lambda_{j})=\psi_{1}^{'}(\lambda_{j})</math> (1)

			Это означает, что гипербола, являющаяся графиком функции <math>h_{1}(\lambda)</math>, касается графика функции <math>\psi_{i}(\lambda)</math> при <math>\lambda = \lambda_{j}</math>. Два условия в (1) - это обычные условия метода Ньютона, за исключением того, что вместо прямой в качестве приближения используется гипербола. Легко проверить, что <math>c_{1}=\psi_{1}^{'}(\lambda_{j})(d_{i} - \lambda_{j})^{2}</math> и <math>\hat{c_{1}}=\psi_{1}(\lambda_{j}) - \psi_{1}^{'}(\lambda_{j})(d_{i} - \lambda_{j})</math>

			Подобным же образом выбираем <math>c_{2}</math> и <math>\hat{c_{2}}</math> так, чтобы функция

			<math>h_{2}(\lambda) \equiv \hat{c_{2}} + \frac{c_{2}}{d_{i+1}-\lambda}</math>

			Удовлетворяла условиям

			<math>h_{2}(\lambda_{j}) = \psi_{2}(\lambda_{j})</math> и <math>h_{2}^{'}(\lambda_{j})=\psi_{2}^{'}(\lambda_{j})</math> (2)

			Наконец, полагаем

			<math>h(\lambda) = 1 + h_{1}(\lambda) + h_{2}(\lambda) = (1 + \hat{c_{1}} + \hat{c_{2}} + \frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda} </math>

			<math>\equiv c_{3} + \frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda}</math>.

	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==

Роман Землянский: /* Макроструктура алгоритма */

2016-12-16T15:49:53Z

Макроструктура алгоритма

← Предыдущая версия		Версия от 15:49, 16 декабря 2016
Строка 156:		Строка 156:

	[[File:InfoGraph.jpg\|thumb\|center\|1200px\|Рис. 3. Детальное описание одного блока алгоритма]]		[[File:InfoGraph.jpg\|thumb\|center\|1200px\|Рис. 3. Детальное описание одного блока алгоритма]]

	~~=== Решение векового уравнения ===~~
	Подробно стоит поговорить о решении векового уравнения, которое является одной из основных частей алгоритма.

	Предположим, что некоторое <math>u_{i}</math>, хотя и мало, все же недостаточно мало для того, чтобы была зарегистрирована дефляция. В этом случае применение метода Ньютона к решению векового уравнения встречается с затруднениями. Вспомним, что пересчет приближённого решения <math>u_{j}</math> уравнения <math>f(\lambda) = 0</math> в методе Ньютона основан на следующих положениях:

	1. Вблизи точки <math>\lambda = \lambda_{j}</math> функция <math>f(\lambda)</math> аппроксимируется линейной функцией <math>l(\lambda)</math>; график есть прямая линия, касающаяся графика функции <math>f(\lambda)</math> при <math>\lambda = \lambda_{j}</math>.

	~~2. В качестве <math>\lambda_{j+1}</math> берётся нуль этого линейного приближения, т.е. <math>l(\lambda_{j+1})=0</math>.~~

	Функция, показанная на рис.1, не доставляет видимых трудностей методу Ньютона, поскольку вблизи каждого своего нуля <math>f(\lambda)</math> достаточно хорошо аппроксимируется линейными функциями. Однако рассмотрим график функции на рис. 4. Она получена из функции на рис. 1 заменой значения .5 для <math>u_{i}^{2}</math> на .001. Это новое значение недостаточно мало для того, чтобы вызвать дефляцию. График функции в левой части рис.4 визуально не отличим от её вертикальных и горизонтальных асимптот, поэтому в правой части укрупненно воспроизведён фрагмент графика, прилегающий к вертикальной асимптоте <math>\lambda = 2</math>. Видно, что график слишком быстро "выполняет поворот" и для большей части значений <math>\lambda</math> почти горизонтален. Поэтому, применяя метод Ньютона почти к любому начальному приближению <math>\lambda_{0}</math>, мы получаем линейное приближение <math>l(\lambda)</math> с почти горизонтальным графиком и малым положительным угловым коэффициентом. В результате <math>\lambda_{1}</math> является отрицательным числом, огромным по абсолютной величине, которое совершенно бесполезно в качестве приближения к истинному корню.

	[[File:GraphNewton.png\|thumb\|center\|800px\|Рис. 4. График функции <math> f(\lambda) = 1 + \frac{10^{-3}}{1 - \lambda} + \frac{10^{-3}}{2 - \lambda} + \frac{10^{-3}}{3 - \lambda} + \frac{10^{-3}}{4 - \lambda}</math>]]

	Чтобы найти выход из этого положения, можно модифицировать метод Ньютона следующим образом: раз <math>f(\lambda)</math> нельзя хорошо приблизить линейной функцией <math>l(\lambda)</math>, попробуем взять в качестве приближения какую-нибудь другую простую функцию <math>h(\lambda)</math>. Нет ничего особого именно в прямых линиях: для метода Ньютона вместо <math>l(\lambda)</math> можно взять любое приближение <math>h(\lambda)</math>, значения и нули которого легко вычисляются. Функция <math>f(\lambda)</math> имеет полюсы в точках <math>d_{i}</math> и <math>d_{i+1}</math>, которые определяют её поведение в соответствующих окрестностях. Поэтому при поиске корня в интервале <math>(d_{i+1}, d_{i})</math> естественно выбрать функцию <math>h(\lambda)</math>, также имеющую эти полюсы, т.е. функцию вида
	~~<math>h(\lambda)= \frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda} + c_{3}</math>~~

	Константы <math>c_{1},c_{2}</math> и <math>c_{3}</math> обеспечивающие, что <math>h(\lambda)</math> есть приближение к <math>f(\lambda)</math>, можно выбрать несколькими способами. Отметим, что если <math>c_{1},c_{2}</math> и <math>c_{3}</math> уже известны, то уравнение <math>h(\lambda)=0</math> легко решается относительно <math>\lambda</math>, поскольку сводится к эквивалентному квадратному уравнению
	~~<math>c_{1}(d_{i+1}-\lambda)+c_{2}(d_{i}-\lambda)+c_{3}(d_{i}-\lambda)(d_{i+1}-\lambda)=0</math>~~

	~~Пусть <math>\lambda_{j}</math> - приближённое значение корня. определим <math>c_{1},c_{2}</math> и <math>c_{3}</math> так, чтобы~~
	~~<math>\frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda} + c_{3} = h(\lambda) \approx f(\lambda) = 1 + \rho \sum_{k=1, n} \frac{u_{k}^{2}} {d_{k}-\lambda} </math>~~

	~~для <math>\lambda</math> в окрестности <math>\lambda_{j}</math>. Заметим, что~~

	~~<math>f(\lambda) = 1 + \rho \sum_{k=1, i} \frac{u_{k}^{2}} {d_{k}-\lambda} + \rho \sum_{k=i+1, n} \frac{u_{k}^{2}} {d_{k}-\lambda} \equiv 1 + \psi_{1}(\lambda) + \psi_{2}(\lambda)</math>.~~

	Если <math>\lambda \in (d_{i+1},d_{i})</math>, то <math>\psi_{1}(\lambda)</math> есть сумма положительных слагаемых, а <math>\psi_{2}(\lambda)</math> - сумма отрицательных. Поэтому и <math>\psi_{1}(\lambda)</math>, и <math>\psi_{2}(\lambda)</math> могут быть вычислены с высокой точностью; однако при их сложении вполне вероятно взаимное уничтожение верных разрядов и потеря относительной точности в сумме. Возьмем числа <math>c_{1}</math> и <math>\hat{c_{1}}</math>, такие, что функция

	<math>h_{1}(\lambda) \equiv \hat{c_{1}} + \frac{c_{1}}{d_{i}-\lambda}</math> удовлетворяет условиям <math>h_{1}(\lambda_{j}) = \psi_{1}(\lambda_{j})</math> и <math>h_{1}^{'}(\lambda_{j})=\psi_{1}^{'}(\lambda_{j})</math> (1)

	Это означает, что гипербола, являющаяся графиком функции <math>h_{1}(\lambda)</math>, касается графика функции <math>\psi_{i}(\lambda)</math> при <math>\lambda = \lambda_{j}</math>. Два условия в (1) - это обычные условия метода Ньютона, за исключением того, что вместо прямой в качестве приближения используется гипербола. Легко проверить, что <math>c_{1}=\psi_{1}^{'}(\lambda_{j})(d_{i} - \lambda_{j})^{2}</math> и <math>\hat{c_{1}}=\psi_{1}(\lambda_{j}) - \psi_{1}^{'}(\lambda_{j})(d_{i} - \lambda_{j})</math>

	~~Подобным же образом выбираем <math>c_{2}</math> и <math>\hat{c_{2}}</math> так, чтобы функция~~

	~~<math>h_{2}(\lambda) \equiv \hat{c_{2}} + \frac{c_{2}}{d_{i+1}-\lambda}</math>~~

	~~Удовлетворяла условиям~~

	~~<math>h_{2}(\lambda_{j}) = \psi_{2}(\lambda_{j})</math> и <math>h_{2}^{'}(\lambda_{j})=\psi_{2}^{'}(\lambda_{j})</math> (2)~~

	~~Наконец, полагаем~~

	~~<math>h(\lambda) = 1 + h_{1}(\lambda) + h_{2}(\lambda) = (1 + \hat{c_{1}} + \hat{c_{2}} + \frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda} </math>~~

	~~<math>\equiv c_{3} + \frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda}</math>.~~

	== Схема реализации последовательного алгоритма ==		== Схема реализации последовательного алгоритма ==

Роман Землянский: /* Информационный граф */

2016-12-16T15:49:04Z

Информационный граф

← Предыдущая версия		Версия от 15:49, 16 декабря 2016
Строка 250:		Строка 250:

	== Информационный граф ==		== Информационный граф ==
	В данном разделе представлен информационный граф алгоритма: на рисунке 5 изображена часть алгоритма, в которой происходит деление - "Divide", а на рисунке 6 описана часть "Conquer".		В данном разделе на рисунке 5 представлен информационный граф алгоритма.

	[[File:InfoGraphSC.jpg\|thumb\|center\|left\|1200px\|Рис. 5. Информационный граф алгоритма "Разделяй и властвуй" - шаг <b>Divide</b>]]		[[File:InfoGraphSC.jpg\|thumb\|center\|left\|1200px\|Рис. 5. Информационный граф алгоритма "Разделяй и властвуй" - шаг <b>Divide</b>]]

Роман Землянский: /* Масштабируемость алгоритма и его реализации */

2016-12-16T15:48:29Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 15:48, 16 декабря 2016
Строка 356:		Строка 356:
	Для управления количеством потоков использовалась операция OpenMP omp_set_num_threads();		Для управления количеством потоков использовалась операция OpenMP omp_set_num_threads();

	[[File:ResultsDiagram.jpg\|thumb\|center\|left\|800px\|Рис. 7. График времени работы программы в зависимости от числа процессов и размера задачи]]		[[File:ResultsDiagram.jpg\|thumb\|center\|left\|800px\|Рис. 6. График времени работы программы в зависимости от числа процессов и размера задачи]]

	Масштабируемость рассматриваемой реализации алгоритма '''"Разделяй и властвуй"''':		Масштабируемость рассматриваемой реализации алгоритма '''"Разделяй и властвуй"''':

Роман Землянский: /* Информационный граф */

2016-12-16T15:48:10Z

Информационный граф

← Предыдущая версия		Версия от 15:48, 16 декабря 2016
Строка 253:		Строка 253:

	[[File:InfoGraphSC.jpg\|thumb\|center\|left\|1200px\|Рис. 5. Информационный граф алгоритма "Разделяй и властвуй" - шаг <b>Divide</b>]]		[[File:InfoGraphSC.jpg\|thumb\|center\|left\|1200px\|Рис. 5. Информационный граф алгоритма "Разделяй и властвуй" - шаг <b>Divide</b>]]

	[[File:Infograph2.jpg\|thumb\|center\|1200px\|Рис. 6. Информационный граф алгоритма "Разделяй и властвуй" - шаг <b>Conquer</b>. Qkk - матрица собственных значений размерности <b>k</b>. Lkk - матрица собственных векторов размерности <b>k</b>.]]

	Операции:		Операции:

Роман Землянский: /* Свойства алгоритма */

2016-12-16T15:44:19Z

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

← Предыдущая версия		Версия от 15:44, 16 декабря 2016
Строка 314:		Строка 314:
	Описанный в данной статье алгоритм является самым быстрым алгоритмом, среди существующих: QR / Бисекция и обратная итерация / Разделяй и властвуй.		Описанный в данной статье алгоритм является самым быстрым алгоритмом, среди существующих: QR / Бисекция и обратная итерация / Разделяй и властвуй.

	Последовательная сложность алгоритма: ~~<math> t = c\frac{4}{3}n^{3} </math>~~		Последовательная сложность алгоритма (не принимая во внимание дефляцию) удовлетворяет рекурсивному соотношению:

	~~Параллельная~~ сложность алгоритма (в силу использования дефляции): <math> O(n^{2.3})</math> или в самых редких случаях <math> O(n^{2}) </math> (см. [3] стр. 8).		<math>t(n) = n^3 +2t(\frac{n}{2})</math>

			Решение которого имеет вид:

			<math> t = c\frac{4}{3}n^{3} </math>

			На практике же, параллельная сложность алгоритма в силу использования дефляции, позволяющей получить выигрыш в количестве операций, который заключается в ускорении матричного умножения на последнем шаге алгоритма (см. [[#Дефляция]]), имеет следующий вид: <math> O(n^{2.3})</math> или в самых редких случаях <math> O(n^{2}) </math> (см. [3] стр. 8).

	Особенности алгоритма:		Особенности алгоритма:

Роман Землянский: /* Информационный граф */

2016-12-16T15:24:32Z

Информационный граф

← Предыдущая версия		Версия от 15:24, 16 декабря 2016
Строка 252:		Строка 252:
	В данном разделе представлен информационный граф алгоритма: на рисунке 5 изображена часть алгоритма, в которой происходит деление - "Divide", а на рисунке 6 описана часть "Conquer".		В данном разделе представлен информационный граф алгоритма: на рисунке 5 изображена часть алгоритма, в которой происходит деление - "Divide", а на рисунке 6 описана часть "Conquer".

	[[File:InfoGraphSC.jpg\|thumb\|center\|left\|~~800px~~\|Рис. 5. Информационный граф алгоритма "Разделяй и властвуй" - шаг <b>Divide</b>]]		[[File:InfoGraphSC.jpg\|thumb\|center\|left\|1200px\|Рис. 5. Информационный граф алгоритма "Разделяй и властвуй" - шаг <b>Divide</b>]]

	[[File:Infograph2.jpg\|thumb\|center\|1200px\|Рис. 6. Информационный граф алгоритма "Разделяй и властвуй" - шаг <b>Conquer</b>. Qkk - матрица собственных значений размерности <b>k</b>. Lkk - матрица собственных векторов размерности <b>k</b>.]]		[[File:Infograph2.jpg\|thumb\|center\|1200px\|Рис. 6. Информационный граф алгоритма "Разделяй и властвуй" - шаг <b>Conquer</b>. Qkk - матрица собственных значений размерности <b>k</b>. Lkk - матрица собственных векторов размерности <b>k</b>.]]