Основные этапы решения нелинейных уравнений

ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ Основные этапы решения нелинейных уравнений Определение 2.1. Нелинейным уравнением называется уравнение вида f x   0 , где f  x   нелинейная функция вида: – нелинейная алгебраическая an x  an 1x n n 1 функция (полином или (2.1) многочлен)  ...  a1 x  a0 ; – трансцендентная функция – тригонометрическая, обратная тригонометрическая, логарифмическая, показательная, гиперболическая функция; –   комбинирование этих функций, например x  sin x . 2 Определение 2.2. Решением нелинейного уравнения (2.1) называется такое значение ** x , которое при подстановке в уравнение (2.1) обращает его в тождество. На практике не всегда удается найти точное решение. В этом случае решение уравнения (2.1) находят с применением приближенных (численных) методов. Определение 2.3. Приближенным решением нелинейного уравнения (2.1) называется * такое значение x , при подстановке которого в уравнение (2.1) последнее будет выполнять-     , где   малая положительная вели- ся с определенной степенью точности, т.е. f x * чина. Нахождение приближенных решений составляет основу численных методов и вычислительной математики. Решение нелинейных уравнений распадается на два этапа: отделение корней уравнений и уточнение корней нелинейных уравнений. На первом этапе необходимо исследовать уравнение и выяснить, имеются корни или нет. Если корни имеются, то необходимо определить их количество и затем найти интервалы, в каждом из которых находится только один корень, т.е. отделить корни. y y  1 x  y y  2 x   Рис. 2.1 x Первый способ отделения корней – графический. Данный метод позволяет определить количество корней на отрезке, но не единственность корня. Если f  x  имеет простой аналитический вид, то, исходя из уравнения (2.1), можно построить график функции y  f  x  . Тогда точки пересечения графика функции с осью абсцисс будут являться приближенными значениями корней исходного нелинейного уравнения. Если f  x  имеет сложный аналитический вид, то можно представить ее в виде раз- ности двух более простых функций f  x   1  x    2  x  . Так как f  x   0 , то выполняет1 ся равенство 1  x    2  x  . Построим два графика y1  1  x  , y 2   2  x  (рис. 2.1). Тогда задача решения нелинейного уравнения (2.1) сводится к поиску абсцисс точек пересечения двух графиков, которые и будут являться приближенными значениями корней уравнения (2.1). x Пример 2.1. Пусть дано нелинейное уравнение вида x  e  0 . Для решения его графическим методом представим уравнение (2.1) в виде 1  x    2  x   0 , где 1  x   x ; 2 x   e  x . Графики функций y  x ; y  e  x представлены на рис. 2.2, из которого видно, что исходное уравнение имеет единственный корень  . yx y 1 y  ex  x Рис. 2.2. Пример 2.2. Пусть задано нелинейное уравнение вида e Построив два графика функций y   x и y  e нение не имеет корней (рис. 2.3). x y  e x y  x x Рис. 2.3 2  x  0 или  x  e  x . , нетрудно заметить, что исходное урав- y 1 x Пример 2.3. Для нелинейного уравнения вида x  sin 2 x  0 с помощью аналогичных преобразований получим, что исходное уравнение имеет три корня (рис. 2.4). y yx y  sin 2 x 1   2 2 3  2  x Рис. 2.4 Второй способ отделения корней нелинейных уравнений – аналитический. Процесс отделения корней здесь основывается на следующих теоремах. Теорема 2.1. Если функция f  x  непрерывна на отрезке a, b и на концах отрезка принимает значения разных знаков (т.е. f a  f b   0 ), то на a, b содержится хотя бы один корень. Теорема 2.2. Если функция f  x  непрерывна на отрезке a, b, выполняется условие вида f a  f b   0 и производная f  x  сохраняет знак на a, b, то на отрезке имеется единственный корень. Теорема 2.3. Если функция f  x  является многочленом n -й степени и на концах от- резка a, b принимает значения разных знаков, то на a, b имеется нечетное количество корней. Если на концах отрезка a, b функция не меняет знак, то уравнение (2.1) либо не имеет корней на a, b, либо имеет четное количество корней. При аналитическом методе исследований необходимо выявить интервалы монотонности функции f  x  . Для этого необходимо найти критические точки 1 ,  2 ,...,  n , т.е. точки, в которых первая производная f  i  равна нулю или не существует. Тогда вся числовая ось разбивается на интервалы монотонности i , i 1  , на каждом из которых определяется знак производной f  xi  , где xi  i , i 1  . Затем выделяются те интервалы монотонности i , i 1  , на которых функция f x  меняет знак, т.е. выполняется неравенство f i  f i 1   0 . На каждом из этих интервалов для поиска корня используются методы уточнения корней. Наиболее распространенными методами уточнения корня на отрезке являются итерационные (приближенные) методы: метод половинного деления (метод дихотомии), метод простых итераций, метод Ньютона (метод касательных) и его модификация. 3 Метод половинного деления Для уточнения корня нелинейного уравнения (2.1) на отрезке a, b, где f a  f b   0 , а производная сохраняет знак, применим метод половинного деления. Для этого разделим отрезок a, b пополам и исследуем знак функции в полученной точке с , где c ab . Из двух отрезков a, c и c, b выбираем тот, на котором функция меняет знак. 2 Уменьшая новый отрезок в два раза, повторяем процесс и т.д. Получим последовательность отрезков a1 , b1 , a2 , b2 ,..., an , bn ,... , на концах которых выполняется неравенство f an  f bn   0 (2.2) и длины этих отрезков равны 1 (2.3) b  a  . 2n Последовательность a1 , a2 ,..., an ,... является монотонной неубывающей ограниченной последовательностью; а b1 , b2 ,..., bn ,...  монотонной невозрастающей ограниченной bn  an  последовательностью. Следовательно, эти последовательности сходятся. Перейдем к пределу при n  в левой и правой частях соотношения (2.3), получим 1 b  a   0 . n  2 n lim bn  an   lim n  Тогда lim an  lim bn   . С другой стороны, из неравенства (2.2) следует, что n  n  2 lim f bn  f an    f    0 . Последнее неравенство возможно только тогда, когда n  f   0 . Следовательно,  является корнем исходного уравнения (2.1). ПРИМЕР. Решить нелинейное уравнение 5 cos( x )  3x  0 на промежутке [0.8; 1.1] с точностью 0,0001 (но не более 3 итераций) методом половинного деления. Решение: исходим из того, что должно выполняться условие f an  f bn   0 . 2 f (0.8)  5 cos(0.82 )  3  0.8  1,6105 f (1.1)  5 cos(1.12 )  3 1.1  1,5349 f (0.8) f (1.1)  1.6105 (1.5349)  0  верно! Действия по Методу: 1. Итерация 1, i=0: a0  0.8, b0  1.1 x0  a0  b0 0.8  1.1   0.95 2 2 Для проверки точности: | f ( x0 ) || 5 cos(0.952 )  3  0.95 | 0.2482  0.0001- не верно!!! Для перехода на следующую итерацию должно быть проверено условие: f (ai ) f ( xi )  0, то ai1  ai , bi1  xi f (ai ) f ( xi )  0, то ai1  xi , bi1  bi 4 f (0.8) f (0.95)  1.6105 0.2482  0, то a1  x0  0.95, b1  b0  1.1 2. Итерация 2, i=1: a1  0.95, b1  1.1 x1  a1  b1 0.95  1.1   1.025 2 2 Для проверки точности: | f ( x1 ) || 5 cos(1.0252 )  3 1.025 || 0.5899| 0.5899  0.0001- не верно!!! Определим следующие границы: f (0.95) f (1.025)  0.2482 (0.5899)  0, то a2  a1  0.95, b2  x1  1.025 3. Итерация 3, i=2: a2  0.95, b2  1.025 x2  a2  b2 0.95  1.025   0.9875 2 2 Для проверки точности: | f ( x2 ) || 5 cos(0.98752 )  3  0.9875|| 0.1573| 0.1573  0.0001- не верно!!! Определим точность: | f ( x2 ) | 0.1573 Значит   0.2 Метод простых итераций Пусть известно, что нелинейное уравнение f  x   0 , где f  x  - непрерывная функ- ция, имеет на отрезке a, b единственный вещественный корень   a, b . Требуется найти этот корень с заданной точностью  . Применяя тождественные преобразования, приведем уравнение (2.1) к виду (2.4) x  x . Выберем произвольно приближенное значение корня (начальное приближение) x0  a, b и вычислим первое приближение  x0   x1 . Найденное значение x1 подставим в правую часть соотношения (2.4) и вычислим  x1   x2 , и так далее, т.е. xn1  xn , n  0, 1, 2,... (2.5) Продолжая процесс вычислений дальше, получим числовую последовательность x0 , x1 , x2 ,.. . Если существует предел этой последовательности, то он и является приближенным значением корня уравнения (2.4 Следовательно, предел последовательности xn  является корнем уравнения (2.4). Таким образом, корень можно вычислить с заданной точностью по следующей итера5 ционной формуле xn 1  xn , n  0,1,2,... Геометрическая интерпретация метода простых итераций Если на интервале [a,b] функция возрастает, то f ’(x)>0, если убывает - f ’(x)<0. Точками экстремума являются те точки, на которых производная меняет свой знак, при этом, если с «+» на «-», то это точки максимума, наоборот – минимума. Геометрически метод итерации может быть пояснен следующим образом. Построим на плоскости XOY графики функций y  x и y   x  . Действительный корень  уравнения (2.4) является абсциссой точки пересечения кривой y   x  с прямой y  x (рис. 2.5). Начиная процесс с некоторой точки B0 x0 , x0  , строим ломаную линию y yx y  x  A0 B0 A1 B1 B2 0 a  x2 x1 x0 b x Рис. 2.5 B0 A0 B1 A1B2 ... («лестница»), звенья которой попеременно параллельны оси OX и оси OY , вершины B0 , B1 , B2 ... лежат на кривой y  x  , а вершины A0 , A1 ,...  на прямой y  x . Общие абсциссы точек A0 и B1 , A1 и B2 , … представляют собой соответственно последовательные приближения x1 , x2 ,... корня  . В рассмотренном случае кривая y  x  пологая, x   0 и  x   1. Возможен другой вид ломаной B0 A0 B1 A1 B2 ... («спираль») (рис. 2.6). В этом случае последовательные приближения x1 , x2 ,... стремятся к корню  то с одной, то с другой стороны. В этом случае x   0 , но  x   1. y  x  y yx B1 y0 A0 y1 a M A2 A1 B2 B0 x1  x2 x0 Рис. 2.6 6 b x Однако если рассмотреть случай, где  x   1 (рис. 2.7), то процесс итераций расходится, т.е. последовательные приближения x0 , x1 , x2 ,... все дальше удаляются от корня  и в какой-то момент могут выйти за пределы отрезка a, b. Поэтому для практического применения метода простых итераций нужно определить достаточные условия сходимости итерационного процесса. Достаточное условие, при котором итерационный процесс, заданный формулой (2.5), сходится, определяет следующая теорема. y  x  y B2 yx B1 A1 B0 A0 0 a  x0 x1 b x2 x Рис. 2.7 Теорема 2.4. Пусть функция x  определена и дифференцируема на отрезке a, b, причем все ее значения x [a, b] и выполняется условие  x   q  1 при a  x  b , (2.6) тогда процесс итераций, определяемый формулой (2.5), сходится независимо от выбора начального приближения x0  a, b и предельное значение   lim xn является единственn  ным корнем уравнения (2.4) на отрезке a, b. Приведение нелинейного уравнения f  x   0 к виду x  x  , допускающему сходящиеся итерации Выполнения достаточного условия сходимости можно добиться путем перехода от исходного уравнения f  x   0 к эквивалентному виду x  x  следующим образом: умножим обе части уравнения (2.1) на неизвестную постоянную c  const  0 , c  1, затем прибавим к обеим частям переменную x , тогда получим x  cf  x   x . Обозначим через x   x  cf x  , тогда x  x . Константа c выбирается так, чтобы выполнялось достаточное условие сходимости итерационного процесса (2.6), т.е.  x   1  cf  x   1 для всех x  a, b. Это условие равносильно условию  1  1  cf  x   1, отсюда: 2  c  0 при f x   0, x  a, b ; 1) f  x  2 2) 0  c  при f  x   0, x  a, b . f  x  7 Условия окончания итерационного процесса Процесс итераций заканчивается при одновременном выполнении двух условий: 1) если два последующих приближения отличаются между собой по модулю на величину, не превышающую заданной точности  , т.е. xn 1  xn   . Отдельно этого критерия недостаточно, так как в случае крутизны графика, данное условие будет выполнено, но xn 1 может находиться далеко от корня; 2) мера удовлетворения уравнению (2.1) последнего приближения корня: f xn 1    . Отдельно данного критерия недостаточно, так как при пологой функции f  x  это условие может быть выполнено, но xn 1 может находиться далеко от корня. Метод простых итераций имеет два достоинства:  является универсальным, простым для реализации на ЭВМ и самоисправляющимся, т.е. любая неточность на каком - либо шаге итераций не отразится на конечном результате, а отразится лишь на количестве итераций. Подобные ошибки устойчивы даже по отношению к грубым ошибкам (сбоям ЭВМ), если только ошибка не выбрасывает очередное приближение за пределы области сходимости;  позволяет достигнуть любой заданной точности при любом начальном приближении x0  a, b . Недостатки метода:  трудоемкость процесса приведения уравнения (2.1) к виду (2.4);  если начальное приближение x0 выбрано достаточно далеко от корня, то число итераций, необходимых для достижения заданной точности, будет достаточно большое и объем вычислений возрастет. Пример 2.4. Доказать графическим и аналитическим методами существование единственного корня нелинейного уравнения f ( x)  e x  x  0 (2.7) на отрезке x  [1,0] и построить рабочие формулы метода простых итераций для поиска корня. 1. Докажем графическим методом единственность корня нелинейного уравнения (2.14). Из графика функции f ( x)  e  x на рис. 2.8 видно, что функция f (x) пересекает ось OX в одной точке, являющейся приближенным значением корня нелинейного уравнения (2.7). Но так как данная функция имеет сложный аналитический вид, то преобразуем x уравнение (2.7) к виду e   x и построим два графика функций y  e и y   x , имеющих более простой аналитический вид (рис. 2.9). Абсцисса точки пересечения графиков является приближенным значением корня. x x 8 y y  x 1,200 y  ex 1,000 y 0,800 0,600 0,400 0,200 0,000 -0,200 -1 -0,9 -0,8 -0,7 -0,6 -0,5 -0,4 -0,3 -0,2 -0,1 x  0 Рис. y 2.9 -0,400 -0,600 -0,800 Рис. 2.8 Для доказательства единственности корня на отрезке воспользуемся аналитическим методом. Функция f ( x) непрерывна на отрезке [ 1,0] , имеет на концах отрезка разные знаки ( f (1)  0.632; f (0)  1), а производная функции f ( x) не меняет знак на отрезке ( f ( x)  e  1  0 x [1,0] ). Следовательно, нелинейное уравнение (2.7) имеет на указанном отрезке единственный корень. x 1) Функция y=f(x) выпукла вниз на промежутках, где вторая производная положи- тельна f ' ' ( x)  0 . 3) Функция y=f(x) выпукла вверх на промежутках, где вторая производная отрицательна f ' ' ( x)  0 . 3) Функция y=f(x) имеет критические точки второго рода в точках, в которых вторая производная равна нулю или не существует (речь идет только о внутренних точках области определения функции. Точки на концах области определения не рассматриваем). 4) Функция y=f(x) имеет точки перегиба в точках, в которых вторая производная меняет знак. Метод Ньютона (метод касательных) Пусть известно, что нелинейное уравнение f  x   0 имеет на отрезке  a, b  един- ственный вещественный корень   a, b . Причем, производные f   x  , f   x  – непрерывны и сохраняют определенные знаки на отрезке  a, b  . Требуется найти этот корень с заданной точностью  . Найдем какое-либо n -е приближенное значение корня xn   ( a  xn  b ) и уточним его методом Ньютона следующим образом. Пусть   xn   n . 9 (2.8) По формуле Тейлора получим 0  f   f xn   n   f xn    n f xn  . f  xn  Следовательно,  n   . f  xn  Внося эту правку в формулу (2.8), получим рабочую формулу метода Ньютона вида: xn 1  xn  f  xn  , n  0,1, f   xn  (2.9) Геометрически метод Ньютона эквивалентен замене небольшой дуги кривой y  f  x  касательной, проведенной в некоторой точке  xn , yn  этой кривой. Для определенности положим f   x   0 и f  b   0 . Выберем начальное прибли- жение x0  b , для которого f  b   0 . Проведем касательную к кривой y  f  x  в точке B0  x0 , f  x0   . За первое приближение x1 берем точку пересечения касательной с осью OX . На кривой определим точку B1  x1, f  x1   и проведем касательную к кривой y  f  x  в этой точке. Найдем следующее приближение x2 и т.д. (рис. 2.10). y B0 y  f  x B1 B2 a  x0  x2 x1 x0  b x1 x Рис. 2.10 Если в качестве начального приближения взять другой конец отрезка  a, b  x0  a , то следующее приближение x1   a, b  . Теорема 2.5. Если f  a  f  b   0 и производные f   x  , f   x  не равны нулю и сохраняют определенные знаки на отрезке [ a, b] , то исходя из начального приближения x0 , удовлетворяющего неравенству f  x0  f   x0   0 , по методу Ньютона, заданному форму- лой (2.9), можно вычислить единственный корень  уравнения (2.1) с любой степенью точности. Замечание. Чем больше числовое значение f   x  в окрестности корня  , тем меньше правка  n . Поэтому методом Ньютона удобно пользоваться, когда в окрестности искомого корня  график функции y  f  x  имеет большую крутизну (т.е. f   xn   , тогда n 10 f  xn   0 ). Если кривая y  f  x  вблизи точки пересечения с осью OX почти горизонf   xn  n тальная (т.е. f   xn   0 , тогда n f  xn   0 ), то применять метод Ньютона для решения f   xn  n уравнения (2.1) не рекомендуется. Достоинства метода Ньютона:  обладает достаточно большой скоростью сходимости, близкой к квадратичной;  достаточно простое получение итерационной формулы (2.17). Недостатки метода Ньютона:  сходится не при любом выборе начального приближения x0 ;  применим только, когда f   x   0 для любого x   a, b  . ПРИМЕР. Решить нелинейное уравнение 5 cos( x )  3x  0 на промежутке [0.8; 1.1] с точностью 0,0001 (но не более 3 итераций) с помощью метода Ньютона. Решение: 1. Определяем тот конец отрезка, на котором выполняется условие на сходимость: f  x0  f   x0   0 . Как видно из формулы нам необходимо вычислить значение функции на концах отрезка, а также значение второй производной. 2. Определим формулу для вычисления второй производной: 2 f ' ( x)  5( sin( x 2 )  2 x  3  10  x  sin( x 2 )  3 f ' ' ( x)  10(sin( x 2 )  cos( x 2 )  2 x  x)  10 sin( x 2 )  20x 2 cos( x 2 ) 3. Определим знак условия на сходимость: f ( x0 )  f (0.8)  5 cos(0.82 )  3  0.8  1,6105 А) f ' ' ( x0 )  f ' ' (0.8)  10 sin(0.8 )  20  0.8 cos(0.8 )  16,2388 2 2 2 f (0.8)  f ' ' (0.8)  1,6105 (16,2388)  0  неверно!!! f ( x0 )  f (1.1)  5 cos(1.12 )  3 1.1  1,5349 Б) f ' ' ( x0 )  f ' ' (1.1)  10 sin(1.1 )  20  1.1 cos(1.1 )  17,8992 2 2 2 f (1.1)  f ' ' (1.1)  1,5349 (17,8992)  0  верно!!! 4. Действия по методу: Определение первого приближения начнем с правого конца интервала. 4.1. Итерация 1, i=0: Используем формулу: f  xn  , n  0,1, f   xn  f ( x0 )  1.5349 x1  x0   1.1   0.9845. f ' ( x0 )  13.2918 xn 1  xn  Проверим достигнутую точность: 11 f ( x1 )  5 cos(0.98452 )  3  0.9845  0.1239 | f ( x1 ) | 0.1239  0.0001  неверно!!! 4.2. Итерация 2, i=1: Используем формулу: x2  x1  f ( x1 )  0.1239  0.9845   0.9734. f ' ( x1 )  11.1168 Проверим достигнутую точность: f ( x2 )  5 cos(0.97342 )  3  0.9734  0.0017 | f ( x2 ) | 0.0017  0.0001  неверно!!! 4.3. Итерация 3, i=2: Используем формулу: x3  x2  f ( x2 )  0.0017  0.9734   0.9732. f ' ( x2 )  10.9036 Проверим достигнутую точность: f ( x3 )  5 cos(0.97322 )  3  0.9732  0.0005 | f ( x3 ) | 0.0005  0.0001  неверно!!! Требуемая точность корня уравнения не достигнута, но 3 итерации были выполнены. Поэтому оценим достигнутую точность для приближения x3 : | f ( x3 ) | 0.0005  0.001. Модифицированный метод Ньютона Если производная f   x  мало изменяется на отрезке [ a, b] , то можно считать, что f   xn   f   x0  . Заменив в формуле (2.9) f   xn  на f   x0  , получим рабочую формулу модифицированного метода Ньютона: xn 1  xn  f  xn  , n  0,1,... f   x0  12 (2.10) В отличие от метода Ньютона, в модифицированном методе касательная заменяется   на прямые, параллельные касательной, проведенной в точке B0 x0 , f  x0  (рис. 2.11). y f  x0  B0 y  f  x B1 B2 a  x3 x2 x1 x0  b x Рис. 2.11 Рабочая формула метода Ньютона (2.9) для данной задачи запишется так: xn 1  xn  e xn  xn , n  0,1,2,... e xn  1 Рабочая формула модифицированного метода Ньютона (2.10) для данной задачи запишется в виде: e xn  xn xn 1  xn  x , n  0,1,2,... e 0 1 13