Н.И. Ионкин - Численные методы (1163659), страница 13
Текст из файла (страница 13)
Из оценки (5)следует, что погрешность метода убывает со скоростью геометрической прогрессии со знаменателем < 1. Предположим, что существует число , независящее от и такое, что − * ≈ , ∈ Z+ , ∈ R.(7)§3. Метод Ньютона и метод секущих99С помощью метода (2) вычислим три последовательных приближения −1 , , +1 и запишем для них соотношение (7):−1 − * ≈ −1 , − * ≈ ,+1 − * ≈ +1 .(8)Из этой системы уравнений можно найти числа * , и , которые заранеене были известны.
В частности, выразим * через итерации −1 , и +1 .Для этого рассмотрим приближенные равенства(+1 − )2 = 2 2 ( − 1)2 ,+1 − 2 + −1 = −1 ( − 1)2 ,получающиеся из выражений (8). Разделим первое равенство на второе:(+1 − )2= +1 .+1 − 2 + −1Подставим полученное выражение для +1 в оценку (8) для корня * и( + 1)-й итерации +1 и получим представление для корня * :* ≈ +1 −(+1 − )2.+1 − 2 + −1(9)Если бы соотношение (7) было точным, то формула (9) давала бы точное значение * . На самом деле равенство (7) приближенное, и выражение, стоящеев правой части равенства (9), можно принять за очередное приближение ккорню * .
Отметим, что хотя данный прием не является вполне обоснованным, он достаточно эффективно используется в практике вычислений. Этотприем ускорения сходимости не зависит от конкретного итерационного метода, важно лишь наличие сходимости, выраженное соотношением (7). Подчеркнем, что главным предположением здесь является требование линейнойсходимости основного итерационного метода. В случае методов, имеющих более высокую скорость сходимости (например, метод Ньютона), ускорение поЭйткену неэффективно (см.
[1]).§3Метод Ньютона и метод секущихРассмотрим функцию (), ∈ R и уравнение () = 0.(1)100Глава III . Численное решение нелинейных уравнений и систем нелинейных уравненийПусть * — вещественный корень этого уравнения, и определена его окрестность радиуса , не содержащая других корней уравнения: (* ) = { : | − * | < },причем заданная функция () определена на этой окрестности.Будем считать, что начальное приближение 0 ∈ (* ) задано. Пусть в (* ) существует и не обращается в ноль непрерывная первая производнаяфункции (): ′ () ̸= 0, ∈ (* ).Разложим (* ) по формуле Тейлора в малой окрестности точки ∈ (* ): (* ) = () + (* − ) ′ () + .
. .и отбросим в этом разложении величины, имеющие второй и выше порядокмалости по (* − ).Заменив * на +1 и на , получим уравнение ( ) + (+1 − ) ′ ( ) = 0, ∈ Z+ .Учитывая, что ′ ( ) ̸= 0, и разрешив последнее уравнение относительно+1 , имеем:+1 = − ( ), ′ ( ) ∈ Z+ .(2)Итерационный процесс поиска корня уравнения (1), задаваемый формулой (2), называется итерационным методом Ньютона.Определение.Дадим геометрическую интерпретацию метода Ньютона. Рассмотрим точку (0 , (0 )).
Определим первую итерацию 1 рассматриваемого процессакак абсциссу точки пересечения с осью касательной к функции () в точке . Аналогично получаем значение 2 как точку пересечения с осью касательной к функции () в точке (1 , (1 )). Продолжая таким образом,на -м шаге получаем значение , приближающее корень * уравнения (1)с заданной точностью.§3. Метод Ньютона и метод секущих101* 210Выпишем уравнение касательной к функции () в точке : − ( ) = ′ ( )( − ).Очевидно, что значение +1 , найденное по формуле (2), представляет собой абсциссу точки пересечения с осью касательной к кривой = (),проведенной через точку ( , ( )).Замечание.сательных.Итерационный метод Ньютона часто называют методом ка-Если не выполнено условие неравенства нулю производной функции ()в области (* ), то метод Ньютона может расходиться.
На графике показанпример такого случая.102Глава III . Численное решение нелинейных уравнений и систем нелинейных уравнений*1 0 2Метод Ньютона является вычислительно сложным, поскольку на каждой итерации проводится вычисление значений производнойфункции (), что является, вообще говоря, неустойчивым процессом.Замечание 1.При решении задач на практике часто рассматривается модифицированный метод Ньютона, задаваемый формулойЗамечание 2.+1 = − ( ), ∈ Z+ .
′ (0 )Преимущество этого метода перед классическим методом заключается втом, что в нем не требуется вычислять значения функции ′ () на каждойитерации. Однако при этом модифицированный метод Ньютона сходится медленнее классического метода Ньютона. Вопросы сходимости методаНьютона излагаются в §4.Метод Ньютона для нелинейных систем уравненийРассмотрим систему из двух нелинейных уравнений:{︃1 (1 , 2 ) = 0.2 (1 , 2 ) = 0(3)Пусть точка (*1 , *2 ) — решение этой системы.
Разложим значение функции1 (*1 , *2 ) по формуле Тейлора в малой окрестности точки (1 , 2 ), лежащейв окрестности решения:1 (*1 , *2 ) = 1 (1 , 2 ) + (*1 − 1 )1 (1 , 2 )1 (1 , 2 )+ (*2 − 2 )+ ...12§3. Метод Ньютона и метод секущих103Заменим в этом разложении на , * на +1, = 1, 2 и учтем, что(*1 , *2 ) — решение первого уравнения системы (3):1 (1 , 2 ) + (+1− 1 )11 (1 , 2 )1 (1 , 2 )+ (+1− 2 )= 0.212(4)Аналогичным образом, разложив функцию 2 (*1 , *2 ) по формуле Тейлора ипроизведя такую же замену переменных, получим− 1 )2 (1 , 2 ) + (+11 2 (1 , 2 )+1 2 (1 , 2 )−)+(= 0.2212(5)Введем векторы = (1 , 2 ) , = (1 , 2 )и матрицу Якоби системы (3) — матрицу1 () и 2 ():⎛1()⎜ 1⎜() = ⎜⎝ 2()1из частных производных функций⎞1()⎟2⎟⎟.⎠2()2(6)Перепишем уравнения (4) и (5) в матричном виде: ( ) + ( )(+1 − ) = .(7)Пусть матрица Якоби невырождена.
Выразим ( + 1)-ю итерацию через -ю:+1 = − −1 ( ) ( ), ∈ Z+ .(8)Заметим, что нахождение матрицы не является простой процедурой, таккак вычисление производных является, вообще говоря, неустойчивым процессом.При поиске значения каждой следующей итерации +1 можно сначала решить линейную систему:Замечание.( ) = − ( ), ∈ Z+ ,где = +1 − .
Теперь значение +1 получается из найденного :+1 = + .104Глава III . Численное решение нелинейных уравнений и систем нелинейных уравненийТеперь перейдем к рассмотрению системы из > 2 нелинейных уравнений⎧⎪1 (1 , 2 , . . . , ) = 0⎪⎪⎪⎨ ( , , . . . , ) = 02 1 2.(9)⎪...⎪⎪⎪⎩ ( , , . . . , ) = 0 1 2Введем векторы = (1 , 2 , . . . , ) , = (1 , 2 , . . . , )и матрицу Якоби системы (9): = ( ), =,, = 1, .Запишем схему итерационного метода Ньютона, используя матрицу Якоби:+1 = − −1 ( ) ( ), ∈ Z+ .Заметим, что вычислять матрицу на каждом шаге достаточно трудоемко.Аналогично одномерному случаю можно рассматривать модифицированный метод Ньютона для решения нелинейных систем:Замечание.+1 = − −1 (0 ) ( ), ∈ Z+ .Реализация модифицированного метода Ньютона проще классического варианта, но скорость сходимости при данном подходе меньше.Метод секущихИтерационный метод решения уравнения (1) называетсяодношаговым, если для нахождения + 1-й итерации корня +1 используется только -я итерация .
Если для нахождения +1 используетсяне только , но и предыдущие ей другие итерации, то метод называетсямногошаговым.Определение.Ранее мы рассматривали одношаговые методы решения нелинейных уравнений — метод простых итераций и итерационный метод Ньютона. Рассмотрим многошаговый итерационный метод — метод секущих.Запишем итерационный метод Ньютона для решения уравнения (1):+1 = − ( ), ∈ Z+ , 0 ∈ (* ).
′ ( )(10)§4. Сходимость метода Ньютона. Оценка скорости сходимости105Заменимпроизводную ′ ( )наеёдискретныйи подставим это отношение в уравнение (10). −−1Получим итерационный метод ( )− (−1 )+1 = −( − −1 ) ( ), ( ) − (−1 ) ∈ N, 0 , 1 заданы.аналог(11)Определение. Итерационный процесс (11) задает двухшаговый метод решения нелинейных уравнений, называемый методом секущих.Рассмотрим геометрическую интерпретацию метода секущих.+1 −1Через точки (−1 , (−1 )), ( , ( )) проводится секущая.
За новоезначение +1 принимается абсцисса точки пересечения секущей и оси .Иначе говоря, на отрезке [−1 , ] функция () интерполируется полиномом первой степени, и за очередное приближение +1 принимается кореньэтого полинома.§4Сходимость метода Ньютона. Оценка скоростисходимостиРассмотрим функцию (), ∈ R и уравнение () = 0.(1)106Глава III . Численное решение нелинейных уравнений и систем нелинейных уравненийПусть * — вещественный корень этого уравнения, и определена его окрестность радиуса , не содержащая других корней уравнения: (* ) = { : | − * | < },причем заданная функция () определена на этой окрестности.Будем считать, что начальное приближение 0 ∈ (* ) задано.
Запишемформулу итерационного метода Ньютона решения уравнения (1):+1 = − ( ), ∈ Z+ , 0 ∈ (* ). ′ ( )Будем рассматривать итерационный метод Ньютона как метод простой итерации с функцией ()() = − ′. ()При изучении сходимости метода простой итерации было замечено, что,если | ′ ()| < 1 при ∈ (* ), то он сходится. Предполагая, что функция () дифференцируема достаточное число раз, продифференцируем функцию ():( ′ ())2 − () ′′ () () ′′ () ′ () = 1 −=.( ′ ())2( ′ ())2Так как * — корень уравнения (1), то (* ) = 0, и, следовательно, ′ (* ) = 0,и по непрерывности функции ′ () имеем | ′ ()| < 1, следовательно методсходится.Введем погрешность приближенного решения: = − * .Покажем, что связь между и +1 квадратичная.
Рассмотрим выражениедля +1 : +1 = +1 − * = ( + * ) − (* ).(2)Разложим ( + * ) по формуле Тейлора и учтем, что ′ (* ) = 0:11 +1 = (* ) + ′ (* ) + ′′ (˜ ) ( )2 − (* ) = ′′ (˜ )( )2 ,22(3)˜ = + , ∈ R, || < 1.Пусть функция () трижды непрерывно дифференцируема в окрестности (* ). Тогда(︂)︂ () ′′ () ′′′ () =.( ′ ())2§4. Сходимость метода Ньютона. Оценка скорости сходимости107Пусть существует постоянная > 0 такая, что для любого ∈ (* )выполняется неравенство⃒1⃒(4) > ⃒ ′′ ()⃒ .2Из этого неравенства и уравнения (3) следует оценка| +1 | 6 |( )2 |.(5)Домножим это неравенство на и обозначим = | |.
Тогда получим,что +1 6 ( )2 .Отсюда следует, что 6 ( 0 )2 , значит,(︀ ⃒ ⃒)︀2 | | 6 ⃒ 0 ⃒,1 (︀ ⃒⃒ 0 ⃒⃒)︀2. Введем обозначение = |0 |. Если 0 < < 1, то последовательность{ }∞=0 стремится к нулю: −→ 0,| | 6→∞и итерационный метод Ньютона сходится. Условие на (0 < < 1) будет11выполнено, если 0 < | 0 | < , то есть |0 − * | < .Таким образом, мы доказали следующую теорему.Пусть существует такая константа > 0, для которойвыполнена оценка1 ⃒⃒ ′′ ⃒⃒ () 6 , ∈ (* ).2Тогда если начальное приближение 0 выбрать в соответствии с условиемТеорема 1.|0 − * | <1,то итерационный метод Ньютона сходится, и имеет место оценка:| − * | 6)︀21 (︀ |0 − * |.Если итерационный метод Ньютона сходится, то достаточно быстро.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
