А.А. Самарский, П.Н. Вабищевич, Е.А. Самарская - Задачи и упражнения по численным методам (2000) (1160081), страница 10
Текст из файла (страница 10)
, n , fe = 0,l,...Определим матрицу ЯкобиlF (x) =g/i(»)дх |дМх)дх2дх„df2(x)ах,df2(x)дхгОМ*)дхпдЩдх\д/п(х)дх2ДД(«)дх„и запишем (6.14) в видеF1 (х) (х*+| - хк) + F(xk) = О, it = 0,1,... .(6.15)84Глава 6. Нелинейные уравнения и системыПри использовании записи (6.11) метод Ньютона (6.15) соответствуетвыборуBk+i=F'(xk),т>+, = 1.Система линейных уравнений (6.15) для нахождения нового приближения ж*+| может решаться итерационно. В этом случае мы имеетдвухступенчатый итерационный процесс со внешними и внутреннимиитерациями. Например, внешний итерационный процесс может осуществляться по методу Ньютона, а внутренние итерации — на основеитерационного метода Зейделя.При решении систем нелинейных уравнений можно использоватьпрямые аналоги стандартных итерационных методов, которые применяются для решения систем линейных уравнений.
Нелинейный методЗейделя применительно к решению (6.2) даетfi{x],x2,...,xt,xi+u...,xn)= 0,г = 1,2,...,п.В этом случае каждая компонента нового приближения находится из решения нелинейного уравнения, что можно сделать на основе итерационных метода простой итерации и метода Ньютона в различных модификациях.
Тем самым снова приходим к двухступенчатому итерационномуметоду, в котором внешние итерации проводятся в соответствии с методом Зейделя, в внутренние — методом Ньютона.Основные вычислительные сложности применения метода Ньютонадля приближенного решения систем нелинейных уравнений связаныс необходимостью решения линейной системы уравнений с матрицейЯкоби на каждой итерации, причем от итерации к итерации эта матрицаменяется. В модифицированном методе НьютонаF'{x°)(xk+]-xk)+F(xk)=0,* = 0,1,...матрица Якоби обращается только один раз.6.3. УпражненияПриведены примеры построения и исследования итерационных методов для решения нелинейных уравнений.
Для простоты изложения мыограничились случаем одного уравнения.6.3. Упражнения85Упражнение 6.1. Рассмотрите условия сходимости метода релаксации*+i _*+ / ( * * ) = 0,lb = 0,1,...при решении уравнения (6.1), если f'(x) > О.Решение. Будем ориентироваться на использование оценки (6.7) для скорости сходимости метода последовательных приближений (6.5).
В нашемслучае(р(х) = х -rf(x).Оценим теперь величину q в (6.6). В нашем случае имеем\tp(x) - <р(у)\ = \х-у-т(/(ж) - f(y)) \^q\x-y\,где постояннаяg = max|l - rf'(x+ 6(x - у))\(6.16)с некоторым в 6 [0,1].Для конкретизации условий сходимости и оптимизации выбора итерационного параметра будем считать, чтоО < m ^ f'(x) < М.В этих предположениях из (6.16) следует, чтоq(r) = max{|l - г т | , | 1 - т М | } .Итерационный метод будет сходится (q < 1), если т < 2/М, а для оптимального значения итерационного параметра т = то, при котором минимально q, получимУпражнение 6.2.
В интерполяционных методах нахождение корней уравнения (6.1) основывается на замене функции интерполяционным многочленом.Метод секущих (6.10) связывается с интерполированием многочленом первойстепени. Постройте метод решения уравнения (6.1) на основе интерполяционного многочлена второго порядка (метод парабол).86Глава 6. Нелинейные уравнения и системыРешение. Пусть известны три приближения я* \ хк ' и хк.
Новоеприближение находится как решение уравненияL2(x) = Q,(6.17)где L2{x) — интерполяционный многочлен второго порядка, построенныйпо узлам хк~2, я* - 1 и хк.Интерполяционный многочлен Ньютона имеет вид£ 2 (*) = / ( * * ) + ( * - * * ) / ( * * , * * - * ) ++{x-xk){x-xk-i)f{xk,xk-\xk-'),где, / * *-i t-2\ _ /(ж/(а: ,* ,х ) =,ar) - /(ж ,ar_ хкхк_2)— разделенные разности первого и второго порядка соответственно.Уравнение (6.16) принимает вида(х - хк)2 + Ъ(х - хк) + с = 0,(6.18)гдеа = /(УУ-\**-2),Ь = / ( x V - ) + (хк - xk->)f(xk,xk-\xk-2),с = /(**).Решая квадратное уравнение (6.18) найдем два, в общем случае комплексных, корня.
В качестве нового приближения i* + l в методе параболберется корень уравнения (6.18), который ближе к я*.Упражнение 6.3. Обсудите возможность ускорения итерационного метода,имеющего линейную скорость сходимости.Решение. Для итерационного метода в силу наших предположений о линейной сходимости имеемхк - х* ъ aqk,9 G (О, I).6.3.Упражнения87Числа a,q,x* — неизвестны и для их нахождения рассмотрим три последовательных итерации хк~2, хк~\ хк и составим приближенные равенствахк~2- х* « aqk~2,xk~l - х* ы aqk~l,xk-x*maqk.Отсюда находимХк(а*-**'1)2хк — 2хк ' — х* -2и поэтому в качестве нового приближения можно взятьх* + | = х-(х*-х*-')2х* — 2х*~' — х * - 2Это есть метод Эйткена ускорения сходимости итерационных методоврешения нелинейных уравнений.Упражнение 6.4.
Покажите, что в методе Ньютона (6.9) последовательность приближений либо монотонно убывает (х* < х* +| < х* для всех к),либо монотонно возрастает (х* > х* +| > х* для всех к), если производнаяфункции /(х) сохраняет знак и монотонна.Решение. Будем считать, для определенности, что/'(х)>0,/"(х)>0.Случай отрицательных первой и второй производных функции /(х)рассматривается аналогично.При задании начального приближения х° имеем, например, х° > х*(вторая возможность х° < х*). Доказательство проводится по индукции.Предположим, что х* > х* и докажем, что тогдах* > х* +| > х*.Запишем (6.9) в видеДля правой части имеемf(xk)-f(x*)_(xk-x*)f(e)Глава 6. Нелинейные уравнения и системы88где £ € (х*,х ). В наших предположениях о производных функции f(x)получим/'(а;'-)и поэтому из (6.19) следует неравенствоО < хк - хш <хк- х*,которое обеспечивает монотонность итераций метода Ньютона.6.4.
ЗадачиЗадача 6.1. Обсудите возможность отделения известного корня х* уравнения (6.1), применяя итерационный метод к уравнениюМ = Щ=0.Задача 6.2. Покажите, что итерационный метод Ньютона (6.9) можнорассматривать как интерполяционный метод при использовании интерполяционного многочлена Эрмита первой степени.Задача 6.3. Постройте методы нахождения корней уравнения (6.1) на основе линейной и квадратичной интерполяции функции х = <р(у), обратной у = f(x).Задача 6.4. Покажите, что если корень х* уравнения (6.1) имеет кратность р , то квадратичную сходимость имеет метод Ньютона в следующеймодификациихк+'f(x>)±-хк:L + / ( X *) = 0, * = o , i , .
. . .Задача 6.5. Покажите, что итерационный метод (метод Стеффенсена)i„*+1 _= „*х/(*')обладает квадратичной сходимостью./(*'),4 = 0,1,...(6.20)6.4. Задачи89Задача 6.6. Примените процесс Эйткена для ускорения сходимости итерационного методаxk+l = xk~f(xk), fc = 0,l,...и дайте интерпретацию полученного метода как метода Стеффенсена.Задача 6.7. Исследуйте скорость сходимости итерационного метода Чебышева.»..«,_/W/WH,/'(**)2(/'(«'))t = 0j,!Задача 6.8.
Сформулируйте достаточные условия сходимости нелинейного метода ЯкобиЛ(*?,х2,... ,хк+],*?+„... ,*„) = 0, « = 1,2,...,пдля приближенного решения системы уравнений (6.2).Задача 6.9. Постройте метод Стеффенсена (см. (6.20)) для решениясистем нелинейных уравнений.Задача 6.10. Пусть в системе уравнений (6.3) имеет место разложениеF(x) = F\(x) + F2(x). Рассмотрите итерационный метод (нелинейныйаналог классического итерационного метода переменных направлений)хк+1'2-хк+Ft(xk^2)+F2(xk)=0,•+Fl{xk+l'2)+F2{xk+l)=0,* = 0,l,...,ткоторый основан на последовательном решении двух нелинейных системуравнений.Глава 7Задачи минимизации функцийСреди основных проблем вычислительной математики можно отметить задачи минимизации функций многих переменных (задачиоптимизации). Поиск минимума часто проводится при некоторыхдополнительных ограничениях — условная оптимизация.
Для численного решения таких задач используются итерационные методы. В задачах с ограничениями применяются методы штрафныхфункций. Простейшей задачей рассматриваемого класса являетсяпоиск минимума одномерной функции.7.1. Поиск минимума функции многих переменныхДля заданной функции f(x), определенной на допустимом множестве Xиз евклидова пространства R", ищутся точки минимума (максимума)функции /(ж), т.е.f(x)->min, xeX.(7.1)Точка х* € X есть точка глобального минимума функции f(x) на множестве X, еслиf(x')^f(x),Vx€X,(7.2)и точка локального минимума, если /(а;*) < f(x) в окрестности точкиж* ex.Задача (7.1) называется задачей безусловной оптимизации, еслиX = Rn, т.е./(z)-+min, z € R " .(7.3)Если X некоторое подмножество пространства R", то мы имеем задачуусловной оптимизации.
Такие задачи существенно сложнее для численного решения, чем задачи безусловной минимизации. Ограничения могут7.2. Методы решения задач оптимизации91Основные обозначениях = {ж,} == {Ж1,Ж2 , . . . ,хп{ — и-мерный вектор/(*) — функция одной илип переменных-+min,x€R"—задача безусловной оптимизации/(*)—>min,х€Х—задача условной оптимизации/(*)X — допустимое множествохк — приближенное решение на к-ойитерации(s,2/) =— скалярное произведениеформулироваться в виде равенств (например, <7,(х) = 0, г = 1,2,...,тп)или неравенств (&(х) ^ 0, г = 1,2,..., т).7.2. Методы решения задач оптимизацииВычислительные алгоритмы для приближенного решения задачи оптимизации чаше всего строятся на использовании необходимых и достаточныхусловий оптимальности, т.е.
условий, которые имеют место в точке минимума. Реализация такого подхода связана с решением соответствующихнелинейных уравнений итерационными методами.7.2.1. Поиск минимума функции одной переменнойПусть X — [а, Ь] и кусочно-непрерывная функция /(х) имеет в некоторойточке х* £ X один минимум.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
