История и методология прикладной математики. Русанов, Росляков (2004) (1185895), страница 20
Текст из файла (страница 20)
Последовэ тельность (10.11) сходится к корню со скоростью геометриче> ской прогрессии со знаменателем >7. Метод вль-Каши (10.2)' является методом простой итерации и сходится, причем быстро, поскольку у>'(х) = 3хсУР существенно меньше едини-. цы. Выгодно выбирать у>(х) так, чтобы выполнялось условие у'(а) = О.
Такой итерационный процесс называют процессом второго порядка. Если существуют производные высших поряд-': ков и >с>'(а) == у>и(а) = .. >>21~ 0(а) = О, у>1~! ф О, то говорят„: что итерационный процесс (10.11) имеет порядок п!. Функцию у>(х) можно представить в виде р(х) = х — >с>(х)У(х) . Если в качестве >с>(х) взять функцию >с>(х) = 1/У'(х), то получаем итера-: ционный метод Ньютона (10.10).
Если на [а, Ь] У'(х) и У" (х) не-. прерывны и не обращаются в ноль, то у>'(х) = У(х)Ул(х)УУ' (х), ' у>'(а) = 0 и, следовательно, мегод Ньютона — итерационный; процесс второго порядка. Он сходится, если хр достаточно близко к а. Скодимость метода квадратичная: вблизи корня каждая. итерация примерно удваивает чигло верных знаков корня. Так,. как очередное приближение х„+! к корню находится как точ-:, ка пересечения касательной к графику функции У(х) в точке х = хи с осью х, метод Ньютона называют еще методом каса-. тельных.
Еще один употребительный метод получается, если взять у>(х) = х' 6 [а,Ь], У'(х*)Ув(х') ) О. У(х) — У(х') '!а начальное приближение хэ берется произвольная точка от; сзка [а, Ь] такая, что У(хе)У(х') < О. Итерации сходятся, если сс выбирается достаточно близким к корню, когда выполняется ссловие [у>'(х)] < 1, или если Уи(х) не обращается в нуль на а, Ь]. Очередное приближение х„ь! есть абсцисса точки пересе!ения прямой, проходящей через точки (х', У(х')) и (х„, У(х„)), осью х, поэтому метод (10.12) называют методом хорд или .ктодом секущих. Методы простой итерации и Ньютона используются и для рею ния систем нелинейных уравнений.
Особенно широкое ршь пространение получил метод Ньютона при решении самых раз>ичных задач естествознания на ЭВМ. Как правило, определя>ощим фактором при выборе этого метода для решения систем ;>елинейных уравнений, является его быстрая сксдимость и возможность задать хорошее начальное приближение при массовых рэсчетак. С помощью метода Ньютона можно отыскивать и комилексные корни. Когда возникают затруднения с выбором хорошего начального приближения, иногда целесообразно снача>а использовать более грубый лсетод, например, лютод хорд для ;юлучения нескольких первых приближений, а затем уточнить эачение корня методом Ньютона.
Метод (10.10) часто называ>от методом Ньютона-Рафсона. Существуют методы последовательных приближений более высокого порядка, чем метод Ньютона, однако они применяются реже. Иногда используются приемы ускорения скодимости ите-. раций. Здесь мы отметим лишь, что итерационный метод высокого порядка был предложен в 1838 соду П. Л. Чебышевым для пределения корня уравнения У(х) = О. Он основан на представ.сенин фуннции обратной У(х) с помощью формулы Тейлора. Метод Чебышева второго порядка есть метод Ньютона (10.10).
Метод третьего порядка записывается формулой У(х ) У"( ц)У'( ' ) *""' = " У (-.) .У"(*.)— х'У(х„) — х„У(х') У(х„) — У(х') (10.12) Формула (10.11) приобретает вид Одним из употребительных приемов ускорения сходимости эвляется метод, предложенный в 1937 году А. С. Эйткеном. Пусть х„, х„+с, хи.ьз> ... — приближения к корню а, полу>епные методом простой итерации (10.11). В этом случае и >+! и+2 х„— а э> сс!, х„е! — а - с>7 > хи.ьэ - а - сд ( + — х+)' а сн хпьг— хп+г — 2хп+с + хп аг х г= ат ат — Ф ао х ''' ) и ап Пчевидно, уравнение Ь,у" + Ь,р"-'+-,.
+ Ь„= О, 2 Ьо = ао Ьт = аг — 2аоаг, г Ьг = аг — 2ас аз + 2аоас, г 2 Ьп = гь = — х„о (а = 1, 2,..., и). (10.14$ ~хт) » [хг~ >> . >> )х„~, — 96— Исключение отсюда постоянных с и 4 дает Метод Эйткена заключается в вычислении уточненного прибли",. жения по формуле (Хп+2 Хп.~.т) Хп+З = Х +2— хп+г — 2хп+с + х„ 3. Важным классом уравнений являются алгебраические ура» внения с действительными коэффициентами. К решению таки~с уравнений сводится, в частности, задача определения собстветг:;,' ных значений матрицы. Созданием теории алгебраических уран,'; нений и-ой степени, дающей ответ на вопросы о границах распас ложения действительных и комплексных корнем, о числе поло;, жительных и отрицательных корней, о числе корней на задав::,» ном интервале, ученые занимались, начиная с Декарта.
Важньса': теоремы получены Ньютоном, Лагранжем, Гауссом, Штурмом 11 рядом других математиков. Итерационные методы, упомянутые выпсе, конечно, пригодны и для отыскания корней алгебраичос) ских уравнений, однако для них созданы и специфические мего~.: ды, в частности, не требующие знания начальных приближенийкг Изложим вкратце метод Лобачевского-Греффе. Идея методшг и краткое изложение было дано в 1834 году Лобачевским.
Отз '1 был усовершенствован и более подробно описан швейцарскилй математиком Греффе в 1837 году. Детальная разработка была" ! дана немецким астрономом Иоганном Энке в 1841 году. Подроб» ное изложение метода Лобачевского-Греффе с многочисленны,::~ ми примерами, комментариями и уточнениями имеется в первого'; о' фун,наментальном отечественном труде по вычислительной ма 4 тематике академика А.
Н. Крылова "Лекции о приблинсеннысг) вычислениях", опубликованном в 1911 году и неоднократно пе"'-",' реиздававшемся. Идея метода состоит в следующем. Пусть для уравнения г»п(х) = аохп + осх" + ° -. + а„—.— 0 (10.13$ с действительными коэффициентами известно, что все его корнв„'- дейсгвительны и удовлетворяют условию :4 Еогда из формул Виста следует, что с большой точностью будут оыполннться соотношения Если все корни различны, но условие (10.14) не выполняется, Лобачевский использует процеиуру квадрирования, приводяво яют (10.14) сцую к новому уравнению, корни которого удовлетворяют ( О. ) к просто выражаются через корни исходного уравнения (10.13).
Запишем (10.13) в виде ао(х — х,)(х — хг) (х — хп) = 0- ао(х + хд)(х + хг) ..(х + хп) = О имеет корни, противоположные по знаку. Перемножая эти урав- 2 пения и полагая у = — х, получаем уравнение корнялси которого являются числа йь = — хьг, /с =- = — хг, /с=-1,2,... п,а коэффициенты связаны с коэффициентами исходного уравнения формулами Выполнив процесс квадрирования р раз, получаем уравнение сог +ссг~ +'''+с =0 корнями которого служат числа Если р таково, что для гь выполняются условия (10.14), то из формул Виста имеем хь = х *~/ — гь = х *(/сь/с~ Знаки корней определяются, например, подстановкой их в исходное уравнение.
Процесс квадрирования следует прекращать, если коэффициенты являются в пределах заданной точности квадратами соответствующих коэффициентов уравнения, полученного на предыдущем шаге. Метод Лобачевского-Греффе в случае действительных различных корней быстро сходится, Не вносит сложностей наличие одной или двух пар различных комплексных корней. Если число пар комплексных корней больше двух, можно испольэовать алгоритм Энке.
Наиболее неприятный случай — наличие различных комплексных корней с одинаковыми модулямн. В этом случае целесообразно пользоваться модификацией метода Лобачевского, предложенной Д. Леммером, в котором квадрируется уравнение Р„(х — Ь) = О, где Ь вЂ” малое по модулю число. При этом к тому же отпадает необходимость извлекать корни высоких степеней. Для алгебраическихуравнений предназначен иметодБернулли. Этот метод был улучшен и приспособлен для использования на ЭВМ рядом авторов в середине прошлого столетия. Пусть корни хы хг, ..., х„уравнения (10.13) различны.
Запишем разностное уравнение аоуь+» »Ьа1ул+»-г+ . +аеу» = О, г = 0,1,2,.... (10.15) Если ~заветны уо ую . -, уе г, то по (10.15) можно рекуррентно определить у„, затем уь+ы у~+э и т. д. Уравнение (10.13) является характеристическим для (10.15), общее решение которого имеет вид у; = сгх~ + сгхг + ° ° + с„х'„, г = 1, 2, Константы определяются по начальным условиям уо, уы ..., у„ы в выборе которых имеется большой произвол. Если х»вЂ” наибольший по модулю корень (10.13), то у» »ь1 1пп — = хь »-»»о у; Метод Бернулли может быть применен и для вычисления комплексных корней. Ж.
Лагранж в 1767 гцау в мемуаре "О решении численных уравнений" изложил способ нахождения вещественных корней алгебраического уравнения с помощью непрерывных дробей. Рассмотрим положительные корни уравнении с рациональными коэффициентами Ро(х) =.аох"-~-а,х" '+ . +а„=0. (10.16) Б дем считать, что корень уравнения (10.16), который обознаудем ч чим хо, расположен межпу двумя целыми положительными числами Ьо и Ьо+ 1, и других корней на этом интервале нет. Этого всегда можно добиться умножением х в (10.16) на некоторое положительное число.
Представим корень в виде 1 хо = Ьо+ — » х) (10.17) » де х1 — дробь, большая единицы, и подставим в (10.16). Полу- чим уравнение (10.18) Рг(х) =по * +аг * +"'+а 1 х» = Ьг+— хг и подставим в (10.18), тогда получим для хг уравнение Рг(х)»н ао~ ~х" +а1г 1х" 1+ ° ° + а»» = О. Продолжая так далее, получаем разложение корня хо в непре- рывную дробь 1 хо = Ьо+ Ь! + + ° ° Это уравнение имеет только один корень, больший единицы. В противном случае уравнение (10.16) имело бы в промежутке (Ьо, Ьо + 1) более одного корня. Пусть этот корень заключен межпу целыми положительными числами (Ьм Ьг + 1) .
Положим — 98- — 99— Если корень рациональный, то непрерывная дробь обрывается. В этом заключается принципиальное преимущество мето-: об да Лагранжа перед другими методами которые не позвал ют 1 наружить рациональность корня, как бы близко мы к нему не приближались.
Конечно, практически зто возможно, только если все вычисления ведутся с рациональными числами и с достаточным числом знаков. Лагранж указал формулы для. вычисления коэффициентов уравнения Рэ ьэ (х) = 0: а~' ) =,Фьэ) 1 а(гг1) Р1»)(~ ) Ы Р„(с) кэ аэл» + азл» ' + + а„ = О, (10.19) где л = х + 19. В методе спуска уравнение представляется в виде Р„(л) =- и(х,у) +1е(х, р), и вводится функция 1о(иги) > О, обращающаясн в ноль при и = и = 0 и не имеющая других экстремумов. Задача определения корней этого уравнения сводится к определению всех точек минимума функции Р(х,у) = ~р(и(х,р),н(х,у)).
Существует много вариантов метала спуска, отличающихся алгоритмом определения минимума и видом функции ~р(иг е) . Часто используются такие функции: сэ = (и(+ Ц, 1о = -(нэ+ ьэ) 1 Он и редложил также эффективный прием вычисления значения Ььс1 с использованием всех ранее вычисленных Ь, Ь, ... Ь;. 0 ° Г, Ч. В нвчэле 60-х гонов в Институте пряклэдной математики АН СССР была предпрннятв попытка прямым расчетом убедиться в достоверности выскезвнной ранее гипотезы об огрэннченностн неполных честных прн рвзложеннн в непрерывную дробь алгебраического числа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
