Участник:EasyBreezy/Стабилизированный метод бисопряженных градиентов (BiCGSTAB) - История изменений

Algoman: Algoman переименовал страницу Участник:EasyBreezy/Стабилизированный метод биспоряженных градиентов (BiCGSTAB) в [[Участник:EasyBreezy/Стабилизированны…

2016-12-20T15:36:54Z

Algoman переименовал страницу Участник:EasyBreezy/Стабилизированный метод биспоряженных градиентов (BiCGSTAB) в [[Участник:EasyBreezy/Стабилизированны…

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

Algoman в 15:35, 20 декабря 2016

2016-12-20T15:35:10Z

← Предыдущая версия		Версия от 15:35, 20 декабря 2016
Строка 1:		Строка 1:
	Основные авторы описания: [[Участник:Novikov alexander\|Александр Новиков (1.4, 1.6, 1.7, 2.4, 2.7, 3)]], [[Участник:EasyBreezy\|Гаврилов Алексей (1.1 - 1.3, 1.5, 1.8, 1.9, 2.7, 3)]]		Основные авторы описания: [[Участник:Novikov alexander\|Александр Новиков (1.4, 1.6, 1.7, 2.4, 2.7, 3)]], [[Участник:EasyBreezy\|Гаврилов Алексей (1.1 - 1.3, 1.5, 1.8, 1.9, 2.7, 3)]]
	~~{{Assignment}}~~
	{{algorithm		{{algorithm
	\| name = BiCGSTAB		\| name = BiCGSTAB

EasyBreezy в 09:38, 19 декабря 2016

2016-12-19T09:38:48Z

← Предыдущая версия		Версия от 09:38, 19 декабря 2016
Строка 3:		Строка 3:
	{{algorithm		{{algorithm
	\| name = BiCGSTAB		\| name = BiCGSTAB
	\| serial_complexity = <math> O(N^2) </math>, где <math> N </math> - размерность СЛАУ		\| serial_complexity = <math> O(I * N^2) </math>, где <math> N </math> - размерность СЛАУ, <math>I</math> - количество итераций
	\| pf_height = <math> O(k*(6 \sqrt N + 4N + 5 \lceil \frac{N}{p} \rceil)) </math>		\| pf_height = <math> O(k*(6 \sqrt N + 4N + 5 \lceil \frac{N}{p} \rceil)) </math>
	\| pf_width = <math> 2 \sqrt N </math>		\| pf_width = <math> 2 \sqrt N </math>

EasyBreezy: /* Ресурс параллелизма алгоритма */

2016-12-19T09:32:34Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 09:32, 19 декабря 2016
Строка 120:		Строка 120:

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	Основной прирост производительности параллельной версии алгоритма дает использование параллельных операций вычисления скалярного произведения, суммы векторов, а так же произведения матрицы на вектор. Каждая из операций вычисления скалярного произведения и суммы векторов, выполняемая на p процессорах, за счет метода сдваивания может ускориться до <math> \frac{p}{\log_2 p} </math> раз. Ускорение же умножения матрицы на вектор может достигать p раз.		Основной прирост производительности параллельной версии алгоритма дает использование параллельных операций вычисления скалярного произведения, суммы векторов, а так же произведения матрицы на вектор. Каждая из операций вычисления скалярного произведения и суммы векторов, выполняемая на <math>p</math> процессорах, за счет метода сдваивания может ускориться до <math> \frac{p}{\log_2 p} </math> раз. Ускорение же умножения матрицы на вектор может достигать <math>p</math> раз.

	Ширина и высота ЯПФ графа данного алгоритма напрямую зависит от конкретных реализаций макроопераций и входных данных.		Ширина и высота ЯПФ графа данного алгоритма напрямую зависит от конкретных реализаций макроопераций и входных данных.

	Для последовательно-параллельной реализации операции взятия скалярного произведения в наиболее оптимальном случае (<math>p= \sqrt N</math>) высота будет равна <math>2 \sqrt N - 1</math>, а ширина <math>\sqrt N</math>, где N - это длина вектора решения.		Для последовательно-параллельной реализации операции взятия скалярного произведения в наиболее оптимальном случае (<math>p= \sqrt N</math>) высота будет равна <math>2 \sqrt N - 1</math>, а ширина <math>\sqrt N</math>, где <math>N</math> - это длина вектора решения.

	Высота ЯПФ простейшего алгоритма умножения матрицы на вектор равна 2N, а ширина m, где N - это уже упомянутая длина вектора(она же ширина матрицы), а m - высота матрицы.		Высота ЯПФ простейшего алгоритма умножения матрицы на вектор равна <math>2N</math>, а ширина <math>m</math>, где <math>N</math> - это уже упомянутая длина вектора(она же ширина матрицы), а m - высота матрицы.

	Высота ЯПФ операции умножения вектора на число = <math>\frac{N}{p}</math>, а ширина p.		Высота ЯПФ операции умножения вектора на число равна <math>\frac{N}{p}</math>, а ширина <math>p</math>.

	Высота ЯПФ операции вычисления разности векторов = <math> \log_2 p </math>, а ширина p.		Высота ЯПФ операции вычисления разности векторов = <math> \log_2 p </math>, а ширина <math>p</math>.

	В конечном счете общую высоту ЯПФ одной итерации алгоритма можно оценить, как <math>6 \sqrt N-3 + 4N + 3 + 1 + 3\lceil \frac{N}{p} \rceil + 2 \lceil \frac{N}{p} \rceil = 6 \sqrt N + 4N + 5 \lceil \frac{N}{p} \rceil + 1</math>, а ширину, как <math>2 \sqrt N</math>, если не брать в рассчет проверку критерия сходимости и упрощенности первой итерации по сравнению с остальными.		В конечном счете общую высоту ЯПФ одной итерации алгоритма можно оценить, как <math>6 \sqrt N-3 + 4N + 3 + 1 + 3\lceil \frac{N}{p} \rceil + 2 \lceil \frac{N}{p} \rceil = 6 \sqrt N + 4N + 5 \lceil \frac{N}{p} \rceil + 1</math>, а ширину, как <math>2 \sqrt N</math>, если не брать в рассчет проверку критерия сходимости и упрощенности первой итерации по сравнению с остальными.

EasyBreezy: /* Общее описание алгоритма */

2016-12-19T09:30:42Z

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

← Предыдущая версия		Версия от 09:30, 19 декабря 2016
Строка 20:		Строка 20:
	:Благодаря свойствам алгоритма область применения метода весьма широка. Фактически, он используется во всех задачах, где требуется решать СЛАУ, в том числе СЛАУ большой размерности, к которым сводится большое количество численных методов, применяемых при решении задач математического моделирования.		:Благодаря свойствам алгоритма область применения метода весьма широка. Фактически, он используется во всех задачах, где требуется решать СЛАУ, в том числе СЛАУ большой размерности, к которым сводится большое количество численных методов, применяемых при решении задач математического моделирования.

	:BiCGSTAB относится к классу так называемых проекционных методов. Основная идея методов данного класса: искать итерационным способом наилучшее приближение решения в некотором подпространстве пространства <math>R^n</math>, и чем шире подпространство, в котором ищется приближение решения, тем ближе будет приближенное решение к точному на каждой итерации. В качестве такого подпространства используются пространства Крылова, порожденные матрицей системы и невязкой первого приближения: <math>K^m (A, r^0) = span(r^0, Ar^0, A^2r^0, ..., A^{m-1} r^0).</math><ref>Горбаченко В.И, Вычислительная линейная алгебра с примерами на MATLAB. — СПб.: БХВ-Петербург, 2011. — 320 с.: ил. — (Учебное пособие)</ref>		:BiCGSTAB относится к классу так называемых проекционных методов. Основная идея методов данного класса: искать итерационным способом наилучшее приближение решения в некотором подпространстве пространства <math>R^n</math>, и чем шире подпространство, в котором ищется приближение решения, тем ближе будет приближенное решение к точному на каждой итерации. В качестве такого подпространства используются пространства Крылова, порожденные матрицей системы и невязкой первого приближения: <math>K^m (A, r^0) = \rm span(r^0, Ar^0, A^2r^0, ..., A^{m-1} r^0).</math><ref>Горбаченко В.И, Вычислительная линейная алгебра с примерами на MATLAB. — СПб.: БХВ-Петербург, 2011. — 320 с.: ил. — (Учебное пособие)</ref>


Строка 29:		Строка 29:
	:Пусть для СЛАУ известно некоторое приближение <math>x^0</math> точного решения <math>x^*</math>. Данное приближение требуется уточнить поправкой <math> \delta: b - Ax^0 + \delta \perp L</math>. Невязка уточненного решения имеет вид: <math>r_{new} = b - Ax^0 + \delta = r^0- A\delta</math>. Условие Петрова-Галеркина тогда можно переписать так: <math>(r_{new}, z)= r^0 - (A\delta, z) = 0, \forall z \in L</math>		:Пусть для СЛАУ известно некоторое приближение <math>x^0</math> точного решения <math>x^*</math>. Данное приближение требуется уточнить поправкой <math> \delta: b - Ax^0 + \delta \perp L</math>. Невязка уточненного решения имеет вид: <math>r_{new} = b - Ax^0 + \delta = r^0- A\delta</math>. Условие Петрова-Галеркина тогда можно переписать так: <math>(r_{new}, z)= r^0 - (A\delta, z) = 0, \forall z \in L</math>

	:Пусть <math> dim K = dim L = m, V = (v_1, ..., v_n) \in R^{n \times m}, W = (w_1, ... w_n) \in R^{n \times m}</math>, где <marh>V</math> и <math>W</math> – матрицы, столбцы которых образуют базисы пространств <math>K</math> и <math>L</math> соответственно. Пусть так же <math> \delta = Vy, z = Wq</math>, где <math>y</math> – коэффициенты разложения вектора поправки по базису пространства <math>K</math>, а <math>q</math> – коэффициенты разложения вектора <math>z</math> в пространстве <math>L</math>. Тогда новое приближение решения можно записать в виде: <math>x^1 = x^0 + \delta= x^0 + Vy</math>. Из условия ортогональности Петрова-Галеркина получаем, что: <math>(r - AVy, Wq) = (W^Tr^0 - AVy, q) = 0</math>. Поскольку <math>q \neq 0</math>, то получаем СЛАУ для вектора <math>y</math>: <math>W^TAVy = W^Tr^0</math>. Если предположить, что матрица <math>W^TAVy</math> невырождена, то вектор y однозначно определяется и равен: <math>y = W^TAV^{-1}W^Tr^0</math>. Подставляя найденные коэффициенты разложения в выражение для первого приближения получаем: <math>x^1 = x^0 + \delta = x^0 + W^TAV^{-1}W^Tr^0y</math>		:Пусть <math>\rm dim K = dim L = m, V = (v_1, ..., v_n) \in R^{n \times m}, W = (w_1, ... w_n) \in R^{n \times m}</math>, где <marh>V</math> и <math>W</math> – матрицы, столбцы которых образуют базисы пространств <math>K</math> и <math>L</math> соответственно. Пусть так же <math> \delta = Vy, z = Wq</math>, где <math>y</math> – коэффициенты разложения вектора поправки по базису пространства <math>K</math>, а <math>q</math> – коэффициенты разложения вектора <math>z</math> в пространстве <math>L</math>. Тогда новое приближение решения можно записать в виде: <math>x^1 = x^0 + \delta= x^0 + Vy</math>. Из условия ортогональности Петрова-Галеркина получаем, что: <math>(r - AVy, Wq) = (W^Tr^0 - AVy, q) = 0</math>. Поскольку <math>q \neq 0</math>, то получаем СЛАУ для вектора <math>y</math>: <math>W^TAVy = W^Tr^0</math>. Если предположить, что матрица <math>W^TAVy</math> невырождена, то вектор y однозначно определяется и равен: <math>y = W^TAV^{-1}W^Tr^0</math>. Подставляя найденные коэффициенты разложения в выражение для первого приближения получаем: <math>x^1 = x^0 + \delta = x^0 + W^TAV^{-1}W^Tr^0y</math>

	:Подведем итог. Общий порядок шагов любого проекционного метода следующий:		:Подведем итог. Общий порядок шагов любого проекционного метода следующий:

EasyBreezy: /* Общее описание алгоритма */

2016-12-19T09:28:22Z

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

← Предыдущая версия		Версия от 09:28, 19 декабря 2016
Строка 23:		Строка 23:


	:Изложим основную идею любого проекционного метода, заложенную в том числе и в BiCGSTAB. Для простоты выкладок и рассуждений здесь и далее будем считать, что матрица системы и ее правая часть вещественны. Без ограничения общности все дальнейшие рассуждения могут быть перенесены и на комплексный случай. Итак, пусть решается система <math>Ax=b</math> с невырожденной матрицей <math>A \in R^{n \times n}</math> и ненулевым вектором <math>b \in R^n</math>. Имеются два подпространства <math>K_n</math> и <math>L_n</math>. Требуется найти вектор <math>x \in K_n</math>, который обеспечивает решение системы, оптимальное относительно подпространства L, то есть требуется выполнение условия Петрова-Галеркина: <math>(Ax,z)=(b,z), \forall z \in L_n</math>. В данном случае вектор x называется обобщенным решением системы.		:Изложим основную идею любого проекционного метода, заложенную в том числе и в BiCGSTAB. Для простоты выкладок и рассуждений здесь и далее будем считать, что матрица системы и ее правая часть вещественны. Без ограничения общности все дальнейшие рассуждения могут быть перенесены и на комплексный случай. Итак, пусть решается система <math>Ax=b</math> с невырожденной матрицей <math>A \in R^{n \times n}</math> и ненулевым вектором <math>b \in R^n</math>. Имеются два подпространства <math>K_n</math> и <math>L_n</math>. Требуется найти вектор <math>x \in K_n</math>, который обеспечивает решение системы, оптимальное относительно подпространства <math>L</math>, то есть требуется выполнение условия Петрова-Галеркина: <math>(Ax,z)=(b,z), \forall z \in L_n</math>. В данном случае вектор x называется обобщенным решением системы.

	:Условие Петрова-Галеркина можно записать и через определение невязки. Пусть <math>r = b - Ax</math> - невязка, тогда условие Петрова-Галеркина перепишется в виде: <math>(b - Ax, z)=(r, z),\forall z \in L_n</math>. Это равносильно тому, что вектор невязки ортогонален пространству <math>L_n</math>.		:Условие Петрова-Галеркина можно записать и через определение невязки. Пусть <math>r = b - Ax</math> - невязка, тогда условие Петрова-Галеркина перепишется в виде: <math>(b - Ax, z)=(r, z),\forall z \in L_n</math>. Это равносильно тому, что вектор невязки ортогонален пространству <math>L_n</math>.
Строка 29:		Строка 29:
	:Пусть для СЛАУ известно некоторое приближение <math>x^0</math> точного решения <math>x^*</math>. Данное приближение требуется уточнить поправкой <math> \delta: b - Ax^0 + \delta \perp L</math>. Невязка уточненного решения имеет вид: <math>r_{new} = b - Ax^0 + \delta = r^0- A\delta</math>. Условие Петрова-Галеркина тогда можно переписать так: <math>(r_{new}, z)= r^0 - (A\delta, z) = 0, \forall z \in L</math>		:Пусть для СЛАУ известно некоторое приближение <math>x^0</math> точного решения <math>x^*</math>. Данное приближение требуется уточнить поправкой <math> \delta: b - Ax^0 + \delta \perp L</math>. Невязка уточненного решения имеет вид: <math>r_{new} = b - Ax^0 + \delta = r^0- A\delta</math>. Условие Петрова-Галеркина тогда можно переписать так: <math>(r_{new}, z)= r^0 - (A\delta, z) = 0, \forall z \in L</math>

	:Пусть <math> dim K = dim L = m, V = (v_1, ..., v_n) \in R^{n \times m}, W = (w_1, ... w_n) \in R^{n \times m}</math>, где V и W – матрицы, столбцы которых образуют базисы пространств K и L соответственно. Пусть так же <math> \delta = Vy, z = Wq</math>, где y – коэффициенты разложения вектора поправки по базису пространства K, а q – коэффициенты разложения вектора z в пространстве L. Тогда новое приближение решения можно записать в виде: <math>x^1 = x^0 + \delta= x^0 + Vy</math>. Из условия ортогональности Петрова-Галеркина получаем, что: <math>(r - AVy, Wq) = (W^Tr^0 - AVy, q) = 0</math>. Поскольку <math>q \neq 0</math>, то получаем СЛАУ для вектора y: <math>W^TAVy = W^Tr^0</math>. Если предположить, что матрица <math>W^TAVy</math> невырождена, то вектор y однозначно определяется и равен: <math>y = W^TAV^{-1}W^Tr^0</math>. Подставляя найденные коэффициенты разложения в выражение для первого приближения получаем: <math>x^1 = x^0 + \delta = x^0 + W^TAV^{-1}W^Tr^0y</math>		:Пусть <math> dim K = dim L = m, V = (v_1, ..., v_n) \in R^{n \times m}, W = (w_1, ... w_n) \in R^{n \times m}</math>, где <marh>V</math> и <math>W</math> – матрицы, столбцы которых образуют базисы пространств <math>K</math> и <math>L</math> соответственно. Пусть так же <math> \delta = Vy, z = Wq</math>, где <math>y</math> – коэффициенты разложения вектора поправки по базису пространства <math>K</math>, а <math>q</math> – коэффициенты разложения вектора <math>z</math> в пространстве <math>L</math>. Тогда новое приближение решения можно записать в виде: <math>x^1 = x^0 + \delta= x^0 + Vy</math>. Из условия ортогональности Петрова-Галеркина получаем, что: <math>(r - AVy, Wq) = (W^Tr^0 - AVy, q) = 0</math>. Поскольку <math>q \neq 0</math>, то получаем СЛАУ для вектора <math>y</math>: <math>W^TAVy = W^Tr^0</math>. Если предположить, что матрица <math>W^TAVy</math> невырождена, то вектор y однозначно определяется и равен: <math>y = W^TAV^{-1}W^Tr^0</math>. Подставляя найденные коэффициенты разложения в выражение для первого приближения получаем: <math>x^1 = x^0 + \delta = x^0 + W^TAV^{-1}W^Tr^0y</math>

	:Подведем итог. Общий порядок шагов любого проекционного метода следующий:		:Подведем итог. Общий порядок шагов любого проекционного метода следующий:

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

2016-12-19T09:25:31Z

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

← Предыдущая версия		Версия от 09:25, 19 декабря 2016
Строка 111:		Строка 111:
	:Наконец, сложение или вычитание векторов требует <math>6N</math> соотвествующих операций. Столько же требует 6 произведений вектора на число.		:Наконец, сложение или вычитание векторов требует <math>6N</math> соотвествующих операций. Столько же требует 6 произведений вектора на число.

	:Итого: <math>2N(2N - 1) + 12N - 6 + 6N + 6N = 4N^2 + 22N - 6</math> операций за одну итерацию. Домножая это на количество итераций <math>I<math>, получаем итоговую сложность алгоритма: <math>I * (4N^2 + 22N - 6)</math>		:Итого: <math>2N(2N - 1) + 12N - 6 + 6N + 6N = 4N^2 + 22N - 6</math> операций за одну итерацию. Домножая это на количество итераций <math>I</math>, получаем итоговую сложность алгоритма: <math>I * (4N^2 + 22N - 6)</math>

	:Имеются так же операции как, извлечение квадратного корня и деление вещественных чисел друг на друга, но они не принимаются в расчет, так как они не влияют на итоговый результат. Окончательно можно заключить, что последовательная сложность алгоритма эквивалента <math>O(I * N^2)</math>		:Имеются так же операции как, извлечение квадратного корня и деление вещественных чисел друг на друга, но они не принимаются в расчет, так как они не влияют на итоговый результат. Окончательно можно заключить, что последовательная сложность алгоритма эквивалента <math>O(I * N^2)</math>

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

2016-12-19T09:25:11Z

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

← Предыдущая версия		Версия от 09:25, 19 декабря 2016
Строка 111:		Строка 111:
	:Наконец, сложение или вычитание векторов требует <math>6N</math> соотвествующих операций. Столько же требует 6 произведений вектора на число.		:Наконец, сложение или вычитание векторов требует <math>6N</math> соотвествующих операций. Столько же требует 6 произведений вектора на число.

	:Итого: <math>2N(2N - 1) + 12N - 6 + 6N + 6N = 4N^2 + 22N - 6</math> операций.		:Итого: <math>2N(2N - 1) + 12N - 6 + 6N + 6N = 4N^2 + 22N - 6</math> операций за одну итерацию. Домножая это на количество итераций <math>I<math>, получаем итоговую сложность алгоритма: <math>I * (4N^2 + 22N - 6)</math>

	:Имеются так же операции как, извлечение квадратного корня и деление вещественных чисел друг на друга, но они не принимаются в расчет, так как они не влияют на итоговый результат. Окончательно можно заключить, что последовательная сложность алгоритма эквивалента <math>O(N^2)</math>		:Имеются так же операции как, извлечение квадратного корня и деление вещественных чисел друг на друга, но они не принимаются в расчет, так как они не влияют на итоговый результат. Окончательно можно заключить, что последовательная сложность алгоритма эквивалента <math>O(I * N^2)</math>

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

EasyBreezy: /* Ресурс параллелизма алгоритма */

2016-12-19T09:19:43Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 09:19, 19 декабря 2016
Строка 124:		Строка 124:
	Ширина и высота ЯПФ графа данного алгоритма напрямую зависит от конкретных реализаций макроопераций и входных данных.		Ширина и высота ЯПФ графа данного алгоритма напрямую зависит от конкретных реализаций макроопераций и входных данных.

	Для последовательно-параллельной реализации операции взятия скалярного произведения в наиболее оптимальном случае (<math>p= \sqrt n</math>) высота будет равна <math>2 \sqrt n - 1</math>, а ширина <math>\sqrt n</math>, где n - это длина вектора решения.		Для последовательно-параллельной реализации операции взятия скалярного произведения в наиболее оптимальном случае (<math>p= \sqrt N</math>) высота будет равна <math>2 \sqrt N - 1</math>, а ширина <math>\sqrt N</math>, где N - это длина вектора решения.

	Высота ЯПФ простейшего алгоритма умножения матрицы на вектор равна 2n, а ширина m, где n - это уже упомянутая длина вектора(она же ширина матрицы), а m - высота матрицы.		Высота ЯПФ простейшего алгоритма умножения матрицы на вектор равна 2N, а ширина m, где N - это уже упомянутая длина вектора(она же ширина матрицы), а m - высота матрицы.

	Высота ЯПФ операции умножения вектора на число = <math>\frac{n}{p}</math>, а ширина p.		Высота ЯПФ операции умножения вектора на число = <math>\frac{N}{p}</math>, а ширина p.

	Высота ЯПФ операции вычисления разности векторов = <math> \log_2 p </math>, а ширина p.		Высота ЯПФ операции вычисления разности векторов = <math> \log_2 p </math>, а ширина p.

	В конечном счете общую высоту ЯПФ одной итерации алгоритма можно оценить, как <math>6 \sqrt n-3 + 4n + 3 + 1 + 3\lceil \frac{n}{p} \rceil + 2 \lceil \frac{n}{p} \rceil = 6 \sqrt n + 4n + 5 \lceil \frac{n}{p} \rceil + 1</math>, а ширину, как <math>2 \sqrt n</math>, если не брать в рассчет проверку критерия сходимости и упрощенности первой итерации по сравнению с остальными.		В конечном счете общую высоту ЯПФ одной итерации алгоритма можно оценить, как <math>6 \sqrt N-3 + 4N + 3 + 1 + 3\lceil \frac{N}{p} \rceil + 2 \lceil \frac{N}{p} \rceil = 6 \sqrt N + 4N + 5 \lceil \frac{N}{p} \rceil + 1</math>, а ширину, как <math>2 \sqrt N</math>, если не брать в рассчет проверку критерия сходимости и упрощенности первой итерации по сравнению с остальными.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

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

2016-12-19T09:15:44Z

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

← Предыдущая версия		Версия от 09:15, 19 декабря 2016
Строка 105:		Строка 105:
	:Всего в вычислительном блоке алгоритма присутствует 20 трудоемких операций: 2 операции умножения матрицы на вектор, 6 скалярных произведений и 6 сложений/вычитаний векторов и 6 умножений вектора на число.		:Всего в вычислительном блоке алгоритма присутствует 20 трудоемких операций: 2 операции умножения матрицы на вектор, 6 скалярных произведений и 6 сложений/вычитаний векторов и 6 умножений вектора на число.

	:Каждое скалярное произведение требует <math>n</math> произведений и <math>n - 1</math> сложение, то есть <math>2n - 1</math> операции. Скалярных произведений всего 6 штук (включая поиск нормы), что дает нам <math>~~12n~~ - 6</math> операций.		:Каждое скалярное произведение требует <math>N</math> произведений и <math>N - 1</math> сложение, то есть <math>2N - 1</math> операции. Скалярных произведений всего 6 штук (включая поиск нормы), что дает нам <math>12N - 6</math> операций.

	:Умножение матрицы размерности <math>n \times n</math> на вектор эквивалентно взятию еще <math>n</math> скаляров, и так как таких операций в вычислительном ядре 2, то дополнительно имеется еще <math>2n(2n - 1)</math> операций.		:Умножение матрицы размерности <math>N \times N</math> на вектор эквивалентно взятию еще <math>N</math> скаляров, и так как таких операций в вычислительном ядре 2, то дополнительно имеется еще <math>2N(2N - 1)</math> операций.

	:Наконец, сложение или вычитание векторов требует <math>6n</math> соотвествующих операций. Столько же требует 6 произведений вектора на число.		:Наконец, сложение или вычитание векторов требует <math>6N</math> соотвествующих операций. Столько же требует 6 произведений вектора на число.

	:Итого: <math>2n(2n - 1) + ~~12n~~ - 6 + 6n + 6n = 4n^2 + ~~22n~~ - 6</math> операций.		:Итого: <math>2N(2N - 1) + 12N - 6 + 6N + 6N = 4N^2 + 22N - 6</math> операций.

	:~~Нетрудоемкие~~ операции, ~~вроде~~ извлечение квадратного корня и деление вещественных чисел друг на друга, не принимаются в расчет, так как они не влияют на итоговый результат. Окончательно можно заключить, что последовательная сложность алгоритма эквивалента <math>O(n^2)</math>		:Имеются так же операции как, извлечение квадратного корня и деление вещественных чисел друг на друга, но они не принимаются в расчет, так как они не влияют на итоговый результат. Окончательно можно заключить, что последовательная сложность алгоритма эквивалента <math>O(N^2)</math>

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