Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 31

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 31)

Рассмотрите уравнение х' — 2 х+ 2 = О. Как ведут себя итерации Ньютона прн различных вещественных начальных приблнженияхт 4.2ЛО. Покажите, что итерации Ньютона сходятся к единственному решению уравнения е эх+ 3 х+ 2 = 0 при любом начальном значении х,. 4.3. Решение систем нелинейных уравнений В разделе 4.1 мы упомянули, что применение метода стрельбы к системе обыкновенных дифференциальных уравнений может привести к необходимости решения системы нелинейных алгебраических уравнений относительно недостающих начальных условий. В разделе 4.4 мы увидим, что применение метода конечных разностей к нелинейным краевым задачам также приводит к нелинейным системам уравнений.

Поэтому в настоящем разделе рассмотрим общую проблему численного решения систем нелинейных уравнений и, в частности, то, как описанные в предыдущем разделе методы переносятся на эту более общую ситуацию. Проблема, которую мы рассматриваем, заключается в нахождении приближенного решения системы уравнений Л(х~, хг,...,х )=О, 1= 1, ..., и, (4.3.1) где Х~, 1.з "-, 1п — заданные функции и переменных х,, ...,х„.Дляудобства записи воспользуемся векторными обозначениями и перепишем (4.3.1) в виде Г(х) = О, (4.3.2) где, как обычно, х — вектор с координатами х,, ...,х„, а à — вектор функ- ЦИЯ С КООРДИНатаМИ Х~, ...„1и.

ЧРИ И = 1 МЫ В КаЧЕСтВЕ ЧаСтНОГО СЛУЧаЯ (4.3.1) получаем рассмотренную в предыдущем разделе задачу отыскания Рис. 4.15. Возможные ситуации прн и = 2: а) нет решений; б) единственное решейне; в) несколько решений корней одного уравнения.

Другим частным случаем, в котором Г(х) = Ах — Ь„ где А — заданная матрица и Ь вЂ” заданный вектор, является рассмотренная в гл. 3 задача решения системы линейных уравнений. 126 В общем случае весьма сложно выяснить, имеет ли уравнение (4.3.2) решение, и если имеет, то сколько. В сравнительно простом случае п = 2 возможные варианты можно, по крайней мере в принципе, представить себе геометрически. Если, например, изобразить на плоскости (х,, ха) множество точек, для которых 11 (х~, хт) = О, и множество точек, для которых ~, (х„х,) = О, то пересечение этих множеств и будет множеством решений системы (4.3.2). (Здесь и далее мы ограничиваемся рассмотрением только вещественных решений.) На рис.

4.15 представлены несколько возможных ситуаций. В дальнейшем будем предполагать, что (4;3.2) имеет решение х', которое нас и интересует, хотя не исключено, что система имеет и другие решения. Во многих ситуациях — и именно так будет в разделе 4.4 — система (4.3.2) имеет вид Г(х) — = Ах — Н(х) = О, (4.3.3) где А — заданная невырожденная матрица, а Н вЂ” заданный вектор, координаты которого являются нелинейными функциями, В этом случае естественна (хотя и не обязательно удачна) следующая итерационная процедура: х~+ = А 'Н(х'), ю' = 0,1, ..., (4.3.4) где верхний индекс указывает номер итерации.

Здесь, как и далее, (4.3.4) означает, что на каждом шаге для получения следующего приближения необходимо решить систему линейных уравнений Ах~+ = Н(х~). Итерации (4.3.4) обычно называют итерациями Пикапа. Этот метод можно рассматривать как специальный случай переноса метода хорд из преды1~- щего раздела на систему л уравнений, который в общем случае имел бы вид х~+ =х' — ВГ(х ), 1=0,1, ..., (4.3.5) 1=0,1,..., х'+1 = С(х~) (4.3.6) где С вЂ” заданная итерируемая функция. Для (4.3.5), например, С(х) = — х — ВГ(х). (4.3.7) Будем предполагать, что решение х' уравнения Г (х) = 0 удовлетворяет равенству х' = С (х') и, наоборот, если х' = С(х'), то Г(х') = О. Ясно, что если матрица В невырождена, то для функции (4.3.7) эти условия выполняются.

В предыдущем разделе теория сходимостн основывалась на выполнении в окрестности решения неравенства! я'(х) ! (1. Соответствующий результат 127 где  — заданная невырожденная матрица. Легко видеть (см. упражнение 4.3.2), что если функция Г задана в форме (4,33) и В = А ', то (4.35) сводится к (4.3.4) . При каких условиях итерации (4.3.5) или (4.3.4) сходятся? Ситуация здесь совершенно аналогична скалярному случаю, но анализ осложняется необходимостью работать с векторфункциями. Давайте рассмотрим один шаг общего итерационного процесса для системы уравнений формулируется следующим образом.

Если !!С (х) !! < 7 < 1, !! — х' !! < !5, (4.3.8) то итерации (4.3.6) сходятся, когда ]! х — х' !! К !1 (или если !! х" — х' !! КД прн некотором /г). Здесь С (х) — матрица Якоби векторфункции С, вычисленная в точке х, а !! !! обозначает, как и в разделе 3.5, нормувектора или соответствующую матричную норму. Не будем доказывать эту теорему сходимости, а только отметим, что это легко сделать, если воспользоваться обобщением неравенства (4.2.16) на случай п переменных, Применяя признак (4.3.8) к итерациям (4.3.5), получаем достаточное условие сходимости !!! — ВГ (х) !! ~ 7 < 1, !!х — х !! ~ р, (4.3.9) которое для итераций (4.3.4) принимает вид !!А 'Н'(х) !! < 7 < 1, !!х — х' !! < Ф.

(4.3.10) Из условия (4.3.10) следует, что итерации (4.3.4) будут сходиться, если матрица А"' Н '(х) "мала", когда точка х близка к х'. Аналогично, итерации (4.3.5) будут сходиться, если матрица ВГ'(х) близка к единичной или, что то же, В ' близка к Г ' (х) .

Так как решение х' заранее неизвестно, эти признаки следует, скорее, рассматривать как дающие некоторое представление о факторах, управляющих сходимостью, а не как практическое средство установления сходимости. Как и в предыдущем разделе, скорость сходимости будет зависеть от величины !!С (х) !!.

Поэтому мы хотели бы сделать этувеличинувозможно меньшей, по крайней мере вблизи решения х'. Если бы для итераций (4.3,5) мы положили В = [Г'(х*) ~ ', то тогда С '(х') = О, и скорость сходимости вблизи решения была бы высокой. Конечно, мы не в состоянии осуществить такой выбор, так как значение х' неизвестно, но мы можем достичь того же эффекта с помощью следующего итерационного процесса: х'+~ =х' — [Г'(хч)[ 'Г(х'), (4.3.11) 1=0,1, Здесь мы, конечно, предполагаем, что матрицы Якоби Г (х ) являются У невырожденными. Фактическая реализация метода (4.3.11) осуществляется с помощью следующих шагов. 1.

Решаем линейную систему Г (х')у = — Г(х'). (4.3.12) 2. Полагаем х~+' = х~ + у~. Ясно, что при и = 1 итерации (4.3.12) представляют собой метод Ньютона, описанный в предыдущем разделе. Из различных возможных распространений итераций Ньютона на случай л переменных метод (4.3.12) является наиболее последовательным, поскольку он обладает следующими свойствами, которые мы приводим без доказательства. 1. Если функция Г дважды непрерывно дифференцируема в окрестности х' и матрица Г (х) невырождена в окрестности х', то при условии, что хе достаточно близко к х', итерации (43.12) будут сходиться к х' (теорема о локальной схоцимости), причем скорость сходимости будет квадратичной: !!х' ' — х* !!(с !!х' — х' !!'.

(4.3 13) 2. Геометрически метод (4.3.!2) можно интерпретировать следующим образом. Каждая функция )"1 аппроксимируется линейной функцией 1,, которая, если рассматривать ее как гиперплоскость в (л+ 1) -мерном пространстве, является касательной к у, в точке х'. Пересечение и множеств (х: ( (х) = О ), >' = 1,..., и, и является следующим приближением х, Эта интерпретация в случае ~+1 и = 2 проиллюстрирована на рис.

4.1б. Пересечение с плоскостью(х„ха) касательной плоскости к поверх- насти г, в точке Г,(д') пересечение с плоскостью(х„ха) квсатегьной пласкастй к поверхности ~~ в точке $ (х") Поверхнас 1;(х) Рис. 4.1б. Метал Ньютона при и = 2 Как пример применения метода Ньютона (4.3.12) в случае двух уравнений приводим в табл. 4.2 первые четыре итерации для системы нелинейных уравнений та ч- та — 1 =О. х~ -х, =О, где в качестве начального приближения использовались значения х, = 0,5 и хв = 0,5.

Как и в одномерном случае, видно, что итерации сходятся примерно с квадратичной скоростью. Свойство квадратичной сходимости (4.3.13) (которое теряется, если матрица а. (х*) вырождена) очень желательно и придает методу Ньютона при решении систем нелинейных уравнений особенную ценность, Однако имеются три обстоятельства, которые могут препятствовать его успешному применению.

Во-первых, это необходимость определения на каждом шаге матрицы Якоби, что требует вычисления и' частных производных о>';~дх;. Если и велико или функции ~; достаточно сложны, то получение аналитических выражений для производных и последующее программирование соответствующих формул можетоказаться исключительно нудной и утомительной работой. Иногда эту работу можно облегчить, используя технику символьного дифференцирования, о которой говорилось в первой главе. Другим широко используемым подходом является аппроксимация частных производных конечными разностями.

Характеристики

Список файлов книги