К содержанию

Численное решение нелинейных уравнений

Введение

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

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

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

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

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

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

Пусть после взятия производной мы пришли к уравнению 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) на концах отрезка [a,b] имеет значения разных знаков, т.е. f(a)ґ f(b)Ј 0, то в указан-ном промежутке содержится хотя бы один корень. Например, для уравнения f(x)= x³-6x+2=0 видим, что при x®Ґ   f(x)>0, при x®-Ґ   f(x)<0, что уже свидетельствует о наличии хотя бы одного корня.

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

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

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

Рис. 1. Метод деления отрезка пополам

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

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

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

Рис. 2. Блок-схема метода половинного деления

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

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

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

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

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

Рис. 3. Метод хорд

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

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

,

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

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

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

Рис. 4. Метод касательных

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

,

.

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

Рис. 5. Расходящийся процесс	Рис. 6. Приближение к другому корню

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

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

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

.

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

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

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

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

.

Если функция j (x) определена и дифференцируема на некотором интервале, причем |j /(x)|< 1, то эта последовательность сходится к корню уравнения x=j (x) на этом интервале.

Геометрическая интерпретация процесса представлена на рис. 7. Здесь первые два рисунка (а, б) демонстрируют одностороннее и двустороннее приближение к корню, третий же (в) выступает иллюстрацией расходящегося процесса (|j /(x)| > 1).

а	б	в
Рис. 7. Геометрическая интерпретация метода простой итерации

Если f '(x)>0, то подбор равносильного уравнения можно свести к замене x=x-l Ч f(x), т.е. к выбору j (x)= x-l Ч f(x), где l >0 подбирается так, чтобы в окрестности корня 0 < j '(x)=1- l Ч f '(x) Ј 1. Отсюда может быть построен итерационный процесс

.

Возьмем для примера уравнение x³ + x -1000 = 0. Очевидно, что корень данного уравнения несколько меньше 10. Если переписать это уравнение в виде x =1000 - x³ и начать итерационный процесс при x₀=10, то из первых же приближений очевидна его расходимость. Если же учесть f '(x)=3x²+1>0 и принять за приближенное значение максимума f '(x) M=300, то можно построить сходящийся итерационный процесс на основе представления

.

Можно и искусственно подобрать подходящую форму уравнения, например:

или .

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

наверх

следующая глава