10 Численные методы решения систем нелинейных уравнений (1013413)
Текст из файла
Лекция 104. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХУРАВНЕНИЙПОСТАНОВКА ЗАДАЧИДана система 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 Gixjj 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(k11) , 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 ) W1( 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 ) W1( 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 ) )W1( 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 ) W1( 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,положить.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.