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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ f(x_n) = \sum_{i=0}^{n}f_ix_n^i }[/math]

[math]\displaystyle{ f^'(x_n) = \sum_{i=0}^{n-1}f^'_ix_n^i }[/math]

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

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

1. Выбираем начальное приближение [math]\displaystyle{ x_0 }[/math]

2. Находим значение функции [math]\displaystyle{ f(x_n) }[/math] в точке x_n.

3. Находим значение производной функции [math]\displaystyle{ f^'(x_n) }[/math] в точке x_n.

4. Получаем следующий шаг итерации [math]\displaystyle{ x_{n+1} }[/math]

[math]\displaystyle{ x_{n+1} = x_n - f(x_n)/f^'(x+n) }[/math]

5. Находим погрешность [math]\displaystyle{ e = |x_{n+1} - x_n| }[/math]

6. Если погрешность не превышает некоторого заранее заданного числа - останавливаемся.

[math]\displaystyle{ e \lt \varepsilon }[/math]

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

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

• [math]\displaystyle{ n }[/math] сложение + [math]\displaystyle{ n }[/math] умножений + [math]\displaystyle{ n-1 }[/math] умножений (возведение в степень)

• [math]\displaystyle{ n-1 }[/math] сложение + [math]\displaystyle{ n-1 }[/math] умножений + [math]\displaystyle{ n-2 }[/math] умножений (возведение в степень)

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

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

Следовательно для одного шага алгоритма требуется:

• [math]\displaystyle{ 2n-1 }[/math] сложение (вычитание)
• [math]\displaystyle{ 4n-3 }[/math] умножений (делений)

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

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

Файл:MNP1.png

Рисунок 1. Информационный граф

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

Файл:MNP2.png

Рисунок 2. Итерация

Аналогично для [math]\displaystyle{ f^'(x) }[/math].

Литература

<references \>