- •§ 2. Решение нелинейных алгебраических уравнений с одной переменной
- •§2. Решение нелинейных алгебраических уравнений с одной переменной
- •2.1. Задача отделения корней. Уточнение корней методом половинного деления (метод дихотомии)
- •Методом хорд (секущих)
- •Методом касательных (Ньютона)
- •Методом итераций
- •Методом парабол
- •2.7. Методы ускорения сходимости
2.1. Задача отделения корней. Уточнение корней методом половинного деления (метод дихотомии)
Вобщем случае редко удается точно найти все корни в алгебраических уравнениях, а если к тому же коэффициенты в уравнении даны с погрешностью, то вопрос о точном определении корней вообще теряет всякий смысл. Однако если предположить, что задано уравнение типа (1.15), то тогда без ограничения общности можно утверждать, чтоF(х) имеет корни, для которых существует окрестность, содержащая только один простой корень. Такой корень иногда называют изолированным. В результате общая задача нахождения корней или нулей функции будет состоять из следующих этапов:
отделения корней, т.е. установления интервала , где содержится один и только один корень уравнения;
задачи уточнения одним из известных методов найденного корня xс заданной погрешностьюe.
Предположим теперь, что найден отрезок [а, b] такой, чтоF(а)F(b)< 0. Тогда, согласно теореме Больцано-Коши [Бахвалов, 1973б], внутри отрезка [а, b] существует точкаx, в которойF(x)= 0. Далее необходимо убедиться, что найденная точкаxединственная на отрезке [а, b]. Одним из методов является деление отрезка на несколько частей, например на четыре, и проверка на концах каждого из отрезков знака функции.
Нули функции на практике вычисляют приближенно несколькими способами. Одним из самых распространенных и не очень точных является графический метод, заключающийся в том, чтоF(х) представляют какF(х)= =j(х)+ y(х), гдеj(х) иy(х) более простые по сравнению сF(х) функции. Далее строят два графикаy = j(х); y = y(х) и определяют точки их пересечения. Этим методомвыгодно решать уравнения вида хn + ах + b = 0 или ах + b + sin(сх)= = 0 и т.п. Но следует помнить, что этот метод дает лишь грубое приближение решения.
Другим, не менее распространенным является метод производных. Он заключается в том, что ищут и приравнивают к нулю производную функции F'(х). Затем на отрезкахрассматривают знакфункции F'(х), гдехi - корни уравненияF'(х)= 0. Таким образом, всю числовую ось разбивают на два интервала и более.Этот метод еще называют методом экстремумов функции.
Если исследуемая функция представлена полиномом n-й степени, то используют метод удаления корней: определяют один корень, и по теореме Виетта функциюF(х) представляют какF(х)= g(х)(х - х1), гдеx1 - первый найденный корень, аg(х) - полином степени (n - 1). Для проверки кратности корняx1 следует подставить вg(х),и еслиg(x1)=0, то говорят, чтоx1 являетсякратным корнем, аF(х) записываетсяF(х)= g(х)(х - x1)2, гдеg(х) - теперь полином степени (n -2). Следуя этому процессу, можно удалить все корни, т.е. представить
.
Чтобы погрешность с каждым шагом не увеличивалась, а очередной корень определялся с высокой степенью точности, следует уточнение корня делать по F(х), а не поg(х). Это особенно важно, когда удалено много (больше половины) корней.
Hа практике предполагаемые корни уточняют различными специальными вычислительными методами. Одним из них можно назвать метод дихотомии (бисекции, половинного деления), относящийся к итерационным. Он состоит в построении последовательности вложенных отрезков, на концах которыхF(х) имеет разные знаки. Каждый последующий отрезок получают делением пополампредыдущего. Этот процесс построения последовательности вложенных отрезков позволяет найти нуль функции (F(х) = 0) с любой заданной точностью.
Опишем подробно один шаг итерации. Пусть на k-м шаге найден отрезок [аk , bk],на концах которого F(х) меняет знак. Заметим, что обязательно [аk, bk]О [а, b].Разделим теперь отрезок [аk, bk] пополам и выделим F(x), гдеx- середина [аk , bk]. Здесь возможны два случая: первый, когдаF(x) = 0, тогда мы говорим, что корень найден; второй, когдаF(x)¹0, тогда сравниваем знакF(x) сF(аk) иF(bk) и из двух половин [аk, x] и [x, bk] выбираем ту, на концах которой функция меняет свойзнак. Таким образом,аk = а , bk = x, еслиF(x)F(аk) < 0 , иаk =x , bk = b, еслиF(x)F(bk) < 0.
При заданной точности e деление пополам продолжают до тех пор, пока длина отрезка не станет меньше 2e, тогда координата середины последнего найденного отрезка и есть значение корня требуемой точности.
Метод дихотомии — простой и надежный метод поиска простого корня1уравненияF(х) = 0. Он сходится для любых непрерывных функцийF(х), в том числе и недифференцируемых. Недостатки метода:
проблема определения отрезка, на котором функция меняет свой знак (как правило, это отдельная вычислительная задача, наиболее сложная и трудоемкая часть решения);
если корней на выделенном отрезке несколько, то нельзя заранее сказать, к какому из них сойдется процесс;
не применим к корням четной кратности;
для корней нечетной, но высокой кратности метод неустойчив, дает большие ошибки;
медленно сходится. Для достижения eнеобходимо выполнить N итераций2, т.е. для получения 3 верных цифр (e = 0.0005) надо выполнить около 10 итераций, если отрезок имеет единичную длину.
Программа, по которой можно вычислить корни методом дихотомии, построена по следующему алгоритму:
Определить входные параметры А, В, ЕРS.
Присвоить: А1Ь А;В1Ь В;КЬ0.
Присвоить: Х1ЬА1;Х2Ь В1;КЬ К+ 1;Х3Ь (В1+А1)/2.
Если F(Х1)´F(Х3) < 0, то перейти на шаг 5 иначе на шаг 7.
Присвоить: В1ЬХ3.
Если | А1 -В1| <ЕРS, то перейти на шаг 10 иначе на шаг 3.
Если F(Х2)´F(Х3) < 0, то перейти на шаг 8 иначе на шаг 11.
Присвоить: А1Ь Х3.
Перейти на шаг 6.
Печать: Х3 - корень уравнения;К- количество итераций.
| А1 -В1| / 2 - погрешность решения.
Конец программы.
Это наиболее простое решение задачи, но не самое эффективное. Эффективность можно повысить, если:
заменить произведения F(х1)×F(х3) иF(х2)×F(х3) на использование встроенной функции sign(х, у). В тех версиях языка, где нет этой встроенной функции, можно заранее написать соответствующую процедуру;
определить процедуру-функцию, вычисляющуюF(х) только один раз;
заменить в операторе цикла медленный оператор (А+В)/2 на более быстрый (А+В)*0.5. Заметим, что именно для этой программы данное усовершенствование будет незаметно, хотя в случае больших программ учет скорости выполнения операций в машине дает ощутимый результат.
Формальные параметры процедуры. Входные: a,b(типreal) - определяют длину отрезка;eps(типreal) - определяет заданную точность вычислений;it(типinteger) - определяет наибольшее разрешенное количество итераций (для избежания зацикливания процесса в случае неправильного определения отрезка).Выходные:х(типreal) -в нем содержится искомый корень сравнения; k (тип integer) - в него заносится количество выполненных итераций.
Учитывая все замечания, окончательный вариант процедуры bisect может быть следующим:
procedure bisect (a,b,eps :real; it:integer;
var x : real; var k:integer);
var a1, b1: real; x1, x2, x3 : integer;
begin
k := 0;
x1 := sign (func(a));
x2 := sign (func(b));
a1 := a;
b1 := b;
repeat
inc (k);
x := (a1+b1)*0.5;
x3 := sign (func (x));
if x3=0 then exit;
if abs(b1-a1)<(2*eps) then exit;
if (x1=x2) and (x2=x3) then exit;
if x1=x3 then
begin
a1 := x;
x1 := x3;
end
else
begin b1 := x;
x2 := x3;
end;
until k>it;
end.
Перед началом работы программы определяют func(x) - процедуру-функцию, по которой вычисляют значенияF(х).Тип функции должен быть вещественным. Если в библиотеке стандартного математического обеспечения отсутствует процедура-функцияsign, то ее следует написать самостоятельно.
Предложенная процедура проверялась напримеререшения уравненияx2- 5 sinx= 0.
Графическим методом находился отрезок,на котором располагался один из корней данного уравнения [1.57; 3.14]; (второй корень тривиальный,х = 0 находится легко). Для того, чтобы найти корень на отрезке [1.57; 3.14]с указанной точностью, полагали ерs = 0.0005.
Результаты проверки работы предлагаемой процедуры приводятся в табл. 1.5.
Таблица 1.5
Отрезок |
Номер | |||||
Левый конец |
Правый конец |
Центральная точка |
итерации | |||
А |
sign (А) |
В |
sign (В) |
x |
sign (x) |
k |
1.0 |
— 1 |
4.0 |
+1 |
2.5000 |
|
0 |
1.000000 |
— 1 |
2.500000 |
+1 |
1.750000 |
+1 |
1 |
1.750000 |
— 1 |
2.500000 |
+1 |
2.125000 |
+1 |
2 |
1.750000 |
— 1 |
2.125000 |
+1 |
1.937500 |
— 1 |
3 |
1.937500 |
— 1 |
2.125000 |
+1 |
2.031250 |
— 1 |
4 |
2.031250 |
— 1 |
2.125000 |
+1 |
2.078125 |
— 1 |
5 |
2.078125 |
— 1 |
2.125000 |
+1 |
2.101563 |
— 1 |
6 |
2.101563 |
— 1 |
2.125000 |
+1 |
2.089844 |
+1 |
7 |
2.101563 |
— 1 |
2.089844 |
+1 |
2.083984 |
+1 |
8 |
2.101563 |
— 1 |
2.083984 |
+1 |
2.086914 |
— 1 |
9 |
2.086914 |
— 1 |
2.083984 |
+1 |
2.085449 |
+1 |
10 |
Окончаниие таблицы 1.5
Отрезок |
Номер | |||||
Левый конец |
Правый конец |
Центральная точка |
итерации | |||
А |
sign (А) |
В |
sign (В) |
x |
sign (x) |
k |
2.086914 |
— 1 |
2.085449 |
+1 |
2.086182 |
— 1 |
11 |
2.086182 |
— 1 |
2.085449 |
+1 |
2.085815 |
+1 |
12 |
2.085815 |
— 1 |
2.086182 |
+1 |
2.085999 |
— 1 |
13 |
2.085815 |
— 1 |
2.085999 |
+1 |
2.085907 |
+1 |
14 |
2.085815 |
— 1 |
2.085907 |
+1 |
2.085953 |
— 1 |
15 |
2.085907 |
— 1 |
2.085953 |
+1 |
2.085930 |
+1 |
16 |
2.085930 |
— 1 |
2.085953 |
+1 |
2.085941 |
— 1 |
17 |
РЕШЕНИЕ: Х = 2.085936; F(x) = 0.0000066938; К = 18 |
2.2. ПРИБЛИЖЕННОЕ РЕШЕНИЕ УРАВНЕНИЯ F(x)= 0