Вычислительная математика
|
назад | оглавление | вперед |
Глава 5. Решение нелинейных уравнений
Будем искать решение уравнения 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.
.
В методе деления пополам интервал многократно делится пополам,
а в методе хорд интервал делится на неравные части в отношении
. Пусть имеется
интервал [а,b], на котором функция f(x)
меняет свой знак, т.е. f(a)
×
f(b)<0. Для определенности будем считать, что
. В данном методе
процесс итераций состоит в том, что в качестве последовательности
приближений к корню принимаются значения точек пересечения хорды,
соединяющей точки a и b с осью Ox.
Найдем уравнение хорды AB:
.
Для точки пересечения хорды с осью Ox (x = c, y = 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, y = 0) получаем:
              (4)
Теорема 2
Если функция f(x) дважды непрерывна и дифференцируема на [a,b], и
на [a,b] не меняют своих знаков (т.е. функция монотонна и выпукла вверх или вниз), то погрешность метода Ньютона можно оценить по формуле:
,               (5)
где ,
.
Метод Ньютона обеспечивает эффект удвоения верных знаков после каждой итерации.
Следующая формула связывает погрешности двух последних приближений xn-1 и xn:
              (6)
Иногда бывает затруднительно вычислять на каждом шаге . Если производная
мало изменяется на отрезке [a,b], то в формуле Ньютона (4) можно положить
. Тогда получим формулу модифицированного метода Ньютона:
              (6)
В этом случае касательные в точках (хn, f(xn)) заменяются прямыми, параллельными касательной в точке (х0, f(x0)). Этот метод работает не хуже, чем метод Ньютона, но дает более медленную скорость сходимости.