Лабораторная работа 5.

Численное решение нелинейных уравнений с заданной точностью.

РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

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

Краткие сведения Основные понятия

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

(3.11)

где функция f(x) определена и непрерывна на некотором конечном или бесконечном интервале

Если функция представляет многочлен, то уравнение (3.11) называется алгебраическим. Если х находится под знаком трансцендентной функции (показательной, логарифмической, тригонометрической и т. п.), уравнение (3.11) называется трансцендентным. Значение, при котором выполняется условие, называ-

етсякорнем уравнения (3.11).

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

Процесс отыскания корня уравнения (3.11) состоит из двух этапов: 1) нахождение приближенного значения корня; 2) уточнение приближенного значения до некоторой заданной степени точности.

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

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

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

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

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

Для этого метода существенно, чтобы функция f(х) была непрерывна и ограничена в заданном интервале [а, Ь], внутри которого ищется корень. Предполагается также, что значения функции на концах интервала f(a) и f(b)имеют разные знаки, т. е. выполняется условие f(a)f(b)<0.

Рис. 3.9. Геометрическая интерпретация метода деления отрезка пополам.

Для нахождения корня уравнения f(x)—0отрезок [а, Ь] делят пополам, т. е. выбирают начальное приближение равнымх[0] = = (а + Ь)/2 (рис. 3.9). Если f(x[0])=0, то х[0] является корнем уравнения. В противном случае выбирают тот из отрезков [а, х[0]] или [х[0], Ь], на концах которого функция f(x) имеет разные знаки, ибо корень лежит на этой половине. Для случая, изображенного на рис. 3.9, выбирают интервал [х[0], Ь]. Данный интервал вновь делят пополам и выбирают ту половину, на концах которой функция имеет противоположные знаки, и т. д. Если требуется определить корень с точностью е, то деление пополам продолжают до тех пор, пока длина отрезка не станет меньшеВ этом случае середина последнего отрезка дает значение корня с требуемой точностью.

Рассмотренный метод прост и надежен, устойчив к ошибкам округления. Обладает достаточно быстрой сходимостью. За одну итерацию точность увеличивается примерно вдвое. Метод удобно программируется на ЭВМ, так как требует простых и цикличных вычислений. Основной недостаток его состоит в следующем. Если на отрезке [а, Ь] имеется несколько корней, то заранее неизвестно, к какому из них сойдется процесс.

Вариант 2.

Метод деления отрезка пополам

Для разрывных функций, а также. если не требуется быстрая сходимость, для нахождения корня на интервале (a, b) применяют надежный метод деления отрезка пополам. Его алгоритм основан на построении рекуррентной последовательности по следующему закону: в качестве начального приближения выбираются границы интервала, на котором точно имеется один простой корень далее находится его середина очередная точка x₃ выбирается как середина того из смежных с x₂ интервалов или , на котором находится корень. В результате получается следующий алгоритм метода деления отрезка пополам:

1. Вычисляем .

2. Вычисляем .

3. Если тогда

иначе .

4. Если тогда повторять с п.2.

5. Вычисляем

6. Конец.

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

Метод последовательных приближений

Уравнение (3.11) можно представить в форме

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

где с — произвольная постоянная. В этом случае

Задаются начальным приближением х[0], а последующие приближения определяют итерационной процедурой вида

Эта итерационная процедура сходится, если на отрезке [а, Ь], содержащем корень, а также все его последовательные приближения

Рис. 3.10. Геометрическая интерпретация метода последовательных приближений.

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

что в качестве очередного приближения принимается не значение , а точка пересечения прямойс хордой, проведенной между двумя соседними приближениями (рис. 3.10). В соответствии с рис. 3.10 имеем:. Очередное приближение х[2] получают путем определения точки пересечения прямой и хорды, проведенной через точки

, т. е.

Следущая итерация выполняется для начальной точки

В общем случае

При k = 0, 1,2, ...

Итерационный процесс завершается при выполнении следующих, условий:

где

Метод последовательных приближений обладает тем важным ) преимуществом, что при его использовании не накапливаются ; ошибки вычислений. Ошибка вычислений эквивалентна ухудшению / очередного приближения, а это может отразиться только на числе Iитераций, но не на точности результата. Метод устойчив даже по отношению к грубым ошибкам (сбоям ЭВМ).

Вариант 2.

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

Для использования метода итерации исходное нелинейное уравнение f(х) = 0 заменяется равносильным уравнением

x = (x).

(8)

Пусть известно начальное приближение корня х = х₀. Подставляя это значение в правую часть уравнения (8), получим новое приближение:

х₁ = (х₀).

Далее, подставляя каждый раз новое значение корня в (8), получаем последовательность значений:

(9)

Геометрически метод итерации может быть пояснен следующим образом. Построим на плоскости хОу графики функций у = х и у = (х). Каждый действительный корень уравнения (8) является абсциссой точки пересечения М кривой у = (х) с прямой у = х (Рисунок 6, а).

Рисунок 6.

Отправляясь от некоторой точки А₀[x₀,(x₀)], строим ломаную А₀В₁А₁В₂А₂... (“лестница”), звенья которой попеременно параллельны оси Ох и оси Оу, вершины А₀, А₁, А₂, ...лежат на кривой у=(х), а вершины В₁, В₂, В₃, …, - на прямой у = х. Общие абсциссы точек А₁ и В₁, А₂ и В₂, ..., очевидно, представляют собой соответственно последовательные приближения х₁, х₂, ... корня .

Возможен также другой вид ломаной А₀В₁А₁В₂А₂ ... - “спираль” (Рисунок 6, б). Решение в виде “лестницы” получается, если производная ' (х) положительна, а решение в виде “спирали”, если ' (х) отрицательна.

На Рисунке 6, а, б кривая у =  (х) в окрестности корня - пологая, то есть <1, и процесс итерации сходится. Однако, если рассмотреть случай, где >1, то процесс итерации может быть расходящимся (Рисунок 7).

Рисунок 7.

Поэтому для практического применения метода итерации нужно выяснить достаточные условия сходимости итерационного процесса.

Теорема: Пусть функция (х) определена и дифференцируема на отрезке [a, b], причем все ее значения (х) [a, b].

Тогда, если существует правильная дробьqтакая, что

q < 1

при a < x < b,то: 1) процесс итерации

сходится независимо от начального значения х_{0 }[a, b];

2) предельное значениеявляется единственным корнем уравнениях = (х) на отрезке [a, b].

Пример 5. Уравнение

f(x) x^3 - x- 1 = 0

(10)

имеет корень [1, 2], так как f(1) = - 1 < 0 и f(2) = 5 > 0.

Уравнение (10) можно записать в виде

х = х^3 - 1.

(11)

Здесь

 (х) = х³ - 1 и ' (х) = 3х²;

поэтому

' (х) 3 при 1 х2

и, следовательно, условия сходимости процесса итерации не выполнены.

Если записать уравнение (10) в виде

(12)

то будем иметь:

.

Отсюда при 1 х2 и значит, процесс итерации для уравнения (12) быстро сойдется.

Найдем корень  уравнения (10) с точностью до 10^-2. Вычисляем последовательные приближения х_nс одним запасным знаком по формуле

Найденные значения помещены в Таблицу 1:

Таблица 1

Значения последовательных приближений x_i.

i	0	1	2	3	4
xi	1	1,260	1,312	1,322	1,3243

С точностью до 10^-2 можно положить  = 1,324.

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

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

Поскольку x – корень уравнения, то . Следовательно,

Таким образом, если нам известно приближенное значение корня уравнения, то полученное уравнение позволяет его уточнить. Понятно, что процесс уточнения можно повторять многократно, до тех пор, пока значение функции не будут отличаться от нуля на величину меньшую, чем заданная точность поиска. Очередное k-е приближение находится по формуле

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

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

(1.1)

Вариант 2.Пусть уравнениеимеет один корень на отрезке [а, Ь],причем первая и вторая производныеопределены, непрерывны и сохраняют постоянные знаки на отрезке [а, Ь].Выбирают некоторое начальное приближение корня 40] на интервале [а, Ь] и проводят касательную в точкек кривой y = f(x) до пересечения с осью абсцисс (рис. 3. 11). Абсциссу принимают за очередное приближение корня. Уравнение касательной в точкеимеет вид

Полагая у = 0, находят абсциссу:

Далее проводят касательную через новую точкуи

находят точку ее пересечения с осью абсцисс:

Эту точку принимают за новое приближение корня. Аналогично находят последующие приближения:

Итерационный процесс прекращают при выполнении условий:

_где— заданная погрешность вычислений.

Рис. 3.11. Геометрическая интерпретация метода Ньютона.

Начальное приближениецелесообразно выбирать из условия

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

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

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

Задание

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

2. Решить нелинейные уравнения, приведенные в табл. 3.9, с помощью диалоговой системы. Начальное приближение корня выбрать из указанной области. Параметр EPS принять равным 0,00001.

Таблица 3.9

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

Варианты заданий

1. Создать и отладить программу отделения всех корней функцииf(x) на указанном интервале [a, b], в соответствии с полученным вариантом из табл. 1.1.

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

Выбрать точность e=10^-3,e=10^-4,e=10^-5. Функция должна проверить правильность определения корня (f(x^*) приблизительно равна нулю).

3. Решить уравнение для выбранного интервала методом деления отрезка пополам

Рис.1.7

Таблица 1.1

N	f(x)	Интервал		методы
		А	B
1		-2	2	Метод простой итерации
2		-1	3	Метод секущих
3		1	8	Метод простой итерации
4		4	7	Метод простой итерации
5		4	8	Метод секущих
6		2	6	Метод простой итерации
7		3	9	Метод секущих
8		-4	0	Метод секущих
9		-12	5	Метод Ньютона
10		-2	5	Метод Ньютона
11		-6	2	Метод Ньютона
12		-4	2	Метод Ньютона
13		-7	3	Метод секущих
14		-4	3	Метод простой итерации
15		-4	4	Метод секущих

Примечание.

В табл. 1.1. все функции на указанном интервале имеют три корня.

Контрольные вопросы

1. Как решается задача нахождения корней уравнения?

2. В чем суть метода простой итерации и условие его сходимости?

3. Дайте геометрическую интерпретацию метода Ньютона.

4. В чем отличие метода Вегстейна от метода секущих?

5. Дайте геометрическую интерпретацию метода секущих (хорд).

Таблица 1. Индивидуальные задания

№ варианта	Уравнение f(x)=0	Диапазон поиска корней
		A	B
1		1	3
2		1	4
3		2	4
4		3	6
5		2	6
6		1	8
7		1	6
8		2	6
9		1	7
10		2	8
11		2	3
12		1	4
13		2	8
14		1	2
15		4	14

[Вверх] [В начало]