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