изучение метода ньютона

Для решения систем нелинейных уравнений"

Работу подготовили: Сумской С.И., к.т.н.

Маклашова И.В.

Башлачев В.К.

г. Москва

2012 г.

Метод Ньютона - метод приближенного нахождения корней действительного уравнения

f(x) = 0, (1)

где f - дифференцируемая функция. Задав начальное приближение к корню уравнения (1), путем итераций получают решение с любой степенью точности.

Итерационный процесс основан на представлении функции в окресности текущего приближения x=a в виде ряда Тейлора:

f(x) = f(a) + f'(a)*(x-a) + 0.5*f''(a)*(x-a)^2 +... (2)

и аппроксимации f(x) линейным приближением

M(x) = f(a) + f'(a)*(x-a). (3)

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

Согласно формуле Ньютона-Лейбница

f(x) = f(a) +

Аппроксимируя интеграл как f'(a)*(x-a) просто и, естественно, получаем выражение (3).

Для получения следующего приближения полагаем M(x)=0 и, следовательно,

x - a = -f(a) / f'(a). (4)

Таким образом, следующее приближение определяется как

x_i+1 = x_i - f(x_i) / f'(x_i), i=0, 1, 2,... (5)

Здесь в нижнем индексе обозначен номер приближения.

Метод Ньютона имеет простую графическую интерпретацию: уравнение

(4) определяет прямую, проходящую через точки (x,0) и (a,f(a)), причем во второй точке она касается кривой f(x) (так как тангенс угла

наклона этой прямой равен значению производной в точке х=а).

Метод Ньютона является частным случаем итерационных методов решения нелинейных уравнений. Эти методы основаны на построении сходящейся числовой последовательности по правилу

g(x_i+1) = h(x_i), (6)

где g(x) и h(x) - непрерывные функции. Вследствие предположенной непрерывности предельное значение такой последовательности Z является корнем X рассматриваемого уравнения (1), так как из соотношений

x{i+1} ─> Z и x{i} ─> Z (7)

в силу непрерывности g(x) и h(x) имеем g(Z)=h(Z), т.е. X=Z.

Достаточные условия сходимости:

g'(x) и h'(x) непрерывны в некоторой окрестности X, в этой окрестности лежит начальное приближение и верно

│g'(x)│ > │h'(x)│. (8)

Применительно к методу Ньютона из условия (8), где

g(x) = x и h(x) = x - f(x) / f'(x) (9)

получим

│h'(x)│ = │ f''(x)*f(x) / f'(x)² │ < 1 (10)

в окрестности корня.

Если X является простым корнем, то выполняются соотношения

f'(X) ╪ 0 и h'(X) ╪ 0. Следовательно, для начального значения x=a

должно выполняться неравенство

│ f''(a)*f(a) │ < │ f'(a)² │. (11)

ПРИМЕР 1. Нахождение значения квадратного корня из C, т.е. решение

уравнения x^2 - C = 0, C > 0.

РЕШЕНИЕ. Перепишем его как

f(x) = x² - C = 0; f'(x) = 2*x;

Тогда x_i+1 = x_i - (x_i² - C) / (2* x_i) =

= x_i - 0.5*(x_i - C/ x_i).

Условие (10) накладывает ограничение на начальное приближение x₀=a:

h(x) = x - 0.5 * (x - C/x) = 0.5 * (x + C/x),

h'(x) = 0.5 * (1 - C/(x²));

Так как │h'(a)│ < 1, то │ 1 - С/(a²) │ < 2 и огрaничение выглядит как a² > C/3. Напомним, что оно является достаточным и часто слишком сильным для практических вычислений. Проведем исчисления для С=2:

2 ─> 1.5 ─> 1.4167 ─> 1.4142157 ─> 1.414213562.

У последнего значения (полученного после 4-ой итерации) все знаки

являются верными.

Метод Ньютона имеет второй порядок сходимости в близкой окрестности решения рассматриваемой задачи, что позволяет достигать необходимой точности за небольшое число итераций.

Метод Ньютона может быть распространен для решения систем нелинейных уравнений, проводя линеаризацию через разложение по формуле Тейлора (метод Ньютона-Канторовича), который позволяет не проводить трудоемких вычислений по расчету производных от рассматриваемых функций, но имеет только первый порядок сходимости.

Рассмотрим n непрерывных функций F(X)=(f₁(X), f₂(X),... f_n(X)) от n независимых переменных X=(x₁, x₂,... x_n), заданных в общей области определения.

Таким образом задается система уравнений F(X)=0:

ì f₁ (x₁, x₂, …, x_n) = 0 n уравнений с n неизвестными

ï f₂ (x₁, x₂, …, x_n) = 0

í

ï

î f_n (x₁, x₂, …, x_n) = 0.

И пусть имеется вектор X', лежащий в этой области, для которого верно:

F(X') = 0.

Тогда вектор X' называется решением системы уравнений F(X) = 0.

Для нахождения решения нелинейное представление F(X) заменяют линейным отображением L(X) = AX+B (A - матрица размера n*n). Тогда при определенных условиях решение Z системы L(X) оказывается подходящимbприближением к X'. Согласно методу Ньютона-Канторовича при непрерывной дифференцируемости f_j(X) в области определения (j=1, 2,... n)

F(X)=F(X₀)+│d(f₁, f₂,... f_n)/d(x₁, x₂,... x_n) │ *

X= X₀

* (X- X₀) + R(X). (12)

Отбрасывая остаточный член R(X), получаем

L(X) = F(X₀) + A*(X-X₀) = 0, (13)

где A - матрица Якоби, вычисленная в точке X₀.

Вы можете самостоятельно провести доказательство, опираясь на интегральное представление функции по формуле Ньютона-Лейбница. Предположим, что матрица A невырождена. Тогда система (13) однозначно разрешима относительно вектора X.

Таким образом, метод описывается следующей схемой:

1. Выбор приближения X₀ к решению X'.

2. Вычисление матрицы A(X₀).

3. Решение Z1 системы A(X₀)*Z + F(X₀) = 0 дает новое приближение X1 = X0+Z1, для которого процесс повторяют до тех пор, пока изменение Z_n не окажется в пределах заданной погрешности.

ПРИМЕР 2. Решим следующую систему уравнений:

x² + y² = 13, f₁(x, y) = x² + y² - 13;

x² - y² = 5; f₂(x, y) = x² + y² - 5,

df₁/dx = 2x; df₁/dy = 2y;

df₂/dx = 2x; df₂/dy = -2y;

Получаем систему двух линейных уравнений относительно приращений ‑x и ‑y:

‑x(2x) + ‑y(2y) = 13 - x² - y²;

‑x(2x) + ‑y(-2y) = 5 - x² + y²;

Решаем ее с начальными значениями (1,1):

x₀=1 2‑x + 2‑y = 11; 4‑x=16 ‑x=4

y₀=1 2‑x - 2‑y = 5; 4‑y=6 ‑y=1.5

x₁=5 10 ‑x + 5 ‑y = -18.25; 20 ‑x = -32 ‑x=-1.6

y₁=2.5 10 ‑x – 5 ‑y = -13.7; 10 ‑y = -4.5 ‑y=-0.45

x₂=3.4 6.8 ‑x + 4.1 ‑y = -2.7625; 13.6 ‑x=-5.12 ‑x=-0.37647

y₂=2.05 6.8 ‑x - 4.1 ‑y = -2.3575; 8.2 ‑y=-0.405 ‑y=-0.04939

x₃=3.02353 6.04706 ‑x + 4.00122 ‑y = -0.14417; 12.09412 ‑x=-0.28346

y₃=2.00061 6.04706 ‑x - 4.00122 ‑y = -0.13929; 8.00244 ‑y=-0.00488

‑x=-0.023438 x4=3.00009,

‑y=-0.0006098 y4=2.00000; точное решение (3,2).

Таким образом, за четыре итерации получена точность 1e-5.

Данная процедура может быть проведена для произвольного числа уравнений (переменных), а получающееся линейное уравнение решается, например, методом Гаусса.

Дата добавления: 2015-10-23