ОДИН АЛГОРИТМ НАХОЖДЕНИЯ КОРНЯ УРАВНЕНИЯ

Соловьёва Дарья Игоревна

Россия, г. Москва, гимназия 1516, 11 класс

Введение

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

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

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

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

Для этого вводится аналог ускорения свободного падения (или «поднятия»), значение которого, как и выбор начальной скорости и модуля этой скорости определяется с учётом геометрии линии , её производной, участком выпуклости и вогнутости, возрастания и убывания на участке .

Основные этапы решения уравнения

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

Корнем, или решением, уравнения  называется значение , при котором .

Решение этой задачи осуществляется в два этапа. Первый этап называется этапом локализации (или отделения) корней, а второй – этапом приближённого вычисления (уточнения)  корней. Оба этапа основаны на теореме о существовании единственного корня на отрезке.

Теорема. Пусть функция удовлетворяет условиям:

а) непрерывна на отрезке ;

б)  строго монотонна на отрезке ;

в)   принимает на концах отрезка  значения разных знаков, т. е. .

Тогда на отрезке  существует единственный корень уравнения .

Отрезок , содержащий только один корень  уравнения , называют отрезком локализации корня .

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

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

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

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

                                                                             (1)

где  х*  — истинное значение корня ( ƒ( х* ) = 0 ),

       n — количество итераций (шагов деления).

Из (1) следует, что точность ε будет достигнута, если количество шагов n будет ближайшим натуральным числом, большим, чем ln( b – a ) / ln2 - 1.

Из неравенства (1) также следует, что метод половинного деления сходится со скоростью геометрической прогрессии, знаменатель, который равен 0,5.

Этот метод самый надёжный, то есть его можно применить практически всегда. Единственным условием его применения является непрерывность исследуемой функции.

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

Если в каждой точке отрезка [a; b] локализации корня уравнения   график функции y = ƒ(x) имеет касательную, сохраняет направление выпуклости, а функция ƒ(х) строго монотонна, в качестве приближения к корню x* можно взять точку пересечения касательной, проведенной на одном из концов отрезка, с осью абсцисс. Из рисунков 1 и 2 видно, что в случае вогнутой кривой (ƒ″ > 0), касательную следует проводить  в  том  конце  [a,b], где функция принимает положительное значение; для выпуклой кривой (ƒ″ (x) < 0) приближение к корню достигается при использовании касательной на том конце отрезка, где функция имеет отрицательное значение.

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

Начальное приближение выбирается в соответствии со следующим правилом

На практике часто используется также такое правило выбора начального приближения. В качестве x0 берется тот конец отрезка локализации корня, для которого выполняется неравенство                                                             

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

Теорема. Если на отрезке xÎ[a,b] выполняется условия:

1)     ƒ(x) дважды непрерывно дифференцируема;

2)     ,                                                                                                 

3)     начальное приближение x0 располагается столь близко к корню x*, что справедливо неравенство                                                                

то итерационный процесс Ньютона сходится к корню x*.

Причем справедлива оценка

Рис. 3. Сходимость метода Ньютона

Алгоритм метода физической аналогии

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

Введём в координатную плоскость аналог ускорения свободного падения . В отличие от физического понятия ускорения тел предлагается ввести понятие ускорения фиктивной материальной точки, которая определена на плоскости, где ищется точка пересечения графика заданной функции с осью абсцисс. Фиктивное ускорение, определяемое вектором , направленно противоположно или по оси абсцисс. Если , то  направлено «влево» (противоположно оси ). Если , то направлено «вправо» (по оси ).

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

Возможно четыре случая:

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

В частности:

а) ;     б) ;         

в) ;     г) .

3. Пусть материальная точка проходит отрезок  локализации корня за максимальное время τmax = 1. По оси  скорость постоянна, тогда . Тогда компонента начальной скорости по  .

4. Найдём максимальное значение параметра  из уравнений движения материальной точки из  в , где τ примем за 1.

Для а) и г)   такое значение ; для б) и в) —. Тогда общая формула .

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

5. Запишем уравнения движения материальной точки из  в . Из полученного уравнения найдём:

6. Подставив значение в уравнение движения материальной точки по оси , найдём , которая будет являться новой точкой внутри отрезка локализации корня. За  примем , где , тогда

7. Критерием остановки итерационного процесса будет являться условие . Если , точность не достигнута, переходим к следующему шагу.

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

Рис. 4. Сходимость метода физической аналогии

Рис. 5. Наглядное сравнение сходимости метода Ньютона и метода физической аналогии

Заключение

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

Пример работы программы

Решение квадратного уравнения x2 + 2x -15 =0

=====================================================================

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

=====================================================================

Введите нижнюю границу отрезка локализации корня (a): 0

Введите верхнюю границу отрезка локализации корня (b): 125

Введите требуемую точность (epsilon): 0.00001

    промежуточное значение:          x =62.50000

            x =31.25000

x =15.62500

x =7.81250

                                                           x =3.90625

                                                           x =1.95313

                                                           x =2.92969

                                                           x =3.41797

                                                           x =3.17383

                                                           x =3.05176

                                                           x =2.99072

                                                           x =3.02124

                                                           x =3.00598

                                                           x =2.99835

                                                           x =3.00217

                                                           x =3.00026

                                                           x =2.99931

                                                           x =2.99978

x =3.00002

                                                           x =2.99990

                                                           x =2.99996

                                                           x =2.99999

                                                           x =3.00001

                                                           x =3.00000

Вычисленное значение корня уравнения: x=3.00000 найдено за 24 шага.

Нажмите любую клавишу...

=====================================================================

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

=====================================================================

Введите нижнюю границу отрезка локализации корня (a): 0

Введите верхнюю границу отрезка локализации корня (b): 125

Введите требуемую точность (epsilon): 0.00001

 промежуточное значение:  x =62.06349

                                               x =30.65860

                                               x =15.08200

x =7.53845

                                               x =4.20616

                                               x =3.13972

                                               x =3.00236

                                               x =3.00000

                                               x =3.00000

Вычисленное значение корня уравнения: x=3.00000 найдено за 9 шагов.

Нажмите любую клавишу...

=====================================================================

                             Метод физичекой аналогии.

=====================================================================

Введите нижнюю границу отрезка локализации корня (a): 0

Введите верхнюю границу отрезка локализации корня (b): 125

Введите требуемую точность (epsilon): 0.00001

Введите n (0<n<1), n=0.6

промежуточное значение:   x =24.93138

x =5.40092

x =2.91669

                                               x =3.17573

                                               x =3.00143

                                               x =3.00000

                                               x =3.00000

Вычисленное значение корня уравнения: x=3.00000 найдено за 7 шагов.

Нажмите любую клавишу...

Список литературы

1.          Курош А. Г. Курс высшей алгебры. –– М.: Наука, 1968.– 432 с.

2.          Амосов А. А., Дубинский Ю. А., Копченова Н. В. Вычислительные методы для инженеров. — М.: Высш. шк., 1994. –554 с.