Метод Ньютона и оценка погрешности приближения

 

 

Получим метод с более высокой скоростью сходимости, чем обычный метод итерации. Для этого вернемся вновь к соотношению между погрешностями на двух соседних итерациях (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.

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

 

Модификации метода Ньютона и оценка погрешности приближения.

 

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

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

Геометрически такая модификация означает, что все касательные заменяются прямыми, параллельными первой касательной, проведенной к кривой в точке х₀. Это приводит к увеличению количества итеративных шагов, необходимых для достижения заданной точности – сходимость становится линейной. Условия сходимости такие же, что и для метода Ньютона.

Вторая модификация связана с заменой производной разностным соотношением:

ƒ '(x_n)» ; x_n+1 = x_n - , где n=1,2,3…

Отличительной особенностью полученного таким образом метода – его двухшаговость. Под этим понимается то, что при нахождении очередного приближения требуется знание двух предыдущих. Соответственно и начальных приближений должно быть задано два: х₀ и х₁, причем х₁ должно быть выбрано между корнем и х₀ (х₁ и х₀ должны лежать по одну сторону от корня). Остальные условие сходимости этого метода такие же, как и для метода Ньютона. Скорость сходимости снижается, но незначительно: e_n+1≈e_n^1,618, т.е. близка к квадратичной. Геометрически вместо касательных строятся секущие по значениям функции в двух соседних приближениях, поэтому эта модификация носит название метода секущих.

 

 

Метoд хорд и оценка погрешности приближения.

Метод хорд

Допустим, что на [a,b] функция f(x) меняется почти линейно. Тогда ее можно заменить стягивающей хордой y(x):

= .

Точку пересечения хорды с осью абсцисс, где y(x₁)=0 примем за первое приближение к корню исходного уравнения

x₁=a- .

Аналогично x₂=x₁- .

Обобщая, получим расчетную формулу x_n+1=x_n- ,

где X―неподвижный конец интервала. Для сходимости метода должны быть выполнены все условия теоремы о сходимости метода Ньютона, только условие f(X)•f"(X)>0 определяет выбор неподвижного конца; противоположный конец берется за начальное приближение: f(x₀)•f "(x₀)<0.

Геометрическая интерпретация метода хорд показана на рис.4.

 

ƒ(b)

y

 

 

ƒ(х)

 

0 a x₁ x₂ ξ b x

ƒ(a)