Главная Обратная связь

Дисциплины:






Решение нелинейных уравнений



Пусть требуется решить уравнение

, (1)

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

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

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

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

.

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

Полное решение поставленной задачи можно разделить на 3 этапа:

1. Установить количество и характер корней уравнения (действительные или комплексные, простые или кратные). Мы будем искать действительные корни уравнения (1).

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

3. Найти значение корней с требуемой точностью (уточнить корни).

Существуют различные графические и аналитические методы решения первых двух задач.

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

На рисунке представлены три наиболее часто встречающиеся ситуации:

 

a) кратный корень: ;

b) простой корень: ;

c) вырожденный корень: не существует, ;

Как видно из рисунка, в случаях а) и в) значение корня совпадает с точкой экстремума функции и для нахождения таких корней можно использовать методы поиска минимума функции. Мы будем искать простые действительные корни уравнения (1).

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



Промежутки изоляции корней уравнения (1) можно получить аналитически, опираясь на теоремы о свойствах функций, непрерывных на отрезке.

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

Если функция удовлетворяет условиям теоремы Больцано—Коши и монотонна на этом отрезке, то на отрезке существует только один корень уравнения (1). Достаточным условием монотонности функции на отрезке mявляется сохранение знака ее первой производной (если , функция возрастает на отрезке, если , функция убывает). Таким образом, уравнение (1) имеет на отрезке единственный корень, если выполняются условия:

1. Функция – непрерывна на отрезке .

2. (2)

3. сохраняет знак на (монотонна на отрезке ).

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

1. Находим производную .

2. Решаем уравнение для нахождения стационарных точек.

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

4. Из полученных интервалов выбираем только те, на концах которых принимает значение разных знаков.

5. Уточняем интервалы за счет их сужения.

Полезным средством для отделения корней полинома является также использование теоремы Штурма.

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

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

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

Метод простых итераций ( MI).

Уравнение вида в методе простых итераций преобразуется к эквивалентному уравнению вида:

. (3)

Это можно сделать многими способами, например, положив

, (4)

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

(5)

Выполнение расчетов по формуле (5) называется одной итерацией. Метод простых итераций не всегда сходится к точному решению уравнения. Достаточным условием сходимости этого метода является выполнение неравенства:

для , (6)

на отрезке, содержащем корень и все приближения . Скорость сходимости зависит от абсолютной величины производной . Чем меньше вблизи корня, тем быстрее сходится процесс. Поэтому выбором функции в формуле (4) для итераций можно влиять на сходимость метода. В простейшем случае со знаком плюс или минус. На практике, если уравнение (1) разрешимо относительно x , выражают непосредственно из уравнения (1). Если не выполняется условие сходимости, уравнение (1) преобразуют к виду (3) , подбирая .

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

Рассмотрим процесс графически. На рисунке представлены случаи: а - односторонний сходящийся процесс; б - односторонний расходящийся процесс; в - двухсторонний сходящийся процесс; г- двухсторонний расходящийся процесс. Из графиков видно, что при и при возможны как сходящиеся, так и расходящиеся итерационные процессы.

 

 

 

Метод простых итераций является одношаговым и имеет линейную скорость сходимости.

 

Метод Ньютона (MN).

Итерации в методе Ньютона осуществляются по формуле:

, . (7)

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

. (8)

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

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

. (9)

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

, (10)

то метод сходится для любых .

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

 

 

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

 

Метод Вегстейна (метод секущих-хорд), MV.

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

,

то получим следующую формулу для итераций:

.

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

Рассмотрим данные методы на примере. Решим уравнение методом простых итераций. Зададим . Построим график функции.

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

1. непрерывна на .

2. .

3. на .

Напомним, что исходное уравнение (1) в методе простой итерации преобразуется к виду , и итерации осуществляются по формуле:

Итерации прекращаются, когда выполняется условие , где - абсолютная погрешность нахождения корня, или , где -относительная погрешность.

Наше уравнение разрешимо относительно x, поэтому привести его к виду (3) можно одним из способов: или . Проверим условие сходимости в обоих случаях.

для

для .

Как видим, условие сходимости выполняется для случая представления . Обратите внимание, что условие сходимости выполняется не , поэтому мы и берем отрезок изоляции корня . Проиллюстрируем условия сходимости на графике, где f1(x) = x. На графике видно, что (|tg| угла наклона касательной к на отрезке )

Выберем (начальное приближение выбирается из области сходимости). Организуем итерационный процесс:

На 19 итерации получим корень нашего уравнения c абсолютной погрешностью

Решим наше уравнение методом Ньютона. Итерации в методе Ньютона осуществляются по формуле:

, .

Как мы уже отмечали, метод Ньютона можно рассматривать как метод простой итерации. Для нашего уравнения условие сходимости (8) выполняется и имеет вид:

.

Что видно как алгебраически, так и на графике, где . За начальное приближение мы можем выбрать .

Выберем , исходя из условия (9). Оно выполняется, например, для : .

Произведем вычисления:
, начальное приближение , .
Организуем итерации по формуле (7):

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

методом Ньютона с , находим корень уравнения на [-1,5;-1]:





sdamzavas.net - 2020 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...