lopt12 (Лекционный курс)

Лекция 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,... , матрица которой W ( x (0) ) не изменяется от итерации к итерации.Очевидно, сходимость упрощенного метода Ньютона в общем случае хуже.Г2. Метод секущих. Идея метода секущих (метода Бройдена) заключается в аппроксимации матрицы Якоби с использованием уже вычисленных значений функций,образующих систему.Методика решения задачиШаг 1.

Задать начальное приближение x (0) и малое положительное число ε .Шаг 2. Положить k = 0 и A0 = W ( x (0) ) , где W ( x ) – матрица Якоби.Шаг 3. Решить систему линейных алгебраических уравнений Ak s k = −F ( x (k ) )относительно s k – поправки к текущему приближению.Шаг 4. Вычислить x (k +1) = x (k ) + s k .Шаг 5. Если s k ≤ ε , процесс завершить и положить x ∗ = x (k +1) . Если s k > ε ,вычислитьy k = F ( x (k +1) ) − F ( x (k ) ),Ak +1 = Ak +k = k + 1 и перейти к п.3.101( y k − Ak s k ) ⋅ s Tks Tk s k,положить.