1611703151-03589a55eaf19010bb3ad337d2045391 (827005), страница 48
Текст из файла (страница 48)
Метод десятичных испытаний. Допустим, что мы нашли интервал (с, с+ 1), с ~ 7, в котором находится один простой корень полинома 1(х) ен [«[х[. Значения полинома на концах интервала , ,имеют разные знаки. Разделим интервал на 1О равных частей и зи пвивлнжвнное вычисление ковнйи полиномА язв выберем ту часть, в которой находится корень. Эта часть характеризуется тем, что )(х) на ее концах имеет разные знаки.
Этот интервал снова разделим иа 10 частей и выберем ту часть, в которой находится корень. После этого шага процесса мы получим корень с точностью до 1О-э, но можно продолжить процесс дальше для достижения большей точности. При фактических вычислениях можно увеличивать на каждом шагу интервал в 10 раз. В этом варианте процесс выглядит так.
Пусть корень х~ полинома 1(х) = асх" + ... + а„находится в интервале (с, с+ 1). Разложим !(х) по степеням х — с: 1(х) = Ь,(х — с) "+ Ь, (х — с) "-' + ... + Ь„что делается по схеме Хорнера, и перейдем к полиному ),(у)= 10"!(х) после замены х — с = у/10. Этот папином имеет корень в интервале (О, 10); заключаем его между с, и с~+ 1 и повторяем процесс. После двух с~ шагов получаем: х, =- с+ — + — н ср < х < сз+ 1, так что ко- 1О ЮО рень известен с точностью до !О-'. П ри мер. Легко видеть, что полипом 1(х) = х' — х — ! имеет только один вещественный корень, и он заключен в интервале (1, 2). Вычислить корень этого полинома с точностью до 1Π— '.
Разложим !(х) по степеням х — 1. Получим по схеме Хорнера 7(х) = (х — 1) + 3(х — 1)'+ 2(х — 1) — 1. Заменим х 1 + -хб 1О и умножим на 1Оз. Получим )~(у) = уз+ ЗОу'+ 200у — 1000. Посредством проб получим, что 3 у~ 4. Разлагаем ~~(у) по степеням у — 3. Получим )~(у) =(у — 3)'+ 39(у — 3)'+407(у — 3)— х — 103. После замены у=3+ — и умножения иа 10' получим 1О ~э(г) = г'+ 390гз+ 40700г — 103000, откуда найдем для корня: 2 < г~ < 3. Итак, мы получили 1,32 < х < 1,ЗЗ.
Описанный метод удобен для вычисления с невысокой точностью корней полипома небольшой степени с небольшими коэффициентами. Его недостаток — быстрый рост коэффициентов от шага к шагу. 2. Метод непрерывных дробей. Пусть для полинома 1(х) снова известно, что он имеет один простой корень х~ в интервале (с, с+ 1). Разложим !(х) по степеням х — с: )(х)=Ьо(х — с)" +... + Ь„. Мы знаем, что х~ — с лежит в интервале (О, !). Сделаем инверсию этого интервала посредством замены х — с = 1/у и умножпм на у", Получим у"!(х) = Ь„у" + ...
+ Ьм На этом этапе коэффициенты не изменяются, но только записываются в обратном порядке. Корень у~ построенного полинома лежит в интервала (1, + о). Заключим его между двумя соседними целыми чис- 1 лами, с~ < у~ < с~+ 1, и повторим процесс.
Пусть у, = с, + —, аз <а, <сз+ 1, г,=сз+ — и с3 < 1~.~ сэ+1, Тогда для корня 1 ялспгвдвлвния когивн полиномл . !гл. !х х! будет ! х,=с+ ! с~+ с~+в причем известно, что сз < 1! < сз+ 1. Заменяя 1! на сз и с!+ 1 и учитывая характер изменения х при этих заменах (заменяя 1! ! ! на с, мы увеличиваем —, уменьшаем — и увеличиваем х!, ! ср+— заменяя т! иа с, + 1, мы уменьшаем х!), получим границы для х!! ! ! с+ <х,<с+ с~+ о+ с~ +— с +— сэ+ ! св Выражения, которые здесь участвуют, носят название непрерывных дробей.
П р и м е р. Применим метод непрерывных дробей к уточнению значения корня полинома х' — х — 1, 1 < х! < 2. Разложим полипом по степеням х — 1. Получим (х — 1)з+ + 3(х — 1)'+2(х — 1) — 1. Теперь делаем замену х — 1 = 1/у н умножаем на — у'. Получим уз — 2у' — Зу — !. Корень этого поли- нома заключен в интервале (3, 4). Разложение по степеням (у — 3) дает (у — 3) + 7(у — 3)'+ 12(у — 3) — 1. Замена у — 3 = 1/х н умножение на — гз дает аз — 12г' — 7г — 1. Корень этого полинома, очевидно, больше 12 и, как легко видеть, меньше 13.
Разложение по степеням г — !2 дает (г — 12)з+ 24(г — 12)э+ 137(г — 12)— — 85, после замены а — 12 = 1/! и умножения на — Р получим 35Р— 137Р— 241 — 1 и для корня !! этого полинома 1 < г! 2. Итак: х,=1+,, где 1 <7! <2. ! 3+ — ' ! !2+— Отсюда получаем границы для х!. 1+, <х! <1+ ! ! ! 3+ ! 3+ — ' !2+— ! 2 !2+— ! 23 !3 т. е.
1 — < х, < 1 — . 71 40 ' Границы эти довольно тесные, Действительно, !3 23 ! 1 — — 1 — = —. 40 77 3030 ' » б] ПРИБЛИЖЕННОЕ ЗЫЧИСЛЕНИЕ КОРНЕП ПОЛИНОМА 237 ]З Таким образом, 1 — „= 1,325 есть приближение к корню с избытком и отличается от корня меньше чем на 0,00033. Можно до. казать, что разность таким образом построенных приближений всегда равна 1, деленной на произведение знаменателей.
Приведем еще один пример, чтобы показать одно интересное явление. Вычислим «/2 как корень полинома х' — 2, лежащий в интервале (1, 2). Разложим полином по степеням х — 1 и сделаем замену х — 1 = 1/у. После умножения на — у» получим полипом у' — 2у — !. Этот полипом имеет корень в интервале (2, 3).
Разложение па степеням у — 2 и замена у в 2 = !/г дают, после умножения на — г', г' — 2г — 1. Мы получили для у н г полиномы с одинаковыми коэффициентами и нас интересуют корни из одного н того я!е интервала (2, 3), Следовательно, процесс будет далее повторяться без изменения, так что ч]2=!+ 2+— 1 2+— 2+ Периодичность при разложении в непрерывную дробь имеет место для всех квадратичных иррациональностей, т. е.
для чисел вида а+ 1/Т при целых а, Ь, ]1, причем д» 0 и с] не является квадратом целого числа. Это явление было обнаружено и доказано еще Эйлером. Читателю, у которого еще сохранилось любопытство, рекомендуем найти несколько приближений к у~6. Здесь, конечно, периодичности не будет, но на 6-м шагу произойдет неожиданное со* бытие. 3, Способ Ньютона. Этот способ основан на «основном принципе дифференциального исчисления», который, в нестрогих терминах, заключается в том, что график всякой «приличной» функции на малом промежутке изменения независимой переменной мало отличается от прямой, именно, касательной в одной из точек.
Пусть с — корень дважды дифференцируемой функции и ха — достаточно хорошее приближение к корню. Тогда имеет место приближенное равенство ) (х) =1(ха)+ 1'(хс) (х — х,) для всех х, достаточно близких к ха. Полагая х = с, получим 0 = 1(с) = 1(ха) + 1'(ха) (с — ха), (ГЛ. 1Х РАСПРЕДЕЛЕНИЕ КОРНЕЙ ПОЛИНОМА 238 откуда для с получаем приближенное значение с = х,— 7г — =х,. 1(х ) 7' (хо) или, после подстановки в интеграле Ь = х — г(х — хо), ) (Х) = 1 (Хо) + (Х Хо)1" (Хо) + (Х Хо) ~ ) (Х Г (Х Х1)) 1 10.
Положив х = с, получим 1 0=)'(с) =)(хо)+(с — хо) ) (хо)+(с — хо) $ Г(с — ((с — х,))(с((. Поделим это равенство на )'(хо) в левую часть. Получим и перенесем первые два члена )а (с — ((с — хо)) ( Ж. о Г (хо) (с — хо)о х — с — —, )' (хо) (' (хо) В левой части выражение хо —, равно приближению хь ) (хо) Г' (хо) Итак, 1 х, — с, ' ~ )а(с — г'(с — х,))(Ж. г ("о) о Пусть хо выбирается в окрестности точки с, н в этой окрестности модуль )'(х) ограничен снизу числом т и модуль Г'(х) Вообще говоря, х, должно быть лучшим приближением к с, чем исходное приближение хо.
По прнближе: ью х1 мы можем найти приближение хо по фарг (х,) муле х,=х, —, и т. д. Если последовательность х1, хо, )'(Х1) сходится, то она сходится к корню полинома ). Действительно, пусть хо- а при й — оо. Переходя к пределу в равенстве хо= ( (х,) 1 (а) х,, — ., о ', получим а=а — —,, откуда )'(а)=0. г' (а) ' Для того чтобы выяснить, насколько близко к с должно под- ходить исходное приближение хо, произведем опенку, учитывая погрешность исходного приближенного равенства, для чего рас- смотрим формулу Тейлора с остаточным членом в интегральной форме: ) (х) = ) (хо) + (х — х,) ) ' (хо) + ~ )а (") (х — Ь) гц х, чн ПРИБЛИЖЕННОЕ БЫЧИСЛЕНИЕ КОРНЕЙ ПОЛИНОМА 239 ограничен сверку числом М.
Тогда ! (Х,— Р!' М ~(х! — с(~ — ' — .М ~(й= — (хз — с)'. м 2вз о Умножив па —. получим М 2л! ' ° ~- ( х! — а ( ч~ ( —,„( х, — с 1) . М М 2 Поэтому, если — (хз — с1!~,'д < 1, то — (х! — с((д. Для М 2 2~ дальней!ппх Б рпближеинй — ! х, — с ) ~~ д', ..., — ! хь — с ! ~ (д Таким образом, в атом предположении имеет место быстрая сходимость приближений в корню с. Такого рода скодимость, когда погрешность приближения равна по порядку квадрату погрешности предыдущего приближения, носит название квадратичной сходимости.
Для полииомов вса проведенные выше рассуждения имеют силу не только для вычисления вещественных корней полиномов с вещественнымг коэффициентами, но и для комплексных корней полиномов с комплексными коэффициентами. Для вещественных функций имеются ситуации, когда иет необходимости выбирать начальное приближение очень близко к корню. Пусть на интервале (а, Ь) первая и вторая производные функции ( не меняют знак, а значения )' на концах интервала имеют противоположные знаки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
