lopt11 (Лекционный курс)
Описание файла
Файл "lopt11" внутри архива находится в папке "Лекционный курс". PDF-файл из архива "Лекционный курс", который расположен в категории "". Всё это находится в предмете "теория оптимизации и численные методы" из 4 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "теория оптимизации и численные методы" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Лекция 113. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙПОСТАНОВКА ЗАДАЧИПусть дано нелинейное уравнение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аx0бРис. 189a1b1x∗1a2b2x∗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=x− ck, k = 0,1,...
,f ′ 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 )≈,– в точке xиспользуется формула f ′ 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 ). Отрезок [a0 , b0 ] называется начальным интерваломнеопределенности, потому что известно, что корень ему принадлежит, но его местоположение с требуемой точностью не определено.95Процедура уточнения положения корня заключается в построении последовательности вложенных друг в друга отрезков, каждый из которых содержит корень уравнения.a + bk,Для этого находится середина текущего интервала неопределенности ck = k2k = 0,1,...
, и в качестве следующего интервала неопределенности из двух возможных выбирается тот, на концах которого функция f ( x ) имеет разные знаки (рис. 7).Процесс завершается, когда длина текущего интервала неопределенности становится меньше заданной величины ε , задающей точность нахождения корня. В качествеприближенного значения корня берется середина последнего интервала неопределенности.yy = f (x )a0c10x∗L3L1c0b0xL2L0Рис. 7Д. МЕТОД ХОРДЭтот метод при тех же предположениях обеспечивает более быстрое нахождениекорня, чем метод половинного деления. Для этого отрезок [a , b ] делится не пополам, а вотношении f (a) : f (b ) .Геометрически метод хорд эквивалентен замене кривой y = f ( x ) хордой, проходящей через точки (a, f (a )) и (b, f (b )) (рис. 8).x −ay − f (a )Уравнение хорды AB имеет вид=. Полагая x = x (1) и y = 0,b −af (b ) − f (a )f (a )(b − a ) .получаем x (1) = a −f (b ) − f (a )Предположим, что вторая производная f ′′(x ) сохраняет постоянный знак, и рассмотрим два случая: f (a ) > 0, f ′′(x ) > 0 (рис.