main (1160440), страница 12
Текст из файла (страница 12)
Будем считать, чтоначальное приближение 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 ∈ (* ) задано. Пусть в (* ) существует и не обращается в ноль непрерывная первая производная функции (): ′ () ̸= 0, ∈ (* ).Разложим (* ) по формуле Тейлора в малой окрестности точки ∈ (* ): (* ) = () + (* − ) ′ () + . . .и отбросим в этом разложении величины, имеющие второй и выше порядок малости по(* − ).Заменив * на +1 и на , получим уравнение ( ) + (+1 − ) ′ ( ) = 0, ∈ Z+ .Учитывая, что ′ ( ) ̸= 0, и разрешив последнее уравнение относительно +1 , имеем:+1 = − ( ), ′ ( ) ∈ Z+ .(2)Определение. Итерационный процесс поиска корня уравнения (1), задаваемый формулой (2), называется итерационным методом Ньютона.Дадим геометрическую интерпретацию метода Ньютона.
Рассмотрим точку (0 , (0 )).Определим первую итерацию 1 рассматриваемого процесса как абсциссу точки пересечения с осью касательной к функции () в точке . Аналогично получаем значение2 как точку пересечения с осью касательной к функции () в точке (1 , (1 )).Продолжая таким образом, на -ом шаге получаем значение , приближающее корень *уравнения (1) с заданной точностью.* 210Выпишем уравнение касательной к функции () в точке : − ( ) = ′ ( )( − ).Очевидно, что значение +1 , найденное по формуле (2), представляет собой абсциссу точкипересечения с осью касательной к кривой = (), проведенной через точку ( , ( )).§3.
Метод Ньютона и метод секущих75Замечание. Итерационный метод Ньютона часто называют методом касательных.Если не выполнено условие неравенства нулю производной функции () в области (* ), то метод Ньютона может расходиться. На графике показан пример такого случая.*1 0 2Замечание 1. Метод Ньютона является вычислительно сложным, поскольку на каждой итерации проводится вычисление значений производной функции (), что является,вообще говоря, неустойчивым процессом.Замечание 2. При решении задач на практике часто рассматривается модифицированный метод Ньютона, задаваемый формулой+1 = − ( ), ∈ Z+ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
