Метод Ньютона

Получим метод с более высокой скоростью сходимости, чем обычный метод итерации. Для этого вернемся вновь к соотношению между погрешностями на двух соседних итерациях (3):

e_n+1=φ '(ξ)•ε_n+[φ ''(η)/2!]•ε²_n; η≤[a.b];

Если φ '(ξ)=0, то ε_n+1=[φ "(η)/2!]•ε²_n, что означает в силу определения 2 квадратичную сходимость итерационного процесса. Преобразуем исходное уравнение f(x)=0, умножая его на некоторую функцию -Q(x) и добавляя по x в каждую часть уравнения:

x=x-Q(x)•f(x).

Таким образом,

φ(х)=х-Q(x)•f(x); φ '(x)=1-Q'•f-Q•f '.

Подставим вместо x корень ξ:

φ '(ξ)=1-Q'(ξ)•f(ξ)-Q(ξ )•f '(ξ)=1-Q(ξ)•f '(ξ);

Для конструируемого метода надо, чтобы φ '(ξ)=0, т.е.

1-Q(ξ)•f'(ξ)=0,

следовательно Q(ξ)= ─ 1/f '(ξ).

Потребуем выполнение последнего соотношения при любом x, тогда и для конкретного значения x=ξ оно также будет выполняться, т.е.

Q(x)= ─ 1/f '(x) и φ(х)=x - ,

а итерационный метод с квадратичной сходимостью определяется формулой

x_n+1= x_n- , где n=0,1,2,… .

Этот метод называется методом Ньютона.

Теорема о сходимости метода Ньютона. Если на концах отрезка [a,b], функция f(x) принимает значения разных знаков, (то есть f(a)•f(b)<0), f '(x),f "(x) определены, непрерывны, отличны от нуля и сохраняют определенные знаки на отрезке [a,b], то исходя из начального приближения х₀Î[a,b], удовлетворяющего условию f(x₀)•f "(x₀)>0, то для данной функции можно методом Ньютона вычислить единственный на этом промежутке корень уравнения f(x)=0 с любой степенью точности.

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

Запишем уравнение касательной к f(x) в точке x₀:

y(x)=f(x₀)+f '(x₀)•(x-x₀).

Найдем точку x₁―точку пересечения касательной с осью абсцисс, т.е

y(x₁)=0 или f(x₀) - f '(x₀)•(x₁-x₀)=0, откуда x₁=x₀ - .

Нетрудно заметить, что x₁ ― это первое приближение в методе Ньютона.

Аналогично получается x₂.- точка пересечения с осью абсцисс касательной, проведенной к кривой в точке x₁ – рис. 3.

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