Метод Ньютона (метод касательных)

РЕШЕНИЕ ТРАНСЦЕНДЕНТНЫХ УРАВНЕНИЙ

Постановка задачи

Во многих инженерных и научных задачах возникает необходимость решения уравнений вида:

F (x, a 1, a 2,..., a k) = 0

(3.1)

где F - заданная непрерывная функция;

x – неизвестная величина, подлежащая определению;

a ₁, a ₂,..., a _k – известные параметры функции F.

Решить уравнение (3.1) - это значит найти такое значение (или такие значения) неизвестной x, при которых уравнение (3.1) превращается в тождество. Эти значения x называются корнями уравнения (3.1).

Только для простейших уравнений удается найти решение в аналитическом виде, т.е. записать формулу

x = f (a ₁, a ₂,..., a _k),

выражающую искомую величину x явным образом через параметры a ₁, a ₂,..., a _k, например, для уравнения вида

ax ² + bx + c = 0

его корни выражаются формулой:

.

В большинстве же случаев аналитическую запись корней уравнения найти очень сло­ж­но или в принципе невозможно (такие уравнения называются трансцендентными), и по­это­му приходится решать уравнение численным способом.

Существует несколько различных методов численного решения трансцендентных уравнений, но все они предполагают выполнение двух этапов: первый из них называется " отделение корней ", второй - " уточнение корней ". Ниже рассматривается один из спосо­бов отделения корней и четыре метода уточнения корней - метод дихотомий, метод хорд, метод касательных и метод простых итераций.

Отделение корней

На данном этапе определяются те интервалы области изменения переменной x, в каждом из которых расположен один и только один корень уравнения (3.1). По сути дела на этом этапе определяются грубые приближения значений x с погрешностью, определяемой длиной каждого найденного интервала. Пол­ностью автоматизировать процесс отде­ле­­ния корней, пожалуй, невозможно, так как в нем обязательно присутствует элемент су­бъ­ективного, интуитивного подхода к решению задачи. Иногда, например, интервал, в котором расположен корень, удается получить из физической сущности решаемой задачи.

При выполнении этого этапа с использованием ЭВМ обычно проводится "табу­лирование " функции F (x, a ₁, a ₂,..., a _k), т.е. построение таблицы ее значений при различных значе­ниях x, следующих друг за другом с некоторым шагом h:

 

x	F (x)
x 1	F 1
x 2	F 2
...	...
x n	F n

 

где x _i+1 = x _i + h; F _i = F (x _i); i = 1,2,...,n-1.

Например, таблица значений функции x ² - 12 ln½ x ½ + 6 sin x на промежутке [1,10] c шагом h = 1 имеет вид:

 

x	F (x)
1.0	6.05
2.0	0.72
3.0	- 3.99
4.0	- 6.01
5.0	- 1.03
6.0	11.75
7.0	28.42
8.0	43.74
9.0	55.79
10.0	67.72

 

В качестве границ искомых интервалов выбираются такие соседние значения x, в которых соответствующие значения F (x) имеют разные знаки, так как изменение знака функции на некотором интервале означает в силу ее непрерывности, что где-то в пределах этого интервала график функции пересекает ось абсцисс, т.е. уравнение F (x) = 0 име­ет корень. В частности, на основании данных из приведенной выше таблицы можно сде­лать вывод, что уравнение x ² - 12 ln½ x ½ + 6 sin x = 0 на промежутке [1,10] имеет по край­ней мере два корня: в интервале (2,3) и в интервале (5,6).

Рис.3.1. Алгоритм отделения корней табулированием функции

При выполнении этого этапа нужно проявлять определенную осторожность: во-пеpвых, оди­наковые знаки функции F на концах интервала (x _i, x _i+1) не означают, что на этом интервале нет корней - их может быть, например, два; во-втоpых, при разных знаках на концах интервала здесь может оказаться не один корень, а три или, например, пять.

В приводимой на рис.3.1 схеме алгоритма отделения корней использованы следующие обозначения:

x _Н, x _К - соответственно левая и правая границы промежутка табулирования функции F (x);

x - текущая точка табулирования;

;

В ₀, В ₁ - знаки функции F (x) соответственно в пре­дыдущей и текущей точках табулирования.

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

 

 

Метод дихотомии

Пусть на этапе отделения корней получены две точки A и B (A<B), между которыми находится корень уравнения (3.1), т.е. такие точки, в которых знаки значений функ­ции F (x) противоположны (см. рис.3.2): sign F (A) ¹ sign F (B).

Метод дихотомии, называемый еще методом половинного деления, заключается в следующем:

1) определяется середина отрезка [ A, B ]:

;

(3.2)

2) вычисляется значение функции в этой точке - F (P) и его знак sign F (P);

3) корень уравнения (3.1) находится в той половине отрезка [ A, B ], на концах которой функция F (x) имеет разные знаки. Если это будет половинка [ A, P ], то перенесем точку B в точку P; если же половинка [ P, B ], то перенесем точку A в точку P. Благодаря этой операции длина отрезка [ A, B ], на котором находится корень уравнения, уменьшилась вдвое, т.е. можно сказать, что значение корня определено с точностью до длины полученного отрезка.

Каждое новое повторение действий 1,2,3 будет давать все более точные значения корня уравнения. Повторение этого процесса следует прекращать, когда длина отрезка [ A, B ] станет меньше заранее заданного значения , являющегося в данном случае ошиб­кой ограничения, т.е. неравенство

B - A <

(3.3)

является критерием окончания вычислительного процесса.

Рис.3.3. Алгоритм метода дихотомии

Если величина задана очень малая, то вблизи корня значения F (x) могут ока­заться сравнимыми с погрешностью ее вычисления, т.е. при подходе к корню вычисли­тельный процесс может попасть в так называемую "полосу шума", и дальнейшее уточне­ние корня окажется невозможным. Поэтому кроме точности надо задавать в алгоритме ширину "полосы шума" 1 и прекращать процесс при попадании в него, т.е. неравенство F(P) | < 1 является дополнительным критерием окончания вычислительного процесса. Схема алгоритма представлена на рис.3.3.       Рис.3.2. Геометрическая интерпретация метода дихотомии

 

Метод хорд

Пусть так же, как в методе дихотомий, известны две точки A и B (A<B),для которых sign F (A) ¹ sign F (B). В методе хорд (см. рис.3.4), в отличие от метода дихотомий, в ка­чес­тве очередного приближения P берется точка пересечения с осью абсцисс хорды, соединяющей точки (A, F (A)) и (B, F (B)).

 

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

Уравнение прямой, проходящей через эти две точки запишем в виде: Y (x) = k x + c.

Коэффициенты k и c определяются из условий:

F (A) = k A + c; F (B) = k B + c.

Решая эту систему из двух уравнений, получим:

; c = F (A) - k A.

Точка P пересечения этой прямой с осью ОX определяется из уравнения

kP + c = 0.

Решая его, окончательно получаем:

.

(3.4)

В методе хорд нельзя использовать в качестве критерия окончания вычислительного процесса неравенство (3.3), так как, как видно из рис.3.4, величина B – A не стремится к нулю. В данном методе, как и в рассматриваемых ниже, вычислительный процесс следует прекращать при выполнении неравенства

,

(3.5)

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

Алгоритм метода хорд, следовательно, отличается от алгоритма метода дихотомий формулой вычисления приближения P (вместо (3.2) использется (3.4))и критерием окончания вычислительного процесса (вместо (3.3) использется (3.5)).

Блок-схему для метода хорд предлагается разработать самостоятельно.

Метод Ньютона (метод касательных)

Графическая интерпретация метода представлена на рис.3.5. Предположим, что каким-либо способом найдено начальное приближение х ₀ к истинному корню. Например, при использовании отделения корней, в качестве х ₀ можно взять левую или правую границу промежутка, содержащего корень уравнения F (x) = 0, либо любую другую точку из этого промежутка. В точке х ₀ вычислим значение функции F (x), а также значение ее производной F ^‘(x). Следующее приближение к корню, т.е. точку х ₁ определим, как пересечение оси ОХ с касательной к кривой F (x) в точке х ₀:

Аналогичным образом, вычислив значения F (x) и F ^‘(x), в точке х ₁, можно получить приближение х ₂:

В общем случае вычислительный процесс метода Ньютона выражается формулой:

(3.6)

где каждое новое значение х _k (k=1, 2, 3, …) будет располагаться все ближе к истинному корню х *., т.е. будет представлять собой все более точное приближение к решению уравнения F (x) = 0.

 

Рис.3.5. Метод Ньютона

Рис.3.6. Модифицированный метод Ньютона

 

Процесс уточнения корня по формуле (3.6) следует прекращать, когда выполнится условие , т.е. когда расстояние между двумя соседними приближениями станет меньше заранее за­данной точности .

Метод Ньютона обладает высокой скоростью сходимости. Обычно абсолютная точность решения 10^-5 – 10^-6 достигается за 4-5 итераций. Недостатком метода является необходимость вычисления на каждом шаге не только левой части F (x) уравнения, но и ее первой производной.

Алгоритм метода Ньютона представлен на рис. 3.7. Из формулы (3.6) видно что для вычисления каждого нового (текущего) приближения требуется знать лишь од­но предыдущее приближение. Эти две величины в блок-схеме названы соответственно х Т и х П. После ввода исходных данных переменной х П присваивается значение () для того, чтобы первая проверка условия | х Т – х П | > обязательно дала значение True.

Рис.3.7. Алгоритм метода Ньютона

На практике иногда применяется так называемый модифицированный метод Ньютона, который отличается от метода Ньютона тем, что первая производная от F (x) вычисляется лишь один раз в точке х ₀. Вычислительный процесс модифицированного метода Ньютона описывается формулой:

(3.7)

а его геометрическая иллюстрация приведена на рис. 3.6.

Метод простых итераций

Исходное уравнение (3.1) преобразуем к эквивалентному уравнению:

x = (x).

(3.8)

Пусть известно начальное приближение (полученное, например, на этапе отделения корней): x = x ₀. Подставим его в правую часть (3.8) и получим новое приближение: x ₁ = (x ₀). Повторяя эту процедуру, будем иметь в общем виде на некотором k-м шаге:

x_k = (x_k-1).

В качестве условия окончания вычислительного процесса можно взять выполнение неравенства: ½ x_k - x_k-1 ½ < .

Значение x _k, удовлетворяющее ему, и есть корень уравнения (3.1).

Геометрическая интерпретация этого метода приведена на рис.3.8, 3.9. Здесь x ^* - истинное, искомое значение корня; x ₀ - начальное приближение к корню; x ₁, x ₂, x ₃ - оче­редные итерации.

Рис.3.8.

Рис.3.9.

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

Рис.3.10.

Рис.3.11.

Условием сходимости метода простых итераций является выполнение в окрестности искомого корня неравенства:

½ (x)½ < 1

(3.9)

Это условие является достаточным, т.е. если оно выполняется, то процесс обязательно схо­­дится; если же условие (3.9) не выполняется или выполняется не во всех точках

x ₀, x ₁, x ₂,..., x _k,...,

то заранее сказать что-либо конкретное о сходимости нельзя.

Итак, для решения уравнения F (x) = 0методом простых итераций надо преобразо­вать его к уравнению вида x = (x) так, чтобы выполнялось условие ½ (x)½ < 1. Схо­димость к истинному корню будет тем быстрее, чем ближе к единице значение (x).