Задача численного решения нелинейного уравнения; локализация корня

ЛЕКЦИЯ 12.1 ЗАДАЧА ЧИСЛЕННОГО РЕШЕНИЯ НЕЛИНЕЙНОГО УРАВНЕНИЯ. ЛОКАЛИЗАЦИЯ КОРНЯ. МЕТОДЫ ПОЛОВИННОГО ДЕЛЕНИЯ И ПРОСТОЙ ИТЕРАЦИИ 1. Нелинейные уравнения. Постановка задачи Решение уравнений – это важная прикладная задача. Практически во всех инженерных, научных расчѐтах приходится решать уравнения или их системы. Для некоторых видов уравнений известны формулы точных корней (квадратные, кубические, некоторые тригонометрические и др.). Но, во-первых, они охватывают весьма узкий круг уравнений, в то время как в вычислительной практике приходится решать самые разнообразные уравнения. Во-вторых, формулы точного решения могут быть громоздки, а потому трудны для практического применения. Поэтому возникает задача численного, или приближѐнного, решения уравнений и систем. В этой лекции мы изучим методы решения нелинейных уравнений. Уравнение ( ) называется нелинейным, если функция ( ) нелинейна. Корнем уравнения называется такое число, что его подстановка вместо переменной обращает уравнение в тождество. Точное (теоретическое) значение корня будем обозначать так же, как переменную, т.е. . Задача заключается в нахождении приближѐнного значения корня ( ) , т.е. такого числа , что . Это приближѐнное равенство означает, что | ( )| где ( ) - точность решения. 2. Локализация корней Все методы численного решения нелинейных уравнений - итерационные (прямые методы разрабатываются в фундаментальной математике). Они состоят из двух этапов. -1- Первый, предварительный – это локализация (отделение) корня. Второй, основной, – это итерационное уточнение корня, т.е. собственно решение уравнения. Локализация корня – это обязательный этап решения. Более того, он очень важен: от него во многом зависит успех решения, т.е. сходимость итерационного процесса и еѐ скорость. Локализация, или отделение, корня - это определение промежутка числовой оси, содержащего ровно один корень. Локализация осуществляется исследованием функции . Для этого применяются самые разнообразные методы. Они сильно зависят от уравнения, поэтому здесь невозможно дать общий универсальный алгоритм. Но есть некоторые общие рекомендации. Первая – использовать график. Можно построить график (или эскиз графика) функции и по нему определить промежутки, на которых он пересекает ось чек пересечения – это и есть корни уравнения ( ) . Абсциссы то- . Вторая – преобразовать уравнение (1). Например, можно привести его к виду ( ) функции и ( ) выбираются так, чтобы это уравнение было проще для исследования, чем исходное. Положение корня можно определить опять же графически, построив графики функций ( ), ( ). Корень уравнения - абсцисса точки пересечения этих графи- ков. Иногда полезно привести уравнение к виду ( ) Тогда корень ищется как абсцисса точки пересечения графика функции мой ( ) с пря- . Наконец, можно построить таблицу значений функции и по ней определить проме- жутки, на которых функция меняет знак. Если непрерывна, то на таком промежутке будет хотя бы один корень. Понятно, что для лучшей локализации надо, чтобы узлы таблицы шли с небольшим шагом, а также следует применять другие методы исследования функций. В частности, определить промежутки монотонности функции. При исследовании свойств уравнения можно применять следующие теоремы из курса математического анализа. -2- Теорема 1 (Больцано-Коши). Если непрерывная на отрезке , концах противоположные знаки, т.е. - функция , то на интервале ( ( ) ( ) имеет на его ) она хотя бы один раз обращается в нуль. Теорема 2. Непрерывная строго монотонная функция имеет на отрезке единственный нуль тогда и только тогда, когда на его концах она принимает значения разных знаков. Также при локализации применяются все методы исследования функции из математического анализа. Пример. Рассмотрим уравнение Функция непрерывна на интервале . /. Рассмотрим значения функции в несколь- ких точках: ( ) ( ) ( ) Непрерывная на отрезке , - функция дважды меняет на нѐм знак. Значит, на этом отрезке функция имеет по крайней мере два нуля, и уравнение имеет хотя бы два корня. Докажем, что на отрезках , -и, - имеется ровно по одному корню. Первая производная функции ( ) на отрезке , - монотонна. В этом можно убедиться с помощью второй производной ( ) ( ) которая положительна на всем рассматриваемом отрезке. Первая производная меняет знак на отрезке , - (в этом можно убедиться, подставив – , в формулу производ- ной). Как следствие, первая производная имеет одну точку экстремума на отрезке 0 причем, это точка минимума функции: ( ) -3- , . / . 1, Можно сделать следующие выводы: функция непрерывна, на концах отрезка - еѐ значения положительны; имеется одна точка минимума, в которой значение , функции отрицательно. Значит, на отрезке , - имеется две точки, в которых значения функции равны нулю. Одна точка принадлежит отрезку , , - другая точка отрезку -. Таким образом, удалось локализовать два корня исходного уравнения. 3. Метод половинного деления После локализации корня вступает в действие его итерационное уточнение: выбирается начальная итерация ность ( ) , ( ) , ( ) ( ) из промежутка локализации и строится последователь- , … , сходящаяся к точному решению . Понятно, что вычисление про- должается не бесконечно, а останавливается при достижении заданной точности. Поэтому для полноты метода надо определить: 1. Расчѐтную формулу для произвольной k-й итерации; 2. Оценку погрешности итерации (для критерия останова); 3. Условия сходимости (понятно, что интервал локализации сам по себе не обеспечивает сходимости). Всѐ перечисленное зависит от конкретного метода. Начнѐм с самого простого – метода половинного деления (бисекций). Пусть ( ) – интервал локализации; функция непрерывна на отрезке , - и на его концах принимает значения разных знаков: . ( ) ( ) Делим отрезок , - пополам, - его середина (рис. 1): ( ) Проверяем условие ( ) т.е. является ли , корнем уравнения. Если да, то решение найдено: определяем, на каком из отрезков теперь корень, на , - или , – корень. Если нет, то -. Для этого достаточно проверить знак произведения ( ) ( ). Если оно отрицательно то корень на отрезке , - если положительно то корень на отрезке , -4- - Отрезок, содержащий корень, уменьшился вдвое. Y ( ) ( ) X O ( ) Рис. 1. Метод половинного деления Далее в качестве нового отрезка , , На новом отрезке , - { , , - берѐм тот, на котором находится корень: - ( ) ( ) ( ) ( ) - повторяется та же процедура деления пополам, и так далее. По- нятно, что выполнение точного равенства (3) маловероятно, а при приближѐнном вычислении оно практически невозможно, поэтому на самом деле проверяют выполнение этого равенство с заданной точностью (см. (2)). На каждом шаге длина отрезка, содержащего корень, уменьшается вдвое; и можно локализовать корень с какой угодно точностью. Процесс заканчивается при условии или при условии | ( )| стью уточнения корня. Значение вие (2)). Число , где , – заданные числа, связанные с погрешно- выдаѐтся как приближение корня (достигнуто усло- будет при этом точностью корня, так как очевидно, что после завершения алгоритма | | | На рис. 2 изображена блок-схема алгоритма. -5- | . Начало Ввод , , , , | ( )| или Да Да ( ) ( ) Нет Нет Вывод Конец Рис. 2. Блок-схема алгоритма половинного деления -6- Если задаться точностью локализации корня , то можно определить число шагов, за которое она будет достигнута. Через шагов деления отрезка пополам его длина ста- нет равной Тогда для достижения точности корня достаточно выполнения неравенства из которого следует Следовательно, после выполнения [ ] делений длина промежутка локализации корня гарантированно станет меньше . Очевидно, что рано или поздно нужная локализация будет достигнута при любой начальной итерации, поэтому метод деления отрезка пополам относится к гарантированно сходящимся. Но он имеет очевидный и существенный недостаток: малая скорость сходимости. На каждом шаге погрешность корня уменьшается всего в два раза, т.е. метод половинного деления имеет линейную скорость сходимости и сходится со скоростью геометрической прогрессии со знаменателем ⁄ . Пример. Пусть надо решить уравнение . Для него известны точные корни. Но на его примере можно рассмотреть приближенные методы. Отправляясь от начального отрезка , вестный корень -, локализуем делением отрезка из- В таблице 1 приведены результаты шагов. Число может прибли- зиться к корню, а на следующем шаге отдалиться, но длина отрезка, содержащего корень, с каждым шагом уменьшается. -7- Табл. 1. Итерации метода половинного деления в примере на с. 7 Шаг ( ) ( ) ( ) 4. Метод простой итерации 4.1. Алгоритм метода Метод простой итерации - это обобщение метода простой итерации для линейных систем на нелинейный случай. Исходное уравнение (1) приводится к эквивалентному уравнению ( ) ( ) Этот переход можно сделать многими способами, и он важен, так как от функции зави- сит сходимость итерационной последовательности. Например, можно поступить совсем просто: умножить (1) на число ( ) и прибавить к обеим частям . Получим уравне- ние ( ) ( ) Итерационная последовательность строится так же, как и в линейном случае. Берѐтся начальная итерация ( ) из промежутка локализации, подставляется в правую часть (4), полученное значение принимается за следующую итерацию ( ) ; ( ) опять подставля- ется в правую часть и так далее. Расчѐтная формула выглядит так: ( ) ( -8- ( ) ) ( ) . Если итерационная последовательность { ( ) } имеет предел ̃ и функция непрерывна на промежутке локализации, то этот предел является корнем уравнения. Это доказывается предельным переходом в (6): ( ) ( ( ) ( ) ) ( ( ) ) . ( ) / ( ̃) ̃ На рис. 3 показана графическая иллюстрация метода простой итерации. Корень уравнения – абсцисса точки пересечения прямой ной точки оси ( ) ( ) находится точка . ( ) ( до пересечения с прямой ( ) и кривой ( ). Для началь- )/. Через неѐ проводится прямая параллельно . Абсцисса точки пересечения - новая итерация . Для неѐ проводится то же построение. Последовательность итераций на рисунке сходится к точному значению корня: предел ̃ последовательности { ( ) } существует и совпадает с корнем. Последовательность { ( ) } может расходиться, как показано на рис. 4. Это не зна- чит, что уравнение не имеет корня. Просто, последовательность к нему не сходится. Y ( ( ) ) ( ( ) ) ( ( ) ) ( ) O ( ) ( ) ( ) ( ) Рис. 3. Метод простой итерации -9- X Y ( ) ( ( ) ) ( ( ) ) ( ( ) ) O ( ) ( ) ( ) ( ) X Рис. 4. Расходимость метода простой итерации 4.2. Сходимость метода Естественно, возникает вопрос об условиях сходимости, а также оценке погрешности итерации для критерия останова. Это даѐт следующая теорема. Теорема 3. Пусть для функции 1. Для любых и ( ) из отрезка | | ( ) где 2. ( ) и начального приближения выполнены условия: имеет место неравенство | ( )| | | . Справедливо неравенство где | ( ) ( ( ) )|. Тогда уравнение имеет единственный корень , к которому сходится последовательность { ( ) } метода простой итерации, и имеет место оценка погрешности | где ( ) | . - 10 - С помощью этой теоремы можно вести вычисления до достижения заданной точности: критерием останова будет выполнение неравенства Более того, можно найти число необходимых шагов из этого же неравенства. Однако теорема требует знания , что может быть не так просто (вторую константу найти очень просто). Поэтому были найдены другие, более практичные, условия сходимости. Одно из них даѐт теорема 4. Теорема 4. Пусть на отрезке локализации , - функция определена, непрерывна и дифференцируема и выполняются условия: 1. ( ) , -; 2. | ( )| ( ) Тогда для любого начального приближения , - последовательность { ( ) } метода простой итерации сходится к корню уравнения, при этом справедлива оценка ( ) | | | ( ) ( ) | ( ) Доказательство. Вычитая (4) из (6), получаем ( ) ( ( Применяем к (8) теорему Лагранжа (функция ( ) где ( ( ) ( – некоторая точка между ) при любом начальном приближении пределы отрезка , ) ( ) удовлетворяет еѐ условиям): ( ) ) ( ) ) ( )( ( ) ), и . В силу первого условия теоремы и формулы (6) ( ) -. А значит, - последовательность { , ( ) } не выходит за - при всех . Отсюда в силу второго условия , следует оценка: | ( ) | | ( )( ( ) | ( )| | )| ( ) | | ( ) Применяя последовательно (9), имеем | ( ) | | ( ) | | ( ) А из этого неравенства следует, что | ( ) - 11 - | | | ( ) |. | ( ) Сходимость доказана. Теперь надо получить оценку (7). В правой части (9) добавим и вычтем ( ) : | ( ) | | ( ) | ( ) ( ) ( ) |. Теперь применим свойство модуля: | ( ) | (| ( ) ( ) | |) | ( ) ( ) а отсюда уже нетрудно вывести (7) (по условию (2) теоремы Константу | | ( ) |, ). в этой теореме найти уже проще. Если в условиях теоремы , то можно пользоваться следующим правилом. Вычисления надо вести до тех пор, пока два последовательных приближения не совпадут в пределах заданной точности: ( ) | ( ) | В связи с рассмотрением вопроса о сходимости введѐм следующую терминологию. Пусть некоторый итерационный процесс генерирует последовательность { ( ) } , имею- щую пределом ̃. Сходимость последовательности итераций к ̃ называется линейной, если существуют такая постоянная ( |̃ при всех ) и такой номер ( ) | |̃ ( ) , что | . Сходимость называется сверхлинейной, если существуют такая положи- тельная сходящаяся к нулю числовая последовательность { |̃ при всех ( ) | |̃ ( ) и такой номер , что } | . Последовательность { ( ) } сходится к ̃ по меньшей мере с p-порядком, если найдутся такие константы , что |̃ при всех ( ) ( ) . При ( ) | |̃ ( ) | получается линейная сходимость. Из (9) следует, что метод простой итерации имеет линейную сходимость. В лекции 10.2 такая сходимость была названа сходимостью со скоростью геометрической прогрессии. Число из теоремы 4 – это знаменатель прогрессии, характеризующий скорость сходимости: чем меньше , тем она выше. В заключение вернѐмся к вопросу о переходе от уравнения (1) к (5). Из теоремы 4 следует, что число надо подобрать так, чтобы производная - 12 - ( ) ( ) была ма- ла по модулю в нужной области. Для конкретного подбора водной . Если ( ), где ( ) , то ( ) *| чение , при котором . Значит, | ( ) |+. Если | | надо знать свойства произ- / , то ( ) . ( )| . Оптимальное зна- минимально, равно Если же нет нужных оценок для , то можно подобрать ( Тогда в некоторой малой окрестности ( ) ( ) так, чтобы ) ( производная ) будет мала. Из (10) выводится выражение для : ( С этим ( ) ) ( ( )) расчѐтная формула простых итераций (6) принимает вид ( ) ( ) ( ( ( ) ( ) )) Эта формула представляет собой формулу модифицированного метода Ньютона, который будет изучен в следующей лекции. Пример. Рассмотрим уравнение Методом простой итерации уточним корни, которые имеются на отрезке , отрезке , -, другой – на , -: один на -. Приведѐм исходное уравнение к виду (5). Для каждо- го отрезка, содержащего по одному корню, подберем число . Уточнение корня на отрезке , подобрать так, чтобы -. На этом отрезке производная отрицательна. Надо ( ) в окрестности корня была по модулю меньше ( ) единицы Поскольку ( ) ( ) √ ( ) - 13 - , то (ранее мы выяснили, что ( ) Можно взять жение к корню , для которого | ( ) положительна на всѐм отрезке , , ( )| -). -. Если взять начальное прибли- , , то на 11-й итерации имеем ( ) , ( ( ) ) . Итерационная последовательность сходится медленно. Ситуацию можно улучшить, либо изменив начальное приближение, либо взяв другое число . Для том же начальном приближении имеем Уточнение корня на отрезке , от до ( ) ( ) , ( такой, что невозможно подобрать . ) -. На этом отрезке производная . Для отрезка , √ ( ) при меняет знак, возрастая - диапазон изменения производной для уменьшения . Уменьшим отрезок локализации положительного корня: √ . / √ . / Отрезок, содержащий корень, сужаем до 0 выполнялось условие | ( )| 1. На нѐм , можно взять . Тогда, начиная с ( ) ( ( ) ) - 14 - ( ) . . Для того, чтобы ( ) , получим