Кафедра: АСОИиУ
Лабораторная Работа
На тему: НАХОЖДЕНИЕ КОРНЯ НЕЛИНЕЙНОГО УРАВНЕНИЯ. МЕТОДЫ РЕШЕНИЯ СИСТЕМЫ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
Москва, 2008 год
НАХОЖДЕНИЕ КОРНЯ НЕЛИНЕЙНОГО УРАВНЕНИЯ
1. Постановка задачи
Пусть задана функция , непрерывная вместе со своими несколькими производными. Требуется найти все или некоторые вещественные корни уравнения
Данная задача распадается на несколько подзадач. Во-первых, необходимо определить количество корней, исследовать их характер и расположение. Во-вторых, найти приближенные значения корней. В-третьих, выбрать из них интересующие нас корни и вычислить их с требуемой точностью e. Первая и вторая задачи решаются, как правило, аналитическими или графическими методами. В случае, когда ищутся только вещественные корни уравнения (1), полезно составить таблицу значений функции . Если в двух соседних узлах таблицы функция имеет разные знаки, то между этими узлами лежит нечетное число корней уравнения (по меньшей мере, один). Если эти узлы близки, то, скорее всего, корень между ними только один.
Найденные приближенные значения корней можно уточнить с помощью различных итерационных методов. Рассмотрим три метода: 1) метод дихотомиии (или деление отрезка пополам); 2) метод простой итерации и 3) метод Ньютона.
2. Методы решения задачи
2.1 Метод деления отpезка пополам
Наиболее простым методом, позволяющим найти корень нелинейного уравнения (1), является метод половинного деления.
Пусть на отрезке задана непрерывная функция Если значения функции на концах отрезка имеют разные знаки, т.е. 
то это означает, что внутри данного отрезка находится нечетное число корней. Пусть для определенности корень один. Суть метода состоит в сокращении на каждой итерации вдвое длины отрезка. Находим середину отрезка (см. рис. 1) 
Вычисляем значение функции и выбираем тот отрезок, на котором функция меняет свой знак. Новый отрезок вновь делим пополам. И этот процесс продолжаем до тех пор, пока длина отрезка не сравняется с наперед заданной погрешностью вычисления корня e. Построение нескольких последовательных приближений по формуле (3) приведено на рисунке 1.
Итак, алгоритм метода дихотомии:
1. Задать отрезок и погрешность e.
2. Если f(a) и f(b) имеют одинаковые знаки, выдать сообщение о невозможности отыскания корня и остановиться.
Рис.1. Метод деления отрезка пополам для решения уравнения вида f(х)=0.
3. В противном случае вычислить c=(a+b)/2
4. Если f(a) и f(c) имеют разные знаки, положить b=c, в противном случае a=c.
5. Если длина нового отрезка , то вычислить значение корня c=(a+b)/2 и остановиться, в противном случае перейти к шагу 3.
Так как за N шагов длина отрезка сокращается в 2 N раз, то заданная погрешность отыскания корня e будет достигнута за итераций.
Как видно, скорость сходимости мала, но к достоинствам метода относятся простота и безусловная сходимость итерационного процесса. Если отрезок содержит больше одного корня (но нечетное число), то всегда будет найден какой-нибудь один.
Замечание. Для определения интервала, в котором лежит корень, необходим дополнительный анализ функции , основанный либо на аналитических оценках, либо на использование графического способа решения. Можно также организовать перебор значений функции в различных точках, пока не встретится условие знакопеременности функции
2.2 Метод простой итерации
При использовании этого метода исходное нелинейное уравнение (1) необходимо переписать в виде
Обозначим корень этого уравнения C * . Пусть известно начальное приближение корня . Подставляя это значение в правую часть уравнения (2), получаем новое приближение
и т.д. Для (n+1)- шага получим следующее приближение
(3)
Таким образом, по формуле (3) получаем последовательность С 0 , С 1 ,…,С n +1 , которая стремиться к корню С * при n®¥. Итерационный процесс прекращается, если результаты двух последовательных итераций близки, т. е. выполняется условие
(4)
Исследуем условие и скорость сходимости числовой последовательности {C n } при n®¥. Напомним определение скорости сходимости. Последовательность {C n }, сходящаяся к пределу С * , имеет скорость сходимости порядка a, если при n®¥ выполняется условие
Допустим, что имеет непрерывную производную, тогда погрешность на (n+1)-м итерационном шаге e n +1 =C n +1 -C * =g(C n)-g(C *) можно представить в виде ряда
e n+1 » C n+1 – C * = g¢(C *) (C n -C *) +¼@ g¢(C *) e n +¼
Таким образом, получаем, что при выполнении условия
çg¢(C *) ç<1(6)
последовательность (3) будет сходиться к корню с линейной скоростью a=1. Условие (6) является условием сходимости метода простой итерации. Очевидно, что успех метода зависит от того, насколько удачно выбрана функция .
Например, для извлечения квадратного корня, т. е. решения уравнения вида x =a 2 , можно положить
x=g 1 (x)=a/x (7а)
x=g 2 (x)=(x+a/x)/2.(7б)
Нетрудно показать, что
½g 1 " (C)½=1,
½g 2 " (C)½<1.
Таким образом, первый процесс (7а) вообще не сходится, а второй (7б) сходится при любом начальном приближении С 0 >0.
Рис. 2. Графическая интерпретация метода простых итераций для решения уравнения вида x=g(х).
Построение нескольких последовательных приближений по формуле (3)
С 0 , С 1 , …, С n = C *
приведено на рисунке 2.
2.3 Метод Ньютона
В литературе этот метод часто называют методом касательных, а также методом линеаризации. Выбираем начальное приближение С 0 . Допустим, что отклонение С 0 от истинного значения корня С * мало, тогда, разлагая f(C *) в ряд Тейлора в точке С 0 , получим
f(C *) = f(C 0) + f¢(C 0) (C * -C 0) +¼(8)
Если f¢(C 0) ¹ 0 , то в (8) можно ограничится линейными по DC =C-C 0 членами. Учитывая, что f(C *)=0, из (9) можно найти следующее приближение для корня
C 1 = C 0 – f (C 0) / f¢(C 0)
или для (n+1)-го приближения
C n+1 = C n – f (C n) / f ¢(C n) (9)
Для окончания итерационного процесса можно использовать одно из двух условий
çC n
+1
– C n
ç çf(C n
+1) ç Исследование сходимости метода Ньютона проводится аналогично предыдущему случаю. Самостоятельно получить, что при выполнении условия ½f ""
(C)/2f"(C)½<1. метод Ньютона имеет квадратичную скорость сходимости (). Рис. 3. Графическая интерпретация метода Ньютона для решения уравнения вида f(х)=0. Построение нескольких последовательных приближений по формуле (9) С 0
, С 1
, …, С n
= C * приведено на рисунке 3. 1. Для заданной функции f(x) · определите число вещественных корней уравнения f(x)=0, место их расположения и приближенные значения (постройте график или распечатайте таблицу значений). · Вычислите один из найденных корней (любой) с точностью e=0,5*10 -3
. Для вычислений используйте метод деления отрезка пополам (определите число итераций), а затем этот же корень найдите с помощью метода Ньютона (также определив число итерационных шагов). Сравните полученные результаты. Варианты заданий 1. x 3
–3x 2
+6x – 5 = 0 2. x 3
+sinx –12x-1=0 3. x 3
–3x 2
–14x – 8 = 0 4. 3x + cos x + 1 =0 5. x 2
+4sin x –1 = 0 6. 4x –ln x = 5 7. x 6
–3x 2
+x – 1 = 0 8. x 3
– 0.1x 2
+0.3x –0.6 = 0 9. 11. 13. x 3
–4x 2
–10x –10 = 0 14. 15. 16. 19. 20. 23. 24. x 4
- 2.9x 3
+0.1x 2
+ 5.8x - 4.2=0 25. x 4
+2.83x 3
- 4.5x 2
-64x-20=0 26. МЕТОДЫ РЕШЕНИЯ СИСТЕМЫ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
1.
Постановка задачи
Пусть требуется решить систему n нелинейных уравнений: Прямых методов решения системы (1) не существует. Лишь в отдельных случаях эту систему можно решить непосредственно. Например, для случая двух уравнений иногда удаётся выразить одну неизвестную переменную через другую и таким образом свести задачу к решению одного нелинейного уравнения относительно одного неизвестного. Систему уравнений (1) можно кратко записать в векторном виде: Уравнение (2) может иметь один или несколько корней в области определения D. Требуется установить существование корней уравнения и найти приближённые значения этих корней. Для нахождения корней обычно применяют итерационные методы, в которых принципиальное значение имеет выбор начального приближения. Начальное приближение иногда известно из физических соображений. В случае двух неизвестных начальное приближение можно найти графически: построить на плоскости (x 1
, x 2) кривые f 1
(x 1
, x 2)=0 и f 2
(x 1
, x 2)=0 и найти точки их пересечения. Для трех и более переменных (а также для комплексных корней) удовлетворительных способов подбора начального приближения нет. Рассмотрим два основных итерационных метода решения системы уравнений (1), (2) - метод простой итерации и метод Ньютона. 2. Методы решения системы нелинейных уравнений
2.1.Метод простой итерации
Представим систему (1) в виде или в векторной форме: Алгоритм метода простой итерации состоит в следующем. Выберем некоторое нулевое приближение Следующее приближение находим по формулам: или более подробно: Итерационный процесс (5) продолжается до тех пор, пока изменения всех неизвестных в двух последовательных итерациях не станут малыми, т.е. На практике часто вместо последнего условия используют неравенство: где - среднеквадратичная норма n-мерного вектора При использовании данного метода успех во многом определяется удачным выбором начального приближения : оно должно быть достаточно близким к истинному решению. В противном случае итерационный процесс может не сойтись. Если процесс сходится, то его скорость сходимости является линейной. 2.2. Метод Ньютона
В переводной литературе можно встретить название метод Ньютона-Рафсона. Этот метод обладает гораздо более быстрой сходимостью, чем метод простой итерации. Пусть известно некоторое приближение к корню , так что Тогда исходную систему (2) можно записать следующим образом: Разлагая уравнение (7) в ряд Тейлора в окрестности точки и ограничиваясь линейными членами по отклонению , получим: или в координатной форме: Систему (8) можно переписать в виде: Полученная система (9) является системой линейных алгебраических уравнений относительно приращений Значение функций F 1
, F 2
, …, F n
и их производные в (9) вычисляются при Определителем системы (9) является якобиан J: Для существования единственного решения системы уравнений (9) он должен быть отличен от нуля. Решив систему (9), например, методом Гаусса, найдём новое приближение: Проверяем условие (6). Если оно не удовлетворяется, находим и якобиан (10) с новым приближением и опять решаем (9), таким образом, находим 2-е приближение и т.д. Итерации прекращаются, как только выполнится условие (6). Используя метод Ньютона, найдите решения системы нелинейных уравнений с заданной точностью . Исследуйте сходимость итерационного процесса. Варианты заданий 1 3 5 7 9 11 13 15. 17. 19. 21. где функция f
(x
) определена и непрерывна на конечном или бесконечном интервале x
(a
,
b
)
. Всякое значение ξ
,
обращающее функцию f
(x
) называется корнем
уравнения функции f
(x
) . Число ξ
называется
корнем k-й кратности,
если при x
=
ξ
вместе с функцией f (x)
равны нулю и ее производные до порядка (k-1)
включительно: (k
−
1) Однократный корень называется простым
. Два уравнения называются равносильными
(эквивалентными), если множества их решений совпадают. Нелинейные уравнения с одной переменной подразделяются на алгебраические (функция f
(x
)
является алгебраической) и трансцендентные в противном случае. Уже на примере алгебраического многочлена известно, что нули f
(x
)
могут быть как действительными, так и комплексными. Поэтому более точная постановка задачи состоит в нахождении корней уравнения (6.1), расположенных в заданной области комплексной плоскости. Можно рассматривать также задачу нахождения действительных корней, расположенных на заданном отрезке. Иногда, пренебрегая точностью формулировок, просто говорят, что требуется решить уравнение (6.1). Большинство алгебраических и трансцендентных нелинейных уравнений аналитически (т.е. точно) не решается, поэтому на практике для нахождения корней используются численные методы. В связи с этим под решением уравнения (6.1) будем понимать задачу приближенного
нахождения корней уравнения вида (6.1). При этом под близостью приближенного значения x
к корню ξ
уравнения, как правило, понимают выполнение неравенства |
ξ
−
x
|
<
ε
при малых ε
>
0
, т.е. абсолютную погрешность приближенного равенства x
≈
ξ
. Используют также и относительную погрешность, т.е. величину |
ξ
−
x
|
. Нелинейная функция f
(x
)
в своей области определения может иметь конечное или бесконечное количество нулей или может не иметь их вовсе. Численное решение нелинейного уравнения (6.1) заключается в нахождении с заданной точностью значений всех или некоторых корней уравнения и распадается на несколько подзадач:
во-первых, надо исследовать количество и характер корней (вещественные или комплексные, простые или кратные), во-вторых, определить их приближенное расположение, т.е. значения начала и конца отрезка, на котором лежит только один корень, в-третьих, выбрать интересующие нас корни и вычислить их с требуемой точностью. Большинство методов нахождения корней требует знания промежутков, где заведомо имеется и притом единственный нуль функции. В связи с этим вторая задача называется отделением корней
. Решив ее, по сути дела, находят приближенные значения корней с погрешностью, не превосходящей длины отрезка, содержащего корень. 6.1. Отделение корней нелинейного уравнения Для функций общего вида нет универсальных способов решения задачи отделения корней. Отметим два простых приема отделения действительных корней уравнения – табличный
и графический
. Первый прием состоит в вычислении таблицы значений функции в заданных точках x
i
, расположенных на условно небольшом расстоянии h
одна от другой и использовании следующих теорем математического анализа: 1.
Если функция y=f(x) непрерывна на отрезке [а,b] и f(a)f(b)<0, то внутри отрезка существует по крайней мере один корень уравнения f(x)=0.
2.
Если функция y=f(x) непрерывна на отрезке [а,b], f(a)f(b) < 0 и f′(x) на интервале (a,b) сохраняет знак, то внутри отрезка существует единственный корень уравнения f(x)=0.
Выполнив вычисление значений функции в этих точках (или только определив знаки f
(x
i
)
), сравнивают их в соседних точках, т.е. проверяют, не выполняется ли на отрезке [
x
i
−
1
,
x
i
]
условие f
(x
i
−
1
)
f
(x
i
)
≤
0
. Таким образом, если при некотором i
числа f
(x
i
−
1
)
и f
(x
i
)
имеют разные знаки, то это означает, что на интервале (x
i
−
1
,
x
i
)
уравнение имеет по крайней мере один действительный корень нечетной кратности (точнее - нечетное число корней). Выявить по таблице корень четной кратности очень сложно. Если заранее известно количество корней в исследуемой области, то, измельчая шаг поиска h
, таким процессом можно либо их локализовать, либо довести процесс до состояния, позволяющего утверждать наличие пар корней, не различимых с точностью h
=
ε
. Это хорошо известный способ перебора. По таблице можно построить график функции
y
=
f
(x
)
. Корнями уравнения (6.1) являются те значения х
, при которых график функции пересекает ось абсцисс. Этот способ более нагляден и даёт неплохие приближённые значения корней. Построение графика функции даже с малой точностью обычно дает представление о расположении и характере корней уравнения (иногда позволяет выявить даже корни четной кратности). Во многих задачах техники такая точность уже достаточна. Если построение графика функции y
=
f
(x
)
вызывает затруднение, следует преобразовать исходное уравнение к виду ϕ
1
(x
)
=
ϕ
2
(x
)
таким образом, чтобы графики функций y
=
ϕ
1
(x
)
и y
=
ϕ
2
(x
)
были достаточно просты. Абсциссы точек пересечения этих графиков и будут корнями уравнения. Пример:
Отделить корни уравнения x
2
−
sin
x
−
1
=
0
. Представим уравнение в виде: x
2
−
1=
sin x
и построим графики 2 −
y
=
sin x
Совместное рассмотрение графиков позволяет сделать заключение, что данное уравнение ξ
1
[−
1,0] и
ξ
2
.
Допустим, что искомый корень уравнения отделен, т.е. найден отрезок , на котором имеется только один корень уравнения. Для вычисления корня с требуемой точностью ε
обычно применяют какую-либо итерационную процедуру уточнения корня, строящую числовую последовательность значений x
n
, сходящуюся к искомому корню уравнения. Начальное приближение x
0
выбирают на отрезке , продолжают вычисления, пока не выполнится неравенство x
n
−
1
−
x
n
< ε
, и считают, что x
n
– есть корень уравнения, найденный с заданной точностью. Имеется множество различных методов построения таких последовательностей и выбор алгоритма – весьма важный момент при практическом решении задачи. Немалую роль при этом играют такие свойства метода, как простота, надежность, экономичность, важнейшей характеристикой является его скорость сходимости. Последовательность x
Сходящаяся к пределу x
* ,
скорость сходимости порядка α
, если при n
→ ∞
− x
*
− x
*
n +
1
α
=1 сходимость называется линейной, при 1<α
<2 – сверхлинейной, при α
=2 – квадратичной. С ростом α
алгоритм, как правило, усложняется и условия сходимости становятся более жесткими. Приближённые значения корней уточняют различными итерационными методами. Рассмотрим наиболее эффективные из них. 6.2. Метод половинного деления (бисекции, дихотомии) Пусть функция f
(x
)
определена и непрерывна при всех x
[
a
,
b
]
и на меняет знак, т.е. f
(a
)
f
(b
)
<
0
. Тогда согласно теореме 1 уравнение имеет на (a
,
b
)
хотя бы один корень. Возьмем произвольную точку c
(a
,
b
)
. Будем называть в этом случае отрезок промежутком существования, корня, а точку c
- пробной точкой. Поскольку речь здесь идет лишь о вещественных функциях вещественной переменной, то вычисление значения f
(c
)
приведет к какой-либо одной из следующих взаимоисключающих ситуаций: А) f
(a
)
f
(c
)
<
0
Б) f
(c
)
f
(b
)
<
0
В) f
(c
)
=
0
Если f
(c
)
=
0
, то корень уравнения найден. В противном случае из двух частей отрезка [
a
,
c
]
или [
c
,
b
]
выберем ту, на концах которой функция имеет разные знаки, так как один из корней лежит на этой половине. Затем повторяем процесс для выбранного отрезка. называют дихотомии.
Наиболее употребительным метода дихотомии c(a1
) является метод половинного деления,
реализующий самый простой способ b(b1
) выбора пробной точки – деление промежутка существования Рис. 6.1. Метод дихотомии За один шаг метода половинного деления промежуток существования корня сокращается ровно вдвое. Поэтому, если за k
-е приближение к корню ξ
уравнения примем точку x
k
, являющуюся серединой полученного на k
-м шаге отрезка [
a
k
,
b
k
]
, полагая a
0
=
a
, b
0
=
b
, то придем к неравенству ξ−
k <
b
−
a
которое, с одной стороны, позволяет утверждать, что последовательность (x
k
) имеет предел – искомый корень ξ
уравнения (6.1), с другой стороны, является априорной оценкой
абсолютной погрешности равенства x
k
≈
ξ
, что дает возможность подсчитать число шагов (итераций) метода половинного деления, достаточное для получения корня ξ
с заданной точностью ε
.Для чего нужно лишь найти наименьшее натуральное k
удовлетворяющее неравенству b
2
−
k
a
<
ε
.
Проще говоря, если требуется найти корень с точностью ε
, то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше 2ε
. Тогда середина последнего отрезка даст значения корня с требуемой точностью. Дихотомия проста и очень надёжна: к простому корню она сходится для любых непрерывных функций f
(x
)
, в том числе недифференцируемых; при этом она устойчива к ошибкам округления. Скорость сходимости невелика: за одну итерацию точность увеличивается примерно вдвое, т.е. уточнение трёх цифр требует 10 итераций. Зато точность ответа гарантируется. К основным недостаткам метода дихотомии можно отнести следующие. 1.
Для начала расчёта необходимо найти отрезок, на котором функция изменяет знак. Если в этом отрезке несколько корней, то заранее неизвестно, к какому из них сойдётся процесс (хотя к одному из них обязательно сойдётся).
2.
Метод неприменим к корням чётной кратности.
3.
Для корней нечётной высокой кратности он сходится, но менее точен и менее устойчив к ошибкам округления, возникающим при вычислении значений функции.
Дихотомия применяется тогда, когда требуется высокая надёжность счёта, а скорость сходимости малосущественна. Один из недостатков дихотомии – сходимость неизвестно к какому корню – характерен почти для всех итерационных методов. Его можно устранить удалением уже найденного корня. Если x
1
есть простой корень уравнения и f
(x
)
липшиц-непрерывна, то вспомогательная функция g
(x
) =
f
(x
) /(x
−
x
1
) непрерывна, причём все нули функций f(x)
и g(x)
совпадают, за исключением x
1
, так как g
(x
1
) ≠
0. Если x
1
- кратный корень уравнения, то он будет нулём g(x)
кратности на единицу меньше; остальные нули обеих функций по-прежнему будут одинаковы. Поэтому найденный корень можно удалить, т.е. перейти к функции g(x)
. Тогда отыскание остальных нулей f
(x
)
сведётся к отысканию нулей g(x)
.
Когда мы найдём какой-нибудь x
2
функции g(x)
, корень тоже можно удалить, вводя вспомогательную функцию ϕ
(x
) =
g
(x
) /(x
−
x
2
). последовательно найти все уравнения. При использовании описанной процедуры необходимо учитывать следующую тонкость. Строго говоря, мы находим лишь приближённое значение корня x
≈
x
.
А функция g
(x
) F
(x
) /(x
−
x
1
) имеет нуль в точке x
1
и полюс в близкой к ней точке x
1
(рис. 6.2); только на некотором расстоянии от этого корня она близка к g(x
)
. Чтобы это не сказывалось при нахождении следующих корней, нужно вычислять каждый корень с высокой точностью, особенно если он кратный или вблизи него расположен другой корень уравнения. g(x)
Кроме того, в любом методе g(x)
окончательные итерации определяемого g(x)
выполнять не по функциям типа g(x)
, а g(x)
по исходной функции f
(x
)
. Последние итерации, вычисленные g(x)
, используются при этом в качестве Рис. 6.2. Иллюстрация возникновения нулевого приближения. Особенно погрешности в окрестности корня важно это при отыскании многих корней, так как чем больше корней вспомогательной соответствуют остальным нулям функции f (x)
.
G
(x
) =
f
(x
) / ∏
(x
−
x
i
Учитывая эти предосторожности и вычисляя корни с 8 – 10 верными десятичными цифрами, зачастую можно определить десятка два корней, о расположении которых заранее ничего не известно (в том числе корней высокой кратности р
5). 6.3. Метод хорд Логично предположить, что в семействе методов дихотомии можно достичь несколько лучших результатов, если отрезок делить точкой c
не пополам, а пропорционально величинам ординат f
(a
) и f
(b
) . Это означает, что точку c
есть смысл находить, как абсциссу точки пересечения оси Ох с прямой, проходящей через точки A
(a
,
f
(a
))
и B
(b
,
f
(b
))
, иначе, с хордой дуги графика функции f
(x
)
. Такой способ выбора пробной точки, называют методом хорд
или методом линейной интерполяции
.
Запишем уравнение прямой проходящей через точки А
и В
: y−
f (a)
x−
a f (b)
−
f (a)
b−
a и, полагая y
=
0, находим: f (a)(b−
a)
c
=
a
−
f (b)
−
f (a)
Метод хорд
подобно алгоритму метода бисекции строит последовательность вложенных отрезков [а
n
,b
n
], но в качестве x
n
берется точка пересечения хорды с осью абсцисс :
n+
1
f (an
)
− a
f (bn
)
−
f (an
)
Длина промежутка локализации корня при этом может не стремится к нулю, поэтому обычно счет ведется до совпадения значений двух очередных приближений с точностью ε
. Метод сходится линейно, но близость двух очередных приближений не всегда означает, что корень найден с требуемой точностью. Поэтому, если 0
<
m
≤
|
f
′
(x
)|
≤
M
,
x
[
a
,
b
]
, M −
m Более надежным практическим критерием окончания итераций в методе хорд является выполнение неравенства − x
n−
1
< ε.
2
x
n−
1
−
x
n −
x
n−
2
6.4. Метод простой итерации Заменим уравнение f
(x
)
=
0
эквивалентным ему уравнением x
=
ϕ
(x
) .
сходилась к корню данного уравнения
знакопостоянная функция. Выберем некоторое нулевое приближение х
0
и вычислим дальнейшие приближения по формулам x
k
+
1
=
ϕ
(x
k
)
,
k
=
0,1,2,.. Эти формулы определяют одношаговый общий итерационный метод, называемым методом простых итераций
. Попытаемся понять, каким требованиям должна удовлетворять функция ϕ
(x
)
, чтобы последовательность (x
k
)
, определяемая (6.7) была сходящаяся, и как построить функцию ϕ
(x
)
по функции f
(x
)
, чтобы эта последовательность f (x)
=
0
.
Пусть ϕ
(x
)
- непрерывная на некотором отрезке [
a
,
b
]
функция. Если определяемая формулой (6.7) последовательность (x
k
)
сходится к некоторому числу ξ
, т.е. ξ
=
lim
x
k
, то, переходя к пределу в равенстве k
→∞ (6.7), получаем ξ
=
ϕ
(ξ
)
. Это равенство означает, что ξ
- корень уравнения (6.6) и эквивалентного ему исходного уравнения. Нахождение корня уравнения (6.6) называется задачей о неподвижной точке. Существование и единственность этого корня основывается на принципе сжимающих отображений. Определение:
Непрерывная функция ϕ
(x
)
называется сжимающей
на отрезке [
a
,
b
]
если: 1)
ϕ
(x
) , x
2)
q
(0,1) : |ϕ
(x
2
)−
ϕ
(x
1
)|≤
q
|x
2
−
x
1
|, x
1
,x
2
.
Второе условие для дифференцируемой на [
a
,
b
]
функции равносильно выполнению неравенства ϕ
" (x
)
≤
q
<
1
на этом отрезке. Метод простых итераций имеет простую геометрическую интерпретацию: нахождение корня уравнения f(x)=0
равносильно обнаружению неподвижной точки функции x=
ϕ
(x)
, т.е. точки пересечения графиков функций y=
ϕ
(x)
и y=x
. Метод простой итерации не всегда обеспечивает сходимость к корню уравнения. Достаточным условием сходимости этого метода является выполнение неравенства ϕ
" (x
)
≤
q
<
1
на Проиллюстрируем (рис. 6.4) геометрически поведение сходящейся итерационной последовательности (x
k
)
, не отмечая значения ϕ
(x
k
)
, а отражая их на ось абсцисс с помощью биссектрисы координатного угла y=
x .
Рис.6.4 Сходимость метода простой итерации при ϕ
" (x
)
≤
q
<
1
. Как видно из рис. 6.4, если производная ϕ
′
(x
)
<
0
, то последовательные приближения колеблются около корня, если же производная ϕ
′
(x
)
>
0
, то последовательные приближения сходятся к корню монотонно. Справедлива следующая теорема о неподвижной точке. Теорема:
Пусть ϕ
(x
)
определена и дифференцируема на [
a
,
b
]
. Тогда, если выполняются условия: 1) ϕ
(x
) x [
a,
b]
x (a,
b)
2)
q
: |ϕ
(x
)|≤
q
<
1 3) 0
x [
a,
b]
то уравнение x
=
ϕ
(x
)
имеет на [
a
,
b
]
единственный корень ξ
и к этому корню сходится определяемая методом простых итераций последовательность (x
k
)
, начинающаяся с x
0
[
a
,
b
]
. При этом справедливы следующие оценки погрешности: k −
1
|ξ
−
x
|≤
1
−
q
|x
−x
ξ −
x
k
1 −
q
x
1 −
x
0 если ϕ
(x
) >
0 ξ −
x
k
− x
k
−
1
если ϕ
(x
) <
0 Вблизи корня итерации сходятся примерно как геометрическая прогрессия со x
k −
x
k −
1
знаменателем Метод имеет линейную скорость x
k −
1
−
x
k −
2
сходимости. Очевидно, что чем меньше q
(0,1) Тем быстрее сходимость. образом, успех от того, насколько удачно выбрано ϕ
(x
)
. Например, для извлечения квадратного корня, т.е. для решения уравненияx
2
=
a
, можно положить ϕ
(x
)
=
a
/
x
или ϕ
(x
) =
1/ 2 и
соответственно написать такие итерационные процессы: x
k +
1
=
x
k +
1
Первый процесс вообще не сходится, а второй сходится при любом х
0
> 0 и сходится очень быстро, так как ϕ
"(ξ
)
=
0
Второй процесс используется при извлечении корня в "запаянных" командах микрокалькуляторов. Пример 1:
Найти методом итерации с точностью ε
=
10−
4
наименьший корень уравнения f
(x
)=
x
3
+
3x
2
−
1=
0 .
Решение
: Отделяем корни: −4
−3
−2
−
1 0 f (x)
Очевидно, уравнение имеет три корня, расположенные на отрезках [
−
3;
−
2]
, [−
1;0] и . Наименьший находится на отрезке [
−
3;
−
2]
. Т.к. на этом отрезке x
2
≠
0
, разделим уравнение на x
2
. Получим: x
+3
− =
0
=> x
=
−3
x2
x2
|ϕ
−2
x
−3
1
, т.е. q=
(x
)|=
−3
≤ x
≤ −2
−3
≤ x
≤ −2
Пусть x
0
=−
2.5
, тогда δ
=
max[−
3−
x
0
;−
2 −
x
0
] =
0.5 x
=
ϕ
(−
2.5) =
−3
=−
2.84 [−
3,−
2] обозначим Проверим выполнение условия теоремы: ϕ
(x
)=
x
2
−
3 (−
2.5)2
|ϕ
(x
0)−
x
0|=
0.34<
(1−
q
) 0 −
1
−
(x
) q
n ≤
ε
=>
2
10 => n
≥
6
1−
q
3 4n
xn
ϕ
(x
n
)=
−3
x2
−
2.50000 −
2.84000 −
2.84000 −
2.87602 −
2.87602 −
2.87910 −
2.87910 −
2.87936 −
2.87936 −
2.87938 −
2.87938 −
2.87938 Замечание:
Для нахождения двух других корней исходного уравнения методом простой итерации уже нельзя пользоваться формулой: x
=
x
1
2
−
3
, −2
x
−3
=−∞,
−2
x
−3
max |
ϕ
(x
)|
=
−1
≤ x
≤ 0
−1
≤ x
≤ 0
−1
≤x
≤0
Условие сходимости на этих отрезках не выполнено. Метод релаксации
- один из вариантов метода простой итерации, в котором ϕ
(x)
=
x −
τ
f (x)
,
т.е. равносильное уравнение имеет вид: x =
x −
τ
f (x)
.
Приближения к корню вычисляются по формулам xn
+
1
=
xn
−
τ
f (xn
),
Если f
(x
)
<
0
, то рассматривают уравнение −
f
(x
)
=
0
.
функции f
(x
)
. Пусть 0
≤α
≤ f
′(x
)
≤γ
<∞ Параметр τ
подбирается таким, чтобы производная ϕ
′
(x
)
=
1
−
τ
f
′
(x
)
в нужной области была малой по модулю. 1
−
τ γ ≤
ϕ′
(x
)
≤
1
−
λα и значит, |ϕ
′
(x
)|≤
q
(τ
) =
max{|1−
τα
|,|1−
τγ
|} Для
нахождения корня уравнения
можно воспользоваться функциейroot(f
(x
)
,x
),
где первым аргументом служит функция
f
(x
)
,
а вторым аргументом служит имя неизвестной
величины, т.е. x
.
Перед обращением к этой функции нужно
искомой переменной присвоить начальное
значение, желательно близкое к ожидаемому
ответу. Приведенное
описание функции пригодно для всех
версий системы МС. Эту функцию можно
вызвать с помощью кнопки f(x)
на панели инструментов, выбрав в левом
списке пункт Solving.
В МС14 выбранная таким образом функция
имеет четыре аргумента. Первые два из
них − такие же, как было описано выше,
а третьим и четвертым аргументами служат
левая и правая границы интервала, на
котором лежит искомый корень. Если
задать третий и четвертый аргументы,
то начальное значение переменной можно
и не присваивать. Рассмотрим
использование этой функции на примере
уравнения
Второй
корень найдем так: Число
выведенных на экран знаков вычисленного
корня не совпадает с точностью нахождения
результата. В памяти компьютера число
хранится с пятнадцатью знаками, а на
экран из этой записи выводится то
количество знаков, которое установлено
в меню Format.
Насколько найденное значение корня
отличается от точного, зависит от метода
вычисления корня и от числа итераций в
этом методе. Это регулируется системной
переменной TOL,
которая по умолчанию равна 0,001. В системе
МС14 функция root
ориентирована на достижение точности
Следует
учесть, что в некоторых исключительных
случаях результат может отклоняться
от точного значения корня значительно
больше, чем на величину TOL.
Изменить значение TOL
можно или простым присвоением, или с
помощью меню Tools
пункт
Worksheet
Options пункт
Built-In
Variables. Для
нахождения корней многочлена можно
воспользоваться другой функцией, которая
выдаст все корни многочлена, включая
комплексные. Это функция polyroots(■),
где аргументом служит вектор, координатами
которого являются коэффициенты
многочлена, первая координата –
свободный член, вторая – коэффициент
при первой степени переменного, последняя
– коэффициент при старшей степени.
Функция вызывается так же, как и функция
root.
Например, корни многочлена
Некоторые
простые уравнения можно решать и с
помощью символьных преобразований.
Можно найти корни многочлена второй
или третьей степени, если коэффициенты
являются целыми числами или обыкновенными
дробями. В качестве примера возьмем
многочлены, корни которых известны. Эти
многочлены мы получим как произведение
линейных множителей. Возьмем многочлен
В
полученном результате выделим переменное
x
,
выберем в меню Symbolics
пункт Variable
и в раскрывшемся окне пункт Solve.
Получим Как
видим, корни найдены правильно. Возьмем
многочлен третьей степени
и
символьными преобразованиями (результат
на рис. 20). Как
видим, последний результат мало пригоден
для использования, хотя и является
«абсолютно» точным. Этот результат
будет еще «хуже», если в многочлен
добавить член с
Символьные
вычисления эффективны, если корни
являются целыми или рациональными
числами: В
этом примере символьные вычисления
произведены с помощью панели Symbolic.
Приведено также решение с помощью
функции polyroots.
Последние результаты менее эффектны,
хотя с точки зрения вычислений ничем
не хуже, так как разумный инженер округлит
второй корень до числа – i
. Символьное
нахождение корней можно применять и
для уравнений, содержащих функции,
отличные от многочленов: Для
полного ответа к ним нужно добавить
число, кратное
Решим
более сложную задачу. Функция y
(x
)
задана неявно уравнением
Для
решения этой задачи естественно
воспользоваться функцией root.
Однако она требует указания отрезка,
на котором лежит искомый корень. Для
этого найдем значение y
графически при нескольких значениях
x
.
(Графики приводятся ниже в виде отдельных
рисунков, а не так как они размещены на
экране MATHCAD). Строим
график (рис.21). На нем видно, что «разумные»
значения y
лежат в промежутке [– 5; 5]. Построим
график в этом диапазоне. Изменения можно
внести в шаблоны на имеющемся рисунке.
Результат приведен на рис. 22. Видим, что
корень лежит на отрезке . Возьмем
следующее значение x
.
На бумаге – это новые записи, а на экране
достаточно внести изменения в блоке,
где x
присваивается значение. При
Введем
функцию пользователя .Построим
график этой функции, считая переменным
z
,
причем шаблоны по вертикальной оси
можно не заполнять, система сама
произведет масштабирование. График
приведен на рис.25. По данному графику
можно отследить значения функции с
помощью панели X-Y
Trace,
как было описано выше. Свои способности человек может узнать, только попытавшись приложить их. (Сенека)
Задачи решения уравнений постоянно возникают на практике, например, в экономике, развивая бизнес, вы хотите узнать, когда прибыль достигнет определенного значения, в медицине при исследовании действия лекарственных препаратов, важно знать, когда концентрация вещества достигнет заданного уровня и т.д. В задачах оптимизации часто необходимо определять точки, в которых производная функции обращается в 0, что является необходимым условием локального
экстремума. В статистике при построении оценок методом наименьших квадратов или методом максимального правдоподобия также приходится решать нелинейные уравнения и системы уравнений. Итак, возникает целый класс задач, связанных с нахождением решений нелинейных
уравнений, например, уравнения или уравнения и т.д. В простейшем случае у нас имеется функция , заданная на отрезке (a
,
b
) и принимающая определенные значения. Каждому значению x
из этого отрезка мы можем сопоставить число , это и есть функциональная
зависимость, ключевое понятие математики. Нам нужно найти такое значение при котором такие называются корнями функции Визуально нам нужно определить точку пересечения графика функции
с осью абсцисс.
Простейшим методом нахождения корней уравнения является метод деления пополам или дихотомия
. Этот метод является интуитивно ясным и каждый действовал бы при решении задачи подобным образом. Алгоритм состоит в следующем. Предположим, мы нашли две точки и , такие что и имеют разные
знаки, тогда между этими точками находится хотя бы один корень функции . Поделим отрезок пополам и введем среднюю
точку . Тогда либо Оставим ту половину отрезка, для которой значения на концах имеют разные знаки. Теперь этот отрезок снова делим пополам и оставляем ту его часть, на границах которой функция имеет разные знаки, и так далее, достижения требуемой точности. Очевидно, постепенно мы сузим область, где находится корень функции, а, следовательно, с определенной степенью точности определим его. Заметьте, описанный алгоритм применим для любой непрерывной функции. К достоинствам метода деления пополам следует отнести его высокую надежность и простоту. Недостатком метода является тот факт, что прежде чем начать его применение, необходимо найти две точки, значения функции в которых имеют разные знаки. Очевидно, что метод неприменим для корней четной кратности и также не может быть обобщен на случай комплексных корней и на системы уравнений. Порядок сходимости метода линейный, на каждом шаге точность возрастает вдвое, чем больше сделано итераций, тем точнее определен корень. Классический метод Ньютона
или касательных
заключается в том, что если — некоторое приближение к корню уравнения Уравнение касательной к функции в точке имеет вид: В уравнении касательной положим и . Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем: Сходимость метода касательных квадратичная, порядок сходимости равен 2. Таким образом, сходимость метода касательных Ньютона очень быстрая.
Запомните этот замечательный факт! Без всяких изменений метод обобщается на комплексный случай. Если корень является корнем второй кратности и выше, то порядок сходимости падает и становится линейным. Упражнение 1
. Найти с помощью метода касательных решение уравнения на отрезке (0, 2). Упражнение 2.
Найти с помощью метода касательных решение уравнения на отрезке (1, 3). К недостаткам метода Ньютона следует отнести его локальность, поскольку он гарантированно сходится при произвольном стартовом приближении только, если везде выполнено условие Недостатком метода Ньютона является необходимость вычисления производных на каждом шаге. Метод Ньютона (метод касательных) применяется в том случае, если уравнение f
(x
) = 0
имеет корень , и выполняются условия: 1) функция y
=
f
(x
)
определена и непрерывна при ; 2) f
(a
)·
f
(b
) < 0
(функция принимает значения разных знаков на концах отрезка [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) =
2
x
>
0
и f
""
(x) = 2
> 0
. Рисунок
1
. f(x) =x 2 -2
Уравнение касательной в общем виде имеет представление: y-y 0 = f
"
(x 0)·(x-x 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 =
Рисунок
2.
Результат первой итерации
y=f(x)
Ox
через точку x 1
, получаем точку В 2 =(1.5; 0.25)
. Снова проводим касательную к функции y = f(x)
в точке В 2 , и обозначаем точку пересечения касательной и оси Ox
точкой x 2
. Уравнение второй касательной: y
-0.25=2*1.5(x
-1.5),
y
= 3
x
- 4.25.
Точка пересечения касательной и оси Ox: x 2 =
.
Рисунок
3.
Вторая итерация метода Ньютона
Затем находим точку пересечения функции y=f(x)
и перпендикуляра, проведенного к оси Ox
через точку x 2 , получаем точку В 3 и так далее. Рисунок
4.
Третий шаг метода касательных
Первое приближение корня определяется по формуле: Второе приближение корня определяется по формуле: Третье приближение корня определяется по формуле: Таким образом,
i
-ое приближение корня определяется по формуле: Вычисления ведутся до тех пор, пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e - до выполнения неравенства |
xi
-
xi
-1
| <
e
.
В нашем случае, сравним приближение, полученное на третьем шаге с реальным ответом, посчитанном на калькуляторе: Рисунок 5. Корень из 2, посчитанный на калькуляторе
Как видно, уже на третьем шаге мы получили погрешность меньше 0.000002. Таким образом можно вычислить значение величины "корень квадратный из 2" с любой степенью точности. Этот замечательный метод был изобретен Ньютоном и позволяет находить корни очень сложных уравнений. В данной статье мы автоматизируем процесс вычисления корней уравнений, написав консольное приложение на языке C++. Разрабатывать его мы будем в Visual C++ 2010 Express, это бесплатная и очень удобная среда разработки С++. Для начала запустим Visual C++ 2010 Express. Появится стартовое окно программы. В левом углу нажмем «Создать проект». Рис. 1. Начальная страница Visual C++ 2010 Express
В появившемся меню выберем «Консольное приложение Win32», введем имя приложение «Метод_Ньютона». Рис. 2. Создание проекта
// Метод_Ньютона.cpp: определяет точку входа для консольного приложения #include "stdafx.h" #include using namespace std; float f(double x) //возвращает значение функции f(x) = x^2-2 float df(float x) //возвращает значение производной float d2f(float x) // значение второй производной int _tmain(int argc, _TCHAR* argv) int exit = 0, i=0;//переменные для выхода и цикла double x0,xn;// вычисляемые приближения для корня double a, b, eps;// границы отрезка и необходимая точность cout<<"Please input \n=>"; cin>>a>>b; // вводим границы отрезка, на котором будем искать корень cout<<"\nPlease input epsilon\n=>"; cin>>eps; // вводим нужную точность вычислений if (a > b) // если пользователь перепутал границы отрезка, меняем их местами if (f(a)*f(b)>0) // если знаки функции на краях отрезка одинаковые, то здесь нет корня cout<<"\nError! No roots in this interval\n"; if (f(a)*d2f(a)>0) x0 = a; // для выбора начальной точки проверяем f(x0)*d2f(x0)>0 ? xn = x0-f(x0)/df(x0); // считаем первое приближение cout<<++i<<"-th iteration = "< while(fabs(x0-xn) > eps) // пока не достигнем необходимой точности, будет продолжать вычислять xn = x0-f(x0)/df(x0); // непосредственно формула Ньютона cout<<++i<<"-th iteration = "< cout<<"\nRoot = "< cout<<"\nExit?=>"; } while (exit!=1); // пока пользователь не ввел exit = 1 Посмотрим, как это работает. Нажмем на зеленый треугольник в верхнем левом углу экрана, или же клавишу F5. Если происходит ошибка компиляции «Ошибка error LNK1123: сбой при преобразовании в COFF: файл недопустим или поврежден», то это лечится либо установкой первого Service pack 1, либо в настройках проекта Свойства -> Компоновщик отключаем инкрементную компоновку. Рис. 4. Решение ошибки компиляции проекта
Мы будем искать корни у функции f(x) =
x2-2
. Сначала проверим работу приложения на «неправильных» входных данных. На отрезке нет корней, наша программа должна выдать сообщение об ошибке. У нас появилось окно приложения: Рис. 5. Ввод входных данных
Введем границы отрезка 3 и 5, и точность 0.05. Программа, как и надо, выдала сообщение об ошибке, что на данном отрезке корней нет. Рис. 6. Ошибка «На этом отрезке корней нет!»
Выходить мы пока не собираемся, так что на сообщение «Exit?» вводим «0». Теперь проверим работу приложения на корректных входных данных. Введем отрезок и точность 0.0001. Рис. 7. Вычисление корня с необходимой точностью
Как мы видим, необходимая точность была достигнута уже на 4-ой итерации. Чтобы выйти из приложения, введем «Exit?» => 1. Чтобы избежать вычисления производной, метод Ньютона можно упростить, заменив производную на приближенное значение, вычисленное по двум предыдущим точкам: Итерационный процесс имеет вид: Это двухшаговый итерационный процесс, поскольку использует для нахождения последующего приближения два предыдущих. Порядок сходимости метода секущих ниже, чем у метода касательных и равен в случае однократного корня . Эта замечательная величина называется золотым сечением:
Убедимся в этом, считая для удобства, что . Таким образом, с точностью до бесконечно малых более высокого порядка Отбрасывая остаточный член, получаем рекуррентное соотношение, решение которого естественно искать в виде . После подстановки имеем: и Для сходимости необходимо, чтобы было положительным, поэтому . Поскольку знание производной не требуется, то при том же объёме вычислений в методе секущих (несмотря на меньший порядок сходимости) можно добиться большей точности, чем в методе касательных. Отметим, что вблизи корня приходится делить на малое число, и это приводит к потере точности (особенно в случае кратных корней), поэтому, выбрав относительно малое , выполняют вычисления до выполнения Как только начнется рост, вычисления прекращают и последнюю итерацию не используют. Такая процедура определения момента окончания итераций называется приемом Гарвика.
Рассмотрим трехшаговый метод, в котором приближение определяется по трем предыдущим точкам , и . Для этого заменим, аналогично методу секущих, функцию интерполяционной параболой проходящей через точки , и . В форме Ньютона она имеет вид: Точка определяется как тот из корней этого полинома, который ближе по модулю к точке . Порядок сходимости метода парабол выше, чем у метода секущих, но ниже, чем у метода Ньютона. Важным отличием от ранее рассмотренных методов, является то обстоятельство, что даже если вещественна при вещественных и стартовые приближения выбраны вещественными, метод парабол может привести к комплексному корню исходной задачи.
Этот метод очень удобен для поиска корней многочленов высокой степени.
Задачу нахождения решений уравнений можно формулировать как задачу нахождения корней: , или как задачу нахождения неподвижной точки. Пусть По теореме Банаха существует и единственна неподвижная точка Она может быть найдена как предел простой итерационной процедуры где начальное приближение — произвольная точка промежутка . Если функция дифференцируема, то удобным критерием сжатия является число . Действительно, по теореме Лагранжа Таким образом, если производная меньше единицы, то является сжатием. Условие Решение одного нелинейного уравнения Данная лабораторная работа включает в себя четыре метода решения одного нелинейного уравнения. Использующиеся методы решения одного нелинейного уравнения: Метод половинного деления. Метод простой итерации. Метод Ньютона. Метод секущих. Также данная лабораторная работа включает в себя: описание метода, применение метода к конкретной задаче (анализ), код программы решения вышеперечисленных методов на языке программирования MicrosoftVisualC++ 6.0. Описание метода: Пусть задана функция f (x) действительного переменного. Требуется найти корни уравнения f (x) =0 (1) или нули функции f (x). Нули f (x) могут быть как действительными, так и комплексными. Поэтому наиболее точная задача состоит в нахождении корней уравнения (1), расположенных в заданной области комплексной плоскости. Можно рассматривать также задачу нахождения действительных корней, расположенных на заданном отрезке. Задача нахождения корней уравнения (1) обычно решается в 2 этапа. На первом этапе изучается расположение корней и проводится их разделение, т.е. выделяются области в комплексной области, содержащие только один корень. Тем самым находятся некоторые начальные приближения для корней уравнения (1). На втором этапе, используя заданное начальное приближение, строится итерационный процесс, позволяющий уточнить значение отыскиваемого корня. Численные методы решения нелинейных уравнений являются, как правило, итерационными методами, которые предполагают задание достаточно близких к искомому решению начальных данных. Существует множество методов решения данной задачи. Но мы рассмотрим наиболее используемые методы решения по поиску корней уравнения (1): метод половинного деления (метод бисекции), метод касательных (метод Ньютона), метод секущих и метод простой итерации. Теперь отдельно по каждому методу: Более распространенным методом нахождения корней нелинейного уравнения является метод деления пополам. Предположим, что на интервале расположен лишь один корень x уравнения (1). Тогда f (a) и f (b) имеют различные знаки. Пусть для определения f (a) >0, f (b) <0. Положим x0= (a + b) /2 и вычислим f (x0). Если f (x0) <0, то искомый корень находится на интервале , если же f (x0) >0, то x принадлежит . Далее из двух интервалов и выбираем тот на границах, которого функция f (x) имеет различные знаки, находим точку x1 - середину выбранного интервала, вычисляем f (x1) и повторяем указанный процесс. В результате получаем последовательность интервалов, содержащих искомый корень x, причем длина каждого последующего интервала вдвое меньше, чем предыдущего. Процесс заканчивается, когда длина вновь полученного интервала станет меньше приближенной точности ( Пусть начальное приближение x0 известно. Заменим f (x) отрезком ряда Тейлора f (x) ≈ H1 (x) = f (x0) + (x - x0) f " (x0) и за следующее приближение x1 возьмем корень уравнения H1 (x) = 0, т.е. x1=x0 - f (x0) / f " (x0). Вообще, если итерация xk известна, то следующее приближение xk+1 в методе Ньютона определяется по правилу xk+1=xk-f (xk) /f" (xk), k=0, 1, … (2) Метод Ньютона называют также методом касательных, так как новое приближение xk +1 является абсциссой точки пересечения касательной, проведенной в точке (xk, f (xk)) к графику функции f (x) с осью Ox. Особенность метода: во-первых, метод имеет квадратичную сходимость, т.е. в отличие от линейных задач погрешность на следующей итерации пропорциональна квадрату погрешности на предыдущей итерации: xk+1-x=O ((xk-x) ²); во-вторых, такая быстрая сходимость метода Ньютона гарантируется лишь при очень хороших, т.е. близких к точному решению, начальных приближениях. Если начальное приближение выбрано неудачно, то метод может сходиться медленно, либо не сойдется вообще. Этот метод получается из метода Ньютона заменой f" (xk) разделенной разностью f (xk) - f (xk-1) /xk-xk-1, вычисленной по известным значениям xk и xk-1. В результате получаем итерационный метод Геометрическая интерпретация метода секущих состоит в следующем. Через точки (xk-1, f (xk-1)), (xk, f (xk)) проводится прямая, абсцисса точки пересечения этой прямой с осью Ox и является новым приближением xk+1. Иначе говоря, на отрезке функция f (x) интерполируется многочленом первой степени и за очередное приближение xk+1 принимается корень этого многочлена. Этот метод заключается в замене уравнения (1) эквивалентным ему уравнением вида Если в выражении (4) положить Иначе можно получить уравнение (4) следующим способом: левую и правую часть уравнения (1) умножить на произвольную константу и прибавить к левой и правой части х, т.е. получаем уравнение вида: На заданном отрезке выберем точку х 0 - нулевое приближение - и найдем: х 1 = f (x 0), потом найдем: х 2 = f (x 1), и т.д. Таким образом, процесс нахождения корня уравнения сводится к последовательному вычислению чисел: х n = f (x n-1) n = 1,2,3… Если на отрезке выполнено условие: |f " (x) |<=q<1 то процесс итераций сходится, т.е. Применение метода к конкретной задаче (анализ). Дано уравнение вида x² - ln (1+x) - 3 = 0 при x Изучив методы и применив их к данному уравнению приходим к такому выводу: при решении данного уравнения 4 известными способами результат одинаков во всех случаях. Но количество итераций при прохождении метода значительно отличается. Зададим приближенную точность Листинг программы: 1. Метод половинного деления #include #include #include #define e 0.000001 double func (double x) res=fopen ("bisekciy. txt","w"); while (fabs (a-b) >e) if ((func (c) *func (a)) <0) b=c; printf ("Otvet:%f\n",a); printf ("Takge smotri otvet v file bisekciy. txt\n"); fprintf (res,"Результат решения уравнения методом половинного деления! \n"); 2. Метод касательных (метод Ньютона) #include #include #include #define e 0.000001 double func (double x) return ((((x*x) - (log (1+x))) - 3)); double dif (double x) return ((2*x) - (1/ (1+x))); res=fopen ("kasatelnih. txt","w"); while (fabs (a-b) >=e) a=a-func (a) /dif (a); b=b-func (b) /dif (b); printf ("Funkciya prinimaet znachenie na intervale: [%d,%d] \n",x1,x2); printf ("Otvet:%f\n",a); printf ("Kol-vo iteraciy:%d \n",k); printf ("Takge smotri otvet v file kasatelnih. txt\n"); fprintf (res,"Результат решения уравнения методом Ньютона! \n"); fprintf (res,"Корень уравнения x =%f\nКоличество итераций =%d",a,k); 3. Метод секущих #include 
10. (x -1) 3
+ 0.5e x
= 0
12. x 5
–3x 2
+ 1 = 0
(1)
. (2)
(3)
(4)
(5)
(6)
, т.е.
(8)
(9)
.
(10)
.
2
4
6
8
10
12
14. 
16. 
18. 
20. 
22. 
.
Сначала выполним отделение корней. Для
этого построим графики функций в правой
и левой части (рис.19). Из рисунка видно,
что уравнение имеет два корня. Один
лежит на отрезке [–2; 0], другой же – на
. Воспользуемся первым в
ариантом
формата функцииroot.
Правый корень уравнения по графику
приближенно равен 1. Поэтому выполним
присвоение x
:=
1, вызовем функцию root,
укажем два первых аргумента
и нажмем клавишу =. На экране получим
результат 1.062. Теперь воспользуемся
вторым вариантом шаблона. Снова вызовем
функциюroot,
укажем четыре аргумента
и нажмем клавишу =. На экране получим
результат
,
если
,
и на достижение точности, задаваемое
переменнойTOL,
если ее значение меньше
.
Значение этой переменной меньше, чем
,
задавать не рекомендуется, т.к. может
нарушиться сходимость вычислительного
процесса.
можно получить так:
.
.
Получим его запись по степенямx
.
Для этого, как было описано в первом
занятии, выделим в этой записи переменное
x
,
выберем в меню Symbolics
пункт Variable
и в раскрывшемся окне пункт Collect:
.
.
.
Найдем его корни тремя способами:
,
,
.
Попробуйте с помощью символьных
преобразований найти корни такого
многочлена. Попробуйте с помощью
символьных преобразований найти корни
многочлена четвертой степени.
.
.При
использовании символьных вычислений
следует быть осторожными. Так при
нахождении нулей следующей функции
МС14 выдает только одно значение:
,
хотя на промежутке
эта функция имеет 6 нулей:
.
В более ранней версии системы (МС2000)
указывались все нули.
.
.
Требуется построить график этой функцииy
(x
)
на
отрезке .
получим рис.23. Согласно ему корень лежит
на отрезке . При
получим рис. 24. Корень лежит на отрезке
. В итоге можно ожидать, что корень
при любыхx
лежит на отрезке 
Численные методы: решение нелинейных уравнений
Метод деления пополам
, либо 
.
Метод Ньютона: теоретические основы
, то следующее приближение определяется как корень касательной к функции , проведенной в точке .
, в противной ситуации сходимость есть лишь в некоторой окрестности корня.
Визуализация метода Ньютона
= 1.5.
=
Метод Ньютона: приложение на С++
Метод секущих
и продолжают их пока модуль разности соседних приближений убывает.
Метод парабол
Метод простых итераций
и — сжатие: (в частности, тот факт, что — сжатие, как легко видеть, означает, что).
существенно, ибо если, например, на , то неподвижная точка отсутствует, хотя производная равна нулю. Скорость сходимости зависит от величины . Чем меньше , тем быстрее сходимость.Введение
1. Метод половинного деления (метод бисекции)
3. Метод секущих
4. Метод простой итерации