Участник: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] в точке [math]\displaystyle{ x_n }[/math].
 3. Находим значение производной функции [math]\displaystyle{  f^'(x_n)  }[/math] в точке [math]\displaystyle{ x_n }[/math].
 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].

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

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

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

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

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

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

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

Литература

<references \>