Уровень алгоритма

Участник:SKirill/Метод Ньютона решения систем нелинейных уравнений

Материал из Алговики
Перейти к навигации Перейти к поиску


Метод Ньютона решения систем нелинейных уравнений
Последовательный алгоритм
Объём выходных данных [math]n[/math]-мерный вектор

Авторы: Шохин К.О., Лебедев А.А.

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

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

Метод Ньютона решения систем нелинейных уравнений является обобщением метода Ньютона решения нелинейных уравнений, который основан на идеи линеаризации. Пусть [math] F(x) : R^1 \to R^1[/math] - дифференцируемая функция и необходимо решить уравнение [math]F(x) = 0[/math].

Взяв некоторое [math]x_0[/math] в качестве начального приближения решения, мы можем построить линейную аппроксимацию

[math]F(x)[/math] в окрестности [math]x_0 : F(x_0+h) \approx F(x_0)+F^'(x_0)h[/math] и решить получающееся линейное уравнение [math]F(x_0 )+F^' (x_0 )h =0[/math].


Таким образом получаем итеративный метод : [math] x_{k+1} = x_k - {F^'(x_k)}^{-1}F(x_k) , k = 0,1,\ldots[/math]


Данный метод был предложен Ньютоном в 1669 году. Более точно, Ньютон оперировал только с полиномами; в выражении для [math]F(x+h)[/math] он отбрасывал члены более высокого порядка по h , чем линейные. Ученик Ньютона Рафсон в 1690 г. предложил общую форму метода (т. е. не предполагалось что [math]F(x)[/math] обязательно полином и использовалось понятие производной), поэтому часто говорят о методе Ньютона—Рафсона. Дальнейшее развитие исследований связано с именами таких известных математиков, как Фурье, Коши и другие. Например, Фурье доказал в 1818 г., что метод сходится квадратично в окрестности корня, а Коши (1829, 1847) предложил многомерное обобщение метода и использовал метод для доказательства существования решения уравнения.


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

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

Основная вычислительная нагрузка алгоритма заключается в решении СЛАУ:

[math]\frac{\partial F(x^{(k)})}{\partial x}\Delta x^{(k)} = -F(x^{(k)}) (*)[/math]

Для нахождения значения [math]\Delta x^{(k)}[/math], по которому вычисляется значение вектора [math]\overline{x}[/math], на очередной итерации вычисляется значение: [math]x^{(k+1)} = x^{(k)} + \Delta x^{(k)}[/math]

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

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

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

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

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

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

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

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

2.1 Масштабируемость алгоритма и его реализации

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

3 Литература

Тыртышников Е. Е. Методы численного анализа — М., Академия, 2007. - 320 c.
Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.


<references \>