Локализация корней при решении нелинейных уравнений

1 Численный метод решения нелинейных уравнений

1.1 Область локализации корней

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

Например , для уравнения выполним преобразование и приведем его к виду f(x)= 0 т.е. . График этой функции представлен на рисунке 1. Очевидно, что данное уравнение имеет два действительных корня – один на отрезке [-1, 0] , а второй – [1, 2].

Рисунок 1. График функции

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

Некоторые виды уравнений допускают аналитическое решение. Например, степенные алгебраические уравнения степени n при n ≤ 4. Однако, в общем виде, аналитическое решение, как правило, отсутствует. В этом случае, применяются численные методы. Все численные методы решения уравнений представляют собой итерационные алгоритмы последовательного приближения к корню уравнения. То есть, выбирается начальное приближение к корню x ₀ и затем с помощью итерационной формулы генерируется последовательность x ₁, x ₂, …, x_k сходящаяся к корню уравнения .

1.2 Критерии сходимости при решении уравнений

Ø Абсолютная погрешность — абсолютное изменение приближения на соседних шагах итерации

Ø Относительная погрешность — относительное изменение приближения на соседних шагах итерации

Ø Близость к нулю вычисленного значения левой части уравнения (иногда это значение называют невязкой уравнения, так как для корня невязка равна нулю)

1.3 Метод половинного деления (метод дихотомии)

Метод половинного деления основан на последовательном делении отрезка локализации корня пополам.

Для этого выбирается начальное приближение к отрезку [ a , b ], такое, что f ( a ) × f ( b ) — середине отрезка [ a , b ]. Если он противоположен знаку функции в точке a, то корень локализован на отрезке [ a , c ], если же нет – то на отрезке [ c , b ]. Схема метода дихотомии приведен на рис у нке 2.

Рисунок 2. Последовательное деление отрезка пополам и приближение к корню

Алгоритм метода дихотомии можно записать так:

1. представить решаемое уравнение в виде

2. выбрать a, b и вычислить

3. если f(a) × f( с ) то a=a; b = c иначе a = c; b=b

4. если критерий сходимости не выполнен, то перейти к п. 2

Пример решения уравнения методом дихотомии

Найти решение заданного уравнения методом дихотомии с точностью до 10 -5 .

Пример создания расчетной схемы на основе метода дихотомии на примере уравнения: на отрезке [1, 2]

Данный метод заключается в проверке на каждой итерации условия:

если f ( a ) × f (с) и выбор соответствующего отрезка для следующей итерации.

Рисунок 3. Последовательность итераций метода дихотомии при поиске корня уравнения на отрезке [1, 2]

a ) схема расчета (зависимые ячейки); b) режим отображения формул;

Для нашего примера итерационная последовательность для нахождения решения принимает вид:

Точность до пятой значащей цифры достигается за 20 итераций.

Скорость сходимости этого метода является линейной.

При выполнении начального условия он сходится к решению всегда.

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

2 Решение уравнений , используя “Подбор параметра ”

Используя возможности Excel можно находить корни нелинейного уравнения вида f(x)=0 в допустимой области определения переменной. Последовательность операций нахождения корней следующая:

1. Производится табулирование функции в диапазоне вероятного существования корней;

2. По таблице фиксируются ближайшие приближения к значениям корней;

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

При подборе параметра Excel использует итерационный (циклический) процесс. Количество итераций и точность устанавливаются в меню Сервис/Параметры/вкладка Вычисления. Если Excel выполняет сложную задачу подбора параметра, можно нажать кнопку Пауза в окне диалога Результат подбора параметра и прервать вычисление, а затем нажать кнопку Шаг, чтобы выполнить очередную итерацию и просмотреть результат. При решении задачи в пошаговом режиме появляется кнопка П родолжить — для возврата в обычный режим подбора параметра.

2.1 Пример решения уравнения, используя “Подбор параметра”

Например , найдем все корни уравнения 2x 3 -15sin(x)+0,5x-5=0 на отрезке [-3 ; 3].

Для локализации начальных приближений необходимо определить интервалы значений Х, внутри которых значение функции пересекает ось абсцисс, т.е. функция меняет знак. С этой целью табулируем функцию на отрезке [–3; 3] с шагом 0,2, получим табличные значения функции. Из полученной таблицы находим, что значение функции трижды пересекает ось Х, следовательно, исходное уравнение имеет на заданном отрезке все три корня.

Рисунок 4. Поиск приближенных значений корней уравнения

Выполните команду меню Сервис/Параметры, во вкладке Вычисления установите относительную погрешность вычислений E=0,00001, а число итераций N=1000, установите флажок Итерации.

Выполните команду меню Сервис/Подбор параметра. В диалоговом окне (рисунок 9) заполните следующие поля:

þ Установить в ячейке : в поле указывается адрес ячейки, в которой записана формула правой части функции;

þ Значение : в поле указывается значение, которое должен получить полином в результате вычислений, т.е. правая часть уравнения (в нашем случае 0);

þ Изменяя значение : в поле указывается адрес ячейки (где записано начальное приближение), в которой будет вычисляться корень уравнения и на которую ссылается формула.

Рисунок 5. Диалоговое окно Подбор параметра для поиска первого корня

После щелчка на ОК получим значение первого корня -1,65793685 .

Выполняя последовательно операции аналогичные предыдущим, вычислим значения остальных корней: -0,35913476 и 2,05170101 .

3 Решение уравнений и систем уравнений, используя надстройку “Поиск решения”

Для решения уравнений можно также использовать команду Поиск решения, доступ к которой реализуется через пункт меню Сервис/Поиск решения.

Последовательность операций нахождения корней следующая:

1. Найти приближенное значение корня уравнения

2. Открыть диалог Поиск решения и установить следующие параметры (рисунок 10):

þ в поле У становить целевую ячейку ввести адрес ячейки, содержащей формулу (левую часть уравнения);

þ установить переключатель в положение ‘ значению’ и ввести значение 0 (правая часть уравнения);

þ в поле Изменяя ячейки ввести адреса изменяемых ячеек, т.е. аргумента x целевой функции,;

þ в поле Ограничения с помощью кнопки Д обавить ввести все ограничения, которым должен отвечать результат поиска (область поиска корня уравнения);

þ для запуска процесса поиска решения нажать кнопку В ыполнить.

þ Для сохранения полученного решения необходимо использовать переключатель С охранить найденное решение в открывшемся окне диалога Результаты поиска решения.

Рисунок 6. Диалоговое окно Поиск решения

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

Рассмотрим некоторые Опции, управляющие работой Поиска решения, задаваемые в окне Параметры (окно появляется, если нажать на кнопку Параметры окна Поиск решения):

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

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

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

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

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

Рисунок 7. Вкладка Параметры окна Поиск решения

3.1 Пример решения уравнения, используя надстройку “Поиск решения”

Например , найдем все корни уравнения 2x 3 -15sin(x)+0,5x-5=0 на отрезке [-3 ; 3]. Для локализации начальных приближений необходимо определить интервалы значений Х, внутри которых значение функции пересекает ось абсцисс, т.е. функция меняет знак. С этой целью табулируем функцию на отрезке [–3;3] с шагом 0,2, получим табличные значения функции. Из полученной таблицы находим, что значение функции трижды пересекает ось Х, следовательно, исходное уравнение имеет на заданном отрезке все три корня. На рисунке 12 представлен пример заполнения окна Поиск решения для нахождения первого корня на отрезке [-2; -1].

Рисунок 8. Пример решения уравнения при помощи надстройки Поиск решения

Задание 1. Решение уравнений численным методом

На листе 1 (название листа: Численные методы) для заданного уравнения вида f(x)=0 (Таблица 1. Индивидуальные задания ) реализовать итерационные расчетные схемы методов, указанных в Таблице 1 для нахождения хотя бы одного корня на заданном интервале. Количество итераций просчитать, оценивая , .

Задания 2. Решение уравнений встроенными средствами “Подбор параметра” и “Поиск решения”

На листе 2 (название листа: Подбор Поиск) для заданного уравнения вида f(x)=0 (Таблица 1. Индивидуальные задания) на заданном интервале и с некоторым шагом (шаг выбрать самостоятельно) построить таблицу значений функции f(x) и определить количество корней уравнения и выделить интервалы, на которых находятся корни. Построить график функции. Уточнить на заданных интервалах с точностью до 10 -6 корни уравнения с помощью встроенных средств: Подбор параметра, Поиск решения

Локализация корней нелинейных уравнений. Вычисление корней нелинейных уравнений с заданной точностью

Страницы работы

Фрагмент текста работы

Чувашский Государственный Университет имени И. Н. Ульянова

Кафедра высшей математики

Курсовая работа по теме:

ЛОКАЛИЗАЦИЯ КОРНЕЙ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

ВЫЧИСЛЕНИЕ КОРНЕЙ НЕЛИНЕЙНЫХ УРАВНЕНИЙ С ЗАДАННОЙ ТОЧНОСТЬЮ.

Чебоксары 2012 г.

Задача отыскания корней нелинейных уравнений вида

встречается в различных областях научных исследований.

Все нелинейные уравнения можно разделить на два типа:

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

Как правило, встречающиеся на практике уравнения не удается решить точными методами, когда решение уравнения можно записать в виде конечной формулы. Так методы решения линейных и квадратных уравнений были известны ещё древним грекам. Решение алгебраических уравнений третьей и четвертой степеней было получено итальянскими математиками Ферро, Кардано, Феррари в XV веке. Однако, как доказал в 20-ых годах XIX века норвежский математик Н.Абель, общее уравнение пятой и более высоких степеней неразрешимо в радикалах.

Для трансцендентных уравнений задача поиска корней ещё более осложняется.

Возьмем в качестве модельного очень простое уравнение

Это уравнение имеет единственный корень (x≈0.73), однако получить формулу для его вычисления невозможно.

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

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

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

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

— нахождение корня с достаточной точностью, если известно некоторое начальное его приближение.

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

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

Для отделения корней уравнения (1.2) необходимо иметь критерий, позволяющий убедится, что, во-первых, на рассматриваемом отрезке имеется корень, а, во-вторых, что этот корень единственный на указанном отрезке. Если функция непрерывна на отрезке , а на концах отрезка её значения имеют разные знаки , то на этом отрезке расположен, по крайней мере, один корень. Это условие (как видно из рисунка 2.1) не обеспечивает единственности корня. Достаточным дополнительным условием, обеспечивающем единственность корня на отрезке является требование монотонности функции на этом отрезке. В качестве признака монотонности функции можно воспользоваться условием знакопостоянства первой производной .

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

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

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

(рис2.2) Табличный способ локализации корней уравнения (рис.2.3)Графическое отделение корней sin 2x—lnx

В качестве примера рассмотрим уравнение .Переходя к эквивалентному уравнению построим графики функций и (рис. 2.3)

Из графика видно, что уравнение содержит один корень, расположенный

Нелинейные уравнения и системы уравнений. Методы их решения.

Нелинейные уравнения и системы уравнений. Методы их решения.

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

Под нелинейными уравнениями ( nonlinear equations ) понимаются алгебраические и трансцендентные уравнения с одним неизвестным в следующем виде:

,

где — действительное число, — нелинейная функция.

Под системой нелинейных уравнений понимается система алгебраических и трансцендентных уравнений в следующем виде:

где < > — действительные числа, < … > — нелинейные функции.

Алгебраическое уравнение — это уравнение содержащие только алгебраические функции, которое можно представить многочленом n ‐ ой степени с действительными коэффициентами (целые, рациональные, иррациональные) в следующем виде:

.

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

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

.

Для решения нелинейных уравнений (или систем нелинейных уравнений) существует несколько методов решения: графические, аналитические и численные методы.

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

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

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

— локализация (отделение) корней

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

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

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

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

.

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

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

Локализация корней.

› Локализация корней аналитическим способом

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

› Локализация корней табличным способом

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

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

Рис. 1. Варианты поведения функции на интервале локализации корня

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

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

Уточнение корней.

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

Существует большое количество численных методов решения нелинейных уравнений для уточнения корней, которые условно можно разделить:

› Методы решение уравнений с одним неизвестным. Основными представителями являются:

— метод половинного деления;

— метод простой итерации;

— метод Ньютона для уравнения с одним неизвестным;