Лекции по алгебре - Фаддеев Д.К.
Скачать (прямая ссылка):
1*0
M 2т
1*0
Умножив на
M
, получим
•fei*'-«
|<
M 2т
X0-
Поэтому, если
M
2т
")*•
Af
|«о-е|<7<1, то -2^-1X1-сKf. Для
дальнейших приближений -^-1 .V2 — с К 0*> ¦ • • > ^Ua — с К •
Таким образом, в этом предположении имеет место быстрая сходимость приближение в корню с. Такого рода сходимость, когда погрешность приближения равна по порядку квадрату погрешности предыдущего приближения, носит название квадратичной сходимости.
Для полиномов все проведенные выше рассуждения имеют силу не только для вычисления вещественных корней полиномов с вещественными коэффициентами, но и для комплексных корней полиномов с комплексными коэффициентами.
Для вещественных функций имеются ситуации, когда нет необходимости выбирать начальное приближение очень близко к корню. Пусть на интервале (а, Ь) первая и вторая производные функции f не меняют знак, а значения f на концах интервала имеют противоположные знаки. В этих предположениях функция f имеет на интервале единственный корень с.
Допустим, для определенности, что /' и /" положительны на интервале (а,Ь). Это значит, что f возрастает и выпуклость ее графика направлена вниз (рис. 17).
Возьмем начальное приближение X0 справа от корня (например, хо=Ь). Геометрически очевидно, что следующее приближение х\ будет ближе к с чем JC0 и останется справа от с. Подтвердим это вычислением:
Х\-
Рис. 17.
= *0 —
/' (*о)
В силу возрастания f заключаем, что }(х0)"> 0, но и /'(лсо)> 0 по условию, следовательно, х\ < хо. Далее,
,____(с —XqY
С~ П*о>
У
(c-t(c — x0))tdt>Q,
240
РАСПРЕДЕЛЕНИЕ КОРНЕЙ ПОЛИНОМА
[ГЛ. IX
ибо CsCIc — /(с — Xo)=SIx0, а /" положительна на всем интервале (а, Ь).
Вычисляя далее последовательные приближения х2, Хз, мы получим убывающую последовательность, ограниченную снизу
Рис. 18. Рис. 19.
числом с. Она сходится и, как мы видели выше, сходится к корню /, который на промежутке (а, Ь) только один, именно, с.
Легко видеть, что если /' и ]" отрицательны на промежутке (а, Ь), то начинать приближения тоже следует справа от корня (рис. 18). Если же у и Y' сохраняют на (а, Ь) противоположные
знаки, то приближения следует начинать слева (рис. 19, 20).
_Пример 1. Найти приближения к л]2, т. е. к положительному корню полинома f = x2 — 2.
Здесь Y — 2х, Y' = 2, так что /' и /" положительны на (0, 4-оо). В качестве начального приближения можно взять любое число, большее д/ 2. В качестве m можно взять 2,8, a M == 2. Поэтому
xk - л/2 < - V27/2.8. В качестве Xq возьмем 3/2. Погрешность Xo не превосходит 0,1. Следующее приближение Xi равно 17/12. Его погрешность не превосходит 0,01/2,8 « 0,003. Следующее приближение X2 равно 577/408. Его погрешность не превосходит 0,0032/2,8 ж 0,000003. Разложение в десятичную дробь дает
577/408== 1,414215...
вместо л/2= 1,414213 ...
Пример 2. Уточнить значение корня полинома f = х3 — х—1, зная, что 1,3 <. X < 1,4.
Здесь f = Зх2 — 1 > 5, Г = 6х < 8,4, M/2т « 0,84 < 1. Начиная с приближения X0= 1,4 с погрешностью меньше 0,1, мы придем к приближению хь погрешность которого меньше 0,01, сле-
Рис. 20.
ПРИБЛИЖЕННОЕ ВЫЧИСЛЕНИЕ КОРНЕЙ ПОЛИНОМА
241
дующее приближение X2 будет иметь погрешность меньше 0,0001, следующее X3 даст 8 верных десятичных знаков после запятой. Посмотрим, как уточняется приближение Jt0 = 1,325 = 53/40, погрешность которого меньше 1/3000. Для него х\ = 180877/136540 (в обыкновенных дробях). Оно приближает корень с точностью до 1/9000000, т. е. с точностью до одной единицы седьмого знака после запятой. В десятичных дробях Х\ = 1,3247180...
Метод Ньютона может применяться и к системам уравнений.
Пример. Решить приближенно систему
X2 -у -1=0, у2 — х — 2 = 0.
Построив графики, найдем приближенно координаты их точки пересечения при положительных X и у. Получим начальное приближение Xo= 1,7, 1/0 = 2. При этом приближении невязка в первом уравнении равна —0,11, во втором 0,3. Положим х= 1,7+ ft, у = S! + к. После подстановки получим
3,4ft + ft2 — k -0,11=0,
-ft + 4fe + fe2 + 0,3 = 0.
Числа ft и k малы. Отбросив их квадраты, получим линейную систему
3,4ft — k —0,11 =0, — ft + 46 + 0,3 = 0,
откуда найдем приближенные значения для ft и k, которые дадут следующее приближение (Х[, у\) к (х, у). Именно, ft = 0,015, k = = —0,059, так что xi = 1,715, ij\ = 1,941. Невязки этого приближения равны 0,000225 и 0,52481, значительно меньше невязок для -хо, г/о.
ГЛАВА X ЭЛЕМЕНТЫ ТЕОРИИ ГРУПП
§ 1. Простейшие сведения
1. Об ассоциативности. Пусть M — множество, в котором определена бинарная операция, сопоставляющая каждой упорядоченной паре а, b элементов из M третий элемент — их «произведение» ab. Из упорядоченной тройки abc элементов из M можно построить два произведения (ab)с и а(Ьс), из четверки а, Ъ, с, d — уже пять: ((ab)c)d, (a(bc))d, (ab)(cd), -a(b(cd)) и a((bc)d), из пятерки элементов — уже 14 и т. д. (Можно доказать, что число осмысленных расстановок скобок в упорядоченной совокупности из п элементов равно (2п —2)!/(«!(«—1)!).) Ассоциативность действия означает, что оба произведения (ab)с и а(Ьс) тройки элементов а, Ь, с равны.
