Участник:Роман Землянский/Метод "Разделяй и властвуй" - История изменений

Роман Землянский в 20:49, 1 ноября 2016

2016-11-01T20:49:54Z

← Предыдущая версия		Версия от 20:49, 1 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~
	Авторы статьи: Завольсков Владислав, [[U:Роман Землянский\|Землянский Роман]], 614 группа		Авторы статьи: Завольсков Владислав, [[U:Роман Землянский\|Землянский Роман]], 614 группа

Lineprinter: Lineprinter переименовал страницу Участники: Завольсков Владислав, Землянский Роман Метод "Разделяй и властвуй" в [[Участник:Роман Землянски…

2016-11-01T08:41:49Z

Lineprinter переименовал страницу Участники: Завольсков Владислав, Землянский Роман Метод "Разделяй и властвуй" в [[Участник:Роман Землянски…

← Предыдущая версия	Версия от 08:41, 1 ноября 2016
(нет различий)

Lineprinter в 14:11, 28 октября 2016

2016-10-28T14:11:04Z

← Предыдущая версия		Версия от 14:11, 28 октября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment}}
	Авторы статьи: Завольсков Владислав, Землянский Роман, 614 группа		Авторы статьи: Завольсков Владислав, [[U:Роман Землянский\|Землянский Роман]], 614 группа

	= ЧАСТЬ. Свойства и структура алгоритмов =		= ЧАСТЬ. Свойства и структура алгоритмов =

Роман Землянский в 17:31, 15 октября 2016

2016-10-15T17:31:08Z

← Предыдущая версия		Версия от 17:31, 15 октября 2016
Строка 1:		Строка 1:
			{{Assignment}}
	Авторы статьи: Завольсков Владислав, Землянский Роман, 614 группа		Авторы статьи: Завольсков Владислав, Землянский Роман, 614 группа

Роман Землянский в 17:21, 15 октября 2016

2016-10-15T17:21:13Z

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

	Авторы статьи: Завольсков Владислав, Землянский Роман, 614 группа		Авторы статьи: Завольсков Владислав, Землянский Роман, 614 группа

Роман Землянский в 17:18, 15 октября 2016

2016-10-15T17:18:36Z

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

	Авторы статьи: Завольсков Владислав, Землянский Роман, 614 группа		Авторы статьи: Завольсков Владислав, Землянский Роман, 614 группа

Роман Землянский: Роман Землянский переименовал страницу Verfinalnewtest Zem/Zav в Участники: Завольсков Владислав, Землянский Роман Метод "Разделяй и властвуй"

2016-10-15T17:17:45Z

Роман Землянский переименовал страницу Verfinalnewtest Zem/Zav в Участники: Завольсков Владислав, Землянский Роман Метод "Разделяй и властвуй"

← Предыдущая версия	Версия от 17:17, 15 октября 2016
(нет различий)

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

2016-10-15T17:15:02Z

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

← Предыдущая версия		Версия от 17:15, 15 октября 2016
Строка 120:		Строка 120:
	В разделе [[#Информационный граф]] описана структура алгоритма, в которой есть блок умножения матриц для вычисления собственных векторов, являющийся вычислительным ядром алгоритма. В соответствующем разделе ([[#Вычислительное ядро алгоритма]]) мы упоминали о том, что данному блоку предшествует вычисление собственных значений, которое производится [https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0 методом Ньютона].		В разделе [[#Информационный граф]] описана структура алгоритма, в которой есть блок умножения матриц для вычисления собственных векторов, являющийся вычислительным ядром алгоритма. В соответствующем разделе ([[#Вычислительное ядро алгоритма]]) мы упоминали о том, что данному блоку предшествует вычисление собственных значений, которое производится [https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0 методом Ньютона].

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

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

2016-10-15T17:13:22Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 17:13, 15 октября 2016
Строка 207:		Строка 207:


	Если <math> Q_{1}, Q_{2}</math> и <math>Q^{'}</math> рассматриваются как плотные матрицы и используется стандартный алгоритм матричного умножения, то константа <math> c </math> в последней строке равна 1. Таким образом, именно это умножение составляет наиболее трудоёмкую часть алгоритма в целом. Игнорируя члены порядка <math>n^{2}</math>, получаем <math>t(n) = 2t(n/2) + cn^{3}</math>. Решая это разностное уравнение, находим <math> t = c\frac{4}{3}n^{3} </math>		Если <math> Q_{1}, Q_{2}</math> и <math>Q^{'}</math> рассматриваются как плотные матрицы и используется стандартный алгоритм матричного умножения, то константа <math> c </math> в последней строке равна 1. Таким образом, именно это умножение составляет наиболее трудоёмкую часть алгоритма в целом. Игнорируя члены порядка <math>n^{2}</math>, получаем <math>t(n) = 2t(n/2) + cn^{3}</math>. Решая это разностное уравнение, находим <math> t \approx c\frac{4}{3}n^{3} </math>

	На практике константа <math>c</math> обычно гораздо меньше 1, потому что матрица <math>Q^{'}</math> весьма разрежена вследствие явления, называемого дефляцией.		На практике константа <math>c</math> обычно гораздо меньше 1, потому что матрица <math>Q^{'}</math> весьма разрежена вследствие явления, называемого дефляцией.

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

2016-10-15T17:13:01Z

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

← Предыдущая версия		Версия от 17:13, 15 октября 2016
Строка 79:		Строка 79:
	Таким образом,		Таким образом,

	<math>det(I + \rho (D - \lambda I)^{-1}uu^{T}) = 1 + \rho u^{T}(D - \lambda I)^{-1}u</math> <math> = 1 + \rho \sum_{i=1, n} \frac{u_{i}^{2}} {d_{i}-\lambda} = f(\lambda)</math> ,		<math>det(I + \rho (D - \lambda I)^{-1}uu^{T}) = 1 + \rho u^{T}(D - \lambda I)^{-1}u</math> <math> = 1 + \rho \sum_{i=1, n} \frac{u_{i}^{2}} {d_{i}-\lambda} \equiv f(\lambda)</math> ,

	т.е. собственные значения матрицы <math>T</math> есть корни так называемого векового уравнения <math>f(\lambda) = 0</math>. Если все числа <math>d_{i}</math> различны и все <math>u_{i} <> 0</math> (случай общего положения), то <math>f(\lambda)</math> имеет график типа показанного на рис.1(где <math>n = 4</math> и <math>\rho > 0</math>).		т.е. собственные значения матрицы <math>T</math> есть корни так называемого векового уравнения <math>f(\lambda) = 0</math>. Если все числа <math>d_{i}</math> различны и все <math>u_{i} <> 0</math> (случай общего положения), то <math>f(\lambda)</math> имеет график типа показанного на рис.1(где <math>n = 4</math> и <math>\rho > 0</math>).