Численные методы. Ионкин (2013) (1160444), страница 12
Текст из файла (страница 12)
, ) достигает своего минимума:= 0,∑︁ = 0, , ( , ) = (, ), = 0, .=0Вид полученной системы аналогичен виду системы, которую мы рассматривали в предыдущем параграфе, следовательно, для рассматриваемой системы сохраняется свойство существования и единственности решения — { }=0 .Значит, для построения наилучшего среднеквадратичного приближения функции с помощью некоторой системы функций достаточно знать значения этой функции лишь в некоторых точках интересующего отрезка.Глава 3Численное решение нелинейныхуравнений и систем нелинейныхуравнений§1ВведениеРассмотрим задачу поиска корней нелинейного уравнения: нелинейные уравнения, вообще говоря, не имеют аналитического решения, поэтому для поиска решения используютвычислительные методы, хотя такое решение является лишь приближенным.Заметим, что принципиальное отличие численных методов решения нелинейных уравнений от численных методов решения систем линейных уравнений состоит в необходимостиспециально выбирать для конкретного итерационного метода начальное приближение, таккак от этого выбора зависит сходимость рассматриваемых итерационных методов решениянелинейных уравнений.Постановка задачи.
Рассмотрим функцию (), ∈ R, и уравнение () = 0.(1)Пусть * — корень уравнения, и определена его окрестность радиуса , не содержащаядругих корней уравнения: (* ) = { : | − * | < },причем заданная функция () определена на этой окрестности. Будем считать, чтоначальное приближение 0 ∈ (* ) задано. Тогда для нахождения численного решенияуравнения в рассматриваемой окрестности необходимо построить последовательность{ }, сходящуюся к корню * уравнения (1):lim ( ) = (* ) = 0.→∞Численное решение нелинейных уравнений можно разбить на два этапа:1. Локализация корня, т.е.
определение окрестности (* ).2. Задание итерационного процесса — построение последовательности { }, сходящейсяк корню уравнения.Пусть () — непрерывная функция, заданная на отрезке [, ]. Рассмотрим два приемалокализации вещественного корня (известно, что уравнение (1) может иметь и комплексныекорни, но в данном курсе мы не будем ими заниматься).70Глава 3. Численное решение нелинейных уравнений и систем нелинейных уравненийПервый приемПусть задано разбиение сегмента [, ]: 6 0 < 1 < 2 < .
. . < 6 ,и если для некоторого = 1, выполняется условие (−1 ) ( ) < 0,(2)то на интервале (−1 , ) существует по крайней мере один корень уравнения (1) или числокорней на этом интервале нечетно. Если же выполняется условие (−1 ) ( ) > 0, = 1, ,то на каждом из интервалов (−1 , ) либо нет корней уравнения (1), либо их число четно.В случае выполнения условия (2) интервал (−1 , ) вновь разбивается на частичныеинтервалы, и для частичных интервалов повторяется описанная выше процедура, котораяв итоге позволит найти промежуток меньшей длины, содержащий корень.Второй приемБолее регулярным способом отделения действительных корней является метод бисекции(деления пополам).Предположим, что на интервале (, ) расположен лишь один корень * уравнения (1).Тогда () и () имеют различные знаки.
Пусть для определенности () > 0, () < 0.Положим+0 =2и рассмотрим значения функции () в этой точке.Если (0 ) < 0, то значение искомого корня * лежит в интервале (, 0 ), если же (0 ) > 0,то * ∈ (0 , ). Далее из этих двух интервалов (, 0 ) и (0 , ) выбираем тот, на границекоторого функция () имеет различные знаки.Затем находим точку 1 — середину выбранного интервала, вычисляем (1 ) и повторяемуказанный выше алгоритм.В результате получаем последовательность интервалов, содержащих искомый корень* , причем каждый последующий интервал имеет длину в 2 раза меньшую, чем предыдущий. Процесс заканчивается, когда длина вновь полученного интервала станет меньшезаданного числа > 0.Замечание. Как правило рассматриваемая функция () имеет больше одного корня, изадача состоит в поиске всех корней уравнения (1) на области определения функции ().Тогда можно поступать следующим образом: пусть мы нашли один из корней этогоуравнения, причем этот корень имеет единичную кратность.
Тогда для поиска другихкорней рассматриваемого уравнения осуществим переход к функции () вида() = (). − *Очевидно, что уравнение () = 0 имеет на единицу меньше корней, чем уравнение (1), ивсе корни этого уравнения являются также корнями уравнения (1). Поэтому после решения данного уравнения получаем корни исходного уравнения, отличные от уже найденных.Таким образом мы сможем найти по крайней мере все некратные корни уравнения (1).§2. Метод простой итерации71Круг вопросов, которые мы рассматриваем в связи с решением одного нелинейногоуравнения, переносится и на поиск решения системы нелинейных уравнений.
Рассмотримнелинейную систему уравнений (1 , 2 , . . . , ) = 0, = 1, .(3)Введем векторы = (1 , 2 , . . . , ) , = (1 , 2 , . . . , ) . Тогда система уравнений (3)запишется в векторной форме, как () = .Последнее уравнение удобно рассматривать как операторное уравнение в m-мерном пространстве R . При этом отображение : R −→ Rпредставляет собой нелинейное отображение пространства R в себя, и рассуждения о методах решения нелинейных систем проводится аналогично одномерному случаю.§2Метод простой итерацииРассмотрим функцию (), ∈ R и уравнение () = 0.(1)Пусть * — корень этого уравнения, и определена его окрестность радиуса , не содержащаядругих корней рассматриваемого уравнения: (* ) = { : | − * | < },причем заданная функция () определена на этой окрестности.Будем считать, что начальное приближение 0 ∈ (* ) задано.
Рассмотрим итерационные методы, задаваемые общей формулой+1 = ( ), ∈ Z+(2)с некоторой функцией (), определенной на (* ). Пусть функция () имеет вид() = + () (), (* ) = * ,(3)где () — функция, не обращающаяся в ноль в окрестности (* ), то есть (()) ̸= 0, ∈ (* ).Определение. Итерационный метод, описываемый формулой (2) с функцией () вида (3), называется методом простой итерации.Определение. Функция () называется Липшиц-непрерывной при ∈ (* ) с константой > 0, если для любых точек 1 , 2 ∈ (* ) выполнено неравенство|(1 ) − (2 )| 6 |1 − 2 |.Утверждение. Пусть функция () Липшиц-непрерывна с константой ∈ (0, 1) в некоторой окрестности (* ), и пусть задано начальное приближение 0 ∈ (* ).
Тогдаметод простой итерации (2) сходится со скоростью геометрической прогрессии со знаменателем .72Глава 3. Численное решение нелинейных уравнений и систем нелинейных уравненийДоказательство. Докажем с помощью метода математической индукции, что ∈ (* )при ∈ Z+ .Справедливость утверждения 0 ∈ (* ) следует из условия. Пусть требуемое условиеверно при = . Рассмотрим ( + 1)-ую итерацию:+1 = ( )и оценим |+1 − * |, учитывая, что функция () Липшиц-непрерывна:|+1 − * | = |( ) − (* )| 6 | − * |.(4)Из условия ∈ (0, 1) следует неравенство|+1 − * | 6 | − * | < .Таким образом, +1 ∈ (* ).Докажем сходимость метода простой итерации. Используя оценку (4) как рекуррентную, получим:| − * | 6 |0 − * |.(5)Из условия ∈ (0, 1) следует, чтоlim = 0.→∞Тогда в силу неравенства (5) и неотрицательности модуля выполнено равенствоlim | − * | = 0.→∞Следовательно, метод простой итерации сходится со скоростью геометрической прогрессиисо знаменателем .Замечание. Если функция () непрерывно дифференцируема, то в качестве можновзять максимальное значение | ′ ()|, и сходимость будет иметь место, если=⃒⃒max ⃒ ′ ()⃒ < 1.∈ (* )Рассмотрим итерационный метод, записанный уравнением:+1 − + ( ) = 0, ∈ R+ , ∈ Z+ , 0 ∈ (* ).(6)Выразим из этого равенства +1 :+1 = − ( ).Этот метод является методом простой итерации вида (2) с функцией (), имеющий вид() = − ().Получим оценку параметра , которая будет гарантировать сходимость метода простойитерации вида (6), то есть обеспечивать выполнение условий замечания к доказанномувыше утверждению.Пусть окрестность (* ) выбрана таким образом, чтобы в ней выполнялось условие′| ()| < 1.
В предположении об ограниченности функции ′ () вычислим точную верхнююгрань ее модуля:⃒⃒ = sup ⃒ ′ ()⃒ .∈ (* )§3. Метод Ньютона и метод секущих73Продифференцируем функцию (): ′ () = 1 − ′ ().Пусть для определенности ′ () > 0, ∈ (* ). Потребовав, чтобы выполнялось условие| ′ ()| < 1, получим оценку для :|1 − | < 1,2.0< <Таким образом, если для поиска корня * применяется итерационныйзаписанный(︀ метод,)︀2в виде (6), то значение параметра следует выбирать из интервала 0, .Метод Эйткена ускорения сходимости итерационного методаПредположим, что существует число , не зависящее от и такое, что − * ≈ , ∈ Z+ , ∈ R.Запишем оценки для трех последовательных итераций:−1 − * ≈ −1 , − * ≈ ,+1 − * ≈ +1 ,(7)Выразим +1 через итерации −1 , , +1 .
Для этого рассмотрим равенства(+1 − )2 = 2 2 ( − 1)2 ,+1 − 2 + −1 = −1 ( − 1)2 ,получающиеся из выражений (7). Разделим первое равенство на второе:(+1 − )2= +1 .+1 − 2 + −1Подставим полученное выражение для +1 в оценку (7) для корня * и ( + 1)-ой итерации +1 и получим представление для корня * :* ≈ +1 −(+1 − )2.+1 − 2 + −1Метод Эйткена позволяет ускорить сходимость метода простой итерации.
Идея метода заключается в том, что после вычисления −1 , , +1 производится пересчет поформуле(+1 − )2′+1 = +1 − +1,(− 2 + −1 )и значение ′+1 берется в качестве нового приближения.§3Метод Ньютона и метод секущихРассмотрим функцию (), ∈ R и уравнение () = 0.(1)Пусть * — корень этого уравнения, и определена его окрестность радиуса , не содержащаядругих корней уравнения: (* ) = { : | − * | < },74Глава 3. Численное решение нелинейных уравнений и систем нелинейных уравненийпричем заданная функция () определена на этой окрестности.Будем считать, что начальное приближение 0 ∈ (* ) задано.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
