Методы хорд и Ньютона

ЛЕКЦИЯ 12.2 МЕТОДЫ ХОРД И НЬЮТОНА В этой части мы продолжим изучение методов численного решения нелинейных уравнений. Задача заключается в нахождении приближѐнного значения корня нелинейного уравнения ( ) ( ) 1. Метод хорд 1.1. Расчѐтная формула Пусть на отрезке [ ] локализован корень уравнения (1), функция непрерывна на нѐм и принимает на его концах значения разных знаков, т.е. ( ) ( ) Показать ход итерационного процесса лучше всего графически. Стягиваем крайние точки дуги кривой ( ) на отрезке [ точка ( ). Еѐ абсциссу ( ) [ ] ордой (рис. 1). Точка пересечения хордой оси абсцисс – возьмѐм за начальное приближение ]). Далее определяем, на каком из отрезков [ ( ) ] или [ к корню (очевидно, что ] находится Y ( ) ( ) ( ) O ( ) Рис. 1. Метод хорд -1- X корень. Для этого проверяем знак произведения ( ) ( ). Если ( ) ( ) ке [ [ ] если ( ) ( ) то корень на отрезке [ то корень на отрез- ] За новый отрезок локализации ] возьмѐм тот, на котором находится корень: [ ] { [ [ ] ] ( ) ( ) ( ) ( ) Для него проделываем ту же операцию: проводим хорду, находим точку пересечения с осью абсцисс, получаем новую итерацию находится на отрезке [ ( ) ], поэтому новый отрезок [ (рис. 2). На этом рисунке корень ] есть [ ]. Этот процесс продол- жаем до тех пор, пока не будет достигнута требуемая точность корня , т.е. до достижения неравенства . Или же пока не будет достигнута точность выполнения прибли- жѐнного равенства ( ) : | ( )| . Y ( ) ( ) ( ) ( ) O X ( ) Рис. 2. Метод хорд. Вторая итерация Выведем расчѐтную формулу метода. Пусть [ на k-м шаге ( ] – текущий отрезок локализации ). Запишем уравнение прямой, содержащей хорду: ( ) ( ) ( ) -2- Далее находим точку еѐ пересечения с осью абсцисс. Подставляем в уравнение , : ( ) Учитывая, что ( ) ( ) – очередная итерация, приходим к расчѐтной формуле метода: ( ) ( ) ( ) ( ) ( ) . Чем меньше длина начального отрезка [ ], тем лучше приближение к корню, тем быстрее сойдѐтся метод. На рисунке 3 изображена блок-схема алгоритма метода хорд. 1.2. Сходимость Ход итерационного процесса сильно зависит от свойств функции . Пусть, например, функция ную на [ т.е. непрерывна и монотонна и имеет монотонную и непрерывную производ- ]. Пусть для определѐнности , ( ) , ( ) ( ) ]. Поэтому на k-м шаге левый конец отрезка [ ( ( ) ], ] есть . Расчѐтную формулу можно записать так: ( ) , не убывает на [ ] Эта ситуация изображена на рисунке 4. Корень каждый [ раз оказывается на отрезке [ предыдущая итерация монотонно возрастает, и ( ) ( ( ) ) ( ) ( ) ( )) . Это метод хорд с «закреплѐнным» правым концом. Можно строго аналитически доказать, что последовательность итераций не выходит за пределы отрезка [ ], не убыва- ет и сходится к точному корню . Аналогично рассматриваются и остальные случаи знаков производных. Эти результаты можно свести в теорему 1. Теорема 1. Пусть функция производную на [ 1. Если ( ) непрерывна и монотонна, имеет непрерывную и монотонную ], и ( ) ( ) ( ) . или ( ) ( ) тельность метода хорд вычисляется по формуле -3- , то итерационная последова- Начало Ввод , , , , ( ) ( ) | ( )| или Да Да ( ) ( ) ( ) Нет Нет Вывод д Конец Рис. 3. Блок-схема алгоритма метода хорд д -4- Y ( ) ( ) O X ( ) ( ) ( ) Рис. 4. Метод хорд, , ( ) ( ) ( ( ) , ( ) ( ) ( ( ) ) ( ) ( ) ( )) . При этом она не выходит за пределы отрезка [ ], не убывает и сходится к точному корню . 2. Если ( ) ( ) или ( ) , то итерационная последова- ( ) тельность метода хорд вычисляется по формуле ( ( ) , ( ) ( ) ( ) ( ( ) )) ( ) . При этом она не выходит за пределы отрезка [ ], не возрас- тает и сходится к точному корню . Первый случай (одинаковые знаки производных) – это метод хорд с «закреплѐнным» правым концом, второй (разные знаки) – с левым. Теперь оценим погрешность итерации. Учитывая, что ( ) рень, запишем ( ( ) ) как ( ( ) ) ( ( ) и применим формулу Лагранжа: -5- ) ( ) , если – точный ко- ( где – некоторая точка между ( ) ( ) ) и ( ) ( ( ) ) ( ), . Отсюда следует равенство ( ( ) ( ) ) ( ) из которого получаем оценку ( ) ( ) | | | ( ( ) )| где [ | ( )| ] Эту оценку можно также использовать для останова вычислений наряду с описанными ранее. Что касается скорости сходимости, то отметим, что она выше, чем у методов половинного деления и простой итерации, которые имеют линейную скорость. Нестрогие оценки показывают, что метод хорд имеет сходимость порядка √ Этот результат справедлив, когда функция не обращается в ноль на [ дважды дифференцируема, а еѐ производная ]. Пример. Решим методом хорд уравнение [ . Начинаем с отрезка локализации ]. Легко проверить, что теорема 1 неприменима, «закреплѐнного конца» нет. В таблице 1 приведены несколько приближений, вычисленных по формуле (2). Видно, что для рассматриваемого уравнения метод хорд сходится быстрее метода половинного деления. 2. Метод Ньютона Метод Ньютона (касательных) относится к быстро сходящимся. Его также лучше описать геометрически. Задаем некоторое начальное приближение к корню ку функции в точке с абсциссой ( ) ( ) . К графи- проводим касательную (рис. 5). Точку пересечения касательной и оси абсцисс примем за следующее приближение к корню ке с абсциссой ( ) ( ) . Затем в точ- проводим еще касательную, и пересечение ее с осью абсцисс – новое -6- Табл. 1. Итерации метода хорд в примере на с. 6 Шаг ( ) ( ) ( ) Y ( ) ( ) O ( ) X Рис. 5. Метод касательных приближение к корню ( ) ( ) (рис. 6). Затем для повторяется та же процедура и т.д. Выведем формулу метода. Пусть получена итерация касательной к кривой ( ) в точке ( ( ) -7- ( ( ) ( ) ( )) имеет вид ). Уравнение Y ( ) ( ) ( ) O ( ) X Рис. 6. Метод касательных. Вторая итерация ( Теперь найдѐм новую итерацию ( ( ) ) ( ) ) ( ( ) ( )( . Подставляя ки пересечения касательной с осью ( ) ) ) ( ) , ( ) в (3) ( ( ) – абсцисса точ- ), получаем ( ( ) ( ) )( ( ) ( ( ) ( ( ) ) ( ) ( )) ) ( ) . Это и есть расчѐтная формула. Для корректности метода необходимо неравенство нулю производной в некоторой окрестности корня. Понятно, что последовательность { ( ) } может не сходиться к корню. На рисунке 7 показано, как первая итерация вышла за пределы отрезка локализации [ ]. Теорема 2 даѐт некоторые достаточные условия сходимости. Теорема 2. Пусть функция пусть производные последовательность { ( ) [ дважды непрерывно дифференцируема на [ сохраняют ( ) знак } сходится к корню ]. -8- на [ ]. Тогда ], кроме того, итерационная при любом начальном приближении Y ( ) ( ) ( ) O X Рис. 7. Расходимость метода касательных Скорость сходимости метода определяет теорема 3. Теорема 3. Пусть функция удовлетворяет условиям: | ( )| Тогда последовательность { ( ) | ( )| [ ]; } метода Ньютона полностью принадлежит отрезку [ ]и сходится к корню . При этом справедливы неравенства ( | | ( ) ) | | ( ) | ( | ) | ( ) | . Из первого неравенства следует, что метод Ньютона имеет второй порядок сходимости, т.е. он самый быстрый из изученных нами. А второе позволяет оценивать погрешность новой итерации. Поэтому критерием останова может служить выполнение неравенства | ( ) -9- ( ) | Эта оценка применяется для останова по достижении заданной точности корня. Пример. Для уравнения корню по формуле (4): построим несколько последовательных приближений к , , , и не сходиться. В качестве начального приближения возьмем . Но метод может ( ) . Методом Ньютона получим следующие приближения (см. табл. 2). Табл. 2. Итерации метода Ньютона в примере на с. 8. Метод расходится ( ) ( ( ) ) При таком начальном приближении итерационная последовательность не сходится к корню. Табл. 3. Итерации метода Ньютона в примере на с. 8. Метод сходится ( ) ( ( ) ) Рис. 8. Расходимость метода Ньютона в примере на с. 8 - 10 - Изменим начальное приближение всего лишь на : ( ) показано, что последовательность метода Ньютона сходится к корню Последовательность, не сходящаяся к корню начальное приближение . Прямые , ные соответственно. - 11 - , . В таблице 3 . , приведена на рисунке 8. Взято – первая, вторая и третья касатель-