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

Участник:MukhayevD/Метод Ньютона

2016-11-30T16:13:54Z

MukhayevD:

{{assignment}}
Автор: [[Участник:MukhayevD|Мухаев Д.Н.]]

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

=== Общее описание алгоритма ===
'''Метод Ньютона''', '''алгоритм Ньютона''' (также известный как '''метод касательных''') — это итерационный численный метод нахождения корня заданной функции(в связи с трудностями программирования производной для произвольной функции рассматриваются только функции в виде полинома). Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных.

=== Математическое описание алгоритма ===
Пусть <math> x_n </math> - некоторое приближение к корню уравнения <math> f(x) = 0, f \in C^1 </math>, то следующее приближение определяется как корень касательной к функции <math> f(x) </math>, проведенной в точке <math> x_n </math>.

Уравнение касательной к функции <math> f(x) </math> в точке <math> x_n </math> имеет вид:
<math> f^'(x_n) = (y - f(x_n))/(x - x_n) </math>
В уравнении касательной положим <math> y = 0 </math> и <math> x = x_{n+1} </math>.
Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:
<math> x_{n+1} = x_n - f(x_n)/f^'(x_n) </math>
Сходимость метода касательных квадратичная, порядок сходимости равен 2.

=== Вычислительное ядро алгоритма ===
Основная вычислительная нагрузка алгоритма заключается в нахождении <math> \varphi(x_n) = f(x_n)/f^'(x_n) </math>, которая в последствии используется для нахождения <math> x_{n+1} = x_n - \varphi(x_n) </math>

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

Как и было описано в описании ядра алгоритма, основную часть метода составляет вычисление значения функции <math> f(x_n) </math> и ее производной <math> f^'(x_n) </math> в точке x_n.

<math> f(x_n) = \sum_{i=0}^{n}f_ix_n^i </math>

<math> f^'(x_n) = \sum_{i=0}^{n-1}f^'_ix_n^i </math>

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

Последовательность исполнения метода следующая:

1. Выбираем начальное приближение <math> x_0 </math>
2. Находим значение функции <math> f(x_n) </math> в точке <math>x_n</math>.
3. Находим значение производной функции <math> f^'(x_n) </math> в точке <math>x_n</math>.
4. Получаем следующий шаг итерации <math> x_{n+1} </math><math> x_{n+1} = x_n - f(x_n)/f^'(x+n) </math>
5. Находим погрешность <math> e = |x_{n+1} - x_n| </math>
6. Если погрешность не превышает некоторого заранее заданного числа - останавливаемся.

<math> e < \varepsilon </math>

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

Для вычисления корня методом Ньютона при последовательном выполнении требуется:

* <math> n </math> сложение + <math> n </math> умножений + <math> n-1 </math> умножений (возведение в степень)

* <math> n-1 </math> сложение + <math> n-1 </math> умножений + <math> n-2 </math> умножений (возведение в степень)

* одно вычитание и одно деление

* одно вычитание

Следовательно для одного шага алгоритма требуется:
* <math> 2n-1 </math> сложение (вычитание)
* <math> 4n-3 </math> умножений (делений)

=== Информационный граф ===
На рисунке ниже изображена структура информационного графа алгоритма. Блок IN представляет собой выбор начального приближения, блок IT - итерацию алгоритма, блок OUT - концу работы алгоритма.

[[Файл:MNP1.PNG|center|frame|Рисунок 1. Информационный граф]]

Как видно, алгоритм строго последовательный.
Ниже подробнее рассмотрено как можно разделить нагрузку связанную с вычислениями <math> f(x) </math> между процессорами. Каждое слагаемое полинома считается отдельно.

[[Файл:MNP2.PNG|center|frame|Рисунок 2. Итерация]]

Аналогично для <math> f^'(x) </math>.

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

Несмотря на то, что сам по себе алгоритм является строго последовательным, его можно ускорить за счет распараллеливания нахождения функции и ее производной на текущей итерации, так как это было описано в предыдущем пункте.

Пусть имеем <math> p </math> процессоров, в таком случае каждому процессору нужно будет произвести <math> (4n-3)/p </math> умножений.

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

Входными данными алгоритма являются:

1. Функция в виде полинома.
2. Область, в которой ищется корень <math> (a;b) </math>.
3. Начальное приближение <math> x_0 </math>.
4. Точность, с которой требуется найти решение.

На выход алгоритмом выдается число - предположительный корень найденный с заданной точностью.

== Программная реализация алгоритма ==

===2.4 Масштабируемость алгоритма и его реализации ===
Так как сам по себе метод является последовательным то, следовательно о его масштабируемости не может быть и речи.

Поверка масштабируемости реализации метода проводилась на следующих тестах:

* 1) <math> (x-1)g(x) </math>, где <math> g(x) </math> - произвольный полином степени <math> n-1 </math>.

[[Файл:MNP4.png|center|frame|Рисунок 1.]]

* 2) <math> 1 + 2x + 2x^2 + ... + 2x^{n-1} + x^n </math>

[[Файл:MNP3.png|center|frame|Рисунок 2.]]

Как видно из рисунков вне зависимости от размерности задачи не удалось добиться времени больше <math> 0.1 </math> секунды, в виду этого можно предположить, что время зависит от физического расположения процессоров, но тем не менее есть общая тенденция, что время работы возрастает вместе с размерностью и количеством процессоров.

=== 2.7 Существующие реализации алгоритма ===

1. Последовательные реализации

**ALIAS C++. Язык реализации - C++. Распространяется бесплатно, исходные коды и примеры использования можно скачать на сайте<ref name="ALIAS">https://www-sop.inria.fr/coprin/logiciels/ALIAS/ALIAS-C++/ALIAS-C++.html</ref>.
**Numerical Recipes. Язык реализации - C++. Исходный код можно найти в секции 9.7 книги Numerical recipes(third edition)<ref name="RECIPES">http://numerical.recipes</ref>. Бесплатно доступны<ref name="RECIPES_old">http://numerical.recipes/oldverswitcher.html</ref> предыдущие издания для языков C, Fortran77, Fortran90.
**Sundials. Язык реализации - C, также есть интерфейс для использования в Fortran-программах. Распространяется<ref name="SUNDIALS_seq">http://computation.llnl.gov/projects/sundials/kinsol</ref> по лицензии BSD.

2. Параллельные реализации
**Построение параллельной реализации метода Ньютона для решения задач линейного программирования описано в работе В.А. Гаранжа, А.И. Голикова, Ю.Г. Евтушенко, М.Х. Нгуена "Параллельная реализации метода Ньютона для решения больших задач линейного программирования" <ref name="CCAS">http://www.ccas.ru/personal/evtush/p/paper1.pdf</ref>.
**Построение параллельной реализации метода Ньютона для решения задач оптимизации, описываются в работе V. A. Garanzha, A. I. Golikov, Yu. G. Evtushenko, and M. Kh. Nguen "Parallel Implementation of Newton’s Method for Solving Large-Scale Linear Programs" <ref name="IMPL_OPT">http://www.ccas.ru/personal/evtush/p/CMMP1303.pdf</ref>.
**Построение параллельной реализации метода Ньютона, а также результаты некоторых экспериментов, описываются в работе Renato N. Elias Alvaro L. G. A. Coutinho Marcos A. D. Martins Rubens M. Sydenstricker "PARALLEL INEXACT NEWTON-TYPE METHODS FOR THE SUPG/PSPG SOLUTION OF STEADY INCOMPRESSIBLE 3D NAVIER-STOKES EQUATIONS IN PC CLUSTERS" <ref name="SUPG">http://www.nacad.ufrj.br/~rnelias/papers/CIL14-020.pdf</ref>.
**Описание использования и результатов экспериментов с параллельной реализацией метода Ньютона в задаче фильтрации вязкой сжимаемой многофазной многокомпонентной смеси в пористой среде описано в работе К.Ю.Богачева "Эффективное решение задачи фильтрации вязкой сжимаемой многофазной многокомпонентной смеси на параллельных ЭВМ"<ref name="BOGACHEV">http://academy.hpc-russia.ru/files/reservoirdynamics_bogachev.pdf</ref>.

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

<references \>

Участник:MukhayevD/Метод Ньютона

2016-11-25T16:38:13Z

MukhayevD: /* Существующие реализации алгоритма */

Автор: [[Участник:MukhayevD|Мухаев Д.Н.]]

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

=== Общее описание алгоритма ===
'''Метод Ньютона''', '''алгоритм Ньютона''' (также известный как '''метод касательных''') — это итерационный численный метод нахождения корня заданной функции(в связи с трудностями программирования производной для произвольной функции рассматриваются только функции в виде полинома). Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных.

=== Математическое описание алгоритма ===
Пусть <math> x_n </math> - некоторое приближение к корню уравнения <math> f(x) = 0, f \in C^1 </math>, то следующее приближение определяется как корень касательной к функции <math> f(x) </math>, проведенной в точке <math> x_n </math>.

Уравнение касательной к функции <math> f(x) </math> в точке <math> x_n </math> имеет вид:
<math> f^'(x_n) = (y - f(x_n))/(x - x_n) </math>
В уравнении касательной положим <math> y = 0 </math> и <math> x = x_{n+1} </math>.
Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:
<math> x_{n+1} = x_n - f(x_n)/f^'(x_n) </math>
Сходимость метода касательных квадратичная, порядок сходимости равен 2.

=== Вычислительное ядро алгоритма ===
Основная вычислительная нагрузка алгоритма заключается в нахождении <math> \varphi(x_n) = f(x_n)/f^'(x_n) </math>, которая в последствии используется для нахождения <math> x_{n+1} = x_n - \varphi(x_n) </math>

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

Как и было описано в описании ядра алгоритма, основную часть метода составляет вычисление значения функции <math> f(x_n) </math> и ее производной <math> f^'(x_n) </math> в точке x_n.

<math> f(x_n) = \sum_{i=0}^{n}f_ix_n^i </math>

<math> f^'(x_n) = \sum_{i=0}^{n-1}f^'_ix_n^i </math>

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

Последовательность исполнения метода следующая:

1. Выбираем начальное приближение <math> x_0 </math>
2. Находим значение функции <math> f(x_n) </math> в точке <math>x_n</math>.
3. Находим значение производной функции <math> f^'(x_n) </math> в точке <math>x_n</math>.
4. Получаем следующий шаг итерации <math> x_{n+1} </math><math> x_{n+1} = x_n - f(x_n)/f^'(x+n) </math>
5. Находим погрешность <math> e = |x_{n+1} - x_n| </math>
6. Если погрешность не превышает некоторого заранее заданного числа - останавливаемся.

<math> e < \varepsilon </math>

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

Для вычисления корня методом Ньютона при последовательном выполнении требуется:

* <math> n </math> сложение + <math> n </math> умножений + <math> n-1 </math> умножений (возведение в степень)

* <math> n-1 </math> сложение + <math> n-1 </math> умножений + <math> n-2 </math> умножений (возведение в степень)

* одно вычитание и одно деление

* одно вычитание

Следовательно для одного шага алгоритма требуется:
* <math> 2n-1 </math> сложение (вычитание)
* <math> 4n-3 </math> умножений (делений)

=== Информационный граф ===
На рисунке ниже изображена структура информационного графа алгоритма. Блок IN представляет собой выбор начального приближения, блок IT - итерацию алгоритма, блок OUT - концу работы алгоритма.

[[Файл:MNP1.PNG|center|frame|Рисунок 1. Информационный граф]]

Как видно, алгоритм строго последовательный.
Ниже подробнее рассмотрено как можно разделить нагрузку связанную с вычислениями <math> f(x) </math> между процессорами. Каждое слагаемое полинома считается отдельно.

[[Файл:MNP2.PNG|center|frame|Рисунок 2. Итерация]]

Аналогично для <math> f^'(x) </math>.

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

Несмотря на то, что сам по себе алгоритм является строго последовательным, его можно ускорить за счет распараллеливания нахождения функции и ее производной на текущей итерации, так как это было описано в предыдущем пункте.

Пусть имеем <math> p </math> процессоров, в таком случае каждому процессору нужно будет произвести <math> (4n-3)/p </math> умножений.

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

Входными данными алгоритма являются:

1. Функция в виде полинома.
2. Область, в которой ищется корень <math> (a;b) </math>.
3. Начальное приближение <math> x_0 </math>.
4. Точность, с которой требуется найти решение.

На выход алгоритмом выдается число - предположительный корень найденный с заданной точностью.

== Программная реализация алгоритма ==

===2.4 Масштабируемость алгоритма и его реализации ===
Так как сам по себе метод является последовательным то, следовательно о его масштабируемости не может быть и речи.

Поверка масштабируемости реализации метода проводилась на следующих тестах:

* 1) <math> (x-1)g(x) </math>, где <math> g(x) </math> - произвольный полином степени <math> n-1 </math>.

[[Файл:MNP4.png|center|frame|Рисунок 1.]]

* 2) <math> 1 + 2x + 2x^2 + ... + 2x^{n-1} + x^n </math>

[[Файл:MNP3.png|center|frame|Рисунок 2.]]

Как видно из рисунков вне зависимости от размерности задачи не удалось добиться времени больше <math> 0.1 </math> секунды, в виду этого можно предположить, что время зависит от физического расположения процессоров, но тем не менее есть общая тенденция, что время работы возрастает вместе с размерностью и количеством процессоров.

=== 2.7 Существующие реализации алгоритма ===

1. Последовательные реализации

**ALIAS C++. Язык реализации - C++. Распространяется бесплатно, исходные коды и примеры использования можно скачать на сайте<ref name="ALIAS">https://www-sop.inria.fr/coprin/logiciels/ALIAS/ALIAS-C++/ALIAS-C++.html</ref>.
**Numerical Recipes. Язык реализации - C++. Исходный код можно найти в секции 9.7 книги Numerical recipes(third edition)<ref name="RECIPES">http://numerical.recipes</ref>. Бесплатно доступны<ref name="RECIPES_old">http://numerical.recipes/oldverswitcher.html</ref> предыдущие издания для языков C, Fortran77, Fortran90.
**Sundials. Язык реализации - C, также есть интерфейс для использования в Fortran-программах. Распространяется<ref name="SUNDIALS_seq">http://computation.llnl.gov/projects/sundials/kinsol</ref> по лицензии BSD.

2. Параллельные реализации
**Построение параллельной реализации метода Ньютона для решения задач линейного программирования описано в работе В.А. Гаранжа, А.И. Голикова, Ю.Г. Евтушенко, М.Х. Нгуена "Параллельная реализации метода Ньютона для решения больших задач линейного программирования" <ref name="CCAS">http://www.ccas.ru/personal/evtush/p/paper1.pdf</ref>.
**Построение параллельной реализации метода Ньютона для решения задач оптимизации, описываются в работе V. A. Garanzha, A. I. Golikov, Yu. G. Evtushenko, and M. Kh. Nguen "Parallel Implementation of Newton’s Method for Solving Large-Scale Linear Programs" <ref name="IMPL_OPT">http://www.ccas.ru/personal/evtush/p/CMMP1303.pdf</ref>.
**Построение параллельной реализации метода Ньютона, а также результаты некоторых экспериментов, описываются в работе Renato N. Elias Alvaro L. G. A. Coutinho Marcos A. D. Martins Rubens M. Sydenstricker "PARALLEL INEXACT NEWTON-TYPE METHODS FOR THE SUPG/PSPG SOLUTION OF STEADY INCOMPRESSIBLE 3D NAVIER-STOKES EQUATIONS IN PC CLUSTERS" <ref name="SUPG">http://www.nacad.ufrj.br/~rnelias/papers/CIL14-020.pdf</ref>.
**Описание использования и результатов экспериментов с параллельной реализацией метода Ньютона в задаче фильтрации вязкой сжимаемой многофазной многокомпонентной смеси в пористой среде описано в работе К.Ю.Богачева "Эффективное решение задачи фильтрации вязкой сжимаемой многофазной многокомпонентной смеси на параллельных ЭВМ"<ref name="BOGACHEV">http://academy.hpc-russia.ru/files/reservoirdynamics_bogachev.pdf</ref>.

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

<references \>

Участник:MukhayevD/Метод Ньютона

2016-11-25T16:37:54Z

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

Автор: [[Участник:MukhayevD|Мухаев Д.Н.]]

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

=== Общее описание алгоритма ===
'''Метод Ньютона''', '''алгоритм Ньютона''' (также известный как '''метод касательных''') — это итерационный численный метод нахождения корня заданной функции(в связи с трудностями программирования производной для произвольной функции рассматриваются только функции в виде полинома). Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных.

=== Математическое описание алгоритма ===
Пусть <math> x_n </math> - некоторое приближение к корню уравнения <math> f(x) = 0, f \in C^1 </math>, то следующее приближение определяется как корень касательной к функции <math> f(x) </math>, проведенной в точке <math> x_n </math>.

Уравнение касательной к функции <math> f(x) </math> в точке <math> x_n </math> имеет вид:
<math> f^'(x_n) = (y - f(x_n))/(x - x_n) </math>
В уравнении касательной положим <math> y = 0 </math> и <math> x = x_{n+1} </math>.
Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:
<math> x_{n+1} = x_n - f(x_n)/f^'(x_n) </math>
Сходимость метода касательных квадратичная, порядок сходимости равен 2.

=== Вычислительное ядро алгоритма ===
Основная вычислительная нагрузка алгоритма заключается в нахождении <math> \varphi(x_n) = f(x_n)/f^'(x_n) </math>, которая в последствии используется для нахождения <math> x_{n+1} = x_n - \varphi(x_n) </math>

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

Как и было описано в описании ядра алгоритма, основную часть метода составляет вычисление значения функции <math> f(x_n) </math> и ее производной <math> f^'(x_n) </math> в точке x_n.

<math> f(x_n) = \sum_{i=0}^{n}f_ix_n^i </math>

<math> f^'(x_n) = \sum_{i=0}^{n-1}f^'_ix_n^i </math>

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

Последовательность исполнения метода следующая:

1. Выбираем начальное приближение <math> x_0 </math>
2. Находим значение функции <math> f(x_n) </math> в точке <math>x_n</math>.
3. Находим значение производной функции <math> f^'(x_n) </math> в точке <math>x_n</math>.
4. Получаем следующий шаг итерации <math> x_{n+1} </math><math> x_{n+1} = x_n - f(x_n)/f^'(x+n) </math>
5. Находим погрешность <math> e = |x_{n+1} - x_n| </math>
6. Если погрешность не превышает некоторого заранее заданного числа - останавливаемся.

<math> e < \varepsilon </math>

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

Для вычисления корня методом Ньютона при последовательном выполнении требуется:

* <math> n </math> сложение + <math> n </math> умножений + <math> n-1 </math> умножений (возведение в степень)

* <math> n-1 </math> сложение + <math> n-1 </math> умножений + <math> n-2 </math> умножений (возведение в степень)

* одно вычитание и одно деление

* одно вычитание

Следовательно для одного шага алгоритма требуется:
* <math> 2n-1 </math> сложение (вычитание)
* <math> 4n-3 </math> умножений (делений)

=== Информационный граф ===
На рисунке ниже изображена структура информационного графа алгоритма. Блок IN представляет собой выбор начального приближения, блок IT - итерацию алгоритма, блок OUT - концу работы алгоритма.

[[Файл:MNP1.PNG|center|frame|Рисунок 1. Информационный граф]]

Как видно, алгоритм строго последовательный.
Ниже подробнее рассмотрено как можно разделить нагрузку связанную с вычислениями <math> f(x) </math> между процессорами. Каждое слагаемое полинома считается отдельно.

[[Файл:MNP2.PNG|center|frame|Рисунок 2. Итерация]]

Аналогично для <math> f^'(x) </math>.

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

Несмотря на то, что сам по себе алгоритм является строго последовательным, его можно ускорить за счет распараллеливания нахождения функции и ее производной на текущей итерации, так как это было описано в предыдущем пункте.

Пусть имеем <math> p </math> процессоров, в таком случае каждому процессору нужно будет произвести <math> (4n-3)/p </math> умножений.

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

Входными данными алгоритма являются:

1. Функция в виде полинома.
2. Область, в которой ищется корень <math> (a;b) </math>.
3. Начальное приближение <math> x_0 </math>.
4. Точность, с которой требуется найти решение.

На выход алгоритмом выдается число - предположительный корень найденный с заданной точностью.

== Программная реализация алгоритма ==

===2.4 Масштабируемость алгоритма и его реализации ===
Так как сам по себе метод является последовательным то, следовательно о его масштабируемости не может быть и речи.

Поверка масштабируемости реализации метода проводилась на следующих тестах:

* 1) <math> (x-1)g(x) </math>, где <math> g(x) </math> - произвольный полином степени <math> n-1 </math>.

[[Файл:MNP4.png|center|frame|Рисунок 1.]]

* 2) <math> 1 + 2x + 2x^2 + ... + 2x^{n-1} + x^n </math>

[[Файл:MNP3.png|center|frame|Рисунок 2.]]

Как видно из рисунков вне зависимости от размерности задачи не удалось добиться времени больше <math> 0.1 </math> секунды, в виду этого можно предположить, что время зависит от физического расположения процессоров, но тем не менее есть общая тенденция, что время работы возрастает вместе с размерностью и количеством процессоров.

=== Существующие реализации алгоритма ===

1. Последовательные реализации

**ALIAS C++. Язык реализации - C++. Распространяется бесплатно, исходные коды и примеры использования можно скачать на сайте<ref name="ALIAS">https://www-sop.inria.fr/coprin/logiciels/ALIAS/ALIAS-C++/ALIAS-C++.html</ref>.
**Numerical Recipes. Язык реализации - C++. Исходный код можно найти в секции 9.7 книги Numerical recipes(third edition)<ref name="RECIPES">http://numerical.recipes</ref>. Бесплатно доступны<ref name="RECIPES_old">http://numerical.recipes/oldverswitcher.html</ref> предыдущие издания для языков C, Fortran77, Fortran90.
**Sundials. Язык реализации - C, также есть интерфейс для использования в Fortran-программах. Распространяется<ref name="SUNDIALS_seq">http://computation.llnl.gov/projects/sundials/kinsol</ref> по лицензии BSD.

2. Параллельные реализации
**Построение параллельной реализации метода Ньютона для решения задач линейного программирования описано в работе В.А. Гаранжа, А.И. Голикова, Ю.Г. Евтушенко, М.Х. Нгуена "Параллельная реализации метода Ньютона для решения больших задач линейного программирования" <ref name="CCAS">http://www.ccas.ru/personal/evtush/p/paper1.pdf</ref>.
**Построение параллельной реализации метода Ньютона для решения задач оптимизации, описываются в работе V. A. Garanzha, A. I. Golikov, Yu. G. Evtushenko, and M. Kh. Nguen "Parallel Implementation of Newton’s Method for Solving Large-Scale Linear Programs" <ref name="IMPL_OPT">http://www.ccas.ru/personal/evtush/p/CMMP1303.pdf</ref>.
**Построение параллельной реализации метода Ньютона, а также результаты некоторых экспериментов, описываются в работе Renato N. Elias Alvaro L. G. A. Coutinho Marcos A. D. Martins Rubens M. Sydenstricker "PARALLEL INEXACT NEWTON-TYPE METHODS FOR THE SUPG/PSPG SOLUTION OF STEADY INCOMPRESSIBLE 3D NAVIER-STOKES EQUATIONS IN PC CLUSTERS" <ref name="SUPG">http://www.nacad.ufrj.br/~rnelias/papers/CIL14-020.pdf</ref>.
**Описание использования и результатов экспериментов с параллельной реализацией метода Ньютона в задаче фильтрации вязкой сжимаемой многофазной многокомпонентной смеси в пористой среде описано в работе К.Ю.Богачева "Эффективное решение задачи фильтрации вязкой сжимаемой многофазной многокомпонентной смеси на параллельных ЭВМ"<ref name="BOGACHEV">http://academy.hpc-russia.ru/files/reservoirdynamics_bogachev.pdf</ref>.

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

<references \>

Участник:MukhayevD/Метод Ньютона

2016-11-25T16:35:58Z

MukhayevD:

Автор: [[Участник:MukhayevD|Мухаев Д.Н.]]

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

=== Общее описание алгоритма ===
'''Метод Ньютона''', '''алгоритм Ньютона''' (также известный как '''метод касательных''') — это итерационный численный метод нахождения корня заданной функции(в связи с трудностями программирования производной для произвольной функции рассматриваются только функции в виде полинома). Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных.

=== Математическое описание алгоритма ===
Пусть <math> x_n </math> - некоторое приближение к корню уравнения <math> f(x) = 0, f \in C^1 </math>, то следующее приближение определяется как корень касательной к функции <math> f(x) </math>, проведенной в точке <math> x_n </math>.

Уравнение касательной к функции <math> f(x) </math> в точке <math> x_n </math> имеет вид:
<math> f^'(x_n) = (y - f(x_n))/(x - x_n) </math>
В уравнении касательной положим <math> y = 0 </math> и <math> x = x_{n+1} </math>.
Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:
<math> x_{n+1} = x_n - f(x_n)/f^'(x_n) </math>
Сходимость метода касательных квадратичная, порядок сходимости равен 2.

=== Вычислительное ядро алгоритма ===
Основная вычислительная нагрузка алгоритма заключается в нахождении <math> \varphi(x_n) = f(x_n)/f^'(x_n) </math>, которая в последствии используется для нахождения <math> x_{n+1} = x_n - \varphi(x_n) </math>

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

Как и было описано в описании ядра алгоритма, основную часть метода составляет вычисление значения функции <math> f(x_n) </math> и ее производной <math> f^'(x_n) </math> в точке x_n.

<math> f(x_n) = \sum_{i=0}^{n}f_ix_n^i </math>

<math> f^'(x_n) = \sum_{i=0}^{n-1}f^'_ix_n^i </math>

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

Последовательность исполнения метода следующая:

1. Выбираем начальное приближение <math> x_0 </math>
2. Находим значение функции <math> f(x_n) </math> в точке <math>x_n</math>.
3. Находим значение производной функции <math> f^'(x_n) </math> в точке <math>x_n</math>.
4. Получаем следующий шаг итерации <math> x_{n+1} </math><math> x_{n+1} = x_n - f(x_n)/f^'(x+n) </math>
5. Находим погрешность <math> e = |x_{n+1} - x_n| </math>
6. Если погрешность не превышает некоторого заранее заданного числа - останавливаемся.

<math> e < \varepsilon </math>

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

Для вычисления корня методом Ньютона при последовательном выполнении требуется:

* <math> n </math> сложение + <math> n </math> умножений + <math> n-1 </math> умножений (возведение в степень)

* <math> n-1 </math> сложение + <math> n-1 </math> умножений + <math> n-2 </math> умножений (возведение в степень)

* одно вычитание и одно деление

* одно вычитание

Следовательно для одного шага алгоритма требуется:
* <math> 2n-1 </math> сложение (вычитание)
* <math> 4n-3 </math> умножений (делений)

=== Информационный граф ===
На рисунке ниже изображена структура информационного графа алгоритма. Блок IN представляет собой выбор начального приближения, блок IT - итерацию алгоритма, блок OUT - концу работы алгоритма.

[[Файл:MNP1.PNG|center|frame|Рисунок 1. Информационный граф]]

Как видно, алгоритм строго последовательный.
Ниже подробнее рассмотрено как можно разделить нагрузку связанную с вычислениями <math> f(x) </math> между процессорами. Каждое слагаемое полинома считается отдельно.

[[Файл:MNP2.PNG|center|frame|Рисунок 2. Итерация]]

Аналогично для <math> f^'(x) </math>.

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

Несмотря на то, что сам по себе алгоритм является строго последовательным, его можно ускорить за счет распараллеливания нахождения функции и ее производной на текущей итерации, так как это было описано в предыдущем пункте.

Пусть имеем <math> p </math> процессоров, в таком случае каждому процессору нужно будет произвести <math> (4n-3)/p </math> умножений.

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

Входными данными алгоритма являются:

1. Функция в виде полинома.
2. Область, в которой ищется корень <math> (a;b) </math>.
3. Начальное приближение <math> x_0 </math>.
4. Точность, с которой требуется найти решение.

На выход алгоритмом выдается число - предположительный корень найденный с заданной точностью.

== Программная реализация алгоритма ==

=== Масштабируемость алгоритма и его реализации ===
Так как сам по себе метод является последовательным то, следовательно о его масштабируемости не может быть и речи.

Поверка масштабируемости реализации метода проводилась на следующих тестах:

* 1) <math> (x-1)g(x) </math>, где <math> g(x) </math> - произвольный полином степени <math> n-1 </math>.

[[Файл:MNP4.png|center|frame|Рисунок 1.]]

* 2) <math> 1 + 2x + 2x^2 + ... + 2x^{n-1} + x^n </math>

[[Файл:MNP3.png|center|frame|Рисунок 2.]]

Как видно из рисунков вне зависимости от размерности задачи не удалось добиться времени больше <math> 0.1 </math> секунды, в виду этого можно предположить, что время зависит от физического расположения процессоров, но тем не менее есть общая тенденция, что время работы возрастает вместе с размерностью и количеством процессоров.

=== Существующие реализации алгоритма ===

1. Последовательные реализации

**ALIAS C++. Язык реализации - C++. Распространяется бесплатно, исходные коды и примеры использования можно скачать на сайте<ref name="ALIAS">https://www-sop.inria.fr/coprin/logiciels/ALIAS/ALIAS-C++/ALIAS-C++.html</ref>.
**Numerical Recipes. Язык реализации - C++. Исходный код можно найти в секции 9.7 книги Numerical recipes(third edition)<ref name="RECIPES">http://numerical.recipes</ref>. Бесплатно доступны<ref name="RECIPES_old">http://numerical.recipes/oldverswitcher.html</ref> предыдущие издания для языков C, Fortran77, Fortran90.
**Sundials. Язык реализации - C, также есть интерфейс для использования в Fortran-программах. Распространяется<ref name="SUNDIALS_seq">http://computation.llnl.gov/projects/sundials/kinsol</ref> по лицензии BSD.

2. Параллельные реализации
**Построение параллельной реализации метода Ньютона для решения задач линейного программирования описано в работе В.А. Гаранжа, А.И. Голикова, Ю.Г. Евтушенко, М.Х. Нгуена "Параллельная реализации метода Ньютона для решения больших задач линейного программирования" <ref name="CCAS">http://www.ccas.ru/personal/evtush/p/paper1.pdf</ref>.
**Построение параллельной реализации метода Ньютона для решения задач оптимизации, описываются в работе V. A. Garanzha, A. I. Golikov, Yu. G. Evtushenko, and M. Kh. Nguen "Parallel Implementation of Newton’s Method for Solving Large-Scale Linear Programs" <ref name="IMPL_OPT">http://www.ccas.ru/personal/evtush/p/CMMP1303.pdf</ref>.
**Построение параллельной реализации метода Ньютона, а также результаты некоторых экспериментов, описываются в работе Renato N. Elias Alvaro L. G. A. Coutinho Marcos A. D. Martins Rubens M. Sydenstricker "PARALLEL INEXACT NEWTON-TYPE METHODS FOR THE SUPG/PSPG SOLUTION OF STEADY INCOMPRESSIBLE 3D NAVIER-STOKES EQUATIONS IN PC CLUSTERS" <ref name="SUPG">http://www.nacad.ufrj.br/~rnelias/papers/CIL14-020.pdf</ref>.
**Описание использования и результатов экспериментов с параллельной реализацией метода Ньютона в задаче фильтрации вязкой сжимаемой многофазной многокомпонентной смеси в пористой среде описано в работе К.Ю.Богачева "Эффективное решение задачи фильтрации вязкой сжимаемой многофазной многокомпонентной смеси на параллельных ЭВМ"<ref name="BOGACHEV">http://academy.hpc-russia.ru/files/reservoirdynamics_bogachev.pdf</ref>.

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

<references \>

Участник:MukhayevD/Метод Ньютона

2016-11-25T16:29:00Z

MukhayevD: /* Существующие реализации алгоритма */

{{algorithm
| name =
| serial_complexity =
| input_data =
| output_data =
}}

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

=== Общее описание алгоритма ===
'''Метод Ньютона''', '''алгоритм Ньютона''' (также известный как '''метод касательных''') — это итерационный численный метод нахождения корня заданной функции(в связи с трудностями программирования производной для произвольной функции рассматриваются только функции в виде полинома). Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных.

=== Математическое описание алгоритма ===
Пусть <math> x_n </math> - некоторое приближение к корню уравнения <math> f(x) = 0, f \in C^1 </math>, то следующее приближение определяется как корень касательной к функции <math> f(x) </math>, проведенной в точке <math> x_n </math>.

Уравнение касательной к функции <math> f(x) </math> в точке <math> x_n </math> имеет вид:
<math> f^'(x_n) = (y - f(x_n))/(x - x_n) </math>
В уравнении касательной положим <math> y = 0 </math> и <math> x = x_{n+1} </math>.
Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:
<math> x_{n+1} = x_n - f(x_n)/f^'(x_n) </math>
Сходимость метода касательных квадратичная, порядок сходимости равен 2.

=== Вычислительное ядро алгоритма ===
Основная вычислительная нагрузка алгоритма заключается в нахождении <math> \varphi(x_n) = f(x_n)/f^'(x_n) </math>, которая в последствии используется для нахождения <math> x_{n+1} = x_n - \varphi(x_n) </math>

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

Как и было описано в описании ядра алгоритма, основную часть метода составляет вычисление значения функции <math> f(x_n) </math> и ее производной <math> f^'(x_n) </math> в точке x_n.

<math> f(x_n) = \sum_{i=0}^{n}f_ix_n^i </math>

<math> f^'(x_n) = \sum_{i=0}^{n-1}f^'_ix_n^i </math>

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

Последовательность исполнения метода следующая:

1. Выбираем начальное приближение <math> x_0 </math>
2. Находим значение функции <math> f(x_n) </math> в точке <math>x_n</math>.
3. Находим значение производной функции <math> f^'(x_n) </math> в точке <math>x_n</math>.
4. Получаем следующий шаг итерации <math> x_{n+1} </math><math> x_{n+1} = x_n - f(x_n)/f^'(x+n) </math>
5. Находим погрешность <math> e = |x_{n+1} - x_n| </math>
6. Если погрешность не превышает некоторого заранее заданного числа - останавливаемся.

<math> e < \varepsilon </math>

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

Для вычисления корня методом Ньютона при последовательном выполнении требуется:

* <math> n </math> сложение + <math> n </math> умножений + <math> n-1 </math> умножений (возведение в степень)

* <math> n-1 </math> сложение + <math> n-1 </math> умножений + <math> n-2 </math> умножений (возведение в степень)

* одно вычитание и одно деление

* одно вычитание

Следовательно для одного шага алгоритма требуется:
* <math> 2n-1 </math> сложение (вычитание)
* <math> 4n-3 </math> умножений (делений)

=== Информационный граф ===
На рисунке ниже изображена структура информационного графа алгоритма. Блок IN представляет собой выбор начального приближения, блок IT - итерацию алгоритма, блок OUT - концу работы алгоритма.

[[Файл:MNP1.PNG|center|frame|Рисунок 1. Информационный граф]]

Как видно, алгоритм строго последовательный.
Ниже подробнее рассмотрено как можно разделить нагрузку связанную с вычислениями <math> f(x) </math> между процессорами. Каждое слагаемое полинома считается отдельно.

[[Файл:MNP2.PNG|center|frame|Рисунок 2. Итерация]]

Аналогично для <math> f^'(x) </math>.

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

Несмотря на то, что сам по себе алгоритм является строго последовательным, его можно ускорить за счет распараллеливания нахождения функции и ее производной на текущей итерации, так как это было описано в предыдущем пункте.

Пусть имеем <math> p </math> процессоров, в таком случае каждому процессору нужно будет произвести <math> (4n-3)/p </math> умножений.

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

Входными данными алгоритма являются:

1. Функция в виде полинома.
2. Область, в которой ищется корень <math> (a;b) </math>.
3. Начальное приближение <math> x_0 </math>.
4. Точность, с которой требуется найти решение.

На выход алгоритмом выдается число - предположительный корень найденный с заданной точностью.

== Программная реализация алгоритма ==

=== Масштабируемость алгоритма и его реализации ===
Так как сам по себе метод является последовательным то, следовательно о его масштабируемости не может быть и речи.

Поверка масштабируемости реализации метода проводилась на следующих тестах:

* 1) <math> (x-1)g(x) </math>, где <math> g(x) </math> - произвольный полином степени <math> n-1 </math>.

[[Файл:MNP4.png|center|frame|Рисунок 1.]]

* 2) <math> 1 + 2x + 2x^2 + ... + 2x^{n-1} + x^n </math>

[[Файл:MNP3.png|center|frame|Рисунок 2.]]

Как видно из рисунков вне зависимости от размерности задачи не удалось добиться времени больше <math> 0.1 </math> секунды, в виду этого можно предположить, что время зависит от физического расположения процессоров, но тем не менее есть общая тенденция, что время работы возрастает вместе с размерностью и количеством процессоров.

=== Существующие реализации алгоритма ===

1. Последовательные реализации

**ALIAS C++. Язык реализации - C++. Распространяется бесплатно, исходные коды и примеры использования можно скачать на сайте<ref name="ALIAS">https://www-sop.inria.fr/coprin/logiciels/ALIAS/ALIAS-C++/ALIAS-C++.html</ref>.
**Numerical Recipes. Язык реализации - C++. Исходный код можно найти в секции 9.7 книги Numerical recipes(third edition)<ref name="RECIPES">http://numerical.recipes</ref>. Бесплатно доступны<ref name="RECIPES_old">http://numerical.recipes/oldverswitcher.html</ref> предыдущие издания для языков C, Fortran77, Fortran90.
**Sundials. Язык реализации - C, также есть интерфейс для использования в Fortran-программах. Распространяется<ref name="SUNDIALS_seq">http://computation.llnl.gov/projects/sundials/kinsol</ref> по лицензии BSD.

2. Параллельные реализации
**Построение параллельной реализации метода Ньютона для решения задач линейного программирования описано в работе В.А. Гаранжа, А.И. Голикова, Ю.Г. Евтушенко, М.Х. Нгуена "Параллельная реализации метода Ньютона для решения больших задач линейного программирования" <ref name="CCAS">http://www.ccas.ru/personal/evtush/p/paper1.pdf</ref>.
**Построение параллельной реализации метода Ньютона для решения задач оптимизации, описываются в работе V. A. Garanzha, A. I. Golikov, Yu. G. Evtushenko, and M. Kh. Nguen "Parallel Implementation of Newton’s Method for Solving Large-Scale Linear Programs" <ref name="IMPL_OPT">http://www.ccas.ru/personal/evtush/p/CMMP1303.pdf</ref>.
**Построение параллельной реализации метода Ньютона, а также результаты некоторых экспериментов, описываются в работе Renato N. Elias Alvaro L. G. A. Coutinho Marcos A. D. Martins Rubens M. Sydenstricker "PARALLEL INEXACT NEWTON-TYPE METHODS FOR THE SUPG/PSPG SOLUTION OF STEADY INCOMPRESSIBLE 3D NAVIER-STOKES EQUATIONS IN PC CLUSTERS" <ref name="SUPG">http://www.nacad.ufrj.br/~rnelias/papers/CIL14-020.pdf</ref>.
**Описание использования и результатов экспериментов с параллельной реализацией метода Ньютона в задаче фильтрации вязкой сжимаемой многофазной многокомпонентной смеси в пористой среде описано в работе К.Ю.Богачева "Эффективное решение задачи фильтрации вязкой сжимаемой многофазной многокомпонентной смеси на параллельных ЭВМ"<ref name="BOGACHEV">http://academy.hpc-russia.ru/files/reservoirdynamics_bogachev.pdf</ref>.

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

<references \>

Участник:MukhayevD/Метод Ньютона

2016-11-25T16:16:46Z

MukhayevD: /* Информационный граф */

Участник:MukhayevD/Метод Ньютона

2016-11-25T16:10:10Z

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

{{algorithm
| name =
| serial_complexity =
| input_data =
| output_data =
}}

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

=== Общее описание алгоритма ===
'''Метод Ньютона''', '''алгоритм Ньютона''' (также известный как '''метод касательных''') — это итерационный численный метод нахождения корня заданной функции(в связи с трудностями программирования производной для произвольной функции рассматриваются только функции в виде полинома). Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных.

=== Математическое описание алгоритма ===
Пусть <math> x_n </math> - некоторое приближение к корню уравнения <math> f(x) = 0, f \in C^1 </math>, то следующее приближение определяется как корень касательной к функции <math> f(x) </math>, проведенной в точке <math> x_n </math>.

Уравнение касательной к функции <math> f(x) </math> в точке <math> x_n </math> имеет вид:
<math> f^'(x_n) = (y - f(x_n))/(x - x_n) </math>
В уравнении касательной положим <math> y = 0 </math> и <math> x = x_{n+1} </math>.
Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:
<math> x_{n+1} = x_n - f(x_n)/f^'(x_n) </math>
Сходимость метода касательных квадратичная, порядок сходимости равен 2.

=== Вычислительное ядро алгоритма ===
Основная вычислительная нагрузка алгоритма заключается в нахождении <math> \varphi(x_n) = f(x_n)/f^'(x_n) </math>, которая в последствии используется для нахождения <math> x_{n+1} = x_n - \varphi(x_n) </math>

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

Как и было описано в описании ядра алгоритма, основную часть метода составляет вычисление значения функции <math> f(x_n) </math> и ее производной <math> f^'(x_n) </math> в точке x_n.

<math> f(x_n) = \sum_{i=0}^{n}f_ix_n^i </math>

<math> f^'(x_n) = \sum_{i=0}^{n-1}f^'_ix_n^i </math>

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

Последовательность исполнения метода следующая:

1. Выбираем начальное приближение <math> x_0 </math>
2. Находим значение функции <math> f(x_n) </math> в точке <math>x_n</math>.
3. Находим значение производной функции <math> f^'(x_n) </math> в точке <math>x_n</math>.
4. Получаем следующий шаг итерации <math> x_{n+1} </math><math> x_{n+1} = x_n - f(x_n)/f^'(x+n) </math>
5. Находим погрешность <math> e = |x_{n+1} - x_n| </math>
6. Если погрешность не превышает некоторого заранее заданного числа - останавливаемся.

<math> e < \varepsilon </math>

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

Для вычисления корня методом Ньютона при последовательном выполнении требуется:

* <math> n </math> сложение + <math> n </math> умножений + <math> n-1 </math> умножений (возведение в степень)

* <math> n-1 </math> сложение + <math> n-1 </math> умножений + <math> n-2 </math> умножений (возведение в степень)

* одно вычитание и одно деление

* одно вычитание

Следовательно для одного шага алгоритма требуется:
* <math> 2n-1 </math> сложение (вычитание)
* <math> 4n-3 </math> умножений (делений)

=== Информационный граф ===
На рисунке ниже изображена структура информационного графа алгоритма. Блок IN представляет собой выбор начального приближения, блок IT - итерацию алгоритма, блок OUT - концу работы алгоритма.

[[Файл:MNP1.png|center|frame|Рисунок 1. Информационный граф]]

Как видно, алгоритм строго последовательный.
Ниже подробнее рассмотрено как можно разделить нагрузку связанную с вычислениями <math> f(x) </math> между процессорами. Каждое слагаемое полинома считается отдельно.
[[Файл:MNP2.png|center|frame|Рисунок 2. Итерация]]
Аналогично для <math> f^'(x) </math>.

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

Несмотря на то, что сам по себе алгоритм является строго последовательным, его можно ускорить за счет распараллеливания нахождения функции и ее производной на текущей итерации, так как это было описано в предыдущем пункте.

Пусть имеем <math> p </math> процессоров, в таком случае каждому процессору нужно будет произвести <math> (4n-3)/p </math> умножений.

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

Входными данными алгоритма являются:

1. Функция в виде полинома.
2. Область, в которой ищется корень <math> (a;b) </math>.
3. Начальное приближение <math> x_0 </math>.
4. Точность, с которой требуется найти решение.

На выход алгоритмом выдается число - предположительный корень найденный с заданной точностью.

== Программная реализация алгоритма ==

=== Масштабируемость алгоритма и его реализации ===
Так как сам по себе метод является последовательным то, следовательно о его масштабируемости не может быть и речи.

Поверка масштабируемости реализации метода проводилась на следующих тестах:

* 1) <math> (x-1)g(x) </math>, где <math> g(x) </math> - произвольный полином степени <math> n-1 </math>.

[[Файл:MNP4.png|center|frame|Рисунок 1.]]

* 2) <math> 1 + 2x + 2x^2 + ... + 2x^{n-1} + x^n </math>

[[Файл:MNP3.png|center|frame|Рисунок 2.]]

Как видно из рисунков вне зависимости от размерности задачи не удалось добиться времени больше <math> 0.1 </math> секунды, в виду этого можно предположить, что время зависит от физического расположения процессоров, но тем не менее есть общая тенденция, что время работы возрастает вместе с размерностью и количеством процессоров.

=== Существующие реализации алгоритма ===

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

<references \>

Участник:MukhayevD

2016-11-23T21:03:36Z

MukhayevD:

Студент 4 курса бакалавриата ВМК МГУ, группа 414.

[[https://algowiki-project.org/ru/Участник:MukhayevD/Метод_Ньютона]]

Участник:MukhayevD/Метод Ньютона

2016-11-23T21:03:16Z

MukhayevD:

Участник:MukhayevD/Метод Ньютона

2016-11-23T20:43:16Z

MukhayevD: /* Информационный граф */

Участник:MukhayevD/Метод Ньютона

2016-11-23T20:40:01Z

MukhayevD: /* Информационный граф */

Участник:MukhayevD/Метод Ньютона

2016-11-23T16:40:24Z

MukhayevD: Новая страница: «{{algorithm | name = | serial_complexity = | input_data = | output_data = }} == Свойства и структура алгори…»

Участник:MukhayevD

2016-11-23T13:11:58Z

MukhayevD: Новая страница: «Студент 4 курса бакалавриата ВМК МГУ, группа 414.»

Студент 4 курса бакалавриата ВМК МГУ, группа 414.