1626435587-51311eae4652e8ad616b5bdef025cbb3 (844239), страница 11
Текст из файла (страница 11)
Поскольку 2 ≈ 2,618, метод секущих может сходиться быстрее метода Ньютона, если сравнивать не по числу итераций, но по затратам машинноговремени, необходимого для нахождения корня с заданной точностью.Когда следует прекращать итерации (13)? Выражение (13) содержит конечную разность, погрешность вычисления которой может сильно возрастать при близких и −1 , особенно если вычисление функции () производится с достаточно большой погрешностью21 и/илив случае кратного корня функции (). Как следствие, итерации (13)могут вначале сходиться к искомому корню, однако в какой-то моментможет возникнуть «разболтка» процесса. Чтобы избежать этого, используется: итерации (13) выполняют, пока изменениеприближения к корню на одном шаге | − −1 | не станет меньшенекоторого порога , обеспечивая тем самым попадание в достаточномалую окрестность корня, где сходимость итерационного процесса была бы монотонной в соответствии с (14).
Далее, итерации продолжаютдо тех пор, пока величина |+1 − | монотонно убывает с ростом .Начало возрастания свидетельствует о «раскачке» итерационного процесса и необходимости его прекращения.приём Гарвика21 Что нередко бывает при использовании недостаточно точного метода вычисления спец.функции или интеграла с помощью квадратурной формулы.513.5. Многомерное обобщениеМетод Ньютона очевидным образом может быть обобщён на многомерный случай. Пусть задана система уравнений f (x) = 0, гдеf = {1 , . . . , }, x = {1 , .
. . , }. Выбрав некоторое начальное при(*)(*)(0)(0)ближение x (0) = {1 , . . . , } к корню x(*) = {1 , . . . , }, по()строим последовательность x , = 1, 2, . . ., сходящуюся к искомомукорню. Для этого, как и в одномерном случае, линеаризуем уравненияf (x) = 0. Используя тензорные обозначения и предполагая суммирование по повторяющимся индексам, имеем:⃒(︀ ())︀(︀ () )︀ ⃒⃒()()()()0 = x+ x≈ x+ , где =, ⃒x=x ()откуда получаем для x (+1) = x () + x () :[︂(︁)︁−1 ]︂(︀)︀(+1)()() x () .= − (15)3.6. Поиск комплексных корнейВ некоторых задачах может возникнуть необходимость поиска нулей функции на комплексной плоскости.
Пусть () — аналитическаяфункция в области , и | ()| < ∞ ∀ ∈ . Разложим () и её производную ′ () в ряд в точке 0 ∈ : () =∞∑︁=0!( − 0 ) , ′ () =∞∑︁=1( − 0 )−1 ,( − 1)! = () (0 ).)︀(︀Если 0 — нуль функции , то 0 = 0 и ′ / = ( − 0 )−1 + | − 0 |0 .Если 0 — нуль кратности , то () =∞∑︁( − 0 ) ,!=(︀)︀ ′ ()=+ | − 0 |0 . () − 0Используя интегральную формулу Коши, имеем∮︁ ′∑︁ () = 2 = 2. ()(16)С точностью до множителя 2 получили количество нулей функции () внутри контура с учетом их кратности.52Стратегия поиска комплексных корней () с использованием (16)может быть следующей.
Выбираем контур интегрирования так, чтобы внутрь∑︀ него попадало 1-2 нуля функции (). Допустим, для примера, = 2. Далее вычисляем интегралы вида∮︁ ′∑︁ ()1 = = 1 + 2 ,1 =2 ()2 =12∮︁∑︁ ′ () 2 =2 = 12 + 22 . ()Решение (1 , 2 ) полученной системы уравнений даёт нам решение исходной задачи о нахождении комплексных корней ().Заметим, что задача нахождения комплексных корней может бытьрешена с использованием рассмотренных выше методов Ньютона, секущих или метода итераций. Эти методы могут быть гораздо болееэффективны в случае, если известно достаточно хорошее начальноеприближение к искомому корню.3.7.
Сравнение методовКакой из рассмотренных выше методов лучше? Однозначного ответа на этот вопрос нет — оптимальный метод зависит от условий поставленной задачи. Метод дихотомии обеспечивает сравнительно невысокую, но при этомскорость сходимости для корнейнечётной кратности, тогда как сходимость других рассмотренных выше методов может быть условной. В этой связи метод дихотомии может быть использован для получения грубого приближения к корню споследующим его уточнением каким-либо другим методом, имеющимболее высокую скорость сходимости. Метод Ньютона эффективен, подходит в том числе для корней с чётной кратностью, но требует вычисления производной.
Метод секущих также очень эффективен, однакоможет приводить к «разболтке» и обеспечивать более низкую точность,особенно в случае кратных корней. Метод простых итераций исключительно прост в реализации и при этом может обеспечивать быструюсходимость к корню, особенно в случае |′ (* )| ≪ 1.Пожалуй, одним из оптимальных решений в случае, когда неизвестны производные функции, является, позволяющий отчасти объединить достоинства дихотомии и метода Ньютона.
Следующее приближение строится по трём начальным точкам с использованием квадратичной интерполяции (), а в тех случаях, когда найденное53гарантированнуюметод Брентас помощью интерполяции приближение не обеспечивает сходимости,применяется бисекция. Такой подход позволяет одновременно достичьгарантированной сходимости при относительно высокой скорости, неуступающей методу дихотомии на самых «плохих» функциях, и значительно ускорить сходимость в «хороших» случаях.
Формулы для вычислений по методу Брента вместе с программным кодом на языке Симожно найти в книге [4].Методы итераций, Ньютона и секущих могут использоваться дляпоиска комплексных корней. Однако если функция () принимает вещественные значения на вещественной оси, для сходимости итерацийк комплексному корню требуется комплексное начальное приближение 0 . Метод парабол [2] (метод Мюллера) лишён этого недостатка —он может естественным образом сойтись к комплексному корню дажев случае вещественного начального приближения.
Метод, основанныйна интегральной формуле Коши, значительно уступает по эффективности другим подходам при наличии хорошего начального приближенияк корню, однако может оказаться более эффективным, если положениеискомого корня неизвестно.Дополнительную информацию о решении конечных уравнений,включая рассмотрение задачи о поиске нескольких корней, в том числе кратных, можно найти в монографии [2]. Целый ряд методов и ихреализация на языке Си обсуждаются в [4]. Готовый код можно такженайти в библиотеках GNU scientific library и boost.Упражнения1. Найти уровень энергии основного состояния в одномерной прямоугольной яме, решая уравнение (4).2. Следующие фрагменты кода содержат «небольшие» ошибки, которые с большой вероятностью могут не проявляться при тестировании.
Для каждого фрагмента кода объясните, в чём заключаются ошибки, а также укажите значения параметров , , и, при которых программа будет даватьневерныйрезультат при поиске корня линейной функции () = + :существенно//способ 1: каждый шаг дихотомии даёт 1 бит мантиссы //в цикле делаем столько шагов, сколько бит в мантиссе:for(int i = 0; i < DBL_MANT_DIG; ++i) {c = (a+b)/2;if(f(c)*f(a) > 0) a=c; else b=c;}54//способ 2: продолжаем итерации до тех пор, пока//разность a и b не станет машинным нулем:while(b-a > DBL_MIN) {c = (a+b)/2;if(f(c)*f(b) < 0) a=c; else b=c;}//способ 3: продолжаем итерации до тех пор, пока//разность a и b не станет меньше машинного эпсилон:while(b-a > DBL_EPSILON) {c = (a+b)/2;if(f(c)*f(a) > 0) a=c; else b=c;}//способ 4:c = (a+b)/2;do {if(f(c)*f(a) < 0) b=c;c = (a+b)/2;}while((a<c)&&(c<b));//способ 5:c = (a+b)/2;do {if(f(c)*f(a) > 0) a=c;c = (a+b)/2;}while((a<c)&&(c<b));else a=c;else b=c;3.
Пусть () — непрерывная функция, и (* ) = 0, * ∈ [, ]. Может ли метод дихотомии на отрезке [, ] не сойтись к * ?4. Пусть () = (tg ()) — полином степени от tg (). Если * —единственный корень функции () на отрезке [, ]. Может лиметод дихотомии на указанном отрезке не сойтись к * ? Изменится ли ответ, если * — простой корень?5. Исследовать зависимость остаточного члена ≡ * − от номера итерации при решении уравнения = 12 ( + cos ) методом итераций (6) с использованием и без использования поправкиЭйткена (10).
Что будет, если уравнение заменить на = 21 (+ 2 )?556. Найти область притяжения к корню уравнения th = 0 при решении методом Ньютона.для любой7. Из (12) следует, чтогладкой функции (), такой что ′ (* ) ̸= 0 и ′′ (* ) ̸= 0, где * — корень (* ) = 0, ∃ > 0 такая,что ∀0 : |0 − * | > будет выполняться | | < |+1 |, где ≡ * − , т. е. итерации будут расходится, если 0 лежитвне области притяжения к корню, имеющей конечную ширину.Найдите ошибку в рассуждениях и приведите примеры функций,для которых итерации в методе Ньютона сходятся безусловно.4. Численное интегрированиеМногие физические величины выражаютсячерез интегралы: рабо∫︀та равна интегралуотсилы=,перемещение— интегралот∫︀∫︀скорости = ˙ , вероятность в квантовой механике — = ||2 ит.
д. Необходимость приближённого численного нахождения интегралов возникает, когда результат не может быть представлен точно через доступные на ЭВМ библиотечные функции, а также когда подынтегральное выражение известно не в символьном виде, а получено врезультате численных расчётов (задано в виде таблицы значений нанекоторой сетке). В данном разделе мы рассмотрим несколько способов приближённого вычисления определённых интегралов, начав снаиболее простых квадратурных формул и постепенно переходя к более сложным и точным.564.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
