9 Численные методы решения нелинейных уравнений (Лекции по теории оптимизации и численным методам)

Лекция 93. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙПОСТАНОВКА ЗАДАЧИПусть дано нелинейное уравнениеf (x )  0 ,(3.1)где f (x ) – функция, определенная и непрерывная на некотором промежутке. В некоторых случаях на функцию f (x ) могут быть наложены дополнительные ограничения, например, непрерывность первой и второй производных, что специально оговаривается.Функция f (x ) может быть задана в виде алгебраического многочлена или трансцендентной функции (тогда ей соответствует алгебраическое или трансцендентное уравнение).Требуется найти корни уравнения, т.е.

числа x 1 , x  2 ,  , которые путем подстановки превращают уравнение в верное числовое равенство. Числа x 1 , x  2 ,  называютсятакже нулями функции f (x ) .На практике часто бывает выгодно уравнение (3.1) заменить равносильным емууравнением (уравнения равносильны, если имеют одинаковые корни):f1 ( x )  f 2 ( x )  0 ,(3.2)где функции f1 ( x ) , f 2 ( x ) – более простые, чем функция f (x ) .

Тогда при задании уравнения в виде (3.1) нулями функции f (x ) являются точки пересечения f (x ) с осью Ox(рис.1,а), а при задании в виде (3.2) – абсциссы точек пересечения функций f1 ( x ) иf 2 ( x ) ( рис. 1,б).yyy  f1 ( x )y  f (x )y  f2 (x )0x 1x2x 3x4x 5аx0a1b1a2x1бРис. 189b2x2 xЧисло x  есть корень уравнения (3.1) кратности k , если при x  x  вместе сфункцией f ( x ) обращаются в нуль ее производные до (k  1) -го порядка включительно,т.е. f ( x  )  f ( x  )    f (k 1) ( x  )  0 , а f (k ) ( x  )  0 .

Корень кратности k  1 называется простым. На рис. 1,а простыми корнями являются x 1 ,x  2 ,x 3 , а корни x  4 ,x 5 –кратные.З а м е ч а н и я.1. Если f ( x )  an x n  an 1 x n 1    a0  Pn ( x ) – алгебраический многочлен, тоуравнение (3.1) называется также алгебраическим n -й степени:Pn ( x )  an x n  an 1 x n 1    a0  0 ,(3.3)где an ,  a0 – действительные числа, коэффициенты уравнения.2. Алгебраическое уравнение n -й степени имеет ровно n корней, действительныхили комплексных, при условии, что каждый корень считается столько раз, какова егократность.3. Если функция f ( x ) , определяющая уравнение f ( x )  0 , на концах отрезкаai , bi  принимает значения разных знаков, т.е. f (ai )  f (bi )  0 , то на этом отрезке содержится по крайней мере один корень уравнения.

Если же f ( x ) непрерывна и дифференцируема и ее первая производная сохраняет знак внутри отрезка ai , bi  sign f ( x )  const  , то на ai , bi  находится только один корень x i уравнения. a ,b  i iЭтапы решения нелинейных уравненийПервый этап. Находятся отрезки ai , bi  , внутри каждого из которых содержитсяодин простой или кратный корень ( x i  ai , bi  ) (см.

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

рис. 1,а);3) формированием простых функций f1 ( x ) и f 2 ( x ) таких, что получается равносильное уравнение в виде (3.2), и дальнейшим построением графиков этих функций (см.рис. 1,б).90А. МЕТОД ПРОСТЫХ ИТЕРАЦИЙПусть известно, что кореньG  a  x  b.уравненияxf (x )  0лежит на отрезкеМетодика решения задачиШаг 1. Уравнение f ( x )  0 равносильным преобразованием привести к видуx  ( x ) . Это преобразование может быть осуществлено различными путями, но длясходимости нужно обеспечить выполнение условия ( x )    1 (  – некоторая константа). При этом задача сводится к нахождению абсциссы точки пересечения прямойy  x и кривой y  ( x ) (рис.

2).yyxy  ( x )0xxРис. 2Шаг 2. Задать начальное приближение x ( 0 )  [a, b ] и малое положительное число . Положить k  0 .Шаг 3. Вычислить следующее приближение:x ( k 1)  ( x ( k ) ) .Шаг 4. Еслиx ( k 1)  x ( k )   , итерации завершаются и x   x (k 1) .

Еслиx ( k 1)  x ( k )   , положить k  k  1 и перейти к п.3.Теорема (о достаточном условии сходимости метода простых итераций).Пусть выполнены условия:1. Функция ( x ) имеет производные для всех x  G .2. Существует число  (0    1,   const) , такое, что (x )   для всехx G .Тогда последовательность x (0 ) , x (1) , , x (k 1) ,  , определяемая на основе итера-ционного процесса, сходится к решению x  , т.е. x (k )  x  при k   .91Геометрическая интерпретация процесса сходимости и расходимости в зависимости от выполнения или невыполнения достаточного условия сходимости представлена нарис. 3. Из рис. 3 видно, что при 0  (x )  1 и при  1  (x )  0 (см. рис.

3, а, б) итерационные последовательности x (0 ) , x (1) , x ( 2) ,  сходятся к x  . Причем в первом случаереализуется односторонняя (монотонная) сходимость, а во втором – двусторонняя (немонотонная). При ( x )  1 (см. рис. 3, в, г) процесс расходится, несмотря на то, что точкаx ( 0 ) очень близка к x  .y0  ( x )  1yyxyx( x (0) )y  ( x )( x (1) ) 1  ( x )  0( x (1) )(x(0) )y  ( x )xx (1)0 x (0 )x ( 2)x0 x (0 )xаyx ( 2)xx (1)бy( x )  1( x )  1y  ( x )y  ( x )yxyxx ( 2)x0x (0) x (1) x (2)0xвx (1) x (0)гРис. 392xСпособы преобразования уравненияПреобразование уравнения f (x )  0 к равносильному виду x  (x ) может бытьвыполнено неоднозначно.1.

Можно заменить уравнение f (x )  0 на равносильное x  x  c f (x ) , гдеc  const  0 . Тогда, принимая правую часть этого уравнения за ( x ) и раскрывая( x )  1  c f ( x )  1 , получаем условие 2  c f (x )  0 .При этом надо стремиться получить такую постоянную c , которая бы больше отличаласьот нуля, и тогда будет реализовываться более быстрая сходимость.2. Уравнение f ( x )  0 заменяется равносильным:xxf (x ) ( x ) при x  G ,max f ( x )где знак в правой части выбирается из условия ( x )  1 .3.

Можно выразить x из уравнения f ( x )  0 так, чтобы для полученного уравнения x  ( x ) выполнялось условие сходимости ( x )  1 в окрестности искомого корня.Б. МЕТОД НЬЮТОНАМетод Ньютона (метод касательных) является одним из наиболее популярныхчисленных методов. Он реализуется по формуле:x ( k 1)  x (k ) f ( x (k ) ), k  0,1, 2,...f ( x ( k ) )yBf ( x (0 ) )y  f (x )a0CxAx ( 2)Рис.

493x (1)bx (0 )xВ точке x (0) строится касательная к графику функции. Следующей точкой x (1) являетсяточка пересечения касательной с осью абсцисс. Далее процесс продолжается аналогично.Теорема (о достаточных условиях сходимости метода Ньютона).Пусть выполняются следующие условия:1. Функция f ( x ) определена и дважды дифференцируема на a, b  .2. Отрезку a, b  принадлежит только один простой корень x  , так чтоf (a )  f (b )  0 .3.

Производные f ( x ), f ( x ) на a, b  сохраняют знак, и f ( x )  0 .4. Начальное приближение x (0 ) удовлетворяет неравенствуf ( x (0) )  f ( x (0) )  0 (знаки функций f ( x ) и f (x ) в точке x ( 0 ) совпадают).Тогда с помощью метода Ньютона можно вычислить корень уравнения f ( x )  0с любой точностью.В. МОДИФИКАЦИИ МЕТОДА НЬЮТОНАВ1.

Упрощенный метод Ньютона. Вместо формулы метода Ньютона используетсяx(k 1)x(k ) ,f x f x (k )(0 )k  0,1,...Отличие от метода Ньютона заключается в том, что производная функции f (x ) подсчитывается только в точке начального приближения, а на последующих итерациях не уточняется. Процесс последовательных приближений отражен на рис. 5. Первая итерациясовпадает с первой итерацией метода Ньютона. На последующих итерациях соответствующие отрезки параллельны касательной, проведенной в начальной точке.yy  f (x )0(1)x ( 2) xxРис. 594x (0 )xВ2.

Метод Ньютона–Бройдена. Этот метод позволяет увеличить скорость сходимости последовательных приближений благодаря использованию формулыf x (k )(k 1)(k )x ck, k  0,1,... ,xf  x (k )где ck – число, которое выбирается на каждой итерации так, чтобы уменьшить значение  f x (k 1) по сравнению с f x (k ) . При ck  1 метод Ньютона–Бройдена совпадаетс методом Ньютона.Как правило, при плохой сходимости или ее отсутствии полагают 0  ck  1 , а прихорошей сходимости для ck  1 полагают ck  1 (это ускоряет сходимость).В3. Метод секущих. В этом методе производная функции f (x ) подсчитываетсяс помощью конечно-разностных соотношений:f x (0 )  f x ( 0 )  (0 )(0 ),используется формула f  x– в точке xгде  – малая положительная величина;f x (k )  f x (k 1).– в точках x (k ) , k  1,2,...

, используется формула f  x (k ) x (k )  x k  1Вычисленное значение f ( x (k ) ) определяет тангенс угла наклона секущей (рис. 6).        yx0y  f (x )x (0 )x ( 2)x (1)xРис. 6Используется формулаx (k 1)  x (k )  f x   f xf x (k )(k )(k 1) x (k )  x (k 1) ,k  1,2,...Г. МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯПусть дано уравнение f ( x )  0 и отделен простой корень x  , т.е. найден такой отрезок a0 , b0  , что x   a0 , b0  , и на концах отрезка функция имеет значения, противоположные по знаку ( f (a0 )  f (b0 )  0 ).