Итерационный метод решения систем нелинейных уравнений
Оценка 5

Итерационный метод решения систем нелинейных уравнений

Оценка 5
Научно-исследовательская работа +4
docx
информатика +1
Взрослым
17.02.2017
Итерационный метод решения систем нелинейных уравнений
При решении задач моделирования поведения химических систем достаточно часто приходится решать системы уравнений, нелинейных по отношению к переменным. Системыn линейных уравнений с n неизвестными x1, x2, ..., xn в общем случае принято записывать следующим образом: где F1, F2,…, Fn – любые функции независимых переменных, в том числе и нелинейные относительно неизвестных. Как и в случае систем линейных уравнений, решением системы является такой вектор (или векторы) (X*), который при подстановке обращает одновременно все уравнения системы в тождества. Система уравнений может не иметь решений, иметь единственное решение, конечное или бесконечное количество решений. Вопрос о количестве решений должен решаться для каждой конкретной задачи отдельно. Рассмотрим несколько простейших итерационных методов решения систем нелинейных уравнений, а именно, метод простой итерации, метод Зейделя и метод Ньютона.
итерационный метод решения систем нелинейных уравнений.docx
итерационный метод решения систем нелинейных уравнений Системы нелинейных уравнений При решении задач моделирования поведения химических систем достаточно часто  приходится решать системы уравнений, нелинейных по отношению к переменным.  Системыn линейных уравнений с n неизвестными x1, x2, ..., xn  в общем случае принято  записывать следующим образом: где F1, F2,…, Fn – любые функции независимых переменных, в том числе и нелинейные  относительно неизвестных. Как и в случае систем линейных уравнений, решением системы является такой вектор (или  векторы) (X*), который  при подстановке обращает одновременно все уравнения системы в  тождества. Система уравнений может не иметь решений, иметь единственное решение, конечное или  бесконечное количество решений. Вопрос о количестве решений должен решаться для  каждой конкретной задачи отдельно.  Рассмотрим несколько простейших итерационных методов решения систем нелинейных  уравнений, а именно, метод простой итерации, метод Зейделя и метод Ньютона. Метод простой итерации Для реализации этого метода решаемую систему уравнений необходимо путем  алгебраических преобразований привести к следующему виду, выразив из каждого  уравнения по одной переменной следующим образом: Выбирая затем вектор начального приближения ,   подставляют его в преобразованную систему уравнений. Из первого уравнения получают  новое приближение к первой переменной, из второго – второй и т. д. Полученное уточненное значение переменных снова подставляют в эти уравнения и т.д.Таким образом, на (i+1)­м  шаге итерационной процедуры имеем Метод Зейделя Модификация Зейделя алгоритма простой итерации заключается в использовании  уточненных значений переменных уже на текущем итерационном шаге. Так, для уточнения  значений первой переменной используются только значения предыдущего шага, для второй  переменной – значение x1 текущего шага, а остальных – от предыдущего и т.д.: Метод Ньютона­Рафсона Математической основой метода является линеаризация функций F1, F2, Fn (левых частей  уравнений, образующих систему) путем разложения в ряд Тейлора в окрестности точки начального приближения к решению и пренебрежением всеми членами ряда кроме линейных относительно приращений переменных. Рассмотрим метод на примере системы двух уравнений с двумя неизвестными: Линеаризуем функции F1, F2 путем разложения в ряд Тейлора вблизи некоторой точки  (начального приближения) и пренебрежения всеми членами ряда кроме линейных  относительно приращений переменных. Вспомним, что для функции одной переменной разложение в ряд Тейлора в окрестности  некоторой точки x0 имеет следующий вид: после пренебрежения всеми членами, кроме линейного: Для функции нескольких переменных разложение проводится аналогично. Выберем для поиска решения системы уравнений некоторое начальное приближение Запишем для функции F1 2­х переменных линейную часть разложения в ряд Тейлора в  окрестности выбранной точки для второго уравнения, аналогично Если значения переменных x1 и x2 являются решением, то оба уравнения системы должны  обратиться в ноль, поэтому полученные разложения приравниваем нулю. Для краткости записи введем следующие обозначения:  ­ приращение i­ой переменной   ­ значение первой частной производной функции Fj по переменной xi при значении  переменных   – значение  j­ой функции при соответствующих значениях переменных, то есть невязкаj­го  уравнения.  Получим систему линейных уравнений 2 x 2 относительно приращения переменных Или, в матричной форме, где матрица значений частных производных называется матрицей Якоби (илиякобианом).  Решение этой системы дает вектор поправок к начальному приближению. Сложение его с вектором начального приближения дает новые значения переменных. Итерационная процедура далее продолжается аналогично. Таким образом, процедура решения выглядит следующим образом: 1.     Выбирается начальное приближение, система приводится к нормальному виду, в  аналитическом виде находятся частные производные правых частей уравнений системы по  всем переменным. 2.     Рассчитывается матрица Якоби значений частных производных в точке начального  приближения 3.     Решается система линейных уравнений относительно приращений переменных. 4.     к вектору начального приближения прибавляется вектор приращений 5.     проверяется условие сходимости и, если оно не достигнуто, то процедура повторяется  с п. 2.   Метод легко обобщается на систему уравнений любой размерности.    Для функции F1  n  переменных линейная часть разложения в ряд Тейлора в окрестности  точки   записывается так  После разложения всех уравнений системы и используя введенные ранее обозначения, после  преобразования получим систему линейных уравнений порядка  n относительно приращения переменных Δxi Или, в матричной форме, В сокращенном виде можно записать так ­ (F')(Δx) = ­(F)  , где матрица значений частных  производных – (F') – называется матрицей Якоби или якобианом системы уравнений. Решение этой системы дает вектор поправок к начальному приближению. Сложение его с  вектором начального приближения дает новые, уточненные значения переменных.  Частные производные, необходимые для расчета матрицы Якоби, можно рассчитать  аналитически или же, если это невозможно или затруднительно, получать по формулам  приближенного дифференцирования, например, как отношение приращения функции к  приращению аргумента    , где эпсилон – достаточно малое число. Методы контроля сходимости итерационных методов решения систем Сходимость итерационного процесса решения системы нелинейных уравнений можно  контролировать несколькими способами, например: 1.  Норма (эвклидова или ­максимум) вектора невязок   2.  Эвклидова норма вектора относительных отклонений переменных 3.  Норма­максимум вектора относительных отклонений     Пример Применим метод Ньютона для решения системы уравнений Матрица частных производных (в аналитическом виде) Система линейных уравнений Может быть решена аналитически или методом Крамера или методом обращения матрицы.  Возьмем начальное приближение x = 0,15, y = 0,17 Первая итерация: Матрица Якоби ­ вектор значений функции Рассчитанный вектор поправок Новое приближение x = 0,15 ­ 0,0138 = 0,0136196,    y = 0,17 + 0,071604 = 0,241604 Вторая итерация: Рассчитанный вектор поправок Новое приближение x=0,168057,    y=0,268688 Третья итерация: Рассчитанный вектор поправок Новое приближение x=0,181878,    y=0,282509 На 25­й итерации эвклидова норма вектора невязок составляет  2.77∙10­7, эвклидова норма  вектора поправок составляет  1.96∙10­7 и решение сходится к  x = 0.2, y = 0.3 с абсолютной  погрешностью менее 1∙10­6 Метод простой итерации при этих же начальных условиях  сходится с такой точностью на 33­м шаге, модификация Зейделя – на 31­м шаге. На рисунке ниже представлен пример организации вычислений при решении рассмотренной  системы в программе MS Excel Пояснения: В ячейки В3 и В4 помещены начальные приближения к решению системы  (значения х0 и у0, соответственно). В диапазоне ячеек D3:E4  помещены формулы для  вычисления матрицы Якоби, при условии что х находится в ячейке В3, а у ­ в ячейке В4  (формулы приведены на рисунке ниже). В ячейках  G3:G4 рассчитывается значение вектора  невязок с отрицательным знаком. В ячейке Н3 вычисляется эвклидова норма вектора невязок. В  ячейках I3:I4 ­ решается  система линейных уравнений и вычисляется вектор поправок к решению. Для этого  обращается матрица коэффициентов системы (матрица Якоби) и умножается на вектор­ столбец свободных членов (отрицательный вектор невязок). Формула в этот диапазон ячеек  вводится как формула массива. Рядом ­ в ячейке J3 ­ рассчитывается норма вектора  поправок для контроля сходимости (см. формулы на рисунке ниже). Полученные в ячейках I3:I4 значения поправок на втором итерационном цикле  прибавляются к начальному приближению (в ячейках В6:В7) и далее вычисления  повторяются аналогично первому циклу. Набранные в строках 6 и 7 рабочего листа формулы могут копироваться до тех пор, пока не  будет достигнута необходимая точность. Задачи, сводящиеся к решению системы нелинейных уравнений Примером задачи, в которой используется решение систем нелинейных уравнений, может  служить аппроксимация таблично заданной функции математическими моделями,  нелинейными по отношению к параметрам. Подробно она описывалась ранее. Если аппроксимирующую функцию и определяющие ее параметры ai обозначить следующим образом то условие прохождения графика функции через все таблично заданные точки можно  записать в виде следующей системы: Другой пример ­ поиск экстремума (минимума или максимума) функции нескольких  переменных Условием экстремума является одновременное равенство нулю всех частных производных  функции. Таким образом, необходимо решить систему уравнений следующего вида,  которая, в общем случае, будет нелинейной Решение системы нелинейных уравнений Каждая операция содержит свои уравнения, которые отражают ее геометрический смысл.  Уравнений может быть одно или несколько, они могут быть скалярными или векторными.  Векторное уравнение является удобной записью нескольких скалярных уравнений для  соответствующих компонент векторов. В общем случае выполнение операции сводится к  решению некоторой системы скалярных нелинейных уравнений относительно параметров  кривых и поверхностей. Задача определения корней системы нелинейных уравнений  решается с помощью некоторого итерационного процесса, который шаг за шагом уточняет  корни уравнения. Итерационный процесс предполагает, что и на первой итерации известно  некоторое приближенное значение корней системы. Будем считать, что начальное  приближение решения нам известно и что оно находится в области сходимости. Метод Ньютона­Рафсона. Пусть требуется найти значения  алгебраическим       уравнениям:  неизвестных   удовлетворяющих     — непрерывно дифференцируемые в некоторой окрестности начального  где  приближения функции. Одним из наиболее часто используемых методов решения систем  нелинейных уравнений является метод Ньютона­Рафсона. Предположим, что после    итераций нам известно   приближение решения   которое отличается от точного  решения   на величины Погрешности   неизвестны и подлежат определению. Введем обозначения:   — для  совокупности неизвестных на   приближении,   — для функций на    приближении,   — для частных     производныхфункций на     приближении. Разложим  левую часть каждого уравнения системы (4.3.1) в ряд      Тейлора по степеням   в  окрестности   приближения Левую часть (4.3.2) заменим нулем, так как  , а в правой части отбросим величины  второго порядка малости и выше по  заменится системой     уравнений   . Тогда система (4.3.1)  являющейся линейной     системой относительно погрешностей    Решив систему линейных алгебраических приближение для искомого решения:       уравнений (4.3.3), вычислим следующее  Каждое приближение будет отличаться от точного решения, так как мы  (4.3.4)       уравнений. Погрешности  линеаризовали систему становиться все меньше и меньше. Мы не будем останавливаться на условиях и скорости  сходимости метода Ньютона­Рафсона. Скажем только, что если начальное приближение  выбрано достаточно хорошо и матрица системы     линейных уравнений (4.3.3) на каждой   на каждом приближении будут итерации хорошо обусловлена и имеет обратную сходится к единственному в данной окрестности решению       матрицу, то метод Ньютона­Рафсона  Метод Ньютона­Рафсона имеет квадратичную сходимость (4.3.5) где М определяется матрицей системы (4.3.3) и удовлетворяет неравенству Это сравнительно быстрая сходимость — после очередной итерации погрешность каждой  неизвестной уменьшается примерно на один или два порядка. Итерационный процесс  решения системы нелинейных уравнений (4.3.1) заканчивается, когда на очередной итерации погрешности всех неизвестных становятся меньше заданной величины е: Запишем систему линейных     уравнений (4.3.3) в матричном виде   где (4.3.6) F(x) — матрица     Якоби, которая одновременно является матрицей системы     линейных      уравнений (4.3.3),   — матрица­столбец значений функций (4.3.1),   — матрица­столбец неизвестных на  на запись  приближении. Запись системы (4.3.3) в матричной форме (4.3.6) похожа  метода       Ньютона для одного нелинейного уравнения. Рекуррентное соотношение для одного нелинейного алгебраического вид       уравнения   имеет  Рекуррентное соотношение (4.3.4) для системы вид       уравнений (4.3.3) в матричной форме имеет  Модифицированный метод Ньютона. В некоторых случаях для решения системы (4.3.1) применяется  модифицированный метод     Ньютона, который имеет вид   (4.3.7)     линейных  Модифицированный метод Ньютона отличается тем, что при решении системы уравнений матрица F не вычисляется на каждой итерации заново, а используется матрица,    . Модифицированный метод     Ньютона обладает  вычисленная на первой итерации  линейной сходимостью, поэтому для получения той же точности он требует больше  итераций, чем метод Ньютона. Но общие вычислительные затраты модифицированного  метода Ньютона за счет расчета по готовой матрице могут оказаться меньшими, чем у  метода Ньютона. Модифицированный метод Ньютона является представителем    стационарных методов решениянелинейных не зависит от номера итерации.       систем уравнений в силу того, что матрица    Если система (4.3.1) имеет большую размерность, то хорошие результаты дает комбинация  метода Ньютона и модифицированного метода Ньютона, когда после очередной итерации  метода Ньютона выполняется несколько итераций модифицированного метода Ньютона.     Ньютона (4.3.6) допускает еще одно видоизменение, которое называется методом  Метод   Ньютона с параметром и имеет вид (4.3.8)  — изменяющийся на каждой итерации параметр. Параметр как бы корректирует  где  правую часть системы (4.3.3), «улучшая» решение на итераций. Для использования метода  Ньютона с параметром нужно иметь способ вычислять или оценивать параметр  . Оценку параметра можно выполнять по приращениям неизвестных на итерационном шаге. Параметр  обычно имеет значения   Метод       Ньютона с параметром обладает линейной сходимостью. Метод простой итерации. Рассмотренные методы Ньютона являются представителями неявных методов    решения нелинейных К явным методам относится метод простой итерации, который получим из (4.3.8)      системуравнений в силу того, что матрица   не является единичной.  заменой   на единичную       матрицу Если в (4.3.9)   не зависит от итерации, то получим метод релаксации. Метод простой  итерации сходится, если  линейных алгебраических методов (в определенных случаях он не сходится). . Метод простой итерации не требует решения системы      уравнений, но сходится медленнее других рассмотренных    Метод Якоби. Рассмотренные до сих пор методы являлись линейными относительно новой  итерации  решать нелинейные уравнения. . Существуют и нелинейные методы, когда для вычисления хприходится  Одним из нелинейных методов является метод Якоби, в котором решаются  уравнений  нелинейных  (4.3.10) В каждом уравнении неизвестной считается только одна величина. Любое уравнение  может быть решено отдельно от других одним из описанных методов применительно к  одному уравнению.   Метод Зейделя. Другим нелинейным методом является метод уравнений       Зейделя, в котором решаются   нелинейных в r­м уравнении неизвестной считается величина   Уравнения (4.3.11) решаются  (4.3.11) последовательно, так что в r­м уравнении все  уравнений. Нелинейные методы сходятся гораздо медленнее метода методах не требуется строить матрицу системы (4.3.10) или (4.3.11) выполняется независимо от других уравнений системы. Решение  каждого уравнения в свою очередь выполняется итерационно. Эти итерации называются  внутренними, а итерации для всей системы нелинейных уравнений называются внешними.     уравнений. Решение каждого уравнения   известны из решения предыдущих      Ньютона. В нелинейных     • Большое распространение получили гибридные методы, когда внешние итерации  осуществляются одним методом, а внутренние итерации — другим. Например, внешние  итерации можно выполнять методом     Зейделя. При этом внутренние итерации  решение системы необязательно выполнять до тех пор, пока решение будет удовлетворять заданной точности,  а можно ограничиться некоторым заданным числом итераций.     Ньютона, а внутренние (итерационное      линейных уравнений) — методом       Метод градиента. В методе скорейшего спуска или методе градиента решение системы (4.3.1) сводится к  задаче отыскания минимумов функции  способами, например,  которую можно построить различными  или (4.3.12) (4.3.13)  — элементы некоторой положительно определенной матрицы  где  строка и матрица­столбец, элементами которых являются правые части уравнений системы   — матрица­ (4.3.1). Функцию (4.3.12) будем считать частным случаем функции (4.3.13). Если   есть  некоторое решение системы (4.3.1), то  . В других точках   в силу положительной определенности матрицы А. Таким образом, решение системы (4.3.1) сводится к поиску  нулевых минимумов функции  Будем рассматривать функцию   как некоторую скалярную функцию  ­ мерного векторного     пространства и будем обозначать ее еще и как     где искомые  величины считаются компонентами  пространстве являются компонентами вектора ­мерного вектора  .Производные   в этом  для функции (4.3.12): (4.3.14) В матричной записи на   итерации градиент (4.3.14) для функции (4.3.12) имеет вид (4.3.15) где   — транспонированная     матрица Якоби    , которая определена в (4.3.6). Вектор    как градиент скалярной функции, вычисленный при некоторых значениях   ортогонален  поверхности уровня, для которой  , и направлен в сторону возрастания     функции     в  данной точке  ­мерного пространства. Таким образом, итерационная зависимость для  определения экстремума     функции     имеет вид (4.3.16) Остается определить множитель  . Для этого подставим новое приближение (4.3.16) в  исследуемую функцию  и рассмотрим ее как функцию параметра  Параметр   должен иметь такой знак, чтобы от итерации к итерации функция    уменьшалась, а величина параметра   должна позволять при данном векторе   как можно ближе продвинуться к минимуму     функции    Параметр   приближенно можно  найти следующим образом. Считая параметр   малой величиной, разложим функцию        Тейлора по степеням  в ряд  степени. В результате получим  в окрестности нуля с точностью до слагаемых второй  где (4.3.17) Функция   дает изменение значения функции   вдоль нормали   к поверхности  уровня в точке  поэтому значение параметра получим из условия минимума     функции      как корень уравнения  Возьмем производную   по  , приравняем ее нулю и получим уравнение для  определения  Отсюда получим параметр где мы использовали равенство (4.3.15) и для краткости обозначили  принятых упрощений равенство (4.3.16) примет вид  Таким образом, для  В процессе решения следует следить за поведением параметра  от итерации к итерации и должен изменяться плавно. Существует много разновидностей  метода градиента на основе управления этим параметром. Для  . Он не должен возрастать  (4.3.18) дважды дифференцируемых     функций    , можно получить более точные формулы для  параметра  Если начальное приближение выбрано удачно и в окрестности искомого    нулевого минимума быстро даст искомое решение с заданной точностью. Если в окрестности искомого решения   нет других минимумов, то метод градиента довольно      функции   имеет другие минимумы, то итерационный процесс (4.3.16) сойдется, но не  функция  обязательно даст решение исходной системы       уравнений (4.3.1). Сжимающий оператор. Все рассмотренные методы решения системы нелинейных уравнений можно записать в виде (4.3.19) где   — квадратная     матрица размерности     — матрица­столбец,   — скалярный  параметр,   —  ­мерный вектор некоторого линейного     нормированного пространства,    компонентами которого являются искомые величины на   итерации решения. Для всех  методов в искомой точке   выполняется равенство   Если условно решить уравнение  (4.3.19) относительно   то получим (4.3.20) где   будем называть оператором, отображающим  ­мерное пространство само на  себя. Точка  является неподвижной точкой оператора, так как для нее выполняется  равенство  . Оператор называется сжимающим в некоторой области  ­ мерного линейного     нормированного пространства, если существует число     такое, что  для любых   принадлежащих этой области, выполняется неравенство Величина q называется коэффициентом сжатия. Существует доказательство того, что если  оператор  является сжимающим на всем конечномерном линейном     нормированном    пространстве, то он имеет единственную неподвижную точку   и итерационный процесс (4.3.20) сходится к этой неподвижной точке при любом начальном   Для погрешности  решения на   итерации справедлива оценка Операторы, соответствующие рассмотренным итерационным процессам, являются  сжимающими только в некоторых окрестностях решений, но если в процессе вычислений мы не выходим из окрестности, где оператор является сжимающим, то итерационный процесс  сойдется к единственному в этой окрестности решению. Методы решения систем нелинейных уравнений Постановка задачи Дана система   нелинейных уравнений с   неизвестными: где  непрерывные в некоторой области  , — нелинейные функции, определенные и  , или в векторном виде  (где  ) Требуется найти такой вектор  (3.22) превращает каждое уравнение в верное числовое равенство. , который при подстановке в систему Замечания 1. Проблема решения системы (3.22) возникает при решении многих прикладных задач,  например, поиска безусловного экстремума функций многих переменных с помощью  необходимых условий, при применении неявных методов интегрирования обыкновенных  дифференциальных уравнений и т.д. 2. Задача нахождения комплексных корней  решения двух уравнений с двумя неизвестными. Для этого следует положить  выделить действительную и мнимую части функции:  может быть сведена к проблеме   и  Отсюда получаем систему  рассматриваемых в данном разделе методов:  которая может быть решена одним из  3. Для всех рассматриваемых далее методов требуется находить начальное  приближение  точки пересечения кривых, описываемых уравнениями  . В случае   это можно сделать графически, определив координаты   и  . 4. Задача решения системы (3.22) может быть сведена к задаче поиска минимума  функции  . Так как функция  неотрицательная, ее минимальное значение, равное нулю, достигается в точке  поиска минимума функции  экстремума функций многих переменных (первого, второго, нулевого порядков). , являющейся решением системы (3.22). Для   можно применить различные методы поиска безусловного  Далее рассмотрим основные методы решения задачи (3.22). Метод простых итераций для решения нелинейных систем Для применения метода требуется привести систему (3.22) к равносильному виду: или в векторной форме (3.24) (3.25) где  непрерывны в окрестности изолированного решения  , функции   определены и  системы (3.24). Алгоритм метода простых итераций для систем 1. Задать начальное приближение  (точность). Положить  .  и малое положительное число    2. Вычислить   по формуле или (3.26) (3.27) 3. Если  то положить   и перейти к п.2. , процесс завершен и  . Если  ,  Замечания 1. Итерационный процесс, реализуемый согласно (3.27), соответствует параллельному  итерированию, так как для вычисления (k+1)­го приближения всех неизвестных  учитываются вычисленные ранее их k­е приближения. 2. Система (3.22) может быть преобразована к виду (3.24) различными способами, например, с помощью выражения переменных  условие сходимости. , таким образом, чтобы выполнялось  Другой способ заключается в замене системы  неособенная матрица. В качестве матрицы  например,  , если  , где  системой   можно использовать,  , где   —   — матрица Якоби. В случае, если  что при таком выборе  Ньютона. , следует выбрать другое начальное приближение. Заметим,   метод простых итераций совпадает с упрощенным методом  3. В качестве   можно использовать различные нормы векторов. Теорема 3.13 (о достаточном условии сходимости метода простых итераций). Пусть  функции  неравенство (где   — некоторая постоянная) , непрерывны в области  , причем выполнено   и  (3.28) Если последовательные приближения   не выходят из  области  вектор  , то процесс последовательных приближений сходится:   является в области   единственным решением системы (3.25).  и  Замечания 1. Вместо условия (3.28) можно также использовать (3.29) 2. Условия (3.28), (3.29) выполняются, если для любого  неравенства  соответственно, где  справедливы  Пример 3.17. Найти корни нелинейной системы уравнений  расположенные в первом квадранте, методом простых итераций с точностью    ▼  Решение Метод Зейделя для решения нелинейных систем уравнений Метод Зейделя предназначен для решения систем, записанных в форме (3.24). Этот метод  является модификацией метода простых итераций, где после задания начального  приближения  итерирование, причем на каждой итерации в каждое последующее уравнение подставляются значения неизвестных, полученных из предыдущих уравнений.  вместо параллельного итерирования производится последовательное  Алгоритм метода Зейделя для решения нелинейных систем 1. Задать начальное приближение  Положить  .  и малое положительное число (точность).  2. Вычислить   по формулам где прямоугольниками отмечены значения, которые берутся из предшествующих уравнений  на текущей итерации. 3. Если  Если  , то положить  , процесс завершить и положить   и перейти к п.2. . Пример 3.18. Найти корни системы расположенные в первом квадранте, методом Зейделя с  точностью  ▼  Решение Метод Ньютона для решения нелинейных систем уравнений Метод используется для решения систем вида (3.22) или (3.23). Формула для нахождения  решения является естественным обобщением формулы (3.14): (3.31) где  — матрица Якоби. Так как процесс вычисления обратной матрицы является трудоемким, преобразуем (3.31)  следующим образом: где   — поправка к текущему приближению  . Умножим последнее выражение слева на матрицу Якоби  В результате получена система линейных алгебраических уравнений относительно  поправки  приближение  . После ее определения вычисляется следующее  . Алгоритм метода Ньютона для решения нелинейных систем 1. Задать начальное приближение  Положить  .  и малое положительное число   (точность).  2. Решить систему линейных алгебраических уравнений относительно поправки  (3.32) 3. Вычислить следующее приближение:  . 4. Если  Если  , то положить  , процесс закончить и положить   и перейти к пункту 2. .  Достаточные условия сходимости метода Ньютона для систем  непрерывно дифференцируема в открытом выпуклом множестве  Теорем а 3.14 (о достаточных условиях сходимости метода Ньютона). Пусть  функция  Предположим, что существуют  и существует  существует  порождаемая соотношением (3.31), сходится к   и удовлетворяет неравенству  и  , такие, что   такое, что для всех   последовательность  , причем   и  . Тогда  . ,  ,  Здесь использованы следующие обозначения:  центром в точке  означает, что   непрерывна по Липшицу, где   — открытая окрестность радиуса   с  ; запись     — константа Липшица, то есть Замечания 1. Теорема 3.14 свидетельствует о локальной квадратичной сходимости метода Ньютона. 2. К недостаткам метода Ньютона следует отнести: – необходимость задавать достаточно хорошее начальное приближение; – отсутствие глобальной сходимости для многих задач; – необходимость вычисления матрицы Якоби на каждой итерации; – необходимость решения на каждой итерации системы линейных уравнений, которая может быть плохо обусловленной. Достоинством метода является квадратичная сходимость из хорошего начального  приближения при условии невырожденности матрицы Якоби. ▼  Примеры 3.19­3.21 Упрощенный метод Ньютона для нелинейных систем В этом методе в отличие от метода Ньютона (3.31) обратная матрица ищется только один  раз в начальной точке  (3.33) Заметим, что при решении одного уравнения  производная функции вычисляется также один раз в начальной точке.  упрощенным методом Ньютона  Методика решения задачи аналогична изложенной в предыдущем разделе, где вместо (3.32)  используется система матрица которой   не изменяется от итерации к итерации. Очевидно, сходимость упрощенного метода Ньютона в общем случае хуже по сравнению со  сходимостью процесса (3.31). Пример 3.22. Найти положительное решение системы  упрощенным методом Ньютона с  точностью  ▼  Решение Метод секущих для решения нелинейных систем уравнений Идея метода секущих (метода Бройдена) заключается в аппроксимации матрицы Якоби с  использованием уже вычисленных значений функций, образующих систему (сравните с  методом секущих для уравнения  , изложенным ранее).  и  Алгоритм метода секущих для нелинейных систем[/indent] 1. Задать начальное приближение  2. Положить  3. Решить систему линейных алгебраических уравнений  поправки к текущему приближению. 4. Вычислить  5. Если  , процесс завершить и положить  , где  .  и малое положительное число е.  — матрица Якоби.  относительно   — , вычислить . Если  положить   и перейти к п.3. Замечания 1. Можно доказать, что если  не вырождена, и если  итераций   сходится к   достаточно близка к   сверхлинейно.  достаточно близко к корню  , где матрица Якоби    , то последовательность  2. Когда метод секущих сходится к  аппроксимаций якобиана  так.  сверхлинейно, нельзя предполагать, что последняя из  , хотя часто это именно   будет приблизительно равняться

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений

Итерационный метод решения систем нелинейных уравнений
Материалы на данной страницы взяты из открытых истончиков либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
17.02.2017