Решение нелинейных уравнений

Решение нелинейных уравнений Постановка задачи Пусть требуется решить уравнение (1) f ( x)  0 , где f(x) – непрерывная функция, заданная в конечном или бесконечном интервале. Если f(x) содержит только алгебраические функции (целые, рациональные, иррациональные), то уравнение называют алгебраическим. В частности, многочлен является целой алгебраической функцией. Уравнение, содержащее другие функции (тригонометрические, показательные, логарифмические и др.), называются трансцендентным. Всякое значение x  x * , обращающее f(x) в ноль, называют корнем этого уравнения. Корень называется изолированным, если существует окрестность, в которой этот корень единственный. Задача: найти изолированные корни уравнения (1). Методы решения нелинейных уравнений делятся на: - прямые методы, позволяющие записать корни в виде некоторого конечного соотношения – формулы (применимы для достаточно узкого класса уравнений); - итерационные методы – методы последовательных приближений (в общем случае на практике можно говорить лишь о приближенном вычислении корней уравнений (1)). Алгоритм нахождения корня уравнения с помощью итерационного метода состоит из двух этапов: - отделение корней – отыскания приближенного значения корня или содержащего его отрезка; - уточнение значения корня до некоторой заданной степени точности. Этап отделения корней При отыскании действительных корней этап отделения производится графически или аналитически, основываясь на следующей теореме. Теорема 1. Если непрерывная функция f(x) принимает значения разных знаков на концах отрезка a; b , т. е. f (a )  f (b)  0 , то внутри этого отрезка существует по меньшей мере один корень уравнения f ( x)  0 , т. е. существует x * , т. ч. f ( x * )  0 . Корень x * будет единственным на a; b если f (x ) существует и сохраняет знак внутри интервала a; b . Пример 1. Графический способ локализации корней. Рассмотрим уравнение 1 f ( x)  x 2  sin x  1  0 . Представим исходное уравнение в виде x 2  sin x  1 и построим графики функций y  x 2  1 и y  sin x (рисунок 1). Рисунок 1. Графическая локализация корней уравнения из примера 1 Из графика видно, что уравнение имеет два корня x1*   1;0 и x2*  1;  . Пример 2. Аналитический способ локализации корней. Рассмотрим уравнение f ( x)  ln x  x 2  0,5  0 . Функция f(x) определена при x  0 . Таблица 1. Знак функции f(x) из примера 2 x 0,1 0,5 sign f(x) (–) (–) 1 (+) 1  2x2 f ( x )   0 при x  0 , т. е. единственный корень x *  0,5; 1 . x Этап уточнение корней Этап уточнения корней заключается в вычислении приближенного значения x n корня с заданной точностью   0 . Приближенное значение корня уточняют с помощью различных итерационных методов. Итерационный процесс состоит в последовательном уточнении начального приближения x0  a; b . Каждый такой шаг называется итерацией. В результате итераций находится последовательность приближенных значений корня x1 , x 2 , …, x n . Если эти значения с ростом n приближаются к истинному значению корня, то говорят, что итерационный процесс сходится. Итерационные методы, дающие в пределе решение данной задачи при любом начальном приближении x0 , называются глобально сходящимися. Если 2 сходимость итерационной последовательности имеет место при задании x0 из некоторой окрестности x * , то метод называют локально сходящимся. Типы сходимостей итерационных последовательностей Пусть некоторый итерационный  последовательность  xn n 0 с пределом x * . процесс генерирует Определение 1. Сходимость последовательности  xn  к x * называется линейной, а итерационный процесс – линейно сходящимся, если существует такая постоянная C  0; 1 и такой номер n0 , что n  n0 . x*  xn 1  C x*  xn К линейной сходимости применяют также термин сходимость со скоростью геометрической прогрессии. Определение 2. Говорят, что последовательность  xn  сходится к x * по меньшей мере с p-м порядком, а итерационный процесс имеет по меньшей мере p-й порядок, если существуют такие константы C  0 и p  1 , что x*  xn 1  C x*  xn p n  n0 . Замечание. О порядке метода судят также по неравенству вида p xn 1  xn  C xn  xn 1 , показывающему скорость сближения членов итерационной последовательности. Теорема 2. Пусть x * – точный, а x n – приближенный корень уравнения (1), принадлежащие отрезку a; b , причем f ( x )  m1  0 . Справедлива оценка f ( xn ) . (2) x *  xn  m1 Замечание. Неравенство (2) обосновывает контроль точности по невязкам, т. е. критерий окончания итерационного процесса f ( xn )    x*  xn с точностью  , если в окрестности x * выполняется условие f ( x )  1 . В случае если f ( x )  1 , необходимо учитывать множитель f ( xn )  m1  x*  xn . Рассмотрим некоторые алгоритмы. 3 1 , т. .е. m1 Метод половинного деления Пусть требуется уточнить единственный корень уравнения f ( x)  0 , ab принадлежащий отрезку a; b (отрезок неопределенности), точка c  – 2 середина a; b . Если f (c)  0 , корень найден. В противном случае для дальнейшего рассмотрения оставляем ту половину a; c или c; b, на концах которой значения f(x) различны (рисунок 2). Рисунок 2. Метод деления отрезка пополам При этом получается последовательность вложенных отрезков, содержащих искомый корень. На каждом шаге длина отрезка неопределенности уменьшается вдвое. В результате последовательного сужения отрезка a; b получим ba x *  xn  n 2 Метод довольно медленный, но сходится всегда, т. е. решение получается всегда, причем с заданной точностью1. Условие окончания поиска корня может быть, например, ba  , f (c)   или 2n где  – точность, a; b – начальный отрезок, n – число итераций. На рисунке 3 приведена блок-схема итерационного процесса нахождения корня уравнения методом половинного деления. Здесь ε – допустимая абсолютная погрешность корня или полудлина его промежутка неопределенности, δ – допуск, связанный с реальной точностью вычислений значений данной функции. Сужение отрезка производится заменой границ a или b на текущее значение корня c. 1 Метод половинного деления является линейно сходящимся методом (метод первого порядка). Он сходится со скоростью геометрической прогрессии со знаменателем 0,5 [1]. 4 Рисунок 3. Блок-схема метода деления отрезка пополам Метод хорд В методе дихотомии точка c вычисляется как середина отрезка и не учитываются вычисляемые на каждом шаге значения функции. Лучший результат можно получить, если находить c как абсциссу точки пересечения оси Ox с хордой AB дуги графика функции f(x) (рисунок 4). Рисунок 4. Дуга графика функции f(x) и стягивающая ее хорда Запишем уравнение прямой, проходящей через две данные точки A и B: 5 y  f (a ) xa  . f ( b)  f ( a ) b  a Полагая y  0 , x  c , получим f (a )b  a  ca (3) f ( b)  f ( a ) Этот метод называется методом хорд (метод пропорциональных частей, метод линейной интерполяции). Метод быстро сходится, если функция f(x) близка к линейной. Но может оказаться, что метод хорд проигрывает по скорости сходимости2 методу половинного деления (рисунок 5) [1]. Рисунок 5. Приближения к корню нелинейного уравнения по методу хорд Существует несколько версий реализации метода хорд. Одна из них – вычисление значения c по формуле (3) в рамках алгоритма половинного деления. Расчет ведется до совпадения значений c на двух соседних итерациях m1 с точностью (лучше, с точностью , если  M 1  m1 0  m1  f ( x)  M1 x  a; b [1]). Блок-схема для метода хорд аналогична представленной на рисунке 3 для метода половинного деления, только для расчета корня необходимо использовать формулу (3) вместо нахождения середины отрезка и добавить вычисление функции f(x) на границах новых отрезков. Другая реализация метод хорд – с фиксированной точкой, когда в процессе итераций фиксируется левый или правый конец отрезка a; b : z  a или z  b в зависимости от условия f ( z )  f ( z )  0 . Тогда - при фиксированном левом конце хорд z  a : начальная точка x0  b ; - при фиксированном правом конце хорд z  b : начальная точка x0  a . Приближение xn 1 находится как абсцисса точки пересечения прямой, проходящей через точки z; f ( z )  и xn ; f ( xn )  , с осью Ox (рисунок 6) Метод хорд, как и метод половинного деления является методом первого порядка и в зависимости от свойств f(x) может иметь как большую, так и меньшую, чем метод половинного деления, среднюю скорость сходимости (часто большую) [1]. 2 6 x n 1  x n  f ( xn )  z  xn  . f ( z )  f ( xn ) (4) Рисунок 6. Приближения к корню нелинейного уравнения по методу хорд при фиксированном левом конце отрезка a; b Метод Ньютона (метод касательных) Правило построения итерационной последовательности здесь получается из геометрических соображений, отсюда название метод касательных, или заменой функции f(x) ее линейной моделью, отсюда название метод линеаризации. В зарубежной литературе его часто называют методом Ньютона-Рафсона. Итерационный процесс Ньютона определяется формулой: f ( xn ) xn 1  xn  , n  0, 1, 2, (5) f ( xn ) Метод быстро сходится. Сходимость метода определяется следующей теоремой. Теорема 3. Если f (a )  f (b)  0 , причем f (x ) и f (x ) отличны от нуля и сохраняют знак при x  a; b, то, исходя из начального приближения x0 , f ( x0 )  f ( x)  0 , удовлетворяющего условию можно вычислить единственный корень x * с любой степенью точности. Геометрический смысл метода Ньютона (рисунок 7): приближения к корню x * осуществляются по абсциссам точек пересечения касательных к графику функции f(x), проводимых в точках, соответствующих предыдущим приближениям. 7 Рисунок 7. Приближения к корню нелинейного уравнения методом касательных Если функция f(x) вблизи корня имеет производную близкую к нулю, метод Ньютона применять не рекомендуется. Оценка погрешности метода M 2 x *  xn  2 xn  xn 1  , 2m1 где M2 – наибольшее f (x ) , m1 – наименьшее f (x ) на a; b 3. 2m1 , то полагают x *  xn , где  – заданная точность. M2 Часто применяют упрощенное правило останова xn  xn 1    x*  xn . Если xn  xn 1  Метод секущих Итерационный процесс определяется формулой f ( xn ) xn 1  xn  , (6) xn 1  xn  f ( xn 1 )  f ( xn ) где n  1, 2, 3, , а x0 и x1 должны задаваться. Метод является двухшаговым: результат (n + 1)-го шага зависит от результатов n-го и (n – 1)-го шагов. На каждой итерации требуется вычисление только одного значения функции, другое значение передается с предыдущего шага. Геометрический смысл метода секущих (рисунок 8): xn 1 – абсцисса точки пересечения с осью Ox секущей, т. е. прямой, проведенной через точки xn 1; f ( xn 1 ) и xn ; f ( xn ) . 3 Метод касательных – метод второго порядка. 8 Рисунок 8. Приближения к корню нелинейного уравнения методом секущих Метод секущих и метод хорд определяются однотипными формулами, но выводятся они из различных соображений, что сказывается на свойствах и скорости сходимости получаемых последовательностей приближений. 1 5  1,618 .4 Метод секущих имеет порядок по крайне мере 2 Высокий порядок сходимости метода секущих в сочетании с минимальными вычислительными затратами – одно вычисление значения функции на один итерационный шаг – делает его одним из самых эффективных методов решения уравнений вида (1) по сравнению с другими итерационными методами. Начальную точку x0 в методе секущих можно выбрать как в методе касательных, а вторую точку x1 взять в непосредственной близости от x0 , желательно между x0 и искомым корнем x * . Заканчивается итерационный процесс по условию f ( xn )   или xn  xn 1   . Погрешность вычислений по формуле (6) может начать превосходить погрешность метода из-за вычитания приближенно вычисляемых близких значений f ( xn 1 ) и f ( xn ) в знаменателе формулы, поэтому важно вовремя остановить процесс вычислений. В плане численной устойчивости метод секущих уступает методу Ньютона. Комбинированный метод хорд и касательных Методы хорд и касательных дают приближения корня с разных сторон. Поэтому их часто применяют в сочетании друг с другом, тогда уточнение корня происходит быстрее. Метод секущих сходится двушагово квадратично – для многошаговых методов иногда вводят специфическое понятие порядка сходимости. 4 9 Рассмотрим случай, когда f ( x)  f ( x)  0 (рисунок 9а, 9в). В этом случае метод хорд дает приближенное значение корня с недостатком (конец b неподвижен), а метод касательных – с избытком (за начальное приближение берем точку b). Тогда вычисляем новые значения a и b: a – по формуле метода хорд, b – по формуле метода касательных. На первом щаге f (a )b  a  a1  a  , f ( b)  f ( a ) f ( b) . b1  b  f (b) В общем случае f (an )bn  an  an 1  an  , f (bn )  f (an ) f (bn ) , bn 1  bn  f (bn ) где a0  a , b0  b . Если f ( x)  f ( x)  0 (рисунок 9б, 9г), то новое значение a вычисляем по методу касательных, а значение b – по методу хорд. На первом шаге f (a ) , a1  a  f (a ) f (b)b  a  b1  b  . f ( b)  f ( a ) В общем случае f ( an ) a n 1  a n  , f (an ) f (bn )bn  an  bn 1  bn  , f (bn )  f (an ) где a0  a , b0  b . Вычислительный процесс прекращается, как только выполнится условие: bn 1  an 1   . 10 а) f ( x )  0 , f ( x )  0 f ( x)  f ( x)  0 а – метод касательных, b – метод хорд б) f ( x )  0 , f ( x )  0 f ( x)  f ( x)  0 а – метод хорд, b – метод касательных в) f ( x )  0 , f ( x )  0 f ( x)  f ( x)  0 а – метод касательных, b – метод хорд г) f ( x )  0 , f ( x )  0 f ( x)  f ( x)  0 а – метод хорд, b – метод касательных Рисунок 9. Приближения к корню нелинейного уравнения комбинированным методом хорд и касательных Гибридные алгоритмы Быстросходящиеся методы, такие как Ньютона и секущих, являются локально сходящимися (критичны к выбору x0 ). В связи с этим используется следующий прием: строятся гибридные алгоритмы на базе двух или нескольких методов, соединяя быструю сходимость одних с глобальной сходимостью других. Например, начинают процесс поиска корня методом 11 половинного деления, затем уточняют методом Ньютона (в окрестности точного значения x * ). Другой вариант: сразу начать процесс вычисления «быстрым» методом, но проводить корректировку получаемых значений с помощью глобально сходящегося метода, например, как в следующем алгоритме [1]. Метод Ньютона–метод половинного деления Шаг 0. Задать начальное приближение x0 , положить n  0 . f ( xn ) Шаг 1. Вычислить ~ . xn  xn  f ( xn ) xn ; иначе xn )  f ( xn ) , то xn 1  ~ Шаг 2. Если f ( ~ 1 ~ xn   xn  ~ xn  и возвратиться к началу шага 2. 2 Шаг 3. При выполнении условия останова работа алгоритма прекращается с x*  xn 1 ; иначе переходим к шагу 1 с n  n  1 . Метод Ньютона правильно определяет направление убывания функции, но продвижение в этом направлении корректируется с помощью деления xn )  f ( xn ) в отрезка пополам, если не выполняется условие релаксации f ( ~ шаге 2 (рисунок 10). Рисунок 10. Один шаг гибридного метода Ньютона–половинного деления На рисунке 11 приведена блок-схема рассмотренного гибридного алгоритма. 12 Рисунок 11. Блок-схема гибридного метода Ньютона–половинного деления Метод простой итерации5 Пусть дано уравнение f ( x)  0 и отрезок a; b , функция f(x) удовлетворяет условиям: 1) f(x) – дифференцируема на a; b ; 2) f (a )  f (b)  0 , т. е. f(x) имеет разные знаки на концах отрезка; 3) f ( x )  0 на a; b . Заменим f ( x)  0 равносильным ему уравнением x  (x ) . Выбирая произвольное значение x0  a; b, вычислим x1  ( x0 ) , x2  ( x1 ) , x3  ( x2 ) , … и т. д. xn 1  ( xn ) , n  0, 1, Слово «простой» означает, что для вычисления следующего приближения необходимо знать только одно предыдущее приближение. 5 13 Геометрически процесс итерации – нахождение абсциссы точки пересечения кривой y  (x) и прямой y  x (рисунок 12). На рисунке 13 приведен пример циклического итерационного процесса. Рисунок 12. Графическая иллюстрация метода простой итерации: а – односторонний сходящийся процесс; б – односторонний расходящийся процесс; в – двухсторонний сходящийся процесс; г – двухсторонний расходящийся процесс Процесс сходится к корню, если выполнены следующие условия теоремы о сходимости (достаточное условие сходимости). Теорема 4. Пусть функция (x ) определена и дифференцируема на a; b , причем все ее значения ( x)  a; b. Тогда, если существует правильная дробь q, такая что ( x)  q  1 при x  a; b , 14 то процесс итерации сходится независимо от начального приближения x0  a; b и предельное значение x *  lim xn является единственным корнем уравнения x  (x ) на a; b . n  Рисунок 13. Графическая иллюстрация метода простой итерации: циклический итерационный процесс а – цикл периода 2; б – цикл периода 4 На рисунке 14 представлена блок-схема решения нелинейного уравнения методом простой итерации [3]. Здесь c – начальное приближение; предполагается, что итерационный процесс сходится или, если в этом нет уверенности, необходимо ограничить число итераций, введя для них счетчик. Рисунок 14. Блок-схема метода простой итерации Рассмотрим один из способов равносильного приведения f ( x)  0 к виду x  (x ) . Построим функцию ( x)    f ( x)  x , 1     0 , если f ( x )  0 ; r 15 1 0    , если f ( x )  0 , r r  max f (a ) , f (b) . Тогда процесс итерации xn 1  ( xn ) , n  0, 1, сходится к корню x * при любом x0  a; b. Скорость сходимости оценивается как6 m n x *  xn  q , 1 q m  x0  ( x0 ) q    r  1 или q  max ( x ) , x  a; b. Примером условия окончания может быть xn  xn 1   или 1 q xn  xn 1  , q где  – требуемая точность. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1. Вержбицкий, В. М. Основы численных методов: Учебник для вузов / В. М. Вержбицкий. – М.: Высш. шк., 2002. – 840 с. 2. Мудров А. Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль. – Томск: МП «Раско», 1991. – 272 с. 3. Турчак Л. И. Основы численных методов: Учеб. пособие. – М.: Наука. Гл. ред. физ.-мат. лит., 1987. – 320 с. 4. Волков Е. А. Численные методы: Учеб. пособие для вузов. – М.: Наука., 1987. – 248 с. 5. Калиткин Н. Н. Численные методы. – М.: Наука, 1978. – 512 с. 6. Крылов В. И., Бобков В. В., Монастырный П. И. Вычислительные методы высшей математики. Т. 1. – Мн., «Вышэйш. школа», 1972. – 584 с. 7. Самарский А. А. Введение в численные методы. – М.: Наука. – 1997. – 286 с. 8. Бедарев И. А. Методы вычислений: учеб. пособие / И. А. Бедарев, Ю. В. Кратова, Н. Н. Федорова; Новосиб. гос. архитектур.-строит. ун-т (Сибстрин). – 2-е изд., перераб. и доп. – Новосибирск : НГАСУ (Сибстрин), 2009. – 116 с. 6 Метод простой итерации сходится со скоростью геометрической прогрессии. 16