Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 40
Текст из файла (страница 40)
На практике для достижения разумной точности е при выборе достаточно хорошего начального приближения х< о' требуется, как правило, 3 — 5 итераций. Однако при оценке общей трудоемкости метода следует учитывать, что на каждой итерации требуется выполнение следующей дополнительной работы: 1) вычисление ти компонент вектора ~(х~ "~ ); 2) вычисление лтт компонент матрицы Якоби 1'(х' "'); 3) решение системы линейных алгебраических уравнений (7.16). Существует большое число модификаций метода Ньютона, позволяющих в тех или иных ситуациях снизить его трудоемкость либо избежать необходимости вычисления производных.
Рассмотрим кратко некоторые из таких модификаций, учитывая, что их одномерные налоги были изучены более подробно в 3 4.7. 204 Упро<цениый метод Ньютона. Заменим в расчетных формулах метода Ньютона (7,16), (7.17) матрицу ~'(х<п)), зависящую от п, пос,оянной матрицей А = ~'(х<~) ). В результате получим расчетные фор— „улы упрощенно<о метода Нь)отона: А~х< и+1) — ~(х< и) ) х< ') = х' и' + Ьх< и") . (7.19) (7.20) точно близким к решению х, причем знаменатель прогрессии <7 тем меньше, чем ближе х'о) к х.
По сравнению с методом Ньютона число итераций, необходимое для достижения заданной точности я, существенно возрастает. Тем не менее общие вычислительные затраты могут оказаться меньше. Причины этого состоят в следующем. Во-первых, вычисление матрицы Якоби производится здесь только один раз; во-вторых, как нетрудно видеть, при использовании упрощенного метода Ньютона (7.19), (7.20) многократно решается система линейных уравнений с фиксированной матрицей А и различными правыми частями. Это означает, что при решении систем (7.19) методом Гаусса возможно применение Ь~1 — разложения матрицы А, которое резко уменьшает число операций, необходи- МЫХ дЛя ВЫЧИСЛЕНИЯ ЬХ<п'1) (СМ. ГЛ.
5). 2. Использование формул численного дифференцирования. ДовольдЛ по часто вычисление производных, являющихся элементами дх)' матрицы у, затруднено или вообще невозможно. В такой ситуации для приближенного вычисления производных можно попытаться использовать формулы численного дифференцирования (см. гл. 12). Например, можно использовать следующую конечно-разностную аппроксимацию производной: д<< ' (х<п)) н 7<п) — (1(х<п) х<п) х<п) + а<п) <и) х<п)) 1 д ху ))<и) 1 1 ' "' )-1' )+1) '''! щ 1 Дх<п) х<п) )) Параметры Ь<.п) Х 0 Ц = 1, 2, ..., т) — это конечно-раэностные <иа<«. 205 Можно показать, что этот метод сходится со скоростью геометрической прогрессии, если начальное приближение х<о) выбрано доста- Если в расчетных формулах метода Ньютона (7.16), (7.17) заменить матрицу ~'(ю~ ">) аппроксимирущей ее матрицей Р"' с элементами У',.М, то получим следующий итерационный метод: у и),л,х< о+и ~(х( и) ) (7.22) (7.23) я~ ~~ы = я~ ~~~ + Ь~~ и+ы .
В простейшем варианте этого метода шаги Ьу ( 1 = 1, 2, ..., ш) не зависят от и. Отметим, что выбор величины шагов представляет собой не очень простую задачу. С одной стороны, они должны быть достаточно малыми, чтобы матрица У "1 хорошо приближала матрицу У'(~'"'), с другой, они не могут быть очень малы, так как в этом случае влияние погрешностей вычисления функций ~~ на погрешность формулы (7.21) численного дифференцирования становится катастрофическим (выполняется вычитание близких приближенных чисел).
Следующие три метода можно рассматривать как варианты метода (7.22), (7.23), в которых реализованы специальные подходы к вычислению вектора Л~ "~ = (Ь< ">, Ь'"', ..., Ь~~ ">)т. Для того чтобы приведен- р = (~5 + 1)~2. 5. Метод Сгеффенсена. Вычисления по лстиоду Стсффсясена производят по формулам (7.21) — (7.23), где Л~"' = ~(а4 ">). Замечательно то, что хотя этот метод не требует вычисления произ- 206 ные ниже рассуждения были формально корректными, в формуле дД (7.21) положим У',.".> = — '(х~ ">), если оказалось, что Ьга> = О. ~1 3.
Метод ложного положения. Пусть с — фиксированный вектор. Положим Л~ "> = с - х< ">. Тогда формулы (7.21) — (7.23) определяют лстиод яожноьо положения, обладающий линейной скоростью сходимости в случае, если вектор с и начальное приближение к~э' выбраны достаточно близко к решению. 4. Метод секущих. В одном из наиболее популярных своих вариантов метод ссжуи1ш можно рассматривать как метод (7.21) — (7.23), где Л~'~1 = х~" ы — в~ "~. Метод секущих является двухшаговым: для вычисления очередного приближения х( "'Ы используют два предыдущих приближения а~ "1 и х~" ы. Для того чтобы начать вычисления, необходимо задать два начальных приближения в'® и а<".
При удачном выборе начальных приближений к~о> и ю~ы метод секущих сходится со сверхлинейной скоростью с порядком сходимости водных и в отличие от метода секущих является одношаговым, он, как и метод Ньютона, обладает свойством квадратичной сходимости. Правда, как и в методе Ньютона, его применение затруднено необходимостью выбора хорошего начального приближения. По-видимому. для решения нелинейных систем вида (7.1) метод Стеффенсена чаще окажется лучшим выбором, чем метод секущих или метод ложного положения. Как и в одномерном случае (см.
Э 4.7), следует отметить, что методы секущих и Стеффенсена теряют устойчивость вблизи решения (фактически это происходит при попадании приближения х'"' в область неопределенности решения х). Поэтому при использовании этих методов важно вовремя прекратить выполнение итераций. ~ 7.5. О некоторых подходах к решению задач локализации и отыскания решений систем нелинейных уравнений Подчеркнем еще раз, что одной из наиболее трудных проблем, возникающих при решении систем нелинейных уравнений, является задача локализации решения.
Изложим некоторые подходы к ее решению, широко применяемые в практике вычислений. Указанные методы можно применять и для вычисления решения с заданной точностью е. 1. Использование методов минимизации. Иногда бывает полезно свести задачу отыскания решения системы нелинейных уравнений к задаче отыскания минимума функции многих переменных. В простейшем варианте это сведение выглядит следующим образом.
Введем функцию Ф (х) = Е Ц(х))~. Она неотрицательна и достигает своего (=1 минимума (равного нулю) тогда и только тогда, когда Д(х) = О для всех 1 = 1, 2, ..., т, т.е. х является решением системы (7.1). Применяя для отыскания минимума функции Ф один из итерационных методов минимизации — методов спуска (см, гл. 10), можно найти вполне удовлетворительное приближение к решению х, которое затем имеет смысл использовать как начальное приближение х<о~ в одном из итерационных методов решения нелинейных систем.
Выгода от указанного сведения исходной задачи к задаче минимизации состоит в том, что, как правило, методы спуска имеют более широкую область сходимости. Использование методов спуска можно Рассматривать и как один из способов локализации решений системы (7 1).
Применение на заключительном этапе методов, специально ори- 207 ентираванных на решение нелинейных систем, вызвано тем, что вблизи искомого решения методы спуска сходятся медленее. Следует отметить, что функция Ф (х) может иметь и ненулевые локальные минимумы, и в зависимости от выбора начального приближения методы спуска могут приводить к точкам локального минимума, не являющимися решениями системы (7.1). Пример 7.4. Решения системы (7.4) являются точками глобального минимума функции Ф (хп хх) = (х1 + х~ — 8х1х~)~ + (х1!п х~ — х~1п х1)~. з з 2.
Метод продолжения по параметру Сначала заметим, что довольно часто на практике встречаются ситуации, когда система нелинейных уравнений естественным образом зависит от некоторого параметра 1, т.е. имеет вид ~(х,1) =О, (7.24) а решение ее следует найти при некотором фиксированном значении параметра, например при 1 = 1. В частности, этим свойством обладает система из примера 7.1. Предположим, что при каждом 1Е~О, 1] система (7.24) имеет решение х = х (~), непрерывно зависящее от параметра 1, причем при 1 = 0 решение системы ~(х, 1) = 0 известно либо легко вычисляется. Таким образом, семейство решений х (1) описывает в пространстве Ю" траекторию, начальная точка х(0) которой известна, а конечная х(1) подлежит определению (рис. 7.5). „аю- 1)-х(й„) хф=х(~,1 х'"= хГО) Рис Х6 208 И в тех случаях, когда система не зависит от параметра, можно ввести параметр $ так, чтобы были выполнены указанные выше условия. Например, если х* — известное приближение к решению системы ~(в) = О, то можно рассмотреть систему вида (7.24), полагая ~(в, 1) = — У(я) — (1 - ~)У(я').
Введем на отрезке [О, 1~ набор точек 0 = ~о < 11 < ... < 1,т = 1. Используя тот или иной итерационный метод, решим последовательно для й = О, 1, 2, ..., Ф системы у(х, ~~) = О. При этом за начальное приближение к я (1~) будем принимать решение х (Ц 1). Если разность ~~ — 1~1 достаточно мала, то можно ожидать, что а (1~ 1) будет доста- точно хорошим начальным приближением к я (~~), обеспечивающим сходимость используемого итерационного метода. 3 а м е ч а н и е. Довольно часто на практике проводится исследование зависимости определенных характеристик объекта от некоторого параметра 1. Для таких задач метод продолжения естествен.
Более того, точки 1с, 11, ..., 1у можно выбрать, используя дополнительные соображения, причем решение я (1~) представляет интерес не только для 1 = У, но и для всех й = О, 1, ..., Ф. 3. Метод дифференцирования по параметру. Предположим, что решение х (1) системы (7.24) является гладкой функцией параметра 1. Дифференцируя тождество 7 (я (1), 1) = О по 1, получим Здесь ~' (х, М) — матрица с элементами — (я, М) (з, 1' = 1, 2, ..., т), а д,~, У~ (в, 1) — вектор-столбец с элементами — (х, 1) (г' = 1, 2, ..., т). Таким дЯ образом, если матрица ~' невырождена (ее~ ~ ~ 0), то х (~) является решением задачи Коши для системы обыкновенных дифференциальных уравнений (7.25) Интересующее нас значение решения х (1) можно теперь найти приближенно, применяя численные методы решения задачи Коши.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
