В классической математике многое выглядит элементарно. Так, если нужно найти экстремум некоторой функции, то предлагается взять ее производную, приравнять нулю, решить полученное уравнение и т.д. Вне сомнения, что первые два действия в состоянии выполнить многие школьники и студенты. Что касается третьего действия, то позвольте усомниться в его элементарности.

Пусть после взятия производной мы пришли к уравнению tg(x)=1/x . Проведем следующие преобразования:
tg(x)=1/x Ю x tg(x)=1 Ю x2 tg=1 Ю x2= 1 / tg(x) Ю x = ± .

Если в приведённой здесь цепочке преобразований ничто не взволновало вашу мысль, то может быть лучше обучение на этом прекратить и заняться чем-нибудь другим, не требующим уровня знаний выше церковно-приходской школы начала XX века.

В самом деле, мы прекрасно решаем квадратные и биквадратные уравнения, наипростейшие тригонометрические и степенные. Еще водятся "мастодонты", знающие о существовании формул Кардано для кубических уравнений. В общем же случае надежд на простое аналитическое решение нет. Более того, доказано, что даже алгебраическое уравнение выше четвертой степени неразрешимо в элементарных функциях. Поэтому решение уравнения проводят численно в два этапа (здесь разговор идет лишь о вещественных корнях уравнения). На первом этапе производится отделение корней - поиск интервалов, в которых содержится только по одному корню. Второй этап решения связан с уточнением корня в выбранном интервале (определением значения корня с заданной точностью).

1.1. Отделение корней

В общем случае отделение корней уравнения f(x)=0 базируется на известной теореме, утверждающей, что если непрерывная функция f(x) на концах отрезка имеет значения разных знаков, т.е. f(a)ґ f(b)Ј 0 , то в указан-ном промежутке содержится хотя бы один корень. Например, для уравнения f(x)= x 3 -6x+2=0 видим, что при x®Ґ f(x)>0 , при x®-Ґ f(x) , что уже свидетельствует о наличии хотя бы одного корня.

В общем случае выбирают некоторый диапазон, где могут обнаружиться корни, и осуществляют "прогулку" по этому диапазону с выбранным шагом h для обнаружения перемены знаков f(x) , т.е. f(x)ґ f(x+h) .

При последующем уточнении корня на обнаруженном интервале не надейтесь никогда найти точное значение и добиться обращения функции в нуль при использовании калькулятора или компьютера, где сами числа представлены ограниченным числом знаков. Здесь критерием может служить приемлемая абсолютная или относительная погрешность корня. Если корень близок к нулю, то лишь относительная погрешность даст необходимое число значащих цифр. Если же он весьма велик по абсолютной величине, то критерий абсолютной погрешности часто дает совершенно излишние верные цифры. Для функций, быстро изменяющихся в окрестности корня, может быть привлечен и критерий: абсолютная величина значения функции не превышает заданной допустимой погрешности.

1.2. Уточнение корней методом половинного деления (дихотомии)

Самым простейшим из методов уточнения корней является метод половинного деления, или метод дихотомии, предназначенный для нахождения корней уравнений, представленных в виде f(x)=0 .

Пусть непрерывная функция f(x) на концах отрезка имеет значения разных знаков, т.е. f(a)ґ f(b) Ј 0 (), тогда на отрезке имеется хотя бы один корень.

Возьмем середину отрезка с=(a+b)/2 . Если f(a)ґ f(c) Ј 0 , то корень явно принадлежит отрезку от a до (a+b)/2 и в противном случае от (a+b)/2 до b .

Поэтому берем подходящий из этих отрезков, вычисляем значение функции в его середине и т.д. до тех пор, пока длина очередного отрезка не окажется меньше заданной предельной абсолютной погрешности (b-a)e .

Так как каждое очередное вычисление середины отрезка c и значения функции f(c) сужает интервал поиска вдвое, то при исходном отрезке и предельной погрешности e количество вычислений n определяется условием (b-a)/2 n e , или n~log 2 ((b-a)/e ) . Например, при исходном единичном интервале и точности порядка 6 знаков (e ~ 10 -6 ) после десятичной точки достаточно провести 20 вычислений (итераций) значений функции.

С точки зрения машинной реализации () этот метод наиболее прост и используется во многих стандартных программных средствах, хотя существуют и другие более эффективные по затратам времени методы.

1.3. Уточнение корней методом хорд

В отличие от метода дихотомии, обращающего внимание лишь на знаки значений функции, но не на сами значения, метод хорд использует пропорциональное деление интервала ().

Здесь вычисляются значения функции на концах отрезка, и строится "хорда", соединяющая точки (a,f(a)) и (b,f(b)) . Точка пересечения ее с осью абсцисс

принимается за очередное приближение к корню. Анализируя знак f(z) в сопоставлении со знаком f(x) на концах отрезка, сужаем интервал до [a,z ] или [z,b ] и продолжаем процесс построения хорд до тех пор, пока разница между очередными приближениями не окажется достаточно малой (в пределах допустимой погрешности) |Z n -Z n-1 |e .

Можно доказать, что истинная погрешность найденного приближения:

Где X * - корень уравнения, Z n и Z n+1 - очередные приближения, m и M - наименьшее и наибольшее значения f(x) на интервале [a,b ].

1.4. Уточнение корней методом касательных (Ньютона)

Обширную группу методов уточнения корня представляют итерационные методы - методы последовательных приближений. Здесь в отличие от метода дихотомии задается не начальный интервал местонахождения корня, а его начальное приближение.

Наиболее популярным из итерационных методов является метод Ньютона (метод касательных) .

Пусть известно некоторое приближенное значение Z n корня X * . Применяя формулу Тейлора и ограничиваясь в ней двумя членами, имеем

откуда

.

Геометрически этот метод предлагает построить касательную к кривой y=f(x) в выбранной точке x=Z n , найти точку пересечения её с осью абсцисс и принять эту точку за очередное приближение к корню ().

Очевидно, что этот метод обеспечивает сходящийся процесс приближений лишь при выполнении некоторых условий (например при непрерывности и знакопостоянстве первой и второй производной функции в окрестности корня) и при их нарушении либо дает расходящийся процесс (), либо приводит к другому корню ().

Очевидно, что для функций, производная от которых в окрестности корня близка к нулю, использовать метод Ньютона едва ли разумно.

Если производная функции мало изменяется в окрестности корня, то можно использовать видоизменение метода

.

Существуют и другие модификации метода Ньютона.

1.5. Уточнение корней методом простой итерации

Другим представителем итерационных методов является метод простой итерации .

Здесь уравнение f(x)=0 заменяется равносильным уравнением x=j (x) и строится последовательность значений

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ

АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ»

Кафедра прикладной математики и вычислительной техники

Excel и Mathcad

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению лабораторных работ

по дисциплине «Вычислительная математика»

Решение нелинейных уравнений в Excel и Mathcad : Метод. указ. / Сост. , - Самара: СГАСУ, 20с.

Методические указания разработаны в соответствии с Государственным образовательным стандартом изучения дисциплины «Вычислительная математика».

Рассмотрена реализация численных методов при решении нелинейных уравнений и систем уравнений в Excel и MathCad. Приведены варианты заданий для индивидуального выполнения и вопросы для самоконтроля и тестирования.

Предназначены для студентов специальности 230201 – «Информационные системы и технологии» всех форм обучения.

Рецензент к. ф-м. н.

Ó , составление, 2012

ã СГАСУ, 2012

1 Решение нелинейного уравнения

1.1 Общие сведения о решении нелинейного уравнения

Как правило, нелинейное уравнения общего вида f(х)=0 невозможно решить аналитически. Для практических задач достаточно найти приближенное значение x , в определенном смысле близкое к точному решению уравнения хточн .

В большинстве случаев поиск приближенного решения включает два этапа. На первом этапе отделяют корни, т. е. находят такие отрезки, внутри которых находится строго один корень. На втором этапе уточняют корень на одном из таких отрезков, т. е. находят его значение с требуемой точностью.

Достигнутая точность может оцениваться либо «по функции» (в найденной точке x , функция достаточно близка к 0, т. е. выполняется условие |f(x)|≤ e f , где e f требуемая точность по оси ординат), либо «по аргументу» (найден достаточно маленький отрезок [ a, b] , внутри которого находится корень, т. е. | b– a|≤ e x , где e x требуемая точность по оси абсцисс).

1.2 Отделение корней

Отделение корней может производиться сочетанием графического и аналитического исследования функции. Такое исследование опирается на теорему Вейерштрасса, в соответствии с которой для непрерывной на отрезке [ a, b] функции f(х ) и любого числа y , отвечающего условию f(a)≤y≤ f(b) , существует на этом отрезке точка x , в которой функция равна y . Следовательно, для непрерывной функции достаточно найти отрезок, на концах которого функция имеет разные знаки, и можно быть уверенным, что на этом отрезке есть корень уравнения f(х)=0 .

Для ряда методов уточнения желательно, чтобы найденный на первом этапе отрезок содержал только один корень уравнения. Это условие выполняется, если функция на отрезке монотонна. Монотонность, можно проверить либо по графику функции, либо по знаку производной.

Пример Найти с точностью до целых все корни нелинейного уравнения y(x)= x3 ‑ 10 x + 7=0 а) построив таблицу и б) построив график. Найти корень уравнения на выделенном отрезке, используя опции «Подбор параметра» и «Поиск решения».

Решение Создадим в Excel таблицу, содержащую аргументы и значения функции и по ней построим точечную диаграмму . На рисунке 1 приведен снимок решения.

На графике видно, что уравнение имеет три корня, принадлежащие отрезкам [-4, -3], и . Эти отрезки можно выявить и наблюдая за сменой знаков функции в таблице. По построенному графику можно сделать вывод, что на указанных отрезках функция f (x ) монотонна и, следовательно, на каждом из них содержится только по одному корню.

Такой же анализ может быть выполнен и в пакете Mathcad. Для этого достаточно набрать определение функции f (x ) , используя оператор присваивания (:=) и естественные общепринятые обозначения математических операций и стандартных функций, задать цикл для изменения аргумента, например, а затем вывести на экран таблицу значений функции (располо­жен­ными в одной строке командами x = f (x )= ) и график. Цикл можно задать, например, командой x :=-5,-4.5…5 . Шаг цикла формируется путем задания начального и следующего за ним значений переменной, а перед конечным значением переменной ставится точка с запятой, которая будет визуально отображена на экране в виде многоточия.

https://pandia.ru/text/78/157/images/image002_56.jpg" width="640" height="334">

Рисунок 1 – Таблица и график для отделения корней нелинейного уравнения

1.3 Уточнение корней стандартными средствами Excel и Mathcad

Во всех методах уточнения корней необходимо задать начальное прибли­же­ние, которое затем и будет уточняться. Если уравнение имеет несколько кор­ней, в зависимости от выбранного начального приближения будет найден один из них. При неудачно выбранном начальном приближении решение может и не быть найдено. Если в результате первого этапа расчетов уже выделен отрезок, содержа­щий единственный корень уравнения, в качестве начального приближения можно взять любую точку этого отрезка.

В Excel для уточнения значений корней можно использовать опции «Подбор параметра» и «Поиск решения». Пример оформления решения приведен на рисунках 2 и 3.

https://pandia.ru/text/78/157/images/image004_31.jpg" width="501" height="175 src=">

Рисунок 3 – Результаты использования средств решения уравнения в Excel

В Mathcad для уточнения корней уравнения можно использовать функцию root (….) или блок решения . Пример использования функции root(…) приведен на рисунке 4, а блока решения на рисунке 5. Следует обратить внимание, что в блоке решения (после заголовка блока Given ) между левой и правой частями уравнения должен стоять жирный знак равенства (тождества), который можно получить выбором из соответствующей палитры инструментов, либо нажатием одновременно клавиши Ctrl и = .

243" height="31">

Рисунок 5 – Решение уравнения с использованием блока решения в Mathcad

Как видим, каждый стандартный инструмент находит решение уравнения с определенной точностью. Эта точность зависит от метода, используемого в пакете и, в определенной степени, настроек пакета. Управлять точностью результата здесь достаточно сложно, а часто и невозможно.

В то же время, очень просто построить собственную таблицу или написать программу, реализующие один из методов уточнения корней. Здесь можно использовать критерии точности расчета, задаваемые пользователем. При этом достигается и понимание процесса расчетов без опоры на принцип Митрофанушки: «Извозчик есть, довезет».

Далее рассмотрены несколько наиболее распространенных методов. Отметим очевидный момент: при прочих равных условиях тот метод уточнения корней будет более эффективен, в котором результат с той же погрешностью найден с меньшим числом вычислений функции f(x) (при этом достигается и максимальная точность при одинаковом числе вычислений функции).

1.4 Метод деления отрезка пополам

В этом методе на каждом шаге отрезок делится на две равные части. Затем сравнивают знаки функции на концах каждой из двух половинок (например, по знаку произведения значений функций на концах), определяют ту из них, в которой содержится решение (знаки функции на концах должны быть разные), и. сужают отрезок, перенося в найденную точку его границу (а или b ). Условием окончания служит малость отрезка, где содержится корень («точность по x »), либо близость к 0 значения функции в средине отрезка («точность по y»). Решением уравнения считают середину отрезка, найденного на последнем шаге.

Пример . Построить таблицу для уточнения корня уравнения x 3 –10 x +7=0 на отрезке [-4, -3] методом деления отрезка пополам. Определить сколько шагов надо сделать методом деления отрезка пополам и какая при этом достигается точность по х, для достижения точности по y , равной 0,1; 0,01; 0, 001.

Решение Для решения можно использовать табличный процессор Excel, позволяющий автоматически продолжать строки. На первом шаге заносим в таблицу значения левого и правого концов выбранного начального отрезка и вычисляем значение середины отрезка с =(a +b )/2, а затем вводим формулу для вычисления функции в точке a (f (a )) и растягиваем (копируем) её для вычисления f (c ) и f (b ). В последнем столбца вычисляем выражение (b -a )/2, характеризующего степень точности вычислений. Все набранные формулы можно скопировать во вторую строку таблицы.

На втором шаге нужно автоматизировать процесс поиска той половины отрезка, где содержится корень. Для этого испльзуется логическая функция ЕСЛИ (Меню : ВставкаФункцияЛогические). Для нового левого края отрезка мы проверяем истинность условия f (a )*f (c )>0, если оно верно, то мы в качестве нового значения левого конца отрезка берем число c a , c a . Аналогично, для нового правого края отрезка мы проверяем истинность условия f (c )* f (b )>0, если оно верно, то мы в качестве нового значения правого конца отрезка берем число c (т. к. это условие показывает, что корня на отрезке [c , b ] нет), иначе оставляем значение b .

Вторую строку таблицы можно продолжить (скопировать) на необходимое число последующих строк.

Итерационный процесс завершается, когда очередное значение в последнем столбце становится меньшим, чем заданный показатель точности ex. При этом, значение середины отрезка в последнем приближении, принимается в качестве приближенного значения искомого корня нелинейного уравнения. На рисунке 6 приведен снимок решения. Для построения аналогичного процесса в Mathcad можно использовать бланк, подобный приведенному на рисунке 7. Число шагов N может варьиро­вать­ся до достижения в таблице результатов требуемой точности. При этом таблица будет автоматически удлиняться или укорачиваться.

Итак, одним из трех корней нелинейного уравнения x 3 – 10x + 7=0, найденным с точностью e=0,0001, является x = - 3,46686. Как мы видим, он действительно принадлежит отрезку [-4; -3].

https://pandia.ru/text/78/157/images/image018_6.jpg" width="563" height="552 src=">

Рисунок 7 – Уточнение корня методом деления отрезка пополам в Mathcad

1.5 Метод хорд

В этом методе нелинейная функция f(x) на отделенном интервале [а, b ] заменяется линейной – уравнением хорды, т. е. прямой соединяющей граничные точки графика на отрезке. Условие применимости метода – монотонность функции на начальном отрезке, обеспечивающая единственность корня на этом отрезке. Расчет по методу хорд аналогичен расчету методом деления отрезка пополам, но теперь на каждом шаге новая точка x внутри отрезка [a , b ] рассчитывается по любой из следующих формул:

(х) > 0 ), или правая его граница: x0 = b (если f(b) f"(х)>0 ). Расчет нового приближения на следующем шаге i +1 производится по формуле:

https://pandia.ru/text/78/157/images/image021_4.jpg" width="596" height="265 src=">

Рисунок 8 – Уточнение корня методом касательных в E xcel

Расчеты в Mathcad выполняются аналогично. При этом значительное облегчение доставляет наличие в этом пакете оператора, автоматически вычисляющего производную функции.

Наиболее трудоемким элементом расчетов по методу Ньютона является вычисление производной на каждом шаге.

При определенных условиях может использоваться упрощенный метод Ньютона , в котором производная вычисляется только один раз – в начальной точке. При этом используется видоизмененная формула

.

Естественно, что упрощенный метод, как правило, требует большего числа шагов.

Если вычисление производной связано с серьезными трудностями (например, если функция задана не аналитическим выражением, а вычисляющей ее значения программой) используется модифицированный метод Ньютона, получивший название – метод секущих . Здесь производная приближенно вычисляется по значениям функции в двух последовательных точках, то есть используется формула

.

В методе секущих необходимо задаться не одной, а двумя начальными точками – x 0 и x 1 . Точка x1 обычно задается сдвигом x0 к другой границе отрезка на малую величину, например, на 0.01.

1.7 Комбинированный метод

Можно показать, что если на начальном отрезке у функции f(x) сохраняются неизменными знаки первой и второй производных, то методы хорд и Ньютона приближаются к корню с разных. В комбинированном методе для повышения эффективности на каждом шаге использует оба алгоритма одновременно. При этом интервал, где содержится корень, сокращается с обеих сторон, что обусловливает другое условие окончания поиска. Поиск можно прекратить, как только в середине интервала, полученного на очередном шаге значение функции станет по модулю меньшим, чем предварительно заданной погрешности e f .

Если, в соответствии со сформулированным выше правилом, метод Ньютона применяется к правой границе отрезка, для вычислений используются формулы:

https://pandia.ru/text/78/157/images/image025_10.gif" width="107" height="45 src=">.

Если метод Ньютона применяется к левой границе, – в предыдущих формулах меняются местами обозначения a и b .

1.8 Метод итераций

Для применения этого метода исходное уравнение f(x)=0 преобразуют к виду: x =y (х) . Затем выбирают начальное значение х0 и подставляют его в левую часть уравнения, получая, в общем случае, x 1 = y (х0) ¹ х0 ¹ y (х1) , поскольку х0 взято произвольно и не является корнем уравнения. Полученное значение х1 рассматривают как очередное приближение к корню. Его снова подставляют в правую часть уравнения и получают следующее значение х2= y (х1) ). Расчет продолжают по формуле хi+1= y (хi) . Получающаяся таким образом последовательность: х0, х1, х2, х3 х4,... при определенных условиях сходиться к корню хточн .

Можно показать, что итерационный процесс сходится при условии
|y ’ (x ) | < 1 на [a , b ].

Существуют различные способы преоб­ра­зо­вания уравнения f(x) = 0 к виду y (х) = х , причем в конкретном случае одни из них приведут к сходящемуся, а другие – к расходящемуся процессу вычислений.

Один из способов, заключается в применении формулы

https://pandia.ru/text/78/157/images/image027_10.gif" width="188" height="44 src=">

где М = max |y ’ (x )| на [a , b ].

Систему n нелинейных уравнений с n неизвестными x1, x2 , ..., xn записывают в виде:

где F1, F2 ,…, Fn – функции независимых переменных, среди которых есть нелинейные.

Как и в случае систем линейных уравнений, решением системы является такой вектор X *, который при подстановке обращает одновременно все уравнения системы в тождества.

https://pandia.ru/text/78/157/images/image030_8.gif" width="191" height="56">

Начальные значения x 0 и y 0 определяются графически. Для нахождения каждого последующего приближения (xi +1 , yi +1 ) используют вектор значений функций и матрицу значений их первых производных, рассчитанные в предыдущей точке (xi , yi ) .

https://pandia.ru/text/78/157/images/image032_5.gif" width="276" height="63 src=">

Для расчета новых приближений на шаге i+1 используется матричная формула

https://pandia.ru/text/78/157/images/image034_4.gif" width="303" height="59 src=">.

Приведенные формулы особенно легко записать в Mathcad, где имеются операторы для вычисления производных и действий с матрицами. Однако при правильном использовании матричных операций эти формулы достаточно просто записываются и в Excel. Правда, здесь придется заранее получить формулы для вычисления производных. Для аналитического вычисления производных также может быть использован Mathcad.

2.3 Решение систем нелинейных уравнений методами итераций

Для реализации этих методов исходную систему уравнений необходимо путем алгебраических преобразований явно выразить каждую переменную через остальные. Для случая двух уравнений с двумя неизвестными новая система будет иметь вид

https://pandia.ru/text/78/157/images/image036_5.gif" width="114" height="57 src=">.

Если одно из решений системы и начальные значения x 0 и y 0 лежат в области D , задаваемой неравенствами: a ≤ x ≤ b , c ≤ y ≤ d , то расчет по методу простых итераций сходится при выполнении в области D соотношений:

https://pandia.ru/text/78/157/images/image038_5.gif" width="75 height=48" height="48">< 1.

В методе итераций Зейделя для каждого расчета используют уже найденные наиболее точные значения каждой переменной. Для рассматриваемого случая двух переменных такая логика приводит к формулам

0 " style="border-collapse:collapse;border:none">

Инструмент (опция)

Начальное приближение

Корень x

f(x)

3.Отсортировать полученные результаты по точности решения.

Мучаясь в школе над решением уравнений на уроках математики, многие ученики часто уверены, что тратят время абсолютно впустую, а между тем такой навык пригодится в жизни не только тем, кто решит пойти по стопам Декарта, Эйлера или Лобачевского.

На практике, например в медицине или экономике, сплошь и рядом встречаются ситуации, когда специалисту требуется выяснить, когда концентрация активного вещества того или иного препарата достигнет требуемого уровня в крови пациента или нужно высчитать время, необходимое конкретному бизнесу для того, чтобы он стал рентабельным.

Чаще всего речь идет о решении нелинейных уравнений различного типа. Сделать это максимально быстро, особенно с использованием ЭВМ, позволяют численные методы. Они хорошо изучены и давно доказали свою эффективность. К их числу относится и метод касательных Ньютона, которым посвящена эта статья.

Постановка задачи

В данном случае имеется функция g, которая задана на отрезке (a, b) и принимает на нем определенные значения, т. е. каждому x, принадлежащему (a, b) возможно сопоставить конкретное число g(x).

Требуется установить все корни уравнения из промежутка между точками a и b (включая концы), для которых функция обнуляется. Очевидно, что это будут точки пересечения y = g(x) с ОХ.

В некоторых случаях удобнее заменить g(x)=0 на аналогичное, вида g 1 (x) = g 2 (x). В таком случае в качестве корней выступают абсциссы (значение x) точек пересечения графиков g 1 (x) и g 2 (x).

Решение нелинейного уравнения важно и для задач оптимизации, для которых условие локального экстремума - обращение в 0 производной функции. Иными словами, такая задача может свестись к поиску корней уравнения p(x) = 0, где p(x) тождественна g"(x).

Методы решения

Для некоторых видов нелинейных уравнений, например квадратных или простых тригонометрических, найти корни можно достаточно простыми способами. В частности, каждый школьник знает формулы, используя которые можно без проблем находить значения аргумента точек, где обнуляется квадратный трехчлен.

Способы извлечения корней нелинейных уравнений принято делить на аналитические (прямые) и итерационные. В первом случае искомое решение имеет вид формулы, используя которую за некоторое число арифметических операций можно найти значение искомых корней. Подобные методы разработаны для показательных, тригонометрических, логарифмических и простейших алгебраических уравнений. Для остальных же приходится использовать специальные численные методы. Их легко реализовать с помощью ЭВМ, которые позволяют найти корни с требуемой точностью.

К их числу относится и так называемый численный метод касательных.Последний был предложен великим ученым Исааком Ньютоном в конце XVII века. В последующие столетия метод неоднократно совершенствовался.

Локализация

Численные способы решения сложных уравнений, не имеющих аналитических решений, принято осуществлять в 2 этапа. Сначала требуется их локализировать. Эта операция заключается в нахождение таких отрезков на ОХ, на которых существует один корень решаемого уравнения.

Рассмотрим отрезок . Если g(x) на нем не имеет разрывов и принимает в концевых точках значения разных знаков, то между a и b или в них самих расположен по крайней мере 1 корень уравнения g(x) = 0. Чтобы он был единственным, требуется, чтобы g(x) на была монотонной. Как известно, таким свойством она будет обладать при условии знакопостоянства g’(x).

Говоря иначе, если на g(x) не имеет разрывов и монотонно растет или убывает, а ее значения в концевых точках имеют не одинаковые знаки, то на существует 1 и только 1 корень g(x).

При этом следует знать, что этот критерий не будет действовать для корней уравнений, являющихся кратными.

Решение уравнения делением пополам

Прежде чем рассматривать более сложные численные касательныхи его разновидности) стоит познакомиться с наиболее простым способом выявления корней. Он называется дихотомией и относится к интуитивным нахождения корней основан на теореме о том, что если для g(x), непрерывной на выполняется условие разнознаковости, то на рассматриваемом отрезке есть хотя бы 1 корень g(x) = 0.

Для его обнаружения нужно поделить отрезок пополам и обозначить среднюю точку как x 2 . Тогда возможны два варианта: g(x 0) * g(x 2) либо g(x 2) * g(x 1) равны или меньше 0. Выбираем тот, для которого верно одно из этих неравенств. Повторяем процедуру, описанную выше, пока длина не станет меньше некой, заранее выбранной величины, определяющей точность определения корня уравнения на .

К достоинствам метода относится его надежность и простота, а недостаток — необходимость изначально выявить точки, в которых g(x) принимает разные знаки, поэтому его нельзя применять для корней, обладающих четной кратностью. Кроме того, он не обобщается на случай системы уравнений или если речь идет о комплексных корнях.

Пример 1

Пусть мы хотим решить уравнение g(x) = 2x 5 + x - 1 = 0. Чтобы долго не искать подходящий отрезок, строим график, используя, например, известную программу "Эксель". Мы видим, что в качестве отрезка для локализации корня лучше брать значения из промежутка . Мы можем быть уверены, что хотя бы один корень искомого уравнения на нем есть.

g"(x) = 10x 4 + 1, т. е. это монотонно возрастающая функция, поэтому на выбранном отрезке есть только 1 корень.

Подставляем концевые точки в уравнение. Имеем 0 и 1 соответственно. На первом шаге за решение берем точку 0,5. Тогда g(0,5) = -0,4375. Значит,следующий отрезок для деления пополам будет . Его серединная точка - 0,75. В ней значение функции равно 0,226. Берем для рассмотрения отрезок и его середину, которая находится в точке 0,625. Вычисляем значение g(x) в 0,625. Оно равно -0,11, т. е. отрицательное. Опираясь на этот результат, выбираем отрезок . Получаем x = 0,6875. Тогда g(x) = -0,00532. Если точность решения 0,01, то можем считать, что искомый результат равен 0,6875.

Теоретическая база

Этот способ нахождения корней методом касательных Ньютона пользуется популярностью из-за его очень быстрой сходимости.

Он основан на том доказанном факте, что если x n — приближение к корню f(x)=0, таком, что f" C 1 , то следующая апроксимация будет в точке, где обнуляется уравнение касательной к f(x), т. е.

Подставляем x = x n+1 и обнуляем y.

Тогда касательных выглядит так:

Пример 2

Попробуем использовать классический метод касательных Ньютона и найти решение какого-либо нелинейного уравнения, которое сложно или невозможно отыскать аналитически.

Пусть требуется выявить корни для x 3 + 4x - 3 = 0 с некоторой точностью, например 0,001. Как известно, график любой функции в виде многочлена нечетной степени должен хотя бы раз пересекать ось ОХ, т. е. сомневаться в существовании корней не приходится.

Прежде чем решить наш пример методом касательных, строим графикf(x) = x 3 + 4x - 3 поточечно. Это очень легко сделать, например, используя табличный процессор "Эксель". Из полученного графика будет видно, что на происходит его пересечение с осью ОХ и функция y = x 3 + 4x - 3 монотонно возрастает. Мы можем быть уверены, что на уравнения x 3 + 4x - 3 = 0 имеет решение и оно единственное.

Алгоритм

Любое решение уравнений методом касательных начинается с вычисления f "(x). Имеем:

Тогда вторая производная будет иметь вид x * 6.

Используя эти выражения, можем записать формулу для выявления корней уравнения по методу касательных в виде:

Далее требуется выбрать начальное приближение, т. е. заняться определением, какую точку считать стартовой (об. x 0) для итерационного процесса. Рассматриваем концы отрезка . Нам подойдет тот, для которого верно условие разнознаковости функции и ее 2-ой производной в x 0 . Как видим, при подстановке x 0 = 0 оно нарушено, а вот x 0 = 1 вполне подходит.

то если нас интересует решение методом касательных с точностью e, то значение x n можно считать удовлетворяющим требованиям задачи, при условии выполнения неравенства|f(x n) / f’(x n)|< e.

На первом шаге касательных имеем:

• x 1 = x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) = 1- 0,2857 = 0,71429;
• так как условие не выполняется, идем далее;
• получаем новое значение для x 2 , которое равно 0,674;
• замечаем, что отношение значения функции к ее производной в x 2 меньше 0,0063, прекращаем процесс.

Метод касательных в Excel

Решить предыдущий пример можно намного легче и быстрее, если не производить расчеты вручную (на калькуляторе), а использовать возможности табличного процессора от компании "Майкрософт".

Для этого в "Эксель" нужно создать новую страницу и заполнить ее ячейки следующими формулами:

• в C7 записываем «= СТЕПЕНЬ (B7;3) + 4 * B7 - 3»;
• в D7 вписываем «= 4 + 3 * СТЕПЕНЬ (B7;2)»;
• в E7 записываем «= (СТЕПЕНЬ (B7;3)- 3 + 4 * B7) / (3* СТЕПЕНЬ (B7;2) + 4)»;
• в D7 вписываем выражение «=В7 - Е7»;
• в B8 вписываем формулу-условие «= ЕСЛИ(Е7 < 0,001;"Завершение итераций"; D7)».

В конкретной задаче уже в ячейке B10 появится надпись «Завершение итераций», и за решение задачи нужно будет взять число, записанное в ячейке, расположенной на одну строку выше. Для него можно выделить и отдельный «растягиваемый» столбец, введя там формулу-условие, согласно которой там будет записан результат, если содержимое в той или иной ячейке столбца B примет вид «Завершение итераций».

Реализация в Pascal

Попробуем получить решение нелинейного уравнения y = х 4 - 4 - 2 * х методом касательных в Паскале.

Используем вспомогательную функцию, которая поможет осуществить приближенное вычисление f"(x) = (f(x + delta) - f(x)) / delta. В качестве условия для завершения итерационного процесса выберем выполнение неравенства|x 0 -x 1 |< некого малого числа. В Паскале его запишем, как abs(x0 - x1)<= epsilon.

Программа примечательна тем, что не требует ручного вычисления производной.

Метод хорд

Рассмотрим еще один способ выявления корней нелинейных уравнений. Процесс итераций заключается в том, что в качестве последовательных приближений к искомому корню для f(x)=0 принимают значения точек пересечения хорды с абсциссами концевых точек a и b с ОХ, обозначаемые, как х 1 , ..., х n . Имеем:

Для точки, где хорда пересекается с осью ОХ выражение запишется, как:

Пусть вторая производная положительная при х £ (противоположный случай сведется к рассматриваемому, если записать- f(x) = 0). В таком случае график у = f(x) - кривая, выпуклая внизу и расположенная ниже хорды AB . Могут иметь место 2 случая: когда функция имеет положительное значение в точке a или она отрицательное в точке b.

В первом случае в качестве неподвижного выбираем конец a, а за x 0 берем точку b. Тогда последовательные приближения по формуле, представленной выше, образуют последовательность, которая монотонно убывает.

Во втором случае неподвижным является конец b при x 0 = a. Значения х, полученные на каждом шаге итерации, образуют последовательность, которая монотонно возрастает.

Таким образом, можем констатировать, что:

• неподвижным в методе хорд является тот конец отрезка, где не совпадают знаки функции и ее второй производной;
• приближения для корня x — x m — лежат от него в той стороне, где у f(х) знак, не совпадающий со знаком f"" (х).

Итерации можно продолжать, пока не выполнится условия близости корней на этом и предыдущем итерационном шаге по модулю abs(x m - x m - 1)< e.

Модифицированный способ

Комбинированный метод хорд и касательныхпозволяет устанавливать корни уравнения, приближаясь к ним с разных сторон. Такое значение, при котором график f(x) пересекает OX, позволяет уточнить решение гораздо быстрее, чем по каждому из методов по отдельности.

Предположим, нужно отыскать корни f(x)=0, если они есть на . Можно применить любой из описанных выше способов. Однако лучше попробовать их комбинацию, благодаря чему значительно повысится точность корня.

Рассматриваем случай с начальным приближением, соответствующим условию разнознаковости первой и второй производной в конкретной точке х.

В таких условиях решение нелинейных уравнений методом касательных позволяет найти корень с избытком, если x 0 =b, а способ с использованием хорд при неподвижном конце b приводит к нахождению приближенного корня с недостатком.

Используются формулы:

Теперь искомый корень х нужно искать в интервале. На следующем шаге нужно применить комбинированный метод уже к этому отрезку. Действуя так далее, получим формулы вида:

Если же имеет место разнознаковость первой и второй производных, то, рассуждая аналогичным образом, для уточнения корня получим следующие рекурентные формулы:

В качестве условия используется оценочное неравенство| b n +1 - a n +1 |< e. Иными словами, на практике приходится находить решение при помощи двух методов, но на каждом шаге требуется выяснять, насколько полученные результаты близки друг другу.

Если вышеприведенное неравенство верно, то в качестве корня нелинейного уравнения на заданном отрезке берут точку, которая находится ровно посередине между найденными решениями на конкретном итерационном шаге.

Комбинированный метод легко реализуется в среде TURBO PASCAL. При большом желании можно попробовать осуществить все вычисления табличным методом в программе "Эксель".

В последнем случае выделяют по нескольку столбцов для решения задачи с использованием хорд и отдельно для способа, предложенного Исааком Ньютоном.

При этом каждая строка используется для записи вычислений на конкретном итерационном шаге по двум методам. Затем, в левой части от области решения, на активной рабочей странице выделяется столбец, в котором вписывается результат вычислений модуля разности значений очередного итерационного шага по каждому из методов. Еще один можно использовать для внесения результатов вычислений по формуле расчета логической конструкции «ЕСЛИ», используемой для выяснения, выполняется ли условие или нет.

Теперь вы знаете, как решать сложные уравнения. Метод касательных,как вы уже видели, реализуется достаточно просто, как в Паскале, так и в "Экселе". Поэтому вы всегда сможете установить корни уравнения, которое сложно или невозможно решить посредством формул.

Пусть найдено приближенное значение корня уравнения f (x ) = 0, обозначим его x n . Расчетная формула метода Ньютона для определения очередного приближения x n +1 может быть получена двумя способами.

Первый способ выражает геометрический смысл метода Ньютона и состоит в том, что вместо точки пересечения графика функции y = f (x ) с осью OX , мы ищем точку пересечения с осью OX касательной, проведенной к графику функции в точке (x n , f (x n )) как показано на рис. 2.6. Уравнение касательной имеет вид .

Рис. 2.7. Метод Ньютона (касательных)

В точке пересечения касательной с осью OX переменная y = 0. Приравнивая y нулю, выразим x и получим формулу метода касательных :

(2.6)

Второй способ. Разложим функцию f (x ) в ряд Тейлора в окрестности точки x = x n :

Ограничимся линейными относительно (x – x n ) слагаемыми, приравняем нулю f (x ) и, выразив из полученного уравнения неизвестное x и обозначив его через x n +1 , мы получим формулу (2.6).

Приведем достаточные условия сходимости метода Ньютона.

Теорема 2.3. Пусть на отрезке выполняются условия:

1) функция и ее производные и непрерывны;

2) производные и отличны от нуля и сохраняют определенные постоянные знаки;

3) (функция меняет знак на отрезке).

Тогда существует отрезок , содержащий искомый корень уравнения , на котором итерационная последовательность схо­дит­­ся. Если в качестве нулевого приближения выбрать ту граничную точку , в которой знак функции совпадает со знаком второй производной, т.е. , то итерационная последовательность сходится монотонно (рис.2.8).

Доказательство . Так как непрерывна, меняет знак и монотонна на , то - интервал изоляции корня. Обозначим искомый корень через . Рас­смотрим функцию и найдем ее производную . Итак, непрерывна на , обращается в нуль в точке , так как в этой точке обращается в нуль функция . Следовательно, существует такой отре­зок (), что . Если возьмем ту часть отрезка, где , то , следовательно, функция возрастающая, но тогда последовательность является монотонной.

Рис. 2.8. Достаточные условия сходимости метода Ньютона

Замечание. Отметим, что метод хорд как раз идет с противоположной стороны, и оба этих метода т.о. могут друг друга дополнять, а возможен и комбинированный метод хорд-касательных .

Пример 2.7. Уточнить до 0,000001 методом Ньютона корень уравнения
sin 5x + x 2 – 1 = 0. За начальное значение принять x 0 = – 0,7.

Решение. Найдем производную .

В программе Excel введем расчетные формулы:

1) Введем формулы и обозначения в ячейках диапазона A 1:D 3 и скопируем вниз маркером заполнения ячейки с формулами: B 3 - до B 5,
C 2 - до C 5, D 2 - до D 5;

Таблица 2.9

Результаты расчетов приведены в таблице 2.10. Получено значение корня – 0,726631609 ≈ – 0,726632 с погрешностью 0,000001.

Таблица 2.10

Создадим функции в программе Excel для решения уравнения из примера 2.7 методом Ньютона.