Н.Н. Калиткин - Численные методы (1133437), страница 31
Текст из файла (страница 31)
е. для получения всех верных разрядов числа осталось сделать одну — три итерации. Г!оэтому такие процессы (за исключением метода парабол) редко употребляются. 7. Метод секущих «) 148]. В методе Ньютона требуется вычислять производную функции, что не всегда удобно, Можно заменить производную первой разделенной разностью, найденной по двум у последним итерациям, т. е.
заменить у)х) касательную секущей. Тогда вместо процесса (28) получим (З2) хь,,=х„— Для начала процесса надо задать х, и Л' х, (рис. 29). Такие процессы, где для вычисления очередного приближения надо знать два предыдущих, называют двухи2аговьтжи. Эти, казалось бы, небольшие изменения сильно влияют на характер итераций. Например, сходимость итераций может быть немонотонной не только вдали от корня, но и в малой окрестности корня. Скорость сходимости также изменяется. Иллюстрацией служит приведенный в таблице 16 расчет по методу секущих; для удобства сравнения с методом Ньютона первые два *) В математической литературе эго название нередко употребляют для другого метода, который по его геометрической интерпретации следовало бы называть методом хорд.
146 1ГЛ. Ч системы уРАВнеиип приближения взяты одинаковыми. Видно, что метод секущих сходится медленнее. Скорость сходимости можно оценить, разлагая все функции в (32) по формуле Тейлора с центром х. Получим с точностью до бесконечно малых более высокого порядка х„„— х=а(х„— х)(х„— х), а= —, Г (х) (33) Решение этого рекуррентного соотношения естественно искать в виде х„,„— х = а" (х„— х)", аналогичном (29) или (31а). Подставляя эту форму в соотношение (33), получим ар=1, (»« — )у — 1=0. (34) Только положительный корень р квадратного уравнения (34) соответствует убыванию ошибки, т. е. сходящемуся процессу.
Следовательно, в методе секущих х„., — х = аца (х, — х)а, () = »/» (~/5 + 1) 1,62, (1ф) 0,62, (35) в то время как в методе Ньютона ошибка убывает быстрей (соответствуя р=2). Но в методе Ньютона на каждой итерации надо вычислять и функцию, и производную, а в методе секущих— только функцию. Поэтому при одинаковом объеме вычислений в методе секущих можно сделать вдвое больше итераций и получить более высокую точность.
В знаменателе формулы (32," стоит разность значений функции. Вдали от корня это несущественно; но вблизи корня, особенно корня высокой кратности, значения функции малы и очень близки. Возникает потеря значащих цифр, приводящая к «разболтке» счета. Зто ограничивает точность, с которой можно найти корень; для простых корней это ограничение невелико, а для кратных может быть существенным.
Заметим, что приводить формулу (32) к общему знаменателю не следует: увеличится потеря точности в расчетах. От «разболтки» страхуются так называемым приемом Гарвика. Выбирают не очень малое е, ведут итерации до выполнения условия )х„<! — х,~(е и затем продолжают расчет до тех пор, пока ~х„.,— х„~ убывают. Первое же возрастание обычно означает начало <разболтки»; тогда расчет прекращают и последнюю итерацию не используют. 8. Метод парабол. Метод секущих можно рассматривать как замену функции ) (х) интерполяциоиным многочленом первой степени, проведенным пе узлам х„, х„,.
По трем последним 147 уРАВнение с Одним неизВестным 421 итерациям можно построить интерполяционный многочлен второй степени, т. е. заменить график функции параболой. Запишем интерполяционный многочлен в форме Ньютона 22 (Х) — 7 (Хд) + (Х ХР) 7 (ХР Хд 2) + (Х ХР) (Х Хд 2)) (Хп| Хд 2~ Хд 2) Приравнивая его нулю, получим квадратное уравнение аг'+ Ьг + с.= О, (Зба) где г=х — х„, а=7(х„, х„„х„,), (36б) Ь=а(х„— х„2)+)(х„, х.,), с=-7'(х,). Тот из двух корней квадратного уравнения (36), который меньше по модулю, определяет новое приближение х,,„=х„+г. Очевидно, для начала расчета надо задать три первых приближения х„х„х, (обычно наугад выбирают три числа), т. е. процесс является п2рехшаговым. Метод парабол построен по образцу методов третьего порядка.
Однако замена производных разделенными разностями приводит к существенному уменьшению скорости сходимости. Рассуждениями, аналогичными рассуждениям в п. 7, можно показать, что вблизи простого корня выполняется соотношение (37) т. е. сходимость даже медленнее квадратичной. Вблизи кратного корня сходимость еще медленнее (хотя и более быстрая, чем линейная). Заметим, что строить аналогичные методы с использованием интерполяционного многочлена еще более высокой степени невыгодно: сходимость все равно будет медленней квадратичной, а расчет сильно усложняется. В методе парабол «разболтка» счета вблизи корня сказывается еще сильней, чем в методе секущих, ибо в расчете участвуют вторые разности.
Тем не менее корни можно найти с хорошей точностью; для определения оптимального числа итераций удобно пользоваться приемом Гарвика, описанном в п. 7. Метод парабол имеет важное достоинство. Даже если все предыдущие приближения действительны, уравнение (36) может привести к комплексным числам. Поэтому процесс может естественно сойтись к комплексному корню исходного уравнения.
В методах простых итераций, касательных или секущих для сходимости к комплексному корню может потребоваться задание комплексного начального приближения (если 7(х) вещественна при вещественном аргументе). Корни многочлена. Метод парабол оказался исключительно эффективным для нахождения всех корней многочлена высокой степени. Если 7(х) — алгебраический многочлен, то, хотя 149 )гл. У СИСТЕМЫ УРАВНЕНИЙ сходимость метода при произвольном начальном приближении и не доказана, на практике итерации всегда сходятся к какому- нибудь корню, причем быстро.
Для многочлена частное ) (х)/(х — х) есть тоже многочлен; поэтому последовательно удаляя найденные корни, можно найти все корни исходного многочлена. 3 а м е ч а н и е 1. Если ) (х) — многочлен высокой степени, то возникают дополнительные трудности.
Многочлен быстро возрастает при увеличении аргумента, поэтому в программе для ЭВМ должна быть страховка от переполнения. Обычно вводят масштабные множители, величина которых связана с диапазоном изменения аргумента. Замечание 2. Наибольшие по модулю корни многочлена высокой степени могут быть очень чувствительны к погрешности коэффициентов при старших степенях. Например, корнями мно- гочлена го Рш(х) = И (х — )е) а =-! являются последовательные целые числа ха = 1, 2, ..., 20. А слегка измененный многочлен Р„(х) =Р„(х) — 2-"х"' имеет такие корни: 1,0; 2,0; ...; 8,0; 8,9; 10,1.+ 0,6(; ...; 19,5 +- 1,9(; 20,8 9.
Метод квадрнровання. Этот метод позволяет найти все корни много- члена. Запишем мнагочлен и-й степени двумя способамн: Р„(х)= ~З~ паха=а„ц(х — х~), а=о г=! (38) где хг — корни миогочлена. Сравнивая обе формы записи, получим раагисглва (здесь приведен только один знак после запятой). Кратные или близкие корни могут быть слабо устойчивыми даже при меньших степенях многочлена. 3 а м е ч а н и е 3.
Для удаления вычисленных корней надц делить многочлен. Это вносит погрешность округления в коэффициенты и влияет на точность нахождения следующих корней. На практике отмечено, что если сначала удалять меньшие по модулю корни, точность падает мало, но если наиать удаление с больших корней, точность может упасть катастрофически. Поэтому за начальное приближение берут хо =- — 1, х, = +1. х,= 0; тогда итерации обычно сходятся к наименьшему по модулю корню. Его удаляют и по такому же начальному приближению ищут следующий корень н т. д. При такой организации вычислений потеря точности будет небольшой. !49 ьр«внкнии с одним нкизвистным Х вЂ” ~ — Х и» т ис пл а чь! - - пл з хс,=-',, х,х,=+=,, Я«хсхм-- — —— ссл «=! «>с «) с )»а (Зй) Предположим, что корни многочлена сильно различаются по абсолютной величине: , 'х, !'~ ~ х, ~))...
~ ~ хл!. Тогда из равенств Виета получаются прибаижеиные значения корвей а . и л-с сса хс — — ха — —, ...,х 1 й л ол ол-с ас (40) Если модули корней мало различаются, то эти формулы слишком неточны. Но квадраты модулей будут различаться сильней, чем сами модули. Поменяем а многочлене (38) знаки всех корней, что эквивалентно смене знака у всех нечетных коэффициентов. Умножая измененный многочлен на исходный, полу- чим с » ')Г" 1 л а«х«~ ~ ~ ( — 1)л-сасхс~=а»„Ц (ха — д')ыссл(г), г хз. (41) «=! у=! »а= ! Мне!пелен С)„(г) имеет и-ю степень и называется квас)рироаоккым лногочлалом. Его корни равны квадратам корней исходного многочлена.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
