Во многих научных и инженерных задачах часто возникает необходимость решения уравнений вида
(1.18)
где f - заданная функция.
Уравнение (1.18) может иметь как конечное, так и бесконечное количество решений, что зависит от вида функции f(x).
Решениями или корнями уравнения (1.18) называются такие значения х, которые при подстановке в уравнение (1.18) обращают его в тождество. Нахождение корней таких уравнений аналитическими методами (т.е. путем записи формулы выражающующей искомую величину х, в явном виде) возможно только для простейших случаев. Поэтому чаще всего приходится решать уравнения вида (1.18) численными методами. Кроме того, иногда, даже при наличии аналитического решения, имеющего сложный вид, бывает проще провести численное решение по известному алгоритму, чем программировать громоздкую аналитическую формулу.
Численное решение уравнения (1.18) обычно проводят в два этапа. На первом этапе необходимо отделить корни уравнения, т.е. найти такие интервалы изменения переменной х, где расположен только один корень. На втором этапе проводят уточнение отделенных корней, т.е. находят корни с заданной точностью. Для этого разработан богатый набор алгоритмов и программ.
По сути дела, на этапе отделения корней находят приближенные значения корней с погрешностью, задаваемой длиной каждого интервала. Нередко отделение корней удается провести, не обращаясь к математическим методам и алгоритмам, на основании физического смысла задачи или из анализа ее упрощенной математической модели. Более наглядным и простым является приближенное отделение корней при изучении графика функции выведенного на экран ПЭВМ.
Для уточнения значений отделенных корней преимущественно используются методы половинного деления (дихотомии), хорд, простых итераций и Ньютона.
Метод половинного деления
Считаем, что отделение корней уравнения (1.18) проведено и на отрезке [а,b] расположен один корень, который необходимо уточнить с абсолютным итерационным допуском ε. Метод половинного деления, заключается в следующем.
Как видно из рисунка 1.1, вначале определяем середину отрезка [а, b] x*=(а+b)/2и вычисляем функцию f(x*). Далее делаем выбор, какую из двух частей отрезка взять для дальнейшего уточнения корня. Если левая часть уравнения f(x) есть непрерывная функция аргумента х, то корень будет находиться в той половине отрезка, на концах которой f(x) имеет разные знаки. На рисунке 1.1 это будет отрезок [а, х*]. Для очередного шага уточнения точку b перемещаем в точку х* и продолжаем процесс аналогичным образом. Итерационный процесс будем продолжать до тех пор, пока интервал [а, b] не станет меньше заданного итерационного допуска ε.
Используя метод половинного деления, следует учитывать, что функция f(x) вычисляется с некоторой абсолютной погрешностью, а вблизи корня значения функции f(x) малы по абсолютной величине и поэтому могут оказаться сравнимыми с погрешностью ее вычисления. Другими словами, при подходе к корню существует опасность попасть в полосу “шумов” 2ε1 (Рис. 1.1) и дальнейшее уточнение корня окажется невозможным. В этом случае процесс уточнения значения корня прекращается. При практических расчетах обычно принимают ε1=ε.
Метод половинного деления обладает быстрой сходимостью, так как за каждую итерацию интервал, где расположен корень, уменьшается в два раза. Таким образом через питераций интервал будет равен (b - a)/2n.
Метод хорд.
Метод хорд также, как и метод половинного деления, предназначен для уточнения корня на интервале [a,b], на концах которого значения функции f(x) разного знака. Первое приближение берется в точке x1, где пересекается прямая линия, проведенная через точки f(a) и f(b) с осью x. В качестве нового интервала для продолжения итерационного процесса выбирается тот из двух [a,x1] или [x1,b], на концах которого функция f(x) имеет разные знаки. В нашем слчае это интервал [a,x1]. На следующих итерациях после уточнения границ нового интервала расчет проводится по формуле:
x=(f(b)*a - f(a)*b)/(f(b) - f(a));
Итерационный процесс уточнения корня заканчивается, когда выполнится условие |xi-xi-1|<e или когда значение функции f(xi) попадет в область шума | f(xi) |<e1.
Метод Ньютона (метод касательных).
Рассмотрим графическую иллюстрацию метода на Рис. 1.3.
Предположим, что известно начальное приближение x0 к корню. В точке x0 вычислим левую часть решаемого уравнения f(xQ), а также производную в этой точке f’’(х0). Следующее приближение к корню найдем в точке х1, где касательная к функции f(x), проведенная из точки (x0,f0), пресекает ось абсцисс. Для этого используем формулу (1.19) построенную на основе элементарных геометрических соображений.
(1.19)
Затем считаем точку х1в качестве начальной и продолжаем итерационный процесс (определяем следующее приближение x2) и т.д. Из Рис. 1.3 видно, что таким способом можно быстро приблизиться к корню х*. При этом с каждой итерацией расстояние между очередным xm и предыдущим хm-1 приближениями к корню будет уменьшаться. Расчет уточненного значения корня в общем случае проводим по уравнению (1.20). Процесс уточнения корня закончим, когда выполнится условие (1.21).
(1.20)
½xm+1 - хm ½< ε, (1.21)
где ε – абсолютный итерационный допуск,
m – номер итерации (приближения).
Метод Ньютона обладает высокой скоростью сходимости, его недостатком является необходимость вычисления на каждой итерации не только левой части уравнения, но и ее производной.
(1.18)
Метод хорд.
(1.19)
(1.20)