Расчет адх вка клипера методом ньютона. Численные методы решения нелинейных уравнений

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

Пусть корень уравнения 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.

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 Практическое руководство по ...

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

Метод был описан Исааком Ньютоном в рукописи De analysi per aequationes numero terminorum infinitas (лат.О б анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу , и в работе De metodis fluxionum et serierum infinitarum (лат.Метод флюксий и бесконечные ряды) или Geometria analytica (лат.Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения x n , а последовательность полиномов и в результате получал приближённое решение x.

Впервые метод был опубликован в трактате Алгебра Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работеAnalysis aequationum universalis (лат. Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений x n вместо более трудной для понимания последовательности полиномов, использованной Ньютоном.

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

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

Рис.1 . График изменение функции

Проведенная в любой точке касательная линия к графику функции определяется производной данной функции в рассматриваемой точке, которая в свою очередь определяется тангенсом угла α (). Точка пересечения касательной с осью абсцисс определяется исходя из следующего соотношения в прямоугольном треугольнике: тангенс угла в прямоугольном треугольнике определяется отношением противолежащего катета к прилежащему катету треугольнику. Таким образом, на каждом шаге строится касательная к графику функции в точке очередного приближения . Точка пересечения касательной с осью Ox будет являться следующей точкой приближения . В соответствии с рассматриваемым методом расчет приближенного значения корня на i -итерации производится по формуле:

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

Условием окончания итерационного процесса является выполнение следующего условия:

где ˗ допустимая погрешность определения корня.

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

Математическое обоснование

Пусть дана вещественная функция , которая определена и непрерывна на рассматриваемом участке. Необходимо найти вещественный корень рассматриваемой функции.

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

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

Производная сжимающего отображения определяется в следующем виде:

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

С учетом этого сжимающая функция прием следующий вид:

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

Алгоритм нахождения корня нелинейного уравнения по методу

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

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

3. Проверяем приближенное значение корня на предмет заданной точности, в случае:

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

Если разность двух последовательных приближений не достигает необходимой точности , то необходимо продолжить итерационный процесс и перейти к п.2 рассматриваемого алгоритма.

Пример решения уравнений

по методу Ньютона для уравнения с одной переменной

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

Вариант решения нелинейного уравнения в программном комплексе MathCAD представлен на рисунке 3.

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

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

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

Рис.3 . Листинг программы в MathCad

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

Существует несколько модификаций метода Ньютона, которые направлены на упрощение вычислительного процесса.

Упрощенный метод Ньютона

В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что ведет к увеличению вычислительных затрат. Для уменьшения затрат, связанных с вычислением производной на каждом шаге расчета, можно произвести замену производной f’(x n ) в точке x n в формуле на производную f’(x 0) в точке x 0 . В соответствии с данным методом расчета приближенное значение корня определяется по следующей формуле: Модифицированный метод Ньютона

Разностный метод Ньютона

В результате приближенное значение корня функции f(x) будет определяться выражением разностного метода Ньютона:

Двух шаговый метод Ньютона

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

В результате приближенное значение корня функции f(x) будет определяться следующим выражением:

где

Рис.5 . Двух шаговый метод Ньютона

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

• Назад
• Вперёд

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

Задача о нахождении решений системы из 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 .



Ключевые слова:

Цель работы: изучить методы решения нелинейных уравнений с одним неизвестным и апробировать их в опытно-экспериментальной работе.

Задачи работы:

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

‒ Шаговый метод

‒ Метод деления пополам

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

Введение.

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

Шаговый метод.

Пусть требуется решить нелинейное уравнение вида уравнение F(x)=0. Предположим также, что нам задан некоторый интервал поиска . Требуется найти интервал [а,b] длиной h, содержащий первый корень уравнения, начиная с левой границы интервала поиска.

Рис. 1. Шаговый метод

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

I этап. Отделение корней.

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

• Подставляем значения X (желательно с каким-то достаточно мелким шагом) и смотрим где функция сменит знак. Если функция сменила знак, это значит, что на участке между предыдущим и текущим значением X лежит корень (если функция не меняет характер возрастания/убывания, то можно утверждать, что корень на этом интервале один).
• Графический метод. Строим график и оцениваем на каких интервалах лежит один корень.
• Исследуем свойства конкретной функции.

II этап. Уточнение корней.

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

Метод половинного деления

Быстрый и достаточно простой численный метод решения уравнений, основанный на последовательном сужении интервала, содержащего единственный корень уравнения F(x)=0 до того времени, пока не будет достигнута заданная точность Е. Данный метод обычно используется при решении квадратных уравнений и уравнений высших степеней. Однако у данного метода есть существенный недостаток - если на отрезке [а,b] содержится более одного корня, то с его помощью не удастся добиться хороших результатов.

Рис. 2. Метод дихотомии

Алгоритм данного метода следующий:

‒ Определить новое приближение корня х в середине отрезка [а;b]: х=(а+b)/2.

‒ Найти значения функции в точках а и х: F(a) и F(x).

‒ Проверить условие F(a)*F(x)

‒ Перейти к пункту 1 и вновь поделить отрезок пополам. Алгоритм продолжить до того времени, пока не будет выполнено условие |F(x)|

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

Самый точный из численных методов решения; подходит для решения очень сложных уравнений, но усложняется необходимостью вычисления производных на каждом шаге. заключается в том, что если x n - некоторое приближение к корню уравнения , то следующее приближение определяется как корень касательной к функции f(x), проведенной в точке x n .

Уравнение касательной к функции f(x) в точке x n имеет вид:

В уравнении касательной положим y = 0 и x = x n +1 .

Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:

Сходимость метода касательных квадратичная, порядок сходимости равен 2.

Таким образом, сходимость метода касательных Ньютона очень быстрая.

Без всяких изменений метод обобщается на комплексный случай. Если корень x i является корнем второй кратности и выше, то порядок сходимости падает и становится линейным.

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

Метод Ньютона (метод касательных) обычно применяется в том случае, если уравнение f(x) = 0 имеет корень , и выполняются условия:

1) функция y= f(x) определена и непрерывна при ;

2) f(a)·f(b) (функция принимает значения разных знаков на концах отрезка [a;b ]);

3) производные f"(x) и f""(x) сохраняют знак на отрезке [a;b ] (т. е. функция f(x) либо возрастает, либо убывает на отрезке [a;b ], сохраняя при этом направление выпуклости);

Смысл метода заключается в следующем: на отрезке [a;b ] выбирается такое число x 0 , при котором f(x 0) имеет тот же знак, что и f""(x 0), т. е. выполняется условие f(x 0)·f""(x) > 0 . Таким образом, выбирается точка с абсциссой x 0 , в которой касательная к кривой y=f(x) на отрезке [a;b ] пересекает ось Ox . За точку x 0 сначала удобно выбирать один из концов отрезка.

Рассмотрим данный алгоритм на конкретном примере.

Пусть нам дана возрастающая функция y = f(x) =x 2– 2, непрерывная на отрезке (0;2), и имеющая f "(x) =2x>0 и f ""(x) = 2> 0 .

В нашем случае уравнение касательной имеет вид: y-y 0 =2x 0 ·(x-x 0). В качестве точки x 0 выбираем точку B 1 (b; f(b)) = (2,2). Проводим касательную к функции y = f(x) в точке B 1 , и обозначаем точку пересечения касательной и оси Ox точкой x 1 . Получаем уравнение первой касательной:y-2=2·2(x-2), y=4x-6. Ox: x 1 =

Рис. 3. Построение первой касательной к графику функции f(x)

y=f(x) Ox через точку x 1 , получаем точку В 2 =(1.5; 0.25) . Снова проводим касательную к функции y = f(x) в точке В 2 , и обозначаем точку пересечения касательной и Ox точкой x 2 .

Уравнение второй касательной: y-2.25=2*1.5(x-1.5), y = 3x - 4.25. Точка пересечения касательной и оси Ox: x 2 = .

Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x 2 , получаем точку В 3 и так далее.

Рис. 4. Построение второй касательной к графику функции f(x)

Первое приближение корня определяется по формуле:

= 1.5.

Второе приближение корня определяется по формуле:

=

Третье приближение корня определяется по формуле:

Таким образом, i -ое приближение корня определяется по формуле:

Вычисления ведутся до тех пор, пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e - до выполнения неравенства |xi-xi-1|

В нашем случае, сравним приближение, полученное на третьем шаге с реальным ответом. Как видно, уже на третьем шаге мы получили погрешность меньше 0.000002.

Решение уравнения при помощи САПР MathCAD

Для простейших уравнений вида f (x ) = 0 решение в MathСAD находится с помощью функции root .

root(f (х 1 , x 2 , … ) , х 1 , a, b ) - возвращает значение х 1 , принадлежащее отрезку [ a, b ] , при котором выражение или функция f (х ) обращается в 0. Оба аргумента этой функции должны быть скалярами. Функция возвращает скаляр.

Рис. 5. Решение нелинейного уравнения в MathCAD (функция root)

Если в результате применения данной функции возникает ошибка, то это может означать, что уравнение не имеет корней, или корни уравнения расположены далеко от начального приближения, выражение имеет локальные max и min между начальным приближением и корнями.

Чтобы установить причину ошибки, необходимо исследовать график функции f (x ). Он поможет выяснить наличие корней уравнения f (x ) = 0 и, если они есть, то определить приблизительно их значения. Чем точнее выбрано начальное приближение корня, тем быстрее будет найдено его точное значение.

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

Рис. 6. Решение нелинейного уравнения в MathCAD (функция solve)

Заключение

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

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

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

Литература:

1. Митяков С. Н. Информатика. Комплекс учебно-методических материалов. - Н. Новгород: Нижегород. гос. техн. ун-т.,2006
2. Вайнберг М. М., Треногин В. А. Теория ветвления решений нелинейных уравнений. М.: Наука, 1969. - 527 с.
3. Бронштейн И. Н., Семендяев К. А. Справочник по математике для инженеров и учащихся ВТУЗов - М.: Наука, 1986.
4. Омельченко В. П., Курбатова Э. В. Математика: учебное пособие. - Ростов н/Д.: Феникс, 2005.
5. Савин А. П. Энциклопедический словарь юного математика. - М.: Педагогика, 1989.
6. Корн Г., Корн Т. Справочник по математики для научных работников и инженеров. - М.: Наука, 1973.
7. Кирьянов Д. Mathcad 15/MathcadPrime 1.0. - С-Пб.: БХВ-Петербург, 2012.
8. Черняк А., Черняк Ж., Доманова Ю. Высшая математика на базе Mathcad. Общий курс. - С-Пб.: БХВ-Петербург, 2004.
9. Поршнев С., Беленкова И. Численные методы на базе Mathcad. - С-Пб.: БХВ-Петербург, 2012.

Ключевые слова: нелинейные уравнения, прикладная математика, САПР MathCAD, метод Ньютона, шаговый метод, метод дихотомии. .

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