1.2.5 Другие задачи, решаемые численными методами

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

Рассмотрим различные способы решения уравнений.

Метод половинного деления (дихотомия)

Пусть мы нашли такие точки a и b что f(a)f(b)0, т. е. на отрезке [a,b] лежит не менее одного корня уравнения. Найдем середину отрезка x_c=(a+b)/2 и вычислим f(x_c). Из двух половин отрезка выберем ту, для которой f(x_c)f(a или b)0, т.е. отрезок на котором функция меняет знак. Затем новый отрезок опять делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис. 9).

Размещено на http://www.allbest.ru/

Если требуется найти корень с точностью , то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше 2. Тогда середина последнего отрезка даст значение корня с требуемой точностью. Дихотомия проста и очень надежна: к простому корню она сходится для любых непрерывных функций f(x), в том числе недифференцируемых; при этом она устойчива к ошибкам округления. Скорость сходимости невелика: за одну итерацию точность увеличивается примерно вдвое, т. е. уточнение трех цифр требует 10 итераций (т.к. длина отрезка, на котором лежит корень, после 10 итераций равна 1/2¹⁰=1/102410^-3). Зато точность ответа гарантируется.

Перечислим недостатки метода.

1. Для начала расчета надо найти отрезок, на котором функция меняет знак.

2. Если в этом отрезке несколько корней, то заранее неизвестно, к какому из них сойдется процесс (хотя к одному из них сойдется).

3. Метод неприменим к корням четной кратности.

4. Для корней высокой нечетной кратности он сходится, но менее точен и хуже устойчив к ошибкам округления, возникающим при вычислении f(x).

5. На системы уравнений дихотомия не обобщается.

Утверждение 1. С помощью данного метода невозможно найти корни чётной кратности.

Доказательство.

Чётно кратный корень это корень уравнения вида

(x+a)²ⁿ=0,

где n - целое, n[0,].

Решением этого уравнения будет корень x=-a кратности 2n. В общем виде уравнение может иметь как чётно, так и нечётно кратные корни. Можно записать общий вид уравнения имеющего (k+m) только действительных корней так:

(x+x₁)²ⁿ¹(x+x₂)²ⁿ²…(x+x_k)^2nk(x+x_k+1)^2n(k+1)+1(x+x_k+2)^2n(k+2)+1…

….(x+x_k+m)^2n(k+m)+1=0,

где n1,…,n(k+m) [0,] - целые числа; x₁ x₂… x_k+m.

В уравнении k чётно кратных и m нечётно кратных корней. Оно раскладывается на (k+m) уравнений, из которых легко получаются корни. Если задать начальный отрезок [-x₁-r,-x₁+r], где r - мало, и проверить условие смены знака функции на его границах, то обнаружим, что знак не меняется в силу чётности степени. А если аналогично проверить нечётно кратные корни, то получим обратную ситуацию.

Следствие 1.

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

Следствие 2.

Если корень имеет нечётную кратность, то на границах бесконечно малого отрезка с центром в этом корне функция имеет разные знаки.

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

Утверждение 2. Если на концах начального отрезка значения функции имеют один знак, то метод может не сойтись, то есть, возможно, ни один из корней не будет найден с заданной точностью.

Утверждение 3. Если на концах начального отрезка значения функции имеют разные знаки, то будет найден с заданной точностью один из корней лежащих на нём.

Метод секущих

В данном методе, в отличие от метода Ньютона, проводятся не касательные, а секущие (Рис. 10). Из рисунка легко получить итерационную формулу:

.

Размещено на http://www.allbest.ru/

В качестве начального приближения необходимо задать не только x₀, но и x₁. Метод секущих имеет одно преимущество перед методом Ньютона - здесь не нужно вычислять производную. Но этот метод имеет также существенные недостатки. Сходимость итераций может быть немонотонной не только вдали от корня, но и в малой окрестности корня [7, C.39].

В знаменателе формулы стоит разность значений функции. Вдали от корня это не существенно; но вблизи корня, особенно корня высокой кратности, значения функции малы и очень близки. Возникает потеря значащих цифр, приводящая к «разболтке» счёта. Это ограничивает точность, с которой можно найти корень; для простых корней это ограничение не велико, а для кратных может быть существенным.

От «разболтки» страхуются так называемым приёмом Гаврика. Выбирают не очень малое е, ведут итерации до выполнения условия |x_n+1-x_n|<е и затем продолжают расчёты до тех пор, пока |x_n+1-x_n| убывают. Первое же возрастание обычно означает начало «разболтки»; тогда расчёт прекращают и последнюю итерацию не используют. Все ограничения по сходимости итераций для данного метода такие же, как и в методах простых итераций и Ньютона. А вот определение достижения заданной точности, как видно из описания метода, затруднительно, и, даже, возможна ситуация, когда из-за «разболтки» счёта заданная точность не будет достигнута никогда. При использовании метода секущих в явном виде определить точность трудно, поэтому используют косвенный метод. Считают, что вблизи корня |x_n+1-x_n||x_т-x_n+1|. Конечно эта оценка весьма примерна, но при больших n (в идеале при n>?) это так и есть.