Алговики - Вклад [ru]

Участник:Nikita270a

2016-10-17T22:14:03Z

Nikita270a:

{{algorithm
| name = Алгоритм Ланцоша с полной переортогонализацией
| serial_complexity = <math>O(n^2)+O(nk^2) </math>
| input_data = <math>\frac{n(n + 1)}{2}</math>
| output_data = <math>k(n + 1)</math>
}}

Авторы: Алексейчук Н.Н 616, Ястребов К.С. 609.

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

Алгоритм Ланцоша ищет собвственные значения и собственные векторы для симетричной матрицы A вещественных чисел. Является итерацонным алгоритмом. Алгоритм Ланцоша использует степенной метод (<math> b_{k+1} = \frac{Ab_k}{||Ab_k||} </math>) для поиска наибольших собственных значений и векторов матриц.

В отличие от прямых алгоритмов требует мешьше памяти и мощности, что является несомненным плюсом для больших матриц.

Несмотря на свою скорость работы и экономию памяти, сначала не был популярным алгоритмом из – за недостаточной вычислительной устойчивости. В 1970 году Ojalvo и Newman [http://arc.aiaa.org/doi/abs/10.2514/3.5878?journalCode=aiaaj] показали способ сделать алгоритм достаточно устойчивым. В этой же статье алгоритм был применен к расчету инженерной конструкции с большим количеством узлов, которые подвергались динамической нагрузке.

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

Памятка:
Степенной метод нахождения наибольшего собственного числа матрицы можно сформулировать в предельном виде: если <math> b_0 </math> – случайный вектор, и <math> b_n+1 = Ab_n </math>, тогда для больших чисел n предел <math>x_n/||x_n|| </math> стремится к нормированному наибольшему собственному вектору.

Алгоритм Ланцоша комбинирует метод Ланцоша для нахождения крыловского подпространства и метод Релэя – Ритца.

Подпространство Крылова для степенного метода:
<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>

В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>.

Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца.

Из-за ошибок округления вектора <math> A^{k-1}x_1 </math>, формирующие подпространство Крылова, становятся неортогональными. Чтобы решить данную прорблему, проводят переортогонализацию методом Грамма-Шмидта.

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

Вычислительным ядром данного алгоритма являются следующие шаги:
*1. <math>Aq=( \sum\nolimits_{i=^n}a_{1i}q_i, \sum\nolimits_{i=2}^na_{2i}q_i, ..., \sum\nolimits_{i=1}^na_{ni}q_i)</math>.

*2. <math>z=z-\sum\nolimits_{i=1}^{k}(z^Tq_i)q_i.</math>

В данном случае первая операция выполняет умножение симметричной матрицы <math>A</math> размерности <math>n</math>X<math>n</math> на <math>n</math>-мерный вектор <math>q</math>, вследствие чего вычислительная сложность выполнения заключается в <math>n^2</math> умножений и <math>n^2-n</math> сложений. Второе действие является процессом ортогонализации Грама-Шмидта. В последнем действии вычисляются <math>k^2n+k(n+2)</math> умножений и <math>k^2n + k(n + 1) + 2</math> операций сложения.

== Макроструктура алгоритма ==
*1. Скалярное произведение: <math> (x,y) </math>.

*2. Суммирование: <math> x+\alpha y </math>.

== Схема ==
Input: A, b (random vector with unit norm)
: <math>

\begin{align}
q_1 = b/||b||_2, \beta_0 = 0, q_0 = 0 \\
j = 1 ,...,k \\
q_1&=b/||b||,\beta_0=0,q_o=0. \\
z&=Aq_j, \\
\alpha_j&=q_j^Tz, \\
z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\
\beta&=||z||,\\
q_{j+1}&=z/\beta_j, \quad j \in [1, k].

\end{align}

</math>

==Вычислительная сложность==
Количество операций складывается из количества операций для классического метода Ланцоша[https://books.google.ru/books?id=T8EPBwAAQBAJ&pg=PA242&lpg=PA242&dq=lanczos+algorithm+complexity&source=bl&ots=kWVnVP_uJp&sig=a-4GTEt6vRE8YhR1R6dOPwvOSIk&hl=en&sa=X&ved=0ahUKEwiQ2u3U4-LPAhWvbZoKHe0QBaw4ChDoAQg7MAY#v=onepage&q=lanczos%20algorithm%20complexity&f=false] и и количества операций для переортогонализации методом грамма-Шмидта[http://stackoverflow.com/questions/27986225/computational-complexity-of-gram-schmidt-orthogonalization-algorithm].

Итоговая сложность составляет <math>O(n^2)+O(nk^2) </math>.

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

[[Файл:Graph.jpg]]

== Входные и выходные данные==
На вход принимается сама матрица <math> A \in R^{n \times n}</math>, случайный вектор <math>b</math> (впрочем возможен вариант, при котором этот вектор генерируется случайным образом).
Ввиду симметричности входной матрицы достаточно передать лишь ее верхнюю треугольную матрицу, что дает объем входных данных <math>\frac{n(n + 1)}{2}</math>.

Выходными данными для <math>j</math>ой итерации являются вектор <math> Aq_j </math> и собственное число <math> \lambda </math>. Общий объем выходных данных <math>k(n+1)</math>.

==Свойства алгоритма==
Если <math>A</math> эрмитова матрица, то алгоритм Ланцоша и Bi-Lanczos сходятся к одинаковым трехдиагональным матрицам ритца[http://ta.twi.tudelft.nl/nw/users/vuik/papers/DUT-TWI-96-44.pdf].

При реализации классического алгоритма Ланцоша возникает большая погрешность при округлении. Вариант с полной переортогонализацией позволяет избегать больших погрешностей, однако является более ресурсоемким. Существует промежуточный вариант с частичной переортогонализацией.

Алгоритм может завершить свою работу досрочно, когда найденные собственные значения будут достаточно близки к целевым.

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

Хотя алгоритм является итерационным, возможно распараллелить внутри каждой итерации умножение матрицы на вектор и процесс переортогонализации Грамма-Шмидта.

Процесс умножения матриц matvec можно распараллелить несколькими способами[https://eprint.iacr.org/2011/416.pdf].

== Библиотеки реализующие алгоритм==

The IETL Project http://www.comp-phys.org/software/ietl/ C++

NAG Library http://www.nag.com/content/nag-library C, C++, Fortran, C#, MATLAB, R

ARPACK https://people.sc.fsu.edu/~jburkardt/m_src/arpack/arpack.html MATLAB

GrapLab https://turi.com/products/create/open_source.html C++

С частичной переортаганализацией

LANSO/PLANSO http://web.cs.ucdavis.edu/~bai/ET/lanczos_methods/overview_PLANSO.html Fortran (уже распараллелена)

== Литература ==

Ojalvo, I.U. and Newman, M., "Vibration modes of large structures by an automatic matrix-reduction method", AIAA J., 8 (7), 1234–1239 (1970).

Участник:Nikita270a

2016-10-16T23:43:40Z

Nikita270a:

{{algorithm
| name = Алгоритм Ланцоша с полной переортогонализацией
| serial_complexity = <math>O(n^2)</math>
| pf_height = <math>O(k)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>\frac{n(n + 1)}{2}</math>
| output_data = <math>k(n + 1)</math>
}}

Авторы: Алексейчук Н.Н 616, Ястребов К.С. 609.

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

Алгоритм Ланцоша ищет собвственные значения и собственные векторы для симетричной матрицы A вещественных чисел. Является итерацонным алгоритмом. Алгоритм Ланцоша использует степенной метод (<math> b_{k+1} = \frac{Ab_k}{||Ab_k||} </math>) для поиска наибольших собственных значений и векторов матриц.

В отличие от прямых алгоритмов требует мешьше памяти и мощности, что является несомненным плюсом для больших матриц.

Несмотря на свою скорость работы и экономию памяти, сначала не был популярным алгоритмом из – за недостаточной вычислительной устойчивости. В 1970 году Ojalvo и Newman показали способ сделать алгоритм достаточно устойчивым. В этой же статье алгоритм был применен к расчету инженерной конструкции с большим количеством узлов, которые подвергались динамической нагрузке.

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

Памятка:
Степенной метод нахождения наибольшего собственного числа матрицы можно сформулировать в предельном виде: если <math> b_0 </math> – случайный вектор, и <math> b_n+1 = Ab_n </math>, тогда для больших чисел n предел <math>x_n/||x_n|| </math> стремится к нормированному наибольшему собственному вектору.

Алгоритм Ланцоша комбинирует метод Ланцоша для нахождения крыловского подпространства и метод Релэя – Ритца.

Подпространство Крылова для степенного метода:
<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>

В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>.

Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца.

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

Вычислительным ядром данного алгоритма являются следующие шаги:
*1. <math>Aq=( \sum\nolimits_{i=^n}a_{1i}q_i, \sum\nolimits_{i=2}^na_{2i}q_i, ..., \sum\nolimits_{i=1}^na_{ni}q_i)</math>.

*2. <math>z=z-\sum\nolimits_{i=1}^{k}(z^Tq_i)q_i.</math>

В данном случае первая операция выполняет умножение симметричной матрицы <math>A</math> размерности <math>n</math>X<math>n</math> на <math>n</math>-мерный вектор <math>q</math>, вследствие чего вычислительная сложность выполнения заключается в <math>n^2</math> умножений и <math>n^2-n</math> сложений. Второе действие является процессом ортогонализации Грама-Шмидта. В последнем действии вычисляются <math>k^2n+k(n+2)</math> умножений и <math>k^2n + k(n + 1) + 2</math> операций сложения.

== Схема ==
Input: A, b (random vector with unit norm)
: <math>

\begin{align}
q_1 = b/||b||_2, \beta_0 = 0, q_0 = 0 \\
j = 1 ,...,k \\
q_1&=b/||b||,\beta_0=0,q_o=0. \\
z&=Aq_j, \\
\alpha_j&=q_j^Tz, \\
z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\
\beta&=||z||,\\
q_{j+1}&=z/\beta_j, \quad j \in [1, k].

\end{align}

</math>

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

[[Файл:Graph.jpg]]

== Библиотеки реализующие алгоритм==

The IETL Project http://www.comp-phys.org/software/ietl/ C++

NAG Library http://www.nag.com/content/nag-library C, C++, Fortran, C#, MATLAB, R

ARPACK https://people.sc.fsu.edu/~jburkardt/m_src/arpack/arpack.html MATLAB

GrapLab https://turi.com/products/create/open_source.html C++

С частично переортаганализацией

LANSO/PLANSO http://web.cs.ucdavis.edu/~bai/ET/lanczos_methods/overview_PLANSO.html Fortran (уже распараллелена)

Участник:Nikita270a

2016-10-16T21:20:22Z

Nikita270a:

{{algorithm
| name = Алгоритм Ланцоша с полной переортогонализацией
| serial_complexity = <math>O(n^2)</math>
| pf_height = <math>O(k)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>\frac{n(n + 1)}{2}</math>
| output_data = <math>k(n + 1)</math>
}}

Авторы: Алексейчук Н.Н 616, Ястребов К.С. 609.

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

Алгоритм Ланцоша ищет собвственные значения и собственные векторы для симетричной матрицы A вещественных чисел. Является итерацонным алгоритмом. Алгоритм Ланцоша использует степенной метод (<math> b_{k+1} = \frac{Ab_k}{||Ab_k||} </math>) для поиска наибольших собственных значений и векторов матриц.

В отличие от прямых алгоритмов требует мешьше памяти и мощности, что является несомненным плюсом для больших матриц.

Несмотря на свою скорость работы и экономию памяти, сначала не был популярным алгоритмом из – за недостаточной вычислительной устойчивости. В 1970 году Ojalvo и Newman показали способ сделать алгоритм достаточно устойчивым. В этой же статье алгоритм был применен к расчету инженерной конструкции с большим количеством узлов, которые подвергались динамической нагрузке.

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

Памятка:
Степенной метод нахождения наибольшего собственного числа матрицы можно сформулировать в предельном виде: если <math> b_0 </math> – случайный вектор, и <math> b_n+1 = Ab_n </math>, тогда для больших чисел n предел <math>x_n/||x_n|| </math> стремится к нормированному наибольшему собственному вектору.

Алгоритм Ланцоша комбинирует метод Ланцоша для нахождения крыловского подпространства и метод Релэя – Ритца.

Подпространство Крылова для степенного метода:
<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>

В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>.

Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца.

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

Вычислительным ядром данного алгоритма являются следующие шаги:
*1. <math>Aq=( \sum\nolimits_{i=^n}a_{1i}q_i, \sum\nolimits_{i=2}^na_{2i}q_i, ..., \sum\nolimits_{i=1}^na_{ni}q_i)</math>.

*2. <math>z=z-\sum\nolimits_{i=1}^{k}(z^Tq_i)q_i.</math>

В данном случае первая операция выполняет умножение симметричной матрицы <math>A</math> размерности <math>n</math>X<math>n</math> на <math>n</math>-мерный вектор <math>q</math>, вследствие чего вычислительная сложность выполнения заключается в <math>n^2</math> умножений и <math>n^2-n</math> сложений. Второе действие является процессом ортогонализации Грама-Шмидта. В последнем действии вычисляются <math>k^2n+k(n+2)</math> умножений и <math>k^2n + k(n + 1) + 2</math> операций сложения.

== Схема ==
Input: A, b (random vector with unit norm)
: <math>

\begin{align}
q_1 = b/||b||_2, \beta_0 = 0, q_0 = 0 \\
for j = 1 ,...,k \\
q_1&=b/||b||,\beta_0=0,q_o=0. \\
z&=Aq_j, \\
\alpha_j&=q_j^Tz, \\
z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\
\beta&=||z||,\\
q_{j+1}&=z/\beta_j, \quad j \in [1, k].

\end{align}

</math>

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

[[Файл:Graph.jpg]]

== Библиотеки реализующие алгоритм==

The IETL Project http://www.comp-phys.org/software/ietl/ C++

NAG Library http://www.nag.com/content/nag-library C, C++, Fortran, C#, MATLAB, R

ARPACK https://people.sc.fsu.edu/~jburkardt/m_src/arpack/arpack.html MATLAB

GrapLab https://turi.com/products/create/open_source.html C++

С частично переортаганализацией

LANSO/PLANSO http://web.cs.ucdavis.edu/~bai/ET/lanczos_methods/overview_PLANSO.html Fortran (уже распараллелена)

Файл:Graph lanczos.jpg

2016-10-15T21:05:25Z

Nikita270a:

Участник:Nikita270a

2016-10-15T21:04:32Z

Nikita270a:

{{algorithm
| name = Алгоритм Ланцоша с полной переортогонализацией
| serial_complexity = <math>O(n^2)</math>
| pf_height = <math>O(k)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>\frac{n(n + 1)}{2}</math>
| output_data = <math>k(n + 1)</math>
}}

Авторы: Ялексейчук Н.Н 616, Ястребов К.С. 609.

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

Алгоритм Ланцоша ищет собвственные значения и собственные векторы для симетричной матрицы A вещественных чисел. Является итерацонным алгоритмом. Алгоритм Ланцоша использует степенной метод (<math> b_{k+1} = \frac{Ab_k}{||Ab_k||} </math>) для поиска наибольших собственных значений и векторов матриц.

В отличие от прямых алгоритмов требует мешьше памяти и мощности, что является несомненным плюсом для больших матриц.

Несмотря на свою скорость работы и экономию памяти, сначала не был популярным алгоритмом из – за недостаточной вычислительной устойчивости. В 1970 году Ojalvo и Newman показали способ сделать алгоритм достаточно устойчивым. В этой же статье алгоритм был применен к расчету инженерной конструкции с большим количеством узлов, которые подвергались динамической нагрузке.

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

Памятка:
Степенной метод нахождения наибольшего собственного числа матрицы можно сформулировать в предельном виде: если <math> b_0 </math> – случайный вектор, и <math> b_n+1 = Ab_n </math>, тогда для больших чисел n предел <math>x_n/||x_n|| </math> стремится к нормированному наибольшему собственному вектору.

Алгоритм Ланцоша комбинирует метод Ланцоша для нахождения крыловского подпространства и метод Релэя – Ритца.

Подпространство Крылова для степенного метода:
<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>

В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>. Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца. Пусть <math>T_k=VAV^T</math> есть спектральное разложение матрицы <math>T_k</math>, столбцы матрицы <math>Q_kV</math> рассматриваются как приближения к соответсвующим собственным векторам матрицы <math>A</math><ref>Дж. Деммель «Вычислительная линейная алгебра» (стр. 391)</ref>:

== Схема ==
Input: A, b (random vector with unit norm)
: <math>

\begin{align}
q_1 = b/||b||_2, \beta_0 = 0, q_0 = 0 \\
for j = 1 ,...,k \\
q_1&=b/||b||,\beta_0=0,q_o=0. \\
z&=Aq_j, \\
\alpha_j&=q_j^Tz, \\
z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\
\beta&=||z||,\\
q_{j+1}&=z/\beta_j, \quad j \in [1, k].

\end{align}

</math>

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

== Библиотеки реализующие алгоритм==

The IETL Project http://www.comp-phys.org/software/ietl/ C++

NAG Library http://www.nag.com/content/nag-library C, C++, Fortran, C#, MATLAB, R

ARPACK https://people.sc.fsu.edu/~jburkardt/m_src/arpack/arpack.html MATLAB

GrapLab https://turi.com/products/create/open_source.html C++

С частично переортаганализацией

LANSO/PLANSO http://web.cs.ucdavis.edu/~bai/ET/lanczos_methods/overview_PLANSO.html Fortran (уже распараллелена)

Участник:Nikita270a

2016-10-15T21:01:32Z

Nikita270a:

{{algorithm
| name = Алгоритм Ланцоша с полной переортогонализацией
| serial_complexity = <math>O(n^2)</math>
| pf_height = <math>O(k)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>\frac{n(n + 1)}{2}</math>
| output_data = <math>k(n + 1)</math>
}}

Авторы: Ялексейчук Н.Н 616, Ястребов К.С. 609.

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

Алгоритм Ланцоша ищет собвственные значения и собственные векторы для симетричной матрицы A вещественных чисел. Является итерацонным алгоритмом. Алгоритм Ланцоша использует степенной метод (<math> b_{k+1} = \frac{Ab_k}{||Ab_k||} </math>) для поиска наибольших собственных значений и векторов матриц.

В отличие от прямых алгоритмов требует мешьше памяти и мощности, что является несомненным плюсом для больших матриц.

Несмотря на свою скорость работы и экономию памяти, сначала не был популярным алгоритмом из – за недостаточной вычислительной устойчивости. В 1970 году Ojalvo и Newman показали способ сделать алгоритм достаточно устойчивым. В этой же статье алгоритм был применен к расчету инженерной конструкции с большим количеством узлов, которые подвергались динамической нагрузке.

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

Памятка:
Степенной метод нахождения наибольшего собственного числа матрицы можно сформулировать в предельном виде: если <math> b_0 </math> – случайный вектор, и <math> b_n+1 = Ab_n </math>, тогда для больших чисел n предел <math>x_n/||x_n|| </math> стремится к нормированному наибольшему собственному вектору.

Алгоритм Ланцоша комбинирует метод Ланцоша для нахождения крыловского подпространства и метод Релэя – Ритца.

Подпространство Крылова для степенного метода:
<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>

В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>. Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца. Пусть <math>Tk=VAVT</math> есть спектральное разложение матрицы <math>T_k</math>, столбцы матрицы <math>Q_kV</math> рассматриваются как приближения к соответсвующим собственным векторам матрицы <math>A</math><ref>Дж. Деммель «Вычислительная линейная алгебра» (стр. 391)</ref>:

== Схема ==
Input: A, b (random vector with unit norm)
: <math>

\begin{align}
q_1 = b/||b||_2, \beta_0 = 0, q_0 = 0 \\
for j = 1 ,...,k \\
q_1&=b/||b||,\beta_0=0,q_o=0. \\
z&=Aq_j, \\
\alpha_j&=q_j^Tz, \\
z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\
\beta&=||z||,\\
q_{j+1}&=z/\beta_j, \quad j \in [1, k].

\end{align}

</math>

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

== Библиотеки реализующие алгоритм==

The IETL Project http://www.comp-phys.org/software/ietl/ C++

NAG Library http://www.nag.com/content/nag-library C, C++, Fortran, C#, MATLAB, R

ARPACK https://people.sc.fsu.edu/~jburkardt/m_src/arpack/arpack.html MATLAB

GrapLab https://turi.com/products/create/open_source.html C++

С частично переортаганализацией

LANSO/PLANSO http://web.cs.ucdavis.edu/~bai/ET/lanczos_methods/overview_PLANSO.html Fortran (уже распараллелена)

Участник:Nikita270a

2016-10-15T21:00:31Z

Nikita270a: Новая страница: «{{algorithm | name = Алгоритм Ланцоша с полной переортогонализацией | serial_complexity = <math>O(n^2)</mat…»

{{algorithm
| name = Алгоритм Ланцоша с полной переортогонализацией
| serial_complexity = <math>O(n^2)</math>
| pf_height = <math>O(k)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>\frac{n(n + 1)}{2}</math>
| output_data = <math>k(n + 1)</math>
}}

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

Алгоритм Ланцоша ищет собвственные значения и собственные векторы для симетричной матрицы A вещественных чисел. Является итерацонным алгоритмом. Алгоритм Ланцоша использует степенной метод (<math> b_{k+1} = \frac{Ab_k}{||Ab_k||} </math>) для поиска наибольших собственных значений и векторов матриц.

В отличие от прямых алгоритмов требует мешьше памяти и мощности, что является несомненным плюсом для больших матриц.

Несмотря на свою скорость работы и экономию памяти, сначала не был популярным алгоритмом из – за недостаточной вычислительной устойчивости. В 1970 году Ojalvo и Newman показали способ сделать алгоритм достаточно устойчивым. В этой же статье алгоритм был применен к расчету инженерной конструкции с большим количеством узлов, которые подвергались динамической нагрузке.

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

Памятка:
Степенной метод нахождения наибольшего собственного числа матрицы можно сформулировать в предельном виде: если <math> b_0 </math> – случайный вектор, и <math> b_n+1 = Ab_n </math>, тогда для больших чисел n предел <math>x_n/||x_n|| </math> стремится к нормированному наибольшему собственному вектору.

Алгоритм Ланцоша комбинирует метод Ланцоша для нахождения крыловского подпространства и метод Релэя – Ритца.

Подпространство Крылова для степенного метода:
<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>

В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>. Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца. Пусть <math>Tk=VAVT</math> есть спектральное разложение матрицы <math>T_k</math>, столбцы матрицы <math>Q_kV</math> рассматриваются как приближения к соответсвующим собственным векторам матрицы <math>A</math><ref>Дж. Деммель «Вычислительная линейная алгебра» (стр. 391)</ref>:

== Схема ==
Input: A, b (random vector with unit norm)
: <math>

\begin{align}
q_1 = b/||b||_2, \beta_0 = 0, q_0 = 0 \\
for j = 1 ,...,k \\
q_1&=b/||b||,\beta_0=0,q_o=0. \\
z&=Aq_j, \\
\alpha_j&=q_j^Tz, \\
z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\
\beta&=||z||,\\
q_{j+1}&=z/\beta_j, \quad j \in [1, k].

\end{align}

</math>

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

== Библиотеки реализующие алгоритм==

The IETL Project http://www.comp-phys.org/software/ietl/ C++

NAG Library http://www.nag.com/content/nag-library C, C++, Fortran, C#, MATLAB, R

ARPACK https://people.sc.fsu.edu/~jburkardt/m_src/arpack/arpack.html MATLAB

GrapLab https://turi.com/products/create/open_source.html C++

С частично переортаганализацией

LANSO/PLANSO http://web.cs.ucdavis.edu/~bai/ET/lanczos_methods/overview_PLANSO.html Fortran (уже распараллелена)

Открытая энциклопедия свойств алгоритмов

2016-10-15T20:57:20Z

Nikita270a:

{{algorithm
| name = Алгоритм Ланцоша с полной переортогонализацией
| serial_complexity = <math>O(n^2)</math>
| pf_height = <math>O(k)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>\frac{n(n + 1)}{2}</math>
| output_data = <math>k(n + 1)</math>
}}

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

Алгоритм Ланцоша ищет собвственные значения и собственные векторы для симетричной матрицы A вещественных чисел. Является итерацонным алгоритмом. Алгоритм Ланцоша использует степенной метод (<math> b_{k+1} = \frac{Ab_k}{||Ab_k||} </math>) для поиска наибольших собственных значений и векторов матриц.

В отличие от прямых алгоритмов требует мешьше памяти и мощности, что является несомненным плюсом для больших матриц.

Несмотря на свою скорость работы и экономию памяти, сначала не был популярным алгоритмом из – за недостаточной вычислительной устойчивости. В 1970 году Ojalvo и Newman показали способ сделать алгоритм достаточно устойчивым. В этой же статье алгоритм был применен к расчету инженерной конструкции с большим количеством узлов, которые подвергались динамической нагрузке.

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

Памятка:
Степенной метод нахождения наибольшего собственного числа матрицы можно сформулировать в предельном виде: если <math> b_0 </math> – случайный вектор, и <math> b_n+1 = Ab_n </math>, тогда для больших чисел n предел <math>x_n/||x_n|| </math> стремится к нормированному наибольшему собственному вектору.

Алгоритм Ланцоша комбинирует метод Ланцоша для нахождения крыловского подпространства и метод Релэя – Ритца.

Подпространство Крылова для степенного метода:
<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>

В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>. Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца. Пусть <math>Tk=VAVT</math> есть спектральное разложение матрицы <math>T_k</math>, столбцы матрицы <math>Q_kV</math> рассматриваются как приближения к соответсвующим собственным векторам матрицы <math>A</math><ref>Дж. Деммель «Вычислительная линейная алгебра» (стр. 391)</ref>:

== Схема ==
Input: A, b (random vector with unit norm)
: <math>

\begin{align}
q_1 = b/||b||_2, \beta_0 = 0, q_0 = 0 \\
for j = 1 ,...,k \\
q_1&=b/||b||,\beta_0=0,q_o=0. \\
z&=Aq_j, \\
\alpha_j&=q_j^Tz, \\
z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\
\beta&=||z||,\\
q_{j+1}&=z/\beta_j, \quad j \in [1, k].

\end{align}

</math>

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

== Библиотеки реализующие алгоритм==

The IETL Project http://www.comp-phys.org/software/ietl/ C++

NAG Library http://www.nag.com/content/nag-library C, C++, Fortran, C#, MATLAB, R

ARPACK https://people.sc.fsu.edu/~jburkardt/m_src/arpack/arpack.html MATLAB

GrapLab https://turi.com/products/create/open_source.html C++

С частично переортаганализацией

LANSO/PLANSO http://web.cs.ucdavis.edu/~bai/ET/lanczos_methods/overview_PLANSO.html Fortran (уже распараллелена)