Вычислительная математика 
 

  назад | оглавление | вперед

 

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

1.Общие замечания

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

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

Приближенное значение корня (начальное приближение) может быть найдено различными способами: из физических соображений, из решения аналогичной задачи при других начальных данных, с помощью графических методов. Если такие оценки начального приближения произвести не удается, то находят две близко расположенные точки a и b, в которых непрерывная функция f(x) принимает значения разных знаков, т.е. выполняется условие: . В этом случае между точками a и b есть, по крайней мере, одна точка, в которой . В качестве начального приближения принимают одну из точек этого отрезка x(0). Итерационный процесс состоит в нахождении последовательных приближений значений корня: x0, x1, ..., xn. Если эти значения с ростом n приближаются к истинному значению корня, то итерационный процесс сходится.


2. Метод деления пополам (метод бисекции)

Это один из простейших методов нахождения корней нелинейного уравнения. Пусть имеется интервал [а,b], на котором функция f(x) меняет свой знак, т.е. f(a)× f(b)<0. В качестве начального приближения корня возьмем середину этого интервала: x(0) = (a + b)/2. Далее выясняем, на каком из интервалов [a, x(0)] или [x(0), b] функция f меняет знак. В качестве нового интервала рассматриваем ту половину интервала [а,b], на которой происходит смена знака. В качестве нового приближения корня выбираем середину нового отрезка и т.д. Таким образом, после каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, т.е. после n итераций начальный интервал уменьшится в 2n раз. Итерационный процесс продолжается до тех пор, пока длина интервала изоляции корня не станет меньше заданной точности. В качестве приближенного значения корня принимаем середину последнего интервала.

Достоинством метода деления пополам является то, что он обязательно сходится, хотя и медленно. При этом

,               (1)

где x* - точное значение корня

Неравенство (1) позволяет оценить количество шагов n, необходимых для достижения заданной точности e.

.


3. Метод хорд

В методе деления пополам интервал многократно делится пополам, а в методе хорд интервал делится на неравные части в отношении . Пусть имеется интервал [а,b], на котором функция f(x) меняет свой знак, т.е. f(a) × f(b)<0. Для определенности будем считать, что . В данном методе процесс итераций состоит в том, что в качестве последовательности приближений к корню принимаются значения точек пересечения хорды, соединяющей точки a и b с осью Ox.

Найдем уравнение хорды AB:

.

Для точки пересечения хорды с осью Ox (x = c, = 0) получаем. .

Из отрезков [a,c] и [c,b] выбираем тот, на котором функция меняет знак. Для рассматриваемого случая это отрезок [с,b]. Следующая итерация состоит в определении нового приближения как точки пересечения новой хорды с осью Ox и т.д. Повторяем процесс до тех пор, пока не будет достигнута заданная точность.

Оценку скорости сходимости в методе хорд дает следующая теорема.

Теорема 1:

Если на интервале [a,b] функция f(x) непрерывна и дифференцируема, а ее производная на интервале [a,b] имеет постоянный знак (т.е. на [a,b] f(x) монотонна), то верна следующая оценка:

,               (2)

где x*-точное значение корня, , , х Î [a,b].

Следствие:

Если отрезок [a,b] узок, т.е. , то

.               (3)

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


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

Метод касательных является наиболее употребительным при приближенном решении уравнений, т.к. дает довольно быструю сходимость процесса вычислений к нужному результату. Поясним процесс производимых итераций метода. В качестве первоначального приближения х0 выбираем тот конец интервала [a,b], в котором знак функции совпадает со знаком второй производной. В точке (х0, f(x0)) проводим касательную к графику функции до пересечения с осью Оx в точке х1. В точке (х1, f(x1)) проводим касательную до пересечения с осью Оx, получаем x2 и т.д.

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

Составим уравнение касательной в точке (xn,f(xn)). Поскольку угловой коэффициент касательной , и касательная проходит через точку (xn,f(xn)), то уравнение касательной имеет вид: . Для точки пересечения касательной с осью Ox (x = xn+1, = 0) получаем:

              (4)

Теорема 2

Если функция f(x) дважды непрерывна и дифференцируема на [a,b], и на [a,b] не меняют своих знаков (т.е. функция монотонна и выпукла вверх или вниз), то погрешность метода Ньютона можно оценить по формуле:

,               (5)

где , .

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

Следующая формула связывает погрешности двух последних приближений xn-1 и xn:

              (6)

Иногда бывает затруднительно вычислять на каждом шаге . Если производная мало изменяется на отрезке [a,b], то в формуле Ньютона (4) можно положить . Тогда получим формулу модифицированного метода Ньютона:

              (6)

В этом случае касательные в точках (хn, f(xn)) заменяются прямыми, параллельными касательной в точке (х0, f(x0)). Этот метод работает не хуже, чем метод Ньютона, но дает более медленную скорость сходимости.



назад | оглавление | вперёд