Метод Ньютона для решения нелинейных уравнений

1.2 Алгоритм метода Ньютона

Построим эффективный алгоритм вычисления корней уравнения. Пусть задано начальное приближение . Вычислим в этой точке значение функции и её производной . Рассмотрим графическую иллюстрацию метода:

.
Далее получим следующее приближение в точке , проводя касательную из точки () до пересечения с осью абсцисс:

(8)
Продолжая этот процесс, получим известную формулу Ньютона:
(9)
y

x

Рис. 1.
Приведем простейшую рекурсивную подпрограмму-функцию:

function X_Newt(x,eps:real):real;

var y:real;

begin

y:=x-f(x)/f1(x);

if abs(f(x)) > eps

then X_Newt:=X_Newt(y,eps)

else X_Newt:=y

end;

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

Преобразуем уравнение (1) к эквивалентному уравнению вида:
x=g(x) (10)
В случае метода касательных . Если известно начальное приближение к корню x=x₀, то следующее приближение найдем из уравнения x₁=g(x₀), далее x₂=g(x₁),... Продолжая этот процесс, получим рекуррентную формулу метода простой итерации
x_k+1=g(x_k) (11)
Итерационный процесс продолжается до тех пор, пока не будут выполнены условия (5-7).

Всегда ли описанный вычислительный процесс приводит к искомому решению? При каких условиях он будет сходящимся? Для ответа на эти вопросы опять обратимся к геометрической иллюстрации метода.

Корень уравнения представляется точкой пересечения функций y=x и y=g(x). Как видно из рис. 3(а), если выполняется условие , то процесс сходится, иначе – расходится (рис3(б)).

(a) (б)

Рис. 3.
Итак, для того чтобы итерационный процесс был сходящимся и приводил к искомому результату, требуется выполнение условия:
(12)
Переход от уравнения f(x)=0 к уравнению х=g(x) можно осуществлять различными способами. При этом важно, чтобы выбранная функция g(x) удовлетворяла условию (12). К примеру, если функцию f(x) умножить на произвольную константу q и добавить к обеим частям уравнения (1) переменную х, то g(x)=q*f(x)+x . Выберем константу q такой, чтобы скорость сходимости алгоритма была самой высокой. Если 1Метод Ньютона обладает высокой скоростью сходимости, однако он не всегда сходится. Условие сходимости , где g(x) = x – f(x)/ f’(x), сводится к требованию .

В практических расчетах важно выбирать начальное значение как можно ближе к искомому значению, а в программе устанавливать «предохранитель от зацикливания».

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

(13)
Другой метод модификации – замена производной конечной разностью
(14)
Тогда (15)
Геометрический смысл такого изменения алгоритма Ньютона состоит в том, что от касательной мы приходим к секущей. Метод секущих уступает методу Ньютона в скорости сходимости, но не требует вычисления производной. Заметим, что начальные приближения в методе секущих могут располагаться как с разных сторон от корня, так и с одной стороны.

Запишем в общем виде алгоритм метода Ньютона.

1. Задать начальное приближение х⁽⁰⁾ так, чтобы выполнилось условие
f(x⁽⁰⁾)*f’’(x⁽⁰⁾)>0. (16)
Задать малое положительное число ε , как точность вычислений. Положить к = 0.

2. Вычислить х^(к+1) по формуле (9) :

.
3. Если | x^(k+1) - x^(k) | < ε, то процесс вычисления прекратить и положить х* = x^(k+1). Иначе увеличить к на 1 (к = к + 1) и перейти к пункту 2.
II. Практический раздел
Решим вручную несколько нелинейных уравнений методом Ньютона, а потом сверим результаты с теми, которые получатся при реализации программного продукта.
Пример 1
Решить уравнение методом Ньютона.
sin x² + cos x² - 10x. = 0.
Вычисления производить с точностью ε = 0, 001.

Решение:

Вычислим первую производную функции.
F’(x)=2x cos x² - 2x sin x² - 10.
Теперь вычислим вторую производную от функции.
F’’(x)=2cos x² - 4 x²sin x² - 2sin x² - 4 x²cos x² = cos x² (2-4 x² ) - sin x² (2+4x²).
Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x⁽⁰⁾) * f’’(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 0, 565, тогда f(0. 565)*f’’(0. 565) = -4. 387 * (-0. 342) = 1. 5 > 0,

Условие выполняется, значит берём x⁽⁰⁾ = 0, 565.

Теперь составим таблицу значений, для решения данного уравнения.

k	x(k)	f(x(k))	f’(x(k))	| x(k+1) - x(k) |
0	0. 565	-4. 387	-9. 982	0. 473
1	0. 092	0. 088	-9. 818	0. 009
2	0. 101	0. 000	-9. 800	0. 000
3	0. 101

Отсюда следует, что корень уравнения х = 0, 101.

Пример 2
Решить уравнение методом Ньютона.
cos x – e^-x2/2 + x - 1 = 0
Вычисления производить с точностью ε = 0, 001.

Решение:

Вычислим первую производную функции.
F’(x) = 1 – sin x + x*e^-x2/2.
Теперь вычислим вторую производную от функции.
F’’(x) = e^-x2/2 *(1-x²) – cos x.
Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x⁽⁰⁾) * f’’(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 2, тогда f(2)*f’’(2) = 0. 449 * 0. 010 = 0.05 > 0,

Условие выполняется, значит берём x⁽⁰⁾ = 2.

Теперь составим таблицу значений, для решения данного уравнения.

k	x(k)	f(x(k))	f’(x(k))	| x(k+1) - x(k) |
0	2	0. 449	0. 361	1. 241
1	-0. 265	0. 881	0. 881	0. 301
2	-0. 021	0. 732	0. 732	0. 029
3	0. 000	0. 716	0. 716	0. 000
4	1. 089

Отсюда следует, что корень уравнения х = 1. 089.

Пример 3
Решить уравнение методом Ньютона.
x² - e^-x = 0.
Вычисления производить с точностью ε = 0, 001.

Решение:

Вычислим первую производную функции.
F’(x) = 2*x + e^-x.
Теперь вычислим вторую производную от функции.
F’’(x) = 2 - e^-x.
Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x⁽⁰⁾) * f’’(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 1, тогда f(2)*f’’(2) = 0. 632 * 1, 632 = 1, 031 > 0,

Условие выполняется, значит берём x⁽⁰⁾ = 1.

Теперь составим таблицу значений, для решения данного уравнения.

k	x(k)	f(x(k))	f’(x(k))	| x(k+1) - x(k) |
0	1, 000	0, 632	2, 368	0, 267
1	0, 733	0, 057	1, 946	0, 029
2	0, 704	0, 001	1, 903	0, 001
3	0, 703

Отсюда следует, что корень уравнения х = 0, 703.

Пример 4.

Решить уравнение методом Ньютона.

cos x –e^-x/2+x-1=0.
Решение:

Вычислим первую производную функции.

F’(x) = -sin x + e^-x/2/2+1.
Теперь вычислим вторую производную от функции.
F’’(x) = -cos x - e^-x/2 /4.
Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x⁽⁰⁾) * f’’(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 1, тогда f(2)*f’’(2) = -0. 066 * (-0. 692) = 0. 046 > 0,

Условие выполняется, значит берём x⁽⁰⁾ = 1.

Теперь составим таблицу значений, для решения данного уравнения.

k	x(k)	f(x(k))	f’(x(k))	| x(k+1) - x(k) |
0	1, 000	-0. 066	0. 462	0. 143
1	1. 161	-0. 007	0. 372	0. 018
2	1. 162	0. 0001.	0. 363	0. 001
3	1. 162

Отсюда следует, что корень уравнения х = 1. 162.

Пример 5
Решить уравнение методом Ньютона.
-2+e^x- e^-x =0.
Решение:

Вычислим первую производную функции.

F’(x) = e^x+e^-x.
Теперь вычислим вторую производную от функции.
F’’(x) = e^x-e^-x.
Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x⁽⁰⁾) * f’’(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 1, тогда f(2)*f’’(2) = 0. 350 * 2, 350 = 0. 823 > 0,

Условие выполняется, значит берём x⁽⁰⁾ = 1.

Теперь составим таблицу значений, для решения данного уравнения.

k	x(k)	f(x(k))	f’(x(k))	| x(k+1) - x(k) |
0	1, 000	0, 350	3, 086	0, 114
1	0, 886	0, 013	2, 838	0, 005
2	0, 881	0, 001	2, 828	0, 000
3	0, 881

Отсюда следует, что корень уравнения х = 0, 881.

III. Разработка программного продукта

3.1 Описание программы

Данная программа создана для работы в текстовом и графическом режиме. Она состоит из модуля Graph, Crt, трёх функций и трёх процедур.

1. 
   модуль Crt предназначен для обеспечения контроля над текстовыми режимами экрана, расширенными кодами клавиатуры, цветами, окнами и звуком;
   
2. 
   модуль Graph предназначен для обеспечения контроля над графическими объектами;
   
3. 
   procedure GrafInit - инициализирует графический режим;
   
4. 
   function VF – вычисляет значение функции;
   
5. 
   function f1 – вычисляет значение первой производной функции;
   
6. 
   function X_Newt – реализует алгоритм решения уравнения методом Ньютона.
   
7. 
   procedure FGraf – реализует построение графика заданной функции f(x);
   

Ots=35 - константа, определяющая количество точек для отступа от границ монитора;

fmin, fmax – максимальные и минимальные значения функции;

SetColor(4) – процедура, которая устанавливает текущий цвет графического объекта, используя палитру, в данном случае это красный цвет;

SetBkColor(9) – процедура, которая устанавливает текущий цвет фона, используя палитру, в данном случае – это светло-синий цвет.

8. 
   Procedure MaxMinF – вычислят максимальные и минимальные значения функции f(x).
   

Line – процедура, которая рисует линию из точки с координатами (x1, у1) в точку с координатами (х2, у2);

MoveTo – процедура, перемещающая указатель (СР) в точку с координатами (х, у);

TextColor(5) – процедура, устанавливающая текущий цвет символов, в данном случае – это розовый;

Outtexty(х, у, ‘строка’) – процедура, которая выводит строку, начиная с позиции (х, у)

CloseGraph – процедура, закрывающая графическую систему.

3.2 Тестирование программы

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

1. 
   sin x² + cos x² - 10x. = 0.
   

Тест:

Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке [a, b].

Введите а = -1

Введите b=1
[a, b] = [-1, 1]
Введите точность вычисления eps=0. 01

{вывод графика функции}

Корень уравнения, найденный методом Ньютона:
x = 0.101.

сделаем проверку, подставив полученный ответ в уравнение.

Получим : х=0, 0000002
2) cos x – e^-x2/2 + x - 1 = 0.
Тест:

Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке [a, b].

Введите а = -3

Введите b=3

[a, b] = [-3, 3]
Введите точность вычисления eps=0. 001

{вывод графика функции}

Корень уравнения, найденный методом Ньютона:
x = 1.089.
сделаем проверку, подставив полученный ответ в уравнение.

Получим : х=-0, 0000000

3) x² - e^-x = 0.
Тест:

Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке [a, b].

Введите а = -1

Введите b=1

[a, b] = [-1, 1]
Введите точность вычисления eps=0. 01

{вывод графика функции}

Корень уравнения, найденный методом Ньютона:
x = 0.703.
сделаем проверку, подставив полученный ответ в уравнение.

Получим : х=0, 0000000

4) cos x –e^-x/2+x-1=0.
Тест:

Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке [a, b].

Введите а = -1,5

Введите b=1,5

[a, b] = [-1,5, 1,5 ]
Введите точность вычисления eps=0. 001

{вывод графика функции}

Корень уравнения, найденный методом Ньютона:
x = 1,164.

сделаем проверку, подставив полученный ответ в уравнение.

Получим : х=0, 0008180
5) -2+e^x- e^-x =0.
Тест:

Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке [a, b].

Введите а = -0,9

Введите b=0,9

[a, b] = [-0,9, 0,9]
Введите точность вычисления eps=0. 001

{вывод графика функции}

Корень уравнения, найденный методом Ньютона:
x = 0.881.
Сделаем проверку, подставив полученный ответ в уравнение.

Получим : х=0, 0000000

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

1.Изучена необходимая литература.

2.Обзорно рассмотрены существующие методы по решению нелинейных уравнений.

3.Изучен метод Ньютона для решения нелинейных уравнений.

4.Рассмотрено решение нелинейных уравнений методом Ньютона на примере.

5.Проведены тестирование и отладка программы.

Список используемой литературы

1. 
   Б.П. Демидович, И.А Марон. Основы вычислительной математики. – Москва, изд. «Наука»; 1970.
   
2. 
   В.М. Вержбицкий. Численные методы (линейная алгебра и нелинейные уравнения). – Москва, «Высшая школа»; 2000.
   
3. 
   Н.С.Бахвалов, А.В.Лапин, Е.В.Чижонков. Численные методы в задачах и упражнениях. – Москва, «Высшая школа»; 2000.
   
4. 
   Мэтьюз, Джон, Г.,Финк, Куртис, Д. Численные методы MATLAB, 3-е издание.- Москва, «Вильяс»; 2001.