Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 31

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 31)

Зачастую само происхождение задачи подсказывает приближенное расположение нулей, и этой информацией можно воспользоваться для начала итераций. При отсутствии таких указаний метод Ньютона часто применяют, исходя из некоего случайного комплексного начального приближения еь В принципе для последовательности (ге) возможны следующие три варианта поведения: х ившеиив нялннвиных гихвнинии 184 1, Она расходится к оо. 2.

Она сходится к нулю г. 3. Она ведет себя хаотически. Для некоторых функций в случае 3 последовательность (гь) в конечном счете переходит в состояние, в котором точки почти зацикливаются с периодом 2,3 или любым другим конечным периодом. Если вам нужен нуль г функции г', то вы можете попробовать применить метод Ньютона, снабженный каким-либо приспособлением, препятствующим слишком большому удалению г„ от гь, в попытке устранить расходимость к о, Затем остается надеяться, что метод сойдется к нулю. Если после достаточно большого числа итераций сходимости нет, то можно начать снова с каким-нибудь другим г,.

Практика показывает, что часто таким образом нуль находится. Пусть был найден один нуль г, и нужен другой, тогда необходим способ воспрепятствовать возвращению последующих итераций к гь Часто бывает полезно продолжать итерационный процесс с новой функцией 1,(г)=— 1 (г) где деление выполняется лишь для числовых значений )(г) и г — г,. Основной член в методе Ньютона — отношение )(г)//'(х); обратная к нему величина есть 1'(г)/~(г)=(4Мг) 1п1"(г). Поэтому 1' (г) — — — 1п 1 (а) — — 1и (х — г,) —,П~х) После того как были найдены з корней, алгоритм Ньютона применяют к функции 1(г))П1,(г — г„) и по-прежнему логарифмическое дифференцирование в принципе производится легко, Если прямое применение алгоритмов Ньютона или секущих не приводит к успеху, то, видимо, следует предпослать им какой- нибудь метод приближения к нулю.

Одна из возможностей— использовать алгоритм для минимизации действительной функции двух действительных переменных х и у в применении к функции ф(х, у)=1~(х+(у)1', Легко доказать, что для аналитической функции ~ все локальные минимумы функции ч~(х, р) соответствуют случаю ~р=-О. Методы минимизации обсуждаются в гл. 8. Широко используемый метод для нахождения нулей аналитической функции комплексного переменного принадлежит Мюллеру. Это обобщение метода секущих с двух интерполяциоиных точек на три Мюллер начинает с произвольных чисел гь х, н з з, нкли полиномоа 185 з,.

В общем случае имеются три точки г, „г„, и г„и соответствующие значения функции, которые обозначим через („.„ и г"„. Мюллер составляет (единственную) квадратичную функцию от гь интерполнрующую три точки (г„)';), где (=-п — 2, а — 1, и. В качестве г„„, затем берется тот из двух нулей квадратичной функции, который ближе к г„. Далее это же повторяется зв-1 зи и зал 1 Исходной мотивировкой Мюллера для этого метода было то обстоятельство, что использование квадратичного многочлена позволяет процессу вычисления нуля переходить от первоначальных действительных итераций к последующим комплексным в отличие от методов Ньютона и секущих. Впоследствие он обнаружил, что метод хорошо работает н при нахождении действительных корней. УА.

Нули полииомов Вследствие того что полиномы являются весьма специальными функциями, можно понять наличие множества алгоритмов для вычисления их нулей. Некоторые из ннх принадлежат к числу старейших алгоритмов численного анализа. С минувших столетий ведут свое происхождение методы Гориера, Греффе и Бернулли; в вычислительную эпоху созданы методы Рутисхаузера, Лемера, Лина, Бэрстоу (Ва(гз(оц), Бэрайсса (Ваге(аа) и другие. С математической точки зрения большой теоретический интерес представляет создание алгоритмов, для которых можно было бы доказать гарантированную сходимость, хотя бы в обманчивых рамках действительной арифметики.

С точки зрения практической имеется потребность в алгоритмах, которые бы почти всегда работалн и вычисляли каждый нуль за малые доли секунды, если полипом умеренного порядка, а машина достаточно мощная. По сравнению с трансцендентными функциями полиномы имеют то преимущество, что наперед известно точное число их корней и, следовательно, известно, когда нужно остановить алгоритм. Читатель должен припомнить крайнюю неустойчивость корней некоторых полиномов как функций от их коэффициентов (Э 2.5). Это значит, что многие задачи, включающие в себя нахождение нулей полиномов, требуют либо предельно точного вычисления коэффициентов, либо совершенно иного подхода. Например, 20 нли 30 лет назад считалось, что наиболее естественный путь вычисления собственных значений матрицы состоит в построении, а затем решении характеристического уравнения.

е Решение нелинейных уРлвненип 1ва В настоящее время известны гораздо лучшие способы получения собственных значений — способы, которые не требуют проведения вычислений в арифметике очень аысокон точности (гл. 9). Вероятно, и многие другие задачи, где используются полиномы, должны решаться иначе. Таким образом, возможно, что нахождение нулей полиномов уже не является столь важной частью научных вычислений, как это было до сих пор. Авторы имеют лишь небольшой опыт работы с фортран-программами для этой задачи; однако полагают, что метод Мюллера вполне хорош во многих приложениях.

Быстрая и надежная фортран-программа для нахождения нулей полиномов с комплексными коэффициентами приведена в статье Дженкинс, Трауб (1972). 7.5. Нелинейные системы уравнений Очень распространенной вычислительной задачей является нахождение некоторых или всех решений системы из и нелинейных алгебраических или трансцендентных уравнений с и неизвестными. Обозначая через х вектор-столбец (х„..., х„)', можно записать уравнения в виде: 1, (х) =О, 7, (х) =О,..., 1"„(х)=О. Или, вводя для вектора-столбца функций (7И..., 7„)г обозначение 1, можем записать всю систему в компактной форме 1(х) =О.

Подобные системы уравнений могут возникать непосредственно, например при конструировании нелинейных физических систем, а могут получаться опосредованно. К примеру, пытаясь минимизировать функцию б(х), можно попробовать найти те точки, где градиент этой функции равен нулю.

Полагая (=ягаб б, получаем нелинейную систему. Один из подходов к решению системы 1(х)=0 состоит в обобщении на размерность и итерационных процессов, полезных при решении единственного уравнения (случай и= — 1). Если могут быть вычислены все частные производные функций 7; по переменным хп то можно применить процесс Ньютона. Пусть l (х) обозначает матрицу Якоби; ее элемент (1, 1) есть значение производной д);/дх7 в точке х.

Как и в одномерном случае, метод Ньютона начинает с произвольного х, скажем х'. Далее, функцию 1 линеаризуют в точке х", разлагая ее в ряд Тейлора и удерживая лишь члены нулевой и первой степени: 1(х) — — 1(х')+ з'(х') (х — х')+.... Линейное приближение к 1 около х' задается, следовательно, формулой 1.

(х) =1(х')+,Р(х — х"), где 7Π— сокращенное обозначение для /(х'). Т.х нелинеиные системы уРАВнениЙ 187 Чтобы найти следующее приближение х к решению системы 1(х)=0, решают уравнение 1 (х') +.(о(х' — х') = О. Разумеется, решение можно записать в форме х'= х' — (7О)-'1(х'); в этом виде формула сильно напоминает одномерную форму метода Ньютона. Однако для большинства систем нз п линейных уравнений с и неизвестными вычисление обратной матрицы (Р)-' не является ни необходимым, ни даже желательным; предпочтительней как раз решать линейную систему относительно поправки х' — х'. В общем случае, имея хь, находят х"+' прибавлением к х" поправки х"-'' — х", полученной решением линейной системы 1" (х'"' — х') = — 1(хэ). Для такого итерационного процесса можно доказать теорему, аналогичную первой теореме й 7.1. Сформулируем ее неформально.

Пусть г — решение системы 1(х)=0, такое, что l(г) ие вырождена и вторые частные производные функции 1 непрерывны вблизи г. Тогда, если х'. достаточно близко к г, то пьютоновы итерации будут сходиться. Более того, для е"=хА--г при й сс отношение (1е""1И1е"й2 ограничено. Таким образом, сходимость будет порядка 2. Как и в одномерном случае, основная проблема в том, чтобы подойти достаточно близко к желаемому корню г, чтобы могла начаться быстрая сходимость. На практике можно подчас, итерируя с мужеством и оптимизмом, найти корень без особых трудностей.

Характеристики

Список файлов книги