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

Пусть корень уравнения f(x)=0 отделен на отрезке , причем первая и вторая производные f’(x) и f""(x) непрерывны и знакопостоянны при хÎ .

Пусть на некотором шаге уточнения корня получено (выбрано) очередное приближение к корню х n . Тогда предположим, что следующее приближение, полученное с помощью поправки h n , приводит к точному значению корня

x = х n + h n . (1.2.3-6)

Считаяh n малой величиной, представим f(х n + h n) в виде ряда Тейлора, ограничиваясь линейными слагаемыми

f(х n + h n) »f(х n) + h n f’(х n). (1.2.3-7)

Учитывая, что f(x) = f(х n + h n) = 0, получим f(х n) + h n f ’(х n) » 0.

Отсюда h n » - f(х n)/ f’(х n). Подставим значение h n в (1.2.3-6) и вместо точного значения корня x получим очередное приближение

Формула (1.2.3-8) позволяет получить последовательность приближенийх 1 ,х 2 , х 3 …, которая при определенных условиях сходится к точному значению корняx, то есть

Геометрическая интерпретация метода Ньютона состоит в следующем
(рис.1.2.3-6). Примем за начальное приближение x 0 правый конец отрезка b и в соответствующей точке В 0 на графике функции y = f(x) построим касательную. Точка пересечения касательной с осью абсцисс принимается за новое более точное приближение х 1 . Многократное повторение этой процедуры позволяет получить последовательность приближений х 0 , х 1 , х 2 , . . ., которая стремится к точному значению корня x.

Расчетная формула метода Ньютона (1.2.3-8) может быть получена из геометрического построения. Так в прямоугольном треугольнике х 0 В 0 х 1 катет
х 0 х 1 = х 0 В 0 /tga. Учитывая, что точка В 0 находится на графике функции f(x), а гипотенуза образована касательной к графику f(x) в точке В 0 , получим

(1.2.3-9)

(1.2.3-10)

Эта формула совпадает с (1.2.3-8) для n-го приближения.

Из рис.1.2.3-6 видно, что выбор в качестве начального приближения точки а может привести к тому, что следующее приближение х 1 окажется вне отрезка , на котором отделен корень x . В этом случае сходимость процесса не гарантирована. В общем случае выбор начального приближения производится в соответствии со следующим правилом: за начальное приближение следует принять такую точку х 0 Î,в которой f(х 0)×f’’(х 0)>0, то есть знаки функции и ее второй производной совпадают.

Условия сходимости метода Ньютона сформулированы в следующей теореме.

Если корень уравнения отделен на отрезке , причем f’(х 0)и f’’(х) отличны от нуля и сохраняют свои знаки при хÎ , то, если выбрать в качестве начального приближения такую точку х 0 Î, что f(х 0).f¢¢(х 0)>0, то корень уравнения f(x)=0может быть вычислен с любой степенью точности.

Оценка погрешности метода Ньютона определяется следующим выражением:

(1.2.3-11)

где -- наименьшее значение при

Наибольшее значение при

Процесс вычислений прекращается, если ,

где -- заданная точность.

Кроме того, условием достижения заданной точности при уточнении корня методом Ньютона могут служить следующие выражения:

Схема алгоритма метода Ньютона приведена на рис. 1.2.3-7.

Левая часть исходного уравнения f(x) и ее производная f’(x)в алгоритме оформлены в виде отдельных программных модулей.

Рис. 1.2.3-7. Схема алгоритма метода Ньютона

Пример 1.2.3-3.Уточнить методом Ньютона корни уравнения x-ln(x+2) = 0при условии, что корни этого уравнения отделены на отрезках x 1 Î[-1.9;-1.1] и x 2 Î [-0.9;2].

Первая производная f’(x) = 1 – 1/(x+2) сохраняет свой знак на каждом из отрезков:

f’(x)<0 при хÎ [-1.9; -1.1],

f’(x)>0 при хÎ [-0.9; 2].

Вторая производная f"(x) = 1/(x+2) 2 > 0 при любых х.

Таким образом, условия сходимости выполняются. Поскольку f""(x)>0на всей области допустимых значений, то для уточнения корня за начальное приближение x 1 выберем х 0 =-1,9(так какf(-1,9)×f”(-1.9)>0). Получим последовательность приближений:

Продолжая вычисления, получим следующую последовательность первых четырех приближений: -1.9; –1.8552, -1.8421; -1.8414. Значение функции f(x) в точке x=-1.8414 равно f(-1.8414)=-0.00003.

Для уточнения корня x 2 Î[-0.9;2] выберем в качестве начального приближениях 0 =2 (f(2)×f”(2)>0). Исходя из х 0 = 2, получим последовательность приближений: 2.0;1.1817; 1.1462; 1.1461. Значение функции f(x) в точке x=1.1461 равно f(1.1461)= -0.00006.

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

Метод хорд

Геометрическая интерпретация метода хорд состоит в следующем
(рис.1.2.3-8).

Проведем отрезок прямой через точки A и B. Очередное приближение x 1 является абсциссой точки пересечения хорды с осью 0х. Построим уравнение отрезка прямой:

Положим y=0и найдем значение х=х 1 (очередное приближение):

Повторим процесс вычислений для получения очередного приближения к корню - х 2 :

В нашем случае (рис.1.2.11) и расчетная формула метода хорд будет иметь вид

Эта формула справедлива, когда за неподвижную точку принимается точка b, а в качестве начального приближения выступает точка a.

Рассмотрим другой случай (рис. 1.2.3-9), когда .

Уравнение прямой для этого случая имеет вид

Очередное приближение х 1 при y = 0

Тогда рекуррентная формула метода хорд для этого случая имеет вид

Следует отметить, что за неподвижную точку в методе хорд выбирают тот конец отрезка , для которого выполняется условие f (x)∙f¢¢ (x)>0.

Таким образом, если за неподвижную точку приняли точку а, то в качестве начального приближения выступает х 0 = b, и наоборот.

Достаточные условия, которые обеспечивают вычисление корня уравнения f(x)=0 по формуле хорд, будут теми же, что и для метода касательных (метод Ньютона), только вместо начального приближения выбирается неподвижная точка. Метод хорд является модификацией метода Ньютона. Разница состоит в том, что в качестве очередного приближения в методе Ньютона выступает точка пересечения касательной с осью 0Х,а в методе хорд – точка пересечения хорды с осью 0Х – приближения сходятся к корню с разных сторон.

Оценка погрешности метода хорд определяется выражением

(1.2.3-15)

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

(1.2.3-16)

В случае, если M 1 <2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.

Пример 1.2.3-4. Уточнить корень уравнения e x – 3x = 0, отделенный на отрезке с точностью 10 -4 .

Проверим условие сходимости:

Следовательно, за неподвижную точку следует выбрать а=0, а в качестве начального приближения принять х 0 =1, поскольку f(0)=1>0 и f(0)*f"(0)>0.

Федеральное агентство по образованию

Сочинский государственный университет туризма и курортного дела

Факультет информационных технологий и математики

Кафедра общей математики

Курсовая работа по дисциплине

«Численные методы»

«Метод Ньютона и его модификации решения систем нелинейных уравнений»

Выполнила:

студентка 3 курса

группы 06-ИНФ

Лавренко М.В.

Проверил:

доцент, кандидат

педагогических наук

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

В данной курсовой работе рассматривается знаменитый метод Ньютона и его модификация решения систем нелинейных уравнений. Решение систем нелинейных уравнений – одна из трудных задач вычислительной математики. Трудность состоит в том, чтобы определить: имеет ли система решение, и, если – да, то сколько. Изучается сходимость основного и упрощенного методов Ньютона и метода, получаемого из метода Ньютона применением итерационного процесса для приближенного обращения матриц Якоби.

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

Знаменитый метод Ньютона является одним из наиболее эффективных методов решения самых разных нелинейных задач. Расчётную формулу метода можно получить, используя различные подходы. Рассмотрим два из них.

1) Метод касательных.

Выведем расчётную формулу метода для решения нелинейного уравнения

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

Уравнение касательной, проведённой к графику функции

в точке имеет вид: . (1.1)

Полагая в равенстве (1.1)

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

Выражая из него

, получаем расчётную формулу метода Ньютона : , . (1.3)

Благодаря такой геометрической интерпретации этот метод часто называют методом касательных .

Пусть требуется решить систему уравнений

(1) - заданные, нелинейные (среди них могут быть и линейные)

вещественнозначные функции п вещественных переменных

. Обозначив , ,

данную систему (2.1) можно записать одним уравнением

(2)

относительно векторной функции F векторного аргумента х. Таким образом, исходную задачу можно рассматривать как зада­чу о нулях нелинейного отображения

В этой постановке она является прямым обобщением основной задачи предыдущей главы - задачи построения методов нахождения нулей одномерных нелинейных отображений. Фактически это та же задача, только в пространствах большей размерности. Поэтому можно как заново строить методы ее решения на основе разработанных выше подходов, так и осуществлять формальный перенос выведенных для скалярного случая расчетных формул. В любом случае следует позаботиться о правомочности тех или иных операций над векторными переменными и векторными функциями, а также о сходимости получаемых таким способом итерационных процессов. Часто теоремы сходимости для этих процессов являются тривиальными обобщениями соответствующих результатов, полученных для методов решения скалярных уравнений. Однако не все результаты и не все методы можно перенести со случая п = 1 на случай п ≥2. Например, здесь уже не будут работать методы дихотомии, поскольку множество векторов не упорядочено. В то же время, переход от n = 1 до n ≥ 2 вносит в задачу нахождения нулей нелинейного отображения свою специфику, учет которой приводит к новым методам и к различным модификациям уже имеющихся. В частности, большая вариативность методов решения нелинейных систем связана с разнообразием способов, которыми можно решать линейные алгебраические задачи, возникающие при пошаговой линеаризации данной нелинейной вектор-функции F ( x ).

2) Метод линеаризации.

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

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

, где
(2.1)

в ряд Тейлора, причём члены, содержащие вторые и более высокие порядки производных, отбрасываются. Такой подход позволяет решение одной нелинейной системы (1.1) заменить решением ряда линейных систем.

Итак, систему (1.1) будем решать методом Ньютона. В области D выберем любую точку
и назовём её нулевым приближением к точному решению исходной системы. Теперь функции (2.1) разложим в ряд Тейлора в окрестности точки . Будем иметь

Т.к. левые части (2.2) должны обращаться в ноль согласно (1.1), то и правые части (2.2) тоже должны обращаться в ноль. Поэтому из (2.2) имеем

Все частные производные в (2.3) должны быть вычислены в точке .

(2.3) есть система линейных алгебраических уравнений относительно неизвестных Эту систему можно решить методом Крамера, если её основной определитель будет отличен от нуля и найти величины

Теперь можно уточнить нулевое приближение , построив первое приближение с координатами

т.е.
. (2.6)

Выясним, получено ли приближение (2.6) с достаточной степенью точности. Для этого проверим условие

,
(2.7)

где наперёд заданное малое положительное число (точность, с которой должна быть решена система (1.1)). Если условие (2.7) будет выполнено, то за приближённое решение системы (1.1) выберем (2.6) и закончим вычисления. Если же условие (2.7) выполняться не будет, то выполним следующее действие. В системе (2.3) вместо
возьмём уточнённые значения

, (2.8)

т.е. выполним следующие действия

. (2.9)

После этого система (2.3) будет системой линейных алгебраических уравнений относительно величин Определив эти величины, следующее второе приближение
к решению системы (1.1) найдём по формулам

Теперь проверим условие (2.7)

Если это условие выполняется, то заканчиваем вычисления, приняв за приближённое решение системы (1.1) второе приближение
. Если же это условие не выполняется, то продолжаем строить следующее приближение, приняв в (2.3)
Строить приближения нужно до тех пор, пока условие на не будет выполнено.

Рабочие формулы метода Ньютона для решения системы (1.1) можно записать в виде.

Вычислить последовательность

Здесь
являются решением системы

Сформулируем алгоритм вычислений по формулам (2.11)-(2.13).

1. Выберем нулевое приближение , принадлежащее области D.

2. В системе линейных алгебраических уравнений (2.13) положим
,а .

3. Решим систему (2.13) и найдём величины
.

4. В формулах (2.12) положим
и вычислим компоненты следующего приближения .

5. Проверим условие (2.7) на : (См. алгоритм вычисления максимума нескольких величин.)

6. Если это условие выполняется, то заканчиваем вычисления, выбрав за приближённое решение системы (1.1) приближение . Если же это условие не выполняется, то перейдём к п.7.

7. Положим
для всех .

8. Выполним п.3, положив
.

Геометрически этот алгоритм можно записать в виде.

Алгоритм. Вычисления максимума нескольких величин .

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

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

, (2.14)

здесь
. Выберем нулевое приближение
, принадлежащее области D. Построим систему линейных алгебраических уравнений (2.3). Она будет иметь вид

(2.15)

Обозначим

Решим систему (2.15) относительно неизвестных
, например методом Крамера. Формулы Крамера запишем в виде

(2.17)

где основной определитель системы (2.15)

(2.18)

а вспомогательные определители системы (2.15) имеют вид

.

Найденные значения подставим в (2.16) и найдём компоненты первого приближения
к решению системы (2.15).

Проверим условие

, (2.19)

если это условие выполняется, то заканчиваем вычисления, приняв за приближённое решение системы (2.15) первое приближение, т. е.
. Если условие (2.19) не выполняется, то положим
,
и построим новую систему линейных алгебраических уравнений (2.15). Решив её, найдём второе приближение
. Проверим его на . Если это условие будет выполняться, то за приближённое решение системы (2.15) выберем
. Если условие на не будет выполняться, положим
,
и построим следующую систему (2.15) для нахождения
и т. д.

Задания

Во всех заданиях требуется:

Составить программу численной реализации метода, согласно предложенному алгоритму.

Получить результаты вычислений.

Проверить полученные результаты.

Задана система двух нелинейных уравнений.

1.
2.

3.
4.

5.
6.

7.
8.

9.
10.

11.
12.

13.
14.

15.
.

Глава 3. Численные методы решения систем линейных алгебраических уравнений (СЛАУ).

Цель работы . Знакомство с некоторыми приближёнными методами решения СЛАУ и их численной реализацией на ПК.

Предварительные замечания. Все методы решения СЛАУ обычно разделяют на две большие группы. К первой группе относятся методы, которые принято называть точными. Эти методы позволяют для любых систем найти точные значения неизвестных после конечного числа арифметических операций, каждая из которых выполняется точно.

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

Рассмотрим некоторые приближённые методы решения СЛАУ и построим алгоритмы их численной реализации. Приближённое решение СЛАУ будем получать с точностью до , где некоторое очень маленькое положительное число.

1. Метод итерации.

Пусть СЛАУ задана в виде

(1.1)

Эту систему можно записать в матричном виде

, (1.2)

где
- матрица коэффициентов при неизвестных в системе (1.1),
- столбец свободных членов,
- столбец неизвестных системы (1.1).

. (1.3)

Решим систему (1.1) методом итерации. Для этого выполним следующие действия.

Во-первых. Выберем нулевое приближение

(1.4)

к точному решению (1.3) системы (1.1). Компонентами нулевого приближения могут быть любые числа. Но удобнее за компоненты нулевого приближения взять либо нули
, либо свободные члены системы (1.1)

Во-вторых. Компоненты нулевого приближения подставим в правую часть системы (1.1) и вычислим

(1.5)

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

В-третьих. Проверим нулевое и первое приближения на

(1.6)

Если все условия (1.6) выполняются, то за приближённое решение системы (1.1) выберем, либо , либо всё равно, т.к. они отличаются друг от друга не больше чем на и закончим вычисления. Если хотя бы одно из условий (1.6) не будет выполнено, то перейдём к следующему действию.

В-четвёртых. Выполним следующую итерацию, т.е. в правую часть системы (1.1) подставим компоненты первого приближения и вычислим компоненты второго приближения
, где

В-пятых. Проверим
и на , т.е. проверим условие (1.6) для этих приближений. Если все условия (1.6) будут выполнены, то за приближённое решение системы (1.1) выберем, либо , либо всё равно, т.к. они отличаются друг от друга не больше чем на . В противном случае будем строить следующую итерацию, подставив компоненты второго приближения в правую часть системы (1.1).

Итерации нужно строить до тех пор, пока два соседних приближения
и будут отличаться друг от друга не больше, чем на .

Рабочую формулу метода итерации решения системы (1.1) можно записать в виде

Алгоритм численной реализации формулы (1.7) может быть таким.

Достаточные условия сходимости метода итерации для системы (1.1) имеют вид

1.
, .

2.
,
.

3.

2. Метод простой итерации.

Пусть система линейных алгебраических уравнений (СЛАУ) задана в виде

(2.1)

Чтобы систему (2.1) решить методом простой итерации, её сначала надо привести к виду

(2.2)

В системе (2.2) -ое уравнение представляет собой -ое уравнение системы (2.1), разрешённое относительно –ой неизвестной (
).

Метод решения системы (2.1), состоящий в сведении её к системе (2.2) с последующим решением системы (2.2) методом итерации, называется методом простой итерации для системы (2.1).

Таким образом, рабочие формулы метода простой итерации решения системы (2.1) будут иметь вид

(2.3)

Формулы (2.3) можно записать в виде

Алгоритм численной реализации метода простой итерации для системы (2.1) по формулам (2.4) может быть таким.

Этот алгоритм можно записать геометрически.

Достаточные условия сходимости метода простой итерации для системы (2.1) имеют вид

1.
, .

2.
,
.

3.

3. Стационарный метод Зейделя.

Метод Зейделя решения СЛАУ отличается от метода итерации тем, что найдя какое-то приближение для -той компоненты, мы сразу же используем его для отыскания следующих
,
, …, -ой компонент. Такой подход позволяет обеспечить более высокую скорость сходимости метода Зейделя по сравнению с методом итерации.

Пусть СЛАУ задана в виде

(3.1)

Пусть
- нулевое приближение к точному решению
системы (3.1). И пусть найдено -ое приближение
. Определим компоненты
-ого приближения по формулам

(3.2)

Формулы (3.2) можно записать в компактном виде

,
,
(3.3)

Алгоритм численной реализации метода Зейделя решения системы (3.1) по формулам (3.3) может быть таким.

1. Выберем , например,
,

2. Положим .

3. Для всех вычислим .

4. Для всех проверим условия
.

5. Если все условия в п.4 будут выполнены, то за приближенное решение системы (3.1) выберем либо , либо и закончим вычисления. Если хотя бы одно условие в п.4 не будет выполнено, перейдем к п.6.

6. Положим и перейдем к п.3.

Этот алгоритм можно записать геометрически.

Достаточное условие сходимости метода Зейделя для системы (3.1) имеет вид
, .

4. Нестационарный метод Зейделя.

Этот метод решения СЛАУ (3.1) обеспечивает еще более высокую скорость сходимости метода Зейделя.

Пусть каким-либо образом для системы (3.1) найдены компоненты -ого приближения и -ого приближения .

Вычислим вектор поправки

Подсчитаем величины

, (4.2)

Расположим величины
, в порядке их убывания.

В таком же порядке перепишем уравнения в системе (3.1) и неизвестные в этой системе., : Линейная алгебра и нелинейные ... Руководство для лабораторных работ по ... методические указания для практических работ по для студентов ...

Учебная литература (естественные науки и технические) 2000-2011 цикл опд – 10лет цикл сд – 5 лет

Литература

... Естественные науки в целом 1. Астрономия [Текст] : пособие для ... Численные методы : Линейная алгебра и нелинейные ... Руководство для лабораторных работ по ... методические указания для практических работ по дисциплине "Экономика транспорта" для студентов ...

- естественные науки (1)

Учебное пособие

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

- естественные науки - физико-математические науки - химические науки - науки о земле (геодезические геофизические геологические и географические науки)

Документ

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

- естественные науки - физико-математические науки - химические науки - науки о земле (геодезические геофизические геологические и географические науки) (7)

Список учебников

Определитель Еремина в линейной и нелинейной алгебре : линейное и нелинейное программирование: новый метод / Еремин, Михаил... Для студентов и преподавателей геологических специальностей вузов. кх-1 1794549 99. Д3 П 693 Практическое руководство по ...

Например:

Поставим задачу отыскать действительные корни данного уравнения.

А таковые точно есть! – из статей о графиках функций и уравнениях высшей математики вы хорошо знаете, что график функции-многочлена нечётной степени хотя бы один раз пересекает ось , следовательно, наше уравнение имеет по меньшей мере один действительный корень. Один. Или два. Или три.

Сначала напрашивается проверить, наличие рациональных корней. Согласно соответствующей теореме , на это «звание» могут претендовать лишь числа 1, –1, 3, –3, и прямой подстановкой легко убедиться, что ни одно из них «не подходит». Таким образом, остаются иррациональные значения. Иррациональный корень (корни) многочлена 3-й степени можно найти точно (выразить через радикалы) с помощью так называемых формул Кардано , однако этот метод достаточно громоздок. А для многочленов 5-й и бОльших степеней общего аналитического метода не существует вовсе, и, кроме того, на практике встречается множество других уравнений, в которых точные значения действительных корней получить невозможно (хотя они существуют).

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

Зададим для нашего примера точность . Что это значит? Это значит, что нам нужно отыскать ТАКОЕ приближённое значение корня (корней) , в котором мы гарантированно ошибаемся, не более чем на 0,001 (одну тысячную) .

Совершенно понятно, что решение нельзя начинать «наобум» и поэтому на первом шаге корни отделяют . Отделить корень – это значит найти достаточно малый (как правило, единичный) отрезок, которому этот корень принадлежит, и на котором нет других корней. Наиболее прост и доступен графический метод отделения корней . Построим поточечно график функции :

Из чертежа следует, что уравнение , судя по всему, имеет единственный действительный корень , принадлежащий отрезку . На концах данного промежутка функция принимает значения разных знаков: , и из факта непрерывности функции на отрезке сразу виден элементарный способ уточнения корня: делим промежуток пополам и выбираем тот отрезок, на концах которого функция принимает разные знаки. В данном случае это, очевидно, отрезок . Делим полученный промежуток пополам и снова выбираем «разнознаковый» отрезок. И так далее. Подобные последовательные действия называют итерациями . В данном случае их следует проводить до тех пор, пока длина отрезка не станет меньше удвоенной точности вычислений , и за приближённое значение корня следует выбрать середину последнего «разнознакового» отрезка.

Рассмотренная схема получила естественное название – метод половинного деления . И недостаток этого метода состоит в скорости. Медленно. Очень медленно. Слишком много итераций придётся совершить, прежде чем мы достигнем требуемой точности. С развитием вычислительной техники это, конечно, не проблема, но математика – на то и математика, чтобы искать наиболее рациональные пути решения.

И одним из более эффективных способов нахождения приближённого значения корня как раз и является метод касательных . Краткая геометрическая суть метода состоит в следующем: сначала с помощью специального критерия (о котором чуть позже) выбирается один из концов отрезка. Этот конец называют начальным приближением корня, в нашем примере: . Теперь проводим касательную к графику функции в точке с абсциссой (синяя точка и фиолетовая касательная) :

Данная касательная пересекла ось абсцисс в жёлтой точке, и обратите внимание, что на первом шаге мы уже почти «попали в корень»! Это будет первое приближение корня . Далее опускаем жёлтый перпендикуляр к графику функции и «попадаем» в оранжевую точку. Через оранжевую точку снова проводим касательную, которая пересечёт ось ещё ближе к корню! И так далее. Нетрудно понять, что, используя метод касательных, мы приближаемся к цели семимильными шагами, и для достижения точности потребуется буквально несколько итераций.

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

Пример 1

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

Перед вами «щадящая версия» задания, в которой сразу констатируется наличие единственного действительного корня.

Решение : на первом шаге следует отделить корень графически. Это можно сделать путём построения графика (см. иллюстрации выше) , но такой подход обладает рядом недостатков. Во-первых, не факт, что график прост (мы же заранее не знаем) , а программное обеспечение – оно далеко не всегда под рукой. И, во-вторых (следствие из 1-го) , с немалой вероятностью получится даже не схематичный чертёж, а грубый рисунок, что, разумеется, не есть хорошо.

Ну а зачем нам лишние трудности? Представим уравнение в виде , АККУРАТНО построим графики и отметим на чертеже корень («иксовую» координату точки пересечения графиков) :

Очевидное преимущество этого способа состоит в том, что графики данных функций строятся от руки значительно точнее и намного быстрее. Кстати, заметьте, что прямая пересекла кубическую параболу в единственной точке, а значит, предложенное уравнение и в самом деле имеет только один действительный корень. Доверяйте, но проверяйте;-)

Итак, наш «клиент» принадлежит отрезку и «на глазок» примерно равен 0,65-0,7.

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

Найдём первую и вторую производные функции :

и проверим левый конец отрезка:

Таким образом, ноль «не подошёл».

Проверяем правый конец отрезка:

– всё хорошо! В качестве начального приближения выбираем .

На третьем шаге нас ожидает дорога к корню. Каждое последующее приближение корня рассчитывается на основании предшествующих данных с помощью следующей рекуррентной формулы:

Процесс завершается при выполнении условия , где – заранее заданная точность вычислений. В результате за приближённое значение корня принимается «энное» приближение: .

На очереди рутинные расчёты:

(округление обычно проводят до 5-6 знаков после запятой)

Поскольку полученное значение больше , то переходим к 1-му приближению корня:

Вычисляем:

, поэтому возникает потребность перейти ко 2-му приближению:

Заходим на следующий круг:

, таким образом, итерации закончены, и в качестве приближённого значения корня следует взять 2-е приближение, которое в соответствии с заданной точностью нужно округлить до одной тысячной:

На практике результаты вычислений удобно заносить в таблицу, при этом, чтобы несколько сократить запись, дробь часто обозначают через :

Сами же вычисления по возможности лучше провестив Экселе – это намного удобнее и быстрее:

Ответ : с точностью до 0,001

Напоминаю, что эта фраза подразумевает тот факт, что мы ошиблись в оценке истинного значения корня не более чем на 0,001. Сомневающиеся могут взять в руки микрокалькулятор и ещё раз подставить приближенное значение 0,674 в левую часть уравнения .

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

Что делать в таких случаях? Проверить выполнение указанных условий (см. выше по ссылке) , и при необходимости уменьшить отрезок. Так, условно говоря, если бы в разобранном примере нам не подошёл промежуток , то следовало бы рассмотреть, например, отрезок . На практике мне такие случаи встречались , и этот приём реально помогает! То же самое нужно сделать, если оба конца «широкого» отрезка не удовлетворяют условию (т.е. ни один из них не годится на роль начального приближения) .

Но обычно всё работает, как часы, хотя и не без подводных камней:

Пример 2

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

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

А поэтому решение начинаем со спасительного трюка: представим уравнение в виде и изобразим графики :


Из чертежа следует, что наше уравнение имеет два действительных корня:

Алгоритм, как вы понимаете, нужно «провернуть» дважды. Но это ещё на самый тяжелый случай, бывает, исследовать приходится 3-4 корня.

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

Тестируем левый конец отрезка:

– подошёл!

Таким образом, – начальное приближение.

Уточнение корня проведем методом Ньютона, используя рекуррентную формулу:
– до тех пор, пока дробь по модулю не станет меньше требуемой точности:

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


По этой же причине следует проявить повышенное внимание при переходе к каждому следующему приближению:

Несмотря на достаточно высокое требование к точности, процесс опять завершился на 2-м приближении: , следовательно:

С точностью до 0,0001

2) Найдем приближённое значение корня .

Проверяем на «вшивость» левый конец отрезка:

, следовательно, он не годится в качестве начального приближения.

Задача о нахождении решений системы из n нелинейных алгебраических или трансцендентных уравнений сn неизвестными вида

	f 1(x 1, x 2, … x n ) = 0,
	f 2(x 1, x 2, … x n ) = 0,
	……………………
	f n (x 1 ,x 2 ,… x n ) = 0,

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

В векторных обозначениях систему (6.1) можно записать в более компактной форме

вектор столбец функций, символом () T обозначена операция транспони-

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

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

Метод простой итерации для систем нелинейных уравнений по существу является обобщением одноименного метода для одного уравнения. Он основан на том, что система уравнений (6.1) приводится к виду

x 1= g 1(x 1, x 2, … , x n ) , x 2= g 2(x 1, x 2, … , x n ) ,

……………………

x n= g n(x 1 , x 2 , … , x n) ,

и итерации проводятся по формулам

x 1 (k + 1 )= g 1 (x 1 (k ), x 2 (k ), … , x n (k )) , x 2 (k + 1 )= g 2 (x 1 (k ), x 2 (k ), … , x n (k )) ,

……………………………

x n (k + 1 )= g n (x 1 (k ), x 2 (k ), … , x n (k )) .

Здесь верхний индекс указывает на номер приближения. Итерационный процесс (6.3) начинается с некоторого начального приближения

(x 1 (0 ) ,x 2 (0 ) ,… ,x n (0 ) ) и продолжаются до тех пор, пока модули приращений

всех аргументов после одной k- итерации не станут меньше заданной величиныε :x i (k + 1 ) − x i (k ) < ε дляi = 1,2,… ,n .

Хотя метод простой итерации прямо ведет к решению и легко программируется, он имеет два существенных недостатка. Один из них – медленная сходимость. Другой состоит в том, что если начальное приближение выбрано далеко от истинного решения (X 1 ,X 2 ,… ,X n ) , то сходимость

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

Решить систему нелинейных уравнений:

	(x ...		) =0
F n (x 1 ...		x n) = 0 .

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

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

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

В случае одного уравнения F (x ) = 0 алгоритм метода Ньютона был легко получен путем записи уравнений касательной к кривойy = F (x ) . В основе метода Ньютона для систем уравнений лежит использование разложения функцийF 1 (x 1 ...x n ) в ряд Тейлора, причем члены, содержа-

щие вторые (и более высоких порядков) производные, отбрасываются. Пусть приближенные значения неизвестных системы (4.1) равны со-

ответственно a 1 ,a 2 ,....,a n . Задача состоит в нахождении приращений (по-

правок) к этим значениям	x 1 ,x 2 ,...,	x n , благодаря которым решение сис-
темы запишется в виде:
x 1= a 1+ x 1,	x 2= a 2+	x 2 , .... ,x n = a n + x n .

Проведем разложение левых частей уравнений (4.1) с учетом разложения в ряд Тейлора, ограничиваясь лишь линейными членами относи-

тельно приращений:
F1 (x1 ... xn ) ≈ F1 (a1 ... an ) +	∂ F 1	x 1+		+ ∂ F 1		x n,
	∂x			∂x
F2 (x1 ... xn ) ≈ F2 (a1 ... an ) +	∂ F 2	x 1+			∂ F 2	x n,
	∂x				∂x
...................................
F n(x 1 ... x n) ≈ F n(a 1 ... a n) +	∂ F n	x 1+			∂ F n	xn .
	∂x				∂x

Подставляя в систему (4.1), получим следующую систему линейных алгебраических уравнений относительно приращений:

∂ F 1			∂ F 1			+ ∂ F 1			= −F ,
∂x			∂x			∂x
∂ F 2			∂ F 2				∂ F 2		= −F ,
∂x			∂x				∂x
..............................
∂ F n			∂ F n				∂ F n		= −F .
∂x			∂x				∂x
Значения F 1 ...				производные				вычисляются при

x 2 = a 2 , …x n = a n .

Определителем системы (4.3) является якобиан:

∂ F 1		∂ F 1
∂x		∂x
∂ F 2		∂ F 2
J = ∂ x		∂ x.

… … … …

∂ F n… … ∂ F n∂ x 1 ∂ x n

x 1= a 1,

Для существования единственного решения системы якобиан должен быть отличен от нуля на каждой итерации.

Таким образом, итерационный процесс решения системы уравнений методом Ньютона состоит в определении приращений x 1 ,x 2 , ...,x n к значениям неизвестных на каждой итерации путем решения системы линейных алгебраических уравнений (4.3). Счет прекращается, если все приращения становятся малыми по абсолютной величине: maxx i < ε . В ме-

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

В качестве примера рассмотрим использование метода Ньютона для решения системы двух уравнений:

∂ ∂ F 1. x

Величины, стоящие в правой части, вычисляются при x = a ,y = b .

Если выполняются условия		y − b		< εи		x − a			при заданном M , то
выводятся значения x иy ,	в противном случае								происходит вывод
x ,y ,M .

← Вернуться