Действия с приближенными величинами

      .    

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, т.е. отрезок на котором функция меняет знак. Затем новый отрезок опять делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис. 1). 

       

     Если  требуется найти корень с точностью e, то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше 2e. Тогда середина последнего отрезка даст значение корня с требуемой точностью. Дихотомия проста и очень надежна: к простому корню она сходится для любых непрерывных функций f(x), в том числе недифференцируемых; при этом она устойчива к ошибкам округления. Скорость сходимости невелика: за одну итерацию точность увеличивается примерно вдвое, т. е. уточнение трех цифр требует 10 итераций (т.к. длина отрезка, на котором лежит корень, после 10 итераций равна 1/2¹⁰=1/1024»10^-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. Если на концах начального отрезка значения функции имеют разные знаки, то будет найден с заданной точностью один из корней лежащих на нём.

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

       

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

      . 

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

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

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

2. Теоретический вопрос  варианта заданий 

     Метод простых итераций

     Основной  принцип метода заключается в  том, что уравнение представляется в виде:

     x=φ(x),     

     где φ(x) можно определить многими способами, например, так:

     φ(x)=x-αf(x), α=const, или

     φ(x)=x+ψ(x)f(x),

     где ψ(x) – произвольная, непрерывная, знакопостоянная функция на отрезке [a,b].

     Метод простых итераций в силу определяется следующей рекурсивной формулой:

     

     x_n+1=φ(x_n), где n=0,1,2,…  

     Здесь n имеет смысл номера итерации, x₀ – некоторое начальное приближение. Из уравнения видно, что если x_n→x_т, то этот предел и есть корень уравнения (рис. 2).

     Пусть в окрестности точки x_т (x_т-Δ,x_т+Δ), где Δ>0 функция φ(x) удовлетворяет условию Липшица:

     |φ(x₂)-φ(x₁)|≤q|x₂-x₁|    

     для любых x₂,x₁Î(x_т-Δ,x_т+Δ),

     0<q<1,      

     при этом x₀Î(x_т-Δ,x_т+Δ),     

     причём, (x_т-Δ,x_т+Δ) Î[a,b].

     В связи с этим допущением можно  сделать несколько утверждений.

     Утверждение 1.

     Полученные  с помощью (5) x_nÎ(x_т-Δ,x_т+Δ) для любого целого n≥0.

     Утверждение 2.

     Последовательность {x_n} сходится при n→∞ к пределу x_т, являющемуся корнем уравнения.

     Утверждение 3.

     На  интервале (x_т-Δ,x_т+Δ) существует только 1 корень уравнения.

     Как и при поиске решения методом  дихотомии будем считать задачу выполненной, если найденное некоторое  значение x_чÎ[x_т-ε,x_т+ε], где ε – заданная точность. Для определения того, когда можно прекратить итерации, т.е. когда достигнута заданная точность, подробнее рассмотрим неравенство. По сути, нам необходимо добиться выполнения следующего неравенства:

     |x_n+1-x_т| ≤ ε,     

     |x_n+1-x_т| ≤ qⁿ⁺¹|x₀-x_т|,

     где q можно определить как для любого целого n≥1, выведем условие достижения заданной точности (12). Введём обозначения

     δ_n+1=|x_n+1-x_т|. ,

     а так же очевидно, что    δ₀-δ_n+1=|x₀-x_n+1|=ξ, тогда:

     δ₀=δ_n+1+ξ

     δ_n+1=gδ=g(δ_n+1+ξ)

     

     

     

     

     

      .      

     Неравенство является условием остановки процесса итераций, т.е. условием достижения заданной точности. В завершение рассмотрения данного метода остаётся только построить блок-схему его алгоритма. Будем считать, что |φ′(x_т)|<1, x₀Î(x_т-Δ,x_т+Δ).

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

       

     Метод Ньютона называют также методом  касательных и методом линеаризации. Суть метода заключается в том, что в точке приближения к функции строится касательная (Рис. 3). Следующая точка приближения – это точка пересечения полученной прямой с осью Ox. Процесс продолжается вплоть до достижения заданной точности.

     Из  рисунка очень легко получить итерационную формулу метода, используя геометрический смысл производной. Если f(x) имеет непрерывную производную f’(x)≠0, тогда получим

     

     

     Аналогично  получаем x₂, x₃, и т.д. Таким образом, можем записать общую формулу:

       

     Метод Ньютона можно рассматривать, как частный случай метода простых итераций, если задать

      .

     В этом случае

     

     Условие сходимости метода простых итераций можно переписать для метода Ньютона следующим образом: