УМК (1013374), страница 16
Текст из файла (страница 16)
,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 (рис.
9,а) и f (a ) < 0, f ′′(x ) > 0 (рис. 9,б). Случай f ′′(x ) < 0 сводится к рассматриваемому, если уравнение записать в форме:− f (x ) = 0.96Первому случаю (см. рис. 9,а) соответствует формулаx ( 0 ) = b,x(k +1)=x(k )−( ) (xf (x ) − f (a )f x (k )(k )(k ))−a ,(I)k = 0,1,...,а второму случаю (см. рис. 9,б) :x (0) = a,( ) ⋅ (b − x ),f (b ) − f (x )f x (k )x (k +1) = x (k ) −(k )(k )(II)k = 0,1,...В первом случае остается неподвижным конец a , а во втором случае - конец b .yBaf (b )y = f (x )x (1)0x∗bxAf (a)Рис. 8yx(2)0af (b )yf (a)x(1) x(0)xx∗by = f (x )f (b )аx(0) x(1)0 af (a)x(2)x∗bxy = f (x )бРис.
9З а м е ч а н и е. Для выявления неподвижного конца используется условиеf ′′( x ) ⋅ f (t ) > 0 , где t = a или t = b . Если неподвижен конец а, применяется формула (I),а если конец b , – формула (II).97Лекция 124. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХУРАВНЕНИЙПОСТАНОВКА ЗАДАЧИДана система n нелинейных уравнений с n неизвестными:f1 ( x1 ,..., x n ) = 0,f 2 ( x1 ,..., x n ) = 0,#f n ( x1 ,..., x n ) = 0,(4.1)где f i ( x1 ,..., x n ) : R n → R , i = 1,..., n , – нелинейные функции, определенные и непрерывные в некоторой области G ⊂ R n , или в векторном видеF ( x ) = 0,где x = ( x1 ,..., x n )T , F ( x ) = [ f1 ( x ),..., f n ( x )]T .Требуется найти такой вектор x ∗ = ( x ∗1 ,..., x ∗ n )T , который при подстановке в систему превращает каждое уравнение в верное числовое равенство.З а м е ч а н и я.1. Для всех рассматриваемых далее методов требуется находить начальное приближение x (0) .
В случае n = 2 это можно сделать графически, определив координатыточки пересечения кривых, описываемых уравнениями f1 ( x1 , x 2 ) = 0 и f 2 ( x1 , x 2 ) = 0 .2. Задача решения системы может быть сведена к задаче поиска минимума функции Ψ( x ) =n∑ f i 2 ( x1,..., x n ).Так как функция Ψ(x ) неотрицательная, ее минимальноеi =1значение, равное нулю, достигается в точке x ∗ , являющейся решением системы. Для поиска минимума функции Ψ(x ) можно применить различные методы поиска безусловного экстремума функций многих переменных (первого, второго, нулевого порядков).А. МЕТОД ПРОСТЫХ ИТЕРАЦИЙДля применения метода требуется привести систему (4.1) к равносильному виду:x1 = ϕ1 ( x1 ,..., x n ),x 2 = ϕ 2 ( x1 ,..., x n ),#x n = ϕ n ( x1 ,..., x n ),или в векторной формеx = Φ(x ) ,98(4.2)где x = ( x1 ,..., x n )T , Φ( x ) = [ϕ1 ( x ),..., ϕ n ( x )]T , функции ϕi (x ) определены и непрерывны в окрестности изолированного решения x ∗ системы.Методика решения задачиШаг 1.
Задать начальное приближение x (0) = (x10 , x 20 ,..., x n0 )T и малое положительное число ε (точность). Положить k = 0 .Шаг 2. Вычислить x (k +1) по формулеx (k +1) = Φ( x (k ) ) ,илиx1(k +1) = ϕ1 ( x1(k ) , x 2(k ) ,..., x n(k ) ),x 2(k +1) = ϕ 2 ( x1(k ) , x 2(k ) ,..., x n(k ) ),#x n(k +1) = ϕ n ( x1(k ) , x 2(k ) ,..., x n(k ) ).Шаг 3. Если Δ(k +1) = max x i(k +1) − x i(k ) ≤ ε , процесс завершен и x ∗ ≅ x (k +1) .i(k +1)Если Δ> ε , то положить k = k + 1 и перейти к п.2.З а м е ч а н и я. Итерационный процесс соответствует параллельному итерированию, так как для вычисления (k + 1) -го приближения всех неизвестных учитываются вычисленные ранее их k -е приближения.Теорема (о достаточном условии сходимости метода простых итераций).Пусть функции ϕi ( x ) и ϕ′i ( x ) , i = 1,..., n, непрерывны в области G , причем выполнено неравенствоn∂ ϕi ( x )max max ∑≤ q < 1,x ∈Gi∂xjj =1где q – некоторая постоянная.Если последовательные приближения x (k +1) = Φ( x (k ) ), k = 0,1,...
, не выходят изобласти G , то процесс последовательных приближений сходится: x ∗ = lim x (k ) и векk →∞тор x ∗ является в области G единственным решением системы.Б. МЕТОД ЗЕЙДЕЛЯМетод Зейделя предназначен для решения систем, записанных в форме (4.2). Этотметод является модификацией метода простых итераций, где после задания начальногоприближения x (0) вместо параллельного итерирования производится последовательноеитерирование, причем на каждой итерации в каждое последующее уравнение подставляются значения неизвестных, полученных из предыдущих уравнений.99Методика решения задачиШаг 1. Задать начальное приближение x (0) и малое положительное число ε (точность). Положить k = 0 .Шаг 2. Вычислить x (k +1) по формуламx1(k +1) = ϕ1 ( x1(k ) , x 2(k ) ,..., x n(k ) ),x 2(k +1) = ϕ 2 ( x1(k +1) , x 2(k ) ,..., x n(k ) ),#x n(k +1) = ϕ n ( x1(k +1) , x 2(k +1) ,..., x n(k−+11) , x n(k ) ),где прямоугольниками отмечены значения, которые берутся из предшествующих уравнений на текущей итерации.Шаг 3.
Если Δ(k +1) = max x i(k +1) − x i(k ) ≤ ε , процесс завершить и положитьix∗ ≅ x(k +1)(k + 1). Если Δ> ε , то положить k = k + 1 и перейти к п.2.В. МЕТОД НЬЮТОНАМетод используется для решения систем вида (4.1).Формула для нахождения решения является естественным обобщением формулыметода Ньютона для решения одного уравнения:x (k +1) = x (k ) − W−1( x (k ) ) ⋅ F ( x (k ) ),k = 0,1,...
,где∂ f1 ( x ) ⎞⎛ ∂ f1 ( x )"⎜⎟∂ xn ⎟⎜ ∂ x1⎟ – матрица Якоби.##W (x ) = ⎜⎜ ∂ f (x )∂ f n (x ) ⎟⎜ n⎟"⎜ ∂x∂ x n ⎟⎠1⎝Так как процесс вычисления обратной матрицы является трудоемким, преобразуемформулу следующим образом:Δx (k ) = − W−1( x (k ) ) ⋅ F ( x (k ) ),k = 0,1,...,где Δx (k ) = x (k +1) − x (k ) – поправка к текущему приближению x (k ) .Умножим последнее выражение слева на матрицу Якоби W ( x (k ) ) :W ( x (k ) ) Δx (k ) = − W ( x (k ) )W−1( x (k ) )F ( x (k ) ) = −F ( x (k ) ),k = 0,1,...В результате получена система линейных алгебраических уравнений относительнопоправки Δx (k ) . После ее определения вычисляется следующее приближениеx (k +1) = x (k ) + Δx (k ) .100Методика решения задачиШаг 1.
Задать начальное приближение x (0) и малое положительное число ε (точность). Положить k = 0 .Шаг 2. Решить систему линейных алгебраических уравнений относительно поправки Δx (k ) : W ( x (k ) ) ⋅ Δx (k ) = −F ( x (k ) ) .Шаг 3. Вычислить следующее приближение:x (k +1) = x (k ) + Δx (k ) .Шаг 4. Если Δ(k +1) = max x i(k +1) − x i(k ) ≤ ε , процесс закончить и положитьix∗ ≅ x(k +1)(k + 1). Если Δ> ε , то положить k = k + 1 и перейти к п.2.Г. МОДИФИКАЦИИ МЕТОДА НЬЮТОНАГ1.
Упрощенный метод Ньютона. В этом методе в отличие от метода Ньютонаобратная матрица ищется только один раз в начальной точке x (0) :x (k +1) = x (k ) − W−1( x (0) ) ⋅ F ( x (k ) ),k = 0,1,...Заметим, что при решении одного уравнения f ( x ) = 0 упрощенным методом Ньютона производная функции вычисляется также один раз в начальной точке.Методика решения задачи аналогична применению метода Ньютона, где используется система W ( x (0) ) ⋅ Δx (k ) = −F ( x (k ) ), k = 0,1,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
